Near-Optimal Distributionally Robust Reinforcement Learning with General $L_p$ Norms

Authors: pierre  clavier
ecole  polytechnique
inria laixi shi
‡  caltech
erwan  le pennec
eric  mazumdar
caltech  adam
wierman ‡ caltech
matthieu  geist
§  cohere
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-13 23:37:45

Abstract: To address the challenges of sim-to-real gap and sample efficiency in reinforcement learning (RL), this work studies distributionally robust Markov decision processes (RMDPs) --- optimize the worst-case performance when the deployed environment is within an uncertainty set around some nominal MDP. Despite recent efforts, the sample complexity of RMDPs has remained largely undetermined. While the statistical implications of distributional robustness in RL have been explored in some specific cases, the generalizability of the existing findings remains unclear, especially in comparison to standard RL.  Assuming access to a generative model that samples from the nominal MDP, we examine the sample complexity of RMDPs using a class of generalized $L_p$ norms as the 'distance' function for the uncertainty set, under two commonly adopted $sa$-rectangular and $s$-rectangular conditions. Our results imply that RMDPs can be more sample-efficient to solve than standard MDPs using generalized $L_p$ norms in both $sa$- and $s$-rectangular cases, potentially inspiring more empirical research.
 We provide a near-optimal upper bound and a matching minimax lower bound for the $sa$-rectangular scenarios. For $s$-rectangular cases, we improve the state-of-the-art upper bound and also derive a lower bound using $L_\infty$ norm that verifies the tightness.

Main paper: 
 introduction: 
 Reinforcement learning (RL) [Sutton, 1988] is a popular paradigm in machine learning, particularly noted for its success in practical applications. The RL framework, usually modeled within the context of a Markov decision process (MDP), focuses on learning effective decision-making strategies based on interactions with a fixed environment. However, the work of Mannor et al. [2004] , among others, has highlighted a vulnerability in RL strategies, revealing the sensitivity to inherent shift or estimation errors in the reward and transition probabilities. A specific example of this is when, because of a sim-to-real gap, policies learned in idealized environments fail when deployed in environments with slight changes or adversarial perturbations [Klopp et al., 2017 , Mahmood et al., 2018] .To address this issue, distributionally robust RL, usually formulated as robust MDPs (RMDPs), proposed by Iyengar [2005] and Nilim and El Ghaoui [2005] , have attracted considerable attention. RMDPs are formulated as max-min problems, seeking policies that are resilient to model environment perturbations within a specified uncertainty set. Despite the robustness benefits, solving RMDPs is NP-hard for general uncertainty sets [Nilim and El Ghaoui, 2005] . To overcome this challenge, the rectangularity condition is often adopted so that the uncertainty set can be decomposed as products of independent subsets for each state or state-action pair, denoted as s-rectangular or sa-rectangular assumptions (see Definition 4 and 5). These assumptions facilitate computation traceability of methods such as robust value iteration and robust policy iteration, preserving many structural properties of MDPs [Ho et al., 2021] . The s-rectangularity condition, though with less restrictive structure assumption, impose more challenges for algorithm design, while the sa-rectangularity condition allows for deterministic optimal policies akin to non-robust MDPs [Wiesemann et al., 2013] . Note that dealing with uncertainty in transition kernels is much more difficult than that in rewards [Kumar et al., 2022 , Derman et al., 2021] .The question of sample efficiency is central in RL problems ranging from practice to theory. Although minimax sample efficiency has been achieved for standard MDPs [Azar et al., 2013b , Li et al., 2023c] , this goal in general remains open in RMDPs. Specifically, there exists prior work studying the sample complexity of distributionally robust RL for a few specific divergences such as total variation (T V ) distance, χ 2 divergence, Kullback-Leibler divergence (KL) divergence, and Wasserstein distance (see discussions in Appendix A) [Yang et al., 2022b , Zhou et al., 2021 , Panaganti and Kalathil, 2022] . While such results remain unclear for more general class, such as the general smooth L p norms (see Def. 1). To the best of our knowledge, minimax optimal sample complexity for the full range of uncertainty level has only been achieved for one case -T V distance [Shi et al., 2023] . In this work, we focus on understanding the sample complexity of RMDPs with a general smooth L p that will be defined in Def. 1. This generalized result is appealing for both practice and theory. In practice, numerous applications are based on optimizations or learning approaches that involve general norms beyond those specific cases that have been studied in prior works. Additionally, optimizing L p norm weighted ambiguity sets for robust MDPs has been proposed in the context of RMDPs in Russel et al. [2019] , which justifies our formulation. Theoretically, prior work has characterized the sample complexity of RMDPs for some specific norms have suggested intriguing insights about the statistical implications of distributional robustness in RL. It is interesting to further understand the statistical cost of robust RL in more general scenarios. One area of focus is the contrast between the sample efficiency of solving distributionally robust RL and solving standard RL. In particular, for the specific case of T V distance, Shi et al. [2023] shows that the sample complexity for solving robust RL is at least the same as and sometimes (when the uncertainty level is relatively large) could be smaller than that of standard RL. This motivates the following open question:Is distributionally robust RL more sample efficient than standard RL for some general class of norms (Def. (1)) ?A second question is about the comparisons between the sample complexity of solving s-rectangular RMDPs and that of solving sa-rectangular RMDPs. Note that s-rectangular RMDPs involve more complex optimization problems with additional variables (uncertainty levels for each action) to optimize. This leads to a richer class of optimal policy candidates-stochastic policies in s-rectangular cases, in contrast to the class of deterministic policies for sa-rectangular cases. In addition, existing sample complexity upper bounds for solving s-rectangular RMDPs are larger than that for solving sa-rectangularity [Yang et al., 2022b] for the investigated cases. This motivates the curious question: Does solving s-rectangular RMDPs require more samples than solving sa-rectangular RMDPs with general smooth L p norms defined in Def. 1? Main contributions. In this paper, we address each of the two questions discussed above. In particular, we provide the first sample complexity analysis for RMDPs with general L p norms (cf. Def. 1) under both the sand sa-rectangularity conditions. For convenience, we present detailed comparisons between the prior arts and our results in Table 1 for quick reference and discuss the contributions and their implications as below.• Considering the first question, we illustrate our results in both saand s-rectangular cases in Figure 1 . In the case of sa-rectangularity, we derive a sample complexity upper bound for RMDPs using general smooth L p norms (cf. Theorem 1) in the order of O SA (1-γ) 2 max{1-γ,Cgσ}ε 2 . Here, σ is the uncertainty level/radius of the uncertainty set, and C g > 0 is a positive constant related to the geometry of the norm defined in Def. 1. For classical L p norms, C g ≥ 1 so we can directly relax this constant to 1 to obtain the result in Table 1 . In addition, we provide a matching minimax lower bound (cf. Theorem 2) that confirms the near-optimality of the upper bound for almost full range of the Panaganti and Kalathil [2022] TV Shi et al. [2023] TV Clavier et al. [2023] LpS 2 A (1-γ) 4 ε 2 S 2 A (1-γ) 4 ε 2 × ×SA (1-γ) 3 ε 2 SA σ(1-γ) 2 ε 2 × ×SA (1-γ) 3 ε 2 SA (1-γ) 4 ε 2 SA (1-γ) 3 ε 2 SA (1-γ) 4 ε 2LpSA (1-γ) 3 ε 2 SA σ(1-γ) 2 ε 2 SA (1-γ) 3 ε 2 SA (1-γ) 2 σ mins∥πs∥ * ε 2General Lp [1]SA (1-γ) 3 ε 2 SA σ(1-γ) 2 ε 2 SA (1-γ) 3 ε 2 SA (1-γ) 2 σCg mins∥πs∥ * ε 2Lower bound Yang et al. [2022a] TVSA (1-γ) 3 ε 2 SA(1-γ) σ 4 ε 2 × × Shi et al. [2023] TV SA (1-γ) 3 ε 2 SA σ(1-γ) 2 ε 2 × × This paper Lp SA (1-γ) 3 ε 2 SA σ(1-γ) 2 ε 2 × × This paper L∞ SA (1-γ) 3 ε 2 SA σ(1-γ) 2 ε 2 SA (1-γ) 3 ε 2 SA σ(1-γ) 2 ε 2Table 1 : Comparisons with prior results (up to log terms) regarding finding an ε-optimal policy for the distributionally RMDP, where σ is the radius of the uncertainty set and σ max defined in Theorem 1. uncertainty level. Our results match the near-optimal sample complexity derived in Shi et al. [2023] for the specific case using TV distance, while holding for broader cases using general L p norms. The results rely on a new dual optimization form for sa-rectangular RMDPs and reveal the relationship between the sample complexity and this new dual form -the infinite span seminorm (controlled in Lemma 5), which may be of independent interest.In the case of s-rectangularity, we provide a sample complexity upper bound for solving RMDPs with general smooth L p norms in the order of O SA (1-γ) 2 max{1-γ,Cg mins∥πs∥ * σ}ε 2 with ∥.∥ * the dual norm and σ the radius of the ball in the s-rectangular uncertainty set. This result improves the prior art O SA (1-γ) 4 ε 2 in Clavier et al. [2023] for classical L p -by at least a factor of O 1 1-γ when σ ≲ 1 -γ. Furthermore, we present a lower bound for a representative case with L ∞ norm, which corroborates the tightness of the upper bound. To the best of our knowledge, this is the first lower bound for solving RMDPs with s-rectangularity.• We highlight the technical contributions as below. For the upper bounds, regarding optimization contribution, we derive new dual optimization problem forms for both saand srectangular cases (Lemma 3 and 4), which is the foundation of the covering number argument in finite-sample analysis. From a statistical point of view, a new concentration lemma (See Lemma 8 for dual forms) is introduced to obtain a lower sample complexity than standard RL, controlling the infinite span semi norm of the value function, both for saand srectangular case are derived (See Lemma 5 and 6). For the lower bound, the technical contributions are mainly in s-rectangular cases, which involves entire new challenges compared to sa-rectangularity case: the optimal policies can be stochastic and hard to be characterized as a closed form, compared to the deterministic one in sa-rectangular cases. Therefore, we construct new hard instances for s-rectangular cases that is distinct from those used in sa-rectangular cases or standard RL.• Considering the second question, as illustrated in Figure 1 , our results highlight that robust RL is at least the same as and sometimes can be more sample-efficient to solve than standard RL for general smooth L p norms (cf. Def. 1). This insight is of significant practical importance and serves to provide crucial motivation for the use and study of distributionally robustness in RL. Notably, robust RL does not only reduce the vulnerability of RL policy to estimation errors and sim-to-real gaps, but also leads to better data efficiency. In terms of comparing the statistical implications of saand srectangularity, our results show that solving s-rectangular RMDPs is not harder than solving sa-rectangular RMDPs in terms of sample requirement (See Theorem 3 and Figure 2 , Right). 
