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

arXiv: https://arxiv.org/abs/2509.08933 · HTML: https://mlsanity.com/paper/2509.08933/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods.
- Builds on 48 of its 75 references that are in the map.
- First posted on arXiv 10 Sep 2025.

## Placed in

- Deep reinforcement learning methods / [RL theory and sample complexity](https://mlsanity.com/deeprl/rl-theory-and-sample-complexity/)

## Builds on (most cited first, 30 of 48)

- [A Finite Time Analysis of Temporal Difference Learning With Linear Function Approximation](https://mlsanity.com/paper/1806.02450/) (2018)
- [Finite-Time Error Bounds For Linear Stochastic Approximation and TD Learning](https://mlsanity.com/paper/1902.00923/) (2019)
- [Mean estimation and regression under heavy-tailed distributions--a survey](https://mlsanity.com/paper/1906.04280/) (2019)
- [Agnostic Estimation of Mean and Covariance](https://mlsanity.com/paper/1604.06968/) (2016)
- [Stochastic bandits robust to adversarial corruptions](https://mlsanity.com/paper/1803.09353/) (2018)
- [Finite-Time Analysis of Asynchronous Stochastic Approximation and Q-Learning](https://mlsanity.com/paper/2002.00260/) (2020)
- [Better Algorithms for Stochastic Bandits with Adversarial Corruptions](https://mlsanity.com/paper/1902.08647/) (2019)
- [Is Q-Learning Minimax Optimal? A Tight Sample Complexity Analysis](https://mlsanity.com/paper/2102.06548/) (2021)
- [Stochastic approximation with cone-contractive operators: Sharp ℓ_∞-bounds for Q-learning](https://mlsanity.com/paper/1905.06265/) (2019)
- [Corruption-robust exploration in episodic reinforcement learning](https://mlsanity.com/paper/1911.08689/) (2019)
- [Finite-Sample Analysis of Nonlinear Stochastic Approximation with Applications in Reinforcement Learning](https://mlsanity.com/paper/1905.11425/) (2019)
- [Stochastic Linear Bandits Robust to Adversarial Attacks](https://mlsanity.com/paper/2007.03285/) (2020)
- [Adversarial Attacks on Stochastic Bandits](https://mlsanity.com/paper/1810.12188/) (2018)
- [Least Squares Regression with Markovian Data: Fundamental Limits and Algorithms](https://mlsanity.com/paper/2006.08916/) (2020)
- [Data Poisoning Attacks on Stochastic Bandits](https://mlsanity.com/paper/1905.06494/) (2019)
- [Corruption-Robust Offline Reinforcement Learning](https://mlsanity.com/paper/2106.06630/) (2021)
- [Nearly Optimal Algorithms for Linear Contextual Bandits with Adversarial Corruptions](https://mlsanity.com/paper/2205.06811/) (2022)
- [A Model Selection Approach for Corruption Robust Reinforcement Learning](https://mlsanity.com/paper/2110.03580/) (2021)
- [Is Temporal Difference Learning Optimal? An Instance-Dependent Analysis](https://mlsanity.com/paper/2003.07337/) (2020)
- [High-Dimensional Robust Mean Estimation in Nearly-Linear Time](https://mlsanity.com/paper/1811.09380/) (2018)
- [Q-learning with Nearest Neighbors](https://mlsanity.com/paper/1802.03900/) (2018)
- [Adapting to Mixing Time in Stochastic Optimization with Markovian Data](https://mlsanity.com/paper/2202.04428/) (2022)
- [Adversarial Attacks on Linear Contextual Bandits](https://mlsanity.com/paper/2002.03839/) (2020)
- [Corruption-Tolerant Gaussian Process Bandit Optimization](https://mlsanity.com/paper/2003.01971/) (2020)
- [Corruption-Robust Algorithms with Uncertainty Weighting for Nonlinear Contextual Bandits and Markov Decision Processes](https://mlsanity.com/paper/2212.05949/) (2022)
- [Corruption-Robust Offline Reinforcement Learning with General Function Approximation](https://mlsanity.com/paper/2310.14550/) (2023)
- [Mixing time estimation in reversible Markov chains from a single sample path](https://mlsanity.com/paper/1708.07367/) (2017)
- [Estimating the Mixing Time of Ergodic Markov Chains](https://mlsanity.com/paper/1902.01224/) (2019)
- [Finite time analysis of temporal difference learning with linear function approximation: Tail averaging and regularisation](https://mlsanity.com/paper/2210.05918/) (2022)
- [On TD(0) with function approximation: Concentration bounds and a centered variant with exponential convergence](https://mlsanity.com/paper/1411.3224/) (2014)

## Built on by (most cited first, 1 of 1)

- [Robust Asynchronous Q-Learning under Reward and State Corruption via Batching](https://mlsanity.com/paper/2607.20822/) (2026)

## Abstract (arXiv)

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.