mlsanityData to 7 Oct 2026

Refined Lower Bounds for Adversarial Bandits

arXiv 1605.07416 ↗First posted 24 May 2016math.ST cs.LG stat.MLcited by 20

Not on the map. Why?

Abstract (arXiv)

We provide new lower bounds on the regret that must be suffered by adversarial bandit algorithms. The new results show that recent upper bounds that either (a) hold with high-probability or (b) depend on the total lossof the best arm or (c) depend on the quadratic variation of the losses, are close to tight. Besides this we prove two impossibility results. First, the existence of a single arm that is optimal in every round cannot improve the regret in the worst case. Second, the regret cannot scale with the effective range of the losses. In contrast, both results are possible in the full-information setting.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 7; 2022: 5; 2023: 2; 2024: 1; 2025: 2; 2026: 3.

20 papers.

Sort:

  1. 2021Achieving Near Instance-Optimality and Minimax-Optimality in Stochastic and Adversarial Linear Bandits Simultaneouslycited by 48
  2. 2021An Efficient Pessimistic-Optimistic Algorithm for Stochastic Linear Bandits with General Constraintscited by 29
  3. 2021Achieving the Pareto Frontier of Regret Minimization and Best Arm Identification in Multi-Armed Banditscited by 13
  4. 2021Scale Free Adversarial Multi Armed Banditscited by 12
  5. 2022Pareto Regret Analyses in Multi-objective Multi-armed Banditcited by 11
  6. 2021Robust Bandit Learning with Imperfect Contextcited by 8
  7. 2022Near-Optimal Goal-Oriented Reinforcement Learning in Non-Stationary Environmentscited by 6
  8. 2023Adversarial Attacks on Adversarial Banditscited by 6
  9. 2021Fast rates for prediction with limited expert advicecited by 4
  10. 2022Coordinated Attacks against Contextual Bandits: Fundamental Limits and Defense Mechanismscited by 4
  11. 2022Slowly Changing Adversarial Bandit Algorithms are Efficient for Discounted MDPscited by 2
  12. 2022Constant regret for sequence prediction with limited advicecited by 2
8 more
  1. 2023Information-Theoretic Regret Bounds for Bandits with Fixed Expert Advicecited by 2
  2. 2025Data-Dependent Regret Bounds for Constrained MABscited by 2
  3. 2025Risk level dependent Minimax Quantile lower bounds for Interactive Statistical Decision Makingcited by 2
  4. 2026Multi-Armed Bandits With Best-Action Queriescited by 2
  5. 2021Hierarchical Causal Banditcited by 0
  6. 2024Minimax-optimal trust-aware multi-armed banditscited by 0
  7. 2026Online Packet Scheduling with Deadlines and Learningcited by 0
  8. 2026Leveraging Similarities in Multi-Armed Banditscited by 0