Natural Actor-Critic for Robust Reinforcement Learning with Function Approximation
Authors: Ruida Zhou
Tao Liu
Min Cheng
Dileep Kalathil
Panganamala Kumar
Chao Tian
Venue: NeurIPS 2023 poster (2023)
Keywords: robust reinforcement learning
policy-based approach
function approximation
actor-critic
TL;DR: We propose a robust natural actor-critic approach with provable guarantee and experimental advantages for robust reinforcement learning employing function approximation.

Abstract: We study robust reinforcement learning (RL) with the goal of determining a well-performing policy that is robust against model mismatch between the training simulator and the testing environment. Previous policy-based robust RL algorithms mainly focus on the tabular setting under uncertainty sets that facilitate robust policy evaluation, but are no longer tractable when the number of states scales up. To this end, we propose two novel uncertainty set formulations, one based on double sampling and the other on an integral probability metric. Both make large-scale robust RL tractable even when one only has access to a simulator. We propose a robust natural actor-critic (RNAC) approach that incorporates the new uncertainty sets and employs function approximation. We provide finite-time convergence guarantees for the proposed RNAC algorithm to the optimal robust policy within the function approximation error. Finally, we demonstrate the robust performance of the policy learned by our proposed RNAC approach in multiple  MuJoCo environments and a real-world TurtleBot navigation task.

Natural Actor-Critic for Robust Reinforcement Learning with Function Approximation
Ruida Zhou" Texas A&M University ruidaOtamu. edu
Tao Liu" Texas A&M University tliu@tamu, edu
Min Cheng Texas A&M University
minrara04040tamu edu
Dileep Kalathil
P. R. Kumar Texas A&M University prk@tamu. edu
Chao Tian
Texas A&M University dileep. kalathillll wwwaaathil@aau....mmmmmmmmm edu
Texas A&M University chao. aeao.tia@tti tian@tau.. edu
Abstract
We study robust reinforcement learning (RL) with the goal of determining a well- performing policy that is robust against model mismatch between the training sim- ulator and the testing environment. Previous policy-based robust RL algorithms mainly focus on the tabular setting under uncertainty sets that facilitate robust pol- icy evaluation, but are no longer tractable when the number of states scales up. To novel uncertainty set formulations,
this end, propose sampling and the other on an integral probability metric. Both make large-scale robust RL tractable even when one only has access simulator. We propose robust natural actor-critic (RNAC) approach that incorporates the new uncertainty and employs function approximation. We provide finite-time convergence guarantees for the proposed RNAC algorithm to the optimal robust policy within the function approximation error. Finally, we demonstrate the robust performance of the policy learned by our proposed RNAC approach in multiple MuJoCo envi- ronments and a real-world TurtleBot navigation task.
based double
Introduction
Training a reinforcement learning (RL) algorithm directly on a real-world system is expensive and potentially risky due to the large number of data samples required to learn a satisfactory policy. To overcome this issue, RL algorithms are typically trained on a simulator. However, in most real- world applications, the nominal model used in the simulator model may not faithfully represent the real-world system due to various factors, such as approximation errors in modeling or varia- tions in real-world parameters over time. For example, the mass, friction, sensor/actuator noise, and floor terrain in a mobile robot simulator may differ from those in the real world. This mis- match, called simulation- ceatiiiontt--rallin to-reality-gap. can significantly degrade the performance of standard RL algorithms when deployed on real-world systems [36] 44 55 51] The framework of robust Markov decision process (RMDP) 19 40) is used model this setting where the testing environment is uncertain and comes from uncertainty set around the nominal model. The optimal robust policy defined as the one which achieves the optimal worst-case performance over all possible models in the uncertainty set. The goal of robust reinforcement learning is to learn such an optimal robust policy using only data sampled from the simulator (nominal) model.
The RMDP planning problem has been well studied in the tabular setting 63 many works have developed model-based robust RL algorithms in the tabular setting
62 35
46
[6]
Also.
66
69
42
'The first two authors contributed equally.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

64 49], focusing on sample complexity, Many robust O-learning algorithms -5 33
39
[5
30
and policy gradient methods for robust RL [6 27 29 58 17 have been developed for the tabular
setting. Different from all these works, the main goal of this paper is to develop a computationally tractable robust RI. algorithm with provable convergence guarantees for RMDPs with large state spaces, using linear and nonlinear function approximation for robust value and policy.
One of the main challenges of robust RL with a large state space is the design of an effective un- certainty set that is amenable to computationally tractable learning with function approximation. Robust RL algorithms, both in their implementation and technical analysis, require robust Bell- man operator evaluations [99 40] which involve an inner optimization problem over the uncertainty set. Performing this inner optimization problem and/or getting an unbiased estimate of the robust Bellman operator evaluation using only the samples from the nominal model can be intractable for commonly considered uncertainty sets when the state space is large. For example, for f-divergence- based uncertainty sets [[6 69 64, 49
33 30), the robust Bellman operator estimate requires solving for a dual variable associated with each state, which is prohibitive for large state spaces. For R- contamination [61]. the estimate requires calculating the minimum of the value function over state space, which is impractical for large state spaces. It is also infeasible for ép norm-based uncertainty sets 127], where the estimates require calculating the median, mean, average peak of the value function depending on the choice of p. Robust RL with function approximation has been explored in a few works [53] 41 45 43 60, 6). However, these works explicitly or implicitly assume an oracle that approximately computes the robust Bellman operator estimate, and the uncertainty set design that facilitates computation and learning is largely ignored. We overcome this challenge by intro- ducing two novel uncertainty set formulations, one based on double sampling (DS) and the other on an integral probability metric (IPM). Both are compatible with large-scale robust MDP, with the robust Bellman operators being amenable to unbiased estimation from the data sampled from the nominal model, enabling effective practical robust RL algorithms.
Policy-based RL algorithms [47 31 [8 15), which optimize the policy directly, have been extremely successful in learning policies for continuous control tasks. Value-based RL approaches, such as Q- learning, cannot be directly applicd to continuous action problems. Moreover, recent advances in policy-based approaches can establish finite time convergence guarantees and also offer insights into the practical implementation [3] 37 4 8]. However, most of the existing works on robust RL with
function approximation use value-based approaches (53 41 45 43
60
34 that are not scalable to
continuous control problems. On the other hand, the existing works that use policy-
methods
for robust RL with convergence guarantees close this important gap in the literature by developing a novel robust natural actor-critic (RNAC) approach that leverages our newly designed uncertainty sets for scalable learning.
limited to the tabular setting [61 27 29 [88 17). We
Summary of Contributions: (1). We propose two novel uncertainty sets, one using double sampling (Section 3.1 and the other integral probability metric (Section 3.2). which are both compatible for robust RL with large state space and function approximation. Though robust Bellman operators require the unknown worst-case models, we provide unbiased empirical robust Bellman operators that are computationally easy to utilize and only based on samples from the nominal model;
(ii). We propose novel RNAC algorithm (Section 4h which to the best of our knowledge is the first policy- approach for robust RL under function approximation, with provable convergence guarantees. We consider both linear and general function approximation for theoretical study, with the latter relegated to Appendix D due to space constraints. Under linear function approximation, the RNAC with a robust critic performing "robust linear-TD" (Section 55) and a robust natural actor performing "robust Q-NPG" (Section(6) is proved to converge to the optimal robust policy within the function approximation error. Specifically, O(1/=²) sample complexity can be achieved, or ((1==") for policy update with a constant step size. For the robust lincar-TD TD, we study the contraction behavior of the projected robust Bellman operator for RMDPs with the proposed uncertainty sets and the well-known f-divergence uncertainty sets, which we believe is of independent interest;
(ii)). We implement the proposed RNAC in multiple MuJoCo environments (Hopper-v3, Walker2d- v3, and HalfCheetah-v3), and demonstrate that RNAC with the proposed uncertainty sets results in robust behavior while canonical policy-based approaches suffer significant performance degrada- tion. We also test RNAC on TottleBot [5), real-world mobile robot, performing navigation task. We show that the Turtleoot with RNAC successfully reaches its destination while canonical non-
2

---

robust approaches fail under adversarial perturbations. A video of the demonstration on TurtleBot available at [Video Link] and the RNAC code is provided in the supplementary material.
Due to the page limit, a detailed literature review and comparison of our work with the existing robust RI. algorithms are deferred to Appendix
2
Preliminaries
For any set X, denote by | its cardinality, by Ax a (1 - 1 d-ddimnnsil probability simplex, and by Unif(X)) uniform distribution over X. Let [m] == (1,..., m.)
Notations:
Markov decision process (MDP) represented by tuple AS,A, where S is the state space, A is the action space, nel sequence with Kt : S A + As. r S A + [0.1] is the reward function, and E (0, I) is the discount factor. For stationary policy
(Ko, k1,...) is possibly non-stationary transition ker-
S + A.. its value func- tion is (s) == Ex, 1_ ""r(s;; (t)ss = =], where the expectation is taken w.rt. the tra- jectory (so, ao; $1, a1:...) with aelst Ts, and s441 0e) Ke, We can similarly define the state visitation distribution under initial distribution E As. (s) == (1 7) D 1 (s; s) p]: the state-action value function (Q function), (%(s,a) == Eg,7 IEE 7 a1) so = s, an = a], and the advantage function (7, a) == as
Robust MDP: A RMDP is represented by a tuple AS, where P is set of transition kernels known as the uncertainty set that captures the perturbations around the nominal stationary kernel pº : S x A > As, and its robust value function is defined as the corresponding worst case:
VT (s)
inf
V (s).
We will assume the following key (s, a) rectangullarit condition that is commonly assumed to fa- cilitate dynamic programming ever since the introduction of RMDPs 19. 40) Definition 1. P is (s, a) reectanngl,,, i s.a Ps.a-for some P.. S
The corresponding robust Bellman operator
T IRS + IRS is
(TTV))) Bawx(-le) (r(8, a) +7 inf p DT]. S VERS.
PEP...
and the Bellman equation for RMDPs is = TVV, where V V is its unique solution from the Banach fixed-point theorem. Typically, Pa.a is taken ball {v C As d(v, S 8} around nominal model p" of the training environment, where d(., -) is some divergence measure between probability distributions, and > 0 controls the level of robustness.
There is a stationary optimal policy n² that uniformly maximizes the robust value function, i.c., V (s) = sup (s): history dependent π }. vs 19 40). Thus, without loss of generality, we only need to optimize within stationary policies. Moreover, for any stationary policy æ there exists stationary worst-case kernel KG with V (s) = (*),,, Vs. We can define the robust Q-function and robust advantage function as (p,s, 1,5,0 a) = Q (s, a) and A5(s,a) == AT (s,a). a), respectively. When the uncertainty set is clear from the context, will omit the subscript P in V. Q7, and A
To summarize, the motivation the robust RL framework to learn the optimal robust policy by only training on a simulator implementing an (unknown) nominal model pº [53] 45| 41) with the robust RL algorithms only having access data generated from pº, and not from any other model in the uncertainty set P.
3 Uncertainty Sets for Large State Spaces
Evaluating the robust Bellman operator T requires solving the optimization inf p TVV. which is challenging for arbitrary uncertainty sets. Moreover, since we only have access to data generated by the nominal model p", estimating 7 not straightforward. Previously studied uncertainty sets, such as R-contamination, f f-divergence, and E, norm, are intractable for RMDPs with large state spaces for these reasons (see Appendix for detailed explanation). We therefore design two uncer- tainty sets for RMDPs where the robust Bellman operator has a tractable form and can be unbiasedly
3

---

