Model Selection in Contextual Stochastic Bandit Problems

Abstract

We study bandit model selection in stochastic environments. Our approach relies on a meta-algorithm that selects between candidate base algorithms. We develop a meta-algorithm-base algorithm abstraction that can work with general classes of base algorithms and different type of adversarial meta-algorithms. Our methods rely on a novel and generic smoothing transformation for bandit algorithms that permits us to obtain optimal $O(\sqrt{T})$ model selection guarantees for stochastic contextual bandit problems as long as the optimal base algorithm satisfies a high probability regret guarantee. We show through a lower bound that even when one of the base algorithms has $O(\log T)$ regret, in general it is impossible to get better than $\Omega (\sqrt{T})$ regret in model selection, even asymptotically. Using our techniques, we address model selection in a variety of problems such as misspecified linear contextual bandits, linear bandit with unknown dimension and reinforcement learning with unknown feature maps. Our algorithm requires the knowledge of the optimal base regret to adjust the meta-algorithm learning rate. We show that without such prior knowledge any meta-algorithm can suffer a regret larger than the optimal base regret.

33 main pages, 15 appendix pages

References in corpus (3)

• The best of both worlds: stochastic and adversarial bandits
• Learning Near Optimal Policies with Low Inherent Bellman Error
• Learning with Good Feature Representations in Bandits and in RL with a Generative Model

Cited by in corpus (17)

• Tactical Optimism and Pessimism for Deep Reinforcement Learning
• Regret Bound Balancing and Elimination for Model Selection in Bandits and RL
• Adapting to Misspecification in Contextual Bandits with Offline Regression Oracles
• Corralling Stochastic Bandit Algorithms
• Provably Efficient Representation Selection in Low-rank Markov Decision Processes: From Online to Offline RL
• Online Model Selection for Reinforcement Learning with Function Approximation
• Linear Contextual Bandits with Adversarial Corruptions
• Upper Confidence Bounds for Combining Stochastic Bandits
• Tractable contextual bandits beyond realizability
• Rate-adaptive model selection over a collection of black-box contextual bandit algorithms
• Smooth Bandit Optimization: Generalization to Hölder Space
• Human-AI Collaboration with Bandit Feedback
• Pareto Optimal Model Selection in Linear Bandits
• Multitask Bandit Learning Through Heterogeneous Feedback Aggregation
• Near Instance Optimal Model Selection for Pure Exploration Linear Bandits
• Neural Active Learning with Performance Guarantees
• Online Model Selection: a Rested Bandit Formulation