The Curious Price of Distributional Robustness in Reinforcement Learning with a Generative Model
Authors: Laixi Shi
Gen Li
Yuting Wei
Yuxin Chen
Matthieu Geist
Yuejie Chi
Venue: NeurIPS 2023 poster (2023)
Keywords: distributionally robust reinforcement learning
robust Markov decision processes
sample complexity

Abstract: This paper investigates model robustness in reinforcement learning (RL) via the framework of distributionally robust Markov decision processes (RMDPs). Despite recent efforts, the sample complexity of RMDPs is much less understood regardless of the uncertainty set in use; in particular, there exist large gaps between existing upper and lower bounds, and it is unclear if distributional robustness bears any statistical implications when benchmarked against standard RL. In this paper, assuming access to a generative model, we derive the sample complexity of RMDPs---when the uncertainty set is measured via either total variation or $\chi^2$ divergence over the full range of uncertainty levels---using a model-based algorithm called distributionally robust value iteration, and develop  minimax lower bounds to benchmark its tightness. Our results not only strengthen the prior art in both directions of upper and lower bounds, but also deliver surprising messages that learning RMDPs is not necessarily easier or more difficult than standard MDPs. In the case of total variation, we establish the minimax-optimal sample complexity of RMDPs which is always smaller than that of standard MDPs. In the case of $\chi^2$ divergence, we establish the sample complexity of RMDPs that is tight up to polynomial factors of the effective horizon, and grows linearly with respect to the uncertainty level when it approaches infinity.

The Curious Price of Distributional Robustness in Reinforcement Learning with a Generative Model
Laixi Shi* Caltech
Gen Li" CUHK
Yuting Wei UPenn
Yuxin Chen UPenn
Matthieu Geist Google
Yuejie Chi CMU
Abstract
This paper investigates model robustness in reinforcement learning (RL.) via the framework of distributionally robust Markov decision processes (RMDPs). Despite recent efforts, the sample complexity of RMDPs is much less understood regardless the uncertainty set use; in particular, there exist large gaps between existing upper and lower bounds, and it is unclear if distributional robustness bears any statistical implications when benchmarked against standard RL. this paper, assuming access generative model, we derive the sample complexity of RMDPs - when the uncertainty set measured via either total variation or x² divergence over the full range of uncertainty levels using model-based algorithm called distributionally robust value iteration, and develop minimax lower bounds to benchmark its tightness. Our results not only strengthen the prior art in both directions of upper and lower bounds, but also deliver surprising messages that learning RMDPs is not necessarily easier more difficult than standard MDPs. In sample complexity
the case of total variation, we establish the minimax-opting of RMDPs which is always smaller than that of standard MDPs. In the case of x² divergence, we establish the sample complexity of RMDPs that is tight up to polynomial factors of the effective horizon, and grows linearly with respect to the uncertainty level when it approaches infinity.
Introduction
Reinforcement learning (RL) deals with the problem of learning to make sequential decisions based on trial-and-rroo interactions with some unknown environment. As fast-growing subfield of artificial intelligence, it has achieved sigmificant success in a variety of domains such as large language model alignment (OpenAl, 2023; Ziegler et al., 2019), healthcare (Liiu et al., 2019; Fatemi et al., 2021). roboties and control (Kober et al., 2013; Mnih et al., 2013). Due to the high dimensionality of the state-action space, achieving sample efficiency lies at the core of modern RL practice, especially in various sample-starved applications. As result, large portion of efforts in RL has been put in designing sample-efficient algorithms and understanding the fundamental statistical difficulty for diverse RL problems (Azar al., 2013; Li et al., 2020).
While standard RL has been heavily invested recently, its use can be significantly hampered in practice due the sim-to-real gap. where an agent trained in an ideal, nominal environment might be extremely sensitive and fail catastrophically when the deployed environment is subject to small changes task objectives or unexpected perturbations (Zhang et al., 2020a; Klopp et al., 2017; Mahmood et al., 2018 8). Consequently, in addition to maximizing the long-term cumulative reward,
Department of Computing Mathematical Sciences, Californa Institute of Technology, CA, USA.
1 Department Statisties, The Chinese University Hong Kong. Hong Kong, China. "Deparmment of Statisties and Data Science, Wharton School, University of Pennsylvania, PA, USA. 8 Google Research, Brain Team, Paris, France.
Department of Electrical and Computer Engineering, Carnegie Mellon University, PA, USA.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

robustness becomes another critical goal for an RL agent, especially in high-stake applications such as robotics, autonomous driving, clinical trials, financial investments, and so on. To address this, distributionally robust RI. (lyengar, 2005; Nilim and EI Ghaoui, 2005), which leverages insights from distributionally robust optimization and supervised learning (Rahimian and Mehrotra, 2019; Gao, 2020; Bertsimas et al., 2018; Duchi and Namkoong, 2018; Blanchet and Murthy, 2019), becomes a natural and versatile framework with the goal of learning a policy that performs well even when the deployed environment deviates from the nominal one in the face of environment uncertainty.
In this paper, we are particularly interested in understanding whether, and how, the choice of distributional robustness bears statistical implications in learning the desired policy, by studying the sample complexity in the widely-used generative model (Kearn and Singh, 1999). Suppose that one has access to a generative model which draws samples from Markov decision processes (MDP) with a nominal transition kernel. Standard RI. aims to learn the optimal policy tailored for the nominal kernel based on this set of samples, where the sample complexity has been well understood with matching upper and lower bounds developed recently (Azar et al., 2013; Li et al., 2020). In contrast, distributionally robust RL leveraging the same set of samples the optimal robust policy whose worst-case performance is maximized when the transition kernel is from some prescribed uncertainty set around the nominal kernel, setting that is referred to as the robust MDP (RMDPs). 6 Clearly, this ensures that the performance of the learned policy is robust and does not fail catastrophically to wonder how the robustness consideration impacts the RL performance: should we always prefer to learn a robust policy for a given set of samples? Is there statistical premium when asking for additional robustness?
aims to learn
long as the sim-to-real gap is not too large. It is then natural
Compared with standard MDPs, RMDPs is richer class of models since one additionally needs to prescribe the shape and size of the uncertainty set, which is usually hand-picked as a small ball around the nominal kernel measured with respect to some distance measure and uncertainty level a To ensure the tractability of solving RMDPs, the uncertainty set is usually assumed to obey certain structures, where the uncertainty set can be decomposed as product of independent uncertainty subsets over each state or state-action pair (Zhou et al., 2021; Wiesemann et al., 2013), denoted as the and (s, a. rrectangularr rectangularity respectively; in particular, our paper adopts the second choice by assuming the uncertainty set satisfies the (s, a) rectangullart An additional challenge with RMDPs arises from distribution shift, where the transition kernel drawn from the uncertainty set can be different from the nominal kernel, leading to complicated nonlinearity and nested optimization in the problem structure not present in standard MDPs
1.1 Prior art and open questions
In this paper, we focus on understanding the sample complexity of learning the optimal robust policy of RMDPs in the infinite-horizon setting assuming access to generative model, when the uncertainty set is measured using one of the f-divergence: total variation (TV) distance and x divergence. These two choices are motivated by their practical appeal: easy to implement, and already adopted by empirical RL (Lee et al., 2021; Pan et al., 2023).
popular learning approach is model-based, which first estimates the nominal transition kernel using a plug-in estimator based on the collected samples, and then runs planning algorithm such as a robust variant of value iteration on top of the estimated RMDP. Despite the surge of recent activities however, existing statistical guarantees for the above paradigm remain highly inadequate, as we shall elaborate momentarily (see Table and Table respectively for a summary). For concreteness, let S be the size of the state space, A be the size of the action space, y be the discount factor (and the effective horizon I-g). ), and a be the uncertainty level. We are interested in the sample complexity the number of samples needed for an algorithm to output a policy whose robust value function (the worst-case value over all the transition kernels in the uncertainty set) is at most away from the optimal robust one- - with respect to all salient problem parameters.
Large gaps between existing upper and lower bounds. There remained large gaps between the sample complexity upper and lower bounds established in prior literature, regardless of the divergence metric in use. Specifically, considering the cases using either TV distance or x2 divergence, the state-of-the the upper bounds (Panaganti and Kalathil, 2022) scales quadratically with the size of the
'While it straightforward to incorporate additional uncertainty of the reward in our framework, we do not consider it here for simplicity, since the key challenge is to deal with the uncertainty of the transition kemel.

---

Sample complexity
Result type
Reference
x
1-7 --5
S²A(220))
Yang al. (2022)
o² (1
Panaganti Kalathil (2022)
(T-))*0
Upper bound
Ours
SA
84
(1=7)9p²
(1-7)Poz²
Yang et al. (2022)
S4 (1 (1-))922
9A(1->)
0'
Lower bound
Ours
SA (1-7)*²²
S4
(1-7)
Table I: Comparisons between our results and prior arts for finding an e-optimal robust policy in the infinite-horizon RMDPs with an uncertainty set measured with respect to the TV distance, where we ignore logarithmic factors in the sample complexities. Here, S, A, 7, and a E (0, 1) are the state space size, the action space size, the discount factor, and the uncertainty level, respectively.
Semple complesity
Sumple complesity
Japee
SPA
(Panaprti and Sdutie
Ittle
Upper bound
94 (1 1 7/%6
Standard MDPe
5A ( (1-78 7/4
menomac lowns lound
X4 IT 1/9F
S.Ar
8.4
Ohhi work)
84
Starderd MDn, usper & mihinos boar bound
11-77
11 -0
PALE
SA0 -10 -0
Lowerboand
SA
Lower boona Freng et
(1-5)e
001 -n)
0()
00--)
O01
0(1/1 -1))
(a) TV distance
(b) x2 distance
Figure 1: Illustrations of the obtained sample complexity upper and lower bounds for learning RMDPs with comparisons to state-of-the-an and the sample complexity standard MDPs, where the uncertainty set is specified using the TV distance (a) and the x² distance (b).
state space, while the lower bound (Yang et al., 2022) exhibits only linear scaling with S. Moreover, the x2 divergence case, the state-of-the-ar upper bound grows linearly with the uncertainty level a when σ 2 1,7 while the lower bound (Yang et al., 2022) is inversely proportional to a. These lead to unbounded gaps between the upper and lower bounds as a grows. Can we hope to close these gaps for RMDPs?
Benchmarking with standard MDPs. Perhaps more pressing issue is that, past works failed to provide an affirmative answer regarding how to benchmark the sample complexity of RMDPs with that of standard MDPs regardless of the chosen shape (determined by p) or size (determined by a) of the uncertainty set, given the large unresolved gaps mentioned above. Specifically, existing sample complexity upper (resp. lower) bounds are all larger (resp. smaller) than the sample size requirement for standard MDPss As consequence, it remains mostly unclear whether learning RMDPP is harder or easier than learning standard MDPs.
1.2 Main contributions
To address these questions, have developed new upper bounds on learning RMDPs with TV distance and x2 distance in the distributionally robust value iteration (DRVI), well minimax lower bounds help gauge their
setting using the model-based approach called
LLt X (S, A, - , 0, 1 1). The notation f(X) O(g(X)) f(x) S ((X) indicates that there exists universal constant Ci >> such that f < Cig. the notation f(X) 2 9(X²) indicates that g(X) (2)).. and the notation f(x²) 9(X²) indicates that f(x) S g(X)) and f(X)) 2 9(X)) hold simultaneously. Additionally, the notation Ō(-) is defined in the same way O()) except that it hides logarithmic factors.
3

---

