PaperlayerView exact revision on arXiv

Source-linked AI summary

Provably Efficient Q-learning for Robust Reinforcement Learning

Yuchen Jiao, Gen Li

arXiv:2610.35656v1stat.MLcs.AIcs.LGmath.STstat.TH

TL;DR

Standard RL can be affected by sim-to-real gaps, and robust learning from nominal trajectory data must implement robust Bellman updates without estimating the transition kernel. The paper proposes model-free Q-learning for RMDPs and reports a near-minimax sample-complexity bound with an additional (1−γ)^−1 factor.

  • Problem

    Standard RL can be affected by sim-to-real gaps; robust learning must implement robust Bellman updates from nominal trajectory data without explicitly estimating the transition kernel.

    Source: §1 · p. 1, §1.1 · p. 2

  • Method

    The paper proposes model-free Q-learning for TV-uncertain RMDPs using a single trajectory, with O(SA) space complexity.

    Source: §6 · p. 24

  • Results

    The robust Q-learning upper bound is nearly minimax-optimal with an additional factor of (1−γ)^−1.

    Source: §6 · p. 24

  • Takeaways & Limitations

    The authors characterize their results as demonstrating the effectiveness and efficiency of a model-free method for addressing RMDPs.

    Source: §6 · p. 24

    The upper bound retains an additional factor of (1−γ)^−1 relative to the minimax bound.

    Source: §6 · p. 24

Abstract

from arXiv · show

Standard reinforcement learning (RL) algorithms based on Markov Decision Processes (MDPs) are vulnerable to sim-to-real gaps. To address this issue, distributionally robust RL algorithms based on robust MDPs (RMDPs) have been proposed, for ensuring that agents can perform reliably to unpredictable conditions in real-world environments. Despite of the rich literature, \revision{an efficient model-free method is still lacking} for robust RL, particularly for Markovian data, which is more relevant in practical applications. In this work, we take a step towards settling this problem by proposing a sample efficient (asynchronous Q-learning) algorithm for robust RL. In particular, consider a $\gamma$-discounted infinite-horizon RMDP with state space $\mathcal{S}$ and action space $\mathcal{A}$, where the uncertainty set is specified by the total variation (TV) distance with uncertainty level $\sigma$. Assuming access to a single trajectory of Markovian samples induced by a behavior policy and the nominal transition kernel, the sample complexity of the proposed Q-learning algorithm --- to achieve an entrywise $\varepsilon$-approximation of the optimal Q-function --- is bounded by $$ \frac{1}{\mu_{\mathsf{min}}\varepsilon^2(1-\gamma)^3\max\{1-\gamma,\sigma\}} + \frac{t_{\mathsf{mix}}}{\mu_{\mathsf{min}}(1-\gamma)} $$ up to logarithmic factors. Here, $t_{\mathsf{mix}}$ and $\mu_{\mathsf{min}}$ denote the mixing time and the minimum state-action occupancy probability of the sample trajectory, respectively. This result is nearly minimax optimal, with an additional factor of $\frac{1}{1-\gamma}$. Moreover, it achieves a significant improvement over existing bounds.

1 Introduction

The introduction develops model-free asynchronous Q-learning for robust MDPs using a single nominal trajectory generated by behavior-policy data, with the goal of approximating the optimal Q-function. It targets O(SA) space and sample complexity comparable to standard Q-learning, and notes an extension to the synchronous setting.

1 Introduction

  • Standard RL can fail under sim-to-real gaps or small adversarial disruptions, motivating robust policies for uncertain, high-stakes environments.Distributionally robust RL seeks policies that maintain performance when deployment conditions deviate from the nominal model.Source: §1 · pp. 1–2

1.1 Challenges

  • Nominal next-state samples estimate the standard Bellman update, not the robust worst-case update, and the surrogate state must adapt as the value estimate changes.The analysis also accounts for resampling bias and error propagation under changing worst-case kernels.Source: §1.1 · p. 2

1.3 Related Works

  • Prior approaches either store transition models, require generative-model queries for low-memory updates, or use asynchronous dual updates with slower reported convergence.The cited χ2-divergence rate for the asynchronous dual method is O(t^-1/3), versus O(t^-1/2) for standard Q-learning.Source: §1.1 · p. 2, §1.3 · p. 4

2 Problem formulation

  • The paper studies discounted infinite-horizon RMDPs with TV uncertainty around a nominal kernel, using a single trajectory from a uniformly ergodic behavior-policy chain.The sample-complexity parameters include the minimum stationary state-action occupancy and the chain's mixing time.Source: §1.2 · p. 3, §2 · pp. 6–7

