# Regret Balancing for Bandit and RL Model Selection

arXiv: https://arxiv.org/abs/2006.05491 · HTML: https://mlsanity.com/paper/2006.05491/

## Key facts

- Cited by 20 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 9 Jun 2020.

## Built on by (most cited first, 20 of 20)

- [Non-stationary Reinforcement Learning without Prior Knowledge: An Optimal Black-box Approach](https://mlsanity.com/paper/2102.05406/) (2021)
- [Unpacking Reward Shaping: Understanding the Benefits of Reward Engineering on Sample Complexity](https://mlsanity.com/paper/2210.09579/) (2022)
- [A Model Selection Approach for Corruption Robust Reinforcement Learning](https://mlsanity.com/paper/2110.03580/) (2021)
- [A Blackbox Approach to Best of Both Worlds in Bandits and Beyond](https://mlsanity.com/paper/2302.09739/) (2023)
- [Leveraging Good Representations in Linear Contextual Bandits](https://mlsanity.com/paper/2104.03781/) (2021)
- [Stochastic Rising Bandits](https://mlsanity.com/paper/2212.03798/) (2022)
- [Pareto Optimal Model Selection in Linear Bandits](https://mlsanity.com/paper/2102.06593/) (2021)
- [Provably Efficient Representation Selection in Low-rank Markov Decision Processes: From Online to Offline RL](https://mlsanity.com/paper/2106.11935/) (2021)
- [Best of Both Worlds Model Selection](https://mlsanity.com/paper/2206.14912/) (2022)
- [Data-Driven Online Model Selection With Regret Guarantees](https://mlsanity.com/paper/2306.02869/) (2023)
- [Time-Varying Gaussian Process Bandits with Unknown Prior](https://mlsanity.com/paper/2402.01632/) (2024)
- [Bayesian Optimisation with Unknown Hyperparameters: Regret Bounds Logarithmically Closer to Optimal](https://mlsanity.com/paper/2410.10384/) (2024)
- [Feature and Parameter Selection in Stochastic Linear Bandits](https://mlsanity.com/paper/2106.05378/) (2021)
- [Scalable Representation Learning in Linear Contextual Bandits with Constant Regret Guarantees](https://mlsanity.com/paper/2210.13083/) (2022)
- [Neural Pseudo-Label Optimism for the Bank Loan Problem](https://mlsanity.com/paper/2112.02185/) (2021)
- [On the Complexity of Representation Learning in Contextual Linear Bandits](https://mlsanity.com/paper/2212.09429/) (2022)
- [Rising Rested Bandits: Lower Bounds and Efficient Algorithms](https://mlsanity.com/paper/2411.14446/) (2024)
- [Adaptive Prior Selection in Gaussian Process Bandits with Thompson Sampling](https://mlsanity.com/paper/2502.01226/) (2025)
- [Model Selection for Average Reward RL with Application to Utility Maximization in Repeated Games](https://mlsanity.com/paper/2411.06069/) (2024)
- [Nonstochastic Bandits with Infinitely Many Experts](https://mlsanity.com/paper/2102.05164/) (2021)

## Abstract (arXiv)

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.