Sample complexity
Result type
Reference
< 0<o51
S I-7
1
Panaganti and Kalathil (2022)
gA((+)))
(1-9)'6²
Upper bound
Yang al. (2022)
5 5*A(1+))*
11+0-119(110)
Ours
SA(1-a)
(I-5))2²
Yang et al. (2022)
84
S4 (1-5) Poct 00
(1-7)
Lower bound
Ours
(1-7)'e²
(1-7) -'+
SAa
Table 2: Comparisons between our results and prior arts for finding an e-optimal robust policy in the infinite-horizon RMDPs with an uncertainty set measured with respect to the x² distance, where we ignore logarithmic factors in the sample complexities. Here, S, A, 7, and E (0, oo) are the state space size, the action space size, the discount factor, and the uncertainty level, respectively.
tightness and provide benchmarking with standard MDPs. As shall be outlined, these new analyses lead to new insights on the interplay between the geometry of uncertainty sets and the statistical sample complexity.
Sample complexity of RMDPs under the TV distance. We summarize the results and comparisons to prior works in Table I; see Figure ((a) for an illustration.
catimmax-optimal sample complexity. We prove that DRVI reaches accuracy soon as the sample complexity is on the order of
SA (1 (1-7)22 min { 1 (1-x12)
for all a E (0, 1), assuming that e small enough. addition, a matching minimax lower bound (modulo some logarithmic factor) is established to guarantee the tightness of the upper bound. To the best of our knowledge, this is the first minimax-ope minimax-optimal sample complexity for RMDPs, which was previously unavailable regardless of the divergence metric and uncertainty level in use and is over the full range of the uncertainty level.
RMDPs are easier than standard MDPs under the TV distance. Given the sample complexity (--ン)p of standard MDPs, it can be seen that RMDPs under the TV distance never harder than standard MDPs, where it matches that of standard MDPs when S 1 7, and becomes simpler by a factor of a/((1 - 7) when 1 --- 7 S a < 1. Therefore, in this case, the robustness comes almost for free since we do not need to collect more samples to reach the same accuracy.
Sample complexity of RMDPs under the x² distance. We summarize the results and comparisons prior works in Table 2: see Figure ((b) for an illustration.
Near-optimal sample complexity. It is established that DRVI reaches e accuracy as soon as the sample complexity on the order of Ö SA(1+o) for all E (0, oc), which is the first sample complexity that scales linearly with respect to the size of the state space S in the infinite-horizon setting, breaking the quadratic scaling bottleneck presented in prior works (Panaganti and Kalathil, 2022; Yang et al., 2022). We have also developed strengthened lower bound that is optimized by leveraging the geometry of the uncertainty set under different ranges of o. Comparing the two bounds, they match δ of the effective horizon 1/(1- (1) over the entire range of the uncertainty level, again significantly improving prior art that exhibits an unbounded gap.
(1-1)"**
SAA (1-7)4²² when x 1, and have a bounded gap no larger than polynomial factor
RMDPs can be harder than standard MDPs under the x" distance. Somewhat surprisingly, the be much harder than standard MDPs, least
new lower bound suggests that RMDPs in this for certain ranges of the uncertainty level. We single out two regimes of particular interest. First,
which provably harder than when a x the sample size requirement of RMDPs is δ (--

---

standard MDPs by factor of the effective horizon 1_ Second, when σ 2 (I-y)a, the lower bound I-y.
exceeds the sample complexity of standard MDPs and keeps growing linearly with the uncertainty level o.
In sum, our sample complexity bounds not only strengthen the prior art in both directions of upper and lower bounds, but also reveal new insights on how the additional consideration of distributional robustness fundamentally changes the sample complexity of RL in a surprising manner. It turns out that RMDPs are not necessarily harder nor easier than standard MDPs, but answer is far more nuanced and highly dependent on both the size and shape of the uncertainty set, which are not elucidated in prior analyses.
2 Problem formulation
In this section, we introduce the model of distributionally robust Markov decision processes (RMDPs) focusing on the discounted infinite-horizon setting, the sampling mechanism, as well as our goal.
Standard MDPs. To begin, we first introduce the standard Markov decision process (MDP), which facilitates the understanding of RMDPs. A discounted infinite- horizon MDP is represented by M = (S, A, P. r), where S = {1..... S} and A = {1. ... A} are the finite state and action spaces, respectively, y E [0, 1) is the discount factor, P x A + (SS) denotes the probability transition kernel, and S A [0, 1] is the immediate reward function which is assumed to be deterministic. A policy is denoted as π S + (AA), which specifies the action selection probability over the action space in any state. When the policy deterministic, we overload the notation and refer to T (s) as the action selected by policy æ in state 8. To characterize the long term cumulative reward, the value function ya. for any policy æ under the transition kernel P is defined by
oc
AP E :::
(s) 10 E
Σ
(sr 0z) =
(1)
where the expectation is taken the randomness of the trajectory {st, at, ra rm generated by executing policy æ under the transition kernel P, namely, az ~ ((s)), and 81+1 ~ P(. 8t, at). Similarly, the Q-function QT. associated with any policy under the transition kernel P is defined as
20
V(s, E Sx
(s) = Ex.P
Er(r(s
as) 80 = s, 00 = 9.
(2)
where the expectation is again taken over the randomness of the trajectory.
Distributionally robust MDPs. In this work, focus on the discounted infinite-horizon distri- butionally robust MDP (RMDP), denoted as Mrab = {S, (S,A,, A, (P9), y,,r,,, r). where A.A.% r are defined the same as those in the above standard MDP. A key distinction from the standard MDP, is that rather than assuming a fixed transition kernel P, it postulates the transition kernel lies in an uncertainty set 24g (Po) centered around a nominal kernel po S x A - A(S), where the uncertainty set is specified using some distance metric p of radius a > O. In particular, given the nominal transition kernel pa and some uncertainty level a, the uncertainty weth divergence p: (SS) x (SS) + IR 1 specified as 4 = & (Po..)
(PD) = (Pa E E((S) p (PP (P..).P.))) S So].
(3)
where we denote vector of the transition kernel or pe at state-action pair (s, a) respectively as po s.a := p- (-|ss,a) E RIx5
Pa. == P( s,a) E I
(4)
In other words, the uncertainty imposed in separate manner for each state-action pair, obeying the so-called (s, -eeetatnggulrr (Zhou et al., 2021; Wiesemann et al., 2013). 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
((s,a) ES A:
VTT*(() = inf (r4)
( (s).
TT (s, = inf
QT. a).
Petig(Po)
Optimal robust policy and robust Bellman operator. Generalizing standard MDPs, it is well- known that there exists at least one deterministic policy that maximizes the robust value function and
5

---

the robust Q-function simultaneously (lyengar, 2005; Nilim and EI Ghaoui, 2005). Therefore, we denote the optimal robust value function (resp. optimal robust (-function) as V* (resp. Q* ) and the optimal robust policy as ' which satisfies
E V**o(s) = V='.0
"00"00( (s) max V*.0 (s),
(5a)
x
(( a) E x A: Q = Q (s. = max Q" (s, a).
(5b)
The robust Bellman operator (lyengar, 2005; Nilim and El Ghaoui, 2005) is denoted T (+): RSA _ IRSA, which is defined as follows: for all (s,a) E S x A,
(")) a) = r(s,a) a) + inf PV, with = = max Q(s.a).
(6)
PEU;
Given that Q is the unique fixed point TT, one can recover the optimal robust value function and Q-function using a procedure termed distributionally robust value cerrationwhiie generalizes the standard value iteration-by recursively applying the robust Bellman operator from some fixed initialization. In addition, this procedure converges rather fast due to the nice 7-contraction property of T. (lyengar, 2005; Nilim and El Ghaoui, 2005) with respect to the lx norm.
Specification of the divergence p. We consider two popular choices of the uncertainty set measured in terms of the f-divergence: total variation and x2 divergence, given respectively by
1 Pee - Poall1 = Σ x'ES
1 P(s' s.
PTv Pe. s.a) = 2
po (5
(7)
(5 [8,))
2 Pxa (Peja Pooo) (e.)) = Σ ( (1- P(s' ss,)
(8)
(
e'ES
Note that PTv (Ps.ay pog) ) E [0. 1] and Px2 (Ps.s pa.)) E [0, oc) in general. As we shall see, the two choices convey drastically different messages in the statistical complexity of RMDPs.
Sampling mechanism: a generative model. Following Zhou et al. (2021); Panaganti and Kalathil (2022), we assume the access to a generative model or simulator (Kearns and Singh, 1999), which allows us collect N independent samples from the nominal kernel pd at each state-action pair:
V(s, S A,
$i,s,a iid (0),,,,))
1 ....
The total sample size therefore is NSA.
Goal. Given the collected samples, the task is to learn the robust optimal policy for the RMDP with some uncertainty set U (P9) around the nominal kernel accurately using as few samples as possible. Specifically, given some accuracy level > O, the goal is to seek an e-optimal robust policy f obeying V*.0 (s) - (s) < for all S.
Model-based algorithm: distributionally robust value iteration
We consider a model-based strategy, which first constructs an empirical nominal transition kernel based on the collected samples, and then applies distributionally robust value iteration (DRVI) to recover the optimal robust policy.
The empirical nominal transition kernel po E R. SAXS can be constructed using the empirical frequency of visits, i.c.
Empirical nominal kernel.
N
V(s,a) e Sx
(0 ss,a) = N
Σ 1 15,,0,0=5 5
(10)
1=1
which leads to an empirical RMDP Mrob = A,,, (P*), n, Analogously, we can define the corresponding robust value function (resp. robust Q-function) of policy π in Miob as V (resp. Q=.0) (cf. (5)). In addition, we denote the corresponding optimal robust policy as 7* and the optimal robust value function (resp. optimal robust Q-function) as V+. (resp. Q (cf. (5)), which satisfies the robust Bellman optimality equation:
((s SS
(x)((s a) = a) + inf
pvva PE
(11)

---

Algorithm 1: Distributionally robust value iteration (DRVI) for infinite-horizon RMDPs.
input: empirical nominal transition kernel p0; reward function r; uncertainty level o; number of iterations T.
initialization: Qo(s, a) 3 for / 1,2, ,. , do
(s for all (s, a) E A.
for s S, a E A do
L Set (r(s, a) according to (13);
for s S do Set Vi(s) max, Q1(s, a):
output: Qr. V7 and मे obeying A(s) arg max, Q8)
Equipped with po, define the empirical robust Bellman operator Tor inf PV, with V(s) max Q(, a). (12)
((s,a) ES x A: (")(ss a) == r(s,a) +
PPu
DRVI: distributionally robust value iteration. To solve for the fixed point of oo. we introduce distributionally robust value iteration (DRVI), which is summarized in Algorithm 1. Starting from some initialization Qo = O, the update rule at the 1-th (t Z 1) step can be formulated as:
V(s,a) ES x A: (s) = 70 (Qc-1) (s, = a(s,a)+ +
inf PV-.
(13)
(P
where ()= max, Qi-1(s, a) for all s E S. However, directly solving (13) is computationally prohibitive since it involves optimization over an S-dimensional probability simplex at each iteration, especially when the dimension of the state space S is prohibitive. Fortunately, in view of strong duality (lyengar, 2005), (13) can be equivalently solved using dual problem, which concerns optimizing of scalar dual variable and thus can be solved efficiently. The specific form of the dual problem depends on the choice of the divergence which we discuss in a more detailed version.
4 Theoretical guarantees: sample complexity analyses
We now present main results, which concern the sample complexities of learning RMDPs when the uncertainty set is specified using the TV distance or the x² divergence. Surprisingly, the choice of the uncertainty set can lead to dramatic consequence the sample size requirement.
4.1 The case of TV distance: RMDP is easier than standard MDP
We start with the case when the uncertainty set is measured via the TV distance, where Theorem I presents the sample complexity upper bound above which DRVI is able to find e-optimal robust policy in small number of iterations; the key challenge of the analysis is to carefully control the robust value function ==,0 as a function of uncertainty level o.
Theorem (Upper bound using TV distance). Fix the uncertainty set UØ (.) U.f(-)) using the TV distance in (7). Consider any discount factor E 1), uncertainty level (0, 1), and 5 E (0, 1). With probability at least 1 8, the output from Algorithm 1 with at most T C₁ log (N(1->))
iterations yields V+ (s) - V².0 (s) S e for any E E (0. VI/ max 11 - 7,, 0 as long as the total
number of samples obeys NSA 2 large enough universal constants.
CASA max m
log
SAN [1-7)6
Here, C₁, C2 > 0 are some
Before discussing the implications of Theorem we present a matching minimax lower bound that confirms the optimality of the upper bound, which in turn pins down the sample complexity requirement for learning RMDPs with TV distance.
Theorem 2 (Lower bound using TV distance). Consider any tuple (S, A,,,0,) obeying (0, 1 co] with O < Co < 1 being any small enough positive constant, [ 1), and E E (0, 200(--77] We
7

---

which is can construct two infinite-horiznt RMDPs Mo. M2 defined by the uncertainty set U, (-) = (-), an initial state distribution ip, and a dataset with independent samples for each state-action pair over the nominal transition kernel (for Mo and Mi respectively), such that
inf max (V (vp V (4) > 8), Pi(V -V)
provided that N 8192(1-7)² (resp. PT) denotes the probability when the RMDP is Mo (resp. M1).
1_,x)1- The infinum is taken over all estimators R, and Po
Below. we interpret the above theorems and highlight several key implications about the sample complexity requirements for learning RMDPs with TV distance.
Near minimax-optimal sample complexity. required for DRVI to yield E-accuracy is
Theorem 1 shows that the total number of samples
SA
(14)
(1-7)²
-, - TE?
Taking together with the minimax lower bound asserted in Theorem 2, this confirms the near minimax- optimality of the sample complexity up some logarithmic factor almost over the full range of the uncertainty level a, which scales linearly with respect to the size of the state-action space.
RMDPs is easier than standard MDPs with TV distance. Recall that the sample complex- ity requirement for standard MDP (Agarwal et al., 2020; Li et al., 2020) to yield accuracy is
Ō (1- Comparing with the sample complexity requirement (14) for RMDPs with TV distance, this confirms that the latter is at least easy as as-if not easicr-than standard MDPs. In particular, when a & 1-11 - y is small, the sample complexity of RMDPs is the same as the standard MDPs, which is expected since the RMDP reduces to the standard MDP when 0. On the other hand, when - 7 S a < 1, the sample complexity of RMDPs becomes Ô
S.4 (1-7)-00)
smaller than that of standard MDPs by a factor of 0/(1 7)-
Comparison with state-of-the-art bounds. For the upper bound, our results (cf. Theorem significantly improves over the prior art Ö
(1-7)-e² of Panaganti and Kalathil (2022) by at least
S²A
factor of S and even [I-7]² when the uncertainty level 7 S a is large. Turning to the lower bound side, Yang al. (2022) developed a lower bound for RMDPs under the TV distance, (1=))= 34 }+) Clearly, this is worse than ours by factor of (1-933 E (1, (1-7))) in the regime where 1 - <<
S
which scales Ô SA(1-1)) min
4.2 The case of x² distance: RMDP can be harder than standard MDP
We now move onto the case when the uncertainty set is measured via the x² distance, where Theorem 3 presents the sample complexity upper bound above which DRVI is able find an e-optimal robust policy in small number of iterations.
Theorem (Upper bound using x2 distance). Fix the uncertainty set (g 27a()) (-) using the x²
distance in (8). Consider any uncertainty level a (0, oo), and 8 (0, 1). With probability at least - 8, the output policy î from Algorithm I with at most T = C1 log (N (1 - -7) iterations
yields V*.0 (8) - (s) < E for any & E T-g] as long as the total number of samples obeying
NSA 2 (ASA(1))) log SAN). Here, C2 > 0 are some large enough universal constants. (1->)+22
In addition, in order to gauge the tightness of Theorem 3, and understand the minimal sample complexity requirement for learning RMDPs with x² divergence, further develop a minimax lower bound as follows.
Theorem 4 (Lower bound using x² divergence). Consider any (S, (S,A,%, obeying E [ 1), (0, oo), and
ifo (0, ) isa E 11,,00)
S C3
(15)
maxx
6
8

---

for some small universal constant Cs > 0. Then we can construct two infinite-horizzn RMDPs M, defined by the uncertainty set (.) = (+), an initial state distribution p. and dataset with N independent samples for each (s, a) pair over the nominal transition kernel (for Mu and Mi respectively), such that
inf max (Fa(VV>())) - > e), (i(v - (p) (0))))) 20)>
(16)
provided that the total number of samples
if E (0, 10,
NSA < C4
[1-7)²²² agA
(17)
ifa 00)
min(L.(->>)
for some universal constant 04 > O.
We are now positioned to highlight some key implications of the above theorems about the sample complexity requirements for learning RMDPs with x² divergence.
Nearly tight sample complexity. To achieve e-accuracy for RMDPs with x² distance, Theorem shows that a total number of samples on the order of Ô (A(L+)) [I-7]aa²
is sufficient for DRVI. Taking
together with the minimax lower bound in Theorem confirms that the sample complexity is near-optimal up to polynomial factor of the effective horizon 1/(1 -?) over the entire range of the uncertainty level σ.. In particular, when x 1, our sample complexity (1--)) is tight and matches with the lower bound; when Z (I-ク}ı our sample complexity correctly predicts the linear dependency with o, suggesting that more samples are needed when one plans for larger x
S.4
uncertainty sets.
RMDPs can be much harder than standard MDPs with x² divergence. The minimax lower bound developed in Theorem 4 exhibits a surprising non-monon non-monotonic behavior of the sample size requirement over the entire range of the uncertainty level a E (0, 20) when the uncertainty set is measured via the
x2 divergence. When S 1 7/ the lower bound reduces Ö
SA
which matches with
[1
[1-7)
that of standard MDPs, as a = 0 corresponds to standard MDP. However, two additional regimes are worth calling out:
(11
SA min ( 0. () and o 2 (1 (1- 7)3 (1-
SAo E2
1-7503 (1 - 7113 :
Ō
both of which are greater than that of standard MDPs, indicating learning RMDPs with x² divergence can be much harder.
Comparison with -tate-of-the-art bounds. Our upper bound significantly improves over the prior art δ Sat A(1-a) of Panaganti and Kalathil (2022) by factor of S, and provides the first finite-sample (1-7)422
complexity that scales linearly with respect to S for discounted infinite-horizon RMDPs, which typically exhibit more complicated statistical dependencies than the Enite-horizon counterpart. On
the other hand, Yang et al. (2022) established lower bound on the order of Ô
(1=7))a0² when
SA
2 - y, which is always smaller than the requirement of standard MDPs, and diminishes when grows. Consequently, Yang et al. (2022) does not lead to the rigorous justification that RMDPs can be harder than standard MDPs, nor the correct linear scaling of the sample size when grows towards infinity.
5 Other related works
Finite-sample guarantees for standard RL. There has been considerable amount of research into non-as -ampttttttoicc sample analysis of standard RL for variety of settings; partial examples include, but are not limited to, the works via probably approximately correct (PAC) bounds for the generative model setting (Kearns and Singh, 1999; Beck and Srikant, 2012; Li et al., 2022a; Chen et al., 2020; Azar al., 2013; Sidford et al., 2018; Agarwal al., 2020; et al., 2023, 2020; Wainwright, 2019) and the offline setting (Rashidinejad et al., 2021; Xie et al., 2021; Yin et al., 2021; Shi et al., 2022: Li

---

et al., 2022b; Jin et al., 2021; Yan et al., 2022). as well as the online setting via both regret-based and PAC-base analyses (Jin et al., 2018: Bai et al., 2019; et al., 2021; Zhang al., 2020b; Dong et al., 2019; Jin et al., 2020; Li et al., 2022a; Jafarnia-Jahrom et al., 2020; Yang et al., 2021; Woo et al., 2023).
Robustness in RL. To address the challenges of deployed environment uncertainty, an emerging line of works begin address robustness of RL algorithms with respect to the uncertainty or perturbation over different components of MDPs state, action, reward, and the transition kemel; see Moos et al. (2022) for recent review. Besides the framework of distributionally robust MDPs (RMDPs) (Iyengar, 2005) adopted by this work, to promote robustness in RL, there exist various other works including but not limited to Zhang al. (2020a, 2021); Han et al. (2022); Qiaohen et al. (2021); Sun et al. (2021); Xiong et al. (2022) investigating the robustness w.r.t. state uncertainty. Besides, Tessler et al. (2019); Tan al. (2020) considered the robustness w.r.t. the uncertainty of the action, and Ding et al. (2023) tackles robustness against spurious correlations.
Distributionally robust RL. Rooted in the literature of distributionally robust optimization, which has primarily been investigated in the context of supervised learning (Rahimian and Mehrotra, 2019: Gao. 2020; Bertsimas et al., 2018; Duchi and Namkoong, 2018; Blanchet and Murthy, 2019), distributionally robust dynamic programming and RMDPs have attracted considerable attention recently (Wolff et al., 2012; Kaufman and Schaefer, 2013; Ho et al., 2018; Smirnova et al., 2019; Ho et al., 2021; Goyal and
2022; Derman and Mannor, 2020; Tamar et al., 2014). In the context of RMDPs, both empirical and theoretical studies have been widely conducted, although most prior theoretical analyses focus on planning with an exact knowledge of the uncertainty set (lyengar, 2005; Xu and Mannor, 2012: 2: Tamar et al., 2014), or are asymptotic in nature (Roy et al., 2017).
Resorting to the tools of high-dimensional statistics, various recent works begin to shift attention to understand the finite-sample performance of provable robust RL algorithms, under diverse data generating mechanisms and forms of the uncertainty set over the transition kernel. Besides the horiitt-horizon setting, finite-sample complexity bounds for RMDPs with the TV distance and the x2 divergence are also developed for the finite-horizon setting in Xu et al. (2023); Dong et al. (2022). In addition, many other forms of uncertainty sets have been considered associated with different divergence function including but not limited to Wasserstein distance, R-contamination, KL divergence, Wang and Zou (2021); Yang et al. (2022); Panaganti and Kalathil (2022); Zhou al. (2021); Shi and Chi (2022); Xu et al. (2023); Wang et al. (2023a); Blanchet et al. (2023); Liu et al. (2022); Wang et al. (2023c); Liang et al. (2023); Xu et al. (2023); Badrinath and Kalathil (2021); Ramesh et al. (2023); Panaganti et al. (2022); Ma et al. (2022). Moreover, various other related problems or issues have been explored such as the difference of various uncertainty types (Wang et al., 2023b), the iteration complexity of the policy-base methods (Li et al., 2022c; Kumar et al., 2023), the cases when the uncertainty level is instance-depender small enough (Clavier et al., 2023), and eegularization-based robust RL (Yang al., 2023; Zhang al., 2023).
6 Discussions
This work studies sample complexity bounds for learning RMDPs when the uncertainty set is measured via the TV distance and the x" divergence under the generative model. Our sample complexity bounds not only strengthen the prior art in both directions of upper and lower bounds, but also reveal new insights on how the additional consideration of distributional robustness fundamentally changes the sample complexity of RL in a surprising manner. It turns out that RMDPs are not necessarily harder nor casier than standard MDPs, but the answer is far more nuanced and highly dependent on both the size and shape of the uncertainty set under consideration. These findings could help to guide the practice of RMDPs, by raising awareness that the choice of the uncertainty set not only represents a preference in robustness, but also influences the statistical complexity of the problem.
Acknowledgments and Disclosure of Funding
The work of L. Shi and Y. Chi is supported in part by the grants ONR N00014-19-1-2404 NSF CCF-2106778, DMS-2134080 and CNS-2148212. I.. Shi is also gratefully supported by the Leo Finzi Memorial Fellowship. Wei Shen and Xuchong Zhang Presidential Fellowship, and Liang
10

---

Ji-Dian Graduate Fellowship at Carnegie Mellon University. The work of Y. Wei is supported in part by the the NSF grants DMS-2144746/2015447,, CAREER award DMS-2143215, CCF-2106778. and the Google Research Scholar Award. The work of Y. Chen is supported in part by the Alfred P. Sloan Research Fellowship, the Google Research Scholar Award, the AFOSR grant FA9550-22-1-00 22-00--------99. the ONR grant N0001 also acknowledge Zuxin Liu and He Wang for valuable discussions.
and the NSF grants CCF-2221000 and CCF-1907661. The authors
References
Agarwal, A.. Kakade, S., and Yang, L. F. (2020). Model-based reinforcement learning with generative model is minimax optimal. In Conference on Learning T'heory, pages 67-83. PMLR.
Azar, M. G., Munos, R., and Kappen, H. J. (2013). Minimax PAC bounds on the sample complexity of reinforcement learning with generative model. Machine learning, 91(3):325-349.
Badrinath, K. P. and Kalathil, D. (2021). Robust reinforeement learning using least squares policy iteration with provable performance guarantees. In International Conference on Machine Learning. pages 51 510-520. PMLR.
Bai, Y., Xie, T., Jiang, N., and Wang, Y.-X. (2019). Provably efficient Q-learning with low switching cost. arXiv preprint arXiv: 1905. 12849.
Beck, C. L. and Srikant, R. (2012). Error bounds for constant step-size Q-learning, Systems & control letters, 61(11):1203-13 1208.
Bertsimas, D., Gupta, V., and Kallus, N. (2018). Data-driven robust optimization. Mathematical Programminng 167(2):235-2))) 292
Blanchet, J., Lu, M., Zhang, T., and Zhong, H. (2023). Double pessimism is provably efficient for distributionally robust offline reinforcement learning: Generic algorithm and robust partial coverage. arXiv preprint wrXhv:2305.09653
Blanchet, J. and Murthy, K. (2019). Quantifying distributional model risk via optimal transport. Mathematics of Operations Research, 44(2):665-600)
Chen, Z., Maguluri, S. T., Shakkottai, S., and Shanmugam, (2020). Finite-sample analysis of stochastic approximation using smooth convex envelopes. arXiv preprint arXiv:2002.00874
Clavier, P., Pennec, F. I.., and Geist, M. (2023). Towards minimax optimality of model-based robust reinforcement learning. arXiv preprint arXiv:230..0377251.
Derman, E. and Mannor, S. (2020). Distributional robustness and regularization in reinforcement learning. arXiv preprint S.XXi::003302884
Ding, W., Shi, L., Chi, Y., and Zhao, D. (2023). Seeing is not believing: Robust reinforcement learning against spurious correlation. In Thirty-seventh Conference Neural Information Processing Systems.
Dong, J., J., Wang. B., and Zhang. J. (2022). Online policy optimization for robust MDP, arXiv preprint arXiv:2209. 13841.
Dong, K., Wang, Y., Chen, X., and Wang, L. (2019). Q-learning with UCB exploration is sample efficient for infinite-horizon MDP. arXiv preprint arXiv:1901.09;
Duchi, and Namkoong, H. (2018). Learning models with uniform performance via distributionally robust optimization. arXiv preprint ftt.:18810085000
Fatemi, M., Killian, T. W., Subramanian, J., and Ghassemi, M. (2021). Medical dead-ends and
learning to identify high-risk states and treatments. Advances in Neural Information Processing Systems, 34:4856-4870.
Gao, R. (2020). Finite-sample guarantees for wasserstein distributionally robust optimization: Breaking the curse of dimensionality. arXiv preprint 273442200..04388
11

---

Goyal, V. and Grand-Clement Clement, J. (2022). Robust markov decision processes: Beyond rectangularity. Mathematics of Operations Research.
Han, S., Su, S., He, S., Han, S., Yang, H., and Miao, F. (2022). What is the solution for state adversarial multi-agent reinforcement learning? arXiv preprint arXiv:2212.02705.
Ho, C. P., Petrik, M., and Wiesemann, W. (2018). Fast bellman updates for robust MDPs. In International Conference Machine Learning, pages 1979-1988. PMLR.
Ho, C. P., Petrik, M., and Wiesemann, W. (2021). Partial policy iteration for 11-robust markoy decision processes. Journal of Machine Learning Research, 22(275):1-46.
Iyengar, G. N. (2005). Robust dynamic programming. Mathematics of Operations Research, 30(2)257-280.
Jafarnia-Jahromi, M., Wei, C.-Y., Jain, R., and Luo, H. (2020). A model-free learning algorithm for infinite-horizon average-reward MDPs with near-optimal regret. arXiv preprint arXiv:2006.0433
Jin, C., Allen-Zhuu Z., Bubeck, S., and Jordan, M. (2018). Is Q-learning provably efficient? In Advances in Neural Information Processing Systems, pages 4863 4873.
Jin, C., Krishnamurthy, A., Simchowitz, M., and Yu, T. (2020). Reward-free exploration for reinforcement learning. In International Conference on Machine Learning, pages 4870 4879. PMLR.
Jin, Y., Yang, Z., and Wang, Z. (2021), Is pessimism provably efficient for offline RL? In International Conference on Machine Learning, pages 5084-5096.
Kaufman, D. L. and Schaefer, A. J. (2013). Robust modified policy iteration. INFORMS Journal on Computing, 25(3):396-410.
Kearns, M. and Singh, S. P. (1999). Finite-sample convergence rates for Q-learning and indirect algorithms. In Advances in neural information processing systems, pages 996-1002.
Klopp, O., Lounici, K., and Tsybakov, A. B. (2017). Robust matrix complction. Probability Theory and Related Fields, 169(1-2);523-564,
Kober, J., Bagnell, A., and Peters, (2013). Reinforcement learning in roboties: A survey. The International Journal of Robotics Research, 32(11):1238-1)
Kumar, N., Derman, E., Geist, M., Levy, K., and Mannor, S. (2023). Policy gradient for s-rectangular robust markov decision processes. arXiv preprint 23X1v:2301.13355
Lee, J., Jeon, W., Lee, B., Pineau, J., and Kim, K.-E. (2021). Optidice: Offline policy optimization via stationary distribution correction estimation. In International Conference on Machine Learning. pages 6120-6130. PMLR.
Li, G., Cai, C., Chen, Y., Wei, Y., and Chi, Y. (2023). Is Q-learning minimax optimal? a tight sample complexity analysis. Operations Research.
Li, G., Chi, Y., Wei, Y., and Chen, (2022a). Minimax-optimal multi-agent markov games with generative model. Advances in Neural Information Processing Systems, 15:15353-15367.
Li, G., Shi, L., Chen, Y., Chi, Y., and Wei, Y. (2022b). Settling the sample complexity of imodel-based offline reinforcement learning, arXiv preprint arX1v:220..05275
Li, G., Shi, L., Chen, Y., Gu, Y., and Chi, (2021). Breaking the sample complexity barrier to regret-optimal model-free reinforcement learning. Advances in Neural Information Processing Systems, 34.
Li, G., Wei, Y., Chi, Y., Gu, Y., and Chen, Y. (2020). Breaking the sample size barrier in model-based reinforcement learning with a generative model. Advances neural information processing systems, 33:12861-12872
12

---

Li, Y., Zhao, T., and Lan, G. (2022c). First-order policy optimization for robust markov decision process. arXiv preprint arXiv:2209.10579.
Liang, Z., Ma, X., Blanchet, J., Zhang, J., and Zhou, Z. (2023). Single-trajectory distributionally robust reinforcement learning. arXiv preprint arXiv:2301.11211
Liu, S., Ngiam, K. Y., and Feng, M. (2019). Deep reinforcement learning for clinical decision support: brief survey. arXiv preprint xrXiv:1907009477
Liu, Z., Bai, Q.. Blanchet, J., Dong, P., Xu, W., Zhou, Z., and Zhou, Z. (2022). Distributionally robust q-learning. In International Conference on Machine Learning, pages 13623- 13623-13633. PMLR.
Ma. X., Liang, Z., Blanchet, J., Liu, M., Xia, L., Zhang, J., Zhao, Q. and Zhou, Z. (2022). Distribu- tionally robust offline reinforcement learning with linear function approximation. arXiv preprint arXiv:2209.0600
Mahmood, A. R., Korenkevych, D., Vasan, G., Ma. W. and Bergstra, J. (2018). Benchmarking reinforcement learning algorithms on real-world robots. In Conference on robot learning, pages 561-591. PMLR.
Mnih, V., Kavukcuoglu, K., Silver, D., Graves, A., Antonoglou, I., Wierstra, D., and Riedmiller, M. (2013). Playing atari with deep reinforcement learning. arXiv preprint arXiv:1312.5600
Moos, J., Hansel, K., Abdulsamad, H., Stark, S., Clever, D., and Peters, J. (2022). Robust reinforce- ment learning: review of foundations and recent advances. Machine Learning and Knowledge Extraction, 4(1 4(1):276-315.
Nilim, A. and El Ghaoui, L. (2005). Robust control of Markov decision processes with uncertain transition matrices. Operations Research, 53(5):780-778
OpenAl (2023). Gpt-4 technical report.
Pan, Y., Chen, Y., and Lin, F. (2023). Adjustable robust reinforcement learning for online 3d bin packing, arXiv preprint arXiv:2310.04323.
Panaganti, K. and Kalathil, D. (2022). Sample complexity of robust reinforcement learning with a generative model. In International Conference on Artificial Intelligence and Statistics, pages 9582-9602. PMLR.
Panaganti, K., Xu, Z., Kalathil, D., and Ghavamzadeh, M. (2022). Robust reinforcement learning using offline data, Advances in neural information processing systems, 35:32211-32224.
Qiaoben, Y., Zhou, X., Ying. C., and Zhu, J. (2021). Strategically-timed state-observation attacks on deep reinforcement learning agents. In ICML 2021 Workshop on Adversarial Machine Learning.
Rahimian, H. and Mehrotra, S. (2019). Distributionally robust optimization: A review. arXiv preprint UrXiv:1908.0550 05659.
Ramesh, S. S., Sessa, G., Hu, Y., Krause, A., and Bogunovic, I. (2023). Distributionally robust model-based reinforcement learning with large state spaces. arXiv preprint
Rashidinejad, P., Zhu, B., Ma, C., Jiao, J., and Russell, S. (2021). Bridging offline reinforcement learning and imitation learning: A tale of pessimism. Neural Information Processing Systems (NeurIPS).
Roy, A., Xu, H., and Pokutta, (2017). Reinforcement learning under model mismatch. Advances in neural information processing systems, 30.
Shi, I.. and Chi, Y. (2022). Distributionally robust model-based offline reinforcement learning with near-optimal sample complexity. arXiv preprint 20XX::2208.05767.
Shi, L.,, Li, G., Wei, Y., Chen, Y., and Chi, Y. (2022). Pessimistic Q-learning for offline reinforcement learning: Towards optimal sample complexity. In Proceedings of the 39th International Conference Machine Learning, volume 162, pages 19967-20025. PMLR.
13

---

Sidford, A., Wang, M., Wu, X., Yang, L., and Ye, Y. (2018). Near-optimal time and sample complexities for solving Markov decision processes with generative model. In Advances in Neural Information Processing Systems, pages 5186-5196.
Smirnova, E., Dohmatob, E., and Mary, J. (2019). Distributionally robust reinforcement learning. arXiv preprint arXiv: 1902.08708.
Sun, K., Liu, Y., Zhao, Y. Yao, H., Jui, S., and Kong, L. (2021). Exploring the training robust- ness of distributional reinforcement learning against noisy state observations. arXiv preprint 109.0770...
Tamar, A., Mannor, S., and Xu, H. (2014). Scaling up robust MDPs using function approximation. In International conference machine learning, pages 181 181-189. PMLR.
Tan, K. L., Esfandiari, Y., Lee, X. Y., and Sarkar, S. (2020). Robustifying reinforcement learning
agents via action space adversarial training. In 2020 American control conference (ACC), pages 3959-3964. IEEE.
Tessler, C., Efroni, Y., and Mannor, S. (2019). Action robust reinforcement learning and applications in continuous control. In International Conference on Machine Learning, pages 6215-6224. PMLR.
Wainwright, M. J. (2019). Stochastic approximation with cone-contractive operators: Sharp fx- bounds for Q-learning. arXiv preprint arXiv:1905.06265
Wang, S., Si, N., Blanchet, J., and Zhou, Z. (2023a). A finite sample complexity bound for distribu- tionally robust q-learning. arXiv preprint arXiv:2302. 13203.
Wang. S., Si, N., Blanchet, J., and Zhou, Z. (2023b). On the foundation of distributionally robust reinforcement learning. arXiv preprint 1iv::2311.000111
Wang. S., Si, N., Blanchet, J., and Zhou, Z. (2023c). Sample complexity of variance-reduced distributionally robust Q-learning. arXiv preprini arXiv:2305. 18420.
Wang. Y. and Zou, S. (2021). Online robust reinforcement learning with model uncertainty, Advances in Neural Information Processing Systems, 34.
Wiesemann, W., Kuhn, D., and Rustem, B. (2013). Robust markov decision processes. Mathematics of Operations Research, 38(1):153-183
Wolff, E. M., Topcu, U., and Murray, R. M. (2012). Robust control of uncertain markov decision processes with temporal logic specifications. In 2012 IEEE 51st IEEE Conference Decision and Control (CDC), pages 3372-3379. IEEE.
Woo, J.. Joshi, G., and Chi, Y. (2023). The blessing of heterogeneity in federated Q-learning: Linear speedup and beyond. arXiv preprini arXiv:2305. 10697.
Xie, T., Jiang, N., Wang, H., Xiong, C.,, and Bai, Y. (2021). Policy finetuning: Bridging sample- efficient offline and online reinforcement learning. Advances in neural information processing systems, 34.
Xiong, Z., Eappen, J., Zhu, H., and Jagannathan, S. (2022). Defending observation attacks in deep reinforcement learning via detection and denoising. arXiv preprint arXiv:2206.077
Xu, H. and Mannor, S. (2012). Distributionally robust Markov decision processes. Mathematics of Operations Research, 37(2):288-304
Xu, Z., Panaganti, K., and Kalathil, D. (2023). Improved sample complexity bounds for distribution- ally robust reinforcement learning. arXiv preprint arXiv:2303.02783.
Yan, Y. Li, G., Chen, Y., and Fan, J. (2022). The efficacy of pessimism in asynchronous Q-learning. arXiv preprint arXivv2203.07366.
Yang, K., Yang, I.., and Du, S. (2021). Q-learning with logarithmic regret. In International Conference on Artificial Intelligence and Statistics, pages 1576-1584. PMLR.
14

---

Yang. W., Wang, H., Kozuno, T., Jordan, S. M., and Zhang, Z. (2023). Avoiding model estimation in robust markov decision processes with a generative model. arXiv preprint arXiv:2302.01228.
Yang, W., Zhang, L., and Zhang, Z. (2022). Toward theoretical understandings of robust Markov decision processes: Sample complexity and asymptotics. The Annals of Statistics, 50(6):3223- 3248.
Yin, M., Bai, Y., and Wang, Y.-.. (2021). Near-optimal offline reinforcement learning via double variance reduction. arXiv preprint arXiv:2102.01748.
Zhang, H., Chen, H., Boning, D., and Hsich, C.-J. (2021). Robust reinforcement learning on state observations with learned optimal adversary. arXiv preprint arXiv:2101.08452
Zhang, H., Chen, H., Xiao, C., Li, B., Liu, M., Boning, D., and Hsieh, C.-J. (2020a). Robust deep reinforcement learning against adversarial perturbations on state observations. Advances Neural Information Processing Systems, 33:21024-21000
Zhang, R., Hu, Y., and Li, N. (2023). Regularized robust mdps and risk-sensitive mdps: Equivalence, policy gradient, and sample complexity. arXiv preprint arXiv:2306.11626.
Zhang, Z., Zhou, Y., and Ji, X. (2020b). Almost optimal model-free reinforcement learning via reference-advantage decomposition. Advances in Neural Information Processing Systems, 33,
Zhou, Z., Bai, Q.. Zhou, Z., Qiu, L., Blanchet, J., and Glynn, P. (2021). Finite-sample regret bound for distributionally robust offline tabular reinforcement learning. In International Conference on Artificial Intelligence and Statistics, pages 3331-3339. PMLR.
Ziegler, M., Stiennon, N., Wu, J., Brown, T. B., Radford, A., Amodei, D., Christiano, P., and Irving. G. (2019). Fine-tuning language models from human preferences. arXiv preprint arXiv:199.008593
15


Reviews:
[{"review_id": "23EgeaFdsZ", "reviewer": "Reviewer_aUcN", "summary": "This paper focuses on the sample complexity of learning robust MDPs under generative model access, with uncertainty sets measured with  TV and chi-squared divergences. The paper proposes tight upper and lower bounds for sample complexity under TV robustness and chi-squared robustness (under some range of the uncertainty radius). Curiously, the minimax bound is smaller than standard MDPs. The upper bound is attained by a model-based distributionally robust value iteration algorithm.\n\n(changed score from 4 -> 6 during discussion.)", "questions": "1. Which parts of the current analysis breaks when trying to extend to more general MDPs, like linear MDPs? \n2. I really like Figure 1, but I do not understand the intuition on why robust MDP is easier/harder in certain cases. I can certainly follow the algebra based on minimax optimal bounds, but can you describe at an intuitive level why this \"curious price\" appears?", "limitations": "See above.", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "1. The paper provides tight bounds for the TV case, and somewhat tight bounds for the chi-squared case, and illustrates the interesting phenomenon where the minimax optimal bounds are sometimes easier/harder than standard RL.", "weaknesses": "1. The presentation can be improved. For example, the algorithm box 1 is very bare and does not contain all the necessary details for implementation. Also, computational efficiency is a key issue in robust MDPs and the current version brushed it aside (in Line 221) into the appendix, which is 46 pages. It would be better to present it clearly in the main paper. Also, what makes this algorithm different from Yang et al, 2022? Is it just an improved analysis or something fundamentally changed in the algorithm to obtain minimax-optimal bounds? \n2. The robust VI algorithm seems not novel, as it is a common method for robust MDPs, eg. Iyengar 2005.\n3. While minimax-optimal theoretical results are nice, there is limited discussion on the practicality of the algorithm, besides its worst-case sample complexities.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank gratefully the reviewer for various valuable suggestions and the praise of our interesting findings!\n\n### 1. Questions about Algorithm 1 in Section 3.\nThanks for raising questions about algorithm 1. We shall address them as below:\n* **Improving the specification of Algorithm 1 and its computation efficiency.**\n The introduced Algorithm 1 in Section 3 --- robust value iteration (VI) is a well-known algorithm proposed by prior art [1], which is efficient with computation cost $O(S \\log(S))$ per iteration --- with only a modest increase compared to standard VI ($O(S)$). We shall introduce more details of the update rule and computation complexity in the main text to keep this paper self-consistent.\n* **Does this work propose a new algorithm?** The brief answer is no. We highlight that this work focuses on investigating the inherent difficulty of solving robust MDPs in terms of sample cost to provide a solid foundation for algorithm design. So we didn't propose new algorithms but concentrated on understanding existing ones, where we choose robust VI (Algorithm 1) as an example to develop sample complexity upper bound.\nWhile indeed, our statistical results can work for any model-based algorithms obeying certain conditions (can learn a policy $\\widehat{\\pi}$ obeying $\\|\\widehat{V}^{\\star, \\sigma} - \\widehat{V}^{\\widehat{\\pi}, \\sigma}\\|_\\infty \\leq \\varepsilon_1$ for small enough $\\varepsilon_1$) but not limited to Algorithm 1.\n* **Practicity of Algorithm 1.** We add new experiments to evaluate Algorithm 1 and demonstrate our theoretical findings (please check the **General response** for details). In addition, Algorithm 1 with TV uncertainty or $\\chi^2$ uncertainty set can be applied to more complex tasks and achieve robust performance when the testing environment deviates from the training one, such as Gambler’s problem and Frozen Lake environment in OpenAI Gym [3].\n\n### 2. Challenges of extending to general MDP like linear MDPs.\nWe believe the findings of current results in tabular cases lays a solid foundation to carry out general MDP cases with function approximation, e.g., the finding of using a simple divergence function such as TV may lead to less sample size requirement. While the entire pipeline in this work will need to adapt since general MDP cases (e.g., linear MDPs) will require distinct problem formulations --- still an open problem with few studies [2], algorithm design, and theoretical analysis framework --- requires more assumptions such as linearization for linear MDPs [4] and realizability/low-rank structure for general function approximation.\n\n### 3. Intuitions of why robust MDPs are easier or harder than standard MDPs in certain cases.\nThanks for liking our illustration in Figure 1. The difficulty of solving standard RL or robust RL is mainly determined by the following error terms. Given the same number of samples (same $\\widehat{P}^0$), a smaller error term means the task is easier.\n\n$\\text{Standard RL:} \\quad  \\quad \\delta\\_{\\text{RL}} = \\underset{ {\\color{blue}{\\bf \\text{  linear}}} \\text{ w.r.t. } P^0 - \\widehat{P}^0 }{\\underbrace{\\Big| P^0\\widehat{V} -\\widehat{P}^0\\widehat{V} \\Big|}}$\n\n$\\text{Robust RL:} \\quad  \\delta\\_{\\text{robust RL}}= \\underset{ {\\color{red}{\\bf \\text{complex form} }}  \\text{ w.r.t. } P^0 - \\widehat{P}^0 \\text{ due to inner problem over uncertainty set } \\mathcal{U}^\\sigma\\_\\rho(\\cdot)}{\\underbrace{ \\Big|\\inf\\_{\\mathcal{P}\\in \\mathcal{U}^\\sigma\\_\\rho\\left(P^0 \\right)} \\mathcal{P}\\widehat{V}\\_{\\text{rob}}- \\inf\\_{\\mathcal{P} \\in \\mathcal{U}^\\sigma\\_\\rho\\left(\\widehat{P}^0 \\right)} \\mathcal{P}\\widehat{V}\\_{\\text{rob}} \\Big|}}$\n\nThe error terms mainly depend on two factors: 1) the relationship w.r.t. the model estimate error $P^0 - \\widehat{P}^0$; 2) the range of the value function $\\widehat{V}$ or $\\widehat{V}_{\\text{rob}}$.\n* **Using TV uncertainty set: easier than standard RL.** In this case, the error term is shown to be $\\delta\\_{\\text{robust RL}} = \\Big| P^0\\widehat{V}\\_{\\text{rob}} -\\widehat{P}^0\\widehat{V}\\_{\\text{rob}} \\Big|$ that is also linear w.r.t. $P^0 - \\widehat{P}^0$ --- the same as standard RL. While the range of robust value function $\\widehat{V}\\_{\\text{rob}}$ in robust RL decrease rapidly and becomes smaller than the range of $\\widehat{V}$ in standard RL, since the values in all states are pushed toward the minimum one and become close to each other. As a result, the error term of robust RL $\\delta_{\\text{robust RL}}$ becomes smaller than standard RL $\\delta_{\\text{RL}}$ as $\\sigma$ grows, i.e., robust RL becomes easier than standard RL.\n* **Using $\\chi^2$ uncertainty set: can be harder than standard RL.** In this case, the error term of robust RL $\\delta_{\\text{robust RL}}$ is non-linear w.r.t. and sensitive to model estimate error $P^0 - \\widehat{P}^0$, which can induce large error term even if $P^0 - \\widehat{P}^0$ is small, especially when $\\sigma$ is large (e.g., $\\sigma > O(\\frac{1}{1-\\gamma})$). Standard RL has an error term that is linear to $P^0 - \\widehat{P}^0$, while the error term of robust RL may explode even $P^0 - \\widehat{P}^0$ is small, namely, robust RL becomes much harder than standard RL.\n\n\n\n\n\n    \n> [1] Iyengar, G. N. (2005). Robust dynamic programming. Mathematics of Operations Research, 368 30(2):257–280. \\\n[2] Ma, Xiaoteng, et al. \"Distributionally robust offline reinforcement learning with linear function approximation.\" arXiv preprint arXiv:2209.06620 (2022). \\\n[3] Panaganti, Kishan, and Dileep Kalathil. \"Sample complexity of robust reinforcement learning with a generative model.\" International Conference on Artificial Intelligence and Statistics. PMLR, 2022. \\\n[4] Jin, Chi, et al. \"Provably efficient reinforcement learning with linear function approximation.\" Conference on Learning Theory. PMLR, 2020."}, {"review_id": "2950v4kXYs", "reviewer": "Reviewer_ZjPC", "summary": "This paper presents new upper and lower bounds for distributionally robust MDPs where the uncertainty set for the transition kernel is specified as a ball with $\\chi^{2}$ divergence or total variation as the distance measure. The bounds significantly improve previous results. \n", "questions": "I would appreciate responses to the points regarding the bounds in Weaknesses.", "limitations": "The paper didn't discuss the limitations. I believe the paper should at least point out that the results do not hold for all $\\gamma$ values and provide a discussion on this.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper is generally well-written, and is easy and interesting to read. The results significantly improve existing bounds and are surprising. However, I didn't read the proofs.\n", "weaknesses": "* The notations $\\lesssim$ and $\\asymp$ should be defined. While $\\lesssim$ is often used in many places, it seems it should be just $\\le$ or $<$ according to the theorems.\n* The distributionally robust value iteration algorithm is taken from (Yang et al., 2022; Iyengar, 2005), but Section 3 describes the algorithm as if this is a contribution from this paper.\n* The bounds usually do not hold for all $\\gamma \\in (0, 1)$, thus there are still some gaps in the results, while the paper did not make this clear.  An intuitive discussion on why the results do not hold for $\\gamma$ values outside the ranges given in the theorems are helpful.\n* I find the statements of Theorem 2 and Theorem 4 unclear. A sample complexity lower bound result should show that no algorithm can solve a problem given fewer than a certain number of samples. However, these theorems do not mention algorithms, but instead mention two robust MDPs and take infimum with respect to the random policy $\\hat{\\pi}$. Did I miss something?\n* I find the lower bound in Theorem 4 very surprising, as the lower bound is discontinuous and non-monotonic. I note that the paper claim the bounds are at least nearly tight, but is it possible that the lower bounds are not sufficiently tight? Can an intuitive explanation for the discontinuity and non-monotonicity be given?\n* There are some discussions on whether uncertainty of the transition kernel makes learning a $\\epsilon$-optimal value function harder, and the discussion is based on comparison of sample complexity lower bounds for robust MDPs and standard MDPs. However, this may be misleading as the lower bounds can be underestimating the complexity of a problem.\n* The appendix has some broken references (??).\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to express our gratitude to the reviewer for their insightful feedback and valuable comments.\n\n\n\n\n\n### 1. The range of the discounted factor $\\gamma$ that is considered in our theorems.\nRecall that the discounted factor $\\gamma$ determines the effective horizon length $\\frac{1}{1-\\gamma}$ of RL tasks, i.e., larger $\\gamma$ leads to tasks with longer horizons.\n* **We consider the entire reasonable range.** We would like to highlight that the main feature and challenge of RL tasks is the **sequential** structure. So when $\\gamma$ is small (e.g., $\\gamma \\in (0, \\frac{1}{2}]$ leads to the effective horizon length is at most $2$), the sequential structure almost disappears and is of much less interest for RL community. So people usually focus on reasonable range $\\gamma \\in (c, 1)$ for some small positive constant $c$ [1][2], such as $\\gamma \\in [\\frac{1}{2},1)$. The situations when $\\gamma\\in (0, c]$ are generally not paid attention by the RL community.\n* **Our results can be directly extended to a broader range of $\\gamma$.**  Recall that all of our four theorems at least hold for $\\gamma \\in (\\frac{3}{4}, 1)$. The theorems can be directly extended to a broader range of $\\gamma \\in  (c, 1)$ along with $c$ as small as desired so that almost cover the full range $(0,1)$.\n \n\n### 2. Improving the statement of Theorem 2 and 4.\nThe reviewer is correct that the lower bound means that no algorithm (estimator) can achieve the desired accuracy, given the sample size that is fewer than a certain number. So $\\hat{\\pi}$ in Theorem 2 and 4 does not represent a random policy, but represents the output of any algorithm (estimator). We will definitely improve the statement and make the definition of $\\hat{\\pi}$ more clear.\n\n### 3. More explanation of the lower bound in Theorem 4.\nThanks for being interested in our results.\n* **A nearly tight lower bound.** The lower bound is nearly tight regarding that: 1) it is tight at least for a certain range of uncertainty levels (when $\\sigma \\in O(1)$), since it matches with the upper bound in Theorem 3 which verifies that the lower bound in this range can't be improved anymore. In addition, the lower bound nearly matches with the upper bound up to the term about $\\gamma$ when $\\sigma \\gtrsim O(\\frac{1}{1-\\gamma})$. The reviewer can refer to Figure 1(b) for illustration.\nWhile in other cases of $\\sigma$, the reviewer is right that the lower bound may not be tight enough, which we leave to future work.\n* **Intuition of the non-monotonicity shape.** We highlight that as the uncertainty level $\\sigma$ varies, the sample requirement may have different behaviors due to uncertainty set changing--- which is an important message from this work. However, we agree with the reviewer that the non-monotonicity is counterintuitive and may can be improved. Although we significantly improve the prior lower bound, we believe there may exist a gap towards the optimal one. The gap may be due to we construct the same set of hard instances (RMDPs) when $\\sigma$ varies. While for different $\\sigma$, distinct hard instances may be required to achieve tighter lower bound --- need specific designs.\n\n### 4. Comparing the difficulty of robust RL and standard RL in terms of sample requirement --- only based on lower bound?\nWe compare the difficulty of robust and standard RL by comprehensively summarizing the information of both lower bounds and upper bounds. Specifically, the sample complexity of standard RL was settled as $\\widetilde{O}\\left(\\frac{SA}{(1-\\gamma)^3\\varepsilon^2} \\right)$ by the matched lower bound and upper bound [3].\n\nThe messages in this work are: 1) robust MDPs are easier to learn than standard MDPs under the TV distance. We arrive at this conclusion by settling down the sample complexity of robust MDPs with as $\\widetilde{O} \\left( \\frac{SA}{(1-\\gamma)^2\\varepsilon^2} \\min \\left\\\\{ \\frac{1}{1-\\gamma}, \\frac{1}{\\sigma} \\right\\\\} \\right)$ through showing the matched lower bound (Theorem 2) and upper bound (Theorem 1); 2) robust MDPs can be harder to learn than standard MDPs under the $\\chi^2$ divergence. This claim is reasonable since the derived sample complexity lower bound for robust MDPs (Theorem 4) already exceeds the sample complexity of standard MDPs, at least for a certain range of uncertainty levels (see Figure 1(b)). Although the lower bound in Theorem 4 may not be sufficiently tight, it already shows that robust MDPs can be harder than standard MDPs.\n\n### 5. Improving clarity and writing.\nThanks for the careful review and valuable suggestions.\n* **Confusion of Section 3.** The reviewer is correct that we didn't propose a new algorithm but concentrated on understanding existing methods. We shall definitely highlight that Algorithm 1 in Section 3 was proposed by [4] and is just an example. While indeed, our sample complexity upper bound can work for any model-based algorithms obeying certain conditions (can learn a policy $\\widehat{\\pi}$ obeying $\\|\\widehat{V}^{\\star, \\sigma} - \\widehat{V}^{\\widehat{\\pi}, \\sigma}\\|_\\infty \\leq \\varepsilon_1$ for small enough $\\varepsilon_1$) but not limited to Algorithm 1.\n* **Notation and definitions of $\\lesssim, \\asymp$.** We add clarification for these notations in the main text.\n* **Typos in the appendix.** We fixed the typos mentioned by the reviewers and have polished the main text and appendix again.\n\n\n> [1]  Li, Gen, et al. \"Settling the sample complexity of model-based offline reinforcement learning.\" arXiv preprint arXiv:2204.05275 (2022). \\\n[2]    Yan, Yuling, et al. \"The efficacy of pessimism in asynchronous Q-learning.\" IEEE Transactions on Information Theory (2023). \\\n[3] Li, Gen, et al. \"Breaking the sample size barrier in model-based reinforcement learning with a generative model.\" Advances in neural information processing systems 33 (2020): 12861-12872. \\\n[4] Iyengar, G. N. (2005). Robust dynamic programming. Mathematics of Operations Research, 368 30(2):257–280."}, {"review_id": "ENybtgl8xY", "reviewer": "Reviewer_fPn4", "summary": "The research primarily focuses on the robust Markov Decision Process setting, where the objective is to learn a robust policy with the uncertainty set being measured by f-divergences using a model-based algorithm. One of the key idea of the paper lies in deriving precise sample complexity bounds for the same with access to the generative model and shows that RMDPs is not necessarily more difficult than standard MDPs, which is an important finding in general.", "questions": "1. In Theorem 1, when $\\sigma > 1- \\gamma$, the sample complexity of RMDPs becomes smaller than MDP. However, when we increase the size of the uncertainty set, indicates we are more unsure of the transition and can come from a larger radius around the nominal. Shouldn't we need more samples in this case, why is considering the total variation causing the reverse? This is critical and will be helpful to have a detailed discussion.\n2. The author compares the sample-complexity results of RMDPs with standard MDP which is interesting and important. However, the result(Th 1) holds for $\\epsilon \\in [0, \\frac{k_0}{1 - \\gamma}$. However, in Agarwal et.al, they also show the sample complexity is $O(S^2 A)$ when $\\epsilon^2 \\geq \\frac{1}{k. (1-\\gamma)^3}$ i.e. in regimes where no meaningfully accurate approximation to the actual transition probabilities can be constructed. It will be in\n3. The authors have mentioned the geometry of the uncertainty set in connection to $\\sigma$, but how is the geometry defined and what the geometry of the set refers to is not explicitly mentioned. What exactly does the geometry of the set refer to? Does it just refer to the shape owing to the type of divergence and size corresponding to the radius? Or there are further detailed connections drawn to the geometry?\n4. Although the research closes the gap b/w the upper and lower bounds with more precise bounds, the generative model assumption, in general, is restrictive, and one of the major hardness for model-based RL is to approximate the transition model which is hard.\n\n#Minor Comment\nIn several places, the citation and references were not coming properly, especially in the Appendix (Lines 663, 689, 692, 701, 800, 801, 1079), which makes it a little unsmooth to follow.", "limitations": "Some of the future and potential research directions are mentioned in the discussion, which I feel is sufficient. ", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "One of the primary challenges in the field of Robust MDPs in general lies in the selection of the uncertainty set and shape and size of the uncertainty set, and the past literature has assumed certain structures around the same specifically (s,a) rectangularity to solve the robust MDP problem.  The paper provides a detailed study of the effect of uncertainty set on the robust MDP and the sample complexity analysis. A primary contribution of the paper lies in reducing the significant gap between the upper and lower bounds of past literature with different f-divergences. A standard formulation in robust MDP deals with defining the uncertainty-set $U_{\\rho}^{\\sigma}(P^0)$ with a divergence $\\rho$ and radius $\\sigma$ around the nominal transition kernel following the (s,a) rectangularity condition and solving the robust Value iteration. Although the robust value iteration is hard to solve in general, the dual of the problem is reasonably simple and can be applied due to the strong duality condition. With this, the authors develop distributionally robust value iteration and improved the upper bounds for RMDPs with various f-divergences. The Theorems also highlight the sample complexity over the entire range of the uncertainty level and how the geometry of the uncertainty set can affect the sample complexity analysis of RMDPs. Overall the paper is clearly written, with detailed analysis, and also provides the theory and proofs of earlier results as required, which I found very helpful. \n\n\n\n", "weaknesses": "1. In the statement of Theorem 1, where the relation of RMDP's sample complexity with the standard MDP is discussed, it states when $\\sigma \\leq 1 -\\gamma$, the sample complexity is almost similar to MDP which makes sense since for smaller $\\sigma$ means eventually we are optimizing just over the nominal $P^0$. However, the other result shows that when $\\sigma > 1- \\gamma$, the sample complexity of RMDPs becomes smaller than MDP, which is not very intuitive. When the uncertainty set over which the robust optimization is performed, when we increase the size of the set ideally the complexity should increase. Hence, it is not very clear what is the intuition of this result and is not explicitly stated here. Why the shape of the uncertainty set with TV can produce a better complexity analysis is not absolutely clear and intuitive.\n2. The authors propose a distributionally robust value iteration algorithm (Algorithm 1) which is resulting in an improved analysis. However, the novelty of the proposed algorithm is not very clear as robust value iteration and solving the robust problem with Wasserstein divergence have been there long before. It will be critical to specifically highlight the novel aspects of the algorithm and which component is causing the improvement in the analysis.\n3. The papers lack any experimental study to verify the theoretical claims for the proposed algorithm. It will be helpful if the authors can provide simple experimental evaluations or ablations on some vanilla RL environments, and how the proposed algorithm is achieving the improvements over prior in terms of sample complexity. That will make the intuition of the improvement in the algorithm very clear.\n4. It is mentioned the distribution shift issue for RMDPs when the transition kernel drawn from the uncertainty set can be different from the nominal kernel. However, it's not clear whether it is addressed by the current algorithm and how? Also, won't this issue be increased when the size of the uncertainty set is large requiring more samples, which seems opposite to what it is shown in Theorem 1? It also needs further clarity.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the reviewer for the comprehensive feedback and recognize the significance of our contributions.\n\n### 1. The intuition of why robust RL with TV uncertainty is easier than standard RL.\nThe intuition is kind of the opposite --- as the uncertainty level $\\sigma$ increases, fewer samples are needed to achieve a desired policy with a certain accuracy. This intuition is not limited to TV, but also any $\\ell_p$ norm, even other uncertainty divergence functions. Specifically, recall the goal of robust RL is to find a policy $\\pi$ whose performance is close to the robust optimal policy, i.e., $V^{\\star,\\sigma}(s) - V^{\\pi,\\sigma}(s) \\leq \\varepsilon$. As the uncertainty level increases, the performance gap between the optimal policy and any policy decreases rapidly, given that no policy can significantly outperform others when the environment may vary substantially. Consequently, only a small number of samples are required to reach the desired accuracy since the potential for improvement is minimal. \n\n### 2. Clarification of the algorithm novelty in Section 3.\n* **We focus on statistical understanding of existing methods.** We didn't propose a new algorithm. Algorithm 1 in Section 3 is a well-known algorithm [1] for robust RL that we show here to keep this paper self-consistent. We highlight that this work focuses on studying the inherent difficulty of robust MDPs in terms of sample cost to provide a solid foundation for algorithm design. So we take Algorithm 1 as an example. Our statistical results can work for any model-based algorithms obeying certain conditions (can achieve a policy $\\widehat{\\pi}$ obeying $\\|\\widehat{V}^{\\star, \\sigma} - \\widehat{V}^{\\widehat{\\pi}, \\sigma}\\|_\\infty \\leq \\varepsilon_1$ for small enough $\\varepsilon_1$) but not limited to Algorithm 1.\n* **Wasserstein uncertainty set.** We concur that Wasserstein distance is also an option for the uncertainty set, but it's relatively new in robust RL [2]. Investigating Wasserstein sets based on our findings presents an interesting direction.\n\n### 3. New experiments to verify the theoretical claims for the proposed algorithm.\nWe add new numerical experiments to verify the theoretical findings of the proposed algorithm as the reviewer suggested. Please refer to **General response** and uploaded **PDF** for details.\n\n\n### 4. How Algorithm 1 addresses the uncertainty issue.\nTo address the uncertainty that the transition kernel $\\mathcal{P}$ may perturbs from the (estimated) nominal kernel $\\widehat{P}^{0}$ inside the set $\\mathcal{U}^\\sigma(\\widehat{P}^{0})$, each value iteration step in Algorithm 1 involves an additional infimum operator over $\\mathcal{U}^\\sigma(\\widehat{P}^{0})$ as below (line 5 of Algorithm 1):\n$$\\widehat{Q}\\_t = r + \\gamma \\inf\\_{ \\mathcal{P} \\in \\mathcal{U}^\\sigma(\\widehat{P}^{0})}  \\mathcal{P} \\widehat{V}\\_{t-1}.$$ In words, Algorithm 1 addresses the uncertainty by considering the worst case performance when the transition kernel is arbitrarily drawn in the uncertainty set $\\mathcal{U}^\\sigma(\\widehat{P}^{0})$. And in addition, there won't be an issue when the uncertainty set size increases with $\\sigma$ since Algorithm 1 knows the size ($\\sigma$) and will solve the corresponding problem based on the size.\n\n### 5. Discussion about the range of $\\varepsilon$ in Theorem 1\nTheorem 1 in this work holds for a large range of accuracy level when $\\varepsilon \\in \\left(0, \\sqrt{1/\\max\\{1-\\gamma, \\sigma\\}} \\right]$. We leave the extension to full range as future work. Note that such extension is non-trivial that may require additional technical tools, such as [4] extend the range $\\varepsilon \\in \\left(0, \\sqrt{1/1-\\gamma} \\right]$ in [3] (the one reviewer mentioned) to full range in standard RL case.\n\n### 6. Improving the specification.\n* **The uncertainty set geometry.** The formal definition of the uncertainty set is shown in Equation (3):\n$$\\mathcal{U}\\_\\rho^{\\sigma}(P^0) := \\otimes \\; \\mathcal{U}\\_\\rho^{\\sigma}(P^0\\_{s,a})\\qquad \\text{with}\\quad\n\t\\mathcal{U}\\_\\rho^{\\sigma}(P^0\\_{s,a}) := \\left\\\\{ P\\_{s,a} \\in \\Delta (\\mathcal{S}): \\rho \\left(P\\_{s,a}, P^0\\_{s,a}\\right) \\leq \\sigma \\right\\\\}.$$So the geometry of the uncertainty set (can be seen as a ball) is determined by two factor: 1) the divergence function $\\rho(\\cdot)$ which determine the 'distance' between two distribution point; 2) uncertainty level $\\sigma$ that represents the radius of the uncertainty ball.\n* **Polishing the appendix.** We revise all the typos that the reviewer mentioned and polish the paper again.\n\n### 7. Discussing the limitation of the generative model setting and model-based algorithms\n* **Generative model setting is a good starting point.** We believe understanding robust RL in the fundamental generative model setting is highly nontrivial and plays an essential role in shaping the theoretical foundation of robust RL, where all prior analyses still fail to give a clear message. Theoretical underpinnings in this setting are critically needed before addressing more complex cases, e.g., online/offline robust RL.\n* **Limitation of model-based RL.** We believe our work lays a solid foundation to design and understand the counterpart of model-based RL --- model-free RL which does not require estimating the model explicitly.\n\n> [1] Iyengar, G. N. (2005). Robust dynamic programming. Mathematics of Operations Research, 368 30(2):257–280.    \n[2] Xu, Zaiyan, Kishan Panaganti, and Dileep Kalathil. \"Improved sample complexity bounds for distributionally robust reinforcement learning.\" International Conference on Artificial Intelligence and Statistics. PMLR, 2023.\\\n    [3] Agarwal, Alekh, Sham Kakade, and Lin F. Yang. \"Model-based reinforcement learning with a generative model is minimax optimal.\" Conference on Learning Theory. PMLR, 2020.\\\n    [4] Li, Gen, et al. \"Breaking the sample size barrier in model-based reinforcement learning with a generative model.\" Advances in neural information processing systems 33 (2020): 12861-12872."}, {"review_id": "Xumi17vxzM", "reviewer": "Reviewer_wpEG", "summary": "1. This paper studies the model robustness in RL via the framework of distributionally robust MDP.  \n2. The authors derive the sample complexity of RMDPs using a model-based algorithm called distributionally robust value iteration when the uncertainty set is measured via either total variation or chi square divergence. \n3. The lower bounds are developed to benchmark its tightness\n4. A interesting insight from this paper is that the required sample complexity of RMDPs can be higher or lower than the standard MDP based on the choice of uncertainty measurement. ", "questions": "What is the intuition / theoretical explanation that whether RMDPs are not harder nor easier than standard MDPs highly depends on both the size and shape of the uncertainty set? \n", "limitations": "N/A", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "1. Nolvety: the improvement of the upper and lower bounds over the existing work is not easy, new techniques are developed.\n2. Presentation is very clear, especially the summarizations in Tables 1-2 and the illustrations in Figure 1\n3. The insights from theoretical results are interesting: RMDPs can be harder than standard MDPs under the chi square distance but can be easier than standard MDPs under the TV distance.\n", "weaknesses": "1. It is better to add experiments to empirically demonstrate the theoretical results in the paper.\n2. It is better to add a discussion on how the theoretical results in this paper could help the practitioners. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the reviewer for careful review and insightful feedback. It is rewarding to know that the reviewer recognizes the significance of our contributions --- the new techniques and interesting takeaway message. In what follows, we provide our response to the reviewer's comments.\n\n### 1. Experimentally demonstrate the theoretical results\nThanks for the insightful suggestion. We have conducted new numerical experiments to demonstrate and verify the theoretical findings as the reviewer suggested. Please refer to **General response** and uploaded **PDF** for details.\n\n\n\n### 2. Adding discussion of how the results can help practitioners\nThanks for the valuable suggestion. We shall add the discussion in the main text:\nThe findings motivate the practitioners to:\n* **Design robust RL algorithms since robustness may be a free lunch.** The results show that promoting additional robustness in RL algorithms does not necessarily harder than standard RL in terms of sample requirement. So we can take this free lunch to have robustness property for RL algorithms.\n* **Design the uncertainty set carefully.** The results show that the statistical difficulty of robust RL heavily depends on the shape and size of the prescribed uncertainty set. So we need to carefully design the uncertainty set: 1) shape: the results for TV uncertainty show that using simple or linear divergence function such as $\\ell_p$ norm (including TV) may be easier than other divergence functions and leads to less sample requirement; 2) size: the results for $\\chi^2$ uncertainty indicate that we should not choose too large uncertainty set, which both induce over-conservative algorithm and sample inefficiency (seen from the exploded sample requirement as $\\sigma$ increasing).\n\n\n### 3. Explanation of why RMDPs are not necessarily harder nor easier than standard MDPs --- depends on both the shape and size of the uncertainty set.\nThanks for raising this insightful question. We would be happy to provide more explanation. The difficulty of solving standard RL or robust RL is mainly determined by the following error terms. Given the same number of samples (same $\\widehat{P}^0$), a smaller error term means the task is easier.\n\n$\\text{Standard RL:} \\quad  \\quad \\delta\\_{\\text{RL}} = \\underset{ {\\color{blue}{\\bf \\text{  linear}}} \\text{ w.r.t. } P^0 - \\widehat{P}^0 }{\\underbrace{\\Big| P^0\\widehat{V} -\\widehat{P}^0\\widehat{V} \\Big|}}$\n\n$\\text{Robust RL:} \\quad  \\delta\\_{\\text{robust RL}}= \\underset{ {\\color{red}{\\bf \\text{complex form} }}  \\text{ w.r.t. } P^0 - \\widehat{P}^0 \\text{ due to inner problem over uncertainty set } \\mathcal{U}^\\sigma\\_\\rho(\\cdot)}{\\underbrace{ \\Big|\\inf\\_{\\mathcal{P}\\in \\mathcal{U}^\\sigma\\_\\rho\\left(P^0 \\right)} \\mathcal{P}\\widehat{V}\\_{\\text{rob}}- \\inf\\_{\\mathcal{P} \\in \\mathcal{U}^\\sigma\\_\\rho\\left(\\widehat{P}^0 \\right)} \\mathcal{P}\\widehat{V}\\_{\\text{rob}} \\Big|}}$\n\nThe error terms mainly depend on two factors: 1) the relationship w.r.t. the model estimate error $P^0 - \\widehat{P}^0$; 2) the range of the value function $\\widehat{V}$ or $\\widehat{V}_{\\text{rob}}$.\n\n**Briefly, both the shape and size of the uncertainty set influence the error term and thus determine the difficulty of robust RL problems with certain sample size:** 1) using different uncertainty shapes will lead to either simple relationship (TV) or complex relationship ($\\chi^2$) w.r.t $P^0 - \\widehat{P}^0$； 2）different size determined by $\\sigma$ will lead to different range of robust value function $\\widehat{V}_{\\text{rob}}$. \nMore specifically, we show how the shape and size determine the statistical difficulty of robust RL for TV or $\\chi^2$ uncertainty set, respectively:\n* **Using TV uncertainty set: easier than standard RL.** In this case, the error term is shown to be $\\delta\\_{\\text{robust RL}} = \\Big| P^0\\widehat{V}\\_{\\text{rob}} -\\widehat{P}^0\\widehat{V}\\_{\\text{rob}} \\Big|$ (determined by the TV uncertainty shape) that is also linear w.r.t. $P^0 - \\widehat{P}^0$ --- the same as standard RL. While the range of robust value function $\\widehat{V}\\_{\\text{rob}}$ in robust RL can reduce rapidly (as the size $\\sigma$ increases) and becomes smaller than the range of $\\widehat{V}$ in standard RL, since the values in all states are pushed toward the minimum one and become close to each other. As a result, the error term of robust RL $\\delta\\_{\\text{robust RL}}$ is equal to or smaller than standard RL $\\delta_{\\text{RL}}$ when trained with the same size of samples, i.e., robust RL becomes easier than standard RL.\n* **Using $\\chi^2$ uncertainty set: can be harder than standard RL.** In this case, the error term of robust RL $\\delta_{\\text{robust RL}}$ is non-linear w.r.t. and sensitive to model estimate error $P^0 - \\widehat{P}^0$ (determined by the $\\chi^2$ uncertainty shape), which leads to a large error term even if $P^0 - \\widehat{P}^0$ is small, especially when $\\sigma$ is large (e.g., $\\sigma > O(\\frac{1}{1-\\gamma})$). So when using the same size of samples --- same $P^0 - \\widehat{P}^0$, standard RL has an error term that is linear to $P^0 - \\widehat{P}^0$, while the error term of robust RL may explode, namely, robust RL becomes much harder than standard RL."}, {"review_id": "T0wXTKLEvz", "reviewer": "Reviewer_Pv5G", "summary": "This paper studies the statistical nature of distributionally robust reinforcement learning under the generative model. Specifically, it studies two divergences, total variation or chi-square divergence, over the full range of uncertainty levels. The paper improves the upper and lower bounds, especially when the uncertainty levels are small. Based on these results, the paper partially answers the question of whether distributionally robust RL is harder to learn compared to the non-robust counterpart.", "questions": "Can the authors briefly explain the current challenges in giving parallel results under the KL divergence?", "limitations": "See weakness.", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "The paper's theoretical results are both interesting and important in understanding the statistical limits of distributionally robust RL. The paper gives a complete story in the TV divergence and chi-square divergence.", "weaknesses": "A brief explanation of the reason for the improvements in both the upper and lower bounds, compared to the previous technique, would significantly help readers better understand the technical contributions of this paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We extend our thanks to the reviewer for their meticulous review and perceptive insights regarding future directions. It is gratifying to know that the reviewer found our results both interesting and important. In what follows, we provide our response to the reviewer's comments.\n\n### 1. Adding discussion on the technical contribution for improving both the upper and lower bounds.\nThanks for this valuable suggestion. We shall highlight the following discussion in the introduction.\n* **Technical contribution to improving upper bound.** Achieving the tighter upper bound for TV and $\\chi^2$ uncertainty set requires different technical tools. For TV uncertainty set, the key part that pins down the sample complexity to be better than standard RL is a carefully derived tighter bound for the range of the robust value function (i.e., Lemma 7). For $\\chi^2$ uncertainty set, we improve the existing sample complexity with a quadratic dependency on the state space $S$ to a linear one through 1) the property of the dual equivalence in Lemma 5; 2) the leave-one-out technique to decouple statistical dependency inspired by [3][4]. \n* **Technical contribution to improving lower bound.** To achieve a much tighter lower bound compared to prior work [1], we construct new hard instances (RMDPs) illustrated in Figure 2(a) of the uploaded **PDF**, which are different from the ones that are usually used in standard RL [2] and prior art [1] of robust RL. The new instances are inspired by the asymmetric structure of RMDPs induced by the additional infimum operator in the robust value function, which are tailored based on the uncertainty level $\\sigma$. Please refer to Appendix D and F for more details.\n\n### 2. The challenges of extending to the KL divergence case.\nThanks for raising this insightful question. Extending the current results to KL divergence is definitely of great interest. For the lower bound, it is promising to use the hard instance construction approach in this work to improve the lower bound of the existing work [5] about KL divergence, while the main challenge is that the calculation of KL case is much more complicated since it is more non-linear than both TV and $\\chi^2$ and thus require careful design. To improve the upper bound in KL divergence case, we may need to carefully control the bound for the dual parameter --- which is now the bottleneck to achieve minimax-optimal sample complexity with respect to the effective horizon length $\\frac{1}{1-\\gamma}$. In summary, extending the results to KL divergence is promising but may need additional specific techniques.\n\n    [1] Yang, Wenhao, Liangyu Zhang, and Zhihua Zhang. \"Toward theoretical understandings of robust Markov decision processes: Sample complexity and asymptotics.\" The Annals of Statistics 50.6 (2022): 3223-3248.\n    [2] Gheshlaghi Azar, Mohammad, Rémi Munos, and Hilbert J. Kappen. \"Minimax PAC bounds on the sample complexity of reinforcement learning with a generative model.\" Machine learning 91 (2013): 325-349.\n    [3] Agarwal, Alekh, Sham Kakade, and Lin F. Yang. \"Model-based reinforcement learning with a generative model is minimax optimal.\" Conference on Learning Theory. PMLR, 2020.\n    [4] Li, Gen, et al. \"Breaking the sample size barrier in model-based reinforcement learning with a generative model.\" Advances in neural information processing systems 33 (2020): 12861-12872.\n    [5] Shi, Laixi, and Yuejie Chi. \"Distributionally robust model-based offline reinforcement learning with near-optimal sample complexity.\" arXiv preprint arXiv:2208.05767 (2022)."}]

Author rebuttal:
We thank the reviewers for their careful reading of the paper and their insightful and valuable feedback. Below we provide some new numerical results to corroborate the theoretical findings in this work.

### New numerical results
As reviewers suggested, we add new experiments to corroborate and demonstrate the theoretical findings in this paper:



* **Experimental settings.** We demonstrate the sample size requirements in robust RL when the uncertainty level $\sigma$ varies. Specifically, we evaluate robust value iteration (Algorithm 1) in the following robust MDP $\mathcal{M}_\phi= \left(\mathcal{S}, \mathcal{A}, P^0, r, \gamma \right)$ illustrated in the uploaded **PDF Figure 2(a)**, where $\gamma$ is the discount parameter, $\mathcal{S} = \{0, 1\}$, $\mathcal{A} = \{0, 1\}$, nominal transition kernel $P^0$ obeys $P^0(1|1,0) = P^0(1|1,1) =1, P^0(1|0,0) =p, P^0(1|0,1) =q$, reward $r(0,0) = r(0,1) =0, r(1,0) = r(1,1) = 1$. Denote N as the sample size per state-action pair. For each point $(N, \gamma, \sigma)$, we conduct 100 Monte Carlo simulations and claim $N$ successfully attain $\varepsilon$ accuracy if the accuracy is achieved at least $95$ times. 
* **Results with TV uncertainty set.** For TV uncertainty set, we focus on the effect of the discount complexity $\frac{1}{1-\gamma}$, which dominates the difference of robust RL compared to standard RL (see Figure 1(a)). We set $p = 2 \max(1-\gamma, \sigma)$, and $q = p - 16(1-\gamma)\max(1-\gamma, \sigma)\varepsilon$ inspired by our lower bound, and fix $\varepsilon= 0.13$ (a randomly chosen small value). The results in **PDF Figure 2(b)** show that the numerical sample complexity per state-action pair $N$ scales on the order of $\frac{1}{(1-\gamma)^3}$ when the uncertainty level is small ($\sigma = 0.005$), while on the order of  $\frac{1}{(1-\gamma)^2}$ when the uncertainty level is large ($\sigma = 0.3$). The results match the derived sample requirements illustrated in Figure 1.
* **Results with $\chi^2$ uncertainty set.** For $\chi^2$ uncertainty set, we focus on the effect of $\sigma$ especially when $\sigma$ is very large, since the exploded sample requirement as $\sigma$ increases is a key finding. We set $q = \frac{\sigma}{1+\sigma}$, $p = q + \frac{8}{3(1+\sigma)}\varepsilon$, and fix $\varepsilon= 0.13$ and $\gamma = 0.9$. **PDF Figure 2(c)** demonstrates that the required sample complexity increases linearly w.r.t. the uncertainty level $\sigma$ when $\sigma$ is large (in the range $(\frac{1}{1-\gamma},\infty)$), which matches our theoretical findings (see Figure 1).


We would be grateful if the reviewers could take a look at the responses and consider raising support for this work if we have addressed your concerns adequately. We would be glad to discuss further if there are additional concerns.

Meta-review: After discussion, reviewers all agree that that paper's new result on robust MDP is a good contribution, and the paper should be accepted.
Decision: Accept (poster)