mlsanityData to 14 Oct 2026

Toward Optimal Second-Order Path-Length Guarantee for Adversarial Multi-Armed Bandits

arXiv 2608.15996 ↗First posted 17 Aug 2026cs.LGcited by 0

Not on the map. Why?

Abstract (arXiv)

We study second-order path-length regret in adversarial K-armed bandits against oblivious loss sequences. Bubeck et al. [2019] designed an algorithm that achieves widetildeO(K+√KQ∞,1) regret, where Q∞,1 is the first-order path length, and left open whether widetildeO(poly(K)√1+Q∞,2) regret is achievable under bandit feedback, where Q∞,2 is the second-order path length. Somewhat surprisingly, we resolve this question positively by showing that with a more involved analysis, the exact same algorithm of Bubeck et al. [2019] achieves Oleft(Klog(KT)+√Klog(KT)bigl(1+Q∞,2bigr)right) expected regret when Q∞,2 is known, where T is the horizon. This matches the Omega(√KQ∞,2) lower bound up to logarithmic factors and additive terms. We further remove the knowledge of Q∞,2 using an adaptive restart scheme whose path-length estimator has uniformly bounded increments.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Builds on 19 of its 26 references that are in the map. First posted on arXiv 17 Aug 2026.

Builds on

19 of 26 references.

References · 19

  1. 2015Fast Convergence of Regularized Learning in Gamescited by 150
  2. 2018Tsallis-INF: An Optimal Algorithm for Stochastic and Adversarial Banditscited by 124
  3. 2018More Adaptive Algorithms for Adversarial Banditscited by 114
  4. 2021Impossible Tuning Made Possible: A New Expert Algorithm and Its Applicationscited by 52
  5. 2020Bias no more: high-probability data-dependent regret bounds for adversarial bandits and MDPscited by 51
  6. 2020Simultaneously Learning Stochastic and Adversarial Episodic MDPs with Known Transitioncited by 48
  7. 2021The best of both worlds: stochastic and adversarial episodic MDPs with unknown transitioncited by 40
  8. 2015First-order regret bounds for combinatorial semi-banditscited by 26
  9. 2017Sparsity, variance and curvature in multi-armed banditscited by 24
  10. 2019Improved Path-length Regret Bounds for Banditscited by 23
  11. 2020A Closer Look at Small-loss Bounds for Bandits with Graph Feedbackcited by 21
  12. 2017Small-loss bounds for online learning with partial informationcited by 18
7 more
  1. 2023Improved Best-of-Both-Worlds Guarantees for Multi-Armed Bandits: FTRL with General Regularizers and Multiple Optimal Armscited by 18
  2. 2023Best-of-Three-Worlds Linear Bandit Algorithm with Variance-Adaptive Regret Boundscited by 14
  3. 2022Adversarially Robust Multi-Armed Bandit Algorithm with Variance-Dependent Regret Boundscited by 12
  4. 2020Comparator-adaptive Convex Banditscited by 11
  5. 2024Follow-the-Perturbed-Leader with Fr'echet-type Tail Distributions: Optimality in Adversarial Bandits and Best-of-Both-Worldscited by 10
  6. 2015Gains and Losses are Fundamentally Different in Regret Minimization: The Sparse Casecited by 9
  7. 2026Improved Dimension Dependence for Bandit Convex Optimization with Gradient Variationscited by 5

Built on by

Not cited yet.