arXiv · Oct 23, 2026
Optimal Multiclass Online Regret with Arbitrary Label Spaces
By Sajad Ashkezari, Shai Ben-David
We determine the optimal regret in agnostic multiclass online learning with arbitrary, possibly infinite, label spaces. For every hypothesis class of multiclass Littlestone dimension d<∞, we prove a regret upper bound of O(min{T,√dT}) over T rounds, matching the known lower bound. This resolves a question of Hanneke et al. (2023) and extends the optimal binary regret bound of Alon et al. (2021). Our proof strengthens the one-sided expert cover of Hanneke et al. (2023) to a fractional cover. We combine this cover with a minimax reduction to a finite expert game, whose best-response rewards provide the disagreement bounds needed for chaining.