1.2 Contributions

  • The proposed algorithm uses O(SA) space on a single trajectory and has nearly minimax-optimal sample complexity comparable to standard Q-learning.It constructs surrogate next states by thresholding the value estimate and redirecting high-value samples to a fixed state.Source: §1.2 · pp. 2–3

2 Problem formulation

  • The mixing time is the time required for the Markov chain to become decorrelated from its initial state, and dTV denotes total variation distance between measures.The passage defines dTV by reference to equation (6).Source: §2 · p. 7
  • The goal is to approximate Q⋆,σ and analyze the sample efficiency of asynchronous Q-learning, with both algorithm and analysis extended to the synchronous setting as a corollary.In the synchronous generative-model setting, independent samples are collected for every state-action pair in each iteration.Source: §2 · p. 7

3 Algorithm

The algorithm replaces the nominal next-state sample in standard Q-learning with a surrogate drawn from a worst-case transition distribution. For TV uncertainty, it constructs this surrogate by resampling according to value-function thresholds, then estimates the resampling parameters from trajectory data in stages.

3 Algorithm

  • Resampling nominal next states according to value-function thresholds constructs a surrogate for the worst-case transition kernel without explicitly estimating the transition model.The algorithm stores two thresholds and a resampling probability per state-action pair, requiring O(SA) space.Source: §3 · pp. 7–8, §3.2 · p. 9

3.1 Ideal resampling construction

  • The ideal TV-based construction shifts probability mass from high-value states to a minimum-value state, yielding a distribution that minimizes expected next-state value.The procedure uses a threshold to decide whether to retain a nominal next state or redirect it to a minimum-value state.Source: §3.1 · p. 8

3.2 Proposed algorithm

  • Because the nominal kernel is unknown, the algorithm estimates resampling parameters from trajectory samples, using bisection and a threshold interval with a randomization probability.A small threshold-estimation error alone may not ensure small bias because the tail probability is a step function; the value function remains fixed while each batch of N samples is collected.Source: §3.2 · pp. 8–9

11 end

  • Stage k updates Q using the value function and resampling parameters from earlier stages while estimating parameters for the next value function.The algorithm uses each nominal observation both to form a surrogate-state Q update and to estimate parameters; later stages use more samples under the stated schedule.Source: §3.2 · p. 9, §11 · p. 10

22 end

The section establishes sample-complexity guarantees for robust Q-learning and develops the proof controls used to bound Q-function error. It separates variance and higher-order sampling-noise terms and outlines resampling error controls for the asynchronous analysis.

22 end

  • Compared with Yang et al. (2023), the method’s single-resampled-state update avoids dual optimization and has convergence rate O(t^-1/2) versus O(t^-1/3).Their approach handles general divergences under regularity conditions, while this resampling scheme is tailored to TV uncertainty sets; the cited comparison uses their χ2-divergence result.Source: §22 · p. 12, §4.1 · p. 13

4.1 Main results: sample complexity of Algorithm 3

  • For asynchronous robust Q-learning, the main term of the sample complexity for ε-accuracy is nearly minimax optimal, with an additional factor of 1/(1−γ).The model-free algorithm has space complexity O(SA).Source: §4.1 · pp. 12–13
  • For asynchronous learning, robust-MDP sample complexity matches standard MDPs when σ ≤ 1−γ and improves by σ/(1−γ) when 1−γ < σ < 1.The paper conjectures that the extra 1/(1−γ) factor in its near-minimax guarantee is also unavoidable for robust MDPs.Source: §4.1 · p. 13

4.2 Extension: sample complexity of synchronous setting

  • For synchronous learning, the sample bound scales as SA/[ε²(1−γ)³ max{1−γ, σ}], up to logarithmic factors, and is nearly minimax optimal up to 1/(1−γ).When 1−γ < σ < 1, its sample complexity is lower than standard MDP learning by a factor σ/(1−γ).Source: §4.2 · p. 14

5.2 Key lemmas

  • The key lemmas show that ideal resampling produces the worst-case transition kernel and bound expectation and variance errors from estimated resampling parameters.They also bound value-function ranges by a quantity scaling as 1/max{σ, 1−γ}, which supports the resampling-error control.Source: §5.2 · pp. 16–17

5.3 Proof of Theorem 1

  • The proof decomposes Q-function error into propagation, sampling noise, and resampling bias, then controls cumulative noise under changing worst-case kernels.The analysis bounds resampling bias and sampling noise within stages before combining those bounds to establish the sample-complexity guarantee.Source: §4.1 · p. 13, §5.3 · p. 18
  • Robust Bellman propagation complicates variance control because the transition kernel used for error propagation differs from the one used to compute variance.The analysis separates variance under parameter-dependent distributions from resampling error; another variance term compares value functions under different distributions, requiring separate bounds.Source: §5.3 · pp. 20–21
  • The proof also bounds the higher-order sampling-noise term appearing in both cumulative noise expressions using the lower bounds on the stage length and sample budget.The resulting variance and higher-order bounds are combined with the resampling-bias terms before establishing the overall error bound.Source: §5.3 · pp. 22–23
  • Combining the noise bounds yields an error bound for every iteration, which the final lemma uses to complete the sample-complexity proof.The derivation uses the logarithmic factor and sample-budget condition, with a stated restriction relating ετ to (1−γ)ε.Source: §5.3 · p. 23

