betaFeedback

WorksMathematics

Provably Efficient Q-learning for Robust Reinforcement Learning

Abstract

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 γγ-discounted infinite-horizon RMDP with state space S\mathcal{S} and action space A\mathcal{A}, where the uncertainty set is specified by the total variation (TV) distance with uncertainty level σσ. 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 1μminε2(1−γ)3max⁡{1−γ,σ}+tmixμmin(1−γ) \frac{1}{μ_{\mathsf{min}}\varepsilon^2(1-γ)^3\max\{1-γ,σ\}} + \frac{t_{\mathsf{mix}}}{μ_{\mathsf{min}}(1-γ)} up to logarithmic factors. Here, tmixt_{\mathsf{mix}} and μminμ_{\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 11−γ\frac{1}{1-γ}. Moreover, it achieves a significant improvement over existing bounds.

Introduction

As a fast-growing subfield of artificial intelligence, reinforcement learning (RL) demonstrated impressive success across various domains, including networked systems (Qu et al., 2022), trading (Park and Van Roy, 2015), operations research (de Castro Silva et al., 2003; Pan et al., 2023; Zhao et al., 2021), large language model alignment (Ziegler et al., 2019), healthcare (Fatemi et al., 2021; Liu et al., 2019), and robotics and control (Kober et al., 2013; Mnih, 2013). Due to the unprecedented dimensionality of the state-action space, enhancing sample, space and computational efficiency has become a central challenge in contemporary RL applications. As a result, significant research efforts have been devoted to developing sample-efficient and memory-efficient algorithms and to characterizing the sample complexity and space complexity (Li et al., 2021b, 2024c, 2022) across diverse RL settings, including different algorithm paradigms (model-based (Li et al., 2024c); model-free (Li et al., 2021a; Zhang et al., 2021)) and different data-access regimes (online (Zhang et al., 2024; Li et al., 2020); offline (Li et al., 2024b; Rashidinejad et al., 2022)).

Despite this progress, practical applications of standard RL techniques can still be greatly affected by the sim-to-real gap or environmental uncertainty (Bertsimas et al., 2019; Zhang et al., 2020). For instance, a standard RL agent trained in an ideal environment might fail drastically when the real-world environment is subject to small adversarial disruptions (Klopp et al., 2017; Mahmood et al., 2018). Consequently, in addition to maximizing the expected total reward, robustness has emerged as an important goal for an RL agent, especially in high-stakes applications like robotics, autonomous driving, clinical trials, and financial investments. To address these challenges, distributionally robust RL [1 Cai et al.,] 2016; Iyengar (2005); Nilim and El Ghaoui (2005); Xu and Mannor (2010); Shi et al. (2025, 2024b); Jiao and Li (2024), offers a flexible framework by drawing on principles from distributionally robust optimization and supervised learning [2] (Blanchet and Murthy 2019; Chen et al. 2019; Duchi and Namkoong 2021; Gao 2023; Lam 2019; Rahimian and Mehrotra 2019). This approach aims to develop policies capable of maintaining high performance even when the deployed environment deviates from the nominal model due to environmental uncertainty.

Challenges

We study robust Markov decision processes (RMDPs) in the discounted infinite-horizon setting, where the learner observes a single trajectory generated by the nominal transition kernel. Our goal is to develop a model-free algorithm that achieves O(SA)O(SA) space complexity and a sample complexity comparable to that of standard Q-learning. The main difficulty is to implement robust Bellman updates using nominal trajectory samples without explicitly estimating the transition kernel.

To explain this difficulty, consider the standard Q-learning update:

Qt+1(st,at)=(1−ηt)Qt(st,at)+ηt(r(st,at)+γVt(st+1)),(1)Q_{t+1}(s_t, a_t) = (1-\eta_t)Q_t(s_t, a_t) + \eta_t\left(r(s_t, a_t) + \gamma V_t(s_{t+1})\right), \tag*{(1)}

where Vt(s)=max⁡a∈AQt(s,a)V_t(s) = \max_{a\in\mathcal{A}} Q_t(s,a) and the observed next state satisfies st+1∼P0(⋅∣st,at)s_{t+1} \sim P^0(\cdot\mid s_t, a_t). The sampled target therefore estimates the nominal Bellman update. In an RMDP, however, the Bellman update involves the smallest expected next-state value over an uncertainty set centered around P0P^0 (cf. (5)). Thus, directly using the observed next state generally does not estimate the desired robust Bellman update.

Our approach is to replace st+1s_{t+1} with a surrogate next state s~t+1\widetilde{s}_{t+1} drawn from a worst-case transition kernel associated with the value function estimate. The resulting ideal update is

Qt+1(st,at)=(1−ηt)Qt(st,at)+ηt(r(st,at)+γVt(s~t+1)).(2)Q_{t+1}(s_t, a_t) = (1-\eta_t)Q_t(s_t, a_t) + \eta_t\left(r(s_t, a_t) + \gamma V_t(\widetilde{s}_{t+1})\right). \tag*{(2)}

The challenge is to construct such a surrogate state using only observations from the nominal kernel. Moreover, the worst-case kernel depends on the value function, so the state construction must be adjusted as the value estimate changes.

Existing approaches address this problem with different resource requirements. Model-based methods estimate and store the nominal transition kernel and then perform robust planning, requiring O(S2A)O(S^2A) space (Shi et al., 2024a; Zhou et al., 2021; Panaganti and Kalathil, 2022; Yang et al., 2022). The model-free method in Wang et al. (2024) reduces the space requirement to O(SA)O(SA), but relies on generative-model access to query arbitrary state-action pairs. Such access is not assumed in our trajectory setting. For Markovian data, Yang et al. (2023) use stochastic gradient ascent to update a dual variable in a penalized Bellman formulation alongside the Q-function. Their reported Q-function convergence rate for the χ2\chi^2-divergence formulation is O(t−1/3)O(t^{-1/3}), which is significantly slower compared with the O(t−1/2)O(t^{-1/2}) rate of standard Q-learning. These limitations motivate the following question:

Can a model-free algorithm for RMDPs learn from a single trajectory with O(SA)O(SA) space complexity and a sample complexity comparable to that of standard Q-learning?

To answer this question, we address two challenges: constructing surrogate state with worst-case expected value from nominal trajectory data without estimating the transition kernel, and controlling the resulting estimation error when the worst-case kernel changes across stages. Our approach uses resampling rather than the dual optimization of Yang et al. (2023). Compared with the standard Q-learning analysis of Li et al. (2024a), our analysis needs to additionally account for resampling bias and error propagation under changing worst-case kernels. We summarize these contributions in § 1.2.

Contributions

In this paper, we propose an efficient Q-learning algorithm for RMDPs that integrates several key advantages. Specifically, the algorithm achieves the optimal space complexity of O(SA)O(SA), and operates effectively in the asynchronous setting in terms of sample complexity. To the best of our knowledge, this is the first algorithm that combines all these advantages and is supported by a rigorous theoretical analysis.

In particular, assume that we have access to a single trajectory of the Markov decision processes (MDPs) with a transition nominal kernel induced by a stationary behavior policy (also called an asynchronous setting). Consider an uncertainty set with the shape and size of the ball specified by the total variation (TV) distance between probability distributions and some uncertainty level σ∈(0,1)\sigma\in(0,1). Let SS be the size of the state space, AA the size of the action space, γ\gamma the discount factor. We are interested in how the space complexity and the sample complexity — the number of samples required for an algorithm to output a Q-function whose entrywise error with the optimal Q-function is at most ε\varepsilon — scales with all these salient problem parameters. Our main contributions are as follows.

  • We design an efficient Q-learning algorithm for RMDPs that operates on a single trajectory and achieves O(SA)O(SA) space complexity. At each time step, the agent selects an action according to a behavior policy and observes the next state st+1∼P0(⋅∣st,at)s_{t+1} \sim P^{0}(\cdot\mid s_t, a_t) according to the nominal transition kernel. We observe that the worst-case transition kernel can be realized by thresholding the value function of st+1s_{t+1} and redirecting state samples with large values to a fixed state. This allows us to construct a surrogate state st+1′s'_{t+1} and update the Q-function following the same form as (2), but with the value function from an earlier stage to avoid using the current Q-estimate when constructing st+1′s'_{t+1}. The resulting space complexity is O(SA)O(SA), which is optimal in the tabular setting where Q-values are explicitly stored. Moreover, the algorithm processes samples as they arrive along a single trajectory generated by a fixed behavior policy. It does not require a generative model or the ability to query arbitrary state-action pairs.

  • We prove that the proposed Q-learning algorithm is sample-efficient. Specifically, it can find an ε\varepsilon-approximation of the optimal Q-function for RMDPs with sample complexity (modulo log factors) of

O~(1μmin⁡ε2(1−γ)3max⁡{1−γ,σ}+tmixμmin⁡(1−γ)).\widetilde{O}\left(\frac{1}{\mu_{\min}\varepsilon^2(1-\gamma)^3\max\{1-\gamma,\sigma\}}+\frac{t_{\mathrm{mix}}}{\mu_{\min}(1-\gamma)}\right).

where tmixt_{\mathrm{mix}} denotes the mixing time that characterizes how fast the trajectory converges to stationary, and μmin⁡\mu_{\min} denotes the minimum state-action occupancy probability of the stationary distribution of the trajectory. Our theoretical results establish a nearly minimax-optimal sample complexity for model-free robust RL, substantially improve existing bounds, and achieve a sample complexity comparable to that of standard Q-learning. As indicated in Shi et al. (2024a), the main term in our bound is nearly minimax-optimal with an additional factor of 11−γ\frac{1}{1-\gamma}, which is shown unavoidable for Q-learning for standard RL (Li et al., 2021b), and we think it is also unavoidable for robust MDP case. In addition, our result improves significantly over the existing bound of O~(1μmin⁡4ε3(1−γ)9(1(1−γ)6+tmix3))\widetilde{O}\left(\frac{1}{\mu_{\min}^{4}\varepsilon^3(1-\gamma)^9}\left(\frac{1}{(1-\gamma)^6}+t_{\mathrm{mix}}^3\right)\right) (Yang et al., 2023) by a factor of μmin⁡4ε(1−γ)7max⁡{1−γ,σ}\frac{\mu_{\min}^4\varepsilon(1-\gamma)^7}{\max\{1-\gamma,\sigma\}}. Furthermore, our result is no larger than the sample complexity of Q-learning for standard RL in Li et al. (2024a), O~(1μmin⁡ε2(1−γ)4+tmixμmin⁡(1−γ))\widetilde{O}\left(\frac{1}{\mu_{\min}\varepsilon^2(1-\gamma)^4}+\frac{t_{\mathrm{mix}}}{\mu_{\min}(1-\gamma)}\right). In particular, if σ≳1−γ\sigma\gtrsim1-\gamma, then the sample complexity for RMDPs is improved by a factor of σ/(1−γ)\sigma/(1-\gamma) when ε\varepsilon is small enough.

  • As a corollary, the proposed algorithm can be naturally extended to the generative model, which assumes access to a simulator (also called a synchronous setting). In this context, we prove that the sample complexity of the proposed synchronous Q-learning algorithm is O~(SAε2(1−γ)3max⁡{1−γ,σ})\widetilde{O}\left(\frac{SA}{\varepsilon^2(1-\gamma)^3\max\{1-\gamma,\sigma\}}\right) (modulo log factors). This result is nearly minimax optimal with an additional factor of 11−γ\frac{1}{1-\gamma} inherent to the design of Q-learning algorithms as stated before. Moreover, similar insights arise when comparing with synchronous Q-learning for standard RL O~(SAε2(1−γ)4)\widetilde{O}\left(\frac{SA}{\varepsilon^2(1-\gamma)^4}\right) (Li et al., 2021b).

Related Works

Robust MDPs have been extensively studied, both empirically and theoretically, under various forms of uncertainty sets (Panaganti and Kalathil, 2021; Ding et al., 2024; Goyal and Grand-Clement, 2023; Ho et al., 2018, 2021; Iyengar, 2005; Xu and Mannor, 2010; Tamar et al., 2014). However, most existing theoretical studies either focus on planning algorithms (Tamar et al., 2014; Xu and Mannor, 2010; Iyengar, 2005) or adopt an asymptotic perspective (Roy et al., 2017). Recently, several robust RL algorithms have been developed, focusing on finite-sample performance guarantees under various sampling mechanisms, as show in Table 1. A line of work focuses on model-based algorithms. In particular, Yang et al. (2022); Panaganti and Kalathil (2022) studied model-based robust RL algorithms with an (s,a)(s,a)-rectangular uncertainty set specified by the TV distance, which matches our uncertainty-set specification, and used data collected from a generative model, corresponding to the synchronous setting in this work. They also considered other uncertainty sets, including those specified by the χ2\chi^2-divergence or the KL divergence, and Yang et al. (2022) additionally considered the ss-rectangular case under these measures. Zhou et al. (2021) assumed that the reward follows a certain distribution on a bounded set and conducted an offline analysis where states are uniformly sampled by a known policy, focusing on uncertainty sets defined by the KL divergence. Panaganti and Kalathil (2021) proposed a policy iteration algorithm based on linear function approximation and analyzed its convergence asymptotically under certain dedicated assumptions on the iterative policy and the induced stationary distribution. Though an asynchronous setting is considered, its space complexity in the tabular case is O(S2A2)O(S^2A^2) to store the feature matrix. Moreover, Shi et al. (2024a) provided the near-optimal sample complexity bounds for model-based robust RL algorithms with access to a generative model when the uncertainty set is measured by the TV distance or the χ2\chi^2-divergence. Specifically, for a TV-based uncertainty set, the minimax-optimal sample complexity of O~(SAε2(1−γ)2max⁡{1−γ,σ})\widetilde{O}\left(\frac{SA}{\varepsilon^2(1-\gamma)^2\max\{1-\gamma,\sigma\}}\right) is achieved by robust value iteration. However, these algorithms require at least O(S2A)O(S^2A) space complexity to store the transition probability kernel, which is prohibitive for large-scale problems.

Algorithmsettinguncertainty setspace compl.sample compl.
Yang et al. (2022)model-basedTV distanceS2AS^2 AS2Aε2(1−γ)4σ2\frac{S^2 A}{\varepsilon^2(1-\gamma)^4\sigma^2}
Panaganti and Kalathil (2022)model-basedTV distanceS2AS^2 AS2Aε2(1−γ)4\frac{S^2 A}{\varepsilon^2(1-\gamma)^4}
Zhou et al. (2021)model-basedKL divergenceS2AS^2 ACP0S2Aε2(1−γ)2σ2\frac{C_{P_0}S^2 A}{\varepsilon^2(1-\gamma)^2\sigma^2}
Shi et al. (2024a)model-basedTV distanceS2AS^2 ASAε2(1−γ)2max⁡{1−γ,σ}\frac{SA}{\varepsilon^2(1-\gamma)^2\max\{1-\gamma,\sigma\}}
Wang et al. (2023)synchronousKL-divergenceSASASAε2(1−γ)5σ4pmin⁡6\frac{SA}{\varepsilon^2(1-\gamma)^5\sigma^4p_{\min}^6}
Wang et al. (2024)synchronousKL-divergenceSASASAε2(1−γ)4pmin⁡3\frac{SA}{\varepsilon^2(1-\gamma)^4p_{\min}^3}
Yang et al. (2023)asynchronousχ2\chi^2-divergenceSASA1μmin⁡9ε3(1−γ)9(1(1−γ)6+tmix3)\frac{1}{\mu_{\min}^9\varepsilon^3(1-\gamma)^9}\left(\frac{1}{(1-\gamma)^6}+t_{\mathrm{mix}}^3\right)
this worksynchronousTV distanceSASASAε2(1−γ)3max⁡{1−γ,σ}\frac{SA}{\varepsilon^2(1-\gamma)^3\max\{1-\gamma,\sigma\}}
this workasynchronousTV distanceSASA1μmin⁡(1ε2(1−γ)3max⁡{1−γ,σ}+tmix1−γ)\frac{1}{\mu_{\min}}\left(\frac{1}{\varepsilon^2(1-\gamma)^3\max\{1-\gamma,\sigma\}}+\frac{t_{\mathrm{mix}}}{1-\gamma}\right)

Table 1. Our results and comparisons with prior art (up to log factors) for robust RL algorithms in terms of setting, uncertainty set, space complexity and the sample complexity. Here tmixt_{\mathrm{mix}} denotes the mixing time, μmin⁡\mu_{\min} denotes the smallest state-action occupancy probability of the stationary distribution of the trajectory, pmin⁡p_{\min} denotes the minimum of nominal transition probability, and CP0C_{P_0} is determined by the nominal transition probability.

References

  1. [1]Bäuerle, N. and Glauner, A. (2022). Distributionally robust markov decision processes and their connection to risk measures. Mathematics of Operations Research, 47(3):1757–1780.DOI
  2. [2]Bertsimas, D., Gupta, V., and Kallus, N. (2018). Data-driven robust optimization. Mathematical Programming, 167:235–292.

Paper details

vlnc:W_etbdsty5
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents