# The Intrinsic Robustness of Stochastic Bandits to Strategic Manipulation

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

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 4 Jun 2019.

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

- [Learning with Exposure Constraints in Recommendation Systems](https://mlsanity.com/paper/2302.01377/) (2023)
- [Combinatorial Bandits under Strategic Manipulations](https://mlsanity.com/paper/2102.12722/) (2021)
- [Adversarial Attacks on Adversarial Bandits](https://mlsanity.com/paper/2301.12595/) (2023)
- [Bandits Meet Mechanism Design to Combat Clickbait in Online Recommendation](https://mlsanity.com/paper/2311.15647/) (2023)
- [Multi-armed Bandit Algorithm against Strategic Replication](https://mlsanity.com/paper/2110.12160/) (2021)
- [Strategic Linear Contextual Bandits](https://mlsanity.com/paper/2406.00551/) (2024)
- [Efficient Action Poisoning Attacks on Linear Contextual Bandits](https://mlsanity.com/paper/2112.05367/) (2021)
- [Robust and Performance Incentivizing Algorithms for Multi-Armed Bandits with Strategic Agents](https://mlsanity.com/paper/2312.07929/) (2023)
- [Stealthy Adversarial Attacks on Stochastic Multi-Armed Bandits](https://mlsanity.com/paper/2402.13487/) (2024)
- [Strategic Multi-Armed Bandit Problems Under Debt-Free Reporting](https://mlsanity.com/paper/2501.16018/) (2025)
- [Incentivized Lipschitz Bandits](https://mlsanity.com/paper/2508.19466/) (2025)
- [COBRA: Contextual Bandit Algorithm for Ensuring Truthful Strategic Agents](https://mlsanity.com/paper/2505.23720/) (2025)
- [Optimization-friendly generic mechanisms without money](https://mlsanity.com/paper/2106.07752/) (2021)
- [Reward Teaching for Federated Multi-armed Bandits](https://mlsanity.com/paper/2305.02441/) (2023)
- [MESHA: Mechanism-Enforced Sequential Halving for Strategic Linear Bandits](https://mlsanity.com/paper/2607.14706/) (2026)

## Abstract (arXiv)

Motivated by economic applications such as recommender systems, we study the behavior of stochastic bandits algorithms under strategic behavior conducted by rational actors, i.e., the arms. Each arm is a self-interested strategic player who can modify its own reward whenever pulled, subject to a cross-period budget constraint, in order to maximize its own expected number of times of being pulled. We analyze the robustness of three popular bandit algorithms: UCB, varepsilon-Greedy, and Thompson Sampling. We prove that all three algorithms achieve a regret upper bound O(max  B, Kln T) where B is the total budget across arms, K is the total number of arms and T is length of the time horizon. This regret guarantee holds under arbitrary adaptive manipulation strategy of arms. Our second set of main results shows that this regret bound is tight -- in fact for UCB it is tight even when we restrict the arms' manipulation strategies to form a Nash equilibrium. The lower bound makes use of a simple manipulation strategy, the same for all three algorithms, yielding a bound of Omega(max  B, Kln T). Our results illustrate the robustness of classic bandits algorithms against strategic manipulations as long as B=o(T).