estimated by the data sampled from the nominal model, thus making effective learning possible. We will also use function approximation tractably parameterize policy and value functions.
3.1 Double-Sampling (DS) Uncertainty Set
The central difficulty in employing the robust Bellman operator is how to evaluate infpeP... p V. Our first method is based on the following key idea for drawing samples that produce an unbiased estimate for it. Let {s), .i...; kn) be m samples drawn i.i.d. cording to the nominal model Pi Then, for any given divergence measure d(--)) and ra- dius 8 > O, there exists uncertainty set P = Ba,aPa.a such that infpep... p"V
P8.a jnn jinfa (nd Σ or (c() (See Appendix B.1 for brief explana-
*1.m "i
tion.) We therefore define an empirical robust Bellman operator T corresponding to 2 by Σ a, (s.))
(T (s, a, smm) = a(),a) +y
inf aed ml (m)(
Ts gives an unbiased estimate, which one key property we use in our robust RL algorithm. We refer to this as "double sam- pling" since > ax (s()) is the expected value when one further chooses one sample s' from (2,,, m according to the distribution on [m] and evaluates Vss'). Above, a is per- turbation of [m]]( and when 8 0, a [mi] and s' Ps.a- The uncertainty set P corresponding to the double sampling is implicitly defined by specifying the choices of m, d(::), and 8. Its key advantage is that samples can only be drawn according to the nominal model pº.
Since (T) = E
(T a, 1mm))
an)n(-le), si... 2x p2..
Double sampling requires sampling multiple next states for given state-action pair, which can be implemented if the simulator is allowed to set to any state. (All MuloCo environments (56) support DS.) Since the calculation of is within [m] the empirical robust Bellman operator is tractable for moderate values m. We use m 2 in experiments for training efficiency, where for almost all divergences d),,,)
explicitly write
(T, 8122) r(s, a) + (0.5(V(s)) + V(+6)) 8)V(s1) v(())))
(4)
Bellman completeness (value function class closed under the Bellman operator) is key property for efficient reinforcement learning. whereas RMDP with canonical uncertainty sets may violate it. We show in Appendix [B.I that for RMDP with DS uncertainty sets, the linear function approximation
class satisfies Bellman completeness the nominal model is a linear MDP 22
3.2 Integral Probability Metric (IPM) Uncertainty Set
Given some function class F RS including the zero function, the integral probability metric (IPM) is defined by (p 9) == su f-q" f} 2 0 (38. Many metrics such as Kantorovich metric, total variation, etc., are special cases of IPM under different function classes (38
requires solving the optimization infgeP... q TV. V. For an IPM-based uncertainty set with P s.a = {q dy(g,p?.a) 8). we relax the domain g E As to qss) as done in 28 27 which incurs no relaxation error for small 8 min a
The robust Bellman operator 7 V
0.
One should choose F so that it properly encodes information of the MDP and its value functions. We start by considering linear function approximation. Denote by v E Sxd the feature matrix with rows db (s), Vs E S. The value function approximation is V., = Vw E RRS. A good choice of feature vectors encodes information about the state and transition. For example, vectors (b(s), (ss') should be "close" when states s, s' are "similar" and (s), (s'( have small differences. We propose the following function class (with &a the preferred norm but any other be used);
(s (T)
Rd . ||E|l < 1).
(5)
Without loss of generality, assume has full column rank since d & |S]. and let the first coordinate of (s) be for any s, which corresponds to the bias term of the lincar regressor.
Proposition 1. For the IPM with F in 5 we have inf gT Vv (P) (T TV, V.. 8) 61|

---

Algorithm 1: Robust Natural Actor-Critic
Input: T, 7, K, N
Initialize: @ for policy parameterization and Wanit for value function approximation fort= 0att=0.....,
do
Robust critic updates w'; //E.g., w' (T K) Algorithm 2 Robust natural actor updates gz+ gf+l://E.gg. g = RQNPG (0", n",, w', N) Algori thm
We can thus design the empirical robust Bellman operator, which is an unbiased estimator of T with sample s' drawn from the nominal model:
(T,,))s,,, : r(s. +V - --6
Guided by the last regularization term the empirical robust Bellman operator (6). when consider- ing value function approximation by neural networks we add similar negative regularization term for the neural network parameters except for the bias parameter in the last layer.
Robust Natural Actor-Critic
We propose robust natural actor-critic (RNAC) approach in Algorithm[]for the robust RL problem. As its name suggests, there are two components a robust critic and a robust actor, which update alternately for 7 steps. At each step i, there is a policy x' determined by parameter 0'. The robust critic updates the value function approximation parameter w based on on-policy trajectory data sampled by executing r the nominal model with length K. The robust actor then updates the policy with step size 1/', and the critic returns w by on-policy trajectory data with length N. In practice, a batch of on-policy data can be sampled and used for both critic and actor updates.
We now give the main (informal) convergence results for our RNAC algorithm with linear function approximation and DS IPM uncertainty sets, where the robust critic performs robust lincar- TD and the robust natural actor performs robust-QNPG (as the comments in Algorithm [ The formal statements, proofs, and generalization general function approximation
given in Appendix E
Theorem (Informal linear convergence of RNAC). Under linear function approximation, RNAC in Algorithm with DS IPM uncertainty sets using an RLTD robust critic update and an RQNPG robust natural actor update, with appropriate geometrically increasing step sizes ny, achieves BVV= (p) V=² (p)) O(e-T)++ O(Estat) + O(Evia)) and Ó(1/=²) sample complexity.
The optimality gap bounded in this theorem via three terms, where the first term, related to the number of time steps T, is the optimization rate (linear convergence since O(e-f)), the second term Estat Ō V is statistical error that depends on the number of samples K, N in the robust critic and robust actor updates, and the last term ébias is the approximation error due the limited representation power of value function approximation and the parameterized policy class. Omitting the approximation eтror Cbias, the sample complexities for achieving ε robust optimal value are Ō(1/²²), which achieves the optimal sample complexity in tabular setting (64. However, RNAC with geometrically increasing step sizes induces a larger multiplicative constant factor (not shown in big-O notation) and does not generalize well to general function approximation. We then analyze RNAC with a constant step size.
Theorem 2 (Informal sublinear convergence of RNAC). RNAC under the same specification as in Theorem but with constant step size rÝ = r has E[V" (p) - -rD ---1v= (p) = 0 +
(EEsta)) (Evias), implying an Ö(L/E3) sample complexity.
Although the theorem shows a slower optimization rate RNAC with constant step size, this non- increasing step size is preferred in practice. Moreover, the analysis can be generalized to general policy class with optimization rate O(1/vT), and ((1/E4) sample complexity.
5

---

Algorithm 2: Robust Linear Temporal Difference (RLTD)
Input: K
Initialize: wo. 80 for k 1.... K do
Sample Og ~ (-118k); Vk+1 according to P and 8k+1 from yk++1
Update wk+11 = w/ + (s))(s)) (TT Vw, (sk, ak, Uk+1) (s*)) ( Tuk
// For DS: yk+1 $/.m i.id
Pie sk+1 Unif and T in (3)
// For IPM: yk+1 = Sk+1 ~ Payma and TØ in (6)
Return: WK
5 Robust Critic
The robust critic estimates the robust value function with access to samples from the nominal model.
the critic learns the Q function, while realistic implementations in on on-policy algorithms (c.g., proximal policy optimization (PPO)) treat the V function as the target of the critic for training efficiency. We consider a robust critic that learns the robust V function to align with such realistic implementations.
One may note that in many previous actor-critic analyses for canonical RL 66 29 9
We present the robust linear femporal difference (RLTD) Algorithm 2 which is similar to the canonical linear-TD algorithm, but with an empirical robust Bellman operator. It iteratively per- forms the sampling and updating procedures. The sampling procedure differs for the uncertainty set by double sampling and IPM as shown in the comments in Algorithm [ Using the samples, the parameter for the linear value function approximation V =ww is updated with step size on-
The following assumption is common [0 29]:
Assumption (Geometric mixing). For any policy n, the Markov chain {sk} induced by applying t in the nominal model pº is geometrically ergodic with a unique stationary distribution v".
The update procedure essentially minimizes the Mean Square Projected Robust Bellman Error MSPRBE" (w) || (TB Vww Viell.. where ||V||-= VE. Dat (s)? is the v weighted norm, and - (VVV D ạ)) y -p D* is the weighted projection matrix with D ddiagu>))
SSSS The minimizer of MSPRBE" (w), denoted by w",, is the unique solution of the projected robust Bellman equation VT = II T Vw. which equivalent to 0 = vp D=TTp w (ww) RLTD
is thus a stochastic approximation algorithm since the empirical operator tØ (3) or 6 is unbiased (b)) (T a, 3/) (ss) w| = v D" D"TTTV V. V.o).
with E (( ~or Moropp
To ensure that RLTD converges to the optimal linear approximation Van,, it is crucial that the pro- jected robust Bellman operator 11"TT be a contraction map with some 3 << 1.
Definition 2. IFT is a (-contraction w.E.. -1- [I V
S B|| V'
Unlike in linear TD for MDP 57 Tamar et al. 53 make an additional assumption (Assumption) 2 to establish the contraction property of TI (Proposition B for RMDP.
Assumption 2. There exists 3 E (0, 1) with ( < Bppp (s') Vs, s' E S, Va E A and Vp E P.
Proposition 2 (Prop.3 3 in [53 Under Assumption 2 1T a B-contraction w.r.t ||
The implicit uncertainty set P of double-sampling satisfies Assumption 2 for small 8, and thus guarantees contraction of TT. For example, for m = 2 as in a 8
< 2
1-7 is sufficient.
However, simply taking a small radius is not panacea for all uncertainty sets:
Proposition 3. For any [-divergence and radius > there exists a geometrically mixing nominal model such that the f-divergence defined uncertainty set violates Assumption 2
may not be necessary. The proposed IPM uncertainty set relates robustness and regularization with an explicit formula for ro- bust Bellman operator as in (6). The contraction behavior of IT for IPM uncertainty set can be established without Assumption
On the other hand, Assumption 2 though well-accepted 53 45

---

Lemma 1. For IPM uncertainty set with radius 8 < Amin ( D v) 1_2 there exists 3 < that T is 8-contraction mapping w.r.f. norm || -Ilm-.
Since the contraction of T obtained by RMDP under DS or IPM uncertainty sets with small radius 6, we have the first finite sample guarantee of RLTD by recent advances in Markovian stochas- tic approximation [10]:
Theorem (Informal convergence of robust critic: Details in Appendix C RLTD with step sizes og - (1//k satisfies Billux- w= - (
Robust Natural Actor
The robust natural actor updates the policy parameter 0 along ascent direction that improves the value via preconditioning through the KL-divergence KL(p, g) == (p, (og(p/4)). It has been well explored for natural policy gradient (NPG)-like algorithms, such as TRPO and PPO in canonical RL. The ascent direction is obtained by the policy gradient theorem in canonical MDP. We therefore first discuss the policy gradient for RMDP, where policy my is differentiably parameterized by 0.
The robust value V (p) =: J()) typically Lipschitz under proper parameterization [1] and therefore differentiable a.e. by Rademacher's theorem [14]. Where it is not differentiable, Fréchet
supergradient J of J exists if lim supgr-to
J(0)) J(0)
25 The following con-
[ tains the policy gradient theorem for canonical RL. as a special case:
Lemma (Policy supergradient). For a policy my that is differentiable w.r.t. parameter 0,
Eg tu Eawn, [Q" as log π (als)) B E [AT a.VaaVVo log x (a|s)
VOVT (p)
1-
1-
is Fréchet supergradient of V (p), where K2z is the worst-case transition kernel w.r.t.
exp(é(s,a) T 0)
We consider log-linear policies no (u(ss) E. oxp(o(s,a")" 0j. where c(s,a) E Rd is the feature vector and Rd is the policy parameter. (The general policy class is treated in Appendix D)
In canonical RI, the training and testing environments follow the same nominal transition pº. NPG updates the policy by 0
FF (0) Vo pa (p), where F0)t is the Moore-Penrose inverse omg. [V log (a(as) (Vo log (als)) J. An "equivalent" Q-NPG was proposed in B to update the policy by 0 + Q + mu', where w' arg min, (s.a))dd700 of I (s, a) - u ((s,a))²). Note that u determines a Q value func- tion approximation Q" a) = (fs, a) u. which compatible with the log lineer policy class 52 Since Q" contains the information on the ascent direction as suggested by Lemma 2 the Q-NPG update can be viewed as inserting the best compatible Q-approximation Q" for the policy,
of the Fisher information matrix (0) = E
(s.0)~aJo0p"
We adopt the Q-NPG to robust RL and propose the Robust Q-Natural Policy Gradient (RQNPG) (Algorithm 3). Note that unlike canonical RL, where Q can be estimated directly from a sample trajectory of executing æ in model pd, the robust Q" is hard estimate with samples from p². A value function approximation V. from the critic comes to help, as we can approximate the robust Q function via (s, a) r(s, a) + iinfpep... p V..., which exactly matches Q" if Vn, V The RQNPG obtains information on Q" by first approximating it via a critic value V.. Vur-guided function Qwi and then estimating 2. by a policy-compatible robust Q-approximation Q".
As shown in Algorithm 3 RQNPG estimates a compatible Q-approximation Q"N by iteratively performing sampling and updating procedures, where the sampling procedure follows that of the RLTD (Algorithm 2). The update procedure essentially approaches the minimizer u ==
arg min, (ss (s, - u a] by stochastic approximation with step size So
(stochastic gradient descent with Markovian data), since conditioned on (s, a), fz ( (6) is an unbiased estimator for the Q function approximation Q...
Now we look at specific update 0++1 RQNPG(0', .n',,""""" w', N) with G. @(1/n) where w (T K). The following theorem shows an approximate policy improvement property of the R RQNPG update:
7

---

Algorithm 3: Robust Q-Natural Policy Gradient (RQNPG)
Input: 0, 1); w. N Initialize: No, 80
for 0, 1,,,....N Sample On ~ To (.)) Un+1 according to Pen.ax and determine 8n+1 from Vn+1
do
Update Mn+1 un + Sn S5,, an) (w) on vn+11 0(5n. T Un
// For DS: Mn+1 $1mm Psnann sn+1 Unif and TØ in (3)
// For IPM: Ba++ 8841 1 ~ Penian and TB in (6)
Return: 9 + IJN
RNAC-PPOIDS)
PPO
Curriatie reeare
6530
3202
Cumulaativa
6020
2000
2302
1520
500
3020
1002
RNAC PPOIDS)
RNAC-PPOIDSI
500
PPO
-500
0.4
0.6
1.0
Jegnjoint Stffiness' (defaut=0.0))
Moot Joint stiftness'
(dlefaulbe0.0)
range
(a) Double sampling, Hopper
(b) Double sampling, Walker
(c) Double sampling, HalfChectah
RNAC-PRO(PPN)
5526
2500
PPO
Cumuative reeatd
3002
Cumulative raward
0020
2002
1000
2530
2502
3030
500
RNAC PPOUPM]
PNA(PP)O(PM)
1502
PPO
Weg_jointstiffnes (default=0.0)
10
20
39
foot jtifinnttiissss (default=0.0)
43
1.0 11t i 1 (x(+1, (x(+1xx*)
0.4
06
range
us
(d) IPM, Hopper
(e) IPM, Walker
(1 IPM, HalfCheetah
Figure 1: Cumulative rewards of RNAC- PPODS/PP) and PPO on (a-c) stochastic MuJoCo Envs and (d-f) deterministic MuJoCo Envs under perturbation.
Theorem 4 (Approximate policy improvement). For any t 2 O, we know
KL 2111 (T", 1 + KI.
Va-- (p) 2 V (p)
dp
(1 7)
where (T, == E, (()) 2 0 and E[es] = Ó + +x) + O(Ebiae).
Experimental Results
We demonstrate the robustness of our RNAC approach (Algorithm T with Double- Double-Sampling (DS) and IPM uncertainty sets on MuloCo simulation environments [56]. We also perform real-world evaluations using TurtleBot [5], mobile robot, on navigation tasks under action/policy perturba- tion. We implement practical version RNAC using neural network function approximation, with the robust critic minimizing squared robust TD-error and the robust natural actor performing a robust proximal policy optimization (PPO) (see Algorithm/ Appendix [ details). We call this RNAC algorithm as RNAC-PPO and compare it with the canonical PPO algorithm [48). Additional exper- imental results and details are deferred to Appendix A We provide code with detailed instructions at httpss//gituub.co//iiii wtwp:ticccoo..iuuaae/a... wwtm/tliu199///00 1997/RNAC
7.1 MuJoCo Environments
We present the experimental results for perturbed MuloCo Envs (Hopper-v3, Walker2d-v3 and HalfCheetah-v3) by changing their physical parameters (ieg--ointsstiffeess, foint and
8

---

-2.6
-2.0
-2.0
-2.0
PPO
170
barget
Turt-boon poottoom
Large:
postton
2.5
tagat
Turt positon
tagat
3,5
4.5
0.5
0.0
055
1.0
3.5
2.0
0.0
0.5
1.0
15
2.0
0.0
0.5
1.0
1,5
2.0
0.0
0.5
1.0
15
2.
Turth:Sot posttion
2t positon
position
TurtieBot postion
DS, Unif(- 0.5, 0.5)
DS) DS, Unif(1, 1.5)
(c) IPM, deterministic
(d) IPM, Unif(1, 1.5)
Figure 2: (a-b) show trajectories under balanced (nominal) / unbalanced noise perturbed envs; (c-d) show trajectories under deterministic (nominal) / unbalanced noise perturbed envs.
We compare the performance of RNAC-PPO with that of the canonical PPO algorithm in Fig. D where the curves are averaged over 30 different seeded runs and the shaded region indicates the mean standard deviation. RNAC-PPO and PPO are trained with data sampled from the nominal models (e.g., leg..leg-jjinn leg- foot.joni stiffstteeessss 0.0, and back actuator range= 1.0).
backactuutoor
DS Uncertainty Set: MuJoCo environments have deterministic models. However, most uncertainty sets only reasonable for stochastic models, e.g.. f-divergence uncertainty sets. So, add uniform actuation noise ~ Unif[-5e-3. 5e-3] in constructing stochastic MuJoCo environments as in makes the
[65] We m 2 and radius 6 1/6 for RNAC-PPO in (4). The choice of
training time of RNAC-PPO with DS uncertainty set and PPO comparable. Fig. Ta 1c demonstrate the robust performance of RNAC-PPO with Souble-Sampling (DS) uncertainty
stochastic MuJoCo environments. Compared to PPO, the cumulative rewards of RNAC-PPO decay much slower as perturbations increase though they are slightly lower at the beginning (i.c., for the nominal model). The slight drop in initial performance may stem from optimizing the robust value function (1) under the worst-case transition models instead of the nominal models.
IPM Uncertainty Set: Since IPM with robust Bellman operator in 66) establishes robustness by negative regularization, it applies to environments with deterministic transition kernels. We select 5 = 10-5 in (6) and evaluate RNAC-PPO with IPM uncertainty sets on deterministic MuJoCo envi- ronments in Fig. [i RNAC-PPO has more robust behaviors with slow cumulative reward decay as perturbations increase. Notably, RNAC-PPO enjoys similar and sometimes even better initial performance on the nominal model compared PPO, which believe is due the regularization of neural network parameters suggested by IPM (6) that can potentially improve neural network training.
7.2 TurtleBot Experiments
We demonstrate the robustness of the policy learned by RNAC-PPO on real-world mobile robot (Fig. 3) We consider a navigation task as illustrated in Fig. 2] where the goal of the policy is to navigate the TurtleBot from the origin (0, 0) to target region centered at (1, 11).
DS Uncertainty Set: We train RNAC-PPO and PPO on stochastic nominal model with balanced actuation noise (54), and test the learned policies in the nominal model (Fig. 2a and unbalanced perturbed model (Fig. 2bb. 'he policies learned by RNAC-PPO can reach the target region in both the nominal model and the perturbed model, while policies learned by PPO are fragile to perturbation and may not reach the target, as shown in Fig. 2b
IPM Uncertainty Set: The robustness of the policies learned by RNAC- PPO trained
deterministic nominal model is demonstrated in Fig. Pd and 2d] where the RNAC-PPO learned policies drive the robot to the target under perturbation, while the PPO-learned policies fail.
A video of this real-world demonstration TurtleBot available at Video Link]
Figure 3: TurtleBot Burger

---

8 Conclusion and Future Works
We have proposed two novel uncertainty sets based on double sampling and an integral probability metric, respectively, that are compatible with function approximation for large-scale robust RL. We propose a robust natural actor-critic algorithm, which to the best of our knowledge is the first policy- based approach for robust RL under function approximation with provable guarantees on learning the optimal robust policy, We demonstrate the robust performance of the proposed algorithm in multiple perturbed MuJoCo environments and real-world TurtleBot navigation task.
Although several new theoretical and empirical results about large-scale robust RL are presented in this paper, there are still many open questions that need to be addressed. Current work focuses on the (s, a) reectangull RMDP (Def. T. We leave extensions to more general s-rectangular and non-rectangular RMDP for future works. Some theoretical analysis in this paper partly relies on Assumption [ Though it is commonly made and accepted in theoretical works as discussed in it is not necessary condition. Further exploration of this can potentially lead to more theoretical advances. Another natural future direction to extend current results to more complex settings such as robust constrained RL and robust multi-agent RL, following and multi-agent RL
paragraphs after Assumption
recent developments policy gradient-bar based approaches in safe RL 68 32
67 50].
Acknowledgement
Dileep Kalathil's work is partially supported by the funding from the U.S. National Science Foun- dation (NSF) grant CEFFCCAREER--ECC-2445527
P. R. Kumar's work is partially supported by the US Army Contracting Command under W91 INF- 22-1-0151 and
US National Science Foundation under CMMI-2038625, and US The views expressed herein and conclusions contained in this document are those of the authors and should not be interpreted as representing the views or official policies. either expressed or implied, of the U.S. NSF, ONR, ARO, or the United States Govermment. The U.S. Government is authorized to reproduce and distribute reprints for Government purposes notwithstanding any copyright notation herein.
Office of Naval Research under N00014-21-1-2386
Portions of this research conducted with the advanced computing resources provided by Texas A&M High Performance Research Computing.
References
[1] Mohammed Amin Abdullah, Hang Ren, Haitham Bou Ammar, Vladimir Milenkovic, Rui Luo, Mingtian Zhang, and Jun Wang. Wasserstein robust reinforcement learning. arXiv preprint 19X1::997.113999 2019.
[2] Alekh Agarwal, Nan Jiang, Sham M Kakade, and Wen Sun. Reinforcement learning: Theory and algorithms. CS Dept., UW Seattle, Seattle, WA, USA, Tech. Rep, pages 10-4, 2019.
[3] Alekh Agarwal, Sham M Kakade, Jason D Lee, and Gaurav Mahajan. On the theory of policy gradient methods: Optimality, approximation, and distribution shift. The Journal of Machine Learning Research, 22(1):4431-4500 2021.
[4] Carlo Alfano and Patrick Rebeschini. log-linear policy parametrization. arXiv preprint arXiv:2209. 2022.
Linear convergence for natural policy gradient with
[5] Robin Amsters and Peter Slaets. Turtlebot Robotics Education Platform, pages 170-181. 01 2020.
[6] Jose Blanchet, Miao Lu, Tong Zhang, and Han Zhong. Double pessimism is provably efficient for distributionally robust offline reinforcement learning: Generic algorithm and robust partial coverage. arXiv preprint ar3iv:2305. 2306099,00 2023.
[7] Greg Brockman, Vicki Cheung, I Ludwig Pettersson, Jonas Schneider, John Schulman, Jie Tang, and Wojciech Zaremba. Openai gym. arXiv preprint arXiv: I 1606.01540 2016.
10

---

[8] Shicong Cen, Chen Cheng, Yuxin Chen, Yuting Wei, and Yuejie Chi. Fast global conver- gence of natural policy gradient methods with entropy regularization. Operations Research, 70(4):2563-255 2578, 2022.
[9] Zaiwei Chen, Sajad Khodadadian, and Siva Theja Maguluri. Finite-sample analysis of off- policy natural actor-critic with linear function approximation. IEEE Control Systems Letters, 1-2611-2616, 2022.
[10] Zaiwei Chen, Sheng Zhang. Thinh T Doan, John-Paul Clarke, and Siva Theja Maguluri. Finite-sample analysis of nonlinear stochastic approximation with applications in reinforce- ment learning. Automatica, 146: 10623, 2022.
[11] Esther Derman, Daniel Mankowitz, Timothy A Mann, and Shie Mannor. Soft-robust actor- critic policy-gradient. arXiv preprini 1803, 2018.
[12] John C Duchi Hongseok Namkoong. Learning models with uniform performance via distributionally robust optimization. The Annals of Statistics, 49(3):1378-14066 2021.
[13] Benjamin Eysenbach and Sergey Levine. Maximum entropy rl (provably) solves some robust rl problems. In International Conference Learning Representations.
[14] Herbert Federer. Geometric measure theory. Springer, 2014.
[15] Scott Fujimoto, Herke Hoof, and David Meger. Addressing function approximation error in actor-critic methods. International conference on machine learning. pages 1587-1596. PMLR, 2018.
[16] Vineet Goyal and Julien Grand-Clement. Robust markov decision processes: Beyond rectan- gularity, Mathematics of Operations Research, 48(1):203-226, 2023.
[17] Julien Grand-Clément and Christian Kroer. Scalable first-order methods for robust mdps. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 12086-12094, 2021.
[18] Tuomas Haarnoja, Aurick Zhou, Pieter Abbeel, and Sergey Levine. Soft actor-critic: Off- policy maximum entropy deep reinforcement learning with stochastic actor. In International conference on machine learning, pages 1861-1870. PMLR, 2018.
[19] Garud N Iyengar. Robust dynamic programming. Mathematics of Operations Research, 30(2):257-280, 2005.
[20] Nick Jakobi, Phil Husbands, and Inman Harvey. Noise and the reality gap: The use of simu- lation in evolutionary robotics. In Advances in Artificial Life: Third European Conference Artificial Life Granada, Spain, June 4-6, 1995 Proceedings 3, pages 704-720. Springer, 1995.
[21] Bai Jiang, Qiang Sun, and Jianqing Fan. Bernstein's inequality for general markov chains. arXiv preprint a8Xiv: 1800.0055.11111 2018.
[22] Chi Jin, Zhuoran Yang, Zhaoran Wang, and Michael Jordan. Provably efficient reinforcement learning with linear function approximation. In Conference Learning Theory, pages 2137- 2143. PMLR, 2020.
[23] Sham Kakade and John Langford. Approximately optimal approximate reinforcement leam- ing. In Proceedings of the Nineteenth International Conference Machine Learning, pages 267-274, 2002.
[24] Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv: 1412.980, 2014.
[25] Kruger. On fréchet subdifferentials,, Journal of Mathematical Sciences, 116(3):3325- 3358, 2003.
11

---

[26] Yufei Kuang, Miao Lu, Jie Wang, Qi Zhou, Bin Li, and Houqiang Li. Learning robust pol- icy against disturbance in transition dynamics via conserovneevvttve policy optimization. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pages 7247-7254, 2022.
[27] Navdeep Kumar, Esther Derman, Matthieu Geist, Kfir Levy, and Shie Mannor. Policy gradient for s-reetangular robust markov decision processes. arXiv preprint arXiv:2301.13589, 2023.
[28] Navdeep Kumar, Kfir Levy, Kaixin Wang, and Shie Mannor. Efficient policy iteration for robust markov decision processes via regularization. arXiv preprint arXiv:2205. 14327, 2022.
[29] Yan Li, Tuo Zhao, and Guanghui Lan. First-order policy optimization for robust markov decision process. arXiv preprint XxXi:2209.105793 2022.
[30] Zhipeng Liang, Xiaoteng Ma, Jose Blanchet, Jiheng Zhang, and Zhengyuan Zhou. Single- trajectory distributionally robust reinforcement learning. arXiv preprint arXiv:2301.11721, 2023.
[31] Timothy P Lillicrap. Jonathan J Hunt, Alexander Pritzel, Nicolas Heess, Tom Erez, Yuval Tassa, David Silver, and Daan Wierstra. Continuous control with deep reinforcement learning. arXiv preprint /50900297, 2015.
[32] Tao Liu, Ruida Zhou, Dileep Kalathil, PR Kumar, and Chao Tian. Policy optimization for constrained mdps with provable fast global convergence. arXiv preprint arXi::2111.0055, 2021.
[33] Zijian Liu, Qinxun Bai, Jose Blanchet, Perry Dong, Wei Xu, Zhengqing Zhou, and Zhengyuan Zhou, Distributionally robust q-learning. International Conference on Machine Learning. pages 13623-13643, PMLR, 2022.
[34] Xiaoteng Ma, Zhipeng Liang, Li Xia, Jiheng Zhang, Jose Blanchet, Mingwen Liu, Qianchuan Zhao, and Zhengyuan Zhou. Distributionally robust offline reinforcement learning with linear function approximation. arXiv preprint 2XXv:22299006600 2022.
[35] Shie Mannor, Ofir Mebel, and Huan Xu. Robust mdps with k-rectangular uncertainty. Mathe- matics of Operations Research, 1444:1184-1550, 2016.
[36] Shie Mannor, Duncan Simester, Peng Sun, and John N Tsitsiklis. Bias and variance approxi- mation in value function estimates. Management Science, 53(2):308-33) 322, 2007.
[37] Jincheng Mei, Chenjun Xiao, Csaba Szepesvari, and Dale Schuurmans. On the global con- vergence rates of softmax policy gradient methods. In International Conference Machine Learning, pages 6820-6829. PMLR, 2020.
[38] Alfred Müller. Integral probability metrics and their generating classes of functions. Advances in applied probubility, 29(2):429-443, 1997.
[39] Ariel Neufeld and Julian Sester. Robust q-learning algorithm for markov decision processes under wasserstein uncertainty. arXiv preprint arXi::2210.0089, 2022.
[40] Arnab Nilim and Laurent El Ghaoui. Robust control of markov decision processes with uncer- tain transition matrices. Operations Research, 53(5):780-798, 2005.
[41] Kishan Panaganti and Dileep Kalathil. Robust reinforcement learning using least squares pol- icy iteration with provable performance guarantees. In International Conference Machine Learning, pages 511-520. PMLR, 2021.
[42] Kishan Panaganti and Dileep Kalathil. Sample complexity of robust reinforcement learning with a generative model. In International Conference on Artificial Intelligence and Statistics (AISTATS), pages 9582-9602, 2022.
[43] Kishan Panaganti, Zaiyan Xu, Dileep Kalathil, and Mohammad Ghavamzadeh. Robust rein- forcement learning using offline data. In Advances in Neural Information Processing Systems, pages 3221 1232244, 2022.
12

---

[44] Xue Bin Peng, Marcin Andrychowicz, Wojciech Zaremba, and Pieter Abbeel. Sim-to-real transfer of robotic control with dynamics randomization. In 2018 IEEE international confer- ence on robotics and automation (ICRA), pages 3803-3810. IEEE, 2018.
[45] Aurko Roy, Huan Xu, and Sebastian Pokutta. Reinforcement learning under model mismatch. Advances in neural information processing systems, 30, 2017.
[46] Reazul Hasan Russel and Marek Petrik. Beyond confidence regions: Tight bayesian ambiguity sets for robust mdps. Advances in Neural Information Processing Systems, 2019.
[47] John Schulman, Sergey Levine, Picter Abbeel, Michael Jordan, and Philipp Moritz. Trust region policy optimization. In International conference on machine learning, pages 1889- 1897. PMLR, 2015.
[48] John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint arXiv:1707.06337, 2017.
[49] Laixi Shi and Yuejie Chi. Distributionally robust model-based offline reinforcement learning with near-optimal sample complexity. arXiv preprint arXiv:2208.05567, 2022.
[50] Youbang Sun, Tao Liu, Ruida Zhou, PR Kumar, and Shahin Shahrampour Provably fast convergence of independent natural policy gradient for markov potential games. arXiv preprint arXiv:2310.09727, 2023.
[51] Niko Sünderhauf, Oliver Brock, Walter Scheirer, Raia Hadsell, Dieter Fox, Jürgen Leitner, Ben Upcroft, Pieter Abbeel, Wolfram Burgard, Michael Milford, et al. The limits and potentials of deep learning for robotics. The International journal of robotics research, 37(4-5):405-420. 2018.
[52] Richard S Sutton, David McAllester, Satinder Singh, and Yishay Mansour. Policy gradient methods for reinforcement learning with function approximation. Advances in neural infor- mation processing systems, 12, 1999.
[53] Aviv Tamar, Shie Mannor, and Huan Xu. Scaling up robust mdps using function approxima- tion. In International conference on machine learning, pages 181-189. PMLR, 2014.
[54] Chen Tessler, Yonathan Efroni, and Shie Mannor. Action robust reinforcement learning and applications in continuous control. In International Conference on Machine Learning, pages 6215 1224..224.222 PMLR, 2019.
[55] Josh Tobin, Rachel Fong, Alex Ray, Jonas Schneider, Wojeiech Zaremba, and Picter Abbeel. Domain randomization for transferring deep neural networks from simulation to the real world. In 2017 IEEE/RSJ international conference on intelligent robots and systems (IROS), pages 23-30. IEEE, 2017.
[56] Emanuel Todorov, Tom Erez, and Yuval Tassa. Mujoco: A physics engine for model-based control. In 2012 IEEE/RSJ international conference on intelligent robots and systems, pages 5026-5033. IEEE, 2012.
[57] John Tsitsiklis and Benjamin Van Roy. Analysis of diffferrece learning with function approximation. Advances in neural information processing systems, 9, 1996.
[58] Qiuhao Wang, Chin Pang Ho, and Marek Petrik. On the convergence of policy gradient in robust mdps. arXiv preprint 2eXix:2212.10433 2022.
[59] Shengbo Wang, Nian Si, Jose Blanchet, and Zhengyuan Zhou. A finite sample complexity bound for distributionally robust l-larning. In International Conference on Artificial Intelli- gence and Statistics, pages 3370-3398. PMLR, 2023.
[60] Yue Wang and Shaofeng Zou. Online robust reinforcement learning with model uncertainty. Advances in Neural Information Processing Systems, 34:7193-7206, 2021.
[61] Yue Wang and Shaofeng Zou. Policy gradient method for robust reinforcement learning. In International Conference on Machine Learning, pages 23484-2352 PMLR, 2022.
13

---

[62] Wolfram Wiesemann, Daniel Kuhn, and Berę Rustem. Robust Markov decision processes. Mathematics of Operations Research, 38(1):153-183, 2013.
[63] Huan Xu Shie Mannor. Distributionally robust Markov decision processes. In Advances in Neural Information Processing Systems, pages 2505-2513, 2010.
[64] Zaiyan Xu, Kishan Panaganti, and Dileep Kalathil. Improved sample complexity bounds for distributionally robust reinforcement learning. International Conference on Artificial Intel- ligence and Statistics (AISTATS), pages 9728-97544 2023.
[65] Mengjiao Yang, Dale Schuurmans, Pieter Abbeel, and Ofir Nachum. Dichotomy of control: Separating what you can control from what you cannot. arXiv preprint 3tti:22100.134333 2022.
[66] Wenhao Yang, Liangyu Zhang, and Zhihua Zhang. Toward theoretical understandings of robust markov decision processes: Sample complexity and asymptotics. The Annals of Statistics, 50(6):3223-322 -248,, 2022.
[67] Runyu Zhang, Jincheng Mei, Bo Dai, Dale Schuurmans, and Na Li. On the global convergence rates of decentralized softmax gradient play in markov potential games. Advances in Neural Information Processing Systems, 35:1923-1935, 2022.
[68] Ruida Zhou, Tao Liu, Dileep Kalathil, PR Kumar, and Chao Tian. Anchor-changing regular- ized natural policy gradient for multi-objective reinforcement learning. Advances in Neural Information Processing Systems, 2022.
[69] Zhengqing Zhou, Qinxun Bai, Zhengyuan Zhou, Linhai Qiu, Jose Blanchet, and Peter Glynn. Finite sample regret bound for distributionally robust offline tabular reinforcement learning. In International Conference on Artificial Intelligence and Statistics, pages 3331-3339, 2021.
14

---

A Experimental Details and Additional Experimental Results
In this section, we provide details of the RNAC algorithm (Algorithm implemented in the experi- ments robust natural actor-critic proximal policy optimization (RNAC-PPO) algorithm (Algorithm F.. We also demonstrate further experimental results evaluated on different perturbations of physical hyperparameters in Hopper-v3, Walker2d-v3, and HalfCheetah--V' from OpenAl Gym 7 compared with soft actor-critic (SAC) [8]] and soft-robust [1I] PPO (SRPPO). Finally, we introduce experi- mental details of the TurtleBot navigation task.
A.1 RNAC-PPO Algorithm
We provide the RNAC-PPO algorithm in Algorithm 4 where the robust critic is minimizing squared robust TD error (MSRTDE) and the robust natural actor is performing the clipped version of robust PPO (RPPO) for computational efficiency, and we name it RNAC-PPO for simplicity. We implement RNAC-PPO employing neural network (NN) function approximation, where the robust natural actor utilizing neural Gaussian policy [48] with two hidden layers of width 64, and the value function in the robust critic is also parameterized by an NN with two hidden layers of width 64. Compared with the canonical empirical Bellman operator in the PPO algorithm, we adopt the robust empirical Bellman operator in the Robust PPO algorithm based on the double-sampling (DS) uncertainty set and the integral probability metric (IPM) uncertainty set, which can be efficiently computed. For better comparison with SAC in the next subsection, normalization, reward scaling, gradient clip, etc) in the implementation of PPO-base algorithms to improve their performance under the nominal model. Note that for fairness employ the same modification for both PPO and RNAC-PPO algorithms.
adopt several modifications (e.g., state
We use the same hyperparameters across different MuJoCo environments. Specifically, we select = 0.99 for the discount factor, 17 a' = 3 x 10 for learning rates both actor and critic updates implemented by ADAM [24), T 3 x 10 for the maximum training steps, and B = 2048 for the batch size.
Algorithm 4: -RNAC-PPO-MSRITTI + RPPO
Input: T, B, 17 0:7-1
Initialize: 8 for policy parameterizaaton, do
for value function approximation
for to 0, 1,
Collect of trajectories Dt until |D*| B by running policy Tpi under pd Update value function by minimizing mean-squared TD error with learning rate a
w arg min
Σ
Vi)(s)
(T V .)(s,,,)))
DE
(E.D)""))
// For DS: y' = mmm sid. pe.. Unif(y') and TØ in (3)
// For IPM: 8/ =/= s' ~ pe.a and TF in 6 Compute
( v') Var (s), V(s v.v E Dr
Update policy via maximizing robust PPO objective with learning rate ny
0++l arg max 0
min
Ta(as Tgr (a|s)
Á' clip(e, A ((())))
D
(E.
(1 (1+ if A 2 0 (11 (1-e)A, if A
where clip(e, A)
Output: HT
15

---

3500
5020
Cumulstive rewarr
noward
3000
3253
6020
2300
2202
8500
2390
2252
ANAC (PDSS)
2530
RNAC-PPOIDS)
(NAC-PPO((DS)
1003
20
02
90
100
10
20
20
50
20
20
30
40
63
75
Percenfage change jeinjiint damping
joint stiffiees
values (defautt=o.0)
Percentage change front joint stiffness
(a) DS, H3pper-v3
(b) DS, Walker-v3
(c) DS, HalfCheetah--y
2300
3500
Cururatve reward
Cumulative ruward
6520
1500
6020
300
2002
RNAC (PO()PM)
2920
RNAC PPOUPM!
RMAC FPOLIPM)
1590
3030
20
100
10
20
70 20 36
40
Percentage change Jeg_joint, So__join__aampnng damping
Teg htt.jonntssttffee values 1dcfault=000f
Percentage change in front joint stiffees
(d) IPM, Hopper-v3
(e) IPM, Walker-v3
(I) IPM, HalfCheetah-v3
Figure 4: Cumulative rewards RNAC-PPO(DS/IM,, and PPO on (a-c) stochastic MuJoCo Envs
and (d-f) deterministic MuJoCo Envs under perturbation.
A.2 Perturbed Mujoco Environments with Other Hyperparamettrss
In this subsection, we provide more experimental results different perturbations of physical hy- perparameters (e.g., leg. joint damping, ja-joontttifnness and front foint_stiffreet in Hopper-v3, Walker2d-v3, and HalfCheetah-v33 Figure shows that the RNAC-PPO algorithm is consistently robust compared to the PPO algorithm.
A.3 Comparison with Soft Actor-Critic and Soft-Robust PPO
In Section we demonstrate the robust behavior of the RNAC-PPO algorithm compared with the PPO algorithm in Figure [ In this subsection, we add two more baselines for robust algorithms: soft actor-critic (SAC) [18] and soft-robust [IT] PPO (SRPPO). SAC is regarded as one of the robust baselines since maximum entropy RL (e.g. SAC) was shown to solve some robust RL problems by maximizing the lower bound on robust objective [13] Soft-robust RL learns an optimal policy based on distribution over uncertainty set instead of considering the worst-casc scenario [ For a fair comparison, we implement the idea of soft robustness into the framework PPO. Specifically, build uncertainty set wrapping up four environments, including nominal environment and three perturbed environments with leg joint stiiinsstiffesss5... (default=0.0), gravity=- 9.50 (default=<9.81 and actuator ctrlrange=(-0995, 0.95) (default=(-1.0, 1.0)), respectively. Addi- tionally, we select [0.85, 0.05, 0.05, 0.05) as the distribution over the above uncertainty set for the SRPPO algorithm.
Figures 5c and 5d show that the cumulative rewards of RNAC-PPO decay much slower compared with those of PPO, but similar to those of SAC under the perturbation of gravity. This verifies the claim that SAC can solve some robust RL problems [33] However, as shown in Figures 5a and 5b SAC is not panacea for all robust RL problems. Under the perturbation of leg jes_jointtstiifnesss SAC suffers faster cumulative rewards decay compared with RNAC-PPO. Since SRPPO considers distribution over uncertainty set instead of only sampling from the nominal model, it doesn't t
perform well under the nominal model, but it shows fairly robust behavior in Figures 5a and 5b when leg joint_stiffeess values perturbed.
Since the cumulative rewards of SAC (> 14000) are much higher than those of PPO-based gorithms (< 3000) in HalfCheetahh-3, we only report the results of SAC in this subsection for Hopper-v3 to prevent the information of robustness from being blurred. Additionally, the training time of RNAC-PPO, PPO, and SRPPO is similar, which is at least 5 times less than that of SAC to
16

---

4000
RNAC (PCC-)
4000
RNAC-PPO(IPM)
PPO
Cumulative reward
3500
SAC SRPPO
Cumulative reward
3500
SAC
3000
SRPPO
2500
2500
2000
2000
1500
1500
1000
1000
500
10
30
40
20
40
lle__ stiffness' values (default=0.0)
leg reg_joint_sstffineee stiffness' values (default=0.0)
(a) DS, stochastic Hopper-v3
(b) IPM, deterministic Hopper-v3
(ACC-PPO(DS)
RNAC-PPO(IPM)
PPO
PPO
Cumulative reward
3500
SAC
Cumulative reward
SAC
3000
SRPPO
SRPPO
2500
2000
1500
1000
1000
500
-50
-40
-30
-20
-10
-50
-40
-30
-20
-10
Percentage change in 'gravity' (default=0.0)
Percentage change in 'gravity' (default=0.0)
(c) DS, stochastic Hopper-v3
(d) IPM, deterministic Hopper-v3
Figure 5: Cumulative rewards of RNAC-PPO(DS/IPM), PPO, SAC, and SRPPO on perturbed Hopper-v3 environments.
end the training of 3 million steps. This is due to the fact that PPO-based algorithms require fewer updates for critie V, while SAC requires updates for critic Q.
A.4 TurtleBot Experiment Details
The goal of this TurtleBot navigation task is to guide the robot to any desired target within 2-meter range. The state space 2-dimensional continuous space, comprising the distance and relative orientation between the robot and the target. The robot is fixed to move towards its front with linear velocity of 15 cm/s, while its angular velocity is controlled by the algorithm. Action space is 1-dimensional and continuous, ranging from 2 to 2. The action signal is then linearly scaled into [-1.5 rad/s, 1.5 rad/s]. The reward function is designed to be proportional to the product of distance and action-scaled orientation between the robot and the target. Hitting the boundary reaching the target would cause reward of -200 or 200 respectively. One trajectory would end when the robot hits the boundary, reaches the goal, the elapsed time is more than 150 seconds.
We train both PPO and RNAC-PPO(IPM) under the simulator Gazebo. To introduce stochasticity into the originally deterministic Gazebo environment, we apply uniform action noise perturbation. PPO and RNAC-PPO(DS) are trained under a balanced Unif[-0.5, 0.5] noise-perturbed environ- ment. All algorithms undergo 400 epochs of training, and the policy with the highest speed is saved. Subsequently, we evaluate all policies in an unbalanced Uniff1.0, 1.5) noise-perturbed environment. We employ such high noise since all learned algorithms close to the limit of 2 or 2. The trajectories of the robot under Gazebo simulator and a video for the real-world experiment
aggressive at fast turning, with action
demonstrated in Figure and [iieoo Link].
Specifically, both PPO and RNAC-PPO are implemented by neural networks. The actor network defined by the Gaussian policy, with one hidden layer and tanh activation function, projecting the
17

---

-2.0
-2.0
RNAC-FFO/DSS)
(HAC-FFOODDS)
PPO
PFO
Action Noise Dynamic Random Target
Action Noise Dynamic Random
TurtleBot position
-1.5
TurtleBot position
-1.5
Target
-1.0
-1.0
0.5
0.5
0.0
0.0
0.0
0.5
1.0
1.5
2.0
0.0
0.5
1.0
2.0
TurtieBot position x
TurtleBot position
(a) DS, Unif(-0.5,0.5)
(b) DS, 1n)5(1,1.55)
-2.0
-2.0
RNAC-PPOJIPM)
RNAC-PPO(IPM)
PPO
PPO
TurtleBot position y
TurtleBot position y
Action
-1.5
Dynamic Random
-1.5
Dynamic Random Target
Target
-1.0
-1.0
-0.5
-0.5
0.0
0.5
1.0
1.5
2.0
0.0
0.5
1.0
1.5
2.0
TurtleBot position x
TurtleBot position x
(c) IPM, deterministic
(d) IPM, Unif((.11.5)
Figure 6: Turtlebot's trajectories of RNACC-PPODS//PM), PPO, dynamic randomization, and action noise envelope. (ac) are trajectories under a nominal environment, (bd) are trajectories under an unbalanced testing environment. In (b), target reaching rates are: 100% for RNAC-PPO(DS), 67.5% for action noise envelope, 9% for dynamic randomization, 0% for PPO. In (d), target reaching rates are: 100% for RNAC-PPO(IPM), 13% for action noise envelope. 2% for dynamic randomization, 0% for PPO
input state into a feature with dimension 100, then into the I-dimensional action. Critic network consists of one hidden layer, with a width 100, and a ReLU activation function. We choose discount factor as 0.99, learning rate as 2.5 x 10-4, batch size as 64, and optimizer ADAM.
Additionally, we also add more baselines (i.e., dynamics randomization 44 and action noise en- velope 20 to demonstrate the robustness of the proposed methods in the real-world TurtleBot environment. As shown in Figure 66 the proposed algorithm RNAC-PPO (DS / IPM) enjoys higher target reaching rates (100% / 100%), compared with action noise envelope (67.5% 13%). dynamic randomization (9% 2%), and PPO (0% / 0%), under perturbed testing environments, which illus- trates the robustness of the RNAC-PPO algorithm.
We end this section by illustrating our hardware configurations. All experimental results are carried out on a Linux server with 48-core RTX 6000 GPUs, 48-core Intel Xeon 6248R CPUs, and 384 GB DDR4 RAM.
B Discussions on Uncertainty Sets
R-contamination For R-contamination 660, the uncertainty set is P &s,aPa.a where Psaa { Rq + (1- R)p2a 9 E As}. It can be shown that
inf p = (1 R).) TV + Rmin V(s)).
(8)
pEP,a
18

---

Its corresponding robust Bellman operator requires searching the entire state space S to calculate the minimum value in V, and thus intractable for large state space.
lp norm 28 For any nominal model p², the uncertainty set is P = Ss.a s.a with Pa.a = (p :
||g Po.al S 5, Exr(()) = 1}. where || llp is an f norm with its dual norm || lla satisfying
- 1, and the domain q E As is relaxed to hyperplane E. g(s") = due to the difficulty
in handling the boundary of Ag. was shown (28) that
inf PEP
p V = (P2,a) min IV willa:
(9)
which requires solving minimization problem via binary search. The minimum value may have a closed-form representation (c.f. Table 1 in (27). For example, the minimum value the average of V for lz norm, the median of V for & norm, and the average peak of V (i.e., the average of the maximum and minimum value of V) for lo norm. 4, norm-based uncertainty set is thus intractable in the large-scale scenario.
d-divergence Given continuous strict convex function f RR+ R with f(1) = 0. f-divergence By distributionally robust optimization literature 12), we
is defined by dy (q. = Σ, p(s)
2(0)
p(x)
have
- (-V(s) A
inf p V sup E. pEP...
-2f"
A6 17
(10)
X>ONNER
where I is the Fenchel conjugate of J, i.e., (v) = sup=>o(yr - (())) Given such a formula, the robust Bellman operator can be estimated given samples from the nominal model but requires the optimal dual variables X, for each (s, a) pair.
Wasserstein distance Given some metric d(. .) state space S, Wasserstein-or distance is defined for any p, q E As that
W (p. q) := inf B(o,e') (d(, s)) uEU((.a)
where Upp. q) is the set of all couplings of and q. Wasserstein RMDP has uncertainty set P PapPo. s,a with Pa.a- = =gg Wo Wo P%.a) S 8) and we have
vTV sup inf PEP,,
Σ (n)(())) M 8)]. ASO
(11)
The Wasserstein RMDP has been previously studied 1 26 Kuang et al. 26 gives a state dis- turbance view of Wasserstein RMDP, where the robust Bellman operator requires searching the
worst-case state in the vicinity of the next state sample, i.e., infs: so V(5). Although this ap- proach can be applied to RMDP with large state space, the theoretical guarantee provided in (26) is only for policy iteration (planning problem) in the tabular setting (i.e., the robust Bellman operator is a contraction mapping under
(l.)).
B.1 Double-Sampling Uncertainty Sets
When action a is taken at state s, the nominal model transits to the next state 5' ~ pi.a- It can be viewed as a double-sampling process that the next state is generated by uniformly sampling one from states s1, s2,...,, s'm sampled i..d. according p%. The transition kernel in the DS uncertainty set at (s, a)-pai can be viewed as selecting the next state s' in (sh...., 8'm) according to a distribution a E a(m) that is perturbed from a uniform distribution Unif(m) and potentially depends on the samples {s!...., )m).. The DS uncertainty set is implicitly defined by choice of m, divergence measure .)..)) and radius > O.
Bellman completeness for robust linear MDP under DS uncertainty set: A Q function class C SAA is said to be Bellman complete if it is closed, and for all g E 9, T'g also lies in g. where
T')(s,a) == r(s,a) + Epaa(s)) max g(s',a).
19

---

Bellman completeness is critical for reinforcement learning. For RMDP with the Double- Sambll-g (DS) uncertainty set, the linear function approximation can satisfy Bellman completeness if the nominal model is linear MDP. In linear MDP [22]. we have
( (18 a) m(s'), r(s.a) = (ss,a) O)
where μ is a vector of (signed) measures over S. Then for any V R
r(s, a) - TlBes-pp (itt:,p,.[((())) = r(s, +
0(s, "(ss ((d))V(s)
= a (0+7
/ (((')((s')dd')) E @pan(())
For the DS uncertainty set P Sa Pe. determined by m, d(:,,),,, let fv(
inf (aa Ei= (s)(s and (v()1) that for any V
E
2 "2 p2. (5v It then follows
r(s,a) + inf V = r(s, + + fimm PEPa.
" (fv(m
= =((,,)) T0 Pls [fv (s1)) a) (0+7 / (s')dds) sp)n($).
The Bellman completeness for DS-based RMDP with linear MDP nominal model is thus proved.
B.2 Integral Probability Metric Uncertainty Sets
Under the linear value function approximation, (s) (bs)) w. Denote V E RSxd as the feature matrix by stacking up (=s) and the value function approximation is a linear regressor Vn Vw E R Let Vi [ ... *ba] with eú IRS, without loss of generality, assume th is an all-one vector, which corresponds to the bias term of the linear regressor, and V/ is full column rank.
We propose the IPM dp 9) sup (p
--q f) determined by function class
F W & R |IEll S 1}
restatement of Eq (5) in matrix form.
The robust Bellman operator TBV equivalent to
requires solving the optimization inf o TV, which
mingeds q Tv s.t. supjer f (
We relax the domain constraint E As to E.9(s) = and define Psa {g dr(g.p%.a) S 5, Σ. (()) = 1}. This relaxation omits the boundary effect of As. which facilitates the following analysis. The relaxation is also made for E, norm-based uncertainty set (28), and one can argue that it does not introduce any relaxation error for ps (s') O, Vs, s' and small d.
Restatement of Proposition 1
For the IPM with F in S). we have inf inf. a. q VVo. (p%.a) TV
6 ||2aa||-
Proof of Proposition
L
Denote =9 Ps.a. The inf inf g.P... a q V under the relaxation is
min (p Tw + u Lw, s.t. sup u 1 s 8, u T 1 O. 1ells1
Since & is full column rank and 4 is an all vector, know ( T 1 0, R$3 = tu
Rd y1 0}. The optimization problem can then be written min (p²,a) The + W2ad;
s.t. sup
V2a S 8. 1
The constraint is equivalent to || < 5 and the optimal value can then be written as (pi,)) TV,
8 |/waall, which concludes the proof of Proposition []
The IPM has many merits due to its capability to take advantage of the geometry of the domain (state space) through the function class.
20

---

C Robust Critic Analysis
We analyze the robust critic component in the RNAC algorithm (Algorithm D also be of independent interest for the robust policy evaluation problem, where one aims to estimate the robust value of some policy given Markovian data.
This section would
The first two subsections focus on the linear function approximation and prove the main theorems stated in Section of the main paper. The last subsection focuses the general function approx- imation.
C.1 Linear Robust Value Function Approximation
Setting: We aim to approximate the robust value function V thorough linear function class (s) = ( w, Vs S.
(12)
The "optimal" linear value approximation Vw= is the solution of the projected robust Bellman equa- tion i.c.,
I1 VV Vun,
where the projection matrix 11" ( -- D with D diag(v") and 1/= is the state stationary distribution of executing policy π on the nominal model p".
Definition (Linear value approximation error). 6V,bias == sup, | V* 1,2.
" is the solution of the projected robust Bellman equation II II A-contraction w.r.t. Ilu,, we have (according to Corollary 53
Vn. When 11T is
V
V
V
< 1 8
EV,bias
(13)
C.1.1 Contraction of Projected Robust Bellman Operator
The contraction property of the projected robust Bellman operator is the key to guaranteeing the convergence linear TD algorithms. The contraction property can be guaranteed when Assumption is satisfied, and we show that the DS uncertainty set with a small 5 indeed satisfies this assumption.
We refer divergence -).:-) as C-continuous at uniform distribution Unif([m]). if {ax Am]]] d(a, [mil([m])) c) S {a [m]] l|a [nif([m]) lox I Ce), Ve >> 0.
Proposition 4. Uncertainty set implicitly defined by double sampling with divergence d(:y)) that is
C-continuous uniform distribution Umil((ml) and 5 < ymo satisfies Assumption 2
Proof. For the uncertainty set P implicitly defined by double-sampling with robust Bellman opera- tor
m
V)))s) = (19) PS..
r(s,a) +
inf ac Lall 58
Σ a (s11)
Since d(.,-) is C-continuous uniform distribution, take arbitrary (s, a, s'), we know
sup q(s') Egg... ~pp... gEP,.
sup acA ml (ni S4
0, =
i=1
Byy.. up?.a
sup
0; (0/ 80)
aEA mm
[nnf((]) a 505 1=1
Est, upp
C6) =
(s') mC8).
m
To guarantee 7 ysup ((5') < 3p% with some < 1, we know need (1 + mC8) 4. which can be achieved by 8 7
21

---

The following theorem shows that choosing a small 6 is not panacea for the well-known f- divergence uncertainty set. Note that many well-known metrics, such as KL-divergence, total varia- tion, and x divveeegee are special cases of f-divergence.
Proposition 5 (Restatement of Proposition 3. For any I-divergence and radius ô >> O, there exists geometrically mixing nominal model such that the f-divergence defined uncertainty set violates Assumption 2
Proof of Proposition Given a continuous strict convex function f :R+ - R with f(1) = 0, the f-divergence is defined as p) = -. ( g(s) p(a)
Given a nominal model p" and radius > O, the f-divergence-based uncertainty set is P with Ps.a = {q (g.g.P8.a) S 8). For any S and d > O, consider nominal model pº, which has a uniform transition probability, i.e., transits to a uniformly and randomly se- lected next state at any state-action pair, except for (s) The transition probability (s, a) is sT 8|-T), where a is some parameter to be determined later. It is clear
1-a 1-a Pa.a- = (a, - that this nominal model pº is well mixed for any a [0, 1]. Consider another model q which 1-a/7 1-a/1
coincides with p" except for states (s,a) with 9a.a = (a/7, |5|-1 |s|-1 ..... ( Note that (.a(()) = 7, thus if E P, the Assumption of 8 < 1 is violated. Since - 0, by the continuity of and f(1) O, we have
(1)
(g = Epe ( Unsll')) = + (1- a)s( 2- 1
1/7 1-a - 00<
+ +1
Therefore, with a sufficiently small ax we have qa.0 E Ps.a and clearly P. Thus there does not exist a universal choice for f-divergence- based uncertainty set to guarantee Assumption 2
We next prove Lemma ! which shows the contraction of robust Bellman operator for IPM-based RMDP without Assumption
Proof of Lemma 7 Let PT (s'(s) Ee P2 (a))(()))(
(s') be the state transition kernel of executing
policy x on the nominal model pº. We can view pm E RSSS as a matrix. Recall D = diag(u"), have
I Vww - Ve V = | ye - 761| - Wnd + 7
76
///lVww Vwlllu llr + 7611|/0 - || ||| s 71 ww Vw''l I|u- + Amin (V D=
Uw Vw llue.
Since TTT is non-expansion mapping w.r.t. || Ilue. TT is a contraction mapping if 7(1 + Auina W D= 1, which equivalent to the condition Amin D
C.1.2 Convergence of Robust Linear TD
As discussed in the paragraph under Assumption I robust linear TD (RLTD) is stochastic approx- imation (c.f. Section F3 for a brief overview of stochastic approximation) since empirical operator
T or 66 is unbiased with
E (ssay (out (b(() (TFV -()) w| " DTD V.).
We can then let a(w, (5)) (IT) (bs) with x (0, a,y) and RLTD is solving the following equation
F(w) = v T D(T Vw Ww) --=== 00
22

---

through stochastic approximation:
Wk++1 wk. + og (Wa, Ii (Sk: dee 1k++1)
It is clear that { is also a Markov chain with domain X = S x A x y y= = 8t for the double-sampling uncertainty set with m samples and y = S for the IPM uncertainty set.
Theorem 5 (Formal statement of Theorem 3
Take ô as in Lemma Lemma[aand in Proposition
4 for the
DS uncertain set or the IPM uncertainty set, respectively. Under Assumption 7 RLTD with step
sizes ag = (1/k) guarantees Billux- - == = x and Balle - -V 1 0
Proof of Theorem 5 By Proposition 4 Hand Lemma DS or IPM with small 8 can guarantee T a 3-contraction w.r.t. || Ilue for some < 1. The theorem can be proved by applying Lemma 12 For this purpose, we only need to show that Assumption is satisfied for RLTD. We check the three conditions in Assumption 8 as follows.
1. The geometric mixing property of {ar = (Sk, ak: 1++1) is straightforward given geo- metrically mixed {5k J=20-
2. Since r E [0, 1] and []{(())] is bounded Vs S, we have [IF(0, x) [1()))(s) s [[{())]] is also bounded for any x = (8, 0, 3/) 33 and any z (s, a, a. 1mmm)
For double-sampling
m
inf F(w,x) (ss) a() +7 ac amAimpdla (n)) Uni
a (or (bss w
Let Vor. E m be the matrix by stacking up (s(() ( (5'm)) T,, we have
x) - x))1
{s)] inf a T Ve um w1 - inf a T W wz + =11bss)))))) wo2)l
s Syll(ss) sup a T TV sii. (w1 w2)1 + w2ll
< max 2>/| || w2l1
where sup,, i inf
are taking in {a E [mm] d(a, (nil((m]) Σ 6). Thus there exists L1 max(max, [|<((>)]] 27 max, [1²() that guarantee [| xx]l < L1 and [[(,,))) F(w', xx]] S L1 w w/ll for the sumplig RMDP.
For IPM (6 and any x = (s, as
F(w,,) x)) (s) (r(s,a) 70's') Tw - =dlluuzlll (ss) (ss)sw)
We have
[1 - Fw'' x)1 S max ((7
||w w'll
which also satisfics the second item of Assumption max(max, [|)(,, max, ((> (s)l + +
S by setting L1
3. Note that for small 8, I1" 8-contraction w.r.t. || Ilu.. Since there exists w" with F(w*)= 0, let D = D diag( (v*), we have
(w w²,, F(w)) (w -t F (w) - F(u*))
(w - w², v D(T Vu T V || [T )1
(V TyDDO DVW(W (w )" ), (1) T DVV) -1 v (T Vww - T ))=)) 1| w² 113=
(D)/2 12//21((2 (w wz) DD // DV -1 1p D(T Tu T V2"") - || [i((w -
| (wr w -²)]]~-> 11 T Vw 11 Vn"" II llue [ w² 112-
S -1 - 3) ) )12- S 5- B) Amin (v DV) - - 10
where the first inequality due to the Cauchy- Schwarz inequality and the second inequality is due to the 3-contrcction property of T
23

---

In addition, we have
E E|[l wx
Vw [1:=] El(wK -=> ( D (wwk w=)l S Amar (V D* DYBBlllwx w" w"1l - 0(1K))
C.2 Extension of General Value Function Approximation
Setting: In the general function approximation setting, consider known finite and bounded function class G C R$ to fit the robust value function V" i.e.,
G C R
|9] < oc, 19()) < co, Vg
(14)
Note that IPM-based RMDP with empirical robust Bellman operator 66 only applies to linear func- tion approximation. We implement it similarly by adding negative regularization with neural network approximating the robust values, which also induces robust behavior of the learned policy as illustrated in the experiments (Section 77. However, it may not directly match any specific uncer- tainty set. We thus only consider the DS-based RMDP in this general value function approximation setting.
We define the robust Bellman error as follows.
Definition 4 (Robust Bellman Error), Eg.bias == max, maXgeg miny'eg 11T g llur.
Cg. bibiis = 0, then the robust value realizable within the function class, i.e., V E 9 for any g.
C.2.1 Fitted Robust Value Evaluation Algorithm
We propose the fitted robust value evaluation (FRVE) in Algorithm 5 robust version of the fitted value evaluation commonly used in offline RL. This algorithm first samples a batch of data from the nominal model, then select the last half as training data for analytical purpose without losing the order while the Markovian data close the stationary distribution due to geometric mixing Assumption I and iteratively solve for a better robust value approximation based on the current approximation 9a and its robust value estimate T (gk).
Algorithm 5: Fitted Robust Value Evaluation (FRVE)
Input: n, K
Initialize: go.
for : = 0, T,..,, K do
Sample
(-18k)) Uk++1 according to P and 88+1 from yk+11
// For DS: uk+1 1mmm ii.d
phc.az> 8k+1 Uni (Va41) and ts in (3)
Let D {(Skk ax 3k+1)) 1- k== be the dataset
for & 1..,...,, K do
( (fF5g)(e,,a - g(s))
Update 1 = arg minges ক E(aONED
Return: gK
Theorem 6 (Convergence of FRVE). For DS RMDP with ê suggested by Proposition T3 the return of FRVE Algorihm has
8-contraction mapping for some 3 < 1. Under Assumption 7
B gxllu= [|]l=] (
Cg.stat
Eg.bias
1-
1-3¹
where Gmax = maxzed (T a, a,,,,,,))),, 11F 1
(gl1 and eg.stat = Ō(I/KK). Thus
E|||V* [k]]u=]] Ō(L/V(( KK) (Eg.biia).
24

---

Proof. By the contraction mapping of Tp
-|V
9K 1Ive
7T V
TTpp-- + [| -9Kllur
$ 5 9K-11l |T 9K-1 - -9kllu
K
gk k 1 + 1IV* gollur
km
Bk KK-k
Tp 9 9kllum + 3* (1lg0llvm
Note that 7 9k-1 is target that Ol is an approximation through MSE with Markovian data. the data is stationary, i.e., SK/2 v², applying Lemma 11 and the union bound over & (taking T g as a target for each E 9), we know with probability at least 5,
9 O (0
Gmann
log ( log(1/5) + (Eggbbas))
4k: 1.2..... K.
K
Let PA. be distribution on D with TK/2 μ. and let P.- be distribution on D with TK/2 V² Take as the true distribution of xx/2 according to the data sampling process as in Algorithm We know || 1" lTv = Ole K) by Assumption and thus
1pl gkllu~] S 2G | Pe- llv ED~ 11 9k-1 gxllus]
2G || v" 1Tv + ED [1] 9k-1 -kllu=]
log(19)) + +log(K) (K)
= O K) + Gmax
+ (Eggbbias)
K
The proof of the theorem is thus concluded.
D Robust Natural Actor Analysis
We analyze the robust natural component in the RNAC algorithm (Algorithm IT.
We first discuss the Fréchet supergradient of the robust value function in the first subsection. The second subsection focuses on the linear function approximation and proves the main theorems as stated in Section 5 of the main paper. The last subsection focuses on the general function approxi- mation.
D.1
Policy Gradient and Performance Difference
The robust value function J(0)= (p)
()) is in general not differentiable. But since is Lipschitz (w.rt. Lipschitz policy parameterization) it is differentiable almost everywhere according to Rademacher's 's theorem 14] At the place not differentiable, Fréchet supergradient V. of J is then
defined as
J(0') - J(0) (VJ(0), - < O.
lim sup
0'-0
| 01
When function is differentiable, J any point 0 has unique Fréchet supergradient, which the gradient of at
Proof of Lemma
2 The Fréchet supergradient exists for tabular RMDP 29 which is
1 - d (s)Q"(ss,) Vs, a,
V (T)
where VV,V* (p))... indicates the (s, a) coordinate of vector V V*(P). म = me a policy param- eterized by 0.
VT (p) Σ V (p) (orooals)
25

---

γ Eg B Ba (Q Vo log (a]s)
E B Bawn, (s, a) log (d]
where the first relation is by the chain rule of supergradient.
D.2
Linear Function Policy Approximation
Setting: This subsection considers the log-linear policy with
cxp()(s.a)T (aaas)) E. exp(o(s, a') 0) Ex
(15)
where ((s, a) E Rd is some known feature vector and R is the policy parameter. Let t R|S|A xd be the feature matrix by stacking up the feature vectors a(s.a)
Recall the discussion of the proposed RQNPG in Section function Q" via (u, a) = r(s,a) + infper... Vi given a value function approximation
We approximate the robust Q
V. from the robust critic, and then approximate Qu by a policy-compatible [52) robust Q- approximation Q" = tu. In other words, we project Qu onto span(T). Denote by IT (( diag(v" oz - diag(v" o E giSiI-AI((SILA the projection matrix onto space span () w.r.t. norm || Illtow We then define the approximation error &Q "iass below. When realizable, i.e., Q span ()), the approximation error EQibios O.
Definition 5, EQ,b == maX max d=dp aa! da or -1
Q"
We assume a finite relative condition number (Assumption 3 (similar to that in B)). The relative condition number is not necessarily related to the size of the state space (details are shown in Remark 6.3 of
Assumption 3. max max d=dp '" "=' .47" or vm"
sup
ballanttrr Toullaoo
S < 00 for some &.
Now we look at specific update 0t+1 RQNPG O',, nn, wt, N), where w RLTDDTTT K).
D.2.1 RQNPG One-Step Analysis Robust Q Function Approximation
In this update g+++1 RQNPG(0", ,1' w.
NN,,,, where w' RLTD To. K). RQNPG first approximates
Qu' (s, a) = r(s, a) + y inf p Vin = B((TT Vo. by Q" the caculation of un in Algorithm
(s, (s, a) = o(s, a) u, as
Let
v =- arg min oor [(Q (s, -s.,)
be the optimal approximation for the target Qwi. wt is approximated by stochastic approximation (c.f. Section F3 for a brief overview stochastic approximation) with a mean squared error loss
L(u; Vwt, T) = ( you ( ( 27
a(s,a)
We know ut the unique solution of
0 = -=-VaL(u; Vat, (u,,7 T) ((s.ay"))) oropo (o(s, a) (T ((s, o(s, a) Tw)]
Let F(u, x) be the function inside the expectation with x = (s, a, v/), ) and F(u) be the negative gra- dient - (u, V). We then solve this stochastic zero point problem by stochastic approximation as in
un-1 un Sno(sn an) (f ann Ba+1) 6(8n an)) un u, Gn FuFu(un
where F, = (Sns an. 1)+
Lemma 3 (Convergence of compatible Q function approximation (SGD with Markovian data)).
Under Assumption ! RONPG (Algorithm 3) with step sizes Sn ((1/n) guarantees E[][uN
w [2] = Ō and [ Qu: oor )
26

---

Proof of Lemma 3 The lemma is implied by Lemma 12 To see this, we only need to show that Assumption iis satisfied. We check the three conditions Assumption Bas follows.
1. The geometric mixing property of {= is straightforward given geometrically mixed {8k k:20
2. Since ||o(s, a)ll is bounded v(s, a) S E A, similar proof follows in the proof of
3. Since there exists ur with F(ux) and L(u; V, is Amin (Ba, (0 -strongly convex, we have
(u Uny F(u)) (u Ug F(u) F(u,))
(u Uv, Vilu;; V, VI(u"; V, -mmin (Evroo) ||u Ux |1?
where MipoR Eewv ann 0..
Denote by IT ( diag(v" on
))) ())))))11) diag(v OT) [ISAAII(SSIAI the projection matrix of function Q IR. [ onto matrix E RRSS|AA xd under norm || || We know Q": mg Qwe.
We have
BI 1u B[(nt, uN) (Φ diag(v' + uN]] S Amoa T diag(v' +)) - uN|| = Ō(1/N).
For the update at step t, g++1 RQNPG((', '7", wt, ,N and w' RLTD( K), let n' Tge be the policy at step t. Let u² uN (uN in Algorithm 3 and Lemma above shows that E[] Q 1 = ) This does not necessarily implies that Q" and Q are close since the property of the critic returned w³ required. We measure the difference between Q" and Q in the following lemma.
Let 1. = "t and wt = RLTD(TTO, K) is the output of RLTD at step t. Define EV,atat == m.x.= 1f BlIV Vi [2, and CVsttat = Ó(1V/)) by Theorem 3
Lemma 4. Under the conditions in Theorem
S and Assumption there is some e = Cstat + Ebias dp .re or v²"
that for any n, nt' and any d do ,= ..
Ble 1Q" (8, 10-00"0 Q=' (s. Sc,
(16)
where the outside expectation taken w.r.t. the randomness of the data collected in w BLTD(TT ngr K) and g++1 RQNPG( nn, wt, NN, Moreover, Extat = VVAl (EßEV,,tat + (tt.stat)
with Ev.stat + VT and EQ.stat Ō VN ): Ehins VIA I-p EV,bias + EQ,biax) with Evibias
and EQ,i in Definitions 3 and 5
respectively.
Proof of Lemma For any d 11
dz d=="
xe' or v= and for any n, we know for any Q'
- -
$ E
A (e (Q((.))) - (e VIAB [|| Q'll [/
To quantify the error between Qu' - Q=',, recall Qu! 11.' Qwe and we decompose into
Q"' - Q = (Q" - Qui)+ (II Q.. HE Qw:) + (IIZ' Qw! T='QT)) + (IT5 Q"' - QT),
and bound each term respectively. We can transfer the norm within the space spanned by & via the assumption that sPuulldstnif S Eullaloo Note that the first three terms all lie the span ()), we have the first term bounded by
E [ - Q²i Ildouair
I SE [1QU* Q²à 1l SE
[IQu" QQs 19411/.00
orl S ECQ
27

---

for some &Q,t = 0 VN
as in Lemma
3 The second term is bounded by
E |11 Qm 11 Qw? liaoUnit
S { I Qm - 11 Quo Illl' oxt
$ { [1Q
I E Vus [Ive] S EPV EllV
ViDi 11arl S EBEEV
for some EV,stat
1 VR
as in Theorem
The third term bounded by
[ Qu!
TT Q"1 |1
S ETE
[ Qwe
mh Q I1ut 5BCcvbias
S & |1Que
|
E
V [
< v |l < EB
1-
where the last inequality is by Definition
The last term is then bounded by I EQ.bias. We thus have
3 and inequality (3
Definition B Q" -Q" |Idoumie]
((..a)doorQ"" (s, a) - a (s,a)]] s vIAI (EEq.sta + EBE, + 1- VVibia + EQ,bias
EB
which concludes the proof.
D.2.2 RQNPG One-step Analysis Mirror Ascent Update
Now we look at the policy improvement of the update g RQMPG(0*, '7',, w², NN with Sn ((1/n) (Algorithm 3. where w' = RLTD( K). Let u' uN (uN in Algorithm 3), and we know the RQNPG update is 00++ 0 + +
This RQNPG update is equivalent to a certain mirror ascent update. Specifically, recall Q" (s, a) (s, a) n² is the approximated robust Q function, the RQNPG update 0++1 0² +'+r uu is equivalent to
T 1-1 t arg max (1) (Q"" x) - KI(x, m() E xEDA
(17)
where we let v. == (-18) and Qs == (s: for simplicity. Note that this update can viewed as a mirror descent step with Kl--divergence as Bregman divergence. Given this mirror descent formulation of policy update in Eq (77). the pushback property indicates that for any policy æ (Eq (2) in (68).
1' T + (I( m 2 (Q"" m.) KT m²) ( +
which is equivalent to the following fundamental inequality
n/ (Q n. =5) (Q"" क. - < KT( x²) KL +1+ (T ==))) (18)
Restatement of Theorem 4 (Approximate policy improvement) For any 2 O, we know
KL ++ + d 144 (Tt ++1 KT dp
s001 (n(+1, (441,79) m²)
v+ 2 2 va (p) +
(19)
(1 ?)n
1 1-
where KL = E. (())s(((( ((1ss) 2 0 and E[e]] = Ö + +x + O(Ebias).
Proof of Theorem
Let !+1 Ngets be the worst-case transition kernel w.r.t. policy x(+1, and 14 "(2=" - -Qu" oft - =.)]. We have
let Et = E
endp"
1 E
V (p) V= (p) 2
s w 1(0T" +++ -
snude 11 11 11 1QQ4" [+1 --()] + 1 E
snue 12 2 1(Q=" Qu" 1+1 -TiM
28

---

Algorithm 6: Robust Natural Policy Gradient (RNPG)
Input: 0, 1/, w, N
Initialize: No, 80, let π = To for 0, 1.........
do
Sample On ~ [ 8n), Un+1 according to Par.ax and determine Sn+1 from Vn+1
Update u = (1 Ajun
Sn. Va log Te (a (nn) (TzV (Bn an vn-1) (8n( - Vo log no (an T 26
// For DS: Un+1 = s1.m i.s.d.
Pansan 8nt1 ~ Unif(yn-1) and TØ in (3)
// For IPM: Da+1 8nt1 Penian and Tp in (6)
Return: 0 + mjN
KL gett utti (1t', xlt1) + KL ap at+ (n1411 m²)
(1-
1-7²
where the first inequality is by Lemma and the last inequality is by taking π n² in the funda- mental inequality Eq 18. which implies
1' T T²) > KL(T ) (L mT).
' can then be bounded by Lemma 4 with [[G]] S 26stat 20biass where statt Chias are
specified in Lemma with Estar =
VK
D.3 Extension of General Function Approximation of Policy
Setting: this subsection, we consider a general policy class of form
exp (fo(s.a)
(a(a))) Exee exp (fo (s)) 1 Rd
(20)
where fe is a differentiable function. This general policy class contains the log- log-linear policy class as special case by fo(s, a) a)
D.3.1 Robust Natural Policy Gradient with General Function Approximation
For the general policy class in Eq 20 we propose Robust NPG (RNPG) algorithm.
This algorithm be applied to RNAC (Algorithm I for the robust natural actor update. Now look at a specific update ge+1 RNPG(0 n7 w", .V. where is the output the robust critic at step Note that for the critic with general function approximation Eq. (44 we slightly abuse the notation by Vu = g', where gf is the output of the FRVE (Algorithm 5) at step t RNAC. We can view g E G is parameterized by some w, as indicated in the RNAC algorithm Algorithm
and Φº E R|S|IA[xd xd as the feature matrix stacking up feature vector 6² For each =,,1,.... I....,T T 1, we let of := 60h and &' := o0 for simplicity. The RNPG update is gr+1 t gr + n'u',, where = uy as the output of the stochastic gradient descent in Algorithm
Denote by (s a) = Ve log logre((e
Un+1 = (1 - A)u, + S. V log Ta (s,
(t550 Vna (sns On. Un+1) - Vani (sn) V 9 log To Ta(an)sa) TT Jun
RNPG approximates the value approximated advantage function And (s, a) r(s, a) +
Y yinfper,.. p. Vva - (s) by A == I'u. Note that (T Vun (5 an Bn+1) - Vir (5x) is an unbiased estimate of Apr an), i.c.
[[(TT' Vu (sn an, Bn+1) - Val (sn)(sn, and = Agg (Sns an).
RNPG thus is iteratively solving the following optimization
1 |4 Φ6 2ulll2ooot + X
2 111112
(21)
2
29

---

by stochastic approximation (stochastic gradient descent with Markovian data). Denote by uf the optimal value of the optimization, which also solution of the equation
0 = (66')((Am))
('u) Au
= (oxtopp (x, a) (1T Vor)), Vin (o, [ Au.
Theorem 7 (Convergence of compatible advantage function approximation (SGD with Markovian RNPO -q', w², N) (Algorithm 6 with step sizes Sa = (1/nn) guar-
data)). Under assumption
/
antees El][uN w=,1 = ( and A A [[ = (
Proof of Theorem 7 The theorem can be proved in the same manner as that for Lemma] since the objective function Eq (21 is strongly convex.
With slight abuse of notation, denote by E = ((a.a-ooox [6, (s. The opti- mal value w._ = (AI + (Tb) diag(v' o x x²)(²) (()) ( diag(v v¹ Aw:) satisfies ||u I
Al llutor v EEt= 1ol1 Let u' uN. Theorem gives [[[[ [13] < 2T[[1 ( We Ammm (2" then have [i]]
S under the following assumption.
Assumption (Bounded feature). Assume sup4 Σi= | T < co. Since ||A Ill < oo and there exists < U < oo that max, [[]] U.
14 bounded,
D.3.2 Robust General Advantage Function Approximation
Denote by Hh the projection mapping to the space { ||u/| s [| under metric ||
llstor..
Definition 6. CA.iia = max E 1 - -x
[|] g
Note that A,biis also implicitly depends on the choice of À since ut depends on X. If the realizable case, i.e., Ar E span(@'), Ca,bias = 0 O.
| o $ 6². Assumption 5. There is some 0 < < oo that for any 6, sup,, |
Lemma 5. Under the conditions in Theorems 7 aand Assumption [5] for any
ox- [[ ox- [A" (8, - AT (s, < <6'= + chias:
(22)
where the outside expectation is laken w.rl. the randomness of the data collected the robust natural actor and robust critic update. Moreover, éstat = Õ V OCeAbiis + EV.baas) for linear robust critic.
1 + )) Ebias = (CA,bbia + e bibi)) or
Proof of Lemma
5
To quantify the error between Au" Ad, we decompose it into
nr - A' 1-= (A"" Ao. + (TT Ane - IT's Awe) ) + (T Ams - IT A') + (TT A A²),
and bound each term respectively. The proof follows similarly to that in Lemma 4 by applying Theorem and Theorem 6
E Robust Natural Actor-Critic Analysis
In this section, we first state and prove the formal versions of the main theorems Theorem 1 and
Theorem 2 in Theorem g and Theorem 9 respectively. We then give the convergence of RNAC
employing general function approximation in Theorem 10
30

---

E.1 Linear Function Approximation
We introduce the detailed setup of the RNAC algorithm with linear function approximation, based on which the theorems are stated and proved.
RNAC-Linear Setting: We study the RNAC (Algorithm D with robust critic performing RLTD
(Algorithm with &n = ( as in Theorem 5 and robust natural actor performing RQNPG
in Eq (12) and log-linear policy as in Eq (15), for DS or IPM uncertainty sets taking 5 suggested by Proposition
(Algorithm with &.. (1/n)) as in Lemma under linear value function approximation
4 orr Lemma [ respectively. We assume Assumption !
and Assumption Batiipttionnolee hold.
1. the value approximation and policy in RNAC are updated as w' RL, K) and g RQNPG(0*, n7', w ,N), respectively. Denote by u' as un in RQNPG(0', nn', wt, .N) (Algorithm 3. which defines robust Q-function approximation Q" Let x² = =Tg, 1²' = Kx', V = v= for simplicity. We have the following lemma.
For each time t = 0, o..,..., T
Lemma 6. Under the RNAC-Linear Setting, for any t = 0, ......,.. T 1. we have (Q , ) 2 0, V's and
E 1(2 or. -
E(v++1(p) - 2x
7
where the expectation E is laken w.r.t. the data sampled by RNAC, and Estat + Chins is the same as that in Lemma 4
Proof of Lemma 6 Taking = n² in the fundamental inequality Eq 18) gives
(Q m 1 (T, m KT. 1+1 m²) 0,
which implies n² +++ is indeed improving x' along Q"' direction. We then have
T T
111
E
[(22) Tt. - [
1
1
? wn 11 1
E
1+1
1 - y s' mi 11 nnt 1(2 -2 m/ x5t"
E
1
a'mos (s' a'))]+ + 1- 7 d' wett 1(Q2 - Q5"
13' TTy Tty
=
s'nd wett1
lett1
(s) - vl+ (s) + 1-7 E
[(0g) Q m n [1
where the second inequality is by Lemma 8 The proof of the lemma is then concluded by taking expectation E[Ess~p-1]] on both sides and applying Lemma 4
Assumption 6. For initial state distribution p. there exists M that sup uPP - 11 S M < cc.
Theorem 8 (Formal statement of Theorem D Under RNAC-Linear Setting and Assumption 6 RNAC with geometrically increasing step sizes n¹
n²- for each = 1,2,..., T, satisfies
-VT (p) S
1-7
1-2 -
- (²) + log L4))
M
M
2
2M
11-7
(1
7)3
E,
where (stat Cbio as in Lemma with Estat -1 VK + Omitting the approximation
Ehios. the sample complexity for achieving robust optimal value (i.e., V*(p) - -EIV (p)) $ E) is
Ó(1/e2) by taking N = K @(1/²)) and T @(log(1/=).
Proof of Theorem Taking π = x in inequality (8),
we have
(Q - - + 'Q - + < m
KL (T,TTT,T)))
T/)) 17
KL(T, ,(+1),
(23)
31

---

We then take the expectation E|
s of [-]] on both sides. Note that
EI swad a KQ 3 x: x E & af 1( m
- + EI sna 1(02
Q
(1 7) (p) (p)) - 2c,
where the inequality is by Lemma 8 and Lemma I M = sup, bo we have
Then by Lemma 6 and Assumption 6 that
2x 2 M [[) - E[v++(())) - 1-7)
EI n nf 1Q2 m3 o.
since (Q=) T.. + < 0. The outside expectation E is taken w.r.t the data sampled by RNAC, and since all the following statements are under expectation E, we omit E in the proof for simplicity and bring it back at the end. Combining the inequality above and Eq (23), we have
(1 - (0) -
20 + M ('((p) - (p+ 1-7)
26
1 KL se (TT, π²) /
KL s (T" , tt11).
11
It follows that
- S (1- 1 (1-1 (V-())--V'))) - VV)()) + KL
-p)
Mn of (xt,
Mip de (TT (21 )+++)+ + (
1
KI,
+
M 1-7
which implies
1- 1 1
T
- (V')))-V(())) + 1 -
)
T-1 KT, donn a (TT", 20
(-(0)- - v²()) S
M
M
Mn
T-1
Σ
1-7
T-1-t
KL,
dg (TT", x²))
1-7
M
KT,
pentt (xt", xr7)
M
Mnp
Mnp-1
1=1
2M
6
E
+
1-7
M
1
Take geometrically increasing step sizes n/²
2
1-
M
for each t. Since M- = =sup,
||
-. 11 2
(1 11-7) 7) supx, N
|| Nr
1l,c. we have
1- 1-7
KL
(TT", (T'
Map-1 KL x 7*)
Mnj
<
1-x
M
(1-7KL,
KL, aginl (TT", ,x²)== - KI, aine (1T" ,x7) s 0.
Mn-11
M
We bring back the expectation E over the data and finally arrive at
()( EV] S (1
1-7)
(V* - (P)) (V))) + (1- 1 1-7)
T-1 KI,
2000 (T" x0)
M
M
Mn
2M
Y
M
where KL (T",, 7)) < log AA| when x² is a uniform policy.
Theorem 9 (Formal statement of Theorem 2}. Under RNAC-Linear Setting and Assumption Owhen
IPM uncertainty set is considered, take p 8²² and n¹ = (1 (0g-))/oo(((1 log(( RNAC satisfies
V*(p) - T
Σ E[V 5 (1 (1-7)(1 - ByT + 1 3
2 7
32

---

where 3 is in Assumption guaranttedd by Proposition 4 foo DS uncertainty set and assumed for IPM uncertainty set), and e Estot Ebios as in Lemma with Estat = = + ) Omitting the approximation Cbias. the sample complexity for achieving robust optimal value average (i.e., E[V I E) ((1/E²) by N = ((1/=²) and T ((1/s).
(D()) (
Proof of Theorem Taking = x in inequality
18 we have (2 T - (Q n. n.
1 S ( m3) - KL m
Since all the following statements are under expectation E over the data, omit IE in the proof for simplicity and bring it back at the end. According to Lemma and Lemma we have
E E -. - - = Ba ((0= T. - . + Es-ol(Q." Q T. -
2 (1 3) (p) - v'(()) - 2c.
Based on Lemma we have
2e
Ee TT. n. - 2 (((p) - (2+
1-7
It then follows that
s /v+ ( (p)) + KL x²) KLp ( xt11)
2 2
- v (1 - ())
+
2E.
n
Taking summation from t T from both sides we have
Σ v' (p) < VT(p) + KT,p( n
T
2 -
()()) - T
B)T 17(1 B)T
1 1 B
1-7
We then conclude the theorem by choosing over data,
(1 7) log( (og((AA)) and bringing back the expectation
T
(p)
+ Σ E(v'(W)
S (1 - >) 3)T
+
1 B E.
Discussion:
The linear convergence for NPG with linear function approximation has been previ-
ously studied in camonical MDP [4. We present the linear convergence of RNAC (Algorithm) in
Theorem 8 Compared to Theorem 8 Theorem ArrcoremPutilian Jutilizing constant step sizes and leads sublinear convergence, and it is proved only for initial state distribution n² Moreover, Theorem does not require Assumption 6 though may need Assumption for IPM uncertainty set.
E.2 General Function Approximation
RNAC-General Setting. We study the RNAC (Algorithm I with robust critic performing FRVE (Algorithm 5 and robust natural actor performing RNPG (Algorithm with Sn O(1/n) as in Theorem 7 under general value function approximation as in Eq (14) and general policy class as in Eq (0)). for DS uncertainty set taking å suggested by Proposition We assume Assumption !
Assumption and Assumption 4
[[]x,]]] S U', hold.
Theorem 10. Under RNAC-General Setting, suppose log (a(as an L-smooth function of 8.
Take p= p= and n¹ V
2KI.p(m"=09) for each t, RNAC satisfies
LUTT
22L T
C
(p) E
(0)
(1-3)VT 1-3
where B is in Assumption 6 (guaranteed by Proposition 4 for DS uncertainty set), and Catat + éhias as in Lemma with t'taa = - /
- ) Omitting the approximation éhas the sample
complexity for achieving e robust optimal value Ô(1/E2) by N K = =ō(1/e2) and T ((1/E)).
33

---

Proof. We have
(1 -
- -
(s (pa) [A'(s,
(s
E B((aa))
Vo log x (als) w²] + E (p0)) (A'(s,a) - 1 A (s)a)]
[
(a(s)
+ nLE
||
112)
S E B(a,))-por
log (aaass
+
"
2
< 1 E[KT, x²)
nLU2 (]
2 +,,
1)
where the first inequality is by Lemma 2 the first equality is by the definition of A (s, a) v log IT' (als) ((ls))uu Tu', and the second inequality is by the L-smoothness of log (a(a)s) and Lemma 5
We then conclude the proof by summing from t 0 to T - 1 from both sides and taking 2KLp(x*,a0) LU-T
Note that in RNAC-General Setting, the critic is employing general function approximation. where the IPM uncertainty set is not defined (c.f. Section C.2 for more discussion). It is not hard to show a similar result as in Theorem 10 for the RNAC with robust critic performing RLTD (Algorithm 2) and robust natural actor performing RNPG (Algorithm O for both DS and IPM uncertainty sets.
F Supporting Lemmas
We introduce some supporting lemmas for proving the results of this paper.
F1
Performance Difference Lemmas
key supporting lemma in the proof of convergence of policy gradient- basee methods is the perfor- mance difference lemma. In the canonical RL with fixed transition kernel K, we have the following performance lemma.
Lemma (Performance difference
23
For any policy n, n', and transition have
V (p) Vz (p)
E s- E (19
However, due to the non-singleton uncertainty set P, the worst-case transition kernel is a function of policy т, and we have the following performance difference inequality lemma. Lemma (Robust performance difference). For any policy n. n', denote K' = Kiz' and ki = Kix be their worst-case transition kernels, respectively. Then
E emaggi Eara (11)) AAT (s, a)) S V (0) (p) S 1- E
snad Buwnr a)).
T-7
Proof of Lemma
8 The LHS is by
V (p) (p) Bx
Σ at)(ss)))+ - -s(()))s))(s)))) (P)
E
Σ (((((s) + +~ -
120
1 snady (1)) (10)AAsss)))
E
The RHS is by
1
V (p) - -2 (p) < V (p) -V
E
Ra (A0)
1 2
34

---

Moreover, the optimality gap between the optimal policy x² and any policy is upper bounded as in the lemma below.
Lemma 9 (Robust optimality gap lemma). Under Assumption 2 for any π and any p.
1
V*(p) - (p) S 1-
E ondd we -arx; (s.
Proof of Lemma
9
(p) (0) = Eowp [1(8, (0 + +
B (r(s, + <n<(s(ss.o + (D)
+ t (n (1 (s)
< EeyylEann [A (s, + 7 -ll Exn((
< [A (s) + Boup PPinld')(V vT
- ...
1
$ 1 3 endd" w away awwyl1A
F.2 Concentration Lemmas with Markov samples
Assumption 7 (Uniformly geometric mixing, quantitative restatement of Assumption D. There exists some 0 < À < 1 and C > O such that for any policy n, the Markov chain {8x} induced by applying in the nominal model pe is geometrically ergodic with unique stationary distribution v", i.e., max, [[P(ss E -ss s) v* I|T S CX²,, Vk. The uniform convergence to unique stationary distribution implies that for any policy π the spectral gap (i.e., the difference between the largest and the second largest eigenvalues) of the state transition kernel has strictly positive lower bound.
Lemma 10 (Bernstein's inequality for stationary Markovian data, Theorem 2 in (1).. Suppose Zn, 72,.-..; Zu follow some stationary Markovian data in space Z with stationary distribution Az and spectral gap of the Markov chain strictly greater than O. For any function f : + c. that, [f and Ez [f(]] =z, with probability least 1 6,
1 ((Z)) s (n21/(1/8) CC2
cIn(1/8)
n
for some spectral gap-dependent multiplicative factors C₁ Cz.
Since we assume Assumption 7 throughout the paper during the analysis, the spectral gap is uni- formly lower bounded by some constant great than zero, and view C1, C2 as some constant that can be omitted in the big-O notation. We refer to 21 for further details of Bernstein's 's inequality for stationary Markovian data.
Lemma 11 (Lemma A.11 in [2] with Markovian data). Consider stationury Markev chain on domain X x Z that is geometrically mixing with transition p(a', z' [x, 2) = 2x ( 2 (='(z) and stationary distribution v xz Let ary Markovian data sampled with X1 ~ v. Given a function class G C R and func- tion G X x Z + R that Ez-pzix (1))) Z) gx( and [G(z, 2) I Gmar- Let
{(X1, Z1), (X2, Z2), (Xn; Zn)) be station-
g = arg mingeg 1/2 Σ (maa)ED(G(( - g(x))² be the MSE estimate of g within G, then with probability at least 8.
log( (1/8))
Eenr [0(x)) -0)0))g())))) (x))) 0 Gmex
+ (Cbbaa))
(24)
35

---

where Ebios mingeg 11g g" Ilu.
Proof. The proof follows the same as 22. The only difference replacing the canonical Bernstein's inequality with i..d. data by Bernstein's s inequality for stationary Markovian data in Lemma TO
F.3 Convergence of Stochastic Approximation
F Rd Z + Rd is a stochastic operator. The stochastic approximation algorithm updates the parameter by wk+1 = Wk + a Zn), where (Zo. Zi....) .) is a Markov chain, that is geometri- cally ergodic for some C 0, 1 X 0 with stationary distribution v, i.c., max, [IP(Zx E -1/0- = The stochastic approximation algorithm solves the
2) v/lrv CA*, Yk. (c.f. Assumption I.
following equation
0 F(w) == Ez~ [F(w; Z)},
under the following assumption and appropriate step sizes (a1, 02....). Assumption 8.
1. (Zo, ......) ......))n) are geometrically mixed to the stationary distribution.
2. 3/1 > that [[ F(w', =)|l S Lillw - =w'l [[((0, < Lı for any w, w/ E
R4 2 E Z.
3. F(w) has unique solution w and there exists co -col|a w w"1 for any w Rd
> that (w - T S
The second condition of Assumption 8 is Lipschitz condition of the operator F, and the third condition the "strongly-coneavitt" structure of the averaged operator F.
Lemma 12 (Big-O version of Corollary 2.1.2 in (10). Under Assumption
X taking appropriate
0% (1/k)) gives [[[]wx w [|2] (1)
To apply the lemma above, we need to show that the proposed operator F satisfies Assumption g
G More Related Works
The framework of the robust Markov decision process (RMDP) is proposed by 19 40 to learn the optimal robust policy that achieves the optimal worst-case performance over all possible models in the uncertainty set. For the planning problem of RMDP, Iyengar [99 and Nilim et al. show that value iteration achieves linear convergence to the optimal robust values.
When the transition model is unknown, several model-based and value-based approaches have been proposed and studied for robust RL in both the tabular setting and the function approximation set- ting. Under the tabular setting, Xu et al.
(64) design the model-based robust phase value learning algorithm and demonstrates an O sample complexity bound. Under the function approx- imation setting, Panaganti al. (43 develop robust fitted Q-iteration with the total variation uncertainty set and show an (11/=") sample complexity to achieve approximate optimality and [6] develop model-based method with the same sample complexity under certain coverage assump- tion. However, these methods are not scalable to continuous control problems. Instead, policy-based approaches directly parameterize policy and have more representation power modeling stochas- tic policies, more flexibility for policy manipulation, and a better ability to solve robotics control problems with large action space.
The existing policy-based methods with convergence guarantees mainly focus on the tabular setting. Wang et al. [61] show O(1/e7) sample complexity for robust actor-critic with R-contamination uncertainty sets. et al. 29 prove an ((1/e²) sample complexity for robust natural actor-critic assuming the existence of an oracle to solve the inner optimization problem. Kumar et al. [27] de- velop a robust policy gradient method based on & norm uncertainty sets and extends its formulation under the s-rectangular assumption. All works mentioned above are limited to the tabular case with critic Q and adopt computationally infeasible uncertainty sets the case of the large state space. Kuang et al. [26] illustrate state disturbance view of Wasserstein metric-based RMDP, which can be generalized to the large state space. However, they only provide a policy iteration guarantee in the tabular setting (contraction under || |loo). Instead, we focus on large-scale robust RL, propose
36

---

two computationally efficient uncertainty sets, and demonstrate O(1/2²) (resp.. O(1/e*)) sam- ple complexity under linear (resp., general) function approximation. Additionally, we regard V as a critic instead of Q, which is closer to the actual implementation of on-policy natural actor-critic algorithms.
37


Reviews:
[{"review_id": "WqhzY1yaJy", "reviewer": "Reviewer_Fq66", "summary": "RL methods trained on simulators suffered from generalization problems because of the \"simulation-to-reality-gap\". Previous works proposed robust RL methods in a tabular setting, with limited search spaces. The paper aims to develop a computationally tractable robust RL algorithm with large search spaces. To this end, the paper proposed two novel uncertainty sets and the first policy-based approach for robust RL with provable convergence guarantees.", "questions": "- Can previous tabulated-based robust RL methods be applied to the experiments in Sec. 7? If so, what about the comparison results? On the other hand, can the author provide some experiments to directly compare the proposed method with large search space to the previous one with limited search space to demonstrate the benefits of the proposed method?", "limitations": "The paper has discussed its limitations.", "rating": 6, "confidence": 1, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper studies a critical problem. Several technical contributions are proposed to devise a robust policy-based RL method with a large search space. The theoretical analysis seems solid.", "weaknesses": "The paper aims to devise a robust RL method. More real-world experiments are expected to demonstrate the robustness of the proposed methods.\n\n---------------------\nAfter reading the rebuttal, my main concerns were addressed.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the comments and suggestions. We are encouraged by the fact that the reviewer finds that our paper \"studies a critical problem\" and provides \"solid theoretical analysis\". Please see our response below with respect to the specific comments. Please note that line numbers are based on the supplementary material (RNAC-full.pdf). We believe  that we have addressed all the concerns, and we sincerely hope that the reviewer would consider increasing the score.  \n\n**Q1.** \"More real-world experiments are expected to demonstrate the robustness of the proposed methods.\"\n\n**Response:**\nWe would like to emphasize that our paper is primarily a   theoretical work that develops large-scale robust RL algorithms with provable convergence guarantees, the first of their kind to the best of our knowledge. We have also included extensive simulations of our RNAC algorithms on MuJoCo environments (Hopper-v3, Walker2d-v3, and HalfCheetach-v3) and have demonstrated their superior performance compared to many benchmarks. Significantly different from similar theoretical works on RL algorithms which limit the evaluations only to simulation experiments, we have gone one step further and demonstrated the effectiveness of our RNAC algorithm on a real-world mobile robot. **We have included the video of this real-world robot demonstration**, see Section 7.2 and the supplementary files. \n\nNow, based on your suggestion (also suggested by Reviewer haxo), we have added the results from additional MuJoCo and TurtleBot environments to illustrate the superior performance and effectiveness of our RNAC algorithm. **Please see Authors' Response to All for details**. We sincerely hope that these additional experiments will alleviate the reviewer's concerns. \n\n**Q2.** \"Can previous tabulated-based robust RL methods be applied to the experiments in Sec. 7? Can the authors provide some experiments to directly compare the proposed method with large search space to the previous one with limited search space to demonstrate the benefits of the proposed method?\"\n\n**Response:**\nWe thank the reviewer for this suggestion. In Section 7, we run the proposed algorithm and non-robust baselines in large-scale MuJoCo (Hopper-v3, Walker2d-v3, and HalfCheetah-v3) and TurtleBot experiments with continuous state spaces and continuous action spaces. The uncertainty sets studied in previous works cannot scale up as discussed in Lines 42-49 and Appendix B, which makes them inapplicable to the experiments in Section 7. (Previous tabular-based papers show experimental results only in the tabular setting, as in [25, 57].) Therefore, new *large-scale* robust RL algorithms with corresponding convergence guarantees and superior empirical results are required, which is the major motivation of this work.\n\n[25] Navdeep Kumar, Esther Derman, Matthieu Geist, Kfir Levy, and Shie Mannor. Policy gradient for s-rectangular robust Markov decision processes. arXiv preprint arXiv:2301.13589, 2023.\n\n[57] Yue Wang and Shaofeng Zou. Policy gradient method for robust reinforcement learning. In International Conference on Machine Learning, pages 23484–23526. PMLR, 2022. "}, {"review_id": "jYSorSegs1", "reviewer": "Reviewer_haxo", "summary": "This paper studies the sim-to-real transfer problem. It extends the learning of a robust policy by using the framework of robust Markov decision processes (RMDPs). It extends this paradigm to large state and action spaces using two uncertainty set formulations: double sampling, and integral probability metric.\nThese formulations are then used in the proposed algorithm robust natural actor critic (RNAC). RNAC is tested in MuJoCo as well as on a real robot.", "questions": "* In the second to last paragraph of Section 2, when describing the single worst-case kernel, is this kernel constant for the entire state space or varying?\n* In the double sampling setup, does $\\sum \\alpha = 1$ in Equation (3)? ", "limitations": "n/a", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "* Proposed uncertainty sets as well as the RNAC algorithm seem like practical steps forward in sim-to-real transfer with robustness approaches.\n* The theoretical analysis seems interesting", "weaknesses": "* The experiments compare only to PPO. They should compare to other sim-to-real methods such as dynamics randomization [1] or action noise envelope [2].\n* The related works being relegated to the appendix seems like a red flag. The authors should better organize the paper to include related works and comparisons to the main paper.\n\n### References\n[1] Peng, X.B., Andrychowicz, M., Zaremba, W. and Abbeel, P., 2018, May. Sim-to-real transfer of robotic control with dynamics randomization. In 2018 IEEE international conference on robotics and automation (ICRA) (pp. 3803-3810). IEEE.\n\n[2] Jakobi, N., Husbands, P. and Harvey, I., 1995. Noise and the reality gap: The use of simulation in evolutionary robotics. In Advances in Artificial Life: Third European Conference on Artificial Life Granada, Spain, June 4–6, 1995 Proceedings 3 (pp. 704-720). Springer Berlin Heidelberg.\n\n\n================================\n\nThe additional experiments alleviate my concerns about the experimental analysis.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your comments and suggestions. We are encouraged by the fact that the reviewer finds that our paper takes \"practical steps forward in sim-to-real transfer with robustness approaches\" and has \"interesting theoretical analysis\". Please see our response below with respect to the specific comments. Please note that line numbers are based on the supplementary material (RNAC-full.pdf). We believe that we have addressed all the concerns, and we sincerely hope that the reviewer would consider increasing the score.\n\n**Q1.** \"The experiments compare only to PPO. They should compare to other sim-to-real methods such as dynamics randomization or action noise envelope.\"\n\n**Response:** We compare the proposed algorithm with the reviewer's suggested baselines -- \"dynamics randomization\" and \"action noise envelope\" for MuJoco Envs and TurtleBot experiment.\n\nPlease note that in Appendix A.3, we have in fact compared the proposed RNAC algorithms with soft actor-critic and soft-robust PPO algorithms in MuJoCo, and indeed reported results in Figure 5 with detailed explanation in Lines 557-582. The core idea of the soft robust algorithm is the same as \"dynamics randomization\", where the agent learns an optimal policy based on a distribution over an uncertainty set instead of considering the worst-case scenario. We add \"action noise envelope\" (Gaussian noise $\\mathcal{N}(0, 0.05)$) as an additional baseline of Figure 5 in the attached pdf. In Figure 1 (attached new pdf), we also observe that the cumulative reward of RNAC-PPO decays much slower compared with action noise envelope, which further demonstrates the robust performance of the proposed algorithms.\n\nAdditionally, based on the reviewer's suggestion, we have added two more baselines (i.e., \"dynamics randomization\" and \"action noise envelope\") to demonstrate the robustness of the proposed methods in the real-world TurtleBot environment. As shown in Figure 2 (attached new pdf), the proposed algorithms RNAC-PPO enjoy higher target-reaching rates (100\\%) compared with action noise envelope (67.5\\%), dynamic randomization (9\\%), and PPO (0\\%) under testing perturbed environments, which illustrates the robustness of the RNAC-PPO algorithms. Please see Lines 330-345 and Lines 584-600 for details of the TurtleBot environments. **Please also see Authors' Response to All.**\n\n**Q2.** \"The related works being relegated to the appendix seems like a red flag. The authors should better organize the paper to include related works and comparisons to the main paper.\"\n\n**Response:** \nWe have in fact discussed the most important related works quite extensively in the introduction. Please note that lines 30-66 are indeed a survey of related works, where almost all references have been mentioned. We leave the additional discussion of the technical sides of these works, e.g., convergence rate or sample complexity, to Appendix G, mostly due to space constraints. However, to avoid confusion, we will add a \"related work\" subsection under the introduction section in our revision.\n\n**Q3.** \"In the second to last paragraph of Section 2, when describing the single worst-case kernel, is this kernel constant for the entire state space or varying?\"\n\n**Response:** As adopted in all previous works in reinforcement learning literature, we refer to a map $p: \\mathcal{S} \\times \\mathcal{A} \\rightarrow \\Delta_{\\mathcal{S}}$ as a transition kernel. For each current state $s$ and current action $a$, the worst-case kernel $p(s'| s, a)$ is the probability that the next state is $s'$. It does depend on $s$. \n\nThe second to the last paragraph of Section 2 summarizes the existing results on robust MDP in the literature [18, 37], so as to lay the foundation of robust RL. The major claim in the robust MDP with $(s,a)$-rectangular uncertainty set is that the optimal policy is stationary (not time-varying) and the worst-case transition for any stationary policy is also stationary. \n\n[18] Garud N Iyengar. Robust dynamic programming. Mathematics of Operations Research, 30(2):257–280, 2005.\n\n[37] Arnab Nilim and Laurent El Ghaoui. Robust control of markov decision processes with uncertain transition matrices. Operations Research, 53(5):780–798, 2005.\n\n**Q4.** \"In the double sampling setup, does $\\sum \\alpha =1$ in Equation (3)?\"\n\n**Response:** Yes, in Eq (3), $\\sum_{i=1}^m \\alpha_i = 1$ since $\\alpha \\in \\Delta_{[m]}$, where $\\Delta_{[m]}$ is a probability simplex, i.e., $\\Delta_{[m]} = \\{ \\beta \\in \\mathbb{R}^m: \\sum_{i=1}^m \\beta_{i} = 1, \\beta_i \\geq 0, \\forall~i\\}$. "}, {"review_id": "l2f9wqLihX", "reviewer": "Reviewer_r1LZ", "summary": "This paper tackles robust reinforcement learning in large state spaces, where the transition kernel is accessible only in a nominal setting. The authors demonstrate that the $f$-divergence, R-contamination, and the $l_{p}$ norm are computationally infeasible in the context of robust RL for large state spaces. To overcome this limitation, the authors propose two new tractable uncertainty set formulations suitable for large dimensions: double sampling (DS) and the integral probability metric (IPM).\nDS involves independently and identically distributed state sampling following a transition kernel $p^o_{s,a}$. The IPM corresponds to the robust Bellman operator, but with a regularization term on the norm of weights. Both approaches are enabling Robust RL in scenarios previously hindered by computational complexity.\nThe paper introduces a new algorithm, the Robust Natural Actor Critic (RNAC), for training both a critic and an actor for the proposed IPM and double sampling uncertainty sets. The authors provide convergence guarantees for the RNAC algorithm.\nFinally, the authors demonstrate the efficency of their approach via two applications: one involving the suite of MuJoCo environments and the other, a real-world robotics application. These practical applications lend credence to the theoretical contributions and the robustness of the proposed approach.\n", "questions": "- In lines 175-177, why did you not apply regularization to the bias parameter in the last layer? Moreover, this seems inconsistent with the provided implementation (lines 201-206 in the `RNAC-ppo/ppo_continious.py` file), where regularization is applied to all the critic's layers.\n\n- Doesn't the IPM's proposed regularization ultimately reduce the Lipschitz constant of the learned function, making the agent less sensitive to state variations?\n", "limitations": "The authors mention their limitations as future research directions. We appreciate the authors for being upfront.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 2, "contribution": 3, "strengths": "- The authors provide two straightforward and computationally feasible uncertainty set formulations for large state spaces.\n- The paper offers substantial theoretical contributions.\n- The real-world robotics application lends credibility to the paper's robustness claims.\n", "weaknesses": "- The convergence guarantees are valid for $(s,a)$-rectangular uncertainty sets, which is rather limiting. However, it is commendable that the authors have acknowledged this limitation in their work and suggested it as an avenue for future research.\n- The paper seems incomplete without the appendix. The need to constantly refer to the appendix disrupts the flow of reading.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the clear summary of the paper, finding our theoretical results of substantial contribution and our empirical evaluations credible. \n\n**Q1.** \"The convergence guarantees are valid for $(s,a)$-rectangular uncertainty sets, which is rather limiting. However, it is commendable that the authors have acknowledged this limitation in their work and suggested it as an avenue for future research.\"\n\n**Response:** As the reviewer noted, the $(s,a)$-rectangularity assumption is now a standard assumption used in the robust MDP/RL literature that can yield  tractable theoretical analysis. We completely agree with the reviewer  that this assumption is indeed a limitation of the existing literature, including ours.  We believe alleviating this limitation while maintaining theoretical tractability is an essential endeavor for future research in robust RL. \n\n**Q2.** \"The paper seems incomplete without the appendix. The need to constantly refer to the appendix disrupts the flow of reading.\"\n\n**Response:** We thank the reviewer's valuable feedback. We refer to the appendix for detailed or technical discussions in several places in the main paper due to space limits. To eliminate the disruptions of the flow, we will not refer to the appendix at each different place in the main paper, but we will simply add one remark discussing the appendix and its supporting relation to the sections all in one place. We would be glad to take action on any further suggestions from the reviewer to make our presentation better. \n\n**Q3.** \"In lines 175-177, why did you not apply regularization to the bias parameter in the last layer? Moreover, this seems inconsistent with the provided implementation (lines 201-206 in the RNAC-ppo/ppo\\_continious.py file), where regularization is applied to all the critic's layers.\"\n\n**Response:** It is theoretically proved in Proposition 1 that under the designed IPM uncertainty set, the regularization does not include the bias parameter. The regularization without bias parameter is thus an implication of the structure of the designed IPM uncertainty set. \nWe thank the reviewer's careful examination of our code. The theory is consistent with our implementation, where in lines 201-206 of RNAC-ppo/ppo\\_continous.py file, the last layer's bias term is not included in the regularization, cf. bias\\_norm[0:-1] in line 206. \n\n**Q4.** \"Doesn't the IPM's proposed regularization ultimately reduce the Lipschitz constant of the learned function, making the agent less sensitive to state variations?\"\n\n**Response:** We agree with the reviewer's intuition that this regularization has the effect of reducing the Lipschitz constant of the value function, and thus the learned value function is less sensitive with respect to the state variations. This intuition can also corroborate the theoretical finding of regularization without bias term in Proposition 1, since the bias term corresponds to the vertical shift of the value function and has no impact on the Lipschitz constant of the value function. "}, {"review_id": "4YkioAB9wZ", "reviewer": "Reviewer_4Et9", "summary": "This paper studies the actor-critic approach for robust RL. Especially, a Double-Sampling Uncertainty Set and an Integral Probability Metric Uncertainty Set are developed to overcome the curse of problem scale. A robust natural Actor-Critic algorithm is then proposed with convergence results. A significant number of experiments are designed.", "questions": "Can you explain the motivation for the designing of the uncertainty sets? In what sense do they imply robustness and uncertainty?", "limitations": "See the parts above.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The paper is well-written and clear in general. The design of the two uncertainty sets is new and novel, which shows advantages under large-scale problems.", "weaknesses": "1. The motivation for designing the two uncertainty sets is somehow unclear to me. I understand there is uncertainty in the sets designed, but don't understand the motivation of this uncertainty set. In lines 640-646, the authors explain the uncertainty set contains transition kernels that are perturbed from the uniform distribution, this explanation seems unclear to me, and I can't understand the motivation for such a definition. \n2. One of the critical problems in studying robust RL with function approximation is the contraction of the approximated Bellman operator. The approach used in this paper is similar to the previous ones, i.e., use conditions on the radius of the uncertainty set and discount factor. This hence reduces the novelty and contribution of the paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are encouraged by the reviewer's comments that the paper is well-written, and that the designed uncertainty sets are novel and show advantages for large-scale problems. Below, we give a detailed response to your comments. We believe that we have addressed all your concerns, and we sincerely hope that the reviewer would consider increasing their score. Please note that line numbers are based on the supplementary material (RNAC-full.pdf). \n\n**Q1.** \"The motivation for designing the two uncertainty sets is somehow unclear...\"\n\n**Response:** From the perspective of the development of robust RL in the literature, previous works have considered multiple types of uncertainty sets, such as KL uncertainty set, Total-Variation uncertainty set, and Chi-square uncertainty set. However, as we have discussed in  Lines 42-49 and Appendix B, these uncertainty sets do not scale up for function approximation in large state spaces. This motivates the design of tractable uncertainty sets for large state spaces. The tractability is provided by the computationally efficient empirical robust Bellman operators of the designed uncertainty sets (Eq (3) and Eq (6)). \n\nThe Double-Sampling (DS) uncertainty set (cf. Lines 134-140 and 640-646) can be motivated and explained as follows. In canonical RL, the next-step state $s'$ sampled from the nominal model, i.e., $s' \\sim p^0_{s, a}$ can be viewed equivalently as a double-sampling process: first generate $m$ states  $s_1', s_2', \\ldots, s_m'$ sampled i.i.d. according to $p^0_{s, a}$ , and then uniformly select one from these $m$ states as the next-step state $s'$. Double sampling gets its name from these two phases of sampling. With this interpretation, we can thus perturb the nominal transition $p^0_{s, a}$ by perturbing the second phase sampling from uniform selection. We let the selection distribution be $\\alpha \\in \\Delta(m)$ and allow it to deviate from the uniform distribution $\\text{Unif}(m)$ as $\\mathrm{d}(\\alpha, \\text{Unif}(m)) \\leq \\delta$. Due to this perturbation of the second phase of the double sampling process ($\\alpha$ can depend on the generated $m$ states of the first phase), the induced next-step state $s'$ will not follow the nominal kernel $p^0_{s, a}$ but a new kernel that lies in the uncertainty set. The DS uncertainty set is implicitly defined as the set of all such new kernels, which is determined by $m, \\mathrm{d}(\\cdot, \\cdot), \\delta$. \n\nIPM is a general class of divergence measures that contains many metrics as special cases for different function classes (cf. Lines 158-160). IPM takes advantage of the prior information in the function class, which is helpful when considering RL with a large state space under function approximation. We take a function class based on the feature matrix Eq. (5), and the designed IPM-based uncertainty set based on this function class takes advantage of the underlining structure of the value function approximation. \n\nPlease let us know if the above discussion is clearer for motivating the design of the  uncertainty sets. If so, we will add the discussion in the revision. \n\n**Q2.** \"...The approach used in this paper is similar to the previous ones, i.e., use conditions on the radius of the uncertainty set and discount factor. This hence reduces the novelty and contribution of the paper.\"\n\n**Response:**\nWhile we acknowledge the partial adoption of the approach in [47] by Assumption 2 for the DS uncertainty set (Proposition 2), it is essential to emphasize that [47] does not offer any specific uncertainty set satisfying Assumption 2. Our paper introduces technical novelty by demonstrating that the commonly considered f-divergence may violate Assumption 2 (Proposition 3). Additionally, for the IPM uncertainty sets, their contraction property shown in Lemma 1 is independent of the previous approach. Furthermore, a large volume of the analysis in the paper is regarding the convergence of the proposed algorithm (e.g., Theorems 1-4 in the main paper), which also constitutes a significant technical contribution. The fact that the proof of Proposition 2 partly leverages a previous approach diminishes neither the overall novelty and contribution of the paper, nor the technical contribution. \n\nIn addition, the major novelty of the paper can be attributed to the design of the new uncertainty sets and the robust policy-based algorithm. The major contributions, besides the novel uncertainty sets and algorithms, are both theoretical -- convergence guarantees under function approximation for robust RL, as well as empirical -- extensive experiments in Mujoco simulation and real-world TurtleBots suggesting robust behavior of the proposed algorithm. By providing guarantees we have successfully closed an important gap in the literature on a policy-based approach for robust RL under function approximation.\n\n[47] Aviv Tamar, Shie Mannor, and Huan Xu. Scaling up robust mdps using function approximation. In International conference on machine learning, pages 181–189. PMLR, 2014.\n\n**Q3.** \"In what sense do they imply robustness and uncertainty?\"\n\n**Response:** By the definition of the uncertainty set for the Robust MDP (RMDP, cf. Line 103-119), the results establish robustness in the sense that the optimal policy of the RMDP achieves the best performance for the worst transition model in the uncertainty set. Equipped with the newly designed DS or IPM uncertainty sets, the proposed algorithm aims to find the optimal policy of the corresponding RMDP. We have demonstrated that the proposed algorithm with either DS or IPM uncertainty sets results in robust policy, in the sense that the learned policies have more stable performances in perturbed environments, as shown in Figures 1-2 in Section 7, Figures 4-5 in Appendix A, and Figures 1-2 in the attached new pdf. "}]

Author rebuttal:
## Authors' Response to All

We wholeheartedly thank all reviewers for their time and their constructive feedback on our paper. As suggested by Reviewers Fq66 and haxo, **we have added additional MuJoCo and real-world TurtleBot experiments** in the attached new pdf.

As suggested by Reviewer haxo, we have added more baselines (i.e., "dynamics randomization" and "action noise envelope") to demonstrate the robustness of the proposed methods in the real-world TurtleBot environment. As shown in Figure 2 (in the attached new pdf), the proposed algorithm RNAC-PPO enjoys higher target reaching rates (100\%), compared with action noise envelope (67.5\%), dynamic randomization (9\%), and PPO (0\%), under perturbed testing environments, which illustrates the robustness of the RNAC-PPO algorithm. Please see Lines 330-345 and Lines 584-600 for details of the TurtleBot environments.

We have also added one more baseline (i.e., "action noise envelope") to illustrate the robustness of the proposed methods in MuJoCo environments. In Figure 5 (original paper), we have already compared the proposed RNAC-PPO with PPO, soft actor-critic, and soft-robust PPO (same idea as dynamics randomization). Please see Lines 557-582 for a detailed description of the robust performance of RNAC-PPO. In Figure 1 in the attached new pdf, we also observe that the cumulative reward of RNAC-PPO decays much slower compared with action noise envelope, which further demonstrates the robust performance of the proposed algorithms.

*This paper closes an important gap in the policy-based approaches for robust RL under **function approximation** with **theoretical guarantee**.* Though a theory-driven paper with two novel uncertainty set designs and a robust policy-based algorithm with convergence guarantee, extensive experiments were conducted in the paper and more baselines are included during the rebuttal that lend credence to the theoretical contribution. We also hope that our detailed response will convince the reviewers of the value of our work and they will consider increasing their evaluations accordingly.

Meta-review: The paper proposes an algorithm based on the natural actor critic that implements robustness, and presents both theoretical guarantees as well as experiments to show the advantage of the procedure.
Some limitations of the paper include limited numerical experiments and some organizational issues with respect to the appendix, and some limitations of the theoretical setup. But these seem to be addressable in a revised version as well as with further research.
Decision: Accept (poster)