Distributionally Robust Reinforcement Learning with Interactive Data Collection: Fundamental Hardness and Near-Optimal Algorithms
Authors: Miao Lu
Han Zhong
Tong Zhang
Jose Blanchet
Venue: NeurIPS 2024 poster (2024)
Keywords: Theory of distributionally robust reinforcement learning
interactive data collection
robust Markov decision process
sample complexity
online regret
Primary area: reinforcement_learning

Abstract: The sim-to-real gap, which represents the disparity between training and testing environments, poses a significant challenge in reinforcement learning (RL). A promising approach to addressing this challenge is distributionally robust RL, often framed as a robust Markov decision process (RMDP). In this framework, the objective is to find a robust policy that achieves good performance under the worst-case scenario among all environments within a pre-specified uncertainty set centered around the training environment. Unlike previous work, which relies on a generative model or a pre-collected offline dataset enjoying good coverage of the deployment environment, we tackle robust RL via interactive data collection, where the learner interacts with the training environment only and refines the policy through trial and error. In this robust RL paradigm, two main challenges emerge: managing distributional robustness while striking a balance between exploration and exploitation during data collection. Initially, we establish that sample-efficient learning without additional assumptions is unattainable owing to the curse of support shift; i.e., the potential disjointedness of the distributional supports between the training and testing environments. To circumvent such a hardness result, we introduce the vanishing minimal value assumption to RMDPs with a total-variation (TV) distance robust set, postulating that the minimal value of the optimal robust value function is zero. We prove that such an assumption effectively eliminates the support shift issue for RMDPs with a TV distance robust set, and present an algorithm with a provable sample complexity guarantee. Our work makes the initial step to uncovering the inherent difficulty of robust RL via interactive data collection and sufficient conditions for designing a sample-efficient algorithm accompanied by sharp sample complexity analysis.

Distributionally Robust Reinforcement Learning with Interactive Data Collection: Fundamental Hardness and Near-Optimal Algorithms
Miao Lu
Han Zhong
Tong Zhang' Jose Blanchet
DDpartmeett Management Science and Engineering, Stanford University
Center for Data Science, Peking University Department of Computer Science, University of Illinois Urbana- Jheama-Champaign
Abstract
Distributionally robust reinforcement learning (DRRL), often framed as a robust Markov decision process (RMDP), seeks to find robust policy that achieves good performance under the worst-case scenario among all environments within pre- specified uncertainty set centered around the training environment. Unlike previous work, which relies on generative model or pre-collected offline dataset enjoying good coverage of the deployment environment, we tackle robust RL via interactive data collection, where the learner interacts with the training environment only and refines the policy through trial and error. In this robust RI. paradigm, two main challenges emerge: managing the distributional robustness while striking balance between exploration and exploitation during data collection. Initially, we establish that sample-efficient learning without additional assumptions is unattainable owing to the curse of support shift; i.e., the potential disjointedness of the distributional supports between training and testing environments. To circumvent such hardness result, we introduce the vanishing minimal value assumption to RMDPs with a total-variae varl-varaaiion distance robust postulating that the minimal value of the optimal robust value function is zero. Such an assumption effectively eliminates the support shift issue for RMDPs with TV distance robust set, and present an algorithm with a provable sample complexity guarantee. Our work makes the initial step to uncovering the inherent diffieulty of robust RL via interactive data collection and sufficient conditions for sample-efficien algorithms with sharp sample complexity.
1 Introduction
Reinforcement learning (RI.) serves as a framework for addressing complex docision-making prob- lems through iterative interactions with environments. The advancements in deep reinforcement learning have enabled the successful application of the general RL framework across various domains, including mastering strategic games, such as Go (Silver et al., 2017), robotics (Kober al., 2013), and tuning large language models (LLMs; Ouyang et al. (2022)). The critical factors contributing to these successes encompass not only the potency of deep neural networks and modern deep RL algorithms but also the availability of substantial training data. However, there are scenarios, such as healthcare (Wang al., 2018) and autonomous driving (Kiran al., 2021), among others, where collecting data in the target domain is challenging, costly, or even unfeasible.
In such cases, the sim-to-real transfer (Kober et al., 2013; Sadeghi and Levine, 2016; Peng et al., 2018; Zhao al., 2020) becomes remedy- process in which the RL agents are trained some simulated environment and subsequently deployed in real-world settings. Nevertheless, the training
Equal contribution. Email to miaolu@stanford. edu, hanzhong@stu. pku. edu. cn
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

