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

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 $\tilde{\mathcal{O}}(K+\sqrt{K{Q}_{\mathrm{\infty },1}})$ regret, where $Q_{\mathrm{\infty },1}$ is the first-order path length, and left open whether $\tilde{\mathcal{O}}(\text{poly}(K)\sqrt{1+Q_{\mathrm{\infty },2}})$ regret is achievable under bandit feedback, where $Q_{\mathrm{\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}(K\log (KT)+\sqrt{K\log (KT)(1+Q_{\mathrm{\infty },2})})$ expected regret when $Q_{\mathrm{\infty },2}$ is known, where $T$ is the horizon. This matches the $\mathrm{\Omega }(\sqrt{K{Q}_{\mathrm{\infty },2}})$ lower bound up to logarithmic factors and additive terms. We further remove the knowledge of $Q_{\mathrm{\infty },2}$ using an adaptive restart scheme whose path-length estimator has uniformly bounded increments.