cs.LGApr 4, 2024

Distributionally Robust Reinforcement Learning with Interactive Data Collection: Fundamental Hardness and Near-Optimal Algorithms

Authors: Miao Lu, Han Zhong, Tong Zhang, Jose Blanchet

Abstract

The sim-to-real gap, which represents the disparity between training and testing environments, poses a significant challenge in reinforcement learning (RL). A promising approach to addressing this challenge is distributionally robust RL, often framed as a robust Markov decision process (RMDP). In this framework, the objective is to find a robust policy that achieves good performance under the worst-case scenario among all environments within a pre-specified uncertainty set centered around the training environment. Unlike previous work, which relies on a generative model or a pre-collected offline dataset enjoying good coverage of the deployment environment, we tackle robust RL via interactive data collection, where the learner interacts with the training environment only and refines the policy through trial and error. In this robust RL paradigm, two main challenges emerge: managing distributional robustness while striking a balance between exploration and exploitation during data collection. Initially, we establish that sample-efficient learning without additional assumptions is unattainable owing to the curse of support shift; i.e., the potential disjointedness of the distributional supports between the training and testing environments. To circumvent such a hardness result, we introduce the vanishing minimal value assumption to RMDPs with a total-variation (TV) distance robust set, postulating that the minimal value of the optimal robust value function is zero. We prove that such an assumption effectively eliminates support shift pathologies for RMDPs with a TV distance robust set, and present an algorithm with near-optimal sample complexity. To demonstrate the breadth of our framework, we extend our algorithm and theory to new robust set formulations and robust Markov games. To illustrate the operational relevance, we apply our algorithm to data-driven robust inventory control.

Explore similar work

CardsList
May 8, 2026cs.LG

Central Limit Theorem for Two-Time-Scale Approximate Distributionally Robust RL

Designing model-free algorithms for distributionally robust reinforcement learning (DRRL) poses fundamental challenges. The robust Bellman operator is nonlinear in the transition kernel, which makes one-sample Bellman updates biased, while the adversarial optimization underlying robustness makes robust evaluation computationally demanding. To address these difficulties, we consider the natural small-ambiguity regime under Kullback--Leibler ambiguity sets and propose an approximate DRRL framework based on a first-order expansion of the relevant robust functional. This yields an approximate robust Bellman equation that removes the adversarial optimization while remaining first-order accurate in the ambiguity radius. To learn the fixed point of this approximate equation, we propose Mean-Variance Stochastic Approximation (MVSA), a model-free algorithm that uses only one-sample updates. This is achieved via a lifted stochastic approximation dynamics and a two-time-scale design. We then prove convergence and a central limit theorem for MVSA: its main iterate satisfies a central limit theorem at the canonical n−1/2n^{-1/2} scale, with explicitly characterized asymptotic covariances. Finally, we validate our theoretical findings with a numerical experiment.
Shengbo Wang, Zexi Zhang
Distributional Reinforcement LearningModel-Free Reinforcement LearningLarge Deviations TheoryBellman EquationLow-Data Regimes
AskPDF
Aug 6, 2026cs.LG

Robust Average-Reward Markov Decision Processes: Minimax-Optimal Learning via Plug-in Reductions

Distributionally robust Markov decision processes provide a principled framework for sequential decision making under model uncertainty. We study how many samples are necessary and sufficient to learn an ε\varepsilon-optimal robust policy under the average-reward criterion. A generative model provides samples from the nominal transition kernel, whereas policy performance is evaluated over (s,a)(s,a)-rectangular total-variation uncertainty sets of radius at most σσ. Let H0H_0 and HσH_σ denote the nominal and robust optimal bias spans, respectively. We identify σH0σH_0 as the perturbation scale separating high- and low-tolerance regimes. Our matching upper and lower bounds show that, up to logarithmic factors, the minimax total sample complexity is NSA≍SAε2{min⁡{H0,Hσ},ε≳σH0,min⁡{H0,Hσ}+σHσ2,ε≲σH0.NSA \asymp \frac{SA}{\varepsilon^2}\begin{cases} \min\{H_0,H_σ\}, & \varepsilon\gtrsimσH_0,\\ \min\{H_0,H_σ\}+σH_σ^2, & \varepsilon\lesssimσH_0. \end{cases} Here SS and AA are the numbers of states and actions, and NN is the number of samples per state-action pair. The sample complexity consists of a linear-span term that resembles the nominal AMDP results and a robustness-specific term that appears only in the low-tolerance regime. We attain these rates using reduction-based plug-in procedures that select the reduction---nominal or robust---and its discount factor: a span-informed procedure that makes these choices using known span parameters, and a span-agnostic procedure that calibrates both choices from data.
Yuepeng Yang, Yuxin Chen, Yuejie Chi
Markov Decision ProcessesOptimal PoliciesOptimal LearnerSample ComplexityDecisions
AskPDF
May 18, 2025cs.LG

Model-Free Robust Average-Reward Reinforcement Learning with Sample Complexity Analysis

Robust reinforcement learning (RL) under the average-reward criterion is essential for long-term decision-making, particularly when the environment may differ from its training dynamics. However, most existing studies focus on model-based settings and provide only asymptotic guarantees, hindering their principled understanding and practical deployment, especially in data-limited scenarios. We aim to close this gap by proposing a model-free algorithm, \textbf{Robust Halpern Iteration (RHI)}. We first design our algorithm based on a black-box sampling oracle, which can estimate the worst-case performance accurately. We then derive the finite sample complexity of RHI under the generative model setting, assuming the sampling oracle. To concretely design such an oracle, we propose a KK-order multi-level Monte-Carlo estimator, which is shown to have a lower bias compared to prior methods. We further instantiate our design for multiple uncertainty models, including KL and χ2χ^2 divergence sets, and show that our RHI algorithm achieves an ε\varepsilon-optimal robust policy with a sample complexity of O~(SAH2ε(2+o(1)))\tilde{\mathcal{O}}\left( \frac{SA\mathcal{H}^2}{\varepsilon^{(2+o(1))}}\right), where S,AS,A are the number of states and actions, and H\mathcal{H} is the robust optimal span. Our result asymptotically matches the best complexity in robust average reward RL.
Zachary Roch, George Atia, Yue Wang
Model-Free Reinforcement LearningOptimal PoliciesSample Complexity
AskPDF