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

• URL: http://arxiv.org/abs/2607.20822v2
• Date: Fri, 24 Jul 2026 00:47:01 GMT
• Title: Robust Asynchronous Q-Learning under Reward and State Corruption via Batching
• Abstract summary: We propose BR-Async-Q: a novel, epoch-based, robust Q-learning algorithm built upon two key ideas.<n>We prove a high-probability error bound for BR-Async-Q that matches that for vanilla Q-learning.<n>When only rewards are corrupted, the dependence of our algorithm's bound on the corruption fraction is minimax optimal.
• Score: 2.3096751699592137
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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 $\ell_\infty$ 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.

Related papers

• Corruption-robust Offline Multi-agent Reinforcement Learning From Human Feedback [26.662444975280792]
  We consider robustness against data corruption in offline multi-agent reinforcement learning from human feedback.<n>We model the problem using the framework of linear Markov games.<n>To the best of our knowledge, this is the first systematic treatment of data corruption in offline MARLHF.
  arXiv  Detail & Related papers  (2026-03-30T11:03:36Z)
• Online Learning to Rank under Corruption: A Robust Cascading Bandits Approach [15.847551488328866]
  Online learning to rank studies how to recommend a short ranked list of items from a large pool and improves future rankings based on user clicks.<n>This setting is commonly modeled as cascading bandits, where the objective is to maximize the likelihood that the user clicks on at least one of the presented items.<n>We propose MSUCB, a robust algorithm that incorporates a novel mean-of-medians estimator, which is applied to bandits with corruption setting.
  arXiv  Detail & Related papers  (2025-11-04T23:39:37Z)
• Reinforcement Learning with Verifiable yet Noisy Rewards under Imperfect Verifiers [90.50039419576807]
  Reinforcement Learning with Verifiable Rewards (RLVR) trains policies against automated verifiers to avoid costly human labeling.<n>To reduce vulnerability to verifier hacking, many RLVR systems collapse rewards to binary $0,1$ during training.<n>This choice carries a cost: it introduces textitfalse negatives (rejecting correct answers, FNs) and textitfalse positives (accepting incorrect ones, FPs)
  arXiv  Detail & Related papers  (2025-10-01T13:56:44Z)
• Corruption-Tolerant Asynchronous Q-Learning with Near-Optimal Rates [2.3096751699592137]
  We propose a new provably robust variant of the Q-learning algorithm that operates effectively even when a fraction of the observed rewards are arbitrarily perturbed by an adversary.<n>Our contributions provide the first finite-time robustness guarantees for asynchronous Q-learning, bridging a significant gap in robust RL.
  arXiv  Detail & Related papers  (2025-09-10T18:56:39Z)
• Adversarially-Robust TD Learning with Markovian Data: Finite-Time Rates and Fundamental Limits [2.07180164747172]
  Motivated by harsh, real-world environments, we revisit the policy evaluation problem from the perspective of adversarial robustness.<n>We develop a novel algorithm called Robust-TD and prove that its finite-time guarantees match that of vanilla TD with linear function approximation up to a small $O(epsilon)$ term.<n>To our knowledge, these results are the first of their kind in the context of adversarial approximation schemes driven by Markov noise.
  arXiv  Detail & Related papers  (2025-02-07T05:05:42Z)
• Robust Q-Learning under Corrupted Rewards [2.07180164747172]
  We investigate the robustness of the celebrated Q-learning algorithm to a strong-contamination attack model. We develop a novel robust synchronous Q-learning algorithm that uses historical reward data to construct robust empirical Bellman operators. Our results continue to hold even when the true reward distributions have infinite support, provided they admit bounded second moments.
  arXiv  Detail & Related papers  (2024-09-05T04:37:02Z)
• Noisy Correspondence Learning with Self-Reinforcing Errors Mitigation [63.180725016463974]
  Cross-modal retrieval relies on well-matched large-scale datasets that are laborious in practice. We introduce a novel noisy correspondence learning framework, namely textbfSelf-textbfReinforcing textbfErrors textbfMitigation (SREM)
  arXiv  Detail & Related papers  (2023-12-27T09:03:43Z)
• Simultaneous Double Q-learning with Conservative Advantage Learning for Actor-Critic Methods [133.85604983925282]
  We propose Simultaneous Double Q-learning with Conservative Advantage Learning (SDQ-CAL) Our algorithm realizes less biased value estimation and achieves state-of-the-art performance in a range of continuous control benchmark tasks.
  arXiv  Detail & Related papers  (2022-05-08T09:17:16Z)
• A Robust Phased Elimination Algorithm for Corruption-Tolerant Gaussian Process Bandits [118.22458816174144]
  We propose a novel robust elimination-type algorithm that runs in epochs, combines exploration with infrequent switching to select a small subset of actions, and plays each action for multiple time instants. Our algorithm, GP Robust Phased Elimination (RGP-PE), successfully balances robustness to corruptions with exploration and exploitation. We perform the first empirical study of robustness in the corrupted GP bandit setting, and show that our algorithm is robust against a variety of adversarial attacks.
  arXiv  Detail & Related papers  (2022-02-03T21:19:36Z)
• Linear Contextual Bandits with Adversarial Corruptions [91.38793800392108]
  We study the linear contextual bandit problem in the presence of adversarial corruption. We present a variance-aware algorithm that is adaptive to the level of adversarial contamination $C$.
  arXiv  Detail & Related papers  (2021-10-25T02:53:24Z)
• Risk Minimization from Adaptively Collected Data: Guarantees for Supervised and Policy Learning [57.88785630755165]
  Empirical risk minimization (ERM) is the workhorse of machine learning, but its model-agnostic guarantees can fail when we use adaptively collected data. We study a generic importance sampling weighted ERM algorithm for using adaptively collected data to minimize the average of a loss function over a hypothesis class. For policy learning, we provide rate-optimal regret guarantees that close an open gap in the existing literature whenever exploration decays to zero.
  arXiv  Detail & Related papers  (2021-06-03T09:50:13Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.