Sample Complexity of Distributionally Robust Off-Dynamics Reinforcement Learning with Online Interaction
Authors: Yiting He
Zhishuai Liu
Weixin Wang
Pan Xu
Venue: ICML 2025 poster (2025)
Keywords: online learning
distributionally robust Markov decision process
distribution shift
Primary area: reinforcement_learning->online
TL;DR: Online learning of the distributionally robust Markov decision process

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.

Sample Complexity of Distributionally Robust Off-Dynamics Reinforcement Learning with Online Interaction
Yiting He
Zhishuai Liu 1
Weixin Wang'
Pan Xu
Abstract
the deployment environment differs from that of the training environment. Such problems can be modeled as learning a robust Markov decision process (RMDP) (Satia & Lave Jr, 1973; Iyengar, 2005; Nilim & El Ghaoui, 2005), where the objective is to learn policy that performs well when un- certainties are imposed into the transition dynamics. Two major frameworks have been proposed in the literature in- corporate the uncertainty of transition dynamics in RMDPs. The first, known the Constrained Robust Markov Deci- sion Process (CRMDP), formulates a max-min optimization problem that seeks the best policy under the worst-case tran- sition dynamics within a predefined uncertainty set. The second. the Regularized Robust Markov Decision Process (RRMDP), replaces the hard constraint on uncertainty sets with regularization term that quantifies the divergence between the training and deployment dynamics.
Off-dynamics reinforcement learning (RL., where training and deployment transition dynamics are different, can be formulated as learning in robust Markov decision process (RMDP) where uncer- tainties in transition dynamics are imposed. Exist- ing 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 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 pro- pose 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 opti- mal dependence both the supremal visitation ratio and the number of interaction episodes. Fi- nally, we validate our theoretical results through comprehensive numerical experiments.
CRMDP was initially introduced for optimal control prob- lems (Nilim & El Ghaoui, 2005; Iyengar, 2005; Xu & Man- nor, 2006; Wiesemann et al., 2013), where the transition dynamics and reward functions of the nominal MDP are assumed to be fully known. More recently, CRMDPs have been studied from learning perspective (Zhou et al., 2021; Yang et al., 2022), where an agent must gather data to esti- mate the environment rather than relying on perfect knowl- edge. Existing research on learning CRMDPs can be cate- gorized into three settings: (1) Learning with a generative model (simulator). In this setting, the agent can query tran- sitions at any state-action pair arbitrary number of times (Panaganti & Kalathil, 2022; Yang et al., 2022: Xu et al., 2023b; Shi et al., 2024). (2) Learning with an offline dataset. Here, the agent learns from a pre-collected dataset, typi- cally assumed to be generated by a behavior policy from the nominal MDP (Panaganti et al., 2022; Blanchet et al.,
1. Introduction
2023; Shi & Chi, 2024: Liu Xu, 2024b; Tang et al., 2024). Effective robust policy learning relies sufficient coverage of the dataset states in the deployment environment. (3) Leurning through online interuction. More recent works have considered online learning of CRMDPs through direct interaction with the training environment to collect data (Liu & Xu, 2024a; Lu et al., 2024; Liu et al., 2024), focusing on specific case where the uncertainty is defined via total
Off-dynamics reinforcement learning (RL) (Eysenbach al., 2021; Lyu et al., 2024) has recently gained signif- icant attention in scenarios where the transition dynamics of
Equul contribution Duuee University. Correspondence to: Pan Xu <pan.xu@ duke.
Proceedings of the 42nd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Sample Complexity of Distributionally Robust Off- Oft-Dynamies Reinforeement Learning with Online Interaction
variation (TV) distance!.
such nice properties do not hold in RMDPs with general f- divergence based uncertainty sets or regularization, limiting all existing research on online RMDPs to CRMDPs with TV-distance based uncertainty sets.
RRMDP was introduced to get rid of the constrained opti- mization in the formulation of CRMDPs for the tractability of robust policy learning (Yang et al., 2023; Zhang et al., 2024). In particular, Yang et al. (2023) studied RRMDPs with general /-divergence-basee regularization under gen- erative model setting, while Zhang et al. (2024) analyzed RRMDPs with Kullback-Leibler divergence-basee regular- ization in the offline setting, relying similar data cov- erage assumptions as in offlin CRMDPs. More recently. Panaganti et al. (2024) extended this work to general f- divergence- based regularization in the offline setting and
In this work, we answer the following fundamental question:
Under what conditions can provably efficient online learning of RMDPs be achieved?
We investigate tabular RMDPs with finite states and actions. We show that if the nominal environment is sufficiently ex- ploratory-i.e., the agent can collect enough information through interaction-thhe sample-efficient online learning should be achievable for broader classes of RMDPs, includ- ing those with general f-divergence based dynamics uncer- tainties and without restrictive structural assumptions like fail-states. We rigorously prove that the sample complexity of any online learning algorithm should be proportional to the difficulty of exploration.
explored RRMDPs with total variation regularization and fail-states in a hybrid online-offliee setting.
Despite these advances, in more realistic applications where simulators or pre-collected datasets with strong state cov- erage are not available, the problem of efficient online ex- ploration in RMDPss remains understudied. Unlike standard MDPs, where exploration aims to reduce uncertainty within fixed transition model, in RMDPs, the agent can only gather experience from a nominal environment, yet it must generalize to potentially shifted dynamics at deployment. This presents fundamental challenge of information deficit in online RMDPs, requiring the development of exploration strategies that proactively account for distributional shifts. More specifically, the information deficit in online RMDPs arises when states that are rarely visited in the nominal en- vironment become critical in the deployment environment. For instance, consider state in the nominal MDP that is extremely difficult to visit, e.g., with exponentially small visitation probability, resulting in limited data collection. If, in the deployment environment, the dynamics shift in- creases the visitation probability of s, the agent must make informed decisions at this state despite having little prior ex- perience. In standard MDPs, such rare states typically have negligible effects on policy learning, but in RMDPs, they can critically impact performance, making online learning in RMDPs significantly more challenging than in standard MDPs.
Our contributions are summarized as follows.
We introduce the supremal visitation ratio Cor (see As- sumption 5.5) as measure of exploration difficulty in RMDPs. We develop the first computationally efficient algorithm, Online Robust Bellman Iteration (ORBIT), for CRMDPs and RRMDPs based on the total variation (TV), Kullback-Leibler (KL), and x² divergences, and prove sample complexity bounds that explicitly depend on Cur- We establish regret lower bounds, demonstrating that the supremal visitation ratio Cur is an unavoidable term in the sample complexity of online RMDP learning. This result confirms that Cur serves as a fundamental measure of exploration difficulty and a sufficient condition for prov- ably efficient online learning in RMDPs. As a corollary, construct hard instances to demonstrate that if Cvr is unbounded, general online learning in CRMDPs can become exponentially difficult.
We conduct comprehensive numerical experiments to val- idate our theoretical findings. In a simulated MDP, we show that the performance of learned policies degrades as Cur increases. We evaluate our algorithms in a simulated RMDP and the Frozen Lake environment, highlighting their effectiveness when distribution shifts are significant.
To overcome this information deficit issue, existing research on online RMDPs adopt a fail-state type of assumption- there exist states with zero reward that only transit among themselves (Liu& & Xu, 2024a; Lu et al., 2024; Liu et al., 2024). As we show in Proposition 5.4 and the discus- sion following it, these assumptions essentially ensure that worst-case distribution shifts occur in a deterministic direc- tion, which climinating the information deficit issue and makes provably efficient online learning possible. However,
Notations For any positive integer / E E4, we denote [H] = (1, H). For any set S, define A(S) the set of probability distributions over S. Let P, E A(S) and
P < Q. For convex function f +00) + (-20, +o] such that f(x) is finite for all x > 0, f(1) = 0 and f(0) = lim,-so+ f()). The f-divergence of P from Q. which measures their difference, is defined as (P(()) =
We note that Dong et al. (2024) also studied online CRMDPs, hut we found essential flaws in proofs of their Lemmas A.2 and C.5, which invalidates their results.
2

---

Sample Complexity of Distributionally Robust Off- Off-Dynamics Reinforeement Learning with Online Interaction
(( [q dQ. In our paper, we consider three common f-divergences including total variation (TV) distance with f(t) = / 11, Kullback-Leibler (KL) divergence with f(t) = t in t, and x²-divergence with ft) = (t - (t= We use (O-) to hide absolute constant factors and O() to fur- ther hide logarithmic factors. For any two integers a and b, we denote a V b == max(a, b}.
sets, respectively. Their algorithmic design and theoretical analysis rely on assuming access to exploratory policies, which implicitly assumes that the nominal MDP is suffi- ciently exploratory. In contrast, we revisit this challenge from a different angle, focusing on the information deficit issue induced by distributional shift. Our work differs from theirs in two key aspects. First, we introduce a novel quan- tity to characterize the hardness of exploration in the nom- inal MDP and analyze it thoroughly via both upper and lower bounds on the sample complexity. Second, instead of assuming access to exploratory policies, we design al- gorithms that explicitly incorporate exploration strategies tailored for with (s, d)-rectangular uncertainty sets defined by general f-divergences.
2. Related Work
CRMDPs and RRMDPs The framework of CRMDPs was first introduced in the context of optimal control (Iyengar, 2005; Nilim & EI Ghaoui, 2005; Xu & Mannor, 2006; Wiesemann et al., 2013; Mannor et al., 2016), where the nominal MDP is assumed to be exactly known, and robust policies are obtained by solving a constrained max-min opti- mization problem. Subsequent works extended CRMDPs to the learning setting with access to generative model (Zhou et al., 2021: Yang et al., 2022; Panaganti & Kalathil, 2022; Shi et al., 2024). More recently, CRMDPs have been studied in the offline learning setting, where only pre-collected dataset from the nominal MDP is available through a behav- ior policy (Shi& & Chi, 2024; Panaganti et al., 2022; Blanchet et al., 2023; Wang et al., 2024a; Liu & Xu, 2024b; 2025). To ensure that robust policy can be learned from a reasonably sized offline dataset, these works make assumptions about the behavior policy (and implicitly, the nominal MDP) to guarantee sufficient coverage. Such assumptions include the robust single-policy clipped concentrability (Shi & Chi, 2024), robust partial coverage (Blanchet et al., 2023), and uniformly well coverage assumptions (Liu & Xu, 2024b; Wang et al., 2024a). The framework of RRMDPs was more recently proposed by Yang al. (2023) and Zhang al. (2024), who studied it under the generative model setting and the offline setting, respectively. This line of work was extended to function approximation settings by Panaganti et al. (2024) and Tang et al. (2024), considering both hybrid offline-online and purely offline scenarios.
tabular CRMDPs and RRMDPs
Liu & Xu (2024a); Lu et al. (2024); Liu et al. (2024) fo- cused on online robust RL under the specific setting of CRMDPs with uncertainty sets defined by the TV-distance, coupled with assumptions such as the existence of ftil-states or vanishing minimal values. From an information theoorttic perspective, we show that these assumptions effectively circumvent the information deficit by constraining the di- rection of the distribution shift. In contrast, our work seeks to identify a more general sufficient condition for provably efficient online learning in CRMDPs- one that applies to arbitrary divergence- based uncertainty sets and does not rely on the fail-state or vanishing minimal value assumption.
RL A substantial body of empirical work addresses off-dynamics RL through the lens of domain adap- tation and transfer learning (Eysenbach et al., 2021; Desai et al., 2020; Zhang et al., 2021; Xu et al., 2023a; Wen et al., 2024; Guo et al., 2024; Wang et al., 2024b; Lyu et al., 2024; Da et al., 2025), among others. In this paper, we focus on the robust MDP (RMDP) formulation of off-dynamics RL. We refer readers to the above works for complementary approaches along this orthogonal line of research.
3. Preliminaries
It is worth noting that CRMDPs are sometimes referred to in the literature as Robust MDPs (RMDPs) or Distribution- ally Robust MDPs (DRMDPs). To distinguish them from the regularized robust framework, we adopt the term CR- MDPs Similarly, RRMDPs appear under various names, including penalized robust MDPs (Yang et al., 2023), soft robust MDPs (Zhang et al., 2024), and robust o-regularized MDPs (Panaganti al., 2024). We use the term RRMDPs to clearly differentiate them from CRMDPs while remaining consistent with the literature.
Constrained Robust MDP (CRMDP) We denote fi- nite horizon CRMDP CRMDP (S. A, P r, H), where S is the state space. A is the action space, iod {PR) H is the nominal transition kernel, r S x A + 1] is the reward function, Up is the un- certainty set centered around the nominal kernel, p is the uncertainty level, H is the horizon length. In this rertanty work, we specifically focus on general f-divergence de- fined (s, -rectaggull uncertainty sets (lyengar, 2005), a), where (f,
(P(P)) = Mis. (P (PIP) I p). The robust value
Online RMDPs Wang & Zou (2021): Badrinath & Kalathil (2021) studied the online learning for infinite-horizon RMDPs with R-contamination and more general uncertainty
3

---

Sample Complexity of Distributionally Robust Off- Off-Dynamics Reinforeement Learning with Online Interaction
function and Q-function are defined as
regret after K episodes, defined as
K Σ
(s)= =
inf (Pu)(po)
Pr,
Σ rx (st.
=
Regret (K)
[V
(sF) for CRMDPs,
k=
H Σ 1-/h
(s. = inf Ex (PU)(Po)
(se, ac)
8h =, an a
Regret(K))
Σ
[V (sf) V1" (s1) for RRMDPs.
k=1
The optimal robust value function and optimal robust Q-function are defined as: (s) supxen (s). (s, a) = supzen 27 a), where IT the set of all policies. Correspondingly, the optimal robust policy is the policy that achieves the optimal robust value function oे argsup=en V/, (s). For CRMDPs, Iyengar (2005) proved the robust Bellman optimality equations
4. Online Robust Bellman Iteration (ORBIT)
In this section, we first present a meta-algorithm for online tabular RMDPs with general f-divergence defined uncer- tainty sets or regularization terms, We then instantiate the algorithm for CRMDPs with TV, KI. and x² diverggges defined uncertainty sets and RRMDPs with TV, KL and (3.1)
(s. = an) +
inf Er, (s,a) (PO))
x" divveeereenees defined regularization terms, respectively.
(s) = max 17 as,, "EA
A Algorithm 1 Online Robust Bellman Iteration (ORBIT)
where Ep, (s, E. Eacpaa [Vrif(
Require: uncertainty level p > 0 (for CRMDPss,, or regu- larizer / > 0 (for RRMDPs).
1: for k = 1, ... K do
Regularized Robust MDP (RRMDP) A finite horizon
RRMDP can be denoted as RRMDP(S, A, po,r, 3,3 R, H), where 3 is the regularizer parameter, R is a penalty on distri- bution shift, and we set R to be the probability divergence D throughout this paper. RRMDPs replace the uncertainty set constraint CRMDPs with regularization term. Specif- ically, the robust value function and Q Q-fuctiion under the regularized setting are defined as
r,
2:
Vi HH+1 (-) 5 0.
3:
for = H,.... do
4:
for V (s.a)
5:
Update Q-function estimation 2% (s, a)
CRMDP: refer to Section 4.2;
RRMDP: refer to Section 4.3.
end for for V do
H
V. (s) = inf E.... PEA(S)
Σ as)
8:
(s()) + argmax, E.A (s.
(s)( + m (s,
+ 8- ((Pr(-)se, PT =
end for
10: end for
H
(s,a) inf PEA(S)
Er,
Σ as)
11: Collect trajectory 7 by executing /².
pk+1 ph+1 according to (4.1). 12: Update ni Ph
t=h
13:
end for
D(Pr(-Ist,, + 8- D(P( st, ac), (-(ssss,
st. 0,
For RRMDPs, Yang al. (2023) showed the robust Bellman optimality equations:
4.1. Algorithm Interpretation
We present our meta-algorithm, Online Robust Bellman It- eration (ORBIT), Algorithm 1. The algorithm follows a value iteration framework and integrates optimistic estima- tion and the robust Bellman optimality equation in (3.1) and (3.2) for estimating the robust Q- Q-functions. In each episode k E [K]. ORBIT consists of two stages. In the first stage (Lines 3 to 10), Algorithm I iteratively updates the value function and Q-function estimations in a backward manner. In the second stage (Lines 11 to 12), we collect trajectory - = =st af r r..... *k &k r. (, by executing ~² After new trajectory collected, ORBIT updates the empirical reward function and transition kernel as follows
(s. = rs(aa) inf
P. [Vri as)
((E)(S)
+ 3. (.. a). ()))s,
(3.2)
Vr (s)) max Q7 (s.
AEA
Learning Goal We have an agent actively interacting with the nominal environment for K episodes to learn the opti- mal robust policy. At the start episode k with initial state sft the agent chooses a policy x² based on the history infor- mation. Then it interacts with the nominal environment by executing x until the end of episode kt and collects new trajectory. The agent's 's goal is minimize the cumulative
(i 11ssh s, af === a).

---

Sample Complexity of Distributionally Robust Off- Off-Dynamies Reinforeement Learning with Online Interaction
Σ ri a) fsh = s = =
(s, (1
2H
21n(2SAHK/0)
(4.6)
xt (8.0)
(4.1)
pCur
ni n (s,
V1
where CмP is defined in Assumption 5.7. The dual formu- lation for KL-divergence and the optimism the estimated Q-function are proved Appendix C.2.
(sh s. a, 8/41 = o4}
Ph 1 as)
(1
Algorithm 1 updates Q-functions at each (s, a) according to different RMDP settings and choices of f-divergences. We differentiate these cases using specific labels: CRMDP-TV, CRMDP-KL, CRMDP-x RRMDP-TV, RRMDP-KL, and RRMDP-x2 2 Finally, Algorithm adopts the greedy policy of the estimated Q-function as the estimated optimal policy at episode
CRMDP-X2 For ORBIT in CRMDPs with diveeregeee defined uncertainty sets, we have
RB (s.
sup AE(O,
(Bj h+1 - (s,0)
para (Viig 21):
(4.7)
25 1921
(s, 0) 3H
+ K'
(4.8)
For the robust Q-function estimation, we leverage the robust optimality Bellman equation (3.1) and (3.2). Incorporating the optimism principle in the face of uncertainty (Abbasi Yadkori al., 2011) 1) in the Q-function update, we have
(s.a)
The dual formulation for diverrgee and the optimism of the estimated Q-function are proved in Appendix C.3.
(x a) = (s, a) + by (s)
(4.2)
4.3. ORBIT under Regularized Robust MDPs
There are two components in (4.2): robust Bellman esti- mator RB (s, a) and bonus term by, (s,a). Next, we will instantiate this meta-algorithm for CRMDPs and RRMDPs with various f-divergences, and provide explicit formulation for robust Bellman estimation and bonus design.
We then focus on RRMDPs and detail the update of robust Q-functions (4.2) in various settings.
RRMDP-TV In RRMDPs with TV-distance regulariza- tion terms, estimators in (4.2) are defined as follows
4.2. ORBIT under Constrained Robust MDPs
RB a) (h a) Epg
[[ min .ES
W+4 (s) +
We first focus on CRMDPs and detail the update of robust Q- functions (4.2) in various settings. To solve the optimization problem in the robust Bellman equation (3.1) and (3.2), we resort to strong duality results in the following.
- -D (s,
(mi DiL (s) B #E8
(4.9)
2S 12
(s, a) = 2H
(4.10)
(ss V1
CRMDP-TV In CRMDPs with TV-distance defined un- certainty sets, estimators in (4.2) are defined as follows
The dual formulation for TV-distance and the optimism of the estimated Q-function are proved in Appendix D.I.
(s, = rl)ssaa) - inf (Ezg [(7 ( (s,
mE(0,1]
RRMDP-KL
For ORBIT in RRMDPs with KL-
+ p((1 1- min V.kup (( -1);
(4.3)
divergence regularization terms, we have
2S In(12SAH2K/00) 1
(s, Fh(ss a) 3 II exp (- B (
(%,s, ((s,a)= 2H,
(4.4)
n (s, V1
K
(4.11)
where (4.3) represents the empirical version of the robust Bellman operator and (4.4) is the bonus. The dual formu- lation for TV-distance and the optimism of the estimated Q-function are established in Appendix C.I.
(s, (1+ 3e 1 /S)
2 21n(25AH//8)
(4.12)
nh (s. v1
The dual formulation for KL-divergence and the optimism of the estimated Q-function are provided in Appendix D.2.
CRMDP-KL In CRMDPs with KL--divergence defined uncertainty sets, estimators in (4.2) are defined as follows
RRMDP-X2 2 For ORBIT in RRMDPs with -iverreee regularization terms, we have
(s, ())
inf hv Epp eep ( -o-pb)))) (s, + up), (4.5)
RB a) = =/)(s. a) + sup xE(o.H]
Tgp [ih- - A] (8)
rejo, #1
5

---

Sample Complexity of Distributionally Robust Off- Off-Dynamics Reinforcement Learning with Online Interaction
48 h+1
Varpa
2/ 2))
(4.13)
as the visitation measure on S induced by the policy under pw.". For convenience, we also write pa,k := pe,"" d := d= and q" :=q"
( 0) = 5H²
25a In 1/
2
(4.14)
(s)
K'
We show that Condition 5.1 implies the following property the CRMDP.
The dual formulation for x2 divergeee and the optimism of the estimated Q-function are provided in Appendix D.3.
Proposition 5.4. For CRMDPs with TV-distance defined uncertainty set satistying Condition 5.1, for any 8 E S, a E
5. Theoretical Results
A, s' E Sy,S, and policy म. we have Ph (s' [s a) S PR (d)
In this section, we provide theoretical understandings on the online learning of RMDPs. We start with new perspective- the information deficit issue-to understand existing condi- tions for provably efficient online learning. Motivated by existing solutions to address the information deficit issue, we propose a new metric, the supremal visitation ratio, to quantify the hardness in exploration under online RMDPs. Further, we provide upper and lower bounds, involving the supremal visitation ratio, on the regret of Algorithm 1 in all settings.
Proposition 5.4 shows that, for any state-action pair, the transition probability to non-fail state is smaller in the worst-case environment than in the nominal environment. Consequently, non-fail states that are rarely visited in the nominal environment remain rarely visited in the worst-case environment, hence it would not incur large regret when making decisions at these states. Meanwhile, by definition, states S lead to precisely zero value no matter what action is taken and thus no regret could be incurred at these states. This implies that Condition 5.1 or Condition 5.2 ensures the information obtained from exploration in the nominal environment is sufficient for decision making in the worst-case environment, thus bypassing the information deficit issue.
5.1. Learnability of Online RMDPs
Focusing on CRMDPs with TV-distance defined uncertainty sets, Liu & Xu (2024a) and Lu et al. (2024) identified that the following assumptions can admit provably efficient on- line learning. In particular, Liu & Xu (2024a) made the following fail-states assumption.
Note that both Condition 5.1 and Condition 5.2 are specifi- cally designed for CRMDPs with TV-distance defined un- certainty sets. In more general f-divergence contexts, such as RMDPs with KL-divergence or x x2-divergence defined uncertainty sets or regularization terms, the property de- scribed in Proposition 5.4 does not hold. Consequently, learning RMDPs through online interaction is in general a challenging open problem (Lu al., 2024) without addi- tional assumptions. To characterize the inherent difficulty in learning online RMDPs with general f-divergences, we propose more intrinsic metric that captures the essential of the problem, based on visitation measures in both the nomi- nal and worst-case environments. Specifically, we have the following assumption.
Condition 5.1 (Fail-states). (Liu & Xu, 2024a, Condition 4.3) There exists a subset Sj C S of ftil-states such that (x a) = 0, (Syl,, a) = 1, V (s, h) E Sj x A [H].
Lu et al. (2024) extended Condition 5.1 to Condition 5.2, but both assumptions essentially serve the same purpose, climinating min,es (s) in the dual formulation of the optimization problem in the CRMDP-TV setting.
Condition 5.2 (Vanishing minimal value). (Lu et al., 2024, Assumption 4.1) The RMDP satisfies that min (s) 0. $E$
Assumption 5.5 (Bounded visitation measure ratio). Under (e) the definition of Definition 5.3, we define Cup := sup di dg(s) n,h.
To explain the rationale behind Condition 5.1, we first define the visitation measure as follows.
Definition 5.3 (Visitation measure). Under both CRMDPs and RRMDPs, for any policy æ, we define the worst-case transition corresponding to π as
as the supremal ratio between the nominal visitation mea- sure and the worst-case visitation measure. We assume that Cur is polynomial in H. S and A.
(+(s,) a) =
argmin Er, [V a) for CRMDPs, P. (P))
Remark 5.6 (Reduction non-robust setting). In non- robust settings, Assumption 5.5 is always satisfied with Cur 1, since (s) dz (s). This indicates our results also apply to the non-robust setting as a special case.
p (1|s,a) = argmin Ep, (V (s) PrEA(S)
(BP(((P()))))) ())) for RRMDPs.
At timestep h E [H] we denote (.) as the visitation measure on S induced by the policy स under po, and (-)
Visitation measure is a common metric in the offline liter- ature such as Li et al. (2024, Definition 3) and Shi Chi
6

---

Sample Complexity of Distributionally Robust Off- Off-Dynamies Reinforcement Learning with Online Interaction
(2024, Assumption 1). Assumption 5.5 ensures that the information obtained in the nominal environment can be ef- fectively used for estimation in the worst-case environment.
with probability at least ò, the uniform mixture of the policies produced by Algorithm is e-optimal.
To see how tight the upper bounds in Theorem 5.9 are, we provide the following results on lower bounds.
5.2. Regret Bound for Constrained Robust MDP
Theorem 5.12 (CRMDP regret lower bound). For CR- MDPs with TV, KL and x² divergence defined uncertainty sets, for any learning algorithm &, there exists CRMDP M satisfying Assumption 5.5, such that IE |Regret (M, K)] =
We first focus on CRMDPs with TV, KL and x2 divergences defined uncertainty sets. Before we present our results, we introduce an extra assumption for the CRMDP-KL setting.
Assumption 5.7. We assume there exists constant CMP > 0, such that for any (h, 8, a,,a8)) 8') E [H] x if (s a) > O, then P [s. a) > CMP.
Ω C VK).
Remark 5.13. Comparing Theorem 5.9 and Theorem 5. 5.12, we observe the order of Cer in the dominant terms of the upper bounds matches that in the lower bounds. The upper bounds thus align with the lower bounds in the two most critical parameters governing sample complexity: Cor and K. This indicates the fundamental presence of the informa- tion deficit issue in the online learning of robust policies. which stems from the discrepancy between the nominal and worst-case transitions and can be characterized by C.r-
Remark 5.8. For CRMDPs with KI.-divergence defined uncertainty sets, Assumption 5.7 guarantees the regularity of dual formulation for KL-divergence. We note that similar assumptions also appear in Yang et al. (2022, Theorem 3.2) and Shi & Chi (2024, Theorem 3), both study CRMDPs with KL-divergence defined uncertainty sets.
Theorem 5.9 (CRMDP regret upper bounds). Assume As- sumption 5.5 holds for CRMDPs with TV, KI. and x² di- vergence defined uncertainty sets. Assume Assumption 5.7 holds for the CRMDP-KL KL setting. Then for any 8 1), with probability at least 8, Algorithm satisfies
Based on the proof of Theorem 5.12, construct hard instances to illustrate the necessity of Assumption 5.5 in guaranteeing sample efficient online learning in CRMDPs.
Regret(K)
Õ( S AH (((1+ PCMP
Cl. A
(TV)
Lemma 5.14 (CRMDP hard instances). For CRMDPs with TV. KL and x² divergence defined uncertainty sets, for any learning algorithm &. there exists a CRMDP M with Cer = 224 such that E (eegret,(E.10 K)] = ((2*/K))
HVS
(C..
C
(KL).
O(C...SAAA A C
(x3)
Remark 5.10. Theorem 5.9 presents the first provably sub- linear result in the online RMDP literature for KL and x² defined uncertainty sets. The differences in dominant terms stem from how value function errors are amplified in dual formulations through Bellman equations and induction. Al- though the radius is not explicitly part of the results for TV- distance and x² >ivdivergence, it implicitly affects the bounds through Car in Assumption 5.5. A larger p loosens con- straints, increases distribution shifts, and consequently, re- quires higher Our and leads to increased regret bound.
Remark 5.15. Lemma 5.14 shows that, in the absence of additional assumptions, any online learning algorithm may perform poorly in CRMDPs. The hard instances are con- structed by selecting a critical state that has an exponentially small visitation measure in the nominal environment, and make it has a visitation measure of constant order in the worst-case environment. As result, an agent requires an exponential number of episodes to explore sufficient infor- mation about this state, while suffering a constant regret per episode when taking a suboptimal action.
is worth noting that under the policy selection scheme in Algorithm 1, our regret upper bounds still hold if we relax the definition of Cu. in Assumption 5.5 to be defined as the supremum visitation ratio over deterministic policies.
5.3. Regret Bound for Regularized Robust MDP
We then focus on RRMDPs with TV, KL and x² divergences defined regularization.
Theorem 5.16 (RRMDP regret upper bound). Assume As- sumption 5.5 holds for RRMDPs with TV, KL and x² diver- gence defined regularization terms. Then for any ò E (0,1) with probability at least 1 - 5, Algorithm I satisfies
By the standard online-to-band batch conversion (Cesa-Bianch) Bianchi et al., 2004), the regret bounds in Theorem 5.9 immediately imply the following sample complexity results:
Corollary 5.11. Under the same setup in Theorem 5.9, when
Regret ())
(TV)
(TV)
K=
ò
(I+ (
HYS (CH)SAHP/2))
(KL),
Ō((1+Be Be ' (C.S( cà.s A
(KL)
(Crr ATT
(x3)
O(C A A
(3)
7

---

Sample Complexity of Distributionally Robust Off- Oft-Dynamies Reinforcement Learning with Online Interaction
1.2
0.525
optimal polccy learned palicy
1.0
Non robust
ORBIT (CRMDR-TV)
1.0
Non robust ORBIT (OMMDR KLJ
1.2-
OBBIT ICRMDP
Non robust
ORBIT IRAMOR
ORBIT (RRMDP
0RBII IRRMDP 2
8-17--
0.6
0.8
0.5
0.450-
Avenoe
5.6
Avergge
0.000
0.375
10
14
16
15
20
50
0.2
3A
0.5
5.6
1.5
53
0.2
5.4
0,5
5.0
1.5
555
0.
2.4
0.6
5.6
1.0
Nuturbation
Perturbation
Perturbation
(a) Illustration of Cur
(b) TV settings
(c) KL settings
(d) X settings
Figure/ 1. Figure I(a) shows the comparison of the learned policy and the optimal policy in Section 6.1 (Illustration of the Effect of Cev on Robustness), where the optimal policy represents the ground truth optimal policy, the learned policy is obtained by Algorithm 1. Figures 1(b) to I(d) present the comparison between algorithm ORBIT and the non-robust algorithm in Section 6.2 (Learning on Simulated RMDPs)
Remark 5.17. Theorem 5.16 presents the first provably sublinear results in the online RRMDP settings. The re-
Online-Robol -Be--Belll ---BBllaaa Iteration
sult in Theorem 5.16 corresponding to the TV-distance is smaller by a factor of O)VS) compared Theorem 5.9. This efficiency gain arises because the dual formulation for RRMDPs eliminates the need for constructing net, which also speeds up solving the inner optimization problem and demonstrates computational advantages. No-
0.5
Avannge reweort
0.0
tably, Assumption 5.7 is not required in the RRMDP-KL setting, as the dual formulation for KL has a closed-form solution, which also reduces the computational cost. In the diverrege setting, the upper bound is larger than that in the constrained setting by a factor of (H)) This gap derives from the differences in dual formulations in two RMDPs, where Lemma D.9 in the RRMDP-x² 2 setting does not admit a square root compared to Lemma C.15 in the CRMDP-X2 2 setting.
GRAIT (CRMDATV) ORBIT (CRDDP KLI
ORBIT (RANDATV) ORBIT (PANE KU
DRIIT (CHIDDY')
CRIITT (UUINDPy?)
Eploade
Episade
(a) CRMDP
(b) RRMDP
Figure 2. The convergence ORBIT Section 6.3 (Learning the Frozen Lake Problem). We use the policies obtained after each training episode evaluate the convergence.
Theorem 5.18 (RRMDP regret lower bound). For RRMDPs with TV, KL and x² divergence defined regu- larization terms, for any learning algorithm &, there ex- ists a RRMDP M satisfying Assumption 5.5, such that E |eegret K)] V(C).KK.
6.1. Illustration of the Effect of Cur on Robustness
The supremal visitation ratio Cur measures the difficulty in exploration. With a fixed number of episodes, our re- sults Theorem 5.9 and Theorem 5. show that Cur would increase the sub- sub-optimality gap of the learned policies. In this section, we construct toy example (see Figure 4) with Hl = 3, S = {so, ,55, and A {0, 9}. focusing on the CRMDP-TV setting. More details about the environ- ment can be found in Appendix A.1. The visitation measure of each states are influenced by a hyper-parameter 33 and we can calculate that C.,, = 3 + in this case.
Comparing Theorem 5.16 and Theorem 5.18, we observe that the order of Cur in the dominant terms of upper bounds matches that in the lower bound. Together with the obser- vation in Remark 5.13, we can conclude that Cur is tight measure for evaluating exploration difficulty in RMDPs.
6. Experiments
As we can see from Figure I(a), when we increase Cupy by decreasing 3 in the nominal environment, it becomes harder for the agent explore the nominal environment sufficiently to learn the optimal policy in the perturbed environment, and thus deteriorate the performance of the learned policy and enlarge the ootimaiiyl gap. This aligns well with our theoretical results.
In this section, conduct numerical experiments to thor- oughly verify the theoretical findings in previous sec- tions. All numerical experiments were conducted on a server equipped with Intel(() Xeon(R) Gold 5118 CPU @ 2.30GHz. The implementation of our ORBIT algorithm available https:/ /ttp:///gttttbbtt http://gttaaaa....aaa.aat/ta cwtpp/axw./aaaa//////mmo
8

---

Sample Complexity of Distributionally Robust Off- Oft-Dynamies Reinforcement Learning with Online Interaction
trinking 10
Narribb and DRBIT (CMMONTVV DABIT (RAMOP-VV)
Namerhhaa DRBIT ICRMDR-KE KLI DRBIT JRRMOP-KL]
5900
0.84
Aveenee reMArE
Awoero TOWNES
5000
0.
0.5
4000
Aurengee
64-
9--
2009
Non-robust
02-
0.2
ORDIT (CAMDD-g"
conto Me
Rooicu KRMOP'
(A8MD
6.00
6.05
0.5
0:35
0.20
9.25
9.30
0.00
0.05
0.30
015
0.20
0.25
0.59
0.69
0.05
0.15 0.5 0.20
025
0.30
Setting
Nettrbation
Nettrrbation
Perturbation
(a) Average training time
(b) Evaluation (TV settings)
(c) Evaluation (KL settings)
(d) Evaluation (x² settings)
Figure 3. Results in Section 6.3 (Learning the Frozen Lake Problem). Figure 3(a) presents the average time taken for training in various settings. Figures 3(b) to 3(d) present the comparison between our algorithm ORBIT and the non-robust algorithm. We use the last episode policy K for the comparison.
6.2. Learning on Simulated RMDPs
mit closed-form solutions, simplifying the training process and resulting in lower computation complexity compared to CRMDPs. Lemma D.9 in the RRMDP-x² setting, on the other hand, requires solving optimization problems to get the dual formulations, leading to higher computational com- plexity than Lemmas C. 1 and D.1 in both two RMDPs with TV-distance and Lemmas C. 1 and D.5 in both two RMDPs with KL-divergence, though still lower than Lemma C.15 in the CRMDP-X setting. Notably, the training time for the CRMIP-TV setting is not significantly higher than that of RRMDP-TV, as we incorporate an additional optimization algorithm (detailed in Algorithm 2) to accelerate computa- tion. Also, due to our additional optimizations, increased exploration may result in longer training times.
Next, we design a simple MDP with learning horizon H = the state space is S = {so..... ,4 and the action space is A {0, 4). The source environment and target environment are illustrated in Figures 5(a) and 5(b). More details about the environment can be found in Appendix A.2.
The experiment results are presented in Figures 1(b) to 1(d). We can see that the policies under CRMDPs perform sim- ilarly their RRMDP counterpart. And compared to the non-robust algorithm, all robust policies are less sensitive to the environment perturbation. In particular, the performance of the non-robust algorithm drops drastically with respect to the perturbation. When the perturbation exceeds 0.6, all robust policies outperform the non-robust algorithm. This confirms the robustness of our proposed algorithm.
We also evaluate the robustness of the policy =² after K iterations of updates in various target environments with different Ppenuurb by calculating the average reward obtained in each target environment. As shown in Figures 3(b) to 3(d), our robust algorithm outperforms the corresponding non- robust version in most cases.
6.3. Learning the Frozen Lake Problem
Now we test our algorithm in a hard-to-explore setting, the Frozen Lake problem. In this scenario, the agent's 's objective to traverse a frozen lake from the Start (S) the Goal (G) without falling into any Holes (H), navigating over the Frozen (F) surface. A hyper- parameter Pperturb is used to measure the perturbation in the test environment. More details about the environment can be found in Appendix A.3.
7. Conclusion
We investigated online robust reinforcement lcarning within the context of tabular CRMDPs and RRMDPs, demonstrat- ing that when the nominal MDP is sufficiently exploratory, sample-efficient online learning becomes feasible. We quan- tified the exploration efficiency of RMDPs through a novel quantity called the supremal visitation ratio. We constructed hard instances show that moderate supremal visitation ratio is necessary for ensuring sample-efficient online leamn ing. We developed computationally efficient algorithms and provided regret analyses with both upper and lower bounds, which indicates our algorithm has an optimal dependency on the supremal visitation ratio and the number of episodes. We also conducted numerical experiments on diverse envi- ronments to validate our theory and show the robustness of our proposed algorithm.
First, we evaluate the convergence of our algorithm by track- ing the average reward throughout the training process in single target environment with fixed perturbation model, Ppertur. Specifically, we compute the average reward of the policy - obtained after each episode k. As shown in Figures 2(a) and 2(b), our algorithm consistently converges by the end of training. The corresponding average training time is reported in Figure 3(a).
For RRMDPs with TV and KL divergence defined regular- ization terms, the dual formulations of the Q-functions ad-

---

Sample Complexity of Distributionally Robust Off- Off-Dynamics Reinforcement Learning with Online Interaction
Impact Statement
Dong, J., Li, J., Wang, B., and Zhang, J. Online policy optimization for robust markov decision process. In Con- ference Uncertainty in Artificial Intelligence, 2024.
This paper presents work whose goal to advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
Eysenbach, B., Chaudhari, S., Asawa, S., Levine, S., and Salakhutdinov, R. Off-dynamiis reinforcement learning: Training for transfer with domain classifiers. In Interna- tional Conference on Learning Representations, 2021.
Acknowledgements
Guo, Y., Wang, Y.. Shi, Y., Xu, P., and Liu, A. Off-dynamics reinforcement learning via domain adaptation and reward augmented imitation. In Advances in Neural Informa- tion Processing Systems, volume 37, pp. 136326-136333 2024.
W. Wang, Z. Liu and P. Xu are supported in part by the Na- tional Science Foundation (DMS-23231 12) and the White- head Scholars Program at the Duke University School of Medicine.
Iyengar, G.N. N. Robust dynamic programning. Mathematics of Operations Research, 30(2):257-280, 2005.
References
Lattimore, T. and Szepesvári, C. Bandit algorithms. Cam- bridge University Press, 2020.
Abbasi-Yadea Yadkori, Y., Pál, D., and Szepesvári, C. Improved algorithms for linear stochastic bandits. Advances in Neural Information Processing Systems, 24, 2011.
Li, G., Shi, L.., Chen, Y., Chi, Y., and Wei, Y. Settling the sample complexity of model-based offline reinforcement learning. The Annals of Statistics, 22(1):233-260) 2024.
Auer, P.. Cesa-Bianche N., Freund, Y., and Schapire, R. E.
The nonstochastic multiarmed bandit problem. SIAM journal on computing, 32(1):48-77) 77, 2002.
Liu, Z. and Xu, P. Distributionally robust off-dynamics reinforcement learning: Provable efficiency with linear function approximation. In International Conference on Artificial Intelligence and Statistics, pp. 2719-2727. PMLR, 2024a.
Badrinath, K. P. and Kalathil, D. Robust reinforcement learning using least squares policy iteration with provable performance guarantees. In International Conference on Machine Learning, pp. 511-520. PMLR, 2021.
Liu, Z. and Xu, P. Minimax optimal and computation- ally efficient algorithms for distributionally robust offline reinforcement learning. In Advances in Neural Informa- tion Processing Systems, volume 37, pp. 86602 86654, 2024b.
Blanchet, J., Lu, M., Zhang, T., and Zhong, H. Double pessimism is provably efficient for distributionally robust offline reinforcement learning: Generic algorithm and robust partial coverage. Advances in Neural Information Processing Systems, 36:66845-66857 2023.
Liu, Z. and Xu, P. Linear mixture distributionally robust markov decision processes. arXiv preprint arXiv:2505. 18044, 2025.
Cesa-Bianchi, N., Conconi, A., and Gentile, C. On the gen- eralization ability of on-line learning algorithms. IEEE Transactions on Information Theory, 200)):000--2077, 2004.
Liu, Z., Wang, W., and Xu, P. Upper and lower bounds for distributionally robust off off-dynamics reinforcement learning. arXiv preprint arXiv:2409.2052/ 2024.
Da, L., Turnau, J., Kutralingam, T. P., Velasquez, A., Shakar- ian, P., and Wei, H. A survey of sim-to-real methods in rl: Progress, prospects and challenges with foundation models. arXiv preprint arXiv:2502. 131.1 2025.
Lu, M., Zhong, H., Zhang, T., and Blanchet, J. Distribu- tionally robust reinforcement learning with interactive data collection: Fundamental hardness and npar-optimal algorithms. In The Thirly-eighth Annual Conference on Neural Information Processing Systems, 2024.
Dann, C., Lattimore, T., and Brunskill, E. Unifying pac and Uniform pac bounds for episodic reinforcement learning. Advances in Neural Information Processing Systems, 30, 2017.
regret:
Lyu, J., Xu, K., Xu, J., Yang, J.-W., Zhang, Z., Bai, C., Lu, Z., Li, X., et al. Odrl: benchmark for off-dynamics reinforcement learning. Advances in Neural Information Processing Systems, 37:59859-5991 2024.
Desai, S., Durugkar, I., Karnan, H., Warnell, G., Hanna, J., and Stone, P. An imitation from observation approach to transfer learning with dynamics mismatch. Advances in Neural Information Processing Systems, 33:3917-3929, 2020.
Mannor, S., Mebel, O., and Xu, H. Robust mdps with k-rectangular uncertainty. Mathematics of Operations Research, 41(4):1484-1155 2016.
10

---

Sample Complexity of Distributionally Robust Off- Off-Dynamics Reinforcement Learning with Online Interaction
Maurer, A. and Pontil, M. Empirical bernstein bounds and sample variance penalization. arXiv preprint arXiv:0907.37440 37400 2009.
Wang, Y. and Zou, S. Online robust reinforcement learning with model uncertainty. Advances in Neural Information Processing Systems, 34:7193-7206, 2021.
Nilim, A. and El Ghaoui, L. Robust control of markov decision processes with uncertain transition matrices. Op- erations Research, 53(5):780-798, 2005.
Weissman, T., Ordentlich, E., Seroussi, G., Verdu, S., and Weinberger, M. Inequalities for the 11 deviation of the empirical distribution. Hewlett-Puckard Labs, Tech. Rep. pp. 125, 2003.
Panaganti, K. and Kalathl, D. Sample complexity of ro- bust reinforcement learning with generative model. In International Conference Artificial Intelligence and Statistics, pp. 9582-9602. PMLR, 2022.
Wen, X., Bai, C.,, Xu, K., Yu, X., Zhang, Y., Li, X., and Wang. Z. Contrastive representation for data filtering in cross-domain offline reinforcement learning. In Proceed- ings of the 41st International Conference Machine Learning, pp. 00700-277225 52743, 2024.
Panaganti, K., Xu, Z., Kalathil, D., and Ghavamzadeh, M. Robust reinforcement learning using offline data. Ad- vances in Neural Information Processing Systems, 35: 32211-32224, 2022.
Wiesemann, W., Kuhn, D., and Rustem, B. Robust markov decision processes. Mathematics of Operations Research, 38(1):153- 183, 2013.
Panaganti, K., Wierman, A., and Mazumdar, E. Model-free robust d-divergence reinforcement learning using both offline and online data. In Proceedings of the 4 1st Inter- national Conference on Machine Learning, pp. 39324- 39363, 2024.
Xu, H. and Mannor, S. The robustness peaitness--erfoomance trade- off in markov decision processes. Advances in Neural Information Processing Systems, 19, 2006.
Xu, K., Bai, C.,, Ma, X., Wang, D., Zhao, B., Wang, 7., Li, X., and Li, W. Cross-domain policy adaptation via value- guided data filtering. Advances Neural Information Processing Systems, 36:73395-73421 2023a.
Satia, J. K. and Lave Jr, R. E. Markovian decision pro- cesses with uncertain transition probabilities. Operations Research, 21(3):728-744 1973.
Xu, Z.. Panaganti, K., and Kalathil, D. Improved sample complexity bounds for distributionally robust reinforce- ment learning. In International Conference on Artifi- cial Intelligence and Statisties, pp. 2023b.
Sayyareh, A. A new upper bound for kullback- leibler diver- gence. Appl. Math. Sci, 67:3303-3317, 2011.
PMLR,
Shi, L. and Chi, Y. Distributionally robust model-based offline reinforcement learning with near-optimal sample complexity. Journal of Machine Learning Research, 25 1200):1-91, 2024.
Yang, W., Zhang, I.., and Zhang, Z. Toward theoretical un- derstandings of robust markov decision processes: Sam- ple complexity and asymptotics. The Annals of Statistics, 50(6):3223-3248, 2022.
Shi, L., Li, G., Wei, Y., Chen, Y., Geist, M., and Chi, Y. The curious price of distributional robustness reinforcement learning with a generative model. Advances in Neural Information Processing Systems, 36, 2024.
Yang, W., Wang, H., Kozuno, T., Jordan, S. M., and Zhang, Z. Robust markov decision processes without model estimation. arXiv preprint arXiv:2302.01244, 2023.
Tang, C., Liu, 7.., and Xu, P. Robust offline reinforcement learning with linearly structured f-dieergence regulariza- tion. arXiv preprint arXiv:2411.18617 2024.
Zanette, A. and Brunskill, E. Tighter moblem-deppnden regret bounds in reinforcement learning without domain knowledge using value function bounds. Interna- tional Conference on Machine Learning, pp. 7304-7312. PMLR, 2019.
Vershynin, R. High- digh-ddimessooal probability: An introduc- tion with applications in data science, volume 47. Cam- bridge university press, 2018
Zhang, R., Hu, Y., and Li, N. Soft robust mdps and risk- sensitive mdps: Equivalence, policy gradient, and sample complexity. In The Twelfth International Conference on Learning Representations, 2024.
Wang, H., Shi, L., and Chi, Y. Sample complexity of offline distributionally robust linear markov decision processes. In Reinforcement Learning Conference, 2024a.
Wang, R., Yang, Y., Liu, Z., Zhou, D., and Xu, P. Return augmented decision transformer for off-dynamics rein- forcement learning. arXiv preprint arXiv:2410.23450, 2024b.
Zhang, T., Zhang, K., Lin, J., Louie, W.-Y. G., and Huang, H. Sim2real learning of obstacle avoidance for robotic manipulators in uncertain environments. IEEE Robotics and Automation Letters, 7(1):65-72, 2021.

---

Sample Complexity of Distributionally Robust Off- Off-Dynamics Reinforcement Learning with Online Interaction
Zhou, Z.,, Zhou, Z., Bai, Q., Qiu, L., Blanchet, J., and Glynn, P. Finite-sample regret bound for distributionally robust offline tabular reinforcement learning. In International Conference on Artificial Intelligence and Statistics, pp. 3331-3339. PMLR, 2021.
12

---

Sample Complexity of Distributionally Robust Off Off-Dynamics Reinforcement Learning with Online Interaction
A. Additional Details on Experiments.
In this section, we provide more details about the experiments conducted Section 6.
A.1. More Details on Section 6.1 (lllustration of the Effect of Cor on Robustness)
Construction We consider a simulated RMDP Figure 4(a) with horizon length H = 3, state space S = {s0,- 8s). and action space A= = {0,- {O.... -). At each episode, the initial state is always sy. The nominal transition the first stage independent of actions taken, Oo (s1 (80)
(82 (8) B3 where B is hyperparameter. At the second stage, if the current state is 82, it will transit to 85 with probability 1; if the current state is 81, then we have (s(s3|11, a = 0) 6. (s (1,))) r(33, a) = 1, (,, a) = 1. Va E A. By construction, the action taken at determines the final reward, and there are actually two kinds of actions: = 0 if = and if a E A/0. Though actions in 4/0 are equivalent, they are set to increase the harness in exploration. We construct a TV-distance defined uncertainty set with radius p -
2: Vu {1. .9) and (s a) = 1 (s Only 83 and 85 can generate reward, with
is easy to observe that, regardless of the policy π chosen, (** I VT.P (53) and (s1) (s2) therefore the worst-case transition probability for any policy π is pw, (syl $1, 0) 2.2 p (1 6 Va {1. {1. .9} and pwn (sa 81, a)
(s2). Furthermore, the transition probability pw. (s] 50: a) 1 pw." ($2 5o, a) 3 + 3. Va, where 3 (0, ()) is hyper-parameter. We can easily verify that all those transitions are within [0, 1] and therefore well defined. With this analysis, we can calculate the visitation measure for each policy in Table 1 and derive Co. = 3 3.
pe. (#3 81, a). Thus, (s1)(s)) =
Implementation Under the optimal policy (taking a = 0 at s = $1), the expected reward is Ex- [r] = 1 3. We set the number of episodes K = 1000 to simulate a scenario with limited exploration and run Algorithm in the CRMDP-TV setting. We test learned robust policies in the worst-case target environment and calculate the average reward among 2000 runs. The experimental results are based on 50 replications and plotted in Figure ((a).
2. regardless of
$3
33
$1
$1
8
+
84
50
50
8
82
85
82
(a) The nominal MDP enviromment.
(b)
The worst-case MDP environment.
Figure 4, The constructions of the nominal MDP and the worst-case MDP environments in Section 6.1.
Table I. The visitation measure of each state in Section 6.1, the maximum of
9 a (e)
is achieved by taking ä = at $4.
50
81
82
83
84
85
(g)
8
8
( + 8
B
8 + 33
38
3
(
G
+ (3
+ )
A.2. More Details on Section 6.2 (Learning on Simulated RMDPs)
Construction We consider a simple MDP Figure 5(a) as the source environment. The learning horizon H 3, the state space is S = (so, ... 844, and the action space is = (0...., 4). The initial state always 8p, where it can transit to
13

---

Sample Complexity of Distributionally Robust Off- Off-Dynamics Reinforcement Learning with Online Interaction
$1, 83 and 54 with probability (s0 0.4 + To (83 80, a) 0.1 and (s a) 0.5 To correspondingly; From 81, can transit to 82 and 83 with probability Po
Po (2 81, a) 1o and Pa (s = a by taking action From 52, it can transit to 83 and 84 with probability (s a) = 1 TO and Pd (s4(s1),, a) 10 by taking action The 83 and 81 are absorbing states. The agent is rewarded 20 by taking action at su. $1 and $2, rewarded regardless of the action taken at 84, and rewarded O regardless of the action taken at 83.
The target environment Figure 5(b) is obtained by perturbing the first step in the source environment. To be specific, with perturbation rate q. the transition probability from so to $3 and $1 is p (s3 so.a) 0.1 q x (0.5 10) and p" (s4(80,, a) (1 q) (0.5 1. while pa (s1(s180, a) = 0.4 + 10 stays the same.
Implementation We set K 1, 000 in Algorithm and evaluate the learned policy in target environments with q E {0,0.05, 0.1, ,I, respectively. In each target environment, the average reward among 500 runs is calculated for evaluation. All experimental results are based on 20 replications. The choice of uncertainty level regularizer 33 and constant Cbenus are provided in Table 2. For the non-robust algorithm, we simply set / = 10000 for Algorithm instantiated with TV-distance defined regularization. can be justified by Lemma D.I that the extremely large regularization would not tolerate any perturbation, and thus the learned policy is basically the optimal policy under the source environment. The results are plotted in Figures I(b) I(d).
83
$3
9
x (0.5
10
82
50
81
0.4
10
0.4
0.5
10
(1 - 9) (0.5
54
94
(a) The source RMDP environment. (b) The target RMDP environment.
Figure 5. The source and target RMDP enviromments in Section 6.2, where the target environment is constructed perturbing the first step.
A.3. More Details on Section 6.3 (Learning the Frozen Lake Problem)
Construction In this scenario, the agent's objective is to traverse a frozen lake from the Start (S) to the Goal (G) without falling into any Holes (H), navigating over the Frozen (F) surface. The agent's 's movement is influenced by a hyper- parameter Paip = 0.1, which determines the probability of the agent successfully moving the intended direction. Specifically, the agent moves towards the intended direction with a probability veer off in either perpendicular direction. The Goal state is absorbing state, once reached the agent will stay there. The agent earns reward of if and only if it is at the goal (G) at step H 1. For evaluation, after the agent selects an intended action, with probability of P Ppenurr. the agent actually takes action towards the opposite direction instead. The difficulty of this en environment arises from two sources: 1) it is a sparse reward MDP, and 2) the influence onto the movement in the source environment makes the exploration of the goal state very hard.
Pasip 0.9, and with probability Paipp /2 0.05, it will
Implementation We use the default map in the OpenAl Gym library, which is illustrated in Example A. and set = 25 and K = 1, .00 in Algorithm The hyperparameter p the constrained setting, 3 in the regularized setting, and Chonus are
14

---

Sample Complexity of Distributionally Robust Off- Off-Dynamics Reinforcement Learning with Online Interaction
tuned from {0.001, 0.003, 0.01,000,, 0.1, 0.3, 1), with the final choice presented in Table 2. All experimental results based on 20 replications.
We implement several optimizations to accelerate the algorithm. First, we reuse the counts nf, (s, a) from (4.1) across different steps, as the transition dynamics remain consistent throughout. Additionally, we observe that the inner optimization process, which is the primary bottleneck of the algorithm, does not need to be fully recalculated at each episode. For instance, the agent falls into hole after the first step, the information about the environment remains largely unchanged. To take advantage of this, we create a map where the keys are hashes of the optimization parameters and the values are the corresponding results, allowing us reuse prior computations efficiently. We also applied Algorithm 2 to obtain the result in the CRMDP-TV setting, which can directly be derived from definition.
We assess the convergence of our algorithms by calculating the average reward among 500 runs in the single target environment with Ppenur 0.1, of the policy x² obtained after each episode & during the training. The convergence results are plotted in Figures (()) and 2(b), and the average training time is plotted in Figure 3(a). We also evaluate the robustness of the policy æ K after K episodes across various target environments with Perturb {0, 0.05, 0.1, .0.3}. For each target environment, we compute the average reward among 500 runs, and the results shown in Figures 3(b) 3(d).
Example A.1 (lllustration of Frozen Lake environment). The environment of the Frozen Lake problem is illustrated as follows, where S denotes "Start", G denotes "Goal", H denotes "Hole" and denotes "Frozen".
S
F
F
F
F
F
F
F
F
F
F
F
F
F
F
F
F
F
F
H
F
F
F
F
F
F
H
F
F
H
F
F
H
F
F
F
H
F
F
F
F
F
F
H
F
F
F
G
A.4. A More Computationally Efficient Solver for the CRMDP-TV Setting
As shown in Lemma C.I, the update formulation of Algorithm the CRMDP-TV setting involves solving an optimization problem in its dual formulation. To reduce the computational complexity, we introduce Algorithm 2, which simplifies this procedure.
We explain the rationale behind Algorithm follows. The original formulation of the CRMDP-TV problem is given inf by (x a) = rx (x a) TV(P))P)) [ a). It is easy to see that the worst-case scenario is reached when the
transition probabilities for states with the highest value functions are reduced by a total of p. and those for states with the lowest value functions are increased by This greedy approach avoids the need to solve the optimization problem for 7 as described in Lemma C.I.
A.5. paperrprramterrs for Experiments Section
Here, we provide the Syper-parametery used training in the experiments section. Note that we reformulate the bonus term as Obonus/ /V in practical experiments.
15

---

Sample Complexity of Distributionally Robust Off-Dynamics Reinforcement Learning with Online Interaction
Algorithm 2 A efficient solver for the CRMDP-TV setting
Require: robust set radius > O, transition array P[S], value function array V[$] (S > 1)
1: args argsort(V).
2: V V |argss)
P(args].
3: pnt, 1, pnt, S.
4: rho, 0, rho, O.
5: while rhoo < p do
6: tmp min(p rhoo, 1 - P(pnt)))
7: P[pnt,] - P Pipnty + tmp.
8: rho, = rho + tmp.
9: pnt, = pnt,
end while
11: while rho; < p do
12: tmp mpn(p rhoi P pntt [).
13: Pipnt, = P P'pnt,] - tmp.
14: rho, = rho, + tmp.
15: pnt, = pnt -
16: end while
Output: Σ Pid] * V[d.
Table 2. hyper-parametory for Scction 6.2 (Learning on Simulated RMDPs)
Setting
p or 3
Obonus
non-robust
constrained TV
0.5
constrained KL
0.5
constrained x²
1
regularized TV
0.1
regularized KI.
0.1
regularized x²
0.1
B. Proof of Proposition 5.4
Proof of Proposition 5.4. We prove it by contradiction. We assume that there exists s", a" and s' such that VT 0 and p (s' 3,=,00 a²) > (8'11"",")) We pick & Sj arbitrarily and consider the following transition measure PA;
Pi (sls",a")
8 $ {s)
s'
P a²) + PI (5'1s" (s'1' (0'8'""",'") aa)
8.
easy to verify that P/ E A(S), TV(P)) PR) S TV(P PR), therefore P/, is a valid transition measure in the transition uncertainty set. Based on the definition of fail-states, we have Vi (B) 0 V (8") and thus Pp (V <
Epp. (V77), which contradicts the fact that pw., is the worst-case transition.
C. Proofs of Results in Constrained RMDPs
C.1. Proof of Theorem 5.9 (Constrained TV Setting)
Before proving this theorem, we first present several technical lemmas that will be useful in the proof.
We first give the closed form solution of constrained TVV update formulation. This dual formulation has also been proved by
16

---

Sample Complexity of Distributionally Robust Off- Off-Dynamics Reinforcement Learning with Online Interaction
Table hyper-parameters for Section 6.3 (Learning the Frozen Lake Problem)
Setting
p porg 3
Oboous
non-robust
0.001
constrained TV
0.15
0.001
constrained KL
0.15
0.01
constrained x²
0.5
0.01
regularized TV
0.1
0.003
regularized KL
0.1
0.001
regularized x²
0.05
0.01
Iyengar (2005, Lemma 4.3), but the formulation of result is slightly different from theirs. Note that Lu al. (2024) used the same formulation, but their expression is incorrect by factor of 2.- This error arises because they directly cited Yang et al. (2022), which employed the Lı distance rather than the TV-distance. So we prove it again for the sake of completeness. Lemma C.1 (Dual formulation). For the optimization problem (s(s,a) an(s,a) have its dual formulation as follows
inf Ep(Vi+a((s,a)) TV(P)PR)SP
Qn Th
inf nE
(Ep:l(n Vv-1(s))+] p(11
min sES
(i)) n)
(C.1)
Proof. Consider the optimization problem
Qn Thh
inf (PPP))))
Ep[V++1] = th +
inf (V(P)I)))
Σ P(s)Vi-1(S).
We denote (p(t) = It - 11/2, then the Lagrangian can be written as
C(P,n) = Σ (s)) + Σ PR(S)D
P(5)
-D) -x(O))()++
+
PP(s))
SES
.ES
SES
#ES
We denote g(8) = P(s)/ (s),, then we have
inf C(P, = - sup Σ (R()))(()((((S)) + n) - V/++([s]] -
- vp +
p
NES
(M(s) + - (5) ] up +
= -1 40"
where the second equation is from the definition of dual function 4p" (v) sup(y Tx (((x)) From f-divergence literature (Xu et al., 2023b), we know that for TV-distance,
for 8 < 2
(s))
for 2 < < Ι 1.
(C.2)
2
to0 for > 2'
So have
Qh
Th
sup
inf ((P,n))
v20.220.v
(A(s) + 1) (s+
= Th
inf
pE 6²
+ up +up -
o20.X20,m
V
(>(s) + 17) Vn+i(8)
- 1)
+ +up up--1) 1)
Th
inf v20.A20,1,
vEpp
max
(C.3)
X (o))
1
17

---

Sample Complexity of Distributionally Robust Off- Off-Dynamics Reinforeement Learning with Online Interaction
Vh+ (A)
+ + - 5
Th
inf AGOTO
EPg
+
v20.A20.m.
Th- 220.A20.n' 2 (2 (n)
inf
-Vu+(()))) up - n/)
(C.4)
1Bpg1(A66 + (+++( pmax +1/ Vh+ V/++( -n')
Th inf X20,n'
(C.5)
Th inf (Brg [(n' Vh+1 - (8)) + p(1/ -min V (8) -n¹)
min SES
(C.6)
Th inf (Rrgllií Va+ (+))+ + p(11 min V Va+1 (8) + - n/) EES
min
(C.7)
of [
where (C.3) follows from the definition of up (C.2), we redefine of . 2 in (C.4), (C.5) holds because the result increases monotonically with respect to thus the minimum value is attained at = (a()) 1/ Vi+1 (s))++ (C.6) holds
.ES
because the result increases monotonically with respect to X, (C.7) holds because the result increases monotonically with respect to n/ when rf S 0 and increases monotonically with respect to nf' when n/ 2 H.
In the next lemma, we prove the optimism of estimation Q which helps control the estimation error Q" -
Lemma C.2 (Optimism). If we set the bonus term as follows
2S In (I(2SAHH))100 bonus a)= 2H
+ K
(C.8)
1 (s.a) V1
then for any policy x and any (k; 8,a) E [K] x [ S x A, with probability least 1 - 28, we have Qh ( a) 2 ( a). Specially, by setting = =",, we have Q (s, a) 2 0% (s,
Proof. We prove this by induction. First, when h= + 1, t. (s. a) 0 T=:FI118, holds trivially.
Assume a) 2 12 (s) holds, since n is the greedy policy, we have
h+1 (+) Qhiff (s. (+)) 2 2hff (8, 1 (8)) 2 Q 2hff (s, (s)))+(()) (x),
where the first inequality is because we choose - as the greedy policy.
Recall that we denote " as the optimistic estimation in k-th episode, that is,
@ a) bon a) a)) + inf TV(P)PH)s
Ep Bp[vit]]
We can infer that
Qh
b. Q% = bonus/; + + + inf TS(P h+1 - -h -
Ep (P[V/
inf Ps(
Ep [Vr
bonus $ + -r +
inf TV(PIPPN)
Ep [V
inf TV(PIP:)Sp
Ep [VA+1]
inf Ep 1 Will TV(P)PR)SP
inf TV(P)PP)SP V
2 >oous
& + + rh inf TV(PIPP)SPP
Ep [viie]]
inf TV(
Ep [Vrie]]
(C.9)
= b + + rh inf n
[E (1 - Vida (s)) + p(1
min Vitt((s) -1) SES
+ inf
(Epe [17 ( ] + p(1
min
EES 1 (2)4(()) -n)
(C.10)
18

---

Sample Complexity of Distributionally Robust Off- Off-Dynamics Reinforcement Learning with Online Interaction
bonus, + p% rh + inf { ne(0,.
[Bp [(7
n+1 (s)) + p
min
Vit (s)) - n) SEB
+
[Bpx [17 Viii (s)) +] + p min
NES h+1 (s) (6)) - }
= bonus,
+ 1% Th +
inf H)
{ pg [177 - Vi4 (s)) +] - -Ept [(1] - p (s) (s)) +1}
bonus;
|r Th
sup [0
E Ep
(n
Vi (s)) Bpp ((n (s) +11:
(C.11)
(i)
where (C.9) is from the induction assumption, plug in the dual formulation (C.1) in (C.10).
For term (i) in (C.11), from Lemma G.1 and a union bound, with probability at least 1 - 8, we have
1n(2SAHK/0)
(P) - (r)
(C.12)
2n k- (
for any h,, E [K] X H x X
We denote ((n) (n- V (s)),
E [0, H) and V (V E R |V S H}. To bound term (ii) in (C.11), we create a (c(() for V. From Lemma G.4, it holds that In (wr()) < [S] ln(3//c).
Therefore, by the definition of (e),)), for any fixed V. there exists V E (ev(e) such that | V'
S that is
Er - EE px
[V] S Pg [V] Epg [V]] + Epp [V] - Ep [V] +
E by
[V'] - EEp [V]
< |P - Vo + Epp [V] - Epp [ +
2 h
|IV - V'l
< sup weNv(e
Epg ['] pp V'] + 2c,
(C.13)
where the second inequality follows from the Holder's inequality.
For any fixed V. we apply Lemma G.3 and have
2S (2/8))
E [V] E pa [V]
< PM -
-Phll
[V - H
V
(C.14)
k-1 V1
ni
with probability at least 5.
Then with probability at least 1 - 8, we have
sup rE(o.H]
Epg [n (=)) Epy
V (s)) -
sup [E
Epg [v()) Ep [V())]
sup VeNv(e)
Ee V
Epp [V] 2c
(C.15)
25 21
H
+ 26
(C.16)
Th v1
25a In 165 K K/ee)
< H
2e
Th
V1
282
11S /8)
H
(C.17)
"
V1
K'
for any (ks h, s, a) E [K] x [ x A, where (C.15) follows from (C.13), (C.16) from (C.14) and a union bound, we
set c = 1/2K in
in (C.17).
19

---

Sample Complexity of Distributionally Robust Off- Off-Dynamics Reinforcement Learning with Online Interaction
Apply the union bound again and combine (C.11) with (C.12), (C.17), the definition of bonus and induction assumption.
With probability at least 1 26, we have ( a) 2 (s a) for any s,, [K] x (M) S A. This completes the proof.
Lemma C.3. For any [K], bound the estimation error follows
0 Q7
Σ h=1
E (px. w
2bonus
Proof. From the proof of Lemma C.2, we see that
a)) rr(s,)))
inf TV(PIPR)s
Ep [Vifi TV(PIPE)))
inf
Ep Ep[Vit (s, a) I bonus (s, a).
(C.18)
Recall that we define pia
Ep [ TV(PIIg))s
argmin
of the worst-case transition in Definition 5.3, we have
Qh Q x= bonus + rh
inf TV(PIPP)sp
Ep [ htil rh TV(P)PR)
inf
Ep Bv[vi :
bonus + th rh +
inf Ep [v[V TV(PIPR)
inf TV(P)P))
EP [v
inf Er [v[4]]]] TV(P)PP)sP
inf TV(P)PR)SP
Er [v(ti]
2bonus
inf TV(P))PR)
Ep [V inf TV(PliggsP
Ep [V
(C.19)
2bonus & + pp.. [Vinp - Whtil
(C.20)
2bonus
E Bpp..t. a
k.P
(C.21)
where the (C.19) holds because of (C.18), (C.20) and (C.21) use the definition of PA and x² accordingly. Apply (C.21) recursively, we can obtain the result.
Next, in Lemma C.9, provide upper bound the sum of the expectations of V n 'v under the worst-case
environment. In order prove this lemma, we follow a similar procedure to that of Zanette & Brunskill (2019), whose setting differs from ours consider the non-stationary dynamics.
Lemma C.4. (Failure Events) We define the following failure events:
SAHK 5
3s, a, h: n k- (s, - 2 Fv
Σ
(s, - In
ick
Then we have P
U F& $ 1 1-
Proof. Consider fixed E S,a E A, [H). We define F& to be the a-field induced by the first A: episodes and X₃ to be the indicator whether (s, a) was visited in episode ls at step h. The probability PPss = s a a mx)) of whether X = 1 is measuuuue,, therefore we apply Lemma G.5 with W = Inn IIn SAHK The proof is finished by applying union bound over 8, a, h, k.
Definition C.5. (The Good Set) We define
Lx = { (
[SAHK +1
ick
20

---

Sample Complexity of Distributionally Robust Off- Off-Dynamics Reinforcement Learning with Online Interaction
Lemma C.6. (Visitation Ratio) Outside the failure event, if (s, a, Lgp we have
Tb k as) 2
(s)
k
Proof. Outside the failure events defined in Lemma C.4, we have
SAHK
n (s, a) > d (s, a) - In 8
2 i<
(8) +
1
Σ
()) - In [SAHK
7
5
ic
as, +12
Σ
as (s, 2 Σ (s.
ick
where the second inequality uses (s, a,a) h) E La and the definition of L in Definition C.S.
Lemma C.7. (Minimal Contribution) Outside the failure event, we have
K
Σ Σ
- - O(SAI).
k= (s,a,hjEL
Proof. We have
K
Σ Σ d)(saa Σ Σ a Lx}
k= (L,
(,,0,)) k=1
Σ ((s,))
L
(s,a,)
KCK
SAHK
4ln
+5)
8
(s,0,))
O(SA).
where the first inequality uses the definition of LA in Definition C.5.
Lemma C.8. (Visitation Ratio) Outside the failure event, it holds that
d) Ō(SAH).
Σ
n (s,a)
(s.a.))ELx
Proof. Outside the failure events defined in Lemma C.4, we have
(s
K Σ
as 1((s,a,h) E Lx)
Σ
n
(s,
mi
(
(s,a,))ELx
k=
(8,0,h)
K
(s
1(((s( Lxb.
Σ (s a)
k= (s.a.h)
tsk
where the inequality follows from Lemma C.6.
21

---

Sample Complexity of Distributionally Robust Off- Off-Dynamies Reinforcement Learning with Online Interaction
Next, for any fixed (h, a, Lg for some lig since Σ dl (s, a) is strictly increasing with k. there exists critical episode
i ko such that a,) E Lg holds for all k > k and (h, 8, a) E L holds for all & < k. From the definition of k and Definition C.5, we know
Σ d (s, 2 4 SAHK) + 4 4. Therefore,
ic
K
(s,0)
K
(s
Σ
h() E Lz}-
Σ
d
11(s, E Lx}
Σ (8,a)
Σ
(s, a) + Σ dx(s,a)
ich
Asisk
K
(3,00) σ)
a((,,a,)) E Lx3
+
Σ (8,00)
kiisk
(s.a)
4+ Σ (s,a)
REASK
kiisk
where the third inequality comes from the definition of k. To simplify the notations, we define d1 = ds, U2 = dl (s, a), x-- = dj (s,, a). And in order to bound the
x++1
[x]
above summation, we also define the functions F(x) =
Σ
U/s u/a (a - [x|) and f(x) u[a It is easy to verify that the
derivative of F(x)) is (xx) Then we write
K k+1
K K++
Σ
(s, a)
Uk
f(k)
(8,
4 F(k)
Rsisk
k=1
4
U1
k=1
[
Additionally, we have that F(x)= S Σ Us +
Σ Us
F([x1) and f(x) = =[[[2]). Then, we have
K -
s(k)
K-K+1
f((x]) dx
Σ
4 F())
4+ F([z])
K K-T-11
f(x) dr
4+ F(r)
In F(K 1 + 1)) In(4 + F(0)) S Ō(l((K).
We obtain the result by summing over all the (s, a, h) pairs. Lemma C.9. Outside the failure event, it holds that
K
H
O( + SAH).
pm
[V
( (st (+t))
nip
1=1h=1
Proof. Outside the failure event, we can calculate as follows
K H
pu.k x
k k- (s.a)
Thp
Σ (k, /)
1
(8,
1=1 (h,s,a)
22

---

Sample Complexity of Distributionally Robust Off- Off-Dynamics Reinforcement Learning with Online Interaction
K
dht a
1
(s,a)
(C.22)
(s,a) n
V1
1= (R,s,a)ELx
k=1
(h,s.0)ELz
K
k= (h.s,a)Ehu (
Σ
Σ
(),
(C.23)
1 (s,a)
k=
Σ
qf ()
t
+ CCr
Σ
Σ
(s
(C.24)
1/ (s,a)
k= (1,s,a)ELx
k= (h,
a))
+ +((CoASAH)
(C.25)
1/ (s,a)
R= (b,
( k= (N.S,a)EL
af ap(()
Σ
Σ
+ +O(C..SAH)
(C.26)
"h (s,
k= (h,
K
K
(s (s,a) + +O(C,,
dh (a(s,))
Cur
Σ 1=1 (h,s,0)ELx
Σ
(C.27)
k=1 (h.8.0)
SV KH SAHC + ((HH.
(C.28)
OVVC, + SAH),
2h, (s.a]VI 1, (C.23) holds because n k- (s. a) 2 In( 8 + 2 1 by combining Definition C.5 and Lemma C.6. (C.24) and (C.27) are from our assumption Assumption 5.5, (C.25) and (C.28) are from Lemma C.7 and Lemma C.8 accordingly, and (C.26) the Cauchy-Schwartz inequality.
where (C.22) decomposes the summation into two parts and makes use of the fact that
We are now ready prove the main theorem that establishes the regret bound of ORBIT in the CRMDP-TV setting. Theorem C.10 (Restatement of Theorem 5.9 in TV-distance setting). For CRMDP with (s, re-ttnggga TV-distance defined uncertainty set satisfying Assumption 5.5, with probability at
least 1 6, the regret of Algorithm I satisfies
Regret Ō (C.,, S? AH? S² A HVKK.
Proof. Setting 8' = 5/33 in Lemmas C.2 and C.4, then with probability at least 1 - 5, we get
K
Regret
(VT
k=1
Σ (Vite visit)
(vho vith
K
H
piit x [2bous
(C.29)
k=
h=1
2Sa In mm
1
2H.
(C.30)
k- (s, V1
K
k= 1=
S AH
c².
(C.31)
where (C.29) is the combination of Lemma C.2 and Lemma C.3, we plug in the bonus (C.8) in (C.30), (C.31) is from
Lemma C.9.
23

---

Sample Complexity of Distributionally Robust Off- Off-Dynamics Reinforcement Learning with Online Interaction
C.2. Proof of Theorem 5.9 (Constrained KL Setting)
We first give the closed form solution of constrained KL update formulation. This dual formulation has also been proved by Iyengar (2005, Lemma 4.1), but the rage of y in our result is more precise compared to theirs. Lemma C.11 (Dual formulation). For the optimization problem Qu(s, a) rr (x) (I(PP))))
inf Ep[Va+1](s, a), we
have its dual formulation as follows
Qh Th
inf (v/n le [Vats] + up) velo, #1
(C.32)
Proof. Consider the optimization problem
Qn rh +
inf (L(PIIPg)
Ep[V++1] rh+ +
inf E P(s)Vi+1(s).
KLAPIPP)) SES
The Lagrangian can be written as
((P,n) - P()N)++1()) +
Σ
P(s)
-
(s))P(s)++111
Σ
(s)
.ES
SES
.ES
.E9
We set the derivative of w.r.t. P(s) to zero
0c
P(s)
(p(s) Vh+1(s) + +lnn
+ (A(s) + n] =
(C.33)
P)(s)
We denote p' as the worst-case transition that satisties (C.33), then we have
P'(s) (8)eee - - V
inf ((P,n) pp 16-0"" up
Therefore,
Qh = rh +
sup u20,20..
(inf C(P, 11)) p
Fh inf (vEpg [e (1100)) w20,A20.r
up 1)
Fh inf (vEpp [e [e- -e--v-v Vo- v-1] + up 1-p-1) 7)
(C.34)
v20,g
= rh
inf (v In pg [e- Vv121] + vp). .00
(C.35)
where (C.34) holds because the result increases monotonically with respect to X, (C.35) holds by calculating the derivation with respect to 1) and thus setting -v( In [ (e-v- Va+1
We denote ū = argmin (v Epe [epee-r le- Vo+1] + up), from the strong duality, it is easy to infer that
#20
D7 in In [e -e- Vi+t1] + + < 0.
(C.36)
And since V4+1 S H, we have
Dln Epg [c- Vo+i]] -H.
(C.37)
Combine (C.36) and (C.37) into (C.35), we have i [0, #1. That is.
Qn = Th
inf (v In Epp -e-v VVi11] + up)) +00
Th inf (v le- Vo-s + up). velo
This finishes the proof.
24

---

Sample Complexity of Distributionally Robust Off- Off-Dynamics Reinforcement Learning with Online Interaction
Similar to Lemma C.2, we prove the optimism of estimation Q* and control Q' Q*+
Lemma C.12 (Optimism). If we set the bonus term follows
bonus (1 (1+ VH
2 (
(C.38)
pCmp
"A (s.a) V1
then for any policy x and any (k; 8,,,,,,00 8, E [K] x [H] x S x A. with probability at least 1 - 28, we have Q/ (8, a) 2 0% " a). Specially, by setting = xT, we have Q ( (s. a) 2 0% (s)
Proof. We prove this by induction. First, when h = H + 1, 2 h 11+1 (s. a) = 0 = -27 (8, a) holds trivially.
Assume Qhi1 a) 2 Qhf1 (s)a) a) holds, since nh is the greedy policy, we have
V (s) Qifei (s, (s)) Qh (s, (s)) Q (s, (8+1)())))) (x)
where the first inequality is because we choose n as the greedy policy.
Recall that we denote ohe as the optimistic estimation k-th episode, that is,
@ha (s. a) bonus (s, a) + (s, + inf KL(PIPP)SP
Ep Vi as)
We can infer that
2h - 0h = bonus + + +
inf KL(PHPP)s
Ep h+1ll - Thh
inf (L(PIP))
Ep BP(1
bonus & + + - rh +
Ep Bp(V/ii] inf PH)S
inf kL(PII)))
Ep [P[v h41
inf (L(PIIP))
Ep [V
inf kL(PIIP))
Ep Ep[V [V
> bonus
+ ph
+ inf KL(P)
Ep Ep [v
inf kI((P)))))s
Ep R4t1
(C.39)
bbonu
+ ph - rh
+
inf
(v Erg [e-v vv + up)
vE
inf (n lE [e - ( + up) vE(0. #1
(C.40)
bonus &
+ p/
rh +
inf vElu, #1
(v le- vv-e v wn Epg le-v (2-9))
bonus &
h
sup vE
v/ In Ep
[c 1 Pn [e
(C.41)
where (C.39) is from the induction assumption, we plug in the dual formulation Lemma C.11 in (C.40).
For term (i) in (C.41), from Lemma G.1 1 and a union bound, with probability at least 1 - 6, we have
(m(2SAH//0) 2n 1e--'ss.00 (s.a) V1
(p)(),)) - as)
(C.42)
for any h,, E [K] X [H] x SxX A.
To bound term (ii) in (C.11), we have
| In Ep --- 1221l] - v In Epp [E vv
sup vE(0, #1
25

---

Sample Complexity of Distributionally Robust Off- Off-Dynamics Reinforcement Learning with Online Interaction
Σ (P) - (8()) (145(()
sup rE #1
vln
1+
SES
Σ (6( ( (445(1)
SES
(s) - (3())) - (+)
Σ
sup
2v
SES
(C.43)
Σ ( - (
ME(0, 41
BES
(s) ((()))
sup
2
max SES,PR(s)FE
(C.44)
(s)
_ 1
2H
max
(i(() - (s)
(C.45)
PCMP
#ES
2H
|| 1Rll1
PCMP
2H
25 In (/)
(C.46)
pCMp
T (s, V1
for any (k, h, 8, a) E [K] x [M]] x A. where (C.43) is because In(1 + x) S 2/2r|. (C.44) follows from the Holder's inequality, noting that we have nh k-1 (s. a) when (s) 0 and thus PA (s) = 0 from (4.1), (C.45) uses Assumption 5.7, (C.46) from (C.14) and a union bound.
Apply the union bound again and combine (C.41) with (C.42), (C.46), the definition of bonus and induction assumption. With probability at least 1- 26, we have ( a) 2 2 (s, a) for any (k, s, [K] x [M] S x A. This completes the proof.
With similar proof to Lemma C.3, we can control the item Q* Q=*
Lemma C.13. For any k E [K], we can bound the estimation error as follows
H
Que -
E pp 1 --
[2bonus
h=1
Proof. From the proof of Lemma C.12, we see that
a)) - ar) +
inf KL(PIPRSPP
Ep [V[via (s, KL(PIPP)SP
inf Ep [V (s, a) s bonus (s, a).
(C.47)
Recall that we define pink
Ep BP(vTTi' h+1 the worst-case transition in Definition 5.3, we have KL(PIPP))
argmin
2 Q
bonus pk
inf (L(PPPP)SP
Ep [P[ViP [ Th PR)P
inf
Ep [VTT
2bonus & + inf KL(PPIPA)
Ep [V+[]] inf KL(PHPPRS [h wnt1l.
Ep [V
(C.48)
2bonus + E E .
(C.49)
where (C.48) uses (C.47). Apply (C.49) recursively, we can obtain the result.
Combine everything together the same way as the proof of Theorem C.10, we have
26

---

Sample Complexity of Distributionally Robust Off-Dynamics Reinforcement Learning with Online Interaction
Theorem C.14 (Restatement of Theorem 5.9 in KL--divergence setting). For CRMDP with (s, (eett--eca KL-divergence defined uncertainty set satisfying Assumption 5.5 and Assumption 5.7, with probability least 6, the regret of Algorithm satisfies
Regret = Ō ((1+
HVS pCMP
(C. Ct C
Proof. Setting 8' = =5/3 Lemmas C.4 and C.12, then with probability at least we get
K (Vi -17 ())
Regret
k=1
(VT Vilim)
(vi.P- ViT":O)
K
H
<
pb sppl [2bonus)]
(C.50)
k= h=1
K
(1+
2HVS
2 2In(2SAHH//0
2
E Suie a
(C.51)
pCmr
Th - (s.
==1k=1
HVS pCMP)
(Co + CI.StAAHK)
(C.52)
where (C,50) is the combination of Lemma C.12 and Lemma C.13, we plug in the bonus (C.38) in (C.51), (C.52) is from Lemma C.9.
C.3. Proof of Theorem 5.9 (Constrained x² Setting)
We first give the closed form solution of constrained x2 update formulation. This dual formulation has also been proved by Iyengar (2005, Lemma 4.2), but the rage of À in our result is more precise compared to theirs. Lemma C.15 (Dual formulation). For the optimization problem Qn(8, a) ()) inf have its dual formulation as follows
Er[Ve+1] a),
Q Th + sup
- A] (V
(C.53)
XE[O.H]
Proof. Consider the optimization problem
Q₂ = +
inf (P
Ep(Va+1] = + inf (PPP))))
Σ ((s)
SES
The Lagrangian can be written as
P(s) -1 1 -p) Σ (()) 1- PPs))
(1)
C(P.n) Σ (()) + Σ (s)
(3)
#ES
SES
SES
SES
We set the derivative of w.r.t. (s)) to zero
0C
P(s)
= (s+ + 2v
(s) -1) - AAss) + =
(C.54)
@P(s)
We denote P as the worst-case transition that satisfies (C.54), then we have
(s) = Ps()) (1 (s) - [A(s) + m)
2v
27

---

Sample Complexity of Distributionally Robust Off Off-Dynamics Reinforeement Learning with Online Interaction
1 (V)+1(6) - (A(s) + + - (Vi+i (8) - (A(s) + vl) up + 11-
inf inf ((P,)) - -Epp p
4v
Therefore,
Qn = Th +
sup
inf L(P: n))
v20.220.1
1
+ +up 11 m)
inf
Epp 4v
(V++1(s) - (A(s) + n1) (Vh+1(s) - (A(s) + +1)
=20.200.v
+ sup 220,220
Epp Vh+1 -A
Varry Var+z(Vh++ A) up
(C.55)
4v
Th + sup A
Epg Vh+1 X1 VoVarrg (Va+1 - -A)
(C.56)
Th + sup
PE [V4+1 >| (V -11441-1) 11).
(C.57)
AE[U.H]
where (C.55) holds by calculating the derivation with respect to 7 and thus setting = ==Epp[V4+1 - ^], (C.56) from the
basic incquality a- b > 2/ab, (C.57) holds because the result increases monotonically with respect to À when À 2 H.
Similar to Lemma C.2, prove the optimism of estimation Q' and control Q" -Q Lemma C.16 (Optimism). If we set the bonus term follows
25 In 1122
bonus -3H,
+ K
(C.58)
n V1
then for any policy and any (k, 8,a)) E [K] x [H] x S x A. with probability at least 1 - 35, we have ( a) 2 (s, a). Specially, by setting π = =,, we have kuP (s, a) 2 0% as,
Proof. We prove this by induction. First, when h = H + 1, 2 (s, a) 0 --t (8, holds trivially.
Assume Qhif (8, a) 2 2hif (s.a) holds, since * is the greedy policy, we have
h44 (s) Qhe (s. The (s)) of (s, (s)) ( (s, (s)))())) V,41 (s),
where the first inequality is because we choose x as the greedy policy.
Recall that we denote oh the optimistic estimation in k-th episode, that is,
(s, a) bonus (s, a) (s,
inf (PPIPP)ss
Ep /V/e (s)
We can infer that
Q QT = bonus & + p/ + inf
Ep [hhp -hh-
inf (P
Ep [V
x² (P
bonus
pt rh inf ((P
Ep [v
inf (((l)())s
Ep [V+.]
inf Ep x((P)Pp)S b & px rm inf (P
Ep [VEP]] + inf {²(P((P))
Ep [v(4
inf (P
Ep [v[4]]]]
(C.59)
bonus + rm
sup A1
Epp Wit >]
VoVarpy (V - 1)
28

---

Sample Complexity of Distributionally Robust Off- Off-Dynamics Reinforcement Learning with Online Interaction
sup AE(O,
PE
V h+1
>)
VVaarp (V 2)
(C.60)
bonus r th inf
{
(k V -11 pVarrpu pu (V A)
- [Krg [Vi4] - >]
VaVarpy (Vit2 - -2)}
bonus
| -ral sup xE
pE h+1 >] v /Varrp (Vitte - 2)
Ppgl
^|
par (V - -21)
h+1
bonus
/2
hh rh
sup X
E Vilu >) -Epg [itta - A|
Varrng (V 2)
sup XE(O.11
V Varpy (Vi42 >)
(C.61)
(ii)
where (C.59) is from the induction assumption, we plug in the dual formulation Lemma C.15 in (C.60), (C.61) is because sup (x) + sup g(x) 2 sup(f (x)).
For term (i) in (C.61), from Lemma G.I and union bound, with probability at least 1 - 6, we have
In(2S 2n k-
(1)),))) rr(s,a))
(C.62)
(
V1
for any h,,), E [K] x H SSAA A.
We denote V(A) Vkpp- - X E I- c-net (c) for V. From Lemma G.4, it holds that In [Nv(e)) s 1S| In (3HHec). Then follow the same proof as (C.17), with
and V= (V e R V I H}. To bound term (ii) in (C.61), create
probability at least 1- - 8, we have
sup A
E h+1
X] - Bpp [V44
sup VeNv(()
E V
E pp.
[V]
+ 2e
25t In (15
S H
(C.63)
K
nb.
for any (ki, 11, 8, a) E [K] x [H] x S x A.
For term (iii) in (C.61), by the definition of Myr(),, for any fixed V, there exists a V E NN(cc) such that VIV that is
V' S
v (V) Varpy (V)
(V)
VVarpg(V) Varr: (V1) Varp: / Var pa (V')
+ V Var (V') / Var (V)
|Vargg (V) - Varpa + | (arpg(V'') Varpy. (V')
Varpy (V') - Var (V)
EPP VV2 - 222 + / EB [V] Eznn [
Epy V222 V2 + pa [V' - B2 [V]
Varp:(VV)) (Varpe(V"))
Varpp((V)) (V') + 44/21l
sup v'Evv(e)
IV /Vrr:((V')- (Var + 4V2HH,
(C.64)
29

---

Sample Complexity of Distributionally Robust Off- Off-Dynamics Reinforcement Learning with Online Interaction
where the second inequality follows from | v
S v | y) and the third inequality follows from vo+y v vi.
For any fixed V. we apply Lemma G.2 and have
I 2mm(2/)
v Varrg(V) - v Var (V)
(C.65)
n k-1
V
with probability at least 8.
Then with probability at least 1 - 8, we have
sup AE
Varpa (Vitt 2) -v Varpy (V - 2)
2 sup Ac(O.
Varpg (V / Var (V
Varrg(VV Var (V) +4V2He (C.66)
sup VENv(c)
2I(22AH (N)(C)/ + 4VE
(C.67)
n
25 In (6SAH K (6))
H
+ 442
V1
25 11
H
(C.68)
K
Th
for any (k., h, s, a) E [K] x [M] x A, where (C.66) follows from (C.64), (C.67) from (C.65) and a union bound, we set = in (C.68).
Apply the union bound again and combine (C.61) with (C.62), (C.63), (C.68), the definition of bonus and induction assumption. With probability at least - 30, we have 2 (s,a) a) 2 1 This completes the proof.
(s, a) for any (k, h, s, a) E [K] x [M] S x A.
With similar proof to Lemma C.3, we can control the item Qh Qn* Lemma C.17. For any l E [K], we can bound the estimation error as follows
Q -
[pp y
22bonus p.
h=1
Proof. From the proof of Lemma C.12, we see that (h, a) (r(s +
inf (PIIPPS
Ep
inf (PPPPPS)
Ep [V (s, a) < bonus (s.
(C.69)
Recall that we define pick
Ep V []] as the worst-case transition in Definition 5.3, we have SP
argmin
Qh O bonus & + r/ +
inf (PPP)P))
Ep Thup
Th
inf (PPPPP)S
Ep V
2bonus inf (
Ep [V
Ep [Va""[]] ((
inf
(C.70)
2bonus Epp ,
1++1 Qu"i]].
(C.71)
where (C.70) uses (C.69). Apply (C.71) recursively, we can obtain the result.
30

---

Sample Complexity of Distributionally Robust Off- Off-Dynamics Reinforcement Learning with Online Interaction
Theorem C.18 (Restatement of Theorem 5.9 in --viieegee setting). For CRMDP with (s, re-ettnggull x divivergeecce defined uncertainty set satisfying Assumption 5.5, with probability least 1 6, the regret of Algorithm satisfies
Regret O AH2 A
Proof. Setting 8' = 5/4 Lemmas C.4 and C.16, then with probability at least ō, we get
K
Regret
(V
()
E (v - -v-D-
Σ
(V 1/5
k=1
E
Ppmn .pp
22oons
(C.72)
K
H
25 In (19192SAHHA K3/6)
pauk
3H,
(s, V1
+ K
(C.73)
k=
1=1
S
S
AI
A
(C.74)
where (C.72) is the combination of Lemma C.16 and Lemma C.17, plug in the bonus (C.58) in (C.73), (C.74) is from Lemma C.9.
D. Proofs of Results in Regularized RMDPs
D.1. Proof of Theorem 5.16 (Regularized TV Setting)
We first give the closed form solution of regularized TV update formulation. This dual formulation has also been proved by Panaganti et (2024), but our formulation is more concise.
Lemma D.1 (Dual formulation). For the optimization problem Qn(s,a) = rn(s,a)
inf PEA(S)
(Ep[Va+1] +
(TV(P))P)) (s, a), we have its dual formulation as follows
Q Th Epg
[ min wEe
( Voti(6)) . + SES (s) (s)+ + 3).
min
(D.1)
Proof. Consider the optimization problem
Qn Th
inf PEA(S)
( (TV(P1)P))
(P((8) ))
P(s)
inf PEA(S)
Σ P(s) BP)(s)
Pp(())
SES
where v0() = |6- 11/2, and then the Lagrangian can be written as
(8) P(s)
\(())((s) (1(0)))+((11D)) (P))(s))
[(P,n) = > P(s) +
Σ
(s)))
sES
SES
eES
aES
We denote g(s) P(s)/ (s), then have
inf L(P,)) sup Σ P + +1) - Vs) -Bp(((s)]]]] +
p
NES
-3 40" (A(s)) + +n (()(S)+))
Viti(6) +
B
31

---

Sample Complexity of Distributionally Robust Off- Off-Dynamics Reinforcement Learning with Online Interaction
where the second equation is from the definition of dual function (²(v) sup(y' xx spx)).
So we have
Qn = Th + sup X20.9
(inf [(P.))) P
(A(8) + 1) - Va+1(s) ]] -11)
r/ inf
HE 8
(A(s) + + - -V)+1(8) - - 1
1T
inf Ma)+n V(+t(()) 57
[EPR
max
(D.2)
|
A
Epp (A(s) + V+++(()) + 9) ] -1 1 3
= Th
Xaa inf
2
2
A20.0.
=
Th
X20 A(a)+ay Va+1())58 (Epz (A(s) + -V)+1 - nn)
inf
(D.3)
=
Th inf
(Epg - (++1 [}] -n/)
(D.4)
min (s) + 3 - Vi+1(s)), |] + ( min Vh+1 (s) + +)) .ES
= Epp
(D.5)
$ES
where (D.2) follows from the definition of 4-* (C.2), redefine n/ 1 2/2 in (D.3), (D.4) holds because the result
increases monotonically with respect to X, (D.5) holds because the result increases monotonically with respect to n/. L
Similar to Lemma C.2, we prove the optimism of estimation Q' and control Q* -Q+.
Lemma D.2 (Optimism). If we set the bonus term as follows
25 (51((2SAH//0)
(onus 2H,
(D.6)
k-
(8,
then for any policy and any h,, E [K] x H S x A, with probability at least 1 - -25, we have 2h (s.a) a) 2 Q a). Specially, by setting क = x², we have Q (s, a) 2 Q% (s)a).
Proof. We prove this by induction. First, when h H 1, t (s. 0= Q7 (s, a) holds trivially.
Assume ( a) 2 2 (s. a) holds, since nh is the greedy policy, we have
(s,
V (s) = 2 h+1111 (s. Th+ 2 k.B
h++ (s. (s)) 2 2741 (s))s))) Vr
where the first inequality is because we choose & as the greedy policy.
Recall that we denote hh0 as the optimistic estimation in k-th episode, that is,
(s, a) = bonus a) + (h(, a) + inf
(Ep Wiill + (T
PEA(S)
We can infer that
Qt k - QT.
& + ph + inf bonus /
(Er [Br[v/ h+1 + (PI(P))) - Th - inf
(Er + (PV(P))))
PEA(S)
PEA(S)
bonus & + pt: rh + inf PEA(S)
(Ep (Ep[V + STV STV
inf
(Ep +TV
PEA(S)
+ inf PEA(S)
(Er (Er[ 1+1 + (PT(())))
inf PEA(S)
(Er [ + BTV
32

---

Sample Complexity of Distributionally Robust Off- Off-Dynamics Reinforcement Learning with Online Interaction
bonus & + + .h PEA(S)
inf
(Ep
Ep (V
+ inf (Ep (Bp|V h+1l + STV Pk)) PEA(S)
inf PEA(S)
(LEp
h+1 + [ +TV
(D.7)
2 bonus, & + 5% r/ + inf PEA(S)
(Ep V + (PV(()))P))
inf PEA(S)
(Ep + (TV(P))PR))
(D.8)
= bonus t + tr - rn Epg
min $EB
v. h+1 (s) + Veri (8) )m] +
min v (s) +3) #ES
+ Epp. (
min V/hta (6) + 3 SES
k (5) 1
min V
v (s) +
(D.9)
SES
bonus
& n + p
- Epp
min V R SEB
h+ (s) + 8 - whi (s) [ + +Bpt
(
min vk. (s) + - SEB
- V (s)
c bonus
//
hh Th
pg
min h+i (s) 3 v (s)
]
pp
min V (s) + V 3. SES
SES
(i)
(D.10)
where (D.7) is from inf [xx inf g(x) 2 inf(f (x), (D.8) is from the induction assumption, we plug in the dual formulation (D.1) in (D.9).
For term (i) in (D.10), from Lemma G.1 and a union bound, with probability at least - 6, we have
In (2(2S/HK/))
(+) rs(s,))) <
(D.11)
V
2n k (8,
for any h,, s, a) E [K] [M] A
For term (ii) in (D.10), follow the same proof as (C.14) and union bound, with probability at least 1 5, we have
Egg min
( v/ v++((s)) E Epp
(min (min
(
(
(2) ]
S V
25 2S1n(2SAHK/0)
SES
V
(D.12)
for any (k. h, s, E [K] H S A.
Apply the union bound again and combine (I.11) with (D.11), (D.12), the definition of bonus and induction assumption. With probability at least 1 - 28, we have (f:i((s,, a) 2 "x a) for any (k, s, E [K] x [M] S x A. This completes the proof.
With similar proof to Lemma C.3, we can control the item Q² Q**
Lemma D.3. For any i E [K], we can bound the estimation error as follows
Q -
E
(p & o
2bbous
Proof. From the proof of Lemma D.2, we see that
()(),a) ra(s, a)/ +
inf PEA(S)
(Ep
[ Pk. h+1 + (TV())
inf PEA(S)
(IEp k. + STV (VV (s, a)l s (s.
(D.13)
33

---

Sample Complexity of Distributionally Robust Off-Dynamics Reinforcement Learning with Online Interaction
Recall that we define
h
argmin PEA(S)
[V 1+1 + (PT(())))P))
the worst-case transition in Definition 5.3, we have
2h 0% -r 3- bonus & + ph + inf rEA(S)
(Er [Er[] h+1 + (TT((()))))))
inf PEA(S)
[Br[V44] 1f + (TV(P))
S 2bonus + inf PEA(S)
(Er V++11 (TV P?))
inf PEA(S)
(Er
[Br[Viti .81 h+1 (TV
(D.14)
2bonus + E pyn . 1 --
(D.15)
where (D.14) uses (D.13). Apply (D.15) recursively, we can obtain the result.
Theorem D.4 (Restatement of Theorem 5.16 in TV-distance setting). For RRMDP with (s, reettangga TV-distance defined regularization term satisfying Assumption 5.5, with probability at least 6, the regret of Algorithm I satisfies
Regret (C.r AH + SAAHA'
Proof. Setting 8' = 5 in Lemmas C.4 and D.2, then with probability at least 1 - ò, we get
K
Regret-
(VT
VT 3
(vr - V/l.0) + Σ
(V
V/+
k=
k=1
k=1
2bonus
(D.16)
K
H
(2
2
2H
(D.17)
Th
(s V1
k=1
1=11
=CC... AH Ca
HP
(D.18)
where (D.16) is the combination of Lemma D.2 and Lemma D.3, we plug in the bonus (D.6) in (D.17), (D.18) is from Lemma C.9.
D.2. Proof of Theorem 5.16 (Regularized KL Setting)
We first give the closed form solution of regularized KI. update formulation. This dual formulation has also been proved by Panaganti et al. (2024), but our formulation is more concise. Zhang et al. (2024) applied the equivalence between regularized RMDPs and risk-sensitive MDPs obtain the same result, which is different from our proof.
Lemma D.5 (Dual formulation). For the optimization problem Qn(s,a) = (n( + inf (Ep[Va+i] + PEA(S)
(KI(() (s, a), we have its dual formulation as follows
Qn = TI - 3 pg a-- ---Va-
(D.19)
Proof. Consider the optimization problem
Qn rh +
inf PEA(S)
(Er[Va+1] (KTT
Σ P(s)Vo+1 3P(s) In P(s)
Th + inf PEA(S)
pp(s)
The Lagrangian can be written as
(s) )
P(s)
Σ Ass) + (1
C(P,n)= Σ
(S)
SES
RES sES
34

---

Sample Complexity of Distributionally Robust Off- Off-Dynamics Reinforcement Learning with Online Interaction
We set the derivative of w.r.t. P(s) zero
0C aP(s)
P(s) (R((s) + B - (A(s) + n) = O.
Vh+z(8)+ + B1n
(D.20)
We denote P as the worst-case transition that satisfies (D.20), then we have
P'(s) (s)e
(D.21)
inf ((P.n) -3EPpl - (169)))))) n
p
We have
Qn = rh + sup
(inf C(P, 11))
\20,1
P
= Th inf (3Epg e - -0- Vo++(00+ (D(00))0) - -n) A20
Th inf (gErg le (V -Vh+1(0)43---111 -n) 1)
(D.22)
Fa 3 In Epp. (e- -e---ta VVVVa.
(D.23)
where (D.22) holds because the result increases monotonically with respect to X, (D.23) holds by calculating the derivation with respect to 17 and thus setting -3 In [p [c- !Va11] -1i1)-1).
3
Similar to Lemma C.2, we prove the optimism of estimation Q and control Q" - Q². Lemma D.6 (Optimism). If we set the bonus term as follows
(s, = + 3 Be H
3H 15)
2 In ln(2SAH//)) (s. V1
(D.24)
then for any policy ग and any (k, h, a) E [K] x [H] x S x A, with probability at least 1 - 25, we have Q (8, a) 2 Q (s, a). Specially, by setting π = x², we have Q (s, a) N Q% (s,
Proof. We prove this by induction. First, when h H + 1, Q 3
3 H+ a) 0 QH++ 17,41(s,0) (s,a) holds trivially.
Assume (s, 2 2h: (s, a) holds, since x is the greedy policy, we have
v v (s) = k. (s. th (s)) 2 Q (s, (s)) 2 2f (s, (s)) = VT
where the first inequality is because we choose - as the greedy policy.
Recall that we denote thri² as the optimistic estimation in k-th episode, that is,
2 (s, a) bonus a) + a) + inf PEA(S)
(Ep [E[[V] + (KL((P)P)) (s)
We can infer that
Que - -TT B
b $o + ph + inf
(E, [V + (KL((P - -Th inf
(Er [1 h+1 + (KL
PEA(S)
PEA(S)
bonus R + pt Fh +
inf PEA(S)
(Ep [V SKL((P|(P)))
inf PEA(S)
(Ep kv + 9KL (P| P()P))
inf PEA(S)
(E, (V. k
+ SKL (PIIP))
- inf PEA(S)
(Er (Er[V + KKL (P((P)
h+1
35

---

Sample Complexity of Distributionally Robust Off- Off-Dynamics Reinforcement Learning with Online Interaction
bonus & + + rh PEA(S)
inf
(Epp
EPp (V++1))
inf PEA(S)
[10[[V k.
h+1
+ 3KL
[|| Pl))
(Lep [EP[VAAT + (KL((IIPP)) PEA(S)
inf
(D.25)
bonus A + ph rh + inf PEA(S)
(Ep [ (.3 (KI((I)PP))
inf PEA(S)
(Ep [+11l + (P] PR))
(D.26)
bonus,, & + 5/ - Th + B In pg (e 8 v [ati - 3 In pp [e [
(D.27)
bonus A
rr Tme B In In pic - v In Bpp 88 v++]]
(D.28)
(1)
where (D.25) is from inf f(x) inf g 2 inf(J - (x), (D.26) from the induction assumption, we plug in the dual formulation (D.19) in (D.27).
For term (i) (D.28), from Lemma G.1 and a union bound, with probability at least 6, we have
a) (s, - (n(2SAHK/8)
(D.29)
2n, (
for any (k., h, 8, E [K] X И x A.
For term (ii) in (D.28), following the same proof as (C.14) and union bound, with probability at least 1 - 8, we have
25 251n(2AHK//))
In pg [e-D WWll In Erg [e v S e 'H
(D.30)
1 k-
V
for any (k, s, E [K]
H A.
Apply the union bound again and combine (D.28) with (D.29), (D.30), the definition of bonus and induction assumption. With probability at least 1 - 26, we have Qf: a) 2 " a) for any (k, h s, a, E [K] x [M] x S x A. This completes the proof.
With similar proof to Lemma C. 13, we can control the item Q+ Q=*
Lemma D.7. For any E [K], we can bound the estimation error as follows
H
- 2
<
pp " W
2bonus
Proof. From the proof of Lemma D.6, we see that
F a) (n(s,a) a)l +
inf PEA(S)
(E (Er [v/4]] + (KL (PIP))))
inf PEA(S)
(Ep
+ +KL P (s. < (o,
(D.31)
h+1
Recall that we define pm argmin (Ep PEA(S)
R. + (PL( as the worst-case transition in Definition 5.3, we have
k.
0h r / & + pt + inf PEA(S)
(Ep [VAL]]]
h+l + +KLK (PI
inf PEA(S) (Er[V (KL(P))
2bonus
inf PEA(S)
(Ep (V h+1 + (KL(PI
inf PEA(S)
(Ep [ETT Nti (KL(PIIPP))
(D.32)
2bonus/; IE sh 1141 - QF
(D.33)
where (D.32) uses (D.31). Apply (D.33) recursively, we can obtain the result.
36

---

Sample Complexity of Distributionally Robust Off- Off-Dynamics Reinforcement Learning with Online Interaction
Theorem D.8 (Restatement of Theorem 5.16 in KL--divergence setting). For RRMDP with (s, -rectnuucaa KL-divergence
defined regularization term satisfying Assumption 5.5, with probability at least 6, the regret of Algorithm 1 satisfies
Regret ((11 Be "
C Sà (bHvK))
Proof. Setting 8' = 5/3 Lemmas C.4 and D.6, then with probability least 6, we get
K
K
Regret-
(Vi B vith
=
(vi - v/h10) + Σ
(v
Vi vitt.)
k=1
E
pir
[2honus
(D.34)
k=
K
H
(1+ Be
3e SS "V)))
2 (m(225HH//))
2
(D.35)
nh (s,
k=
= =((1 + Be
H
+ C. S A
(D.36)
where (D.34) is the combination of Lemma D.6 and Lemma D.7, we plug in the bonus (D.24) in (D.35), (D.36) is from Lemma C.9.
D.3. Proof of Theorem 5.16 (Regularized x² Setting)
We first give the closed form solution of regularized x² update formulation. This dual formulation has also been proved by Panaganti et al. (2024), but our formulation is more concise.
Lemma D.9 (Dual formulation). For the optimization problem Qx(s,a) = rn(s,a) rEa(S)
inf
[Er[Va+1] +
(p)P)) a), we have its dual formulation as follows
Qh TA + sup pE Vh+1 ^|
Varp:(Vn+1 (Vh+1 A)).
(D.37)
XE(o.
43
Proof. Consider the optimization problem
Qx = + inf PEA(S)
P(s)
- )
= rh + inf
Σ
P(s)V + 3P
pp(s)
PEA(S) sES
The Lagrangian can be written as
P(s)
1)1 {(s) + (1-EP(s) (())P)))((I-E(((s))
1 27
C(P.n) Σ (S)
(
SES
We set the derivative of L w.r.t P(s) to zero
0c
P(s)
(s+ +
(s) -1) (A(s) + + =0
(D.38)
0P(s)
We denote P' as the worst-case transition that satisfies (D.38), then have
('(s) = (s) (1- Vh+1 (s) - [A(s) + m)
(D.39)
23
37

---

Sample Complexity of Distributionally Robust Off- Off-Dynamies Reinforeement Learning with Online Interaction
inf ((P,)) - -Bpg 1
4/3 (Vo+i(s) (A(s)
()(>)) + +n) - (V)+1(s) - (A(+) + +nl)) + v.
P
We have
Qn rh + sup (inf [(P,n))
X20,n
Epg 43 (Vi+2(s) - (A(s) + =n))²= -(Vn+1(s)- [A(s) (((()) ((s))+nl)]) +n]] - -n)
= rh
inf X
rh + sup X20
Erp Vh-1- - ->] 43
Varpg (Va+1 (6611-1) -21)
(D.40)
Var (Vi+1 (V - 21).
rh + sup XE(O.H]
Epp Vh+1 >|
(D.41)
43
where (D.40) holds by calculating the derivation with respect to n and thus setting 7 = Erg ErglV/+1 - A], (D.41) holds because the result increases monotonically with respect to À when X 2 H.
Similar to Lemma C.2, we prove the optimism of estimation Q' and control Q* Q" Lemma D.10 (Optimism), we set the bonus term as follows
25 (344SAAFF33 /5)
2
bonust((s,)) a) 5/12
(D.42)
1 (s, V
K
then for any policy ग and any (k, h 8, E [K] x [H] x S x A, with probability at least 1 - 35, we have ( () h (s, a). Specially, by setting π = x², we have hh (s, a) こ 0% (s.a).
(8,
Proof. We prove this by induction. First, when h = H + 1,
H+1 ( (s a) 0 Q7 (s, a) holds trivially.
k.
Assume (s.
(s.1 a) 2 2 (s, holds, since nh is the greedy policy, we have
V (s) Qhif (s. th+n (s)) 2hu (s, (s)) Q (s, (s)))(())) (s))(s),,
where the first inequality is because we choose ² as the greedy policy.
Recall that we denote Qha the optimistic estimation in k-th episode, that is,
2 (s, a) = (s, a) + as) + inf PEA(S)
(Ep[V + (
We can infer that
Q 27. bonus & + p/: + inf
(Ep [VA + BX (PIIPA))
inf PEA(S)
[EP[V + +xx (PI)P))
PEA(S)
bonus + P/z - Th +
inf PEA(S)
(Ep [v..8 + 3x (PIIP))
inf PED(S)
(Ep [ V
h+1
+ Bx (PI PX)
inf PEA(S)
EE V + x (P(IP))
inf PEA(S)
(Er
(V h+1
Bx2 2
2 bonus + p/
Th + inf
(Ep [v Ep [VTVA]]]]
PEA(S)
inf PEA(S)
(E [vh1f] + xxx (PII - inf
(Er (PI(P))
(D.43)
PEA(S)
2 bonust, + -/. Th. + inf PEA(S)
(Ep [V + (PI(()))
inf PEA(S)
(Er [Er[VA + (PI
(D.44)
38

---

Sample Complexity of Distributionally Robust Off Off-Dynamics Reinforeement Learning with Online Interaction
bonus K r% Th + sup AE(0,
V >1
1
Var pi (V A))
4,3
1
sup AE
(Epg [h+11 - >]
Varpg (v/ - 2))
(D.45)
43
2 bonus * + p/ Th + inf
{
- 21
Var pm (V 2))
XE|O,
1+1
43
- (Epg [ A1
Varpy
=))}}
4/
P
h-1
bonus A: - 1 rm - sup
(E p.
h-1 - X]
Var pa h+1 - -)))
XE [
43
[g [V >]
Vg h--1 2))1
4
bonus
jo rm
sup X
[ h+1
>]
Epg.
[V
h+1
2]]
(
(i)
1 sup
Var (Vr+t >) - Varpe ( (v
2)1
(D.46)
4,3
(E(U,H]
(ii)
where (D.43) is from inf f(x) inf g(x) 2 in - (z), (D.44) is from the induction assumption, we plug in the dual formulation (D.37) in (D.45).
For term (i) in (D.46), from Lemma G.1 and a union bound, with probability at least 1 6, we have
In(2S 2n - (s)
(s, rs)s)a))=
(D.47)
for any (ks, s, a) E [K] X [M] x X x A.
To bound term (ii) in (D.46), following the same discussion as (C.63), with probability at least 6, we have
sup A
Epe
V
A] Epp [vir
Al s
sup VENv(r)
Epg
[V]
Epa [V]
2c
25 In 125 AH
< H
(D.48)
th
v 1
K"
for any (k, E [K] x H x A
We denote V(A) V x E | H, H] and == (V E R [ < H.. To bound term (iii) in (D.46), we create a e-net Ne)(e) for V. From Lemma G.4, it holds that In (Ni((e)) < [S| (3H/ee..
Therefore, by the definition of (e),)), for any fixed V. there exists V E (N) such that V V'll S e, that is
Varpg Var pp (V)l < Varrg (V) Varrg (V') + Varyg ( (V') Var (V'I + Var (V') Var (V)
Epg [ V + P [V] B3 V'] + |Bpp V22 V2] + 7 [V'] W [V]
Varpg (V') - Var p. (V')
< Varp; (V') - Var (V'I + SHE
sup veN
\Var - Varp. (V'I 8He.
(D.49)
For any fixed V. following the same analysis (C.14), we have
\arr (V) - Var (V)] = (Epg l | - ( - pe -E [V])
39

---

Sample Complexity of Distributionally Robust Off- Off-Dynamics Reinforeement Learning with Online Interaction
Epp
[V?]
E pp
[V]
[V]
2S
22/0))
112
+ (1ppg [V] + Bp [V]) |Bpr[[] pp
[V]
n/ V1
(2/8)
(2
I H²
+ 2H²
n/-1 V1
n
--1
25 In (2/6)
S 3H²
(D.50)
"h V1
with probability at least - 8.
Then with probability at least 1 - 8, we have
sup H
Varry (Vi+1 >) Varrg (V
A/1
sup AE[O,H]
Varp. (V(Pp)((A))))))) Var (V()))
s sup VENv(e)
Var (V) - Var (V) + 8Hc
(D.51)
25 ln5 AH AHK//1)/
< 3H²
+ 8He
(D.52)
n v1
2.2h 2H6SAH2K/eD &HHe
S 3122
V1
2.5
A /0)
312
(D.53)
K"
1/
for any (k, h, s, a) E [K] x [H] x S x A. where (D.51) follows from (D.49), (D.52) is from (D.50) and a union bound, we set SHK in (D.53).
Apply the union bound again and combine (D.46) with (D.47), (D.48), (D.53), the definition of bonus and induction assumption. With probability at least - 36, we have (s. a) 2 Q7 a) for any (k, h, s, a) E [K] x [ 8 x A. This completes the proof.
With similar proof Lemma C.3, we can control the item Q' Q=* Lemma D.11. For any &s E [K], we can bound the estimation error as follows
Q - 1
S
(p p +
2bonus k
h=1
Proof. From the proof of Lemma D.2, we see that
(h a) - (n(s,a)) a) +
inf PEA(S)
(Ep [V [+ + + (s.
(D.54)
inf
(Ep
k. h+1
3x (PII (s, a)) < (s, a).
(D.55)
PEA(S)
Recall that we define pick argmin
(Ep (v + x (PI as the worst-case transition in Definition 5.3, we have
PEA(S)
kB
0% x = b & + p/ + inf PEA(S)
(Er
h+1
+ 8x (PI rh
inf PEA(S)
(Ep V h+1 + + + (P))
< 2bonus + inf PEA(S)
(Br[v + + (Pl P?))
inf PEA(S)
(Er (Er _9 h+i + 8x 2xx
(D.56)
40

---

Sample Complexity of Distributionally Robust Off- Off-Dynamics Reinforcement Learning with Online Interaction
=2bonus & + E pp ., [Qh+1 Qu+i
(D.57)
where (D.56) uses (D.55). Apply (D.57) recursively, we can obtain the result.
Theorem D.12 (Restatement of Theorem 5.16 in <é-diveree setting). For RRMDP with (s, reeetangaa divergeeee defined regularization term satisfying Assumption 5.5, with probability at least - 6, the regret of Algorithm satisfies
Regret O AH CA
Proof. Setting 8' 55/4 in Lemmas C.4 and D.10, then with probability least 8, get
Regret-
(V
(vr - Vilie) + Σ
(V
1i
Arm
km
$
E
pr .ank
[2bonus
(D.58)
K
H
25 A K2 K2/6)
2
2
Σ
E
puuk
5/²² 2
Th
(s V1
+
K
(D.59)
k=1
1=1
S AH
S3 ((HKK)
(D.60)
where (D.58) is the combination Lemma D.10 and Lemma D. 1,, we plug in the bonus (D.42) in (D.59), (D.60) is from Lemma C.9.
E. Proofs of Results in Lower Bounds
E.1. Proof of Lower Bounds on the Regret
p ((pa).11)
p'
r N (u(()) 1)
$1
$1
1-p
1-p
T=1
(a) The nominal RMDP. (b) The perturhed RMDP.
Figure Constructions of the nominal environment and the worst-case environment in the proof's regret lower bounds, the value on each arrow represents the transition probability.
Theorem E. (Combination of Theorem 5.12 and Theorem 5.18). For CRMDPs with TV, KL and x2 divergence defined uncertainty sets and RRMDPs with TV, KI. and x² divergence defined regularization terms, for any learning algorithm &, there exists RMDP M satisfying Assumption 5.5, such that Regret (S, K) ((C..K).
Proof. The proof here follows the high level idea Lattimore & Szepesvári (2020, Theorem 15.2). We consider two RMDPs Mj and Mg, as illustrated in Figure where /1 2, {31, 52, 83} and A {a), .2. AIiii. The only difference between these two RMDPs is the mean reward at $2. $1 is always the initial state, and can transit to 82 with fixed probability and with fixed probability 1 p regardless of the action. We assume that K > IA and 2 A//K to facilitate the constructions, this bound becomes loose as K grows large.
The agent receives a reward drawn from unit normal distribution, r ~ (p(a)), 1), at state s2, and a fixed reward r = state 83, where ((a) E [0, 1). This choice of ((a) ensures that the robust value function satisfies V*.P(>2) < Vx

---

Sample Complexity of Distributionally Robust Off- Off-Dynamics Reinforcement Learning with Online Interaction
implying that the transition probability from 81 82 will not decrease in the worst-case environment compared the nominal environment. In M1, the mean reward vector at 82 is given by 141 (A,0,-. E TRl and A < 2 is constant to be specified.
We introduce some notations that will be useful in the following discussion. The agent follows a learning algorithm & and, in the k-th episode, selects a policy n² to interact with the environment and collect a trajectory (o", a² r²), where of denotes the state to which the agent transitions from 81 after taking an arbitrary action; a² denotes the action the agent takes at step 2, i.c., state $2 or $3i and r denotes the corresponding reward received at $2 or $3, all in episode k. The joint distribution over the trajectories collected across all K episodes, {(o*, a", r* ))==>
"")] induces a distribution denoted by P..
The random variables corresponding to oR a², rk are denoted by 0 A R² respectively. We use Ey to denote the expectation under 17. As similarly noted by Auer et al. (2002), it suffices to consider deterministic strategies without loss of generality. Let Sy (K) denote the number of episodes in which the agent selects action aj if visiting state 82 according to the learned policy
K 1100= -
=ag
(E.I)
k=1
and let (K) denote the number of episodes in which action aj is actually taken at state 82,
K T2KK = 11fo = 82, A = =az].
(E.2)
We set argmin (n)) as the least chosen action (excluding 01) under environment M1. Since the expected number j>1 of times the agent transitions from 81 82 over K episodes is Kp, and given the selection of it follows that
Kp En]T(()) - |A| - 1
(E.3)
We now define the mean reward at 82 in environment M2 as
122 (A, 0, 0, 24, 0, ,.) o-th
That is, (2(aa)) = ii (az) for all j + e and u2(a)) = 24. Clearly, the optimal policy at state 82 selects action ai in Mi and action 0₂ in M22
Recall the definition of Cur in Assumption 5.5 and the visitation measure notations introduced in Definition 5.3. Since the visitation measure 81 is always 1, and the visitation measure 83, which is equivalently the transition probability from 81 to $3, does not increase in the worst-case environment compared to the nominal one, the maximum visitation measure ratio can only be attained at state 82. In the nominal environment, the visitation measure to 82 is d ($2) = - for any policy In the worst-case environment of M₁. let p max (s2) denote the maximum visitation measure to $2, that is, the largest transition probability from $1 to $2 across all policies, under both the CRMDP and RRMDP settings. In what follows, we show that this value p remains unchanged in M2-
To proceed, we present the following lemma, which provides lower bound the sum of the total regret in environments Mj and M2.
Lemma E.2. For TV, KL and x2 divergence defined CRMDP and RRMDP settings, there exists a corresponding constant Ç such that
E Regret M, (E + Regret M, (E, (M, K)] 5 5 5- exp ( KL (PP, PP) KA.
(E.4)
for CRMDP settings, for RRMDP-TV setting, for RRMDP-KL setting, for RRMDP-X setting.
where ==
8[1+
16
42

---

Sample Complexity of Distributionally Robust Off- Off-Dynamics Reinforcement Learning with Online Interaction
We present the following lemma simplify the expression for (PI,P,,Pg) Lemma E.3. For the distributions Pf and P2 the following property holds:
KL(
Σ
(R]])(K]]KKL) (L (v2,0)); P (722()));))
(E.5)
where (K) defined in (E.2).
From the construction of reward function, we can simplify (E.5) as
|A
KL (P,,
Σ
E (K)]
KL(CM, (M2)
-E]]T(()]
1),
2^7 [K)]
(E.6)
(E.7)
A 1
where (E.6) follows from Lemma G.7, and (E.7) applies the result of (E.3).
We now return to bounding (E.4). By plugging in (E.7) and setting to the given range of K and p. we obtain
v(1 1)/(4Kp), which satisfies 1/2 due
2 max { Regret (5, K)], E Regret (5, K)]}
2 E Regret (5, K) + Regret (5. K)]
Ç p exp
KL P2)
KA
24 K
2 p exp
KA
AA
e 1 V/D
20
Cir((AA 1)K
(E.8)
2
=( VK).
This finishes the proof.
E.2. Proof of Lemma 5.14
To establish the results for hard instances, we instantiate the constructed example in Theorem E.1 by appropriately selecting the nominal transition and the uncertainty set radius We assume that K > 22| |A| throughout the proof.
For TV-distance. We set p= 2 > JA/K K and p = 2. First, we solve the worst-case transition in the first step explicitly. Follow the definition of TV-distance, have
T = argmin p' ('V + (11
(E.9)
V'
s.t. p' PS-p
Since (E.9) decrease monotonically with F. the solution of this optimization problem is 5 p- p Cu, p/p 22
2
Therefore,
From (E.8), we see that the expected regret for constructed environments Mi and M2 satisfies
max (E [Regggr (E. B(egret Regret M, (5, K)]] 2 Ω E / C (IAI 1)K = -12(21-1
This finishes the proof.
43

---

Sample Complexity of Distributionally Robust Off- Off-Dynamics Reinforcement Learning with Online Interaction
For x² 2 d'-divergence. We set p क 2 |A/K K and p 12a -1 step explicitly. Follow the definition of divvergee,e,, have
2-1 First, we solve the worst-case transition in the first
p argmin argming'V (1-p')
(E.10)
L (6-1) + - 1-p -1 (1----1)) Sp. s.t. p
Since (E.10) decrease monotonically with p. the solution of this optimization problem p p ppp(1- p) Therefore, Cur = p/p 22|A1_
From (E.8), see that the expected regret for constructed environments Mi and M2 satisfies
e //// v C - 1)K = =22(2-1V
RRegret, max (E[Regret M3 (E. B Regret Ma (5, K)]] 2 2
2
This finishes the proof.
We set p= 231A++1 2 |A/K and p p= (221-1-17 -11 First, we solve the worst-case transition in the first step explicitly. Follow the definition of Kl-divergence, have
For KL-divergence.
p arrgminp' + (1-
s.t. p' log 2 2=++ + +11 p) log 1- p'
S.p.
Though it is difficult to obtain a closed-form solution for this optimization problem, Lemma G.8 implies that its optimal value is no less than that of the previous -2-based optimization problem. That is, p 2 p + v pp((1 p) 2' Therefore, Cpr = p/p 2 22|A|_
From (E.8), we see that the expected regret for constructed environments M₁ and M2 satisfies
max (R[Regret Mi (S. K)]. B RRegret (5, K)]] 2 2 e ///vp v Cor 1)k =
This finishes the proof.
F. Proofs of Supporting Lemmas in the Proofs of Lower Bounds
F.1. Proof of Lemma F.2
We provide the proofs for the three CRMDP settings in Appendix F.1.1, as they share a similar underlying structure. The proofs for the RRMDP-TV, RRMDP-KI, and RRMDP-x² settings are given in Appendix F.1.2, Appendix F.1.3, and Appendix F.1.4, respectively.
F.1.1. THE CRMDP SETTINGS
First, we consider the optimization problem the worst-case transition from state 81 to states 82 and 83, given by
pw argmin ":D(P*IP')))
argmin PIP(P'lP'))
[p' pp'.V'S V.V + (1 - p') v=
pp' VVT.((8)) + (1-p')}
44

---

Sample Complexity of Distributionally Robust Off Off-Dynamics Reinforeement Learning with Online Interaction
where pD = (0', and p (p. 1 1-1--), p),
where the second equality holds because (52) < and (s3) = 1 by construction. As a result, the objective function p' (*2) + (1 -p') decreases monotonically with respect to p'. Therefore, the worst-case transition probability characterized by p = sup(p': D(P"II S p), where denotes an f f-divergence (TV, KL or x²). This implies that p remains invariant across different policies ग and environments Mi and M2.
For environment M1, the total regret incurred by selecting a suboptimal policy (82) o a1 in each episode can be bounded as
K
(Regret M. K)]
Ei y ((1)) - V= (s1)]
k=1
K
Ei (p. V (P(2) + (1 P) V ((())) - (5. V* (s22) + (1 P) . V P(a)) (F.I)
K
Ei pr. (V=''((22) v=tt((s))
K
Σ
B p 1 ($2)
(82) 7 a1/1
(F2)
K
1f (52) f 5- A E
k=1
p. A Bi[K- (K)
(F.3)
pk A
P. (5)( s 2
K
(F.4)
where (F.1) follows from the definition of the robust value function under the CRMDP setting, using p as the worst-case transition probability, (F.2) relies on the construction of the reward function at state 82, (F.3) uses the definition of Sy(K) given in (E.1), and (F.4) follows from Markov's inequality.
For environment M2, following the same analysis, the total regret incurred by selecting a suboptimal policy n² (82) F a in each episode can be bounded as
K
E Regret M2 (5, K)]
Σ
E2 V VT ((1) - V- ((1)]
k=
K
E2 p. (v (32) - v= (s2))
k=1
K
E2 p- [1) + Σ
= - [11
k=1
$>1ofC
K
2
= [1]4A]
k=1
K
A
E
(12) a1)
- A (K))
アKΛ
K
Po (S)
(F.5)
2
45

---

Sample Complexity of Distributionally Robust Off-Dynamics Reinforcement Learning with Online Interaction
By combining (F.4) and (F.5) with Lemma G.6, we obtain
pK4 A
2// + P7 PP S2(K) > )) exp ( (- KL Pp)
- K)
E Regret M,, (5, K) + Regret,,
M, (5, K)]
2
P1 (i(()
2
pk A
4
We complete the proof by setting Ç = 1 1'
F.1.2. THE RRMDP-TV SETTING
For the RRMDP-TV setting, the robust value function at state 81, denoted by V*. is defined as
VT. inf {p' (x.0((2)) (1 p') V= (8s) Blp' pl}
inf {p' V= (82) (1 p') + 3(p' - p))}
where the second equality holds because V* (s2) < and V=. (sg) by construction. Given that V/T.((s)) (s2) takes value
in (0, A, 24), we set 3 E [0, 1 - 2A], so that V2 (s2) - + 8 < 0. Therefore, the term [Vz (82) 1 + 3) decreases monotonically with p', and the infimum attained at p = 1. Consequently, we obtain
(s1) (T2)(s2) + 3(1 1a1-pp. p).
For environment M1, the total regret incurred by selecting a suboptimal policy x** (*2) o an in each episode can be bounded as
E Regret M. (s,
E1 V= (81) - y
=
K
E
1 n 2 (82) F a1) ((A + 3(1 p)) 3(1 - -p))
p
E Σ 1 # a1
(F.6)
p A By KK (K)
(F.7)
p A P. (K) S ))
(F.8)
2
where (F:6) holds because ş previously derived, (F.7) uses the definition of SyK as given in (E. and (F88 follows from Markov's ' inequality.
For environment M2. following the same analysis, the total regret incurred by selecting a suboptimal policy (s2) # a in each episode can be bounded as
K
E [Reggee Ma (,, K)]
Σ
Eg
V 13 (81) - V=' (s1)]
k=1
K
Eg (3) = a1} ((24 + 3(1- -)) - -A + 3(1 -)))
Σ ( a²} ((2 + 3(1- ((1-p) p)) - 3(1 3(1-))) p))
j>1.ee
K
2 2. E
(s) = a1
k=1
46

---

Sample Complexity of Distributionally Robust Off- Off-Dynamics Reinforcement Learning with Online Interaction
p- A (K))
PKa P2 Si(K)
K
(F.9)
2
By combining (F.4) and (F.5) with Lemma G.6, we obtain
pk A
2 PP (i(K) > )
K
E Regrett, (G, + Regret Ma (c: [{,K]]
Po (i(K)
S
pk A
exp
KKL(PP (P) Pg))
We complete the proof by setting -
F.1.3. THE RRMDP-KL SETTING
For the RRMDP-KL setting, the robust value function at state 81, denoted by (*1)) is defined as
(s1) = inf {p' VVT + +1 (1-p') V=.8 (=x)(5)) + 333 p' log 2 ( + (1 (1-p') log (1-
(F.10)
P/
Using the construction that (83) and setting the derivative of the objective function in (F.10) with respect p' to zero, obtain
pe 8 (s2)
p'
(F.11)
pc B IVa (82)
p)e-B
The worst-case transition probability is defined as the maximum value p' over all policies Since (F.11) monotonically decreasing in (x2)( we set V (s2) 0 in (F.11) to obtain
(F.12)
B
p
Finally, substituting (F.11) back into (F.10), we derive the expression for the robust value function (*. as
(s,)(s)) = -Blog pe v=- + +(1 p)c---1)
(F.13)
For the environment, MI, if (#2) A 01, then the episodic regret can be bounded by
Vx 10 (s1) - v=a,00 (s1) 3 log
A + (1 - (1-p)e-9-) + B +.llog (p+ (1 p)e p)e-
pe
pe-8-'s + (1 (1-p)--8 -81
pe
--8log
p+ (1 -
(1-p)e- p)--
1+ p A 1)
Blog
p+ (1 - -)e-8-1
p
(1 (1-e-0-1
(F.14)
p+ + (1 5--
B-1A
P
(F.15)
+ (1 -pe--8-
1+3-IA
p
(F.16)
1+ 3-1
where (F.14) is because log(1 + x) S x for r > -1, (F.15) is because 1
for r > 0. (F.16) plugs in (F.12) and
I+e
uses the selection that A < }.
47

---

Sample Complexity of Distributionally Robust Off-Dynamics Reinforcement Learning with Online Interaction
Summing (6.16) over all K episodes, we obtain
E Regrett K)]
Ei (3 (01) -va .0 (s1)]
k=1
K
R1 1 (12) F #01) p ( |
PA
.E9
Σ k=1
(52) # an
1+ 3+3-1
PA
BiiK -
(F.17)
1+ 3-1
2 PKA
(i(K)= < )
2(1 + 3-1) Pi
(F.18)
where (F.17) uses the definition of ()) as given in (E.1), and (F.18) follows from Markov's inequality.
For the environment M2, if xr*t*(()) (s2) = 01, then the episodic regret can be bounded by
V ($1) V='
, ($1) = - log
pe 23 -2-
a + (1 p)e- ')
+ 3.log (pe-8 21 + (1 p)c
p)e-8 8 1)
pe
pe- 28 LA
+ (1 p) -
3 log
pe-
1-----12-0 a + (1 - p)e
p(e ple-200 22 3 - E -
3 log
1
pe 3-1- + (1 -)e---T
(1 -1-e- -0-0'A))-87 -9-1
2 3
DE 18-1-1 1A (1 p)e-
B-~
2 Be 8-1
(F.19)
p+ -) 8-1
1+
e g-
2 2
A
(F:20)
1+ 1+B-T B-T
where (F.19) uses - S <e- < 1, (F:20) plugs in (F.12) and uses the selection that A S 2-
Summing (F.20) over all K episodes, following the same analysis, we obtain
E Regret Re K)] =
Eg a 18 ((11) - ( (81)
k=
c 8
E (52) = = -p
1 B د
1=1
e 8-1 PA
K
IE2 Σ 1 (52) =a a1
1+ 8-1
8 'A
1+ +-T-T (E((S(())
8 8 PKA
Po (K)( > K) K)
2
(F.21)
2(1 + 3-1)
By combining (F.18) and (F.21) with Lemma G.6, we obtain
e e 5KΛ A
[ (K) < K
) + pg (()(())= > )
E [Regret (E, K)= + Regret,,, k)]
2(1 + 3-11
2
48

---

Sample Complexity of Distributionally Robust Off- Off-Dynamics Reinforcement Learning with Online Interaction
e- PKd
exp (-KT,((P) P3))
4(1 + 411+8-1)
A
We complete the proof by setting Ç 4(1=8
F.1.4. THE RRMDP-X" SETTING
For the RRMDP-X x² setting, the robust value function at state $1, denoted by (s1), is defined
(x) inf {p' (x2) + (1 -1 p/) Va. (..) + 8 - ( + p) (1- 2
}
(F:22)
p'
Using the construction that V (8s) = and setting the derivative of the objective function in (F.22) with respect to p' to zero, we obtain
D' = p p(1 p) VT.
(F.23)
28
The worst-case transition probability is defined as the maximum value of over all policies æ. Since (F.23) is monotonically decreasing in (**())), we set ()70((8)) 0 in (F.23) to obtain
p(1 p)
p p
(F.24)
23
Finally, substituting (F.23) back into (F.22), we derive the expression for the robust value function (*.9 as
(51) = (22 (1 11-p)) (1-p) p(1 p) VT,
(F:25)
4,3
For the environment MI, if n (s2) # 01 then the episodic regret can be bounded by
p4 (1 -p)) p(1 - p) (11-p)(1 4)²
(11 -(1- (1-p)
p(1 p)
F" (0)) -
43
48
PA p( p)
(2A A2)
43
p(1 p)
2 7A +
A
(F:26)
48
(F.27)
where (F:26) uses the selection that A < and (F.27) plugs in (F224.
Summing (F:27) over all K episodes, obtain
E Regret (E, [5]
E
y 1=0 (s1)
1=1
[ (82) a0 [/ R2
K
P4
E
Σ
( # an
2
k=
AA
E SK)
(F.28)
2
49

---

Sample Complexity of Distributionally Robust Off- Off-Dynamics Reinforcement Learning with Online Interaction
pKA P1 (((() -
K )
(F.29)
where (F.28) uses the definition of (J( as given in (E.1). and (F.29) follows from Markov's inequality.
For the environment M2, if ($2) = 01, then the episodic regret can be bounded by
V (= (si) (1n)) (81) 2 2p + (1 - p) p(1 - -2](1 -22)²
(P + (1 (1-p) p(1 - -p)(1 -))²
43
43
pA + p( - D)
(2A - 322
43
PA + p(1 p)
(2 - 34)
43
1
p(1 - p)
704
A
(F.30)
83
IV
(F31))
where (F.30) uses the selection that A - and (F31) plugs in (F:24).
Summing (F31) over all K episodes, following the same analysis, we obtain
EE [Regret M. (E, K)]
Eg m ((1)) - - (s1)]
K
1 n (82) = an) P /
2
E2
K
P4
((T an
4
PA
(K))
4
pk
2 )
K
P2
(i
(F:32)
By combining (F.29) and (F.32) with Lemma G.6, obtain
PKA A
po (S)()) - K
2 + +P2(()(()) ))
E [Regret M1 (s, K) + Regret My (5, K)]
>
8
PKA A
exp ( (-KIA (KL(P,, Po))
16
We complete the proof by setting Ç = 1 To
F.2. Proof of Lemma E.3
In order to prove this, we borrow the same technology as Lattimore & Szepesvári (2020, Lemma 15.1). First, by the definition of KL-ddivergecce, we have that
d_P dPg
(L
E
log
(F.33)
Following the notation defined in Theorem 1. we calculate the Radon-Nikodym derivative of TP as follows
K
Pi(o', al.rr,...,,, K K kk) = II
Pr (1) (a"|oo aa ... R-1 a R-1 nI ,00) (o'r = =)
50

---

Sample Complexity of Distributionally Robust Off Off-Dynamics Reinforcement Learning with Online Interaction
The density of P2 is exactly identical except that rMM replaced by TM2. which gives rise
log
dF1
(o' aaa aaarr,,
ok aak :rki)
K
log
Pr(rM, at) = pd)
dPa
Pr(r,, (o a²) r4)
k=
Pr(rMi =r² Σ 1f0 s2) log Pr(rrss ah) r²)
(F.34)
where (F.34) because the agent receives a fixed reward r when o* 83.
Taking expectations on both sides of (F.34,, we obtain
dP
Ei
log
(O', A A',R', OOKKKK," A R*)
(F:35)
dP2
K
PriileaiA (11h) (1ith)
Ei
110 = 52} -log
K
PrM, 1 (P+)
Σ
Ei
Ei
110t = -
Ok A
Pr Prag (R%)
k=1
Prag (k) (R+) Pr Prrm (122
Ei
110* = Ei
log
Oh AA
(F.36)
KI. (e2. Pr Prazg (2)44)1)))) = =22) 11
(F:37)
K
Σ Ei
Σ
1 = -2,
= aa} == (T((PM, (22ra)) Prong(enes))
[
= Σ
Ei(T,(K))
KL (o),aa)) Pr Pr (2))))))))))
(F.38)
where (F.36) is because 1 }2} is measurable with respect to the a-field generated by O and A (F.37) follows from the definition of KL divergence, (F.38) follows from the definition of ; in (E.2). Combining (F.38) with (F.33,, we conclude the proof.
G. Auxiliary Lemmas
Here, we present some auxiliary lemmas which are useful in the proof.
Lemma G.1 (Hoeffding's inequality). (Vershynin, 2018, Theorem 2.2.6) Let XI.... .xr be independent random variables. Assume that X, E [0, M] for every i with M 0. Let ST + Ei= X,, then for any >> have
E[Sr]| 2 e) < 2exp (-
2T
P([S E[Sr]
M
Lemma G.2 Self-bounding variance inequality). (Maurer Pontil, 2009, Theorem 10) Let XI,".., Xr be independent and identically distributed random variables with finite variance. Assume that X, [0, M] for every with M > 0. Let Sr - X? ET x,)2, then for any > we have
Te²
P([ST- VVr(X1n 2 2) 2exp
2M2
51

---

Sample Complexity of Distributionally Robust Oft- Off-Dynamics Reinforcement Learning with Online Interaction
Lemma G.3. (Weissman al., 2003, Theorem 2.1) Let P be probability distribution over S {(81,-.. ,88).
; X1, ....... XT
be independent and identically distributed random variables distributed according to P. Let P(s) - $ +E 1(X, = s). then for any > we have
T
P( 2 S 2 exp
Lemma G.4. (Panaganti & Kalathil, 2022, Lemma 7) We define V = V| S Vinx J. Let (e(e) be minimal 6-cover of) V with respect to the distance metric d(V, VV) = | - >0 for some fixed c E (0, 1). Then we have
3V max
log (vv(c) & [S] log
Lemma G.S. (Dann et al., 2017, Lemma F.4) Let F; for 1,2, ... be a filtration and .., X,, be a sequence of Bernoulli random variables with P(X; 11F P, being Fi-1-measurable and X; being F--measurabl. It holds that
P 3n
X 1=1
Pr/2- W Se-w.
1=1
Lemma G.6 (Bretagnolle-Hutte Huber inequality). (Lattimore & Szepesvári, 2020, Theorem 14.2) Let P and Q be probability measures on the same measurable space (2, and let A E F be an arbitrary event. Then
1 P(A) + Q(4)) exp((KK((,,C)
Lemma G.7. (Lattimore & Szepesvári, 2020, Section 4.2) The KI-divergence between Gaussian distributions with means f1, 22 and common variance x² is
(11 112)
20²
Lemma G.8. (Sayyareh, 2011, Theorem 3.1) Let P and Q be two probability distributions, then
KL(PIIQ) S (PIIQ).
52


Reviews:
[{"review_id": "dILn4gGoGB", "reviewer": "Reviewer_uMDK", "summary": "This paper considers distributionally robust RL with online access to the nominal model, including the constrained MDP (CMDP) and the regularized robust MDP (RRMDP) frameworks. They propose *supremal visitation ratio* $C_{vr}$ as a hardness measure and show that this measure is unavoidable in the regret lower bounds. They also provide numerical results to validate how $C_{vr}$ would affect learning efficiency.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your valuable time and effort in providing detailed feedback on our work. We hope our response will fully address all of your questions.\n\n---\n\n### 1. The definitions of $P_h^\\pi$ and $d_h^\\pi$ in Assumption 4.5\n\nThe definitions are provided in Definition 4.3, where $P_h^\\pi$ represents the visitation measure under the worst-case scenario, and $d_h^\\pi$ represents the visitation measure in the nominal environment, both are defined to be induced by the policy $\\pi$.\n\n---\n\n### 2. Comparison of ORBIT with algorithms in Liu and Xu (2024a) and Lu et al. (2024)\n\nAll three works investigate the online robust MDP setting using value-iteration-based methods. In particular, Liu and Xu (2024a) focuses on the linear function approximation regime, whereas Lu et al. (2024) and our work consider the tabular setting. However, Liu and Xu (2024a) and Lu et al. (2024) address only the constrained TV-divergence scenario. In contrast, our study addresses a broader range of online robust problems, including robust sets defined by three different $f$-divergences, as well as constrained RMDP and regularized RMDP, the latter of which was not considered in their work. Consequently, our algorithm provides distinct update formulations and bonus terms across six settings.\n\n---\n\n### 3. Discussion on the average training time for $\\chi^2$ cases in Figure 3(a)\n\nLemmas E.15 and F.10 reveal that deriving the dual formulation for the $\\chi^2$ update requires solving a multi-dimensional optimization problem, which leads to longer training times. In contrast, the constrained KL setting (Lemma E.11) relies only on one-dimensional optimization. Furthermore, for constrained TV (as illustrated in Algorithm 2), regularized TV (Lemma F.1), and KL settings (Lemma F.5), the optimization problems have closed-form solutions. This is why the average training time for $\\chi^2$ cases is significantly longer.\n\n---\n\n### 4. Is it correct that the fail-state conditions 4.1 and 4.2 are special cases of bounded visitation measure ratio?\n\nNo, our assumptions do not imply theirs, nor do theirs imply ours. The fail-states condition was specifically designed for the constrained TV robust sets, as explained in Proposition 4.4. In contrast, our assumption addresses the general online robust problem and is applicable to various other $f$-divergence robust sets.\n\n\n---\nWe hope we have addressed all of your questions/concerns. If you have any further questions, we would be more than happy to answer them.\n\n\n### References:\n\n[1] Liu, Z., & Xu, P. (2024, April). Distributionally robust off-dynamics reinforcement learning: Provable efficiency with linear function approximation. In International Conference on Artificial Intelligence and Statistics (pp. 2719-2727). PMLR.\n\n[2] Lu, M., Zhong, H., Zhang, T., & Blanchet, J. (2024). Distributionally robust reinforcement learning with interactive data collection: Fundamental hardness and near-optimal algorithm. arXiv preprint arXiv:2404.03578.", "claims_and_evidence": "See Question 1.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "See Questions.", "experimental_designs_or_analyses": "The experimental setups in Section 5 are clearly described.", "relation_to_broader_scientific_literature": "N/A", "essential_references_not_discussed": "No.", "other_strengths_and_weaknesses": "**Strengths:**\n\n1. This paper introduces supremal visitation ratio as a hardness measure and shows it is unavoidable in the lower bounds.\n2. They present numerical results showing how the harness measure would affect learning performance.\n\n**Weaknesses:** See Questions.", "other_comments_or_suggestions": "1. What are the definitions of $P_h^\\pi$ and $d_h^\\pi$ in Assumption 4.5?", "questions_for_authors": "1. Can you compare ORBIT and the algorithms in (Liu & Xu, 2024a) and (Lu et al., 2024)?\n2. In Figure 3(a), why the average training time for $\\chi^2$ cases is significantly longer?\n3. Is it correct that the fail-state conditions 4.1 and 4.2 are special cases of bounded visitation measure ratio?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "k7z9GOYkBC", "reviewer": "Reviewer_WS6K", "summary": "This paper explores robust Markov decision processes (RMDPs) in the context of off-dynamics reinforcement learning, where distribution shifts occur between training and deployment environments. The authors investigate two variants: constrained RMDPs (CRMDPs) and regularized RMDPs (RRMDPs). They propose computationally efficient algorithms for both settings and establish sublinear regret guarantees, demonstrating the effectiveness of their approach in mitigating performance degradation due to environmental shifts.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the positive feedback on our work. We hope our response will fully address all of the reviewer's questions. \n\n---\n\n### 1. The key insights from Figure 2\n\nThe primary purpose of Figure 2 is to show that our algorithm converges stably by the end of training in a fixed environment, rather than to compare performance under different ambiguity sets. In the Frozen Lake experiment, our main goal is to highlight the algorithm’s robustness, specifically its ability to handle worst-case scenarios effectively.\n\n---\n\n### 2. How should one decide which ambiguity set to use?\n\nAs depicted in Figure 3(a), the computational costs vary with different ambiguity settings, where the regularized setting generally proves to be more computationally efficient than the constrained setting. Selecting an appropriate ambiguity set (TV v.s. KL v.s. $\\chi^2$) may be specific to the application and the structure of the problem. For hyperparameters like the radius or the regularization parameters, we can select them via hyperparameter tunning based on empirical performance.\n\n---\n\n### 3. Can you better motivate the specific choice of ambiguity sets?\n\nOur primary goal is to study the general online robust problem. We focus on these three ambiguity sets because they are widely used and extensively investigated in the reinforcement learning literature (Panaganti & Kalathil, 2022; Yang et al., 2022; Xu et al., 2023; Shi et al., 2024), enabling more direct comparisons with existing studies.\n\n---\n\n### 4. Could you also include the popular Wasserstein or MMD ambiguity set?\n\nThanks for the great suggestion! Our algorithm has the potential to be adapted to these two ambiguity sets since we address the general online robust problem. However, this adaptation might require additional analysis, as these ambiguity sets lack a closed-form dual formulation, posing challenges for direct application of our current algorithm. This will be a great future direction on online robust MDPs. \n\n---\n\n### 5. Can you also handle those non-rectangular ambiguity sets?\n\nNon-rectangular ambiguity sets differ fundamentally from those discussed in this paper, and our algorithm is not equipped to handle these due to their inherent complexity. To our knowledge, nearly all studies in the robust MDP literature use rectangular ambiguity sets. Moreover, Wiesemann et al. (2013) showed that solving DRMDPs with general uncertainty sets can be NP-hard. We therefore identify this as an open problem for future research.\n\n\n---\nWe hope we have addressed all of your questions/concerns. If you have any further questions, we would be more than happy to answer them.\n\n\n### References:\n\n[1] Panaganti, K., & Kalathil, D. (2022, May). Sample complexity of robust reinforcement learning with a generative model. In International Conference on Artificial Intelligence and Statistics (pp. 9582-9602). PMLR.\n\n[2] Yang, W., Zhang, L., & Zhang, Z. (2022). Toward theoretical understandings of robust markov decision processes: Sample complexity and asymptotics. The Annals of Statistics, 50(6), 3223-3248.\n\n[3] Xu, Z., Panaganti, K., & Kalathil, D. (2023, April). Improved sample complexity bounds for distributionally robust reinforcement learning. In International Conference on Artificial Intelligence and Statistics (pp. 9728-9754). PMLR.\n\n[4] Shi, L., Li, G., Wei, Y., Chen, Y., Geist, M., & Chi, Y. (2023). The curious price of distributional robustness in reinforcement learning with a generative model. Advances in Neural Information Processing Systems, 36, 79903-79917.\n\n[5] Wiesemann, W., Kuhn, D., & Rustem, B. (2013). Robust Markov decision processes. Mathematics of Operations Research, 38(1), 153-183.", "claims_and_evidence": "The paper is well-structured, with clear results. Section 3 introduces the ORBIT algorithm (Online Robust Bellman Iteration), which serves as a foundation for addressing both RMDPs and CRMDPs. Section 4 establishes the corresponding regret bounds, demonstrating the theoretical performance of the proposed methods. Finally, Section 5 presents numerical experiments that validate the effectiveness of the approach in practical scenarios.", "methods_and_evaluation_criteria": "I am not entirely clear on the key insights from Figure 2. If I understand correctly, in the CRMDP setting, the TV-ambiguity set appears to yield the best performance, while in the RRMDP setting, the $\\chi^2$-ambiguity set performs better. Can this be theoretically justified, or is it purely an empirical observation? If it is the latter, what makes this result interesting, and how can we be sure it is not merely an artifact of the Frozen Lake problem setting?  \n\nThis also raises a broader question: How should one decide which ambiguity set to use? Can you provide theoretical insights to guide this choice, and do the numerical results align with such theoretical expectations?", "theoretical_claims": "I am wondering why the authors decided to choose exactly these 3 ambiguity sets: (1) TV, (2) KL, (3) $\\chi^2$?\n\nCould you also include the popular Wasserstein or MMD ambiguity set?", "experimental_designs_or_analyses": "See points raised above", "relation_to_broader_scientific_literature": "The related literature is adequately summarized. I have no compaints here.", "essential_references_not_discussed": "-", "other_strengths_and_weaknesses": "MDPs under environment shifts are a crucial and challenging topic in both the ML and OR communities. This paper explores an interesting direction in addressing these challenges, presenting a well-written and relatively accessible exposition.", "other_comments_or_suggestions": "-", "questions_for_authors": "1) Can you motivate better the specific choice of ambiguity sets?\n2) All uncertainty sets are defined a rectangular ambiguity sets. Uncertainty sets defined from maximum likelihood principles, however turn out to be non-rectangular. Can you also handle those?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "QqWC64f2VJ", "reviewer": "Reviewer_9Uk6", "summary": "The paper considers two types of robust MDP formulations - one with constraints and one with regularization. \n\nA new value update is proposed for both which can be shown to guarantee for a tabular case some regret bounds.\n\nLower and upper regret bounds are given as a function of the supremal visitation ratio which is introduced in the paper. \n\nThe authors also show case when the regret is especially high due the supremal visitation ratio.\n\nFinally, the authors provide some simple experiments to support their claims.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your valuable time and effort in providing detailed feedback on our work. We hope our response will fully address all of your questions.\n\n---\n\n### 1. Explanation about the bounds in 3.2 and 3.3\n\nSections 3.2 and 3.3 present update formulas for different types of robust sets (constrained vs. regularized) and different $f$-divergences (TV, KL, and $\\chi^2$). Although these updates all follow a similar pattern--applying an optimism-based principle and a robust Bellman operator--their specific forms differ because the dual formulations vary across robust set types and divergence measures. Hence, the resulting $Q$-function estimates and bonus terms change accordingly.\n\nWe have outlined the final equations for the updates in Sections 3.2 and 3.3 due to space constraints, but we agree that more in-depth explanation would help clarify how each term arises from the respective dual formulation. We plan to include further details in the final version of the paper to make the derivations and resulting bounds more transparent.\n\n---\n\n### 2. Proof sketch of this paper\n\nWe summarize the core proof idea as follows.\n\nFor the upper bounds, we decompose the regret as\n$\\text{Regret}=\\sum\\limits_{k=1}^K\\big(V_1^{\\*,\\rho}-V_1^{{\\pi^k},\\rho}\\big)=\\sum\\limits_{k=1}^K\\big(V_1^{\\*,\\rho}-V_1^{k,\\rho}\\big)+\\sum\\limits_{k=1}^K\\big(V_1^{k,\\rho}-V_1^{{\\pi^k},\\rho}\\big)$.\n\nWe use the dual formulation to estimate $V$ and add an extra bonus term to maintain an optimistic estimate, ensuring that the first term is less than zero. From the definition of $V^k$, it follows that the second term can be controlled by $\\sum\\limits_{k=1}^K\\sum\\limits_{h=1}^H\\mathbb{E}\\_{\\\\{P_h^{w,k}\\\\}_{h=1}^H,\\pi^k}\\big[2\\text{bonus}_h^k\\big]$. The cumulative bonus is of an order not larger than $\\sqrt{K}$, as derived from the concentration inequalities.\n\nFor the lower bounds, we construct a key state that is difficult to explore in the nominal environment but easier to explore in the perturbed environment. Consequently, insufficient knowledge about this key state can lead to significant regret.\n\nWe will add the proof sketch in the final version.\n\n---\n\n\n### 3. The text display on the third page\n\nWe believe this might be due to the floating environment in LaTeX.\n\n---\n\n### 4. Further clarifications on experiment setup and observed performance\n\n\nIn the case of $C_{vr}$, we constructed a well-designed MDP environment where the hyperparameter $\\beta$ allows for adjustments to the value of $C_{vr}$ to observe performance changes. However, the $\\frac{1}{2}$ order dependency on $C_{vr}$ represents merely a worst-case bound. Furthermore, the regret formulations incorporate additional terms, so we do not anticipate results to be strictly proportional to $\\sqrt{C_{vr}}$. Here, we merely demonstrate a general positive correlation to validate our intuition, akin to an ablation study.\n\nRegarding $S$, $A$, and other variables, they are not the primary focus within this topic. The crucial parameters here are $K$ (indicating efficient learning of the problem) and $C_{vr}$ (demonstrating that $C_{vr}$ is a precise metric for the difficulty of the environment). Unlike $C_{vr}$, which is relatively easier to manipulate, altering the values of $S$ and $A$ would lead to a complete structural change in the environment. Given that our environment is specifically designed, it is challenging to introduce $S$ and $A$ as variables into the existing problem.\n\nTo answer the reviewer's question, we have conducted a new experiment on the Gambler's Problem (inspired by Panaganti et al., 2022, Section 6). We set the heads-up probability to $p_h=0.6$ for the nominal environment and $p_h=0.4$ for the perturbed environment. We applied the constrained TV setting with $H=30$ and varied the size of $S$ from 15 to 55, reporting the results across 10 training runs as shown in the following table. This demonstrates that performance deteriorates as the sizes of $S$ and $A$ increase.\n\n|size of S|15|23|31|39|47|55|\n|-|-|-|-|-|-|-|\n|mean of reward|0.1294|0.1254|0.1192|0.1240|0.1140|0.0968|\n|std of reward|0.0088|0.0134|0.0164|0.0163|0.0219|0.0118|\n\n\n---\n\n### 5. Explanation about performance under minimal perturbation in Figure 1\n\nAs is well-known in robust reinforcement learning, algorithms designed to hedge against large uncertainties naturally trade off some performance in near-nominal settings. Therefore, while ORBIT typically outperforms non-robust approaches under significant perturbations, it may appear less effective when perturbations are small or absent because it prioritizes worst-case scenarios over short-term gains.\n\n\n---\nWe hope we have addressed all of your questions/concerns. If you have any further questions, we would be more than happy to answer them.\n\n\n### References:\n\n[1] Panaganti, K., & Kalathil, D. (2022, May). Sample complexity of robust reinforcement learning with a generative model. In International Conference on Artificial Intelligence and Statistics (pp. 9582-9602). PMLR.", "claims_and_evidence": "The paper is mainly theoretical and its claims are well supported.", "methods_and_evaluation_criteria": "The authors provide experiments that show general behavior as a function of the supremal visitation ratio, but these experiments do not seem to reflect the behavior of the regret they found ($\\sqrt{C_{vr}}$).  Also if they could show the behavior reflects the other parameters in their bound it would've been better (e.g. $S$, $A$).", "theoretical_claims": "No.", "experimental_designs_or_analyses": "No.", "relation_to_broader_scientific_literature": "The key contributions seem to be well related to relevant literature.", "essential_references_not_discussed": "No to my best knowledge.", "other_strengths_and_weaknesses": "The paper is written very clearly, it has a solid theoretical result that can be significant to the community. \n\nThe weaknesses of the paper in my opinion are:\n\n1. The bounds in 3.2 and 3.3. are not explained enough. What is the difference between all of them? do the terms we see there makes sense? \n\n2. It's nice that the proofs are in the appendix, but it would be good if you share the general intuition beyond them - what was the main idea in the proof. This is in my view much more important than showing the bounds for another case.\n\n3. In the third page the text looks cramped. I hope it's an artifact in my viewer since changing the spaces between lines is prohibited as far as I know.\n\n4.  The experiments are not very important because the result is mainly theoretical - but still. The first environment is too simple (H=3 is barely RL). As I wrote before it would make sense to show that the regret bounds behave like you would expect it for all of its parameters (S, A, K, Crv...). I didn't see a discussion on why in Figure 1 ORBIT works less good when there is small or no perturbation?", "other_comments_or_suggestions": "None.", "questions_for_authors": "Can you provide a proof sketch for the main result in the paper (Thm. 4.14 and also 4.17)?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "zv7LiunchA", "reviewer": "Reviewer_pPuk", "summary": "Other reviews checked. I keep my score. Thanks for the rebuttal.\n\nThis paper investigates two types of robust Markov decision processes (RMDPs) in tabular reinforcement learning: CRMDP and RRMDP. \n\nIt introduces hard instances and visitation ratios and establishes both regret lower and upper bounds.\n\nThe authors also present empirical results to support their findings.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the positive feedback on our work. We hope our response will fully address all of the reviewer's questions. \n\n---\n\n### 1. Discussion on possible relaxation of Assumption 4.5\n\nWe appreciate the reviewer's insightful question and agree that Assumption 4.5 might be relaxed to require coverage only of $d^{\\pi^\\*}$ instead of $d^\\pi$ for all $\\pi$, similar to the off-policy problem. While this modification is theoretically feasible, it is not straightforward due to the dynamics shift in the deployment environment. It would likely involve revising the way we decompose the regret, leading to non-trivial changes in our current proof structure.\n\n\n---\n\n### 2. Explanation about KL bound in Theorem 4.19\n\nAs stated by Remark 4.2 in Blanchet et al. (2023), the $e^H$ dependency for KL bounds is commonly observed in the literature. This is due to the logarithmic function used in the definition of KL divergence.\n\n\n---\n\n### 3. Do you have any comments or comparisons with other existing upper bound results?\n\nThank you for the question. We would like to point out that no previous work has explored the exact same setting we are studying. The research Lu et al. (2024), which most closely resembles ours in the constrained TV setting, relies on a different assumption that cannot be generalized to other settings considered in our paper. Unlike their approach, we do not concentrate on one specific scenario of uncertainty sets (constrained TV setting) but instead explore the general online learning of robust MDP.\n\n---\n\n### 4. Intuition behind the presence of the 1/K term in the bonus functions\n\nThe $1/K$ terms in the bonus functions are not intrinsic. In the proof, we constructed $\\epsilon$-nets to bound one part of the estimation, which leads to an additional term of $\\mathcal{O}(\\epsilon)$ or $\\mathcal{O}(\\sqrt{\\epsilon})$, where the value of $\\epsilon$ can be arbitrary. We set $\\epsilon=\\mathcal{O}(1/K)$ or $\\epsilon=\\mathcal{O}(1/K^2)$, which results in the extra $1/K$ term in the bonus. For a detailed explanation, please refer to Lemmas E.2, E.12, E.16, F.2, F.6, and F.11 respectively for the specific setting.\n\n---\n\n### 5. Clarification about notations such as on line 274\n\nAs defined in Definition 4.3, $P^o$ represents the nominal transition, $P^w$ represents the worst-case transition, and $P^\\pi$ is the corresponding visitation measure. These are distinctly different concepts.\n\n---\nWe hope we have addressed all of your questions/concerns. If you have any further questions, we would be more than happy to answer them.\n\n\n### References:\n\n[1] Blanchet, J., Lu, M., Zhang, T., & Zhong, H. (2023). Double pessimism is provably efficient for distributionally robust offline reinforcement learning: Generic algorithm and robust partial coverage. Advances in Neural Information Processing Systems, 36, 66845-66859.\n\n[2] Lu, M., Zhong, H., Zhang, T., & Blanchet, J. (2024). Distributionally robust reinforcement learning with interactive data collection: Fundamental hardness and near-optimal algorithm. arXiv preprint arXiv:2404.03578.", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "Yes", "theoretical_claims": "Yes.\n\nThis paper presents hard instances to illustrate that a well-defined exploration hardness condition is essential for general online learning in robust Markov decision processes (RMDPs). When state visits are exponentially rare, online learning becomes intractable.\n\nThe authors introduce the supremal visitation ratio as a metric for measuring exploration difficulty in RMDPs. They propose computationally efficient algorithms for CRMDPs and RRMDPs with various uncertainty sets and provide theoretical guarantees for these methods.\n\nPlus, the paper establishes regret lower bounds, showing that the supremal visitation ratio is an unavoidable factor in the sample complexity of online RMDP learning.", "experimental_designs_or_analyses": "Yes.\n\nThe authors assess the algorithms in a simulated RMDP and the Frozen Lake environment, demonstrating their effectiveness under significant distribution shifts.", "relation_to_broader_scientific_literature": "Off-dynamics reinforcement learning (RL) has attracted much attention due to scenarios where the transition dynamics of the deployment environment differ from those during the training process. This approach requires exploration strategies that proactively address distributional shifts, ensuring robustness to dynamic changes.", "essential_references_not_discussed": "na", "other_strengths_and_weaknesses": "In other parts", "other_comments_or_suggestions": "The proposed algorithms follow the robust value iteration template.\n\nAssumption 4.5 is interesting. My understanding is that the intuition behind it is that collecting data in the nominal MDP is somewhat analogous to an offline RL problem in the true MDP, requiring adequate data coverage in the true MDP.\n\nI’m curious whether this necessity assumption could be relaxed to require coverage of only d^{pi*} instead of covering d^pi for all pi.\n\nThe KL bound in Theorem 4.19 appears to have an exponential dependence on H. Could you provide some intuition for this bound?\n\nThis paper presents many upper bound results. Do you have any comments or comparisons with other existing upper bound results?", "questions_for_authors": "Some bonus terms include the 1/K component, while others do not. Could you provide some intuition behind the presence of the 1/K term in the bonus functions?\n\nAdditionally, why do some P notations include w while others do not, such as in line 274?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

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

Paper-Summary: This paper addresses the problem of robust policy learning under dynamics uncertainty in online reinforcement learning. Unlike prior works that rely on offline data or assume strong coverage conditions, this paper focuses on online settings where the agent can only interact with the nominal training environment but must learn policies that generalize to distributionally shifted deployment dynamics. The authors study two robust MDP formulations—Constrained Robust MDPs (CRMDPs) and Regularized Robust MDPs (RRMDPs). A key contribution is the introduction of the supremal visitation ratio as a metric to capture the exploration difficulty under distributional shift. The paper shows that if the ratio is unbounded, sample-efficient learning is provably impossible. It proposes a computationally efficient algorithm called ORBIT and proves regret bounds that optimally depend on this ratio and the number of episodes. The theoretical findings are validated with numerical experiments on simulated environments and the Frozen Lake benchmark. 


Review and feedback: We received 4 expert reviews, with scores, 3, 3, 4, 4, and the average score is 3.5.  

The reviewers are generally positive about this paper. The introduction of supremal visitation ratio (C_vr) as a general measure of robustness-induced exploration difficulty is very interesting and theoretically justified, and is appreciated by all reviewers. The paper provides comprehensive regret analyses for both CRMDPs and RRMDPs, achieving tight sample complexity bounds that depend optimally on key parameters such as horizon length, state-action space size, and C_vr. The proposed algorithm, ORBIT, is computationally tractable and generalizable across different uncertainty sets, including Total Variation, KL, and χ². Hard instance constructions and impossibility results are particularly well studied. The paper is well-written and accessible. 

Reviewers have also made suggestions for improvement. One concern is the lack of experimental results beyond a simple tabular setting.  Reviewers have also asked to include more qualitative/intuitive explanations for the proofs and justification for the assumptions. 
Please address these comments/suggestions while preparing the final submission.
Decision: Accept (poster)