problem formulation: robust markov decision processes: 
 In this section, we formulate distributionally robust Markov decision processes (RMDPs) in the discounted infinite-horizon setting, introduce the sampling mechanism, and describe our goal.Figure 1 : Left: Sample complexity results for RMDPs with saand s-rectangularity with L p with comparisons to prior arts [Shi et al., 2023] (for L 1 norm, or called total variation distance) and [Clavier et al., 2023] ; Right: The data and instance-dependent sample complexity upper bound of solving s-rectangular dependency RMDPs with L p norms.A discounted infinite-horizon MDP is represented by M = (S, A, γ, P, r), where S = {1, • • • , S} and A = {1, • • • , A} are the finite state and action spaces, respectively, γ ∈ [0, 1) is the discounted factor, P : S × A → ∆(S) denotes the probability transition kernel, and r : S × A → [0, 1] is the immediate reward function, which is assumed to be deterministic. Moreover, we assume that the reward function is bounded in (0, 1) without loss of generality of the results due to the variance reward invariance. Finally we denote 1 A or 1 S the unitary vector of respectively dimension A or S. Moreover, e s is the standard unitary vector supported on s. The policy we are looking for is denoted by π : S → ∆(A), which specifies the probability of action selection over the action space in any state. Note that if the policy is deterministic in the sa-rectangular case, we overload the notation and refer to π(s) as the action selected by the policy π in state s. Finally, to characterize the cumulative reward, the value function V π,P for any policy π under the transition kernel P is defined by ∀s ∈ S V π,P (s) := E π,P ∞ t=0 γ t r s t , a t s 0 = s .(1)The expectation is taken over the randomness of the trajectory {s t , a t } ∞ t=0 generated by executing the policy π under the transition kernel P , such that a t ∼ π(• | s t ) and s t+1 ∼ P (• | s t , a t ) for all t ≥ 0. In the same way, the Q function Q π,P associated with any policy π under the transition kernel P is defined using expectation taken over the randomness of the trajectory under policy π asEQUATIONDistributionally robust MDPs. We consider distributionally robust MDPs (RMDPs) in the discounted infinite-horizon setting, denoted by M rob = {S, A, γ, U σ ∥•∥ (P 0 ), r}, where S, A, γ, r are the same sets and parameters as in standard MDPs. The main difference compared to standard MDPs is that instead of assuming a fixed transition kernel P , it allows the transition kernel to be arbitrarily chosen from a prescribed uncertainty set U σ ∥•∥ (P 0 ) centered around a nominal kernel P 0 : S × A → ∆(S), where the uncertainty set is specified using some called L p smooth norm denoted ∥•∥ defined in of radius σ > 0 defined in 1. Definition 1 (General smooth L p norms and dual norms). A norm ∥ • ∥ is said to be a general smoothL p , norm , p > 1 if • for all x ∈ R n , ∥x∥ := ∥x∥ p,w = ( n k=1 w k (|x k |) p ) 1/p for some w ∈ R n+ , being an arbitrary positive vector.• it is twice continuously differentiable Rudin et al. [1964] with the supremum of the Hessian Matrix over the simplex C S = sup x∈∆ S ∇ 2 ∥x∥ 2 , where ∥•∥ 2 here is the spectral norm.Finally, we denote the dual norm of ∥•∥ as ∥•∥ * s.t. ∥y∥ * := max x x T y : ∥x∥ ≤ 1. Moreover, for any metric ∥•∥, we define C g C g := 1/ min s ∥e s ∥ where e s ∈ R S is the standard basis vector with only 1 at the s-th entry, otherwise 0.Note that the quantity C S exists, as the Hessian of a C 2 functional is continuous and because the simplex is a compact set, so by Extreme Value Theorem Rudin et al. [1964] , C S is finite. For example, considering L p norms with any p ≥ 2, C S is bounded by (p -1)S 1/q . (See ( 154) ) This definition is general and includes L p norms [Rudin et al., 1964] for any p ≥ 2 and all rescaled and weighted norms. Moreover, we could extend our results to a larger set than the one of the norms defined in Def. 1, where the further discussion can be found in Appendix B. However, it does not include divergences such as KL and χ 2 . Not that the case of T V which is not C 2 smooth is treated independently with different arguments in the proof but has the same sample complexity.In particular, given the nominal transition kernel P 0 and some uncertainty level σ, the uncertainty set-with arbitrary smooth L p norm metric ∥ ∥ : R S × → R + in sa rectangular case or from R S×A in the s-rectangular case, is specified asEQUATIONEQUATIONwhere we denote a vector of the transition kernel P or P 0 at state-action pair (s, a). In other words, the uncertainty is imposed in a decoupled manner for each state-action pair, obeying the so-called sa-rectangularity [Zhou et al., 2021 , Wiesemann et al., 2013] . More generally, we define s-rectangular MDPs asU σ ∥•∥ (P ) = ⊗ s U s, σ ∥•∥ (P s ), for the general smooth L p norm ∥•∥.The uncertainty is imposed in a decoupled manner for each state pair, and a fixed budget given a state for all action is defined. To get a similar meaning for the radius of the ball between sa-rectangular and s-rectangular assumptions, we need to rescale the radius depending on the norm like in Yang et al. [2022b] . The suncertainty set is then defined using the rescaled radius σ asEQUATIONEQUATION)where 1 A ∈ R A denotes the unitary vector. For the specific case of respectively L 1 ,L p and L ∞ norm, σ is equal to |σA|, σ|A| 1/p and σ. Note that this scaling allows for a fair comparison between saand s-rectangular MDPs. In RMDPs, we are interested in the worst-case performance of a policy π over all the possible transition kernels in the uncertainty set. This is measured by the robust value function V π,σ and the robust Q-function Q π,σ in M rob , defined respectively as ∀(s, a) ∈ S × A V π,σ (s) := infEQUATIONSimilarly for s-rectangularity, the value function is denotedV π,σ s (s) := inf P ∈U s, σ ∥•∥ (P 0 ) V π,P (s).Optimal robust policy and robust Bellman operator. As a generalization of properties of standard MDPs in the sa-rectangular robust case, it is well-known that there exists at least one deterministic policy that maximizes the robust value function (resp. robust Q-function) simultaneously for all states (resp. state-action pairs) [Iyengar, 2005, Nilim and El Ghaoui, 2005] but not in the s-rectangular case. Therefore, we denote the optimal robust value function (resp. optimal robust Q-function) as V ⋆,σ (resp. Q ⋆,σ ), and the optimal robust policy as π ⋆ , which satisfy ∀(s, a) ∈ S × AEQUATIONA key concept in RMDPs is a generalization of Bellman's optimality principle, encapsulated in the following robust Bellman consistency equation (resp. robust Bellman optimality equation):EQUATIONEQUATIONfor the sa-rectangular case and same equation replacing P 0 s,a by P 0 s and σ by σ. The robust Bellman operator [Iyengar, 2005, Nilim and El Ghaoui, 2005] EQUATIONfor sa-rectangular MDPs. Given that Q ⋆,σ is the unique-fixed point of T σ one can recover the optimal robust value function and Q-function using a procedure termed distributionally robust value iteration (DRV I). Generalizing the standard value iteration, DRV I starts from some given initialization and recursively applies the robust Bellman operator until convergence. As has been shown previously, this procedure converges rapidly due to the γ-contraction property of T σ with respect to the L ∞ norm [Iyengar, 2005, Nilim and El Ghaoui, 2005] . 
distributionally robust value iteration: 
 Generative model-based sampling. Following Zhou et al. [2021] , Panaganti and Kalathil [2022] , we assume access to a generative model or a simulator [Kearns and Singh, 1999] , which allows us to collect N independent samples for each state-action pair generated based on the nominal kernelP 0 : ∀(s, a) ∈ S × A, s i,s,a i.i.d ∼ P 0 (• | s, a), i = 1, 2, • • • , N.The total sample size is, therefore, N SA. We consider a model-based approach tailored to RMDPs, which first constructs an empirical nominal transition kernel based on the collected samples and then applies distributionally robust value iteration (DRVI) to compute an optimal robust policy. As we decouple the statistical estimation error and the optimization error, we exhibit an algorithm that can achieve arbitrary small error ϵ opt in the empirical MDP defined as an empirical nominal transition kernel P 0 ∈ R SA×S that can be constructed on the basis of the empirical frequency of state transitions, i.e. ∀(s, a) ∈ S × AEQUATIONwhich leads to an empirical RMDP M rob = {S, A, γ, U σ ∥•∥ ( P 0 ), r}. Analogously, we can define the corresponding robust value function (resp. robust Q-function) of policy π in M rob as V π,σ (resp. Q π,σ ) (cf. ( 8)). In addition, we denote the corresponding optimal robust policy as π ⋆ and the optimal robust value function (resp. optimal robust Q-function) as V ⋆,σ (resp. Q ⋆,σ ) (cf. ( 9)), which satisfies the robust Bellman optimality equation ∀(s, a) ∈ S × A:EQUATIONEquipped with P 0 , we can define the empirical robust Bellman operatorT σ as ∀(s, a) ∈ S × A T σ (Q π )(s, a) := r(s, a) + γ inf P∈U sa,σ ∥•∥ ( P 0 s,a )PV,with V (s) := max π Q π (s, a). The aim of this work is given the collected samples, to learn the robust optimal policy for the RMDP w.r.t. some prescribed uncertainty set U σ (P 0 ) around the nominal kernel using as few samples as possible. Specifically, given some target accuracy level ε > 0, the goal is to seek an ε-optimal robust policy π obeyingEQUATIONEQUATION)This formulation allows plugging any solver of RMDPs in this bound, for instance, the distributionally robust value iteration (DRVI) algorithm detailed in Appendix G. 
theoretical guarantees: 
 In this section, we present our main results characterizing the sample complexity of solving RMDPs with sa-and s-rectangularity. Additionally, we discuss the implications of our results for the comparisons between standard and robust RL, and for comparisons between saversus s-rectangularity.To begin, we consider the RMDPs with sa-rectangularity with general norms. We first provide the following sample complexity upper bound for certain oracle planning algorithms, whose proof is postponed to Appendix D.2. Technically, we derive two new dual forms for RMDPs problems using arbitrary norms in Lemmas 3 and 4 for respectively saand s-rectangular RMDPS. In these dual forms, a central quantity denoted sp(.) * , representing the dispersion of the value function, appears and is the dual span semi-norm associated with the considered general L p norm ∥.∥ defined in 1 in the initial primal problem. The main challenge in this analysis is to derive a tight upper bound on this quantity in Lemmas ( 5) and ( 6), leading to the following sample complexity.Theorem 1 (Upper bound for sa-rectangularity). Consider the uncertainty set U sa,σ ∥•∥ (•) associated with arbitrary L p smooth norm ∥ • ∥ defined in 1. We denote σ max := max p1,p2∈∆(S) ∥p 1 -p 2 ∥ as the accessible maximal uncertainty level. Consider any δ ∈ (0, 1), discount factor γ ∈ 1 4 , 1 , and uncertainty level σ ∈ (0, σ max ]. Let π be the output policy of some oracle planning algorithm with optimization error ε opt introduced in (15). With introduced in 1, one has with probability at least 1-δ,∀s ∈ S : V ⋆,σ (s) -V π,σ (s) ≤ ε + 8ε opt 1 -γ (16)for any ε ∈ (0, 1/ max{1 -γ, σC g }], as long as the total number of samples obeysN SA ≳ c 1 SA (1 -γ) 2 max{1 -γ, C g σ}ε 2 + c 2 SAC S ∥1 S ∥ * (1 -γ) 2 ϵ (17)with c 1 , c 2 , c 3 a universal positive constant. For a sufficiently small level of accuracy ϵ ≤ (max{1 -γ, C g σ})/(C S ∥1 S ∥), the sample complexity isEQUATION)Note that this result is also true for T V without the geometric smooth term depending on C S . Considering L p norms, C g ≥ 1 and C S ≤ S 1/q (p -1). In Theorem 1, we introduce the following minimax-optimal lower bound to verify the tightness of the above upper bound; a proof is provided in Appendix E.Theorem 2 (Lower bound for sa-rectangularity). Consider the uncertainty set U sa,σ ∥•∥ (•) associated with arbitrary L P norm ∥ • ∥ defined in 1. We denote σ max := max p1,q1∈∆(S) ∥p 1 -p 2 ∥ as the accessible maximal uncertainty level. Consider any tuple (S, A, γ, σ, ε), where γ ∈ 1 2 , 1 , σ ∈ (0, σ max (1 -c 0 )] with 0 < c 0 ≤ 1 8 being any small enough positive constant, and ε ∈ 0, c0 256(1-γ) . We can construct two infinite-horizon RMDPs M 0 , M 1 such that giving a dataset with N independent samples for each state-action pair over the nominal transition kernel (for either M 0 or M 1 respectively), one hasinf π max M∈{M0,M1} P M max s∈S V ⋆,σ (s) -V π,σ (s) > ε ≥ 1 8 ,where the infimum is taken over all estimators π, P 0 (resp. P 1 ) are the probability when the RMDP is M 0 (resp. M 1 ), as long as, for c 7 is a universal positive constant,EQUATION)• Near minimax-optimal sample complexity with general L p norms. Recall that Theorem 1 shows that the sample complexity upper bound of oracle algorithms for RMDPs is in the order of O(1-γ) 2 max{1-γ,Cgσ}ε 2 . Combined with the lower bound in Theorem 2, we observe that the above sample complexity is near minimax-optimal, in almost the full range of uncertainty.• Solving RMDPs with general L p norms can be easier than solving standard RL. Recall that the sample complexity of solving standard RL with a generative model [Agarwal et al., 2020 , Li et al., 2024 , Azar et al., 2013a] is: O SA (1-γ) 3 ε 2 .Comparing this with the sample complexity in (18), it highlights that solving robust MDPs (cf. ( 18)) using any norm as the divergence function for the uncertainty set is not harder than (and is sometimes easier than) solving standard RL (cf. (4.1)). Specifically, when the uncertainty level is small σ ≲ 1 -γ, the sample complexity of solving robust MDPs matches that of standard MDPs. While when the uncertainty level is relatively larger 1 -γ ≲ σ ≤ σ max , the sample complexity of solving robust MDPs is smaller than that of standard MDPs by a factor or σ 1-γ , which goes to 1 1-γ when σ = O(1).• Comparisons with prior arts. In Figure 1 , we illustrate the comparisons with two state-of-thearts [Clavier et al., 2023 , Shi et al., 2023] which use some divergence functions belonging to the class of general norms considered in this work. In particular, Shi et al. [2023] achieved the state-of-the-art minimax-optimal sample complexity O(1-γ) 2 max{1-γ,σ}ε 2 for specific L 1 norm (or called total variation distance). In this work, we attain near minimax-optimal sample complexity for any general norm (including L 1 ) which matches the one in Shi et al. [2023] when narrowing down to L 1 norm. Note that in T V case, C g = 1. This reveals that the finding of robust MDPs can be easier than standard MDPs [Shi et al., 2023] in terms of sample requirement does not only hold for L 1 norm, but for any general norm. In addition, compared to Clavier et al. [2023] which focuses on L p norms for any 1 ≤ p ≤ ∞: when 1 -γ ≲ σ ≤ σ max , we improve the sample complexityO( SA (1-γ) 4 ε 2 ) to O( SA (1-γ) 2 σε 2) by at least a factor of 1 1-γ ; otherwise, we match the results in Clavier et al. [2023] .• Burn-in Condition, C g factor and T V case : In Th. 1 and 3 we need a sufficiently small level of accuracy ϵ ≤ (max{1 -γ, C g σ})/(C s ∥1 S ∥), to obtain the sample complexity. This type of condition is usual in MDPS analysis Shi et al. [2022] and is equivalent to burn in term. Moreover, the quantity C S exists (see 1) and for example, considering L p norms, C S is bounded by S 1/q . (See ( 154)) and the product C S ∥1 S ∥ is upper bounded by S for L 2 norm. Moreover, note that our theorem for the smooth norm is also true for T V which is not C 2 and has the same complexity as (Shi et al. [2023] . In this case, the burn-in condition is not needed. (See Lemma D.3.3). Finally, the factor C g = 1/ min s ∥e s ∥ is norm dependent and depends on how big the vector e s0 is in the considered norm. Note for classical L p this quantity is bigger than 1, which reduces the sample complexity.To continue, we move on to the case when the uncertainty set is constructed under s-rectangularity smooth norm. The following theorem presents the sample complexity upper bound for learning an ϵ-optimal policy for RMDPs with s-rectangularity. A proof is shown in Appendix D.2.Theorem 3 (Upper bound for s-rectangularity). Consider the uncertainty set U s, σ ∥•∥ (•) with s-rectangularity. Consider any discount factor γ ∈ 1 4 , 1 , the rescaled uncertainty level σ = σ ∥1 A ∥, and denote σmax := ∥1 A ∥ max p1,p2∈∆(S) ∥p 1 -p 2 ∥ and δ ∈ (0, 1). Let π be the output policy of an arbitrary optimization algorithm with error ε opt . , with probability at least 1 -δ, one has for any ε ∈ (0, 1/ max{1 -γ, C g min s ∥π s ∥ * σ}], ∀s ∈ S : V ⋆, σ (s) -V π, σ (s) ≤ ε + 8εopt 1-γ as long as the total number of samples obeysN SA ≳ c4SA (1 -γ) 2 ε 2 min 1 max{1 -γ, Cgσ} , 1 σCg min s∈S ∥π * s ∥ * ∥1A∥ , ∥πs∥ * ∥1A∥ + c5SACS ∥1S∥ * (1 -γ) 2 ϵ (20)For a sufficiently small accuracy, ϵ ≤ (max{1 -γ, C g σ})/(C s ∥1 S ∥) the sample complexity isEQUATIONwhere πs ∈ ∆ A denote the policy of the empirical RMPDs at state s, π * s ∈ ∆ A the optimal policy given s of the true RMPDs, ∥.∥ * the dual norm and c 4 , c 5 , c 6 are universal constant. Note that this result is also true for T V without the term depending on smoothness C S . In addition, we provide the lower bounds for a representative divergence function -L ∞ norm in the following. Note that for classical L p , C S = S 1/q (p-1) and C g can be lower bounded by 1. A proof is provided in Appendix F.Theorem 4 (Lower bound for s-rectangularity). Consider the uncertainty set U s, σ L∞ (•) associated with the L ∞ norm. Consider any tuple (S, A, γ, σ, ε) and 0 < c 0 ≤ 1 8 being any small enough positive constant, where γ ∈ 1 2 , 1 , and ε ∈ 0, c0 256(1-γ) . Correspondingly, we denote the accessible maximal uncertainty level for U s, σ L∞ (•) as σ ∞ max := max p1,p1∈∆(S) A ∥p 1 -p 2 ∥ ∞ = 1. Then we can construct a collection of infinite-horizon RMDPs M L∞ defined by the uncertainty set with U s, σ L∞ (•) so that for any σ ∈ (0, σ ∞ max (1 -c 0 )], and any dataset with in total N all independent samples for all state-action pairs over the nominal transition kernel (for any RMDP inside M L∞ ), one hasEQUATIONprovided that for c 8 is a universal positive constant,EQUATION)with P M the probability when the RMDP is M, and the infimum is taken over all estimators π. Now we can present some implications of Theorem 3 and Theorem 4.• Robust MDPs with s-rectangularity are at least as easy as sa-rectangularity. Theorem 3 shows that the sample complexity of solving RMDPs with s-rectangularity does not exceed the order of O(1-γ) 2 max{1-γ,Cgσ}ε 2 . This matches the sample complexity for sa-rectangularity (cf. ( 18)) and indicates that although s-rectangular RMDPs are of a more complicated formulation, solving s-rectangular RMDPs is at least as easy as solving sa-rectangular RMDPs in terms of the sample complexity. In addition to the worst-case sample complexity upper bound, Theorem 3 also provides a data and instance-dependent sample complexity upper bound for s-rectangular RMDPs (cf. in ( 20)).Taking the divergence function ∥ • ∥ = L p for instance, the data and instance-dependent sample complexity upper bound is   O SA (1-γ) 2 ε 2 1 max{1-γ,σ} if π s (a | s) = π * s (a | s) = 1 A , ∀(s, a) ∈ S × A O SA (1-γ) 2 ε 2 1 max{1-γ,σA 1/p } if ∥ π s (• | s)∥ 0 = ∥π * s (• | s)∥ 0 = 1, ∀s ∈ S.where ∥.∥ 0 corresponds to the total number of nonzero elements in a vector.The intuition beyond this theorem is that when the policy becomes proportional to uniform, the uncertainty budget of the s-rectangular MDPs is equally spread into all actions, and we retrieve the sa-rectangular case.When the policy becomes deterministic, all the uncertainty budget concentrates on one action. In this case, most of the actions are not robust except one, and the problem is simpler than classical MDP for this only specific action. An illustration of this result can be found in Fig. 2 .• Comparisons with prior arts. In Figure 1 , we illustrate the comparisons with Clavier et al.[2023] which use L p norms functions belonging to the class of general norms considered in this work. We do not compare in this section to Yang et al. [2022a] as it is not anymore state-of-the-art with regard to the work of Clavier et al. [2023] . In particular, the latest achieves in the s-rectangular case at sample complexity of O(1-γ) 3 ε 2 in the regime where σ ≲ 1 -γ. In this regime, our result is the same but more general but in the regime where σ ≳ 1 -γ, they achieve sample complexity ofO SA (1-γ) 4 ε 2 which is bigger than our result O SA (1-γ) 2 max{1-γ,σ}ε 2 by a factor at least 1 1-γ . 
conclusion: 
 This work refined sample complexity bounds to learn robust Markov decision processes when the uncertainty set is characterized by an general L p metric, assuming the presence of a generative model. Our findings not only strengthen the current knowledge by improving both the upper and lower bounds, but also highlight that learning s-rectangular MDPs is less challenging in terms of sample complexity compared to classical sa-rectangular MDPs. This work is the first to provide results with a minimax bound, as prior results concerning s-rectangular cases were not minimax optimal. Additionally, we have established the minimax sample complexity for RMDPs using a general L p norm, demonstrating that it is never larger than that required for learning standard MDPs. Our research identifies potential avenues for future work, such as exploring the characterization of tight sample complexity for RMDPs under a broader family of uncertainty sets, such as those defined by f -divergence. It would be highly desirable for a more unified theoretical foundation, as the distance between probability measures is more natural to define using divergence. Moreover, it would be interesting to focus on the finitehorizon Setting and linear setting, as our current analytical framework opens the door for potential extensions to address finite-horizon RMDPs. Such an extension would contribute to a more comprehensive understanding of tabular cases. Finally, the case of linear MDPs would be interesting to explore.Huan Zhang, Hongge Chen, Duane Boning, and Cho-Jui Hsieh. Robust reinforcement learning on state observations with learned optimal adversary. arXiv preprint arXiv:2101.08452, 2021.Zihan Zhang, Yuan Zhou, and Xiangyang Ji. Almost optimal model-free reinforcement learning via reference-advantage decomposition. Advances in Neural Information Processing Systems, 33, 2020b.Zhengqing Zhou, Qinxun Bai, Zhengyuan Zhou, Linhai Qiu, Jose Blanchet, and Peter Glynn. Finite-sample regret bound for distributionally robust offline tabular reinforcement learning. In International Conference on Artificial Intelligence and Statistics, pages 3331-3339. PMLR, 2021. 
 
 Appendix: Here we provide additional discussion of related work that could not be fit into the main paper due to space considerations. We limit our discussions to the tabular setting with finite state and action spaces provable RL algorithms. , 1999 , Beck and Srikant, 2012 , Li et al., 2022a , Chen et al., 2020 , Azar et al., 2013b , Sidford et al., 2018 , Agarwal et al., 2020 , Li et al., 2023a ,b, Wainwright, 2019] and the online setting via both in PAC-base or regret-based analyses [Jin et al., 2018 , Bai et al., 2019 , Li et al., 2021 , Zhang et al., 2020b , Dong et al., 2019 , Jin et al., 2020 , Li et al., 2023c , Jafarnia-Jahromi et al., 2020 , Yang et al., 2021] and finally offline setting [Rashidinejad et al., 2021 , Xie et al., 2021 , Yin et al., 2021 , Shi et al., 2022 , Li et al., 2022b , Jin et al., 2021 , Yan et al., 2022] .Robustness in reinforcement learning. Reinforcement learning has had notable achievements but has also exhibited significant limitations, particularly when the learned policy is susceptible to deviations in the deployed environment due to perturbations, model discrepancies, or structural modifications. To address these challenges, the idea of robustness in RL algorithms has been studied. Robustness could concern uncertainty or perturbations across different Markov Decision Processes (MDPs) components, encompassing reward, state, action, and the transition kernel. Moos et al. [2022] gives a recent overview of the different work in this field.The distributionally robust MDP (RMDP) framework has been proposed [Iyengar, 2005] to enhance the robustness of RL has been proposed. In addition to this work, various other research efforts, including, but not limited to, Zhang et al. [2020a Zhang et al. [ , 2021]] , Han et al. [2022] , Clavier et al. [2022] , Qiaoben et al. [2021] , explore robustness regarding state uncertainty. In these scenarios, the agent's policy is determined on the basis of perturbed observations generated from the state, introducing restricted noise, or undergoing adversarial attacks. Finally, robustness considerations extend to uncertainty in the action domain. Works such as Tessler et al. [2019] , Tan et al.[2020] consider the robustness of actions, acknowledging potential distortions introduced by an adversarial agent.Given the focus of our work, we provide a more detailed background on progress related to distributionally robust RL. The idea of distributionally robust optimization has been explored within the context of supervised learning [Rahimian and Mehrotra, 2019 , Gao, 2020 , Duchi and Namkoong, 2018 , Blanchet and Murthy, 2019] and has also been extended to distributionally robust dynamic programming and Distributionally Robust Markov Decision Processes (DRMDPs) such as in [Iyengar, 2005 , Xu and Mannor, 2012 , Wolff et al., 2012 , Kaufman and Schaefer, 2013 , Ho et al., 2018 , Smirnova et al., 2019 , Ho et al., 2021 , Goyal and Grand-Clement, 2022 , Derman and Mannor, 2020 , Tamar et al., 2014 , Badrinath and Kalathil, 2021] . Despite the considerable attention received, both empirically and theoretically, most previous theoretical analyses in the context of RMDPs adopt an asymptotic perspective [Roy et al., 2017] or focus on planning with exact knowledge of the uncertainty set [Iyengar, 2005 , Xu and Mannor, 2012 , Tamar et al., 2014] The introduction of an R-contamination uncertainty set Wang and Zou [2021] , has been proposed to tackle a robust Q-learning algorithm for the online setting, with guarantees analogous to standard RL. Finally, the finite-horizon scenario has been studied by Xu et al. [2023] , Dong et al. [2022] with finitesample complexity bounds for (RMDPs) using TV and χ 2 divergence. More broadly, other related topics have been explored, such as the iteration complexity of policy-based methods [Li et al., 2022c , Kumar et al., 2023] , and regularization-based robust RL [Yang et al., 2023] . Finally, Badrinath and Kalathil [2021] examined a general sa-rectangular form of the uncertainty set, proposing a model-free algorithm for the online setting with linear function approximation to address large state spaces.B Further discussions of Theorem 1 and Theorem 3 = |λ| ∥x∥ ∀x ∈ R n , λ ∈ R) with norms of the form x → ϕ -1 ( n k=1 , ϕ(|x k |)) with ϕ a convex incising function such as the norm is still positive, definite positive. Choosing ϕ(x) = x p leads to the L p norms.• Assumptions on γ in Theorems 1 and 3, and Assumptions on γ for lower bound. When γ is small (e.g., γ ∈ (0, 1 2 ] leads to the effective horizon length is at most 2), the sequential structure almost disappears and is much less of interest for RL community. So people Li et al. [2023b] Yan et al. [2023] usually focus on reasonable range γ ∈ (c, 1) for some small positive constant c, such as γ ∈ [ 1 2 , 1). However, the theorems can be directly extended to a broader range of γ ∈ (c, 1) along with c as small as desired so that almost cover the full range (0, 1).• Why final results on s depend on π? Theorem 3 is π data dependent which is randomness-dependent measure. However, taking the minimum of this quantity leads to the same bound as is sa-rectangular, so to illustrate that it is possible to get tighter bounds for s-rectangular with instance-dependent RMDPs, we decide to write also randomness-dependent quantity, while the less tight upper bound is written also in the theorem, taking the first term in the min operator in (21).• Why our results are still true for T V ? Theorems 1 and 3 are stated for C 2 smooth norms, however, our result is still true for T V which is not C 2 as in this specific case, the dual of the optimization problem becomes a 1-dimensional problem. In this case in the main concentration lemma 8, the additional term involving smoothness term denoted C S is not present and the bound is simpler as is not required this additional term.• Why burn-in or sufficiently small ϵ condition is not too restrictive? The burn-in term in Th. 1 and 3 is proportional to 1/ϵ where the "sample complexity" term is proportional to 1/ϵ 2 . The smooth term depending on C S or burn-in is then not too large for sufficiently small ϵ compared to the other term, which will give final sample complexity.• Why this is not extendable to f -divergence currently? The f-divergence as a distinct family of divergence is beyond the scope of this paper. Current proof for arbitrary norms cannot be directly extended since the key phenomenon of shrinking range of the robust value function has not been verified for f -divergence yet, while it is promising as an interesting future direction.These quantities appear in the dual formulation of the robust optimization problem and more preciously the dual span semi norm sp(.) * note that for L 2 , we retrieve the classical mean with the definition of ω) With slight abuse of notation, we denote 0 (resp. 1) as the all-zero (resp. all-one) vector. We then introduce the notation [T ] := {1, • • • , T } for any positive integer T > 0. Then, for all 1 ≤ i ≤ n, for two vectors x = [x i ] 1≤i≤n and y = [y i ] 1≤i≤n , the notation x ≤ y (resp. x ≥ y) means x i ≤ y i (resp. x i ≥ y i ) . Finally, for any vector x, the notation is overloaded by lettingx •2 = x(s, a) 2 (s,a)∈S×A (resp. x •2 = x(s) 2 s∈S ), Finally, we drop the subscript ∥.∥ to writeU σ ∥.∥ (•) = U σ (•)for both saand srectangular assumptions such that we write uncertainty set in the for sa-rectangular case U sa,σ (.) or U s, σ (.) in the s-rectangular assumptions.Matrix and Vector Notations. We define the following notation.• r ∈ R SA the reward function, such that r (s,a) = r(s, a) for all (s, a) ∈ S × A.• P 0 ∈ R SA×S the nominal transition kernel matrix using P 0 s,a as the (s, a)-th row. • P 0 ∈ R SA×S the estimated nomimal transition kernel matrix with P 0 s,a as the (s, a)-th row. • Π π ∈ {0, 1} S×SA the projection matrix associated with a policy πEQUATION)where1 ⊤ π(1) , 1 ⊤ π(2) , . . . , 1 ⊤ π(S) ∈ R A are simplex vector such as 1 ⊤ π(1) = (π(a 1 |s 1 ), π(a 2 |s 1 ), ..., π(a A |s 1 )).• The two matrices P V ∈ R SA×S , P V ∈ R SA×S represent the probability transition kernel in the uncertainty set that leads to the worst-case value for any vector V ∈ R S . Moreover, the quantities P V s,a (resp. P V s,a ) stands for the (s, a)-th row of the transition matrix P V (resp. P V ). In sa-rectangular case , the (s, a)-th rows of these transition matrices are defined as P V s,a = argmin P∈U sa,σ (P 0 s,a ) PV, and P V s,a = argmin P∈U sa,σ ( P 0 s,a ) PV. (25a) Moreover, the shorthand notation defined below is usedEQUATIONEQUATIONEQUATIONEQUATIONIn the following, we define the corresponding probability transition matrices which are denoted by P π,V ∈ R SA×S , P π, V ∈ R SA×S , P π,V ∈ R SA×S and P π, V ∈ R SA×S .• Using the projection over π, the matricesP π ∈ R S×S , P π ∈ R S×S , P π,V ∈ R S×S , P π, V ∈ R S×S , P π,V ∈ R S×S and P π, V∈ R S×S represent probability transition matrices w.r.t. policy π.P π := Π π P 0 , P π := Π π P 0 , P π,V := Π π P π,V , P π, V := Π π P π, V , P π,V := Π π P π,V , andEQUATIONFor s-rectangular, we will use the same notation for these transition matrices. Finally, we denote P π s as the s-th row of the transition matrix P π .• r π ∈ R S is the reward function restricted to the actions chosen by π, r π = Π π r.• Var P (V ) ∈ R SA is the variance for a given transition kernel P ∈ R SA×S and vector V ∈ R S , we denote the (s, a)-th row of Var P (V ) as Var P (s, a) := Var Ps,a (V ).For any norm smooth ∥.∥ introduced in 1, we define the span semi norm as Definition 2 (Span semi norm). Given any norm ∥ • ∥, we define the span semi norm as: sp(x) = min ω∈R ∥v -ω1∥ and the generalized mean as ω(x) := arg min ω∈R ∥x -ω1∥.Let vector P ∈ R 1×S and vector V ∈ R S , we define the varianceVar P (V ) := P (V • V ) -(P V ) • (P V ).(28) The following lemma bounds the Lipschitz constant of the variance function. Lemma 1. (Shi et al. [2023] EQUATION)Lemma 2. [Panaganti and Kalathil, 2022, Lemma 6 ] Consider any δ ∈ (0, 1). For any fixed policy π and fixed value vector V ∈ R S , one has with probability at least 1 -δ,Var P π (V ) -Var P π (V ) ≤ 2∥V ∥ 2 ∞ log( 2SA δ ) N 1.We define the robust MDP M rob = {S, A, γ, U σ ( P 0 ), r} based on the estimated nominal distribution P 0 in (11). Then, we denote the associated robust value function (resp. robust Q-function) are V π,σ (resp. Q π,σ ) qnd we can notice that that Q ⋆,σ is the unique-fixed point of T σ (•) (see Lemma C.3), the empirical robust Bellman operator constructed using P 0 . Finally, similarly to (9), for M rob , the Bellman's optimality principle gives the following robust Bellman consistency equation (resp. robust Bellman optimality equation) for sa-rectangular assumptions:EQUATIONEQUATIONUsing matrix notation, we can write the robust Bellman consistency equations asEQUATIONwhich implyEQUATIONwhere (i) and (ii) hold by the definitions in ( 24), ( 25) and (26). For s-rectangular, we can define the same notation, removing a subscript:EQUATIONThe robust Bellman operator (cf. ( 10)) shares the γ-contraction property of the standard Bellman operator as:EQUATION)It can be also shown that, Q ⋆,σ is the unique fixed point ofT σ (•) obeying 0 ≤ Q ⋆,σ (s, a) ≤ 1 1-γ for all (s, a) ∈ S × A.One of the main contributions is to derive the dual form of optimization problem using arbitrary norms. These lemma take ideas from Iyengar [2005] and are adapted to arbitrary norms and not only T V distance.Dual equivalence of the robust Bellman operator. Fortunately, the robust Bellman operator can be evaluated efficiently by resorting to its dual formulation, and this idea is central in all proofs for RMPDs. Dual formulation of RMDPs have been introduced in [Iyengar, 2005] but the proof was done uniquely for the T V and the χ 2 case. Before continuing, for any V ∈ R S , we denote [V ] α as its clipped version by some non-negative vector α, namely,EQUATIONDefining the gradient of P → ∥P ∥ as ∇ ∥P ∥, λ > 0, a positive scalar and ω is the generalized mean defined as the argmin in the definition of the span semi norm in Def.2, we derive two optimization lemmas.Lemma 3 (Strong duality using norm ∥•∥ in the sa-rectangular case.). Consider any probability vector P ∈ ∆(S) and any fixed uncertainty level σ, we abbreviate the notation of the uncertainty set U sa,σ ∥.∥ (P ) (cf.(3)) as U sa,σ (P ). For any vector V ∈ R S obeying V ≥ 0, recalling the definition ofEQUATION)where sp() * is defined in Def..2. Here, the two auxiliary variational family A λ,ω P , M λ,ω P are defined as below:EQUATION) (40)For L 1 or T V , case , the vector α λ,ω P reduces to a 1 dimensional scalar such as α ∈ [0, 1/(1 -γ)].Proof.inf P∈U sa,σ (P ){P:P∈∆s,∥P-P∥≤σ}s ′ P(s ′ )V (s ′ ) = PV + inf {y:∥y∥≤σ,1y=0,y≥-P } s ′ y(s ′ )V (s ′ )where we use the change of variable y(s ′ ) = P(s ′ ) -P(s ′ ) for all s ′ ∈ S. Then the Lagrangian function of the above optimization problem can be written as follows:EQUATIONEQUATION)where µ ∈ R S + , ν ∈ R are Lagrangian variables, (a) is true using the equality case of Cauchy-Swartz inequality for dual norm Yang [1991] , and (b) is due to is the definition of the span semi-norm (see (C)). The value that maximizes the inner maximization problem in (42) in ω(V, µ) is the generalizedmean by definition denoted with abbreviate notation ω. If the norm is differentiable, then we have that the equality (a) comes from the generalized Holder's inequality for arbitrary norms Yang [1991] , namely, defining z = (V -µ -ω), it satisfiesz = ∥z∥ * ∇ ∥y∥ (44)The quantity ν is replaced by the generalized mean for equality in (b) while ( 44) comes from Yang [1991] . Using complementary slackness Karush [2013] stackness let B = {s ∈ S :EQUATIONwhich leads to the following equality by plugging the previous ( 45) in ( 44) and defining z * = V -µ * -ω:EQUATIONorEQUATIONby letting λ = ∥z * ∥ * ∈ R + . Note that here the hypothesis of 1 are use and especially separability is needed to ensure that for s ∈ B, ∇ ∥y∥ = ∇ ∥P ∥ only depend on P (s) and not on other coordinates, which is true form generalized L p norms. We can remark that v -µ * is P dependent, but if P is known, the best µ * is only determined by one 2 dimensional parameters λ = ∥v -µ * -ν∥ * and ω ∈ R + . Moreover, when P is fixed, the scalar ω is a constant is fully determined by P , v and µ * . This is why the quantity defined α λ P varies through 2 parameter λ and ω. Given this observation, we can rewrite the optimization problem as :EQUATION)where we defined the maximization problem on µ not in R S but at the optimal in the variational family denote M λ,ω P = {v -α λ,ω P , (λ, ω) ∈ R 2 + , P ∈ ∆(S)}. We can rewrite the optimization problem in terms of α P with [V ] α λ,ω P defined in 35. Contrary to the T V case, α is not a scalar but α λ,ω P belongs to a variational family only determined by two parameter. Note that this lemma is still true writing subgradient and not gradient of P . As we assume C 2 -regularity on norms, the subgradient space of the norm reduce to the singleton of the gradient in our case. C 2 smoothness will be needed in concentration part while it is possible to be more general in optimization lemmas. Note that for T V or L 1 , this lemma holds, but the vector α λ,ω P reduces to a positive scalar denoted α which is equal to ∥v -µ * ∥ ∞ according to Iyengar [2005] .Lemma 4 (Strong duality for the distance induced by the norm ∥∥ in the s-rectangular case.). Consider any probability vector P π := Π π P ∈ ∆ s for P ∈ ∆(S) A , any fixed uncertainty level σ and the uncertainty set U s, σ ∥.∥ (P ), we abbreviate the subscript to use U s, σ (P ) := U s, σ ∥.∥ (P ). Then for any vector V ∈ R S obeying V ≥ 0, recalling the definition of [V ] α in (35), one has inf P∈U s, σ (P )EQUATION)with the definition of sp() * in C and where the variational family A λ,ω P is defined as :EQUATION)with ω is the generalized mean defined as the argmin in the definition of the span semi norm in 2 and λ, ω a positive scalar. Moreover, for L 1 or T V , case, the vector α λ,ω P reduces to a 1 dimensional scalar such as α ∈ [0, 1/(1 -γ)].In the proof of the previous lemma, we decompose this problem s-rectangular radius σ into sarectangular sub-problem with respectively radius σ sa .inf We can exchange the min and the max as we get concave-convex problems in σ and µ in the second line according to minimax theorem [v. Neumann, 1928] and using Cauchy Swartz inequality which is attained in the last equality. Finally, we obtain:EQUATIONinf P∈U s, σ (P) P π V = a π(a|s) max µ≥0 P sa (V -µ) -σ ∥π s ∥ * sp(V -µ) * (a) = a π(a|s) max α λ,ω Psa ∈A λ,ω Psa P sa [V ] α λ,ω Psa -σ ∥π s ∥ * sp([V ] α λ,ω Psa ) *where in (a) we use the previous lemma for sarectangular case. Note that as we are using sarectangular case, for T V or L 1 , this lemma holds, but the vector α λ P reduces to a positive scalar denoted α which is equal to ∥v -µ * ∥ ∞ . (See also Iyengar [2005] ).We begin with a key lemma concerning the dynamic range of the robust value function V π,σ (cf. ( 7)), which produces tighter control when σ is large; the proof is deferred to Appendix D.3.1. This lemma allows tighter control compared to Clavier et al. [2023] . Lemma 5. In sa-rectangular case (see (3), for any nominal transition kernel P ∈ R SA×S , any fixed uncertainty level σ, and any policy π, its corresponding robust value function V π,σ (cf. (7)) satisfiesEQUATION)where C g = 1/(min s ∥e s ∥) is a geometric constant depending on the geometry of the norm. For example, for L p , norms p ≥ 1, C g ≥ 1 which reduce the sample complexity. In s-rectangular case, we obtain a slightly different lemma because of the dependency on π. Lemma 6. The infinite span semi norm can be controlled as follows for every s in s-rectanuglar case (See (5)):EQUATIONwhere C g = 1 mins∥es∥ is a geometric constant depending on the geometry of the norm. These lemmas are required to get tight bounds for the sample complexity. The main difference between saand srectangular case is that we have an extra dependency on ∥π s ∥ * , which represents how stochastic the policy can be in s rectangular MDPs. Lemma 7. Consider an MDP with transition kernel matrix P and reward function 0 ≤ r ≤ 1. For any policy π and its associated state transition matrix P π := Π π P and value function 0 ≤ V π,P ≤ 1 1-γ (cf. (1)), one has for saand srectangular assumptions.(I -γP π ) -1 Var Pπ (V π,P ) ≤ 8 γ 2 (1 -γ) 2 sp(V π,P ) ∞ 1.See D.3.7 for the proofThe first decomposition of the proof of Theorem 1 and Theorem 3 Agarwal et al. [2020] while the argument needs essential adjustments in order to adapt to the robustness setting. One has by assumptions using any planner in empirical RMDPs :EQUATIONusing previous inequality, performance gap V ⋆,σ -V π,σ ∞ , can be upper bounded using 3 steps.First step: subdivide the performance gap in 3 terms. We recall the definition of the optimal robust policy π ⋆ with regard to M rob and the optimal robust policy π ⋆ , the optimal robust value function V ⋆,σ (resp. robust value function Q π,σ ) w.r.t. M rob . Then, the performance gap V ⋆,σ -V π,σ can be decomposed in one optimization term and two statistical error termsEQUATIONwhere (i) holds by V π ⋆ ,σ -V π ⋆ ,σ ≤ 0 since π ⋆ is the robust optimal policy for M rob , and (ii) comes from (55) and definition of optimization error. The proof aims to control the last remaining terms in (56) using concentration theory and sufficiently big number of step N . To do so, we will consider a more general term V π,σ -V π,σ for any policy π even if control of these two terms slightly differ at the end. Using (32), it holds that for both saand s-rectangular assumptions:V π,σ -V π,σ = r π + γ P π, V V π,σ -r π + γP π,V V π,σ = γ P π, V V π,σ -γP π, V V π,σ + γP π, V V π,σ -γP π,V V π,σ (i) ≤ γ P π,V V π,σ -P π,V V π,σ + γ P π, V V π,σ -γP π, V V π,σ ,where (i) holds because P π, V V π,σ ≤ P π,V V π,σ because of the optimality of P π, V (see. ( 25)).Factorizing terms leads to the following equationEQUATIONIn the same manner, we can also obtain a lower bound of this quantity:EQUATIONUsing both ( 57) and ( 58), we obtain infinite norm control:EQUATION)By decomposing the error in a symmetric way, he haveEQUATIONArmed with these inequalities, we can use concentration inequalities to upper bound the two remaining termsEQUATIONFinally, π = π ⋆ , applying (60) gives usEQUATION)Note that to control V π ⋆ ,σ -V π ⋆ ,σ ∞ , we use decomposition not depending on π for value function as V π ⋆ ,σ is deterministic and fixed, allowing use of classical concentration analysis tools. This decomposition is the same for both sa-rectangular and s-rectangular case.Second step: bound first term and second term in (62) to control ∥ V π ⋆ ,σ -V π ⋆ ,σ ∥ ∞ To control the two terms in (62), we use lemma 8 based Bernstein's concentration argument and whose proof is in Appendix D.3.3. Lemma 8. For both saand s-rectangular setting, consider any δ ∈ (0, 1), with probability 1 -δ, it holds:EQUATION)with L = 2 log(18 ∥1∥ * SAN/δ) and where Var P π ⋆ (V ⋆,σ ) is defined in (27). Moreover, for the specific case of T V , this lemma is true without the smoothness term3LC S ∥1∥ * N (1-γ) .Armed with the above lemma, now we control the first term on the right-hand side of (62) as follows:EQUATION≤ I -γ PEQUATIONwhere (a) holds as the matrix I -γ P π ⋆ ,V -1 is positive definite, (b) holds due to Lemma 8, and the last point holds from the following decomposition for variance and triangular inequalityVar P π ⋆ (V ⋆,σ ) = Var P π ⋆ (V ⋆,σ ) -Var P π ⋆ (V ⋆,σ ) + Var P π ⋆ (V ⋆,σ ) ≤ Var P π ⋆ (V ⋆,σ ) -Var P π ⋆ (V ⋆,σ ) + Var P π ⋆ (V ⋆,σ ) -Var P π ⋆ ,V (V ⋆,σ ) + Var P π ⋆ ,V (V ⋆,σ ).Finally, the fact that P π ⋆ ,V is a stochastic matrix, soEQUATIONArmed with these inequalities, the three terms R 1 , R 2 , R 3 in (64) can be controlled separately.• Consider R 1 . We first introduce the following lemma, whose proof is postponed to Appendix D.3.4.Lemma 9. Consider any δ ∈ (0, 1). With probability at least 1 -δ, one hasI -γ P π ⋆ ,V -1 Var P π ⋆ ,V (V ⋆,σ ) ≤ 4 1 + L (1-γ) 2 N + C S ∥1∥ * L N (1-γ) γ 3 (1 -γ) 2 max{1 -γ, C g σ} 1 ≤ 4 1 + L (1-γ) 2 N + C S ∥1∥ * L N (1-γ) γ 3 (1 -γ) 3 1 with L = 2 log( 18∥1∥ * SAN δ) in the sa-rectangular case. In the s-rectangular case, it holds:I -γ P π ⋆ ,V -1 Var P π ⋆ ,V (V ⋆,σ ) ≤ 4 1 + L (1-γ) 2 N + C S ∥1∥ * L N (1-γ) γ 3 (1 -γ) 2 max{1 -γ, C g σ min s ∥π s ∥ * } 1 ≤ 4 1 + L (1-γ) 2 N + C S ∥1∥ * L N (1-γ) γ 3 (1 -γ) 3 1Using Lemma 9 and inserting back to (64) gives in sa-rectangular caseEQUATION• Consider R 2 . First, denote V ′ := V ⋆,σ -η1 η ∈ R, by Lemma 5, we have for any π,EQUATIONfor sa-rectangular case or in s-rectangular we obtain0 ≤ min η ∥V -η1∥ ∞ ≤ 1 γ max{1 -γ, σC g ∥π s ∥ * } (68)by the definition of the span semi norm. Moreover, we can use Holder with L 1 and L ∞ we have for both sa and s-rectangular case to as it holds that:EQUATION)In the first inequality, we useV ′ 2 ∞ = V ′2∞ and and we use Lemma 5 in (a) where C g σ = σ 1 . With the same arguments for s-rectangular, we obtain forEQUATIONwhere (a) comes Eq 126, (b) comes lemma 6 or more precisely eq (139). Then, taking the sup over s in the previous equations, it holdsEQUATIONApplying the previous inequality, it holds in sa-rectangular case:EQUATIONwhere the last inequality uses I -γ P 65)) for sa-rectangular. In the s-rectangular case, we obtain a different result asπ ⋆ ,V -1 1 ≤ 1 1-γ 1 (cf. (EQUATION• Consider R 3 . The following lemma plays an important role.Applying Lemma 2 and using π = π ⋆ and V = V ⋆,σ , it holdsVar P π ⋆ (V ⋆,σ ) -Var P π ⋆ (V ⋆,σ ) ≤ 2∥V ⋆,σ ∥ 2 ∞ log( 2SA δ ) N 1,which can be inserted in (64) to givesEQUATIONwhere the last line uses I -γ PEQUATION)).Finally, inserting the results of R 1 in (66), R 2 in (76), R 3 in (79), and (65) back into (64) givesEQUATIONEQUATIONwhere the last inequality holds by the fact γ ≥ 1 4 and letting N ≥ L (1-γ) 2 . We have the same result for s-rectangular, replacing, max{1 -γ, C g σ} by max{1 -γ, min s ∥π * s ∥ * σC g }.Now we are ready to control second term in (62) to control ∥ V π ⋆ ,σ -V π ⋆ ,σ ∥ ∞ . To proceed, applying Lemma 8 on the second term of the right-hand side of (62) leads toEQUATION)We now bound the above four terms R 4 , R 5 , R 6 , R 7 separately.• Using Lemma 7 withP = P π ⋆ , V , π = π ⋆ and V = V π ⋆ ,σ which follow V π ⋆ ,σ = r π ⋆ + γ P π ⋆ , V V π ⋆ ,σ, and in view of (65), the term R 4 in (83) can be controlled as follows:EQUATIONwhere the last inequality is due to Lemma 5 for sa-rectangular case and with the same quantity replacing max{1 -γ, σ} by max{1 -γ, min s ∥π * s ∥ * σ} in the srectangular case.• For bounding R 5 , we can simply use ( 65)) to getEQUATION• The term R 6 can upper bounded as (76) as follows:EQUATION)for sa-rectangular case and with the same quantity replacing max{1 -γ, C g σ} by max{1γ, min s ∥π * s ∥ * σC g } in the srectangular case.• Finally, R 7 can be controlled the same as (79) shown below:EQUATION)Combining the results in ( 84), ( 86), (87), and (88) and inserting back to (83) leads to forEQUATIONwhere the last inequality follows from the assumption γ ≥ 1 4 . Finally, inserting ( 82) and (89) back to (62) yieldsEQUATION)where the last inequality holds by taking N ≥16 log( SAN δ ) (1-γ) 2rearranging terms. In s-rectangular case, we obtain the same result, replacing max{1 -γ, C g σ} by max{1 -γ, min s ∥π * s ∥ * C g σ}.Third step: controlling ∥ V π,σ -V π,σ ∥ ∞ or bounding the first and second term in (61). Unlike the earlier term, one has to face a more complicated statistical dependency between π and the empirical RMDP. To begin with, we introduce the following lemma which controls the main term on the right-hand side of ( 61), which is proved in Appendix D.3.5. Lemma 10. Consider any δ ∈ (0, 1). Taking N ≥ L ′′ with probability at least 1 -δ, one has for saor s-rectangular case :EQUATION)with L ′′ = 2 log(54∥1∥ * SAN 2 (1-γ)δ). Moreover, for T V this lemma holds but without the geometric term14L ′′ C S ∥1∥ * N (1-γ) 1.Taking the sup over s gives the final result.With Lemma 10 in hand, we have to control first term in ( 61)EQUATIONwhere (i) and (ii) hold by the fact that each row of (1 -γ) I -γP π, V -1 is a probability vector that falls into ∆(S). The remainder of the proof will focus on controlling the three terms in (93) separately.• For S 1 , we introduce the following lemma, whose proof is postponed to D.3.6.Lemma 11. Consider any δ ∈ (0, 1). Taking N ≥ L ′′ (1-γ) 2 one has with probability at least 1 -δ, for sarectangularI -γP π, V -1 Var P π, V ( V π,σ ) ≤ 6 1 + ε opt + L ′′ C S ∥1∥ * N (1-γ) γ 3 (1 -γ) 2 max{1 -γ, σ} 1 ≤ 6 1 + ε opt + L ′′ C S ∥1∥ * N (1-γ) (1 -γ) 3 γ 3 1.and for s-rectangularI -γP π, V -1 Var P π, V ( V π,σ ) ≤ 6 L ′′ 1 + ε opt + C S ∥1∥ * N (1-γ) γ 3 (1 -γ) 2 max{1 -γ, C g σ min s ∥π s ∥ ∞ } 1 ≤ 6 L ′′ 1 + ε opt + C S ∥1∥ * N (1-γ) (1 -γ) 3 γ 2 1.Applying Lemma 11 and ( 65) to ( 93) leads toEQUATION)for sa-rectangular and the same quantity replacing max{1 -γ, C g σ} by max{1γ, C g σ min s ∥π s ∥ * } for srectangular case.• Applying Lemma 1 with ∥ V ⋆,σ -V π,σ ∥ ∞ ≤ ε opt and (65), S 2 can be controlled asEQUATION)• S 3 can be controlled similar to R 2 in (76) as follows:S 3 = 2 L ′′ N I -γP π, V -1 Var P π ( V ⋆,σ ) -Var P π, V ( V ⋆,σ ) ≤ 4 L ′′ N I -γP π, V -1 1 γ 2 max{1 -γ, C g σ} 1 (96) ≤ 8 L ′′ γ 2 (1 -γ) 2 max{1 -γ, C g σ}N 1 (97)for sa-rectangular and replacing max{1 -γ, σ} by max{1 -γ, σ min s ∥π s ∥ * } for srectangular case.Finally, summing up the results in ( 94), ( 95), and ( 97) and inserting them back to (93) yields: takingN ≥ L ′′ (1-γ) 2 , with probability at least 1 -δ, I -γP π, V -1 P π, V V π,σ -P π, V V π,σ ≤ 2ε opt 1 -γ 1 + 14L ′′ C S ∥1∥ * N (1 -γ) 2 1 + 12 L ′′ 1 + ε opt + C S ∥1∥ * N (1-γ) γ 3 (1 -γ) 2 max{1 -γ, C g σ}N 1 + 8 ε opt L ′ (1 -γ) 4 N 1+ (98) 8 L ′ γ 2 (1 -γ) 2 max{1 -γ, C g σ}N 1 ≤ 16 L ′′ 1 + ε opt + C S ∥1∥ * N (1-γ) γ 3 (1 -γ) 2 max{1 -γ, σ}N 1 + 2ε opt γ (1 -γ) + 8 ε opt γL ′ (1 -γ) 4 N 1 + 15L ′′ C S ∥1∥ * N (1 -γ) 2 1 (99) (100)for sa-rectangular and the same quantity replacing max{1 -γ, σ} by max{1 -γ, σ min s ∥π s ∥ * } for srectangular case. In this step, it is harder to decouple terms as V π depends on data both in π and V .Step 5: controlling ∥ V π,σ -V π,σ ∥ ∞ : bounding the second term in (61). Towards this, applying Lemma 10 leads to in sa-rectangular case:EQUATION)We shall bound each of the terms separately.• Applying Lemma 7 with P = P π,V , π = π, and taking V = V π,σ which obeys V π,σ = r π + γP π,V V π,σ , the term S 4 can be controlled similar to (84) as follows:EQUATION)for sa-rectangular and the same quantity replacing max{1 -γ, C g σ} by max{1γ, min s ∥ πs ∥ * σC g } for srectangular case.• For S 5 , it is observed thatEQUATION• Next, observing that S 6 and S 7 are almost the same as the terms S 2 (controlled in ( 95)) and S 3 (controlled in (97)) in ( 93), it is easily verified that they can be controlled as followsEQUATION)for sa-rectangular and the same quantity replacing max{1 -γ, σ} by max{1 -γ, min s ∥ πs ∥ * σ} for srectangular case. Then inserting the results in ( 103), ( 104), and (105) back to (102) leads toEQUATIONEQUATION) (109) Taking N ≥ 16L ′′ 1-γ , we obtain 2εopt (1-γ) + 4ε opt L ′′ (1-γ) 4 N 1 ≤ 3εopt(1-γ) with probability at least 1 -δ, inserting (99) and (107) back to (61)V π,σ -V π,σ ∞ ≤ max 16 L ′′ 1 + ε opt + C S ∥1∥ * N (1-γ) γ 3 (1 -γ) 2 max{1 -γ, σ}N + 2ε opt γ (1 -γ) + 14L ′′ C S ∥1∥ * N (1 -γ) 2 , 12 L ′′ 1 + ε opt + C S ∥1∥ * N (1-γ) γ 3 (1 -γ) 2 max{1 -γ, σ}N + 4 L ′′ (1 -γ) 2 N V π,σ -V π,σ ∞ (110) + 3ε opt (1 -γ) + 14L ′′ C S ∥1∥ * N (1 -γ) 2 ≤ 48 L ′′ 1 + ε opt + C S ∥1∥ * N (1-γ) γ 3 (1 -γ) 2 max{1 -γ, C g σ}N + 6ε opt (1 -γ) + 28L ′′ C S ∥1∥ * N (1 -γ) 2 (111)for sa-rectangular and the same quantity, replacing max{1 -γ, C g σ} by max{1 -γ, σ min s ∥π s ∥ * } for srectangular case. The proof is similar for T V without the geometric term depending on C S .Step 6: summing all the previous inequalities results. Using all the previous results in ( 90) and ( 111) and inserting back to (56) complete the proof as follows: taking N ≥ 16L ′′ (1-γ) 2 , γ > 1/4, , with probability at least 1 -δ, for sa-rectangularV ⋆,σ -V π,σ ∞ ≤ V π ⋆ ,σ -V π ⋆ ,σ ∞ + ε opt + V π,σ -V π,σ ∞ ≤ ε opt + 48 L ′′ 1 + ε opt + C S ∥1∥ * N (1-γ) γ 3 (1 -γ) 2 max{1 -γ, C g σ}N + 6ε opt (1 -γ) + 28L ′′ C S ∥1∥ * N (1 -γ) 2 + 160 L(1 + C S ∥1∥ * N (1-γ) ) (1 -γ) 2 max{1 -γ, C g σ}N + 14LC S ∥1∥ * N (1 -γ) 2 ≤ 8ε opt 1 -γ + 42L ′′ C S ∥1∥ * N (1 -γ) 2 + 1508 L ′′ (1 + C S ∥1∥ * N (1-γ) ) (1 -γ) 2 max{1 -γ, C g σ}N (112)where the last inequality holds by γ ≥ 1 4 and N ≥ 16L ′′ (1-γ) 2 for sa-rectangular and the same quantity replacing max{1 -γ, σ} by max{1 -γ, σ min s {∥π * s ∥ * }} for srectangular case. The proof is similar for T V without the geometric term depending on C S .Similarly to Shi et al. [2023] , denoting s 0 the argmax of V π,σ such that V π,σ (s 0 ) = min s∈S V π,σ (s) using recursive Bellman's equationEQUATIONEQUATIONwhere the second line holds since the reward function r(s, a) ∈ [0, 1] for all (s, a) ∈ S × A.Then we construct for any (s, a) ∈ S × A, P s,a ∈ R S by reducing the values of some elements of P s,a such that P s,a ≥ P s,a ≥ 0 and s ′ P s,a (s ′ ) -P s,a (s ′ ) = σC s,a g . with C s,a g = 1 ∥es 0 ∥ It lead to P s,a + σC s,a g e ⊤ s0 ∈ U σ ∥∥ (P s,a ), where e s0 is the standard basis vector supported on s 0 , since1 2 P s,a + σC s,a g e ⊤ s0 -P s,a ≤ 1 2 P s,a -P s,a + C s,a g σ ∥e s0 ∥ 2 = σ/2 + σ/2 = σ (115)Consequently, infEQUATIONwhere the second inequality holds byEQUATION)Plugging this back to the previous relation givesmax s∈S V π,σ (s) ≤ 1 + γ(1 -C s,a g σ) max s∈S V π,σ (s) + γC s,a g σ min s∈S V π,σ (s) (119)which, by rearranging terms, yieldsEQUATIONSo rearranging terms it holds :sp(V π,σ ) ∞ ≤ 1 γ max{1 -γ, C s,a g σ} (122)or taking the sup over s:sp(V π,σ ) ∞ ≤ 1 γ max{1 -γ, C g σ} (123)As we pick the supreme over s, the quantity, C s,a g is replaced by C g = 1/(min s ∥e s ∥) to obtain a control for every s.Similarly to 5 denoting s 0 the argmax of V π,σ such that V π,σ (s 0 ) = min s∈S V π,σ (s) using recursive Bellman's equationEQUATIONEQUATIONwhere the second line holds since the reward function r(s, a) ∈ [0, 1] for all (s, a) ∈ S × A.Then we construct for any s ∈ S P s ∈ R S×A by reducing the values of some elements of P s such that P s ≥ P s ≥ 0 and ∀a ∈ A,s ′ P s (s ′ , a) -P s (s ′ , a) = σ s,a C s gwhere C s g is defined as 1/ ∥e s ∥. Writting ∥σ s,a ∥ ≤ σ we construction σ s,a such that a π(a|s)EQUATIONNot that this construction is possible as it is simply Cauchy Swartz equality case. It leads toP s + σe ⊤ s0,a ∈ U σ (P s ), where e s0,a ∈ R S×A is the standard basis vector supported on s 0 which is equal to 1 at s 0 for every a and otherwise.EQUATIONas C s g ∥σ s,a e s0,a ∥ is equal to C s g σ ∥e s0 ∥ Consequently, infEQUATIONEQUATIONEQUATIONEQUATIONEQUATIONwhere ∥π∥ ∞ is the norm of the vector π(.|s) and where (a) holds becauses ′ P s (s ′ ) = - s ′ P s (s ′ ) -P s (s ′ ) + s ′ P s (s ′ ) = 1 -σ s,a C s g (134)Finally (b) is due to (126) and using Holder's inequality in the second term. Plugging this back to the previous relation givesEQUATIONwhich, by rearranging terms, yieldsEQUATIONSo rearranging and taking the sumpremum over all sterm it holds :EQUATION)As we pick the supreme over s ovf this quantity, C s g is replaced by C g = 1/ min s ∥e s ∥.Proof. Concentration of the robust values function. with probability 1 -δ, it holds:P π,V s,a V -P π,V s,a V ≤ 2 L N Var P 0 s,a (V ) + 3LC S ∥1∥ * N (1 -γ)with L = 2 log(18 ∥1∥ * SAN/δ) and First we can use optimization duality such as in (50):EQUATIONmaxEQUATIONwhere in the first equality we use Lemma 3. The final inequality is a consequence of the 1-Lipschitzness of the max operator. First, we control g s,a (α λ,ω P , V ). To do so, we use for a fixed α λ,ω P and any vector V that is independent with P 0 , the Bernstein's inequality, one has with probability at least 1 -δ with sa-rectangular notations,EQUATIONOnce pointwise concentration derived, we will use uniform concentration to yield this lemma. First, union bound, is obtained noticing that g s,a (α λ,ω P , V ) is 1-Lipschitz w.r.t. λ and ω as it is linear in λ and ω. Moreover,λ * = ∥V -µ * -ω∥ * obeying λ * ≤ ∥1∥ * 1-γ . The quantity ω ∈ [0, 1/(1 -γ)]as it is always smaller that V by definition. We construct then a 2-dimensional a ε 1 -net N ε1 overλ * ∈ [0, ∥1∥ * 1-γ ] and ω ∈ [0, 1/(1 -γ)] whose size satisfies |N ε1 | ≤ 3∥1∥ * ε1(1-γ)2 [Vershynin, 2018] .Using union bound and (145), it holds with probability at least 1 -δ SA that for all λ ∈ N ε1 ,EQUATIONUsing the previous equation and also (144) , it results in using notation 2 log(EQUATION≤ supα λ P ∈Nε 1 P 0 s,a -P 0 s,a [V ] α λ P + ε 1 (b) ≤ 2 log( SA|Nε 1 | δ ) N Var P 0 s,a (V ) + 2 log( 2SA|Nε 1 | δ ) 3N (1 -γ) + ε 1 (147) (c) ≤ 2 log( 2SA|Nε 1 | δ ) N Var P 0 s,a (V ) + log( 2SA|Nε 1 | δ ) N (1 -γ) (d) ≤ L N Var P 0 s,a (V ) + L N (1 -γ) (148) ≤ L N ∥V ∥ ∞ + L N (1 -γ) ≤ 2 L (1 -γ) 2 N (149)where (a) is because the optimal α falls into the ε 1 -ball centered around some point inside N ε1 and g s,a (α λ P , V ) is 1-Lipschitz with regard to λ and ω, (b) is due to Eq. ( 146), (c) arises from takingε 1 = log( 2SA|Nε 1 | δ ) 3N (1-γ) , (d) is verified by |N ε1 | ≤ 3∥1∥ * ε1(1-γ)≤ 9N ∥1∥ and that variance of a ceiling function of a vector is smaller than the variance of non-ceiling vector , and the last inequality comes from the fact ∥V ⋆,σ ∥ ∞ ≤ 1 1-γ and taking N ≥ 2 log(18SAN ∥1∥ * δ ) = L.Contrary to the previous term, the second term g s,a (α λ P , V ) is more difficult as we need concentration. Still, the data has an extra dependency through the parameter α λ P . We need to decouple this problem using absorbing MDPs. Then it leads to g s,a (α λ,ω P , V )EQUATIONIn the first equality, we add the term µ λ,ω P 0 s,a to retrieve the previous concentration problem, fixing P 0 s,a and optimizing λ, ω. In the second, we extend the max using triangular inequality. The first term in the last equality is exactly the term we have controlled previously, while the second one needs more attention. We decouple the data's dependency, then control the difference between the µ. Then using the characterization of the optimal µ from equation ( 47):P 0 s,a -P 0 s,a (µ λ,ω P 0 s,a -µ λ,ω P 0 s,a ) = s ′ λ P 0 s,a (s ′ ) -P 0 s,a (s ′ ) (∇ P 0 s,a -∇ P 0 s,a )Here we assume that the subgradient is a gradient as we assume that the norm is C 2 . The question that arises is whether the gradient of the norm is Lipschitz.Note that we are considering the worst case as (µ λ,ωP 0 s,a -µ λ,ω P 0 s,a) can be zero in the case where µ the Lagrangian variable is equal to zero. Finally, note that we can also control this term when one of the two terms µ λ,ω P 0 s,a or µ λ,ω P 0 s,a is equal to zero as µ λ,ω P 0 s,a and µ λ,ω P 0 s,a smaller that V because V -µ need to be positive in equation ( 43). In this case, classical control using Bernstein's inequality without uniform concentration can be applied, giving the same result. In the worst case where all terms in (µ λ,ωP 0 s,a -µ λ,ω P 0 s,a) are non zero, assuming that the norm is C 2 , using mean value theorem, we know that(∇ P 0 s,a -∇ P 0 s,a ) 2 ≤ sup x∈∆(S) ∇ 2 ∥x∥ 2 (P 0 s,a -P 0 s,a ) 2 .As the norm is C 2 , is continuous and as the simplex is bounded, this quantity exists according to the Extreme value theorem. It is possible to compute this contact depending on S for explicit norms such as L p . Indeed, for L 2 :∇ 2 ∥x∥ 2 = (I -x x) ∥x∥ 2 2 ∥x∥ 2 ≤ 1 ∥x∥ 2 I ≤ 1 min x∈∆(S) ∥x∥ 2 I = √ Swhere is the Kronecker product. So we have an upper bound independent of x. For L p = ∥x∥ p norms, p ≥ 2, we have simple taking derivative twice:∇ 2 ∥x∥ p = p -1 L p A p-2 -g p g T p with A = Diag abs(x) L p g p = A p-2 x L p .where Diag is the diagonal matrix. However, as x ≤ L p , A ≤ I, we getEQUATIONwhere the 1/L p is minimized for the uniform distribution. Then using Cauchy Swartz inequality, it holdsEQUATION)Then the question is how to bound the quantity P 0 s,a -P 0 s,a 2 2 . To do so, we will use McDiarmid inequality.A function f : X 1 × . . . X n → R satisfies the bounded difference property if for each i = 1, . . . , n the change of coordinate from s i to s ′ i may change the value of the function at most on c i ∀i ∈ [n] : supx ′ i ∈Xi |f (x 1 , . . . , x i , . . . , x n ) -f (x 1 , . . . , x ′ i , . . . , x n )| ≤ c i In our case, we consider f (X 1 , . . . , X n ) = ∥ n k=1 X k ∥ 2 .Then we can notice that by triangle inequality for any x 1 , . . . , x n and x ′ k with X i,s ′ = P 0 i,s,a (s ′ ) -P 0 s,a (s ′ ) ( index i holds for index of sample generated from the generative model) thatf (x 1 , . . . , x k , . . . , x n ) = ∥x 1 + . . . + x n ∥ 2 ≤ ∥x 1 + . . . + x n -x k + x ′ k ∥ 2 + ∥x k -x ′ k ∥ 2 ≤ f (x 1 , . . . , x ′ k , . . . , x n ) + 2Theorem 5. (McDiarmid's inequality). McDiarmid et al. [1989] Let f : X 1 × . . . X n → R be a function satisfying the bounded difference property with bounds c 1 , . . . , c n . Consider independent random variables X 1 , . . . , X n , X i ∈ X i for all i. Then for any t > 0P [f (X 1 , . . . , X n ) -E [f (X 1 , . . . , X n )] ≥ t] ≤ exp - 2t 2 n i=1 c 2 iUsing McDiarmid's inequality and union bound, we can bound the term hereP 0 s,a -P 0 s,a 2 -E[ P 0 s,a -P 0 s,a 2 ] 2 ≤ 2N log(|S||A|/δ)) N 2with probability 1 -δ/(|S||A|). Moreover, the additional term can be bounded as follows:E[ P 0 s,a -P 0 s,a 2 2 ] = E[ s ′ (P 0 s,a (s ′ ) -P 0 s,a (s ′ )) 2 = E[ s ′ ( 1 N N i X i,s ′ ) 2 ]with X i,s ′ = P 0 i,s,a (s ′ ) -P 0 s,a (s ′ ) is one sample sampled from the generative model. ThenEQUATIONwhere (a) the last equality comes from the independence of the random variables, and where the last inequality comes from the fact the maximum of two elements in the simplex is bounded by 2.Moreover, we know that, EQUATION-E P 0 s,a -P 0 s,a 2 a ≤ 2N log(|S||A|/(δ))) N 2 + 4 N + 4 N 2N log(|S||A|/(δ))) N ≤ 10 log(|S||A|/(δ)) N = L ′ Nwhere in first inequality use (a + b) 2 = a 2 + b 2 + 2ab and where in (a) we combine equation ( 158) and ( 157) and ( 156).with L ′ = 10 log(|S||A|/(δ)). Finally, plugging the previous equation in (155):max µ∈µ λ P 0 s,a P 0 s,a -P 0 s,a (µ λ P 0 s,a -µ)| ≤ max λ P 0 s,a -P 0 s,a 2 2 C S λ.This term can be easily controlled by taking the supremum over λ, which is a 1 dimensional parameter.Then we can bound λ ∈ [0, H ∥1∥ * ]. Indeed,λ * = ∥V -µ * -η∥ * ≤ ∥V ∥ * ≤ H ∥1∥ * .Finally, we obtain:max λ P 0 s,a -P 0 s,a 2 2 C S λ ≤ L ′ C S ∥1∥ * N (1 -γ) .Regrouping all terms:g s,a (α λ P , V ) ≤ | max µ λ P 0 s,a∈M λ P 0 s,a P 0 s,a -P 0 s,a (V -µ λ P 0 s,a ) + maxEQUATIONWe can recognize that the second term is a second-order term as long as N ≥ (C S ∥1∥ * ) 2 , we can regroup the two terms. Finally, as g s,a (α λ P , V ) ≥ g s,a (α λ P , V ), we obtainEQUATIONIt is important to note that the geometry of the norm is present in the second order term 3LC S ∥1∥N (1-γ)but this term is negligible as it is proportional to 1/N with regard to the variance term in 1/ √ N . Moreover, note that the quantity C S ∥1∥ * = S for L 2 norms.For the specific case of T V which is not C 2 smooth, this lemma still holds as in ( 144), we only need to control one term without the dependency on data in the supremum as α λ P reduces to a scalar α which does not depend on P . Then extra decomposition using smoothness of the norm is not needed, as the only remaining term in the max in ( 144) is the left-hand side term.For the s-rectangular case, the first equation can be rewritten simply by factorizing by π(a|s) using lemma 4.EQUATIONusing sa-rectangular results, which gives the result for s-rectangular case.Combining this lemma with a matrix notation using union bound, one has with probability 1 -δ:EQUATION(166)Using the same argument as in ( 216), it holds that for any α * solution of ( 53)I -γ P π ⋆ ,V -1 Var P π ⋆ ,V (V ⋆,σ ) = 1 1 -γ ∞ t=0 γ t P π ⋆ ,V t Var P π ⋆ ,V (V ⋆,σ ). (167)Then we can control Var P π ⋆ ,V (V ⋆,σ ) . Defining V ′ := V ⋆,σ -η1, η ∈ R, we use Bellman's equation in ( 32)) which lead toEQUATIONEQUATIONwhere in the second line we use Lemma 3. and we define r′ π ⋆ = r π ⋆ -(1 -γ)η < r π ⋆ < 1.We obtain the same result in s-rectangular using lemma 4 instead. ThenEQUATIONEQUATIONwhere (a) holds by the fact that Var Pπ (V -η1) = Var Pπ (V ) for any scalar η, (b) follows from (172), moreover (c) comes from 1γ 2 V ′ • V ′ ≥ 1 γ V ′ • V ′ and -1 ≤ r π ⋆ -(1 -γ)V min 1 = r ′ π ⋆ ≤ r π ⋆ ≤ 1.Finally, the inequality is due to Lemma 8. Plugging ( 176) into (167) gives,EQUATIONusing in (i) the triangle inequality. The final part of the proof focuses on the first term, which follows (181) using recursion between the two sums. Then, using (181) back to (180) leads to∞ t=0 γ t P π ⋆ ,V t P π ⋆ ,V (V ′ • V ′ ) - 1 γ V ′ • V ′ = ∞ t=0 γ t P π ⋆ ,V t+1 - ∞ t=0 γ t-1 P π ⋆ ,V t (V ′ • V ′ ) ≤ 1 γ ∥V ′ ∥ 2 ∞ 1I -γ P π ⋆ ,V -1 Var P π ⋆ ,V (V ⋆,σ ) ≤ ∥V ∥ 2 ∞ γ(1 -γ) 1 + 3 1 + L (1-γ) 2 N + C S ∥1∥ * L N (1-γ) ∥V ′ ∥ ∞ (1 -γ) 2 γ 2 1 ≤ 4 1 + L (1-γ) 2 N + C S ∥1∥ * L N (1-γ) ∥V ′ ∥ ∞ (1 -γ) 2 γ 2 1 (182) ≤ 4 1 + 1 L (1-γ) 2 N + C S ∥1∥ * L N (1-γ) ∥V ′ ∥ * (1 -γ) 2 γ 2 1 (183)Taking the infimum over η in the right-hand side, recall V ′ := V ⋆,σ -η1, we obtain the definition of the span semi norm.EQUATIONwhere the penultimate inequality follows from applying Lemma 5 with P = P 0 and π = π ⋆ :sp(V ⋆,σ ) * ≤ 1 γ max{1 -γ, C g σ}or with an extra factor for s rectangular assumptions.sp(V ⋆,σ ) * ≤ 1 γ max{1 -γ, min s ∥π s ∥ * σCg} .In this proof, we will sa-rectangular notations, for any (s, a) ∈ S × A, using the results in (144). In the sa-rectangular case:EQUATIONThe first term in this max can be bounded using:EQUATIONEQUATIONwhere (a) comes from the triangle inequality, and (b) comes from P 0 s,a -P 0 s,a 1 ≤ 2 andV π,σ α λ,ω * Psa -V ⋆,σ α λ,ω * Psa ∞ ≤ V π,σ -V ⋆,σ∞ , and (c) follows from the definition of the optimization error in (55). The second term of the max can be controlled in the same manner, i.e.: (191) where the last inequality follow the decomposition of (150). Finally, to control the remaining termP 0 s,a -P 0 s,a V π,σ α λ,ω * Psa ≤ P 0 s,a -P 0 s,a V ⋆,σ α λ,max µ λ P 0 s,a ∈M λ P 0 s,a P 0 s,a -P 0 s,a ( V ⋆,σ -µ λ P 0 s,a ) = max α λ P ∈A λ P (P 0 s,a -P 0 s,a ) [V ] α λ P (192) (191) for any given α ∈ [0, α λ,ω * Psa [⊂ 0, 1 1-γS in the variational family with one parameter λ, with the dependency between V ⋆,σ and P 0 , we resort to the following leave-one-out argument or absorbing MDPs used in [Agarwal et al., 2020 , Li et al., 2022b , Shi and Chi, 2022 , Clavier et al., 2023] . To begin, we create a collection of auxiliary RMDPs that exhibit the intended statistical independence between robust value functions and the estimated nominal transition kernel. These auxiliary RMDPs are designed to be minimally distinct from the initial RMDPs, subsequently, we manage to control the relevant term within these auxiliary RMDPs and demonstrate that its value closely approximates the target quantity for the desired RMDP. Recall that the empirical infinite-horizon robust MDP M rob is defined using the nominal transition kernel P 0 . Inspired by Agarwal et al. [2020] , we can construct an auxiliary absorbing robust MDP M s,u rob for each state s and any non-negative scalar u ≥ 0, so that it is the same as M rob except for the transition properties in state s. These auxiliary MDPS are called absorbing MDPs are have been used for the first time in the context of RMDPS in Clavier et al. [2023] . Defining the reward function and nominal transition kernel of M s,u rob as P s,u and r s,u , which are expressed as follows using the same notation as Shi et al. [2023] :EQUATIONEQUATIONNominal transition probability at state s of the auxiliary M s,u rob never leaves state s once entered, which gives the name absorbing to these auxiliary RMPDs. Finally, we define the robust Bellman operator T σ s,u (•) associated M s,u rob as T σ s,u (Q)(s, a) = r s,u (s, a) + γ inf P∈U sa,σ (P s,u s,a )PV, withEQUATIONin sa-rectangular case and with stochastic policy in s-rectangular case. Using these auxiliary RMDPs we can remark equivalence between M rob and the auxiliary RMDP M s,u rob fixed-point. First, Q ⋆,σ is the unique-fixed point of T σ (•) with associated value V ⋆,σ . We will show that the robust value function V ⋆,σ s,u ⋆ obtained from the fixed point of T σ s,u (•)is the same as the the robust value function V ⋆,σ derived from T σ (•), as long as we choose u asEQUATIONwith e s is the s-th standard basis vector in R S . This assertion is verified as:• First for state s ′ ̸ = s, for all a ∈ A: it holds 197) where the first equality holds because of (193) and (194) , and the last inequality comes from that Q ⋆,σ is the fixed point of T σ (•) (see Lemma C.3) and the definition of the robust Bellman operator in (13).EQUATION• Then for state s, for any a ∈ A :EQUATIONusing in the first equality is the definition of P s,u ⋆ s,a in ( 194) and where we use the definition of u ⋆ in (196) in the second one.Finally, we have proved that there exists a fixed point Q ⋆,σ s,u ⋆ of the operator T σ s,u ⋆ (•) by takingEQUATION)we have confirmed the existence of a fixed point of the operator T σ s,u ⋆ (•) with corresponding value function V ⋆,σ s,u ⋆ that coincide with V ⋆,σ . Note that the corresponding properties between M rob and M s,u rob in Step 1 and Step 2 hold in fact for any uncertainty set and sor sa-rectangular assumptions. Equipped with these fixed point equalities, we can use concentration inequalities to show this lemma.Concentration inequality using an ε-net for all reward values u. First we can verify thatEQUATION)Then, we define a N ε2 -net over the interval 0, 1/(1 -γ) , where |N ε2 the size of the net can be controlled by [Vershynin, 2018] . The only parameter that varies is λ in the variation family, α λ Psa so we have 1-dimensional control and not a vector in R S . Then similarly to Lemma C.3, it holds that for each u ∈ N ε2 , there exists a unique fixed point Q ⋆,σ s,u of the operator 194) and (193) by construction for all u ∈ N ε2 , M s,u rob is statistically independent of P 0 s,a . This independence indicates that [ V ⋆,σ s,u ] α and P 0 s,a are independent for a fixed α. Using ( 148) and ( 149) and taking the union bound over all (s, a, α) ∈ S × A × N ε1 , u ∈ N ε2 gives that, with probability at least 1 -δ, it holds for all (s, a, u)|N ε2 | ≤ 3 ε2(1-γ)EQUATIONEQUATIONFinally, we use uniform concentration to obtain the lemma. Recalling that u ⋆ ∈ 0, 1 1-γ (see ( 200)), we can always find some u∈ N ε2 such that |u -u ⋆ | ≤ ε 2 . Consequently, plugging in the operator T σ s,u (•) in (195) yields ∀Q ∈ R SA : T σ s,u (Q) -T σ s,u ⋆ (Q) ∞ = |u -u ⋆ | ≤ ε 2We can then remark that the fixed points of T σ s,u (•) andT σ s,u ⋆ (•) obey Q ⋆,σ s,u -Q ⋆,σ s,u ⋆ ∞ = T σ s,u ( Q ⋆,σ s,u ) -T σ s,u ⋆ ( Q ⋆,σ s,u ⋆ ) ∞ ≤ T σ s,u ( Q ⋆,σ s,u ) -T σ s,u ( Q ⋆,σ s,u ⋆ ) ∞ + T σ s,u ( Q ⋆,σ s,u ⋆ ) -T σ s,u ⋆ ( Q ⋆,σ s,u ⋆ ) ∞ ≤ γ Q ⋆,σ s,u -Q ⋆,σ s,u ⋆ ∞ + ε 2 ,where we use that the operator T σ s,u (•) is a γ-contraction. It gives that:EQUATIONFinally to control the first term in (191), using the identity V ⋆,σ = V ⋆,σ s,u ⋆ or fixed point relation between the two RMPDS, established in previous step of the proof gives that: for all (s, a) ∈ S × A, max α λ,ω Ps,a ∈A λ,ω Ps,aEQUATION≤ max α λ,ω Ps,a ∈A λ,ω Ps,aP 0 s,a -P 0 s,a [ V ⋆,σ s,u ] α λ,ωPs,aEQUATION≤ maxEQUATIONwith L ′′ = log54∥1∥ * SAN 2 (1-γ)δwhere (a) comes from triangular inequality, (b) is due (203), for anyEQUATION(c) follows from ( 201), (d) holds using Lemma 1 with (203). Here, the two last inequalities hold byletting ε 2 = 2 log( 18∥1∥ * SAN |Nε 2 | δ ) N , which gives |N ε2 | ≤ 3 ε2(1-γ) ≤ 3N1-γ , and the last inequality holds by the factVar P 0 s,a ( V ⋆,σ ) ≤ ∥ V ⋆,σ ∥ ∞ ≤ 1 1-γ and letting N ≥ 2 log 54∥1∥ * SAN 2 (1-γ)δ = L ′′ .Rewriting (186), the first term of the max is controlled.max P 0 s,a -P 0 s,a V π,σ α λ * Ps,a , P 0 s,a -P 0 s,a V π,σ α λ * Ps,aThe second term can be controlled by the same term as the first one plus an additional term withP 0 s,a -P 0 s,a V π,σ α λ * Ps,a ≤ | max µ λ P 0 s,a ∈M λ P 0 s,a P 0 s,a -P 0 s,a ( V ⋆,σ -µ λ P 0 s,a ) + max µ λ P 0 s,a ∈M λ P 0 s,a P 0 s,a -P 0 s,a (µ λ P 0 s,a -µ λ P 0 s,a )|and similarly to previous lemma in (159), the residual or term in the right in the previous equation can be controlled withL ′ C S ∥1∥ * N (1-γ)Finally, putting ( 205) and ( 206) back into Equation (191) and using Eq. ( 206) with probability at least 1 -δ we obtainEQUATION∀(s, a) ∈ S × A. Using matrix form we obtain finally:EQUATIONThe proof is similar in the s-rectangular case, factorising by π(a|s), like in in 8. Moreover, the proof is similar for T V without the geometric term depending on C S .We always use the same manner as in Appendix D.3.4. Similarly to (167), it holds:EQUATIONIn order to upper bound Var P π, V ( V π,σ ), we define V ′ := V π,σ -η1 with η ∈ R. Using as (174), it holdsEQUATIONwhere the last inequality makes use of Lemma 10. Plugging (212) back into (210) leads toEQUATIONwhere (a) is the same as ( 180), (b) holds by repeating the argument of ( 181), (c) follows by taking N ≥ L ′′ (1-γ) 2 and then the last inequality holds by ∥V ′ ∥ ∞ ≤ ∥V ⋆,σ ∥ ∞ ≤ 1 1-γ . Then taking the infimum over η in the right-hand side of the equation in the definition of V ′ and using sp(.) ∞ ≤ ∥.∥ * givesI -γP π, V -1 Var P π, V ( V π,σ ) ≤ 6 1 + ε opt + L ′′ C S ∥1∥ * N (1 -γ) sp(V ) ∞ (1 -γ) 2 γ 2 1Finally, applying Lemma 5 with P = P 0 and π = π yields sp( V π,σ ) * ≤ 1 γ max{1 -γ, γC g σ} ,for sa-rectangular or sp( V π,σ ) * ≤ 1 γ max{1 -γ, min s ∥π∥ * σ} in the s-rectangular case, which can be inserted into (214) and gives in sa-rectangular case:I -γP π, V -1 Var P π, V ( V π,σ ) ≤ 6 1 + ε opt + L ′′ C S ∥1∥ * N (1-γ) γ 3 (1 -γ) 2 max{1 -γ, σ} 1 ≤ 6 1 + ε opt + L ′′ C S ∥1∥ * N (1-γ)(1 -γ) 3 γ 3 1 where first inequalities comes from that we can bound it Eq. left-hand side of equation ( 214) by ∥V ′ ∥ ∞ ≤ ∥V ⋆,σ ∥ ∞ ≤ 1 1-γ . Proof for s-rectangular is similar, but requires adding an extra factor depending on the norm of the current policy and we have:I -γP π, V -1 Var P π, V ( V π,σ ) ≤ 6 1 + ε opt + L ′′ C S ∥1∥ * N (1-γ) γ 3 (1 -γ) 2 max{1 -γ, C g σ min s ∥π s ∥ ∞ } 1 ≤ 6 1 + ε opt + L ′′ C S ∥1∥ * N (1-γ)(1 -γ) 3 γ 2 1.First, if each row of P π belongs to the simplex ∆(S), it lead that the row of (1 -γ) (I -γP π )-1 falls into ∆(S). Then, (I -γP π )-1Var Pπ (V π,P ) = 1 1 -γ(1 -γ) (I -γP π )-1Var Pπ (V π,P )(a) ≤ 1 1 -γ (1 -γ) (I -γP π ) -1 Var Pπ (V π,P ) = 1 1 -γ ∞ t=0 γ t (P π )t Var Pπ (V π,P ),where (a) is due to Jensen's inequality. Then for any η ∈ R + , V ′ := V π,P -η1 , we can upper bound Var Pπ (V π,P ) :Var Pπ (V π,P )EQUATIONwhere (i) holds by the fact that Var Pπ (V π,P -b1) = Var Pπ (V π,P ) for any scalar b and V π,P ∈ R S , (ii) follows from V ′ ≤ r π + γP π V π,P -η1 = r π -(1 -γ)η1 + γP π V ′ , and the last line arises from 1 Var Pπ (V π,P ) ≤γ 2 V ′ • V ′ ≥ 1 γ V ′ • V ′EQUATION) (220)where (i) holds due to, (ii) holds by following recursion between the two sums, and the last inequality holds because∥V ′ ∥ ∞ ≤ 1 1-γ . Then taking the minimum over η in the right-hand side of the equation gives the result.(I -γP π ) -1Var Pπ (V π,P ) ≤ 8sp(V π,P ) ∞ γ 2 (1 -γ) 2of states X = {x 0 , x 1 , • • • , x S-1 } and Y = {y 0 , y 1 , • • • , y S-1 }. The action space for each state is A of A possible actions. So we have totally 2S states and there is in total 2SA state-action pairs. Armed with the above definitions, we can first introduce the following nominal transition kernel: for all (s, a) ∈ X ∪ Y × AP (0,0) (s ′ | s, a) =             p1(s ′ = y i ) + (1 -p)1(s ′ = x i ) if s = x i , a = 0, ∀i ∈ S q1(s ′ = y i ) + (1 -q)1(s ′ = x i ) if s = x i , a ̸ = 0, ∀i ∈ SEQUATIONHere, p and q are set according to 0 ≤ p ≤ 1 and 0 ≤ q = p -∆for some p and ∆ > 0 that will be introduced momentarily.Then we introduce the S(A -1) components inside M ∞ . Namely, for any (i, j) ∈ S × A \ {0}, the nominal transition kernel of M (i,j) is specified asP (i,j) (s ′ | s, a) =              p1(s ′ = y i ) + (1 -p)1(s ′ = x i ) if s = x i , a = j q1(s ′ = y i ) + (1 -q)1(s ′ = x i ) if s = x i ∈ X , a = 0 P (0,0) (s ′ | s, a) otherwise (226)In words, the nominal transition kernel of each variant M (i,j) only differs slightly from that of the basic nominal transition kernel P (0,0) when s = x i and a = {0, j}, which makes all the components inside M ℓ∞ closed to each other.In addition, the reward function is defined asEQUATION)Uncertainty set of the transition kernels. Recall the following useful notation for any transition probability P , i.e., the transition vector associated with some state s is denoted as:EQUATIONWith this in hand, the uncertainty set (definition in (5)) with ℓ ∞ norm for any P θ with θ ∈ Θ can be represented as:U s, σ ∞ (P θ s ) := U s, σ ∥.∥ (P θ s ) = P ′ s ∈ ∆(S) A :EQUATION)So without loss of generality, we set the radius σ ∈ (0, (1 -c 0 )] with 0 < c 0 < 1. Before proceeding, we observe that as the uncertainty set above is defined with respect to ℓ ∞ , it directly implies that for each (s, a) ∈ S × A, the uncertainty set is independent and can be decomposed as U s, σ ∞ (P θ s ) = ⊗U s, σ ∥.∥ (P θ s,a ) = P ′ s,a ∈ ∆(S) : P ′ s,a -P θ s,a ≤ σ .Notably, this indicates that using s-rectangular uncertainty set with ℓ ∞ norm as the divergence function is analogous to the case of using (s, a)-rectangular uncertainty set with ℓ ∞ norm. As a result, we follow the pipeline of the prior art Shi et al. [2023, Section C] which established the minimax-optimal lower bound for (s, a)-rectangular RMDPs with TV distance, which is analogous to the ℓ ∞ case. Towards this, we set p, q, ∆ as the same as the ones in Shi et al. [2023, Section C.1] , where we recall the expressions of p, q, ∆ for self-contained as below: taking c 1 := c0 2 , p = (1 + c 1 ) max{1 -γ, σ} and ∆ ≤ c 1 max{1 -γ, σ},which ensure several facts: 0 ≤ p ≤ 1 and p ≥ q ≥ max{1 -γ, σ}.• It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is not verified. • For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates). • The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 10. Broader Impacts Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed? Answer: [NA] Justification:Theoretical paper. Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact. • Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations. • The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to 


