Near-Optimal Distributionally Robust Reinforcement Learning with General $L_p$ Norms
Authors: Pierre Clavier
Laixi Shi
Erwan Le Pennec
Eric Mazumdar
Adam Wierman
Matthieu Geist
Venue: NeurIPS 2024 poster (2024)
Keywords: Robust Markov decision process
norm
sample complexity
strong duality
Primary area: reinforcement_learning
TL;DR: To address the challenges of robustness and sample efficiency in reinforcement learning (RL), this work studies the sample complexity of distributionally robust Markov decision processes (RMDPs).

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.

Near-Optimal Distributionally Robust Reinforcement Learning with General Lp Norms
Pierre Clavier Ecole Polytechnique, Inria
Laixi Shi Caltech
Erwan Le Pennec Ecole polytechnique
Eric Mazumdar Caltech
Adam Wierman Caltech
Matthieu Geist
Cohere
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 specific cases, the generalizability of the existing findings remains unclear, especially in comparison to standard RI. Assuming access to a generative model that samples from the nominal MDP, we examine the sample complexity of RMDPs using a class of generalized Lp 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 Lp norms both sa- and s-rectangular cases, potentially inspiring more empirical research. We provide near-optimal upper bound and matching minimax lower bound for the sa-rectangular scenarios. For s-rectangular cases, we improve the state-of-the-ar upper bound and also derive lower bound using L norm that verifies the tightness.
Introduction
Reinforcement learning (RI.) [Sutton| 1988 is popular paradigm in machine learning, particularly noted for its success in practical applications. The RL framework, usually modeled within the context of Markov decision process (MDP), focuses on learning effective decision-making strategies based on interactions with fixed environment. However, the work of Mannor et al. [2004), among others, has highlighted vulnerability RL strategies, revealing the sensitivity inherent shift or estimation errors in the reward and transition probabilities. A specific example of this is when, because of sim-to-real gap, policies learned in idealized environments fail when deployed environments with slight changes or adversarial perturbations [Koppp et al. 2017 Mahmood et al. 2018).
To address this issue, distributionally robust RI., usually formulated as robust MDPs (RMDPs), proposed by Tyengar (0055) and Niilim and El Ghaoui (2055) have attracted considerable attention. RMDPs are formulated max-min problems, seeking policies that resilient to model environment
*CMAP, CNRS, Ecole Polytechnique, Institut Polytachnique de Paris, 120 Palaiscau
Inria Paris, HeKA, 75015 Paris, France 'Department Computing Mathematical Sciences, Califomia Institute of Technology, CA 91125, USA. CChhree, Paris.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

perturbations within 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 3
and These assumptions facilitate computation traceability of meth- ods 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 se-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. 202T].
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. [013b) Li et al. [023c).
this goal in general remains open in RMDPs. Specifically, there exists prior work studying the sample complexity of distributionally robust RL for few specific divergences such as total variation (TV)
distance, x" divergence, Kullback-Leibler divergence (K L) 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 Lp norms (see Def. D To the best of our knowledge, minimax optimal sample complexity for the full range of uncertainty level has only been achieved for one case - TV distance (Shi et al., [023]. In this work, we focus understanding the sample complexity of RMDPs with a general smooth L that will be defined in Def. 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 Lp 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 TV distance, (Shi 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:
application
Is distributionally robust RL more sample efficient than standard fo some general class of norms (Def. (I? ?
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 op- timize. 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 Lyp norms defined in Def.
Main contributions. In this paper, address each of the two questions discussed above. In particular, we provide the first sample complexity analysis for RMDPs with general Lp norms (cf. Def. under both the s- and so-rectangularity conditions. For convenience, we present detailed comparisons between the prior arts and our results in Table for quick reference and discuss the contributions and their implications as below.
Considering the first question, we illustrate our results in both sa- and s-rectangular cases in Figure D In the case of so-rectangularity, we derive sample complexity upper bound for RMDPs
Here, o the uncertainty level/radius of the uncertainty set, and C, > is a positive constant related to the geometry of the norm defined in Def. [ For classical Lp norms, C 2 1 so we can directly relax this constant to to obtain the result in Ta 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
using general smooth Lp norms (cf. Theorem in the order of Ö m==-)==m((11-7-p-1
SA
2

---

rectiugullarit
s-rectangularity
Result type
Reference
Distance
0<a51
0<ā51
1-756 Bran
Yang et al.
2022a
s'atzool
0111-1/52
Panaganti and Kalathil
TV
2'4
Upper bound
Sli al.
2023
TV
SAA
54
Clavier et
2023
12-1P
11
12-17
B1
This paper
1
54
84
11my1t any Saller
This paper
General
Yang et
2022a
TV
$40--1)
12-57
Lower hound
Shi al.
2023
TV
paper
1
This puper
94
Table Comparisons with prior results (up to log terms) regarding finding an E-optimal policy for the distributionally RMDP, where is the radius of the uncertainty set and max defined in Theorem |
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 7pp norms. The 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.
results rely on
In the case of s-rectangularity, we provide a sample complexity upper bound for solving RMDPs SA
with general smooth Lp norms in the order of Ö [1->]² max[1-7,C min, + with ||-I|+ the dual norm and ā the radius of the ball in the s-rectangular uncertainty set. This result improves the prior art Ô
S4 (1-7)+a² in Clavier et al. (2023) for classical Lp - by at least a factor of O
when ā < 1-7. Furthermore, we present lower bound for representative case with Loo 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, derive new dual optimization problem forms for both sa- and s- rectangular cases (Lemma and and 4). which is the foundation of the covering number argument in finite-sample analysis. From statistical point of view, a new concentration lemma (See Lemma 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 sa and s- rectangular 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 rectangularity case: the optimal policies can be stochastic and hard to be characterized as closed form, compared to the deterministic one in sa-rectangular cases. Therefore, we construct new hard instances for s-rectangular cases that distinct from those used in sa-rectangular cases or standard RI.
Considering the second question, as illustrated in Figure I 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 Lp norms (cf. Def. Tp. 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 estimation errors and sim-to- gaps, but also leads to better data efficiency. In terms of comparing the statistical implications of sa- and s- rectangularity, our results show that solving s-rectangular RMDPs not harder than solving sa-rectangular RMDPs in terms of sample requirement (See Theorem and Figure 2 Right).
2 Problem Formulation: Robust Markov Decision Processes
In this section, we formulate distributionally robust Markov decision processes (RMDPs) in the discounted anfiite-horizon setting, introduce the sampling mechanism, and describe our goal.
3

---

Sample complesity
Sample complesity
For (1.3) (ca./rccmmmpaaaatt tom Upe loorl (l
54
S4
Srasird MOR
7/462
(1-1)?
ASE JARK EiRAAAo
54
Standlrrd WDDS upper miiiree lowar
1)
(1-7)
du redaargelll with nore
54
Upper meniras lower boundd (D ald
(1-1) 11-///0
[1 7P
sppir bound miniractooe Boand
For p-recctre gdar
(1 7--P77
0,1
0(1)
Uncertaintyy
Figure 1: Left: Sample complexity results for RMDPs with sa- and s-rectangularity with Lp with comparisons prior arts (Shi al. 2023] (for Lı norm, called total variation distance) and sample complexity upper bound of solving s-rectangular dependency RMDPs with Lp norms.
[Clavier et al., [0233] Right: The data and instance-dependee
Standard Markov decision processes (MDPs). discounted infinite-horizon MDP is represented by .M = A, r,), where S = (1, 5) and A (1. A} are the finite state and action spaces, respectively, y E [0, 1) the discounted factor, P P + ((S) denotes the probability transition kernel, and S A - [0, 1] is the immediate reward function, which is assumed to be deterministic. Morcover, 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 LA or 1s the unitary vector of respectively dimension A or S. Moreover, e, the standard unitary vector supported on The policy we are looking for is denoted by S > (AA), which specifies the probability of action selection over the action space in any state. Note that the policy is deterministic in the
sa-rectangular case, overload the notation and refer (s) the action selected by the policy state 8. Finally, to characterize the cumulative reward, the value function Va,P for any policy under the transition kernel P is defined by Vs E
V=.P (s) = E
Σ Entr(se. 50
(I)
The expectation is taken over the randomness of the trajectory {st, at j generated by executing the policy π under the transition kernel P. such that a, ~ ((-|ss)) and 8t+1 P(- St. at) for all t 1 0. In the same way, the Q function QT.²² associated with any policy under the transition kernll P is defined using expectation taken over the randomness of the trajectory under policy क as
(m, = ET.P =
Σ 2r'r(ss, 80, = 8,
Distributionally robust MDPs. We consider distributionally robust MDPs (RMDPs) in the discounted infinite-horizon setting, denoted by Mrab = (S,A, 7, (P").r) where S,A, 7, 7, are the same sets and parameters as in standard MDPs. The main difference compared to standard MDPs is that instead of assuming fixed transition kernel P, it allows the transition kernel to be arbitrarily chosen from a prescribed uncertainty set Ufi (P") centered around a nominal kernel
po S x A (S)), where the uncertainty set is specified using some called L, smooth norm denoted ||-I| defined in of radius a > 0 defined in 1
Definition (General smooth L, norms and dual norms). norm || is said to be general smooth Lp, norm, >> 1 if
for all x E RR,, ||||| = 1|011p.. = (E wek (((((x))))) for some w E R2, being an arbitrary positive vector.
it is twice continuously differentiable Rudin al. 1964) with the supremum of the Hessian where II-llp here is the spectral norm.
Matrix over the simplex Cs supxess
2 x

---

Finally, we denote the dual norm of |1|11 as Il-Il, s.t. levll+ = max, x'y: any metric II-II, we define Cg Cg 1/ min, ||e/]] where E R is the standard basis vector with only at the s-th entry, otherwise
y: |2|| S 1. Moreover, for
Note that the quantity Cs exists, as the Hessian of C2 functional is continuous and because the simplex is a compact set, so by Extreme Value Theorem Rudin et al. [1964), Cs is finite. For example, considering Lp norms with any p 2 2, Cg is bounded by (p 1)57 (See (154) ) This definition is general and includes L, norms [Rudin et al., 1964] for any p 2 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. [ where the further discussion can be found in Appendix B However, it does not include divergences such as KT, and x². Not that the case of TV which not C2 smooth is treated independently with different arguments in the proof but has the same sample complexity. In particular, given the nominal transition kernel fa and some uncertainty level a, the uncertainty set-with arbitrary smooth Lp norm metric || R + Bt in rectangular case or from SxA in the s-rectangular case, is specified as (P0) == Sa.a 11-1 (P
11-1 (Po. s.a) = (Paa E ||Pa.e s.a - Po. S sa). .oo , s,a == (-) E ERIXS P.o = P(- s,a) IRI
(3)
(4)
where we denote a vector of the transition kernel P or ood 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 su-rectangularity (Zhou et al. 202T Wiesemann et al. 2013]. More generally, we
define s-rectangular MDPs as 2ij- (P) = 60 Miil( for the general smooth L,p norm I|-|I- 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 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. [022b]] The 8- uncertainty set is then defined using the rescaled radius ē
u (Ps) = P P P ||la||
(5)
1111| P. = (0)
p = Po IRISA
(6)
where 1A E RA denotes the unitary vector. For the specific case of respectively L1 and Loo norm, ā is equal to |a,Al, or [A|L/P and Note that this scaling allows for fair comparison between sa- and 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 Mrob. defined respectively as V(s,a) E S x A
V= (s) =
inf PELC (Po)
(= = VT. VT.,(s),
inf
(T.
(7)
Ri Peufi (1o)
Similarly for s-rectangularity, the value function is denoted (s) := inf repp (Po) VT)((s).
Optimal robust policy and robust Bellman operator. As 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) [[yegarr 2005 Nilim and El Ghaoui (0055) but not in the s-rectangular case. Therefore, we denote the optimal robust value function (resp. optimal robust Q-function) as V*. (resp. "**"), and the optimal robust policy as x², which satisfy V(s, a) E x A
V* (s) V : (7s) max VT.*(s), (s), (* = Q- (s, max (s,
(8a)
A key concept in RMDPs is a generalization of Bellman's 's optimality principle, encapsulated in the following robust Bellman consistency equation (resp. robust Bellman optimality equation):
Y(s,a) QTh a) = r(s,a) a) + 7
inf
PV
(9a)
((s,)) (s = r(s, + PEtp (pow.)
inf PV*
(9b)
5

---

for the so-rectangular case and same equation replacing P. by P and by ö. The robust Bellman
operator [Iyengar 2005 Nilim and El Ghaoui 2005 is denoted by (.) RSA RSA
(P" (8, = r(s,() a) +
inf PV, with V(s) == max ("(s,a) a) x
(10)
PElli-1 (PS))
for so-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 (DRVI). Generalizing the standard value iteration, DRVI 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 y-contraction property of T with respect to the Ti norm [lyengar 2005
Nilim and Ghaoui 2005
3 Distributionally Robust Value Iteration
Generative model-based sampling. Following Zhou et al.
2021 Panaganti and Kalathil [002
we assume access to generative model or a simulator [Kearns and Singh 1999]. which allows us to collect N 'ndependent samples for each state-action pair generated based on the nominal kernel
ii.d po; (ss a) E S x A, 81,5,a ~ (-11s,a) NSA. We consider model-based approach tailored to RMDPs, which first constructs 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 Eapt in the empirical MDP defined empirical nominal transition kernel Po R. that can be constructed on the basis the empirical frequency of state transitions, i.e. V(8, a) E x ESXA
i = 1, ..... ......N. N. The total sample size is, therefore,
( (S51s,,a))
a) = N
Σ
1f Si.e. = =/}
(11)
1=1
which leads to an empirical RMDP Miob {8, Y, (P') (Pr), Analogously, we can define the corresponding robust value function (resp. robust Q-function) of policy in Mrob V. (resp. Q7 (ef. (8). In addition, we denote the corresponding optimal robust policy f* and the optimal robust value function (resp. optimal robust Q-function) as V.. (resp. Q*-9) (ef. (.) which satisfies the robust Bellman optimality equation V(s,a) E S x A:
i a) r(s, a) +7
inf PV+. PELfi (Po
(12)
Equipped with go we can define the empirical robust Bellman operator 7o as ES
(Q")) = a(s, +
inf PV,
(13)
PEUf (P2.)
with V($)= == max; (" 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 2 (P*) around the nominal kernel using as few samples as possible. Specifically, given some target accuracy level e > 0, the goal to seek an e-optimal robust policy मे obeying
Vs S: D a pa.0 < Eopt.
(*) v (s) SE,
(14)
(15)
This formulation allows plugging any solver of RMDPs in this bound, for instance, the distributionally robust value iteration (DRVT) algorithm detailed in Appendix G
4 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 com- parisons between standard and robust RL, and for comparisons between sa- versus s-rectangularity

---

4.1 sa-rectangular uncertainty set with general smooth norms
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 [.2 Technically, we derive two new dual forms for RMDPs problems using arbitrary norms in Lemmas 3 and 4 for respectively sa- and s-rectangular RMDPS. In these dual forms, central quantity denoted sp(.).; representing the dispersion of the value function, appears and is the dual span semi-norm associated with the considered general Tp norm ||-I| defined in [ in the initial primal problem. The main challenge in this analysis is derive tight upper bound on this quantity in Lemmas ( and 6 leading to the following sample complexity.
Theorem 1 (Upper bound for sa-rectangularity. Consider the uncertainty set 1 (-) associated
P | || p2 as the accessible maximal uncertainty level. Consider any 8 E (0, 1), discount factor ry E [1. and uncertainty level a E (0, maxx]. Let be the outpul policy of some oracle planning algorithm with optimization error Eopt introduced in (1). With introduced in one has with probability at least 1 1 8,
with arbitrary Ep smooth norm || || defined in We denote mmax
85
Vs (*) - V (s) S E 1-7
(16)
for any E (0, 1/ max (1 - 7, Cg as long as the total number of samples obeys
SAA NSA 71- max y. CgorJE2
e2SACs ||1s||=
(17)
(1-
with C2,C2 universal positive constant. For sufficiently small level of accuracy e S (max/1 - C/ ||ss])), the sample complexity is
c3SA
NSA Z (1 7)2 max 7, Cgole?
(18)
Note that this result is also true for TV without the geometric smooth term depending on Cs- Considering T.p norms, Cg 2 and Cs < 51/9(p - 1). In Theorem [ 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 1 (.) associated
with arbitrary Lp norm || defined in 1 We denote Tmax == mmax EA(S) llpi p2 as the accessible maximal uncertainty level. Consider any tuple (S, A, E). where y E [ 1).
G E (0, (0,0max(1 (1 ca)] with 0 < cu S being any small enough positive constant, and E E (0, 156[1-7]]- We can construct two infinite-horizon RMDPs Mo, such that giving a dataset with N' independent samples for each state-action puir over the nominal transition kernel (for either Mo or Mi respectively), one has
inf max (M(M,
( max sES [V+.0 (s) V (s) >5
2
1
where the infimum taken over all estimators Pu (resp. P1) are the probability when the RMDP Mo (resp. M2), as long as, for 07 is universal positive constant,
NSA S (1 -1-7) 7) max 7, Cy
(19)
Near minimax-optimal sample complexity with general I.p norms. Recall that Theorem 1 shows that the sample complexity upper bound of oracle algorithms for RMDPs is in the order of
(1 (1-n)²² ,, 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.
SA
Solving RMDPs with general I.p norms can easier than solving standard RI., Recall that
the sample complexity of solving standard RL with generative model [Agarwal et al. 2020 Li

---

al. 2024 Azar et al. 2013a] is: δ
SA [1-
Comparing this with the sample complexity in
(18), highlights that solving robust MDPs (cf. (8)) using any norm as the divergence function for the uncertainty set is not harder than (and is sometimes easier than) solving standard RI. (cf. (4.T). Specifically, when the uncertainty level is small a X 1 7, the sample complexity of solving robust MDPs matches that of standard MDPs. While when the uncertainty level is relatively larger 1 y S S max, the sample complexity of solving robust MDPs is smaller than that of standard MDPs by a factor or T- which goes to when o = 0(1).
we illustrate the comparisons with two state-of-the arts (Clavier et al. 2023] (Shi et al. [023) which use some divergence functions belonging to the class of general norms considered in this work. In particular, Shi et al. [023) achieved the state-of-the
Comparisons with prior arts. In Figure !
minimax-optimal sample complexity Ô (1~>)) _aa] 1aaaaa11pp-0 7=0))=² for specific I, norm (or called total
S4
variation distance). In this work, we attain near minimax optiimal sample complexity for any general norm (including L1) which matches the one in [Shi et al. [2023] when narrowing down to L1 norm. Note that in TV case. Cg = 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, norm, but for any general norm. In addition, compared to Clavier et al. (2023) which focuses on Ipp norms for any S p S oc: when
7 S maax, we improve the sample complexity Ö( (n (1-2) to
Ō (1=7)"08? by at least a factor of T otherwise, we match the results in Clavier et al. 2023
Burn-in Condition, C, factor and TV case: Th. [and 3 we need a sufficiently small level of accuracy S (max{[ - 7: C) (CC |s ). to obtain the sample complexity. This type of condition is usual in MDPS analysis Shi et al. [022] and equivalent to burn in term. Moreover, the quantity Css exists (see I) and for example, considering I,p norms, Cs is bounded by S1/9, (See (154 ) and the product Cs |sll is upper bounded by S for L2 norm. Moreover, note that our theorem for the smooth norm is also true for TV which is not C2 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 1/ min, ||e]]| norm dependent and depends on how big the vector eso is in the considered norm. Note for classical Lp this quantity is bigger than 1, which reduces the sample complexity.
4.2 s-rectangular uncertainty set with general norms
To continue, move 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 e-optimal policy for RMDPs with s-rectangularity. A proof is shown in Appendix D.2
Theorem (Upper bound for s-rectangularity). Consider the uncertainty set 11-1 ()) with
s-rectangulariry. Consider any discount factor [2. 1), the rescaled uncertainty level ā ||ll and denote Tmax := ||I maxp, P2E ||pi p2ll and ō E 10. Let से be the oulput policy of an arbitrary optimization algorithm with error Eopt- with probability at least 1 - ō, one has for any
e E (0, /1/ max[11 7, Cg min, IaTll J.J. Vs S V+ă V (s) S e + Seae as long as the total number of samples obeys
csSA
csSACs ||
NSA 2
P1-
max (1 - 7, ).C)
oCo min
sES ( [| | [|AI
(1 7)2
(20)
For a sufficiently small accuracy, es (maxf1 (,,1-1,,,,,00 (,,,)))(CC, |sll the sample complexity is
coSA NSAR (1 282 min
(21)
max - C oC, min,es [| ||
|
where n. E A denote the policy of the empirical RMPDs at state s, T E A A the optimal policy given of the true RMPDs, II-Ile the dual norm and c4, cs, C. universal constant. Note that this result is also true for TV without the term depending on smoothness Cs. In addition, we provide the lower bounds for representative divergence function - Loo norm in the following. Note that for classical Lp. Cs 51/((p-1) 1) and Cg can be lower bounded by 1. A proof is provided in Appendix F
8

---

Theorem 4 (Lower bound for s-rectangularity), Consider the uncertainty set U (-) associated with the Lx norm. Consider any tuple (S, A, (,E) and 0 < co S i being any small enough positive constant, where Y E (2.1), and E E (0, 156111]]1 Correspondingly, we denote the accessible maximal uncertainty level for Uix (.) as a max = PIaXPPIPIIAISS lPp1 - P2llso
Then we can
construct a collection of infinite-horizon RMDPs ME.. defined by the uncertainty set with U (-) so that for any (0, maa co)]. and any dataset with in total Nau independent samples for all state-action pairs over the nominal transition kernel (for any RMDP inside ML ). one has
inf max Mc
(PM((ag (max [V*r0s) V (s)))) > >5) sES
2 8
(22)
provided that for og is a universal positive constans,
0gSA
Nall S (1 (1-7) 7) max y, 0)
(23)
with IP, M the probability when the RMDP is M, and the infinum is taken over all estimators ît
Now we can present some implications of Theorem B and Theorem
Robust MDPs with s-rectangularity are at least easy su-rectangularity Theorem
shows that the sample complexity of solving RMDPs with s-rectangularity does not exceed the order of Ö (1-7)² max max
SA
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 terms of the sample complexity. In addition to the worst-case sample complexity upper bound, Theorem [3 alsso provides a data and instance-dependent sample complexity upper bound for s- s-rectangular RMDPs (cf. in (20). Taking the divergence function || = Lp for instance, the data and instance-dependent sample complexity upper bound is
if ia 8) x 8) = 4. V(s,u) ES A 1, Vs
1-
max (1-7,7]
SA 11-7)
if |-
max Taxx|1-,,a00 1-77,
where I1-Iln corresponds to the total number of nonzero elements in veetor.The intuition beyond this theorem is that when the policy becomes proportional to uniform, the uncertainty budget of the e-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 al.
[223] which use Lp 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-an
with regard to the work of Clavier et al. [2023] In particular, the latest achieves in the s-rectangular SA
case at sample complexity of Ô (1- in the regime where o S - 7.. In this regime, our result
the same but more general but in the regime where ă 2 7. they achieve sample complexity
of Ō
SA
SA which is bigger than our result Ô (1-7)) 1 by factor at least 1--"
(1 (2²
5 Conclusion
This work refined sample complexity bounds to learn robust Markov decision processes when the uncertainty set is characterized by general Lp 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 minimax bound, prior results concerning s-rectangular cases were not minimax optimal. Additionally, we

---

have established the minimax sample complexity for RMDPs using general Lp norm, demonstrating that it never larger than that required for learning standard MDPs. Our research identifies potential avenues for future work, such exploring the characterization of tight sample complexity for RMDPs under a broader family uncertainty sets, such as those defined by /-divergence. It would be highly desirable for more unified theoretical foundation, as the distance between probability measures more natural to define using divergence. Morcover, it would be interesting to focus on the finite- horizon Setting and linear setting, as current analytical framework opens the door for potential ex- tensions to address finite-horizon RMDPs. Such an extension would contribute to a more comprehen- sive understanding of tabular cases. Finally, the of linear MDPs would be interesting explore.
6
Acknowledgements
Fondation Mathématique Jacques Hadamard supported this work during Pierre Clavier's visiting the Californian Institute of Technology. Pierre Clavier has been supported by grant from Region Ile-de-France; DIM Math Innov. The work of L. Shi is supported in part by the Resnick Institute and Computing, Data, and Society Postdoctoral Fellowship at California Institute of Technology. The work of E. Mazumdar is supported in part from NSF-2240110 10. The work of A. Wierman is supported part from CNS-21466 21 14,
CNS-2106400) and NGSDI-2105648.
10

---

References
Alekh Agarwal, Sham Kakade, and Lin F Yang. Model-based reinforcement learning with a generative model is minimax optimal. In Conference on Learning Theory, pages 67-83. PMLR, 2020.
Mohammad Azar, Rémi Munos, and Hilbert J Kappen. Minimax pac bounds on the sample complexity of reinforcement learning with generative model. Machine learning, 91:325-349, 2013a.
Mohammad Gheshlaghi Azar, Rémi Munos, and Hilbert J Kappen. Minimax PAC bounds on the sample complexity of reinforcement learning with generative model. Machine learning, 91)3): 325-349, 2013b.
Kishan Panaganti Badrinath and Dileep Kalathil. Robust reinforcement learning using least squares policy iteration with provable performance guarantees. In International Conference on Machine Learning, pages
PMLR, 2021.
Yu Bai, Tengyang Xie, Nan Jiang. and Yu-Xiang Wang. Provably efficient Q-learning with low switching cost. arXiv preprint arXiv:1905. 12849, 2019.
Carolyn L Beck and Rayadurgam Srikant. Error bounds for constant step-size Q-learning. Systems & control letters, (1(12):10331222 2012.
Jose Blanchet and Karthyek Murthy. Quantifying distributional model risk via optimal transport. Mathematics of Operations Research, 44(2):565-666 6000, 2019.
Jose Blanchet, Miao Lu, Tong Zhang, and Han Zhong. Double pessimism is provably efficient for distributionally robust offline reinforcement learning: Generic algorithm and robust partial coverage. arXiv preprint 2:05.::30000965, 2023.
Zaiwei Chen, Siva Theja Maguluri, Sanjay Shakkottai, and Karthikeyan Shanmugam. Finite- sample analysis of stochastic approximation using smooth convex envelopes. arXiv preprint arXiv:2002.00874. 2020.
Pierre Clavier, Stéphanie Allassonière, and Erwan Le Pennec. Robust reinforcement learning with distributional risk-averse formulation. arXiv preprint arXiv:2206 06841, 2022.
Pierre Clavier, Erwan Le Pennec, and Matthieu Geist. Towards minimax optimality of model-based robust reinforcement learning. arXiv preprint arXiv:2302.0537,.22 2023.
Esther Derman and Shie Mannor. Distributional robustness and regularization reinforcement learning. arXiv preprini arXiv:2003.02894, 2020.
Esther Derman, Matthieu Geist, and Shie Mannor. Twice regularized MDPs and the equivalence between robustness and regularization. Advances Neural Information Processing Systems, 34, 2021.
Jing Dong, Jingwei Li. Baoxiang Wang, and Jingzhao Zhang. Online policy optimization for robust MDP. arXiv preprint arXiv:2209.1388 13841, 2022.
Kefan Dong, Yuanhao Wang, Xiaoyu Chen, and Liwei Wang. Q-learning with UCB exploration is sample efficient for infinite-horizon MDP. arXiv preprint
2019.
John Duchi and Hongseok Namkoong, Learning models with uniform performance via distributionally robust optimization. arXiv preprint arXiv:1810.08750 2018
Rui Gao. Finite-sample guarantees for wasserstein distributionally robust optimization: Breaking the curse of dimensionality. arXiv preprint arXiv:2009.0438) 2020.
Vineet Goyal and Julien Grand-Clement. Robust markov decision processes: Beyond rectangularity. Mathematics of Operations Research, 2022.
Songyang Han, Sanbao Su, Sihong He, Shuo Han, Haizhao Yang, and Fei Miao. What is the solution for state adversarial multi-agent reinforcement learning? arXiv preprint arXiv:2212.02705, 2022.
Chin Pang Ho, Marek Petrik, and Wolfram Wiesemann. Fast bellman updates for robust MDPs, In International Conference Machine Learning, pages 1979-1988. PMLR, 2018.

---

Chin Pang Ho. Marek Petrik, and Wolfram Wiesemann. Partial policy iteration for 11 I1-robust markov decision processes. Journal of Machine Learning Research, 22(275):1-46, 2021.
Garud N Iyengar. Robust dynamic programming. Mathematics of Operations Research, 30(2): 257-280, 2005.
Mehdi Jafarnia-Jahromi, Chen- Yu Wei, Rahul Jain, and Haipeng Luo. model-free learning algorithm for infinite-horizon average-reward MDPs with near-optimal regret. arXiv preprint arXiv:2006.0433 04354, 2020.
Chi Jin, Zeyuan Allen-Zhu, Sebastien Bubeck, and Michael Jordan. Is Q-learning provably efficient?
In Advances Neural Information Processing Systems, pages 4863-4873, 2018
Chi Jin, Akshay Krishnamurthy, Max Simchowitz, and Tiancheng Yu. Reward-free exploration for reinforcement learning. In International Conference on Machine Learning, pages PMLR, 2020.
Ying Jin, Zhuoran Yang, and Zhaoran Wang. Is pessimism provably efficient for offline RL? In International Conference on Machine Learning, pages 5084-5096, 2021.
William Karush. Minima of functions of several variables with inequalities as side conditions. In Traces and emergence of nonlinear programming, pages 217-245. Springer, 2013.
David L Kaufman and Andrew J Schaefer. Robust modified policy iteration. INFORMS Journal on Computing, 25(3):396 410, 2013.
Michael Kearns and Satinder P Singh. Finite-sample convergence rates for Q-learning and indirect algorithms. In Advances in neural information processing systems, pages 996-1002, 1999.
Olga Klopp, Karim Lounici, and Alexandre B Tsybakov. Robust matrix completion. Probability Theory and Related Fields, 169(1-2):53-564, 2017.
Aounon Kumar, Alexander Levine, Tom Goldstein, and Soheil Feizi. Certifying model accuracy under distribution shifts. arXiv preprint axXiv:2201.124400 2022.
Navdeep Kumar, Esther Derman, Matthieu Geist, Kfir Levy, and Shie Mannor. Policy gradient for s-rectangular robust markov decision processes. arXiv preprint arXiv:2301. 2023.
Gen Li, Laixi Shi, Yuxin Chen, Yuantao Gu, and Yuejie Chi. Breaking the sample complexity barrier to regret-optimal model-free reinforcement learning. Advances Neural Information Processing Systems, 34, 2021.
Gen Li, Yuejie Chi, Yuting Wei, and Yuxin Chen. Minimax-optimal multi-agent RL in Markov games with a generative model. Neural Information Processing Systems, 2022a.
Gen Li, Laixi Shi, Yuxin Chen, Yuejie Chi, and Yuting Wei. Setling the sample complexity of model-based offline reinforcement learning. arXiv preprint arXiv:2204.05277. 2022b.
Gen Li, Changxiao Cai, Yuxin Chen, Yuting Wei, and Yuejie Chi. Is Q-learning minimax optimal? tight sample complexity analysis. Operations Research, 2023a.
Gen Li. Yuting Wei, Yuejie Chi, and Yuxin Chen. Breaking the sample size barrier in model-based reinforcement learning with a generative model. accepted to Operations Research, 2023b.
Gen Li, Yuling Yan, Yuxin Chen, and Jianqing Fan, Minimax-optimal reward-agnostic exploration in reinforcement learning. arXiv preprint XxXv:2304.07278, 2023e.
Gen Li, Yuting Wei, Yuejie Chi, and Yuxin Chen. Breaking the sample size barrier in reinforcement learning with a generative model. Operations Research, (2(1):233222) 2024.
Yan Li, Tuo Zhao, and Guanghui Lan. First-order policy optimization for robust markov decision process. arXiv preprint MIXXv:2209.1000 2022c.
A Rupam Mahmood, Dmytro Korenkevych, Gautham Vasan, William Ma, and James Bergstra. Benchmarking reinforcement learning algorithms on real-world robots. Conference on robot learning, pages 561-591. PMLR, 2018.
12

---

Shie Mannor, Duncan Simester, Peng Sun, and John N Tsitsiklis. Bias and variance in value function estimation. In Proceedings of the twenty-first international conference on Machine learning.
page 72, 2004.
Colin McDiarmid et al. On the method of bounded differences. Surveys in combinatorics, 141(1): 148-188, 1989.
Janosch Moos, Kay Hansel, Hany Abdulsamad, Svenja Stark, Debora Clever, and Jan Peters. Robust reinforcement learning: A review of foundations and recent advances. Machine Learning and Knowledge Extraction, (()):776-115, 2022.
Arna Nilim and Laurent EI Ghaoui. Robust control of Markov decision processes with uncertain transition matrices. Operations Research, 53(5):780-798, 2005.
Kishan Panaganti and Dileep Kalathil, Sample complexity of robust reinforcement learning with generative model. In International Conference Artificial Intelligence and Statistics, pages 9582-9602. PMLR, 2022.
You Qiaoben, Xinning Zhou, Chengyang Ying, and Jun Zhu. Strategically-tmeed state-observation attacks on deep reinforcement learning agents. In ICML 202/ Workshop on Adversarial Machine Learning, 2021.
Hamed Rahimian and Sanjay Mehrotra. Distributionally robust optimization: A review. arXiv preprint 190.::/998.05599 2019.
Paria Rashidinejad, Banghua Zhu, Cong Ma, Jiantao Jiao, and Stuart Russell. Bridging offline reinforcement learning and imitation learning: A tale of pessimism. Neural Information Processing Systems (NeurIPS), 2021.
Aurko Roy, Huan Xu, and Sebastian Pokutta. Reinforcement learning under model mismatch. Advances in neural information processing systems, 30, 2017.
Walter Rudin et al. Principles of mathematical analysis, volume 3. McGraw-hill New York, 1964.
Reazul Hasan Russel, Bahram Behzadian, and Marek Petrik. Optimizing norm-bounded weighted ambiguity sets for robust mdps. arXiv preprint arXiv: 1912.00296 2019.
Laixi Shi and Yuejie Chi. Distributionally robust model-based offline reinforcement learning with near-optimal sample complexity. arXiv preprint arXiv:2208.05740 05767, 2022.
Laixi Shi, Gen Li, Yuting Wei, Yuxin Chen, and Yuejie Chi. Pessimistic Q-learning for offline rein- forcement learning: Towards optimal sample complexity. In Proceedings of the 39th International Conference on Machine Learning, volume 162. pages 19967-20025. PMLR, 2022.
Laixi Shi, Gen Li, Yuting Wei, Yuxin Chen, Matthieu Geist, and Yuejie Chi. The curious price of distributional robustness in reinforcement learning with generative model. arXiv preprint arXiv:2305. 16589, 2023.
Aaron Sidford, Mengdi Wang, Xian Wu, Lin Yang, and Yinyu Ye. Near-optimal time and sample complexities for solving Markov decision processes with generative model. In Advances in Neural Information Processing Systems, pages 5186-5196, 2018
Elena Smirnova, Elvis Dohmatob, and Jérémie Mary. Distributionally robust reinforcement learning. arXiv preprint arXiv: 087088 2019.
Richard S Sutton. Learning to predict by the methods of temporal differences. Machine learning, (1):9 44, 1988.
Aviv Tamar, Shie Mannor, and Huan Xu. Scaling up robust MDPs using function approximation. In International conference on machine learning, pages 181-189 PMLR, 2014.
Kai Liang Tan, Yasaman Esfandiari, Xian Yeow Lee, and Soumik Sarkar. Robustifying reinforcement learning agents via action space adversarial training. In 2020 American control conference (ACC), pages 3959-3964. IEEE, 2020.
13

---

Mathematics of Chen Tessler, Yonathan Efroni, and Shie Mannor. Action robust reinforcement learning and applica- tions in continuous control. In International Conference on Machine Learning, pages 2215-6224 PMLR, 2019.
A. B. Tsybakov. Introduction to nonparametric estimation, volume 11. Springer, 2009.
J v. Neumann. Zur theorie der gesellschaftssielle. Mathematische annalen, 100(1)229-320,, 1928.
Roman Vershynin. High-dimensional probability: An introduction with applications in data science, volume 47, Cambridge university press. 2018.
Martin J Wainwright. Stochastic approximation with conc-contractive operators: Sharp lx -bouds for Q-learning. arXiv preprint arXiv:1905.06265 2019.
Shengbo Wang, Nian Si, Jose Blanchet, and Zhengyuan Zhou, A finite sample complexity bound for distributionally robust q-learning. arXiv preprini arXiv:2300. 13203, 2023.
Yue Wang and Shaofeng Zou. Online robust reinforcement learning with model uncertainty. Advances in Neural Information Processing Systems, 34, 2021.
Wolfram Wiesemann, Daniel Kuhn, and Berç Rustem. Robust markov decision processes. Mathe- matics of Operations Research, 38(1):153-1833 183, 2013.
Eric M Wolff, Ufuk Topcu, and Richard M Murray. Robust control of uncertain markov decision processes with temporal logic specifications. In 2012 IEEE 51st IEEE Conference on Decision and Control (CDC), pages 3372-3379. IEEE, 2012.
Tengyang Xie, Nan Jiang, Huan Wang, Caiming Xiong, and Yu Bai. Policy finetuning: Bridg- ing sample-efficient offline and online reinforcement learning. Advances in neural information processing systems, 34, 2021.
Huan Xu and Shie Mannor. Distributionally robust Markov decision processes. Operations Research, 37(2))288 200000 2012.
Zaiyan Xu, Kishan Panaganti, and Dileep Kalathil. Improved sample complexity bounds for distribu-
tionally robust reinforcement learning. arXiv preprint arXiw:2303.02783, 2023.
Yuling Yan, Gen Li, Yuxin Chen, and Jianqing Fan. The efficacy of pessimism in asynchronous Q-learning, arXiv preprint arXiv:2203. 220.03383.... 07368, 2022.
Yuling Yan, Gen Li, Yuxin Chen, and Jianqing Fan. The efficacy of pessimism in asynchronous q-learning. IEEE Transactions on Information Theory, 2023.
Kunhe Yang. Lin Yang, and Simon Du. Q-learning with logarithmic regret. In International Conference on Artificial Intelligence and Statistics, pages 1576-1584. PMLR, 2021.
Wei H Yang. On generalized holder inequality. 1991.
Wenhao Yang, Liangyu Zhang, and Zhihua Zhang. Toward theoretical understandings of robust Markov decision processes: Sample complexity and asymptoties. The Annals of Statistics, 50(6): 3223-3248, 2022a.
Wenhao Yang. Liangyu Zhang, and Zhihua Zhang. Toward theoretical understandings of robust markov decision processes: Sample complexity and asymptotics. The Annals of Statistics, 50(6): 3223-3248, 2022b.
Wenhao Yang, Han Wang, Tadashi Kozuno, Scott M Jordan, and Zhihua Zhang. Avoiding model estimation in robust markov decision processes with generative model. arXiv preprint arXiv:2302.012243 2023.
Ming Yin, Yu Bai, and Yu-Xiang Wang. Near-optimal offline reinforcement learning via double variance reduction. arXiv preprint arXiv:2102.01748. 2021.
Huan Zhang, Hongge Chen, Chaowei Xiao, Bo Li, Mingyan Liu, Duane Boning, and Cho-Jui Hsieh. Robust deep reinforcement learning against adversarial perturbations on state observations. Advances in Neural Information Processing Systems, 33:21024-21033 21037, 2020a.
14

---

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-advantagg 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.
A Other related works
Here we provide additional discussion 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.
Classical reinforcement learning with finite-sample guarantees. A recent surge in attention for RL has leveraged the methodologies derived from high-dimensional probability and statistics to analyze RL algorithms in non-asymptotic scenarios. Substantial efforts have been devoted to conducting non-asymptotic sample analyses of standard RL in many settings. Illustrative instances encompass investigations employing Probably Approximately Correct (PAC) bonds in the context
of generative model settings KKarns and Singh 1999 BBck and Srikant 2012 Li et al. 2022a Chen
al. 2020 |Azar et al. 2013b [Sidford al. Agrraa et al. 2020 el. 2023a b Wainwright
2019 and the online setting via both in PAC-base or regret- regret-based analyses Jin et al. 2018 Bai
ct al. [2019 Li et al.) 2021 Zhang et al. [020bb Dong et al. [019 Jin et al. 2020 Li et al. 2023c
JafarniaJJarromi et al. | 20200 Yang et al.
2021 and finally offline setting [Rashiiinejad et al. 2021
Xie et al. 2021 Yin et al. 2021 Shi et al.
2022 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 [Lyengar 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] 2021]. Han et al. [2022]. Clavier et al. (2022). Qiaoben 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. [ 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 distribu- tionally robust RL. The idea of distributionally robust optimization has been explored within the con- text of supervised learning [Rahimian and Mehrotra] 2019 Gao (020) Duchi and Namkoong 2018
Blanchet and Murthy 2019) and has also been extended to distributionally robust dynamic program- ming and Distributionally Robust Markov Decision Processes (DRMDPs) such as in [Iyengar] 2005
Xu and Mannor 2012 Wolff et al. 2012 Kaufman and Schaefer 2013 et al. 2018 Smirnova al.
2019 Ho et al. 2021 Goyal and
[222 Derman and Mannor 2020 Tamar et al. 2014
Badrinath and
Despite the considerable attention received, both empirically and theo-
retically, most previous theoretical analyses in the context of RMDPs adopt an asymptotic perspective
[Roy al. [0177] or focus on planning with exact knowledge of the uncertainty set [[yengar] 20055 Xu and Mannor 2012 Tamar et al. 2014). Many works have focused on the finite-sample performance of verifiable robust Reinforcement Learning (RI.) algorithms. These investigations encompass various data generation mechanisms and uncertainty set formulations over the transition kernel. Closely
15

---

related to our work, various forms of uncertainty sets have been explored, showcasing the versatility of approaches. Divergence such as Kullback-Leibler (KL) divergence is another prevalent choice.
extensively studied by Yang et al. [022a Panaganti and Kalathil [022] Zhou et al. [202T] Shi and
Chi [022].
Xu et al. 2023] J. Wang et al. 2023 Blanchet et al. [2023) who investigated the sample
complexity of both model-based and model-free free algorithms in simulator or offline settings. Xu et al.)
[023] considered various uncertainty sets, including those associated with the Wasserstein distance. The introduction of an R-contamination uncertainty set Waan and Zou (2021), has been proposed to tackle robust Q-learning algorithm for the online setting, with guarantees analogous to standard RL. Finally, the finite-horzon scenario has been studied by Xu et al. 2202), Dong et al. (022) with finite- sample complexity bounds for (RMDPs) using TV and x" 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 RI. Yang et al. 2023]. Finally, Badrinath and Kalathil [202] examined a general so-rectangular form of the uncertainty set, proposing model-free
algorithm for the online setting with linear function approximation to address large state spaces.
B Further discussions of Theorem and Theorem 3
What norms are included in the Definition TP In our upper bound result Theorems and 1 we upper bound the sample complexity for C norms and TV. The set of C smooth norm is very large as it includes all, Ep norm, weighted, rescaled Lp norms for p 2. Weighted norms can be useful in practice,
weights on dangerous specific states in Robust MDPs formulation such as in Russel et al. [2019]. Morcover, note that our result can generalize to metric or pscudo metric (which are not homogencous ic
get
||| X| ||=||| Ye E IR", À E R) with norms of the form x + o (E o( (((x)))) with
@ convex incising function such as the norm is still positive, definite positive. Choosing o x:) = xx leads to the Lp norms.
Assumptions on in Theorems 7 and 3 and Assumptions on < for lower bound. When y is small (e.g.. 7 (0, 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 y E (c, 1) for some small positive constant c, such as 7 E [ 1). However, the theorems can be directly extended to a broader range of y E (c. 1) along with e as small as desired so that almost cover the
full range (0, 1).
Why final results on s depend on #?
Theorem is data dependent which is deppoeees-- measure. However, taking the minimum of this quantity leads to the same bound as is sa-rectangular, so to illustrate RMDPs, quantity, while the less tight upper bound
that it possible to get tighter bounds for s-rectangular with instance-dependee
we decide to write also candomness-depentee is written also in the theorem, taking the first term the min operator in 2T
Why our results are still true for TV? Theorems and are stated for C2 smooth norms, however, our result is still true for TV which is not C 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 Cs 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. [nd Bs proportional 1/c where the "sample complexity" term is proportional to I/e². The smooth term depending on Cs or burn-in is then not too large for sufficiently small compared to the other term, which will give final sample complexity.
Why this not extendable to f-divergence currently? ? The f-divergence as distinct family of divergence is beyond the scope of this paper. Current proof for arbitrary norms cannot be di- rectly 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 interesting future direction.
16

---

C
Preliminaries
These quantities appear in the dual formulation of the robust optimization problem and pre- ciously the dual span semi norm sp(-). note that for L2, we retrieve the classical mean with the definition of w) With slight abuse of notation,
denote 0 (resp. 1) as the all-zero (resp. all-one) vector. We then introduce the notation [T] = {1,-- ... } for any positive integer I >> 0. Then, for [ I and y - [yilisis the notation S y (resp. means 2; S Yi (resp. 3; 2 y/) Finally, for any vector x, the notation is overloaded by letting r22 [sss a)² (s,a)ESxA (resp. x²2 (r(s))).es) Finally, we drop the subscript ||-I] write
all < for two vectors
y)
4f (+) 4 (-) for both sa- and s- rectangular assumptions such that we write uncertainty set in the for sa-rectangular case u (.) or 20.0 (.) in the s-rectangular assumptions.
Matrix and Vector Notations. We define the following notation.
SR the reward function, such that ((s.a) r(s, a) for all (s,a) E A.
p0 E SAXS the nominal transition kernel matrix using P as the (s, a)-th row.
0o e SAXS the estimated nomimal transition kernel matrix with po a,a as the (s, ah row
II" E (0, 1x5AA the projection matrix associated with a policy π
H(1)
T
T
u (2) T
II
(24)
TT
T
((s)
where I
17 *x1)> x(2)) (2)).....
1 (8) RA simplex vector such
1 [i) (I(a, (10](11):: (.,
The two matrices PV E RAXS pV E SAXS represent the probability transition kernel in the uncertainty set that leads the worst-case value for any vector V R.S. Moreover, the quantities PV. (resp. PV,)) stands for the (s, a) row of the transition matrix pV (resp. pv). In sa-rectangular case the (s, a)-t rows of these transition matrices are defined as
PV = argmilpezze PV, and PV 8,0
= wag.min-pua..r..... . PV.
(25a)
Moreover, the shorthand notation defined below used
argmin p pv
p PV
(25b)
8,0
8.0 = p
argmin pVn.a
(25c)
pr. = pV
argmin pegmin (oo. PVT.
(25d)
s.a
Po,V =
p
argmin argmippemme PVaa
(25e)
In the following, we define the corresponding probability transition matrices which are denoted by pm.V E SAXS pe.. E RAAx p..VV E SAXS and er.D E SAXS
Using the projection over म, the matrices pa E R f. S p..V RSS
E SxS represent probability transition matrices p=.V E RSSS PT..V E Rxx and pT.
w.r.t. policy x.
pr = 11
P= Po
Pv.VV II P..
p 11 P
p V VV.
and
I P=.
(26)
For s-rectangular, we will use the same notation for these transition matrices. Finally, we denote pa as the s-th row of the transition matrix px
17

---

E R is the reward function restricted to the actions chosen by π. r1 VVrp(V) E RSA is the variance for a given transition kernel E RSAxS and vector V E IRS we denote the (s, a)-th row of (ar as
(sr a) = Varp... (V).
(27)
C.1 Additional definitions and basic facts
For any norm smooth ||-I| introduced i we define the span semi norm Definition 2 (Span semi norm). Given any norm || ||. we define the span semi norm sp(z)
minweR ||e - w1ll and the generalized mean as w(xx == arg minweR | - -w-l
Let vector P E IR 1x8 and vector V E RR we define the variance VVr = P(V o V) - (PV) o (PV). The following lemma bounds the Lipschitz constant of the variance function.
(28)
Lemma 1. SSh et al. (2023 Lemma 2 Assuming S V1, 1/2 S - which obey [|V V22loo S x, then P E ASS), one has
2x
(V1) Varp (V2)l
(29)
(1-
Lemma 2. |Panaganti and Kalathil 2022 Lemma 6] Consider any E (0, For any fixed policy and fixed value vector V E R², one has with probability at least 1 - 5.
V log( 2SA N
Varp.. Varpr pr (V) &
1.
C.2 Empirical robust MDP Mrab Bellman equations
We define the robust MDP Miob (S, ", 7, 21 (P9); r based on the estimated nominal distribution po in TT.. Then, we denote the associated robust value function (resp. robust Q-function) are V7,00 (resp. QTic qnd we can notice that that Q is the unique-fixed point of F (-) (see Lemma C.3 the empirical robust Bellman operator constructed using P0, Finally, similarly (9. for Mrob. the Bellman's 's optimality principle gives the following robust Bellman consistency equation (resp. robust Bellman optimality equation) for sa-rectangular assumptions:
Qua (s, = r(s, a) +
PVx.o inf Petei (Po.a)
(30a)
inf (s, r(s,a) Petmi (P2.))
PVAio
(30b)
Using matrix notation, we can write the robust Bellman consistency equations as
Q
inf (Po)
PVz.a and @Ta =r+ inf Pet
Pvz.
(31)
which imply
inf pyno (1) Fn + p pT. va
V Tx +111"
Petr (Po)
Vmo rr +11
inf Pva.o (ii)
Ts + 7 P V.
pa
(32)
Petma (Fo)
where (i) and (ii) hold by the definitions in 24 25 same notation, removing subscript:
and
26 For s-rectangular, we can define the
V =r, + III
inf (PM)
PV + v..VV
V = + I
inf
ppxo (ii
rx + 7 P
(33)
Pelpo
18

---

C.3
Properties of the robust Bellman operator and dual representation
The robust Bellman operator (cf. 10 shares the y-contraction property of the standard Bellman operator as:
[Lyengar 2005
Theorem 3.2] Given y E [0, the robust Bellman operator (+) (cf. 10p is
y-contraction w.r.t ||- Il.0 More formally, for any Q1, Q2 E RS s.t. Qi(s, Q2(5, E 0, T-7 for all (s, a) e S A, one has
- T [T (Q2)l s111 Q21l It can be also shown that, Qn1 is the unique fixed point of TT (-) obeying 0 S Q all (s,a) 8 A.
(34)
1 for
One of the main contributions is 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 TV 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 [yyengar] 2005) but the proof was done uniquely for the TV and the x" case. Before continuing, for any RS denote [V], as its clipped version by some non-negative vector a, namely.
aa (V(s),
if if) a((),
[V]a(s)
(35)
otherwise.
Defining the gradient of P + |||| as V IlI. À > 0, a positive scalar and w the generalized mean defined as the argmin the definition of the span semi norm Def we derive two optimization lemmas.
Lemma 3 (Strong duality using norm ||-|| in the sa-rectangular case.). Consider any probability vector P E (SS) and any fixed uncertainty level a, we abbreviate the notation of the uncertainty set
2 (P) (cf. 33 as Usa (P). For any vector V IRS obeying V 0, recalling the definition of
Iill
[V]o in 35 one has
{P(V (1 a (sp((V ( 1)))).)}}
inf PV (P)
max
(36)
# EME
{PIV -
max EA
(37)
where sp(). is defined in 2 Here, the two auxiliary variational family A daw M are defined as below:
A =app A.
Aw
E
0,
(38)
Mpr
[up N.w =V ap Aw
X, A PE ASS) ER A.
0.
(39)
(40)
For L1 or TV, case, the vector ap reduces to a dimensional scalar such as a E [0,1/(1 - 7)].
Proof.
inf PV = Petc
inf (P.PEA.. P.PEA..IPPPII.. - ΣP(S)((s)
inf [o:llv] $o.1y=0, Ev(s)(((s)
= PV +
19

---

where we use the change of variable y(s") P(s)) P(s") for all s' E S. Then the Lagrangian function of the above optimization problem can be written follows:
inf PV PPV + sup (P)
inf 220EER tallla Sa}
_u(())((') + ((((s)(V(6) p(s5) v) (41)
(a)
PV +
sup M20,ER
-m(d))((') [IV(ss) mls') - -v1)ll.
(42)
(b)
sup P(V - - -1).
(43)
where μ E R7, E R are Lagrangian variables, (a) is true using the equality case of Cauchy-Swarte inequality for dual norm Yang [199T]. and (b) due the definition of the span semi-norm (see CC). The value that maximizes the inner maximization problem in 42) in wVV, j4) is the generalized- mean by definition denoted with abbreviate notation w. 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 (V μ w), it satisfies
| V
||vll
(44)
The quantity is replaced by the generalized mean for equality in (b) while (44) comes from Yang [191]]. Using complementary slackness Karush [2013)stackness stackness let B = {s E S uss) > 0}
Vs B: y (s) P(s),
(45)
which leads to the following equality by plugging the previous 1 wt
45 in 44 and defining x
B, 2s)s) = 11 V (s)
(46)
or
E B.
V(s) - (s) = + AV (s)
(47)
by letting À = 1|2*1l_ E RR Note that here the hypothesis of are use and especially separability is needed ensure that for E B, V Myll = V [|]]| only depend on P(s) and not on other coordinates. which is true form generalized Lp norms. We can remark that e μ is P dependent, but if P is known, the best μr only determined by one dimensional parameters X = ||e 1r* =11. and RR Moreover, when fixed, the scalar w is constant is fully determined by P. and μ², This is why the quantity defined a²: varies through 2 parameter À and w. Given this observation, we can rewrite the optimization problem as
sup P(V - p) - asp(V - 1). = sup P(V - osp((V - 1 )),
(48)
#20
EMM
sup PIV A- - osp([V] (1 )
(49)
ap EAA"
where we defined the maximization problem on μ not in R$ but at the optimal in the variational Ae (A,w) R²_ P A(S)). We can rewrite the optimization
family denote M {u ap problem in terms of ap with [V 3, defined in 35 Contrary to the TV case, a is not a scalar but
A.w ap 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'-regularity on norms, the subgradient space of the norm reduce to the singleton of the gradient in our case. C smoothness will be needed in concentration part while it is possible to be more general in optimization lemmas.
A.or reduces to a positive scalar denoted Note that for TV or L,, this lemma holds, but the vector ap which is equal to ||e 1r" II., according Iyengar 20055.
Lemma 4 (Strong duality for the distance induced by the norm |||| in the s-rectangular case.). Consider any probability vector pa = 11 e for P e A(S)A any fixed uncertainty level ō
20

---

and the uncertainty set Ui..il1 (P), we abbreviate the subscript to use U (P) = (P). Then for
any vector V IR$ obeying 2 0, recalling the definition of [V]a in 35 one has
inf (PU
P"V Σ π [aals\(
max
Psal Paa[Vaag A. - @1 sp([V) sp((V)oz))))
(50)
Pen EAPan
with the definition of sp(p) in and where the variational familyy do is defined as
Ap = E
aa= w + PI = ap 1
(51)
(52)
with w is the generalized mean defined as the argmin the definition of the span semi norm in 2 and
X, w a positive sealar. Moreover, for L1 or TV, case, the vector ap A reduces to a dimensional scalar such
10, -)]]
In the proof of the previous lemma, we decompose this problem s-rectangular radius ā into sa- rectangular sub-problem with respectively radius sa-
Proof.
inf p (P=)
paV
inf inf
ET(als)P'
(ara M (allss) Preuein(P...
Σ T(aas) Pau V
min (oaallaa (a)
Σ <alss)
min
Ev(s'V
Paa)
where we use the change of variable y(s') Pea (s') Psa (5') in (a). Then we case use the previous lemma for sa rectangular assumption, Lemma Then,
min fomilloallss
Σ T(als)
min (willillSo...1y=0.... Paat
E Ev(s'iv
min (
Σ ग. (aass) max #20
(- Psalt sasp(V 11).)
Σ T(als) max (- [eaa: [S) 120
Σ #(als)asp(V - 1))
max
Σ (a)s)) max
(-Psalt)
||TTTl sp(V - -p) 1))
420
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 [928] and using Cauchy Swartz inequality which is attained in the last equality. Finally, obtain:
inf Petri (P)
PT Σ T(als) max Psa(V - 11) - @1 sp(V - -1).) 1220
Σ T(als)
Pea Paa[Vaak Mapa - - 1|Toll sp((V (a )=)
max Jel A. Pee A
where in (a) we use the previous lemma for sa- rectangular case. Note that as we are using sa- rectangular case, for TV or L1, this lemma holds, but the vector a reduces to positive scalar denoted a which is equal to | - 1r' (See also Iyyngar (005))-
21

---

D Proof of the upper bound
Theorem
1 and 3
D.1 Technical lemmas
We begin with a key lemma concerning the dynamic range of the robust value function V* (cf. which produces tighter control when large; the proof is deferred to Appendix D.3.1 This lemma allows tighter control compared to Clavier et al. [2023].
Lemma 5. sa- un-rectangular case (see (3) for any nominal transition kernel E SRAS any
fixed uncertainty level a, and any policy n, its corresponding robust value function Vao (cf. satisfies
sp(V )x S max - 1, C9
(53)
where C, (/ ||==1]) is geometric constant depending on the geometry of the norm. For example, for Lp. norms 2 1, C. 2 1 which reduce the sample complexity. In s-rectangular case, we obtain slightly different lemma because of the dependency on
Lemma 6. The infinite span semi norm be controlled as follows for every s in s-rectanuglar case (See 5 )
1
sp(V=.o)
)oo S ? max - Y, |ol. C,ō} ry max - Y, ming Tell. C5
(54)
where C. min, is 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 sa- and 8- rectangular case is that we have an extra dependency on ||T,|,,, which represents how stochastic the policy can be s rectangular MDPs.
Lemma 7. Consider MDP with transition kernel matrix P and reward function 0 < < For any policy x and its associated state transition matrix P. = II P and value function 0 S VR.P S T-q
(cf. 11) ), one has for sa- and 8- rectangular assumptions.
8
(T-7P=) V Varp, (V=.P) S
1 72 7)2 7))8p((vr.P)
See D.3.7 for the proof
D.2
Proof of Theorem and Theorem
3
The first decomposition of the proof of Theorem [ and Theorem 3 Agarwal et al. (2020) while the argument needs essential adjustments order to adapt to the robustness setting. One has by assumptions using any planner in empirical RMDPs:
| - - I1 I Copt:
(55)
using previous inequality, performance gap
| V ll can be upper bounded using steps.
First step: subdivide the performance gap in 3 terms. We recall the definition of the optimal robust policy n² with regard Mrob and the optimal robust policy म*, the optimal robust value function 47.00 (resp. robust value function @m.0) w.r.t Mrob- Then, the performance gap V*too V can be decomposed in one optimization term and two statistical error terms
V+. vū,0
V=" / -ix'0) (D=ii ( 1i---vVa v)*00) + (D*'0- -V8.0 (
(DR. V4o
y - - + (v - + (pā-0- - -V
(
yxx'o - pxx + Eopt + (pã.0 - V2.0) (12.0
(56)
22

---

where (i) holds by --*'-~~*** < 0 since A* is the robust optimal policy for Mrob. and (ii) comes from (5) 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 more general term V=.0 v for any policy even if control of these two terms slightly differ at the end. Using (32 it holds that for both sa- and s-rectangular assumptions:
VT V =r P..T pm (rx + +pt.
= =(7P"
D pm - p + (s ppn.vproo- -ypo-
( S 27(p0 pT. Vav - pa. vaie) + (2L" Daa - 70. pno))
where (i) holds because P < p...Vi because of the optimality of pa..v (see. Factorizing terms leads to the following equation
(5)
V V= S > ( (I- (1- "
(57)
In the same manner, we can also obtain a lower bound of this quantity:
V VaT = x + 7P p. Vu
- (rx +IpT. Vo.0)
(2 D. p: -10--7p -pP ( + pn Pa.o - - V
2 7 px.V - pa. pm..) + (xI" pm pppa )
(1 (1-2p=0)² -1 (p"D pno - p
(58)
Using both 57 and 58
we obtain infinite norm control:
|i - V Io S y max
(1-
-1 (pm. v - pm. pmrp) lmo
|| (1-72))))
( mT P px ppt }
(59)
By decomposing the error in a symmetric way, he have
| V=,0 1o S max
{ll (1-25Th) -1 ( px.
- -
-1 T. V -P-V-V--VVs (1-22"0) 2 (e
(60)
Armed with these inequalities,
we can use concentration inequalities to upper bound the two remaining terms || V=*,0r 1rl'o and |7.00 v 00 in (56). Taking क = म, applying (59 leads to
| - 11o0 S y max {/l (1-221)))))
P F.V p p pa:0
(1 (1-2eay) ( (p*P PR.o _ 1
(61)
Finally, n = "," applying (60) gives us
pim' - v= 111000 S max [1111-p-11 -1
(p"tiv 11"""""(p"""" (p"'iv=''o '==io- - px serNvi'))l
VT 111-22"'01 )'(((0
.D
N -1
V - - )b.}
2 V
L
(62)
Note that to control || y=" 10 x.' we use decomposition not depending मे for value function as y= - deterministic and fixed, allowing use of classical concentration analysis tools. This decomposition is the same for both sc-rectangular and s-rectangular case.
23

---

Second step: bound first term and second term in 62 to control ||²=' V* /1 To control the two terms in (62) we use lemma based Bernstein s concentration argument and whose proof is in Appendix D.3.3
Lemma 8. For both sa- and s-rectangular setting, consider any E (0, 1), with probability it holds:
L p Pr V=' - V= < N V par (V+o) +
3LCs ||1|1 N -7) 7)
(63)
with L log ||2|1, SAN/8) and where Var (V*.0) is defined in (2 Moreover, for the specific case of TV, this lemma is true without the smoothness term
3LCa||1
N(1-7)
Armed with the above lemma, now we control the first term on the right-hand side of (62) follows:
(1 1-
V=' pp VVV.V"n
(a)
1 1- ;
-1
p V V=' - -pri.
(b)
1 (1- -1
L Vaa pm (V+ir)+
3LCs ||111:
2
N(1 7)
<
(1- <11-21=11)
13LCs ||-||
1 2
N (1
L
11
v get Varget
Var
(V.o)
N(1 N(1-7)
=RR,
L
I - 1----:;)- Varp.. (VAi0) - Vargat.r(V
+ 2
N
=R
L
[ (I-
+ 2
Warrpr pu (Vi.r)- V Var (V+.0)
(64)
N
Rg
where (a) holds as the matrix [ 11 the last point holds from the following decomposition for variance and triangular inequality
is positive definite, (b) holds due to Lemma 8 and
Varp.. (V+,0) (V = ( (v Var pm (V+r)) - v Var pr. (V+.o) +
Var (V+.))
Var (Var)- / Var (V+.o))
+ V/argar (V+rr)- (Vtto)-
Var Varget (V*a)
Varp (VVro))
Finally, the fact that p. is stochastic matrix,
(1- (
(65)
Armed with these inequalities, the three terms R1, R2, Rs in 664 can be controlled separately.
Consider R1. We first introduce the following lemma, whose proof is postponed Ap- pendix D33.4
24

---

Lemma 9. Consider any 5 E (0, 1). With probability at least 1 6, one has
(1+ (V (1-7)aN + 11 1.
(1 (1-22- 11 v Var yargmriv (V+,0) S (V s4\
N(1-7) 73(1 - 7)22 max 7/ Czo}
L (1+ (V 1-PY + M(1))
-
S $41
(1 7)3
with L = 2og
18 1811 in the sa-rectangular case. In the s-rectangular case, it holds:
5
- 1\ 7 - 7)2 ///mmx/11 7/s Cgō min, || [Tl)
(1+ (V + N(1-)
(1-7e=-i -1
V Var prs Vargar (Vir)s
(1+ (Vu-irx 1
i-- (1 71
+ N(1-7
< 1
Using Lemma 9 and inserting back to (64) gives in sa-rectangular case
T
[ "1=
R1 = 2V
Vargar ger (Vv.0)
Var
N
L
L
Cs C1|1 L
< 8
73 - 7) max - 7: Cgo 1+ V (1 7)2
+
N(1 - 7) 1. (66)
Consider R2, First, denote V = V* n1 17 E R. by Lemma
we have for any n.
1
5 min |V 1 y max(1 7. Cgo
(67)
for so-rectangular case or in s-rectangular we obtain
1
0 S min V 1111
(68)
7 max(( 7, 70 ||
by the definition of the span semi norm. Moreover, we can use Holder with Lı and Loo we have for both sa and s-rectangular case to as it holds that:
Varp P... (V*.9) - Varr... (V*9)] = Var ps,. (V') - Varr.,. (V')l
< P..a- Ps.a 1/ -
01
(max (1 - Cgo))
$ 22 (1xx((1-)),
(69)
In the first inequality, we use I = ||| and and we use Lemma 5 in (a) where C, 01.
With the same arguments for s-rectangular, we obtain for V'= V*: -111 17 E RR
Var p. (V+.) Varr, (V++)) = |I (Var (V') Varr (V')
(als) Σ (P.(s'. (((ssa))
(70)
1 ΣΣ
n" (als)
P.(s', a)) - 1 / /| C31
(71)
3C2 ll.
V'Il
V'
15
1.
(72)
7 7| 11. 5CA
7
25

---

where (a) comes Eq 126 (b) comes lemma 0 or more precisely eq 1339. Then, taking the sup over in the previous equations, holds
II" (Varp, (V*.0)- Varr, (V4.0)) inf nER+ I1V 1)1'|
(73)
?
7 min, >| 1l. Cg 1.
(74)
Applying the previous inequality, holds in sa-rectangular case:
L -
11>
-1
R₂ = V N
Varp.. (VA.0) - Var par. (V+ro))
2/ N [-yp" ->="">>"
L
|II=' (Varpa(V<.o)) - Var (V+.o))
L (1-2P" -. ")
-1
$ 2
V/ - Var & (V+ia))
L
[ ->p""
1
2
(75)
N
72 max(111x, Coo
L
2 4 72 7)2 max 7, Coo
(76)
where the last inequality uses the s-rectangular case, we obtain a different result
(1-22"
-1
1 S - I (cf. 655 for so-rectangular. In
L 1 7--pp" ","""""
-1
R₂ 2/
Varp.. (V+t)) Var ge .v (Vrr))
L
1 ---
VITT (Varpo(V<o) - Var v (V+.o))
2 N
L
$ 2
(77)
N
72 max(1 7, ming || T ao C5ō}
L
2// 72 7)2 max (1 7. ming
|| oC,IN
(78)
Consider R3. The following lemma plays an important role. Applying Lemma 2 and using π n" and V V*.g it holds
V 2 log 25A
Var (V+.)= v Var (Vtt)) (V+:0)+
20
1,
N
which can be inserted in 64) to gives
R₂ 2/ N
L
1
- ( (Varat (V+o)- v Var (V
7
ppt
log(
SAN
] 1
4L
< (1 7)
15 (1 2)2
1,
(79)
N
(1 (1-25-i))
-1
where the last line uses
1 15 - 1 (cf.
65
26

---

Finally, inserting the results of R1 in (66) R₂ in (76). R3 in
779 and 65 back into
664
gives
1 1- pT -1
( Va o pp", pat.VVa'.o)
(80)
L
L
-s1111,44
3LCs ||1I,
58 8
(1 7) max (1- y. Coo
1+ 1+1 1+ (1--)2N
+
N(1 ((1->)
N(1 7)
2L
4L
2
72 7)2 max | 7, Co0
(1 7))
2T.
I.
Cs 111111.4 L
4T.
< 10 $10
[+ (+/(a- (1-7)
73 7)2 max 7, Cgo
N(1 V(1-18 7)
(1 7)2
(81)
3LCs |||||
N(1 7)
Ca
L(1 + N(179)
7LCs ||
< <160
(82)
(1- (1-+)3mas max 11 - y, C N(1 7)
where the last inequality holds by the fact y 2 and letting 2 (1-7)2- We have the same result for s-rectangular, replacing, max 0 by max 7, min, || oC₁}.
Now we are ready to control second term in 62 to control |i y'''""loo. To proceed, applying Lemma 8 on the second term of the right-hand side of leads
1 (1~ (1-
p pp".v' o - VVtia
< (1-7 3p" pprt 1) -1
)7(22)
(2V ((2v
N V Var (V+.)= + 3LC's ||1|1.
I
N(1 (1)
< 1 - ,,"p .) -1 L'C's ||1||.
L N(1 7) + +2 N (I - (1->p-';)
Var pa. (Vor,o)
R.
L 1 - 1 1))
-1 (
2
Var Var pr (V= -VV (x7,0)
RiRs
[ 1 "" Varp (V+.0)= - Var p (V+.o))
+ 2
N
R:Ro
L
I (1-クpーー)~ -1 (Vaarpr (V+.0)- v Var (Vrr)
"
2
(83)
N
R;
We now bound the above four terms R4, Rs, Ra, R7 separately.
27

---

Using Lemma with P = p x and V -rri which follow Pr
Tx + TP V and in view (65). the term RS in 83 can be controlled as follows:
L
RF 1)- Var Be (Viyg)
R4 = 2
P
N
L
8min (VT,)) (ni 1/(1 1011-)) 7))
< 2
N
72(1 101-77 7)
L
s 8 V 73 7)2 max 7, Cg
(84)
where the last incquality is due to Lemma 5 for so-rectangular case and with the same quantity replacing max(1 7, ) by max y, min, || ll. J} in the s- rectangular case.
For bounding R3, we can simply use 665)) to get
R3
L 2/
(I 1
p -1
Var p . (V - -
N
$ 2
|00 - P=' 1. (1 7)2N
(85)
Rs 2
V - pr
1.
(86)
(1 - 2)N
The term Rs upper bounded as 766 follows:
2L
Rs S 2
72 7) max (1 y, Cgr 1.
(87)
for sa-rectangular case and with the same quantity replacing max - 7, Cgo} by max
Y, ming || ll. 5C,} } in the s- rectangular case.
Finally, R₂ can be controlled the same as 779 shown below:
4L
R₂ <
1.
(88)
2
Combining the results in
84
86
87 and
88 and inserting back to
83 leads to for N 2
1.
[1 (1
L(1
Cs C311111
(I-xP=-)) p Vx'
p VV'VV''oo 581
N(1-7)
73(1 7)2 max [1 7, Cyo
(1 NN | pa _a
L
2L
7LC's ||1|/. N(1 7)
+ 2
1 1 1+2 2
72(1 73
max (1 7, CyooN
L(1 1s1|11|
N(177)
L
Vio 1 -="10
7LCss |||||
< 80
+
1 1+
(1 7] max (1 7, C, J.N
(1-
N(1 7(1-7)²
80
(89)
28

---

where the last inequality follows from the assumption y 2 4' Finally, inserting 62 yields
82 and 89 back to
-V== -V=
| - V='-0
10 S max
160
L(1 + N(1
7 ||-11. N(1 711-))²
(1 -1-18 -)- max 7, Cgo
101 (1 - 7)2 max - 7/6 Cgo +2V
L(1 + N(1-7)
Cal
T.
Vio | pa
7LCSs || + N(1 7)
(1 (1-7)2N
Cal1211.)
L(1 + N(1-7))
14LC's ||
< 160 (1 (1-7)=max(1 7, Coo
(90)
N(1 711-))²
where the last inequality holds by taking N 1olg SAN)
rearranging terms. In s-rectangular case, we obtain the same result, replacing max(1 7. C } by max y, min, || C₂ō).
Third step: controlling || - V Io 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 (6T), which proved in Appendix []3.3
Lemma 10. Consider any d (0,1) 1). Taking N I," with probability least 1 5, one has for sa- or s-rectangular case:
V P V=. - pR..PR..
L' V /aarp (v+10) + 2o 1 C5L"Cs |1l1l $21 N
N(1 -7)
L"
+ 28 + 14L"Os ||
s /
91))
(1 (1-7)- 11-ク)
N(1 (1
with L" = 2 log(
14/11S8ANN (1-7)6
). Moreover, for TV this lemma holds but without the geometric term
C4r"Cs11 1. Taking the sup over s gives the final result.
N(1-))
With Lemma 10 in hand, we have to control first term in 61
(1-20=.)) -1
P pR. - -P..V8...))
( (1-2Da.D) -1
pao p
I'
1 --> V Varpa (Dri)) + (1-2DR.V8)
< 2 N
25
(92)
11 - -,...r
-1 14L"Cs IIII,
N(1 77)
2topt 1-7
L' (I (1-ppR)) -1
1+ 1+2V
Var pa. (V#..))
L' (1 (1=2
+ 21 V
Var ps. (V+.0) Var psi v (D+.00))
+ 2
L'
1 - (
V
Var (D+.0)
Var pa, (D+.o)
14L"Cs |||||_
1,
(93)
N
N(1 - -7)²
=:S
29

---

where (i) and (ii) hold by the fact that each row of (1 (1-7) 7) (1- is probability vector that falls into (SS). The remainder of the proof will focus on controlling the three terms in 93 separately.
For S1, we introduce the following lemma, whose proof is postponed to D.3.6
I." Lemma 11. Consider any ò E (0, 1). Taking N 2 (I- one has with probability at least
8. for sa- rectangular
L"CG||111_
+ Eopt +
(-7 (1-)Pt.)²
V
Var pa. (Vi.))
S <6\
N((1-)
70 7)2 max 0,
1 + Eapt + 1."Os| 111.
N((1-)) (1- 78
S <61
and for s-rectangular
L" + Copt + M(1-))
Cell
(I (1-1E*))) V Varp*. p*. (VR.)) s 61
73 7)2 max 7, GG min, | 100)
L" + Eopt + NN(17))
Collblla
61
1.
7)
Applying Lemma 11 and (65)
(93) leads
S = 2/ N
L'
[ -270)7 V
Var pa. (VR.0)
L"
$ 12
(94)
31 - 7)2 max C,o
for sa-rectangular and the same quantity replacing max(1 - 7, Cgo} by max(1
7: Cōō minmin [ for s- rectangular case.
Applying Lemma with |! V.. 1lo0 Eapt and 65 S2 be controlled
2 = 2/ L" [ (I-
Var p+.v (V+na) Var pa. Var (v=.00)
L"
[ (1-2PR))-
1 -
EopeL""
$ <4 N
Eopt
S 8
V
(1 - 7 1.
(95)
. S3 can be controlled similar to R2 in 76) as follows:
S3 =1 N
1 (1-7Pa.)7
Varpa (D+.)) - Var pa. (Dv.o)
L"" (1-22a.07
1 72 max(1 7, C.oJ
< 4
(96)
N
L"
88
(97)
72 7)2 max (1 - 7,, CyotN
for sa-rectangular and replacing max (1 7, by max(1 7, ā min, [l for rectangular case.
30

---

Finally, summing up the results in 194 195 L" N
and 997 and inserting them back to (93 yields: taking
(1- with probability at least 8,
P R, P
6 - pa.V v..0
2oopt
C4L"Cs |1]1
v 1 --7)
1
N(1
7)
L" + Copt + C3 1111.
N(1-7)
EoptL'
+ 12
81 V
(1- 1+
(98)
(1 - 7)3 max - C J. N
D'
8
21 ?) max n, Coo
L" 1 + Eopt + Ca
N(1-2)
+ +8/ (1- (1 7)aN 1 15L"Cs |1]1
28opt?
Eopt
s 16 73 7)² max(1 1- 7, J.
+
N(1 - 77)
(99)
(100)
for sa-rectangular and the same quantity replacing max - 7, ]r} by max - 7, ā min, [|
for 8- rectangular case. In this step, it is harder to decouple terms as 8/* depends on data both in π.
and V.
Step 5: controlling |i.00 V boo bounding the second term in (6 Towards this, applying
Lemma 10 leads to in sa-rectangular case:
(I 1 1 P paoo - - pa. 5 <11-2R))1))
RR. pa. p
pa. pr.0
L"
1 ( V (V+.)) + (I (1-2PR.V) -1 2Eopt
$ 2 N
(101)
-1 1"14C's |1111.
+ -pR.))
N(1 77)
25ap
L"
(1- (I-DDRrV) -1
V Varper (V3.)) (V (1000)+((~22R)))) -1 114L" ||]|l,,
5 (1-
1+21
N
N(1 -7)
+ 21
T!
- >Pai))
-1
V -V VRR
N
L"
[ (1>1)t.)7 / V/Vara.v(Dvo.) Var ((D3.0)
+ 2
N
L"
N (1 (I=
-1
Varppa (D..0) Var ps.v (Dr..))
+ 2
(102)
=.S,
We shall bound each of the terms separately.
Applying Lemma
7 with P pä.V ग म, and taking V Vř,o which obeys VŘ.0
TR + 7.P.VV a, the term S4 can be controlled similar to 84 as follows:
Cull1ll.
L" 1 + Eopt + N(11 73 7 max 7, C,o)
S s 8\
(103)
for sa-rectangular and the same quantity replacing max(1 - 7, Cgo) by max(1 7, ming Il, 5C₂} for rectangular case.
31

---

For S5, is observed that
L" S =5 N
(T (
V Varpa.v (Va. - V
L"
Va.0- - p7.00
s 2
1.
(104)
(1 (1-
Next, observing that Sg and Sn are almost the same as the terms S2 (controlled in (95 and
S3 (controlled (97) in (3). it easily verified that they can be controlled as follows
Eopt L"
L"
S6 S S (1 (1-7)
St S V 72(1 - 7)² max [ 7, C2o 1.
(105)
for sa-rectangular and the same quantity replacing max 1 - 7/ J by max 7, min,
for 8- rectangular case. Then inserting the results in [03). (004 and (105) back to (02 leads to
(I (1
F.V pao
_ pa.
(106)
2oopt
L" 1 + Eopt + N(1-7)
Cs11111.
14T |11|1
1
(1 7)
73(1 - (11 max - -,,0NN
N(1-7))
L"
| - 1
L"
+ 2 V
1 1+ 1+4/ (1-
+ 1V 7- 7)2 max - 7. Cgo
(1 1-))2N
L" (1(1 + Eopt + Csl1ill
< 12
N(1-7)
+ V (1 (1-
1
va. - p
(107)
(1 - 7/ 7))22xx max - O.
3Sopt 1 14L"Cs ||111.
+ (1 7) N(1 7)2
(108)
(109)
Taking N > 161."
T-y- we obtain
25 (1->)
+ 4aapt V [1->)'m 1 <
1."
3 (1-y)
with probability at least 8,
inserting 199 and 107) back to (61
|| | vū.o0 < max 16
1." 1 + Copt
+
N(1
2Eopt"
14L"Cs ||1]|
7:(1 mamx 71 J. +
+ N - 7)2
(1 (1-
L" (1 Eopt Copt +
Cs Ca|l11|
12 (1 m)xmmx(1 7,, J.N
N(1
+ 1 (1 (1-7)2N
I
V80 - p&.
(110)
3copt + 14 ||1//-
+ (1 7)
N(1 -7) s
T." 1 + Copt + Cs 1/1
NI1 x)
6Eept (1-7)
28L"C' ||1||+
48
(111)
70(1 - (1"
7 max(1 - 7, C,a
for sa-rectangular and the same quantity, replacing max{1 7,, CG } by max{1 -, ō min, }l for s- rectangular case. The proof is similar for TV without the geometric term depending on Css.
Step 6: summing all the previous inequalities results. Using all the previous results in (90) and 161."
|11 and inserting back to (56) complete the proof as follows: taking N 2 ( 7 > 1/4,, with
32

---

probability at least 1 - ò, for sa-rectangular
|V~0 V8.0 10c S | pm 2 + Eapt + 1188:0 - VF.a 1l.c
I (1 Copt C211111, N(117)
6Eopt + Cs ||||
S Eopt 48
7: 7)2 max - 7/s J
(1-7)
N(1-))²
T.11 + N(1-7)
14LCs ||1||
+ 160
(1 31-91 7)3 max 7, CgooNN
N(1 -)
LI + Cai |||
42I ||1|1.
N(1
+
N(1 7)2 + 1508
(1 (1- m1=-))mmx([1 7: J
(112)
where the last inequality holds by 7 2 1 and 2 16
[1-)] for sa-rectangular and the same quantity
replacing max 7 by max 7, 7 min, [1 [ll]] } for rectangular case. The proof is
similar for TV without the geometric term depending on Cs.
D.3
Proof of the auxiliary lemmas
D.3.1 Proof of Lemma 5
Similarly to Shi et 2023), denoting su the argmax of Va, such that V7,0 (su) min Va.0
using recursive Bellman s equation
max V (8) max SES
E
(a a()),)+ +
inf (P.))
PV
(113)
sES
(1+7
<
max (s.0)E8xAA
inf (P.)a
PVa.
(114)
where the second line holds since the reward function r(s, a) E [0, for all (8, E S x A.
Then we construct for any (s,a) E S x A, Pa.a E RR by reducing the values of some elements of Ps.a such that Ps.a 2 P..a 2 0 and Σ. (Pa.a (s') - P..a (s') oC'.a. with C ||->0] It
lead to Ps,a o0 e Ufi (Psa), where eso is the standard basis vector supported on 80, since
1
1 P..o + oCg - Pa.a
-
1 P..a Paol
C ||e.o a/2+a/2-0
(115)
2
2
Consequently,
inf (Poaa
PV < (Peu + +o 620
v= -= <
|| 11o0 + +oV (5)) C
(116)
< < (1-0a o) max VTT +0
min (T) sES
(117)
RES
where the second inequality holds by
Pa.a = - = -- - Pa (6)) + E Praa(s)
= oC (118)
Plugging this back to the previous relation gives
33

---

max V (8) S + 7(1 00000 0)
max V=.0
+g0
min (* sES
(119)
#E8
SEB
which, by rearranging terms, yields
1 1+ 70 a minses Vala
max SES
(5)
(120)
71 Cg 0)
+ min V (8) y max - 7, Cg o}
+ min V (s)
(1 - 7) + g0g
#ES
#ES
(121)
So rearranging terms it holds
1
y mmx 7/ C5.00 o sp(V 0
(122)
taking the sup over
1 ? max 7, Cg
sp(V
(123)
As we pick the supreme over s, the quantity, Cg is replaced by Cg 1/(min, ||ca|l) obtain control for every 8.
D.3.2 Proof of Lemma 6
Similarly denottng so the argmax v such that V=,0 (so) min,es (*:0(s) using recursive Bellman's 's equation
max (s) max E (s)s)) sE3
r(s,a)+ +2
inf PV*, (P))((s)
(124)
max sES'
11
inf p (PT)
payza
(125)
where the second line holds since the reward function r(s, a) [0, 1] for all (s,a) E S x A.Then we construct for any s E S Ps E SxA by reducing the values of some elements of P, such that P. > P, 2 and
Ya E A. -P. J C
where C2 is defined as 1/ /eelll. Writting |o ll S ã we construction a such that
Em(als) Σ (P. (s',a)) P.
(s',a)) (
||TT,l, ac
(126)
Not that this construction is possible as is simply Cauchy Swartz equality case. leads to P. + TeT E 21 (Ps), where esp.a E SXA is the standard basis vector supported on so which is equal at so for every a and otherwise.
/ C = 0/2 8/2
Pg + Cz - P.. - P.
(127)
2
2
34

---

as Ci o is equal to Că ||e,,] ll Consequently,
inf (PE)
papao 11 (P + oogee VT
(128)
Pa (s) (so) T(al))
(129)
Σ sup
P. (a))) V (80) ((n))(((8)))) =(als)os,a
(130)
max V (8) Σ cC (a) + Σ V (( SES
(131)
(
max v (s) 8Ct) ||l + || ll. o #ES
min (*) sES
(132)
< (1 - C x)
max ( + +o0g min V (s)
(133)
#E8
sES
where |/ is the norm of the vector x (.1s) and where (a) holds because
-((0)-- + - = -1
(134)
Finally (b) is due to (26) and using Holder's inequality in the second term. Plugging this back to the previous relation gives
VT (1) -0 [TT max sEB (s)0(s) + ( [T.l, o0g min Vs) (135)
max #ES
sE8
which, by rearranging terms, yields
1 yā TTll. Cj min (T)
max V= (8)
(136)
#ES
1->(1 Cāă Tx
S (1- 7) + || 7
+ min V (s)
(137)
#ES
1
min V (s) SES
(138)
(1- 7) + + |Tl.. Cgō
min
V (s).
(139)
7 max - 7, C2 |T, |1 σ)
sES
So rearranging and taking the sumpremum over all sterm it holds
sp(V T ) S
(140)
max min, || ll. C5ā]*
As we pick the supreme over s ovf this quantity, C is replaced by Cg = 1/ min, |e
D.3.3 Proof of Lemma 8
Proof. Concentration of the robust values function. with probability 8, holds:
L
Varpa, (V) + 3LCs ||
pT.VV V - $,0
V/
<
2
N
N(1 7(1-7)
35

---

with L = 2ogg 18 |||, SAN/6) and First we can use optimization duality such as in 500
p.. V - V..VV V
(141)
max
- (V (V (V
(sp((V - ())=)}
Aw EM "pq
9.u
po saa (V - pl
Aus ) - σ (sp((V -
upp 1),))
Aow
max
E.A
pu
< mmax
max Ppp EMP
po PV (V
A.
(sp((V
1e 1), ))²}
Ae
max
po (V
A.w (sp((V
(142)
"pp EM
max EMAw. ph.
po (V
1 po
Ao
N,w - sp
po.
)),
(143)
max Aw EMAAi PP R.a nia
po (V (V
11
Aie
- (sp((V- - poo 1)m
I mmxx
max WEN pg
pn 8.0
Du 8,0
(V -p
Now
EM An pg
max Aow
pn
s.a
-Pa)) (V
d. po
pq
(a (V))
(a (a
(144)
where in the first equality we use Lemma 3 The final inequality consequence of the Lipschitzness of the max operator. First, we control (a,a V). To do so, we use for fixed a A. and any vector V that is independent with po, the Bernstein's inequality, one has with probability at least 1 with sa-rectangular notations,
gs
Aw ()) ()=
(p 1
2 2log(3) 2 -Poo) Ma S
Varpo (V)
2 2log(3) 3N 77)
(145)
N
Once pointwise concentration derived, we will use uniform concentration to yield this lemma. First,
union bound, is obtained noticing that Is (a Aw V) is 1-Lipschitz w.r.t. À and w as it is linear in
and w. Moreover, X" IVV - -r" - wil, obeying X S |||||_ The quantity E [0, 1/11 7)]
1-7
as it is always smaller that by definition. We construct then a 2-dimensional a e en-net N. over
X E [0, | and w E [0, 1/(1 7)] whose size satisfies |Ne, < 3||1|||
Vershynin 2018
(1
Using union bound and 145).. it holds with probability at least that for all Ne..
2 logl gs V)
28A[Ng I
2 log( 28A1N Varro (V) +
(146)
N
3N 7)
36

---

Using the previous equation and also (144. it results in using notation logg 18SAN L.
(a)
ge,aaa, V)
sup aBEN,,
( - p. Maa +
IV3
log SAINi1))
2 2log( 28A[Ne)
Varpo (V) +
+ E1
(147)
N
3N - 7)
2SA[N
log( 2S.1
2 log
Varpo (V)
N
N(1 - 7)
L
I
N V Par (V)
(148)
N(1 - 7)
L
L
IV N(1-7)
s 2 V (1 2)
(149)
where (a) is because the optimal a falls into the e1-ball centered around some point inside Ne, and
Is.a (ar,, V) is 1-Lipschitz with regard to À and w, (b) is due to Eq. (146). (c) arises from taking log( 2841%G11
E1 (1-(1-)) (d) verified by |Ne. S (=il1-)) 2
I 9NV ||||| and that variance of a ceiling function of a vector is smaller than the variance of non- vector, and the last inequality comes
from the fact ||** I 1-- and taking 2 2 log( 185AN]]lI, 8 =
Contrary to the previous term, the second term ga,a V) is more difficult as we need concentration. Still, the data has an extra dependency through the parameter ar. We need to decouple this problem using absorbing MDPs. Then it leads
Ao .) Is.a .V)
(150)
= max
pp
s,a
- -Po)) (V - 1p )
Aow
(151)
Po EMA pn
2.a
max W M
8,0 p5 Pa.a) ((
Niw
+ (po - -p
(m
1
New
pr
)
(152)
max
po
5,a
(V
10po
Aow
+
max EM
(pe - po 8,0 6,a
(upp
) "pp
Aew
EM
(153)
In the first equality, we add the term pp to retrieve the previous concentration problem, fixing po and optimizing X, w. In the second, we extend the max using triangular inequality. The first term in the last equality is exactly the term have controlled previously, while the second one needs more attention. We decouple the data's 's dependency, then control the difference between the μu. Then using the characterization of the optimal (a from equation (47
Aw
(Pa
-00 2,a (1'po
A. 11 F.n.
)= Σ (Po (Paa Poo (x))
(V
pd P
psu 3,a
Here we assume that the subgradient is a gradient as we assume that the norm is C2, The question that arises is whether the gradient of the norm is Lipschitz.
A, A ) can be zero in the case where μ the Note that we are considering the worst case (urr0
Lagrangian variable is equal to zero. Finally, note that we can also control this term when one of
37

---

A. the two terms Hpo. or Aw is equal to zero as pp and Aw Mpg. smaller that V because V - need to be positive in equation (43 In this case, classical control using Bernstein's 's inequality without uniform concentration can applied, giving the same result. In the worst case where all terms in are non zero, assuming that the norm C2, using mean value theorem, we know that (upp 2 - Pp.
A,
po
A,d
[ s,a
1 1D1 -
|
sup xEA(8)
As the norm is C², continuous and as the simplex bounded, this quantity exists according the Extreme value theorem. It is possible compute this contact depending on S for explicit norms such as Tpp- Indeed, for Lz:
22 |0l|2
IS
T =
VS
|011
min |
where X is the Kronecker product. So have upper bound independent of æ. For Lpp ||5/|p norms, p 2 2, we have simple taking derivative twice:
| = p-1 (AP-2 9p096
V
Lp
with
abs((x)
A Diag
Lp
9p AP-2
Lip
where Diag the diagonal matrix. However, as x. S Leps A S I, we get
H p ||>||
S (p- 1)5 Cs
(154)
where the L,, is minimized for the uniform distribution. Then using Cauchy Swartz inequality, it holds
(po - Poo))
A. (1
-
New S <2 - 11 -e
(155)
[P Po )
To do so, we will use McDiarmid 11:
Then the question is how to bound the quantity inequality.
Definition 3. Bounded difference property
A function f X, X X. + R satisfies the bounded difference property if for each
I,...,7
the change of coordinate from 8; oy may change the value of the function most
Vi [n]: sup If (I), Si.....,......... x/EX.
(2)
2/ 2n)I S
In case, consider [(X,,.... Xa) 1E Xullg- Then notice that by triangle inequality for any Ii..... Fn and x/ with Xt,er = p0 Ph.aa(s) sample generated from the generative model) that
-p (s') (index i holds for index of
f (Z Ik...., In) = ||] + xnll2 2 S || +
In. I& + 2/61l2 + 11 1/1l2
< f (Zi,.... 2e...., xn) +2
38

---

Theorem 5. (McDiarmid's 's inequality). McDiarmid et al. (1989] Let f f: : x x. be function satisfying the bounded difference property with bounds Ci.... Cu- Consider independent random variables XI...., Xn, X; E X; for all i. Then for any > 0
2t Σ o
Is (XI, - 1B (X X.)] 2 2 S exp
Using McDiarmid's inequality and union bound, we can bound the term here
(I( [ -Po )1, 11-11) [8| (Pa. P )
2NN (A((()))//)))
N2
with probability 10/(/S//A|)) Moreover, the additional term be bounded follows:
BI |
Pe. Do. 0.0
1
F (Pa (s') - -0 (8')) (
1
Σ X
N
with Xi, po. (5') (5') is one sample sampled from the generative model. Then
N X
N
E (po - Do
5.0
N²
Var
N²
V
(156)
N
IE
x
(157)
N2
N
where (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,
E (P - Po.)) )|,] s < - Po. )
(158)
due Jensen's inequality. Finally, regrouping the two terms, we obtain with probability 1 A|())||A|):
po
- - - -OO0 )11 1E (1(( pm p
go 6,0)
POO 11.)) + (B[ll PP. Poo Bba)l1.)> 2 ) 112 - E (pl. - -Paa)) 11
po
|1 pd - -po
1 (1(p - - -Po.a)
+ 2E
2N (og((S((AA|((8))
4
2N log( Al/(1))
+
N
N
N
10 10 N
L'
N
where in first inequality use (a + b)2 = a² 6² + 2ab and where in (a) we combine equation (158) and (17pp and (16).
with = 10 ()){(()))))())) Finally, plugging the previous equation
155
(u6o - -m]1 S max (po -Po
s.a l| CsA.
max E p0
This term can be easily controlled by taking the supremum over X, which is a dimensional parameter. Then we can bound E [0, H []]]].] Indeed,
X |V /²- nl1. < |VII, H H|]]I.-
39

---

Finally, we obtain:
( (po, pa.)) |1
L'Cs
max
CsA
X
N(1-7)
Regrouping all terms:
(a V)
max EMPg p2.
p - Poo (V - uio
+
max
po
5.a - po
(utpo.
upo )
pop a.a
EMM
2.0
L
Varpo, (V) + L'Cs 1111,
L
S 21
+
N
N(1 -7)
N 7)
L
3LCs |1-1e
$ Varpe (V)
(159)
(160)
We can recognize that the second term is second-order term as long as N 2 (Cs [| we can regroup the two terms. Finally, as as.a( (a V) 2 (ap V), we obtain
3LCs ||1||. Varpe (V) +
P..VV s.a
V
- S 21
V
(161)
8,0
N
N(1
It is important to note that the geometry of the norm is present in the second order term 3LC=||1| but this term is negligible it is proportional to 1/N with regard to the variance term in 1/vN. Moreover, note that the quantity Cs || = S for L2 norms.
NNI
For the specific case of TV which is not C22 smooth, this lemma still holds in (144), only need to control one term without the dependency on data in the supremum as ar) reduces to a scalar a 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 (44) is the left-hand side term.
For the s-rectangular case, the first equation can be rewritten simply by factorizing by (als) using lemma
V 5,a
V
P... aa
VVVVV=
= Σ t(als)
max as po.
(P -1) - (sp((V - -1))))}
EMA.
Ph.
max n
Po
- (sp((V - -M }=m}
(162)
EM!
LC's |1111. N(1 -7)
$ (aals) (2v N Var (V))
(163)
L = 2/ N Var (V) + 3LCs |||||
(164)
N(1-7)
using 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 8:
p -p V V -p",,"VV'"" p=''Vv=''
T 22 N V Var (V+o)+ + 3LCss |||||_ 1
(165)
N(1 7)
(166)
40

---

D.3.4 Proof of Lemma 9
Using the same argument as in 216 it holds that for any a² solution of 53
(1 (1-12"')) ")
-1 v /Var vv
Σ (m0
76 ( (D"
Var vVrto). (167)
Then we can control Var prt, v (V*.7). Defining V' V*00-171 which lead to
-111, 17 E R, we use Bellman's 's equation
in 32
V' = V-o - 7/ S V*.0 -n1 = 1.. + + ..t.VVVV -nl n
(168)
-Ta. +ypp VV Vna -v0sp(V"10)) -1
(169)
= + V V + p - 15- .V | -oosp(V*.))
(170)
= - + 77p" /
V + p - -pxt) Vit
(171)
vv V + 7 p - -p - Viio
s + tIp
(172)
where in the second line use Lemma 3 and we define r.. rzz - - (1-7)=- < rxx < 1. We
obtain the same result in s-rectangular case using lemma 4 instead. Then
Var perp pet,v (V+.0) (a)
Var par Varget. (V')= = =p" (V'oV') - -Pp' Vi o (p"i" vy
P (V' (Vov"' -
V') o (F V')
(b)
< pT (V'- - 1
マ (v' Ps. - (priv - - vvo) 02
M. . (V' 1') - ب 2 V + 2 v (1ar + +7 - )
1
vmo)
7 ( + 7 - - - v\ Frri) (am)
02
V (V' o V') - / - v + 72
V 1x0
(173)
2 | _-mii_ -
iv - /
(174)
-. (A.4)
2 .. o v + 72 |
(175)
?
+ 2 2 (2/
L
+ 3Cs |1 L.
N(1 7) )1, 1,
(176)
(1 (1-7)3 ?
where (a) holds by the fact that Varp, (V -11) = Varp, (V) for any scalar y, (b) follows from 172
morcover (c) comes from $ o V 2 1 v' V' and -1 Tx* - (1-n) 1 = r'p. Tax
41

---

Finally, the inequality is due to Lemma
8
Plugging (766 into 167 gives,
(1-15"1))
(177)
V 7
1
Σ
2
7t (Driv)
p p (V' VV' 1 V' V' + 2
72 |0
(178)
t=0
2 +
+ 3Cs 11111111 1. )1)) 1/2
(V
(1 7)N
1
Σ 7t ( (x=:)))
( (M - 1 v'oV))
7
7
1=
Σ 7 p 11 ( 2 1o + 2
x
1IV'lloo 100 (2
L
3Cs 11 30 1.)
)1
?
(1 (1-7)2N
N(1 7)
t=0
Σ 7t (2 ()= - - (V' (V')V') v2) - 1 v v
(179)
1
?
1=
2 (2+ 222 (1-タアー + N(I-9) ||'||
1.
(180)
(1 7
using in (i) the triangle inequality. The final part of the proof focuses on the first term, which follows
06
(V''1') ( ()
(p"
1 -V' vv
7
Σ (E(
2 (V'
worll
s 1 11
(181)
7
1=0
using recursion between the two sums. Then, using (181 back to 180 leads to
I - p 11 p -1
Var pet.
(VVrr) (V+r)
(1+ (V 1-1por
L + C2
|
|
N(1-7)
1 ++3 +31
7(1 - -7)
- 77)272
1 V (1 (1- + C
| -((-)))
< 11
1
(182)
(1 - 2222
1+ (1 (ー- + 11llll| 1.
||V N)
<41
(183)
(1 71-7)
42

---

Taking the infimum over 1y in the right-hand side, recall V == Vxa 171, we obtain the definition of the span semi norm.
+ V [1-7)'N + N(1-9) sp(VA.0).
1.
1 (I-2ET10) /ar pra. (VA.0) 541
(1 7)
+ [ー + C211111,6
1.
N(1
1 4
(184)
73 7)² max 1 - 7, Coo}
pー + 1,11111,6
N(1-7)
I
|
(185)
70 7)3
where the penultimate inequality follows from applying Lemma
5 with P = po and =
1
sp(V*.0). 7 max - 7 Cgo)
or with an extra factor for s rectangular assumptions.
sp(V^o0 max min, |T. 5Cg)
D.3.5 Proof of Lemma 10
In this proof, will sa-rectangular notations, for any (s,a) E S x A. using the results in the sa-rectangular case:
144 In
pa. V. DR. - PR.VDRR. I max { { -Poa) |7a.0|
-PP.) |a.
8.0
Aiwa Paia
Ps.a
(186)
The first term in this max can be bounded using:
po -5o
0.0
[5..0
Aame Fea
(187)
(a)
((pd) - Do. 2.a) [f0.0]]
( p0 - 3/a)
-
)
) ))
Aume
+
Paa
(1(Pg (po
-po
|i:00
+
po
530
|
ll
6,0)
A
8,a
a
Awwa Peu
Awa
Psa
ara
(b)
po
po
+
pix
A.wa Pen
8
(2)
p0
9.a
po
s.a
+ +Eopt
(188)
where (a) comes from the triangle inequality, and (b) comes from |
Po || < and s.a
V+ I| Il and (c) follows from the definition of the optimization enror in (55) The second term of the max can be controlled in the same manner, i.e.:
[[ a.
-.-- Il.e
(Po 3,a - - ) [pa.o]
$ po 3.a -Po))
-
[Fi.0]
Awn
+ 28
(189)
P.a
Pen
max
po
3,a
po
(D~a
+
max EMP pa
(po 3,a - (Po)
u )
mep EMA.
pg.
(190)
+ 25 opt
(191)
43

---

where the last inequality follow the decomposition of (150). Finally, to control the remaining term
(Paa- - Po.)) (v+-0- - p
{1P - - [V
max EMA P8
max agEAA.
(192)
191 for any given a E [0, Aws [c Pea
[0,
1
S
in the variational family with one parameter X, with
1->
the dependency between 7 and po, we resort to the following leave-one-out argument or absorbing MDPs used in [Agarwal et al. 2020 Li et al. 2022b] Shi and Chil 2022, Clavier et al. 2023]. To begin, we create a collection auxiliary RMDPs that exhibit the intended statistical independence between robust value functions and the estimated nominal transition kemel. These auxiliary RMDPs are designed to 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 Mrob defined using the nominal transition kernel Po. Inspired by Agarwal al. 2200)) we can construct an auxiliary absorbing robust MDP M for each state s and any non-negative scalar u 2 0, so that it is the same Mro except for the transition properties in state s. These auxiliary MDPS 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 Mr as 8s, and r which are expressed as follows using the same notation as Shi al. 2023
(s, a) u pe (3.0) = a))
E A, ((5 E S A and
(193)
pa s, = 1(s' (1s'=8) =8) pai(-1 5, a) PO (,)))
(s'sa) ((, E X and 3 8
(194)
Nominal transition probability at state 8 of the auxiliary M never leaves state 8 once entered, which gives the name absorbing these auxiliary RMPDs. Finally, we define the robust Bellman operator Tg, (+) associated M as
(Q) a) -,."
inf PV, Petfa (P2.2)
with V(5) max Q(3,
(195)
in sa-rectangular case and with stochastic policy in s-rectangular case. Using these auxiliary RMDPs we can remark equivalence between Mrob and the auxiliary RMDP M fixed-point. First, Q the unique-fixed point of f (-) with associated value V--. We will show that the robust value function V- obtained from the fixed point of T (-)is the same as the the robust value function
a. V+,0 derived from 7at (-), as long as we choose u as
u = u² (s) = D (s) (e.)
inf PV-a
(196)
with eg is the s-th standard basis vector in R.S This assertion is verified as:
First for state 5' f s, for all E A: it holds
inf s.u" (s', a) +7 PEUM)(pp)))
pì+0= - + inf PV+io
Petr (Pg..)
= = (ss (s'
(197)
where the first equality holds because of 193) and 194). and the last inequality comes from that @+ is the fixed point of (-) (see Lemma C.3 and the definition of the robust
Bellman operator in (3).
Then for state s, for any a AE
7 9:00 (s, a) +
inf
PpA = = +v inf
PV
(Po.")
(e)
= =P. 7 (e.)
inf
pìro +y inf (e(
pv4o (s), (198)
44

---

using in the first equality is the definition of P in 194 and where we use the definition of u² in (196) in the second one.
Finally, we have proved that there exists fixed point 2 of the operator Ts (-) by taking
{ Q (8, a) (. Q (5', Q (s'
Va E E,,
(199)
A' + and A.
we have confirmed the existence of a fixed point of the operator Ty.u: (.) with corresponding value function V that coincide with V- Note that the corresponding properties between Mrob and ".u* M in Step and Step 2 hold in fact for any uncertainty set and s- or sa-rectangular assumptions.
Equipped with these fixed point equalities, we can use concentration inequalities to show this lemma.
Concentration inequality using e-net for all reward values u. First we can verify that
1
0 S u < [V 1 (s) (a)) I (+ S
(200)
1-7
Then, we define NN, -net over the interval [0, 1/(1 - [[]] where |:Nezl the size of the net can be controlled by |Nea S -x(iー) [Vershynin 2018 The only parameter that varies is À in the variation family, ade so we have 1-dimensional control and not vector in R Then similarly to Lemma C.3 it holds that for each u E Nez, there exists a unique fixed point Q of the operator (+), which satisfies Q7: S - Consequently, the corresponding robust value function can be upper bounded by [Vr. S 1-q" Using 194) and (933 by construction for all u E Ne,, Mi0 is
statistically independent Po. This independence indicates that [Vrt and P5 s.a are independent for a fixed a. Using (148) and (149) and taking the union bound over all (s, a, a) E x A x Ne., E Ne. gives that, with probability at least 1 - 6, it holds for all (s, a, u) E S x Ax Nez that
18 SIIISAN
2oo
max Ai o EA
[pn. - s.a)
[
22
Varpo (Vrie) (201)
N
+ E2
18 1II,
2oo
s 2
+
(202)
(1 2
Finally, we use uniform concentration to obtain the lemma. Recalling that u* E |0, T (see
(200), we can always find some 77 NN, such that 1 u²1 S E2. Consequently, plugging in the operator T (+) in (155) yields
VQ E SAA
|TT. T... (0) = uul
We can then remark that the fixed points of s.a (.) and to (.) obey
2 - Qia
@2:00
( - a,
+ + -Fo (Q:.
< 7 Q2a - Q+: + 82
where we use that the operator To (.) 7-contraction. gives that:
|::0
82 7)
and
De < <1000
Qio
5 (1 7)
2
(203)
45

---

Finally to control the first term in (991, using the identity V. = Vi fixed point relation between the two RMPDS, established in previous step of the proof gives that: for all (s,a) E S x A.
P - - pa.))
[V
max
Popa EA
(pn s,a pn. 1 Paya
max
{11000 po.
(pa. sa s.a)
(I An -IVese
}
max
[V
Ja Am Para
apra EAP,e
(po - po
(poa-
[Vay Jada.
252
max EA
(1 -17)
Ps.a Ps.a
282
+ + -2
2log( 18|111, SAN)Ne
6
Var (Vai)
log(
5 3N((1
18|111| SANIM New
(1 11-9)
N
2 2oo 1811111, SANI SANIN + +21
Var (V+o) + 4log( S8NI)],
352
(1-7)
N
3N(1 -7)
log( 1 SANING
+ 2V
Var (V+.0)= - Varpo pe.
(V+.)) 2,
N
(4)
352
+ +
2
log
18/ SANIA
Varpa (D+.0) 2\
482 log(
18 [111 SAN|NN,
(1-7)
N
N(1 7)
(204)
N Varro (V+.0)= + logg 54/111,SANIN..
L
< 2
8
(205)
N(1-7)
L"
16
(206)
(1 1-7)2
with L" = llo
[4/ (1-7)8
where (a) comes from triangular inequality, (b) is due 2003. for any
VERS
( n,a
poo)
(IV
(V
po
po s.a
[ la
2
v=
28a 71-
(207)
20
(c) follows from 201 (d) holds using Lemma with 203 Here, the last inequalities hold by
letting S2 log Toi SAN Nea!
which gives |Ne S 2a(1
3N
and the last inequality holds
I-7.
by the fact Varpa (V+.) S 1 S - and letting N 2
[4|||1] SAN?
L."
(1-7)6
Rewriting (86). the first term of the max is controlled.
(
max
PD
uu s.a
[
- -5
[
The second term can be controlled by the same term as the first one plus an additional term with
(10 - po
[
Psa
max MA te
po
500
(Vio
upo
)
+
pp) - po
6,0)
(up2.
u6o
EMA. no
AA
EM3
po.
Pa.a
46

---

and similarly to previous lemma in (199,, the residual or term in the right in the previous equation can be controlled with L'Cellill_ N(1-7)) Finally, putting (205) and (206) back into Equation (91]) and using Eq. (006 with probability at least we obtain
fR. V Pa. - -a. pa
(Po -Po )o.a) [V Japin
S
max or.a EAPa
+ 28
paice
D'
14L" ||111.
2
N Varpo (V+.0) + 2oopt
N(1 - 7)
L"
14L"Cs |||||=
$ 2/1/
+ 28apt
(208)
(1 2
N(1 -7)
((s E A. Using matrix form we obtain finally;
pa. VR.00
L." I 2 N V Varpa (Vx:r)) + 2Eopt
L"
C4I"Cs ||
I 2
+ 23 1. +
(209)
7)2N
N(1-7)
The proof is similar the s-rectangular case, factorising by (als), like in Moreover, the proof is similar for TV without the geometric term depending on Cs.
D.3.6 Proof of Lemma 11
We always use the same manner as in Appendix D.3.4, Similarly to (167)
holds:
(1- V Varpe, (V3.0) S
Σ ra p t=
Var pe, p
(210)
In order to upper bound Var p (VR.0), we define V = VR.o0 7/1 with 1y E IR. Using as 174 it
holds
p.ppp((( (V8.0) S D (V' v') 1 V' + 2 1 22 +
2 | /...P. - pp. PR.o
Var pa.
p2. (V'oV') V²) - -
(211)
7
2 2 V' o0 1/ 2/ (1 (1-7)2N
1"
+ 25opt + 14L"Cs |1/1 1,
(212)
N(1 (117))
47

---

where the last inequality makes use of Lemma 10 Plugging 212 back into 210 leads to
V (1-2ER))7
-1
pa. (Vi.)=
(a)
Σ 7
[aa.) (V'v)) - - (
7
(1 7) + Eopt + 14L"Cs ||-1l-
L"
+
7) (2
||o1
N(1 -7)
2 (1-1PN - 25ptt + 14L"Ca|ILL
||V'
1V
V &
N(1-2)
7(1 ++1
(1-7)
WN
IV &
1 + ++5/
(1+ +
L"Os |111.)
||
(213)
7(1 7)
N(1 7) (1 2)
6/ Eopt + LnOs |1 ||
(214)
N(1 77) (1 7-
where (a) is the same (80), (b) holds by repeating the argument of (181). (c) follows by taking
N 2 1." ロー and then the last inequality holds by || I ||V*ll S - Then taking the
infimum over v in the right-hand side of the equation in the definition of V and using sp(-) S ll-Il. gives
(I->PRP)- -1
LnCs [1111.) sp(V) no
Var pa. (VR..)) s <6/ (1+ Eopt +
N(1 (11-7) (1 7y2
Finally, applying Lemma 5 with P = 0o0 and π = के yields
sp( S max 7, [Co
1
(215)
for sa-rectangular or in the s-rectangular case, which can be inserted into 214 and gives in sa-rectangular case:
sp (
7 max 7, min, ||
L"Cs|[i1
I (1-ppt.)) -1 v Var Warpp..((20 (V s 61
+ Eopt + N(I->)
73 - 7 max (1 - 7, 0}
(1 + Eopt +
L"Cs|ILL
N(1->
S <6
(1-7)373)
where first inequalities comes from that we can bound it Eq. left-hand side of equation (214) by ||V'llo < Il* I 1-- Proof for s-rectangular is similar, but requires adding an extra factor depending on the norm of the current policy and we have:
+ Copt + 1/CSs| 1|1
(1-1ERD)*
-1 V
Varps.
Var pa. (V7.0)) S6
[1117)
73(1 7)22 max(1 7/, C, min, | look
(1 1 Eopt Eopt + L"Css 12111
N(1-7)
< '
(1 777 1.
48

---

D.3.7 Proof of Lemma 7
First, if each row of P= belongs to the simplex ASS), it lead that the row of (I- falls into A(S). Then,
(1 (
V /Var,, (VT.)) (V
1 (1
1
v (Vrr)(VV..)) (VT.P)
(a)
((1 (1-))((1- (1-7))
-1 Varp, (Vo.P)
x
Σ 7 (P=)' Varp, (Vo.P),
(216)
where (a) is due to Jensen's inequality. Then for any 17 E R+, V Va. -71 we can upper bound Varr, PV=
Varp, (V=.P) (
Varp, (V') = Pa (V'o o V') - -Va''' (PaV")
(
1
Pa V')
(V' - r
(1 71) (V' rx + (1 1)
72
= o V²) - V' v' + / V' o (rr (1-7)11)
1
2
(217)
72
72
1
73 (Tx - (1-7)nl) (Tx - (1 7)11)
S Pr (V' o V') V V'
1
2
| ||01 S Px (V' o V')
2 | V V' + 72
1V' (218)
7
g2
7
b1) = Varp, Varp,(V=..)) (V=:P) for any scalar b and Va. E R (ii) follows from V < I + yP= Va.P 11 rr (1 -7) +7P, V', and the last line arises
where (i) holds by the fact that Varp.
Varp,(V=, (VoP
from 5/ V' o VV 2 1 V' o V' and | - (1 - 7)nll S 1. for n E (0, 1/(11 - --][ Plugging 218
7
back to 216 leads to
(1-7Pa) 1 V Varr. (VTPP) (VT.P) S
(Px)' Ps (P -
L' vo V + 2 > |1V1
* (Pa)* -
1
H (Pa)) 2 72 |
+1
t=
t=
Σ 7d (Px) (+
Σ x ) (V/rr)
2
+11
72(1 (51-7) 7)
t=
BVB
V 1 7(1 7)
+ 1/ 77(1-7))
8
(219)
72(1 7)33'
(220)
where (i) holds due to, (ii) holds by following recursion between the two sums, and the last inequality holds because || Vo S m-g. Then taking the minimum over vy in the right-hand side of the equation
gives the result.
8sp( Bsp(VT.P)oo 7211 7)
(I (I-7PT) / /Var., (V=.P) S
49

---

However, we also > & IVe.Pllo S 1-
1 in 219
So finally, the result is
(1 --(P /aar,, V 72(1 - 7)3 sp Sp(psppV (V=..PP) Pool..
8
E Proof of Theorem 2
In this section, we focus on the scenarios in the uncertainty sets constructed with (s, a)- rectangularity condition with some general norms. Towards this, we firstly observe that for the two limiting cases & norm and &o norm, one has ||p: - p2ll1 S 2 and ||p P2llcc S 1 for any two probability distribution P1: P2 IR. Namely, the accessible ranges of the uncertainty level a for I norm and to norm are (0, 2] and (0, 1], respectively. In addition,
have
Pp P2 E R |PI P2ll0o S lP p2ll S |PP p2ll1
(221)
for any norm || It indicates that the accessible range of the uncertainty level 011| for any given norm || I| between (0, iH-l _maa where
0 I-1l 2. 2.
To continue, specify the definition of the uncertainty set with sa-rectangularity condition with some given general norm || as below: for any nominal transition kernel P E RSSSS
(P) = Uinn Ug (Pa,a)
(Pa,)) = ={Pa E A(S): | Ps.a
%1-1 j
(222)
Then, we recall the assumption of the uncertainty radius 1-111 E (0, max (1 (1-c)] with < co < 1.
|+|
Then, resorting to the same class of hard MDPs in (Shi et al. [023 Section C.I], we can complete the proof by directly following the same proof pipeline of Shi et al. 2023 Section C] by replacing with max
||-1|
||-I- I1-11-
F Proof of Theorem
Developing the lower bound for the cases with s-rectangular uncertainty set involves several new challenges compared to that (s, a) reetaangular cases. Specifically, the first challenge that the optimal policy can be stochastic and hard to be characterized with closed form for the RMDPs with a s-rectangular uncertainty set, rather than deterministic polices in (s, a) reetangguaa cases. Such richer and smoother class of optimal policies makes slightly changing the transition kernel generally could only leads to a smoothly changed stochastic optimal policy instead completely different one. Such reduced changing of optimal policy further gives smaller performance gap. thus challenges of a tighter lower bound. Second, most of the hard instances the literature are constructed as S states with constant number of action spaces without loss of generality. While when it comes to s-rectangular uncertainty set, the action space size becomes important and can't 't be assumed as a constant anymore. So a new class of instances are required.
To address these challenges, this section, we construct a new set of hard RMDP instances for two limiting cases: & norm and &o norm.
F1 Construction of the hard problem instances
Before proceeding, introduce two useful sets related the state space and action space as below:
10.1....,.5
and
(0, A 1}.
In this section, we construct a set of RMDPs termed as M which consists of S(A 1) components including S(AA - 1) components, each associates with some different state-action pair. Specifically, it defined as
Mr = {Me = (S. (S.
o e = (1.5) : (i.j) e AA\
(223)
We introduce the detailed definition of Me by introducing several key components of sequentially. In particular, for any RMDP Ma E Me the state space is of size 2S, which includes two classes
50

---

of states A' = fIo, ........sss). and y = foo. 31..... . The action space for each state is A of possible actions. So we have totally 2S states and there in total 2S state-action pairs.
Us-11
Armed with the above definitions, we can first introduce the following nominal transition kernl:: for all (s,a) X XXUY> A
p yb) + (1 p) = =x;) if 8 -1, a; ViES
plo.0) (s
91(s' = v.) + (1 - g) =z,) if s= 2,, a #0, ViE (224)
1(s' =)
if SEY
Here, p and q are set according to
0 p and 0
(225)
for some and A > O that will be introduced momentarily.
Then introduce the S(A - 1) components inside M Namely, for any (i.5) x (0), the nominal transition kernel of M(..) is specified as
pll(s' = y.) + - p)1((1 =x;) if = Fi, a =
(5'{8a))))))
Q1 = vi) + (1- 1) =x,) if = x, E a
(226)
(lo.0) ss
otherwise
In words, the nominal transition kernel of each variant M(a.)) only differs slightly from that of basic nominal transition kernel p(0,0) when æ; and = {0,5}, which makes all the components inside Mr_ closed each other.
In addition, the reward function is defined as
if Ey
Va E A: r(s,a)=
(227)
0 otherwise.
Uncertainty set of the transition kernels. Recall the following useful notation for any transition probability P, i... the transition vector associated with some state is denoted as:
Ps == P(. |8) 1RA
pd = pa 11)))))))))))))) 1RSA
(228)
With this in hand, the uncertainty set (definition in 5 with lo norm for any pd with 0 e θ can be represented as:
u (P. 2 (P?) (p= E
- = s
=o]
(229)
So without loss of generality, we set the radius (0, (1 co)l with 0 < < 1. Before proceeding, we observe that as the uncertainty set above is defined with respect to lee, directly implies that for each (s, a) E S x A. the uncertainty set is independent and can be decomposed as
(P!)) S = ( A(S) |
P {o)
(230)
Notably, this indicates that using s-rectangular uncertainty set with foo norm the divergence function is analogous to the case of using (s, a r)-rennang uncertainty set with foo norm. As result, follow the pipeline of the prior art (Shi al. [2023] Section CJ which established the
minimax-optimal lower bound for (s, a) --reectagg RMDPs with TV distance, which is analogous the lxo case. Towards this. where we recall the expressions of p, g, A for self-contained as below: taking C1 == M
set p. q, A as the same as the ones in Shi et 2023 Section C.I].
2
p (1 + (1) max 7. and A e max 7, 7,
(231)
which ensure several facts:
05p51 and p2 q max(1 7.
(232)
51

---

Value functions and optimal policies. For each RMDP instance Mg E -Mex with some abuse of notation, we denote Tg as the optimal policy. In addition, let V (resp. V/ represent the corresponding robust value function of any policy (resp. =ÿ) with uncertainty level a. Armed with these notations, the following lemma shows some essential properties concerning the value functions and optimal policies; the proof is postponed to Appendix
Lemma 12. Consider any Ma E Miz and any policy n. one has
( o)
((L,) E
(6.)) (24)
(233)
(1 - 7) ( 1+ (1))
7 ( -0)
)
(1 (1-7
where (G.) defined as
Vi.j)
2h, = pr(j (2;) + a T(j [
(234)
In addition, the robust optimal value functions and the robust optimal policies satisfy
7 7(p ((p-o) σ)
v(i.j) O,
(65)(( (s)
(235)
(1 (1-)) (1+
2(p-0) (1-
1-7(1-0)
and
T ( ( =1 =1
and
(0 Vs E (2.)-
(236)
In words, this lemma shows that for any RMDP M(s.)): the optimal policy on state x, satisfies Taas (1 (4) = and will focus on a for all other states s E X' {az}.
F.2
Establishing the minimax lower bound
Step 1:
converting the goal estimate (i,j). Now we are in position derive the lower bound. Recall the goal is to control the following quantity associated with any policy estimator म based on the dataset with total Na samples:
(an ())
(1,)) (s) (s)
max ((.j) (iJ)ee
max SEXUY
max P(.)) (iJ)ee
max SEX
(237)
To do so, can invoke a key claim in Shi et al. 2023 here since our problem setting can be reduced to the same one in Shi et al. 20233: With E <
letting
32(1
A 32(1 >) max(1 7. oe S max - 0,
(238)
which satisfies 231 leads to that for any policy 2े and all (i,j) E O
(Z.) - (x)) 2 2:(1 - [ (x:)). (in (a) > 2s 7 s))
Vs E X (x:):
(239)
Before continuing, we introduce a useful notation for the subset of & excluding the cases with state i is selected:
Vie S: θ_, =
(240)
Armed with the above facts and notations, first suppose there exists a policy â such that for some (i,j) E O,
P(n { (z) Van S
3
(241)
which in view of 239 indicates that necessarily have カ( xx))) > 1 with probability at least 3.
52

---

As result, taking
j' arg max a(a 1;): asA
(242)
we are motivated to construct the following estimate of A:
0 {- = (i:j')
if j' >
(243)
G=
if
j = 0,
which satisfies
1 A
3 4
(1. 2 Pasti'==1 Pan)
(244)
Step 2: developing the probability of error in testing multiple hypotheses. Before proceeding, we discuss the dataset consisting of in total Nail independent samples. Observing that each RMDP inside the set Me.. constructed symmetrically associated with one pair of states (I,, yr) for all i E S and another action j E A x (0), respectively. Therefore, is obvious that the dataset is supposed be generated uniformly on each (zi, wi. maximize the information gain, leading to Nail samples for any states states-action (Ii; Vi with E S,j E A \ {0).
5(A-1J
Then we are ready to turn to the hypothesis testing problem over (i.j) E O. Towards this, we consider the minimax probability of error defined as follows:
Pe inf max (P + (i.5)) (6,))
(245)
where the infimum taken over all possible tests constructed from the dataset introduced above.
To continue, armed with the above dataset with Nall independent samples, we denote μ (resp. (s, a)) the distribution vector (resp. distribution) of cach sample tuple as, un- der the nominal transition kernel p(.J)) associated with M(a.)) With this in mind, combined with Fano's inequality from Tsybakov [2009 Theorem 2.2] and the additivity of the KL divergence
(cf. Tsybakov 2009 Page 85]). we obtain
Pe 2 Nall (E0. KL ( (²' + log
max
log [
2 Nall max KL 114 2
max 2 (IJ). (EE)))))))) KL KL (1
Nall
(246)
where (i) holds by log [ 2 log as long as S(A 1) are large enough. Then following the same proof pipeline of et al. [2023] Section C.2], we can arrive at
Na
4096
Pe 2
a (1 7)2 max 7,0 4'
(247)
5(A - 1)
if the sample size is selected as
0₁ S1A 1)
Na S 16396(1 7)3 max(1 0
(248)
Step 3: summing up the results together. such that
Finally, suppose that there exists an estimator î
max ((..) (K,j)e
max SEXUD (vAg)
(6.) (M 2 <
(249)
then according to (237) we necessarily have
As E X:
max ((i)) (Leee
[Vg - V2g 26
<
1
(250)
53

---

which indicates
3
Vs X:
max I ((s)) (E.) (s) V (s) <E 2
(251)
(Jle
(1,)
4
As a consequence, 244 shows we must have
v(i.j E
P(. (i,j) 2
(252)
achieve 249 However, this would contract with (247) if the sample size condition in (248) satisfied. Thus, we complete the proof.
F.3 Proof Lemma
Without loss of generality, we first consider any M(.) with (i,j) E S x A\ {0). Following the same routine of [Sh et al. [2023] Section C.3.1], we can verify that the order of the robust value o over different states satisfies
function (5.f)
Vk S: (i.) S V
(i.) (yk),
(253)
which means the robust value function of the states inside X' are always larger than the corre- sponding states inside y.
Then denote the minimum of the robust value function over states below:
VTTo min V (s). (f.).min
(254)
.ES (t.)
In the following arguments, we first take moment to assume V - mind, we arrive at
(iJ).
(i.)) (1))(()))
(z:).
With this in
+ 1 (24)
(i.5)
= 1 + ((,) + VoV min)
(255)
1 1 - (1-o)
Then, when we move on to the characterization of the robust value function at state F, To do so, we notice two important facts:
1) The nominal transition probability p(..)) at state-action pair (I, a) for any A is Bernoulli distribution (see (226) and (224)) The TV distance and the foo norm between two Bernoulli distribution are the same.
2) Invoking the definitions of the nominal transition probability in 226 and 224
we have
p(t-)) pll(s' = w) + (1- (ss') =x;)
p(ij)) q1 = y.) + (1 x.) Ya E A 0,.a
(256)
With the above two facts in hand, our problem setting is reduced to the same one Shi et and can reuse the results in Shi et al. 2023 Section C.3.1] to achieve
2023
v8.0 (x:) s ((J)
1-7(1-0)
(257)
(1 ?) 1 ((-00100
1-7[1-0)
and
(il;)) =1
Y ( -0
(pp-r)
(z,) = (1- 1+
1-9(1-0)
1-7(1-0)
(258)
7 [ -0
(1- (1 + 2)
I-7(1-0]
1 1-1(1-0)
Analogously, we can verify that for other us X (xi).
n Tho xR) =
(p m)
(6.) (xx)
1 1-2(1-0)
(259)
(1 - 7) (1+ (p-rr)
I-1(1-0)
54

---

G DRVI for sa rectangular algorithm for arbitrary norm
In order to compute the fixed point of f", distributionally robust value iteration (DRVI, is defined in Algorithm| 1 For so-rectangularity. starting from initialization Qo 0, the update rule the t-th (t 2 1) iteration is the following v(s, a) E S x A:
(7, = ((, r(, +2
inf PV-11
(260)
p (P2,)
where (s-1(5) max, QT- for e
Directly solving (26)) computationally expensive since involves optimization over S- dimensional probability simplex at each iteration, especially when the dimension of the state space S large. Fortunately, given strong duality (260) can be equivalently solved using its dual problem, which concerns optimizing two variable (A and w) and thus can be solved efficiently. The specific form of the dual problem depends on the choice of the norm ||-I|, which we shall discuss separately in Appendix C.3 To complete the description, we output the greedy policy of the final Q-estimate Qr as the final policy म, namely.
Vs E
A(s) = arg max Qr)
(261)
Encouragingly, the iterates {Qt} e20 of DRVI converge linearly to the fixed point t+0 owing to the appealing y-contraction property of 7
input: empirical nominal transition kernel 5o; reward function r; uncertainty level o; number of iterations T.
initialization: Qo(s, a) = 0, Vo(s) = for all (s.a) ESX.
for ( 1,2, T do
for 8 E S, a E A do Set Q.(s, a) according to 260
end for
E S do Set Vi(8) max, (8)
end end
output: Qr. Vy and â obcying ((s) arg max, Qr(s, a).
Algorithm 1: Distributionally robust value iteration (DRVT) T) for infinite-horizon RMDPs for sa-rectangular for arbitrary norm
Using Algorithm T it allows getting an Copt error the empirical MDP the so-rectangular case. In the s-rectangular case, finding algorithm to get Copt is more difficult to use, as the policy is not
deterministic anymore and cannot anymore be applied. For Lp norms, Clavier et al. [2023] derived an algorithm but for arbitrary norm we need to consider more general problem for arbitrary norm in Appendix G
55

---

NeurIPS Paper Checklist
Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Yes
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results be expected to generalize other settings.
is fine include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: See conclusion.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification. asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low images are taken in low lighting. Or speech-to-text system might be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question:
For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
56

---

Justification:
Assumtions are stated in lemmas and Theorems.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [NA]
Justification: Theoretical paper.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architccture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reprodueibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
57

---

Answer:
[NA]
Justification:
Theoretical paper.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please the NeurlPS code and data submission guidelines (https://nips... cc/
pub / gui des Codeeubmme ssi aasionoolico icy) for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https //nips. cc/ wwwpiic/guiiipoooooo / /eddiddee//deeeeeeee Cooeeeooeeeeeeeeee SudeSuumiiee Suwmissiiiii wwwssnoooiiiyyy for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: Theoretical paper.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [NA]
Justification:
Theoretical paper.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, at least for the experiments that support main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
58

---

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 96% CI, if the hypothesis of Normality of enrors 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 range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification: Theoretical paper.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g.. preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethies
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics htttt:ttt////t /ttt::::///euiis..m httpaa/pp.........aacc/ccccceee.
Answer: [Yes]
Justification:Dnne
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is a special consid- eration due to laws or regulations 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]
Theortttcal 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 direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to
59

---

generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
there are negative socictal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
Theoretical paper.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification: Theoretical paper.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
assets are released, the license, copyright information, and terms of in the package should be provided. For popular datasets, paperssi hopersswiccoe com/ dataset has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
this information is not available online, the authors are encouraged to reach out to the asset's is creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and the documentation provided alongside the assets?
60

---

Answer: [NA]
Justification: Theortiicll paper.
Guidelines:
The answer NA means that the paper does release new assets.
Researchers should communicate the details the dataset/codeemoodll as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: Theoretical paper.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: Theoretical paper.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
61


Reviews:
[{"review_id": "xQwMCaW1yS", "reviewer": "Reviewer_6HyR", "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", "questions": "It would great improve the draft with some empirical evaluation to back the theoretical bounds, even a toy example.\nEspecially important since the bounds are not significant improvement from the prior art", "limitations": "Please add experimental work to back the theoretical bounds", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper is generally well-written, and results improve existing bounds. However, I didn't thoroughly read the proofs.", "weaknesses": "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.\n\nIn 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", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Answer to Reviewer 6HyR**\n\nWe appreciate the reviewer for recognizing our contributions, and for providing constructive suggestions. Here some comments on the different questions raised :\n\n> Q1: NSA been not use in Eq. 17, 18,19,20,21. Although the intention of the authors is clear, but that would improved readability.\n\nThanks for the suggestions. We add a new notation $N_{\\mathsf{all}} = NSA$ to represent the total number of samples and use $N_{\\mathsf{all}}$ in Eq. 17, 18,19,20,21 or other equations to make it clearer for the readers. \n\n> Q2: 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.\n\nThank you for the clarification question. Throughout the paper (including Table 1), we use the same metric to measure the sample complexity --- the order that defined as:\n- \"Let $\\mathcal{X} := \\big( S, A, \\frac{1}{1-\\gamma}, \\sigma, \\frac{1}{\\varepsilon}, \\frac{1}{\\delta} \\big)$.  The notation $f(\\mathcal{X}) = O(g(\\mathcal{X}))$ or $f(\\mathcal{X}) \\lesssim g(\\mathcal{X})$ indicates that there exists a universal constant $C_1>0$ such that $f\\leq C_1 g$,  the notation $f(\\mathcal{X}) \\gtrsim g(\\mathcal{X})$ indicates that $g(\\mathcal{X})=O(f(\\mathcal{X}))$, and the notation $f(\\mathcal{X})\\asymp g(\\mathcal{X})$ indicates that  $f(\\mathcal{X}) \\lesssim g(\\mathcal{X})$ and  $f(\\mathcal{X}) \\gtrsim g(\\mathcal{X})$ hold simultaneously. Additionally, the notation $\\widetilde{O}(\\cdot)$ is defined in the same way as ${O}(\\cdot)$ except that it hides logarithmic factors.\"\n\nWe added the footnote inside Table 1 to introduce the definition of order as above and clarify that we omit $\\widetilde{O}(\\cdot)$ in the caption, as the reviewer suggested.\n\n\n> Q3: It would great improve the draft with some empirical evaluation to back the theoretical bounds, even a toy example. \n\nThank you for the constructive suggestion. We will conduct an experiment with simple RMDPs defined with $L_p$ balls on a toy example to show the dependency in the radius of the ball $\\sigma$ on the sample complexity. \n\n\n> Q4: Does our sample complexity improvement significant improve prior art?\n\n\nFor RL problems, especially in theory, the sample complexity dependency on the salient parameter $\\frac{1}{1-\\gamma}$ is one of the significant terms that dominate the sample efficiency. A line of work has committed to the endeavor of gradually improve this dependency towards optimal in various RL problems including but not limited to standard RL [1,2], and robust RL [3,4,5] that this work focus on. \n\n In $sa$-rectangular cases. We focus on improving the sample complexity when $\\sigma >1-\\gamma$, where the prior art is still far from optimal. In $sa$-rectangular cases, we improve upon the prior art [5] sample complexity $\\widetilde{O}(\\frac{S A}{(1-\\gamma)^4  \\varepsilon^2}$) to $\\widetilde{O}(\\frac{S A}{(1-\\gamma)^2 \\sigma \\varepsilon^2})$ by at least a factor of $\\frac{1}{1-\\gamma}$ and goes to $\\frac{1}{(1-\\gamma)^2}$ when $\\sigma \\geq O(1)$. Notably, this results is minimax-optimal in all salients parameters that match our lower bound for general $L_p$ norms, as long as the accuracy level $\\epsilon$ is in a reasonable range. This is a significant improvement and near-optimal result. The same improvement is done for the $s$-rectangular case, by at least a factor of $1/(1-\\gamma)$ compared to [5]. \n\n\n\n\n>[1] Azar, Mohammad and Munos, Rémi and Kappen Hilbert , Minimax PAC bounds on the sample complexity of reinforcement learning with a generative model \n\n>[2]  Gheshlaghi Azar, R Munos, HJ Kappen - Minimax PAC bounds on the sample complexity of reinforcement learning with a generative model\n\n>[3]  Wenhao Yang, Liangyu Zhang, and Zhihua Zhang. Toward theoretical understandings of robust\nMarkov decision processes: Sample complexity and asymptotics\n\n>[4] Laixi Shi, Gen Li, Yuting Wei, Yuxin Chen, Matthieu Geist, Yuejie Chi The Curious Price of Distributional Robustness in Reinforcement Learning with a Generative Model\n\n>[5] Pierre Clavier, Erwan Le Pennec, Matthieu Geist Towards minimax optimality of model-based robust reinforcement learning", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "kwllLUQy8Q", "reviewer": "Reviewer_5t5a", "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.", "questions": "na", "limitations": "The authors have discussed limitations in the paper.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "For sa-rectangular RMDPs, the authors derive a near-minimax optimal sample complexity upper bound that matches the lower bound, showing their result is tight for almost the full range of the uncertainty level. This improves upon prior work which only achieved minimax optimality for the specific case of TV distance.\n\nFor s-rectangular RMDPs, the authors provide the first sample complexity upper and lower bounds, showing that solving s-rectangular RMDPs is not harder than solving sa-rectangular RMDPs in terms of sample requirement. This is an interesting and non-trivial result, as s-rectangular RMDPs have a more complicated optimization formulation.\n\nThe authors show that solving robust MDPs can be at least as sample-efficient as, and sometimes more sample-efficient than, solving standard MDPs. This provides important motivation for the study and use of distributionally robust RL.\n\n\nThis work develops new technical tools such as new concentration lemmas to obtain tighter sample complexity bounds.", "weaknesses": "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.\n\nA 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Answer to reviewer 5t5a**\n\nWe appreciate the reviewer's careful review and insightful feedback. It is rewarding to know that the reviewer recognizes the significance of our contributions. In what follows, we provide our response to the reviewer's comments.\n\n> Q1) 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.\n\n\nThere are many differences between our work and Clavier et al. [2023], e.g., our key lemma 5 and 6 to improve the sample complexity and the Variance decomposition (equation 64 of our work) which is central in our paper and differ from Clavier et al. [2023]. Please refer to the General Response for all technical contributions and new challenge addressed in our paper upon Clavier et al. [2023]. \n\n\nSection 8.3 of this work about optimization duality is similar to Clavier et al. [2023], while our proof is slightly more general as it works for weighted $L_p$ norms. We will refer to it in our last version of the proof of this manuscript. Moreover, the difference in optimization part is that we are not relaxing the dual of RMDPs problem like in Lemma C2 of Clavier et al. [2023]. \n\n\n> Q2) 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.\n\nThanks for proposing this interesting direction, investigating robust RL with linear function approximation or other settings such as online settings, or model-free algorithms are definitely interesting directions in the future work. Robust RL with linear function has inspired some recent works such as [1,2,3]. We believe the findings of current results in tabular cases about norms lays a solid foundation to carry out to cases with linear function approximation, e.g., the finding of using any $L_p$ norm may lead to less sample size requirement. While the entire pipeline in this work will need to adapt or change a lot since this setting involves additional challenges from problem definition (how to define a reasonable uncertainty set is still relatively open) towards algorithm design. \n\n> [1] Blanchet, J., Lu, M., Zhang, T., and Zhong, H. (2024). Double pessimism is provably efficient for distributionally robust offline reinforcement learning: Generic algorithm and robust partial coverage. Advances in\nNeural Information Processing Systems, 36.\n\n> [2] H Wang, L Shi, Y Chi  Sample complexity of offline distributionally robust linear markov decision processes arXiv preprint arXiv:2403.12946, 2024\n\n> [3] Liu, Z. and Xu, P. (2024a). Distributionally robust off-dynamics reinforcement learning: Provable efficiency\nwith linear function approximation. arXiv preprint arXiv:2402.15399.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "7cT7aDlwIL", "reviewer": "Reviewer_Tr2g", "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.", "questions": "1. Regarding Section 8.3:\n   - (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.\n   - 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]?\n2. 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? \n3. 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?\n4. Some typos and grammatical mistake that I found:\n   - Line 137 to 138.\n   - Line 144: simple -> simplex.\n   - Line 155: typo in defining the domain of the norm.\n   - Inconsistent usage of label (sometimes Theorem x but sometimes Theorem (x)), e.g., Lines 62 and 71, Lines 218 and 222.", "limitations": "Please refer to the weakness section and the question section above.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "**Originality and Significance:**\n\n1. The paper considers a generalized smooth version of $L_p$-norm with $p\\geq 2$ (whose algorithm and analysis also easily extend to the TV case) for the robust set and provides the corresponding sample complexity for the first time.\n2. The paper studies both $\\mathcal{S}\\times\\mathcal{A}$-rectangular and $\\mathcal{S}$-rectangular robust sets. For both cases, the corresponding sample complexity improves over the prior art for a special case (standard $L_p$ norm provided by [1]) when the robust set size is relatively large. \n3. For the $\\mathcal{S}\\times\\mathcal{A}$-rectangular case, the paper proves a matching lower bound showing its minimax optimality. For the $\\mathcal{S}$-rectangular case, the paper provides a lower bound for the special case of $L_{\\infty}$-norm robust set. The results also shows the learning $\\mathcal{S}$-rectangular robust MDPs with general $L_p$-norm is no harder than learning $\\mathcal{S}\\times\\mathcal{A}$-rectangular robust MDPs. \n\n**Clarity and Quality:**\n\nThe paper is well written. All the theoretical results are sound and are well proved. Some typos exist but are minor. See my questions below.\n\n**References:**\n\n[1] Clavier, P., Pennec, E.L. and Geist, M., 2023. Towards minimax optimality of model-based robust reinforcement learning. *arXiv preprint arXiv:2302.05372*.", "weaknesses": "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. \n2. 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. \n\n**References:**\n\n[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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Aswer to revierwer Tr2g**\n\nWe appreciate the reviewer's comprehensive feedback and recognition of the significance of our contributions.\n\n> Q1. One of the key message is that learning general $L_p$-norm robust MDPs is easier than learning standard MDPs. So I think it is less discussed how the exact choice of the generalized $L_p$-norm would further affect the difficulty of learning this type of robust MDPs.\n\nThank you for the clarification question. How different $L_p$ norm metric compared to TV affects the sample complexity or difficulty of learning RMDPs is present in two coefficients $C_g$ and $C_s$. For instance, in $sa$-rectangular cases, we recall that our sample complexity results is in the order of $O(\\frac{ S A}{(1-\\gamma)^2 \\max \\{ 1-\\gamma, C_g \\sigma\\} \\varepsilon^2} + \\frac{ SA C_S \\left\\|1_S\\right\\|  }{(1-\\gamma)^2 \\epsilon})$.\n\n- **The coefficient $C_g>0$ is related to the geometry of the norm.** For classical non-weighted $L_p$ norms, this coefficient is bigger than $1$, leading to sample complexity smaller than in classical TV case. However, for arbitrary weighed norms, this coefficient can be smaller than 1, which imply a bigger sample complexity compared to TV cases.\n- **The coefficient $C_s>0$ represent how smooth is the gradient of the norm.** This coefficient does not affect the sample complexity for small error $\\epsilon \\leq    \\left(\\max \\{1-\\gamma, C_g \\sigma\\}\\right) /\\left(C_S\\left\\|1_S\\right\\|\\right)$, with $\\sigma$ the radius of the uncertainty ball, and $\\left\\| . \\right\\|$ the considered norm, as it is a second order term in terms of $\\epsilon$ or burn in term. The smoother the gradient of the norm is, the smaller is $C_s$ which lead to smaller burn-in term. \n\n> Q2. 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.\n\nThank you for the insightful suggestion. We consider general $L_p$ norm since its soundness in both theory and practice. [4] use TV for RL learning of Online 3D Bin or [6] for Offline policy optimization and [5] use $L_\\infty$ for learning S-rectangular Robust MDPs. Moreover, the general $L_p$ problem formulation has unique interesting optimization properties, namely, relaxing slightly the problems will lead to a closed-form dual problems ([1,2] developed respectively Value Iteration and policy-based methods to solve RMDPs with $L_p$ norms).\n\n>[1] Navdeep Kumar, Esther Derman, Matthieu Geist, Kfir Levy, Shie Mannor \"Policy Gradient for Rectangular Robust Markov Decision Processes\"\n\n>[2] Navdeep Kumar, Kfir Levy, Kaixin Wang, Shie Mannor \"Efficient Policy Iteration for Robust Markov Decision Processes via Regularization\"\n\n>[4] Adjustable Robust Reinforcement Learning for Online 3D Bin Packing\nYuxin Pan, Yize Chen, Fangzhen Lin\n\n>[5] B Behzadian, M Petrik, CP Ho  Fast Algorithms for $ L_\\infty $-constrained S-rectangular Robust MDPs, Advances in Neural Information Processing Systems, 2021\n\n>[6] Lee, J., Jeon, W., Lee, B., Pineau, J., and Kim, K.-E. (2021). Optidice: Offline policy optimization via\nStationary distribution correction estimation. \n\n> Q3 (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.\n\nYes it is true, we will replace it, this is a typo.\n\n>  Q4 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]?\n\nThere are many differences between our work and Clavier et al. [2023], such as our key lemma 5 and 6 to improve the sample complexity, the Variance decomposition (equation 64 of our work) which is central in our paper and differ from Clavier et al. [2023]. Please refer to the General Response for all technical contributions and new challenge addressed in our paper upon Clavier et al. [2023]. \n\n> Q4. 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?\n\nThank you for the insightful question. In equation (20) of Theorem 3, using the result for the  $L_\\infty$ gives that the upper bound is exatly proportional to $\\frac{SA}{\\epsilon^2(1-\\gamma)^2\\max\\{1-\\gamma,\\sigma \\}  }$. The other cases of the upper bound in equation (20) involve the quantity\n\n$\\min_{s \\in \\mathcal{S}} (  \\lVert \\pi_s^*\\ \\rVert_*   \\lVert 1_A \\rVert ,  \\lVert \\hat{\\pi_s} \\rVert_*   \\lVert 1_A \\rVert )=1$\nin the case of $L_\\infty$ RMDPs because.\n\n$\\min_{s \\in \\mathcal{S}} (  \\lVert \\pi_s^*\\ \\rVert_*   \\lVert 1_A \\rVert ,  \\lVert \\hat{\\pi_s} \\rVert_*   \\lVert 1_A \\rVert )=\\min_{s \\in \\mathcal{S}} (  \\lVert \\pi_s^*\\ \\rVert_1   \\lVert 1_A \\rVert_\\infty ,  \\lVert \\hat{\\pi_s} \\rVert_1   \\lVert 1_A \\rVert_\\infty )=1$\nSo there is no contradiction with our lower bound which exactly match the upper bound.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "JL9BVz7YZR", "reviewer": "Reviewer_QVRk", "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.", "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?\n\n2- What challenges are involved in establishing lower bounds that hold for any L_p norm in the s-rectangularity case?\n\n3- Is there a fundamental limitation to extending the results to the *entire* range of the uncertainty level?\n\n4- 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": "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.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper makes several contributions. Firstly, the authors improve upon previous upper and lower bounds, demonstrating near minimax optimality for any choice of L_p norm. They show that the sample complexity for solving robust RL is at least the same as, and sometimes (when the uncertainty level is relatively large) smaller than, that of standard RL. This generalizes the findings of Shi et al., 2023, where minimax optimality and comparisons between robust RL and standard RL were only established for the total variation distance (p=1). Secondly, the results indicate that solving s-rectangular RMDPs is not more difficult than solving sa-rectangular RMDPs in terms of sample complexity.\n\nOn the technical side, the analysis seems non-trivial, utilizing a finite-sample approach established by the authors that leverages a novel dual formulation for RMDPs optimization, which could be of independent interest. The literature review is comprehensive, and the positioning and contributions of this work are clearly articulated.", "weaknesses": "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.\n\nEstablishing 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Answer to reviewer QVRk**\n\n\n\nWe appreciate the reviewer for careful review and insightful feedback. It is rewarding to know that the reviewer recognizes the significance of our contributions. In what follows, we provide our response to the reviewer's comments.\n\n\n\n> 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.\n\nWe will try to correct as much as possible all minor typos in the next version of the manuscript.\n\n\n\n>* 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?\n\n\nThe challenge in comparing to the work of  Shi et al., 2023 is the following. Is it possible to generalize the work of Shi et al., 2023  to general $L_p$ norms and to $s$-rectangular case ?\nOne of the key of their proof was to bound the range of the value function by $1/\\sigma$ for large radius $\\sigma\\geq 1-\\gamma$. Is it possible to adapt it to $L_p$ RMDPs and to $s$-rectangular assumptions. Moreover is there a chance to concentrate more complex dual for $L_p$ RMDPs compare to TV case in Shi et al., 2023 ? \n\n\n\nFrom upper bound perspective: \n\n* **Adaptation  and generalisation of key lemma from Shi et al., 2023 to reduce sample complexity in the $L_p$ context.**  \nTwo new key lemmas 5 and 6 which are different from $TV$ case are derived,  introducing $C_g$ coefficient which is not present in Shi et al., 2023. \n\n\n* **Concentration of more complex dual for $L_p$ RMDPs compare to TV case**\nConcentration lemma (lemma 8) is very different from Shi et al. 2023 with additional term to control. Indeed as the dual form for $TV$ and $L_P$ , $p>1$  involve respectively a scalar optimization and a vector in the case of $L_p$, uniform concentration in lemma 8 is more challenging in the $L_p$ case with factor depending on the geometry of the norm called $C_s$. \n\n* **Adaptation and generalisation of the proof to $s$-rectangular case**\nContrary to Shi et al., 2023 , our proof tackles the problem of $s$-rectangular.  We introduce quantities related to the stochasticity of the policy in the upper bound which is not present in Shi et al., 2023 to derive bound in the $s$-rectangular case.\n\n\n* Finally **from a lower bound perspective** : new lower bound using counter example with stocastic optimal policy  for $s$-rectangular case  are derived and result from $sa$ rectangular is extended to $L_p$ norms.\n\n\n> 2- What challenges are involved in establishing lower bounds that hold for any $L_p$ norm in the s-rectangularity case? and  Establishing the lower bounds in the s-rectangularity setting for any L_p norm, not just the L_\\{linfty\\} norm, would strengthen the paper, enabling it to discuss minimax optimality also in that setting.\n\n\nThe lower bounds are for the case of $s$-rectangularity, which poses entirely new challenges compared to the case of $sa$-rectangularity: the \noptimal policies may be stochastic and difficult to characterise 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).\n\n\n\n> Q3  Is there a fundamental limitation to extending the results to the entire range of the uncertainty level?\n\nIndeed, we consider the full range of the uncertainty level in our theorems.\nIn Theorem 1 and 3, the entire possible range of uncertainty level $\\sigma$ is considered (see Theorem 1 and 3 where we defined $\\sigma_{max}$ and $\\tilde{\\sigma}_{max}$ in the $sa$- and $s$-rectangular case.\n\n> Q4- 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?\n\n\nIn the context of RMDPs the work of  [1] proposed to use weighted norm to define a RDMPs. Moreover, in other application without the scope of RDMPS, general norm are used in robust optmization such as in [2,3].\n\ngive examples from other areas, such as supervised learning, adversarial learning.\n\n>[1] Reazul Hasan Russel, Bahram Behzadian, and Marek Petrik. \"Optimizing norm-bounded weighted ambiguity\nsets for robust mdps\"  arXiv preprint arXiv:1912.02696, 2019\n\n> [2] Dimitris Bertsimas, Dessislava Pachamanova, Melvyn Sim  \"Robust linear optimization under general norms\n\n> [3]  J Rony, L Gustavo, R Sabourin, E Granger : Decoupling direction and norm for efficient gradient-based l2 adversarial attacks", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
# General response:
First, We would like thank the reviewers for their careful reading of the paper and their insightful and valuable feedback. 


### Highlight of our new challenges and technical contributions

We would like to highlight the technical challenge to answer reviewers 6HyR and 5t5a and explain the comparison to prior work Clavier et al. [2023]. Our main contributions focus on statistical perspective.



Compared to Clavier et al. [2023], the motivation was to improve the sample complexity when the radius of the uncertainty set  $\sigma>1-\gamma$. The bottleneck of Clavier et al. [2023] is that when $\sigma>1-\gamma$, the sample complexity is proportional to $1/(1-\gamma)^4$, which is far from optimal. Towards optimal and more broader results, our technical contributions is summarized as:
 
1) **Use a tighter error decomposition.** Clavier et al. [2023] use a  decomposition of Q functions related to the work of [1] (Lemma C1 in their paper). However, this decomposition is not fine enough for large radius $\sigma$ to obtain tighter bounds. The Variance decomposition in our paper allow tighter control of errors and is completely different (equation 64 of our work) compared to their work. Denoting $V^{\star, \sigma}$ the robust value function and the different kernel , and  $P^\pi$, the projection  $\pi$ projection  of kernel $P$ and   $\underline{P}^V$ the worst kernel such as  $\underline{P}^V =\arg \min_{P} PV$,
 we use :

$ \sqrt{Var_{P^{\pi^{\star}}}\left(V^{\star, \sigma}\right)}=\left(\sqrt{Var_{P^{\pi^{\star}}}\left(V^{\star, \sigma}\right)}-\sqrt{Var_{\widehat{P}^{\pi^{\star}}}\left(V^{\star, \sigma}\right)}\right)+\sqrt{Var_{\widehat{P}^{\pi^{\star}}}\left(V^{\star, \sigma}\right)} $

$
 \leq\left(\sqrt{Var_{P^{\pi^{\star}}}\left(V^{\star, \sigma}\right)}-\sqrt{Var_{\widehat{P^{\pi^{\star}}}}\left(V^{\star, \sigma}\right)}\right) 
 +\sqrt{\left|Var_{\widehat{P}^{\pi^{\star}}}\left(V^{\star, \sigma}\right)-Var_{\widehat{\underline{P}}^{\pi^{\star}, V}}\left(V^{\star, \sigma}\right)\right|}+\sqrt{Var_{\widehat{\underline{P}}^{\pi^{\star}, V}}\left(V^{\star, \sigma}\right)} .$

>[1] Azar, Mohammad and Munos, Rémi and Kappen Hilbert , Minimax PAC bounds on the sample complexity of reinforcement learning with a generative model 

2) **Use exact dual of RMDPs problem and not a relaxion.** Clavier et al. [2023] have an extra term in their upper bound proportional to $\frac{2 \gamma \beta|S|^{1 / q}}{1-\gamma}$ contrary to our work. To control error in their second theorem (Th.2),  they use a relaxation of the dual form or RMDPs in their Lemma C2, which lead to non-minimax bound for large radius $\sigma$ contrary to our proof. On contrary, we use the exact form of the dual in our proof in Theorem 1 and 3.


3) **Use a key lemma about the range of the value function.** Clavier et al. [2023] cannot achieve sample complexity lower than $1/(1-\gamma)^3$ as they did not use fundamental idea than the range of value function in RMPDS is constrained for large radius. The key idea that allows us to get smaller sample complexity, namely lemma 5 and 6 for $sa$- and $s$-rectangular for radius $\sigma>1-\gamma$ for $L_p$ norms, is that the range of the value function is bounded for $L_p$ RMDPs.


 
**From a lower bound perspective**, we derive the first  minimax lower bound for general $L_p$ in the $sa$ rectangular cases. In addition, we develop the first lower bound $s$-rectangular cases using divergence function for $L_\infty$.
The main technical contributions focus on the lower bounds are for $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 $L_p$ 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).

Meta-review: 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.
Decision: Accept (poster)