Corruption-Tolerant Asynchronous Q-Learning with Near-Optimal Rates

We study the problem of learning the optimal policy in a discounted, infinite-horizon reinforcement learning (RL) setting in the presence of adversarially corrupted rewards. To address this problem, we develop a novel robust variant of the Q-learning algorithm and analyze it under the challenging asynchronous sampling model with time-correlated data. Despite corruption, we prove that the finite-time guarantees of our approach match existing bounds, up to an additive term that scales with the fraction of corrupted samples. We also establish an information-theoretic lower bound, revealing that our guarantees are near-optimal. Notably, our algorithm is agnostic to the underlying reward distribution and provides the first finite-time robustness guarantees for asynchronous Q-learning. A key element of our analysis is a refined Azuma-Hoeffding inequality for almost-martingales, which may have broader applicability in the study of RL algorithms.

Reinforcement learning allows artificial intelligence (AI) agents to learn optimal decision-making strategies through a stream of data rewards, much like training an animal with treats. However, real-world data streams in autonomous driving, robotics, or aerospace sensors are highly vulnerable to hardware malfunctions and malicious cyberattacks that inject completely fabricated or corrupted reward data. Even a tiny fraction of these corrupted points can permanently blind conventional algorithms, leading the AI to learn entirely incorrect behaviors. To resolve this vulnerability, we developed two new mathematical frameworks which automatically isolate and filter out corrupted data on the fly. Our algorithms establish a dynamic, self-shrinking "safety zone" that screens incoming signals and securely discards wild anomalies. Crucially, the second algorithm can effectively protect the system even when it has absolutely no prior knowledge of what clean, uncorrupted data statistics are supposed to look like. We mathematically prove that our approach allows AI systems to successfully find the best operational path at the same speed as if they were processing entirely flawless data. As machine learning is deployed in safety-critical infrastructure like automated financial trading and self-driving vehicles, this framework ensures that critical AI infrastructure remains resilient, stable, and accurate even under active data-poisoning attacks.