Abstract
We study the linear contextual bandit problem in the presence of adversarial corruption, where the interaction between the player and a possibly infinite decision set is contaminated by an adversary that can corrupt the reward up to a corruption level $C$ measured by the sum of the largest alteration on rewards in each round. We present a variance-aware algorithm that is adaptive to the level of adversarial contamination $C$. The key algorithmic design includes (1) a multi-level partition scheme of the observed data, (2) a cascade of confidence sets that are adaptive to the level of the corruption, and (3) a variance-aware confidence set construction that can take advantage of low-variance reward. We further prove that the regret of the proposed algorithm is $\tilde{O}(C^2d\sqrt{\sum_{t = 1}^T \sigma_t^2} + C^2R\sqrt{dT})$, where $d$ is the dimension of context vectors, $T$ is the number of rounds, $R$ is the range of noise and $\sigma_t^2,t=1\ldots,T$ are the variances of instantaneous reward. We also prove a gap-dependent regret bound for the proposed algorithm, which is instance-dependent and thus leads to better performance on good practical instances. To the best of our knowledge, this is the first variance-aware corruption-robust algorithm for contextual bandits. Experiments on synthetic data corroborate our theory.
1. Introduction
Linear Contextual Bandits (LCB) are a cornerstone of modern recommendation systems and personalized medicine, allowing agents to make decisions based on high-dimensional context vectors. However, standard LCB algorithms, such as the Optimism-in-the-Face-of-Uncertainty (OFUL) approach, are notoriously fragile when faced with adversarial data. In real-world scenarios like click-fraud or sensor manipulation, an adversary can corrupt rewards to mislead the learner.
Existing robust bandit literature often assumes a finite number of actions or requires prior knowledge of the total corruption level $C$. This paper addresses these limitations by introducing a variance-aware, corruption-robust algorithm that adapts to unknown corruption levels in infinite action spaces.
2. Methodology: Multi-level Weighted OFUL
The proposed algorithm, Multi-level weighted OFUL, integrates three primary defensive mechanisms to maintain performance under attack:
2.1 Multi-level Partitioning and Sub-sampling
The algorithm maintains a "cascade" of learners, each corresponding to a different guess of the corruption magnitude ($2^l$). By randomly assigning each round of data to a specific level, the algorithm ensures that even if an adversary heavily corrupts a portion of the data, higher-level learners remain statistically "cleaner." This partitioning allows the agent to identify and rely on the most reliable data estimates without knowing $C$ beforehand.
2.2 Variance-Awareness and Heteroscedastic Noise
Unlike traditional algorithms that treat all noise as uniform, our approach utilizes weighted ridge regression to account for heteroscedasticity (varying noise levels). By incorporating the variance ($\sigma_t^2$) of rewards, the algorithm can "trust" low-variance data more. This is a critical defense: if an adversary attempts to corrupt a low-noise reward, the deviation is more easily detected and mitigated by the variance-aware weighting.
2.3 Cascade of Confidence Sets
The algorithm constructs confidence ellipsoids that intersect global data with level-specific data. This geometric approach allows the learner to maintain valid confidence sets even when the action space is infinite, overcoming the limitations of "action elimination" strategies used in prior work.
3. Theoretical Contributions
We provide a rigorous analysis of the algorithm's regret, defined as the difference between the rewards of the optimal policy and the agent's choices.
- Regret Bound: The algorithm achieves a regret of $\tilde{O}(C^2d\sqrt{\sum_{t = 1}^T \sigma_t^2} + C^2R\sqrt{dT})$. This bound is sub-linear, ensuring the agent eventually learns the optimal policy provided the corruption $C$ grows slower than $T^{1/4}$.
- The $C^2$ Penalty: A key theoretical insight is the cost of uncertainty regarding the adversary. While regret scales linearly with $C$ if the corruption level is known, it scales quadratically ($C^2$) when $C$ is unknown, highlighting the fundamental difficulty of defending against an invisible adversary.
- Gap-Dependent Analysis: We also establish a gap-dependent regret bound. This instance-dependent metric shows that the algorithm performs significantly better when there is a clear margin between the best and second-best actions.
4. Empirical Results
We evaluated the algorithm using synthetic datasets with 20-dimensional context vectors ($d=20$) over 10,000 rounds ($T=10,000$). To simulate a targeted attack, the adversary flipped the sign of the true reward for the first $k$ rounds, attempting to force the learner to "unlearn" the optimal policy.
In simulations with heavy corruption ($C=900$), Multi-level weighted OFUL significantly outperformed standard OFUL and variance-aware (but non-robust) baselines. While standard algorithms were completely misled by the initial attack and failed to recover, our proposed algorithm successfully identified the underlying reward pattern and achieved low regret.
5. Conclusion and Future Work
This work presents the first variance-aware, corruption-robust framework for linear contextual bandits. By leveraging heteroscedastic noise estimation and multi-level data partitioning, the algorithm provides robust guarantees without requiring prior knowledge of the adversary's strength.
Future research will focus on reducing the $C^2$ dependence to a linear $C$ dependence and validating the algorithm on real-world datasets, such as advertising logs containing known fraudulent activity. Additionally, exploring methods for variance estimation in black-box environments remains an important open challenge.
Summary updated