Decision: The reviewers appreciated the optimal sample complexity bound in the Lp RMDP settings. I concur and believe are of great interest to the distributionally robust RL community. A clear accept.

Reviews: review: paper_summary: paper_summary: This paper proposes tighter than prior art sample complexity bounds for Robust Markov Decision Processes. In sa-rectangularity and s-rectangularity conditions with non-zero uncertainty measured using $L_p$  around a nominal transition kernel, the upper bound is $\frac{SA}{(1-\gamma)^3\\epsilon^2}$. The setup assumes access to a simulator to collect $N \times S \times A$ samples to first learn a transition kernel and determines optimal policy using distributional robust value iteration. The goal is utilize few samples there after to identify the optimal policy
strength_weakness: strength_weakness: It would be better has NSA been not used in Eq. 17, 18, 19, 20, 21 . Although the intention of the authors is clear, but that would improved readability.

In Table 1, the bounds are used in order sense, it would improve readability to have written in $\mathcal{O}(.)$, especially since the lower and upper bounds are of same order
questions: questions: It would great improve the draft with some empirical evaluation to back the theoretical bounds, even a toy example.
Especially important since the bounds are not significant improvement from the prior art
limitations: limitations: Please add experimental work to back the theoretical bounds
paper_summary: paper_summary: The paper presents an analysis of the sample complexity of solving distributionally robust Markov decision processes (RMDPs) with general Lp norms as the distance metric for the uncertainty set. The authors consider both the sa-rectangular and s-rectangular settings and provide near-optimal upper and lower bounds on the sample complexity.
strength_weakness: strength_weakness: The primary issue is that this paper closely aligns with Clavier et al. [2023]. To clarify the unique contributions, the authors should include more in-depth discussions comparing their work to Clavier et al. [2023]. For instance, the proof in Section 8.3 appears to follow Clavier et al. [2023] without proper citation.

