mlsanityData to 14 Oct 2026

Nearly Minimax-Optimal Regret for Linearly Parameterized Bandits

arXiv 1904.00242 ↗First posted 30 Mar 2019stat.ML cs.LGcited by 54

Not on the map. Why?

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.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 5; 2022: 19; 2023: 10; 2024: 5; 2025: 7; 2026: 8.

54 papers.

Sort:

By area:

  1. 2021A Simple Approach for Non-stationary Linear Banditscited by 54
  2. 2021Efficient First-Order Contextual Bandits: Prediction, Allocation, and Triangular Discriminationcited by 53
  3. 2022Computationally Efficient Horizon-Free Reinforcement Learning for Linear Mixture MDPscited by 52
  4. 2021Improved Regret Analysis for Variance-Adaptive Linear Bandits and Horizon-Free Linear Mixture MDPscited by 44
  5. 2023Variance-Dependent Regret Bounds for Linear Bandits and Reinforcement Learning: Adaptivity and Computational Efficiencycited by 40
  6. 2022A Simple and Provably Efficient Algorithm for Asynchronous Federated Contextual Linear Banditscited by 28
  7. 2022Contexts can be Cheap: Solving Stochastic Contextual Bandits with Linear Bandit Algorithmscited by 19
  8. 2023Bypassing the Simulator: Near-Optimal Adversarial Linear Contextual Banditscited by 19
  9. 2022Nearly Minimax Algorithms for Linear Bandits with Shared Representationcited by 16
  10. 2022Double Doubly Robust Thompson Sampling for Generalized Linear Contextual Banditscited by 14
  11. 2022Variance-Aware Sparse Linear Banditscited by 11
  12. 2023Best-of-Both-Worlds Algorithms for Linear Contextual Banditscited by 11
38 more
  1. 2021Almost Optimal Batch-Regret Tradeoff for Batch Linear Contextual Banditscited by 9
  2. 2022Asymptotic Instance-Optimal Algorithms for Interactive Decision Makingcited by 7
  3. 2022Global Optimization with Parametric Function Approximationcited by 7
  4. 2025Contextual Online Uncertainty-Aware Preference Learning for Human Feedbackcited by 7
  5. 2022Provably and Practically Efficient Neural Contextual Banditscited by 6
  6. 2022Squeeze All: Novel Estimator and Self-Normalized Bound for Linear Contextual Banditscited by 6
  7. 2023Adversarial Contextual Bandits Go Kernelizedcited by 6
  8. 2024Causally Abstracted Multi-armed Banditscited by 6
  9. 2025Single Index Bandits: Generalized Linear Contextual Bandits with Unknown Reward Functionscited by 6
  10. 2024Linear Contextual Bandits with Hybrid Payoff: Revisitedcited by 5
  11. 2024Linear Causal Bandits: Unknown Graph and Soft Interventionscited by 5
  12. 2022Provably Efficient Kernelized Q-Learningcited by 4
  13. 2022Lifelong Bandit Optimization: No Prior and No Regretcited by 4
  14. 2023Provably Efficient Reinforcement Learning via Surprise Boundcited by 4
  15. 2023CO-BED: Information-Theoretic Contextual Optimization via Bayesian Experimental Designcited by 4
  16. 2025Variance-Dependent Regret Lower Bounds for Contextual Banditscited by 4
  17. 2023Federated Linear Bandits with Finite Adversarial Actionscited by 3
  18. 2022Optimal Regret Is Achievable with Bounded Approximate Inference Error: An Enhanced Bayesian Upper Confidence Bound Frameworkcited by 2
  19. 2023No-Regret Linear Bandits beyond Realizabilitycited by 2
  20. 2023Follow-ups Also Matter: Improving Contextual Bandits via Post-serving Contextscited by 2
  21. 2024Prior-dependent analysis of posterior sampling reinforcement learning with function approximationcited by 2
  22. 2024Minimax Optimality in Contextual Dynamic Pricing with General Valuation Modelscited by 2
  23. 2025Optimal and Practical Batched Linear Bandit Algorithmcited by 2
  24. 2026Practical and Optimal Algorithm for Linear Contextual Bandits with Rare Parameter Updatescited by 2
  25. 2021The Elliptical Potential Lemma for General Distributions with an Application to Linear Thompson Samplingcited by 1
  26. 2022Truncated LinUCB for Stochastic Linear Banditscited by 1
  27. 2022Flexible and Efficient Contextual Bandits with Heterogeneous Treatment Effect Oraclescited by 1
  28. 2022A Reinforcement Learning Approach in Multi-Phase Second-Price Auction Designcited by 1
  29. 2023Communication-Efficient Federated Non-Linear Bandit Optimizationcited by 1
  30. 2025Generator-Mediated Bandits: Thompson Sampling for GenAI-Powered Adaptive Interventionscited by 1
  31. 2025Experimental Design for Semiparametric Banditscited by 1
  32. 2026Logistic Bandits with tildeO(√dT) Regret without Context Diversity Assumptionscited by 1
  33. 2026Batched Stochastic Linear Bandits with 1-Bit Communication Constraintscited by 1
  34. 2026Policy Regret for Embedding Model Routing: Contextual Bandits with Low-Rank Expertscited by 1
  35. 2022Rate-matching the regret lower-bound in the linear quadratic regulator with unknown dynamicscited by 0
  36. 2022Cost-Efficient Distributed Learning via Combinatorial Multi-Armed Banditscited by 0
  37. 2022Dual Instrumental Method for Confounded Kernelized Banditscited by 0
  38. 2025Parameter-Adaptive Dynamic Pricingcited by 0

50 most cited of 54 All 54 (JSON)