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

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

## Key facts

- Cited by 16 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 46 of its 61 references that are in the map.
- First posted on arXiv 30 Sep 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 46)

- [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)
- [Sim-to-Real Transfer in Deep Reinforcement Learning for Robotics: a Survey](https://mlsanity.com/paper/2009.13303/) (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)
- [Reinforcement Learning in Feature Space: Matrix Bandit, Kernels, and Regret Bound](https://mlsanity.com/paper/1905.10389/) (2019)
- [Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processes](https://mlsanity.com/paper/2012.08507/) (2020)
- [What are the Statistical Limits of Offline RL with Linear Function Approximation?](https://mlsanity.com/paper/2010.11895/) (2020)
- [Robust Reinforcement Learning on State Observations with Learned Optimal Adversary](https://mlsanity.com/paper/2101.08452/) (2021)
- [Provably Efficient Reinforcement Learning with Linear Function Approximation Under Adaptivity Constraints](https://mlsanity.com/paper/2101.02195/) (2021)
- [Generalization and Regularization in DQN](https://mlsanity.com/paper/1810.00123/) (2018)
- [Frequentist Regret Bounds for Randomized Least-Squares Value Iteration](https://mlsanity.com/paper/1911.00567/) (2019)
- [Sample Complexity of Reinforcement Learning using Linearly Combined Model Ensembles](https://mlsanity.com/paper/1910.10597/) (2019)
- [Off-Dynamics Reinforcement Learning: Training for Transfer with Domain Classifiers](https://mlsanity.com/paper/2006.13916/) (2020)
- [Robust Reinforcement Learning using Offline Data](https://mlsanity.com/paper/2208.05129/) (2022)
- [On Reward-Free Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/2006.11274/) (2020)
- [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)
- [Logarithmic Regret for Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/2011.11566/) (2020)
- [Provably Efficient Q-Learning with Low Switching Cost](https://mlsanity.com/paper/1905.12849/) (2019)
- [Nearly Minimax Optimal Reinforcement Learning for Linear Markov Decision Processes](https://mlsanity.com/paper/2212.06132/) (2022)
- [Computationally Efficient Horizon-Free Reinforcement Learning for Linear Mixture MDPs](https://mlsanity.com/paper/2205.11507/) (2022)
- [The Curious Price of Distributional Robustness in Reinforcement Learning with a Generative Model](https://mlsanity.com/paper/2305.16589/) (2023)
- [Double Pessimism is Provably Efficient for Distributionally Robust Offline Reinforcement Learning: Generic Algorithm and Robust Partial Coverage](https://mlsanity.com/paper/2305.09659/) (2023)
- [Randomized Exploration for Reinforcement Learning with General Value Function Approximation](https://mlsanity.com/paper/2106.07841/) (2021)
- [Reward-Free RL is No Harder Than Reward-Aware RL in Linear Markov Decision Processes](https://mlsanity.com/paper/2201.11206/) (2022)
- [Improved Variance-Aware Confidence Sets for Linear Bandits and Linear Mixture MDP](https://mlsanity.com/paper/2101.12745/) (2021)
- [Improved Regret Analysis for Variance-Adaptive Linear Bandits and Horizon-Free Linear Mixture MDPs](https://mlsanity.com/paper/2111.03289/) (2021)

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

- [A Survey of Sim-to-Real Methods in RL: Progress, Prospects and Challenges with Foundation Models](https://mlsanity.com/paper/2502.13187/) (2025)
- [Inverse Reinforcement Learning with Dynamic Reward Scaling for LLM Alignment](https://mlsanity.com/paper/2503.18991/) (2025)
- [MOBODY: Model Based Off-Dynamics Offline Reinforcement Learning](https://mlsanity.com/paper/2506.08460/) (2025)
- [Robust Offline Reinforcement Learning with Linearly Structured f-Divergence Regularization](https://mlsanity.com/paper/2411.18612/) (2024)
- [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)
- [Multi-Objective Reinforcement Learning with Max-Min Criterion: A Game-Theoretic Approach](https://mlsanity.com/paper/2510.20235/) (2025)
- [Rectified Robust Policy Optimization for Model-Uncertain Constrained Reinforcement Learning without Strong Duality](https://mlsanity.com/paper/2508.17448/) (2025)
- [Online Robust Reinforcement Learning with General Function Approximation](https://mlsanity.com/paper/2512.18957/) (2025)
- [A Reward-driven Automated Webshell Malicious-code Generator for Red-teaming](https://mlsanity.com/paper/2505.24252/) (2025)
- [Distributionally Robust Online Markov Game with Linear Function Approximation](https://mlsanity.com/paper/2511.07831/) (2025)
- [Localized Dynamics-Aware Domain Adaption for Off-Dynamics Offline Reinforcement Learning](https://mlsanity.com/paper/2602.21072/) (2026)
- [VisuoAlign: Safety Alignment of LVLMs with Multimodal Tree Search](https://mlsanity.com/paper/2510.15948/) (2025)
- [Cross-Domain Energy-Guided Diffusion Generation for Off-Dynamics Reinforcement Learning](https://mlsanity.com/paper/2605.24810/) (2026)
- [Transferable Reinforcement Learning via Probabilistic Latent Embeddings and Dynamic Policy Adaptation for Sim-to-Real Deployment](https://mlsanity.com/paper/2605.27659/) (2026)
- [Interactive Distributionally Robust Multi-Agent Learning with General Function Approximation](https://mlsanity.com/paper/2609.32048/) (2026)

## 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).