Toward Optimal Second-Order Path-Length Guarantee for Adversarial Multi-Armed Bandits
2026-08-17 • Machine Learning
Machine Learning
AI summaryⓘ
The authors study a problem where someone tries to choose the best option out of many while losses change in tricky ways. Previous work gave a way to measure how well an algorithm does based on how much the losses change (called path length), but only for a simpler version of this measurement. The authors show that the same algorithm actually works well even for a more detailed version of this measurement (second-order path length), matching the best possible performance except for small extra factors. They also improve the algorithm so it does not need to know this detailed measurement in advance by adapting as it goes.
adversarial banditsmulti-armed banditregret minimizationpath lengthsecond-order path lengthoblivious lossesadaptive algorithmsupper boundlower boundrestart scheme
Authors
Mengxiao Zhang
Abstract
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 $\widetilde{\mathcal{O}}(K+\sqrt{KQ_{\infty,1}})$ regret, where $Q_{\infty,1}$ is the first-order path length, and left open whether $\widetilde{\mathcal{O}}(\text{poly}(K)\sqrt{1+Q_{\infty,2}})$ regret is achievable under bandit feedback, where $Q_{\infty,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 $\mathcal{O}\left(K\log(KT)+\sqrt{K\log(KT)\bigl(1+Q_{\infty,2}\bigr)}\right)$ expected regret when $Q_{\infty,2}$ is known, where $T$ is the horizon. This matches the $Ω(\sqrt{KQ_{\infty,2}})$ lower bound up to logarithmic factors and additive terms. We further remove the knowledge of $Q_{\infty,2}$ using an adaptive restart scheme whose path-length estimator has uniformly bounded increments.