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

The paper investigates the adversarial multi-armed bandit problem against oblivious loss sequences, focusing on adaptivity to temporal variation. While prior work by Bubeck et al. (2019) established first-order path-length guarantees of order tilde{O}(K + sqrt{KQ_infty,1}), it remained an open question whether a sharper second-order path-length regret bound of order tilde{O}(poly(K)sqrt{1 + Q_infty,2}) could be achieved under bandit feedback, matching what was already known in the full-information experts setting.

Rather than designing a new algorithm, the author demonstrates that the exact same recent-arm-biased optimistic mirror-descent algorithm proposed by Bubeck et al. (2019) achieves the desired second-order guarantee under a more careful and refined analysis. Standard analyses bound the sampling bias by relaxing terms into first-order movement measures. The key technical innovation here is to combine the bias term directly with the squared prediction error, retaining a signed difference and carefully managing the log-barrier stability divergence. To eliminate the assumption of knowing Q_infty,2 in advance, the author further incorporates an adaptive restart scheme with a path-length estimator possessing uniformly bounded increments.

With oracle tuning based on the known second-order path length Q_infty,2, the algorithm yields an expected regret bound matching the omega(sqrt{KQ_infty,2}) lower bound up to logarithmic factors and lower-order additive terms. When the exact value of Q_infty,2 is unknown, the parameter-free adaptive restart variant achieves an analogous guarantee with an additional logarithmic penalty in the horizon T.

This result resolves a prominent open problem posed by Bubeck et al. and Wei and Luo, closing the theoretical gap between full-information online learning and partial-feedback bandit environments regarding second-order temporal smoothness.