Near Optimal Adversarial Attack on UCB Bandits

Shiliang Zuo

Abstract

This paper studies a stochastic multi-arm bandit problem where rewards are subject to adversarial corruption. We propose a novel attack strategy that manipulates a learner employing the Upper Confidence Bound (UCB) algorithm into pulling a non-optimal target arm $T - o(T)$ times with a cumulative cost that scales as $\widehat{O}(\sqrt{\log T})$, where $T$ is the number of rounds. We also prove the first lower bound on the cumulative attack cost, which matches the upper bound up to $O(\log \log T)$ factors, demonstrating the near-optimality of the proposed strategy.

Introduction

Stochastic multi-arm bandits (MAB) are essential for sequential decision-making in recommendation systems and online advertising. Standard algorithms like UCB and Thompson Sampling (TS) are designed to minimize regret in benign environments. However, these algorithms are increasingly deployed in settings where rewards may be subject to adversarial manipulation. This paper investigates the security of these algorithms, demonstrating that they are significantly more vulnerable than previously estimated and proposing robust defense mechanisms.

Near-Optimal Adversarial Attacks

The primary goal of an adversary is to hijack the learner's decision process with minimal budget. While previous work estimated a corruption cost of $O(\log T)$, this work introduces an "exponential gap" strategy that reduces this cost to $O(\sqrt{\log T})$.

In this scenario, a malicious actor injects corruption to ensure the perceived difference between a target arm and other arms grows exponentially relative to the number of times non-target arms are pulled. This forces the learner to pull non-target arms only $O(\log \log T)$ times. Because these arms are pulled so rarely, the adversary expends minimal budget to keep them suppressed. The paper proves a matching lower bound of $\Omega(\sqrt{\log T})$, establishing this attack as near-optimal for both UCB and Thompson Sampling.

Robust Defense Strategies

Traditional low-regret algorithms are easily hijacked because their aggressive pursuit of the "best" arm makes them predictable. To defend against such attacks, the paper shifts the objective from regret minimization to maximizing the competitive ratio—the ratio of the learner's reward to the optimal reward.

Two defense algorithms are proposed:

  1. Smoothed Myopic Response: A strategy that picks the empirically best arm most of the time but pulls every other arm with a small, fixed probability $\rho$.
  2. Quantal Response: Inspired by behavioral economics, this uses a softmax function to assign pull probabilities, adding "noise" to the decision process to hinder adversarial manipulation.
Algorithm 6: The Smoothed Response defense strategy.

Results and Performance

Numerical simulations confirm that the proposed attack strategy is significantly more efficient than previous state-of-the-art methods. For example, in a two-arm bandit scenario with Gaussian rewards ($\sigma=0.1, \mu=0.1$), the cumulative attack cost was reduced from 23.6 to just 1.3.

Regarding defense, the Smoothed and Quantal Response algorithms achieve a competitive ratio arbitrarily close to 1, provided the adversary's budget is sublinear ($o(T)$). As shown in the cumulative reward plots, these "smoothed" learners eventually identify the true best arm despite adversarial noise, provided they are willing to accept a small degree of intentional suboptimality.

Cumulative reward of the Smoothed Response algorithm.

Interestingly, simpler algorithms like $\epsilon$-greedy are naturally harder to attack, requiring a budget of $\Omega(\log T)$. This suggests a fundamental trade-off: the very features that make UCB and TS efficient in benign settings are exactly what make them vulnerable to manipulation.

Conclusion

This work provides a tight characterization of the vulnerability of popular bandit algorithms to adversarial attacks. By introducing near-optimal attack strategies and robust "smoothed" defense mechanisms, it highlights the need for security-aware design in sequential decision-making systems. Future work may explore intermediate metrics between regret and competitive ratio to capture robustness more granularly.

Summary updated

Abstract

I study a stochastic multi-arm bandit problem where rewards are subject to adversarial corruption. I propose a novel attack strategy that manipulates a learner employing the UCB algorithm into pulling some non-optimal target arm $T - o(T)$ times with a cumulative cost that scales as $\widehat{O}(\sqrt{\log T})$, where $T$ is the number of rounds. I also prove the first lower bound on the cumulative attack cost. The lower bound matches the upper bound up to $O(\log \log T)$ factors, showing the proposed attack strategy to be near optimal.
BibTeX
@inproceedings{zuo2024near,
  author = {Shiliang Zuo},
  title = {{Near Optimal Adversarial Attack on UCB Bandits}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2024},
}
Figure