mlsanityData to 14 Oct 2026

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

arXiv 2607.20822 ↗First posted 23 Jul 2026cs.LG cs.SY eess.SYcited by 0

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

Abstract (arXiv)

Motivated by reinforcement learning in harsh environments, we consider the problem of learning an optimal policy subject to adversarially corrupted feedback. Specifically, at each time-step, an adversary can perturb both the reward and state observations of the learner following the Huber contamination model. To defend against such data corruption, we propose BR-Async-Q: a novel, epoch-based, robust Q-learning algorithm built upon two key ideas: (i) partitioning the online data stream into batches to reduce variance, and (ii) constructing robust estimates of the Bellman optimality operator using such batched data. We prove a high-probability ℓ_∞ error bound for BR-Async-Q that matches that for vanilla Q-learning, up to a small additive term that scales with the fraction of corrupted samples. To our knowledge, this provides the first robustness guarantee for asynchronous Q-learning subject to both reward and state corruption. Furthermore, when only rewards are corrupted, the dependence of our algorithm's bound on the corruption fraction is minimax optimal.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods. Builds on 15 of its 29 references that are in the map. First posted on arXiv 23 Jul 2026.

Builds on

15 of 29 references.

Closest ancestors · 2

Same direction, newest first

  1. 2025Corruption-Tolerant Asynchronous Q-Learning with Near-Optimal Rates10 Sep
  2. 2025Adversarially-Robust TD Learning with Markovian Data: Finite-Time Rates and Fundamental Limits7 Feb

Other references · 13

  1. 2018Byzantine-Robust Distributed Learning: Towards Optimal Statistical Ratescited by 711
  2. 2018A Finite Time Analysis of Temporal Difference Learning With Linear Function Approximationcited by 229
  3. 2019Finite-Time Error Bounds For Linear Stochastic Approximation and TD Learningcited by 166
  4. 2018Stochastic bandits robust to adversarial corruptionscited by 119
  5. 2020Finite-Time Analysis of Asynchronous Stochastic Approximation and Q-Learningcited by 96
  6. 2021Is Q-Learning Minimax Optimal? A Tight Sample Complexity Analysiscited by 92
  7. 2019Stochastic approximation with cone-contractive operators: Sharp ℓ_∞-bounds for Q-learningcited by 77
  8. 2019Finite-Sample Analysis of Nonlinear Stochastic Approximation with Applications in Reinforcement Learningcited by 67
  9. 2022Adapting to Mixing Time in Stochastic Optimization with Markovian Datacited by 36
  10. 2014On TD(0) with function approximation: Concentration bounds and a centered variant with exponential convergencecited by 22
  11. 2024A Simple Finite-Time Analysis of TD Learning with Linear Function Approximationcited by 16
  12. 2022Robust Online and Distributed Mean Estimation Under Adversarial Data Corruptioncited by 5
1 more
  1. 2024Robust Q-Learning under Corrupted Rewardscited by 2

Built on by

Not cited yet.

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. 2023Towards Robust Offline Reinforcement Learning under Diverse Data Corruption
  4. 2024Towards Optimal Adversarial Robust Q-learning with Bellman Infinity-error
  5. 2021Corruption-Robust Offline Reinforcement Learning
  6. 2026Achieving varepsilon-2 Dependence for Average-Reward Q-Learning with a New Contraction Principle
  7. 2026Learning from Unreliable Trajectories: Adversarially-Robust Federated Q-Learning
  8. 2025Efficient Q-Learning and Actor-Critic Methods for Robust Average-Reward Reinforcement Learning