Optimal Multiclass Online Regret with Arbitrary Label Spaces

Ashkezari and Ben-David determine the optimal regret in agnostic multiclass online learning when the label space is arbitrary and possibly infinite. For every hypothesis class with finite multiclass Littlestone dimension \(d\), they prove a regret upper bound of \(O(\min\{T, \sqrt{dT}\})\) over \(T\) rounds, which matches the known lower bound.

The result answers a question of Hanneke et al. from 2023 and extends the optimal binary bound of Alon et al. from 2021. The proof strengthens the one-sided expert cover of Hanneke et al. to a fractional cover and combines it with a minimax reduction to a finite expert game, whose best-response rewards supply the disagreement bounds needed for chaining.