Model selection for contextual bandits

Abstract

We introduce the problem of model selection for contextual bandits, where a learner must adapt to the complexity of the optimal policy while balancing exploration and exploitation. Our main result is a new model selection guarantee for linear contextual bandits. We work in the stochastic realizable setting with a sequence of nested linear policy classes of dimension $d_1<d_2<\dots$, where the $m^{\star }$-th class contains the optimal policy, and we design an algorithm that achieves $\tilde{O}(T^{2/3}{d}_{m^{\star }}^{1/3})$ regret with no prior knowledge of the optimal dimension $d_{m^{\star }}$. The algorithm also achieves regret $\tilde{O}(T^{3/4}+\sqrt{T{d}_{m^{\star }}})$, which is optimal for $d_{m^{\star }}\ge \sqrt{T}$. This is the first model selection result for contextual bandits with non-vacuous regret for all values of $d_{m^{\star }}$, and to the best of our knowledge is the first positive result of this type for any online learning setting with partial information. The core of the algorithm is a new estimator for the gap in the best loss achievable by two linear policy classes, which we show admits a convergence rate faster than the rate required to learn the parameters for either class.

References in corpus (5)

• Variance estimation in nonparametric regression via the difference sequence method
• Contextual Bandit Learning with Predictable Rewards
• A New Algorithm for Non-stationary Contextual Bandits: Efficient, Optimal, and Parameter-free
• Simultaneous Model Selection and Optimization through Parameter-free Stochastic Learning
• OSOM: A simultaneously optimal algorithm for multi-armed and linear contextual bandits

Cited by in corpus (16)

• Beyond UCB: Optimal and Efficient Contextual Bandits with Regression Oracles
• Hedging the Drift: Learning to Optimize under Non-Stationarity
• Model Selection in Contextual Stochastic Bandit Problems
• Minimax Regret for Stochastic Shortest Path with Adversarial Costs and Known Transition
• Sample Complexity of Reinforcement Learning using Linearly Combined Model Ensembles
• OSOM: A simultaneously optimal algorithm for multi-armed and linear contextual bandits
• A Model Selection Approach for Corruption Robust Reinforcement Learning
• Corralling Stochastic Bandit Algorithms
• Efficient and Robust Algorithms for Adversarial Linear Contextual Bandits
• Online Model Selection for Reinforcement Learning with Function Approximation
• Thompson Sampling with a Mixture Prior
• Tractable contextual bandits beyond realizability
• Pareto Optimal Model Selection in Linear Bandits
• Confidence-Budget Matching for Sequential Budgeted Learning
• Universal and data-adaptive algorithms for model selection in linear contextual bandits
• Near Instance Optimal Model Selection for Pure Exploration Linear Bandits