A potential limitation of the paper is its focus on the tabular setting. It would be valuable to explore whether these insights can be applied to the function approximation setting as well. Nevertheless, this does not diminish the importance of the contributions presented in this work.
questions: questions: na
limitations: limitations: The authors have discussed limitations in the paper.
paper_summary: paper_summary: This paper dives into the theoretical understanding of learning robust MDPs with a generative model. The robust set is modeled as a distribution ball induced by the general $L_p$-norm centered around the nominal model. The sample complexity is provided for both  $\mathcal{S}\times\mathcal{A}$-rectangular and $\mathcal{S}$-rectangular robust sets and for the former case the minimax optimality is established.
strength_weakness: strength_weakness: 1. One of the key message is that learning general $L_p$-norm robust MDPs is easier than learning standard MDPs. However, this result is not superising given the prior arts on certain special cases such as the TV norm robust MDP [2]. So I think it is less discussed how the exact choice of the generalized $L_p$-norm would further affect the diffuculty of learning this type of robust MDPs. 
2. Although theoretically sound, it is not well discussed when and why people need to consider modeling the inherent uncertainty of the MDP parameters using the generalized $L_p$-norm. 

**References:**

[2] Shi L, Li G, Wei Y, Chen Y, Geist M, Chi Y., 2023. The curious price of distributional robustness in reinforcement learning with a generative model. Advances in Neural Information Processing Systems.
questions: questions: 1. Regarding Section 8.3:
   - (Line 687-689) It is claimed that the dual form is derived for *arbitrary* norms, which seems like an overclaim since the proofs still depend on the assumptions in Definition 1 (e.g., Line 718). I think this is a misleading claim and needs revision.
   - It seems that the proof of duality in Section 8.3 resembles that in [1] without mentioning that work. Could the authors highlight a bit more the difference between the proofs here the and the proofs for duality in the previous work [1]?
