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_cc_2024_Conference
Published: 2024-05-13 23:13:29

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.

Main paper: 
 introduction: 
 Reinforcement learning (RL) serves as a framework for addressing complex decision-making problems 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 et 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 et al., 2018) and autonomous driving (Kiran et 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 et al., 2020) becomes a remedy -a process in which the RL agents are trained in some simulated environment and subsequently deployed in real-world settings. Nevertheless, the training environment may differ from the real-world environment. Such a discrepancy, also known as the simto-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 RL (Iyengar, 2005; Pinto et al., 2017; Hu et 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.A robust RL problem is 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 a 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-error (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 on 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 a provably sample-efficient robust RL algorithm that relies on interactive data collection in the training environment?Answering the above question faces a 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, it 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 precollected 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 to guarantee the performance of the learned policy in testing environments. The situation is similar if one has a 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.In this work, we study robust RL in a finite-horizon RMDP with an S × 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 are 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 an Ω(ρ • HK)-online regret (Theorem 3.2) under at least one RMDP instance. Here, ρ signifies 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-efficient robust RL via interactive data collection in general.Identifying a 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. In a 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.operator asE Q [f ] := inf p(•)∈Q E X∼p(•) [f (X)].For any x, a ∈ R, we denote (x) + = max{x, 0} and x ∨ a = max{x, a}. We use O(•) to hide absolute constant factors and use O to further hide logarithmic factors. For a positive integer H ∈ N + , we denote the set {1, 2, . . . , H} by [H]. 
robust markov 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, P ⋆ , 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 ⋆ = {P ⋆ h } H h=1 is the collection of nominal transition kernels where P ⋆ h : S × A → ∆(S). The set R = {R h } H h=1 is the collection of reward functions where R h : S × A → [0, 1]. For simplicity, we denote P = {P (•|•, •) : S × A → ∆(S)} as the space of all possible transition kernels, and we denote S = |S| and A = |A|. Most importantly and different from standard MDPs, the RMDP is equipped with a mapping Φ : P → 2 P that characterizes the robust set of any transition kernel in P. Formally, for any transition kernel P ∈ P, we call Φ(P ) the robust set of P . One could interpret the nominal transition kernel P ⋆ h as the transition of the training environment, while Φ(P ⋆ h ) contains all possible transitions of the testing environments.Given an RMDP (S, A, H, P ⋆ , R, Φ), we consider using a Markovian policy to make decisions. A Markovian decision policy (or simply, policy) is defined as π = {π h } H h=1 with π h : S → ∆(A) for each step h ∈ [H]. To measure the performance of a policy π in the RMDP, we introduce its robust value function, defined as for any (s, a) ∈ S × A, V π h,P ⋆ ,Φ (s) := infP h ∈Φ(P ⋆ h ),1≤h≤H E { P h } H h=1 ,{π h } H h=1 H i=h R i (s i , a i ) s h = s , Q π h,P ⋆ ,Φ (s, a) := inf P h ∈Φ(P ⋆ h ),1≤h≤H E { P h } H h=1 ,{π h } H h=1 H i=h R i (s i , a i ) s h = s, a h = a .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 = {P h } H h=1 ⊂ P as V π h,P,Φ and Q π h,P,Φ , which we usually use in the sequel. Among all the policies, we define the optimal robust policy π ⋆ as the policy that can maximize the robust value function at the initial time step h = 1, i.e.,π ⋆ ∈ argmax π={π h } H h=1 V π1,P ⋆ ,Φ (s 1 ), ∀s 1 ∈ S.(2.1)In other words, the optimal robust policy π ⋆ 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 s 1 ∈ S is fixed. Our results could be directly generalized to s 1 ∼ p 0 (•) ∈ ∆(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 h } H h=1 ⊂ P in the same way as (2.1). We denote the optimal robust value functions associated with P as V ⋆ h,P,Φ and Q ⋆ h,P,Φ respectively. S × A-rectangularity and robust Bellman equations. We consider robust sets Φ that have the S × A-rectangular structure (Iyengar, 2005) . which requires that the robust set is decoupled and independent across different (s, a)-pairs. 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 × A-rectangularity). We assume that the mapping Φ satisfies for any transition kernel P ∈ P, the robust set Φ(P ) is in the form of Φ(P ) = (s,a)∈S×A P(s, a; P ), where P(s, a; P ) ⊆ ∆(S).Under above Assumption 2.1, we have the so-called robust Bellman equation (Iyengar, 2005; Blanchet et al., 2023) which gives a dynamic programming representation of robust value functions.Proposition 2.2 (Robust Bellman equation). Under Assumption 2.1, for any transition P = {P h } H h=1 ⊆ P and any policy π = {π h } H h=1 with π h : S → ∆(A), it holds that V π h,P,Φ (s) = E π h (•|s) Q π h,P,Φ (s, •) , Q π h,P,Φ (s, a) = R h (s, a) + E P(s,a;P h ) V π h+1,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 = {P h } H h=1 ⊆ P, the robust value functions of any optimal robust policy of P satisfies that,V ⋆ h,P,Φ (s) = max a∈A Q ⋆ h,P,Φ (s, a), Q ⋆ h,P,Φ (s, a) = R h (s, a) + E P(s,a;P h ) V ⋆ h+1,P,Φ . Taking π ⋆ h (•|s) = argmax a∈A Q ⋆ h,P,Φ (s, a), then π ⋆ = {π ⋆ h } Hh=1 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 a "distribution ball" centered at P (•|s, a). In this paper, we mainly consider this type of robust sets specified by a total-variation distance ball. We put it in the following definition.Definition 2.4 (Total-variation distance robust set). Total-variation distance robust set is defined asP ρ (s, a; P ) := P (•) ∈ ∆(S) : D TV P (•) P (•|s, a) ≤ ρ ,for some ρ ∈ [0, 1), where D TV (•∥•) denotes the total variation distance defined as 2023), which all focus on robust RL with a generative model or with a 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, as is generally adopted by the above previous works on learning RMDPs with TV robust sets. According to (2.2), we allow p to have a different support than q. That is, there might exist an s ∈ S such that p(s) > 0 and q(s) = 0. Given that, the TV robust set in Definition 2.4 could contain transition probabilities that have different supports than the nominal transition probability P ⋆ (•|s, a).EQUATIONAn 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 a duality representation that only uses the expectation under the nominal transition kernel, as is shown in the following theorem and proved in Appendix C.1.Proposition 2.5 (Strong duality representation). Under Definition 2.4, the following duality representation for the robust expectation holds, for any V : S → [0, H] and P h : S × A → ∆(S),E Pρ(s,a;P h ) V = sup η∈[0,H] -E P h (•|s,a) (η -f ) + - ρ 2 • η -min s∈S V (s) + + η . (2.3)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 Definition 2.4, the robust value functions satisfies thatmax (s,a)∈S×A Q π h,P,Φ (s, a) -min (s,a)∈S×A Q π h,P,Φ (s, a) ≤ min H, ρ -1 , max s∈S V π h,P,Φ (s) -min s∈S V π h,P,Φ (s) ≤ min H, ρ -1 ,for any transition P = {P h } H h=1 ⊂ P, any policy π, and any step h ∈ [H].We study how to learn the optimal robust policy π ⋆ in (2.1) from interactive data collection. Specifically, the learner is required to interact with only the training environment, i.e., P ⋆ , for some K ∈ N episodes. In each episode k, the learner adopts a policy π k to interact with the training environment P ⋆ and to collect data. When the k-th episode ends, the learner updates its policy to π k+1 based on historical data and proceeds to the subsequent (k + 1)-th 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 ε > 0, the sample complexity is the minimum number of episodes K required for the algorithm to output an ε-optimal robust policy π satisfyingV ⋆ 1,P ⋆ ,Φ (s 1 ) -V π 1,P ⋆ ,Φ (s 1 ) ≤ ε.The goal is to design algorithms whose sample complexity has small or even optimal dependence on the problem parameters S, A, H, ρ, and 1/ε.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 π ⋆ and the executed policies{π k } K k=1 . Formally, we define Regret Φ (K) := K k=1 V ⋆ 1,P ⋆ ,Φ (s 1 ) -V π k 1,P ⋆ ,Φ (s 1). The goal is to design algorithms that can achieve a sublinear-in-K regret with small dependence on S, A, H, ρ. It turns out that any sublinear-regret algorithm can be easily converted to a polynomialsample complexity algorithm by applying the standard online-to-batch conversion (Jin et al., 2018) . 
a hardness result: the curse of support shift: 
 Unfortunately, we show in this section that in general such a problem of robust RL with online data collection is impossible -there exists a simple class of two RMDPs such that an Ω(K)-online regret lower bound exists. However, previous works on robust RL with a generative model or offline data with good coverage do provide sample-efficient ways to find the optimal robust policy for this class of RMDPs. This is a separation between robust RL with interactive data collection and generative model/offline data. Please see also Figure 1 for an illustration of the example.Example 3.1 (Hard example of robust RL with interactive data collection). Consider two RMDPs M 0 and M 1 which only differ in their nominal transition kernels. The state space is S = {s good , s bad }, and the action space is A = {0, 1}. The horizon length H = 3. The reward function R always is 1 at the good state s good and is 0 at the bad state s bad , i.e.,R h (s, a) = 1, s = s good 0, s = s bad , ∀(a, h) ∈ A × [H].For the good state s good , the next state is always s good . For the bad state s bad , there is a chance to get to the good state s good , with the transition probability depending on the action it takes. Formally,P ⋆,M θ h (s good |s good , a) = 1, ∀(a, h) ∈ A × {1, 2}, ∀θ ∈ {0, 1}, P ⋆,M θ 2 (s good |s bad , a) = p, a = θ q, a = 1 -θ , ∀θ ∈ {0, 1},where p, q are two constants satisfying 0 < q < p < 1. 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 , where ρ ∈ [0, q] is the parameter characterizing the size of the robust set. We set s 1 = s good .Φ(P ) =For this class of RMDPs, we have the following hardness result for doing robust RL with interactive data collection, an Ω(ρ The solid lines represent possible transitions of the nominal transition kernel. The dashed lines represent the transitions induced by the worst case transition kernel 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 s bad to s good . We notice that when starting from s1 = s good , the nominal transition kernel keeps the agent at s good and no information at s bad is revealed.R1 = 1 R2 = 1 R3 = 1 R2 = 0 R3 = 0inf ALG sup θ∈{0,1} E Regret M θ ,ALG Φ (K) ≥ Ω ρ • HK ,where Regret M θ ,ALG Φ (K) refers to the online regret of algorithm ALG for RMDP M θ .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 a policy π is evaluated via the robust expected total rewards, or equivalently, the expected return under the most adversarial transition kernel P †,π .In such an example, as we explicitly show in the proof, when in the good state s good , the worst-case transition kernel P †,π would transit the state to s bad with a constant probability ρ > 0. But the state s bad is out of the scope of the data collection process because starting from s 1 = s good the nominal transition kernel always transits the state to s good . As a result, the performance of the learned policy at the bad state s bad is not guaranteed, and inevitably incurs an Ω(ρ  
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 × 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.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 min s∈S V ⋆ 1,P ⋆ ,Φ (s) = 0. Also, WLOG, we assume that the initial state s 1 / ∈ argmin s∈S V ⋆ 1,P ⋆ ,Φ (s).Assumption 4.1 imposes that the minimal robust expected total rewards over all possible initial states is 0. Assuming that the initial state s 1 / ∈ argmin s∈S V ⋆ 1,P ⋆ ,Φ (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, min s∈S V π h,P ⋆ ,Φ (s) = 0 for any policy π and any step h ∈ [H]. With this observation, the following proposition explains why this assumption helps to overcome the difficulty, with the proof of the proposition in Appendix C.3. Proposition 4.2 (Equivalent expression of TV robust set with vanishing minimal value). For any function V : S → [0, H] with min s∈S V (s) = 0, we have thatE Pρ(s,a;P ⋆ h ) [V ] = ρ ′ • E B ρ ′ (s,a;P ⋆ h ) [V ], with ρ ′ = 1 - ρ 2 > 0,where the TV robust set P ρ (s, a; P ⋆ h ) is defined in (3.1) and the set B ρ ′ (s, a; P ⋆ h ) is defined as 2 B ρ ′ (s, a; P ⋆ h ) = P (•) ∈ ∆(S) : sups ′ ∈S P (s ′ ) P ⋆ h (s ′ |s, a) ≤ 1 ρ ′ .2 Here we implicitly define 0 0 = 0 and a 0 = ∞ for any a > 0.Algorithm 1 OPtimistic RObust Value Iteration for TV Robust Set (OPROVI-TV)1: Initialize: dataset D = ∅. 2: for episode k = 1, • • • , K do 3:Training environment transition estimation:4:Update the count functions N k h (s, a, s ′ ) and N k h (s, a) based on D.Calculate the transition kernel estimator P k h as N k h (s, a, s ′ )/(N k h (s, a) ∨ 1).Optimistic robust planning:7: Set V k H+1 = V k H+1 = 0.8:for step h = H, • • • , 1 do 9: Set Q k h (•, •) and Q k h (•, •) as (4.2) and (4.3), with bonus k h (•, •) defined in (4.5).10:Set π k h (•|•) = argmax a∈A Q k h (•, a), V k h (•) = E π k h (•|•) [Q k h (•, •)], and V k h (•) = E π k h (•|•) [Q k h (•, •)].11:end for 12:Execute the policy in training environment and collect data:13:Receive the initial state s k 1 ∈ S.14: ) that shares the same support as the nominal transition kernel P ⋆ (•|s, a), discounted by a constant ρ ′ < 1. Intuitively, this new robust set rules out the difficulty originated in unseen states in training environments and the discount factor ρ ′ 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 discussions/examples of Assumption 4.1.for step h = 1, • • • , H do 15: Take action a k h ∼ π k h (•|s k h ), observe reward R h (s k h , a k h )In this section, we propose our algorithm that solves robust RL with interactive data collection for RMDPs with S × A-rectangular total-variation (TV) robust sets (Assumption 2.1 and Definition 2.4) and satisfying the vanishing minimal value assumption (Assumption 4.1). Our algorithm, OPtimistic RObust Value Iteration for TV Robust Set (OPROVI-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 k ∈ [K], we maintain an estimate of the transition kernel P ⋆ of the training environment by using the historical data D = {(s τ h , a τ h , s τ h+1 )} k-1,H τ =1,h=1 collected from the interactiion with the training environment. Specifically, we simply adopt a vanilla empirical estimator, defined asP k h (s ′ |s, a) = N k h (s, a, s ′ )/(N k h (s, a) ∨ 1) for any (s, a, h, s ′ ) ∈ S × A × S × [H],where the count functions N k h (s, a, s ′ ) and N k h (s, a) are calculated based on the current dataset D byN k h (s, a, s ′ ) = k-1 τ =1 1 (s τ h , a τ h , s τ h+1 ) = (s, a, s ′ ) and N k h (s, a) = s ′ ∈S N k h (s, a, s ′ ) for any (s, a, h, s ′ ) ∈ S × A × 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) .Step II: Optimistic Robust Planning (Line 6 to 11). Given P k (•|•, •) that estimates the training environment, we perform an optimistic robust planning to construct the policy π k to 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 it maintains an upper bound and a 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 is to 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 (Assumption 4.1), we take a closer look into the robust Bellman equation. By strong duality (Proposition 2.5), the robust expectation E Pρ(s,a;P ) [V ] for any V ∈ [0, H] satisfying min s∈S V (s) = 0 is equivalent toE Pρ(s,a;P ) V = sup η∈[0,H] -E P (•|s,a) η -V + + 1 - ρ 2 • η . (4.1)Consequently, with a slight abuse of the notation, in the remaining of the paper, we re-define the operator E Pρ(s,a;P ) [V ] as the right hand side of (4.1). 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 V k H+1 = V k H+1 = 0, we recursively define that for any (s, a) ∈ S × A,EQUATIONwhere the robust expectation E Pρ(s,a; P k h ) follows the definition in the right hand side of (4.1), and the bonus function bonus k h (s, a) ≥ 0 is defined later. Here we truncate the optimistic estimate Q k h via the upper bound min{H, ρ -1 } of the true optimal robust value function Q ⋆ h,P ⋆ ,Φ . This truncation arises from the combined implication of Proposition 2.6 and the fact that min (s,a)∈S×A Q ⋆ h,P ⋆ ,Φ (s, a) = 0 under Assumption 4.1. As we establish in Lemma E.2, Q k h and Q k h form upper and lower bounds for Q ⋆ h,P ⋆ ,Φ and Q π k h,P ⋆ ,Φ under a proper choice of the bonus. After performing (4.2) and (4.3), we choose the data collection policy π k h to be the optimal policy with respect to the optimistic estimator Q k h and define V k h and V k h accordingly byπ k h (•|•) = argmax a∈A Q k h (•, a), V k h (s) = E π k h (•|s) Q k h (s, •) , V k h (s) = E π k h (•|s) Q k h (s, •) . (4.4)We remark that the purpose of maintaining the lower bound estimate (4.3) is to facilitate the construction of the bonus and to help sharpen our theoretical analysis. The construction of the policy π k is still based on 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 a balance between exploration and exploitation while managing distributional robustness.▷ Bonus function. The bonus function bonus k h (s, a) is a Bernstein-style bound defined asV P k h (•|s,a) V k h+1 + V k h+1 /2 c 1 ι N k h (s, a) ∨ 1 + 2E P k h (•|s,a) V k h+1 -V k h+1 H + c 2 H 2 Sι N k h (s, a) ∨ 1 + 1 √ K ,(4.5)where ι = log(S 3 AH 2 K 3/2 /δ), c 1 , c 2 > 0 are absolute constants, and δ signifies a pre-selected fail probability. Under (4.5), Q k h and Q k h 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.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 ×A-rectangular total-variation robust set of radius ρ ∈ [0, 1) (Assumption 2.1 and Definition 2.4) satisfying Assumptions 4.1, choosing the bonus function as (4.5) with sufficiently large c 1 , c 2 > 0, then with probability at least 1 -δ, Algorithm 1 satisfiesRegret Φ (K) ≤ O min H, ρ -1 H 2 SAKι ′ ,where ι ′ = log 2 (SAHK/δ) and O(•) hides absolute constants and lower order terms in K.Theorem 4.3 shows that Algorithm 1 enjoys a sublinear online regret of O( √ 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 a 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 1 -δ, Algorithm 1 can output an ε-optimal policy withinO min H, ρ -1 H 2 SAι ′′ /ε 2 (4.6)episodes, where ι ′′ = log(SAH/εδ) and O(•) hides absolute constants. The valid range of ε satisfies ε ∈ (0, c • min{1, 1/(ρH)}] for some constant c > 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 O(H 3 SA/ε 2 ), matching the minimax sample complexity lower bound for online RL in non-robust MDPs (Azar et 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 1 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 a TV robust set and a generative model showcases a minimax optimal sample complexity ofO min H γ , ρ -1 H 2 γ SA/ε 2 , for ρ ∈ [0, 1), where we H γ := 1/(1-γ) is the effective horizon of the infinite γ-discounted RMDPs. As a result, the sample complexity (4.6) of Algorithm 1 matches their result. We highlight that our algorithm does not rely on a generative model and operates purely through interactive data collection.Extensions of Algorithm 1 and its theory. In Appendix B.4.2, we extend Algorithm 1 to solve a new 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 × A-rectangular RMDP with a TV robust set and vanishing minimal value assumption in an appropriate sense (Proposition 4.2) Consequently, by a clever usage of Algorithm 1, we can also solve this new model sample-efficiently, as is shown in Corollary B.5. Such a result echoes our intuition on the curse of support shift. 
conclusions and future works: 
 This work shows that in the absence of any structural assumptions, robust RL via interactive data collection necessarily induces a linear regret lower bound in the worst case due to the curse of support shift. Under the vanishing minimal value assumption, an assumption that is able to effectively rule out the potential support shift issues for RMDPs with a TV robust set, we propose a sample-efficient 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. OUYANG, L., WU, J., JIANG, X., ALMEIDA, D., WAINWRIGHT, C., MISHKIN Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material?Answer: [NA] Justification: This is a 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/ public/guides/CodeSubmissionPolicy) for more details. • While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e. Guidelines:• The answer NA means that the paper does not involve crowdsourcing nor research with human subjects. • Including this information in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then as much detail as possible should be included in the main paper. • We recognize that the procedures for this may vary significantly between institutions and locations, and we 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 as the institution conducting the review. 
 
 Appendix: 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) (Iyengar, 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 a given RMDP, i.e., planning (Iyengar, 2005; El 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) 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 exploration-exploitation 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 Zhang et al., , 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 ε-optimal policy within O(H 3 SA/ε 2 ) 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-optimality for non-robust 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., 2021a; 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., 2021; Liu et al., 2022; Zhong et al., 2022; Liu et al., 2023; Huang et al., 2023a; Xu and Zeevi, 2023; Agarwal et 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 in 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 of robust RL is difficult because each addresses unique aspects of resilience.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.About a generative model and a simulator. A generative model here means a mechanism that when queried at some state, action, and time step, returns a sample of next state. Here we distinguish this notion with the notion of simulator or simulated environment which generally refers to a humanmade training environment that mimics the real-world environment. With a generative model on hand, interactive data collection is no longer needed, but in a 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 sampleefficient 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 on 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 a 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 an existing work (Dong et al., 2022) also studies the problem of robust RL with interactive data collection. They study S × 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 O( √ K)-online 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 ρ. We do not signify the situation when ρ = 1 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.Robust Bellman equations. We remark that the original version of the robust Bellman equation (Iyengar, 2005) is for infinite horizon RMDPs and a customized proof of robust Bellman equation for finite horizon RMDPs (Proposition 2.2) can be found in Appendix A.1 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 a duality representation that only uses the expectation under the nominal transition kernel. Previous works, e.g., Yang et al. (2022) , have proved such a result when the TV distance is defined through f -divergence. Here we extend such a result to the TV distance defined directly though (2.2) that allows a difference support between p and q.Remark B.1. Despite all previous works on RMDPs with TV robust sets relying on the definition of TV distance D TV (p(•)∥q(•)) 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 a tighter form of bound of the gap between the maximum and minimum as1 ρ • 1 -(1 -ρ) H .But in the sequel, we mainly use the form of min{H, ρ -1 } for its brevity and the fact of (1-(1 - ρ) H )/ρ = Θ(min{H, ρ -1 }) in the sense that c • min H, ρ -1 ≤ (1 -(1 -ρ) H )/ρ ≤ min H, ρ -1for any H ≥ H 0 ∈ N + and ρ ∈ [0, 1] with some constant c > 0 that is independent of (H, ρ).In contrast with a crude bound of H, such a 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.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 or pre-collected offline data required to achieve ε-optimality. In contrast, here the sample complexity is measuring the least number of interactions with the training environment needed to learn π ⋆ , where no generative or offline sample is available. Such a learning protocol casts unique challenges on the algorithmic design and theoretical analysis to get the optimal sample complexity. There is a broader understanding of the curse of 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 a "high probability of disjointness" is enough to maintain the integrity of the hardness result. For instance, we can modify the state s good in Example 3.1 so that it is no longer an absorbing state. Rather, s good could transit to s bad with a small probability, such as 2 -H . This modification expands the support of the training environment to encompass the entire state space. Nevertheless, acquiring information about s bad necessitates exponential samples, thereby preserving the hardness result. Examples of Assumption 4.1. In the sequel, we provide a concrete condition that makes Assumption 4.1 hold, which imposes that the state space of the RMDP has a "closed" subset of "fail-states" with zero rewards., R ′ , Φ ′ ) with R ′ h (s, a) = (ρ ′ ) h-1 R h (s,There exists a subset S f ⊂ S of fail states such thatR h (s, a) = 0, P ⋆ h (S f |s, a) = 1, ∀(s, a, h) ∈ S f × A × [H].This type of "fail-states" condition is first proposed by Panaganti et al. ( 2022) (with |S f | = 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) is given below.We first observe that Condition B.2 implies that min s∈S V π h,P ⋆ ,Φ (s) = 0 for any policy π and step h ∈ [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, one can consider an RMDP characterized by the state space S = {s 1 , s 2 }, action space A = {a 1 }, time horizon H = 2, reward function R h (s, a) = 1{s = s 2 }, and transition probabilities defined as follows:P ⋆ 1 (s 1 |s 1 , a 1 ) = 1 -ρ, P ⋆ 1 (s 2 |s 1 , a 1 ) = ρ, P ⋆ 1 (s 1 |s 2 , a 1 ) = 0, P ⋆ 1 (s 2 |s 2 , a 1 ) = 1, 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 V ⋆ 1,P ⋆ ,Φ (s 1 ) = 0. Remark B.4 (Reduction to non-robust MDP without loss of generality). It is noteworthy that assuming the vanishing minimal value (Assumption 4.1) or the presence of fail-states (Condition B.2) in the non-robust case (ρ = 0) is without loss of generality. This is achievable by expanding the prior state space S of MDP to include an additional state s f , denoted as the fail-state. More importantly, this augmentation 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 fail-states (Condition B.2). This indicates that our algorithm and theoretical analysis in the sequel can be directly reduced to non-robust MDPs without additional assumptions.In this section, we show that our algorithm design (Algorithm 1) can also be applied to S × Arectangular 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 a sublinear regret upper bound for this model, which means that this type of RMDPs can also be solved sample-efficiently by a clever usage of Algorithm 1. This coincides with our intuition on support shift in Section 4.1.S × A-rectangular discounted RMDPs with robust set (B.1). We first formally define the model we consider. We define a finite-horizon discounted RMDP as a finite-horizon RMDP M γ = (S, A, H, P ⋆ , R γ , Φ ′ ), where the robust set Φ ′ is given by (B.1), i.e.,Φ ′ (P ) = (s,a)∈S×A P (•) ∈ ∆(S) : sup s ′ ∈S P (s ′ ) P ⋆ h (s ′ |s, a) ≤ 1 ρ ′ := (s,a)∈S×A B ρ ′ (s, a; P ⋆ ). (B.2)This robust set contains transition probabilities that share the same support as the nominal transition kernel. The reward functionR γ = {γ h-1 • R h } H h=1, where γ ∈ (0, 1) is the discount factor and R h ∈ [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 set (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, Φ) which include an additional "fail-state" s f . More specifically, the state space S = S ∪ {s f }. The transition kernel P ⋆ is defined as, for any step h ∈ [H],P ⋆ h (•|s, a) = P ⋆ h (•|s, a), ∀(s, a) ∈ S × A and P ⋆ h (•|s f , a) = δ s f (•), ∀a ∈ A. (B.3) The reward function R is defined as, for any step h ∈ [H], R h (s, a) = γ ρ ′ h-1 • R h (s, a), ∀(s, a) ∈ S × A and R h (s f , a) = 0, ∀a ∈ A.We suppose that the discount factor γ ≤ ρ ′ so that the reward function R h ∈ [0, 1]. The robust mapping Φ is defined as, for any P : S × A → ∆( S),Φ( P ) = (s,a)∈ S×A P (•) ∈ ∆( S) : D TV P (•) P (•|s, a) ≤ ρ := (s,a)∈ S×A P ρ (s, a; P ), ρ = 2 -2ρ ′ .Therefore, M is an RMDP with S × A-rectangular TV robust set of radius ρ and satisfying Assumption 4.1 (because it satisfies the "fail-state" Condition B.2). Furthermore, for any initial state s 1 ∈ S \ {s f } = S, the interaction with the transition kernel P ⋆ is equivalent to the interaction with the transition kernel P ⋆ of the original RMDP M γ , since by the definition (B.3), starting from any s ̸ = s f the agent would follow the same dynamics as P ⋆ . What's more, for any policy π h : S → ∆(A) for M, it naturally induces the unique policy π S,h : S → ∆(A) for the original RMDP M γ .Therefore, we can run Algorithm 1 on the auxiliary RMDP M, starting from the initial state s 1 ∈ S \ {s f }, which only needs the interaction with P ⋆ . Suppose the output policy by the algorithm is { π k } K k=1 , then the following corollary shows the induced policy { π k S } K k=1 for the original RMDP M γ enjoys a sublinear regret. There exists an algorithm ALG (specified by the above discussion) such that its online regret for this RMDP is bounded byRegret ALG Φ ′ (K) ≤ O min H, (2 -2ρ ′ ) -1 H 2 SAKι ′ ,where ι ′ = log 2 (SAHK/δ) and O(•) 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 × A-rectangular RMDPs with TV robust set and vanishing minimal value assumption, the S × 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 4.1. Furthermore, the regret decays as ρ ′ decays in which case the transition probability ratio bound becomes higher, i.e., the robust set becomes larger.Remark B.6. The upper bound in Corollary B.5 does not depend on the discount factor γ since Algorithm 1 adopts a coarse bound of R h ≤ 1. The upper bound can be directly improved to be γ-dependent using a tighter truncation in step (4.2) of Algorithm 1.In this work, we show that in 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 a TV robust set, we propose a sample-efficient 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 S × A-rectangular TV-robust-set RMDPs with linear or even general function approximation (Blanchet et al., 2023) . Nonetheless, achieving the nearly optimal rate under general function approximation remains elusive. 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],infQ(•):DTV(Q(•)∥Q ⋆ (•))≤σ E Q(•) [f ] = sup η∈[0,H] -E Q ⋆ (•) (η -f ) + - σ 2 • η -min s∈S f (s) + + η ,where σ ∈ [0, 1] and the TV distanceD TV (Q(•)∥Q ⋆ (•)) is defined as D TV (Q(•)∥Q ⋆ (•)) = 1 2 s∈S |Q(s) -Q ⋆ (s)|.Proof of Lemma C.1. First, we note that when Q ⋆ (s) > 0 for any s ∈ S, i.e., anyQ(•) ∈ ∆(S) is absolute continuous w.r.t. Q ⋆ (•), it has been proved by Yang et al. (2022) that inf Q(•):DTV(Q(•)∥Q ⋆ (•))≤σ E Q(•) [f ] = sup η∈R -E Q ⋆ (•) (η -f ) + - σ 2 • η -min s∈S f (s) + + η .Furthermore, as is shown in Lemma H.8 in Blanchet et al. ( 2023), the optimal dual variable η ⋆ lies in[0, H] when f ∈ [0, H]. Therefore, for Q ⋆ (•) such that Q ⋆ (s) > 0 for any s ∈ S, we have inf Q(•):DTV(Q(•)∥Q ⋆ (•))≤σ E Q(•) [f ] = sup η∈[0,H] -E Q ⋆ (•) (η -f ) + - σ 2 • η -min s∈S f (s) + + η .Now for any Q ⋆ (•) ∈ ∆(S), we can prove the same result by averaging Q ⋆ (•) with a uniform distribution and taking the limit. More specifically, denote U (•) ∈ ∆(S) as the uniform distribution on S, i.e., U (s) = 1/|S| for any s ∈ S. Consider the following distributionally robust optimization problem, for any ϵ ∈ [0, 1],P(ϵ) := inf Q(•):DTV Q(•)∥(1-ϵ)Q ⋆ (•)+ϵ•U (•) ≤σ E Q(•) [f ].By our previous discussions, since (1 -ϵ)Q ⋆ (s) + ϵ • U (s) > 0 for any s ∈ S and ϵ > 0, we have thatP(ϵ) = D(ϵ), ∀ϵ ∈ (0, 1], (C.1)where the function D(•) : [0, 1] → R + is defined asD(ϵ) := sup η∈[0,H] -(1 -ϵ) • E Q ⋆ (•) (η -f ) + -ϵ • E U (•) (η -f ) + - σ 2 • η -min s∈S f (s) + + η .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 ϵ→0+ D(ϵ) exists and lim ϵ→0+ D(ϵ) = D(0); and (ii) lim ϵ→0+ P(ϵ) = P(0). To prove (i), consider that for any ϵ > 0, by the definition of D(•),|D(0) -D(ϵ)| ≤ sup η∈[0,H] ϵ • E Q ⋆ (•) (η -f ) + + ϵ • E U (•) (η -f ) + ≤ ϵ • 2H.Since the right hand side tends to 0 as ϵ tends to 0, we know that lim ϵ→0+ D(ϵ) exists, lim ϵ→0+ D(ϵ) = D(0). This also indicates that lim ϵ→0+ P(ϵ) exists due to (C.1). This proves (i). Now we prove (ii). Notice that since the setQ(•) ∈ ∆(S) : D TV Q(•)∥(1 -ϵ)Q ⋆ (•) + ϵ • U (•) ≤ σ is a closed subset of R |S| , and E Q(•) [f ] is a continuous function of Q(•) ∈ R |S| w.r.t. the ∥ • ∥ 2 -norm,we can denote the optimal solution to the optimization problem involved in P(ϵ) asQ † ϵ (•) = arginf Q(•):DTV Q(•)∥(1-ϵ)Q ⋆ (•)+ϵ•U (•) ≤σ E Q(•) [f ],which also gives thatP(ϵ) = E Q † ϵ (•) [f ] = s∈S Q † ϵ (s)f (s).With these preparations, we are able to prove (ii). On the one hand, consider for any ϵ ∈ (0, 1],D TV (1 -ϵ) • Q † 0 (•) + ϵ • U (•) (1 -ϵ) • Q ⋆ (•) + ϵ • U (•) ≤ (1 -ϵ) • σ ≤ σ.Therefore, for any ϵ ∈ (0, 1], it holds thatP(ϵ) = inf Q(•):DTV Q(•)∥(1-ϵ)Q ⋆ (•)+ϵ•U (•) ≤σ E Q(•) [f ] ≤ E (1-ϵ)•Q † 0 (•)+ϵ•U (•) [f ] = (1 -ϵ) • E Q † 0 [f ] + ϵ • E U (•) [f ],which implies thatlim ϵ→0+ P(ϵ) ≤ E Q † 0 [f ] = P(0). (C.2)On the other hand, for any ϵ ∈ (0, 1],σ ≥ 1 2 s∈S Q † ϵ (s) -(1 -ϵ) • Q ⋆ (s) -ϵ • U (s) ≥ (1 -ϵ) • D TV (Q † ϵ (•)∥Q ⋆ (•)) -ϵ • D TV (Q † ϵ (•)∥U (•)), and by using D TV (Q † ϵ (•)∥U (•)) ≤ 1, we obtain that D TV (Q † ϵ (•)∥Q ⋆ (•)) ≤ σ + ϵ 1 -ϵ . (C.3) Consider a sequence of {ϵ i } ∞ i=1 converging to 0, i.e., lim i→0+ ϵ i = 0. Since {Q † ϵi (•)} ∞ i=1 is a sequence contained in a compact subset of R |S| , it has a converging (w.r.t. ∥ • ∥ 2 ) subsequence denoted by {Q † ϵi k (•)} ∞ k=1 whose limit is denoted as Q † (•) ∈ ∆(S). By (C.3), we know thatD TV (Q † ϵi k (•)∥Q ⋆ (•)) ≤ σ + ϵ i k 1 -ϵ i k . (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 thatD TV (Q † (•)∥Q ⋆ (•)) ≤ σ. (C.5)Now we can arrive at the following,lim ϵ→0+ P(ϵ) = lim ϵ→0+ E Q † ϵ (•) [f ] = lim k→0+ E Q † ϵ i k (•) [f ] = E Q † (•) [f ] ≥ inf Q(•):DTV(Q(•)∥Q ⋆ (•))≤σ E Q(•) [f ] = P(0), (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 {ϵ i k } ∞ k=1 that converges to 0, the third equality is due to the continuity ofE Q(•) [f ] of Q(•) (w.r.t. ∥ • ∥ 2 ), and the inequality follows from (C.5). Finally, with (C.2) and (C.6), we conclude that lim ϵ→0+ P(ϵ) = P(0), which proves (ii). Consequently, by (i) and (ii)P(0) = lim ϵ→0+ P(ϵ) = lim ϵ→0+ D(ϵ) = D(0).Recalling the definitions of P(•) and D(•), we conclude the proof of Lemma C.1.Proof of Proposition 2.6. Here we prove a stronger result that for any policy π and step h ∈[H] max (s,a)∈S×A Q π h,P,Φ (s, a) -min (s,a)∈S×A Q π h,P,Φ (s, a) ≤ 1 ρ • 1 -(1 -ρ) H-h+1 , (C.7) max s∈S V π h,P,Φ (s) -min s∈S V π h,P,Φ (s) ≤ 1 ρ • 1 -(1 -ρ) H-h+1 . (C.8)First, we note that for the last step h = H, (C.7) and (C.8) naturally hold since R H ∈ [0, 1]. Now suppose that (C.8) hold for some step h + 1. By robust Bellman equation (Proposition 2.2), we have thatQ π h,P ⋆ ,Φ (s, a) = R h (s, a) + E Pρ(s,a;P ⋆ h ) V π h+1,P ⋆ ,Φ ≤ 1 + E Pρ(s,a;P ⋆ h ) V π h+1,P ⋆ ,Φ , ∀(s, a) ∈ S × A, (C.9)where the inequality uses the fact that R h ≤ 1. Now we denote the state with the least robust value ass 0 ∈ argmin s∈S V π h+1,P ⋆ ,Φ (s). (C.10)Inspired by Shi et al. ( 2023), we choose a transition kernel P h satisfying thatP h (•|s, a) 1 = 1 -ρ, P ⋆ h (s ′ |s, a) ≥ P h (s ′ |s, a) ≥ 0, ∀(s, a, s ′ ) ∈ S × A × S,which implies thatD TV P h (•|s, a) + ρ • δ s0 (•) P ⋆ h (•|s, a) ≤ ρ, ∀(s, a) ∈ S × A.Here δ s0 (•) is the point measure centered at s 0 defined in (C.10). Combined with (C.9), we have thatQ π h,P ⋆ ,Φ (s, a) ≤ 1 + E P h (•|s,a)+ρ•δs 0 (•) V π h+1,P ⋆ ,Φ = 1 + E P h (•|s,a) V π h+1,P ⋆ ,Φ + ρ • V π h+1,P ⋆ ,Φ (s 0 ) ≤ 1 + (1 -ρ) • max s∈S V π h+1,P ⋆ ,Φ (s) + ρ • min s∈S V π h+1,P ⋆ ,Φ (s). (C.11)Consequently from (C.11), we further obtain that for any (s, a) ∈ S × A,Q π h,P ⋆ ,Φ (s, a) -min (s,a)∈S×A Q π h,P ⋆ ,Φ (s, a) ≤ 1 + (1 -ρ) • max s∈S V π h+1,P ⋆ ,Φ (s) + ρ • min s∈S V π h+1,P ⋆ ,Φ (s) -min (s,a)∈S×A Q π h,P ⋆ ,Φ (s, a) = 1 + (1 -ρ) • max s∈S V π h+1,P ⋆ ,Φ (s) -min s∈S V π h+1,P ⋆ ,Φ (s) + min s∈S V π h+1,P ⋆ ,Φ (s) -min (s,a)∈S×A Q π h,P ⋆ ,Φ (s, a) ≤ 1 + (1 -ρ) • max s∈S V π h+1,P ⋆ ,Φ (s) -min s∈S V π h+1,P ⋆ ,Φ (s) , (C.12)where the first inequality uses (C.11) and the last inequality uses the following fact,min (s,a)∈S×A Q π h,P ⋆ ,Φ (s, a) = min (s,a)∈S×A R h (s, a) + E Pρ(s,a;P ⋆ h ) V π h+1,P ⋆ ,Φ ≥ min s∈S V π h+1,P ⋆ ,Φ (s).Now applying the assumption that (C.8) holds at step h + 1 to the right hand side of (C.12), we obtain that max (s,a)∈S×AQ π h,P ⋆ ,Φ (s, a) -min (s,a)∈S×A Q π h,P ⋆ ,Φ (s, a) ≤ 1 + 1 -ρ ρ • 1 -(1 -ρ) H-h = 1 ρ • 1 -(1 -ρ) H-h+1 .Thus given (C.8) at step h + 1, we can derive (C.7) at step h. Now by noticing that min (s,a)∈S×AQ π h,P ⋆ ,Φ (s, a) ≤ min s∈S V π h,P ⋆ ,Φ (s) ≤ max s∈S V π h,P ⋆ ,Φ (s) ≤ max (s,a)∈S×A Q π h,P ⋆ ,Φ (s, a),we can conclude that (C.8) also holds at step h. As a result, by an induction argument, we finish the proof of Proposition 2.6.Proof of Proposition 4.2. We consider some fixed (s, a, h) ∈ S × A × [H] throughout proof. By Lemma C.1, we have thatE Pρ(s,a;P ⋆ h ) [V ] = sup η∈R -E P ⋆ h (•|s,a) (η -V ) + - ρ 2 • η -min s∈S V (s) + + η = sup η∈[0,H] -E P ⋆ h (•|s,a) (η -V ) + - ρ 2 • η -min s∈S V (s) + + η = sup η∈[0,H] -E P ⋆ h (•|s,a) (η -V ) + + 1 - ρ 2 • η , (C.13)where the second equality follows from the fact the optimal dual variable η ⋆ is in [0, H] when V ∈ [0, H] (see e.g., Lemma H.8 in Blanchet et al. ( 2023)), and the last equality is obtained by the fact that min s∈S V (s) = 0.Part (i). For any η ∈ [0, H] and Q ∈ B ρ ′ (s, a; P ⋆ h ), we have that-E P ⋆ h (•|s,a) (η -V ) + + 1 - ρ 2 • η ≤ 1 - ρ 2 • -E Q(•) (η -V ) + + η ≤ 1 - ρ 2 • -E Q(•) η -V + η = 1 - ρ 2 • E Q(•) V , (C.14)where the first inequality uses the definition of B ρ ′ (s, a; P ⋆ h ), the second equality follows from the fact that (x) + ≥ x. Furthermore, by (C.14) we have thatsup η∈[0,H] -E P ⋆ h (•|s,a) (η -V ) + + 1 - ρ 2 • η ≤ 1 - ρ 2 • inf Q∈B ρ ′ (s,a;P ⋆ h ) E Q(•) V . (C.15)Combining (C.13) and (C.15), we have thatE Pρ(s,a;P ⋆ h ) V ≤ ρ ′ • E B ρ ′ (s,a;P ⋆ h ) V .Part (ii). Since ρ ∈ [0, 1], we know that there exists a η ∈ [0, H] such thats ′ :V (s ′ )< η P ⋆ h (s ′ |s, a) ≤ 1 - ρ 2 ≤ s ′ :V (s ′ )≤ η P ⋆ h (s ′ |s, a),which further implies that we have the following interpolation for some λ ∈ [0, 1]:1 - ρ 2 = λ s ′ :V (s ′ )< η P ⋆ h (s ′ |s, a) + (1 -λ) s ′ :V (s ′ )≤ η P ⋆ h (s ′ |s, a).We define a probability measure P ⋆ ∈ ∆(S) asP ⋆ h = λP ⋆ h (s ′ |s, a) • 1{V (s ′ ) > η} + (1 -λ)P ⋆ h (s ′ |s, a) • 1{V (s ′ ) ≥ η} 1 -ρ 2 .(C.16)It is not difficult to verify that P ⋆ h ∈ B ρ ′ (s, a; P ⋆ h ). Hence, we have1 - ρ 2 • E B ρ ′ (s,a;P ⋆ h ) [V ] ≤ 1 - ρ 2 • E P ⋆ h (•) V = 1 - ρ 2 • E P ⋆ h (•) V -η + 1 - ρ 2 • η = -E P ⋆ h (•|s,a) ( η -V ) + + 1 - ρ 2 • η, (C.17)where the last inequality uses the definition of P ⋆ h in (C.16). Furthermore, by (C.17) we have thatρ ′ • E B ρ ′ (s,a;P ⋆ h ) V ≤ sup η∈[0,H] -E P ⋆ h (•|s,a) (η -V ) + + 1 - ρ 2 • η (C.18)= E Pρ(s,a;P ⋆ h ) V , where the equality follows from (C.13).Combining Part (i) and Part (ii). Finally, combining (C.15) and (C.18), we prove Proposition 4.2.Proof of Theorem 3.2. We first explicitly give the expressions of the robust value functions in Example 3.1, based on which we derive the desired online regret lower bound.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 ⋆,M θ ,Φ and Q π h,P ⋆,M θ ,Φ . 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 a ∈ A,Q π 3,P ⋆,M θ ,Φ (s good , a) = V π 3,P ⋆,M θ ,Φ (s good ) = 1, (D.1) Q π 3,P ⋆,M θ ,Φ (s bad , a) = V π 3,P ⋆,M θ ,Φ (s bad ) = 0.For step h = 2, by the robust Bellman equation (Proposition 2.2), we have that for the good state s good ,Q π 2,P ⋆,M θ ,Φ (s good , a) (D.2) = 1 + inf P ∈Pρ(s good ,a;P ⋆,M θ 2 ) E P (•) V π 3,P ⋆,M θ ,Φ = 1 + (1 -ρ), ∀a ∈ A,where the last equality is because V π 3,P ⋆,M θ ,Φ takes the minimal value 0 at the bad state s bad and thus the most adversarial transition distribution is achieved atP † (s ′ ) = (1 -ρ) • 1{s ′ = s good } + ρ • 1{s ′ = s bad }.Similarly, we have that for the bad state s bad ,Q π 2,P ⋆,M θ ,Φ (s bad , a) = 0 + inf P ∈Pρ(s bad ,a;P ⋆,M θ 2 ) E P (•) V π 3,P ⋆,M θ ,Φ (D.3) = p -ρ, a = θ q -ρ, a = 1 -θ .Finally by the robust Bellman equation again, we have thatV π 2,P ⋆,M θ ,Φ (s good ) = 1 + (1 -ρ), V π 2,P ⋆,M θ ,Φ (s bad ) = π 2 (θ|s bad ) • (p -ρ) + π 2 (1 -θ|s bad ) • (q -ρ).Notice that by q < p we know that V π 2,P ⋆,M θ ,Φ (s bad ) < p -ρ < 1 + (1 -ρ) < V π 2,P ⋆,M θ ,Φ (s good ). For step h = 1, we consider the robust values on the initial state s 1 = s good , by robust Bellman equation,Q π 1,P ⋆,M θ ,Φ (s good , a) = 1 + inf P ∈Pρ(s good ,a;P ⋆,M θ 1 ) E P (•) V π 2,P ⋆,M θ ,Φ (D.4) = 1 + (1 -ρ) • 1 + (1 -ρ) + ρ • π 2 (θ|s bad ) • (p -ρ) + π 2 (1 -θ|s bad ) • (q -ρ) , ∀a ∈ A.By robust Bellman equation, we also derive V π 1,P ⋆,M θ ,Φ (s good ) = Q π 1,P ⋆,M θ ,Φ (s good , a) for ∀a ∈ A.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,V π ⋆ 1,P ⋆ ,Φ (s) -V π 1,P ⋆ ,Φ (s) ≥ E (P π ⋆ , † ,π ⋆ ) H h=1 a∈A π ⋆ h (a|s h ) -π h (a|s h ) • Q π h,P ⋆ ,Φ (s h , a) s 1 = s ,where the expectation is taken with respect to the trajectories induced by policy π ⋆ , transition kernel P π ⋆ , † . Here the transition kernel P π ⋆ , † is defined as Finally, let's consider step h = 2. By (D.2), we have that for the good state, it holds thatP π ⋆ , † h (•|s, a) = arginf P ∈P(s,a;P ⋆ h ) E P (•) V π ⋆ h+1,P ⋆ ,a∈A π ⋆,M θ 2 (a|s good ) -π 2 (a|s good ) • Q π 2,P ⋆,M θ ,Φ (s good , a) = 0, (D.7)Meanwhile, by (D.3), we have that for the bad state, it holds that (recall that q < p)a∈A π ⋆,M θ 2 (a|s bad ) -π 2 (a|s bad ) • Q π 2,P ⋆,M θ ,Φ (s bad , a) = max p -ρ, q -ρ -π 2 (θ|s bad ) • (p -ρ) + π 2 (1 -θ|s bad ) • (q -ρ) = p -ρ -π 2 (θ|s bad ) • (p -ρ) + π 2 (1 -θ|s bad ) • (q -ρ) = p -q 2 • π ⋆,M θ 2 (θ|s bad ) -π 2 (θ|s bad ) + π ⋆,M θ 2 (1 -θ|s bad ) -π 2 (1 -θ|s bad ) = (p -q) • D TV π ⋆,M θ 2 (•|s bad ) π 2 (•|s bad ) , (D.8)where according to (D.3) the optimal policy of M θ at h = 2 and s bad is π ⋆,M θ 2 (θ|s bad ) = 1. Now combining (D.5), (D.6), (D.7), and (D.8) with Lemma D.1, we can conclude thatV π ⋆,M θ 1,P ⋆,M θ ,Φ (s good ) -V π 1,P ⋆,M θ ,Φ (s good ) ≥ E a1∼π ⋆,M θ 1 (•|s good ),s2∼P π ⋆,M θ , † 1 (•|s good ,a1) a∈A π ⋆ 2 (a|s 2 ) -π 2 (a|s 2 ) • Q π 2,P ⋆,M θ ,Φ (s 2 , a) = P π ⋆,M θ , † 1 (s bad |s good , 0) • (p -q) • D TV π ⋆,M θ 2 (•|s bad ) π 2 (•|s bad ) , (D.9)where the adversarial transition kernel P π ⋆,M θ , † 1 is given byP π ⋆,M θ , † 1 (•|s good , 0) = argmin P ∈P(s good ,0;P ⋆,M θ 1 ) E P (•) V π ⋆,M θ 2,P ⋆,M θ ,Φ = (1 -ρ) • 1{• = s good } + ρ • 1{• = s bad }. (D.10)Consequently, taking (D.10) back into (D.9), we have thatV π ⋆,M θ 1,P ⋆,M θ ,Φ (s good ) -V π 1,P ⋆,M θ ,Φ (s good ) ≥ ρ • (p -q) • D TV π ⋆,M θ 2 (•|s bad ) π 2 (•|s bad ) .This implies that for any algorithm executing π 1 , • • • , π K , its online regret is lower bounded by the following,Regret M θ ,ALG Φ (K) = K k=1 V π ⋆,M θ 1,P ⋆,M θ ,Φ (s good ) -V π k 1,P ⋆,M θ ,Φ (s good ) ≥ ρ • (p -q) • K k=1 D TV π ⋆,M θ 2 (•|s bad ) π k 2 (•|s bad ) .However, since in RMDPs of Example 3.1, the online interaction process is always kept in s good and there is no information on θ which can only be accessed at (s, h) = (s bad , 2). As a result, the estimates π k 2 (•|s bad ) of π ⋆,M θ 2 (•|s bad ) = 1{• = θ} can do no better than a random guess. Put it formally, consider thatsup θ∈{0,1} E M θ ,ALG Regret M θ ,ALG Φ (K) ≥ ρ • (p -q) • sup θ∈{0,1} E M θ ,ALG K k=1 D TV π ⋆,M θ 2 (•|s bad ) π k 2 (•|s bad ) = ρ • (p -q) • sup θ∈{0,1} K k=1 E ALG π k 2 (1 -θ|s bad ) . (D.11)Here in the last equality we can drop the subscription of M θ because the algorithm outputs π k 2 independent of the θ due to our previous discussion. Notice thatθ∈{0,1} K k=1 E ALG π k 2 (1 -θ|s bad ) = K k=1 θ∈{0,1} E ALG π k 2 (1 -θ|s bad ) = K k=1 1 = K, which further indicates that sup θ∈{0,1} K k=1 E ALG π k 2 (1 -θ|s bad ) ≥ K 2 . (D.12)Therefore, by combining (D.11) and (D.12), we conclude thatinf ALG sup θ∈{0,1} E M θ ,ALG Regret M θ ,ALG Φ (K) ≥ (p -q) • ρK 2 .This is the desired online regret lower bound of Ω(ρ • K) for the RMDPs presented in Example 3.1. Furthermore, we can construct two RMDPs { M 0 , M 1 } with horizon 3H by concatenating H RMDPs {M 0 , M 1 } presented in Example 3.1. Notably, at any steps {3i + 1} H-1 i=0 , we define R 3i+1 (s bad , a) = 1, P ⋆, M θ 3i+1 (s good |s bad , a) = 1, ∀(a, θ) ∈ A × {0, 1}. Then we haveinf ALG sup θ∈{0,1} E M θ ,ALG Regret M θ ,ALG Φ (K) ≥ H • Ω(ρ • K) = Ω(ρ • HK),which completes the proof of Theorem 3.2.Thus by recursively applying (D.14) over h ∈ [H], we can conclude thatV π ⋆ 1,P ⋆ ,Φ (s) -V π 1,P ⋆ ,Φ (s) ≥ E (P π ⋆ , † ,π ⋆ ) H h=1 a∈A π ⋆ h (a|s h ) -π h (a|s h ) • Q π h,P ⋆ ,Φ (s h , a) s 1 = s ,which completes the proof of Lemma D.1.In this section, we prove our main theoretical results (Theorem 4.3). In Appendix E.1, we outline the proof of the theorem. In Appendix E.2, we list all the key lemmas used in the proof of the theorem.We defer the proof of all the lemmas to subsequent sections (Appendices E.3 to E.8).Before presenting all the proofs, we define the typical event E asE =    E P ⋆ h (•|s,a) -E P k h (•|s,a) η -V ⋆ h+1,P ⋆ ,Φ + ≤ V P k h (•|s,a) η -V ⋆ h+1,P ⋆ ,Φ + • c 1 ι N k h (s, a) ∨ 1 + c 2 Hι N k h (s, a) ∨ 1 , P ⋆ h (s ′ |s, a) -P h (s ′ |s, a) ≤ min P ⋆ h (s ′ |s, a), P k h (s ′ |s, a) • c 1 ι N k h (s, a) ∨ 1 + c 2 ι N k h (s, a) ∨ 1 , ∀(s, a, s ′ , h, k) ∈ S × A × S × [H] × [K], ∀η ∈ N 1/(S √ K) [0, H]    , where ι = log(S 3 AH 2 K 3/2 /δ), c 1 , c 2 > 0 are two absolute constants, N 1/S √ K ([0, H]) denotes an 1/S √ K-cover of the interval [0, H].Lemma E.1 (Typical event). For the typical event E defined in (E.35), it holds that P(E) ≥ 1 -δ.Proof of Lemma E.1. This is 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, η) ∈ S × A × S × [H] × [K] × N 1/(S √ K) ([0, H]). Note that the size of N 1/(S √ K) ([0, H]) is of order SH √ K.In this section, we always let the event E hold, which by Lemma E.1 is of probability at least 1 -δ.Proof of Theorem 4.3. With Lemma E.2 (optimism and pessimism), we upper bound the regret asRegret Φ (K) = K k=1 V ⋆ 1,P ⋆ ,Φ (s 1 ) -V π k 1,P ⋆ ,Φ (s 1 ) ≤ K k=1 V k 1 (s 1 ) -V k 1 (s 1 ). (E.1)In the sequel, we break our proof into three steps.Step 1: upper bounding (E.1). According to the choice ofQ k h , Q k h , V k h , V k h in (4.2), (4.3), and (4.4), let's consider that for any(h, k) ∈ [H] × [K] and (s, a) ∈ S × A, Q k h (s, a) -Q k h (s, a) = min R h (s, a) + E Pρ(s,a; P k h ) V k h+1 + bonus k h (s, a), min H, ρ -1 -max R h (s, a) + E Pρ(s,a; P k h ) V k h+1 -bonus k h (s, a), 0 ≤ E Pρ(s,a; P k h ) V k h+1 -E Pρ(s,a; P k h ) V k h+1 + 2 • bonus k h (s, a) = E Pρ(s,a; P k h ) V k h+1 -E Pρ(s,a;P ⋆ h ) V k h+1 + E Pρ(s,a;P ⋆ h ) V k h+1 -E Pρ(s,a; P k h ) V k h+1Term (i)+ E Pρ(s,a;P ⋆ h ) V k h+1 -E Pρ(s,a;P ⋆ h ) V k h+1 Term (ii) + 2 • bonus k h (s, a). (E.2)Step 1.1: upper bounding Term (i). By using a 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) ≤ 2 • bonus k h (s, a). (E.3)Step 1.2: upper bounding Term (ii). By our definition of the operator E Pρ(s,a;P ⋆ h ) [V ] in (4.1), we haveTerm (ii) = sup η∈[0,H] -E P ⋆ h (•|s,a) η -V k h+1 + + 1 - ρ 2 • η -sup η∈[0,H] -E P ⋆ h (•|s,a) η -V k h+1 + + 1 - ρ 2 • η ≤ sup η∈[0,H] E P ⋆ h (•|s,a) η -V k h+1 + -η -V k h+1 + . (E.4) By Lemma E.2 which shows that V k h+1 ≥ V k h+1and the fact that (η -x) + -(η -y) + ≤ y -x for any y > x, we can further upper bound the right hand side of (E.4) byTerm (ii) ≤ E P ⋆ h (•|s,a) V k h+1 -V k h+1 . (E.5)Step 1.3: combining the upper bounds. Now combining (E.3) and (E.5) with (E.2), we have thatQ k h (s, a) -Q k h (s, a) ≤ E P ⋆ h (•|s,a) V k h+1 -V k h+1 + 4 • bonus k h (s, a).By Lemma E.4, we can upper bound the bonus function, and after rearranging terms we further obtain thatQ k h (s, a) -Q k h (s, a) ≤ 1 + 12 H • E P ⋆ h (•|s,a) V k h+1 -V k h+1 + 4 V P ⋆ h (•|s,a) V π k h+1,P ⋆ ,Φ • c 1 ι N k h (s, a) ∨ 1 + 4c 2 H 2 Sι N k h (s, a) ∨ 1 + 4 √ K , (E.6)where c 1 , c 2 > 0 are two absolute constants. For the sake of brevity, we introduce the following notations of differences, for any(h, k) ∈ [H] × [K], ∆ k h := V k h (s k h ) -V k h (s k h ), ζ k h := ∆ k h -Q k h (s k h , a k h ) -Q k h (s k h , a k h ) , (E.7) ξ k h := E P ⋆ h (•|s k h ,a k h ) V k h -V k h -∆ k h+1 . (E.8) If we further define the filtration {F h,k } (h,k)∈[H]×[K] as F h,k = σ {(s τ i , a τ i )} (i,τ )∈[H]×[k-1] {(s k i , a k i )} i∈[h-1] {s k h } , then we can find that {ζ k h } (h,k)∈[H]×[K] is a martingale difference sequence with respect to {F h,k } (h,k)∈[H]×[K] and {ξ k h } (h,k)∈[H]×[K] is a martingale difference sequence with respect to {F h,k ∪ {a k h }}} (h,k)∈[H]×[K]. Also, we further have that∆ k h = ζ k h + Q k h (s k h , a k h ) -Q k h (s k h , a k h ) (E.9) ≤ ζ k h + 1 + 12 H • E P ⋆ h (•|s k h ,a k h ) V k h+1 -V k h+1 + 4 V P ⋆ h (•|s,a) V π k h+1,P ⋆ ,Φ • c 1 ι N k h (s k h , a k h ) ∨ 1 + 4c 2 H 2 Sι N k h (s k h , a k h ) ∨ 1 + 4 √ K = ζ k h + 1 + 12 H • ξ k h + 1 + 12 H • ∆ k h+1 + 4 V P ⋆ h (•|s,a) V π k h+1,P ⋆ ,Φ • c 1 ι N k h (s k h , a k h ) ∨ 1 + 4c 2 H 2 Sι N k h (s k h , a k h ) ∨ 1 + 4 √ K ,where the inequality applies (E.6). Recursively applying (E.9) and using the fact that (1+ 12 H ) h ≤ (1 + 12H ) H ≤ c for some absolute constant c > 0, we can upper bound the right hand side of (E.1) asRegret Φ (K) ≤ K k=1 ∆ k 1 ≤ C 1 • K k=1 H h=1 (ζ k h + ξ k h ) + V P ⋆ h (•|s,a) V π k h+1,P ⋆ ,Φ • ι N k h (s k h , a k h ) ∨ 1 + H 2 Sι N k h (s k h , a k h ) ∨ 1 + 1 √ K . (E.10)where C 1 > 0 is an absolute constant.Step 2: controlling the summation of variance terms. In view of (E.10), it suffices to 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 Cauchy-Schwartz inequality,K k=1 H h=1 V P ⋆ h (•|s k h ,a k h ) V π k h+1,P ⋆ ,Φ N k h (s k h , a k h ) ∨ 1 ≤ K k=1 H h=1 V P ⋆ h (•|s k h ,a k h ) V π k h+1,P ⋆ ,Φ • K k=1 H h=1 1 N k h (s k h , a k h ) ∨ 1 . (E.11)On the right hand side of (E.11), the summation of the inverse of the count function is a 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 a sharp bound. To this end, we invoke Lemma E.5 to obtain that with probability at least 1 -δ,K k=1 H h=1 V P ⋆ h (•|s k h ,a k h ) V π k h+1,P ⋆ ,Φ ≤ C 2 • min H, ρ -1 • HK + min H, ρ -1 3 • Hι , (E.12)where C 2 > 0 is an absolute constant. With inequality (E.12) and Lemma E.13 thatK k=1 H h=1 1 N k h (s k h , a k h ) ∨ 1 ≤ C ′ 2 • HSAι,with C ′ 2 > 0 being another constant, we can upper bound the summation of the variance terms (E.11) asK k=1 H h=1 V P ⋆ h (•|s k h ,a k h ) V π k h+1,P ⋆ ,Φ N k h (s k h , a k h ) ∨ 1 ≤ C 3 min H, ρ -1 • H 2 SAKι + min H, ρ -1 3 • H 2 SAι 2 . (E.13)where C 3 > 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 ζ k h and ξ k h are bounded by min{H, ρ -1 } according to (4.2) and Lemma E.2 (optimism and pessimism). As a result, using Azuma-Hoeffding inequality, with probability at least 1 -δK k=1 H h=1 (ζ k h + ξ k h ) ≤ C 4 • min H, ρ -1 • √ HKι,where C 4 > 0 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 1 -3δ, we haveRegret Φ (K) ≤ C 5 • min H, ρ -1 • H 2 SAKι 2 + min H, ρ -1 3 • H 2 SAι 3 + min H, ρ -1 • √ HKι + H 3 S 2 Aι 2 + H √ K = O min H, ρ -1 • H 2 SAKι ′ ,where C 5 > 0 is an absolute constant and ι ′ = log 2 (SAHK/δ). This completes the proof of Theorem 4.3.Lemma E.2 (Optimistic and pessimistic estimation of the robust values). By setting the bonus k h as in (4.5), then under the typical event E, it holds thatQ k h (s, a) ≤ Q π k h,P ⋆ ,Φ (s, a) ≤ Q ⋆ h,P ⋆ ,Φ (s, a) ≤ Q k h (s, a), V k h (s) ≤ V π k h,P ⋆ ,Φ (s) ≤ V ⋆ h,P ⋆ ,Φ (s) ≤ V k h (s), (E.14) for any (s, a, h, k) ∈ S × A × [H] × [K].Proof of Lemma E.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 k h as in (4.5), then under the typical event E, it holds thatE Pρ(s,a; P k h ) V k h+1 -E Pρ(s,a;P ⋆ h ) V k h+1 + E Pρ(s,a;P ⋆ h ) V k h+1 -E Pρ(s,a; P k h ) V k h+1 ≤ 2 • bonus k h (s, a),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 k h in (4.5) is bounded bybonus k h (s, a) ≤ V P ⋆ h (•|s,a) V π k h+1,P ⋆ ,Φ • c 1 ι N k h (s, a) ∨ 1 + 4 • E P ⋆ h (•|s,a) V k h+1 -V k h+1 H + c 2 H 2 Sι N k h (s, a) ∨ 1 + 1 √ K ,where ι = log(S 3 AH 2 K 3/2 /δ) and c 1 , c 2 > 0 are absolute constants.Proof of Lemma E.4. See Appendix E.5 for a detailed proof.Lemma E.5 (Total variance law for robust MDP with TV robust sets). With probability at least 1 -δ, the following inequality holdsK k=1 H h=1 V P ⋆ h (•|s k h ,a k h ) V π k h+1,P ⋆ ,Φ ≤ c 3 • min{H, ρ -1 } • HK + min{H, ρ -1 } 3 • Hι .where ι = log(S 3 AH 2 K 3/2 /δ) and c 3 > 0 is an absolute constant.Proof of Lemma E.5. See Appendix E.6 for a detailed proof.Proof of Lemma E.2. We prove Lemma E.2 by induction. Suppose the conclusion (E.14) holds at 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), we have thatQ ⋆ h,P ⋆ ,Φ (s, a) -Q k h (s, a) ≤ max E Pρ(s,a;P ⋆ h ) V ⋆ h+1,P ⋆ ,Φ -E Pρ(s,a; P k h ) V k h+1 -bonus k h (s, a), Q ⋆ h,P ⋆ ,Φ (s, a) -min H, ρ -1 ≤ max E Pρ(s,a;P ⋆ h ) V ⋆ h+1,P ⋆ ,Φ -E Pρ(s,a; P k h ) V ⋆ h+1,P ⋆ ,Φ -bonus k h (s, a), 0 ,(E.15)where the second inequality follows from the induction of V ⋆ h+1,P ⋆ ,Φ ≤ V k h+1 at step h + 1 and the fact that Q ⋆ h,P ⋆ ,Φ ≤ min{H, ρ -1 } (by Proposition 2.6 and Assumption 4.1). By Lemma E.7, we have thatE Pρ(s,a;P ⋆ h ) V ⋆ h+1,P ⋆ ,Φ -E Pρ(s,a; P k h ) V ⋆ h+1,P ⋆ ,Φ ≤ V P k h (•|s,a) V ⋆ h+1,P ⋆ ,Φ • c 1 ι N k h (s, a) ∨ 1 + c 2 Hι N k h (s, a) ∨ 1 + 1 √ K ,Now by further applying Lemma E.11 to the variance term in the above inequality, we can obtain thatE Pρ(s,a;P ⋆ h ) V ⋆ h+1,P ⋆ ,Φ -E Pρ(s,a; P k h ) V ⋆ h+1,P ⋆ ,Φ ≤ V P k h (•|s,a) V k h+1 + V k h+1 /2 + 4H • E P k h (•|s,a) V k h+1 -V k h+1 • c 1 ι N k h (s, a) ∨ 1 + c 2 Hι N k h (s, a) ∨ 1 + 1 √ K ≤ V P k h (•|s,a) V k h+1 + V k h+1 /2 • c 1 ι N k h (s, a) ∨ 1 + E P k h (•|s,a) V k h+1 -V k h+1 • 4Hc 1 ι N k h (s, a) ∨ 1 + c 2 Hι N k h (s, a) ∨ 1 + 1 √ K ≤ V P k h (•|s,a) V k h+1 + V k h+1 /2 • c 1 ι N k h (s, a) ∨ 1 + E P k h (•|s,a) V k h+1 -V k h+1 H + c ′ 2 H 2 ι N k h (s, a) ∨ 1 + 1 √ K , (E.16)where the first inequality is due to Lemma E.11, the second inequality is due to √ a + b ≤ √ a + √ b, and the last inequality is from √ ab ≤ a + b where c ′ 2 > 0 is an absolute constant. Therefore, combining (E.15) and (E.16), and the choice of bonus k h (s, a) in (4.5), we can conclude thatQ ⋆ h,P ⋆ ,Φ (s, a) ≤ Q k h (s, a). Furthermore, it holds that Q π k h,P ⋆ ,Φ (s, a) ≤ Q ⋆ h,P ⋆ ,Φ (s, a). Thus it reduces to prove Q k h (s, a) ≤ Q π k h,P ⋆ ,Φ (s, a). Again, by using the robust Bellman equation (Proposition 2.2) and (4.3), we have thatQ k h (s, a) -Q π k h,P ⋆ ,Φ (s, a) ≤ max E Pρ(s,a; P k h ) V k h+1 -E Pρ(s,a;P ⋆ h ) V π k h+1,P ⋆ ,Φ -bonus k h (s, a), 0 -Q π k h,P ⋆ ,Φ (s, a) ≤ max E Pρ(s,a; P k h ) V π k h+1,P ⋆ ,Φ -E Pρ(s,a;P ⋆ h ) V π k h+1,P ⋆ ,Φ -bonus k h (s, a), 0 , (E.17)where the second inequality follows from the induction of V k h+1 ≤ V π k h+1,P ⋆ ,Φ at step h + 1 and the fact that Q π k h,P ⋆ ,Φ ≥ 0. By Lemma E.8, we have thatE Pρ(s,a; P k h ) V π k h+1,P ⋆ ,Φ -E Pρ(s,a;P ⋆ h ) V π k h+1,P ⋆ ,Φ ≤ V P k h (•|s,a) V ⋆ h+1,P ⋆ ,Φ • c 1 ι N k h (s, a) ∨ 1 + E P k h (•|s,a) V k h+1 -V k h+1 H + c ′ 2 H 2 Sι N k h (s, a) ∨ 1 + 1 √ K .Now by applying Lemma E.11 to the variance term, with an argument similar to (E.16), we can obtain thatE Pρ(s,a; P k h ) V π k h+1,P ⋆ ,Φ -E Pρ(s,a;P ⋆ h ) V π k h+1,P ⋆ ,Φ (E.18) ≤ V P k h (•|s,a) V k h+1 + V k h+1 /2 • c 1 ι N k h (s, a) ∨ 1 + 2E P k h (•|s,a) V k h+1 -V k h+1 H + c ′′ 2 H 2 ι N k h (s, a) ∨ 1 + 1 √ K ,Thus by combining (E.17) and (E.18), and the choice of bonus k h (s, a) in (4.5), we can conclude that a) . Therefore, we have proved that at step h, it holds that a) . Finally for the robust V function part, consider that by robust Bellman equation (Proposition 2.2) and (4.4),Q k h (s, a) ≤ Q π k h,P ⋆ ,Φ (s,Q k h (s, a) ≤ Q π k h,P ⋆ ,Φ (s, a) ≤ Q ⋆ h,P ⋆ ,Φ (s, a) ≤ Q k h (s,V k h (s) = E π k h (•|s) Q k h (s, •) ≤ E π k h (•|s) Q π k h,P ⋆ ,Φ (s, •) = V π k h,P ⋆ ,Φ (s),and that by robust Bellman optimal equation (Proposition 2.3), the choice of π k , and (4.4),V ⋆ h,P ⋆ ,Φ (s) = max a∈A Q ⋆ h,P ⋆ ,Φ (s, a) ≤ max a∈A Q k h (s, a) = V k h (s),which proves thatV k h (s) ≤ V π k h,P ⋆ ,Φ (s) ≤ V ⋆ h,P ⋆ ,Φ (s) ≤ V k h (s). Since the conclusion (E.14) holds for the V function part at step H + 1, an induction proves Lemma E.2.Proof of Lemma E.3. We upper bound the differences by a concentration inequality Lemma E.9,E Pρ(s,a; P k h ) V k h+1 -E Pρ(s,a;P ⋆ h ) V k h+1 + E Pρ(s,a; P k h ) V k h+1 -E Pρ(s,a;P ⋆ h ) V k h+1 ≤ 2 V P k h (•|s,a) V ⋆ h+1,P ⋆ ,Φ • c 1 ι N k h (s, a) ∨ 1 + 2 • E P k h (•|s,a) V k h+1 -V k h+1 H + 2c ′ 2 H 2 Sι N k h (s, a) ∨ 1 + 2 √ K , (E.19)where c 1 , c ′ 2 > 0 are absolute constants. Then applying Lemma E.11 to the variance term in (E.19), with an argument the same as (E.16) in the proof of Lemma E.2, we can obtain thatE Pρ(s,a; P k h ) V k h+1 -E Pρ(s,a;P ⋆ h ) V k h+1 + E Pρ(s,a; P k h ) V k h+1 -E Pρ(s,a;P ⋆ h ) V k h+1 ≤ 2 V P k h (•|s,a) V k h+1 + V k h+1 /2 • c 1 ι N k h (s, a) ∨ 1 + 4 • E P k h (•|s,a) V k h+1 -V k h+1 H + 2c ′′ 2 H 2 ι N k h (s, a) ∨ 1 + 2 √ K .Therefore, by looking into the choice of bonus k h (s, a) in (4.5), we can conclude thatE Pρ(s,a; P k h ) V k h+1 -E Pρ(s,a;P ⋆ h ) V k h+1 + E Pρ(s,a; P k h ) V k h+1 -E Pρ(s,a;P ⋆ h ) V k h+1 ≤ 2 • bonus k h (s, a),This finishes the proof of Lemma E.3.Proof of Lemma E.4. Recall that the bonus k h (s, a) is defined asbonus k h (s, a) = V P k h (•|s,a) V k h+1 + V k h+1 /2 • c 1 ι N k h (s, a) ∨ 1 + 2E P k h (•|s,a) V k h+1 -V k h+1 H + c 2 H 2 Sι N k h (s, a) ∨ 1 + 1 √ K .The main thing we need to consider is to control the first term and the second term. We first deal with the second term of bonus k h (s, a) by invoking Lemma E.10, which gives2E P k h (•|s,a) V k h+1 -V k h+1 H ≤ 2 H + 2 H 2 • E P ⋆ h (•|s,a) V k h+1 -V k h+1 + c ′ 2 HSι N k h (s, a) ∨ 1 ≤ 3E P ⋆ h (•|s,a) V k h+1 -V k h+1 H + c ′ 2 HSι N k h (s, a) ∨ 1 , (E.20)where the second inequality is from H ≥ 2. Then we deal with the first term (variance term) of bonus k h (s, a) by invoking Lemma E.12, which givesV P k h (•|s,a) V k h+1 + V k h+1 /2 • c 1 ι N k h (s, a) ∨ 1 (E.21) ≤ V P ⋆ h (•|s,a) V π k h+1,P ⋆ ,Φ + 4H • E P ⋆ h (•|s,a) V k h+1 -V k h+1 + c ′′ 2 H 4 Sι N k h (s,a)∨1 + 1 • c 1 ι N k h (s, a) ≤ V P ⋆ h (•|s,a) V π k h+1,P ⋆ ,Φ • c 1 ι N k h (s, a) ∨ 1 + 4H • E P ⋆ h (•|s,a) V k h+1 -V k h+1 • c 1 ι N k h (s, a) ∨ 1 + c 1 c ′′ 2 SH 2 ι N k h (s, a) ∨ 1 + c 1 ι N k h (s, a) ∨ 1 ≤ V P ⋆ h (•|s,a) V π k h+1,P ⋆ ,Φ • c ′ 1 ι N k h (s, a) ∨ 1 + E P ⋆ h (•|s,a) V k h+1 -V k h+1 H + 4c 1 + c 1 c ′′ 2 S H 2 ι N k h (s, a) ∨ 1Thus by combining (E.20) and (E.21) with the choice of bonus k h , we can conclude the proof of Lemma E.4.Proof of Lemma E.5. The key idea is to relate the visitation distribution (w.r.t. P ⋆ ) and the variance (w.r.t. P ⋆ ) to the value function of π k , after which we can derive an upper bound for the total variance. Throughout this proof, we use the shorthand thatH = min H, ρ -1 .According to Proposition 2.6 and Assumption 4.1, for any policy π and any step h, the robust value function of π holds thatmax s∈S V π h,P ⋆ ,Φ (s) ≤ H, (E.22)which we usually apply in the sequel. Also, to facilitate our analysis, we defineT k h (•|s, a) = argmin P (•)∈P h (s,a;P ⋆ h ) E P (•) V π k h+1,P ⋆ ,Φ , ∀(s, a, h) ∈ S × A × [H],and set T k = { T k h } H h=1 , which is the most adversarial transition for the true robust value function of π k . Now consider the following decomposition of our target,K k=1 H h=1 V P ⋆ h (•|s k h ,a k h ) V π k h+1,P ⋆ ,Φ = K k=1 H h=1 V P ⋆ h (•|s k h ,a k h ) V π k h+1,P ⋆ ,Φ -E (s k h ,a k h )∼(P ⋆ ,π k ) H h=1 V P ⋆ h (•|s k h ,a k h ) V π k h+1,P ⋆ ,Φ + K k=1 E (s k h ,a k h )∼(P ⋆ ,π k ) H h=1 V P ⋆ h (•|s k h ,a k h ) V π k h+1,P ⋆ ,Φ = K k=1 H h=1 V P ⋆ h (•|s k h ,a k h ) V π k h+1,P ⋆ ,Φ -E (s k h ,a k h )∼(P ⋆ ,π k ) H h=1 V P ⋆ h (•|s k h ,a k h ) V π k h+1,P ⋆ ,ΦTerm (i): martingale difference term+ K k=1 E (s k h ,a k h )∼( T k ,π k ) H h=1 V T k h (•|s k h ,a k h ) V π k h+1,P ⋆ ,ΦTerm (ii): total variance law+ K k=1 E (s k h ,a k h )∼(P ⋆ ,π k ) H h=1 V P ⋆ h (•|s k h ,a k h ) V π k h+1,P ⋆ ,Φ -E (s k h ,a k h )∼( T k ,π k ) H h=1 V T k h (•|s k h ,a k h ) V π k h+1,P ⋆ ,ΦTerm (iii): error from P ⋆ to T k .In the sequel, we upper bound each of the three terms respectively.Term (i): martingale difference term. This is a summation of martingale difference term (with respect to filtrationG k = σ({(s τ h , a τ h )} (h,τ )∈[H]×[k])). By Azuma-Hoeffding's inequality, with probability at least 1 -δ,Term (i) ≤ c • H • H 2 • √ Kι, (E.23)where c > 0 is an absolute constant. We have utilized the fact of (E.22) to obtain the upper bound HH 2 on each martingale difference term in the summation.Term (ii): total variance law. The upper bound of this term is 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 π, define thatT h (•|s, a) = argmin P (•)∈Pρ(s,a;P ⋆ h ) E P (•) V π h+1,P ⋆ ,Φ , ∀(s, a, h) ∈ S × A × [H], (E.24)and set T = { T h } H h=1 . Then we haveE (s h ,a h )∼( T ,π) H h=1 V T h (•|s h ,a h ) V π h+1,P ⋆ ,Φ ≤ 2H • H.We defer the proof of Lemma E.6 to Appendix E.7. With Lemma E.6, we consider taking policy π = π k for k ∈ [K] therein (which are deterministic policies), and obtain that the Term (ii) is upper bounded byTerm (ii) ≤ 2H • H • K. (E.25)Term (iii): error from P ⋆ to T k . We first relate the visitation distribution under P ⋆ to that under T k . On the one hand, by the choice of the adversarial transition kernel T k h , it holds thatD TV P ⋆ h (•|s, a) T k h (•|s, a) ≤ ρ, ∀(s, a, h) ∈ S × A × [H]. (E.26)On the other hand, by (E.22), we can upper bound the variance term byV P ⋆ h (•|s,a) V π k h+1,P ⋆ ,Φ ≤ H 2 , ∀(s, a, h) ∈ S × A × [H]. (E.27)Therefore, by combining (E.26) and (E.27), we can conclude thatE (s k h ,a k h )∼(P ⋆ h ,π k ) H h=1 V P ⋆ (•|s k h ,a k h ) V π k h+1,P ⋆ ,Φ ≤ E (s k h ,a k h )∼( T k ,π k ) H h=1 V P ⋆ h (•|s k h ,a k h ) V π k h+1,P ⋆ ,Φ + H • sup (s,a,h)∈S×A×[H] D TV P ⋆ h (• | s, a) T k h (• | s, a) • sup (s,a,h)∈S×A×[H] V P ⋆ h (•|s,a) V π k h+1,P ⋆ ,Φ ≤ E (s k h ,a k h )∼( T k ,π k ) H h=1 V P ⋆ h (•|s k h ,a k h ) V π k h+1,P ⋆ ,Φ + ρH • H 2 . (E.28)We then relate the variance term under P ⋆ to that under T k . Specifically, we haveV P ⋆ h (•|s,a) V π k h+1,P ⋆ ,Φ = E P ⋆ h (•|s,a) V π k h+1,P ⋆ ,Φ 2 -E P ⋆ h (•|s,a) V π k h+1,P ⋆ ,Φ 2 ≤ E T k h (•|s,a) V π k h+1,P ⋆ ,Φ 2 -E T k h (•|s,a) V π k h+1 (s ′ ) 2 + 2 • sup (s,a)∈S×A D TV P ⋆ h (•|s, a) T k h (•|s, a) • max s ′ ∈S V π h+1,P ⋆ ,Φ (s ′ ) 2 ≤ V T k h (•|s,a) V π k h+1,P ⋆ ,Φ + 2ρ • H 2 , ∀(s, a, h) ∈ S × A × [H], (E.29)where the last inequality follows from the definition of T k and (E.22). Combining (E.28) and (E.29), we can upper bound Term (iii) by the following,Term (iii) = K k=1 E (s k h ,a k h )∼(P ⋆ ,π k ) H h=1 V P ⋆ h (•|s k h ,a k h ) V π k h+1,P ⋆ ,Φ (E.30) -E (s k h ,a k h )∼( T k ,π k ) H h=1 V P ⋆ h (•|s k h ,a k h ) V π k h+1,P ⋆ ,Φ + K k=1 E (s k h ,a k h )∼( T k ,π k ) H h=1 V P ⋆ h (•|s k h ,a k h ) V π k h+1,P ⋆ ,Φ -E (s k h ,a k h )∼( T k ,π k ) H h=1 V T k h (•|s k h ,a k h ) V π k h+1,P ⋆ ,Φ ≤ 3ρH • H 2 • K ≤ 3H • H • K,where in the last inequality we use the fact that for any ρ ∈ [0, 1], it holds thatρH = ρ • min H, ρ -1 = min ρH, 1 ≤ 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 at least 1 -δ, it holds thatK k=1 H h=1 V P ⋆ h (•|s k h ,a k h ) V π k h+1,P ⋆ ,Φ ≤ c • H • H 2 • √ Kι + 2H • H • K + 3H • H • K ≤ c ′ • H • H • K + c ′′ • H • H 3 • ι,where in the last inequality we use √ ab ≤ a + b for any a, b > 0. Plug in the notation that H = min{H, ρ -1 } and finish the proof of Lemma E.5.Proof of Lemma E.6. Using the property of variance, we have that for any (s h , a h ) ∈ S × A,V T h (•|s h ,a h ) V π h+1,P ⋆ ,Φ = E T h (•|s h ,a h ) V π h+1,P ⋆ ,Φ 2 -E T h (•|s h ,a h ) V π h+1,P ⋆ ,Φ 2 .(E.31)By robust Bellman equation (Proposition 2.2) and the definition of T h in (E.24), we have thatV π h,P ⋆ ,Φ (s h ) = R h (s h , π h (s h )) + E T h (•|s h ,π h (s h )) V π h+1,P ⋆ ,Φ . (E.32)Therefore, by (E.31) and (E.32), we have thatV T h (•|s h ,π h (s h )) V π h+1,P ⋆ ,Φ = E T h (•|s h ,π h (s h )) V π h+1,P ⋆ ,Φ 2 -V π h,P ⋆ ,Φ (s h ) -R h (s h , π h (s h )) 2 . (E.33)For the second term in (E.33), we can calculate it as-V π h,P ⋆ ,Φ (s h ) -R h (s h , π h (s h )) 2 = -V π h,P ⋆ ,Φ 2 (s h ) + 2 • V π h,P ⋆ ,Φ (s h ) • R h (s h , π h (s h )) -R 2 h (s h , π h (s h )) ≤ -V π h,P ⋆ ,Φ 2 (s h ) + 2H, (E.34)where the last inequality utilizes the facts that 0≤ R h (s h , π h (s h )) ≤ 1, R 2 h (s h , π h (s h )) ≥ 0, and (E.22) that V π h,P ⋆ ,Φ (s h ) ≤ H.Combining (E.33) and (E.34), we have thatV T h (•|s h ,π h (s h )) V π h+1,P ⋆ ,Φ ≤ E T h (•|s h ,π h (s h )) V π h+1,P ⋆ ,Φ 2 -V π h,P ⋆ ,Φ 2 (s h ) + 2H,which further implies thatE (s h ,a h )∼( T ,π) V T h (•|s h ,a h ) V π h+1,P ⋆ ,Φ = E s h ∼( T ,π) V T h (•|s h ,π h (s h )) V π h+1,P ⋆ ,Φ ≤ E s h ∼( T ,π) E T h (•|s h ,π h (s h )) V π h+1,P ⋆ ,Φ 2 -V π h,P ⋆ ,Φ 2 + 2H = E s h+1 ∼( T ,π) V π h+1,P ⋆ ,Φ 2 -E s h ∼( T ,π) V π h,P ⋆ ,Φ 2 + 2H.Taking summation over h ∈ [H] gives thatE (s h ,a h )∼( T ,π),h∈[H] H h=1 V T h (•|s h ,a h ) V π h+1,P ⋆ ,Φ ≤ 2H • H = 2H • min H, ρ -1 ,which concludes the proof of Lemma E.6.Before presenting all lemmas, we recall that the typical event E is defined as E =    E P ⋆ h (•|s,a) -E P k h (•|s,a) η -V ⋆ h+1,P ⋆ ,Φ + ≤ V P k h (•|s,a) η -V ⋆ h+1,P ⋆ ,Φ + • c 1 ι N k h (s, a) ∨ 1 + c 2 Hι N k h (s, a) ∨ 1 , P ⋆ h (s ′ |s, a) -P h (s ′ |s, a) ≤ min P ⋆ h (s ′ |s, a), P k h (s ′ |s, a) • c 1 ι N k h (s, a) ∨ 1 + c 2 ι N k h (s, a) ∨ 1 , ∀(s, a, s ′ , h, k) ∈ S × A × S × [H] × [K], ∀η ∈ N 1/(S √ K) [0, H]    , (E.35) where ι = log(S 3 AH 2 K 3/2 /δ),) V ⋆ h+1,P ⋆ ,Φ -E Pρ(s,a;P ⋆ h ) V ⋆ h+1,P ⋆ ,Φ ≤ V P k h (•|s,a) V ⋆ h+1,P ⋆ ,Φ • c 1 ι N k h (s, a) ∨ 1 + c 2 Hι N k h (s, a) ∨ 1 + 1 √ K ,where ι = log(S 3 AH 2 K 3/2 /δ).Proof of Lemma E.7. By our definition of the operator E Pρ(s,a;P k h ) [V ⋆ h+1,P ⋆ ,Φ ] in (4.1), we can arrive that E Pρ(s,a; P k h ) V ⋆ h+1,P ⋆ ,Φ -E Pρ(s,a;P ⋆ h ) V ⋆ h+1,P ⋆ ,Φ = sup η∈[0,H] -E P k h (•|s,a) η -V ⋆ h+1,P ⋆ ,Φ + + 1 - ρ 2 • η -sup η∈[0,H] -E P ⋆ h (•|s,a) η -V ⋆ h+1,P ⋆ ,Φ + + 1 - ρ 2 • η ≤ sup η∈[0,H] E P k h (•|s,a) -E P ⋆ h (•|s,a) η -V ⋆ h+1,P ⋆ ,Φ + , (E.36)Now according to the first inequality of event E, we have thatE P ⋆ h (•|s,a) -E P k h (•|s,a) η -V ⋆ h+1,P ⋆ ,Φ + ≤ V P k h (•|s,a) η -V ⋆ h+1,P ⋆ ,Φ + • c 1 ι N k h (s, a) ∨ 1 + c 2 Hι N k h (s, a) ∨ 1 ≤ V P k h (•|s,a) V ⋆ h+1,P ⋆ ,Φ • c 1 ι N k h (s, a) ∨ 1 + c 2 Hι N k h (s, a) ∨ 1 , for any η ∈ N 1/(S √ K) ([0, H]).Here the second inequality is because Var[(a -X) + ] ≤ Var[X]. Therefore, by a covering argument, for any η ∈ [0, H], it holds thatE P ⋆ h (•|s,a) -E P k h (•|s,a) η -V ⋆ h+1,P ⋆ ,Φ + ≤ V P k h (•|s,a) V ⋆ h+1,P ⋆ ,Φ • c 1 ι N k h (s, a) ∨ 1 + c 2 Hι N k h (s, a) ∨ 1 + 1 √ K .This finishes the proof of Lemma E.7.Lemma E.8 (Bernstein bound for TV robust sets and the robust value function of π k ). Under event E in (E.35), suppose that the optimism and pessimism (E.14) holds at (h + 1, k), then it holds thatE Pρ(s,a; P k h ) V π k h+1,P ⋆ ,Φ -E Pρ(s,a;P ⋆ h ) V π k h+1,P ⋆ ,Φ ≤ V P k h (•|s,a) V ⋆ h+1,P ⋆ ,Φ • c 1 ι N k h (s, a) ∨ 1 + E P k h (•|s,a) V k h+1 -V k h+1 H + c ′ 2 H 2 Sι N k h (s, a) ∨ 1 + 1 √ K ,where ι = log(S 3 AH 2 K 3/2 /δ) and c 1 , c ′ 2 are absolute constants.Proof of Lemma E.8. By our definition of the operator E Pρ(s,a;P ) [V π k h+1,P ⋆ ,Φ ] in (4.1), we can arrive that,E Pρ(s,a; P k h ) V π k h+1,P ⋆ ,Φ -E Pρ(s,a;P ⋆ h ) V π k h+1,P ⋆ ,Φ = sup η∈[0,H] -E P k h (•|s,a) η -V π k h+1,P ⋆ ,Φ + + 1 - ρ 2 • η -sup η∈[0,H] -E P ⋆ h (•|s,a) η -V π k h+1,P ⋆ ,Φ + + 1 - ρ 2 • η ≤ sup η∈[0,H] E P k h (•|s,a) -E P ⋆ h (•|s,a) η -V π k h+1,P ⋆ ,Φ + ≤ sup η∈[0,H] E P k h (•|s,a) -E P ⋆ h (•|s,a) η -V ⋆ h+1,P ⋆ ,Φ + Term (i) + sup η∈[0,H] E P k h (•|s,a) -E P ⋆ h (•|s,a) η -V π k h+1,P ⋆ ,Φ + -η -V ⋆ h+1,P ⋆ ,Φ + 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 as Lemma E.7 gives the following upper bound,Term (i) ≤ V P k h (•|s,a) V ⋆ h+1,P ⋆ ,Φ • c 1 ι N k h (s, a) ∨ 1 + c 2 Hι N k h (s, a) ∨ 1 + 1 √ K . (E.37)For Term (ii), we first apply the second inequality of event E to obtain that,Term (ii) (E.38) ≤ sup η∈[0,H] s ′ ∈S P k h (s ′ |s, a) • c 1 ι N k h (s, a) ∨ 1 + c 2 ι N k h (s, a) ∨ 1 • η -V π k h+1,P ⋆ ,Φ (s ′ ) + -η -V ⋆ h+1,P ⋆ ,Φ (s ′ ) + .By the assumption that (E.14) holds at (h + 1, k), we can upper bound the absolute value above byη -V π k h+1,P ⋆ ,Φ (s ′ ) + -η -V ⋆ h+1,P ⋆ ,Φ (s ′ ) + ≤ V π k h+1,P ⋆ ,Φ (s ′ ) -V ⋆ h+1,P ⋆ ,Φ (s ′ ) ≤ V k h+1 (s ′ ) -V k h+1 (s ′ ). (E.39)where the first inequality is due to the 1-Lipschitz continuity of ψ η (x) = (η -x) + , and the second inequality is due to (E.14). Thus combining (E.38) and (E.39), we know thatTerm (ii) ≤ s ′ ∈S   P k h (s ′ |s, a) • c 1 ι N k h (s, a) ∨ 1 + c 2 ι N k h (s, a) ∨ 1   • V k h+1 (s ′ ) -V k h+1 (s ′ ) . (E.40)Now following the argument first identified by Azar et al. (2017) , we proceed to upper bound (E.40) asTerm (ii) ≤ s ′ ∈S P k h (s ′ |s, a) H + c 1 Hι N k h (s, a) ∨ 1 + c 2 ι N k h (s, a) ∨ 1 • V k h+1 (s ′ ) -V k h+1 (s ′ ) ≤ E P k h (•|s,a) V k h+1 -V k h+1 H + c ′ 2 H 2 Sι N k h (s, a) ∨ 1 , (E.41)where c ′ 2 > 0 is another absolute constant. The first inequality is by√ ab ≤ a + b and the second inequality is due to V k h+1 , V k h+1 ∈ [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 E in (E.35), suppose that the optimism and pessimism (E.14) holds at(h + 1, k), it holds that max E Pρ(s,a; P k h ) V k h+1 -E Pρ(s,a;P ⋆ h ) V k h+1 , E Pρ(s,a; P k h ) V k h+1 -E Pρ(s,a;P ⋆ h ) V k h+1 ≤ V P k h (•|s,a) V ⋆ h+1,P ⋆ ,Φ • c 1 ι N k h (s, a) ∨ 1 + E P k h (•|s,a) V k h+1 -V k h+1 H + c ′ 2 H 2 Sι N k h (s, a) ∨ 1 + 1 √ K ,where ι = log(S 3 AH 2 K 3/2 /δ) and c 1 , c ′ 2 are absolute constants.Proof of Lemma E.9. This follows from the same proof as Lemma E.8 and is thus omitted.Lemma E.10 (Non-robust concentration). Under event E in (E.35), suppose that the optimism and pessimism (E.14) holds at (h + 1, k), then it holds thatE P k h (•|s,a) -E P ⋆ h (•|s,a) V k h+1 -V k h+1 ≤ 1 H • E P ⋆ h (•|s,a) V k h+1 -V k h+1 + c ′ 2 H 2 Sι N k h (s, a) ∨ 1.where ι = log(S 2 AH 2 K 3/2 /δ) and c ′ 2 is an absolute constant.Proof of Lemma E.10. According to the second inequality of event E, we have thatE P k h (•|s,a) -E P ⋆ h (•|s,a) V k h+1 -V k h+1 ≤ s ′ ∈S P ⋆ h (s ′ |s, a) • c 1 ι N k h (s, a) ∨ 1 + c 2 ι N k h (s, a) ∨ 1 • V k h+1 (s ′ ) -V k h+1 (s ′ ) ,where we also apply (E.14) that V k h+1 (s ′ ) ≥ V k h+1 (s ′ ). Now using the same argument as (E.41) in the proof of Lemma E.8, we can arrive atE P k h (•|s,a) -E P ⋆ h (•|s,a) V k h+1 -V k h+1 ≤ E P ⋆ h (•|s,a) V k h+1 (s ′ ) -V k h+1 (s ′ ) H + c ′ 2 H 2 Sι N k h (s, a) ∨ 1, which finishes the proof of Lemma E.10.Lemma E.11 (Variance analysis 1). Suppose that the optimism and pessimism (E.14) holds at (h + 1, k), then the following inequality holds,V P k h (•|s,a) V k h+1 + V k h+1 /2 -V P k h (•|s,a) V ⋆ h+1,P ⋆ ,Φ ≤ 4H • E P k h (•|s,a) V k h+1 -V k h+1 .Proof of Lemma E.11. Directly consider that the left hand side can be upper bounded by the following,V P k h (•|s,a) V k h+1 + V k h+1 /2 -V P k h (•|s,a) V ⋆ h+1,P ⋆ ,Φ ≤ E P k h (•|s,a) V k h+1 + V k h+1 2 /4 -E P k h (•|s,a) V ⋆ h+1,P ⋆ ,Φ 2 + E P k h (•|s,a) V k h+1 + V k h+1 /2 2 -E P k h (•|s,a) V ⋆ h+1,P ⋆ ,Φ 2 . (E.42) Since all of V k h+1 , V k h+1 , V ⋆ h+1,P ⋆ ,Φ ∈ [0, H](by the correctness of (E.14) and the definitions of V k h+1 , V k h+1 ), we can further upper bound the right hand side of (E.42) asV P k h (•|s,a) V k h+1 + V k h+1 /2 -V P k h (•|s,a) V ⋆ h+1,P ⋆ ,Φ ≤ 4H • E P k h (•|s,a) V k h+1 + V k h+1 /2 -V ⋆ h+1,P ⋆ ,Φ ≤ 4H • E P k h (•|s,a) V k h+1 -V k h+1 ,where the last inequality is due to the correctness of (E.14) at (h+1, k). This proves Lemma E.11.Lemma E.12 (Variance analysis 2). Under event E in (E.35), suppose that optimism and pessimism (E.14) holds at (h + 1, k), then it holds thatV P k h (•|s,a) V k h+1 + V k h+1 /2 -V P ⋆ h (•|s,a) V π k h+1,P ⋆ ,Φ ≤ 4H • E P ⋆ h (•|s,a) V k h+1 -V k h+1 + c ′ 2 H 4 Sι N k h (s, a) + 1.Proof of Lemma E.12. We first relate the variance on P k h to the variance on P ⋆ h . Specifically, we haveV P k h (•|s,a) V k h+1 + V k h+1 /2 -V P ⋆ h (•|s,a) V k h+1 + V k h+1 /2 = E P k h (•|s,a) V k h+1 + V k h+1 /2 -E P k h (•|s,a) V k h+1 + V k h+1 /2 2 + E P ⋆ h (•|s,a) V k h+1 + V k h+1 /2 -E P ⋆ h (•|s,a) V k h+1 + V k h+1 /2 2 . (E.43) Since (V k h+1 + V k h+1 )/2 ∈ [0, H],we can further upper bound (E.43) byV P k h (•|s,a) V k h+1 + V k h+1 /2 -V P ⋆ h (•|s,a) V k h+1 + V k h+1 /2 ≤ H 2 • s ′ ∈S P ⋆ h (s ′ |s, a) -P h (s ′ |s, a) ≤ H 2 • s ′ ∈S P ⋆ h (•|s, a) • c 1 ι N k h (s, a) ∨ 1 + c 2 ι N k h (s, a) ∨ 1 ≤ H 2 • c 1 Sι N k h (s, a) ∨ 1 + c 2 Sι N k h (s, a) ∨ 1 ≤ 1 + c ′ 2 H 4 Sι N k h (s, a) ∨ 1 , (E.44)where the second inequality is by the second inequality in event E, the third inequality is by Cauchy-Schwartz inequality and the probability distribution sums up to 1, and the last inequality is from √ ab ≤ a + b. Thus by (E.44), we can bound our target asV P k h (•|s,a) V k h+1 + V k h+1 /2 -V P ⋆ h (•|s,a) V π k h+1,P ⋆ ,Φ ≤ V P ⋆ h (•|s,a) V k h+1 + V k h+1 /2 -V P ⋆ h (•|s,a) V π k h+1,P ⋆ ,Φ + c ′ 2 H 4 Sι N k h (s, a) ∨ 1 + 1. (E.45)Now by the same proof of Lemma E.11, using the correctness of (E.14) at (h + 1, k), we can show thatV P ⋆ h (•|s,a) V k h+1 + V k h+1 /2 -V P ⋆ h (•|s,a) V π k h+1,P ⋆ ,Φ ≤ 4H • E P ⋆ h (•|s,a) V k h+1 -V k h+1 . (E.46)Combining (E.45) and (E.46), we can finish the proof of Lemma E.12.Lemma E.13 (Lemma 7.5 in Agarwal et al. ( 2019)). For the sequences of {s k h , a k h } H,K h,k=1 , it holds thatK k=1 H h=1 1 N k h (s k h , a k h ) ∨ 1 ≤ c • HSA log(K).where c > 0 is an 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.2In this section, we prove the theoretical results in Section B.4.2.F.1 Proof of Corollary B.5Proof of Corollary B.5. We consider applying Algorithm 1 on the auxiliary S ×A-rectangular RMDP with a TV robust set M (see Section B.4.2) which satisfies the vanishing minimal value assumption (Assumption 4.1). Suppose the algorithm outputs π 1 , • • • , π K for the K episodes. Then Theorem 4.3 shows that by a proper choice of the hyperparameters, with probability at least 1 -δRegret Φ (K) = K k=1 max π V π 1, P ⋆ , Φ (s 1 ) -V π k 1, P ⋆ , Φ (s 1 )≤ O min H, ρ -1 H 2 (S + 1)AKι ′ , .(F.1)where ι ′ = log 2 (SAHK/δ) and ρ = 2 -2ρ ′ ∈ [0, 1). In the sequel, we prove that for any policy π of M and its induced policy π S of M γ , their robust value functions coincide at the initial state s 1 ∈ S, that is,V π 1, P ⋆ , Φ (s 1 ) = V π S 1,P ⋆ ,Φ ′ (s 1 ), where V π 1, P ⋆ , Φ is the robust value function of π in M = ( S, A, H, P ⋆ , R, Φ), and V π S 1,P ⋆ ,Φ ′ is the robust value function of π S in M γ = (S, A, H, P ⋆ , R γ , Φ ′ ). To this end, we actually prove a stronger result that for any step h ∈ [H], it holds that (ρ ′ ) h-1 • V π h, P ⋆ , Φ (s) = V π S h,P ⋆ ,Φ ′ (s), ∀s ∈ S. (F.2)We prove (F.2) by induction. For step H, by robust Bellman equation, we have that, for any (s, a) ∈ S × A,(ρ ′ ) H-1 • Q π H, P ⋆ , Φ (s, a) = (ρ ′ ) H-1 • γ ρ ′ H-1• R H (s, a) = R γ,H (s, a) = Q π S H,P ⋆ ,Φ ′ (s, a), and thus for any s ∈ S,(ρ ′ ) H-1 • V π h, P ⋆ , Φ (s) = E π(•|s) (ρ ′ ) H-1 • Q π H, P ⋆ , Φ (s, •) = E π S (•|s) Q π S H,P ⋆ ,Φ (s, •) = V π SH,P ⋆ ,Φ ′ (s). This proves (F.2) for step H. Suppose that (F.2) holds at some step h + 1, that is,(ρ ′ ) h • V πh+1, P ⋆ , Φ (s) = V π S h+1,P ⋆ ,Φ ′ (s), ∀s ∈ S.(F.3)Then for step h, by robust Bellman equation and Proposition 4.2, we have that(ρ ′ ) h-1 • Q π h, P ⋆ , Φ (s, a) = (ρ ′ ) h-1 • γ ρ ′ H-1 • R h (s, a) + (ρ ′ ) h-1 • E Pρ(s,a; P ⋆ h ) V π h+1, P ⋆ , Φ = R γ,h (s, a) + (ρ ′ ) h-1 • ρ ′ • E Bρ(s,a; P ⋆ h ) V π h+1, P ⋆ , Φ , (F.4)where the last equality utilizes Proposition 4.2 since min s∈ S V π h+1, P ⋆ , Φ (s) = 0, and we adopt the notation where the second equality applies (F.3) and the last equality is from robust Bellman equation. Consequently, for any s ∈ S, we have that(ρ ′ ) h-1 • V π h, P ⋆ , Φ (s) = E π(•|s) (ρ ′ ) h-1 • Q π h, P ⋆ , Φ (s, •) = E π S (•|s) Q π S h,P ⋆ ,Φ (s, •) = V π Sh,P ⋆ ,Φ ′ (s), which finishes the induction argument, proving our claim (F.2). By taking h = 1, we can derive that for any initial state s 1 ∈ S, it holds that for any policy π of M and its induced policy π S of M γ , V π 1, P ⋆ , Φ (s 1 ) = V π S 1,P ⋆ ,Φ ′ (s 1 ).This indicates two facts: the first is that max π V π 1, P ⋆ , Φ (s 1 ) = max π V π 1,P ⋆ ,Φ ′ (s 1 ), (F.6)where on the right hand side the maximization is with respect to all the policies for M γ ; the second is thatV π k 1, P ⋆ , Φ (s 1 ) = V π k S1,P ⋆ ,Φ ′ (s 1 ), (F.7)for each k ∈ [K], where recall that π k is the policy output by Algorithm 1 for episode k. As a result, the k policies { π k S } K k=1 of M γ during interactive data collection satisfies with probability at least 1 -δ,Regret Φ ′ (K) = K k=1 max π V π 1,P ⋆ ,Φ ′ (s 1 ) -V π k S 1,P ⋆ ,Φ ′ (s 1 ) = K k=1 max π V π 1, P ⋆ , Φ (s 1 ) -V π k 1, P ⋆ , Φ (s 1 ) ≤ O min H, (2 -2ρ ′ ) -1 H 2 SAKι ′ ,where in the second equality we apply the facts (F.6) and (F.7), and the last inequality follows from (F.1) and that ρ = 2 -2ρ ′ . This completes the proof of Corollary B.5.• 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 a 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.For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a 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 to 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 to 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 NeurIPS does not require releasing code, the conference does require all submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. (d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to 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., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.Proof of Lemma D.1. For any step h ∈ [H], we have that by robust Bellman equation (Proposition 2.2),Q π ⋆ h,P ⋆ ,Φ (s, a) -Q π h,P ⋆ ,Φ (s, a) = E Pρ(s,a;P ⋆ h ) V π ⋆ h+1,P ⋆ ,Φ -E Pρ(s,a;P ⋆ h ) V π h+1,P ⋆ ,Φ. By the definition of the transition kernel P π ⋆ , † in Lemma D.1 and the property of infimum, we have thatQ π ⋆ h,P ⋆ ,Φ (s, a) -Q π h,P ⋆ ,Φ (s, a) ≥ E P π ⋆ , † h (•|s,a) V π ⋆ h+1,P ⋆ ,Φ -E P π ⋆ , † h (•|s,a) V π h+1,P ⋆ ,Φ = E P π ⋆ , † h (•|s,a) V π ⋆ h+1,P ⋆ ,Φ -V π h+1,P ⋆ ,Φ . (D.13)By robust Bellman equation (Proposition 2.2) and (D.13), we further obtain thatV π ⋆ h,P ⋆ ,Φ (s) -V π h,P ⋆ ,Φ (s) = E π ⋆ h (•|s) Q π ⋆ h,P ⋆ ,Φ (s, •) -E π h (•|s) Q π h,P ⋆ ,Φ (s, •) = E π ⋆ h (•|s) Q π h,P ⋆ ,Φ (s, •) -E π h (•|s) Q π h,P ⋆ ,Φ (s, •) + E π ⋆ h (•|s) Q π ⋆ h,P ⋆ ,Φ (s, •) -E π ⋆ h (•|s) Q π h,P ⋆ ,Φ (s, •) ≥ a∈A π ⋆ h (a|s) -π h (a|s) • Q π h,P ⋆ ,Φ(s, a) + E a∼π ⋆ h (•|s),P π ⋆ , † h (•|s,a) V π h,P ⋆ ,Φ -V π h,P ⋆ ,Φ . (D.14) 


Decision: 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.

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: 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? 
Specifically, 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)$.
* 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.
* 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. 



[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.
questions: questions: 1. In the introduction "Given that all the existing52
literature on robust RL theory relies on a generative model or pre-collected data" 
Not all the existing works are using generative model or offline dataset? Such as [1]. If so, please check


[1] Dong, Jing, et al. "Online policy optimization for robust mdp." arXiv preprint arXiv:2209.13841 (2022).
limitations: limitations: Well-answered
paper_summary: paper_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.
strength_weakness: strength_weakness: 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. 
2. I am not sure if the Interactive Data Collection design is feasible in practice especially in some real-world problems. 
3. 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.
questions: questions: Please see the weakness part.
limitations: limitations: No
paper_summary: paper_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.
strength_weakness: strength_weakness: I am not aware of notable weaknesses.
questions: questions: 1. In my understanding, this is the first **value-based** online/interactive data collection DRRL algorithm. Can authors confirm this is the case?
2.  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.
3. 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.

Reference
[1] ZHOU, R., LIU, T., CHENG, M., KALATHIL, D., KUMAR, P. and TIAN, C. (2023). Natural actor-560
critic for robust reinforcement learning with function approximation. In Thirty-seventh Conference561
on Neural Information Processing Systems.
limitations: limitations: No other limitations I would like to bring up.
paper_summary: paper_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.

Three main contributions are :

1)  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.
2) 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.
3)  Proposing an algorithm with a provable sample complexity guarantee under this framework.
strength_weakness: strength_weakness: 5) It would also be interesting to extend results for $s$- rectangular case.
6) There is no lower bound with vanishing minimal assumption to ensure that the upper bound under these assumptions is tight.
7)  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"
8) I think it would be interesting to gives more intuition on vanishing minimal assumption.
questions: questions: 9) Do you think that vanishing minimal assumption is restrictive to derive Deep Robust RL algorithm ? 
10) Do you think it would be possible to adapt Proposition 4.2 to other norms such as $L_p$ ? 
11) To clarify thing, the main difference between generative model setting and online setting in RMDPs is to deal with support shift of kernel ? 
12) 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 ?
13) 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: limitations: No limitations.

