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

arXiv: https://arxiv.org/abs/1905.10040 · HTML: https://mlsanity.com/paper/1905.10040/

## Key facts

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

## Built on by (most cited first, 28 of 28)

- [Leveraging Good Representations in Linear Contextual Bandits](https://mlsanity.com/paper/2104.03781/) (2021)
- [The Pareto Frontier of model selection for general Contextual Bandits](https://mlsanity.com/paper/2110.13282/) (2021)
- [Pareto Optimal Model Selection in Linear Bandits](https://mlsanity.com/paper/2102.06593/) (2021)
- [Oracle Inequalities for Model Selection in Offline Reinforcement Learning](https://mlsanity.com/paper/2211.02016/) (2022)
- [Provably Efficient Representation Selection in Low-rank Markov Decision Processes: From Online to Offline RL](https://mlsanity.com/paper/2106.11935/) (2021)
- [Dealing With Misspecification In Fixed-Confidence Linear Top-m Identification](https://mlsanity.com/paper/2111.01479/) (2021)
- [Model Selection in Batch Policy Optimization](https://mlsanity.com/paper/2112.12320/) (2021)
- [Best of Both Worlds Model Selection](https://mlsanity.com/paper/2206.14912/) (2022)
- [Data-Driven Online Model Selection With Regret Guarantees](https://mlsanity.com/paper/2306.02869/) (2023)
- [On Dynamic Pricing with Covariates](https://mlsanity.com/paper/2112.13254/) (2021)
- [Exploration in Linear Bandits with Rich Action Sets and its Implications for Inference](https://mlsanity.com/paper/2207.11597/) (2022)
- [Model Selection for Generic Contextual Bandits](https://mlsanity.com/paper/2107.03455/) (2021)
- [Leveraging Initial Hints for Free in Stochastic Linear Bandits](https://mlsanity.com/paper/2203.04274/) (2022)
- [Universal and data-adaptive algorithms for model selection in linear contextual bandits](https://mlsanity.com/paper/2111.04688/) (2021)
- [Breaking the √T Barrier: Instance-Independent Logarithmic Regret in Stochastic Contextual Linear Bandits](https://mlsanity.com/paper/2205.09899/) (2022)
- [Linear Contextual Bandits with Hybrid Payoff: Revisited](https://mlsanity.com/paper/2406.10131/) (2024)
- [Adaptive Clustering and Personalization in Multi-Agent Stochastic Linear Bandits](https://mlsanity.com/paper/2106.08902/) (2021)
- [Choosing the Better Bandit Algorithm under Data Sharing: When Do A/B Experiments Work?](https://mlsanity.com/paper/2507.11891/) (2025)
- [Demystifying Online Clustering of Bandits: Enhanced Exploration Under Stochastic and Smoothed Adversarial Contexts](https://mlsanity.com/paper/2501.00891/) (2025)
- [Efficient Algorithms for Logistic Contextual Slate Bandits with Bandit Feedback](https://mlsanity.com/paper/2506.13163/) (2025)
- [Model Selection for Generic Reinforcement Learning](https://mlsanity.com/paper/2107.05849/) (2021)
- [Model Selection in Reinforcement Learning with General Function Approximations](https://mlsanity.com/paper/2207.02992/) (2022)
- [Competing Bandits in Decentralized Contextual Matching Markets](https://mlsanity.com/paper/2411.11794/) (2024)
- [Estimating Optimal Policy Value in General Linear Contextual Bandits](https://mlsanity.com/paper/2302.09451/) (2023)
- [Ranking with Popularity Bias: User Welfare under Self-Amplification Dynamics](https://mlsanity.com/paper/2305.18333/) (2023)
- [Empirical Bound Information-Directed Sampling for Norm-Agnostic Bandits](https://mlsanity.com/paper/2503.05098/) (2025)
- [Signature Approach for Contextual Bandits with Nonlinear and Path-dependent Rewards](https://mlsanity.com/paper/2605.10313/) (2026)
- [Contextual Slate GLM Bandits with Limited Adaptivity](https://mlsanity.com/paper/2606.31449/) (2026)

## 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.