mlsanityData to 7 Oct 2026

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

arXiv 1905.10040 ↗First posted 24 May 2019stat.ML cs.LGcited by 28

Not on the map. Why?

Abstract (arXiv)

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.

Key facts. Cited by 28 papers in the map (data through 7 Oct 2026). First posted on arXiv 24 May 2019.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 11; 2022: 6; 2023: 3; 2024: 2; 2025: 4; 2026: 2.

28 papers.

Sort:

By area:

  1. 2021Leveraging Good Representations in Linear Contextual Banditscited by 29
  2. 2021The Pareto Frontier of model selection for general Contextual Banditscited by 24
  3. 2021Pareto Optimal Model Selection in Linear Banditscited by 14
  4. 2022Oracle Inequalities for Model Selection in Offline Reinforcement Learningcited by 13
  5. 2021Provably Efficient Representation Selection in Low-rank Markov Decision Processes: From Online to Offline RLcited by 12
  6. 2021Dealing With Misspecification In Fixed-Confidence Linear Top-m Identificationcited by 11
  7. 2021Model Selection in Batch Policy Optimizationcited by 11
  8. 2022Best of Both Worlds Model Selectioncited by 11
  9. 2023Data-Driven Online Model Selection With Regret Guaranteescited by 11
  10. 2021On Dynamic Pricing with Covariatescited by 10
  11. 2022Exploration in Linear Bandits with Rich Action Sets and its Implications for Inferencecited by 9
  12. 2021Model Selection for Generic Contextual Banditscited by 7
16 more
  1. 2022Leveraging Initial Hints for Free in Stochastic Linear Banditscited by 7
  2. 2021Universal and data-adaptive algorithms for model selection in linear contextual banditscited by 5
  3. 2022Breaking the √T Barrier: Instance-Independent Logarithmic Regret in Stochastic Contextual Linear Banditscited by 5
  4. 2024Linear Contextual Bandits with Hybrid Payoff: Revisitedcited by 5
  5. 2021Adaptive Clustering and Personalization in Multi-Agent Stochastic Linear Banditscited by 4
  6. 2025Choosing the Better Bandit Algorithm under Data Sharing: When Do A/B Experiments Work?cited by 4
  7. 2025Demystifying Online Clustering of Bandits: Enhanced Exploration Under Stochastic and Smoothed Adversarial Contextscited by 3
  8. 2025Efficient Algorithms for Logistic Contextual Slate Bandits with Bandit Feedbackcited by 2
  9. 2021Model Selection for Generic Reinforcement Learningcited by 1
  10. 2022Model Selection in Reinforcement Learning with General Function Approximationscited by 1
  11. 2024Competing Bandits in Decentralized Contextual Matching Marketscited by 1
  12. 2023Estimating Optimal Policy Value in General Linear Contextual Banditscited by 0
  13. 2023Ranking with Popularity Bias: User Welfare under Self-Amplification Dynamicscited by 0
  14. 2025Empirical Bound Information-Directed Sampling for Norm-Agnostic Banditscited by 0
  15. 2026Signature Approach for Contextual Bandits with Nonlinear and Path-dependent Rewardscited by 0
  16. 2026Contextual Slate GLM Bandits with Limited Adaptivitycited by 0