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

Sajad Ashkezari; Shai Ben-David

cs.LGFeb 19, 2026

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

Authors: Sajad Ashkezari, Shai Ben-David

Organizations: University of Waterloo

Abstract

We investigate the recently introduced model of learning with improvements, where agents are allowed to make small changes to their feature values to be warranted a more desirable label. We extensively extend previously published results by providing combinatorial dimensions that characterize online learnability in this model, by analyzing the multiclass setup, learnability in a bandit feedback setup, modeling agents' cost for making improvements and more.

Figures & tables

\tilde{h}^{(t)}(x)=\begin{cases}1&\quad\text{if}\quad\mathrm{ILdim}(\mathrm{VS}_{x,0})<\mathrm{ILdim}(\mathrm{VS})\\ 0&\quad\text{otherwise}\end{cases}

Algorithm 1 ISOA

Online Learning

Online learning studies algorithms that update predictions or decisions from sequential feedback while controlling cumulative error or regret.

See all 131 papers

Universal Multiclass Transductive Online Learning
May 28, 2026Steve Hanneke, Hongao WangMulticlass Classification Transductive Learning
Department of Computer Science, Purdue University, West Lafayette, IN 47907, USA
Optimal Multiclass Online Regret with Arbitrary Label Spaces
Oct 23, 2026Sajad Ashkezari, Shai Ben-DavidMulticlass Classification Statistical Learning Theory
University of Waterloo
Linear Strategic Classification with Endogenous Improvements
May 31, 2026Siddharth Shrivastava, Mahvith Akshintala, B Vamsha Vardhan Reddy +3Strategic Classification Linear Classification
Department of Artificial Intelligence, IIT Hyderabad · IIIT Hyderabad · Departement of Artifical Intelligence, IIT Hyderabad

May 28, 2026J/K move · Enter open · S save

Universal Multiclass Transductive Online Learning

Steve Hanneke, Hongao Wang

Department of Computer Science, Purdue University, West Lafayette, IN 47907, USA

Multiclass Classification Transductive Learning Classification Statistical Learning Theory Supervised Learning

Open paper AskPDF arXiv

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.

Abstract

Online Learning

Explore similar work

Universal Multiclass Transductive Online Learning

Optimal Multiclass Online Regret with Arbitrary Label Spaces

Linear Strategic Classification with Endogenous Improvements