Policy Gradient for Rectangular Robust Markov Decision Processes
Authors: Navdeep Kumar
Esther Derman
Matthieu Geist
Kfir Yehuda Levy
Shie Mannor
Venue: NeurIPS 2023 poster (2023)
Keywords: robust Markov decision process
policy gradient
TL;DR: We introduce RPG a policy gradient method that solves rectangular robust Markov decision processes with similar time complexity as non-robust policy-gradient.

Abstract: Policy gradient methods have become a standard for training reinforcement learning agents in a scalable and efficient manner. However, they do not account for transition uncertainty, whereas learning robust policies can be computationally expensive. In this paper, we introduce robust policy gradient (RPG), a policy-based method that efficiently solves rectangular robust Markov decision processes (MDPs). We provide a closed-form expression for the worst occupation measure. Incidentally, we find that the worst kernel is a rank-one perturbation of the nominal. Combining the worst occupation measure with a robust Q-value estimation yields an explicit form of the robust gradient. Our resulting RPG can be estimated from data with the same time complexity as its non-robust equivalent. Hence, it relieves the computational burden of convex optimization problems required for training robust policies by current policy gradient approaches.

Policy Gradient for Rectangular Robust Markov Decision Processes
Navdeep Kumar* Technion
Esther Derman
MILA, Université de Montréal
Matthieu Geist Goodle Deepmind
Kfir Levy Technion
Shie Mannor
Technion, NVIDIA Research
Abstract
Policy gradient methods have become standard for training reinforcement learning agents in a scalable and efficient manner. However, they do not account for transition uncertainty, whereas learning robust policies can be computationally expensive. In this paper, we introduce robust policy gradient (RPG), a policy- based method that efficiently solves rectangular robust Markov decision processes (MDPs). We provide a closed-for forommffommmmmooooooo expression for the worst occupation measure. Incidentally, find that the worst kernel is rank-one perturbation of the nominal. Combining the worst occupation measure with a robust Q-value estimation yields explicit form of the robust gradient. Our resulting RPG can be estimated from data with the same time complexity as its non-robust equivalent. Hence, relieves the computational burden of convex optimization problems required for training robust policies by current policy gradient approaches.
Introduction
Markov decision processes (MDPs) provide analytical framework to solve sequential decision- making problems and seek the best performance in fixed environment. Since the resulting policy can be highly sensitive parameter values (18), the robust MDP setting alternatively maximizes return under the worst scenario, thus yielding robustness to uncertain environments 20 [2].
practice, the robust MDP paradigm quantifies the level of uncertainty through set 2/ determining the possible range of model perturbations. Then, policy is said to be robust-optimal if reaches maximal perfor- mance under the most adversarial model within the uncertainty set. Developing efficient solvers for robust MDPs is of great interest, as it can lead to behavior policies with generalization guarantees (34).
If not computationally expensive, robust MDPs can be strongly NP-hard tractability, we commonly assume that 2/ is convex and s-rectangular, i.e., 2
33 Thus, to preserve
sl, 20 12 331
10 28 the latter as- sumption means that the overall uncertainty should be designed independently for each state. Further simplification may consider (s, a) rertttnaga uncertainty sets of the form L/ ((.0)ExX((s..)) albeit this naturally leads to more conservative strategies. In any case, planning in robust MDPs can be com- putationally costly, as it involves successive max-min problems
Well established in the robust reinforcement learning (RL) literature 8 3
( 1 [33] To address this issue, the works B. [4] have established an equivalence between robustness and regularization RL order to derive efficient robust planning methods for and (s, rerctannga robust MDPs. Indeed, it appears that resorting to proper regularization instead of solving minimization problem can yield robust behavior without requiring the polynomial time complexity of convex optimization problems [3.
"Contact author Savdeepkuuar@camppe wechnion.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Alternatively to planning, policy gradient algorithms (PG) directly learn an optimal policy by applying gradient steps towards better performance [25]. Due to its scalability, ease of implementation. and adaptability to many different settings such as model-free and continuous state-action spaces [13 [2]. PG has become the workhorse of RI., Although regularization techniques such as max-entropy Tsallis [1] have shown robust behavior without impairing computational cost, they only account for adversarial reward [2 6 3]. Differently, robust PG formulations (RPG) formulations aim to address
or
uncertainty to reward and transition fuuctiinn.
Despite their ability to propel robust behavior, RPG methods that target robust optimal policies are still rare in the RL literature. The global convergence of RPG established in [66 [0] already ensures global convergence of our proposed algorithm, but motivates a practical method for estimating the gradients. Indeed, [16] 30) occult the estimation part, as they assume full access to the policy gradient. Alternatively, the inner loop solution proposed in (30 (Sec. 4.1] requires solving convex optimization problems to find the worst model, which represents a larger time complexity of O A log Togg -1 for (s, aa-a)-eeee rectanguul,,,, or O A log " for s-rectangular uncertainty sets. These worst kernel and reward models are needed to compute RPG using the policy gradient theorem [26]. Other approaches that elicit an expression for RPG rely on a specific type of uncertainty set such as reward uncertainty
with known kernel K 5 r-contaminated kernel with known reward [32] or (s, a) o)-rec)anguular
uncertainty [6],, whereas we aim to tackle more general robust MDPs.
In this work, we introduce an RPG method for both s and (s, a) reetangulaa ball-constraing un- certainty sets, with similar complexity as non-robust PG. Our approach provides a closed-form expression of RPG without relying on an oracle while applying to the most common robust MDPs. To this end, we derive the worst reward and transition functions, thus revealing the adversarial nature of the corresponding uncertainty set. Surprisingly, we also find that the worst kernel is a rank-one perturbation of the nominal kernel. Leveraging this rank-one perturbation enables us to derive a robust occupation measure. We concurrently propose alternative definition of the robust Q-value together with an efficient way to estimate it. Combining these results enables us to obtain RPG in closed form. Our resulting RPG update requires 0(5 A loge -1) computations, thus showing similar time complexity as non non-robust PG.
(i) We establish the worst reward and transition models in closed- form; (ii) We show that the worst-case transition function is a rank-one perturbation of the nominal; (iii) We introduce alternative robust Q-values that can be evaluated through efficient Bellman recursion while retrieving the robust value function; (iv) We establish an expression of RPG that can be estimated with similar time complexity as non-robust PG. Experiments show that our RPG speeds up state-of-the-arr robust PG updates by orders of magnitude.
To summarize our contributions:
2
Related work
Although some previous works use gradient methods learn robust policies, they seek empirical robustness to adversarial behavior rather than robust MDP solutions [21 29 4 In that sense, our study differs from adversarial RI. as we explicitly optimize the max-min objective to find a robust optimal policy. Accordingly, the risk-averse approach focuses on the internal uncertainty due to the stochasticity of the system, whereas robust RL addresses the external uncertainty of the system's 's dynamics. As result, common risk-averse objectives can be reformulated as robust problems with specific uncertainty sets [27].
These are established RPG for s-rectangular reward-robus MDPs, i.c., robust MDPs with uncertain reward but given kernel. Although it applies to general norms, their result does not account for transition perturbation. Differently, in 32.. the authors introduced RPG for r-contaminated MDPs, i.e., robust MDPs with uncertainty set 24 == } x P1 + r x A1. Although it has similar complexity as non-robust PG, by construction, their setting is limited to (s, a) rretaangullriiy with known reward and mixed transition. As such, the proof techniques in [32 are tallor-ade to the r-contamination framework and do not apply to more general robust MDPs. In fact, we remark that the r-contamination setting is equivalent to the action robustness approach introduced in 29). which emphasizes its limitation to action perturbation. Differently, our RPG holds whenever the worst kernel is rank-one perturbation of the nominal transition function (see Lemma
Previous studies that did aim to derive robust posicy-based methods are 3 32
30
summarized in Table []] which also displays the complexity of existing approaches. [3]

---

The work [66] provides a convergence proof of robust policy
in the (s, a) rectanngula case, whereas we study robust policy optimization for s-rectangular uncertainty sets. In fact, its restriction to the (s, 9,,a-ccaee prevents from transposing the analysis to our setting. This is due to the fact that the standard robust Bellman operator on Q-functions can no longer be applied on s-rectangular sets. To address generic robust MDPs, [0)] recently introduced RPG for general uncertainty sets. Their gradient update has a complexity of O(S A which is more expensive than non-robust PG by factor of 5 Both works [16 30) additionally assume access to an oracle gradient of the robust return with respect to the transition model. Avoiding this oracle assumption naturally leads to even higher time complexity in [30 which is not scalable. At the same time, the two works [16, 30 guarantee global convergence projected robust gradient iterates, thus establishing the potential promise of RPG. In fact, equipped with RPG convergence, the remaining challenge in making it practical is to efficiently estimate the gradient. This represents the main focus of our study: We aim to explicit RPG method that generalizes existing results on specific uncertainty sets 3 32 while holding for s-rectangular robust MDPs.
Table 1: Time complexity of RPG update according to the type of uncertainty set. For conciseness, the displayed complexity hides logarithmic factors in A and S. Our RPG method has the same complexity as non-robust PG while it generalizes other RPG methods with similar efficiency.
UNCERTAINTY SET U
TIME COMPLEXITY REFERENCE
[Bo} (Po}
S Algl
26
(Ro) [(1 (1-r)) Po r x (s, a--recctan ball U (s, -rretanngul,,, convex _
5 S²Aloge
32
52 Aog c-
This work
5 S'Alog Aloge
Convex optimization
rectangular ball Up
S Alog e
This work
recctnngular ball (Ro + R2y x (Po)
S2 A log c-
3
s-rectangular, convex 21=
St A log
Convex optimization
s-rectangular, convex ut2
6 A
30
s-rectangular, non-convex 21=
NP-hard
33
Non-rectangular, convex 4
NP-hard
33
Preliminaries
Notation: We denote the cardinal of an arbitrary finite set E by |2]. Given two real functions a, 2 - IR their inner product is (a, b) == E=ez a(z) b(z), which induces the fn-m ||al| = v(a z. More generally, the l,- fo-morm of a is denoted by ||а||p whose conjugate norm is ||all == max|ib] [b) 51 (a, b) with 9 = p- by Hölder's inequality. The vector of all zeros (resp. all ones) with appropriate dimensions is denoted by 0 (resp. 1); the probability simplex over by Az {a : Z + R+ ((a, 1)2 = 1), and Iz designates the identity matrix in R x 2 Given v E 2 we finally define the variance function as (T(v) = min - 1|1 llg and the mean function as (v) arg min wenleel/lv w1 ll (see Tab. 2 for their closed-form expression when
q E oo)).
3.1 Markoy Decision Processes
A Markov decision process (MDP) is tuple AS,,A77, 7, P,R such that S and A are finite state and action spaces of cardinal S and A respectively, 7 [0,1] is discount factor and μ Ag the initial state distribution. Denoting X' := S x A, the couple (P, R) corresponds to the MDP model with P X + As being a transition kernel and R X + reward function. A policy : S + AA maps each state to probability distribution over A, and we denote by II the set of such functions. For any policy æ E II, RM E IR is the expected immediate reward defined as RdT (s) := (T,, -)A, Vs E S, where n. is a shorthand for r(-Is). We similarly define Vs. E S, and extend the
the stochastic matrix induced by т as PT (s'ls) == (T P(s'(s.)))
occupation measure to an arbitrary initial vector v E R by defining
dpp := v (Is PP7
3

---

Note that the initial vector here is not necessarily a probability measure: it can be the initial state distribution, but also the balanced value function introduced in Sec. Eq 2 The performance measure we aim to maximize is the value function V(P.R) = (Is Pr R or alternatively, the return ((P.R) = (u, R))ss. We denote the optimal value function (resp. optimal return)
by v(P..) = maX k() (resp. P(P,R) (44 (P,,)))). It can obtained using Bellman operators, which are defined as T u:= R + and T (P,80 "==== maxzen T (p,N) v, Ve E ERS
respectively 22 For any vector v E R. we associate its Q-function Q E R. such that
Q(s,a) = R(s, a) + (P(-s,,,) s)s, V(s,a) E X.
Table Expressions the q-mean, the q- v-arriance, and its gradient. We assume that the vector v is sorted, i.e., v(s;) 2 v(s+41), Vi E 21,2, ... ,S,, and denote == L(S + 1)/2], == + 1)/21)/2
(w(
(v)
V (eni(())
q
arg min w llg
min w1llg
(ny(U) Bn(s;)
if 1
00
tu(s)
0 ((a)-0a [(s)]
2
2
if =
0
O.W.
2
D v(ac)
V Ei (u(st) w2(w))²
o(a)) ((4))-22())
Ka(1)
i <
1
o(Sn )
C u(ss-i))
if na
0 O.W.
With a slight abuse of notation, we can similarly define a Bellman operator over Q-values
T (P.R) ((s = R(s, +7
Σ (()(1s.))) V(s,a) X
(d',a')Ex
3.2 Robust Markov Decision Processes
In a robust MDP setting, we assume that (P, It) and aim to maximize return under the worst model from the set. We denote the robust performance of policy E by Pu == =min(P,K)eu Ry It is maximal when it reaches Pă max P an optimal robust policy Th arg max Pü- When considering the robust value function U// == min RPP.R) we further need to assume that U4 is convex and rectangular so that an optimal robust policy realizing oi == max, o can be computed in polynomial time [33]. We thus assume U4 be convex and rectangular in the remainder of this work. Specifically. we denote an (s, a -eeetttangl uncertainty set by 4 == X (s.a)ex (s.a)ex(P(ss.))) (s...a): R..,))).
represents a particular case of s-rectangular uncertainty which we similarly denote by Ut := X X RR). ). In both cases, there exists an optimal robust policy that is stationary, although all optimal ones may be stochastic [33].
Similarly non-robust MDPs, robust MDPs be solved through Bellman recursion. Indeed, the robust value function oi (resp., optimal robust value function vyy)) is known to be the unique fixed point of the robust Bellman operator T min Rjeu T(r.,) (resp., the optimal robust Bellman
operator Th maxæen e), Vo E I both being 7-contractions for the sup-norm. Although this ensures linear convergence of robust value iteration, the evaluation each Bellman operator can still be prohibitive for practical use.
3.2.1 Ball Constrained Uncertainty set
To facilitate the computation robust Bellman updates, we consider uncertainty sets that are centered around nominal model (Po, Ro), i.c., of the form 2/ (Po, Ro) + (P, R), and constrained according

---

to Ep en-norm balls [ [1]]]]]] 9 In the (s, recttaguul case, the corresponding uncertainty set is denoted by u : R x Pp ((s.))x(((ss.))) R(s,a)) where for any (s. E X,
(s,a) fr E R |r| as and P(s.a) {p E I (p, 1)s = 0, IIpllp S Pa,a)
Similarly, an s-rectangular norm-constrained uncertainty is denoted by Ug = XsES(Pxs R₂)) where for any s E S
R. = (r R-A ||r||p S aa). and P R o)
Ya E A, 1llll S B.).
In both cases, the kernel uncertainty set conceals linear constraints ensuring all entries in Po + P are non-negative. Indeed, we generally ignore Po to satisfy these constraints in practice [23] Although it may include absurd models and unnecessarily lead to conservative policies, this proxy region is appropriate for model-free robust learning. Moreover, the norm-ball structure on uncertainty sets above enables to compute robust Bellman updates with similar time complexity as non-robust ones using regularization 14]. We formalize this below.
Proposition 3.1. M4 Thm. 2-31.) For any policy π E II and any rectangular f--ball- co-ssll-conttrinnt uncertainty set, the robust Bellman operator is equivalent to its regularized form:
(T (8) =T (o) v(() + Pggl,, B,,),
=Tx
where (2, (m as. + (v) A for (s, reettanguull uncertainty Upo and (, = (a,, + (78,6( n. 1l for s-rectangular uncertainty U.
In the following, we leverage the regularized formulation of robust value functions to explicitly derive RPG for rectangular by-ball uncertainty sets.
3.2.2 Robust Gradient Method
Since the robust return can be non-differentiable, we need to follow the projected sub-gradient ascent rule in order optimize the robust return, namely, update Tk4 == -projn + +000p where
Pxpū == V P(r.) (P.R)=(PZ,R5))
17 is the learning rate, projm denotes the orthogonal projection II, and (Pū Ry) is the worst model associated with π E II and Ut ie., (Pu, RT)) E arg inf (r, Prr.y
Given oracle access to sub-gradient 0ph. projected gradient ascent converges to an e-optimal policy TH Moreover, under similar conditions in the non-robust setting, projected gradient ascent holds an iteration complexity of ASS A [30]. Yet, the sub-gratd uub-gradient in (I) is generally intractable, particularly because general convex uncertainty sets may yield NP-hard complexity. Instead, propose to focus on ball-constrained uncertainty sets in order to efficiently compute RPG updates.
Towards RPG: Expressing the worst quantities
In this section, provide all the ingredients needed for deriving RPG. Before diving into the gradient expression, we first settle on the general framework of policy gradient. Secondly, in Sec. 4.1 we focus on expressing the worst model according the nominal explicitly. Surprisingly, we find that the worst transition kernel is rank-one perturbation of the nominal. This finding enables us derive the robust occupancy measure, i.c., the visitation frequency of the worst kernel in Sec. 4.2 As last piece, in Sec. 4.3 we propose an alternative definition of robust Q-value and show that it can be estimated from a specific Bellman recursion.
Consider again the projected gradient ascent rule:
Tkt1 p-rroj ( + 10xx77))) (.)..
By definition of the sub-grad -radirrd and applying the standard PG theorem 26 it holds that:
Omp
Σ
(s)
(x.))xx
5

---

where Qū := Q Prg.mg m.) is the Q-value associated with the worst-case model, and di :- dz the occupation measure of the worst transition kernel. In fact, for the uncertainty sets we focus in this work, the worst Q-value Qu retrieves the common definition of robust Q-value [20] (28) (see the appendix for detailed discussion). Therefore, for conciseness and with a slight abuse, we shall designate Qu by the robust Q-value, and dip by the robust visitation frequency. The remaining question is how to compute these quantities and in particular, can efficiently find the worst parameters (Pū. ? The following part of our study aims to address these questions.
Given uncertainty set U, let first define the normalized and balanced robust value function as: (s) == sign(ug(s) (, (1 w. (*()))
(2)
Kig (eg,)) 19-1
By construction, it has mean and unit norm, i.e., (už 1)s 0 and 1 Il stated in the result below, ui is the gradient of the g-variance function, and correlates with the (unnormalized, unbalanced) robust value function according to the same q-variance.
In fact, as
Proposition 4.1. For any policy II and ey ey-ball rectangular uncertainty set, the following holds:
ui V (v)
0=
(ul vū) Kig (v))
4.1 Worst Kernel and Reward
In the following results, we explicit the relationship between the nominal and the worst-case model for (s, a) and s-rectangular e,- é,-balls. We will then leverage this relationship to compute the robust Q-values and the robust occupation measure, both necessary for RPG.
Theorem 4.2 ((s, recttangga case). Given uncertainty set U Ug. and any policy TT, the worst model is related to the nominal one through: and
( a) = Ro(ss,) a)
assaa
- Ba.a ".
Based on Thm. 4.2 it follows that in the (s, reettaguraa case, the worst reward function is independent of the employed policy. As we establish Thm. bellw this no longer applies under s-rectangularity. In either case, the worst kernel is policy-dependent, discouraging the system to move toward high-rewarding states and directing it to low-rewarding ones instead. Surprisingly, the vector penalty uz E R additionally illustrates that the worst kernel rank-one perturbation the nominal. Indeed, considering the stochastic matrix induced by any policy E II, we have
[P P5)('1ss
uzl (s'),
Vs E
so that the perturbation matrix PT PT is of rank one. In the sequel, we will leverage this finding to compute the robust visitation frequency.
Theorem 4.3 (s-rectangular case). Given uncertainty set = -2 and any policy æ E II, the worst model is related to the nominal one through:
(T,
9-1
[a(a) TT
RV (s. a) R)(s,a)= as
and (a Po(-ls. - -Buul
Similarly to the (s, casse, the adversarial kernel is rank-one perturbation of the nominal. Yet, an extra dependence on the policy through the coefficient (a(a)
9-1
[Ta appears in the s-case, affecting
both the worst reward and the worst kernel. Intuitively, it means that the worst model cannot be chosen independently for each action, but must instead depend the agent's 's policy. This further explains why optimal policies can all be stochastic s-rectangular robust MDPs B3]
Thms. 4.2 and 4.3 enable us to derive the worst MDP model in closed form with time complexity O(S Algg ). up to logarithmic factors (please see the appendix for a detailed discussion). It thus holds the same complexity as non-robust value iteration, since we additionally need to compute the value function to derive corresponding regularizer 3 14]. On the other hand, we employ convex optimization using value methods instead, obtaining the worst model requires time complexity of O A log e -1) the (s, reettaguraa case, and O A log -1) in the s-rectangular case [3]] 4.1].

---

4.2 Robust Occupation Measure
We finally derive the robust occupation measure using nominal values, which will lead to an explicit RPG. Although intractable in general, we show that focusing on ball-constrained uncertainty enables deriving the robust occupation matrix efficiently from the (nominal) occupation measure. We first establish the lemma below, which leverages the fact that the worst transition function is rank-one perturbation of the nominal and represents our core contribution.
Lemma 4.4. Let b, k E I and Po. P1 E (As)s two transition matrices. P; = Po - bb_ iie. Pi is rank-one perturbation of Po. then their occupation matrices D; == (I PP:) (--PP,)--1 --,1-= 0, are related through:
Dobk? Do
D1 = Do 7 (1 +k Dob)
Combining Thms. 4.2 and 4.3 with the above lemma, obtain the robust occupation in terms of the nominal, as stated in Thm. below.... Prior to this, we introduce the notion of expected transition uncertainty below.
Definition 4.5. Let a rectangular ey-ball-conttriine uncertainty set of transition radius B. For II, the expected Iransition uncertainty at any state E S is given by B
any policy EVEA Te (a if = Upe and 3 := 3g |T if = U.:
Theorem 4.6. For any rectangular fy--bal--onntrrinee uncertainty and E 11, it holds that:
(d 3r)s
tit = dPo.. 7 Po 3d)
11
d' Po.ug.
Thm. A.jexxpliyyyyy highlights the relationship between the robust visitation frequency and the nominal one. Thus, according to Eq. (3). the standard non-robust occupation measure in the first term needs to be penalized by another one, d/o.ug = (ut) (Is yP ) to obtain the robust occupation measure. Recall that ut is the balanced-scaled value function determined by E II and uncertainty set Thus, the penalty term d. tends to zero all coordinates of the robust value function vector converge to the same value.
Nonetheless, our expression (3) does present some challenges. First, the visitation frequency appear- ing the correction term indicates that instead of taking a fixed initial state distribution, we should start from a varying and signed measure represented by the balanced value function. Although it suggests putting more weight on worst-performing states, obtaining a non-biased estimator for this occupancy measure remains unclear in model-free learning. One may use importance sampling, but as any off-policy approach, both variance and bias would need to be controlled then. Such statistical analysis goes beyond the scope of this work.
4.3 Robust Q-values
In this section, focus on the last element needed for RPG and aim to estimate the robust Q- value denoted previously by Qū == 2rz (Pr.))))) Define its associated value function as ()((s)
(m.: Qu (s. )), vs E S, II. Based standard Bellman recursion, it thus holds that:
(x a) = R2 (s, a) 7P (-1s, a), wū)s. V(s, E X, E IT, while Qū is the unique fixed point of the 7-contracting operator
(s),Q)ss, a) == T(p..R)) Q(s,
(4)
The relations above hold for general uncertainty sets, provided that we have access to the worst model. The s-rectangularity assumption additionally enables us to retrieve the robust value function using the Bellman operator above 33 Concretely, we have: 27 = min(P, ((P.)) "(pg .p))
The following result derives a regularized operator equivalent to Lip, which results an efficient iteration method to compute the robust Q-value.
Proposition 4.7. The Bellman operator Cū defined in Eq. (4) is equivalent to:
(fT,Q) a) = -o ((s a) + S2 (as,a Br,a,
where u(s) = (T,, Q(+ A) (a,,3, == -(as,a +
for (8, a)-rectangular uncer- (as + (33xk,(1)) for s-rectangular Uü.
wainty U53 and S2 3,v) = [=(0) [T
9-1
7

---

Robust Policy Gradient
We are able to derive an RPG by combining previous results. Notably, unlike previous works that need to sample next-state transitions based on all models from the uncertainty set [2] here, only need the nominal kernel to get the occupation measures. Theorem 5.1 (RPG). For any rectangular Ey ball-constraiined uncertainty, the robust policy gradient is given by:
Pmp =
Σ (s.a)EX
(d) (s)) QT(ssa))Mm(())
(5)
where
Po. 37
c (s) 1 y/d Po. 3r)
d Pu (s), E.
The implementation of RPG directly follows and can be found in Alg. Thm. 5.1 is straightforward application of non-robust PG, as its proof simply consists in plugging Eq. (3) into the standard PG expression Ö.Pū = a(,,) dū (i) a (a, We obtain regular PG in the first term, with the robust Q-value instead of the non-robust one, plus a correction term c* resulting from taking the visitation frequency of the worst kernel instead of the nominal. Unlike previous work that uses policy regularization to achieve empirical robustness in PG methods (2 11. Thm. establishhss an RPG that accounts for transition uncertainty and targets a robust optimal policy. It crucially relies on the rank-one- rank-one-perturbation structure of the worst transition kernel (see Lem. 4.44. As established in Thm. (46) by-ball uncertainty implies such property, but the converse as to whether any convex set leads to the worst transition kernel being rank-one perturbation of the nominal remains open question. For example, it would be interesting to investigate the structural properties needed on the uncertainty set for the rank-one perturbation to hold.
Algorithm 1 RPG
Input: μr, 17 Initialize: Uk. TT
1: for k 1.2.... do
-c) 2: Ozpk = -((s))E (C)) (s)
D Compute policy gradient > Update policy
3:
+ (T + p)*P))
4: end for
5.1 Complexity Analysis
A major concern in solving robust MDPs is time complexity 33
Similarly, it is of major importance assess the additional time required for computing an RPG update, compared to its non-robust variant. Although previous work has analyzed the convergence rate of RPG to a global optimum 300, it assumes access to an oracle gradient, thus occulting the computational concerns raised from gradient estimation. In fact, the NP-hardness of non-rectangular and/or non-convex robust MDPs 33 already indicates that their resulting RPG can be intractable.
To compute RPG in Thm. 5.1 we first need to evaluate the robust Q-value. Based on Lemma 4.7 and the Bellman operators introduced there, evaluation method involves additional estimation of the variance function Kp. According to [14, this takes logarithmic time at most, using binary search. As to the compensation term e in Eq. (1I. it requires computing occupancy measures with respect to two different initial vectors, namely the balanced value function and the initial distribution. Thus, the computational cost for estimating c is the same estimating non-robust occupancy measure. Tab. | summarizes the complexity of different approaches while detailed discussion can be found in the appendix. We refer to [Scc. 4.1] for the complexity of RPG based on convex optimization.
Generalization to arbitrary norms. Until now, we have focused on É, norm for concreteness. However, the above results apply to any norm ||- at least if the uncertainty set is (s,a) arrectnagu,,r in which case the variance function changes to x<v)) == min c= v) and the balanced value (c, to arg min ||o| $1,17 - v). The rank-one perturbation structure of the worst kernel is preserved, so
the robust occupation measure can be obtained similarly using Lemma 4.4 The s-rectangular is more involved. We defer its discussion to the appendix and leave its complete derivation for future work.
8

---

Experiments
In order to test the effectiveness of our RPG update, we evaluate its increased time complexity relative to non-robust PG. In the following experiments, randomly generate nominal models for arbitrary state-action space sizes. Each experiment was averaged over 100 runs. We refer the reader to the appendix for more details on the radius levels and other implementation choices.
We first focus on frobutttt MDPs to compare our RPG with convex optimization approach. Specifically, we consider robust PG with an optimization solver, which we designate by LP-RPG. Indeed, recall that & optimization problem. Therefore, compute the robust value function for given policy, iteratively evaluate the robust Bellman operator using LP 30 Section 4.1J. Using this approximated value function, we can compute the worst value parameters to apply PG theorem by [26] and deduce an LP-based robust PG update. Differently, our RPG method relies on the regularized formulation of robust value iteration proposed in [3], from which we deduce the cermalized-balanee value function as in Eq. 2 We finally apply Thm. 4.6 to compute the robust occupation measure, and Prop. 4.7 to obtain the robust Q-value.
induce a linear program (LP) rather than a more general convex
Tab. displays the results obtained for the two alternative methods described above. In all experiments. the standard deviation was typically 2- 1-10% so we omitted it for brevity. As can be seen in Tab. LP-RPG does not scale well compared to RPG, whereas RPG has similar time complexity as PG. Notably, the running time of s-rectangular LP-RPG scales much better with the space size than its (8, d)-rectangular equivalent, which confirms the theoretical complexities from Tab. Yet, since these methods expensive than RPG by 1-3 orders of magnitude, which illustrates its inefficiency. We emphasize that here, only focused on & fo-bstttt MDPs to leverage LP solvers in robust policy evaluation. We expect the computational cost of L.P-PG to scale even more poorly for other fp-robust MDPs that involve polynomial time-consuming convex programs.
time-consuming,
repeated these for few only. In fact, LP-RPG is more
Table 3: Comparison of the relative running time between RPG and the convex optimization approach (here, LP). Our method faster than LP-based updates by to orders magnitude.
{(Po, Ro))
Ufa
uf
S
A
PG
RPG
LP-RPG
RPG
LP-RPG
10
10
1.4
326
1.4
77
30
10
1.4
351
1.4
109
50
10
1.4
408
1.4
159
100
20
1.5
469
1.3
268
500
50
1.3
925
1.3
5343
We further compare RPG to non-robust PG different ba-ball.. Tab. confirms the comparable time complexity RPG to non-robust PG, thus demonstrating the effectiveness our method. We note that for p E {1, )o), the corresponding regularization quantities can be computed in closed form, whereas they involve a binary search for other values [4]. We thus get a slight running- uunning-time time increase for p E (5, 10).
Table 4: Relative running time for computing RPG under different types of uncertainty sets.
((Po, Ro)}
Ug
Ug
uga
ug
U
L/s
10
10
1
1.5
1.5
4.9
4.7
4.7
4.9
1.5
1.6
30
10
1
1.4
1.5
4.2
4.3
4.2
4.0
1.4
1.4
50
1.5
1.4
4.5
4.1
4.0
4.0
1.4
100
20
I
1.4
1.3
2.6
2.5
2.5
2.4
1.3
1.2
500
I
1.2
1.2
1.7
1.7
1.7
1.7
1.2
1.3

---

7 Discussion
This paper introduced an explicit expression of RPG for rectangular robust MDPs. Our approach involved auxiliary results such as deriving the worst model in closed form and showing that it is rank-one perturbation of the nominal kernel. The resulting RPG extends vanilla PG with additional correction terms that can be derived in closed form as well. Thus, the computational time of RPG is similar its non-robust variant.
A key assumption that would be interesting to relax is the normed-ball structure of the uncertainty sets considered in this study. Indeed, since the proofs of our technical results rely norm properties, it is still unclear if and how RPG can generalize to metric- based or f-divergence uncertainty sets. The latter type of uncertainty can be particularly useful for data-driven settings, the radius can be chosen according to cross-validation or statistical bounds [TO]. Another compelling direction would be explore other variants of RPG using mirror descent or natural policy gradient and examine their compatibility with deep architectures, which would further demonstrate the practical efficiency of our RPG method.
References
[1] Bahram Behzadian, Marek Petrik, and Chin Pang Ho. Fast algorithms for consttaaed s-rectangular robust MDPs. Advances in Neural Information Processing Systems, 34:25982- 25992, 2021.
[2] Rob Brekelmans, Tim Genewein, Jordi Grau-Moya, Grégoire Delétang, Markus Kunesch, Shane Legg, and Pedro Ortega. Your policy regularizer is secretly an adversary. Transactions on Machine Learning Research (TMLR), 2022.
[3] Esther Derman, Matthieu Geist, and Shie Mannor. Twice regularized MDPs and the equivalence between robustness and regularization. Advances in Neural Information Processing Systems, 34:22274-22287, 2021.
[4] Esther Derman, Daniel J. Mankowitz, Timothy A. Mann, and Shie Mannor. Soft-robust actor- critic policy-gradiemm AUAI press for Association for Uncertainty in Artificial Intelligence. pages 208-218 2018.
[5] Esther Derman, Yevgeniy Men, Matthieu Geist, and Shie Mannor. Twice regularized Markov decision processes: The equivalence between robustness and regularization. arXiv preprint arXiv:2303. 06654, 2023.
[6] Benjamin Eysenbach and Sergey Levine. Maximum entropy RL (provably) solves some robust RL problems. International Conference on Learning Representations, 2022.
[7] Tuomas Haarnoja, Aurick Zhou, Pieter Abbeel, and Sergey Levine. Soft actor-critic: Off- policy maximum entropy deep reinforcement learning with a stochastic actor. In International Conference on Muchine Leurning, pages 1861-1870. PMLR, 2018
[8] Chin Pang Ho, Marek Petrik, and Wolfram Wiesemann. Fast Bellman updates for robust MDPs. In International Conference Machine Learning, pages 1979-1988. PMLR, 2018.
[9] Chin Pang Ho, Marek Petrik, and Wolfram Wiesemann. Partial policy iteration for 4 rrrbuttt Markov decision processes. J. Mach. Learn. Res., 22 2021.
[10] Chin Pang Ho, Marek Petrik, and Wolfram Wiesemann. Robust d-divergence MDPs. arXiv preprint arXiv:2205. 14202, 2022.
[11] Hisham Husain, Kamil Ciosek, and Ryota Tomioka. Regularized policies are reward robust. In International Conference on Artificial Intelligence and Statistics, pages 64-72. PMLR, 2021.
[12] Garud N Iyengar. Robust dynamic programming. Mathematics of Operations Research, 30(2):257-28) 2005.
[13] Sham Kakade and John Langford. Approximately optimal approximate reinforcement learning.
In International Conference on Machine Learning. Citeseer, 2002.
10

---

[14] Navdeep Kumar, Kfir Levy, Kaixin Wang, and Shie Mannor. Efficient policy iteration for robust markov decision processes via regularization. 2022.
[15] Kyungjae Lee, Sungjoon Choi, and Songhwai Oh. Sparse Markov decision processes with causal sparse Tsallis entropy regularization for reinforcement learning. IEEE Robotics and Automation Letters, 3(3):1466-1473, 2018.
[16] Yan Li, Tuo Zhao, and Guanghui Lan. First-order policy optimization for robust Markov decision process. arXiv preprint arXiv:2209. 100::2099.1079, 2022.
[17] Daniel Mankowitz, Timothy Mann, Pierre-Luc Bacon, Doina Precup, and Shie Mannor. Learn- ing robust options. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 32, 2018.
[18] Shie Mannor, Duncan Simester, Peng Sun, and John N Tsitsiklis. Bias and variance approxima- tion in value function estimates. Management Science, 53(2):308-322, 2007.
[19] Paul Milgrom and Ilya Segal. Envelope theorems for arbitrary choice sets. Econometrica. 70:583-601, 02 2002.
[20] Arna Nilim and Laurent Ghaoui. Robust control of Markov decision processes with uncertain transition matrices. Operations Research, 53(5):780-3) 2005.
[21] Lerrel Pinto, James Davidson, Rahul Sukthankar, and Abhinav Gupta. Robust adversarial reinforcement learning. In International Conference on Machine Learning, pages 2817-2826. PMLR, 2017.
[22] Martin L Puterman. Markov decision processes: discrete stochastic dynamic programming. John Wiley & Sons, 2014.
[23] Aurko Roy, Huan Xu, and Sebastian Pokutta. Reinforcement learning under model mismatch. Advances in Neural Information Processing Systems, 2017.
[24] John Schulman, Xi Chen, and Pieter Abbeel. Equivalence between policy gradients and soft q-learning, 2017.
[25] Richard S. Sutton and Andrew G. Barto. Reinforcement Learning: An Introduction. The MIT Press, second edition, 2018.
[26] Richard S Sutton, David A McAllester, Satinder Singh, Yishay Mansour, al. Policy gradient methods for reinforcement learning with function approximation. In Advances in Neural Information Processing Systems, volume 99, pages 1057-1063. Citeseer, 1999.
[27] Aviv Tamar, Yinlam Chow, Mohammad Ghavamzadeh, and Shie Mannor. Policy gradient for coherent risk measures. Advances in neural information processing systems, 28, 2015.
[28] Aviv Tamar, Shie Mannor, and Huan Xu. Scaling up robust MDPs using function approximation. In International Conference on Machine Learning, pages 181 181-189. PMLR, 2014.
[29] Chen Tessler, Yonathan Efroni, and Shie Mannor. Action robust reinforcement learning and applications in continuous control. In International Conference on Machine Learning, pages 6215-6224. PMLR, 2019.
[30] Qiuhao Wang, Chin Pang Ho, and Marek Petrik. Policy gradient in robust MDPs with global convergence guarantee. In International Conference Machine Learning, pages 35763-35797. PMLR, 2023.
[31] Yue Wang, Fei Miao, and Shaofeng Zou. Robust constrained reinforcement learning. arXiv preprint arXiv:2209.066:
2022.
[32] Yue Wang and Shaofeng Zou. Policy gradient method for robust reinforcement learning. In International Conference on Machine Learning, pages 23484-23526. PMLR, 2022.
[33] Wolfram Wiesemann, Daniel Kuhn, and Berç Rustem. Robust Markov decision processes. Mathematics of Operations Research, 38(1):153-188 183, 2013.
[34] Huan Xu and Shie Mannor, Robustness and generalization. Machine learning, 86:391-45 2012.
11

---

Contents
Balanced and Normed Vectors
13
Proof of Proposition 4.
14
Worst Kernel and Reward
14
Proof of Theorem
14
B. Proof of T'heorem
15
Occupation Matrix
16
Proof of Lemma
16
Proof of Theorem 4.6
17
D Robust Q-value
17
D.I Basic Properties
17
D.2 Evaluation
18
D.3 Convergence
19
Robust Policy Gradient
20
Complexity Analysis
20
Helper results for Robust MDPs
F2 RPG Complexity
22
Generalization to arbitrary norms
23
G.I
(s, a. rectannuula robust MDPs
23
s-rectangular case
24
G.3
Generalization metrics and divergences
24
Experiments
24
H.1
RPG by LP
24
12

---

A Balanced and Normed Vectors
In this section, we lay down some basic properties of p-normalized--alaaea vectors. First recall the p-variance and the p-mean defined as:
(p)
min| w1 w1|pp: up(v) = arg min|| - w1 pp.
weR
WER
Given any o E RR let also the bbalanced-nommalliiie function:
[u((s) (0(6))4w))) uip(o)]
Up (v)(s) == (IG)( wp(w))
Ve WERRS
(1)(1)
According to 14 |Sec. 16.1, Lemma 11. the following holds:
min (c, (c, (v) = [iellp=ee/e.1==0
(6)
namely, the p-variance function is the optimal value of linear optimization under kernel noise constraint. The result below further characterizes the solution to the above problem.
Lemma A.1. The vector defined as c' == (C)(() (v) is optimal solution to the optimization problem min
(c,
Se
Proof. It suffices to show that c* satisfies both constraints ||c*|p S and (c", ,1ss 0. and that it reaches optimal value, i.e., (c v) (v))). We thus compute:
||c* 11 = Σ (s)
.ES
(lu(s) (I(s)) w 8-1
Σ
ESIGN(U(s) - wo(()))
(t)
(u(s) wg(u)) Kig (r)
9- 8-1100 -up()-
Σ
Mig (w))o-
FESI
Σ (u(s))
w0g(1) (
Kig(1) (
leES
(By assumption, p p+ g pq
(u(s) - (1))
1)
(
BES
(1) (1)
(By definition, Ki((r) = +1| w/g 11
2 2 (4-111 1) 9- pq + 0)
6,
p
p
so the norm constraint is satisfied. We check the noise constraint by computing:
ESTGN(U(s) wg(()) ( [lo(s) - (g)
Ed'ss)
(1)(v)
#ES
ES
SIGN(D(s) - (,(v))lu(s) w
Ky (v)
sES
Now, considering the real function ip : ||I -w1ll and taking its derivative, remark the proportional relation:
Σ (s) = (w(()))))
SES
13

---

where C' E I is the proportionality coefficient. By construction, wy(() is minimizer of so we must have o (w)( and c* satisfies the noise constraint.
We finally show that e" reaches the optimal value:
1 (c" (
(c', v)
((c', 1/s =
lu(s) - (v)
(Putting the value of c*)
Ni (o)
(1))
(Kg(U) = 1110 (
(y(()
(v))
A.1 Proof of Proposition 4.1
Proposition. For any policy π E II and e--ball reclangular uncertainty set, the following holds:
uu (v)
(ull uz)) Kiy (v()
Proof. The second claim directly follows from Lemma A. applied to : o7 that by optimality, (og(17) = (u7, v7) For the first claim, we take the gradient of Kp(v) == min - wilpp w.r.t. using the envelope theorem [9]] Then, the p-balanced-normalizze vector (p) is sub-gradien of (V), that is,
up (R)
which we apply uo :- 0
We have the additional properties below:
The variance function Kg is manslation-invarian in all-ones directions, i.e., for all w I, (v) (T + w1). As result, (Viigv)) 1)s 0. The balanced-normaliaee vector (v) has unit norm, i.e., [|bp())]pp by Lemma A.I
B Worst Kernel and Reward
Here we present the proofs for the worst/adwersarial kernel and reward function characterization.
B.1 Proof of Theorem 4.2
Theorem ((s, -)-rectangular case). Given uncertainty set U Ug and any policy E 11, the worst model is related to the nominal one through:
( a) Ro(s, a) assaa
and
(- = Po(-1s,a) Ba
Proof. By definition,
(Pūga Rip) E min ThP ((P.R) "i.. (P.R)
Additionally, since U (Ro R) (Po P), results that:
RRi.. Pūm.) = (Po + P", Ro + R²)
where
(P*.R*) E mig T(P Tūge. (P.R)EPxR
14

---

By the (s, rectangluay assumption, we get that for all (s, X.
(P)) R (s,
arg min (Re, J RRai
Tea +y
Po )olg)))))))))
s'ES
It is clear from the above that the worst reward independent of policy Thus, by the ball constraint, it is given by
R (8, a) = -0,aa V(s, a) E E Differently, the worst kernel depends on the value function which itself depends on the policy. is given by
Pd (+(s,a))= arg min (t Pa.a
V(s,a) EX
sEES
The optimization is the form
arg min (c,0), |e lelp (1,(()))))
so by Lemma A.I
99-1
"ig (6' (8') - Wy (vipp)
('(('(s,a)= = SIGN (1ū7(5') wo (g((1)m)))
(1)
As result, we proved that for all (s E N, (s, = Ro(ssa) assa and
9-11
(p') - w w
Uun (5'1s, (s)) SIASIGN ((gge(s)) - wg (
Kig kig(1)0-1
B.2 Proof of Theorem
Theorem (s-rectangular case). Given uncertainty set U = Ut and any policy n E II, the worst model is related to the nominal one through:
Ta (a)
(Ta(a)
(s a) = a) as
and Pū(-),a) Po(-ls, - -Bulll
[|T mllllo
Proof. By definition.
(Pay: Rig) E arg min ((,.) (P,R)e
and since UØ =(R R) (Po + P), have
(Pigy. Rig) = (Po Ro R*)
where
R*) (P", arg min T(. Vip.
(P.N)EXXR
By the s-rectangularity assumption, we get that for all s S
Ema(a) fran
(P*(()s),
arg min (P..,.)PP.RR R. a.d
Tan +
Σ
Pa Po
#'ES
Here, the worst reward does depend on policy and is given by
(a
R* a) a0 Σ. - (a
V(s,a) EX.
15

---

As for the worst kernel, it depends both on the value function and the policy. It is given by
(1(,,,)) = arg min
Σ
Ta(a)
Σ
Pa (z) (
P.EP, aEA
s'ES
The optimization of interest is of the form
Σ
min Ce Sou O.aEAA
a'EA
which is equivalent to the following two-fold minimization:
Σ Ts (Co,, j.
min
min (e.
a'EA
Thus, rewriting the problem our context,
min
min I| 50 Per (6)=0
ETs(a)(Psan) v)
E (Sea)))S(18))
min ((00))))(00))
Σ (a(a)
min Spo Dea (s))=0 ()
min (00
Σ T.e
(By Lemma A.I
(i)
Σ Tz sa)
Computing the optimal above, the optimization is now the same in the (s, recttnngga case. Hence, we have
8
(* -3, (a) | g-1 SIGN (u)g Wg (1gg)
Vip (s') wo (1
which ends the proof by definition of the balanced value function u7.
C Occupation Matrix
C.1 Proof of Lemma 4.4
Lemma. Let b, R and Po, P1 E (As)s two transition matrices. Pf Po -bb i.e., P
rank-one perturbation Po. then their occupation matrices D) == -P)) -P,)-1, 0, 1 related through:
Dobk Do
D1 = Do -11 + R Dob)
Proof. By definition, Dj = (Is -P1) so it follows that:
(Is DP is
+ 1s +P,P = =D,
+ Is +++( r(P - -b:T),), =D
(By assumption, Pi Po - T
Is bbk Dj (Is PP))
= (Is PPu) -1 (Is ?bk T D1) Dj
(Multiplying both sides by (Is 7 Po) -1) (By definition, Do = (Is PP)
Do ybk D1) = D
- Do 2 Dobk T D, Dj.
16

---

Now, multiplying both sides by l and noticing that k. Dob is scalar we get
kJ Do -yk² Dabk' D1 k Di
k.T Do= (1 Dobik" D1
kT Do
D1 (1 + yk' Dob)
(8)
Combining Eqs. 7 and (8) thus yields:
Dobk Do
D1 Do -1 11+7he 7k
Dob)*
which concludes the proof.
C.2
Proof of Theorem 4.6
Theorem. For any rectangular l.-bbull-onstrriinee uncertainty and π E II, it holds that:
(d \m))
4 = d Po.. 1 P Pa. 3m)s
d Po.ng
Proof. From Thms. 4.2 and 4.3 holds that:
( () P5 (s'1s) 8 (5'),, Es..'ES.
Therefore, setting Pi
P7. Po PJ. b =- 3 and k uh can apply Lemma 4.4 and relate the corresponding occupation matrices. Additionally multiplying both sides of the relation by R 1x yields the desired result.
D Robust Q-value
D.1 Basic Properties
In the literature, robust Q-values are defined in various ways that turn out to be conflicting for but non-(s, a) rectangular uncertainty sets. In this section, propose define the robust Q-value solely based on the worst model. Define the robust Q Q-value, the robust value function, and the robust occupation respectively
Qi Upg..
d o := 0 "Pp..p) Rg)
For s-rectangular uncertainty sets (in particular, for (s, r)-recaanglllr) the above definition of robust value function coincides with the common one, i.e., "(p Rg) min "(P.R) (33]. the
uncertainty set is additionally (s, a) rectaangula (as in [31] [ [4)) ), the above definition of robust Q-value also coincides with the common one because then,
Vir (s,
(s, = min (P.R)EL("
B(s,a) + [(((1s..)000))) a(s,a) X X
x'ES
Getting back to our own definition, robust Q-value and value functions are related through:
(s) (T., Q7 (s, A)
(s R2 (s, a) + Σ 10(
#'ES
as both quantities are defined based on worst kernel and reward, i.e., Qi == Qipg. and og ==
Tig nz)
Given optimal robust policy कÿ. further use Pe. Rig oi Qi di shorthand for P p Tu Vi Q dii respectively. For reettnulla uncertainty set a the optimal value function is the best optimal Q-value, that is
Ui (s) max Qipa Qs, V.
aEA
17

---

because an optimal policy deterministically takes the action with the highest Q-value 20 [2]. This does no longer hold for s-rectangular or coupled uncertainty sets, as there, an optimal policy may be stochastic 33 Still, based on Thms. 4.2 and 4.3 we get the Bellman recursion below.
Proposition D.I. Let an e--ball constrained uncertainty set. Then, for all (8, E X and E II, the robust Q-value satisfies the following recursion in the (8,a) and s-reciangular case respectively:
(s, =7 (Fo.
Qipp(s,00 a) -as -7
TT(aa)
9-1
(5, ())
=T -T (Po. (5g(8,0)
(as (ig
|
Proof. We give proof for the (s, a) rrectnnuul case only. The s-rectangular case follows the exact
same lines except that uses Thm. 4.3 insteed of Thm. 4.2 We have:
(s, Qipg, Rg) (s.
(By definition)
Rí (s, +
Σ (s ())
s'ES
-Ro(s,a) asa +
(olls(ss Boa (pp))))) vip
(By Thm.
4.2
S'ES
= =oo(s, a) asa +7
Σ
Pols' a) (5') - -Baatttann
(2d statement of Prop. 4.1
s'ES
= a)(s, +7 s'aa'
Po(s'lss a) (a' Qi)QQu (5', (s', d') - asa - 17Beata(1ipp
= (g)
(s asa Ri
The above recursion applies the standard Bellman operator robust Q-values. We can similarly apply it on the robust value function (itself can be computed efficiently based on 14). Corollary D.2. Let an lp-ball constrained uncertainty set. Then, for all (s, a) X and II, the robust Q-value satisfies the following recursion in the (s, a) and s-rectangular case respectively:
(up((, Ro(s, a) + Σ
Pols') (5)))
Ossa ((aatia((ip)))
TT(a)) 9-1 (as + 18511
(s) Ro(s, a) +
Σ Pols' o))
||Tlll/)
D.2 Evaluation
Based on the Bellman recursion above, we now derive robust Q-learning equations to learn a robust Q-value. Precisely, investigate if the linear operator below contracting and can be evaluated efficiently:
(s, (8, +7
Σ (s',a))x
YQER*.
(9)
where (PT R arg (r,Neu T (p.m)) and u(s) (T Q(s,
Vs S.
Proposition D.3. Consider b,lllll constrained uncertainty set. Then, for all Q E Xx and π E 11,
the operator _ can be evaluated as:
Q) a) T (P) Ro) (s+,a) -asa -7Bssttg(1),
9-1 (ar + +,,,g
(C7, (8, a) TT (Po.
Q(8, a)
(TT((1)
where for all Q X its corresponding value is v(s) = (TT,, Q(s, V S.
18

---

Proof. We give proof for the (s, a) reettangula case only, The s-rectangular case follows the exact same lines except that we take the worst model for s-rectangular balls. By definition.
(d) }
()),)) = min (P.R)eup
R(s,a)+ +y
Σ
(v'a))x
Σ P(s
min (((s0) + RER
min PEPi
sEES
= Ro(ss a) - Caa + Σ Po(s"(s,a)u(s') Baati(())
(By [4]
s'ES
= Ro(8, a) - Ussa +7 Σ
a a²) - (a
(d',a')EX
-x Ro) Q(s a) - Ussa (v))
D.3 Convergence
In the remainder of this section, we focus on lp-ball constrained uncertainty sets of the form Up or Up Let our Q-value iteration Qn+1 := Qn and denote Un = (T.. Qn M) Vs S, n E N.
Proposition D.4. For all Q E R²² denote v(s) :- ( Q(s, A) Vs E S. Then, for any policy II, the Q-value iteration defined according to Qn+1 Qn induces
Unt1 == Tt Un
Proof. By construction, for all E S we have
(n) (Te, Qn+1(s, A)
(T (s, ))
Σ (a)
R ( (8, +7
Σ
Pú,,, (4
(By Eq. 9
uEA
(s)xa))Ex
Σ (a)
RE,,, (s, +2 Σ
Pa,,, (d'1s,))(((1)
(By definition of v,,)
uEA
s'ES
= = v. (8),
where the last equality holds because (Pū,.,, R arg p.g Te On.
As result of the above proposition, the value iteration induced by our Q-value iteration rule converges linearly to the robust value function, i.e., [| llo I ""11/olla> Therefore, Q-value iterates converge to fixed point. Precisely, 2n th vi implies that (PiT..,. Ry - (P Ry),. which in turn implies that Qn t, Q7- The result below further characterizes the convergence rate.
Proposition D.S. For any policy π E IT, the recursion Qut1 = Lu n E N converges linearly to Qi
Proof. Thanks to Prop. D.4 we have:
||Q++1 2i -1 || + 7.7 R2 7P.. 00
=
P.7 11 00
(R Rig
Vo),
=Yo[(Po - BBT "rTu))y>>
(Po - Bd B 1
19

---

where by the worst kernel characterization, (² = Bo.a for U = up and (= ==
8g x.la2
for U = Ug. This implies
1|Q+11 Qu x0 P w1) xo 1 (un) T On - (ui) "iglloo
S 1100 u loc + ?(((un) T Un 1n--(1j) (uu)) uill
(B, - 1),
5ymt1||00
ut loo + 71((ux) ( 'Hill + 7 7 - uit rill
|
5yn+||10 1|00
o ooo + =+1 S1100 - < +
7-7 lun - uilloo.
Here, un: uy is the normmlleddrmallzeed vector associated with vector Un and uz respectively. Recall that the p-balanced normalized vector u associated with vector is given by
u(s) = sign(v(s) wy (v)]l(((s) wg(v))l0-1
(10)
(1)
where (v) min |/ w1 |p and wp(w) = 110 wl|pp It is easy to see that wp, are Lipschitz in v. Hence, |/,, u lloe I C. Pol( - ) (((((15))) A), where Pol is a polynomial and real function. This implies that
[|Qu+1 0illo I n+ I ((((()))) 1110 2/ S.
which concludes our proof.
E
Robust Policy Gradient
Theorem (RPG). For any rectangular fy-ball-constraiine uncertainty the robust policy gradient
given by:
0.P Σ (d) c= (7(s,))m(()))
(11)
(x,a)EX
where
g5 Po. 87) 87)
c (=(s)= :=
di (s)) S.
Proof. The proof directly follows from plugging the robust occupation measure of Thm. 4.6 and the robust Q-value into standard policy-gradient theorem (26].
Complexity Analysis
In this section, we aim to derive the complexity of one RPG iteration for different uncertainty sets. We first focus on non-robust MDPs, to then see how the complexity increases with the uncertainty structure.
Non-robust MDPs. Computing non-robust Q-values and occupation measure takes OSS2 log(e-1) each, which represent the most expensive computations in PG. The product of d Q and Vx in PG requires ((SA) operations. which insignificant. Hence, the total cost of PG corresponds the computational cost of Q-values. More precisely, approximate the Q-value by Q and the occupation measure by d with A tolerance, that is, ||Q - Q* Iloo SA and I|d d= Il SA- This involves OSS2 A Aog(S 1)) operations for each. Then, we have
Σ (s(s))'(s,a) (x,0)
+ Σ ((. (s,a)xX
e2(s, vz.
d= (s, a). Let B be an upper bound where (1 a) == Q(s, a) (=, a) and eg(s, : d(s,
of ll and ||d 1o.. Then
Σ (m) = Σ +
(s.a)ex
(K.O)E
Σ (s. 0(0)
(K.))E
20

---

so the exact complexity of policy gradient for non-robust MDP is O log (
Convex non-rectangular uncertainty set. Robust policy improvement is strongly NP-Hard for non-rectangular uncertainty sets, even convex [33] The PG method finds global optimal given oracle access policy gradient in polynomial time 30 This implies that the computation of RPG must be NP-Hard.
F.1 Helper results for Robust MDPs
Variance and mean functions. Computing Kp(e) (resp. wp(e)) with c-tolerance requires ((Slog((ee))) (resp. O(S ((Sloy()))))) computations if we use binary search [1].
Occupation measure. Let R$ be any vector. By definition,
20 k (Pa)²
dp.
>
n=0
and
p.
Σ
k (PT)R
Σ = (PTy
Σ
||||| Σ 1h
Since P" is stochastic matrix, || ||
S and
N-1
|| 1 1 P*1
||
d
Σ T" ( (Pa)T
1 1-x
n=0
This implies that Em= 7rt k (P*)* is an M) approximation of d'p,.. Now, take uo = k and
Un+1 == P.
then N-1 (PT)" cost O(S2N) N) for N iterations. Computing pa from is O(5² A). We conclude that computing the occupation measure has complexity of O(S² A S log((-1)
Un. Each iteration takes (SS²) computations, leading to total
Lemma F.I. We can approximate d'p, by END (A with complexity O A Sa log((= 1) and tolerance
N-1 Σ n=0
||ll + | 1'1l )
dr.
TT (pajn
50
1-7
Proof.
N-1
N-1
N-1
N-1
dp
Σ k (payn
x d3 Σ
T (P5ym)
+
Σ
n (payn-
Σ n=0
n" T (pr)m
n=0
n=
m=0
|
N
N-1
N-1
Σ 7k (PT)"
Σ
n k (ptjm
n=0
|
N-11
N-1
|14- -
Σ
(P
Σ (pTy"
n=o
||
kk - K'll
00
1->
-
21

---

Computing Q-value given value function. Let be an é1 approximation of robust value function et. that is ||u o c1. We want compute the Q-value using the relation:
(s,
Rig R a) + Σ (s'ss,,
= Ro(s, a) + Σ
Pols s Po(s'(s, ()) nu(vi m..
where Org. (ggg: T) = xx(a)=-
(as + (1800t ) and Reyz (15gg σ) = assa + BBsati (v7r)) Let
Q be approximated from v by
((s,a)= = ((o,,)= + Σ P((5's, (St
We thus have
[|Q7(s, a) - Q(s,
Σ Polo'ls,
a)(o(s))=))))))))))))()))))))a)_ ((((s) -
+
+)|
EEES
S ye1 + [ π) - Qu( x)]
$ 761 ||||| 0o (K) (x)))
I Tel + STEl
(By Lemma F2
= O(Ste))
so that - Qi S O(Stez) Lemma F.2. The variance function Ky Lipschitz. More precisely,
[1b((1)) (x22 S s [|u v2llon S 1//1 v2lloo, Ve1, E RS.
Proof. Let vs R$ and w; E arg mig l1u wll,, for 1,2. Without loss of generality, further assume that (v))) 2 (12).. Then,
[11pp(1]) - (x2)))
(1))1) (2()2)
minl|vi w1 ||r
min U2 11// WER
(By definition)
wek
|e w2 1/p ||02 w2
1bp
(By definition of w2) (Reverse triangle inequality)
( w21) (e2 w2l)llp
$ < <
Σ (1)()))02(s))))
Uzlloc
Lemma F3. Qūp can be approximated tolerance with the same complexity computing Vūge
to S-1e. 9e.
Proof. We compute the value function with S 1ee tolerance. The rest of the operations insignificant. The result follows from above.
F.2 RPG Complexity
Let (e) be the complexity of computing Vip with e-tolerance (see [14 for more details). Calculat-
ing Q-value up to 6 requires O computations according to Lemma R3 Letting dj and d2
be 62 aa-appoxximations of dff.. and d respectively, their complexity is insignificant compared to
O (8-+ Now, approximating the gradient using d1, d2, Q, Vπ as in Thm. 5.1 has complexity
22

---

of ((SA). Since the uncertainty set U is compact, all quantities are bounded. There are ((SA) operations in Thm. 5.1 so taking c 62 O ( we get O(e) for the gradient. Hence, the total complexity is Oz (S A e) which is Algee by hiding log factors. A similar analysis follows for the s-rectangular case.
G Generalization to arbitrary norms
In this section, we analyze how to generalize our result to general norms that are not Ep.
G.1 (s, a) reetanggull robust MDPs
Consider an (s, a) rrectanggll uncertainty set ut fi-1 constrained by:
a
(o + P)) (Ro + R), where (P,R) (Xx,aPsa ssaaaa))
(s,aa) {r R ||||| asaa and Pls.a) - {p RR (p,1)s 0, 0,11pl S Ba,
The robust Bellman operator Tit can be evaluated as
(s)
(v) + Σ P(6))s, - (a) R(s,,) a (
where the variance function is defined
Kil-I (v) =
min (=.1)s=0.Jlu]
(u, VZ)-
This can be used to compute the robust value function. Then the worst values can found using robust Bellman operator Tæ and robust value function vă as
(Pū RW
aarginn min T (P.R)eu
arg
33
is easy to see that the worst values are given as
(5, (s, a) as.a and (- a) (-]s,a) Bs
where coanmalized-aalnneeee value function un is solution to
min 0.
(u, u17).
Observe that the worst kernel is still rank-one perturbation of the nominal kernel. Hence, the robust occupation measure can be obtained using Lemma 4.4 as
(d (d \T)s
Hu d.o. - 7 + (dd Pa.
8r)s d
Po.uz
(12)
where -. (a) The last ingredient to compute RPG is the robust Q-value which can be computed using robust value function and worst values. However, it can be computed directly using the following iterates:
Qn+1(s)=
min (P.R)eu
[(ssaa) a) + P((s(s,,)u(s)))
=R(s, Us,a Ba Σ P()()s,a)u(5))
as Qn converges to robust Q-value Q7 linearly.
The proofs of the above claims are very similar to the E, case so they are omitted. Finally, computing the variance function Ki and the normalized-value function up can be done using numerical convex optimization methods for general norms. For the Ep case, these can obtained in concrete form, so we choose to focus Ép in our main study.
23

---

G.2 s-rectangular case
Generalization to s-rectangular balls of a general norm is not straightforward and may not be possible for all types of norms. The crucial property of the l--norm exploited in our rank-one perturbation proof is 'decoupling', that is, for all x E RAA there must exist I, R4, such that
|
Σ REA
Iaa llm
This holds in the lp case with & = 1 = m = Further analysis of this setting is left for future work.
G.3
Generalization to metries and divergences
Generalizing RPG to distance or divergence- based uncertainty sets is also not obvious. Our RPG method, in particular the robust occupation measure, crucially relies on the rank-one perturbation characterization of the worst kernel, which might not apply for example with KL-ball constraints. We leave this analysis for future work.
H Experiments
Parameters. All the nominal transition kernels and reward functions are generated randomly. The number of states and the number of actions varied. Discount factor ? 0.9, reward noise radius 0s,a, 02 = 0.1, transition noise kernel 3..., 3, 0.01
3A
Hardware Experiments are done the machine with the following configuration: Intel(R) Core(TM) i7-6700 CPU @3.40GHZ, size:3598MHZ, capacity 4GHz, width 64 bits, memory size 64 GiB.
Software and codes All the experiments were done in Python using numpy, matplotlib, All codes and results are available at http::/github.coomnavaeeee
Procedure and Results. All the experiments were repeated 100 times, except for Linear Programming (LP) cases LP methods were very time-consuming. In LP methods, experiments were repeated 5 times except for the case (S 500, A = 100) which was done only once. As this case was prohibitively expensive. Standard deviation in all cases was less than 10%, and typically 1 2%. This conveniently illustrates the superiority of our methods over LP methods.
Observations
Scalability of methods. Note that methods scale very well with large state-action space. It takes a (small) constant times the time required by non-robust MDPs. On the other hand, LP methods explode. Both observations confirm the theoretical time complexity.
sa-case vs s case LP methods. We see s-case outperforms sa-case for small state-action spaces via LP methods. This opposite the theoretical time complexity of s-case which expensive than sa-case. We believe this is due to the internal implementation issues. Note that computing the robust value function is the most expensive step which requires evaluation of the robust Bellman operator. In sa case, one evaluation requires solving SA LP programs with S variables each, while for s-case, it is S LP programs with SA variables each. To solve LP, scipy.linpro is used, we believe it does some parallelization for large LPs. Hence, we observe less cost for sa-case. However, observe that the cost of s-case increases much faster than s-case, and eventually under-performing than sa-case.
H.1 RPG by LP
compute RPG using LP in the following steps:
(Robust Value Iteration) Approximately compute the robust value function oū using the iterates Un+1 == T77..- Un- Evaluation of robust Bellman operator TØ is done via LPs as described below. This the most expensive step as it requires evaluating robust Bellman operators (llog(e))) times, and each evaluation requires many LPs.

---

2. (Adversarial Values) Compute the worst values (Pū. ( using the robust value function from the following relation:
P Rig) arg min Ty v/
(P,R)eu
This also solved by LP.
3. (Policy Gradient Theorem) We now compute the RPG using policy gradient Theorem [26 w.r.t the adversarial values computed above,
Opu
Σ dop (8) Q Pz. (8. (Tz(a). 8.0
Observe that dy can be approximated as (xpP)" for large enough, and Qr can be approximated by dynamic programming [25 Notably, this step and the second step are negligible as compared to the first step.
Robust Value Iteration by LP
sa-rectangular robust MDPs. We first consider sa-rectangular L₁ upa = P x R. Robust Bellman operator is given by
constrained uncertainty
(Th max
min PEP
(r+ Em(d)O())
LP with 9 variable
Note that the above can be solved by LPs as uncertainty set set U.5h = P x R. induces linear constraint
and the objective is also linear with S variables. Hence, evaluation of Tip. requires solving SA LPs with S variable each.
s-rectangular robust MDPs. We now consider s-rectangular L1 constrained uncertainty set U5 = x R. Robust Bellman operator given by
v)(s)
min PEP,,TER,
Σ (T(()) r(a)) Ep(d(()o(s)}
LP with SA variable
Note that the above can be solved by one LP as uncertainty set U4 = P x R induces linear constraint and the objective is also linear with S.A variables. Hence, evaluation of 7 requires solving LPs with S.A variable each.
25


Reviews:
[{"review_id": "LVpz4pt3JJ", "reviewer": "Reviewer_2g5m", "summary": "This present studied robust policy gradient to solve rectangular robust Markov decision process, where the authors provide a closed-form expression for the worst case of reward model and transition kernel. The provided explicit form of the robust policy gradient can be estimated from data with the same time complexity as its non-robust equivalent. ", "questions": "- Can authors give me a concrete example or explanation of the difference of the risk-averse approach and robust RL? the uncertainty set you mentioned?", "limitations": "NA", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "- Instead of previously performing max-min optimization approaches, this paper presents a closed-form expression for the worst case kernel and reward estimation; thus we can achieve similar time complexity. \n\n- Empirical experiments demonstrate that the new proposed method can achieve similar complexity as non-robust settings, make the algorithm more practical than previous ones. \n\n- The main part of the paper is easy to follow and understand the main idea. ", "weaknesses": "- The techniques mainly replies on the properties of the normed-ball structure of the uncertainty set, I am not sure how practical it is in realistic settings such as continuous policy optimization?\n\n- it is still unclear for real-world scenarios, how the method or the idea can be leveraged to derive a computational efficient and practical algorithm. To me, it seems that to get the optimal reward and kernel, it is quite difficult to estimate from empirical samples (continuous case). ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> *\"Leveraging the method to derive a computationally efficient and practical algorithm in continuous policy optimization\"*\n\nWe thank the reviewer for the constructive remark. \n\nIn fact, one of the goals in this work is to develop building blocks for robust continuous control. The derivation of an explicit robust policy-gradient is a first step towards this goal. On the one hand, our RPG provably trains a robust optimal policy (as opposed to the reward-robust model in [3] or $r$-contaminated kernel-robust model in [27]). On the other hand, it avoids the expensive convex optimization solvers required to find the worst MDP model [26]. Yet, we agree that some challenges remain in our RPG formulation, in particular how to estimate the occupancy measure $d^\\pi_\\{P_0, u^\\pi_\\{\\mathcal{U}}}$ (see l. 218-222). Importance sampling may be used here, but we leave this for future work. \n\nAs a final note, previous works that proposed to train a robust policy in a model-free setting either restricted to discrete control [15, I] or focused on a specific type of robustness criterion [3, 4, 27]. We  believe that devising an efficient RPG method with theoretical grounding paves the path towards more applications to robust continuous control. \n\n\n> *\"A concrete example or explanation of the difference of the risk-averse approach and robust RL?\"*\n\nWe believe the reviewer refers to lines 72-75, where we briefly explain the difference between the two settings: the risk-averse approach focuses on the **aleatoric uncertainty**, i.e., the uncertainty internal to the system's stochasticity. Whereas the robust setting tackles the **epistemic uncertainty** due to ambiguity in the model. We further clarify this below. \n\nRisk-averse RL aims to overcome the **variability** of the return. For example, a mean-variance objective would aim to maximize return under variance constraints, or dually, minimize variance under minimal performance constraints. The moments considered there are taken with respect to one environment dynamics and reward model. General risk measures similarly formulate various probabilistic constraints under one fixed distribution. \n\nDifferently, robust RL tackles **adversarial** outcomes in the return. Thus, a robust agent would maximize return under the worst environment dynamics. This is where the uncertainty set plays a role, as it defines over what set of environments to judge which is worst: if it is reduced to a singleton, we would recover the standard RL objective; whereas if it is a set of properly perturbed versions of the true environment, we would recover a risk-averse objective [23]. In the robust MDP case, the uncertainty set can be arbitrary provided that it is convex and rectangular.\n\nTo give further intuition, consider a fully deterministic MDP, i.e., with deterministic transition and reward functions. In this setting, a risk-averse objective would necessarily reduce to a standard expected utility, whereas through its uncertainty set, the robust objective can address changes in the dynamics and/or the reward function (both being possibly stochastic). Although compatible (one may combine risk averseness with robustness in the objective function), the two approaches are different. \n\n[I] Derman, Esther, et al. \"Twice Regularized Markov Decision Processes: The Equivalence between Robustness and Regularization.\" arXiv preprint arXiv:2303.06654 (2023)."}, {"review_id": "a6R62VTvLq", "reviewer": "Reviewer_qyVV", "summary": "This paper develops policy gradients for robust MDPs, and proves several interesting properties of the worst-case kernel and occupancy measure along the way. The paper also shows that the robust Bellman operator is just the vanilla Bellman operator, with regularization of the vector's generalized variance function. The key result is a robust gradient expression that only depends on nominal samples. ", "questions": "1. Why is there a p-norm on a scalar in def. of R_{(s,a)}? \n2. In Sec 3.2.1., what if the perturbation has a negative entry, which could possibly make P_0 + P have negative entries as well? This is not so unrealistic if P_0 has small entries somewhere.\n3. Can this result generalize to convex uncertainty sets, or does it crucially rely on the uncertainty set being a lp ball? \n4. Looking at Table 1, is the main benefit of this work a better time complexity, rather than the ability to learn better policies? Convex optimization approaches that guarantee global optimum seem to only be worse in terms of time complexity. \n\n", "limitations": "Please see questions/weaknesses.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. Except the large amount of newly introduced notation, this paper seems polished and well written.\n2. Good discussion on time complexity, which is often absent from many prior works but crucially important for robust MDPs. \n3. The proposed method only requires samples from the nominal data distribution, and appears more computationally efficient than prior convex optimization approaches.\n", "weaknesses": "1. Notation is a bit hard to follow and is defined all over the place throughout section 3. It would be helpful to have a centralized place where all notation is defined.\n2. There is no \"convergence to local/global optima\" result.\n3. The experimental results only show running time, but does not evaluate the robust MDP performance of the learned policies. Do all methods end up learning the same robust optimal policies? ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We first thank the reviewer for the constructive remarks. \n\n> *\"Notation is a bit hard to follow and is defined all over the place throughout section 3. It would be helpful to have a centralized place where all notation is defined.\"*\n\nThank you for the suggestion. Although we tried to centralize it as much as possible, we wanted to put notations into context, which may have turned out to be too spread throughout the text. \nYet, we agree that some definitions could appear in the Notation paragraph rather than in the middle of Sec. 3. For example, the definition of the variance and the mean function is general enough to move it to the Notation section. Perhaps also the regularization function $\\Omega_q$ defined in Prop. 3.1. We will do that in the final version and centralize notations more carefully.\n\n> *\"There is no \"convergence to local/global optima\" result.\"*\n\nRobust policy gradient has recently been shown to converge to a global optimum in [26]. Global convergence of our RPG method thus follows. This is hinted at in lines 92-96 and lines 147-151. We will emphasize this more clearly in the final version.\n \n> *\"The experimental results only show running time, but does not evaluate the robust MDP performance of the learned policies. Do all methos end up learning the same robust optimal policies?\"*\n\nYes, they do. For a given nominal MDP and uncertainty set, all baselines should end up learning the same robust optimal policy. Our RPG distinguishes itself from other methods by its computational efficiency (see also our last answer below).\n\n> *\"Why is there a p-norm on a scalar in def. of R_{(s,a)}?\"*\n\nThe reviewer is correct. Although it appears for consistency, the p-norm notation is redundant there. We will remove it and write $|r| \\leq \\alpha_{s,a}$ instead. \n    \n> \"*In Sec 3.2.1., what if the perturbation has a negative entry, which could possibly make P_0 + P have negative entries as well?*\"\n\nAgain, the reviewer is correct: even when all entries of $P_0$ are positive, they could be so small that $P_0 + P$ may have negative entries, and the uncertainty set possibly includes absurd MDP models. \n\nIn fact, as with many existing works on robust MDPs [10, 17, 28], we tackle the constrained optimization problem without caring about the realizability of all constraints. Moreover, uncertainty sets are generally based on statistical confidence intervals [28]. Although these may include absurd MDP models and lead to unnecessarily conservative behavior, the robust approach holds generalization guarantees. \n\nIn that respect, our sentence \"the noise radius $\\beta$ should be small enough so that transition kernels of the form $P_0 + P$ are well defined\" (l. 129-130) is misleading. Although all $P_0 + P$ should ideally be well-defined to obtain possibly less conservative behavior and more realistic uncertainty, robust RL methods do not rely on this assumption. Instead, they address the optimization problem regardless of whether or not all kernels in the uncertainty constraints are meaningful. \n\n>*\"Can this result generalize to convex uncertainty sets, or does it crucially rely on the uncertainty set being a lp ball?\"*\"\n\nOur result crucially relies on the 'rank-one-perturbation structure' of the worst transition kernel (Lemma 4.4). The $\\ell_p$-ball uncertainty implies such property, which we establish in Thm. 4.6. However, whether any convex uncertainty set leads to the worst transition kernel being a rank-one perturbation of the nominal remains an open question. In fact, it would be interesting to investigate the structural properties needed on the uncertainty set for the rank-one perturbation to hold. We thank the reviewer for this remark. \n\n>\"*Looking at Table 1, is the main benefit of this work a better time complexity, rather than the ability to learn better policies? Convex optimization approaches that guarantee global optimum seem to only be worse in terms of time complexity.*\"\n\nThe reviewer is correct: this work's main benefit is providing a substantially better time complexity than existing RPG methods. Like previous studies on robust policy gradient, our algorithm converges to an optimal robust policy (global optimum, see [26]). However, it does so within a much lower time complexity. This point is critical, as most robust RL methods cannot scale to deep domains because of their computational burden, whereas they provably ensure more stable behavior. \n"}, {"review_id": "fdq3SklSfS", "reviewer": "Reviewer_rkBw", "summary": "The paper presents a policy gradient method for solving rectangular-robust MDPs. They propose closed forms for the worst-case reward and transition models. They also present robust Q-value forms that can be efficiently updated by a proper Bellman operator. Furthermore, they show an expression for the robust policy gradient that matches the non-robust PG complexity, and is therefore very fast. ", "questions": "I would like the authors to address the points I raised in the Weaknesses section, even though they don't point to any fundamental short-comings in the paper.", "limitations": "The paper portrays a fair description of its limitations. This includes, but isn't limited to, (1) the second paragraph of discussion (Lines 304-311), (2) Lines 262-267, and (3) Lines 218-222.", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "The paper targets a specific problem, and is very well-written. I applaud the authors for their valuable work, and enjoyed reading through the paper without any significant issues. The notation used for the theory is standard and appropriately compact, and the theory itself is clear and insightful. The computational efficiency obtained by the proposed method is both supported by theory, and also shown to be significant-enough in practice. This proves, once again, that a well-tailored algorithm can produce significant speed-ups over generic solvers (e.g., linear programming or convex optimizers).", "weaknesses": "While this is a minor point, I think the authors could slightly increase external references and elaborate more to help (an otherwise unfamiliar) reader follow through the content. For instance, (1) in Line 100, it would only take the authors a few words to reference this inequality as the Holder inequality, (2) provide a second common name for terms (such as the credal set for the probability simplex, or the visitation frequency for the occupation measure), (3) briefly derive simple results with the proposed notation (e.g., the gamma-contraction property in Line 118). These are only a few examples, and will mostly help the reader warm-up and get comfortable with the derivations before jumping into the core part of the paper.\n\nAlso, while I understand that this is out of the scope of the paper, but due to its importance I should mention it. The authors could possibly comment deeper about the resiliency of their proposed approach to stochastic approximation. While there is some limited discussion in the paper (e.g., Lines 218) about this point, I would like this point to be discussed in more length. If in future, this method is adapted to a more realistic or model-free setting, it would be valuable to have the authors comment on the statistical aspects of this approach.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the positive feedback. \n\n> *\"slightly increase external references and elaborate more to help (an otherwise unfamiliar) reader follow through the content\"*\n\nThank you for the suggestion. We will go over the text thoroughly to elaborate more on the wording and the mathematical derivations. \n\n> *\"comment deeper about the resiliency of [the] proposed approach to stochastic approximation\"*\n\nWe agree with the reviewer, as the main objective of our work is to eventually enable the applicability of robust RL to more realistic settings. As mentioned in lines 218-222, the remaining challenge in our approach is to estimate the occupation measure $d^\\pi_\\{P_0, u_\\{\\mathcal{U}}^\\{\\pi}}$. We may use importance sampling techniques, but as in any off-policy approach, we need to control variance and bias here. This is an interesting direction that we leave for future work. Other points worth being checked theoretically and empirically are the sensitivity of RPG to the learning rate and to the step size in the policy parameters. \n\nFollowing the reviewer's suggestion, we will include more of this discussion in the final version.\n\n\n"}, {"review_id": "5STCwBqTip", "reviewer": "Reviewer_c24r", "summary": "This paper proposes the robust policy gradient (RPG) algorithm as an efficient approach to solve rectangular RMDPs. The results are based on an explicit characterization of $\\ell_p$-ball-constrained RMDPs, where the worst-case kernel can be viewed as a rank-one perturbation of the nominal kernel and the worst-case occupation frequency can also be written in closed form, so that the well-known policy gradient theorem can still be applied to calculate the sub-gradient for the RMDP. It is further pointed out in the appendix that these results are all closely related to a fundamental characterization of a constrained inner product minimization problem. The paper also redefines the robust value functions using the worst-case kernel, and shows its equivalence with the common definition in literature, so that it comes up with a more efficient way to calculate the value function of RMDPs, which constitutes as the last piece for evaluating the sub-gradient. Numerical simulations are presented to show the efficiency of the proposed algorithm.", "questions": "1. The reviewer urges the authors to design better experiments to show both the running time and the performance of the proposed RPG algorithm against a few other baseline algorithms. Results should ideally be presented in the form of figures.\n2. In the introduction, [14] seems to be closely relevant to this paper, yet it is not discussed in details in the related works section, and nor does it appear in the table. How does this work compare with [14]? And how about the efficiency of the algorithm proposed in [14]?", "limitations": "The paper discusses about its limitations and future work in a satisfactory way.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The flow of this paper is very good. It provides the reader with enough background information to understand the framework, and the final algorithm naturally builds upon the building blocks established in the first few sections so that the readers can easily acquire the intuition.\n2. The paper consists of a thorough literature review that justifies the place of this result in the spectrum of related works. The reviewer particularly appreciates the table presented in Section 2 that compares the contributions a full range of related works.\n3. The contribution of this work is significant as viewed by the reviewer, in that it is among the first to apply policy gradient methods to solve RMDPs. The algorithm is presented with theoretical complexity guarantees, and the paper also discusses more efficient LP-based algorithms  in the $\\ell_1$-constrained special case, which adds to the applicability of the algorithm.\n4. The mathematical proofs seem correct to the reviewer in the form they are presented in the paper. (Note: since the proof cites quite a few theorems from e.g. [12], the reviewer took those published results for granted and didn't bother to check them.)", "weaknesses": "1. The numerical experiments seem relatively crude and incomplete, and the results are not convincing as viewed by the reviewer. The authors do not release the code for the simulations, and nor do they describe the settings in detail so that the results can be replicated. The presentation of results only focuses on running time but says nothing about the policy found by the algorithm, nor are they compared to any SOTA baselines. Experiments seem to be repeated with different random seeds, yet the deviation is only roughly reported in the appendix. Finally, figures cannot be found anywhere! The reviewer will be more positive if the results are more concrete, visualized, and reproducible.\n2. This paper cites a lot of results from previous work like [12]. Readers unfamiliar with it (like me) may sometimes find it very uneasy to handle these cited results which basically scatter across the whole paper. It is advisable to have an independent preliminaries section that explains what is done in [12] and why we need them here.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> *\"numerical experiments seem relatively crude and incomplete\"* \n\nFor each experiment, we fixed a state-space size and an action space size. An environment was generated by readily sampling a transition kernel and a reward matrix with proper dimensions. This was taken as an input to RPG or LP-RPG. A table with all parameters, including those that do not appear in the appendix, can be found below: \n\n| Parameter  | Value |\n| ----------- | ----------- |\n| discount factor $\\gamma$ | 0.9        |\n| initial distribution $\\mu$ | uniform      |\n| $\\epsilon$ tolerance error for policy evaluation      | 1e-4    |\n| learning rate for RPG update | 1e-3        |\n| number of RPG iterations | 3000        |\n| $\\alpha$-radius (constant for all states/state-action pairs)  | 0.1        |\n| $\\beta$-radius (constant for all states/state-action pairs)  | 0.01  $\\cdot(\\lvert\\mathcal{S}\\rvert\\lvert\\mathcal{A}\\rvert)^{-1}$ |\n\nAs mentioned in the appendix, the std was <10% for all the experiments, and in most cases between 1 and 2%. We avoided writing the exact values to make the result tables more readable. However, following your suggestion, we will display the exact std for each of our experiments in Tabs. 3 and 4.\n\nWe additionally ran RPG ($s$ and $(s,a)$-rectangular cases), together with a classical PG baseline. The convergence plot can be found in the following link:\nhttps://www.dropbox.com/scl/fi/w0ob97xgejwxon6ccozbq/rpg_methods_s50a20seed50.png?rlkey=eb4dqawr38k2oobsjlppl2712&dl=0\n\nThe green plot labeled 'nr' corresponds to the non-robust PG; the blue line is RPG on $s$-rectangular balls for the $\\ell_2$-norm, whereas the orange plot represents its $(s,a)$-rectangular version. \n\nAs we can see in the figure, the number of iterations required for RPG to converge is similar to that of PG. The performance of RPG upon convergence is slightly lower than PG, because the robust approach induces some conservativeness. In that respect, the performance in the $(s,a)$-case is slightly lower than the $s$-case, which confirms the additional conservativeness of $(s,a)$-rectangularity.\n\nWe will add RPG's pseudo-code in the final version and release the full code upon publication. \n\n\n\n> *\"This paper cites a lot of results from previous work like [12]. Readers unfamiliar with it (like me) may sometimes find it very uneasy to handle these cited results which basically scatter across the whole paper. It is advisable to have an independent preliminaries section that explains what is done in [12] and why we need them here.\"*\n\nWe apologize for the lack of comprehensiveness and provide further explanation below. \n\nThe work [12] refines the results of [3]. In both works, the motivation is to reduce the computational cost of robust dynamic programming. They do so using regularization, a well-known technique of robustification in supervised learning. More precisely, [3] establishes an equivalence between robust Bellman updates and regularized ones with a properly defined regularization function. \n\nYet, when it comes to normed-ball ambiguity sets, the authors in [3] occult the simplex constraints in the transition uncertainty. This may lead to unneeded conservativeness: if not intersected with the simplex, ball-constraints alone may include elements that are not transition kernels while the learned policy accounts for them in the inner minimization. [12] fills this gap, so the value regularizer $\\lVert v\\rVert$ of [3] becomes $\\kappa_q(v)$ in [12].\n\nThese results are needed in the policy gradient derivation. In order to avoid solving an optimization problem at each gradient step of RPG (as proposed in [26]), we leverage the equivalence between robust RL and regularized RL established in [3, 12] to speed-up RPG updates. \n\nWe will include these details in the final version of this work. \n\n\n> *\"In the introduction, [14] seems to be closely relevant to this paper, yet it is not discussed in details in the related works section, and nor does it appear in the table. How does this work compare with [14]? And how about the efficiency of the algorithm proposed in [14]?\"*\n\nThe work [14] provides a convergence proof of robust policy mirror descent, which is different from our contribution. Moreover, full access to the gradient is assumed in [14], whereas we provide an explicit expression of RPG that can be estimated from data. Also, Li et al. [14] focus on $(s,a)$-rectangular uncertainty sets, while we additionally study robust policy optimization in the $s$-rectangular case. In fact, their restriction to the $(s,a)$-case prevents us from transposing their analysis to our setting. This is due to the fact that the standard robust Bellman operator on $Q$-functions can no longer be applied on $s$-rectangular sets. \n\nAs of [26], it proves convergence of RPG with a sample complexity of  $O(\\frac{1}{\\epsilon^4})$. This result holds for arbitrary uncertainty sets as long as there is an oracle access to robust policy gradient. Otherwise,  the method they propose to compute the gradient is much more expensive and not scalable. "}, {"review_id": "STUvtEmoEr", "reviewer": "Reviewer_bn4R", "summary": "The paper investigates policy gradient methods in the context of unknown transition kernels in Markov Decision Processes (MDPs). The authors focus on a robust approach, where the uncertain transition kernel is assumed to lie within a specific uncertainty set, known as a rectangular uncertainty set. The authors address the computation of robust policy gradients in this setting, aiming to achieve the same time complexity as in the non-robust case.", "questions": "1) See the two questions raised as weaknesses?\n2) Uncertainty sets are often chosen with the goal to achieve some statistical properties of the learned solution (here policy gradient). Is there a statistical motivation for choosing the specific uncertainty set you choose? Or in other words, why not choosing another uncertainty set than the one you chose?\n3) In Section 3.1, what is the relation between $k$ and $\\mu$?\n4) How do you choose the radius $\\beta$?\n5) What is the motivation/justification for $\\mathcal{U}$ being convex?\n6) Line 106 has a typo. Should be $(P,R)$", "limitations": "1) Uncertainty set modelling is a) not well motivated and b) it seems rather restrictive. Please see the questions and points raised above.\n\n", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "The combination of policy gradients with robust MDPs is an interesting and practical approach with promising initial results. The paper is well-written and accessible, making it relatively easy to understand.", "weaknesses": "There are a couple of issues regarding the modelling of the uncertainty set:\n1) In Section 3.2.1 it is written that the radius $\\beta$ of the uncertainty set should be “small enough” such that transition kernels of the form $P_0 + \\mathcal{P}$ are well defined. This, however, requires the nominal transitions kernel $P_0$ to be strictly positive everywhere. Moreover, small positive values of $P_0$ are also not enough. Therefore, this modelling seems highly restrictive - particularly for high-dimensional settings.\n2) The motivation for using rectangular ambiguity sets is not clear. In practice, ambiguity sets are often non-rectangular and derived from principles like maximum likelihood estimation. Could the method handle more general uncertainty sets?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": ">*\"In Section 3.2.1 it is written that the radius of the uncertainty set should be “small enough” such that transition kernels of the form are well defined. This, however, requires the nominal transitions kernel to be strictly positive everywhere...this modelling seems highly restrictive\"*\n\nWe apologize for the confusion this sentence has caused. We also agree that $P_0$ may have so small values that the uncertainty set would most likely include absurd MDP models. However, our results do not require all $P_0+P$-s in the uncertainty set to be well-defined. \n\nLike any existing work on robust MDPs [10, 17, 28], we treat an optimization problem under uncertainty set constraints. This approach does not question or rely on the realizability of all MDPs in the uncertainty set. Although all $P_0 + P$ should ideally be well-defined to obtain possibly less conservative behavior and more realistic uncertainty, robust RL methods do not rely on this assumption. Instead, they address the optimization problem regardless of whether or not all kernels in the uncertainty constraints are meaningful.\n\nMoreover, uncertainty sets are generally constructed based on statistical confidence intervals [28]. Although these may include absurd MDP models and lead to unecessarily conservative behavior, they concurrently hold generalization guarantees [29]. \n\n>*\"The motivation for using rectangular ambiguity sets is not clear. In practice, ambiguity sets are often non-rectangular and derived from principles like maximum likelihood estimation. Could the method handle more general uncertainty sets?\"*\n\nWe agree that ambiguity sets are non-rectangular in practice. In fact, this assumption is required to compute a worst model within polynomial time [28]. Solutions that relax this condition have been proposed in [I, II, III], but each one relies on a specific structure of the coupling. On the other hand, the $s$-rectangularity assumption is well-established in the robust RL literature [1, 3, 7, 8, 24]. Although relaxing it while preserving tractability would lead to more realistic solutions, it would deserve a full study on its own that goes beyond the scope of our work. Still, the construction of ambiguity sets from maximum likelihood estimation is compatible with rectangularity, and is actually described in [28, Sec. 5.2], [17, Sec. 5] and [10, Sec. 4]. \n\n>*\"In Section 3.1, what is the relation between $k$ and $u$.\"*\n\nThe variable $k\\in\\mathbb{R}^{\\mathcal{S}}$ is just used as a general notation in the definition of state visitation $d_{P,k}^{\\pi}$. In our specific framework, $k$ is either the initial state distribution $\\mu$ (first term in Eq. (3)), or the normalized robust value $u_{\\mathcal{U}}^{\\pi}$, i.e., \n$d^\\pi_\\{P,u^\\pi_{\\mathcal{U}}}=(u^\\pi_{\\mathcal{U}})^\\top(\\mathbf{I}_\\{\\mathcal{S}}-\\gamma P^\\pi)^\\{-1}$ (second term in Eq. (3)). \n\n>*\"How do you choose the radius?\"*\n\nThe radius choice goes alongside the uncertainty set construction. As such, it is a challenging question that deserves its own analysis. Intuitively, the smaller the radius value, the less robust its optimal policy. On the other hand, if the radius is too large, the learned policy can be overly conservative. Therefore, determining the size of the uncertainty set leads to a robustness-conservativeness dilemma. Solutions that tighten the radius have been proposed in [IV]. Other approaches that update the uncertainty set online and adapt to incoming data can also be found in [V, VI]. However, these works tackle the conservativeness of robust policies, while we address the tractability of robust learning. \n\n>*\"What is the motivation/justification for $\\mathcal{U}$ being convex?\"*\n\nThe uncertainty set needs to be convex for computational reasons. Without convexity, the inner minimization problem (robust policy evaluation) or alternatively, the computation of the worst case model may be NP-hard (see [28, Table 1] and Table 1 in our work). The convex property is not hard to satisfy in practice, as uncertainty sets are generally constructed based on statistical confidence intervals or divergence constraints such as KL. \n\n>*\"Line 106 has a typo. Should be $(P, R)$\"*\n\nRight. We will fix this together with the two previous equations where we notice the same typo. \n\n\n\n**Additional references:**\n\n[I] Mannor, Shie, Ofir Mebel, and Huan Xu. \"Robust MDPs with k-rectangular uncertainty.\" Mathematics of Operations Research 41.4 (2016): 1484-1509.\n\n[II] Mannor, Shie, Ofir Mebel, and Huan Xu. \"Lightning Does Not Strike Twice: Robust MDPs with Coupled Uncertainty.\" ICML (2012).\n\n[III] Goyal, Vineet, and Julien Grand-Clement. \"Robust Markov decision process: Beyond rectangularity.\" arXiv preprint arXiv:1811.00215 (2018).\n\n[IV] Petrik, Marek, and Reazul Hasan Russel. \"Beyond confidence regions: Tight Bayesian ambiguity sets for robust MDPs.\" Advances in neural information processing systems 32 (2019).\n\n[V] Lim, Shiau Hong, Huan Xu, and Shie Mannor. \"Reinforcement learning in robust Markov decision processes.\" Advances in Neural Information Processing Systems 26 (2013).\n\n[VI] Derman, Esther, et al. \"A Bayesian approach to robust reinforcement learning.\" Uncertainty in Artificial Intelligence. PMLR, 2020."}]

Author rebuttal:

Meta-review: This paper studies policy learning for robust MDPs with rectangular uncertainty sets (which allow the solution to be characterized by a robust Bellman equation) and develops a policy gradient approach. The paper is well executed, clear, interesting, and addressing a specific problem, as recognized by the reviewers. There was some hesitance on the significance with only weak recommendations but there was uniform agreement the paper is valuable. I concur with that consensus.
Decision: Accept (poster)