Beyond UCB: Optimal and Efficient Contextual Bandits with Regression Oracles
arXiv:2002.04926
Abstract
A fundamental challenge in contextual bandits is to develop flexible, general-purpose algorithms with computational requirements no worse than classical supervised learning tasks such as classification and regression. Algorithms based on regression have shown promising empirical success, but theoretical guarantees have remained elusive except in special cases. We provide the first universal and optimal reduction from contextual bandits to online regression. We show how to transform any oracle for online regression with a given value function class into an algorithm for contextual bandits with the induced policy class, with no overhead in runtime or memory requirements. We characterize the minimax rates for contextual bandits with general, potentially nonparametric function classes, and show that our algorithm is minimax optimal whenever the oracle obtains the optimal rate for regression. Compared to previous results, our algorithm requires no distributional assumptions beyond realizability, and works even when contexts are chosen adversarially.
arXiv commentICML 2020
References in corpus (24)
- Taming the Monster: A Fast and Simple Algorithm for Contextual Bandits
- Contextual Bandit Algorithms with Supervised Learning Guarantees
- Provably Optimal Algorithms for Generalized Linear Contextual Bandits
- Finite-Time Analysis of Kernelised Contextual Bandits
- Efficient Optimal Learning for Contextual Bandits
- Nonparametric Bandits with Covariates
- Making Contextual Decisions with Low Technical Debt
- BISTRO: An Efficient Relaxation-Based Method for Contextual Bandits
- Efficient Learning of Generalized Linear and Single Index Models with Isotonic Regression
- Empirical entropy, minimax regret and minimax risk
- On the Universality of Online Mirror Descent
- A Contextual Bandit Bake-off
- Prediction, Learning, Uniform Convergence, and Scale-sensitive Dimensions
- Contextual Bandit Learning with Predictable Rewards
- Practical Contextual Bandits with Regression Oracles
- Multiclass learnability and the ERM principle
- Model selection for contextual bandits
- Efficient Algorithms for Adversarial Contextual Learning
- Comments on the Du-Kakade-Wang-Yang Lower Bounds
- Learning with Good Feature Representations in Bandits and in RL with a Generative Model
- Metric entropy in competitive on-line prediction
- Make the Minority Great Again: First-Order Regret Bound for Contextual Bandits
- Contextual bandits with surrogate losses: Margin bounds and efficient algorithms
- Strongly Adaptive Online Learning