Tractable contextual bandits beyond realizability
arXiv:2010.13013
Abstract
Tractable contextual bandit algorithms often rely on the realizability assumption - i.e., that the true expected reward model belongs to a known class, such as linear functions. In this work, we present a tractable bandit algorithm that is not sensitive to the realizability assumption and computationally reduces to solving a constrained regression problem in every epoch. When realizability does not hold, our algorithm ensures the same guarantees on regret achieved by realizability-based algorithms under realizability, up to an additive term that accounts for the misspecification error. This extra term is proportional to T times a function of the mean squared error between the best model in the class and the true model, where T is the total number of time-steps. Our work sheds light on the bias-variance trade-off for tractable contextual bandits. This trade-off is not captured by algorithms that assume realizability, since under this assumption there exists an estimator in the class that attains zero bias.
arXiv comment35 pages, 6 figures
References in corpus (13)
- A Contextual-Bandit Approach to Personalized News Article Recommendation
- Thompson Sampling for Contextual Bandits with Linear Payoffs
- Taming the Monster: A Fast and Simple Algorithm for Contextual Bandits
- Contextual Bandit Algorithms with Supervised Learning Guarantees
- Efficient Optimal Learning for Contextual Bandits
- Nonparametric Bandits with Covariates
- Making Contextual Decisions with Low Technical Debt
- What is Local Optimality in Nonconvex-Nonconcave Minimax Optimization?
- Learning Near Optimal Policies with Low Inherent Bellman Error
- Practical Contextual Bandits with Regression Oracles
- Model selection for contextual bandits
- Model Selection in Contextual Stochastic Bandit Problems
- Adapting to Misspecification in Contextual Bandits