Regret Balancing for Bandit and RL Model Selection
This work addresses the challenge of selecting the best learning algorithm adaptively in online decision-making problems, but it is incremental as it builds on prior model selection strategies with a specific focus on regret balancing.
The paper tackles the problem of model selection in stochastic bandit and reinforcement learning by proposing a regret balancing strategy that adapts to the best base algorithm online, achieving a regret close to the optimal base algorithm's regret, with performance depending on the tightness of an input upper bound.
We consider model selection in stochastic bandit and reinforcement learning problems. Given a set of base learning algorithms, an effective model selection strategy adapts to the best learning algorithm in an online fashion. We show that by estimating the regret of each algorithm and playing the algorithms such that all empirical regrets are ensured to be of the same order, the overall regret balancing strategy achieves a regret that is close to the regret of the optimal base algorithm. Our strategy requires an upper bound on the optimal base regret as input, and the performance of the strategy depends on the tightness of the upper bound. We show that having this prior knowledge is necessary in order to achieve a near-optimal regret. Further, we show that any near-optimal model selection strategy implicitly performs a form of regret balancing.