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

Abstract

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.

arXiv comment57 pages

References in corpus (7)

• A Contextual-Bandit Approach to Personalized News Article Recommendation
• Provably Efficient Reinforcement Learning with Linear Function Approximation
• Learning Near Optimal Policies with Low Inherent Bellman Error
• Model Selection in Contextual Stochastic Bandit Problems
• Adapting to Misspecification in Contextual Bandits
• Regret Balancing for Bandit and RL Model Selection
• Rate-adaptive model selection over a collection of black-box contextual bandit algorithms

Cited by in corpus (9)

• Non-stationary Reinforcement Learning without Prior Knowledge: An Optimal Black-box Approach
• Tactical Optimism and Pessimism for Deep Reinforcement Learning
• Model-free Representation Learning and Exploration in Low-rank MDPs
• Leveraging Good Representations in Linear Contextual Bandits
• Provably Efficient Representation Selection in Low-rank Markov Decision Processes: From Online to Offline RL
• A Model Selection Approach for Corruption Robust Reinforcement Learning
• Improved Algorithms for Misspecified Linear Markov Decision Processes
• Pareto Optimal Model Selection in Linear Bandits
• Universal and data-adaptive algorithms for model selection in linear contextual bandits