In sequential decision-making frameworks like multi-armed bandits and reinforcement learning, an agent learns by interacting with an environment and observing feedback. However, real-world deployments often expose these systems to adversarial data poisoning, where an attacker manipulates rewards, observations, or actions to mislead the agent.
To defend against these attacks, classical robust statistics relies on a critical piece of information: the corruption budget ($C$), which quantifies the total magnitude or frequency of adversarial interference. Knowing $C$ allows an algorithm to pad its confidence intervals or scale its pessimism bonuses perfectly. But in practice, an agent rarely knows how hostile an environment will be.
If the agent overestimates the corruption budget, it becomes overly conservative, over-padding its confidence intervals and failing to exploit optimal actions. If it underestimates the budget, the adversary can easily exploit the narrow safety margins to hijack the agent's behavior. As Dongruo Zhou et al. point out in Linear Contextual Bandits with Adversarial Corruptions, this dependency creates a severe gap between theoretical robustness and practical deployability.
The core challenge of this research direction is achieving agnostic robustness: designing algorithms that can maintain near-optimal performance when the corruption budget is completely unknown.
Why the Information Gap Breaks Standard Learning
To understand why an unknown corruption budget breaks standard algorithms, consider the classic Upper Confidence Bound (UCB) algorithm. UCB maintains an estimate of each action's reward alongside a confidence interval that shrinks as the action is sampled more frequently. The algorithm optimistically selects the action with the highest upper bound.
When an adversary can corrupt rewards, the true mean of an action can be pulled away from its empirical estimate. If the total corruption budget $C$ is known, the algorithm can expand its confidence intervals by an additive factor proportional to $C$ to guarantee that the true reward still lies within the bounds. Lin Yang 0013 et al. prove in Adversarial Bandits with Corruptions: Regret Lower Bound and No-regret Algorithm that algorithms unaware of this budget cannot achieve sublinear regret, as they fail to protect their confidence intervals from being systematically deceived.
Standard UCB Interval (Unsafe under attack):
[----|--★--|----] <- True reward ★ can be pushed outside by corruption
Budget-Aware Expanded Interval (Safe but requires knowing C):
[--------|----★----|--------] <- Expanded by a factor of C
As Andreas Krause et al. demonstrate in Corruption-Tolerant Gaussian Process Bandit Optimization, this creates a delicate balancing act. Without prior knowledge of the adversary's strength, an algorithm cannot properly calibrate its exploration constants. Underestimating the noise leads to catastrophic failures where the agent is permanently misled by poisoned signals, while overestimating it leads to paralysis through excessive caution.
Mechanism 1: Meta-Learning and Model Selection
One powerful strategy for bypassing this information gap is to transform the unknown budget problem into a secondary online learning problem. Instead of trying to guess the budget statically, the system runs multiple base learners in parallel, each operating under a different assumption of the corruption budget.
In Robust Stochastic Linear Contextual Bandits Under Adversarial Attacks, Cho-Jui Hsieh et al. introduce a "Bandit-over-Bandit" framework. The architecture consists of a master algorithm that treats the individual base learners as "arms." As the master algorithm observes the actual performance of each base learner over time, it adaptively shifts its selection probability toward the base learner whose budget assumption best matches the true environmental hostility.
┌───────────────┐
│ Master Bandit │
└───────┬───────┘
│ (Selects best hypothesis)
┌────────────────┼────────────────┐
▼ ▼ ▼
┌────────────────┐┌────────────────┐┌────────────────┐
│ Base Learner 1 ││ Base Learner 2 ││ Base Learner 3 │
│ (Assumes C=0) ││ (Assumes C=10)││(Assumes C=100) │
└────────────────┘└────────────────┘└────────────────┘
A similar intuition drives the reinforcement learning framework proposed by Chen-Yu Wei et al. in A Model Selection Approach for Corruption Robust Reinforcement Learning. The authors design a model selection routine that dynamically tests base learners against incoming environmental feedback. If a base learner's performance deviates from its theoretical guarantees, the framework concludes that its corruption estimate is incorrect and eliminates it, allowing the agent to adapt to unknown levels of sabotage in both rewards and transition physics.
Mechanism 2: Agnostic Checking and Multi-Layered Racing
Another approach focuses on structural defense mechanisms that isolate corruption without explicitly parameterizing it. Instead of estimating a global budget, these algorithms use hierarchical verification or elimination structures to filter out corrupted feedback.
For environments with binary feedback, Shiliang Zuo introduces an "agnostic checking" technique in Corruption-Robust Lipschitz Contextual Search. When an adversary maliciously flips binary signals to mislead a search algorithm, the agnostic checker cross-references incoming feedback against localized geometric properties of the search space. This allows the algorithm to identify and ignore inconsistent signals without needing to know the total number of allowed flips in advance.
In multi-agent settings, such as decentralized matching markets, Zheshun Wu et al. leverage a multi-layered "racing" mechanism in Bandit Learning in Matching Markets Robust to Adversarial Corruptions. By organizing the elimination of suboptimal choices into synchronized layers, the honest agents can out-race the influence of the adversary, achieving near-optimal regret even when the scale of the corruption is completely hidden.
Mechanism 3: Parameter-Free Robust Estimators
A third paradigm replaces standard empirical means with robust statistical estimators that are inherently blind to the exact corruption budget. These estimators rely on properties like the median or trimmed mean to bound the influence of outliers automatically.
In CRIMED: Lower and Upper Bounds on Regret for Bandits with Unbounded Stochastic Corruption, Debabrota Basu et al. utilize the median as a core reward estimator. Because the median is naturally resilient to arbitrary corruptions affecting less than 50% of the data, the resulting algorithm achieves asymptotic optimality without requiring a predefined upper bound on the corruption probability. The authors extend this principle to heavy-tailed data in Bandits Corrupted by Nature: Lower Bounds on Regret and Robust Optimistic Algorithms via a linear-time algorithm called SeqHuberUCB, which uses a sequential Huber loss to handle both natural outliers and adversarial noise without predefined variance bounds.
However, parameter-free robustness comes with structural constraints. As Andi Nika et al. demonstrate in Corruption-Robust Offline Two-Player Zero-Sum Markov Games, learning an equilibrium policy from corrupted offline data without knowing the corruption level is theoretically impossible unless the dataset provides uniform coverage over all state-action pairs. Without uniform coverage, an algorithm cannot mathematically distinguish between a legitimate, low-probability event and a targeted adversarial data-poisoning injection.
The Fundamental Cost of Agnosticism
While these frameworks prove that learning without a corruption budget is possible, they also reveal a fundamental theoretical limit: uncertainty carries a quantifiable performance cost.
In Robust Lipschitz Bandits to Adversarial Corruptions, Yue Kang et al. establish that while agents can adapt to unknown levels of interference, doing so forces a strict mathematical tradeoff in the rate of convergence. An algorithm that must protect itself against an unknown budget can never match the tightest possible regret bounds of an algorithm perfectly tuned to a known budget. The core of modern research in this area is minimizing this "agnosticism tax," ensuring that performance degrades gracefully and linearly relative to the actual corruption encountered, as achieved by Arpit Agarwal et al. in Stochastic Dueling Bandits with Adversarial Corruption.
Key Foundational Work
Stochastic bandits robust to adversarial corruptions (2018) — contributed 1 concept elements to this direction.
Efficient Algorithms for Outlier-Robust Regression (2018) — contributed 1 concept elements to this direction.
Resilient Distributed Optimization Algorithms for Resource Allocation (2019) — contributed 1 concept elements to this direction.