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

AI summary

Overview

Research area: Reinforcement learning theory, specifically robust/distributionally robust Markov decision processes (RMDPs) and off-dynamics RL.

Technical level: Advanced. The paper uses measure-theoretic probability, f-divergences, dual formulations of robust Bellman equations, and regret lower-bound constructions.

Scope: The paper establishes the first sample-complexity and regret guarantees for online learning in tabular RMDPs with general f-divergence uncertainty sets, using a new quantity called the supremal visitation ratio to characterize when efficient online learning is possible.

What This Paper Is About

In off-dynamics reinforcement learning, an agent trains in one environment but is deployed in another whose transition dynamics differ. This is modeled as a robust MDP (RMDP), where the agent optimizes against worst-case dynamics within an uncertainty set. Prior work either assumed access to a simulator or a pre-collected dataset with good state coverage, effectively sidestepping the exploration problem. This paper tackles the harder setting where the agent only has online interaction with the nominal (training) environment and must figure out what conditions make efficient learning even possible.

Key Contributions

1. A new difficulty measure for online RMDPs. The authors introduce the supremal visitation ratio C_vr, the worst-case ratio between the state-visitation distribution under the nominal dynamics and under the adversary-chosen worst-case dynamics. This quantity precisely captures the "information deficit" caused by distribution shift.

2. The first efficient algorithm for general f-divergence RMDPs. They propose ORBIT (Online Robust Bellman Iteration), which handles both constrained robust MDPs (CRMDPs) and regularized robust MDPs (RRMDPs) with TV, KL, and χ² divergences—far broader than the TV-only, fail-state-requiring prior work.

3. Matching upper and lower bounds on regret. The regret bounds scale polynomially in C_vr, S, A, H, and sqrt(K), and they prove matching lower bounds showing C_vr is unavoidable. If C_vr is unbounded, they construct hard instances where online learning becomes exponentially hard.

4. Bridging assumptions from prior work. They show that the widely used "fail-states" and "vanishing minimal value" assumptions are special cases that essentially force the adversary to shift in a predictable direction, thereby eliminating the information deficit—explaining why those papers only worked for TV-divergence CRMDPs.

Main Findings

• Exploration difficulty is measurable by C_vr. When C_vr is polynomial in H, S, A, efficient online learning is possible; when unbounded, the sample complexity can blow up exponentially.

• ORBIT achieves sublinear regret for CRMDP-TV, CRMDP-KL, CRMDP-χ², RRMDP-TV, RRMDP-KL, and RRMDP-χ², with explicit dependence on C_vr in every bound.

• Fail-state assumptions are unnecessary but not equivalent. Proposition 5.4 shows that fail-states force the worst-case transition to be elementwise dominated by the nominal transition toward reachable states, making C_vr effectively trivial. General divergences break this property, motivating C_vr.

• KL-divergence requires an extra regularity condition. Assumption 5.7 (a minimum-probability bound C_MP on positive-probability transitions) is needed to make the KL dual well-behaved, echoing similar conditions in prior KL-RMDP work.

• Reduction to standard MDPs. In the non-robust case, C_vr = 1, so the results recover standard MDP regret bounds as a special case.

• Empirical validation. Synthetic MDP experiments show performance degrades as C_vr increases; the Frozen Lake experiments show ORBIT still performs well under significant distribution shift.

Methodology in Plain English

The algorithm alternates between two steps across K episodes:

1. Planning step. For each state-action pair, ORBIT solves a robust version of the Bellman equation using the empirical transition kernel collected so far. Because the robust Bellman operator involves an inner minimization over the uncertainty set (or a regularization penalty), the authors use strong duality to rewrite it as a tractable one-dimensional optimization over a dual variable (η, ν, or λ, depending on the divergence). This is why the algorithm is computationally efficient.

2. Exploration and update step. The algorithm follows an optimistic upper-confidence-bound style: it adds a bonus term to the Q-function estimate that shrinks as more samples accumulate for each (s, a) pair. The bonus sizes are derived separately for each divergence. The greedy policy is executed, a new trajectory is collected, and the empirical reward and transition estimates are refreshed.

The theoretical analysis then:

• Defines C_vr and shows how the mismatch between nominal and worst-case visitation measures enters the regret decomposition.
• Proves optimism (the estimated Q-function upper-bounds the true robust Q under high probability) for each divergence, which requires careful dual analysis.
• Proves matching lower bounds via hard-instance constructions.

Why This Matters

Impact on research: This paper answers a question explicitly left open in prior online RMDP work (Lu et al., 2024): under what conditions is provably efficient online robust RL possible for general f-divergences? It provides an information-theoretic answer (bounded C_vr) and shows the previously used fail-state assumptions were hiding this deeper condition. It also corrects an identified flaw in Dong et al. (2024).

Real-world applications:

• Sim-to-real robotics. Policies trained in simulation must survive real-world physics shifts; C_vr quantifies how much sim exploration matters for robust deployment.
• Healthcare treatment policies. Training data comes from one patient population; deployment on a shifted population requires robustness to different disease-progression dynamics.
• Autonomous driving. Simulated driving environments differ from real road conditions; the framework captures how exploration in the simulator translates to safety in deployment.
• Recommendation and finance. Historical user behavior or market dynamics shift; robust policies must hedge against distributional drift without full offline coverage.

Industry relevance: Any ML team training policies on a simulator or historical log and deploying under distribution shift gains a principled diagnostic (is C_vr small enough?) and an algorithm (ORBIT) with computable regret guarantees. This is directly useful for teams that cannot afford infinite simulator queries or extensive coverage.

Future Directions

• Estimating C_vr in practice. The bound is stated as an assumption; deriving sample-based estimators or verifiable sufficient conditions for C_vr would make the theory actionable.
• Function approximation. The paper is tabular; extending ORBIT and the C_vr framework to linear or neural function approximation is a natural and important next step.
• Infinite-horizon and average-reward settings. Only finite-horizon is analyzed; the discounted and average-reward regimes raise new challenges for visitation-ratio analysis.
• Tighter bounds and divergences. Only TV, KL, and χ² are instantiated; other f-divergences (Hellinger, reverse KL) may yield different C_vr dependence, and looser bonus terms could potentially be tightened.

Target Audience

Theoretical reinforcement learning researchers, especially those working on robust MDPs, distributionally robust optimization, and sample-complexity/regret analysis. Also relevant to applied researchers in sim-to-real transfer and safety-critical decision-making who want a rigorous foundation for why online robust RL is hard and when it becomes tractable. Readers should be comfortable with MDP formalism, Bellman equations, concentration inequalities, and basic f-divergence theory.

Authors’ abstract

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.