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

arXiv: https://arxiv.org/abs/2404.03578 · HTML: https://mlsanity.com/paper/2404.03578/

## Key facts

- Cited by 26 papers in the map (data through 14 Oct 2026).
- Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods.
- Builds on 62 of its 82 references that are in the map.
- First posted on arXiv 4 Apr 2024.

## Placed in

- Deep reinforcement learning methods / [RL theory and sample complexity](https://mlsanity.com/deeprl/rl-theory-and-sample-complexity/)

## Builds on (most cited first, 30 of 62)

- [Training language models to follow instructions with human feedback](https://mlsanity.com/paper/2203.02155/) (2022)
- [Deep Reinforcement Learning for Autonomous Driving: A Survey](https://mlsanity.com/paper/2002.00444/) (2020)
- [Sim-to-Real Transfer of Robotic Control with Dynamics Randomization](https://mlsanity.com/paper/1710.06537/) (2017)
- [Provably Efficient Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/1907.05388/) (2019)
- [Minimax Regret Bounds for Reinforcement Learning](https://mlsanity.com/paper/1703.05449/) (2017)
- [Is Q-learning Provably Efficient?](https://mlsanity.com/paper/1807.03765/) (2018)
- [Robust Adversarial Reinforcement Learning](https://mlsanity.com/paper/1703.02702/) (2017)
- [Sim-to-Real Transfer in Deep Reinforcement Learning for Robotics: a Survey](https://mlsanity.com/paper/2009.13303/) (2020)
- [Contextual Decision Processes with Low Bellman Rank are PAC-Learnable](https://mlsanity.com/paper/1610.09512/) (2016)
- [Model-Based Reinforcement Learning with Value-Targeted Regression](https://mlsanity.com/paper/2006.01107/) (2020)
- [CAD2RL: Real Single-Image Flight without a Single Real Image](https://mlsanity.com/paper/1611.04201/) (2016)
- [Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithms](https://mlsanity.com/paper/2102.00815/) (2021)
- [The Statistical Complexity of Interactive Decision Making](https://mlsanity.com/paper/2112.13487/) (2021)
- [Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processes](https://mlsanity.com/paper/2012.08507/) (2020)
- [Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Bounds](https://mlsanity.com/paper/1901.00210/) (2019)
- [Bilinear Classes: A Structural Framework for Provable Generalization in RL](https://mlsanity.com/paper/2103.10897/) (2021)
- [Unifying PAC and Regret: Uniform PAC Bounds for Episodic Reinforcement Learning](https://mlsanity.com/paper/1703.07710/) (2017)
- [Almost Optimal Model-Free Reinforcement Learning via Reference-Advantage Decomposition](https://mlsanity.com/paper/2004.10019/) (2020)
- [Supervised Reinforcement Learning with Recurrent Neural Network for Dynamic Treatment Recommendation](https://mlsanity.com/paper/1807.01473/) (2018)
- [Is Reinforcement Learning More Difficult Than Bandits? A Near-optimal Algorithm Escaping the Curse of Horizon](https://mlsanity.com/paper/2009.13503/) (2020)
- [Online Robust Reinforcement Learning with Model Uncertainty](https://mlsanity.com/paper/2109.14523/) (2021)
- [Robust Reinforcement Learning using Offline Data](https://mlsanity.com/paper/2208.05129/) (2022)
- [Is Q-Learning Minimax Optimal? A Tight Sample Complexity Analysis](https://mlsanity.com/paper/2102.06548/) (2021)
- [Distributionally Robust Model-Based Offline Reinforcement Learning with Near-Optimal Sample Complexity](https://mlsanity.com/paper/2208.05767/) (2022)
- [Sample Complexity of Robust Reinforcement Learning with a Generative Model](https://mlsanity.com/paper/2112.01506/) (2021)
- [Corruption-robust exploration in episodic reinforcement learning](https://mlsanity.com/paper/1911.08689/) (2019)
- [Policy Gradient Method For Robust Reinforcement Learning](https://mlsanity.com/paper/2205.07344/) (2022)
- [Nearly Minimax Optimal Reinforcement Learning for Linear Markov Decision Processes](https://mlsanity.com/paper/2212.06132/) (2022)
- [The Curious Price of Distributional Robustness in Reinforcement Learning with a Generative Model](https://mlsanity.com/paper/2305.16589/) (2023)
- [Corruption-Robust Offline Reinforcement Learning](https://mlsanity.com/paper/2106.06630/) (2021)

## Built on by (most cited first, 26 of 26)

- [Maximum Likelihood Reinforcement Learning](https://mlsanity.com/paper/2602.02710/) (2026)
- [Upper and Lower Bounds for Distributionally Robust Off-Dynamics Reinforcement Learning](https://mlsanity.com/paper/2409.20521/) (2024)
- [MOBODY: Model Based Off-Dynamics Offline Reinforcement Learning](https://mlsanity.com/paper/2506.08460/) (2025)
- [Unveiling Implicit Advantage Symmetry: Why GRPO Struggles with Exploration and Difficulty Adaptation](https://mlsanity.com/paper/2602.05548/) (2026)
- [ORVIT: Near-Optimal Online Distributionally Robust Reinforcement Learning](https://mlsanity.com/paper/2508.03768/) (2025)
- [Linear Mixture Distributionally Robust Markov Decision Processes](https://mlsanity.com/paper/2505.18044/) (2025)
- [Rectified Robust Policy Optimization for Model-Uncertain Constrained Reinforcement Learning without Strong Duality](https://mlsanity.com/paper/2508.17448/) (2025)
- [Causality-Inspired Robustness for Nonlinear Models via Representation Learning](https://mlsanity.com/paper/2505.12868/) (2025)
- [DR-SAC: Distributionally Robust Soft Actor-Critic for Reinforcement Learning under Uncertainty](https://mlsanity.com/paper/2506.12622/) (2025)
- [Distributionally Robust Optimization via Generative Ambiguity Modeling](https://mlsanity.com/paper/2602.08976/) (2026)
- [Distributionally Robust Multi-Agent Reinforcement Learning for Dynamic Chute Mapping](https://mlsanity.com/paper/2503.09755/) (2025)
- [Pessimism Principle Can Be Effective: Towards a Framework for Zero-Shot Transfer Reinforcement Learning](https://mlsanity.com/paper/2505.18447/) (2025)
- [Online Robust Reinforcement Learning with General Function Approximation](https://mlsanity.com/paper/2512.18957/) (2025)
- [Curriculum-Adapted Robust Reinforcement Learning for UAV Deconfliction in Adversarial Environments](https://mlsanity.com/paper/2506.21129/) (2025)
- [Distributionally Robust Self Paced Curriculum Reinforcement Learning](https://mlsanity.com/paper/2511.05694/) (2025)
- [Distributionally Robust Online Markov Game with Linear Function Approximation](https://mlsanity.com/paper/2511.07831/) (2025)
- [Duality and Policy Evaluation in Distributionally Robust Bayesian Diffusion Control](https://mlsanity.com/paper/2506.19294/) (2025)
- [Robust Reinforcement Learning in Finance: Modeling Market Impact with Elliptic Uncertainty Sets](https://mlsanity.com/paper/2510.19950/) (2025)
- [Distributionally Robust Cooperative Multi-Agent Reinforcement Learning via Robust Value Factorization](https://mlsanity.com/paper/2602.11437/) (2026)
- [The Price of Paranoia: Robust Risk-Sensitive Cooperation in Non-Stationary Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2604.15695/) (2026)
- [Taming the Curses of Multiagency in Robust Markov Games with Large State Space through Linear Function Approximation](https://mlsanity.com/paper/2605.03125/) (2026)
- [Breaking the Epistemic Trap: Active Perception Under Compound Uncertainty](https://mlsanity.com/paper/2605.26627/) (2026)
- [Stationary Robust Mean-Field Games under Model Mismatches](https://mlsanity.com/paper/2606.22579/) (2026)
- [Online Security Learning in Cooperative Multi-Agent Systems under Hidden Byzantine Attacks](https://mlsanity.com/paper/2608.06520/) (2026)
- [Vector Bellman Theory for Multichain Robust Average-Reward Markov Decision Processes](https://mlsanity.com/paper/2609.28792/) (2026)
- [Linear Programming Representations and Strongly Polynomial Algorithms for Robust Markov Decision Processes](https://mlsanity.com/paper/2610.02131/) (2026)

## Abstract (arXiv)

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.