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

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 respect to a family of loss functions parameterized by \(\eta\), for a range of \(\eta\) restricted by the norm of the competitor. The family of loss functions ranges from hinge loss (\(\eta =0\)) to squared hinge loss (\(\eta =1\)). This provides a solution to the open problem of (J. Abernethy and A. Rakhlin. An efficient bandit algorithm for \(\sqrt{\sqrt{T}}\)-regret in online multiclass prediction? In COLT, 2009). We test our algorithm experimentally, showing that it also performs favorably against earlier algorithms.