# On Randomized Algorithms in Online Strategic Classification

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 23 of its 31 references that are in the map.
- First posted on arXiv 5 Feb 2026.

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

- [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)
- [Explore no more: Improved high-probability regret bounds for non-stochastic bandits](https://mlsanity.com/paper/1506.03271/) (2015)
- [The Social Cost of Strategic Classification](https://mlsanity.com/paper/1808.08460/) (2018)
- [Strategic Classification is Causal Modeling in Disguise](https://mlsanity.com/paper/1910.10362/) (2019)
- [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)
- [Causal Strategic Linear Regression](https://mlsanity.com/paper/2002.10066/) (2020)
- [PAC-Learning for Strategic Classification](https://mlsanity.com/paper/2012.03310/) (2020)
- [The Strategic Perceptron](https://mlsanity.com/paper/2008.01710/) (2020)
- [Information Discrepancy in Strategic Learning](https://mlsanity.com/paper/2103.01028/) (2021)
- [Maximizing Welfare with Incentive-Aware Evaluation Mechanisms](https://mlsanity.com/paper/2011.01956/) (2020)
- [The Disparate Equilibria of Algorithmic Decision Making when Individuals Invest Rationally](https://mlsanity.com/paper/1910.04123/) (2019)
- [The Role of Randomness and Noise in Strategic Classification](https://mlsanity.com/paper/2005.08377/) (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)
- [Strategic Littlestone Dimension: Improved Bounds on Online Strategic Classification](https://mlsanity.com/paper/2407.11619/) (2024)
- [The Real Price of Bandit Information in Multiclass Classification](https://mlsanity.com/paper/2405.10027/) (2024)
- [Should Decision-Makers Reveal Classifiers in Online Strategic Classification?](https://mlsanity.com/paper/2506.01936/) (2025)

## Abstract (arXiv)

Online strategic classification studies settings in which agents strategically modify their features to obtain favorable predictions. For example, given a classifier that determines loan approval based on credit scores, applicants may open or close credit cards and bank accounts to obtain a positive prediction. The learning goal is to achieve low mistake or regret bounds despite such behavior. While randomized algorithms have the potential to offer advantages to the learner in strategic settings, they have been largely underexplored. In the realizable setting, no lower bound is known for randomized algorithms, and existing lower bound constructions for deterministic learners can be circumvented by randomization. In the agnostic setting, the best known regret upper bound is O(T3/4log1/4T|mathcal H|), which is far from the standard online learning rate of O(√Tlog|mathcal H|). In this work, we provide refined bounds for online strategic classification in both settings; our bounds depend on the Littlestone dimension Ldim(mathcal H) of the hypothesis class mathcal H and the maximum degree Delta of the manipulation graph. In the realizable setting, we extend, for T > Ldim(mathcal H) Delta2, the existing lower bound Omega(Ldim(mathcal H) Delta) for deterministic learners to all learners. This yields the first lower bound that applies to randomized learners. We then provide the first randomized learner that improves the known (deterministic) upper bound of O(Ldim(mathcal H) · Delta log Delta). In the agnostic setting, we give an improper randomized learner that improves the regret upper bound to O(√Tlog|mathcal H|), matching the standard online learning rate. We also show a larger lower bound for all proper learning rules, demonstrating that improperness is necessary to achieve the optimal rate.