New paper shows UCB bandits are vulnerable to deceptive Stackelberg attacks

A paper accepted to the NExT-Game workshop at ICML 2026 (Seoul, July 11) reveals a previously overlooked security flaw in Upper Confidence Bound (UCB) algorithms—the workhorses of multi-armed bandit exploration. The authors formalize a finite-horizon repeated Stackelberg game where a rational leader (e.g., a recommendation system) faces a boundedly rational follower using UCB to learn reward distributions. Classical strong Stackelberg equilibrium (SSE) assumes the follower immediately best-responds, but UCB's 'optimism in the face of uncertainty' allows the leader to manipulate the follower's empirical history.

In their attack, the leader executes a two-phase deception: first a 'honeypot' phase where it artificially boosts the observed reward of a designated follower action to inflate its UCB index, then a 'trap' phase where the leader switches to a selfish action distribution. Because the manipulated history and exploration bonus dominate competing indices, the follower remains locked into the designated action. The leader's cumulative utility strictly exceeds the classical SSE ceiling, and the manipulation cost is bounded by O(√(T ln T)) regret. The results formally prove incompatibility between static equilibrium prescriptions and dynamically learned incentives, suggesting that AI agents using UCB for exploration in strategic environments may be systematically exploitable.