6 Discussions

The paper presents a model-free robust Q-learning algorithm for a single trajectory with O(SA) space complexity. Its sample-complexity bound is nearly minimax optimal up to an additional factor, and the authors also extend the algorithm and analysis to the synchronous setting.

6 Discussions

  • The proposed model-free algorithm operates on a single trajectory and achieves O(SA) space complexity.The paper contrasts this with O(S2A) space for existing model-based approaches.Source: §6 · p. 24
  • The authors report that the bound significantly outperforms existing asynchronous Q-learning sample-complexity bounds for RMDPs.They also extend the algorithm and its analysis to the synchronous setting.Source: §6 · p. 24
  • The sample-complexity bound is nearly minimax optimal, with an additional factor of (1−γ)^−1.The authors identify closing this gap as a direction for future work.Source: §6 · p. 24
  • The analysis is specific to TV uncertainty sets; extending the resampling construction and guarantees to other uncertainty sets remains future work.The authors mention χ2-divergence as an alternative distance measure to explore.Source: §6 · p. 24

A preliminary Lemmas

The preliminary lemmas collect auxiliary bounds, including one on differences between worst-case expectations. The proof of Lemma 5 controls stagewise error by separating sampling noise from resampling bias.

A preliminary Lemmas

  • The preliminary lemmas include an upper bound on the difference between worst-case expectations for two value functions.The section introduces auxiliary lemmas used throughout the proof.Source: A preliminary Lemmas · p. 25

B Proof of Lemma 5

  • For sampling noise, the proof applies Bernstein’s inequality to weighted resampled next states indexed by successive visits to each state-action pair.For a fixed stage and visit count, the resampled samples are independent and the weights are deterministic.Source: B Proof of Lemma 5 · p. 26
  • The proof controls resampling bias by bounding the weighted bias with the single-sample expectation discrepancy and a span bound.A union bound makes the sampling-noise bounds hold simultaneously across stages and state-action pairs.Source: B Proof of Lemma 5 · pp. 26–27

C Proof of Lemma 6

The Lemma 6 proof iterates a two-stage error recursion and bounds accumulated error terms. The Lemma 7 proof controls propagated variance by aligning transition matrices and summing across stages.

C Proof of Lemma 6

  • Because stage k updates use V_{k−2}, the proof iterates the error recursion separately over even and odd stages.It first derives a one-stage inequality.Source: C Proof of Lemma 6 · p. 27
  • The Lemma 6 argument bounds accumulated resampling bias and scalar error terms before deriving the stagewise error bound.It substitutes the bounds for accumulated bias, sampling noise, and stagewise terms into the recursion.Source: C Proof of Lemma 6 · pp. 27–28

D Proof of Lemma 7

  • The Lemma 7 proof aligns the greedy-policy transition matrix with propagation under the optimal policy, then sums variance bounds across stages.The second-moment terms cancel between consecutive stages except for boundary terms and terms from changing denominators.Source: D Proof of Lemma 7 · pp. 29–31

E Proof of Lemma 8

The Lemma 8 proof reduces weighted standard deviations to variance sums and handles the optimal value function and policy terms. The Lemma 9 proof decomposes and bounds the variance discrepancy uniformly over state-action pairs.

E Proof of Lemma 8

  • The Lemma 8 proof reduces weighted standard deviations to variances and centers the optimal value and Q-functions by the minimum optimal Q-value.The centering allows the functions to be bounded by their spans while preserving variance.Source: E Proof of Lemma 8 · pp. 32–33
  • To align second-moment terms with propagation, the proof replaces the optimal policy with the stage’s greedy policy and sums the resulting bounds.Increasing stage denominators make interior terms nonpositive, leaving a boundary term.Source: E Proof of Lemma 8 · pp. 33–34

F Proof of Lemma 9

  • The Lemma 9 proof separates variance discrepancy from estimated resampling parameters and differences between ideal variances, then bounds it uniformly over state-action pairs.The resulting scalar bound is preserved by the propagation matrices.Source: F Proof of Lemma 9 · pp. 35–36

G Proof of Lemma 10

The proof bounds a recursively defined error sequence by induction and simplifies the resulting inequalities. The following section introduces proofs of the key lemmas from Section 5.2.

