# Problem-Complexity Adaptive Model Selection for Stochastic Linear Bandits

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

## Key facts

- Cited by 26 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 4 Jun 2020.

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

- [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)
- [Provably Efficient Representation Selection in Low-rank Markov Decision Processes: From Online to Offline RL](https://mlsanity.com/paper/2106.11935/) (2021)
- [Norm-Agnostic Linear Bandits](https://mlsanity.com/paper/2205.01257/) (2022)
- [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)
- [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)
- [Scalable Representation Learning in Linear Contextual Bandits with Constant Regret Guarantees](https://mlsanity.com/paper/2210.13083/) (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)
- [Coordinated Attacks against Contextual Bandits: Fundamental Limits and Defense Mechanisms](https://mlsanity.com/paper/2201.12700/) (2022)
- [Demystifying Online Clustering of Bandits: Enhanced Exploration Under Stochastic and Smoothed Adversarial Contexts](https://mlsanity.com/paper/2501.00891/) (2025)
- [On the Complexity of Representation Learning in Contextual Linear Bandits](https://mlsanity.com/paper/2212.09429/) (2022)
- [Sparsity-Agnostic Linear Bandits with Adaptive Adversaries](https://mlsanity.com/paper/2406.01192/) (2024)
- [Model Selection for Generic Reinforcement Learning](https://mlsanity.com/paper/2107.05849/) (2021)
- [Flexible and Efficient Contextual Bandits with Heterogeneous Treatment Effect Oracles](https://mlsanity.com/paper/2203.16668/) (2022)
- [Model Selection in Reinforcement Learning with General Function Approximations](https://mlsanity.com/paper/2207.02992/) (2022)
- [Symmetric Linear Bandits with Hidden Symmetry](https://mlsanity.com/paper/2405.13899/) (2024)
- [Competing Bandits in Decentralized Contextual Matching Markets](https://mlsanity.com/paper/2411.11794/) (2024)
- [Empirical Bound Information-Directed Sampling for Norm-Agnostic Bandits](https://mlsanity.com/paper/2503.05098/) (2025)

## Abstract (arXiv)

We consider the problem of model selection for two popular stochastic linear bandit settings, and propose algorithms that adapts to the unknown problem complexity. In the first setting, we consider the K armed mixture bandits, where the mean reward of arm i ∈ [K], is μi+ langle αi,t,θ^* rangle , with αi,t ∈ ℝd being the known context vector and μi ∈ [-1,1] and θ^* are unknown parameters. We define |θ^*| as the problem complexity and consider a sequence of nested hypothesis classes, each positing a different upper bound on |θ^*|. Exploiting this, we propose Adaptive Linear Bandit (ALB), a novel phase based algorithm that adapts to the true problem complexity, |θ^*|. We show that ALB achieves regret scaling of O(|θ^*|√T), where |θ^*| is apriori unknown. As a corollary, when θ^*=0, ALB recovers the minimax regret for the simple bandit algorithm without such knowledge of θ^*. ALB is the first algorithm that uses parameter norm as model section criteria for linear bandits. Prior state of art algorithms citeosom achieve a regret of O(L√T), where L is the upper bound on |θ^*|, fed as an input to the problem. In the second setting, we consider the standard linear bandit problem (with possibly an infinite number of arms) where the sparsity of θ^*, denoted by d^* ≤ d, is unknown to the algorithm. Defining d^* as the problem complexity, we show that ALB achieves O(d^*√T) regret, matching that of an oracle who knew the true sparsity level. This methodology is then extended to the case of finitely many arms and similar results are proven. This is the first algorithm that achieves such model selection guarantees. We further verify our results via synthetic and real-data experiments.