Taking a hint: How to leverage loss predictors in contextual bandits?
arXiv:2003.01922
Abstract
We initiate the study of learning in contextual bandits with the help of loss predictors. The main question we address is whether one can improve over the minimax regret for learning over rounds, when the total error of the predictor is relatively small. We provide a complete answer to this question, including upper and lower bounds for various settings: adversarial versus stochastic environments, known versus unknown , and single versus multiple predictors. We show several surprising results, such as 1) the optimal regret is when is known, a sharp contrast to the standard and better bound for non-contextual problems (such as multi-armed bandits); 2) the same bound cannot be achieved if is unknown, but as a remedy, is achievable; 3) with predictors, a linear dependence on is necessary, even if logarithmic dependence is possible for non-contextual problems. We also develop several novel algorithmic techniques to achieve matching upper bounds, including 1) a key action remapping technique for optimal regret with known , 2) implementing Catoni's robust mean estimator efficiently via an ERM oracle leading to an efficient algorithm in the stochastic setting with optimal regret, 3) constructing an underestimator for via estimating the histogram with bins of exponentially increasing size for the stochastic setting with unknown , and 4) a self-referential scheme for learning with multiple predictors, all of which might be of independent interest.
References in corpus (13)
- Taming the Monster: A Fast and Simple Algorithm for Contextual Bandits
- Contextual Bandit Algorithms with Supervised Learning Guarantees
- Online Learning with Predictable Sequences
- Optimization, Learning, and Games with Predictable Sequences
- Efficient Optimal Learning for Contextual Bandits
- Fast Convergence of Regularized Learning in Games
- More Adaptive Algorithms for Adversarial Bandits
- Efficient Algorithms for Adversarial Contextual Learning
- A New Algorithm for Non-stationary Contextual Bandits: Efficient, Optimal, and Parameter-free
- Tracking the Best Expert in Non-stationary Stochastic Environments
- Make the Minority Great Again: First-Order Regret Bound for Contextual Bandits
- Strongly Adaptive Online Learning
- Equipping Experts/Bandits with Long-term Memory