2. Regarding Theorems 3 and 4 for the $\mathcal{S}$-rectangular case. The upper bound in Theorem 3 (Equation (21)) involves a minimization over two terms (this is different from the $\mathcal{S}\times\mathcal{A}$-case where only the first term appears, which I think comes from a different upper bound on the span of the value function), but the lower bound in Theorem (Equation (23)) for a special case only involves the first term in the minimization in the upper bound, which seems like a contradiction. Could the authors explain more on that? 
3. Regarding Theorem 4. For the $\mathcal{S}$-rectangular robust set case, the lower bound is only for the standard $L_{\infty}$-norm case. Could the authors elaborate more on the difficulty in proving a lower bound for the general $L_p$-norm case?
4. Some typos and grammatical mistake that I found:
   - Line 137 to 138.
   - Line 144: simple -> simplex.
   - Line 155: typo in defining the domain of the norm.
   - Inconsistent usage of label (sometimes Theorem x but sometimes Theorem (x)), e.g., Lines 62 and 71, Lines 218 and 222.
limitations: limitations: Please refer to the weakness section and the question section above.
paper_summary: paper_summary: The paper investigates distributionally robust Markov decision processes (RMDPs) in the discounted infinite-horizon setting. The authors consider the case where the transition kernel can be arbitrarily chosen from a prescribed (given) uncertainty set centred around a reference kernel, where the uncertainty set is specified using a smooth norm--the authors consider L_p norms. Assuming access to a generative model (simulator) that can sample from the reference transition kernel, the authors analyse a model-based approach that first constructs an empirical approximation of the reference transition kernel and then applies distributional robust value iteration to it. Considering the robust value function--which measures the worst case performance over all the possible transition kernels in the uncertainty set--the authors show that their method convergences to the optimal robust policy under two commonly adopted conditions (sa-rectangularity and s-rectangularity) describing the decoupled nature of the uncertainty sets. The authors establish upper bounds and sample complexity results for the procedure they consider (or any procedure that achieves a certain optimization error), as well as algorithmic-independent lower bounds.
strength_weakness: strength_weakness: Overall, I found the main paper to be well-written, though it does contain some minor typos, formatting inconsistencies, and punctuation errors within the main text.

