Efficient Online Bandit Multiclass Learning with $\tilde{O}(\sqrt{T})$ Regret

Alina Beygelzimer, Francesco Orabona, Chicheng Zhang

We present an efficient second-order algorithm with $\tilde{O}(\frac{1}{\eta }\sqrt{T})$ regret for the bandit online multiclass problem. The regret bound holds simultaneously with respe…