Coordinated Attacks against Contextual Bandits: Fundamental Limits and Defense Mechanisms

Jeongyeol Kwon, Yonathan Efroni, Constantine Caramanis, Shie Mannor

Abstract

Motivated by online recommendation systems, we propose the problem of finding the optimal policy in multitask contextual bandits when a small fraction $\alpha < 1/2$ of tasks (users) are arbitrary and adversarial. The remaining fraction of good users share the same instance of contextual bandits with $S$ contexts and $A$ actions (items). Naturally, whether a user is good or adversarial is not known in advance. The goal is to robustly learn the policy that maximizes rewards for good users with as few user interactions as possible. Without adversarial users, established results in collaborative filtering show that $O(1/\epsilon^2)$ per-user interactions suffice to learn a good policy, precisely because information can be shared across users. This parallelization gain is fundamentally altered by the presence of adversarial users: unless there are super-polynomial number of users, we show a lower bound of $\tilde{\Omega}(\min(S,A) \cdot \alpha^2 / \epsilon^2)$ per-user interactions to learn an $\epsilon$-optimal policy for the good users. We then show we can achieve an $\tilde{O}(\min(S,A)\cdot \alpha/\epsilon^2)$ upper-bound, by employing efficient robust mean estimators for both uni-variate and high-dimensional random variables. We also show that this can be improved depending on the distributions of contexts.

Introduction

Modern online recommendation systems, such as those used by Netflix or Amazon, rely heavily on collaborative filtering to pool data across millions of users. This "parallelization gain" allows the system to learn optimal recommendations (actions) for specific situations (contexts) much faster than if it learned from each user in isolation. Ideally, with $L$ users, the data required per user drops by a factor of $O(1/L)$.

However, this shared knowledge pool is a prime target for coordinated attacks. If a small fraction of users are malicious bots, they can poison the data to skew recommendations. This paper investigates the fundamental limits of learning in such corrupted multitask settings and proposes a defense mechanism that remains robust even when the identity of the attackers is unknown.

Problem Definition and Threat Model

The authors model the environment as a multitask contextual bandit with $S$ contexts and $A$ actions. A fraction $\alpha < 1/2$ of users are adversarial, while the rest are "good" users sharing a common reward structure. The challenge lies in the fact that the system cannot distinguish between these groups a priori.

Comparison of reward distributions for good vs. adversarial users.

As shown in the figure above, good users provide rewards based on a Bernoulli distribution $Ber(1/2 + \epsilon)$ for optimal actions. In contrast, adversarial users can introduce arbitrary corruptions ($e^{(n)}$) to the reward stream, effectively poisoning the collaborative learning process.

Methodology: Robust MCB

To defend against these attacks, the authors propose the Robust MCB algorithm. The core innovation is the application of robust statistical estimators to filter out adversarial noise:

  1. Univariate Robust Estimation: For frequent context-action pairs, the algorithm uses univariate estimators (like trimmed means) to filter extreme values.
  2. High-Dimensional Robust Estimation: In more realistic scenarios where contexts are diverse, the algorithm treats a user's entire interaction history as a single high-dimensional vector. It then applies advanced robust mean estimation to identify and mitigate coordinated shifts in the data pool.
  3. Context Frequency Optimization: The algorithm adaptively applies these methods based on context popularity, using simpler univariate methods for the "head" of the distribution and high-dimensional methods for the "long tail."

Key Results

Theoretical Limits

The research establishes a new fundamental limit: the presence of adversaries destroys perfect parallelization. Even with an infinite number of users, there is a "sample complexity floor." Any algorithm requires at least $\Omega(\min(S, A) \cdot \alpha^2 / \epsilon^2)$ per-user interactions to find an $\epsilon$-optimal policy. The Robust MCB algorithm nearly matches this with an upper bound of $\tilde{O}(\min(S, A) \cdot \alpha / \epsilon^2)$.

Empirical Validation

In synthetic experiments, Robust MCB demonstrated significant resilience compared to standard approaches. While "Naive UCB" (which ignores adversaries) fails as the corruption rate increases, Robust MCB maintains near-optimal performance.

Robustness of different algorithms against increasing corruption rates (alpha).

As illustrated in the plot above, Robust MCB's sub-optimality remains low and stable even as the corruption rate $\alpha$ grows to 0.05, whereas the performance of Naive UCB and other corruption-robust baselines degrades significantly.

Conclusion

This work highlights that while collaborative learning is powerful, it is fundamentally limited by the presence of coordinated adversaries. By treating user histories as high-dimensional samples and applying robust statistical techniques, it is possible to reclaim much of the parallelization gain and build recommendation systems that are resilient to sophisticated attacks.

Summary updated

Abstract

Motivated by online recommendation systems, we propose the problem of finding the optimal policy in multitask contextual bandits when a small fraction $\alpha < 1/2$ of tasks (users) are arbitrary and adversarial. The remaining fraction of good users share the same instance of contextual bandits with $S$ contexts and $A$ actions (items). Naturally, whether a user is good or adversarial is not known in advance. The goal is to robustly learn the policy that maximizes rewards for good users with as few user interactions as possible. Without adversarial users, established results in collaborative filtering show that $O(1/\epsilon^2)$ per-user interactions suffice to learn a good policy, precisely because information can be shared across users. This parallelization gain is fundamentally altered by the presence of adversarial users: unless there are super-polynomial number of users, we show a lower bound of $\tilde{\Omega}(\min(S,A) \cdot \alpha^2 / \epsilon^2)$ {\it per-user} interactions to learn an $\epsilon$-optimal policy for the good users. We then show we can achieve an $\tilde{O}(\min(S,A)\cdot \alpha/\epsilon^2)$ upper-bound, by employing efficient robust mean estimators for both uni-variate and high-dimensional random variables. We also show that this can be improved depending on the distributions of contexts.
BibTeX
@inproceedings{kwon2022coordinated,
  author = {Jeongyeol Kwon and Yonathan Efroni and Constantine Caramanis and Shie Mannor},
  title = {{Coordinated Attacks against Contextual Bandits: Fundamental Limits and Defense Mechanisms}},
  booktitle = {International Conference on Machine Learning},
  year = {2022},
  url = {https://openreview.net/forum?id=diXS1wJR3l},
}
Figure