Establishing the lower bounds in the s-rectangularity setting for any L_p norm, not just the L_{\infty} norm, would strengthen the paper, enabling it to discuss minimax optimality also in that setting.
questions: questions: 1- At the technical level, beyond considering a new dual formulation, what is the main difference compared to the proof scheme in Shi et al., 2023?

2- What challenges are involved in establishing lower bounds that hold for any L_p norm in the s-rectangularity case?

3- Is there a fundamental limitation to extending the results to the *entire* range of the uncertainty level?

4- On the motivation side, the authors write (page 2) that "in practice, numerous applications are based on optimizations or learning approaches that involve general norms beyond those that have already been studied". Could the authors provide relevant citations?
limitations: limitations: The paper includes numerous remarks that qualify the level of contribution and limitations of the results. The conclusion identifies the important task of establishing f-divergences as future work.

Comments: title: Folllowing of the Aswer to revierwer Tr2g
comment: Thank you for your response. The clarification provided by the authors addresses my main concerns, and I would like to raise the score.
Thank you very much for your response.
Updated score
We are grateful for your feedback and will incorporate your suggestions into the final version of the manuscript.
Thank you for your response, we will revise the final version of the manuscript, following your recommendations.
I would like to thank the authors for their response. I continue to hold a positive outlook on this work, and I maintain my score.
Thank you very much for your detailed response! I agree with your clarifications on several points that I am concerned with. But I think the proof of the duality result in the paper still ought to mention the existence of the results in Clavier et al. [2023]. I currently have no further questions. Given the answer and the contributions of the work, I am willing to increase my score.
> Q5 Regarding Theorem 4. For the $\mathcal{S}$-rectangular robust set case, the lower bound is only for the standard $L_{\infty}$-norm case. Could the authors elaborate more on the difficulty in proving a lower bound for the general $L_p$-norm case?


The lower bounds are for the case of $s$-rectangularity, which poses entirely new challenges compared to the case of $sa$-rectangularity: the 
optimal policies can be stochastic and difficult to characterize as closed forms, compared to the deterministic ones in $sa$ cases. When using different norms, the corresponding optimal policies might even not have closed forms, which is also the bottleneck to extend the $L_\infty$ case (Theorem 4) to more general $L_p$/arbitrary norms (as in Theorem 2).

> Q6. Some typos and grammatical mistake that I found:

Many thanks for pointing out the typos. We have revised them and check throughout the entire paper again.