Robust Constrained Reinforcement Learning
Authors: Yue Wang
Fei Miao
Shaofeng Zou
Venue: Submitted to ICLR 2023 (2023)

Abstract: Constrained reinforcement learning is to maximize the reward subject to constraints on utilities/costs. However, in practice it is often the case  that the training environment is not the same as the test one, due to, e.g., modeling error, adversarial attack, non-stationarity, resulting in severe performance degradation and more importantly constraint violation in the test environment. To address this challenge, we formulate the framework of robust constrained reinforcement learning under model uncertainty, where the MDP is not fixed but lies in some uncertainty set. The goal is two fold: 1) to guarantee that constraints on utilities/costs are satisfied for all MDPs in the uncertainty set, and 2) to maximize the worst-case reward performance over the uncertainty set. We design a robust primal-dual approach, and further develop theoretical guarantee on its convergence, complexity and robust feasibility. We then investigate a concrete example of $\delta$-contamination uncertainty set, design an online and model-free algorithm and theoretically characterize its sample complexity. 

Under review as a conference paper at ICLR 2023
ROBUST CONSTRAINED REINFORCEMENT LEARNING
Anonymous authors
Paper under double-blind review
ABSTRACT
Constrained reinforcement learning is to maximize the reward subject to constraints utilities/costs. However, in practice it is often the case that the training envi- ronment is not the same as the test one, due to, e.g., modeling error, adversarial attack, non-stationarity, resulting in severe performance degradation and more importantly constraint violation in the test environment. To address this challenge, we formulate the framework of robust constrained reinforcement learning under model uncertainty, where the MDP is not fixed but lies in some uncertainty set, The goal is fold: 1) guarantec that constraints on utilities/costs are satisfied for all MDPs in the uncertainty set, and 2) to maximize the worst-case reward performance over the uncertainty set. We design robust primal-dual approach, and further develop theoretical guarantee on its convergence, complexity and robust feasibility. We then investigate a concrete example of o-contamination uncertainty set, design an online and model-free algorithm and theoretically characterize its sample complexity.
INTRODUCTION
In many practical reinforcement learning (RL) applications, it is critical for an agent to meet certain constraints on utilities/costs while maximizing the reward. This problem is usually modeled as the constrained Markov decision processes (CMDPs) (Altman 1999). Consider CMDP with state space 8, action space A, transition kernel = {r E A s E S,a E A}, reward and utility functions: 8 x A + [0, 11. < i < m. and discount factor 7. The goal of CMDP is to find a stationary policy π 8 + AA that maximizes the expected reward subject to constraints on the utility:
max E..P xell
Σ rrS, A.)S -==
s.t. E.,P
Σ ==
(S,, S.) P 2 b, sis m, (1)
where p is the initial state distribution, b; 's are some thresholds and E,,, denotes the expectation when the agent follows policy æ and the environment transits following P.
In practice, is often the case that the environment on which the learned policy will deploy (the test environment) possibly deviates from the training one, due to, e.g., modeling error of the simulator, adversarial attack, and -tatotationarity. This could lead to a significant performance degradation in reward, and more importantly, constraints may not be satisfied anymore, which is severe in safety- critical applications. For example, a drone may run out of battery and crash due to mismatch between training and test environments. This hence motivates the study of robust constrained RL in this paper. In this paper, we take a pessimistic approach in face of uncertainty. Specifically, consider a set of transition kernels P. which is usually constructed in way to include the test environment with high probability (Iyengar 2005 Nilim& & El Ghaoui 2004 Bagnell et al. 2001). The learned policy should satisfy the constraints under all these environments in P. i.e., VP
P.
Ex. Σ
C/ 4r) ~
2 b,,
(2)
which is equivalent to minpe E,,P EE 7 Y((S,, Ar) pl N by At the same time, we aim to
optimize the worst-case reward performance over P:
max min E. HEll PEP
Σ r'r(S,, A.) ~ p
"x denotes the probability simplex supported the X.

---

Under review as a conference paper at ICLR 2023
1 Σ (S 4r]50 ~ p 2 bi, sis m.
s.t. min E PEP
On one hand, a feasible solution to eq. (3) always satisfies eq. (2). and on the other hand, the solution to eq. (3) provides performance guarantee for any P P. We note that our approach and analysis can also be applied to the optimistic approach in face of uncertainty.
In this paper, design and analyze robust primal-dual algorithm for the problem of robust constrained RL. In particular, the technical challenges and our major contributions are as follows.
We take the Lagrange multiplier method to solve the constrained policy optimization problem. A first question is that whether the primal problem is equivalent to the dual problem, i.e., whether the duality gap is zero. For non-robust constrained RL, the Lagrange function has zero duality gap (Paternain et al. 2019 Alrman 1999). However, we show that this is not necessarily true in the robust constrained setting. Note that the set of visitation distribution being convex one key property to show zero duality gap of constrained MDP (Altman. 1999] Paternain et al. (201)). In this paper, we constructed a novel counter example showing that the set of robust visitation distributions for our robust problem is non-convex.
In the dual problem of non-robust CMDPs, the sum of two value functions is actually a value function of the combined reward. However, this does not hold in the robust setting, since the worst- case transition kernels for the two robust value functions are not necessarily the same. Therefore, the geometry of our Lagrangian function is much more complicated. In this paper, we formulate the dual problem of the robust constrained RL problem as a minimax linear-nonconcave optimization problem, and show that the optimal dual variable is bounded. We then construct a robust primal- dual algorithm by alternatively updating the primal and dual variables. We theoretically prove the convergence to stationary points, and characterize its complexity.
In general, convergence stationary points of the Lagrangian function does not necessarily imply that the solution is feasible (Lin et al. [2020] Xu et al. 2020). We design a novel proof to show that the gradient belongs to the normal cone of the feasible set, based which we further prove the robust feasibility of the obtained policy.
We apply and extend our results on an important uncertainty set referred to as 6-contamination model (Huber) 1965). Under this model, the robust value functions are not differentiable and we hence propose smoothed approximation of the robust value function towards better geometry. We further investigate the practical online and model-free setting and design an actor-critic type algorithm. We also establish its convergence, sample complexity, and robust feasibility.
We then discuss works related to robust constrained RL.
Robust constrained RL. (Russel et al. 2020p, the robust constrained RL problem was studied, and a heuristic approach was developed. The basic idea is to estimate the robust value functions, and then to use the vanilla policy gradient method (Sutton et al., 1999) with the vanilla value function replaced by the robust value function. However, this approach did not take into consideration the fact that the worst-case transition kernel is also a function of the policy (see Section 3.1 in (Russel et al., 20200) and therefore the "gradient" therein is not actually the gradient of the robust value function. Thus, its performance and convergence cannot be theoretically guaranteed. The other work (Mankowitz) al., (2020) studied the same robust constrained RL problem under the continuous control setting, and proposed a similar heuristic algorithm. They first proposed a robust Bellman operator and used it to estimate the robust value function, which further combined with some non-robust continuous control algorithm to update the policy. Both approaches in (Russel et al., 2020) and (Mankowitz al. 2020) inherit the heuristic structure of "robust policy evaluation" + "non-robust vanilla policy improvement", which may not necessarily guarantee an improved policy in general. In this paper, we employ a "robust policy evaluation" "robust policy improvement" approach, which guarantees an improvement in the policy, and more importantly, we provide theoretical convergence guarantee, robust feasibility guarantee, and complexity analysis for our algorithms.
Constrained RL. The most commonly used method for constrained RL is the primal-dual method
(Altman 1999 Paternain et al. 2019 2022, Liang et al.) 2018; Stooke et al.) 2020 Tessler et al.
2018: Yu et al. 2019 Zheng & Ratlifi 2020; Efroni et al. 2020 Auer et al. 2008), which augments
the objective with a sum of constraints weighted by their corresponding Lagrange multipliers. and
then alternatively updates the primal and dual variables. It shown that the strong duality holds
2

