mlsanityData to 7 Oct 2026

The End of Optimism? An Asymptotic Analysis of Finite-Armed Linear Bandits

arXiv 1610.04491 ↗First posted 14 Oct 2016stat.ML cs.LGcited by 48

Not on the map. Why?

Abstract (arXiv)

Stochastic linear bandits are a natural and simple generalisation of finite-armed bandits with numerous practical applications. Current approaches focus on generalising existing techniques for finite-armed bandits, notably the optimism principle and Thompson sampling. While prior work has mostly been in the worst-case setting, we analyse the asymptotic instance-dependent regret and show matching upper and lower bounds on what is achievable. Surprisingly, our results show that no algorithm based on optimism or Thompson sampling will ever achieve the optimal rate, and indeed, can be arbitrarily far from optimal, even in very simple cases. This is a disturbing result because these techniques are standard tools that are widely used for sequential optimisation. For example, for generalised linear bandits and reinforcement learning.

Key facts. Cited by 48 papers in the map (data through 7 Oct 2026). First posted on arXiv 14 Oct 2016.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 9; 2022: 11; 2023: 10; 2024: 6; 2025: 8; 2026: 4.

48 papers.

Sort:

By area:

  1. 2021Achieving Near Instance-Optimality and Minimax-Optimality in Stochastic and Adversarial Linear Bandits Simultaneouslycited by 48
  2. 2022Learning in Observable POMDPs, without Computationally Intractable Oraclescited by 30
  3. 2021Leveraging Good Representations in Linear Contextual Banditscited by 29
  4. 2022When Privacy Meets Partial Information: A Refined Analysis of Differentially Private Banditscited by 28
  5. 2021Fair Exploration via Axiomatic Bargainingcited by 21
  6. 2021Information Directed Sampling for Sparse Linear Banditscited by 20
  7. 2021Reinforcement Learning in Linear MDPs: Constant Regret and Representation Selectioncited by 17
  8. 2022An Optimization-based Algorithm for Non-stationary Kernel Bandits without Prior Knowledgecited by 17
  9. 2022Optimistic PAC Reinforcement Learning: the Instance-Dependent Viewcited by 17
  10. 2022Optimal Clustering with Bandit Feedbackcited by 15
  11. 2023Best-of-Three-Worlds Linear Bandit Algorithm with Variance-Adaptive Regret Boundscited by 13
  12. 2022Norm-Agnostic Linear Banditscited by 12
36 more
  1. 2023Linear Partial Monitoring for Sequential Decision-Making: Algorithms, Regret Bounds and Applicationscited by 11
  2. 2023Best-of-three-worlds Analysis for Linear Bandits with Follow-the-regularized-leader Algorithmcited by 11
  3. 2023Practical Contextual Bandits with Feedback Graphscited by 10
  4. 2022Exploration in Linear Bandits with Rich Action Sets and its Implications for Inferencecited by 9
  5. 2021Breaking the Moments Condition Barrier: No-Regret Algorithm for Bandits with Super Heavy-Tailed Payoffscited by 8
  6. 2025When and why randomised exploration works (in linear bandits)cited by 8
  7. 2022Asymptotic Instance-Optimal Algorithms for Interactive Decision Makingcited by 7
  8. 2024Optimal Batched Linear Banditscited by 7
  9. 2023Adaptive Linear Estimating Equationscited by 6
  10. 2024Beyond Optimism: Exploration With Partially Observable Rewardscited by 6
  11. 2021Incentivizing Exploration in Linear Bandits under Information Gapcited by 5
  12. 2023Learning and Collusion in Multi-unit Auctionscited by 5
  13. 2024Causally Abstracted Multi-armed Banditscited by 5
  14. 2021Indexed Minimum Empirical Divergence for Unimodal Banditscited by 4
  15. 2022The price of unfairness in linear bandits with biased feedbackcited by 3
  16. 2023Geometry-Aware Approaches for Balancing Performance and Theoretical Guarantees in Linear Banditscited by 3
  17. 2023Statistical Limits of Adaptive Linear Models: Low-Dimensional Estimation and Inferencecited by 3
  18. 2023Optimal Exploration is no harder than Thompson Samplingcited by 3
  19. 2026Adversarial Learning in Games with Bandit Feedback: Logarithmic Pure-Strategy Maximin Regretcited by 3
  20. 2022On the Complexity of Representation Learning in Contextual Linear Banditscited by 2
  21. 2023Best-of-Both-Worlds Linear Contextual Banditscited by 2
  22. 2024Regret Minimization via Saddle Point Optimizationcited by 2
  23. 2024Indexed Minimum Empirical Divergence-Based Algorithms for Linear Banditscited by 2
  24. 2025Adapting to Stochastic and Adversarial Losses in Episodic MDPs with Aggregate Bandit Feedbackcited by 2
  25. 2024Asymptotically and Minimax Optimal Regret Bounds for Multi-Armed Bandits with Abstentioncited by 1
  26. 2025Asymptotically Optimal Linear Best Feasible Arm Identification with Fixed Budgetcited by 1
  27. 2025Pure Exploration via Frank-Wolfe Self-Playcited by 1
  28. 2025The Confusing Instance Principle for Online Linear Quadratic Controlcited by 1
  29. 2021Practical, Provably-Correct Interactive Learning in the Realizable Setting: The Power of True Believerscited by 0
  30. 2022Truncated LinUCB for Stochastic Linear Banditscited by 0
  31. 2025Leveraging priors on distribution functions for multi-arm banditscited by 0
  32. 2025Beyond ATE: Multi-Criteria Design for A/B Testingcited by 0
  33. 2025Best-of-Both Worlds for linear contextual bandits with paid observationscited by 0
  34. 2026On the Complexity of Offline Reinforcement Learning with Q^star-Approximation and Partial Coveragecited by 0
  35. 2026Bandits for Efficient Experimentation: Adapting to Control Group, Preferences, and Context Driftscited by 0
  36. 2026Bootstrap-Conditioned Action Selection with Tabular Foundation Modelscited by 0