# Pareto Optimal Model Selection in Linear Bandits

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

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- Builds on 29 of its 61 references that are in the map.
- First posted on arXiv 12 Feb 2021.

## Builds on (most cited first, 29 of 29)

- [Coin Betting and Parameter-Free Online Learning](https://mlsanity.com/paper/1602.04128/) (2016)
- [Learning with Good Feature Representations in Bandits and in RL with a Generative Model](https://mlsanity.com/paper/1911.07676/) (2019)
- [Black-Box Reductions for Parameter-free Online Learning in Banach Spaces](https://mlsanity.com/paper/1802.06293/) (2018)
- [Corralling a Band of Bandit Algorithms](https://mlsanity.com/paper/1612.06246/) (2016)
- [Model Selection in Contextual Stochastic Bandit Problems](https://mlsanity.com/paper/2003.01704/) (2020)
- [Sequential Batch Learning in Finite-Action Linear Contextual Bandits](https://mlsanity.com/paper/2004.06321/) (2020)
- [High-Dimensional Sparse Linear Bandits](https://mlsanity.com/paper/2011.04020/) (2020)
- [Model selection for contextual bandits](https://mlsanity.com/paper/1906.00531/) (2019)
- [Second-order Quantile Methods for Experts and Combinatorial Games](https://mlsanity.com/paper/1502.08009/) (2015)
- [Regret Bound Balancing and Elimination for Model Selection in Bandits and RL](https://mlsanity.com/paper/2012.13045/) (2020)
- [Misspecified Linear Bandits](https://mlsanity.com/paper/1704.06880/) (2017)
- [Satisficing in Time-Sensitive Bandit Learning](https://mlsanity.com/paper/1803.02855/) (2018)
- [Online Learning Without Prior Information](https://mlsanity.com/paper/1703.02629/) (2017)
- [Parameter-free online learning via model selection](https://mlsanity.com/paper/1801.00101/) (2017)
- [OSOM: A simultaneously optimal algorithm for multi-armed and linear contextual bandits](https://mlsanity.com/paper/1905.10040/) (2019)
- [Simultaneous Model Selection and Optimization through Parameter-free Stochastic Learning](https://mlsanity.com/paper/1406.3816/) (2014)
- [Problem-Complexity Adaptive Model Selection for Stochastic Linear Bandits](https://mlsanity.com/paper/2006.02612/) (2020)
- [A simple parameter-free and adaptive approach to optimization under a minimal local smoothness assumption](https://mlsanity.com/paper/1810.00997/) (2018)
- [Corralling Stochastic Bandit Algorithms](https://mlsanity.com/paper/2006.09255/) (2020)
- [Linear Bandits in High Dimension and Recommendation Systems](https://mlsanity.com/paper/1301.1722/) (2013)
- [Regret Balancing for Bandit and RL Model Selection](https://mlsanity.com/paper/2006.05491/) (2020)
- [On Regret with Multiple Best Arms](https://mlsanity.com/paper/2006.14785/) (2020)
- [The Pareto Regret Frontier for Bandits](https://mlsanity.com/paper/1511.00048/) (2015)
- [Minimax Optimal Algorithms for Unconstrained Linear Optimization](https://mlsanity.com/paper/1302.2176/) (2013)
- [Open Problem: Model Selection for Contextual Bandits](https://mlsanity.com/paper/2006.10940/) (2020)
- [Experimental Design for Regret Minimization in Linear Bandits](https://mlsanity.com/paper/2011.00576/) (2020)
- [Polynomial Cost of Adaptation for X -Armed Bandits](https://mlsanity.com/paper/1905.10221/) (2019)
- [Upper Confidence Bounds for Combining Stochastic Bandits](https://mlsanity.com/paper/2012.13115/) (2020)
- [Linear Bandits with Feature Feedback](https://mlsanity.com/paper/1903.03705/) (2019)

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

- [The Pareto Frontier of model selection for general Contextual Bandits](https://mlsanity.com/paper/2110.13282/) (2021)
- [Efficient Sequential Decision Making with Large Language Models](https://mlsanity.com/paper/2406.12125/) (2024)
- [Norm-Agnostic Linear Bandits](https://mlsanity.com/paper/2205.01257/) (2022)
- [Best of Both Worlds Model Selection](https://mlsanity.com/paper/2206.14912/) (2022)
- [Strategic Scaling of Test-Time Compute: A Bandit Learning Approach](https://mlsanity.com/paper/2506.12721/) (2025)
- [Universal and data-adaptive algorithms for model selection in linear contextual bandits](https://mlsanity.com/paper/2111.04688/) (2021)
- [Adaptation to Misspecified Kernel Regularity in Kernelised Bandits](https://mlsanity.com/paper/2304.13830/) (2023)
- [Near Instance Optimal Model Selection for Pure Exploration Linear Bandits](https://mlsanity.com/paper/2109.05131/) (2021)
- [Linear Bandits on Ellipsoids: Minimax Optimal Algorithms](https://mlsanity.com/paper/2502.17175/) (2025)
- [Causal Bandits: The Pareto Optimal Frontier of Adaptivity, a Reduction to Linear Bandits, and Limitations around Unknown Marginals](https://mlsanity.com/paper/2407.00950/) (2024)
- [Achieving Optimal Static and Dynamic Regret Simultaneously in Bandits with Deterministic Losses](https://mlsanity.com/paper/2602.07418/) (2026)
- [Leveraging User-Triggered Supervision in Contextual Bandits](https://mlsanity.com/paper/2302.03784/) (2023)
- [Estimating Optimal Policy Value in General Linear Contextual Bandits](https://mlsanity.com/paper/2302.09451/) (2023)
- [Bandits with Multiple Optimal Arms: Minimax Regret and Non-Adaptivity](https://mlsanity.com/paper/2609.38659/) (2026)

## Abstract (arXiv)

We study model selection in linear bandits, where the learner must adapt to the dimension (denoted by d_star) of the smallest hypothesis class containing the true linear model while balancing exploration and exploitation. Previous papers provide various guarantees for this model selection problem, but have limitations; i.e., the analysis requires favorable conditions that allow for inexpensive statistical testing to locate the right hypothesis class or are based on the idea of "corralling" multiple base algorithms, which often performs relatively poorly in practice. These works also mainly focus on upper bounds. In this paper, we establish the first lower bound for the model selection problem. Our lower bound implies that, even with a fixed action set, adaptation to the unknown dimension d_star comes at a cost: There is no algorithm that can achieve the regret bound widetildeO(√d_star T) simultaneously for all values of d_star. We propose Pareto optimal algorithms that match the lower bound. Empirical evaluations show that our algorithm enjoys superior performance compared to existing ones.