mlsanityData to 7 Oct 2026

Upper and Lower Bounds for Distributionally Robust Off-Dynamics Reinforcement Learning

arXiv 2409.20521 ↗First posted 30 Sep 2024cs.LG cs.AI stat.MLcited by 15

Not on the map. Why?

Abstract (arXiv)

We study off-dynamics Reinforcement Learning (RL), where the policy training and deployment environments are different. To deal with this environmental perturbation, we focus on learning policies robust to uncertainties in transition dynamics under the framework of distributionally robust Markov decision processes (DRMDPs), where the nominal and perturbed dynamics are linear Markov Decision Processes. We propose a novel algorithm We-DRIVE-U that enjoys an average suboptimality widetildeObig(d H · min 1/ρ, H/√K big), where K is the number of episodes, H is the horizon length, d is the feature dimension and ρ is the uncertainty level. This result improves the state-of-the-art by O(dH/min1/ρ,H). We also construct a novel hard instance and derive the first information-theoretic lower bound in this setting, which indicates our algorithm is near-optimal up to O(√H) for any uncertainty level ρ∈(0,1]. Our algorithm also enjoys a 'rare-switching' design, and thus only requires O(dHlog(1+H2K)) policy switches and O(d2Hlog(1+H2K)) calls for oracle to solve dual optimization problems, which significantly improves the computational efficiency of existing algorithms for DRMDPs, whose policy switch and oracle complexities are both O(K).

Key facts. Cited by 15 papers in the map (data through 7 Oct 2026). Builds on 46 of its 61 references that are in the map. First posted on arXiv 30 Sep 2024.

Builds on

46 of 61 references.

References · 46

  1. 2017Sim-to-Real Transfer of Robotic Control with Dynamics Randomizationcited by 616
  2. 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 514
  3. 2017Minimax Regret Bounds for Reinforcement Learningcited by 500
  4. 2018Is Q-learning Provably Efficient?cited by 485
  5. 2020Sim-to-Real Transfer in Deep Reinforcement Learning for Robotics: a Surveycited by 388
  6. 2019Information-Theoretic Considerations in Batch Reinforcement Learningcited by 285
  7. 2021Bellman-consistent Pessimism for Offline Reinforcement Learningcited by 267
  8. 2019Reinforcement Learning in Feature Space: Matrix Bandit, Kernels, and Regret Boundcited by 199
  9. 2020Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processescited by 199
  10. 2020What are the Statistical Limits of Offline RL with Linear Function Approximation?cited by 135
  11. 2021Robust Reinforcement Learning on State Observations with Learned Optimal Adversarycited by 133
  12. 2021Provably Efficient Reinforcement Learning with Linear Function Approximation Under Adaptivity Constraintscited by 124
