# Sample Complexity of Distributionally Robust Off-Dynamics Reinforcement Learning with Online Interaction

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

## Key facts

- Cited by 7 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.
- First posted on arXiv 7 Nov 2025.

## Placed in

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

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

- [Dual-Robust Cross-Domain Offline Reinforcement Learning Against Dynamics Shifts](https://mlsanity.com/paper/2512.02486/) (2025)
- [Online Robust Reinforcement Learning with General Function Approximation](https://mlsanity.com/paper/2512.18957/) (2025)
- [Perturbation-mitigated USV Navigation with Distributionally Robust Reinforcement Learning](https://mlsanity.com/paper/2512.00030/) (2025)
- [Localized Dynamics-Aware Domain Adaption for Off-Dynamics Offline Reinforcement Learning](https://mlsanity.com/paper/2602.21072/) (2026)
- [Cross-Domain Energy-Guided Diffusion Generation for Off-Dynamics Reinforcement Learning](https://mlsanity.com/paper/2605.24810/) (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)

## Abstract (arXiv)

Off-dynamics reinforcement learning (RL), where training and deployment transition dynamics are different, can be formulated as learning in a robust Markov decision process (RMDP) where uncertainties in transition dynamics are imposed. Existing literature mostly assumes access to generative models allowing arbitrary state-action queries or pre-collected datasets with a good state coverage of the deployment environment, bypassing the challenge of exploration. In this work, we study a more realistic and challenging setting where the agent is limited to online interaction with the training environment. To capture the intrinsic difficulty of exploration in online RMDPs, we introduce the supremal visitation ratio, a novel quantity that measures the mismatch between the training dynamics and the deployment dynamics. We show that if this ratio is unbounded, online learning becomes exponentially hard. We propose the first computationally efficient algorithm that achieves sublinear regret in online RMDPs with f-divergence based transition uncertainties. We also establish matching regret lower bounds, demonstrating that our algorithm achieves optimal dependence on both the supremal visitation ratio and the number of interaction episodes. Finally, we validate our theoretical results through comprehensive numerical experiments.