Abstract: We consider a stochastic linear bandit problem in which the rewards are not only subject to random noise, but also adversarial attacks subject to a suitable budget $C$ (i.e., an upper bound on the sum of corruption magnitudes across the time horizon). We provide two variants of a Robust Phased Elimination algorithm, one that knows $C$ and one that does not. Both variants are shown to attain near-optimal regret in the non-corrupted case $C = 0$, while incurring additional additive terms respectively having a linear and quadratic dependency on $C$ in general. We present algorithm independent lower bounds showing that these additive terms are near-optimal. In addition, in a contextual setting, we revisit a setup of diverse contexts, and show that a simple greedy algorithm is provably robust with a near-optimal additive regret term, despite performing no explicit exploration and not knowing $C$.
1. Introduction
Stochastic linear bandits are fundamental to modern decision-making systems, ranging from personalized recommendation engines to clinical trial designs. These models typically rely on the assumption that rewards are generated by a linear function of the chosen action plus random, zero-mean noise. However, in many real-world applications, this assumption is violated by malicious actors or system failures. Adversaries can subtly corrupt rewards to mislead the learner, often causing standard algorithms like Upper Confidence Bound (UCB) or Thompson Sampling to fail catastrophically.
This paper addresses the challenge of designing algorithms that are resilient to such adversarial attacks. We introduce a framework for "corruption-tolerant" bandits that maintain high performance even when an adversary manipulates rewards within a total budget $C$.
2. The Budgeted Adversary Model
We consider a learner who interacts with an environment over $T$ rounds. In each round, the learner chooses an action $x_t$ and receives a reward $y_t$. Unlike the standard model, the reward is defined as:
$$y_t = \langle x_t, \theta^* \rangle + \eta_t + c_t$$
where $\theta^*$ is the unknown parameter, $\eta_t$ is random noise, and $c_t$ is the corruption injected by an adversary. The adversary is "budgeted," meaning the total magnitude of all attacks is bounded: $\sum_{t=1}^T |c_t| \le C$. The adversary is assumed to be powerful, observing the learner's action and the random noise before deciding on the corruption $c_t$. The goal is to minimize regret—the difference between the rewards of the optimal actions and the rewards actually received—without knowing the specific timing or magnitude of the attacks.
3. Robust Phased Elimination (RPE)
To counter these attacks, we propose the Robust Phased Elimination (RPE) algorithm. RPE deviates from the step-by-step updates of UCB in several key ways:
- Epoch-Based Exploration: RPE operates in epochs of increasing length. This structure prevents the algorithm from overreacting to individual corrupted rewards.
- Experimental Design: Within each epoch, the algorithm utilizes a near-optimal experimental design (computed via the Frank-Wolfe algorithm) to select a set of actions that maximizes information gain about $\theta^*$.
- Robust Estimation: Instead of a simple least-squares estimator, RPE uses a robust estimator that averages rewards for specific actions, effectively diluting the impact of any single corrupted observation.
3.1 The Price of Ignorance
A central finding of our work is the performance gap between knowing and not knowing the attack budget $C$.
- Known $C$: If the budget is known, RPE can use fixed, enlarged confidence bounds to account for potential corruption. This results in a regret of $\tilde{O}(\sqrt{dT} + Cd^{3/2})$, where the penalty for corruption scales linearly with $C$.
- Unknown $C$: If $C$ is unknown, the algorithm must be more conservative, leading to a regret of $\tilde{O}(\sqrt{dT} + Cd^{3/2} + C^2)$.
We provide algorithm-independent lower bounds proving that this $O(C^2)$ term is a fundamental "price of ignorance" for any algorithm that remains optimal in the uncorrupted ($C=0$) case.
4. Robustness through Context Diversity
In the contextual bandit setting, where the learner receives feature vectors (contexts) each round, we explore the power of Context Diversity. We demonstrate that if the environment naturally provides diverse contexts—meaning the features cover all directions in the feature space—a simple Greedy Algorithm becomes inherently robust.
In this scenario, the natural randomness of the environment acts as a shield. Because the algorithm is forced to see the problem from many different angles, it is much harder for an adversary to hide the optimal arm. Remarkably, this greedy approach requires no explicit exploration and does not need to know the budget $C$ to achieve near-optimal additive regret.
5. Empirical Results
We validated our theoretical findings using both synthetic datasets and the MovieLens-100K recommendation dataset. In the MovieLens experiments, movies were treated as contexts and users as underlying parameters.
Our results show that while standard baselines like LinUCB can occasionally perform well, they are highly susceptible to "catastrophic failure" under targeted attacks. In contrast, RPE and the diversity-based greedy algorithm remained stable across various attack intensities, showing significantly lower variance and consistent performance.
6. Conclusion
This work establishes rigorous bounds on the robustness of linear bandits. We show that while adversaries can force a penalty on performance, phased elimination and context diversity provide powerful defenses. Future research may focus on improving the dimension scaling ($d^{3/2}$) and extending these robust techniques to infinite or continuous action spaces.
Summary updated