Abstract: 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 $\mathcal{O}(\max \{ B, K\ln 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, K\ln T\})$. Our results illustrate the robustness of classic bandits algorithms against strategic manipulations as long as $B=o(T)$.
Introduction
In the standard Multi-Armed Bandit (MAB) problem, we assume rewards come from fixed, honest distributions. In the "adversarial" version, we assume a malicious attacker is trying to ruin our performance. However, many real-world economic systems—like Amazon marketplace or Yelp—fall somewhere in between.
The "arms" in these systems are strategic actors (sellers or restaurants). They aren't trying to destroy the system; they just want to be recommended as often as possible. To do this, they might "manipulate" their rewards—for instance, by offering discounts or coupons to buy better ratings. This paper asks: If arms can strategically manipulate their own reward feedback subject to a total budget, do our classic bandit algorithms break?
Theoretical Framework
The interaction is modeled as a stochastic game between a principal (the algorithm) and $K$ strategic arms.
- The Budget: Each arm $i$ has a total budget $B_i$ that it can use to boost its realized reward over the entire time horizon $T$.
- The Strategy: Arms can be adaptive, meaning they decide how much budget to spend based on the history of the game.
- The Algorithms: The researchers provide a rigorous regret analysis for three workhorses of the MAB world: Upper Confidence Bound (UCB), $\epsilon$-Greedy, and Thompson Sampling (TS).
A key technical contribution is the analysis of the Lump Sum Investing (LSI) strategy, where an arm spends its entire budget the very first time it is pulled. For UCB, the authors prove that LSI is actually a dominant strategy—the best possible move regardless of what other arms do.
Key Insights and Robustness
Robustness is "Baked In"
The most striking insight is that you don't need a specialized "robust" algorithm to handle strategic players. Standard UCB and Thompson Sampling already achieve a regret bound of $O(\max\{B, K \ln T\})$. In a purely adversarial setting (where an attacker can change any arm's reward), a budget of $O(\ln T)$ can force UCB to suffer linear regret ($O(T)$). But in this strategic setting—where arms only manipulate their own rewards and the optimal arm is "honest"—the algorithm remains robust.
The LSI Dominance and Linear Degradation
For UCB, the "best" way to trick the system is to go all-in early (LSI). This boosts the arm's average reward and confidence interval significantly at the start. However, the algorithm eventually "learns" through the noise, and the arm's budget eventually runs out, allowing the true optimal arm to take over. Regret scales linearly with the total budget $B$. As long as the total manipulation across all arms is sublinear ($B = o(T)$), the principal will still converge to the best arm.
Experimental Validation
As a theoretical paper, the authors use synthetic simulations to validate their proofs. They tested 3-arm bandit problems with Gaussian distributions (unbounded rewards) and Beta distributions (bounded rewards) for $T = 10^4$ rounds across 100 trials.
Key Results
- Tight Upper and Lower Bounds: All three algorithms achieve an expected regret of $O(\max\{B, K \ln T\})$. The authors proved a matching lower bound of $\Omega(\max\{B, K \ln T\})$, showing that their analysis is essentially tight.
- Equilibrium Behavior: For UCB, they characterized the subgame perfect Nash equilibrium, showing that the "Lump Sum" strategy is the rational choice for strategic arms.
- Simulation Validation: The experiments confirmed that regret grows linearly with the budget $B$ until the budget is exhausted, at which point the regret curve flattens back to the standard logarithmic growth.
Conclusion and Future Work
While the authors found the Nash equilibrium for UCB, doing so for $\epsilon$-Greedy and Thompson Sampling is more complex due to algorithmic randomness. Characterizing the exact equilibrium for these remains an open question. Additionally, the model assumes the optimal arm is "honest" and doesn't reduce its reward. Future work could explore settings where the "best" arm might also be incentivized to behave in more complex ways, or where the underlying true quality of arms changes over time (non-stationarity).
Summary updated