34 more
  1. 2018Generalization and Regularization in DQNcited by 117
  2. 2019Sample Complexity of Reinforcement Learning using Linearly Combined Model Ensemblescited by 100
  3. 2019Frequentist Regret Bounds for Randomized Least-Squares Value Iterationcited by 100
  4. 2022Robust Reinforcement Learning using Offline Datacited by 95
  5. 2020Off-Dynamics Reinforcement Learning: Training for Transfer with Domain Classifierscited by 93
  6. 2020On Reward-Free Reinforcement Learning with Linear Function Approximationcited by 89
  7. 2022Distributionally Robust Model-Based Offline Reinforcement Learning with Near-Optimal Sample Complexitycited by 85
  8. 2021Sample Complexity of Robust Reinforcement Learning with a Generative Modelcited by 82
  9. 2020Logarithmic Regret for Reinforcement Learning with Linear Function Approximationcited by 79
  10. 2019Provably Efficient Q-Learning with Low Switching Costcited by 77
  11. 2022Nearly Minimax Optimal Reinforcement Learning for Linear Markov Decision Processescited by 57
  12. 2022Computationally Efficient Horizon-Free Reinforcement Learning for Linear Mixture MDPscited by 52
  13. 2023Double Pessimism is Provably Efficient for Distributionally Robust Offline Reinforcement Learning: Generic Algorithm and Robust Partial Coveragecited by 51
  14. 2023The Curious Price of Distributional Robustness in Reinforcement Learning with a Generative Modelcited by 50
  15. 2021Randomized Exploration for Reinforcement Learning with General Value Function Approximationcited by 49
  16. 2022Reward-Free RL is No Harder Than Reward-Aware RL in Linear Markov Decision Processescited by 49
  17. 2021Improved Variance-Aware Confidence Sets for Linear Bandits and Linear Mixture MDPcited by 45
  18. 2021Improved Regret Analysis for Variance-Adaptive Linear Bandits and Horizon-Free Linear Mixture MDPscited by 44
  19. 2023Improved Sample Complexity Bounds for Distributionally Robust Reinforcement Learningcited by 44
  20. 2023Variance-Dependent Regret Bounds for Linear Bandits and Reinforcement Learning: Adaptivity and Computational Efficiencycited by 39
  21. 2015Distributionally Robust Counterpart in Markov Decision Processescited by 32
  22. 2022Distributionally Robust Offline Reinforcement Learning with Linear Function Approximationcited by 31
  23. 2022Nearly Minimax Optimal Reinforcement Learning with Linear Function Approximationcited by 30
  24. 2023Provable and Practical: Efficient Exploration in Reinforcement Learning via Langevin Monte Carlocited by 29
  25. 2021SimGAN: Hybrid Simulator Identification for Domain Adaptation via Adversarial Reinforcement Learningcited by 27
  26. 2024Distributionally Robust Off-Dynamics Reinforcement Learning: Provable Efficiency with Linear Function Approximationcited by 25
  27. 2024Distributionally Robust Reinforcement Learning with Interactive Data Collection: Fundamental Hardness and Near-Optimal Algorithmscited by 24
  28. 2022Online Policy Optimization for Robust MDPcited by 19
  29. 2024Minimax Optimal and Computationally Efficient Algorithms for Distributionally Robust Offline Reinforcement Learningcited by 17
  30. 2024Randomized Exploration in Cooperative Multi-Agent Reinforcement Learningcited by 17
  31. 2023Soft Robust MDPs and Risk-Sensitive MDPs: Equivalence, Policy Gradient, and Sample Complexitycited by 16
  32. 2024Sample Complexity of Offline Distributionally Robust Linear Markov Decision Processescited by 12
  33. 2023Wasserstein Distributionally Robust Policy Evaluation and Learning for Contextual Banditscited by 9
  34. 2024Model-Free Robust φ-Divergence Reinforcement Learning Using Both Offline and Online Datacited by 2

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 1; 2025: 11; 2026: 3.

15 papers.

Sort:

By area:

  1. 2025A Survey of Sim-to-Real Methods in RL: Progress, Prospects and Challenges with Foundation Modelscited by 36
  2. 2025Inverse Reinforcement Learning with Dynamic Reward Scaling for LLM Alignmentcited by 20
  3. 2024Robust Offline Reinforcement Learning with Linearly Structured f-Divergence Regularizationcited by 8
  4. 2025MOBODY: Model Based Off-Dynamics Offline Reinforcement Learningcited by 8
  5. 2025Linear Mixture Distributionally Robust Markov Decision Processescited by 5
  6. 2025ORVIT: Near-Optimal Online Distributionally Robust Reinforcement Learningcited by 5
  7. 2025Multi-Objective Reinforcement Learning with Max-Min Criterion: A Game-Theoretic Approachcited by 5
  8. 2025Rectified Robust Policy Optimization for Model-Uncertain Constrained Reinforcement Learning without Strong Dualitycited by 4
  9. 2025A Reward-driven Automated Webshell Malicious-code Generator for Red-teamingcited by 1
  10. 2025Distributionally Robust Online Markov Game with Linear Function Approximationcited by 1
  11. 2025Online Robust Reinforcement Learning with General Function Approximationcited by 1
  12. 2026Localized Dynamics-Aware Domain Adaption for Off-Dynamics Offline Reinforcement Learningcited by 1
3 more
  1. 2025VisuoAlign: Safety Alignment of LVLMs with Multimodal Tree Searchcited by 0
  2. 2026Cross-Domain Energy-Guided Diffusion Generation for Off-Dynamics Reinforcement Learningcited by 0
  3. 2026Transferable Reinforcement Learning via Probabilistic Latent Embeddings and Dynamic Policy Adaptation for Sim-to-Real Deploymentcited by 0