Comments: title: Response to the authors
Engage with authors
Engagement with authors
comment: Thank you very much for your efforts reviewing our paper and we appreciate your support! We will further improve our paper following your suggestions during revision.
Thank you for your valuable time reviewing our work and thanks for your support! We appreciate your suggestions on adding numerical experiments in the revision. We will include that and further improve our paper following your suggestion during revision.
Thank you for your valuable time reviewing our paper! We are glad that we have mainly addressed your concerns and thank you very much for raising your score! 

**Q: Could you explain more about the difference between Assumption 1 and fail state assumption?**

**A:** Sure we are happy to explain more on these assumptions. As noticed by the reviewer, we have discussed in the paper that the vanishing minimal value assumption (Assumption 4.1) is *strictly a more general assumption* than the fail-state condition (Condition B.2 in the Appendix). That being said, the any RMDP satisfying the fail-state assumption also satisfies the vanishing minimal value assumption. But there exist instances that satisfy the vanishing minimal value assumption but do not have a fail state (Remark B.3). To get more intuition on why such instance exists, we notice that the robust value function is the worst case total return over the robust set of transitions. Thus, even if there is no fail state (zero-reward and absorbing), there could exist a worst case transition such that the total return is still zero. That is the intuition behind the example of Remark 4.3. 

We hope this can answer your questions, and we are happy to explain more if there are further confusions or concerns.
Hope you can include some numerical studies in the final version, as you mentioned that the setup in this paper 'is indeed possible and is even a common practice in certain real-world problems.'
Thanks for the detailed explaination. The reviewer's concerns are mainly addressed. I raised my score. One more question: Could you explain more about the difference between Assumption 1 and fail state assumption. I know there is a detailed discussion, while still want more intuitions.
Dear authors,

Thank you for responding to my questions. I will maintain my rating. Good luck.
Dear Reviewer, 

Please engage with the authors. This is the last day a back and forth discussion is possible. 

The AC
Dear Reviewer, 

Please engage with the authors. This is the last day a back and forth discussion is possible. 

The AC
Thank you for your efforts reviewing our paper and your support! We will further improve our paper following your suggestions during revision.
Thank you for your detailed answers. I maintain my score and advocate for acceptance.