Efficient Online Bandit Multiclass Learning with $\tilde{O}(\sqrt{T})$ Regret
This provides a solution to a long-standing open problem in online learning, with potential applications in domains requiring efficient multiclass prediction under bandit feedback.
The paper tackles the bandit online multiclass learning problem by presenting an efficient second-order algorithm that achieves $ ilde{O}(\sqrt{T})$ regret, solving an open problem from 2009, and shows favorable experimental performance against earlier algorithms.
We present an efficient second-order algorithm with $\tilde{O}(\frac{1}η\sqrt{T})$ regret for the bandit online multiclass problem. The regret bound holds simultaneously with respect to a family of loss functions parameterized by $η$, for a range of $η$ restricted by the norm of the competitor. The family of loss functions ranges from hinge loss ($η=0$) to squared hinge loss ($η=1$). This provides a solution to the open problem of (J. Abernethy and A. Rakhlin. An efficient bandit algorithm for $\sqrt{T}$-regret in online multiclass prediction? In COLT, 2009). We test our algorithm experimentally, showing that it also performs favorably against earlier algorithms.