Online Learning with Improving Agents: Multiclass, Budgeted Agents and Bandit Learners

We consider the problem of universal transductive online classification with a possibly unbounded label space. This setting considers online learning, with the sequence of instances (without labels) known to the learner in advance. We say a concept class $\mathcal{H}$ is learnable if there is a learning algorithm $\mathcal{A}$, such that for every realizable sequence, the number of mistakes made by $\mathcal{A}$ grows at most sublinearly with the number of predictions. We characterize the learnability of this setting and show that there are only two possible optimal rates for the learnable classes: either bounded or increasing logarithmically. We introduce a new combinatorial structure, called ``Level-Constrained-Littlestone-Littlestone (LCLL) tree'', which, along with the indifference property, characterizes the learnability. We also extend the learnability result to the agnostic case and the case where only the stochastic process that generates the instance sequence is known.

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<\infty$, we prove a regret upper bound of $O(\min\{T,\sqrt{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.

Classical models of strategic classification treat agents' responses to a deployed classifier as cosmetic: features change, but true labels do not. We study an improvement-aware variant in which strategic responses can change outcomes: agents choose post-deployment features strategically at a cost, and labels are then drawn from a fixed conditional outcome law. We formalize this problem for linear classifiers under a single-index qualification model and linear-decomposable costs. Under these assumptions, agents' best responses reduce to a closed-form shift of the decision boundary, and the resulting improvement-aware classification problem is learnable with linear sample complexity. As post-deployment labels are unavailable a priori, we begin by establishing a generalization bound with oracle access to the outcome law. One of our main contributions is a practical plug-in algorithm that replaces the oracle with an estimate, together with a bound on its improvement-aware error. We also show that the optimal classifier for standard strategic classification is a better proxy for the improvement-aware objective than the non-strategic Bayes-optimal classifier. Experiments on semi-synthetic and synthetic data support these findings and the plausibility of our assumptions.