OSOM: A simultaneously optimal algorithm for multi-armed and linear contextual bandits
arXiv:1905.10040
Abstract
We consider the stochastic linear (multi-armed) contextual bandit problem with the possibility of hidden simple multi-armed bandit structure in which the rewards are independent of the contextual information. Algorithms that are designed solely for one of the regimes are known to be sub-optimal for the alternate regime. We design a single computationally efficient algorithm that simultaneously obtains problem-dependent optimal regret rates in the simple multi-armed bandit regime and minimax optimal regret rates in the linear contextual bandit regime, without knowing a priori which of the two models generates the rewards. These results are proved under the condition of stochasticity of contextual information over multiple rounds. Our results should be viewed as a step towards principled data-dependent policy class selection for contextual bandits.
References in corpus (13)
- A Contextual-Bandit Approach to Personalized News Article Recommendation
- Taming the Monster: A Fast and Simple Algorithm for Contextual Bandits
- Contextual Bandits with Similarity Information
- Contextual Bandit Algorithms with Supervised Learning Guarantees
- Concentration of the adjacency matrix and of the Laplacian in random graphs with independent edges
- The best of both worlds: stochastic and adversarial bandits
- Making Contextual Decisions with Low Technical Debt
- BISTRO: An Efficient Relaxation-Based Method for Contextual Bandits
- Learning in Games: Robustness of Fast Convergence
- Model selection for contextual bandits
- Efficient Algorithms for Adversarial Contextual Learning
- The Externalities of Exploration and How Data Diversity Helps Exploitation
- Contextual bandits with surrogate losses: Margin bounds and efficient algorithms