mlsanityData to 7 Oct 2026

Minimax Optimal and Computationally Efficient Algorithms for Distributionally Robust Offline Reinforcement Learning

arXiv 2403.09621 ↗First posted 14 Mar 2024cs.LG cs.AI stat.MLcited by 17

On the map: Offline RL and imitation learning from data → Offline RL algorithms

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.

Key facts. Cited by 17 papers in the map (data through 7 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.

Builds on

44 of 67 references.

Closest ancestors · 12

Same direction, newest first

  1. 2024Offline Multi-task Transfer RL with Representational Penalization19 Feb
  2. 2023Bridging Distributionally Robust Learning and Offline RL: An Approach to Mitigate Distribution Shift and Partial Data Coverage27 Oct
  3. 2023Double Pessimism is Provably Efficient for Distributionally Robust Offline Reinforcement Learning: Generic Algorithm and Robust Partial Coverage16 May
  4. 2022Distributionally Robust Offline Reinforcement Learning with Linear Function Approximation14 Sep
  5. 2022Distributionally Robust Model-Based Offline Reinforcement Learning with Near-Optimal Sample Complexity11 Aug
  6. 2022Nearly Minimax Optimal Offline Reinforcement Learning with Linear Function Approximation: Single-Agent MDP and Markov Game31 May
  7. 2022Near-optimal Offline Reinforcement Learning with Linear Representation: Leveraging Variance Information with Pessimism11 Mar
  8. 2021Provable Benefits of Actor-Critic Methods for Offline Reinforcement Learning19 Aug
  9. 2021Bellman-consistent Pessimism for Offline Reinforcement Learning13 Jun
  10. 2020Is Pessimism Provably Efficient for Offline RL?30 Dec
  11. 2020What are the Statistical Limits of Offline RL with Linear Function Approximation?22 Oct
  12. 2020Offline Reinforcement Learning: Tutorial, Review, and Perspectives on Open Problems4 May

Other references · 32

  1. 2019Scalability in Perception for Autonomous Driving: Waymo Open Datasetcited by 2,436
  2. 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 514
  3. 2017Robust Adversarial Reinforcement Learningcited by 439
  4. 2020Sim-to-Real Transfer in Deep Reinforcement Learning for Robotics: a Surveycited by 388
  5. 2019Information-Theoretic Considerations in Batch Reinforcement Learningcited by 285
  6. 2020Robust Deep Reinforcement Learning against Adversarial Perturbations on State Observationscited by 235
  7. 2020Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processescited by 199
  8. 2019Action Robust Reinforcement Learning and Applications in Continuous Controlcited by 167
  9. 2017Robust Deep Reinforcement Learning with Adversarial Attackscited by 152
  10. 2018Assessing Generalization in Deep Reinforcement Learningcited by 132
  11. 2020Minimax-Optimal Off-Policy Evaluation with Linear Function Approximationcited by 120
  12. 2018Generalization and Regularization in DQNcited by 117
20 more
  1. 2018Supervised Reinforcement Learning with Recurrent Neural Network for Dynamic Treatment Recommendationcited by 101
  2. 2021Online Robust Reinforcement Learning with Model Uncertaintycited by 95
  3. 2022Robust Reinforcement Learning using Offline Datacited by 95
  4. 2021Sample Complexity of Robust Reinforcement Learning with a Generative Modelcited by 82
  5. 2017Reinforcement Learning under Model Mismatchcited by 52
  6. 2023The Curious Price of Distributional Robustness in Reinforcement Learning with a Generative Modelcited by 50
  7. 2023Improved Sample Complexity Bounds for Distributionally Robust Reinforcement Learningcited by 44
  8. 2022Provable Benefits of Representational Transfer in Reinforcement Learningcited by 38
  9. 2023Natural Actor-Critic for Robust Reinforcement Learning with Function Approximationcited by 35
  10. 2021Variance-Aware Off-Policy Evaluation with Linear Function Approximationcited by 34
  11. 2015Distributionally Robust Counterpart in Markov Decision Processescited by 32
  12. 2022Provable Benefit of Multitask Representation Learning in Reinforcement Learningcited by 29
  13. 2024Distributionally Robust Off-Dynamics Reinforcement Learning: Provable Efficiency with Linear Function Approximationcited by 25
  14. 2022Online Policy Optimization for Robust MDPcited by 19
  15. 2021Learning Robust Policy against Disturbance in Transition Dynamics via State-Conservative Policy Optimizationcited by 18
  16. 2023Single-Trajectory Distributionally Robust Reinforcement Learningcited by 15
  17. 2022Provable General Function Class Representation Learning in Multitask Bandits and MDPscited by 12
  18. 2023Robust Markov Decision Processes without Model Estimationcited by 11
  19. 2023Wasserstein Distributionally Robust Policy Evaluation and Learning for Contextual Banditscited by 9
  20. 2023On Estimation of Optimal Dynamic Treatment Regimes with Multiple Treatments for Survival Data-With Application to Colorectal Cancer Studycited by 2

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 5; 2025: 9; 2026: 3.

17 papers.

Sort:

By area:

  1. 2024Distributionally Robust Reinforcement Learning with Interactive Data Collection: Fundamental Hardness and Near-Optimal Algorithmscited by 24
  2. 2024Upper and Lower Bounds for Distributionally Robust Off-Dynamics Reinforcement Learningcited by 15
  3. 2024Sample Complexity of Offline Distributionally Robust Linear Markov Decision Processescited by 12
  4. 2024Hybrid Transfer Reinforcement Learning: Provable Sample Efficiency from Shifted-Dynamics Datacited by 8
  5. 2024Robust Offline Reinforcement Learning with Linearly Structured f-Divergence Regularizationcited by 8
  6. 2025MOBODY: Model Based Off-Dynamics Offline Reinforcement Learningcited by 8
  7. 2025Linear Mixture Distributionally Robust Markov Decision Processescited by 5
  8. 2025ORVIT: Near-Optimal Online Distributionally Robust Reinforcement Learningcited by 5
  9. 2025Dual-Robust Cross-Domain Offline Reinforcement Learning Against Dynamics Shiftscited by 5
  10. 2025Rectified Robust Policy Optimization for Model-Uncertain Constrained Reinforcement Learning without Strong Dualitycited by 4
  11. 2025DR-SAC: Distributionally Robust Soft Actor-Critic for Reinforcement Learning under Uncertaintycited by 3
  12. 2025Model-Free Robust Average-Reward Reinforcement Learning with Sample Complexity Analysiscited by 2
5 more
  1. 2025Distributionally Robust Self Paced Curriculum Reinforcement Learningcited by 1
  2. 2025Online Robust Reinforcement Learning with General Function Approximationcited by 1
  3. 2026Transferable Reinforcement Learning via Probabilistic Latent Embeddings and Dynamic Policy Adaptation for Sim-to-Real Deploymentcited by 0
  4. 2026Improving Generalization and Robustness in Offline Reinforcement Learning via Boundary-Aware Data Augmentationcited by 0
  5. 2026Linear Programming Representations and Strongly Polynomial Algorithms for Robust Markov Decision Processescited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2023Achieving the Asymptotically Optimal Sample Complexity of Offline Reinforcement Learning: A DRO-Based Approach
  2. 2024Robust Offline Reinforcement Learning for Non-Markovian Decision Processes
  3. 2022Optimal Conservative Offline RL with General Function Approximation via Augmented Lagrangian
  4. 2021DROMO: Distributionally Robust Offline Model-based Policy Optimization
  5. 2023Selective Uncertainty Propagation in Offline RL
  6. 2024Diverse Randomized Value Functions: A Provably Pessimistic Approach for Offline Reinforcement Learning
  7. 2023Model-based Offline Reinforcement Learning with Local Misspecification
  8. 2021Uncertainty-Based Offline Reinforcement Learning with Diversified Q-Ensemble