⚡ electrical engineering

Robust Asynchronous Q-Learning under Reward and State Corruption via Batching

This paper introduces BR-Async-Q, a novel epoch-based robust Q-learning algorithm that effectively handles adversarial corruption of both rewards and states by batching data and constructing robust Bellman operator estimates, achieving high-probability error bounds that match vanilla Q-learning up to a term scaling with the corruption fraction.

Original authors: Sreejeet Maity, Aritra Mitra

Published 2026-07-27

📖 8 min read🧠 Deep dive

CC BY 4.0

Original authors: Sreejeet Maity, Aritra Mitra

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are teaching a robot to navigate a maze to find the best treasure. In the perfect world of science fiction, the robot sees every turn clearly, hears every instruction perfectly, and learns from every mistake instantly. But in the real world, things are messy. Sensors glitch, signals get jammed, and sometimes, a mischievous hacker might even try to trick the robot by showing it fake walls or lying about the treasure's location. This is the world of Reinforcement Learning (RL). It's a method where an agent (like a robot or a software program) learns to make decisions by trying things out and getting feedback. The goal is to figure out the best path to maximize rewards, like winning a game or driving a car safely. However, if the feedback the agent receives is corrupted—full of noise, errors, or even deliberate lies—the agent can get confused, learn the wrong lessons, and end up making terrible decisions. The big question scientists are asking is: Can we build a learning system that is tough enough to ignore the lies and still figure out the truth, even when the data is a mess?