environment may differ from the real-world environment. Such a discrepancy, also known as the sim- to-real gap, will typically result in suboptimal performance of RL agents in real-world applications. One promising strategy to control the impact in performance degradation due to the sim-to-real gap is robust RI. (Iyengar, 2005; Pinto et al., 2017; Hu al., 2022), which aims to learn policies exhibiting strong (i.e. robust) performance under environmental deviations from the training environment, effectively hedging the epistemological uncertainty arising from the differences between the training environment and the unknown testing environments.
robust RL problem often formulated within a robust Markov decision process (RMDP) framework, with various types of robust sets characterizing different environmental perturbations. In this robust RL context, prior works have developed algorithms with provable sample complexity guarantees. However, these algorithms typically rely on either generative model (Yang et al., 2022; Panaganti and Kalathil, 2022; Xu et al., 2023; Shi et al., 2023) or offline data with good coverage of deployment environments (Zhou et al., 2021b; Panaganti et al., 2022; Shi and Chi, 2022; Ma et al., 2022; Blanchet et al., 2023). Notably, the current literature does not explicitly address the exploration problem, which stands as one of the fundamental challenges in reinforcement learning through trial-and-crror (Sutton and Barto, 2018). Meanwhile, the empirical success of robust RL methods (Pinto et al., 2017: Kuang et al., 2022; Moos et al., 2022) typically relies reinforcement learning through interactive data collection in the training environment, where the agent iteratively and actively interacts with the environment, collecting data, optimizing and robustifying its policy. Given that all the existing literature on robust RL theory relies on a generative model or pre-collected data, it is natural to ask:
Can we design provably -efpee-effiien robust RL algorithu that relies interactive data collection in the training environment?
Answering the above question faces fundamental challenge, namely, that during the interactive data collection process, the learner no longer has the oracle control over the training data distributions that are induced by the policy learned through the interaction process. In particular, could be the case that certain data patterns that are crucial for the policy to be robust across all testing environments are not accessible through interactive data collection, even through a sophisticated design of an exploration mechanism during the interaction process. For example, specific states may not be accessible within the training environment dynamics but could be reached in the testing environment dynamics.
In contrast, previous work has demonstrated that robust RL through a generative model or a pre- collected offline dataset with good coverage does not face such difficulty. In the generative model setup, fortunately, the learner can directly query any state-action pair and obtain the sampled next state from the generator. Intuitively, once the states that could appear in the testing environment trajectory are queried enough times, it is possible guarantee the performance of the learned policy in testing environments. The situation is similar if one has pre-collected offline dataset that possesses good coverage of the testing environment. This motivates us to take the initial steps towards answering the above questions regarding robust RL with interactive data collection.
1.1 Contributions
In this work, we study robust RL in a finite-horizon RMDP with an S x A-rectangular total-variation distance (TV) robust set (see Assumption 2.1 and Definition 2.4) through interactive data collection. We give both a fundamental hardness result in the general case and a sample-efficient algorithm within tractable settings. More specifically, our contributions three folds.
Fundamental hardness. We construct a class of hard-to-learn RMDPs (see Example 3.1) and demonstrate that any learning algorithm inevitably incurs Q(p- H -onlinne regret (Theorem 3.2) under at least one RMDP instance. Here, P significs the radius of the TV robust uncertainty set, H is the horizon, and K is the number of interactive episodes. This linear regret lower bound underscores the impossibility of sample-efficien robust RL via interactive data collection in general.
Identifying tractable case. Upon close examination of the challenging instance, we recognize that the primary obstacle to achieving sample-efficient learning lies in the curse of support shift, i.e., the disjointedness of distributional support between the training environment and the testing environments. broader sense, the curse of support shift also refers to the situation when the states appearing in testing environments are extremely hard to arrive in the training environment.

---

Table I: Comparison between OPROVI-TV and prior results on RMDP with S x A-rectangular TV robust sets under various settings (generative model/ofiline dataset/intrractie data collection). For the infinite horizon y-ddiscounted RMDPs, we denote H, := (1 - 7) as the effective horizon length. In the offline setting, Clab and Clan represent the robust partial coverage coefficient and full coverage coefficient. respectively. In the general case, our lower hound reads intractable, meaning that there exist hard instances where it is impossible to learn the nearly optimal robust policy via finite number of interactive samples.
Sample complexity E [0, 1)
Model Assump.
Algorithm
Data oracle
RPVL (Xu et al., 2023)
generative model
S*AA
min (1 TpP "JU,SA
DRVI (Shi al., 2023)
generative model
general case
lower bound (Shi et al., 2023)
generative model
S2
min
р²MPO (Blanchet al., 2023)
offline dataset
Ö
Cios 5
lower bound (this work)
interactive data collection
intractable
"fail-state" assumption
Cran Cia na
RFQI (Panaganti et al., 2022)
offline dataset
vanishing minimal value (Assumption 4.1)
OPROVI-TV (this work)
interactive data collection
mint minn HH,p
To rule out these pathological instances, we propose the vanishing minimal value assumption (As- sumption 4.1,, positing that the optimal robust value function reaches zero at a specific state. Such an assumption naturally applies to the sparse reward RL paradigm and offers a broader scope compared to the "fail-state" assumption utilized in prior studies on offiin RMDP with function approximation (Panaganti et al., 2022). For a comprehensive discussion on this comparison, please see Remark B.3. On the theoretical front, we establish that the vanishing minimal value assumption effectively miti- gates the support shift issues between the training and the testing environments (Proposition 4.2), rendering robust RL with interactive data collection feasible for RMDPs with TV robust sets.
Efficient algorithm with sharp sample complexity. Under the vanishing minimal value assumption, we develop an algorithm named OPtimistic RObust Value Iteration for TV Robust Set (OPROVI-TV, Algorithm 1), that capable of finding an e-optimal robust policy with a total number of
Ö min (minnH,, p- -H/A//"))
(1.1)
interactive samples (Theorem 4.3). Here S and A denote the number of states and actions, P represents the radius of the TV robust set, and H/ is the horizon length of each episode. To our best knowledge, this is the first provably sample-efficient algorithm for robust RL with interactive data collection.
According to (1.1), the sample complexity of finding an e-optimal robust policy decreases as the radius p of the robust set increases. When the radius O. an RMDP reduces to a standard MDP, and the sample complexity (1.1) recovers the minimax-optimal sample complexity for online RI in standard MDPs up logarithm factors, i.e., S(H*)
In the end, we further extend our algorithm and theory to a new type of RMDPs, S x A-rectangular discounted RMDP equipped with robust sets consisting of transition probabilities with bounded ratio to the nominal kernel (See Appendix B.4.2). This newly identified class of RMDPs naturally does not suffer from the support shift issue. It is equivalent the S x A-rectangular RMDP with TV robust set and vanishing minimal value assumption in an appropriate sense due to Proposition 4.2. can also solve this new model sample-effiiienlly.
Consequently, by a clever usage of Algorithm as shown in Corollary B.5. Such a result echoes our intuition on the curse of support shift.
Comparison to related works. Due to the space limit, we only compare with the most related works through Table 1. A detailed discussion of related works is in Appendix A.
2 Preliminaries
Notations. For a set X, we denote ( as the set of probability distributions on X. For distribution E A(X') we define the shorthand for expectation and variance as Epp) [f] := (x-r) and
V Woolf] Ep() (E)))ff)² Given any set Q C A(X), we define the robust expectation
3

---

operator as Eolfl == inf De Ex-po For any a, E R, we denote (x)+ = max [2, 0} and x V = max a}. We use (-)) to hide absolute constant factors and use O to further hide logarithmic factors. For positive integer H E N4, we denote the set (1, H) by [H].
2.1 Robust Markoy Decision Processes
We first introduce our underlying model for doing robust RL, the episodic robust Markov decision process (RMDP), denoted by a tuple (S,A, H, Pt, R, +). Here the set S is the state space and the set A is the action space, both with finite cardinality. The integer H is the length of each episode. The set P PPt } h== is the collection of nominal transition kernels where P7 8 A + A(S). The set R Rg H h=1 is the collection of reward functions where R2 S x A + [0. 1]. For simplicity, we denote p = [P(+,.-) :): 8 x A A A(S) as the space of all possible transition kernels, and we denote S |S] and = LA,. Most importantl and different from standard MDPs, the RMDP is equipped with a mapping o : P + 2" that characterizes the robust set of any transition kernel in P. Formally, for any transition kernel P E P, we call (P) the robust set of One could interpret the nominal transition kernel P as the transition of the training environment, while o (PP) contains all possible transitions of the testing environments.
Given an RMDP (S, A. H, P* R. 4), we consider using a Markovian policy to make decisions. A Markovian decision policy (or simply, policy) is defined each step h E [H]. To measure the performance a policy æ in the RMDP, we introduce its robust value function, defined as for any (s, a) S A.
(Tx) h== with TA S A(A) for
H
E PA 1m VV, + (+) P.
inf
Ra(s;,
az)
8h =
H Σ
(..
E BOAAEL P
inf
(s az)
8h 8, Oh
Here the expectation is taken w.r.t. the state-action trajectories induced by policy under the transition P. One can also extend the definition of the robust value functions in terms of any collection of transition kernel P = (Ps } C P as V h. and Q &h which we usually use in the sequel.
Among all the policies, we define the optimal robust policy xe as the policy that can maximize the robust value function the initial time step h i.e.,
n E argmax VT Vsa S.
(2.1)
(
In other words, the optimal robust policy πt maximizes the worst case expected total rewards in all possible testing environments. For simplicity and without loss of generality, we assume in the sequel that the initial state $1 E S is fixed. Our results could be directly generalized to $1 ~ Po(.) E A(S). Similarly, we can also define the optimal robust policy associated with a given stochastic process defined through any collection of transition kernels P [P P in the same way as (2.1). We denote the optimal robust value functions associated with P as Vi, Vi.r. and Qi,r, respectively.
x A-rectangularrty and robust Bellman equations. We consider robust sets & that have the S x A-rectangular structure (Iyengar, 2005). which requires that the robust set is decoupled and independent across different (s, -piiss. This kind of structure results in a dynamic programming representation of the robust value functions (efficient planning), and is thus commonly adopted in the literature of distributionally robust RL. More specifically, we assume the following.
Assumption 2.1 (S Arretangularity) We assume that the mapping & satisfies for any transition kernel P E P, the robust set (P) is the form of
(P)
P(s, P),
where P(s,a; P) C
Sx.A)
Under above Assumption 2. we have the so-called robust Bellman equation (lyengar, 2005; Blanchet et al., 2023) which gives dynamic programming representation of robust value functions.

---

Proposition 2.2 (Robust Bellman equation), Under Assumption 2.1, for any transition P {Pr) - P and any policy {TA)i=1 with Ta S [(A), holds that
V. (+) (-1e) P,
(s, = Ra (8, a) + Pp)s,a:Pa) V+I.P
Regarding the robust value functions of the optimal robust policy, we also have the following dynamic programming solution which plays a key role in our algorithm design and theoretical analysis.
Proposition 2.3 (Robust Bellman optimal equation), Under Assumption 2.1, for any P {Pr) 1 P, the robust value functions of any optimal robust policy of P satisfies that,
(i) max aEAA
P. a),
(s. = (s, (s)sa,)) + Ep(s,a;P)) [
Taking (-16) argmax P. (8,a), then x²' {m is optimal robust policy under P.
Total-variation distance robust set. In Assumption 2.1, the robust set P(s, a; P) is often modeled as "distribution ball" centered at P(- (())s,a). In this paper, mainly consider this type of robust sets specified by total-variation distance ball. We put the following definition.
Definition 2.4 votta-variation distance robust set). Total-variation distance robust set is defined as (=(()))))))))
Ppls, a; P) P):= = (P() E A(S) : Drv (P()) sp]:
for some p E [0, 1), where DTV(-Il-) denotes the total variation distance defined as
1 Elp(s)
Drv (p(()(()))) = 2 SES
p(s) -(s), (pp))..())E E
(2.2)
The TV robust set has recently been extensively studied by Yang et al. (2022); Panaganti and Kalathil (2022); Panaganti et al. (2022); Xu et al. (2023); Blanchet et al. (2023); Shi et al. (2023), which all focus robust RL with a generative model or with pre-collected offline dataset. More importantly, we emphasize that by (2.2) in Definition 2.4, we do not define the TV distance through the notion of f-divergence which requires that the distribution p is absolute continuous w.r.t. q, is generally adopted by the above previous works on learning RMDPs with TV robust sets. According to (2.2), allow p have a different support than q. That is, there might exist an & S such that p(s) 0 and (ss) = 0. Given that, the TV robust set in Definition 2.4 could contain transition probabilities that have different supports than the nominal transition probability |* (-|ss a).
An essential property of the TV robust set that the robust expectation involved in the robust Bellman equations (Propositions 2.2 and 2.3) has duality representation that only uses the expectation under the nominal transition kernel, as is shown in the following theorem and proved in Appendix C.I.
Proposition 2.5 (Strong duality representation). Under Definition 2.4, the following duality repre- sentation for the robust expectation holds, for any V S + [0, H| and Pa S A (SS),
Ep [V]
{ --P,, f+1
(1 -in #ES
min V(s)) + +n} (2.3)
sup [][
Value gap between maximum and minimum. Finally, another useful property of the robust value functions of an RMDP with TV robust sets is a fine characterization of the gap between the maximum and the minimum of the robust value function, which is first identified and utilized by Shi et al. (2023) for an infinite horizon RMDP with TV robust sets. In this work, we prove and use a similar result for the finite horizon case, concluded in the following proposition. The proof is in Appendix C.2.
Proposition 2.6 (Gap between maximum and minimum). Under Assumption 2.1 with the robust set specified by Desinition 2.4, the robust value functions satisfies that
max (a.a)55xA
(s,
min (8,0)ESxA
(s, min {H,
max V SES
(T).P.
min
(T...(a) S min {1I, p-1)
SE
for any transition P = (P
P. any policy n, and any step h [H]]
5

---

2.2 Robust RL with Interactive Data Collection
We study how learn the optimal robust policy '² in (2.1) from interactive data collection. Specifi- cally, the learner is required to interact with only the training environment, i.., P* for some K E N episodes. each episode k the learner adopts a policy n² to interact with the training environment P and to collect data. When the k-th episode ends, the learner updates its policy to n**1 based on historical data and proceeds to the subsequent (I + 1-tth episode. The process ends after K episodes.
Sample complexity. We use the notion of sample complexity as the key evaluation metric. For any given algorithm and predetermined accuracy level E 0, the sample complexity is the minimum number of episodes K required for the algorithm to output an e-optimal robust policy मे satisfying Vi, (s1) p= ($1) S E. The goal is to design algorithms whose sample complexity has small or even optimal dependence on the problem parameters S, A, H, P. and 1/8.
Online regret. Another evaluation metric that is related to the minimization of sample complexity is the online regret, which is the cumulative difference between the optimal robust policy n' and the executed policies { K ===1- Formally, we define Regrel (K) := Σ Vi.r- + (81) Vir a (81 )- The goal to design algorithms that can achieve a sublinear-in -n regret with small dependence on S, A, H, p. It turns out that any sublinear-regret algorithm can be easily converted to polynomial-
sample complexity algorithm by applying the standard online-to to--atch conversion (Jin al., 2018).
Hardness Result: The Curse of Support Shift
Unfortunately, show in this section that in general such problem of robust RL with online data collection is impossible- - there exists simple class of two RMDPs such that an (2(K)-onlin regret lower bound exists. However, previous works on robust RL with generative model offline data with good coverage do provide sample-efficient ways to find the optimal robust policy for this class of RMDDs. This is separation between robust RL with interactive data collection and generative model/oftline data. Please see also Figure for an illustration of the example.
Example 3.1 (Hard example of robust RL with interactive data collection). Consider two RMDPs Ps Mo and Mi which only differ in their nominal transition kernels. The state space is S {ggoods Bhad } and the action space is A {0, 1). The horizon length H = 3. The reward function R always is I at the good state ggood and is 0 at the bad state Sbadi i.e.,
1, Rn(s, a) (0.
Sgood
AA
Sbad
For the good state Sgood, the next state is always Sgood- For the bad state Shad, there is chance to get to the good state Syood, with the transition probability depending on the action il takes. Formully,
Mo (Sgood i Sgood, a) === 1, V(a,h) Ax {1,2),
AO E {0,1).
M* " (Sgood Sbad, a)
P,
a= 0
0- V0 (0,
9, a
where p. q are two constants satisfying 0 < q < << < L. Intuitively, when at the bad state, the optimal action would result in a higher transition probability p to the good state than the transition probability q induced by the other action. Finally, we consider the robust set being specified by a total-variation distance ball centered at the nominal transition kernel, that is, for any P.
+ (P)) =
Pp(s,a;P),
(p() -
Drv (P()) s sp} (3.1)
(s,0)ESXA
where p E 10. q) is the parameter characterizing the size of the robust set. We set $1 Sgood-
For this class of RMDPs, we have the following hardness result for doing robust RL with interactive data collection, an O(p -online regret lower bound. The proof is in Appendix D.I.
Theorem 3.2 (Hardness result (based on Example 3.1)). There exists two RMDPs M1), the following regret lower bound holds,

---

Figure 1: Illustration of the hard example in Example 3.1. The solid lines represent possible transitions of the nominal transition kernel. The dashed lines represent the transitions induced by the worst case transition kernll in the robust set. The red solid line represents the transition where the two RMDP instances differ in that different actions lead to higher transition probability from Sbad to Sgood. We notice that when starting from #) = Sgood, the nominal tramsition kernel keeps the agent at $good and no information at Shad is revealed.
Ra
Rla m
Ra
inf sup E Regret
A00 (K)) 2(p (K)
HK).
ACG (0.1))
where Regret Me ACG (K) refers to the online regret of algorithm ALG for RMDP Ma.
+
The reason why any algorithm fails for this class of RMDPs is the support shift of the worst-case transition kernel. In robust RL, the performance of policy и is evaluated via the robust expected total rewards, or equivalently, the expected return under the most adversarial transition kernel pi. In such an example, as we explicitly show in the proof, when in the good state Sgood, the worst-case transition kernel pi. would transit the state Sbad with a constant probability p >> O. But the state Sbad is out of the scope of the data collection process because starting from $1 = Sgood the nominal transition kernel always transits the state to Syood. As result, the performance of the learned policy at the bad state Sbad is not guaranteed, and inevitably incurs an S2 K) Jlower bound of regret, hardness result. Furthermore, by strategically constructing RMDPs with the horizon 3H based on Example 3.1, we can derive lower bound of Mpp HK). See Appendix B.3 for more discussions.
4 A Solvable Case, Efficient Algorithm, and Sharp Analysis
Motivated by the hard instance (Example 3.1), we now investigate a special subclass of RMDPs with S x A-rectangular total variation robust set that we show allows for doing sample-efficient robust RL through interactive data collection. In Section 4.1, we introduce the assumption we impose on the RMDP. We propose our algorithm design in Section 4.2, with theoretical analysis in Section 4.3.
4.1 Vanishing Minimal Value: Eliminating Support Shift
To overcome the difficulty of support shift identified in Section 3, we make the following vanishing minimal value assumption on the underlying RMDP.
Assumption 4.1 (Vanishing minimal value). We assume that the underlying RMDP satisfies that minses Vi.P.. (s) = O. Also, WLOG, we assume that the initial state $1 & argmin Vī,P. + (s).
Assumption 4.1 imposes that the minimal robust expected total rewards over all possible initial states O. Assuming that the initial state $1 & argmin, Vi,PP: + (s) avoids making the problem trivial. A close look at Assumption 4.1 actually gives that the minimal robust value function of any policy и at any step is zero, that is, minges W..P....C observation, the following proposition explains why this assumption helps overcome the difficulty, with the proof of the proposition in Appendix C.3.
for any policy л and any step E [H]. With this
Proposition 4.2 (Equivalent expression of TV robust set with vanishing minimal value). For any function V : S [0, H] with min,es V(s) = 0, we have that
Pppla.:P)) [ = p' E E.,.,.. with P p==
-
2 >0 0,
where the TV robust set P,(s, a; Př) is defined in (3.1) and the set Br (s, o; Ph)) is defined as
P(s!) ''ES PT
1
(s, P()) A(S) sup
S
p
2 Here implicitly detine 0 = 0 0/2 = for any 0.
7

---

Algorithm 1 OPtimistic RObust Value Iteration for TV Robust Set (OPROVI-TV)
1: Initialize: dataset D Ø.
2: for episode 1,..................... K do
3: Training environment transition estimation:
4: Update the count functions (s, a, s') and (s, based on D.
5: Calculate the transition kernel estimator h (1
6: Optimistic robust planning:
Set V #+1 V H-1 =0. O.
7:
8:
for step h = ..... ... . do
Set (*())) and 2% (4.2) and (4.3), with (o defined in (4.5).
9:
Set (1)) = a a)) Vx()) = Eagct (x and (h() =
10:
(20 end for
11:
12:
Execute the policy in training environment and collect data:
13: Receive the initial state of S.
14:
for step h = I,...
do
15:
Take action af ~ (115)),, observe reward Ry af) and the next state $
16: end for
17: Set ID as D {(sh a +
18:
end for
19: Output: Randomly (uniformly) return a policy from { Ik=1-
K
As Proposition 4.2 indicates, under Assumption 4.1, the robust Bellman equations (Propositions 2.2 and 2.3) at step / E [H] is equivalent to taking an infimum over another robust set B, (s, a; P%) that shares the same support as the nominal transition kernel (* a),, discounted by constant p' < 1. Intuitively, this new robust set rules out the difficulty originated in unseen states in training environments and the discount factor p' hedges the difficulty from prohibitively small probability of reaching certain states that may appear often in the testing environments. This renders robust RL with interactive data collection possible. See Appendix B.4.1 for discussionseexmmple of Assumption 4.1.
4.2 Algorithm Design: OPROVI-TV
In this section, we propose our algorithm that solves robust RL with interactive data collection for RMDPs with S x A-rectangulaa total-variation (TV) robust sets (Assumption 2.1 and Defini- tion 2.4) and satisfying the vanishing minimal value assumption (Assumption 4.1). Our algorithm, OPtimistic RObust Value Iteration for TV Robust Set (DPROVI-TV. Algorithm 1), can automatically balance exploitation and exploration during the interactive data collecting process while managing the distributional robustness of the learned policy. The full algorithm OPROVI-TV is given in Algorithm 1.
Step I: Training Environment Transition Estimation (Line 3 to 5). At the beginning of each episode & E [K], we maintain an estimate of the transition kernel Pa of the training environment by using the historical data IB = {(ST, oh ))= collected from the interactiion with the training environment. Specifically, we simply adopt a vanilla empirical estimator, defined as Ph (s'ls,,, [ss a) = Ni a, ( (s, a) V 1) for any (s, a, s', E S x A x S x [M], where the count functions N8 a, s') and N/ (s. a) are calculated based on the current dataset D by a,,as) s')} and N a) Eves (s, a, s') for any (s,a, h, s') S x Axx S (H). This just coincides with the transition estimator adopted by existing non-robust online RL algorithms (Auer et al., 2008; Azar et al., 2017: Zhang et al., 2021).
(s, s') D==1 (( aT (41))=
Step II: Optimistic Robust Planning (Line to 11). Given 2* (-1--) that estimates the training environment, we perform an optimistic robust planning to construct the policy nh execute. Basically, the optimistic robust planning follows the robust Bellman optimal equation (Proposition 2.3) to approximate the optimal robust policy, but differs in that maintains an upper bound and lower bound of the optimal robust value function and chooses the policy that maximizes the optimistic

---

estimate to incentivize exploration during data collection. Here the purpose of maintaining the lower bound estimate facilitate the construction of the variance-aware optimistic bonus (see following). which helps to sharpen our theoretical analysis.
Simplifying the robust expectation. To utilize the vanishing minimal value condition (Assump- tion 4.1), we take a closer look into the robust Bellman equation. By strong duality (Proposition 2.5), the robust expectation Epp(s,a;P)
[V] for any V E [0, HI] satistying minses Vss) = - is equivalent to
{
- -EP(taaa (1
(1-v)), v)+ + (1-2)-n) }
E Epo(s.ap)
sup ne (0.
(4.1)
Consequently, with slight abuse of the notation, in the remaining of the paper, re-define the operator (s..P)) [V] as the right hand side of (4. Due to Assumption 4.1, the robust Bellman (optimal) equation (Proposition 2.2 and Proposition 2.3) still holds under this new definition.
> Optimistic robust planning. With this in mind, the optimistic robust planning goes as follows. Starting from 'H+1" V O. we recursively define that for any a) E E x A.
() min (sn(s,a) +R,,,E.... Pa(.aa
V h+1
bonus (s, a), min { (H {}
(4.2)
(s,a) max (R, + E Bpplsaa
V k+1
bs.
(4.3)
where the robust expectation 1Ep (r,.P..t follows the definition in the right hand side of (4.1), and the bonus function bonus a) 2 0 is defined later. Here we truncate the optimistic estimate 4% via the upper bound min H, } of the true optimal robust value function Qi, + This truncation arises from the combined implication of Proposition 2.6 and the fact that min(s,,)) Qh, p. a (s, a) = 0 under Assumption 4.1. As we establish in Lemma E.2, Th and Ot form upper and lower bounds for Ph, a and Qh, & under proper choice of the bonus. After performing (4.2) and (4.3), we choose the data collection policy ~ to be the optimal policy with respect to the optimistic estimator Qn and define V/d and VL. accordingly by hh
n (-I-)) argmax Q)())), Vh((s= (1 (M(s.)) ). aEA
(x(s 1x [ (s.-)) }) (4.4)
We remark that the purpose of maintaining the lower bound estimate (4.3) is to facilitate the construc- tion of the bonus and to help sharpen our theoretical analysis. The construction of the policy n² is still based the optimistic estimator, which is why we call it optimistic robust planning. As indicated by theory, the optimistic robust planning can effectively guide the policy to explore uncertain robust value function estimates, striking balance between exploration and exploitation while managing distributional robustness.
Bonus function. The bonus function bonus (s, a) is Bernstein-style bound defined as
V ()
(vh h+1 Vh
12 C14
2E (t
V/ k++1
c2 1 VK"
(4.5)
(x, V1
H
(s,
where A AH2K3/2 8), c2 are absolute constants, and 5 signifies pre-selected fail probability. Under (4.5), Q and Q², become upper and lower bounds of the optimal robust value functions (Lemma E.2). More importantly, the bonus (4.5) is carefully designed for robust value functions such that the summation of this bonus term (especially the leading variance term in (4.5)) over time steps is well controlled, for which we also develop new analysis methods. This is critical for obtaining a sharp sample complexity of Algorithm 1.
4.3 Theoretical Guarantees
This section establishes the online regret and the sample complexity of OPROVI-TV (Algorithm 1). Our main result is the following, upper bounding the online regret of Algorithm 1, proved in Appendix E.

---

Theorem 4.3 (Online regret of OPROVI-TV, Given an RMDP with S x A-rectangular tatal-variation
robust set of radius p E [0, 1) (Assumption 2.1 and Definition 2.4) satisfying Assumptions 4.
choosing the bonus function as (4.5) with sufficiently large cı, C2 > 0, then with probability at least 1 6, Algorithm I satisfies
Regret + (K) S O(vmin (
where d' = log (SAHK/6) and (c) hides absolute constants and lower order terms in K.
Theorem 4.3 shows that Algorithm I enjoys sublinear online regret of K) meaning that it is able to approximately find the optimal robust policy through interactive data collection. This is in contrast with the general hardness result in Section 3 where sample-efficient learning is impossible in the worst case. Thus we show the effectiveness of the minimal value assumption for robust RL with interactive data collection. As corollary, we have the following sample complexity bound for Algorithm 1. It is obtained directly from Theorem 4.3 and a standard online to batch conversion.
Corollary 4.4 (Sample complexity of OPROVI-TV), Under the same setup and conditions as in Theorem 4.3, with probability at least - 6, Algorithm I can output an s-optimal policy within
O (min p -
(4.6)
episodes, where 1" = log (S /88) and (c)) hides absolute constants. The valid range of e satisfies 8 E (0 min 1/ for some constant e 0.
We compare the sample complexity (4.6) with prior arts on non-robust online RL and robust RL with a generative model. On the one hand, (4.6) with 0 equals to S(H=" matching the minimax sample complexity lower bound for online RL in non-robust MDPs (Azar al., 2017). This means that our algorithm design can naturally handle non-robust MDPs as a special case (please also see Remark B.4 for why one can reduce Algorithm to general non-robust MDPs under Assumption 4. 1. On the other hand, the previous work of Shi et al. (2023) for robust RL in infinite horizon RMDPs with TV robust set and generative model showcases a minimax optimal sample complexity of
① (min H -
for p [0, 1), where we H. (1) is the effective horizon of the infinite y-discounted RMDPs. As result, the sample complexity (4.6) of Algorithm matches their result. We highlight that our algorithm does not rely on generative model and operates purely through interactive data collection.
Extensions of Algorithm and its theory. In Appendix B.4.2, we extend Algorithm to solve type of RMDPs whose robust set consists of transition probabilities with bounded ratio to the nominal kernel. The intuition is because it is equivalent to the S x A-rectangular RMDP with TV robust set and vanishing minimal value assumption in appropriate sense (Proposition 4.2) Consequently, by a clever usage of Algorithm 1, we can also solve this new model sample-efficient as is shown in Corollary B.5. Such result echoes our intuition the curse of support shift.
5 Conclusions and future works
This work shows that in the absence of any structural assumptions, robust RL via interactive data collection necessarily induces linear regret lower bound the worst case due the curse of support shift. Under the vanishing minimal value assumption, an assumption that is able to effectively rule the potential support shift issues for RMDPs with a TV robust set, we propose sample-efiie efficieen robust RL algorithm for those RMDPs with sharp analysis. Potential future works include extending to function approximation settings and other types of robust sets. See discussion in Appendix B.5.
Acknowledgments and Disclosure of Funding
The material in this paper is based upon work supported by the Air Force Office of Scientific Research under award number FA9550-20- 20-1-0397. Additional support is gratefully acknowledged from NSF 1915967, 21 18199, 2229012, 2312204. The authors would like to thank the anonymous reviewers for their helpful comments. The authors would also like to thank Pan Xu and Zhishuai Liu for their feedback early draft of this work.
10

---

References
AGARWAL, A., JIANG, N., KAKADE, S. M. and SUN, W. (2019). Reinforcement learning: Theory and algorithms. CS Dept., UW Seattle, Seattle, WA, USA, Tech. Rep 10-4. 44
AGARWAL, A., JIN, Y. and ZHANG, (2023). Vo q Towards optimal regret in model-free rl with nonlinear function approximation. In The Thirty Sixth Annual Conference on Learning Theory.
PMLR. 16, 17
AUER, P., JAKSCH, and ORTNER, R. (2008). Near-optimal regret bounds for reinforcement learning. Advances in neural information processing systems 21. 8
AYOUB, A., JIA, Z., SZEPESVARI, C., WANG, M. and YANG, L. (2020). Model-based reinforcement learning with value-targetes regression. In International Conference on Machine Learning. PMLR.
16
AZAR, M. G., OSBAND, and MUNOS, R. (2017). Minimax regret bounds for reinforcement learning. In International Conference Machine Learning. PMLR. 8, 10, 16, 41
BADRINATII, K. and KALATIIL, D. (2021). Robust reinforcement learning using least squares policy iteration with provable performance guarantees. In International Conference on Machine Learning. PMLR. 16
BLANCHET, J., LU, M., ZILANG, T. and ZIIONG, H. (2023). Double pessimism provably efficient for distributionally robust offline reinforcement learning: Generic algorithm and robust partial coverage. arXiv preprint arXiv:2305.066.
2, 3, 4, 16, 17, 18, 21, 24
CLAVIER, P., PENNEC, E. L. and GEIST, M. (2023). Towards minimax optimality of model-based robust reinforcement learning, arXiv preprint arXiv:2302.0532.. 16
DANN, C., LATTIMORE, T. and BRUNSKILL, E. (2017). Unifying pac and regret: Uniform pac bounds for episodic reinforcement learning. Advances in Neural Information Processing Systems 30.
DING, W., SHI, L.., CHI, Y. and ZHAO, D. (2024). Seeing is not believing: Robust reinforcement learning against spurious correlation. Advances Neural Information Processing Systems 36. 16
DONG, LI, J., WANG, B. and ZHANG, J. (2022). Online policy optimization for robust mdp. arXiv preprini arXiv:2209. 2389/ 17
DU, S., KAKADE, S., LEE, J., LOVETT, S., MAHAJAN, G., SUN, W. and WANG, R. (2021). Bilinear classes: A structural framework for provable generalization in rl. In International Conference on Machine Learning. PMLR. 16
EL GHAOUI, L. and NILIM, A. (2005). Robust solutions markov decision problems with uncertain transition matrices. Operations Research 53 780-798. 16
FOSTER, D. J., KAKADE, S. M., QIAN, J. and RAKHLIN, A. (2021). The statistical complexity of interactive decision making. arXiv preprint arXiv:2112.13487. 16
HE, J., ZHAO, H., ZHOU, D. and GU, Q. (2023). Nearly minimax optimal reinforcement learning for linear markov decision processes. In International Conference Machine Learning. PMLR. 16
HU, J., ZHONG, H., JIN, C. and WANG, L. (2022). Provable sim-to-real transfer in continuous domain with partial observations. arXiv preprint arXiv:2210.1599.
HUANG, J., ZHONG, H., WANG, L. and YANG, L. F. (2023a). Horizon-free and instance-dependent regret bounds for reinforcement learning with general function approximation. arXiv preprint arXiv:2312.04464. 17
HUANG, J., ZHONG, H., WANG, L. and YANG, L. F. (2023b). Tackling heavy-tailed rewards in reinforcement learning with function approximation: Minimax optimal and instance-dependent regret bounds. arXiv preprint 236.00666 16

---

IYENGAR, G. N. (2005). Robust dynamic programming. Mathematics of Operations Research 30
257-280. 2, 4, 16, 17
JIANG, N., KRISHNAMURTHY, A., AGARWAL, A., LANGFORD, and SCHAPIRE, R. E. (2017).
Contextual decision processes with low bellman rank are pac-learnable. In International Conference on Machine Learning. PMLR. 16
JIN, C., ALLEN-ZHIE -HU, Z., BUBECK, S. and JORDAN, M. (2018). Is q-learning provably efficient? Advances in neural information processing systems 31. 6, 16
JIN, C., LIU, Q. and MIRYOOSEFI, S. (2021). Bellman eluder dimension: New rich classes of rl problems, and sample-efficient algorithms. Advances neural information processing systems 34 14406-13418. 16
JIN, C.. YANG, Z., WANG, Z. and JORDAN, M. I. (2020). Provably efficient reinforcement learning with linear function approximation. In Conference on Learning Theory. PMLR. 16
KIRAN, B. R., SOBH, I., TALPAERT, V., MANNION, P., AL SALLAB, A. A., YOGAMANI, and PÉREZ, P. (2021). Deep reinforcement learning for autonomous driving: A survey. IEEE Transactions on Intelligent Transportution Systems 4909-4926.
KOBER, J., BAGNELI, J. A. and PETERS, (2013). Reinforcement learning roboties: A survey. The International Journal of Robotics Research 32 2238-1274.
KUANG, Y., LU, M., WANG, J., ZHOU, Q.. LI, B. and LI, H. (2022). Learning robust policy against disturbance in transition dynamics via ctste-conservattie policy optimization. In Proceedings of the AAAI Conference on Artificial Intelligence, vol. 36. 2, 16
LI, G., CAL, C., CHEN, Y., WEI, Y. and CHI, Y. (2023). Is q-learning minimax optimal? a tight sample complexity analysis. Operations Research. 16
LI, Y. and LAN, G. (2023), First-order policy optimization for robust policy evaluation. arXiv preprint ar 2xXi:2307.15800 16
LIU, Z.,, LU, M., WANG, Z., JORDAN, M. and YANG, Z. (2022). Welfare maximization in competitive equilibrium: Reinforcement learning for markov exchange economy. International Conference on Machine Learning. PMLR. 17
LIU, Z., LU, M., XIONG, W., ZHONG, H., HU, H., ZHANG, S., ZHENG, S., YANG, Z. and WANG, Z. (2023). One objective to rule them all: maximization objective fusing estimation and planning for exploration. arXiv preprint arXiv:2305. 18258. 17
LIU, Z. and XC, P. (2024a). Distributionally robust off-dynamics reinforcement learning: Provable efficiency with linear function approximation. arXiv preprint arXiv:2402.15399 16
LIU, Z. and Xu, P. (2024b). Minimax optimal and computationally efficient algorithms for distribu- tionally robust offline reinforcement learning. arXiv preprint arXiv:2403.0962// 16
LYKOURIS, T., SIMCHOWITZ, M., SLIVKINS, A. and SUN, W. (2021). Corruption-robuse explo- ration in episodic reinforcement learning. Conference on Learning Theory. PMIR. 17
MA. X.. LIANG, Z., XIA, L.., ZHANG, J., BLANCHET, J., LIU, M., ZHAO, Q. and ZHOU, Z. (2022). Distributionally robust offline reinforcement learning with linear function approximation. arXiv preprint arXiv:2209. 066200 2, 16
MAURER, A. and PONTIL, M. (2009). Empirical bernstein bounds and sample variance penalization. arXiv preprint arXiv:0907.3740. 29
MÉNARD, P., DOMINGUES, O. D., SHANG, X. and VALKo, M. (2021). Ucb momentum q-learning: Correcting the bias without forgetting. In International Conference on Machine Learning. PMLR. 16
Moos, J., HANSEL, K., ABDULSAMAD, H., STARK, S., CLEVER, D. and PETERS, J. (2022). Robust reinforcement learning: A review of foundations and recent advances. Machine Learning and Knowledge Extraction 4 276-315. 2
12

---

OUYANG, L., WU, J., JIANG, X., ALMEIDA, D., WAINWRIGHT, C.. MISHKIN, P., ZHANG, C.. AGARWAL, S., SLAMA, K., RAY. A. AL. (2022). Training language models to follow instructions with human feedback. Advances in Neural Information Processing Systems 35 27730- 27744.
PANAGANTI, K. and KALATHIL, D. (2022). Sample complexity of robust reinforcement learning with a generative model. In International Conference on Artificial Intelligence and Statistics.
PMLR. 2, 5, 16, 17, 18
PANAGANTI, K., Xu, Z., KALATHIL, D. and GHAVAMZADEH, M. (2022). Robust reinforcement learning using offline data. arXiv preprint arXiv:2208.05/29, 2,3,5, 16, 17, 18, 19
PENG, X. B., ANDRYCHOWICZ, M., ZAREMBA, W. and ABBEEL, P. (2018). Sim-to-real transfer of robotic control with dynamics randomization. In 2018 IEEE international conference on robotics and automation (ICRA). IEEE.
PINTO, L., DAVIDSON, J., SUKTHANKAR, and GUPTA, A. (2017). Robust adversarial reinforee- ment learning. In International Conference on Machine Learning. PMLR. 2
SADEGHI, F. and LEVINE, S. (2016). Cad2rl: Real single-image flight without single real image. arXiv preprint
SIII, L. and CIII, Y. (2022). Distributionally robust model-based offline reinforcement learning with near-optimal sample complexity. arXiv preprint arXiv:2208.05767. 2. 16, 21
SHI, L., LI, G., WEI, Y., CHEN, Y., GEIST, M. and CHI, Y. (2023). The curious price of distributional robustness in reinforcement learning with a generative model. arXiv preprint arXiv:2305. 16589. 2, 3, 5, 10, 16, 17, 18, 21, 23
SI, N., ZHANG, F., Znou, Z. and BLANCHET, (2023). Distributionally robust batch contextual bandits. Management Science. 16
SILVER, D., SCHRITTWIESER J., SIMONYAN, K., ANTONOGLOU, I., HUANG, A., GUEZ, A.,
HUBERT, T., BAKER, L., LAI, M., BOLTON, A. ET AL. (2017). Mastering the game of go without
human knowledge. nature 550 354 359-359.
SUN, W., JIANG, N., KRISHNAMURTHY, A., AGARWAL, A. and LANGFORD, (2019). Model- based rl in contextual decision processes: Pac bounds and exponential improvements over model- free approaches. In Conference on learning theory. PMLR. 16
SUTTON, R. S. and BARTO, A. G. (2018). Reinforcement learning: An introduction. MIT press.
WANG, H., SHI, L. and CHI, Y. (2024). Sample complexity of offline distributionally robust linear markov decision processes. arXiv preprint arXiv:2403. 12946 16
WANG, L., ZHANG, W., HE, X. and ZHA, H. (2018). Supervised reinforcement learning with recurrent neural network for dynamic treatment recommendation. In Proceedings of the 24th ACM SIGKDD international conference on knowledge discovery & data mining. 1
WANG, Q.. Ho, C. P. and PETRIK, M. (2022). On the convergence of policy gradient in robust mdps. arXiv preprint arXiv:22/2. 16
WANG, Q., Ho, C. P. and PETRIK, M. (2023a). Policy gradient in robust MDPs with global convergence guarantee. In Proceedings of the 40th International Conference on Machine Learning (A. Krause, Brunskill, K. Cho. B. Engelhardt, S. Sabato and J. Scarlett, eds.), vol. 202 of Proceedings of Machine Learning Research. PMLR. 16
WANG, S., SI, N., BLANCHET, J. and ZHOU, Z. (2023b). A finite sample complexity bound for distributionally robust q-learning. In International Conference on Artificial Intelligence and Statistics. PMLR. 16
WANG, S., SI, N., BLANCHET, J. and ZHOU, Z. (2023c). On the foundation of distributionally robust reinforcement learning, arXiv preprint arXiv:2311.00018 16
13

---

WANG, S., S1, N., BLANCHET, J. and ZHOU, Z. (2023d). Sample complexity of variance-reduced
distributionally robust q-learning. arXiv preprint arXiv:2305.18420. 16
WANG, Y. and ZoU, S. (2021). Online robust reinforcement learning with model uncertainty,
Advances in Neural Information Processing Systems 34 7193-7206. 16
WANG, Y. and Zou, S. (2022). Policy gradient method for robust reinforcement learning. In International Conference on Machine Learning. PMLR. 16
WEI, C.-Y., DANN, C. and ZIMMERT, J. (2022). A model selection approach for corruption robust reinforcement learning. In International Conference on Algorithmic Learning Theory. PMLR. 17
WIESEMANN, W., KUHN, D. and RUSTEM, B. (2013). Robust markov decision processes. Mathe- matics of Operations Research 38 153-183. 16
WU, T., YANG, Y., ZHONG, H., WANG, L., Du, S. and JIAO, (2022). Nearly optimal policy optimization with stable at any time guarantee. In International Conference on Machine Learning. PMLR. 16
XU, and MANNOR, S. (2010). Distributionally robust markov decision processes. Advances in Neural Information Processing Systems 23. 16
XU, Y. and ZEEVI, A. (2023). Bayesian design principles for frequentist sequential learning. In International Conference on Machine Learning. PMLR. 17
XU, Z., PANAGANTI, K. and KALATHIL, D. (2023). Improved sample complexity bounds for distributionally robust reinforcement learning. International Conference on Artificial Intelligence and Statistics. PMLR. 2, 3, 5, 16, 17, 18, 21
YANG, R., ZHONG, H., Xu, J., ZHANG, A., ZHANG, C., HAN, L. and ZHANG, T. (2023a). Towards robust offline reinforcement learning under diverse data corruption. arXiv preprint arXiv:2310.1290 12955....22....... 17
YANG, W., WANG, H., KOZUNO. T., JORDAN, S. M. and ZHANG, Z. (2023b). Avoiding model estimation in robust markov decision processes with a generative model. arXiv preprint
arXiv:2302.01228.. 16
YANG, W., ZHANG, L. and ZHANG, Z. (2022). Toward theoretical understandings of robust markov decision processes: Sample complexity and asymptotics. The Annals of Statistics 50 3223-3248. 2, 5, 16, 17, 18, 21
YE, C., HE, J., GU, Q. and ZHANG, T. (2024). Towards robust model -based reinforcement learning against adversarial corruption. arXiv preprint arXiv:2402.08991 17
YE, C., XIONG, W., GU, Q. and ZHANG, T. (2023a). Corruption-robur algorithms with uncertainty weighting for nonlinear contextual bandits and markov decision processes. In International
Conference on Machine Learning. PMLR. 17
YE, C., YANG, R., GU, Q. and ZHANG, T. (2023b). Corruption-robust offline reinforcement learning with general function approximation. arXiv preprint arXiv:2310.14:: 14550. 17
Yu, Z.,, DAI, L., XU, S., GAO, S. and Ho, C. P. (2023). Fast bellman updates for wasserstein distributionally robust mdps. In -hirth-seventh Conference on Neural Information Processing Systems. 16
ZANETTE, A. and BRUNSKILL, E. (2019). Tighter problem-dependent regret bounds in reinforce- ment learning without domain knowledge using value function bounds. In International Conference on Machine Learning. PMLR. 16
ZHANG, X., CHEN, Y., ZHU, X. and SUN, W. (2022). Corruption-robus offline reinforcement learning, International Conference on Artificial Intelligence and Statistics. PMLR. 17
ZHANG, 7.,, CHEN, Y., LEF, J. D. and Du, S. (2023). Settling the sample complexity of online reinforcement learning, arXiv preprint arXiv: 13586
16
14

---

ZHANG, Z., JI, X. and Du, S. (2021). Is reinforcement learning more difficult than bandits? near-optimal algorithm escaping the curse of horizon. In Conference on Learning Theory. PMLR. 8. 16
ZIIANG, Z., ZIOO, Y. and JI, X. (2020). Almost optimal model-free reinforcement learningvia reference-adwee advanaage decomposition. Advances in Neural Information Processing Systems 33 15198-15207. 16
ZHAO, W., QUERALTA, J. P. and WESTERLUND, T. (2020). Sim-to-real transfer in deep rein- forcement learning for robotics: a survey. In 2020 IEEE Symposium Series on Computational Intelligence (SSCI). IEEE.
ZHONG, H., XIONG, W., ZHENG, S., WANG, L., WANG, Z., YANG, Z. and ZHANG, T. (2022). Gec: A unified framework for interactive decision making in mdp, pomdp, and beyond. arXiv preprint xxX1:2211..0192.. 17
ZHONG, H. and ZHANG, (2023). A theoretical analysis optimistic proximal policy optimization in linear markov decision processes. arXiv preprint (tt.:2305508841 16
ZHOU, D., GU, Q. and SZEPESVARI, C. (2021a). Nearly minimax optimal reinforcement learning for linear mixture markov decision processes. In Conference on Learning Theory. PMLR. 16
ZHOU, R., LIU, T., CHENG, M., KALATHIL, D., KUMAR, P. and TIAN, C. (2023). Natural actor- critic for robust reinforcement learning with function approximation. In Thirfy-seventh Conference on Newral Information Processing Systems. 16
ZHOU, Z., ZHOU, Z., BAI, Q.. QIU, L., BLANCHET, J. and GLYNN, P. (2021b). Finite-sample regret bound for distributionally robust offline tabular reinforcement learning. In International Conference on Artificial Intelligence and Statistics. PMLR. 2, 16
15

---

A Related Works
We give a detailed discussion on the related works in this section.
Robust reinforcement learning in robust Markov decision processes. Robust RL is usually framed as a robust Markov decision process (RMDP) (lyengar, 2005; El Ghaoui and Nilim, 2005; Wiesemann et al., 2013). There is a long line of work dedicated to the problem of how to solve for the optimal robust policy of given RMDP, i... planning (Lyengar, 2005: EI Ghaoui and Nilim, 2005;
Xu and Mannor, 2010; Wang and Zou, 2022; Wang et al., 2022; Kuang et al., 2022; Wang et al., 2023a; Yu et al.. 2023; Zhou et al., 2023; Li and Lan, 2023: Wang et al., 2023c; Ding et al., 2024). Recently, the community has also witnessed a growing body of work on sample-effiiient robust RI. in RMDPs with different data collection oracles, including the generative model setup (Yang et al., 2022; Panaganti and Kalathil, 2022; Si et al., 2023; Wang et al., 2023b; Yang et al., 2023b; Xu et al., 2023; Clavier et al., 2023; Wang ct al.. 2023d; Shi et al., 2023), offline setting (Zhou et al., 2021b; Panaganti et al., 2022; Shi and Chi, 2022: Ma et al., 2022; Blanchet et al., 2023; Liu and Xu, 2024b; Wang et al., 2024), and interactive data collection setting (Badrinath and Kalathil, 2021; Wang and Zou, 2021; Liu and Xu, 2024a).
Our work falls into the paradigm of sample- robust RL with interactive data collection. Wang and Zou (2021) and Badrinath and Kalathil (2021) propose efficient online learning algorithms to obtain the optimal robust policy of an infinite horizon RMDP, but none of them handle the challenge of exploration in online RL by assuming the access to explorative policies. This assumption enables the contrast,
learner collect high-quality data essential for effective learning and meaiii.nnmmaking our work focuses developing efficient algorithms for the fully online setting, where there is no predefined exploration policy to use. Under this more challenging setting, we address the exploration challenge through algorithmic design rather than relying assumed access to explorative policies.
During the preparation of this work, we are aware of several concurrent and independent works (Liu and Xu, b024a,b; Wang et al., 2024), which study a different type of RMDPs known as d-rectangular linear MDPs (Ma al., 2022: Blanchet et al., 2023). In particular, Liu and Xu (2024b) and Wang et al. (2024) consider the offline setting, while Liu and Xu (2024a) investigate robust RL through interactive data collection (off-dynamics learning), thus bearing closer relevance to our work. More specifically, under the existence of a "fail-state", the algorithm in Liu and Xu (2024a) can learn an e-optimal robust policy with provable sample efficiency. In contrast, our work first explicitly uncovers the fundamental hardness of doing robust RL in RMDPs with TV distance based robust set and without additional assumptions. To overcome the inherent difficulty, we adopt a vanishing minimal value assumption that strictly generalizes the "fail-state" assumption used in Liu and Xu (2024a). Moreover, our focus is on tabular x A-rectangular RMDPs, with customized algorithmic design and theoretical analysis which allow to obtain sharp sample complexity bound.
Finally, in Table I, we compare the sample complexity of our algorithm with prior work on robust RL. for RMDPs with S x A-rectangular TV robust sets under various settings (generative model/offline dataset). We remark that the works of Panaganti and Kalathil (2022) and Blanchet et al. (2023) are in the paradigm of function approximation, and here we reduce their general sample complexity result to the tabular setup we consider.
Sample-efficient online non-robust reinforcement learning. Our work is also closely related to online non-robust RL, which is often formulated as a Markov decision process (MDP) with online data collection. For non-robust online RL, the key challenge is the peploration-explotattaee
tradeoff. There has been a long line of work (Azar et al., 2017; Dann et al., 2017: Jin et al., 2018; Zanette and Brunskill, 2019; Zhang et al., 2020, 2021; Ménard et al., 2021; Wu et al., 2022; Li et al., 2023; Zhang et al., 2023) addressing this challenge in the context of tabular MDPs, where the state space and action space are finite and also relatively small. In particular, many algorithms (e.g., UCBVI in Azar et al. (2017)) have been proven capable of finding an e-optimal policy within S(HSSA/E sample complexity. Notably, a standard MDP corresponds to an RMDP with a TV robust set and
= 0. suggesting that OPROVI-TV can naturally achieve nearly minimax- -otimaaltyy for non-ro RL. Moving beyond the tabular setups, recent works also investigate online non-robust RL with linear function approximation (Jin et al., 2020; Ayoub et al., 2020: Zhou et al., 2021 la; Zhong and Zhang, 2023; Huang et al., 2023b; He et al., 2023; Agarwal et al., 2023) and even general function approximations (Jiang et al., 2017; Sun et al., 2019; Du et al., 2021; Jin et al., 2021; Foster et al.,
16

---

2021; Liu et al., 2022: Zhong et al., 2022; Liu et al., 2023; Huang et al., 2023a; Xu and Zeevi, 2023; Agarwal al., 2023).
Corruption robust reinforcement learning. Generally speaking, our research is also related to another form of robust RL, namely corruption robust RL (Lykouris et al., 2021; Wei et al., 2022; Zhang et al., 2022; Ye et al., 2023a,b; Yang et al., 2023a; Ye et al., 2024). This branch of researches on robust RL addresses scenarios where training data is corrupted, presenting a distinct challenge from distributionally robust RL. The latter concerns testing time robustness, where the agent is evaluated a perturbed environment after being trained on nominal data. These two forms of robust RL, while sharing the overarching goal to enhance agent resilience, operate within different contexts and confront distinct challenges. Thus, a direct comparison between these two types robust RL is difficult because each addresses unique aspects of resilience.
B Further Discussions
This section complements the main part of the paper by further commenting and discussing several aspects of the paper. Due to space limits, these important remarks are provided here.
B.1 Discussions on Introduction (Section
About a generative model and a simulator. A generative model here means a mechanism that when queried some state, action, and time step, returns sample of next state. Here we distinguish this notion with the notion of simulator or simulated environment which generally refers to a human- made training environment that mimics the real-world environment. With a generative model on hand, interactive data collection is no longer needed, but in simulated environment, it is common to train a robust policy through interactive data collection in practice.
The definition of total-variation robust set. We notice that all of the previous work on sample- efficient robust RL in RMDPs with TV robust sets (Yang et al., 2022; Panaganti and Kalathil, 2022; Panaganti et al., 2022; Xu et al., 2023; Blanchet et al., 2023; Shi et al., 2023) relies defining the TV distance through the general f-divergence so that a strong duality representation holds. But this implicitly requires the testing environment transition probability is absolute continuous w.r.t. the training environment transition probability. In this paper, we do not make such restriction. We prove the same strong duality even if the absolute continuity does not hold. In fact, all the previous work can be directly extended to such TV distance definition via our more general strong duality result.
An existing work. We note that existing work (Dong et al., 2022) also studies the problem of robust RL with interactive data collection. They study x A-rectangular RMDPs with a TV robust set, assuming that the support of the training environment transition is the full state space S. They claim the existence of an algorithm that enjoys a Ō (e))-Koooiin regret. We point out that their proof exhibits an essential flaw (misuse of Lemma 12 therein) and therefore the regret they claim is invalid.
The range of the robust set size p. We do not signify the situation when p since in that case the TV robust set contains all possible transition probabilities, making the problem statistically trivial. In that case, no sample is needed.
B.2
Discussions on Preliminaries (Section
B.2.1 Robust Markoy Decision Processes
Robust Bellman equations. We remark that the original version of the robust Bellman equation (lyengar, 2005) is for infinite horizon RMDPs and customized proof of robust Bellman equation for finite horizon RMDPs (Proposition 2.2) can be found in Appendix A. of Blanchet et al. (2023). The robust Bellman optimal equation (Proposition 2.3) is then a corollary or can be proved similarly.
Strong duality under TV distance robust set. An essential property of the TV robust set is that the robust expectation involved in the robust Bellman equations (Propositions 2.2 and 2.3) has duality representation that only uses the expectation under the nominal transition kernel. Previous
17

---

works, e.g., Yang et al. (2022), have proved such result when the TV distance is defined through f-divergence. Here we extend such result the TV distance defined directly though (2.2) that allows difference support between p and
Remark B.1. Despite all previous works on RMDPs with TV robust sets relying on the definition TV distance Drv (()()))()) with absolute continuity of p with respect to q to obtain the strong duality representation in the form of (2.3), their results can be directly extended to TV distance that allows for different support between p and q thanks to Proposition 2.5.
Value gap between maximum. We note that in the proof of Proposition 2.6, we actually show tighter form of bound of the gap between the maximum and minimum as
1 (1-1 (1-)
p
But in the sequel, we mainly use the form of min H p p) 1/2 = @(min(H, HH, p=")) in the sense that
for its brevity and the fact of (1 (1
c. min { H, pop--1 (1- (1-p) >>>/ S min {H,
for any H 2 Ho E N_ and E [0, 1] with some constant c >> 0 that is independent of (H,
In contrast with crude bound of H, such fine upper bound decreases when is large, which is essential to understanding the statistical limits of doing robust RL in RMDPs with TV robust sets.
B.2.2 Robust RL with Interactive Data Collection
Sample complexity. The metric of sample complexity is connected with the sample complexity used in robust RL with generative models and offline settings (see related works for the references), wherein the sample complexity means the minimum number of generative samples pre-colt colleceee offline data required to achieve e-optimality. In contrast, here the sample complexity is measuring the least number of interactions with the training environment needed to learn n², where generative or offline sample available. Such a learning protocol casts unique challenges on the algorithmic design and theoretical analysis to get the optimal sample complexity.
B.3 Discussions Hardness Result: The Curse of Support Shift (Section 3)
In contrast to the interactive data collection setting we consider, doing robust RL with a generative model or offline dataset with good coverage properties does not face the difficulty we displayed through Example 3.1. turns out that any RMDP with S x A-rectangular tatal-varittion robust set (including Example 3.1) can be solved in sample-efficient manner therein, see Yang et al. (2022); Panaganti and Kalathil (2022); Panaganti et al. (2022); Xu et al. (2023); Blanchet et al. (2023); Shi al. (2023) and Remark B.1. The intuitive reason is that, for the generative model setting, the learner can directly query any state-action pair to estimate the nominal transition kernel P*, and thus no support shift happens. The same reason holds for the offline setup with good-coverage dataset.
There is broader understanding of the curse support shift that hinders the tractability of robust RL via interactive data collection. The concept of support shift could be comprehended within a broader context beyond the disjointness of certain parts of the support sets of the training and testing environments. Instead, ensuring "high probability of disjointness" is enough to maintain the integrity of the hardness result. For instance, we can modify the state $good in Example 3.1 so that it is longer an absorbing state. Rather, $goad could transit to Sbad with small probability, such 2- This modification expands the support of the training environment to encompass the entire state space. Nevertheless, acquiring information about sbad necessitates exponential samples, thereby preserving the hardness result.
B.4
Discussions on A Solvable Case, Efficient Algorithm, and Sharp Analysis (Section 4)
B.4.1 Vanishing Minimal Value Assumption
Another understanding Assumption 4.1. To understand this from another perspective, could be shown that under the conclusions of Proposition 4.2, the robust value function of any
18

---

policy π is equivalent to the robust value function of this policy under another discounted RMDP (S.A, H. Pr, R², D') with Ry (s.a) = (p') (s, a) and & given by
& (P) (a.0)ESxA
(s, a; P).
(B.1)
And therefore we are equivalently considering this new type of RMDPs. Please refer to Section B.4.2 for more discussions on the connections between the two types of RMDPs.
Examples of Assumption 4.1. tion 4.1 hold, which imposes that the state space of the RMDP has "closed" subset of "fail-states" with zero rewards.
the sequel, we provide a concrete condition that makes Assump-
Condition B.2 (Fail-states), There exists subset S C S fail states such that
[s,s, a) =0, 0, () 1, as, E Sj x A x [H].
This type of "fail-states" condition is first proposed by Panaganti et al. (2022) (with |Sy] = 1) to handle the computational issues for robust offline RL under function approximations (out of the scope of our work). In contrast, here we make the vanishing minimal value assumption in order to tackle the support shift or extrapolation issue for the interactive data collection setup. The comparison between the vanishing minimal value assumption (Assumption 4.1) and the "fail-states" condition (Condition B.2) given below.
Remark B.3 (Comparison between Assumption 4.1 and Condition B.2). We first observe that Condition B.2 implies that minses PT
+ (s) = 0 for any policy and step E [H]. therefore satisfying the minimal value assumption (Assumption 4.1). Conversely, the vanishing minimal value assumption in Assumption 4.1 is strictly more general than the fail-state condition in Condition B.2. To illustrate,
consider an RMDP characterized by the state space S {2), action space A = {a1}. time horizon H- = 2, reward functionn (8, a) = 1 = =82), and transition probabilities defined as follows:
(()1(s1,1))=1-- P. (112))11
Pi 82, a1) = (1222222 a1)= 11,
where is the radius of the robust set. It is evident that no fail-state emerges within such an RMDP structure. However, this RMDP satisfies the vanishing minimal value assumption since Vi,ps (s1) 0.
Remark B.4 (Reduction to non-robust MDP without loss of generality). is noteworthy that assuming the vanishing minimal value (Assumption 4.1) 1) or the presence of fail-states (Condition B.2) in the non-robust case (p = 0) is without loss of generality. This achievable by expanding the prior state space S of MDP to include an additional state s,, denoted the fail-state. More importantly, this augmentcation does not alter the optimal value or the optimal value function of the original MDP. Consequently, it becomes sufficient to seek the optimal policy within the augmented MDP, which satisfies the conditions of vanishing minimal value (Assumption 4.1) or the existence of fait-states (Condition B.2). This indicates that algorithm and theoretical analysis in the sequel can be directly reduced to non-robust MDPs without additional assumptions.
B.4.2 Extensions to Robust Set with Bounded Transition Probability Ratio
In this section, we show that our algorithm design (Algorithm 1) can also be applied to S x A- rectangular discounted RMDPs with robust sets given by (B.1) (i.e., bounded ratio between training and testing transition probabilities). We establish that our main theoretical result in Section 4.3 can imply sublinear regret upper bound for this model, which means that this type of RMDPs can also be solved sample-efficiently by clever usage of Algorithm 1. This coincides with our intuition on support shift in Section 4.1.
x A-rectangular discounted RMDPs with robust set (B.1). We first formally define the model we consider. We define morizoo discounted RMDP as fiiie-horizon RMDP M. MM, (S,A, Ht p*, Ry,, Φ'), where the robust set &' is given by (B.1), i.e.
P(s')
1 1]= =
F'(P)
(()) E(S)) A(S): PES (s
sup
$p= (s.a)ESXA
B P*). (B.2)
(x.a)ESxA
19

---

This robust set contains transition probabilities that share the same support as the nominal transition kernel. The reward function R { R ) h= where y (0, 1) is the discount factor and
RA E [0, 1] is the true reward at step h. That is, the robust value function is now the worst case expected discounted total reward.
Algorithm and regret bound. Now we show that we can apply Algorithm 1 to solve robust RL in S A-rectangular discounted RMDPs with robust (B.2) via interactive data collection.
As motivated by the discussions under Proposition 4.2, we define an auxiliary finite-horizon TV- RMDP M as M = (S, A, H, P* R, b) which include an additional "fail-state" sy. More specifi- cally, the state space S = S U {sy}. The transition kernel pa is defined as, for any step h [H], (1s,, a) = PI (11ss,)), a); V(s,a) ES A and ( = =., Va E A. (B.3) The reward function R is defined for any step h E [H), (x a) =
A
(
=0, Va E A. We suppose that the discount factor 7 S p' so that the reward function Rr. E [0, 1]. The robust mapping O is defined as, for any P S x A + A(8).
Rn(s,)), V(s.a) S and
(P))
(()) E A(5) Drv (rr(PP()] sp}
(s.a)E5XA
ap P), p= 2-2-2p!
(xA
Therefore, M is an RMDP with S x A-rectangulla TV robust set of radius p and satisfying As- sumption 4.1 (because satisfies the "fail-state" Condition B.2). Furthermore, for any initial state 81 E E { = S, the interaction with the transition kernel P* is equivalent to the interaction with the transition kernel P* of the original RMDP My, since by the definition (B.3), starting from any s * sy the agent would follow the same dynamics as p What's 's more, for any policy Th S + (AA) for M, it naturally induces the unique policy TS. S + A(A) for the original RMDP M,
Therefore, we can run Algorithm I on the auxiliary RMDP M, starting from the initial state E S {sy]. which only needs the interaction with P*. Suppose the output policy by the algorithm is [T*] 1==1 then the following corollary shows the induced policy ( b K My enjoys a sublinear regret.
Sik= for the original RMDP
Corollary B.5 (Online regret of Algorithm for discounted RMDPs with robust sets (B.2)). Consider an S x A-rectangular y-discounted RMDP with robust set (B.2) satisfying 0 S 7 S p' E (1/2, 1). There exists an algorithm ALG (specified by the above discussion) such that its online regret for this RMDP is bounded by
ACG ACG (K) S (
Regret
where d' = log (SAHK/8) and (-) hides absolute constants and lower order terms in K.
Proof of Corollary B.5. See Appendix F.1 for a detailed proof of Corollary B.5.
Corollary B.5 shows that besides S x A-rectangular RMDPs with TV robust set and vanishing minimal value assumption, the S x A-rectangular discounted RMDP with robust set of bounded transition probability ratio (B.2) can also be solved sample-efficiently by robust RL via interactive data collection. This also echoes our intuition on the support shift issue in Section 1. Furthermore. the regret decays as p' decays in which case the transition probability ratio bound becomes higher, i... the robust set becomes larger.
Remark B.6. The upper bound in Corollary B.5 does not depend on the discount factor "y since Algorithm adopts coarse bound of Rs S 1. The upper bound can be directly improved to be y- d-dependent using a tighter truncation in step (4.2) of Algorithm I.
20

---

B.5 Discussions of Limitations and Future Works
In this work, we show that the absence of any structural assumptions, robust RL through interactive data collection necessarily induces a linear regret lower bound in the worst case due to the curse of support shift. Meanwhile, under the vanishing minimal value assumption, an assumption that is able to effectively rule out the potential support shift issues for RMDPs with TV robust set, propose a sample-effictie robust RL algorithm for those RMDPs, We discuss some potential extensions here and the associated challenges next.
Extension to function approximation setting. The vanishing minimal value assumption also suffices for developing sample-efficient algorithms for A-rectangular TV-robust-set RMDPs with linear even general function approximation (Blanchet al., 2023). Nonetheless, achieving the nearly optimal rate under general function approximation remains elusive.
Extension other types of robust set. Beyond the TV distance based robust we consider, recent literature on robust RI. also investigate other types of o-divergence based robust set including KI. divergence, x2 distance (Yang et al., 2022; Shi and Chi, 2022; Blanchet al., 2023; Xu et al., 2023; Shi et al., 2023). An interesting direction of future work is to investigate is it also possible and, if possible, can we design provably sample-efficient robust RL algorithms with interactive data collection for RMDPPs with those types of robust sets. Notably, the KL divergence based robust set naturally does not suffer from the curse support shifts that gives rise to the hardness for the TV robust set case. However, we find that there are other difficulties for robust RL in KL divergence based RMDPs through interactive data collection. Meanwhile, the optimal sample complexity for robust RL in RMDPs with KL divergence robust set is still clusive even in the offline learning setup (Shi and Chi, 2022). We leave the study of RMDPs with KL divergence robust set for future work.
C Proofs for Properties of RMDPs with TV Robust Sets
C.1 Proof of Proposition 2.5
To simplify the notations, we present the following lemma, which directly implies Proposition 2.5.
Lemma C.1 (Strong duality for TV robust set). The following duality for total variation robust set holds, for f S [0, H..
5 (
}
inf (():rv((Q01Q ())
Eoul/=
sup
-E (11 [1+ -
min #ES
[(s)
+nI.
qE [
where E [0, 1] and the TV distance Drv (rv((()1) is defined as
(Tv(Q()1Q()) 1 Σ Q(s) Q*)
SES
Proof of Lemma C.I. First, we note that when (*) > 0 for any S, i.e. any Q(-) E A(S) is absolute continuous w.r.t. (-), it has been proved by Yang et al. (2022) that
min f(s) (n-
inf an): EgoIf = sup yER
+ +1
Furthermore, as is shown in Lemma H.8 in Blanchet al. (2023), the optimal dual variable 17* lies in [0, H] when / E [o, H). Therefore, for (-) such that (s) >> 0 for any 8 E S, we have
{ Eg - ff+ (
inf (():Drr(Q((1))0()50
Equlfl (0.
sup
min f(() EES
#7
Now for any Q*(-) E A(S), we can prove the same result by averaging Q+(-) with a uniform distribution and taking the limit. More specifically, denote U(-) e A(S) as the uniform distribution
21

---

on S. i... (s) S/|S] for any E S. Consider the following distributionally robust optimization problem, for any E [0, 1].
P(e) =
Q0):Drv (00 Bo
inf
By our previous discussions, since (1 e0 + UU-(()))))))))))))) > for any S and have that
P(() D(c),
Ve E (0. 1]:
(C.1)
where the function D(.): [0, 1] + R is defined as
D(c) sup [0
(1 (11-)) (1- I(n 1nnliinnn- f)+] c. Buy) 1(1 - f)- f)-1- 2.
(1-
min f(s) SES
+ +"5
By the definition of P..) and D(-), our goal is to prove that P(0) = D(0). To this end, it suffices to prove that (i) lim (cc) exists and lim D(c) D(0); and (ii) lim P(c) P(O). To prove (i), consider that for any > 0, by the definition of D(-).
D(0) - D()) <
sup { c Le-Eo-- f)+ + Evos(n n41] 2H.. nE[O,H]
Since the right hand side tends to 0 as tends to O, we know that lim D(E) exists, lim D(e) D(O). This also indicates that lim,-s0+ P(c) exists due to (C.1). This proves (i). Now we prove (ii). Notice that since the set
{Q(-) E A(S) (rv(Q()(((1 +c.(())))))))))))))))))))(()(()) =
is a closed subset of RIST, and [q() is continuous function of Q(-) E IR $ w.r.t. the || ||2-norm, we can denote the optimal solution to the optimization problem involved in P(e) as
2.(+)= =
arginf
Boolff
Q(::Drv ((0000((00000000000eee))
which also gives that
P(c)= = E [ =
SES
With these preparations, we are able to prove (ii). On the one hand, consider for any e E (0, 1],
((1 c) 26(+) + (o-UO]((1-00 - Q²() + U()) s a aa. Therefore, for any E (0, 1]. it holds that
P(c)=
inf Q (000000000000000000)0 So
Bo
< E 1-0) = (1 - c) Bot [f] + e Euolf).
which implies that On the other hand, for any e (0, 1].
lim P(e) s Eoglfl P(O). c+0+
(C.2)
1
Σ
Q)( - (1 (1-c) Q)))) ((s)) C(()
2
SES
2 c) (Iv(Q((011)))) DIVV-
and by using (iv(Q(()[U(() < 1, we obtain that
Div(t(()1)0) o+e T-c
(C.3)
22

---

Consider a sequence of { converging to 0, i.e., lim;-+0 = 0. Since {Q) (0 is sequence contained in compact subset of RR it has converging (w.rt. || Il2) subsequence denoted by (Qt., (-))== whose limit is denoted as Q!) A(S). By (C.3), we know that
0 C+C02 Cip
Drv (1) - 11k
(C.4)
Taking limit on both sides of (C.4) (limit of LHS exists since the TV distance is a continuous function (w.r.t || (|2) of its first entry and the limit of RHS obviously exists), we obtain that
(Tv(Q s
a.
(C.5)
Now we can arrive at the following,
lim P(e) c-00
= lim
E o -00
lim
BO! () = EQr
k-+0+
inf (00)))
Bool// -(())
(C.6)
where the first and the last equality follows from the definition of P()), the second equality follows from the choice of the sequence {ci, l==1 that converges to O, the third equality is due to the continuity of (EQ())]] [S] of Q(-) (w.rt. || 112,, and the inequality follows from (C.5). Finally, with (C.2) and (C.6),
conclude that
lim P(e) P(O), c-0
which proves (ii). Consequently, by (i) and (ii)
P(O) = lim P(c) = lim D(E) = D(0).
c+0
c-0+
Recalling the definitions of P..) and D(-), we conclude the proof of Lemma C.I.
C.2
Proof of Proposition 2.6
Proof of Proposition 2.6. Here we prove stronger result that for any policy π and step h E [M]
max Qh (s (s.a)ESxA
min (s,a)E5xA
Q oi 1
(s, a)
(I
- (C.7)
p
1
(1 (1-(1-p))-htt))
max V &.P. (3) min h.P (s)
(C.8)
First, we note that for the last step h H, (C.7) and (C.8) naturally hold since Rş [0, 1]. Now suppose that (C.8) hold for some step h + 1. By robust Bellman equation (Proposition 2.2), we have that
Th (8, = (s, a) + Ep, Vi
1 Ep (.,a;)))))
(s,4)ESxAA
(C.9)
where the inequality uses the fact that Rs < 1. Now we denote the state with the least robust value as
so argmin V V..1.P.,4 (s).
(C.10)
sES
Inspired by Shi et al. (2023), we choose transition kernel PA satisfying that
Pr a) p. (s'ls,, (a(ssss 20, ((s.x)))SAAXS
which implies that
DTV (Pa(-18, + + (00 Pr((lsa)) Sp. v(s.a)E8xA.
23

---

Here (-) is the point measure centered at so defined in (C.10). Combined with (C.9), we have that
(s, a) 1 + E Pa P (10,))+
V +
=1 + (x Phit,, P. #)
pp- 1
+ p)
max Vh+i. (s) p. min V ( (C.11) seS
SES
Consequently from (C.11), we further obtain that for any (8, E S A.
(s, min (xx
Th (s,a)
2 1 (1 p)
max V P- p.) p. p.min V #ES
1, (8)
min
#ES
(ma))SXA
= 1 + (1 p)
max V 1+ P. * (8)
min V
sES
+ min V 1+ #ES
min (e,0)ESxA
+1+ -m p)
max
V 1 * (s)
min
V
(C.12)
sES
sES
where the first inequality uses (C.11) and the last inequality uses the following fact,
min (s.a)ESxA
Qh ((,
min
(8, + Epp(a.::;;) Viit.
(x.a)ESxA
min V , (s).
Now applying the assumption that (C.8) holds at step h 1 to the right hand side of (C.12), we obtain that
S 1-p p (1 (1-) p)
( - min (s.a)E8XA
(s,
max (s.a)ESXA
1 (1 (1- p)
Thus given (C.8) at step h + 1, we can derive (C.7) at step h. Now by noticing that
min T * ()) < min V. (8) S max (s,a)E8xA
sE$ V. (8) S
max (a.))SxA
Qh
sES
can conclude that (C.8) also holds step h. As result, by an induction argument, we finish the proof of Proposition 2.6.
C.3 Proof of Proposition 4.2
Proof of Proposition 4.2. We consider some fixed (s, h) E A x [M] throughout proof. By Lemma C.I, we have that
E (p((aa: [V] = sup nER
E ( (n v))
P.
H--min
min eES
+n
Epg()aa) (17-))+)) p [)
min V(s) sES
sup
2
- ((r V)+] + (1 2 7
sup nE[o.H
(C.13)
where the second equality follows from the fact the optimal dual variable 1)* is in [0, H when V E (0, H] (see e.g., Lemma H.8 Blanchet et (2023)), and the last equality obtained by the fact that min.es V(s) = O.
24

---

Part (i). For any E [0, and Q E Bp (s, a; Ph), we have that
((7 (1.0) [(1- v)+ -1-2) n
2) (- (-n V)+] nn)
$ (1 2) ( (-E v] +
(1 2) EEq)) [V]
(C.14)
where the first inequality uses the definition of B a; Pt the second equality follows from the fact that (xr) 2 z. Furthermore, by (C.14) we have that
sup [E(o.H] -Epp((ssa) (17 V)+] + (1 (1-2) ( 7
$ (1-
inf QeB,r(s,
Boo (Vic.15)
Combining (C.13) and (C.15), we have that
E (p.(.. [V] S ol (s.....)))))
Part (ii). Since p E [0, 1]. we know that there exists a 77 E [0, H] such that
Σ
P ク Σ
(s)),,))),
(
(
which further implies that we have the following interpolation for some X E [0, 1]:
1 1 L = E +1(s)ss,)+((11)
() (aV((
Σ
2
<'V(')<
We define probability measure Pa E (S) as
P XPA(5's, 1(V(8)) 7i + (1- () 1(V(8) 2 2
(C.16)
It is not difficult to verify that P E Bp a; P.)). Hence, we have
(1 - () Eg (s,a:;)
[V] (1
2 EEROO
P)
P) 2 EFpe) [V - -7] 2) "
- [(7 v)+] + (1 0
2) -7-
(C.17)
where the last inequality uses the definition of F7 (C.16). Furthermore, by (C.17) we have that
p' (s.:::))
sup
{
(p ( v)+] + (1 L
2 -n 3
(C.18)
nE(o,
Epp [V]
where the equality follows from (C..3).
Combining Part (i) and Part (ii). Finally, combining (C.15) and (C.18), we prove Proposition 4.2.
D Proofs for Hardness Results
D.1 Proof of Theorem 3.2
Proof Theorem 3.2. We first explicitly give the expressions the robust value functions in Exam- ple 3.1, based which derive the desired online regret lower bound.
25

---

Robust value function. Firstly, we can explicitly write down the expression of the robust value functions for any policy under Example 3.1, i.e. V h.p and Q Pr.Mo + From now on we fix a policy и.
For step h 3, the robust value function is the reward received. We can directly obtain for any E A,
Pm.MM + (Sgnod: a)
V Mo, & (Sgoad) 1,
(D.1)
Q3 M. + (8badd, a) = V3, M. & (Sbar) = O.
For step h = 2, by the robust Bellman equation (Proposition 2.2), we have that for the good state $ 'good
pr.po. a (8good, a) -1+
(D.2)
inf PEPplsgooa a.P
E p()) [V M. #t 1 (1 p): E
where the last equality is because V* 3M,,, takes the minimal value 0 at the bad state Sbad and thus the most adversarial transition distribution is achieved at
(t(') (1 p) 1(s' ggood + p 1 sbad]. Similarly, we have that for the bad state Shad+
22 Pr. t (Sbad, (1)
inf PEP, (ohadd MPP2
PP (v.
(D.3)
p P.
a=
Finally by the robust Bellman equation again, we have that
Mo & (8good) = 1 +1 p),
V 2. (Sbad) 72 (2(0)bbad) (p p) + 72 0|sbad) (q p).
Notice that by q < we know that 1 Mo, (Sbad) < < (1 p) < V
M. 4 (Sgood).
For step h = 1, we consider the robust values on the initial state Sgood, by robust Bellman equation,
Po (ggoods a) + inf
Ep(-) V Mo
(D.4)
PEP (Agond oz p.pp"" Pr.M
1 (1 - p) [1+ +1 (1-
+ [m2(0[sbal) (0(b)))) (p - p) + TT(1 - 0 0|sbad) ) (g - ()-p)], Va E A. ( (Sgood, a) for Va E A. By robust Bellman equation, we also derive V V.T,pr,,, x (Sgood) = Q", i.. x
Lower bound the online regret under Example 3.1. With all the previous preparation, we can lower bound the online regret for robust RL with interactive data collection in Example 3.1. But first, we present the following general lemma.
Lemma D.1 (Performance difference lemma for robust value function). For any RMDP satisfying Assumption 2.1 and any policy æ, the following inequality holds,
VTPp. (s) VT.p..,(88
H
2 E(pe" ()))
ΣΣ Lh=laEA
(als)) - (alss))) Th. (sh, =
where the expectation is taken with respect to the trajectories induced by policy n², transition kernel pr'sf Here the transition kernel p= it is defined
(-1s,))))))= PEP(s.a;Pt)
arginf
Ep() [Viti.r-.o)
where P(s,ar az Ph)) is the robust set set state-action pair (s, a) (see Assumption 2.1).
26

---

Proof of Lemma D.1. Please refer to Appendix D.2 for detailed proof of Lemma D.1.
Now back to Example 3.1, our previous calculation actually shows that, by (D.1) for step = 3,
Σ 3 (o (als3) na(alss)) Q7 P.,M, a (83, Vas { Sbad
(D.5)
and by (D.4) we also have that for step h
(m (alsi)) Ti (81, a) = 0, where
8good
(D.6)
REA
Finally, let's consider step h = 2. By (D.2), have that for the good state, it holds that
Σ
2
Me (al (glogood) T2 T2(aa (ggod)) Q2 pr, ($good: a) = O,
(D.7)
dEA
Meanwhile, by (D.3), we have that for the bad state, it holds that (recall that y p)
Σ
Me (al sbad) - Tz(al (a(aabbad) Q2, a (Sbad, a)
REA
{p- P.q p} - (T2 Sbad)) (p - p) + x2(1 - O B|sbaad) (4 p))
max
p- (02 (p p) + TT - 01sbaaa (g p)) 2 (1 (1n2: (17g.Mo(0|ssbal)) (0lsbaa) T2(0 (baa)
p- Q
mT2"" Mo 0 0/sbad) TT221 0 (/sbad)
(p- Dry (mD-MM (+|sbaa) T2 (15(a1)))))
(D.8)
where according to (D.3) the optimal policy of Mg at h 2 and Sbad is TT2
Me ( (0]sbad) 1. Now
combining (D.5), (D.6), (D.7), and (D.8) with Lemma D.1, 1, we can conclude that
yxt yo Mo (Sgooa) V Mo (Sgood)
E Ma (=18godd) M. (-1ggodd:a))
Σ (TT(al52) - TT(aas²)) 22 (82,
a2 N
LEEA
- Mu, (t (shad 18 (gond 0) (p- 9) DTV to
T2 (1188ban))
(D.9)
where the adversarial transition kernel p. it is given by
pr TMo.t (-1 (9|8good; 0)
PEP PEPosgood MMa Ep(.) V 2.p
argmin
=(1 p) 1( = Sgood] } + p. 1f. = =sbad)
(D.10)
Consequently, taking (D.10) back into (D.9), we have that
Vi.po.a o (Sgood) V Vip.,. (Sgood) 2 p (p q) Drv Mo
(-|sbad) T2 (2((11bad))
This implies that for any algorithm executing -. T.,... o its online regret is lower bounded by the following.
K
Regret Mc.AC9
(K)
Σ
pa Mi
Mo z (8pood) Vx* Vi.po.mo Mo, (8good)
k=1
K
2 p. (p - q)
Div (m (-1obaa) 1T km
(1loaa(-lobaa))11tt (118baa))
27

---

However, since in RMDPs of Example 3.1, the online interaction process is always kept in sgood and there no information on 9 which can only be accessed at (s, h)) (Shad 2). As a result, the M.Mo (-1sbac) = 1{- = d can do no better than a random guess. Put
estimates ( (badd) of 22
formally, consider that
sup EM Regret MoLACS (K) 0Ef0,1}
K
2 p (p (p-))
sup 8E(U,1}
M.
Σ Drv (m (-1Sbad) x (-1 (1((bba)))
p. (p
sup (E k=1
E EACO
[ 0 [|sbad]]
(D.11)
Here in the last equality can drop the subscription of Mo because the algorithm outputs m independent of the 9 due to our previous discussion. Notice that
K
Σ
Σ
ACG [
(1 - 0 (Bbaa))
=
Σ
Eacs [T](1 0 0/shad)) }]
Σ
= K,
(E
k= OE (0.1)
k=1
which further indicates that
K E Aco [T - 0 0|sbad))
K 2
sup (0
)]
2
(D.12)
k=1
Therefore, by combining (D.11) and (D.12), we conclude that
[Regret Meegret-M..Ace Mc.ACS (K)) (o 2 (p 9) pK
inf sup EMa.ACo ACG 0E70,1}
+
2
This is the desired online regret lower bound of s2(p K) for the RMDPs presented in Example 3.1. Furthermore, we can construct two RMDPs {Mo, MiI with horizon 3/1 by concatenating H
RMDPs (Ma,Mi) presented in Example 3.1. Notably, at any steps {3i + 1 we define
R3141 (Sbad, a) 1,
Pr.Ma (Sgood Sbad, a) 1, V(a, A x 10. 3i+1
Then we have
inf sup E Mo.ACG Regret 2 Mc. (k))))((K)) 2 H S(pp K) = A(p HK), ALG (0.1)
which completes the proof of Theorem 3.2.
D.2 Proof of Lemma D.1
Proof of Lemma D.I. For any step h [H]. have that by robust Bellman equation (Proposi-
tion 2.2),
TT & (s Qh, a (s, a) = (p,(e, [VeL... #1 (e,(e.a:p)) VItLP.* *)
By the definition of the transition kernel pm in Lemma D.1 and the property of infimum, we have that
- QT (s, 2 E pg + ((I,,)) [V [.t s] - E Eg (Hs.a)
[V 1, Pr,
EEp pr + ((s.a) [VT 1141, Pt, =).
(D.13)
By robust Bellman equation (Proposition 2.2) and (D.13), we further obtain that V..P- a (8) - V.J.P. * (b) 1xg 17 a (8, )] - Eus( s) (h. (-1)(10)) [0 4 (8, - Ems( a) 10 p., (8, + E Bx2(11) (T - Bx 1 pr, (8.
Σ (a)(s))) - (als)) (0,
aEA
+ E
VT V..P.. V...P....
(D.14)
28

---

Thus by recursively applying (D.14) over h E [H], we can conclude that
VT. (s) Vi,p* (s)
H
Bep ,,,"* .r))
ΣΣ
(mi(als))- - (alas))) ( =
aEA
which completes the proof of Lemma D.1.
E Proofs for Theoretical Analysis of OPROVI-TV
In this section, prove main theoretical results (Theorem 4.3). In Appendix E.1, outline the proof of the theorem. In Appendix E.2, we list all the key lemmas used the proof the theorem. We defer the proof of all the lemmas subsequent sections (Appendices E.3 to E.8).
Before presenting all the proofs, we define the typical event & as
{
EEp (Epr(lem)) (pp2(10.))) [11 Vitta,r,, [
=
V p (n Vi (
c16
C2Hi Hi (H
C2
a) V1
min PH(5'(s,
( (H(s)ss ci
P) - Pn( $
C21
(1)
(s
a(s,a, k, (ss,,,s,h,kk) S AxXx [ [K], Vn E T (1)(SVR) H!)
where A11 K3/2 /0), c1, 02 are two absolute constants, N N1ssv/ (10, HJ) denotes an KK-over of the interval (0, H).
Lemma E.1 (Typical event). For the typical event & defined in (E.35), it holds that P(g) 2 5.
Proof of Lemma E.I. This a direct application of Bernstein inequality and its empirical version (Maurer and Pontil, 2009), together with a union bound over (s, a, s h,, k, n) S x A S [H] x
[K] Mi ((0, H]). Note that the size of N1 ([0, H]) is of order SHVK.
In this section, we always let the event hold, which by Lemma E. of probability at least 8.
E.1 Proof of Theorem 4.3
Proof of Theorem 4.3. With Lemma E.2 (optimism and pessimism), we upper bound the regret as
K
K V)(()) -v((s).
Regret & (K) =
Σ Vi.r. Vi. (s1) - o <
(E.1)
k=1
km
In the sequel, we break our proof into three steps.
Step 1: upper bounding (E.1). According the choice of Qh Qt V V in (4.2), (4.3), and
(4.4), let's consider that for any (h, k)) E [H] [K] and (s, E ESXA. x A.
(x, (s,
= minn (n, + Ep (x.ax. V4
+ bonus a), min (H,p-1)
29

---

V h+1
(s. a), 0f
max
(s, a) + P. ())
polnniiit)
[/ h+1
Rsp (n Pt)
V
+ 2 bonus (s, a)
-Ep -Bpp(sa:Pp))
V
A+1
-Ep,e,,:PP))
V h+1
+ Bpp(o,a:PP))
V h+1
Ep Bpp(s.a:pp) pp)
La+1
Term (i)
+ Epp(sa:PP)
V h+1
Epplaa:Pt)
++1
+ bonus),
(E.2)
Term (ii)
Step 1.1: upper bounding Term (i). By using Bernstein-style concentration argument customized for TV robust expectations (Lemma E.3), we can bound Term (i) by the bonus function, i.e.,
Term (i) S 2 bonus (8, a).
(F.3)
Step 1.2: upper bounding Term (ii). By our definition of the operator (p,, in (4.1), have
Term (ii)
sup (0
E (rg(-sa
(
+1-2))
() m
sup De (0 Epg(less) (11 kbttt) (1-K
+ (1 2 m
Eppcleea) (1- khttt) - (1- vntta }
sup (6(0.
(E.4)
By Lemma E.2 which shows that V any y x, we can further upper bound the right hand side of (E.4) by
h+1 2 V h+1 and the fact that (17 - x)+ - (17 - y)+ S - x for
Term (ii) (1g()))) Vh+t
kh+1l
(E.5)
Step 1.3: combining the upper bounds. Now combining (F.3) and (F.5) with (F.2), we have that
(h(s, a) - (s,a) a) S Egg(lsa)) V Th+1 - [ht1 + 4 (s a).
By Lemma E.4, we can upper bound the bonus function, and after rearranging terms we further obtain that
(s,aa) Q
1+
12
(p:(()aa)
Vh h+1
Vh
W ((()
V V
4c (s,
4
+ 4
+ VK"
(E.6)
N (s,
where c1, > 0 are two absolute constants. For the sake of brevity, we introduce the following notations differences, for any (h k) E H [K].
A (s (st))
ci A (5t - 24 (sht
(E.7)
ς = (- V Lt} - A
(E.8)
we further define the filtration {F as
of U(iit),
Fr.
30

---

then we can find that (aLA))())) is martingale difference sequence with respect to and (sh (a is martingale difference sequence with respect to (Fn U (0.0)))111 Also, we further have that
A ch
(hhoshaat (5 att))
(E.9)
S ch
12 H
V
h+1
Kht1
4
+ 1
(5 aa))
V1
(5 ok) V1
VK
12
12
ch
+
ch +
11
A 1
H
V (-1,,)
Vaa V
4c St
4
(s
a
V1
( a V1
VK'
where the inequality applies (E.6). Recursively applying (E.9) and using the fact that (1 + 11 < (1+ 12 S e for some absolute constant e O, we can upper bound the right hand side (E. as
K
K
H
Regret & (K)
2 A
(Sh
)h
k=1
k=1
Vxt Vrg(lsa)) 1=.10",000
H (H a V
(E.10)
(N a V1
VK
where C 0 absolute constant.
Step 2: controlling the summation variance terms. In view of (E. suffices upper bound its right hand side. The key difficulty is the analysis of the summation of the variance terms, which we focus on now. By Sauchy-Schwarte inequality,
V PgCCsshaat)
Vaa K+I.P- +
ΣΣ
(5 v1
k=1
K H
V Pgel
Vitk h+LPP'
ΣΣ Σ
1
(E.11)
k= h=1 ( vI
k=
k=1
On the right hand side of (E. 1),, the summation of the inverse of the count function is well bounded term (Lemma E.13). So the key is to upper bound the the summation of the variance of the robust value functions to obtain sharp bound. To this end, invoke Lemma E.5 to obtain that with probability at least 1 8,
ΣD
V p (1)
min p HK + min (11,-'}* "..)).
C2
(E.12)
where C2 > 0 is an absolute constant. With inequality (E.12) and Lemma E.13 that
K
vi S C. HSA.
with C²2 being another constant, we can upper bound the summation the variance terms (E.11)
h
(s a V
1=
31

---

I mosymin (H.p- H'SAKt
min {H, p-1 H2SA
(E.13)
where C3 > 0 is also an absolute constant.
Step 3: finishing the proof. With (E.10) and (E.13), it suffices to control the remaining terms. For the summation of the martingale difference terms, notice that by the definitions in (E.7) and (E.8), both < and ς are bounded by min H, p pー according to (4.2) and Lemma E.2 (optimism and pessimism). As result, using Azuma-Hoeffdin inequality, with probability at least 1 - 8
K
Σ
(ch
+ S C1 min (H .VHK,
1= A=1
where C4 is an absolute constant. For the summation of the inverse of the count function in (E.10), it suffices to invoke again Lemma E.13. Combining all together, with probability at least -6, have
W/min{H, HASAK? + min (H, H
Regret * (K) (K)SCs Cs
min {H, (H, VHKI+ S² HVK
(v { -H
where C3 > 0 is an absolute constant and d' = (SAHK/0) This completes the proof of Theorem 4.3.
E.2 Key Lemmas
Lemma E.2 (Optimistic and pessimistic estimation of the robust values). By setting the bonus as in (4.5), then under the typical event E, holds that
(=,(s) S Th.r,, S Qr (s, s (s,,,,,, (s) h.P (s) Vi (s) S (x(),
(E.14)
for any (s, a, k, E Ax H [K].
Proof of Lemma F.2. See Appendix E.3 for a detailed proof.
Lemma E.3 (Proper bonus for TV robust sets and optimistic and pessimistic value estimators). By setting the bonus h. as in (4.5), then under the typical event E, it holds that
E (x.a;
V
A+1
Ep,(s.):;))
V h+1 + Ep Eppla.ss
Vb [ht]]
E
V
h+1
2- bonus (s,
Proof of Lemma E.3. See Appendix E.4 for a detailed proof.
Lemma E.4 (Control of the bonus term). Under the typical event E, the bonus in (4.5) bounded
by
bonus x (s.a)
W Vgg(ls,))
Va Cil
1+
4. 4.Erg
V
Vh+t1 htl
22 H2
1
S
+ (1
No (s,
H
VK'
where Io and Cı, 02 > are absolute constants.
Proof of Lemma E.4. See Appendix E.5 for detailed proof.
32

---

Lemma E.5 (Total variance law for robust MDP with TV robust sets), With probability at least 1 - 8, the following inequality holds
K
H
V (g
[min(H,p HK + min p Hi)
Rim Pumi
where
1og(S$AA122 AHH2 and > 0 is an absolute constant.
Proof of Lemma E.S. See Appendix E.6 for detailed proof.
E.3 Proof of Lemma E.2
Proof of Lemma E.2. We prove Lemma E.2 by induction. Suppose the conclusion (E.14) holds step h + 1. For step h, let's first consider the robust Q function part. Specifically, by using the robust Bellman optimal equation (Proposition 2.3) and (4.2), have that
Ch (s, ()())a)
< max Ep Eppltaa:p)) Vitti.- [0] (e,,(e, [h+ta] - (s,
Qh. mmin {H, --
E (p,l,, Vittape o) - (s, a), 0f (E.15)
< max Ep, Epplsarrp)) Vittare ]
where the second inequality follows from the induction of V P* S V h+1 at step h and the fact that Qi.p.. S min(HHp (by Proposition 2.6 and Assumption 4.1). By Lemma E.7, we have that
Viti,
-E
V
V (iclla)) Vitios
cil
C2Hi
+
No (s) V1
(s,
VK
Now by further applying Lemma E.1l the variance the above inequality, we can obtain that (pp(e..:P))
Viti.P-.0)
VittI,=
V/ (Ppllaa))
(Ti+i + vh+t1 /2
+ +4H E (1
V V
vh+t1 ))
ci
(s)
H2
(1
VK
(Tht + vh+t) /2 .1
Fst h+1 V
V Pp(llaa)
E Eptclsaa)
4Ho
+
(1
(s) V1 V1
H
(1 VK
V V (Thni + Vh+1 /2 ai
V V h+1
E Bp(()a))
<\
(1
H
CHH,,
(E.
(H VK'
33

---

where the first inequality is due to Lemma E. I, the second inequality is due to va+ S va+ and the last inequality is from vab Σ a + b where c₁ > O is an absolute constant. Therefore, combining (E. 15) and (E. and the choice of bonus (s, a) in (4.5), we can conclude that
Qh a) S (s)sa))
Furthermore, it holds that Qh, + (8, a) &h (s, a). Thus it reduces prove Q7 s Qh, 4 (s, a). Again, by using the robust Bellman equation (Proposition 2.2) and (4.3), have that 2x (s, a) (s.,a)
max
R. P.p
Vk Lht1|
VitL. (sn
v P+
Vi+t VitL.
(s, 0 (
max
where the second inequality follows from the induction of V fact that &h 2 O. By Lemma E.8, we have that
h+1 I P4 at step + and the
Vaa P
E (s,aa::
Epplaaa::))
V h+1
V (P((la))) VIt1P.
ci
E Bpgelsa)
cH (s.
H
V1
VK
Now by applying Lemma E.1l to the variance term, with argument similar to (E.16), we can obtain that
Virt
E Epploaa: PR)
Ex Eppaspasp))
(E.18)
Vi+1
/2 ct
2E (-1,a)
V h+1
V
h+1
(s, V1
H
dH
(s.
VK
Thus by combining (E.17) and (E.18), and the choice of bonus a) in (4.5), we can conclude that
0º (s, a) Q Ph. (s,
Therefore, we have proved that at step h, it holds that
(s)s UZ s (s. a) S Qi (s, (s.
Finally for the robust V function part, consider that by robust Bellman equation (Proposition 2.2) and (4.4),
(s)) = ( 2* < (1 To (8, )) = Vi
and that by robust Bellman optimal equation (Proposition 2.3), the choice of t², and (4.4),
Vi. a (8) max Qh. (s, S max (*, V
aEA
which proves that
(i((s) < Vis ( ( (*.
Since the conclusion (F. holds for the V function part step H 1, an induction proves Lemma E.2.
34

---

E,4 Proof of Lemma E.3
Proof of Lemma E.3. We upper bound the differences by a concentration inequality Lemma E.9,
E pp(s,,;
Vh h+1
(p
V +B pa PR)
V ki+1
Pp, (m,arT)
(t((aaa VitLe +
2 2-Ppg(-ls.a)
V V
h+1
1 21
+
(s)
H
St
2
(B.19)
(5,
VK
where c1 0 are absolute constants. Then applying Lemma E,11 the variance term in (E.19), with an argument the same as (E.16) in the proof Lemma E.2, we can obtain that
p (p.aa:PP))
V h+1
V h+1
L [h+ta
Ep, (m,:f()
Mutz
Vhtt h+1 + Ki+t
/2
-o 4. 4.Rpp(1sa) (1s,a)
Vh+1
Vh. L+
< 2
+
a1) +
H
2c/112
2
(x
VK
Therefore, by looking into the choice bonus a) in (4.5), we can conclude that
E (e,a: V V++1| Ep (pp(na:pp)) V + E. (e,a; V/ [h+tl
Ep, (n.a:%)
Vi+t
2 bonus (8, a),
This finishes the proof of Lemma E.3.
E.5 Proof of Lemma E.4
Proof of Lemma E.4. Recall that the bonus (s, a) is defined as
V V
141 + vh+t1
12 c1t
()) V1
2E ph (-1a.)
V Vhti
C₂ H
1
+
H
(s.
VK
The main thing we need to consider control the first term and the second term. We first deal with the second term of (s, a) by invoking Lemma E.10, which gives
2 (-(,a)))
V Vh+t
Vh+1
2
2
Vh vdn]]
CHH
<
+
11
I1
112
31E (-18,a)
V
h+t
Vk
CgHSe
(F.20)
H
(x(
35

---

where the second inequality is from H 2 2. Then we deal with the first tern (variance term) of (s, a) by invoking Lemma E.12, which gives
V Pp (V
V /2 c1c
(B.21)
a) V1
V (pp((sa))
V 1+1.p=,
Venk
+ +4H Epg (1s.0)
V V
V h+1
+ (o.ojvl + +1) cie
No (s,a)
Vork PP:()aa) 14I.P*,*
4H Epg((
V Vh+1 - V h+1
-11
V1
N (8,
VadSH'
C1
V1
yark
de
Erg()),)
V
Vitt
(4c + veyes H2
(1
(s)
Thus by combining (E.20) and (E.21) with the choice of bonus we can conclude the proof of
Lemma E.4.
E.6 Proof of Lemma E.5
Proof of Lemma E.S. The key idea is to relate the visitation distribution (w.r.t. P*) and the variance (w.rt. P*) to the value function of x² after which we can derive upper bound for the total variance. Throughout this proof, we use the shorthand that
- - min { }).
According to Proposition 2.6 and Assumption 4.1, for any policy æ and any step h, the robust value function of holds that
max sES
h. o (s) S H,
(E.22)
which we usually apply in the sequel. Also, to facilitate our analysis, we define
Th a-)
argmin
Ep(-) [
[H]
(():P(
and set 7h (Th 1 Th=1. which is the most adversarial transition for the true robust value function of
Now consider the following decomposition of target,
V
a2)
H
H
Pp pp
Vi ]
- (P
V (2 V
Σ v ( Vitta
Log MP mb)
H
V (rg(1 V V
Pg (
Term (i): martingale difference term
36

---

H Vatu.rr
Coft MiTh mn))
Term (ii): total variance law
H
H V
[ (
(ot M
V P
a
(ot aat (f (
Term (iii): error from P to T
In the sequel, upper bound each of the three terms respectively.
Term (i): martingale difference term. This is summation of martingale difference term (with respect to filtration Gs o(((%) ())tm))) By namma-Hoeffding" inequality, with probability at least 1 6,
Term (i) S c. H VK,
(B.23)
where c an absolute constant. We have utilized the fact of (E.22) to obtain the upper bound HH on each martingale difference term in the summation.
Term (ii): total variance law. The upper bound of this the core part of the analysis, for which we summarize it in the following lemma.
Lemma E.6 (Total variance law). Under the same setup as Theorem 4.3, given any deterministic policy n, define that
(n(-
argmii (()P)(sa::))
Ep()
V V
ES Ax [H],
(E.24)
and set T {T N Then we have
H
E
Σ
V aa
Vi *
<NH H.
We defer the proof of Lemma E.6 to Appendix E.7. With Lemma E.6, we consider taking policy x for [K] therein (which are deterministic policies), and obtain that the Term (ii) upper bounded by
Term (ii) < 2H K.
(E.25)
Term (iii): error from P to 7*k We first relate the visitation distribution under P to that under Tik On the one hand, by the choice of the adversarial transition kemnel Ti, it holds that
Drv P (-)())s, (-ss.a) ai) < V(s,, E S A [M].
(E.26)
On the other hand, by (E.22), we can upper bound the variance term by
H² V(s,a, Ex
V Pp;(-sa0
(E.27)
Therefore, by combining (E.26) and (E.27), we can conclude that
V P- (-
V
I E (B att
Σ
V P::litaaat)
Virt p
37

---

Drv (Ph(-1s,,) ((((sssa)) T/ s,a))
+ H
sup (saa))SSxxx(1)
V (1 (sx.
sup
V (
E (et DTt s
Vir Pr Σ (l
+ tpH .H.
(E.28)
We then relate the variance term under P to that under T Specifically, we have (vitL.pr, x) ]] (Epg(le ( ))
V
pr (1e.,)
(-
(vxt 11t,,,000 )}= (
V Vitt(6s) 2
+
sup (s,0)SSAA
DTv (1)()s a)
Tht (-1s,)))
max V h+ 1, (0 (0())
$'E8
SV 12 Vi+
+ 2p H
(s,a,h) ES x A [H] (F.29)
where the last inequality follows from the definition of T and (E.22). Combining (E.28) and (E.29), can upper bound Term (iii) by the following.
K
Term (iii)
Σ
B (P)
V PR (R
(aa (ati,
(E.30)
E (shaa)))aTT
V (p:cish
Viti..
E (ohiatt (T (**)
Vaa V Vrgeisaaa
E (s (lokaak)((f (T* stt)
V ( V
S 3pH / < 3H H. K,
where in the last inequality we use the fact that for any E [0, 1]. it holds that
pH p min p min {pH, 1.
Finishing the proof. Finally, combining the upper bounds for Terms (i), (ii), and (iii), i.e. (E.23), (E.25), and (E.30), we conclude that with probability least 1 5, it holds that
K
#1
V Wptelsk
Vi o sc. H H V 2H K-HH-
k=14=1
< H H. K c d' H H
where in the last inequality we use vab < + for any a, > O. Plug in the notation that H min(H, H 1) and finish the proof of Lemma E.5.
E.7 Proof of Lemma E.6
Proof of Lemma E.6. Using the property of variance, we have that for any (Sh, ax) E S x A.
V (1(oaan))))
V V 1..1,P'..
=Bis(lennan) [(Vit1,0,,))) - - [ pntr,.m,o)""
(E.31)
38

---

By robust Bellman equation (Proposition 2.2) and the definition of Th in (E.24), we have that VA, (8h) = (Sh. Th + (ala
V V
(E.32)
Therefore, by (E.31) and (E.32), have that
V (.llsmmmass))) v
(s (v ) p00--VV (Vi.er,, Ra(sk. ((s))) (E.33)
For the second term in (E.33), we can calculate it as
(V (86) Ru Rn(sn; Th (sn))
= PV ))² ($)) + 2 V & ($h) Rn (h(s)) - (s,, (n())) S -VV,,p--,>) (sn) + 2H,
(E.34)
where the last inequality utilizes the facts that 0 S (sh, Th (sh)) I 1, R2 (sh, (n(s))) 2 0, and (F.22) that Vi
(8%) S H. Combining (F.33) and (F.34), we have that
Th (r Vi S (eTatlen which further implies that
(V (V (8%) 2H,
(II
V
E (T,))
V (in
(Viti,,-> ) - (Vi,,r,,)²* " 2H
S E (T)
E Bra(lon-zaaaN)
E
(f (VitL,
E (T)) (Vi,p-,)) + +2H.
Taking summation over [H]] gives that
H
E (f,,,a))=(((
SHH 2H min H, p-1}
which concludes the proof of Lemma E.6.
E.8 Other Technical Lemmas
Before presenting all lemmas, we recall that the typical event & is defined as
{
E (Epg(lam)) Epg(lam)) [n Vi+ +))
3
V (p (n Vitt.,
o2Hi
V
a) V1
(s,
min (P (s cre (1)
() - Pa( $
O21
(H
Vs,,0,8 E Ax H x [K], Vn E (10,
(10 HJ)
(E.35)
where log AH 5), C₁, 02 are two absolute constants, (10, H) denotes 1/8 of the interval [0, H). where c1, C2 are two absolute constants, .N. (N) H])
denotes K-SSvr of the interval [0, H).
39

---

E.8.1
Concentration Inequalities
Lemma E.7 (Bersttei bound for TV robust sets and the optimal robust value function). Under event (E.35), it holds that
B Ppllsa: Viti, o)
Epplanast))
V Vi
V Picloaa) Viti,
11
caHle
1
(s.
(1
VK
where log(5 2H K3/2 /6).
Proof of Lemma E.7. By our definition of the operator E that
Poo Mit,, ,0 in (4.1), we can arrive
E Epplaaa:P))
V - Epplona:P)) Vi+ Vitt.
-
E -BPppclaa)) (1) V x)+ + 1+11-11 -1-))=-
sup [E(U.H]
2 .n]
- Epx((100)) (17 Vi ) + (1-2) -7)
sup vE(0.H]
{ (EPE(lle)) - (l [ Vhi-Vi
sup n m)
(E.36)
Now according to the first inequality of event E, we have that
(Epgt s.0) - -Epe((sa)) [(1 P
(n Vi+I.P=,
o2Hi
( V1
(1,
(i(() Vi Vitt.P
H2
(s,
(=
for any E Mr MI((RR) (10, H)). Here the second inequality is because Var[(a-Xi S Var[X]. Therefore, by covering argument, for any [0, H]. holds that
(Epr(lea) Epg(1oa))
[m
P=+ ()) x)
V Pi(llaa)
Vi+L.p-
+ 1 (y
C2H
(s, V1
VK
This finishes the proof Lemma E.7.
Lemma E.8 (Bernstein bound for TV robust sets and the robust value function of m²). Under event (E.35), suppose that the optimism and pessimism (E. 14) holds at (h + 1, k), then it holds that
E
(
Epp(s.::;))
Vit1.P (+(l)))))
Ve
E Eppcisa)
h+1
Vk
h+1
CHH
V1
H
(x V1
VK"
where 1 lo AH 3/22/3//00 /8) and c₁. og are absolute constants.
40

---

Proof of Lemma E.8. By our definition of the operator Pp, (so in (4.1), we can arrive that,
B (o
V VITLP.,,0 #0
Eppls,a:P:))
Vi 1
V (pte(sn)) (11
1 + (1--)) n}
sup (e((,.1]
Epg(lana) (1 Va 1+ x)) m) + +(11111 -1- ()) m)
sup (E(U.H]
E P(()lba) - Epp((1.)) (11 Vis Ptt.,,
sup
n
(Epp((an)) (pg()sa)) (11 Vi x)
sup
ne
Term (i)
E (Pgglle)) - (pg((a [1 V.+1Pp., - -(1 - ++,1.+
+ sup (E(U,H]
Term (ii)
We deal with Term (i) and Term (ii) respectively. For Term (i), this is exactly the same as the right hand side of (E.36). Therefore, applying the same argument Lemma E.7 gives the following upper bound,
Vi+1.
He as
1
Term (i) S
+
(E.37)
(s,
v1
VK
For Term (ii), first apply the second inequality of event & to obtain that, Term (ii)
(E.38)
(s at
Σ
C2
sup n
(s, + (1
(7 Viti.r (asr..as))) (5') +- (n- Vi
By the assumption that (E.14) holds at (h + 1, k)), we can upper bound the absolute value above by
(n - vith.r Viti..r. (5)) (n Vi (s))) S Vi-re- V (s') VittiP=,, (5')
< V442('') (s)).
(E.39)
where the first inequality is due to the 1-Lipschitz continuity of (x) = (n x)+ and the second inequality is due to 14). Thus combining (F.38) and (F.39), we know that
(s' s, eit (s,
Term (ii) S
Σ S'E8
(Vhtn(s)) ((
C2
v vh+r(6") (E.40)
Now following the argument first identified by Azar et al. (2017), we proceed to upper bound (E.40)
Term (ii) S
Σ
Pk (s')s,
HH
O2
-(vin(6)) - -kh+z(s))
Nk (1,
S'ES
41

---

Bpt (1),a)
Vi
h+1
Vi
h+1
HHH (1,
(E.41)
H
where C2 > 0 is another absolute constant. The first inequality is by Vab S + and the second inequality is due to V 1+41.Vit E [0, H]. Finally, combining (E.37) and (E.41), we prove Lemma E.8.
Lemma E.9 (Bernstein bounds for TV robust sets and optimistic and pessimistic robust value estimators). Under event & in (E.35), suppose that the optimism and pessimism (E.14) holds at (h+ + k,, holds that
Vh [hti] - (pp(a.
Vo-1]]
Vb h+1 - Ep Ep. (s.a: (a,,; Pr,
max
h+1
V Pr (1aaa)
V
0i1 +
(
E
V Fhti
V
h+1
HH
+
(s, V1
H
(s. VK
where log(8 AH ///2/8) and c1, d2 are absolute constants.
Proof of Lemma E.9. This follows from the same proof as Lemma E.8 and thus omitted.
Lemma E.10 (Non-robust concentration). Under event & in (E.35), suppose that the optimism and pessimism (E.14) holds (h 1, k)), then holds that
E (Bpg(lsaa) - (p:((11)) [W h+1
[h+i]
1 H
Bpp(-1aa)
V h+1
1h-1
d H
N as
where = log(S>AH2 and d2 is an absolute constant.
Proof of Lemma E.10. According to the second inequality of event E, we have that
(Epg - (Ep;((lo.)))
V V h+1
Σ S'ES
(8 ci
O2t ( (Vit1(6)- - khri(s)).
+
a)
where we also apply 14, that V 1441(s) (5') 2 (s'). Now using the same argument as (E.41) in the proof of Lemma E.8, we arrive
E (1)a))))) Epg((1))) V/ h+1 Lht1]
Vk (s') Vh (s')
Epp(1a0)
CyH'St
H
(1,
which finishes the proof of Lemma E.
E.8.2 Variance Analysis
Lemma E.11 (Variance analysis 1). Suppose that the optimism and pessimism (F.14) holds at (h+ + 1),,, then the following inequality holds,
V V (Vec + vh+tt)/
-Vgg(1s..) Vittap- 2 S 4H E PEpEcea
Vi Thtt vh+1
42

---

Proof of Lemma E.I1. Directly consider that the left hand side can be upper bounded by the follow- ing.
(V h+1 + -V/++) 1 - V (p((aa)))) 1, 10]
W (1
- E Bppclomn) (v + v )² /4 (Bpg(lana) (Vitt. )0) )
+ (Ept(iin)) (Viit + kh+t /2))² (Epp((ion)) (itta..r. =))
(E.42)
V h41 Mh+i, Vi+L.. * E [0, H] (by the correctness of (E. 14) and the definitions of
Since all of
V Va+i h+1)). 1). we can further upper bound the right hand side of (E.42) as
V Vegcieaa (vh+1 kh+t1 //2 -V pp(lle))) Vitti.er,00
(vi+t h+t1 + kh+tt 12 Vi++i
S 4H 18 (pge(1a))
V [h+i]
S 4H (
where the last inequality due the correctness of (E.14) at (h+1, This proves Lemma E.11.
Lemma E.12 (Variance analysis 2). Under event in (E.35), suppose that optimism and pessimism (E. 14) holds at (h + k), then it holds that
V ppc(1s0) (V kh+1) /2) -Vp((la,a)
Vis V
HH
S 4H (pg()aa)) V Vh+11
+
+1.
N (s, a)
Proof of Lemma 1.. We first relate the variance on P/ the variance on Pj Specifically, we have
(V h+1 + v 1/2 VVr
(V vhtt)/
V (Pttlaa)
Eppcllaa) [(Vin ((htt++ Epgclosa [ (Vh+t vhita) +Kir)) 27
(V N+t + r 27 [ (Phti + Vkri Epp((e.0)
+ E (pg()1a))
EE43)
Since (V) h+t + V 1/2 [0, H}. we can further upper bound (E.43) by
V Vp
(Vh h+1 + +
/2|
V Vp
(v/. h+i + Vh vh+t) )
$ 2
Σ
(s')s,)))
s'eS
S H2 Σ
Pt o1l (H VI
C2e (4
SES
Gt
St
SH..
(1
Ni(s.a)VI)
S1+ (s,
(E.44)
43

---

where the second inequality is by the second inequality in event &, the third inequality is by Cauchy- Schwartz inequality and the probability distribution sums up to and the last inequality is from Vab S b. Thus by (E.44), we can bound our target as
W Wppclee [ (v + (1tti) ) /2 -Vrg(laa) V
V
V Px (Viit + Li+t1 /2| -Vg(-1o,a) Viti
SH (8) V1
+1.
(B.45)
Now by the same proof of Lemma E.11, using the correctness of (E.14) at (h + 1, k)). we can show that
Vpg(lbaa (V h+t vh-1) VVR((laa))
V V
S 4H ()g()s,)) V v
(E.46)
Combining (E.45) and (E.46), we can finish the proof of Lemma E.
E.8.3 Other Auxiliary Lemmas
Lemma E.13 (Lemma 7.5 in Agarwal et al. (2019)). For the sequences of (sh, 0 hh it holds that
k H.K
H.H
H ΣΣ
(* ) v1 S. HS.log(K).
where is absolute constant.
Proof of Lemma E.13. See Lemma 7.5 in Agarwal et al. (2019) for a detailed proof.
F Proofs for Extensions in Section B.4.2
In this section, we prove the theoretical results in Section B.4.2.
F1 Proof of Corollary B.5
Proof of Corollary B.5. We consider applying Algorithm on the auxiliary S x A-rectanngul RMDP with TV robust set M (see Section B.4.2) which satisfies the vanishing minimal value assumption (Assumption 4). Suppose the algorithm outputs #1, ... ...... 7 for the K episodes. Then Theorem 4.3 shows that by proper choice of the hyperparameters, with probability least 1 8
Regret (K)
Σ max V 1, ( (51) 1,P. (81)
V#
#
s 0o
V
min
H2
(FI)
where r' = log2 (SA and 2 2p' E [0, 1). In the sequel, we prove that for any policy of M and its induced policy 7 of M,, their robust value functions coincide at the initial state E S, that is.
V P.
(s1) K
1.P' (s1).
where Vi 1.F=. ē the robust value function of in M (S,.HH, Φ), and Vi is the
robust value function of 7e in M,, (S. A. H. P Ry Φ'). To this end, we actually prove stronger result that for any step h E [H], it holds that
h0' : A.P. - (8) Vãs h.Pr, / (s); E.
(F2)
44

---

We prove (F.2) by induction. For step H. by robust Bellman equation, we have that, for any (s,a) E S A,
H-1
(d) O H.
(s,0) (,, (0))H-1. 1
(s, (s, QH. o (s,a).
and thus for any S,
V h. (5) (
(8) = ER((1s) (d))-1 2 H..
( H.P. (.
= -B+s(11s)
Vi8 H.P", (s)..
This proves (F.2 for step H. Suppose that (F.2) holds some step h + 1, that is,
(d))* V
(s) =
V h+ (5), Vs E S.
(FF3
Then for step h, by robust Bellman equation and Proposition 4.2, we have that
(p) (,, (p)) = Ry a) (p')a-1 pl E (e,a::
(2) -
H-1
(s a)) (p')t-1
E (e,.P)p))
V
4
(F.4)
where the last equality utilizes Proposition 4.2 since min es h+1,F=, (s) 0, and we adopt the notation
V
((s,a;PT) {P)
P(-) P()E A()): sup S' (s s, a)
P(s')
1 p..
Notice that by the definition (B.3), we know for (s, a) E S x A holds that Pj: (-1s,a) (h()), which is supported on S. Therefore,
equivalently write
P(s')
B, a; PT)
P()) (()))(5))))) sup WES (s //
P(s')
P()) E A(S): WES (s
sup
=B, PR).
(F5)
Thus by (F.4) and (F.5) and the induction hypothesis (F.3), we obtain that for any (s, S
A,
(0')-~1 P. (5.a) Rs,, a) + (p')/ EB,(aa)))) V*
Ry,n a) + EB,(0,::P)
Vis ( = (s,
where the second equality applies (F.3) and the last equality is from robust Bellman equation. Consequently, for any E S, we have that
V 1. 1. (s) = Ez(-10) (00 O² 0F.Fa..(.))) (x.
@ (h.pp.(ss.) (s,
= =Eng(1ss)
- h.P., (s));
which finishes induction argument, proving our claim (F:2). By taking = 1, we can derive that for any initial state 81 E S, it holds that for any policy गे of M and its induced policy 7s of M
V 1. (81)
V x (81)
45

---

This indicates two facts: the first is that
max V
( max VT.p (81),
(F.6)
where on the right hand side the maximization is with respect to all the policies for My; the second that
V* 1. x (51)
V 1,P (81),
(F.7)
for each is E [K], where recall that म* is the policy output by Algorithm I for episode k. As result, k= of M, during interactive data collection satisfies with probability at least
the k policies (T & 1 6,
Regret& (K)
Σ
max V (i.p-..a
Vi,P", (81)
3
K
max V
1. x (81)
V**
1, $ (81)
t
k=1
0
min { HH, (2 2p') H2 S
where in the second equality we apply the facts (F.6) and (F.7), and the last inequality follows from (F.1) and that p = 2 -2p'. This completes the proof of Corollary B.5.
L
46

---

NeurIPS Paper Checklist
The checklist is designed encourage best practices for responsible machine learning research, addressing issues of reproducibility, transparency, research ethics, and societal impact. Do not remove the checklist: The papers not including the checklist will be desk rejected. The checklist should follow the references and follow the (optional) supplemental material. The checklist does NOT count towards the page limit.
Please read the checklist guidelines carefully for information on how to answer these questions. For each question in the checklist:
You should answer [Yes], [No], or [NA].
[NA] means either that the question Not Applicable for that particular paper or the relevant information is Not Available.
Please provide short (1-2 sentence) justification right after your answer (even for NA).
The checklist answers are an integral part of your paper submission. They are visible to the reviewers, area chairs, senior area chairs, and ethics reviewers. You will be asked to also include (after eventual revisions) with the final version of your paper, and its final version will published with the paper.
The reviewers of your paper will be asked use the checklist as one of the factors their evaluation. While "[Yes] is generally preferable to "[No]" ", it is perfectly acceptable to answer "[No] providedd proper justification is given (e.g.. "error bars are not reported because it would be too computationally expensive" or "we were unable to find the license for the dataset we used"). In general, answering binary way, we
"[No] or "[NA]" is not grounds for rejection. While the questions are phrased acknowledge that the true answer is often more nuanced, please just use your best judgment and write justification to elaborate. All supporting evidence can appear either in the main paper or the supplemental material, provided in appendix. If you answer [Yes] to a question, in the justification please point to the section(s) where related material for the question can be found.
IMPORTANT, please:
Delete this instruction block, but keep the section heading "NeurIPS paper checklist",
Keep the checklist subsection headings, questions/answers and guidelines below.
Do not modify the questions and only use the provided macros for your answers.
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Sections 2, 3, 4.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results be expected to generalize other settings.
is fine include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: Section B.5
47

---

Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, c.g., if the approach was only tested few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: Sections 3, 4, and the Appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions the paper (regardless whether the code and data are provided or not)?
Answer: [NA]
Justification:
This is theoretical work and we do not conduct experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
48

---

If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. w
For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm. (b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [NA]
Justification:
This is theoretical work and we do not conduct experiments.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips. cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https: Cooeeubmiiiii SoooeeSumiissooPPoo
/ //nips... /tippscc/pppit wttp:cccppppppcccccccee/ococpcca
for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
49

---

Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Question:
Answer: [NA]
Justification:
This is theoretical work and do not conduct experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented the core the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: This is theoretical work and we do not conduct experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
OK to report 1-sigma error bars, but one should state The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative error rates).
If error bars reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification: This is theoretical work and we not conduct experiments.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
50

---

The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethies
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https: /ttp:r//n........eee.. wtt.rrsssccccooeeeeooooooooo cw/public.cpccccccccccccc.pc..bt Cppublic/thhii c/Etci//thcceeeeeei etwhiiiiieeeeeeeeeee
Answer: [Yes]
Justification: The research in this work conforms with the NeurlPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g.. if there special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: There is societal impact of the work performed.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, scraped datasets)?
Answer: [NA]
Justification: The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses such risks.
51

---

Released models that have high risk for misuse or dual use should be released with necessary safeguards to allow for controlled use of the model. for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification: The paper does not use existing assets.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re- re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: The paper does not involve crowdsoureing nor research with human subjects.
52

---

Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According to the NeurIPS Code Ethics, workers involved in data collection, curation, other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
53


Reviews:
[{"review_id": "p6oBVJmUt7", "reviewer": "Reviewer_3BYp", "summary": "The paper addresses the challenges in distributionally robust reinforcement learning (DRRL), particularly focusing on robust Markov decision processes (RMDPs) under the framework of interactive data collection. Unlike previous work that depends on generative models or pre-collected datasets, this study emphasizes interactive data collection where the learner refines policies through interaction with the training environment. The main contributions include identifying fundamental challenges that for total variation (TV) distance, there exists a hard RMDP that all algorithms at least need $O(KH)$ regret. In addition, by introducing a vanishing minimal value assumption to mitigate these challenges, this work proposes a sample-efficient algorithm (OPROVI-TV) with regret $O(\\sqrt{\\min\\{H, 1/\\rho\\}H^2 SAK } after $K$ trajectories, which matches the results from the state-of-the-art non-robust MDP online learning and also robust MDP with generative model.", "questions": "1. In the introduction \"Given that all the existing52\nliterature on robust RL theory relies on a generative model or pre-collected data\" \nNot all the existing works are using generative model or offline dataset? Such as [1]. If so, please check\n\n\n[1] Dong, Jing, et al. \"Online policy optimization for robust mdp.\" arXiv preprint arXiv:2209.13841 (2022).", "limitations": "Well-answered", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. This work focuses on interactive data collection for robust RL, addressing practical challenges and moving beyond reliance on generative models or pre-collected datasets, which is an underdeveloped open direction.\n2. The proposed OPROVI-TV algorithm balances exploration and exploitation, providing strong guarantees for online regret and sample complexity for such robust RL problems with online settings.", "weaknesses": "1. The main assumption (Assumption 4.1) that this work mainly depends on is interesting, but will such assumptions make the problems (robust MDPs with TV uncertainty set ) not a suitable and meaningful robust RL problems for those tasks? \nSpecifically, no matter Assumption 4.1 or the fail-state assumption from [1] indeed implies that for all policy, $ \\min_{s\\inS} V_{h}^{\\pi}(s) = 0 $ for all $h=1,2,\\cdots, H$ if the reviewer does not miss something. The main concern from the reviewer is that (actually the author already discuss about this in Appendix B.4.1): For those tasks under such assumptions, if we consider robust MDPs using TV distance, will those robust MDPs directly equivalent to some non-robust MDPs but with a discounted reward (non-robust MDP with reward function $r<1-\\rho/2)$.\n* So in such cases, will the robust RL problem using TV to construct the uncertainty set be meaningful? I think those robust formulations will reduce back to non-robust MDPs. So maybe some uncertainty set with support control (the adversarial can't make the transition kernel to be out of the support of the nominal transition kernel) will be more suitable to use in such tasks.\n* In addition, the reviewer believe that under Assumption 4.1, the regret of this problem can be improved to $O(\\sqrt{\\min\\\\{H, 1/\\rho\\\\}^3 SAK}?$ Since the maximum value of the robust value function will be $\\min\\\\{ H, 1/\\rho\\\\}$ but not $H$ in the non-robust value function anymore. \n\n\n\n[1]Panaganti, Kishan, and Dileep Kalathil. \"Sample complexity of robust reinforcement learning with a generative model.\" International Conference on Artificial Intelligence and Statistics. PMLR, 2022.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Q1: About whether Assumption 4.1 reduces our problem setup to a non-robust RL problem. (Weakness 1&2)**\n\n**A1:** Here we clarify that Assumption 4.1 does **not** reduce the problem to its non-robust counterpart. \n\nIt is a *misinterpretation* of the discussions in Appendix B.4.1 that Assumption 4.1 reduces the problem to non-robust RL. In fact, Appendix B.4.1 clearly states that (Lines 706-709) under Assumption 4.1, the TV-robust MDP is equivalent to a discounted *robust* MDP with another formulation of robust set (bounded transition probability ratio w.r.t. the nominal model, see Proposition 4.2). Thus, under Assumption 4.1, our problem setup is still in the regime of robust RL and is fundamentally different from doing non-robust RL.\n\nRegarding robust sets where one explicitly assumes that the adversarial can't change the support, again thanks to the equivalent result in Proposition 4.2, we can actually solve robust RL with interactive data collection for discounted robust MDPs with robust set containing transitions that have bounded ratio to the nominal model (and thus the support does not change) by using a variant of our Algorithm 1 (see discussions in Appendix B.4.3). \nIt is an interesting future work to consider other (perhaps more general) types of robust set where the adversarial can't change the support.\n\n\n**Q2: Whether the regret is further improvable to $\\widetilde{O}(\\sqrt{\\min\\{H, 1/\\rho\\}^3SAK})$ given that the maximum value of the robust value function is $\\min\\{H, 1/\\rho\\}$? (Weakness 3)**\n\n**A2:** We first want to point out that achieving the regret bound $\\widetilde{O}(\\sqrt{\\min\\{H, 1/\\rho\\}^3SAK})$ seems impossible. Specifically, even for MDPs with $V_{\\text{MAX}} = R$, the lower bound still scales with $\\Omega(\\sqrt{R^2HSAK})$. The intuition is that when we consider the inhomogeneous setting where the transition kernel $\\{P_h^{\\star}\\}_{h\\in H}$ varies in the $H$ time steps (as we considered in this paper), the factor $\\sqrt{H}$ is inevitable. We believe that the dependence on $H$ instead of $\\min\\{H, 1/\\rho\\}$ is inherent to the problem and cannot be further improved.\n\nIn addition, we need to point out that, actually the proof of the current result has already utilized the fact that the upper bound and the variance of the robust value functions are controlled by terms related to $\\min\\{H, 1/\\rho\\}$, as is observed by the reviewer. More specifically, in the proofs of Lemma C.2 (showing that the robust value estimators are optimistic/pessimistic, see Eq (C.15)) and Lemma C.5 (controlling the summation of robust value functions over time horizons and episodes, see Eq (C.22)), we have utilized the fact that the robust value function is bounded by $\\min\\{H, 1/\\rho\\}$ to make the sharpest of our result.\n\nGiven all that, we are still the first work that provides the algorithm with sharp sample complexity bound in the interactive data collection regime. We leave it as a future work to further figure out the sample complexity lower bound under assumptions that can make interactive data collecting robust RL feasible.\n\n**Q3: About the previous work [1] on robust RL with interactive data collection.**\n\n**A3:** We do agree that this work also considers robust RL that relies on interactive data collection, and we actually cited and discussed this work in our paper (see Appendix B.1, Lines 649 to 653). \n\nHowever, as we pointed out in Appendix B.1, this work exhibits an essential flaw (misuse of Lemma 12 therein) in the proof of their main result (online regret). This error invalidates their theoretical results, as Reviewer sH9q has also recognized. Thus, even though [1] works on the setup of interactive data collection, they actually did not answer the question that *\"Can we design a provably sample-efficient robust RL algorithm that relies on interactive data collection in the training environment?\"*. In contrast, we are the first work that proves the hardness result in the general case and provides the algorithm with sharp sample complexity bound in the interactive data collection regime under suitable assumptions. We would make this comparison clearer in the main part of our paper during revision. \n \n\n**References:** \n\n[1] Dong, Jing, et al. \"Online Policy Optimization for Robust MDP.\" arXiv preprint arXiv:2209.13841 (2022).", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "iwGbiY2GcM", "reviewer": "Reviewer_BadN", "summary": "This paper studies robust RL in a finite-horizon RMDP through interactive data collection. They give both a fundamental hardness result in the general case and a sample-efficient algorithm within tractable settings.", "questions": "Please see the weakness part.", "limitations": "No", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. Unlike previous work, which relies on a generative model or a pre-collected offline dataset enjoying good coverage of the deployment environment, this paper tackles robust RL via interactive data collection.\n2. This paper introduces the vanishing minimal value assumption to RMDPs with a TV-distance robust set, postulating that the minimal value of the optimal robust value function is zero, which eliminates the support shift issue for RMDPs.\n3. This paper proposes an algorithm with sharp sample complexity.", "weaknesses": "1. This paper is purely theoretical. Although I understand the focus of this paper, but I still want to see some empirical results or even some simulations to get more insight. Moreover, an algorithm is given in this article, thus some numerical studies are required. \n2. I am not sure if the Interactive Data Collection design is feasible in practice especially in some real-world problems. \n3. Some more detailed discussion about the comparison between the proposed method and the baseline methods are required especially when they are designed for different cases. So maybe some numerical results are helpful.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Q1: This paper is purely theoretical. Although the reviewer understands the focus of this paper, but still want to see some empirical results to get more insight. Moreover, since an algorithm is given in this article, some numerical studies and comparisons are required. (Weakness 1&3)**\n\n**A1:** Thank you for recognizing that our work focuses on theoretical study. We appreciate your suggestion to add experimental results. We will consider including them in the revision.\n\n**Q2: About the feasibility of the interactive data collection setup. (Weakness 2)**\n\n**A2:** Thanks for the question! Yes, this setup is indeed possible and is even a common practice in certain real-world problems. For examples, in robust RL for robotics, e.g., [1, 2, 3, 4], the agent is usually trained in a simulated environment (corresponding to the training environment in our theoretical setup) through trial and error, which is interactive data collection since the algorithm does not use pre-collected offline data or a generative model (we remark that in the theoretical literature a generative model means that the algorithm has the access to directly query the next state given *any* state-action pair). The goal is to ensure that the robot still functions well even if the environment changes (corresponding to the testing environment in the theoretical setup), e.g., when the coefficient of friction differs or the weight of the robot changes. Thus the interactive data collection setup is indeed feasible in real-world problems.\n\n**References:** \n\n[1] Pinto, Lerrel, James Davidson, Rahul Sukthankar, and Abhinav Gupta. \"Robust adversarial reinforcement learning.\" In International conference on machine learning, pp. 2817-2826. PMLR, 2017.\n\n[2] Tessler, Chen, Yonathan Efroni, and Shie Mannor. \"Action robust reinforcement learning and applications in continuous control.\" In International Conference on Machine Learning, pp. 6215-6224. PMLR, 2019.\n\n[3] Zhao, Wenshuai, Jorge Peña Queralta, and Tomi Westerlund. \"Sim-to-real transfer in deep reinforcement learning for robotics: a survey.\" 2020 IEEE symposium series on computational intelligence (SSCI). IEEE, 2020.\n\n[4] Brunke L, Greeff M, Hall A W, et al. Safe learning in robotics: From learning-based control to safe reinforcement learning[J]. Annual Review of Control, Robotics, and Autonomous Systems, 2022, 5(1): 411-444.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "PHPAmQRMuF", "reviewer": "Reviewer_sH9q", "summary": "This paper studies the learnability of the optimal policy for robust Markov decision process (RMDP) under the interactive data setting. The paper first show a fundamental hardness results which necessitates identifying a subclass of RMDPs which is actually solvable. The authors propose an algorithm whose sample complexity and regret are analyzed.", "questions": "1. In my understanding, this is the first **value-based** online/interactive data collection DRRL algorithm. Can authors confirm this is the case?\n2.  I am aware of Dong et al., 2022, and I am also aware that their proof has fatal flaws. I would like to mention that there is another actor-critic method for DRRL, Zhou et al., 2023 [1]. I believe this can also handle online interaction with the nominal model and learn a robust policy. Can the authors compare it with your work, especially about their robust critic component.\n3. Assumption 4.1 is a sufficient condition for any RMDP to be solvable. Can the authors share some insights about the \"gap\" between this sufficient condition and a could-be necessary condition.\n\nReference\n[1] ZHOU, R., LIU, T., CHENG, M., KALATHIL, D., KUMAR, P. and TIAN, C. (2023). Natural actor-560\ncritic for robust reinforcement learning with function approximation. In Thirty-seventh Conference561\non Neural Information Processing Systems.", "limitations": "No other limitations I would like to bring up.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper is well-organized and well-written.\n2. The setting is meaningful and motivated. \n3. The analysis is thorough. \n4. The comparisons with existing works are very detailed, making the paper easy to follow.", "weaknesses": "I am not aware of notable weaknesses.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Q1: Whether our work is the first value-based interactive data collection DRRL algorithm?**\n\n**A1:** Thanks for pointing this out! But we want to clarify that our algorithm is *model-based* since it necessitates an explicit estimation of the training environment transition kernel, denoted by $\\widehat{P}$. We will make this conceptual point clearer in the revision.\n\n**Q2: Comparison with the previous work [1].** \n\n**A2:** Thanks for pointing out this interesting work [1]! We have also cited and mentioned this work in the paper. [1] proposes a novel robust natural actor-critic algorithm under function approximation to solve robust RL with interactive data collection, also with certain theoretical guarantees. \n\nThe key difference between the theory in [1] and our work is in the data assumptions and thus the subsequent techniques required to design and analysis the respective algorithms. Regarding the data assumptions, [1] relies on interacting with a nominal environment that satisfies several concentrability and mixing assumptions (Assumptions 1, 3, 6 in [1]), and thus [1] does not explicitly address the problem of *exploration* where the agent needs to adaptively use interactive data collection to explore and robustify its policy. In contrast, our work does not make any assumption regarding the concentrability or mixing properties of the underlying nominal MDP. Instead, we use algorithmic design to incentivize the agent to explore automatically. \n\nBesides, regarding the comparison to the robust critic component, since our algorithm is not in the actor-critic style, a direct comparison is hard. But still, we maintain a robust value function estimation during training, which is similar to a robust critic. The key difference is that, in order to address the fundamental challenge of exploration during interactive data collection, our robust value estimator features a carefully designed optimistic bonus that encourages the agent to explore the nominal environment sample-efficiently. This is different from the design idea of the robust critic in [1].\n\n**Q3: About the \"gap\" between the sufficient condition (Assumption 4.1) and other potentially necessary conditions.**\n\n**A3:** While we have established a *worst-case* hardness result without the vanishing minimal value assumption, we acknowledge that more general sufficient or even necessary conditions for sample-efficient learning with interactive data collection may exist. We agree with the reviewer that this is an interesting and challenging direction to explore, as our vanishing minimal value assumption is currently the most general sufficient condition enabling sample-efficient learning to the best of our knowledge. We will include further discussions on this topic in our revision and will consider it for future research.\n\n**References:**\n\n[1] Zhou, Ruida, et al. \"Natural actor-critic for robust reinforcement learning with function approximation.\" Advances in neural information processing systems 36 (2023).", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "JSCEOSKy8l", "reviewer": "Reviewer_bEix", "summary": "This work deal with sample complexity of Robust MDPs. The major improvement is that, contrary to previous research that relies on generative models or pre-collected datasets, this paper focuses on RMDPs learning through interactive data collection, addressing two key challenges: distributional robustness and balancing exploration and exploitation.\n\nThree main contributions are :\n\n1)  Explaining that sample-efficient learning is unachievable without additional assumptions due to the curse of support shift, where training and testing environments may have non-overlapping distributions.\n2) Introducing of the vanishing minimal value assumption for Robust Markov Decision Processes (RMDPs) with a total-variation distance robust set, assuming the minimal value of the optimal robust value function is zero, leading to a tractable case.\n3)  Proposing an algorithm with a provable sample complexity guarantee under this framework.", "questions": "9) Do you think that vanishing minimal assumption is restrictive to derive Deep Robust RL algorithm ? \n10) Do you think it would be possible to adapt Proposition 4.2 to other norms such as $L_p$ ? \n11) To clarify thing, the main difference between generative model setting and online setting in RMDPs is to deal with support shift of kernel ? \n12) I understand that KL and $\\chi^2$ is a slightly different problem, does vanishing minimal assumption for KL or $\\chi^2$ divergences RMDPs make sense as the definition of these divergences already impose bounded support shift of transition kernel ?\n13) From a practical point of view, would the idea that sample complexity of RMDPS is smaller than MDPs (both in online and generative model setting) could lead to more sample efficient algorithms ?", "limitations": "No limitations.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The strengths of this paper are :\n\n1) The paper is clearly written and ideas are well exposed.\n2) Authors derive a nice lower bound with counterexample on the sample complexity of RMDPs in an online setting, and tight upper bound using extra assumptions such that vanishing minimal value assumption where TV uncertainty set can be rewritten using Radon-Nikodym derivatives.\n3) The proof seems correct for me.\n4) Algorithm is quite classic but make sense to derive robust policy while balancing exploration and exploitation.", "weaknesses": "5) It would also be interesting to extend results for $s$- rectangular case.\n6) There is no lower bound with vanishing minimal assumption to ensure that the upper bound under these assumptions is tight.\n7)  It would be nice to add the range of $\\epsilon$ for the upper bound where sample complexity is valid or give  a condition on K rather than saying \"lower order term in K\"\n8) I think it would be interesting to gives more intuition on vanishing minimal assumption.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Q1: It is interesting to extend to $\\mathcal{S}$-rectangular case.**\n\n**A1:** Thanks, we appreciate your suggestions! But still, we would like to emphasize that our work is the first one on robust RL with interactive data collection that proves the hardness result and provides the algorithm with sharp sample complexity under suitable assumptions. We leave possible extensions to a broader range of cases to future work.\n\n**Q2: About the lower bound under the vanishing minimal value assumption.**\n\n**A2:** Thank you for this question! The prior work [1] derived a lower bound of $\\Omega(\\min\\{H_\\gamma,1/\\rho\\}H_\\gamma^2SA/\\varepsilon^2)$ for discounted RMDPs with generative model, where $H_\\gamma = 1/(1-\\gamma)$ is the effective horizon. After examining the proof, we find this lower bound can be extended to finite-horizon RMDPs, giving an $\\Omega(\\min\\{H,1/\\rho\\}H^2SA/\\varepsilon^2)$ lower bound. This applies to both the generative model setting and the online interactive learning setting, as the latter is considered more challenging. \n\nHowever, we acknowledge that the hardness instance given by [1] does not satisfy the vanishing minimal value assumption and requires some modifications. We conjecture that this lower bound still holds with the vanishing minimal value assumption and we will attempt to provide a rigorous proof in the revision.\n\n**Q3: On lower order terms in $K$ and the range of $\\varepsilon$ s.t. the sample complexity is valid.**  \n\n**A3:** Thanks for pointing this out! For the lower order terms in $K$ of the online regret, we actually included them clearly in the proof (see Appendix E.1, Line 999). Correspondingly, the sample complexity of Algorithm 1 is $\\widetilde{O}(\\min\\{H,1/\\rho\\}H^2SA/\\varepsilon^2 + H^3SA/\\varepsilon)$ for any $\\varepsilon>0$. Thus Corollary 4.4 holds for $\\varepsilon\\in(0,c\\cdot\\min\\{1, 1/(H\\rho)\\}]$ with $c$ being an absolute constant. We will make this clear in the revision.\n\n**Q4: About intuitions on the vanishing minimal value assumption.** \n\n**A4:** As we concluded in the paper, the main difficulty of robust RL with interactive data collection is from the curse of support shift. By looking into the duality representation of the robust value functions, once the minimal values vanishes, the robust set is then equivalent to a new type of robust set without explicit support shift, thus combatting the original difficulty (Proposition 4.2). We also refer to the discussions after Proposition 4.2 for more explanations (Lines 259-265).\n\n**Q5: Is the vanishing minimal value assumption restrictive for deep robust RL?**\n\n**A5:** Thank you for asking! The vanishing minimal value assumption is a general, not restrictive, assumption for deep reinforcement learning in real-world applications. One sufficient condition for this assumption is the fail-state assumption, which is common in practice. For example, in robotics scenarios where a \"destroyed robotics\" state is absorbing and yields a minimum zero reward, it satisfies both the fail-state assumption and the more general vanishing minimal value assumption. \n\n**Q6: Is it possible to adapt Proposition 4.2 to other norms such as $L_p$?** \n\n**A6:** Thanks for the interesting direction! We do notice that previous works e.g., [2] (and references therein) considered the general $L_p$-norm, but in a different learning setup than ours. However, the general $L_p$-norm robust set gives a complicated duality representation for the robust Bellman operator (Lemma B.5 in [2]), and the vanishing minimal value assumption alone does not provide similar equivalence results like Proposition 4.2 to combat the curse of support shift. This assumption does rely on $p=1$. Therefore, a direct extension of Proposition 4.2 to $L_p$-norm is hard. However, we appreciate this question. It definitely serves as an exciting direction to study when robust RL with interactive data collection is possible under general $L_p$-norm robust set.\n\n**Q7: Is the difference between generative model and the online setting to deal with support shift?**\n\n**A7:** Yes! More specifically: For generative model setting, since the learner can query each state-action pair for the next state, there is no curse of support shift in estimating the nominal transition. In contrast, in the online setting, the agent collects data by interacting with the training environment, and there could exist hard-to-reach states which are important for generalizing to testing environments (support shift happens).\n\n**Q8: Does vanishing minimal value assumption for KL or $\\chi^2$ divergences make sense?**\n\n**A8:** As we have already mentioned in **Q4** and **Q6**, this assumption is tailored for the TV robust set. It is not a suit for KL or $\\chi^2$ divergences RMDPs.\n\nHowever, we note that even though there is no explicit support shift for KL and $\\chi^2$, we an still build hard instances where the probability of reaching certain states that appear in the test environment is extremely low in the training environment (a broader understanding of support shift, see Appendix B.3). Thus it is unknown whether robust RL is possible with interactive data collection for these types of robust sets even with suitable assumptions. We leave this question as future work.\n\n**Q9: Would that the sample complexity of RMDPs is smaller than MDPs leads to more sample efficient algorithms?** \n\n**A9:** We remark that RMDPs and MDPs use different performance metrics. The former seeks the optimal robust value function while the latter finds the optimal standard value. Therefore, it is reasonable that deep robust RL algorithms find *robust* optimal policy using less samples than standard RL algorithms to find a standard optimal policy.\n\n**References:**\n\n[1] Shi, Laixi, et al. \"The curious price of distributional robustness in reinforcement learning with a generative model.\" NeurIPS 2023.\n\n[2] Clavier, Pierre, et al. \"Towards minimax optimality of model-based robust reinforcement learning.\" arXiv preprint 2023.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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: This work introduces algorithms for robust MDPs. It is the first work to prove bounds in the setting of interactive data collection from the base model in this scenario. The authors also prove impossibility results that justify the structural assumptions under which they analyze their algorithms. The reviewers agreed this work meet the criteria for publication at Neurips.
Decision: Accept (poster)