Adapting to Misspecification in Contextual Bandits with Offline Regression Oracles
arXiv:2102.13240
Abstract
Computationally efficient contextual bandits are often based on estimating a predictive model of rewards given contexts and arms using past data. However, when the reward model is not well-specified, the bandit algorithm may incur unexpected regret, so recent work has focused on algorithms that are robust to misspecification. We propose a simple family of contextual bandit algorithms that adapt to misspecification error by reverting to a good safe policy when there is evidence that misspecification is causing a regret increase. Our algorithm requires only an offline regression oracle to ensure regret guarantees that gracefully degrade in terms of a measure of the average misspecification level. Compared to prior work, we attain similar regret guarantees, but we do no rely on a master algorithm, and do not require more robust oracles like online or constrained regression oracles (e.g., Foster et al. (2020a); Krishnamurthy et al. (2020)). This allows us to design algorithms for more general function approximation classes.
arXiv commentICML 2021
References in corpus (11)
- 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
- Efficient Optimal Learning for Contextual Bandits
- Practical Contextual Bandits with Regression Oracles
- Beyond UCB: Optimal and Efficient Contextual Bandits with Regression Oracles
- Model Selection in Contextual Stochastic Bandit Problems
- Instance-Dependent Complexity of Contextual Bandits and Reinforcement Learning: A Disagreement-Based Perspective
- Adapting to Misspecification in Contextual Bandits
- Upper Counterfactual Confidence Bounds: a New Optimism Principle for Contextual Bandits
- Tractable contextual bandits beyond realizability