# Minimax Optimal and Computationally Efficient Algorithms for Distributionally Robust Offline Reinforcement Learning arXiv: https://arxiv.org/abs/2403.09621 ยท HTML: https://mlsanity.com/paper/2403.09621/ ## Key facts - Cited by 17 papers in the map (data through 13 Oct 2026). - Placed in Offline RL algorithms, one of 13 directions in Offline RL and imitation learning from data. - Builds on 44 of its 67 references that are in the map. - First posted on arXiv 14 Mar 2024. ## Placed in - Offline RL and imitation learning from data / [Offline RL algorithms](https://mlsanity.com/offlinerl/offline-rl-algorithms/) ## Builds on (most cited first, 30 of 44) - [Scalability in Perception for Autonomous Driving: Waymo Open Dataset](https://mlsanity.com/paper/1912.04838/) (2019) - [Offline Reinforcement Learning: Tutorial, Review, and Perspectives on Open Problems](https://mlsanity.com/paper/2005.01643/) (2020) - [Provably Efficient Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/1907.05388/) (2019) - [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) - [Is Pessimism Provably Efficient for Offline RL?](https://mlsanity.com/paper/2012.15085/) (2020) - [Information-Theoretic Considerations in Batch Reinforcement Learning](https://mlsanity.com/paper/1905.00360/) (2019) - [Bellman-consistent Pessimism for Offline Reinforcement Learning](https://mlsanity.com/paper/2106.06926/) (2021) - [Robust Deep Reinforcement Learning against Adversarial Perturbations on State Observations](https://mlsanity.com/paper/2003.08938/) (2020) - [Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processes](https://mlsanity.com/paper/2012.08507/) (2020) - [Action Robust Reinforcement Learning and Applications in Continuous Control](https://mlsanity.com/paper/1901.09184/) (2019) - [Robust Deep Reinforcement Learning with Adversarial Attacks](https://mlsanity.com/paper/1712.03632/) (2017) - [What are the Statistical Limits of Offline RL with Linear Function Approximation?](https://mlsanity.com/paper/2010.11895/) (2020) - [Assessing Generalization in Deep Reinforcement Learning](https://mlsanity.com/paper/1810.12282/) (2018) - [Minimax-Optimal Off-Policy Evaluation with Linear Function Approximation](https://mlsanity.com/paper/2002.09516/) (2020) - [Generalization and Regularization in DQN](https://mlsanity.com/paper/1810.00123/) (2018) - [Provable Benefits of Actor-Critic Methods for Offline Reinforcement Learning](https://mlsanity.com/paper/2108.08812/) (2021) - [Supervised Reinforcement Learning with Recurrent Neural Network for Dynamic Treatment Recommendation](https://mlsanity.com/paper/1807.01473/) (2018) - [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) - [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) - [Near-optimal Offline Reinforcement Learning with Linear Representation: Leveraging Variance Information with Pessimism](https://mlsanity.com/paper/2203.05804/) (2022) - [Nearly Minimax Optimal Offline Reinforcement Learning with Linear Function Approximation: Single-Agent MDP and Markov Game](https://mlsanity.com/paper/2205.15512/) (2022) - [Reinforcement Learning under Model Mismatch](https://mlsanity.com/paper/1706.04711/) (2017) - [Double Pessimism is Provably Efficient for Distributionally Robust Offline Reinforcement Learning: Generic Algorithm and Robust Partial Coverage](https://mlsanity.com/paper/2305.09659/) (2023) - [The Curious Price of Distributional Robustness in Reinforcement Learning with a Generative Model](https://mlsanity.com/paper/2305.16589/) (2023) - [Improved Sample Complexity Bounds for Distributionally Robust Reinforcement Learning](https://mlsanity.com/paper/2303.02783/) (2023) - [Provable Benefits of Representational Transfer in Reinforcement Learning](https://mlsanity.com/paper/2205.14571/) (2022) - [Natural Actor-Critic for Robust Reinforcement Learning with Function Approximation](https://mlsanity.com/paper/2307.08875/) (2023) ## Built on by (most cited first, 17 of 17) - [Distributionally Robust Reinforcement Learning with Interactive Data Collection: Fundamental Hardness and Near-Optimal Algorithms](https://mlsanity.com/paper/2404.03578/) (2024) - [Upper and Lower Bounds for Distributionally Robust Off-Dynamics Reinforcement Learning](https://mlsanity.com/paper/2409.20521/) (2024) - [Sample Complexity of Offline Distributionally Robust Linear Markov Decision Processes](https://mlsanity.com/paper/2403.12946/) (2024) - [MOBODY: Model Based Off-Dynamics Offline Reinforcement Learning](https://mlsanity.com/paper/2506.08460/) (2025) - [Hybrid Transfer Reinforcement Learning: Provable Sample Efficiency from Shifted-Dynamics Data](https://mlsanity.com/paper/2411.03810/) (2024) - [Robust Offline Reinforcement Learning with Linearly Structured f-Divergence Regularization](https://mlsanity.com/paper/2411.18612/) (2024) - [Linear Mixture Distributionally Robust Markov Decision Processes](https://mlsanity.com/paper/2505.18044/) (2025) - [ORVIT: Near-Optimal Online Distributionally Robust Reinforcement Learning](https://mlsanity.com/paper/2508.03768/) (2025) - [Dual-Robust Cross-Domain Offline Reinforcement Learning Against Dynamics Shifts](https://mlsanity.com/paper/2512.02486/) (2025) - [Rectified Robust Policy Optimization for Model-Uncertain Constrained Reinforcement Learning without Strong Duality](https://mlsanity.com/paper/2508.17448/) (2025) - [Model-Free Robust Average-Reward Reinforcement Learning with Sample Complexity Analysis](https://mlsanity.com/paper/2505.12462/) (2025) - [DR-SAC: Distributionally Robust Soft Actor-Critic for Reinforcement Learning under Uncertainty](https://mlsanity.com/paper/2506.12622/) (2025) - [Distributionally Robust Self Paced Curriculum Reinforcement Learning](https://mlsanity.com/paper/2511.05694/) (2025) - [Online Robust Reinforcement Learning with General Function Approximation](https://mlsanity.com/paper/2512.18957/) (2025) - [Transferable Reinforcement Learning via Probabilistic Latent Embeddings and Dynamic Policy Adaptation for Sim-to-Real Deployment](https://mlsanity.com/paper/2605.27659/) (2026) - [Improving Generalization and Robustness in Offline Reinforcement Learning via Boundary-Aware Data Augmentation](https://mlsanity.com/paper/2609.20300/) (2026) - [Linear Programming Representations and Strongly Polynomial Algorithms for Robust Markov Decision Processes](https://mlsanity.com/paper/2610.02131/) (2026) ## Abstract (arXiv) Distributionally robust offline reinforcement learning (RL), which seeks robust policy training against environment perturbation by modeling dynamics uncertainty, calls for function approximations when facing large state-action spaces. However, the consideration of dynamics uncertainty introduces essential nonlinearity and computational burden, posing unique challenges for analyzing and practically employing function approximation. Focusing on a basic setting where the nominal model and perturbed models are linearly parameterized, we propose minimax optimal and computationally efficient algorithms realizing function approximation and initiate the study on instance-dependent suboptimality analysis in the context of robust offline RL. Our results uncover that function approximation in robust offline RL is essentially distinct from and probably harder than that in standard offline RL. Our algorithms and theoretical results crucially depend on a novel function approximation mechanism incorporating variance information, a new procedure of suboptimality and estimation uncertainty decomposition, a quantification of the robust value function shrinkage, and a meticulously designed family of hard instances, which might be of independent interest.