G Proof of Lemma 10

  • Induction reduces the error analysis to bounding the auxiliary sequence eΔ_k, with Δ_k bounded by an earlier term of that sequence.The proof first defines Δ_k as a maximum over neighboring indices, then uses Δ_k ≤ eΔ_⌊k/2⌋ to focus on eΔ_k.Source: G Proof of Lemma 10 · pp. 37–38
  • The induction step establishes the claimed inequality for the next index, after which the proof simplifies the bounds and completes the lemma.The argument assumes the inequality through index k−1 and chooses a sufficiently large universal constant.Source: G Proof of Lemma 10 · pp. 38–39

H Proof of key lemmas

H.1 Proof of Lemma 1

The proofs characterize the worst-case transition distribution under the TV uncertainty set and bound errors from its estimated resampling parameters. The latter analysis controls both expectation and variance differences.

H.1 Proof of Lemma 1

  • The worst-case transition distribution is obtained by removing probability mass from the largest value states, with partial removal at a threshold when needed.The proof shows the resulting distribution solves the optimization problem and is generated by the ideal resampling procedure.Source: §H.1 · pp. 39, 41
  • For the minimum-value state, the proof handles separately whether the threshold equals the minimum value or lies above it, verifying that resampling matches the specified distribution.These cases, together with the other threshold cases, establish the claimed resampling identity.Source: §H.1 · pp. 42–43

H.2 Proof of Lemma 2

  • The estimated threshold interval has width at most ε_τ for every stage and state-action pair.The proof applies conditional Bernstein bounds to visit batches and takes a union bound over updates, pairs, and stages.Source: §H.2 · pp. 43, 45
  • The estimated resampling parameters are analyzed through three threshold-position cases, bounding the expectation difference and then the variance difference.The variance argument separates the changed centering mean from redistributed probability mass.Source: §H.2 · pp. 44, 49, 50

H.3 Proof of Lemma 3

The proof expresses each stage-end update as an ideal robust update plus an error, then uses induction to control the resulting error and span. It bounds sampling noise and resampling bias separately.

H.3 Proof of Lemma 3

  • The optimal robust Q-function is bounded above by 1/max{σ, 1−γ}.Source: §H.3 · p. 50
  • The stage-end update is decomposed into an ideal robust update and an error combining sampling noise with resampling bias.The proof then controls the resulting span recursively.Source: §H.3 · p. 51
  • Induction bounds the update error by treating sampling noise and resampling bias separately, using the value-span bound and Lemma 2.The proof applies Bernstein’s inequality to the sampling term.Source: §H.3 · p. 52

I.1 Proof of Lemma 4

The proof uses geometrically scheduled stage lengths and invokes the lower bound on T to establish its remaining conditions.

I.1 Proof of Lemma 4

  • Stage lengths are defined geometrically as T_k = (1−β)^(K−k)T.Source: §I.1 · p. 53
  • The proof uses the lower bound on T from assumption (18) to establish the remaining inequality and complete the proof.Source: §I.1 · p. 53

I.2 Proof of Lemma 11

The numerical simulations report trends consistent with the theoretical bounds across asynchronous and synchronous settings. The synchronous algorithm updates all state-action Q-values in each iteration while retaining O(SA) space complexity.

J Algorithm for synchronous setting

  • The synchronous algorithm updates Q_t(s,a) and b^mid_{s,a} for all state-action pairs in each iteration and uses O(SA) space.It extends Algorithm 3 by making these updates simultaneously.Source: J Algorithm for synchronous setting · p. 55

K Numerical simulations

  • For asynchronous runs, complexity follows a horizon^-4 trend at σ=0.001 and a horizon^-3 trend at σ=0.2.The paper reports these trends as consistent with its theoretical results.Source: K Numerical simulations · p. 55
  • In synchronous settings, the observed sample-complexity trends match those in asynchronous settings and further validate the theoretical results.The experiments examine dependence on both the effective horizon and uncertainty level.Source: K Numerical simulations · p. 55

13 end

The provided appendix-end material includes a partial algorithm fragment and figures illustrating the considered RMDP and reporting synchronous sample-complexity dependence on the effective horizon and σ.

13 end

  • The algorithm fragment shows a value-function update followed by resampling-probability computation.It specifies V_k(s) as the maximum over actions of Q_{T_k}(s,a).Source: §13 · p. 56

23 end

  • Figure 1 illustrates the RMDP considered in the paper.The supplied caption does not describe the illustration's specific elements.Source: Figure 1 · p. 57
  • Figure 3 reports synchronous sample complexity against the effective horizon and σ, with target error ε=0.5.The supplied caption identifies the plotted quantities but does not state a comparison outcome.Source: Figure 3 · p. 58
Loading 2610.35656v1…