# Nearly Minimax-Optimal Regret for Linearly Parameterized Bandits

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

## Key facts

- Cited by 54 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 30 Mar 2019.

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

- [A Simple Approach for Non-stationary Linear Bandits](https://mlsanity.com/paper/2103.05324/) (2021)
- [Efficient First-Order Contextual Bandits: Prediction, Allocation, and Triangular Discrimination](https://mlsanity.com/paper/2107.02237/) (2021)
- [Computationally Efficient Horizon-Free Reinforcement Learning for Linear Mixture MDPs](https://mlsanity.com/paper/2205.11507/) (2022)
- [Improved Regret Analysis for Variance-Adaptive Linear Bandits and Horizon-Free Linear Mixture MDPs](https://mlsanity.com/paper/2111.03289/) (2021)
- [Variance-Dependent Regret Bounds for Linear Bandits and Reinforcement Learning: Adaptivity and Computational Efficiency](https://mlsanity.com/paper/2302.10371/) (2023)
- [A Simple and Provably Efficient Algorithm for Asynchronous Federated Contextual Linear Bandits](https://mlsanity.com/paper/2207.03106/) (2022)
- [Contexts can be Cheap: Solving Stochastic Contextual Bandits with Linear Bandit Algorithms](https://mlsanity.com/paper/2211.05632/) (2022)
- [Bypassing the Simulator: Near-Optimal Adversarial Linear Contextual Bandits](https://mlsanity.com/paper/2309.00814/) (2023)
- [Nearly Minimax Algorithms for Linear Bandits with Shared Representation](https://mlsanity.com/paper/2203.15664/) (2022)
- [Double Doubly Robust Thompson Sampling for Generalized Linear Contextual Bandits](https://mlsanity.com/paper/2209.06983/) (2022)
- [Variance-Aware Sparse Linear Bandits](https://mlsanity.com/paper/2205.13450/) (2022)
- [Best-of-Both-Worlds Algorithms for Linear Contextual Bandits](https://mlsanity.com/paper/2312.15433/) (2023)
- [Almost Optimal Batch-Regret Tradeoff for Batch Linear Contextual Bandits](https://mlsanity.com/paper/2110.08057/) (2021)
- [Asymptotic Instance-Optimal Algorithms for Interactive Decision Making](https://mlsanity.com/paper/2206.02326/) (2022)
- [Global Optimization with Parametric Function Approximation](https://mlsanity.com/paper/2211.09100/) (2022)
- [Contextual Online Uncertainty-Aware Preference Learning for Human Feedback](https://mlsanity.com/paper/2504.19342/) (2025)
- [Provably and Practically Efficient Neural Contextual Bandits](https://mlsanity.com/paper/2206.00099/) (2022)
- [Squeeze All: Novel Estimator and Self-Normalized Bound for Linear Contextual Bandits](https://mlsanity.com/paper/2206.05404/) (2022)
- [Adversarial Contextual Bandits Go Kernelized](https://mlsanity.com/paper/2310.01609/) (2023)
- [Causally Abstracted Multi-armed Bandits](https://mlsanity.com/paper/2404.17493/) (2024)
- [Single Index Bandits: Generalized Linear Contextual Bandits with Unknown Reward Functions](https://mlsanity.com/paper/2506.12751/) (2025)
- [Linear Contextual Bandits with Hybrid Payoff: Revisited](https://mlsanity.com/paper/2406.10131/) (2024)
- [Linear Causal Bandits: Unknown Graph and Soft Interventions](https://mlsanity.com/paper/2411.02383/) (2024)
- [Provably Efficient Kernelized Q-Learning](https://mlsanity.com/paper/2204.10349/) (2022)
- [Lifelong Bandit Optimization: No Prior and No Regret](https://mlsanity.com/paper/2210.15513/) (2022)
- [Provably Efficient Reinforcement Learning via Surprise Bound](https://mlsanity.com/paper/2302.11634/) (2023)
- [CO-BED: Information-Theoretic Contextual Optimization via Bayesian Experimental Design](https://mlsanity.com/paper/2302.14015/) (2023)
- [Variance-Dependent Regret Lower Bounds for Contextual Bandits](https://mlsanity.com/paper/2503.12020/) (2025)
- [Federated Linear Bandits with Finite Adversarial Actions](https://mlsanity.com/paper/2311.00973/) (2023)
- [Optimal Regret Is Achievable with Bounded Approximate Inference Error: An Enhanced Bayesian Upper Confidence Bound Framework](https://mlsanity.com/paper/2201.12955/) (2022)

## Abstract (arXiv)

We study the linear contextual bandit problem with finite action sets. When the problem dimension is d, the time horizon is T, and there are n ≤ 2d/2 candidate actions per time period, we (1) show that the minimax expected regret is Omega(√dT (log T) (log n)) for every algorithm, and (2) introduce a Variable-Confidence-Level (VCL) SupLinUCB algorithm whose regret matches the lower bound up to iterated logarithmic factors. Our algorithmic result saves two √log T factors from previous analysis, and our information-theoretical lower bound also improves previous results by one √log T factor, revealing a regret scaling quite different from classical multi-armed bandits in which no logarithmic T term is present in minimax regret. Our proof techniques include variable confidence levels and a careful analysis of layer sizes of SupLinUCB on the upper bound side, and delicately constructed adversarial sequences showing the tightness of elliptical potential lemmas on the lower bound side.