# Model selection for contextual bandits

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

## Key facts

- Cited by 60 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 3 Jun 2019.

## Built on by (most cited first, 30 of 60)

- [Adapting to Misspecification in Contextual Bandits](https://mlsanity.com/paper/2107.05745/) (2021)
- [A Model Selection Approach for Corruption Robust Reinforcement Learning](https://mlsanity.com/paper/2110.03580/) (2021)
- [Cost-Effective Online Multi-LLM Selection with Versatile Reward Models](https://mlsanity.com/paper/2405.16587/) (2024)
- [Efficient Deep Reinforcement Learning Requires Regulating Overfitting](https://mlsanity.com/paper/2304.10466/) (2023)
- [Leveraging Good Representations in Linear Contextual Bandits](https://mlsanity.com/paper/2104.03781/) (2021)
- [Which LLM to Play? Convergence-Aware Online Model Selection with Time-Increasing Bandits](https://mlsanity.com/paper/2403.07213/) (2024)
- [The Pareto Frontier of model selection for general Contextual Bandits](https://mlsanity.com/paper/2110.13282/) (2021)
- [Corralling a Larger Band of Bandits: A Case Study on Switching Regret for Linear Bandits](https://mlsanity.com/paper/2202.06151/) (2022)
- [Linear Contextual Bandits with Adversarial Corruptions](https://mlsanity.com/paper/2110.12615/) (2021)
- [Thompson Sampling with a Mixture Prior](https://mlsanity.com/paper/2106.05608/) (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)
- [Confidence-Budget Matching for Sequential Budgeted Learning](https://mlsanity.com/paper/2102.03400/) (2021)
- [Provably Efficient Representation Selection in Low-rank Markov Decision Processes: From Online to Offline RL](https://mlsanity.com/paper/2106.11935/) (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)
- [Active Policy Improvement from Multiple Black-box Oracles](https://mlsanity.com/paper/2306.10259/) (2023)
- [Syndicated Bandits: A Framework for Auto Tuning Hyper-parameters in Contextual Bandit Algorithms](https://mlsanity.com/paper/2106.02979/) (2021)
- [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)
- [Never Start from Scratch: Expediting On-Device LLM Personalization via Explainable Model Selection](https://mlsanity.com/paper/2504.13938/) (2025)
- [Leveraging Initial Hints for Free in Stochastic Linear Bandits](https://mlsanity.com/paper/2203.04274/) (2022)
- [Offline-to-online hyperparameter transfer for stochastic bandits](https://mlsanity.com/paper/2501.02926/) (2025)
- [BOAD: Discovering Hierarchical Software Engineering Agents via Bandit Optimization](https://mlsanity.com/paper/2512.23631/) (2025)
- [Linear Bandits with Memory: from Rotting to Rising](https://mlsanity.com/paper/2302.08345/) (2023)
- [Anytime Model Selection in Linear Bandits](https://mlsanity.com/paper/2307.12897/) (2023)
- [On the Necessity of Collaboration for Online Model Selection with Decentralized Data](https://mlsanity.com/paper/2404.09494/) (2024)
- [ORSO: Accelerating Reward Design via Online Reward Selection and Policy Optimization](https://mlsanity.com/paper/2410.13837/) (2024)

## Abstract (arXiv)

We introduce the problem of model selection for contextual bandits, where a learner must adapt to the complexity of the optimal policy while balancing exploration and exploitation. Our main result is a new model selection guarantee for linear contextual bandits. We work in the stochastic realizable setting with a sequence of nested linear policy classes of dimension d1 < d2 < ldots, where the m^star-th class contains the optimal policy, and we design an algorithm that achieves tildeO(T2/3d1/3m^star) regret with no prior knowledge of the optimal dimension dm^star. The algorithm also achieves regret tildeO(T3/4 + √Tdm^star), which is optimal for d_mstar≥√T. This is the first model selection result for contextual bandits with non-vacuous regret for all values of dm^star, and to the best of our knowledge is the first positive result of this type for any online learning setting with partial information. The core of the algorithm is a new estimator for the gap in the best loss achievable by two linear policy classes, which we show admits a convergence rate faster than the rate required to learn the parameters for either class.