---

Under review as a conference paper at ICLR 2023
for constrained RL, and hence the primal-dual method has zero duality gap (Paternain al. 2019
Altman 1999). The convergence rate of the primal-dual method was investigated in (Ding et al.
2020; Li al. 2021b: Liu et al. 2021 Ying al.) 2021). Another class of method is the
primal method, which is to enforce the constraints without resorting to the Lagrangian formulation
(Achiam et al. 2017: Liu et al. 2020 Chow et al. 2018 Dalal et al., 2018 Xu et al., [202]] Yang et al. (020). The above studies, when directly applied to robust constrained RL, cannot guarantee
the constraints when there is model deviation. Moreover, the objective and constraints in this paper
take min over the uncertainty set (see eq. (4) and therefore have much more complicated geometry
than the non-robust case.
Robust RL under model uncertainty. Model- robust RL was firstly introduced and studied in
(Iyengar]
2005| Nilim& & El Ghaoui] 2004: [Bagnell et al. 2001; Satia & Lave Jr 1973; Wiesemann
et al. et al. 2014), where the uncertainty set is assumed to known, and the problem can be solved using
2013 Lim & Autef 2019; Xu & Mannor, 2010] Yu & Xu 2015: Lim et al. (013)] [aama
robust dynamic programming. It was then extended to the model-free setting, where the uncertainty
set is unknown, and only samples from its centroid can be collected (Roy et al. [017]] Wang &
Zou 2021: 2022; Zhou et al. [021 Yang al. 2021 Panaganti & Kalathil [202] |202 Ho al. 2018
2021). There are also empirical studies on robust RL, e.g.. (Vinitsky et al. |2020] 20200/Pint Pinto et al. 2017
Abdullah al. 2019: Hou et al. 20200] Rajeswaran al., 2017:
al. 2017 Kos & Song 2in et al. 2017: Pattanaik et al.] 2018: Mandlekar et al. 2017). These works focus on robust
RL without constraints, whereas in this paper we investigate robust RL with constraints, which is more challenging. There is a related line of works on (robust) imitation learning (Ho & Ermon 2016
Fu et al., 2017; Torabi et al.) 2018) Viano et al. 2022). which can be formulated
constrained problem. But their problem settings and approaches are fundamentally different from ours.
2
PRELIMINARIES
Constrained MDP. Consider the CMDP problem in eq. ①. Define the visitation distribution induced by policy and transition kernel P: d: (s, = (1-7) Ei= / = s, A, = a alS., ~ p. n. P). can be shown that the set of the visitation distributions of all policies {d" p.p E ASxA : क E 17] is convex (Paternain et al. [2022] |llman 1999). Based on this convexity, the strong duality of CMDP can be established (Altman 1999, Paternain et al. 2019) under a standard assumption referred as Slater's condition: (Bertsekas 2014 Ding et al. 20 there exists a constant Ç > 0 and a policy
T E II s.t. Vi, V..PP bb 2.
Robust MDP. In this paper, we focus on the (s, -)-rettangula uncertainty set NNilim & El Ghaoui 2004 Iyengar 2005), i.e., T 8 2..a Po, where Pa S Ag. At each time step, the environment transits tollowing transition kernel belonging to the uncertainty set P, E P. The robust value function of a policy π is then defined as the worst-case expected accumulative discounted reward following policy over all MDPs in the uncertainty set (Nilim & El Ghaouil 2004 Iyengar 2005):
(s)
min
EN
Σ
(r((S, A0)S0 s, π
K= P...PP..... +5g
where E, denotes the expectation when the state transits according to It was shown that the robust value function is the fixed point of the robust Bellman operator (Nilim & El Ghaoui 2004
Iyengar 2005 Puterman 2014): T. (s) & Eaea (als)) (r(s, + yapp (V)). where oag (V) 2
millpe? V is the support function of V on Pg.
Note that the minimizer of eq. (4), x², is stationary in time [Iyengar 2005 , which we denote by
{P=,p**..... p=.,.., and refer to pa as the worst-case transition kernel. Then the robust value function VT r.p is actually the value function under policy and transition kernel pr The goal of robust RL is
"==(p= px
to find the optimal robust policy x²" that maximizes the worst-case accumulative discounted reward:
T arg max, V (s),, Vs E S.
3 ROBUST CONSTRAINED RL
Recall the robust constrained RL formulated in eq. (3)
max V (p), s.t. V (p) 1 856
(5)
3

---

Under review as a conference paper at ICLR 2023
where for simplicity omit the subscript J in Vo.g and denote by V (p) and V (p) the robust value function for c and under wg. The goal of eq. (5) is to find a policy that maximizes the robust reward value function among those feasible solutions. Here, any feasible solution to eq. ( can guarantee that under any MDP in the uncertainty set, its accumulative discounted utility is always no less than b;, which guarantees robustness to constraint violation under model uncertainty. Furthermore, the optimal solution to eq. (5) achieves the best "worst-case reward performance" among all feasible solutions. If we use the optimal solution to eq. (5). then under any MDP in the uncertainty set, we have a guaranteed reward no less than the value of eq. (
In this paper, we focus on the parameterized policy class, i.e., Ty E 17.. where θ S Rd is parameter set and Lif is a class of parameterized policies, c.g., direct parameterized policy, softmax or neural network policy. For technical convenience, we adopt a standard assumption on the policy class,
Assumption 1. The policy class 1l is k-Lipschitz and I-smooth, i.e., any s E and a E A and for any 0 E O, there exist universal constants k. I, such that V [a|s) ||
k, and V (a(ss)) s L.
This assumption can be satisfied by many policy classes, c.g., direct paramcterization (Agarwal et al. 202T). soft-max (Mei et al., 2020 Li et al., 2021a Wang & Zou 2020). or neural network with Lipschitz and smooth activation functions (Du et al. 2019 Neyshabur 2017 Miyato et al. 2018).
The problem eq. (5) is equivalent to the following max mii problem:
max min V²** + Σ AvVa (p) - b.). BEA 2.20
(6)
Unlike non-robust CMDP, strong duality for robust constrained RL may not hold. For robust RI., the robust value function can be viewed the value function for policy under its worst-case transition kernel Pr, and therefore can be written as the inner product between the reward (utility) function and the visitation distribution induced by and pr (referred to robust visitation distribution of T). The following lemma shows that the set of robust visitation distributions may not be convex, and therefore, the approach used in (Altman 1999 Paternain al. 2019) to show strong duality cannot be applied here.
Lemma 1. There exists a robust MDP, such that the set of robust visitation distributions is non-convex.
In the following, we focus on the dual problem of eq. 6). For simplicity, we investigate the case with one constraint, and extension to the case with multiple constraints is straightforward:
min max V. (p) + A(V. (p) b)..
X20 PED
We make an assumption of Slater's condition, assuming there exists at least one strictly feasible policy (Bertsekas] 20144; Ding et al. 202I), under which, we further show that the optimal dual variable of eq. (7) is bounded. This assumption is Assumption 2. There exists Ç > and policy x E II. s.t. (p( - bb
Lemma 2. Denote the optimal solution of eq. by (X*, m6-). Then, X E [0, c(1-)))
Lemma suggests that the dual problem eq. 7 is equivalent to a bounded min-max problem:
min
max V. (p) + +XV b). BE0
(8)
xE 0.
The problem in eq. (8) is a bounded mneaa-nonconcave optimization problem. We then propose our robust primal-dual algorithm for robust constrained RL in Algorithm TT The basic idea of Algorithm is to perform gradient descent-ascent w.r.t. À and alternatively. When the policy violates the constraint, the dual variable À increases such that \VTTT dominates V. Then the gradient ascent will update 0 until the policy satisfies the constraint. Therefore, this approach is expected to find a feasible policy (as will be shown in Lemma 5). Here, (xx denotes the projection of x to the set X. and {b. } is non-negative monotone decreasing sequence, which will be specified later. Algorithm I reduces to the vanilla gradient descent-ascent algorithm in (Lin et al.] (020) if b, = 0. However, b, is critical to the convergence of Algorithm T
Xu et al. 2020). The outer problem of eq. (8) is
4

---

Under review as a conference paper at ICLR 2023
Algorithm 1 Robust Primal-Dual algorithm (RPD)
Input: T, at, 3c.
Initialization: Ao 80
fort 0, ...,TTT
T - do
Ac+1 + 10.010 (A: 3. (Ve (p) -b) -/,11)))
0z+1 + Ile (r + 1. (VoV, (p) + Xet1 VoVe (0))
end for Output: OT
actually linear, and after introducing by the update of A can be viewed as gradient descent of strongly-convex function A(V. b) + b. X², which converges more stable and faster.
2
Denote that Lagrangian function by (= V + X(V2 (p) - b). and further denote the gradient mapping of Algorithm by
Be Ax [o
de 3. (VAV A0)
Ge A
0tt 02 Ie
0e (VOVL Xx)
The gradient mapping is standard measure of convergence for projected optimization approaches (Beck) 2017). Intuitively, it reduces to the gradient (V,VL, VoV when 1 = co and e Rd and measures the updates of and À time step t. If G| - 0, the updates of both variables are small, and hence the algorithm converges to stationary solution.
To show the convergence of Algorithm D
we make the following Lipschitz smoothness assumption.
Assumption 3. The gradients of the Lagrangian function are Lipschitz:
V A)le,
VAV A) - Ln 00 0211,
(10)
|V (8, VAV A) A, S L A1 Ax11
(11)
V A)lo, VOr"(0, A) - Lei [nl A211,
(12)
(8, - VOV" A> - Le2 A1 - X2l-
(13)
As will be shown in Section Assumption 3 can be satisfied with a smoothed approximation of the robust value function.
In the following theorem, we show that our robust primal-dual algorithm converges to a stationary point of the min-max problem eq. (16), with complexity of O(c
Theorem 1. Under Assumption 3 if set step sizes oe, Be, and b, in Section D Jnd T O 4),
then minişeeT ||G,]| < 2e.
The next proposition characterizes the feasibility of the obtained policy. Proposition 1. Denote by W A arg argiingeerr |[Gell- If Aw Bw (BAV Aw)) E (0, then TW satisfies the constraint with a 2e-violation.
In general, convergence to stationary points the Lagrangian function does not necessarily imply that the solution is feasible. Proposition [showw that Algorithm [awways return policy that is robust feasible, i.c., satisfying the constraints in eq. (5). Intuitively, if we set 1" larger so that the optimal solution X [0, A²), then Algorithm [ is expected converge an interior point of [0, A*) and therefore, Tw feasible. On the other hand, 11" can't it be set too large. Note that the complexity in Theorem depends on 1 (see eq. (59) in the appendix), and larger 1 means higher complexity.
4 S-CONTAMINATION UNCERTAINTY SET
In this section, we investigate a concrete example of robust constrained RL with 8 6-contamination uncertainty set. The method developed here can be similarly extended other type of uncertainty
5

---

Under review as a conference paper at ICLR 2023
sets like KL-divergence total variation. The o-contamination uncertainty set models the scenario where the state transition of the MDP could be arbitrarily perturbed with a small probability This model is widely used to model distributional uncertainty in the literature of robust learning and optimization, e.g.. (Huber 1965 Du et al. 2018 Huber & Ronchetti 2009) Nishimura & Ozaki [0044] 2006; Prasad et al. 2020a b Wang & Zou 2021 2022). Specifically, let =1r s 8, a A] be
the centroid transition kernel, then the d-contammation uncertainty set centered at P is defined as P @sE8,aeA Pg where Pa - {{1 - 5)p² + óglg E As}, E S, PREEA A.
Under the 5-contamination setting, the robust Bellman operator can be explicitly computed: (s)(s) Easa (aas)) (r(s,a) a) + (5 min./ V(s') (1 - 5) Eves P2. P( In this case, the robust value function is non-differentiable due to the min term, and hence Assumption dooes not hold. One possible approach is to use sub-gradient, which, however, less stable, and its convergence is difficult to characterize. In the following, we design a differentiable and smooth approximation of the robust value function. Specifically, consider a smoothed robust Bellman operator T using the LSE function:
TVV() EANa(Hl)) r(s, A) + 7(1 - 5) Σ V(')+ 70L) S'E8
(14)
where LSB((a, V) = 1ox(>;;_ (o) for V E Rdd and some a < 0. The approximation error [LSE(o, V) min V| +
-Cc and hence the fixed point of T denoted by Vi. is an approximation of the robust value function V (Wang & Zou| (022). We refer to V as the smoothed robust value function and define the smoothed robust action-vatt value function as Q (s, a) & r(s, a) + 5) EE Pa (s')
(s') 78LSE((,, V. It can be shown that for any π,, as o + oc.
||V""
V -> and V Vleel -
The gradient of Vi can be computed explicitly (Wang & Zou 2022 VV B(s,0)
76 >8>iees e 2 (v) B(a,0) where B(s,0) T Eves (s'( EAEA Vno(als') ("" (s',a), and
(.(() is the visitation distribution no under P starting from s. Denote the smoothed Lagrangian function by (0, A (p)(p) + X(V - b). The following lemma shows that VV is Lipschitz.
Lemma 3. VVL is Lipschitz 0 and X. And hence Assumption 3 holds for VLL.
A natural idea is to use the smoothed robust value functions to replace the ones in eq.
min max (p) + X(V b). X20 relle
(15)
As will be shown below in Lemma 6 this approximation can be arbitrarily close to the original problem in eq. 7 as a + -c. We first show that under Assumption condition holds for the smoothed problem in eq. [15).
2 the following Slater's
Lemma 4. Let be sufficiently small such that I V.lll < foror any then there exists Ç' > 0 and a policy T' e Ile s.t. (p,( b
The following lemma shows that the optimal dual variable for eq. 15)) is also bounded.
Lemma 5. Denote the optimal solution of eq. (15 by (A", Then X
[,,
2C
where C₂ is
the upper bound of smoothed robust value functions V
Denote by A = max 22C. (G.:राー)) following bounded ones: minxe(o.A11] max Vi(() (p) X(V (p) b), and
) then problems eq. ( and eq. 15) are equivalent to the
min max (p) + A(V b). X selle
(16)
The following lemma shows that the two problems within a gap of O(e).
Lemma 6. Choose a small enough such that -| - || < c and V| - V S Then
min max (p) + X(V b) min max (.()) + X(V (p) bb) (1 + 1²) (e(o.1")=EIl
xell

---

Under review as a conference paper at ICLR 2023
In the following, hence focus the smoothed dual problem in eq. (6)). which is an accurate approximation of the original problem eq. (8). Denote the gradient mapping of the smoothed Lagrangian function V by
Be - at (0. ITe 02 + (VoV Ad))
Ae 1 (V (O. A0)
G7 A
Bi
(17)
Applying our RPD algorithm in eq. (6), we have the following convergence guarantee.
Corollary 1. If we step sizes at, Br, and by in Section J and T O(E then
ming | < 2e.
This corollary implies that our robust primal-dual algorithm converges to a stationary point of the min-max problem eq. (16) under the 6-contamination model, with a complexity of O 4).
Algorithm 2 Smoothed Robust TD (Wang & Zou 2022)
Input: moe.. 0,
Initialization: Qo. so
for 1 = 0, 1.., Tinner- - do
Choose at T-|[s; and observe ct 81+1
Vi(s) + EnEA Q(als)Qi(s, a) for all s E S
Q5+1 ar) + Qr(st, arlce + 7(1
8) (2((++)) + +70 LSB(o,, V,) - (r(s),
end for
Output: Qui...c A QTme
Note that Algorithm I Jasuumes knowledge the smoothed robust value functions which may not be available in practice. Different from the non-robust value function which can be estimated using Monte Carlo, robust value functions are the value function corresponding to the worst-case transition kernel from which samples directly taken. To solve this issue, we adopt the smoothed robust TD algorithm (Algorithm 2 from (Wang & Zou 2022) to estimate the smoothed robust value functions.
It shown that the smoothed robust TD algorithm converges to the smoothed robust value function with sample complexity (c--2) WWang& & Zou 2022) under the tabular case. We then construct our online and model-free RPD algorithm as in Algorithm 3 We note that Algorithm 3 is for the tabular setting with finite S and A. It can be easily extended to the case with large/continuous S and using function approximation.
Algorithm 3 Online Robust Primal-Dual algorithm
Input: T, a. Cess Br, Ott byrrc Initialization: Ag Po
for = 1,.,..,, T
1 do
(1+1)1 Est
Set Timerr = 0
and run Algorithm 2 for r and c, output Quiniryy Qumaci
V (s) - Ea To, (als) @ (s, a), Vo (s) En
ne, (als) Quunn(( a)
T (p) + E, Vos) oo (s). Te (p) + E, p(s) Volo (s)
To
Ac+1 + [I \x=-
Vor0 (p) - b)
b
m
1 0.+1 + Ie Oc + az
(VoVor (p) + det1 VoVa (p))
end for Output: 0T
Algorithm 3 can be viewed as biased stochastic gradient descent-ascent algorithm. It is a sample- based algorithm without assuming any knowledge of robust value functions, and can be performed in an online fashion. We further extend the convergence results in Theorem to the model-free setting, and characterize the following finite-time error bound of Algorithm 3 Similarly, Algorithm be shown to achieve 2e-feasible policy almost surely.
7

---

Under review as a conference paper at ICLR 2023
Under the online model-free setting, the estimation of the robust value functions is biased. Therefore, the analysis is more challenging than the existing literature, where it is usually assumed that the gradients exact. We develop new method to bound the bias accumulated in every iteration of the algorithm, and establish the final convergence results.
Theorem 2. Consider the same conditions as in Theorem Let Eest = O(E²) and T = O(E +), then minisesr | $ (1+ /2)..
NUMERICAL RESULTS
In this section, we numerically demonstrate the robustness of our algorithm in terms of both maximiz- ing robust reward value function and satisfying constraints under model uncertainty. We compare our RPD algorithm with the heuristic algorithms in (Russel et al. [2021] Mankowitz et al. 2020) and the vanilla non-ro non-robust primal-dual method. Based on the idea of 'robust policy evaluation + "non-robust policy improvement" in (Russel et al.) 2021; Mankowitz et al. 2020), we combine the robust TD algorithmm 2 with non-robust vanilla policy gradient method (Sutton et al. 1999). which we refer to as the heuristic primal-dual algorithm. Several environments, including Garnet (Archibald et al. 1995), ) 8 x 8 Frozen-Lake and Taxi environments from OpenAl (Brockman et af.) 2016), are investigated.
We first run the algorithms and store the obtained policies т, each time step. Then non-smoothed robust TD (Alg 3 in (Wang & Zou (022)) with a sample size 200 for 30 times to estimate the non-smoothed objective (=(p) and the non-smoothed constraint Ve(p). We then plot them v.s. the number of iterations t. The upper and lower envelopes of the curves correspond to the 95 and percentiles of the 30 curves, respectively. We repeat the experiment for two different values of 8 = 0.2, 0.3.
the
Garnet problem. Garnet problem can be specified by I(S,, An), where the state space 8 has S, states ($1...., ss,) and action space has A, actions (Q1...., aA..). The agent can take any actions in any state, and receives randomly generated reward/utility signal generated from the uniform distribution on []. The transition kernels are also randomly generated. The comparison results are shown in Fig
8 x 8 Frozen-Lake problem. We then compare the three algorithms under the 8 x 8 Frozen-late The Frozen-Lake problem involves a frozen lake of size contains several "holes". The agent aims cross the lake from the start point to the end point without falling into any holes. The agent receives r = -10 and c = 0 when falling in a hole, receives r = 20 and = 1 when arrive the end point; At other times, the agent receives = 0 and randomly generated utility e according to the uniform distribution on [0.1].
problem setting in Fig 2
which
Taxi problem. We then compare the three algorithms under the Taxi problem environment. The taxi problem simulates a taxi driver in a 5 x 5 map. There are four designated locations in the grid world and passenger occurs at a random location of the designated four locations the start of each episode. The goal of the driver is to first pick up the passenger and then to drop off at another specific location. The driver receives r 20 for each successful drop-off, and always receives r other times. We randomly generate the utility according to the uniform distribution on [0.1] for each state-action pair. The results are shown in Fig
at
From the experiment results above, it can be seen that: (1) Both our RPD algorithm and the heuristic primal-dual approach find feasible policies satisfying the constraint robustly, i.e., the non-smoothed robust utility functions lie above the threshold V 2 b. However, the non-robust primal-dual method fails to find a feasible solution that satisfy the constraint under the worst-case scenario. (2) Compared to the heuristic PD method, our RPD method can obtain more reward and can find a more robust policy while satisfying the robust constraint. Note that the non-robust PD method obtain more reward, but this is because the policy it finds violates the robust constraint. Our experiments demonstrate that among the three algorithms, our RPD algorithm is the best one which optimizes the worst-case reward performance while satisfying the robust constraints the utility.
8

---

Under review as a conference paper at ICLR 2023
obea ontina cka du 2e00004155
mumber Iterationn (a) Ve when 0 = 0.2.
number ittratioon
Rorations
(b) V when = 0.2.
(c) Ve when 0.3.
(d) V when 0.3.
Figure I: Comparison Garnet Problem 9(20, 10).
EIOuect piraal-uu haurtiic prrmidddd
TOURRO out Dessnddee
Brrahobo2
norioot prined
merattonss
Iitrratonn
Rararions
(a) Ve when 0
0.2.
(b) V, when = 0.2.
(c) V. when 0.3.
(d) V when = 0.3.
Figure 2: Comparison x Frozen-Lan Lake Problem.
V..01
Liinations
number Jilnationn
Tember Aeraations
Reraison
(a) V. when 0 0.2.
(b) V, when ó = =.2.
(c) V. when 0 0.3.
(d) V when = 0.3.
Figure 3: Comparison on Taxi Problem.
CONCLUSION
In this paper, we formulate the problem of robust constrained reinforcement learning under model uncertainty, where the goal is to guarantee that constraints are satisfied for all MDPs in the uncertainty set, and to maximize the worst-case reward performance over the uncertainty set. We propose a robust primal-dual algorithm, and theoretically characterize its convergence, complexity and robust feasibility. Our algorithm guarantees convergence to a feasible solution, and outperforms the other two heuristic algorithms. We further investigate concrete example with 5-contamination uncertainty set, and construct online and model-free robust primal-dual algorithm. Our methodology can also be readily extended to problems with other uncertainty sets like KL-divergence, total variation and Wasserstein distance. The major challenge lies in deriving the robust policy gradient, and further designing model-free algorithm estimate the robust value function.

---

Under review as a conference paper at ICLR 2023
REFERENCES
Mohammed Amin Abdullah, Hang Ren, Haitham Bou Ammar, Vladimir Milenkovic, Rui Luo, Mingtian Zhang, and Jun Wang. Wasserstein robust reinforcement learning. arXiv preprint arXiv: 131007...//... 2019.
Joshua Achiam, David Held, Aviv Tamar, and Pieter Abbeel. Constrained policy optimization. In Proc. International Conference on Machine Learning (ICML), pp. 22-31. PMLR, 2017.
Alekh Agarwal, Sham M Kakade, Jason D Lee, and Gaurav Mahajan. On the theory of policy gradient methods: Optimality, approximation, and distribution shift. Journal of Machine Learning Research, 22(98):1-76, 2021.
Eitan Altman. Constrained Markov decision processes: stochastic modeling. Routledge, 1999.
TW Archibald, KIM McKinnon, and LC Thomas. On the generation of Markov decision processes. Journal of the Operational Research Society, 46(3):354-361, 1995.
Peter Auer, Thomas Jaksch, and Ronald Ortner. Near-optimal regret bounds for reinforcement learning. Proc. Advances in Neural Information Processing Systems (NIPS), volume 21, 2008.
J Andrew Bagnell, Andrew Y Ng, and Jeff G Schneider. Solving uncertain Markov decision processes. 09 2001.
Amir Beck. First-order methods in optimization. SIAM, 2017.
Dimitri P Bertsekas. Constrained optimization and Lagrange multiplier methods. Academic press, 2014.
Greg Brockman, Vicki Cheung. Ludwig Pettersson, Jonas Schneider, John Schulman, Jie Tang, and Wojeiech Zaremba. OpenAl Gym. arXiv preprini arXiv: 1606.00066000 5400, 2016.
Yinlam Chow, Ofir Nachum, Edgar Quenez-Guzman and Mohammad Ghavamzadeh. A lyapunov- based approach to safe reinforcement learning. In Proc. Advances in Neural Information Processing Systems (NeurIPS), volume 31, 2018.
Gal Dalal, Krishnamurthy Dvijotham, Matej Vecerik, Todd Hester, Cosmin Paduraru, and Yuval Tassa. Safe exploration in continuous action spaces. arXiv preprint arXiv:1801.0875 801.88777 2018.
Dongsheng Ding, Kaiqing Zhang, Tamer Basar, and Mihailo Jovanovic. Natural policy gradient primal-dual method for constrained Markov decision processes. In Proc. Advances in Neural Information Processing Systems (NeurIPS). volume 33, pp. 8378-8390, 2020.
Dongsheng Ding, Xiaohan Wei, Zhuoran Yang, Zhaoran Wang, and Mihailo Jovanovic. Provably efficient safe exploration via primal-dual policy optimization. In Proc. International Conference on Artifical Intelligence and Statistics (AISTATS), pp. 3304-3312. PMLR, 2021.
Simon Du, Jason Lee, Haochuan Li, Liwei Wang, and Xiyu Zhai. Gradient descent finds global minima of deep neural networks. In Proc. International Conference on Machine Learning (ICML), pp. 1675-1685. PMLR, 2019.
Simon Du, Yining Wang, Sivaraman Balakrishnan, Pradeep Ravikumar, and Aarti Singh. Robust nonparametric regression under Huber's e-contamination model. arXiv preprint 1rXiv:1805.10406. 2018.
Yonathan Efroni, Shie Mannor, and Matteo Pirotta. Exploration-exploitatioo in constrained MDPs. arXiv preprint arXiv:2003.02188) 2020.
Justin Fu, Katie Luo, and Sergey Levine. Learning robust rewards with adversarial inverse reinforce- ment learning. arXiv preprint arXiv:/710.11 1244, 2017.
Saeed Ghadimi and Guanghui Lan. Accelerated gradient methods for nonconvex nonlinear and stochastic programming. Mathematical Progatiiaaarrrrrrraa Programming, 156(1-2):59-99 2016.
10

---

Under review as a conference paper at ICLR 2023
Chin Pang Ho. Marek Petrik, and Wolfram Wiesemann. Fast Bellman updates for robust MDPs. In Proc. International Conference on Machine Learning (ICML), pp. 1979-1988. PMLR, 2018.
Chin Pang Ho, Marek Petrik, and Wolfram Wiesemann, Partial policy iteration for 11-robust Markov
decision processes. Journal of Machine Learning Research, 22(275): 2021.
Jonathan Ho and Stefano Ermon. Generative adversarial imitation learning. Advances in neural information processing systems, 29, 2016.
Linfang Hou, Liang Pang, Xin Hong, Yanyan Lan, Zhiming Ma, and Dawei Yin. Robust reinforcement learning with Wasserstein constraint. arXiv preprint (1t::200000009455, 2020.
Sandy Huang, Nicolas Paperno,, Ian Goodfellow, Yan Duan, and Pieter Abbeel. Adversarial attacks on neural network policies. In Proc. International Conference on Learning Representations (ICLR), 2017.
J. Huber. A robust version of the probability ratio test. Ann. Math. Statist., 36:1753-1758, 1965.
PJ Huber and EM Ronchetti. Robust Statistics. John Wiley Sons, Inc, 2009.
Garud N Iyengar. Robust dynamic programming. Mathematics of Operations Research, 30(2): 257-280, 2005.
Jernej Kos and Dawn Song. Delving into adversarial attacks on deep policies. In Proc. International Conference on Learning Representations (ICLR), 2017.
Gen Li, Yuting Wei, Yuejie Chi, Yuantao Gu, and Yuxin Chen. Softmax policy gradient methods can take exponential time to converge. arXiv preprint arXiv:2 / 2021a.
Tianjiao Li, Ziwei Guan, Shaofeng Zou, Tengyu Xu, Yingbin Liang, and Guanghui Lan. Faster algorithm and sharper analysis for constrained Markov decision process. arXiv preprint 10.351,1 2021b.
Qingkai Liang, Fanyu Que, and Eytan Modiano. Accelerated primal-dual policy optimization for safe reinforcement learning. arXiv preprint
2018.
Shiau Hong Lim and Arnaud Autef. Kernel-based reinforcement learning in robust Markov decision processes. In Proc. International Conference Machine Learning (ICML), pp. 3973-39811
PMLR, 2019.
Shiau Hong Lim, Huan Xu, and Shie Mannor. Reinforcement learning in robust Markov decision processes. In Proc. Advances in Neural Information Processing Systems (NIPS), pp. 701-709, 2013.
Tianyi Lin, Chi Jin, and Michael Jordan. On gradient descent ascent for nonconvex-concave minimax problems. In Proc. International Conference on Machine Learning (ICML), pp. 6083-6093. PMLR. 2020.
Yen-Chen Lin, Zhang- Wei Hong, Yuan- Liao, Meng-Li Shih, Ming- Yu Liu, and Min Sun. Tactics of adversarial attack on deep reinforcement learning agents. In Proc. International Joint Conferences on Artificial Intelligence (IJCAI), pp. 3756-3762, 2017.
Tao Liu, Ruida Zhou, Dileep Kalathil, PR Kumar, and Chao Tian. Fast global convergence of policy optimization for constrained MDPs. arXiv preprint 4rX0v:2111.00552, 2021.
Yongshuai Liu, Jiaxin Ding, and Xin Liu. Ipo: Interior-point policy optimization under constraints.
In Proc. Conference on Artificial Intelligence (AAAI), volume 34, pp. 4940-4947, 2020.
Ajay Mandlekar, Yuke Zhu, Animesh Garg, Li Fei-Fei, and Silvio Savarese. Adversarially robust policy learning: Active construction of physically-plausine perturbations. In 2017 IEEE/RSJ International Conference Intelligent Robots and Systems (IROS), pp. 3932-3939, IEEE, 2017.
Daniel J Mankowitz, Dan A Calian, Rae Jeong, Cosmin Paduraru, Nicolas Heess, Sumanth Dathathri, Martin Riedmiller, and Timothy Mann. Robust constrained reinforcement learning for continuous control with model misspecification. arXiv preprint arXiv:2010. 10644, 2020.
11

---

Under review as a conference paper at ICLR 2023
Jincheng Mei, Chenjun Xiao, Csaba Szepesvari, and Dale Schuurmans. On the global convergence rates of softmax policy gradient methods. In Proc. International Conference on Machine Learning (ICML), pp. 6820-6829, PMLR, 2020.
Takeru Miyato, Toshiki Kataoka, Masanori Koyama, and Yuichi Yoshida. Spectral normalization for generative adversarial networks. In Proc. International Conference on Learning Representations (ICLR), 2018.
Behnam Neyshabur. Implicit regularization in deep learning. arXiv preprint arXiv:1709.0195.. 2017.
Arnab Nilim and Laurent El Ghaoui. Robustness in Markov decision problems with uncertain transition matrices. In Proc. Advances in Neural Information Processing Systems (NIPS), pp. 839-846, 2004.
Kiyohiko G Nishimura and Hiroyuki Ozaki. Search and knightian uncertainty. Journal of Economic Theory, 1 119(2)299-333, 2004.
Kiyohiko G. Nishimura and Hiroyuki Ozaki. An axiomatic approach to e-contamination. Economic Theory, 27(2):333-340, 2006.
Kishan Panaganti and Dileep Kalathil. Sample complexity of robust reinforcement learning with generative model. arXiv preprint arXiv:2112.01506, 2021.
Santiago Paternain, Luiz Chamon, Miguel Calvo-Fullana, and Alejandro Ribeiro. Constrained reinforcement learning has zero duality gap. In Proc. Advances in Neural Information Processing Systems (NeurIPS), volume 32, 2019.
Santiago Paternain, Miguel Calvo-Fullana, Luiz FO Chamon, and Alejandro Ribeiro. Safe policies for reinforcement learning via primal-dual methods. IEEE Transactions on Automatic Control, 2022.
Anay Pattanaik. Zhenyi Tang, Shuijing Liu, Gautham Bommannan, and Girish Chowdhary. Robust deep reinforcement learning with adversarial attacks. In Proc. International Conference on Autonomous Agents and MulfiAgent Systems, pp. 2040,2042,10 2018.
Lerrel Pinto, James Davidson, Rahul Sukthankar, and Abhinav Gupta. Robust adversarial reinforce- ment learning. In Proc. International Conference on Machine Learning (ICML), pp. 2817-2826. PMLR, 2017.
Adarsh Prasad, Vishwak Srinivasan, Sivaraman Balakrishnan, and Pradeep Ravikumar. On learn- ing ising models under Huber's contamination model. Proc. Advances in Neural Information Processing Systems (NeurIPS), 33, 2020a.
Adarsh Prasad, Arun Sai Suggala, Sivaraman Balakrishnan, and Pradeep Ravikumar. Robust estima- tion via robust gradient estimation. Journal of the Royal Statistical Society: Series B (Statistical Methodology)) 82(():601-62) 2020b.
Martin L Puterman. Markov decision processes: discrete stochastic dynamic programming. John Wiley & Sons, 2014.
Aravind Rajeswaran, Sarvjeet Ghotra, Balaraman Ravindran, and Sergey Levine. Epopt: Learning robust neural network policies using model ensembles. In Proc. International Conference on Learning Representations (ICLR), 2017.
Aurko Roy, Huan Xu, and Sebastian Pokutta. Reinforcement learning under model mismatch. In Proc. Advances in Neural Information Processing Systems (NIPS), pp. 3046-3055, 2017.
Reazul Hasan Russel, Mouhacine Benosman, and Jeroen Van Baar. Robust constrained-MDPP Soft- constrained robust policy optimization under model uncertainty. arXiv preprint arXiv:2010.04870, 2020.
Reazul Hasan Russel, Mouhacine Benosman, Jeroen Van Baar, and Radu Corcodel. Lyapunov robust Conttrined-MDDP Soft-constrrimee robustly stable policy optimization under model uncertainty. arXiv preprint 2rXiv:210..027000 2021.
12

---

Under review as a conference paper at ICLR 2023
Jay K Satia and Roy E Lave Jr. Markovian decision processes with uncertain transition probabilities. Operations Research, 21(3):728-74 -408 1973.
Adam Stooke, Joshua Achiam, and Pieter Abbeel. Responsive safety in reinforcement learning by pid lagrangian methods. In Proc. Interaational Conference on Machine Learning (ICML), pP- 9133-9143. PMLR, 2020.
Richard S Sutton, David A McAllester, Satinder P Singh, Yishay Mansour, et al. Policy gradient methods for reinforcement learning with function approximation. In Proc. Advances in Neural Information Processing Systems (NIPS), volume 99, pp. 1057-1063. Citeseer, 1999.
Aviv Tamar, Shie Mannor, and Huan Xu. Scaling up robust MDPs using function approximation. In
Proc. International Conference on Machine Learning (ICML), pp. 181 181-189. PMLR, 2014.
Chen Tessler, Daniel J Mankowitz, and Shie Mannor. Reward constrained policy optimization. arXiv preprint 180. 11074, 2018.
Faraz Torabi. Garrett Warnell, and Peter Stone. Generative adversarial imitation from observation.
arXiv preprint arXiv: /807.06/8.8 2018.
Luca Viano, Yu-Ting Huang, Parameswaran Kamalaruban, Craig Innes, Subramanian Ramamoorthy, and Adrian Weller. Robust learning from observation with model misspecification. In Proceedings of the s1 International Conference on Autonomous Agents and Multiagent Systems, pp. 1337- 1345, 2022.
Eugene Vinitsky, Yuqing Du, Kanaad Parvate, Kathy Jang, Pieter Abbeel, and Alexandre Bayen. Robust reinforcement learning using adversarial populations. arXiv preprint trXiv:2008.0182 2020.
Yue Wang and Shaofeng Zou. Finite-sample analysis of Greedy-GO with linear function approxi- mation under Markovian noise. In Proc. International Conference on Uncertainty Artificial Intelligence (UAI). pp. 11-20. PMLR, 2020.
Yue Wang and Shaofeng Zou. Online robust reinforcement learning with model uncertainty. In Proc. Advances in Neural Information Processing Systems (NeurIPS), 2021.
Yue Wang and Shaofeng Zou. Policy gradient method for robust reinforcement learning. In Proc. International Conference Machine Learning (ICML), 2022.
Wolfram Wiesemann, Daniel Kuhn, and Berç Rustem. Robust Markov decision processes. Mathe- matics of Operations Research, 38(1):153-183, 2013.
Huan Xu and Shie Mannor. Distributionally robust Markov decision processes. In Proc. Advances in Neural Information Processing Systems (NIPS), pp. 2505-2513, 2010.
Tengyu Xu, Yingbin Liang, and Guanghui Lan. Crpo: A new approach for safe reinforcement learning with convergence guarantee. Proc. International Conference on Machine Learning (ICML), pp. 1 11480-11491 PMLR, 2021.
Zi Xu, Huiling Zhang, Yang Xu, and Guanghui Lan. A unified single-loop alternating gradient projection algorithm for nonconvex-concave and convex-nonconcave minimax problems. arXiv preprint arXiv:2006.00000 2020.
Tsung- Yen Yang, Justinian Rosca, Karthik Narasimhan, and Peter J Ramadge. Projection-based constrained policy optimization. arXiv preprint arXiv:2010.03152, 2020.
Wenhao Yang, Liangyu Zhang, and Zhihua Zhang. Towards theoretical understandings of robust Markov decision processes: Sample complexity and asymptotics. arXiv preprint wrXiv:2105.03863, 2021.
Donghao Ying, Yuhao Ding, and Javad Lavaci. A dual approach to constrained Markov decision processes with entropy regularization. arXiv preprint arXiv:2/1000890 08932, 2021.
13

---

Under review as a conference paper at ICLR 2023
Ming Yu, Zhuoran Yang, Mladen Kolar, and Zhaoran Wang. Convergent policy optimization for safe reinforcement learning. Proc. Advances in Neural Information Processing Systems (NeurIPS), volume 32, 2019.
Pengqian Yu and Huan Xu. Distributionally robust counterpart in Markov decision processes. IEEE Transactions on Aulomatic Control, 61()):533-2543, 2015.
Liyuan Zheng and Lillian Ratliff. Constrained upper confidence reinforcement learning. In Learning for Dynamics and Control, pp. 020-629. PMLR, 2020.
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 Proc. International Conference on Artifical Intelligence and Statistics (AISTATS), pp. 3331-3339. PMLR, 2021.
14


Reviews:
[{"review_id": "tGoRXqn1Tt", "reviewer": "Reviewer_gZnw", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The authors present a method for robust constrained RL, a setting where the RL agent is tasked with maximizing the worst-case expected reward subject to a constraint that worst-case costs incurred from the environment are constrained. Here the worst-cases are evaluated as the worst-case among models of the environment in some uncertainty set. The algorithm itself optimizes the lagrangian of the constrained problem by performing gradient updates. To evaluate the expected worst-case reward and constraint, the authors leverage previous work that computes smoothed robust value estimates using log sum exp as an approximation for the worst-case setting. The authors demonstrate that this algorithm should achieve a solution with bounded infeasibility with guarantees on convergence and runtime due to assumptions on the problem. The authors evaluate their algorithm against a constraint-agnosting RL agent as well as a heuristic algorithm for robust constrained reinforcement learning from previous work.\n", "summary_of_the_review": "Overall, I think that the paper approaches an important problem for the RL community. I see the main strength of the paper as presenting a theoretically-motivated approach to solving their problem and evaluating the approach against a reasonable baseline on several simulated domains. I consider the main room for improvement for this work to be in the experimental evaluation and expanding upon whether or not the approach meets the proposed robustness requirements. ", "strength_and_weaknesses": "The main strengths of the paper are in the theoretical evaluation of their algorithm in their specific setting and in evaluating their algorithm against a reasonable baseline showing improved performance. Additionally, their algorithm is reasonable and straightforward and they evaluate the complexity of their convergence.\n\nThe main weaknesses of the paper are in the experimental evaluation. It is unclear whether the results demonstrate that the learned model satisfies the constraint robustly as is desired, although it clearly satisfies the constraints “better” than previous heuristic approach and a standard approach. Additionally, it would be helpful to explain exactly what metrics are used since it is slightly unclear whether the evaluation is a worst-case evaluation of the incurred costs and rewards, or just the incurred costs and rewards. Additionally, it is unclear whether the worst-case evaluations come from the approximation or are evaluated by finding the worst-case scenario from the uncertainty set. \n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "PjvSjfJ4l2u", "reviewer": "Reviewer_yY2u", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper studies the constrained robust MDP problem where the goal is to learn a policy that maximizes the expected rewards, subject to the safety constraint that the expected cost exceeds certain thresholds. Moreover, the transition model is chosen from an ambiguity set. As a result, the goal is to maximize the reward under the most adversarial model, while ensuring that the safety constraint is met for all models in the ambiguity set. \n\nThe authors propose an algorithm based on the Lagrange multiplier, which transforms the policy optimization problem into a min-max optimization problem. For such a problem, a gradient descent-ascent algorithm is proposed. The authors also establish sample complexity results about how many samples are needed to ensure convergence to an approximate stationary point that also approximately satisfies the safety constraints. \n\n", "summary_of_the_review": "The main issue of this paper seems to be a lack of novelty. The algorithm and theoretical results seems to be based on direct combination of results in CMDP and robust MDP literature. ", "strength_and_weaknesses": "Strength: \n\nThe model of robust CMDP seems a novel setting that has not been extensively studied in the literature. The algorithm based on Lagrange multiplier is reasonable as it is an adaptation of the existing algorithm for CMDP. (Although I have certain reservations about extending it to the robust setting. See below.) \n\nWeakness: \n\n1. Novelty: The main issue of this work seems a lack of novelty. Both the standard CMDP and robust MDP have been extensively studied in the literature, and this work seems a direct combination of these strands of research. For example, the algorithm is based on the Lagrange multiplier and policy gradient method for CMDP. Seen from the presentation of the algorithm, the authors even omit the dependency on transition $P$, which makes the algorithm extremely similar to a method for CMDP. In terms of analysis, it seems unclear what additional challenge is caused by ensuring robustness with respect to the ambiguity set. \n\n2. Algorithm. It would be great to carefully derive the algorithm. In particular, I think the transformation based on Lagrange multiplier might not be as simple as shown in the paper. In particular, here the functions  $V_r$ and $V_c$ are actually \n$$\nV_{r} = \\inf_{P \\in \\mathcal{P} } V_{P, r} , \\qquad V_{c} = \\inf_{P \\in \\mathcal{P} } V_{P, c} .\n$$\nWhen you write down the Lagrangian, do you consider \n$$\n\\inf_{P \\in \\mathcal{P} } V_{P, r} + \\lambda \\cdot \\inf_{P \\in \\mathcal{P} } V_{P, c}  \n$$\nor \n$$\n\\inf_{P \\in \\mathcal{P} } \\{  V_{P, r} + \\lambda \\cdot  V_{P, c} \\}\n$$\n\n3. Gradient descent ascent. Following the above comment, since the objective involves $\\inf_{P \\in \\mathcal{P} } $, when taking the gradient with respect to the policy parameter and $\\lambda$, it seems unclear how the gradient is computed. How do you differentiate through $\\inf_P$ and how do you estimate the gradient?\n\n4. Convergence to a stationary point. This paper only shows convergence to a stationary point. However, various existing works on CMDP have established convergence to the globally optimal policy and even ensured zero constraint violation. It would be nice to see if the theoretical guarantees in this work can be improved. Convergence to a stationary point seems not to lead to any optimality certificate of the learned policy. \n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "DsaE2x_p_VB", "reviewer": "Reviewer_TPvy", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper studies the problem of robust constrained reinforcement learning (RL) where the underlying model has uncertainty. The goal is to ensure that the constraints are satisfied for the worst-case MDP in a set of MDPs, while at the same time to maximize the reward over the uncertainty set. A robust primal-dual algorithm is proposed, with theoretical performance analysis under certain assumptions. An example of $\\delta$-contamination uncertainty set is specifically investigated. Three numerical examples are shown to support the validity of the proposed solution.", "summary_of_the_review": "Overall, this work made progress in the robust constrained RL problem, which is important and timely. The proposed algorithm has its value and the analysis is sound, but there are quite a few issues that are not resolved. This leads to my recommendation of marginal rejection.", "strength_and_weaknesses": "Strength:\n+ This work studies an important and timely problem of robust constrained RL. \n+ The proposed robust primal-dual algorithm is valuable.\n+ The theoretical analysis is technically sound (under the given assumptions and the chosen approach).\n\nWeakness:\n- The problem formulation has some inconsistency in terms of the (uncertain) MDP. The formulation in eq. (3) will mostly result in different worst-case MDPs for the \"worst-case reward\" and  the \"worst-case cost\". However, the motivating example is that the training MDP is different than the test MDP. In fact, majority, if not all, of practical applications should have the same MDP where both reward and cost are evaluated, as they are simultaneously collected. This should not be over different MDPs. The authors have specifically discussed the worst-case transition kernels being possibly different for the two robust value functions, but I am having a difficult time understanding why this is useful to begin with.\n- The authors essentially got around the non-differentiable robust Bellman operator issue by taking a differentiable approximation. I understand that such approximation is made in order to make progress. However, despite that this approximation can be close to the original function, any approximation in a **robust** optimization formulation always raises the question of how these two ``uncertainties'' reconcile. Would solving the approximated problem lead to actual constraint violation? How does this affect the rigor of the original problem? Additionally, one can imagine that there could be different ways to do this approximation --  why did the authors choose the current approximation, and how is this superior than others?\n- The above issue also happens when the authors propose to *estimate* the smoothed robust functions. Again, how does the estimation error affect the constraint violation and the rigor of the optimization problem?\n- Assumption 2 and Lemma 4 have two lower bound values $\\zeta$ and $\\zeta'$. Are these two values needed for Alg. 1 and eq. (16), both of which need $\\Lambda^*$? How can we have these values in practice? Knowing $\\Lambda^*$ exists (finite) and selecting its value are non-trivial.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Decision: Reject