mlsanityData to 14 Oct 2026

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

arXiv 2509.08933 ↗First posted 10 Sep 2025cs.LG cs.SY eess.SYcited by 1

On the map: Deep reinforcement learning methods → RL theory and sample complexity

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.

Key facts. Cited by 1 paper 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.

Builds on

48 of 75 references.

Closest ancestors · 4

Same direction, newest first

  1. 2025A Robust widetildeO(1/√T) Rate for Unprojected TD Learning with Linear Function Approximation1 Jun
  2. 2025Finite Sample Analysis of Linear Temporal Difference Learning with Arbitrary Features27 May
  3. 2025Adversarially-Robust TD Learning with Markovian Data: Finite-Time Rates and Fundamental Limits7 Feb
  4. 2024Stochastic Approximation with Delayed Updates: Finite-Time Rates under Markovian Sampling19 Feb

Other references · 44

  1. 2018A Finite Time Analysis of Temporal Difference Learning With Linear Function Approximationcited by 229
  2. 2019Finite-Time Error Bounds For Linear Stochastic Approximation and TD Learningcited by 166
  3. 2019Mean estimation and regression under heavy-tailed distributions--a surveycited by 136
  4. 2016Agnostic Estimation of Mean and Covariancecited by 131
  5. 2018Stochastic bandits robust to adversarial corruptionscited by 119
  6. 2020Finite-Time Analysis of Asynchronous Stochastic Approximation and Q-Learningcited by 96
  7. 2019Better Algorithms for Stochastic Bandits with Adversarial Corruptionscited by 92
  8. 2021Is Q-Learning Minimax Optimal? A Tight Sample Complexity Analysiscited by 92
  9. 2019Stochastic approximation with cone-contractive operators: Sharp ℓ_∞-bounds for Q-learningcited by 77
  10. 2019Corruption-robust exploration in episodic reinforcement learningcited by 72
  11. 2019Finite-Sample Analysis of Nonlinear Stochastic Approximation with Applications in Reinforcement Learningcited by 67
  12. 2020Stochastic Linear Bandits Robust to Adversarial Attackscited by 65
32 more
  1. 2018Adversarial Attacks on Stochastic Banditscited by 57
  2. 2020Least Squares Regression with Markovian Data: Fundamental Limits and Algorithmscited by 56
  3. 2019Data Poisoning Attacks on Stochastic Banditscited by 53
  4. 2021Corruption-Robust Offline Reinforcement Learningcited by 51
  5. 2022Nearly Optimal Algorithms for Linear Contextual Bandits with Adversarial Corruptionscited by 51
  6. 2021A Model Selection Approach for Corruption Robust Reinforcement Learningcited by 45
  7. 2020Is Temporal Difference Learning Optimal? An Instance-Dependent Analysiscited by 41
  8. 2018High-Dimensional Robust Mean Estimation in Nearly-Linear Timecited by 39
  9. 2018Q-learning with Nearest Neighborscited by 37
  10. 2022Adapting to Mixing Time in Stochastic Optimization with Markovian Datacited by 36
  11. 2020Adversarial Attacks on Linear Contextual Banditscited by 34
  12. 2020Corruption-Tolerant Gaussian Process Bandit Optimizationcited by 34
  13. 2022Corruption-Robust Algorithms with Uncertainty Weighting for Nonlinear Contextual Bandits and Markov Decision Processescited by 33
  14. 2023Corruption-Robust Offline Reinforcement Learning with General Function Approximationcited by 31
  15. 2017Mixing time estimation in reversible Markov chains from a single sample pathcited by 27
  16. 2019Estimating the Mixing Time of Ergodic Markov Chainscited by 25
  17. 2022Finite time analysis of temporal difference learning with linear function approximation: Tail averaging and regularisationcited by 23
  18. 2014On TD(0) with function approximation: Concentration bounds and a centered variant with exponential convergencecited by 22
  19. 2020Temporal Difference Learning as Gradient Splittingcited by 21
  20. 2021Improved Corruption Robust Algorithms for Episodic Reinforcement Learningcited by 20
  21. 2024Corruption Robust Offline Reinforcement Learning with Human Feedbackcited by 20
  22. 2024A Simple Finite-Time Analysis of TD Learning with Linear Function Approximationcited by 16
  23. 2021No-Regret Reinforcement Learning with Heavy-Tailed Rewardscited by 14
  24. 2013Concentration bounds for temporal difference learning with linear function approximation: The case of batch data and uniform samplingcited by 13
  25. 2023Temporal Difference Learning with Compressed Updates: Error-Feedback meets Reinforcement Learningcited by 12
  26. 2023Provably Robust Temporal Difference Learning for Heavy-Tailed Rewardscited by 9
  27. 2017Linear Stochastic Approximation: Constant Step-Size and Iterate Averagingcited by 8
  28. 2023Robust Offline Reinforcement learning with Heavy-Tailed Rewardscited by 7
  29. 2022Robust Online and Distributed Mean Estimation Under Adversarial Data Corruptioncited by 5
  30. 2024Finite-Time Analysis of Asynchronous Multi-Agent TD Learningcited by 3
  31. 2023CRIMED: Lower and Upper Bounds on Regret for Bandits with Unbounded Stochastic Corruptioncited by 2
  32. 2024Robust Q-Learning under Corrupted Rewardscited by 2

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2026: 1.

1 paper.

  1. 2026Robust Asynchronous Q-Learning under Reward and State Corruption via Batchingcited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2022The Efficacy of Pessimism in Asynchronous Q-Learning
  2. 2026Hitting-Time Bounds for Asynchronous Q-Learning
  3. 2026Achieving varepsilon-2 Dependence for Average-Reward Q-Learning with a New Contraction Principle
  4. 2024Asynchronous Stochastic Approximation with Applications to Average-Reward Reinforcement Learning
  5. 2023Towards Robust Offline Reinforcement Learning under Diverse Data Corruption
  6. 2025Sparse Offline Reinforcement Learning with Corruption Robustness
  7. 2026Commit to the Bit: Reactive Reinforcement Learning Done Right
  8. 2026Learning from Unreliable Trajectories: Adversarially-Robust Federated Q-Learning