Technical Summary: Corruption-Tolerant Asynchronous Q-learning with Near-Optimal Rates

Problem Formulation

This paper addresses the problem of learning an optimal policy in a discounted, infinite-horizon Markov Decision Process (MDP) under the presence of adversarially corrupted rewards. The setting involves an agent interacting with an environment modeled as an MDP $(S, A, P, R, \gamma)$, where data is collected online via a behavior policy $\mu$ that induces a Markov chain.

The core challenge is the Huber contamination model applied to rewards. At each time step $t$, with probability $1-\epsilon$, the agent observes a reward sampled from the true distribution $R(s_t, a_t)$, which is allowed to be heavy-tailed (admitting only a finite second moment). With probability $\epsilon$, the reward is drawn from an arbitrary, potentially unbounded adversarial distribution $Q$ that can depend on the history. The goal is to estimate the optimal state-action value function $Q^*$ with a finite-time error bound that holds with high probability, despite the corruption and the time-correlated nature of the data (asynchronous, single-trajectory sampling).

Methodology

The authors propose Robust Async-Q, a novel variant of the Q-learning algorithm designed to handle asynchronous sampling and adversarial corruption. The algorithm integrates two primary mechanisms:

1. Robust Reward Estimation via Trimmed Means:
   Instead of using raw sample means, the algorithm maintains a history of rewards for each state-action pair $(s, a)$. It employs a univariate trimmed mean estimator (based on Lugosi & Mendelson, 2021) to compute a robust estimate of the expected reward. This estimator divides the data into two halves, uses one to compute empirical quantiles for filtering, and averages the remaining samples in the second half that fall within these quantiles. This approach provides robustness against heavy-tailed distributions and a fraction of outliers.

2. Adaptive Thresholding:
   To address the probabilistic nature of robust mean estimation guarantees (which may fail on rare extreme events) and the lack of knowledge regarding reward statistics in some settings, the algorithm employs an adaptive thresholding mechanism.

   • Known Statistics: If bounds on the reward mean and variance ($\bar{R}, \bar{\sigma}$) are known, an adaptive threshold $G_t$ is constructed. If the robust estimate exceeds this threshold, the estimate is discarded (set to zero). The threshold shrinks over time as more samples are collected.
   • Reward-Agnostic (Unknown Statistics): When reward statistics are unknown, the algorithm uses a "slowly growing" function of time, $m(t) = t^p$, as a proxy for the unknown bounds. This ensures the threshold eventually dominates any true constant bound, allowing the algorithm to function without prior knowledge of the reward distribution's scale.

The algorithm updates the Q-values using these filtered and thresholded reward proxies within the standard asynchronous Q-learning update rule. For the single-trajectory Markovian setting, the authors propose a sub-sampling strategy (using every $\tau$-th sample, where $\tau$ relates to the mixing time) to decouple temporal dependencies, effectively reducing the problem to an i.i.d.-like analysis.

Key Contributions

1. Novel Algorithm: The paper introduces Robust Async-Q and its reward-agnostic variant Robust Async-RAQ. These are the first algorithms to provide finite-time robustness guarantees for asynchronous Q-learning under adversarial corruption and heavy-tailed noise.
2. Finite-Time Upper Bounds:
   • Under i.i.d. sampling, the authors prove that the algorithm converges to $Q^*$ at a rate of $\tilde{O}(1/\sqrt{T})$, matching the optimal rate for vanilla Q-learning, up to an additive term scaling with $\sqrt{\epsilon}$.
   • Under Markovian (single-trajectory) sampling, the bounds are preserved up to an inflation factor related to the mixing time of the underlying chain, consistent with non-robust asynchronous Q-learning results.
3. Information-Theoretic Lower Bound: The authors establish a fundamental lower bound of $\Omega(\sqrt{\epsilon})$ on the estimation error of $Q^*$. This proves that the additive corruption term in their upper bound is unavoidable, even in a synchronous setting where all state-action pairs are observed simultaneously.
4. Novel Proof Techniques:
   • Refined Azuma-Hoeffding Inequality: A critical technical contribution is the application of a refined variant of the Azuma-Hoeffding inequality (Shamir & Spencer, 1987). This tool is necessary because the martingale differences in the reward-agnostic setting admit a coarse deterministic bound (scaling with time) but a finer high-probability bound. Standard concentration inequalities fail to yield non-vacuous results in this context.
   • Coupling for Markov Data: The analysis extends to single-trajectory data using a coupling technique to relate the sub-sampled Markov chain to an i.i.d. sequence.

Results

• Convergence Rates: The proposed algorithms achieve near-optimal finite-time rates. Specifically, the error bound is of the form:
  $$\|Q_T - Q^*\|_\infty \leq \tilde{O}\left(\frac{1}{\sqrt{T}}\right) + O(\sqrt{\epsilon})$$
  The $O(\sqrt{\epsilon})$ term depends on the corruption fraction and the noise variance but is independent of the magnitude of the adversarial attacks.
• Robustness to Heavy Tails: The algorithms function correctly even when the true reward distributions are heavy-tailed (only finite second moment), a setting where standard Q-learning often fails or requires sub-Gaussian assumptions.
• Agnostic Performance: The reward-agnostic variant (Robust Async-RAQ) achieves the same rates as the known-statistics variant, with only a slight polynomial inflation in the dependence on the unknown scale parameter.
• Simulations: Empirical results on Grid-world, FrozenLake, CliffWalking, and Taxi environments demonstrate that vanilla Q-learning suffers significant errors under corruption, while the proposed robust variants converge to a neighborhood of the optimal value function.

Significance and Claims

The paper claims to provide the first principled and comprehensive study of adversarial robustness in the infinite-horizon, discounted RL setting with asynchronous, Markovian data.

• Theoretical Completeness: By providing matching upper and lower bounds (up to the corruption term), the work paints a "fairly complete picture" of the fundamental limits of learning in such adversarial environments.
• Bridging Gaps: It bridges the gap between robust statistics (specifically the Huber model and trimmed means) and the non-asymptotic analysis of asynchronous stochastic approximation.
• Practical Relevance: The work addresses real-world concerns where feedback data (rewards) can be noisy, biased, or maliciously corrupted, such as in human feedback for large language models or sensor data in autonomous systems.
• Methodological Advancement: The introduction of the refined Azuma-Hoeffding inequality for handling "coarse deterministic but fine probabilistic" bounds is highlighted as a tool with potential broader applicability in the study of RL algorithms beyond this specific problem.

The authors note that while their work establishes strong theoretical guarantees, future directions include extending the framework to corruptions in the full feedback stream (transitions and rewards) and to function approximation settings.