# Regret Bound Balancing and Elimination for Model Selection in Bandits and RL

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

## Key facts

- Cited by 47 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 24 Dec 2020.

## Built on by (most cited first, 30 of 47)

- [Non-stationary Reinforcement Learning without Prior Knowledge: An Optimal Black-box Approach](https://mlsanity.com/paper/2102.05406/) (2021)
- [Model-free Representation Learning and Exploration in Low-rank MDPs](https://mlsanity.com/paper/2102.07035/) (2021)
- [Unpacking Reward Shaping: Understanding the Benefits of Reward Engineering on Sample Complexity](https://mlsanity.com/paper/2210.09579/) (2022)
- [Tactical Optimism and Pessimism for Deep Reinforcement Learning](https://mlsanity.com/paper/2102.03765/) (2021)
- [Misspecified Gaussian Process Bandit Optimization](https://mlsanity.com/paper/2111.05008/) (2021)
- [A Model Selection Approach for Corruption Robust Reinforcement Learning](https://mlsanity.com/paper/2110.03580/) (2021)
- [Provable Benefits of Representational Transfer in Reinforcement Learning](https://mlsanity.com/paper/2205.14571/) (2022)
- [Leveraging Good Representations in Linear Contextual Bandits](https://mlsanity.com/paper/2104.03781/) (2021)
- [The Pareto Frontier of model selection for general Contextual Bandits](https://mlsanity.com/paper/2110.13282/) (2021)
- [Neural Active Learning with Performance Guarantees](https://mlsanity.com/paper/2106.03243/) (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)
- [Exploration in Linear Bandits with Rich Action Sets and its Implications for Inference](https://mlsanity.com/paper/2207.11597/) (2022)
- [Model Selection for Generic Contextual Bandits](https://mlsanity.com/paper/2107.03455/) (2021)
- [Bayesian Optimisation with Unknown Hyperparameters: Regret Bounds Logarithmically Closer to Optimal](https://mlsanity.com/paper/2410.10384/) (2024)
- [Improved Algorithms for Misspecified Linear Markov Decision Processes](https://mlsanity.com/paper/2109.05546/) (2021)
- [Neural Design for Genetic Perturbation Experiments](https://mlsanity.com/paper/2207.12805/) (2022)
- [Feature and Parameter Selection in Stochastic Linear Bandits](https://mlsanity.com/paper/2106.05378/) (2021)
- [Towards Costless Model Selection in Contextual Bandits: A Bias-Variance Perspective](https://mlsanity.com/paper/2106.06483/) (2021)
- [Universal and data-adaptive algorithms for model selection in linear contextual bandits](https://mlsanity.com/paper/2111.04688/) (2021)
- [Breaking the √T Barrier: Instance-Independent Logarithmic Regret in Stochastic Contextual Linear Bandits](https://mlsanity.com/paper/2205.09899/) (2022)
- [Joint Representation Training in Sequential Tasks with Shared Structure](https://mlsanity.com/paper/2206.12441/) (2022)
- [Adaptation to Misspecified Kernel Regularity in Kernelised Bandits](https://mlsanity.com/paper/2304.13830/) (2023)
- [Experiment Planning with Function Approximation](https://mlsanity.com/paper/2401.05193/) (2024)
- [Reinforcement Learning in the Real World: A Survey of Statistical Challenges and Future Directions](https://mlsanity.com/paper/2601.15353/) (2026)
- [Multitask Learning with No Regret: from Improved Confidence Bounds to Active Learning](https://mlsanity.com/paper/2308.01744/) (2023)

## Abstract (arXiv)

We propose a simple model selection approach for algorithms in stochastic bandit and reinforcement learning problems. As opposed to prior work that (implicitly) assumes knowledge of the optimal regret, we only require that each base algorithm comes with a candidate regret bound that may or may not hold during all rounds. In each round, our approach plays a base algorithm to keep the candidate regret bounds of all remaining base algorithms balanced, and eliminates algorithms that violate their candidate bound. We prove that the total regret of this approach is bounded by the best valid candidate regret bound times a multiplicative factor. This factor is reasonably small in several applications, including linear bandits and MDPs with nested function classes, linear bandits with unknown misspecification, and LinUCB applied to linear bandits with different confidence parameters. We further show that, under a suitable gap-assumption, this factor only scales with the number of base algorithms and not their complexity when the number of rounds is large enough. Finally, unlike recent efforts in model selection for linear stochastic bandits, our approach is versatile enough to also cover cases where the context information is generated by an adversarial environment, rather than a stochastic one.