OSOM: A simultaneously optimal algorithm for multi-armed and linear contextual bandits

2019/05/24 by Niladri S. Chatterji, Vidya Muthukumar, Chatterji, Niladri S. +4 · 2 citations
Computer Science · Decision Sciences · Engineering · #Advanced Bandit Algorithms Research #Age of Information Optimization #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Smart Grid Energy Management

paper · pdf · doi:10.48550/arxiv.1905.10040

openalex publication_date 2019/05/24 · openalex created_date 2020/07/02 · openalex updated_date 2026/07/28

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.

Cited by

• Choosing the Better Bandit Algorithm under Data Sharing: When Do A/B Experiments Work?
• Rate-adaptive model selection over a collection of black-box contextual\n bandit algorithms

Related

• A Survey on Contextual Multi-armed Bandits
• Contexts can be Cheap: Solving Stochastic Contextual Bandits with Linear Bandit Algorithms
• A Time and Space Efficient Algorithm for Contextual Linear Bandits
• Contextual Blocking Bandits
• Best-of-Both-Worlds Algorithms for Linear Contextual Bandits