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$.
The Challenge of Adversarial Noise
In the idealized world of machine learning theory, "noise" is usually assumed to be a friendly, zero-mean Gaussian process. However, in real-world applications like high-frequency trading, recommender systems, or clinical trials, the noise might actually be a strategic adversary trying to mislead the model.
This research, presented at AISTATS 2021, tackles the challenge of Stochastic Linear Bandits under adversarial attack. In a standard linear bandit problem, a learner chooses an action (an arm), receives a reward that is a linear function of that action's features, and tries to maximize the total reward. This paper adds a malicious term: $Y = \langle \theta, a \rangle + \epsilon + c_t(a)$, where $c_t(a)$ is an adversarial corruption. The adversary has a total budget $C$ (the sum of all corruptions over time) and complete knowledge of the learner’s strategy. By strategically "nudging" rewards, an adversary can trick standard algorithms like LinUCB into choosing suboptimal actions indefinitely.
Methods for Robustness
The authors propose two primary approaches to maintain low regret (the gap between the best possible reward and the learner's actual reward) despite these attacks:
- Robust Phased Elimination (RPE):
- Epoch-based updates: Unlike UCB-style algorithms that update every step, RPE works in epochs.
- G-optimal design: In each epoch, it uses a diverse set of arms to play, solved via a Frank-Wolfe algorithm.
- Robust Estimation: Instead of a simple least-squares fit, it uses an estimator that averages rewards for the same arm. This forces the adversary to spend more of their budget $C$ to significantly bias the estimate.
- Enlarged Confidence Bounds: The algorithm "widens" its uncertainty intervals based on the corruption budget $C$ to ensure the optimal arm isn't accidentally discarded.
- Contextual Greedy Algorithm: In settings where the "context" (the available arms) changes every round and is sufficiently diverse, the authors show that a simple greedy algorithm is naturally robust. The diversity of the environment acts as a natural explorer, making it too expensive for the adversary to hide the true best parameter $\theta$ in every direction.
Key Insights: The Price of Ignorance
One of the most striking findings is the gap between "known $C$" and "unknown $C$." If the learner knows the budget, they can achieve regret that scales linearly with $C$. If they do not, they must be more cautious, leading to a $C^2$ term. The authors provide a lower bound proving this isn't just a weakness of their algorithm—it's a fundamental limit of the problem.
Empirical Performance
The paper evaluates these algorithms using synthetic simulations and the MovieLens 100K dataset. In experiments, RPE showed much lower variance than standard baselines like LinUCB or Thompson Sampling. While standard algorithms sometimes performed well, they were prone to "catastrophic failure" under specific attacks, whereas the robust approaches remained stable.
Conclusion and Future Work
This work establishes that while adversaries can degrade performance, strategic exploration and averaging can mitigate the damage. Key theoretical challenges remain, such as improving the dependence on the dimension $d$ and addressing adversaries that can corrupt contextual features themselves rather than just rewards. However, the results suggest that in complex, high-dimensional real-world data, simple diverse contexts might provide a natural defense against manipulation.
Summary updated