Research map / Reinforcement learning / MDPs and planning

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

ICML 2025 · Reinforcement learning › MDPs and planning · approach: Function approximation in RL theory · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Studies online learning of tabular robust MDPs (constrained and regularized, with TV, KL, chi-square uncertainty) and proposes Online Robust Bellman Iteration with regret bounds governed by a supremal visitation ratio.

Problem

Online exploration in robust MDPs for off-dynamics RL, where the agent only interacts with the nominal (training) environment and must perform well under f-divergence-bounded transition shifts; existing online results only cover TV uncertainty with fail-state or vanishing-value assumptions.

Approach

Introduces the supremal visitation ratio (sup over policies, steps, states of worst-case visitation over nominal visitation) as the exploration-hardness measure, and an optimistic robust value-iteration algorithm (ORBI) with closed-form dual updates for TV, KL and chi-square constrained and regularized robust MDPs, giving sublinear regret without fail-state assumptions.

Key results

• TV-constrained regret upper bound Õ(V S^2 A H^2 + V^{1/2} S^{3/2} A^{1/2} H^2 sqrt(K)), with a matching Ω(V^{1/2} sqrt(K)) lower bound in V and K.
• Hard instances with unbounded supremal visitation ratio (V=2^{2A}) give regret Ω(2^A sqrt(K)), so online CRMDP learning can be exponentially hard.
• In the simulated RMDP experiment, robust policies outperform the non-robust algorithm once the perturbation exceeds 0.6.

Measured effects reported in the paper

Surprising findings

• The authors report that a prior online CRMDP paper contains flaws in key lemmas that invalidate its results.
• The TV dual formulation in a prior paper was off by a factor of 1/2 because it was taken from an L1-distance result.

Limitations

• Requires the supremal visitation ratio to be polynomial in H, S, A for the sublinear guarantees; unbounded ratio yields exponential hardness.
• Results are for tabular finite state and action spaces only.
• Lower-bound-matching claims are for the dependence on V and K; the analysis is restricted to (s,a)-rectangular f-divergence uncertainty sets.

Experimental setup

Datasets: Simulated tabular RMDP toy environments Frozen Lake (OpenAI Gym default map)

Benchmarks: Frozen Lake (OpenAI Gym) Simulated tabular RMDP toy environments

Metrics: regret average reward of learned policy sub-optimality gap training time

Baselines: Non-robust algorithm (same optimistic value iteration without robustness) CRMDP-TV online method (Liu et al.)

Builds on: Robust Bellman optimality equations Optimism in the face of uncertainty Regularized robust MDPs

Closest papers by meaning

• Offline-Online Reinforcement Learning for Linear Mixture MDPs (NeurIPS 2026 · similarity 0.91)
• Minimax Optimal and Computationally Efficient Algorithms for Distributionally Robust Offline Reinforcement Learning (NeurIPS 2024 · similarity 0.91)
• Distributionally Robust Reinforcement Learning with Interactive Data Collection: Fundamental Hardness and Near-Optimal Algorithms (NeurIPS 2024 · similarity 0.90)
• Selective Uncertainty Propagation in Offline RL (AAAI 2025 · similarity 0.90)
• Information-Directed Offline-to-Online Reinforcement Learning (NeurIPS 2026 · similarity 0.90)
• A Unified Principle of Pessimism for Offline Reinforcement Learning under Model Mismatch (NeurIPS 2024 · similarity 0.90)