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

Reinforcement learning (RL) agents often operate in environments where feedback—specifically rewards and next-state observations—is subject to noise or adversarial manipulation. Standard Q-learning is highly sensitive to such corruptions, as errors in early updates can propagate and compound. This paper addresses the challenge of learning an optimal policy in an infinite-horizon, discounted MDP when both rewards and state transitions are subject to adversarial corruption under the Huber contamination model.

The authors propose BR-Async-Q, an epoch-based algorithm that departs from standard online Q-learning. Instead of updating the Q-table at every time step, the algorithm partitions the data stream into batches (epochs). Within each epoch, it collects samples for every state-action pair and computes robust estimates of the Bellman optimality operator using a trimmed-mean estimator. By using these variance-reduced, robust estimates to update the Q-table only at the end of each epoch, the algorithm effectively filters out the influence of adversarial perturbations.

The study provides a high-probability finite-time error bound for BR-Async-Q. The results show that the algorithm converges to the optimal state-action value function with an error term that scales with the fraction of corrupted samples. Notably, when only rewards are corrupted, the algorithm achieves a minimax optimal dependence on the corruption fraction. This work closes the gap between upper and lower bounds found in previous literature and provides the first robustness guarantee for asynchronous Q-learning under joint state and reward corruption.

This research provides a theoretically grounded solution for deploying RL in "harsh" environments where data integrity cannot be guaranteed. By demonstrating that infrequent, robust updates are sufficient to maintain convergence, the paper offers a practical blueprint for building more resilient decision-making systems that are less susceptible to sensing failures, logging errors, or malicious data poisoning.