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

Mengxiao Zhang

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{\ma…