This paper, titled "Robust Asynchronous Q-Learning under Reward and State Corruption via Batching," tackles exactly that problem. The authors, Sreejeet Maity and Aritra Mitra, are worried about a scenario where an adversary (a bad actor) can mess up both the "reward" (the score the robot gets) and the "state" (the robot's view of the world) at the same time. They propose a new algorithm called BR-Async-Q. Think of it as a new way for the robot to learn that doesn't panic when it sees a lie. Instead of updating its brain after every single step—which makes it vulnerable to a single bad piece of data—they wait and collect a whole "batch" of experiences first. Then, they use a clever statistical trick to filter out the lies and find the average truth before making a single, strong update. They prove mathematically that this method works, showing that even with a certain percentage of corrupted data, the robot can still learn a near-perfect strategy. Their simulations confirm that while standard learning methods crash and burn under these attacks, their new method keeps the robot on track, converging to the right answer with only a tiny, predictable error caused by the remaining lies.

The Problem: A Robot in a Hall of Mirrors

To understand what the authors did, let's picture our robot learning agent as a student taking a test. In a normal Reinforcement Learning setup, the student takes a step, gets a grade (reward), and sees the next question (state). They use this to update their study guide (the "Q-table") immediately.

But imagine a sneaky proctor (the adversary) is watching. Every now and then, the proctor swaps the student's real grade with a fake one, or changes the next question on the page to something completely different. This is what the paper calls Huber contamination. The proctor doesn't need to lie all the time; just a small percentage of lies (say, 1% or 5%) is enough to throw the student off. If the student updates their study guide after every single question, one fake grade can make them think the wrong answer is right. Over time, these small errors compound, and the student ends up with a completely wrong guide.

The situation gets even trickier because the student is learning "asynchronously." This means they don't get to see every possible question and answer at once. They wander through the maze, and some paths are visited often, while others are rare. If the proctor targets those rare paths, the student might never realize they've been lied to because they don't have enough data to spot the pattern.

The Solution: The "Batch and Trim" Strategy

The authors' solution, BR-Async-Q, changes the rhythm of learning. Instead of reacting to every single piece of feedback, the robot pauses and groups its experiences into chunks called epochs or batches.

Imagine the robot is collecting seashells on a beach. A standard robot picks up a shell, looks at it, and immediately decides if it's a treasure or a rock. If a fake shell (a piece of plastic painted to look like gold) is handed to it, the robot might get fooled.

The BR-Async-Q robot, however, fills a bucket with 1,000 shells first. Once the bucket is full, it dumps them out and looks at the whole pile. It knows that the proctor might have slipped in a few plastic shells, but it also knows that the plastic shells are likely to be outliers—either too shiny or too weird. So, the robot uses a special tool called a trimmed mean. It ignores the most extreme shells (the ones that look suspiciously fake or impossibly perfect) and calculates the average value of the remaining, normal-looking shells.

This "trimming" process is the secret sauce. By waiting until it has a large batch of data, the robot can statistically separate the signal (the truth) from the noise (the lies). The paper proves that by doing this, the robot can estimate the true value of its actions with high precision, even if some of the data is corrupted.

Why Batching Matters: The Variance Trap

The authors point out a critical flaw in previous methods. Old robust algorithms tried to be tough by updating every step but using complex math to guess the truth. The problem was that these updates had high variance. In simple terms, "variance" is how much the robot's guess jumps around. If the robot updates too often with noisy data, its brain is constantly jittering, making it easy for the proctor to push it off course.

By batching the data, BR-Async-Q reduces this jitter. It's like taking a long-exposure photo. If you take a picture of a moving car with a fast shutter speed, you get a blurry, shaky image. But if you wait and take a long exposure, the motion blurs out, and you get a clear, steady picture. The authors show that this "variance reduction" allows their algorithm to match the performance of standard learning (when there are no lies) while being immune to the lies.

The Results: Beating the Lies

The paper provides a mathematical guarantee, which is a fancy way of saying they proved with logic that the robot will succeed. They showed that the error (the difference between what the robot learns and the perfect strategy) has two parts:

The Natural Error: This is the normal mistake you'd expect just because the robot hasn't seen enough data yet. This part gets smaller as the robot learns more.
The Corruption Bias: This is the extra error caused by the proctor's lies.

The amazing thing is that the "Corruption Bias" in their new method is very small. It scales directly with the amount of lying (the corruption probability), but it doesn't get blown up by the robot's confusion. In fact, when only the rewards are corrupted (and the states are clean), their method is minimax optimal. This is a technical way of saying: "You can't do better than this." They hit the theoretical limit of how well any algorithm could possibly perform under these conditions.

The authors also ran simulations to see how this works in practice. They created a grid-world environment (a simple maze) with 100 states and 40 actions. They tested their algorithm against a standard one while introducing different levels of corruption.

The Standard Robot: When the proctor started lying, the standard robot's performance crashed. Its error grew huge, and it failed to find the best path.
The BR-Async-Q Robot: Even when 20% of the data was corrupted (a massive amount of lying), this robot stayed calm. It converged to a solution very close to the perfect one, with only a tiny, stable error.

They also tested what happens if the robot visits some paths very rarely. Previous methods struggled here, thinking that rare paths were more vulnerable to lies. But because BR-Async-Q waits for a full batch of data, it ensures that even rare paths get enough attention to filter out the lies, avoiding the "amplification" of errors that plagued older methods.

The Takeaway

In the end, this paper offers a new playbook for teaching machines in a messy, untrustworthy world. It suggests that patience is a virtue. By slowing down, collecting more data, and using smart statistics to filter out the noise, we can build AI systems that don't just survive corruption but thrive despite it. The authors didn't just guess this would work; they proved it mathematically and showed it working in simulations. While the current method requires storing a lot of data in memory (like filling that big bucket of shells), the core idea—that batching and robust estimation can defeat adversarial lies—opens the door for safer, more reliable AI in everything from self-driving cars to medical diagnosis, where the cost of a lie is too high to ignore.

Technical Summary: Robust Asynchronous Q-Learning under Reward and State Corruption via Batching

1. Problem Formulation

The paper addresses the challenge of learning an optimal policy in a discounted infinite-horizon Markov Decision Process (MDP) when the learner's feedback is subject to adversarial corruption. The setting involves an agent interacting with an environment via a behavior policy $\mu$ , observing state-action pairs $(s_t, a_t)$ , next states $s_{t+1}$ , and rewards $r_t$ .

The core difficulty arises from the Huber contamination model, where an adversary can arbitrarily perturb both the observed reward and the observed next state at each time step with a small probability $\epsilon \in [0, 1/2)$ . Specifically:

Reward Corruption: With probability $\epsilon_R$ , the observed reward $\tilde{r}_t$ is replaced by an arbitrary value $z_t$ (potentially unbounded).
State Corruption: With probability $\epsilon_Y$ , the observed next state $\tilde{s}_{t+1}$ is replaced by an arbitrary state $u_t$ .
Heavy-Tailed Rewards: Unlike prior work requiring sub-Gaussian rewards, this framework assumes only that the clean reward distributions admit a finite second moment, allowing for heavy-tailed noise.

The objective is to construct a robust estimate $\hat{Q}$ of the optimal state-action value function $Q^*$ and derive a high-probability $\ell_\infty$ -error bound $\|\hat{Q} - Q^*\|_\infty$ that holds despite these joint corruptions.

2. Methodology: BR-Async-Q

The authors propose BR-Async-Q (Batch Robust Asynchronous Q-Learning), a novel epoch-based algorithm designed to mitigate the variance and bias introduced by adversarial feedback. The approach departs from standard Q-learning, which updates the Q-table at every time step, by introducing two key mechanisms:

A. Online Batching (Epochs)

The interaction horizon $T$ is partitioned into $K$ epochs (batches), each of length $H$ . Within an epoch $k$ , the algorithm collects data but does not update the Q-table. Instead, it aggregates observations for each state-action pair $(s, a)$ into two datasets:

$D_k(s, a)$ : The set of observed (potentially corrupted) rewards.
$Y_k(s, a)$ : The set of bootstrapped values $\max_{a'} Q_k(\tilde{s}_{t+1}, a')$ based on the frozen Q-table from the start of the epoch.

B. Robust Estimation of the Bellman Operator

At the end of each epoch, the algorithm computes a robust estimate of the Bellman optimality operator $\mathcal{T}$ using the aggregated batch data. This involves:

Robust Mean Estimation:
- For rewards ( $D_k$ ), a trimmed mean estimator ( $\text{TRIM}_H$ ) is used to estimate the clean reward mean $R(s, a)$ . This handles the heavy-tailed nature and arbitrary corruption.
- For bootstrapped values ( $Y_k$ ), a clipped mean estimator ( $\text{TRIM}_B$ ) is used. Crucially, this estimator utilizes known bounds on the Q-values (derived from the clipping threshold) to achieve a tighter dependence on the corruption fraction $\epsilon_Y$ .
Clipping for Stability: To prevent rare failures of the robust estimators from destabilizing the Q-table, the estimated reward is clipped to a threshold $G_k$ derived from theoretical bounds. This ensures the Q-iterates remain uniformly bounded.
Synchronous Update: The Q-table is updated only once per epoch using the robustly estimated operator, effectively reducing the variance of the update direction compared to single-sample updates.

3. Key Contributions

Algorithmic Contribution

The paper introduces the first robust Q-learning algorithm capable of handling joint state and reward corruption in an asynchronous online setting. By partitioning data into batches and employing robust statistical estimators, BR-Async-Q overcomes the limitations of standard Q-learning and prior robust variants that update at every step.

Theoretical Contribution

The authors prove a high-probability finite-time $\ell_\infty$ -error bound for BR-Async-Q (Theorem 2). The bound consists of two components:

Statistical Error: A dominant term scaling as $\tilde{O}\left(\frac{\tilde{\sigma}}{(1-\gamma)^{5/2}\sqrt{\lambda_{\min} T}}\right)$ . Notably, the dependence on the minimum visitation probability $\lambda_{\min}$ is improved compared to prior work [9], scaling as $1/\sqrt{\lambda_{\min} T}$ rather than $1/(\lambda_{\min}\sqrt{T})$ .
Corruption-Induced Bias: An additive bias term $\psi$ $ψ$ that scales with the corruption probabilities:
$\psi = O\left(\frac{\tilde{\sigma}\epsilon_Y}{(1-\gamma)^2}\right) \vee O\left(\frac{\bar{\sigma}\sqrt{\epsilon_R}}{1-\gamma}\right)$
- When only rewards are corrupted ( $\epsilon_Y = 0$ ), the bias term scales as $O(\sqrt{\epsilon_R})$ , which matches the fundamental minimax lower bound established in prior work [6].
- This result closes the gap between the upper and lower bounds found in previous literature, demonstrating that the inverse dependence on visitation probability seen in prior upper bounds is avoidable via variance reduction.

4. Results and Significance

Simulation Results

The paper validates BR-Async-Q on a grid-world environment ( $|S|=100, |A|=40$ ).

Robustness: Vanilla Q-learning fails to converge under even small corruption levels ( $\epsilon \in \{0.001, 0.005, 0.01\}$ ) or heavy-tailed noise, whereas BR-Async-Q converges to a neighborhood of $Q^*$ .
Asymmetric Corruption: The algorithm remains stable even when state and reward corruption rates differ ( $\epsilon_Y \neq \epsilon_R$ ).
Epoch Length: The performance is shown to be robust across different epoch lengths $H$ , provided $H$ is sufficiently large to satisfy the visitation probability requirements.

Significance and Claims

The paper claims to provide the first provable robustness guarantee for asynchronous Q-learning under the joint corruption of states and rewards.

Gap Closure: It resolves a fundamental gap in understanding the sample complexity of robust RL under reward-only corruption, showing that the suboptimal dependence on visitation probabilities in prior upper bounds is an artifact of the algorithm design, not the problem itself.
Minimax Optimality: Under reward-only corruption, the algorithm achieves a bias term that is minimax optimal, exactly matching the information-theoretic lower bound.
Practicality: The method demonstrates that reliable learning is possible even in harsh environments with sensing failures, logging errors, or deliberate poisoning, provided the corruption probability is small and the algorithm utilizes batching to reduce variance.

The authors note that the current implementation requires memory linear in the epoch length $H$ and suggest future work on online robust mean estimators and extensions to function approximation.