# Strategic Littlestone Dimension: Improved Bounds on Online Strategic Classification

arXiv: https://arxiv.org/abs/2407.11619 · HTML: https://mlsanity.com/paper/2407.11619/

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 29 references that are in the map.
- First posted on arXiv 16 Jul 2024.

## Builds on (most cited first, 17 of 17)

- [Performative Prediction](https://mlsanity.com/paper/2002.06673/) (2020)
- [Strategic Classification](https://mlsanity.com/paper/1506.06980/) (2015)
- [Strategic Classification from Revealed Preferences](https://mlsanity.com/paper/1710.07887/) (2017)
- [How Do Classifiers Induce Agents To Invest Effort Strategically?](https://mlsanity.com/paper/1807.05307/) (2018)
- [The Disparate Effects of Strategic Manipulation](https://mlsanity.com/paper/1808.08646/) (2018)
- [Strategic Classification in the Dark](https://mlsanity.com/paper/2102.11592/) (2021)
- [PAC-Learning for Strategic Classification](https://mlsanity.com/paper/2012.03310/) (2020)
- [The Strategic Perceptron](https://mlsanity.com/paper/2008.01710/) (2020)
- [Maximizing Welfare with Incentive-Aware Evaluation Mechanisms](https://mlsanity.com/paper/2011.01956/) (2020)
- [On classification of strategic agents who can both game and improve](https://mlsanity.com/paper/2203.00124/) (2022)
- [Strategic Classification under Unknown Personalized Manipulation](https://mlsanity.com/paper/2305.16501/) (2023)
- [Learning Losses for Strategic Classification](https://mlsanity.com/paper/2203.13421/) (2022)
- [Fundamental Bounds on Online Strategic Classification](https://mlsanity.com/paper/2302.12355/) (2023)
- [Learnability Gaps of Strategic Classification](https://mlsanity.com/paper/2402.19303/) (2024)
- [Multiclass Online Learnability under Bandit Feedback](https://mlsanity.com/paper/2308.04620/) (2023)
- [Bandit-Feedback Online Multiclass Classification: Variants and Tradeoffs](https://mlsanity.com/paper/2402.07453/) (2024)
- [Sequential Strategic Screening](https://mlsanity.com/paper/2301.13397/) (2023)

## Built on by (most cited first, 8 of 8)

- [Incentive-Aware Machine Learning; Robustness, Fairness, Improvement & Causality](https://mlsanity.com/paper/2505.05211/) (2025)
- [Should Decision-Makers Reveal Classifiers in Online Strategic Classification?](https://mlsanity.com/paper/2506.01936/) (2025)
- [Learning in Structured Stackelberg Games](https://mlsanity.com/paper/2504.09006/) (2025)
- [Anticipating Gaming to Incentivize Improvement: Guiding Agents in (Fair) Strategic Classification](https://mlsanity.com/paper/2505.05594/) (2025)
- [Conservative classifiers do consistently well with improving agents: characterizing statistical and online learning](https://mlsanity.com/paper/2506.05252/) (2025)
- [Revealing Positive and Negative Role Models to Help People Make Good Decisions](https://mlsanity.com/paper/2603.02495/) (2026)
- [On Randomized Algorithms in Online Strategic Classification](https://mlsanity.com/paper/2602.06257/) (2026)
- [Online Learning with Improving Agents: Multiclass, Budgeted Agents and Bandit Learners](https://mlsanity.com/paper/2602.17103/) (2026)

## Abstract (arXiv)

We study the problem of online binary classification in settings where strategic agents can modify their observable features to receive a positive classification. We model the set of feasible manipulations by a directed graph over the feature space, and assume the learner only observes the manipulated features instead of the original ones. We introduce the Strategic Littlestone Dimension, a new combinatorial measure that captures the joint complexity of the hypothesis class and the manipulation graph. We demonstrate that it characterizes the instance-optimal mistake bounds for deterministic learning algorithms in the realizable setting. We also achieve improved regret in the agnostic setting by a refined agnostic-to-realizable reduction that accounts for the additional challenge of not observing agents' original features. Finally, we relax the assumption that the learner knows the manipulation graph, instead assuming their knowledge is captured by a family of graphs. We derive regret bounds in both the realizable setting where all agents manipulate according to the same graph within the graph family, and the agnostic setting where the manipulation graphs are chosen adversarially and not consistently modeled by a single graph in the family.