Near-Optimal Policy Identification in Robust Constrained Markov Decision Processes via Epigraph Form
Authors: Toshinori Kitamura
Tadashi Kozuno
Wataru Kumagai
Kenta Hoshino
Yohei Hosoe
Kazumi Kasaura
Masashi Hamaya
Paavo Parmas
Yutaka Matsuo
Venue: ICLR 2025 Poster (2025)
Keywords: Markov Decision Process
Constrained Optimization
Robust Optimization
Primary area: reinforcement learning
TL;DR: We propose the first algorithm to identify a near-optimal policy in a robust constrained MDP.

Abstract: Designing a safe policy for uncertain environments is crucial in real-world control systems. However, this challenge remains inadequately addressed within the Markov decision process (MDP) framework. This paper presents the first algorithm guaranteed to identify a near-optimal policy in a robust constrained MDP (RCMDP), where an optimal policy minimizes cumulative cost while satisfying constraints in the worst-case scenario across a set of environments. We first prove that the conventional policy gradient approach to the Lagrangian max-min formulation can become trapped in suboptimal solutions. This occurs when its inner minimization encounters a sum of conflicting gradients from the objective and constraint functions. To address this, we leverage the epigraph form of the RCMDP problem, which resolves the conflict by selecting a single gradient from either the objective or the constraints. Building on the epigraph form, we propose a bisection search algorithm with a policy gradient subroutine and prove that it identifies an $\varepsilon$-optimal policy in an RCMDP with $\widetilde{\mathcal{O}}(\varepsilon^{-4})$ robust policy evaluations.

Published as a conference paper at ICLR 2025
NEAR-OPTIMAL POLICY IDENTIFICATION IN ROBUST CONSTRAINED MARKOV DECISION PROCESSES VIA EPIGRAPH FORM
Toshinori Kitamura", Tadashi Kozuno"*, Wataru Kumagai", Kenta Hoshino', Yohei Hosoe', Kazumi Kasaura', Masashi Hamaya', Paavo Parmas', Yutaka Matsuo
The University of Tokyo, 2 OMRON SINIC X Corporation, Kyoto University, *Osaka University stoshinori-k@webleaeee u-tokyo. ac. jp
ABSTRACT
Designing a safe policy for uncertain environments is crucial in real-world con- trol systems. However, this challenge remains inadequately addressed within the Markov decision process (MDP) framework. This paper presents the first algo- rithm guaranteed identify near-optimal policy in a robust constrained MDP (RCMDP). where optimal policy minimizes cumulative cost while satisfying constraints in the worst-case scenario across a set environments. We first prove that the conventional policy gradient approach to the Lagrangian max-min for- mulation can become trapped in suboptimal solutions. This occurs when its in- ner minimization encounters sum of conflicting gradients from the objective and constraint functions. To address this, we leverage the epigraph form of the RCMDP problem, which resolves the conflict by selecting a single gradient from either the objective or the constraints. Building on the epigraph form, we propose a bisection search algorithm with policy gradient subroutine and prove that iden- tifies an e-optimal policy in an RCMDP with O( robust policy evaluations.
INTRODUCTION
In real-world decision-mmaing it is crucial to design policies that satisfy safety constraints even in uncertain environments. For example, self-driving cars must drive efficiently while maintaining safe distance from obstacles, regardless of environmental uncertainties such as road conditions, weather, the state of the vehicle's components. Traditionally, within the Markov decision process (MDP) framework, constraint satisfaction and environmental uncertainty have been addressed separately-throusee constrained MDP (CMDP; e.g., Altman 1999), which aims to minimize cumulative cost while satisfying constraints, and robust MDP (RMDP; e.g., [yengar 2005). which aims to minimize the worst-case cumulative cost However, in practice, both robustness and constraint satisfaction are important. The recent robust constrained MDP (RCMDP) framework addresses this dual need by aiming to minimize the worst-case cost while robustly satisfying the constraints. Despite significant theoretical progress in CMDPs and RMDPs (see Appendix AA, theoretical results RCMDPs remain scarce. Even in the tabular setting, where the state and action spaces are finite, there exists no algorithm with guarantees to find a npar-optimal policy an RCMDP.
uncertainty of possible environments.
The difficulty of RCMDPs arises from the challenging optimization process, which simultane- ously considers robustness and constraints. The dynamic programming (DP) approach, popular in unconstrained RMDPs, is unsuitable for constrained settings where Bellman's principle of optimality can be violated (Haviv) 1996 Bellman et al., 1957). Similarly, the linear programming (LP) approach, commonly used for CMDPs, is inadequate due to the nonconvexity of the robust formulation [Iyengar 2005) Ceene-Clément & Petrik 2024). Consequently, the policy gradient method with the Lagrangian formulation has been studied the primary remaining option (Russel jet al. 2020 Wang et al. (022).. The Lagrangian formulation approximates the RCMDP problem 0) by maxx20 min, f(T)) + XN(TT), where f(T) and h(T)) represent the
min, [
h(m))

---

Published as a conference paper at ICLR 2025
Approach
MDP
CMDP X
RMDP
RCMDP
Dynamic Programming
X
Beliman et al. (957)
Iyengar 2005
Linear Programming
X
Denardo
Altman [999
Lagrangian + PG
X
Agarwal (021
Ding el 2020)
Wang et 2023
Epigraph+ + PG (Ours)
Table I: Summaay of approaches and the problem settings. "PG" denotes Policy Gradient. Each cell displays "V" indicating the presence of algorithm with this approach that guarantees yielding an E-optimal policy. Representative works supporting each "V" are listed below it. Conversely, "X" denotes settings where the approach either isn't 't suitable lacks performance guarantees.
worst-case cumulative cost-called the (cost) return and the worst-case constraint violation of policy т, respectively. There have been few attempts to provide theoretical guarantees for the Lagrangian approach (Wang et al.] 2022] Zhang et al., [024]; however, no existing studies offer rigorous and satisfactory guarantees that the max-min problem yields the same solution as the original RCMDP problem. As a result, existing Lagrangian- basad algorithms lack theoretical performance guarantees. This leaves with fundamental question:
How can we identify a near-optimal policy in a tabular RCMDP?
We address this question by presenting three key contributions, which are summarized as follows:
Gradient conflict in the Lagrangian formulation (Section 3 We first show that solving the Lagrangian formulation is inherently difficult, even when its max-min problem can yield an optimal policy. Given the limitations of DP and LP approaches as discussed, the policy gradient method might seem like viable alternative to solve the max- max-min. However, our Theorem reveals that policy gradient methods can get trapped in a local minimum during the inner minimization of the Lagrangian formulation. This occurs when the gradients, Vf((T) and Vh(x), conflict with each other, causing their sum V (T) + (V to cancel out, even when the policy is not optimal. Consequently, the Lagrangian approach for RCMDPs may not reliably lead to a near-optimal policy.
We then demonstrate that the epigraph form, com- monly used in constrained optimization literature (Boyd & Vandenberghe 2004 [eyer & Sendhoff 2007| Rahimian & Mehrotra 2019), entirely circumvents the challenges associated with the Lagrangian formulation. The epigraph form transforms the RCMDP problem into miny min, (ax) y, v²)( < 0). introducing an auxiliary minimization problem of min, max - y. h(T)) and minimizing its threshold variable y. Unlike the Lagrangian approach, which necessitates summing ff(T) and Vh(T)) policy gradient methods for the auxiliary problem update the policy by selecting either V or Vh(Tr), thanks to the maximum operator the problem. As result, the epigraph form avoids the problem of conflicting gradient sums, preventing policy gradient methods from getting stuck in suboptimal minima (Theorem
Epigraph form of RCMDP (Section
new RCMDP algorithm (Section 5) Finally, we propose tabular RCMDP algorithm called Epigraph Robust Constrained Policy Gradient Search (EpiRC-PGS) pronounced as "Epic-P-G- S²). The algorithm employs a double-loop structure: the inner loop verifies the fcasibility of the threshold variable y by performing policy gradients on the auxiliary problem, while the outer loop employs a bisection search to determine the minimal feasible y. [pIRC-PGS] is guaranteed to find an E-optimal policy with Ö( -) robust policy evaluations (Corollary 1). where Ö(-) represents the conventional big-O notation excluding polylogarithmic terms. Since RCMDP generalizes plain MDP, CMDP, and RMDP, our Ep RC-PGS is applicable to all these types of MDPs, ensuring near-optimal policy identification for each. Table [ compares existing approaches in various MDP settings. Due to the page limitation, more related work is provided in Appendix A limitations and potential future directions in Section 7
We discuss
Wee often use the term return to refer specifically to the objective cost return. When discussing a return
value in the context of RCMDP's constraints, we refer to it as the constraint return.
"The definition of s-optimal policy is provided in Definition 1
2

---

Published as a conference paper at ICLR 2025
2 PRELIMINARY
We use the shorthand R+ = [0, 20). The set of probability distributions over S denoted by (S)) For two integers S b. we define [a, b] == {a....,b). 6). If a b, [a, bj = 0. For a vector x E IR,, its n-th element is denoted by In or æ(n), and we use the convention that ||r||| = v2 2, x. and |0 = max; | For two vectors 2; y E IRV,, we denote (æ, - Σ: J;ye- We let 0 = (O,...,0) 0) and 1 = (I..... .)",, with their dimensions being clear from the context. All scalar operations and inequalities should be understood point-wise when applied vectors + R as vector f R|S
and functions. Given finite set S, often treat function Both notations, S S + R and f E TR|S are used depending on notational convenience. Finally, (x)) and (xx)) denote the set of (Fréchet) subgradients and gradient of f X + R at point respectively. Their formal definitions are deferred to Definition
2.1 CONSTRAINED MARKOV DECISION PROCESS
Let N E Zzo be the number of constraints. An infinite-horizon discounted constrained MDP (CMDP) is defined as tuple (S,A, P. P.C. CCC,,,,) μr), where S denotes the finite state space with size S, A denotes the finite action space with size A, 7 E (0, 1) denotes the discount factor, and E (S)) denotes the initial state distribution. For notational brevity, let H == (1 7)- denotes the effective horizon. Further, b = "b.....,b// E [0, H|N denotes the constraint threshold vector, where bn is the threshold scalar for the n-th constraint, C == (Cn)ne[o,N] denotes the set of cost functions, where On S A - [0, 1] denotes the n-th cost function and (s, a) denotes the n-th cost when taking an action at state s. Cu is for the objective to optimize and {cI..... cN are for the constraints. p S x A + (S) denotes the transition probability kernel, which can be interpreted as the environment with which the agent interacts. P(s s, a) denotes the state transition probability new state s' from a state s when taking an action a.
2.2 POLICY AND VALUE FUNCTIONS
((A) for any E S. (s,, a) denotes the probability taking an action a at state 8. The set of all the policies is denoted as
A (Markovian stationary) policy is defined as E SA such that <(s.) :)
II. which corresponds to the direct parameterization policy class presented in Agarwal et (002 Although Mon-Markovian policies can yield better performance in general RMDP problems (Wiese- mann al. 2013), for simplicity, focus Markovian stationary policies in this paper. With an abuse of notation, for two functions T, g E SAA we denote (x, E. ((s, a))(s,a).
For a policy ı and transition kernel P. let d% : S - R4 denote the occupancy measure of under P. (s) represents the expected discounted number of times visits state under P, such that ds)(s = (1 7) [> >^1
= $} so μ. T, P]. Here, the notation means that the expectation is taken over all possible trajectories, where an ((sh.) and sh-1 P(- Sh, an).
For π E SA and a cost c E 1254, let OT.P 8 A + E. be the action-value function such that
Q2,((s,) c(s, a) +y
Σ T(s' (' a'EA
((s.a)
S'ES
Let V S be the state-value function such that (x) = EoEA ((8 a) ((,,a))Q,,p( (s, a) for any s E I E II, (s) represents the expected cumulative cost of π under P with an initial state s. We denote the (cost) return function as Je.p(T) = E.es u(s) V(
Policy gradient method. For a problem min f(T) where f I1 + R is differentiable at II, policy gradient methods with direct parameterization update æ to new policy n' as follows:
1
= Projn (TT a (T)) @ arg min (VI(T), n' m) + 2a
(1)
m'Ell
where is the learning rate and Projy denotes the Euclidean projection operator onto II. The equality (a) is a standard result (see, e.g., Parikh et al. (2014)). The following lemma provides the gradient of Je, (TT) for the direct parameterization policy class II (e.g.. Agarwal al. (021)).
The domain of Q is not restricted to IT to ensure well-defined policy gradients over E TT.
3

---

Published as a conference paper at ICLR 2025
Lemma 1 (Policy gradient theorem). For any π E II, transition kernel P. x A (SS) and cost c E RSA,, the gradient is given by (V))..(T))(s..)) = (d [
V(s,a) ESx
2.3 ROBUST CONSTRAINED MARKOV DECISION PROCESS
An infinite-horizon discounted robust constrained MDP (RCMDP) is defined as a tuple (S,A, C,b, where U is compact set of transition kemels, called the uncertainty set, which can be either finite or infinite. The infinite uncertainty set typically requires some structural assumptions. A common structure is the (s, -ecttaurcaa
(Iyengar 2005 Nilim &
El Ghaoui ) defined as U = X Us where Us S 9 (S) and x denotes Cartesian product over A. We remark that our work is not limited any specific structural assumption,
but rather considers a general, tractable uncertainty set (see Assumptions 1 and 3 When N = 0,
an RCMDP reduces to an RMDP. When 4 (P), an RCMDP becomes CMDP.
For cost e E R&A, let (T) = maXpez ((T) denote the worst-case (cost) return function,
which represents the cost return of ı under the most adversarial environment within U. The goal of an RCMDP is to find solution to the following constrained optimization problem:
(RCMDP) J min (TT) such that (T)) S bn Vn [1,
(2)
xell
Let 1I == {TT E II maxnE[L.N] Jo,, (T)) - bn - 0} be the set of all the feasible policies. We assume that Tp non-empty. An optimal policy x'" Ip a solution to Equation (2).
Definition 1. π E II is e-optimaf Jo (no J S e and maxne]1.N] (1)))( bn S
3 CHALLENGES OF LAGRANGIAN FORMULATION
To motivate our formulations and algorithms presented in subsequent sections, this section illus- trates the limitations of using the conventional Lagrangian approach for RCMDPs. By introducing Lagrangian multipliers À = (A1...., AN) E R. Equation (2) is equivalent to
N
J min max ( TEll AER
Σ
An (n(Cen - bn)
As this ming hard to solve due to the inner maximization, Russel et al. (2020); Mankowitz et al.) 2020); Wang et al. (2022) swap the min-max and consider the following Lagrangian formulation:
(Lagrange)
max min Lx(T) where Lx(x) = Joo (T) + A (n - bn) (3)
XER sell
Let X" be a solution to Equation 3 The Lagrangian approach aims to solve Equation (3) by expect- ing x* arg min Lx- (T). However, this expectation may not hold, as swapping the min-max is not necessarily equivalent to the original min-max problem (Boyd & Vandenberghe) 2004). There- fore, guarantee the performance of the Lagrange approach, the questions must be addressed:
(i) Can ensure T* arg min Lx- (T)) (ii) If so, is tractable to solve mingeen L (m)?
However, answering these questions affirmatively is challenging due to the following issues:
(i) π- solution challenge. To ensure that T² E arg min rell (x.(T). ) the standard approach is to establish the strong duality, i.c., J L* (Boyd & Vandenberghe, 2004). In the CMDP setting, where 4 {P). strong duality has been proven to hold (Altman 1999 Paternain et al. 2019
2022]. However, proving strong duality for RCMDPs is highly non-trie trivial compared to CMDPs.
When 2 = {P), a typical proof strategy is to combine the sum of cost returns Je,.P.... Jex P in (x) into a single return function. For example, when 1, we have Ix(TT) (T)) where
*ttict constraint satisfaction is straightforward by using slightly stricter threshold 1'
4

---

Published as a conference paper at ICLR 2025
Lifna 244
Py: Objective worst case for 1
Pa: Constraint worst-case for H, "2
2000
84
160
4,4 1.0
Ga 6.1
Gadia 6,11
2000
2430
d2
S2
2043
Cards -Li-5
[x(r) 2.51
Local
(1(1::91)
(a) RCMDP presented in Example
! where 8 O.
(b) Li (z) and policy gradients.
Figure 1: (a): An RCMDP example illustrating the gradient conflict challenge. Action labels omitted when transitions action-independen independent. (b): Policy gradients in the example with (7, b)) = (0.4, 0.09, 0). Arrows represent the gradient to decrease (T).. T2 attracts policy gradients but is local minimum since L1 (TT2 La (TI), where T (;,a) = and T2(;,02) 1.
é + Me11 - /H1)). Since (T)) is linearly represented as pxx (c dr. is easy to show min, max, ((T) = max, min, P(T) by Sion's 's minimax theorem Sion 1958).
However, applying this return-combining strategy to RCMDPs is difficult. For n E [I, let Pa E arg maxpey ((T). When [2]] # 1, (T)) has a sum of returns Ja., (T) (T).... JeN. Jev.PN PP (T), where Po + ... * PN may differ. Thus, [Trr) no longer takes the form of (c', d')) for a single environment P. making well-established duality proof techniques in CMDP literature inapplicable.
(ii) Gradient conflict challenge. Unfortunately, even if strong duality holds and n' can be found by x² E arg min Tx- (T), solving this minimization remains challenging. Since the sum of robust cost returns in Lx (α) excludes the use of DP and convex-optimization approaches [Iyengar 2005 Altman 1999| Grand-Clément & Petrik 2024). the policy gradient method such as Equation 1 the primary remaining option to solve ein (T)
In CMDP setting when [u[| = 1. the problem mittgen (T(T) reduces to solving a standard MDP and thus the policy gradient method is ensured solve min (x) (Agarwal al.) 2021) However, the following Theorem [ shows that even when [ = 2, RCMDP can trap the policy gradient in a local minimum that does not solve min (T)::
Theorem 1. For any 7 E (0, 1), there exist a X > O, policy и E Tl and an RCMDP with p. >
satisfying the following condition: There exists a positive constant R R> 0 such that, for any bi E IR.
3-
[T(T)) < (x) VT ( E IT || - 2112 R x # but [x(m) 2 min L [x( +
(4)
xell
16
Moreover, there exists b1 (0, H) where Ā satisfies À E arg maXXeRN min (x
The detailed proof is deferred to Appendix G Essentially, the proof constructs simple RCMDP where the policy gradients for the objective and the constraint are in conflict.
Example 1. Consider the RCMDP with u (2) presented in Figure la with 5 0, a = 0.251, and set = 1 for simplicity. Let и and n2 be policies that select ai and 02 for all states, respectively. For both policies, the objective worst-case is P1 and the constraint worst-case is P2 (see Appendix G.. Hence, switching from policy Te to taking action @1 decreases the objective return in P, but increases the constraint return in Pg. This conflict causes the gradients of Ta for the objective (VJog, (m2)) and for the constraint (VJe,,P (T2)) to sum to a constant vector, i.e., (T2()))))s: :) (VJe,.P, (T2) + (
= constant 1 Vs S (5) showing that T2 is a stationary point. However, m2 cannot solve min L1 (T) because Ti would clearly result in a smaller (T). This stationary point becomes a strict local minimum when 8 > O, where Ty slightly prefers d2 over dn (see Appendix G for details).
Figure lb computationally illustrates this negative result by plotting the landscape of L [T(T) in the RCMDP example across all possible policies for (7, 6) (0.4. 0.09). We set b, 0 as it does not influence the landscape of L, (x). In this example, To becomes a local minimum that attracts the policy gradient but fails to solve minzen (TT) as सi achieves [x(=)) < (x(
With abuse of notation, here denote d' a) E "1 {sk. 8. = a) 80 ~ NM
5

---

Published as a conference paper at ICLR 2025
4 EPIGRAPH FORM OF RCMDP
This section introduces the epigraph form of RCMDP, which overcomes the challenges discussed
in Section 3 For constrained optimization problem of the form min h(x)) - 0} with
x E 12"h and f, h IR" + IR, its epigraph form is defined as: min such that f() < y and h(x) 00
(6)
with variables E R and y E R. It is well-known that (ar y) is optimal for Equation (6 if and only if r optimal for the original problem and y == fx) (see, e.g.. [oyd & Vandenberghe 2004).
Using Equation
6 and by introducing new optimization variable bo [0, H), an RCMDP becomes Jen (x) S bu and (e.. - b, Vn E [1,
J min bu such that
(7)
H)
constraint minimize objecttive
constraints for lElly
Intuitively, Equation 7 seeks the smallest objective threshold bn such that feasible policy я E Пp exists with its cumulative objective cost satisfying (e S ho.
We transform Equation into a more convenient form. Define Ad, : RRAA -> R such that
bbp (T) max (TT - by VT E II,
(8)
n
which denotes the maximum violation of the constraints max (() bn S 0 with the additional constraint Jen (T) 6o S O. By moving min in Equation to its constraint and using Abo (T), Equation ? can be transformed as follows:
Theorem 2. Let A = min Abo (T)), where Abo (x)) is defined in Equation 8 Then,
(Epigraph Form) J min by such that Aio S0.
Furthermore, if bo J", any π E arg min Ato (T) is optimal.
The proof is provided in Appendix H.2 Instead of Equation 77. we call Equation (9) the epigraph
form of RCMDP. Since the epigraph form provides J and x it overcomes the π solution chal- lenge discussed in Section 3
The remaining task develop an algorithm to solve Equation (
EPIRC-PGS ALGORITHM
According to Theorem we can solve an RCMDP by first identifying the optimal return value by J and then solving min Asp (x). Our Epigraph Robust Constrained Policy Gradient Search (EpiRC-PGS) algorithm implements these two steps using double-loop structure: (i) an outer loop that determines bn = J through a bisection search over by E [0, H) (Section 5.1 and (ii) an inner loop that solves min Ang (x) using a policy gradient subroutine (Section 5.2)
Note that without any assumptions about the uncertainty set U, solving an RCMDP is NP-hard (Wiesemann al. 2013). However, imposing concrete structures on U can restrict the applicability ReableEpiRc. EpiRC- PGS to handle a broader class U4, we consider Ui where we approximate the robust cost return value Jc,, (TTT) and its subgradient aJe,, (e(T) as follows:
of Epicc PPSS To enable
Assumption (Robust policy evaluator). For each such that [.. - J... S Eest for any π E TI, where Eest 2 0.
[0,N], have algorithm J. II R
Assumption 2. 2/ is either (i) a finite set or (ii) a compact set such that, for any π E II, V.e...PTTT is continuous with respect to P U. Assumption 3 (Subgradient evaluator). For each n E [[o NJ. we have an algorithm To : I1 - SA such that mingeeJ.,, (x) [ glla S Eged for any E IT, where Egra 2 0.
Assumptions
I 2 and Bl are satisfied for most tractable uncertainty sets, such as finite, ball (Kumar 2024). R-contamination (Wang & Zou| 2022), Ir, x². and Kullback-Leibler (KL.) sets (Yang
et al.
ct al.
2022).
For these tractable uncertainty sets U the robust policy evaluator (J,) and subgradient
evaluator (Jo) can be efficiently implemented using robust DP methods (Iyengar 2005 Kumar al.
2022 2024 Wang & Zou 2022). As concrete examples, we provide detailed implementations of Jn and J for finite and KL sets in Appendix C We assumed Assumption because the envelope the- orem (Lemmas and 10), together with this assumption, guarantees that JJ,,, ((()) is dell-defined.

---

Published as a conference paper at ICLR 2025
Algorithm Bisection Search with gin (n) Subroutine
(also referred to as EpiRC- PGS when using Algorithm aas the subroutine)
1: Input: Iteration length K E N, evaluator Jn and subroutine sl (see Assumptions
and
2: Initialize the search space: ;(0) = and j(0) = H
3: for k = 0.... ...
K 1 do
4: (kk) of (b) where (/4) (i(h) //k))
I/ Compute policy by subroutine // Robust policy evaluation
5: A (k) = Io.NN (T)) 6n where by = 6/
6: Compute j(++1) and j(k+1) by Equation 11 using (R)
Update search space
7: end for
8: return Tiet computed by of (j(K))
5.1 BISECTION SEARCH WITH minzenl Abg (л) SUBROUTINE
A J
This section describes the outer loop of EpirC PGS to identify
0.4
bp = J" The outer loop utilizes the following monotonicity Ag for the identification. The proof is deferred to Appendix H.1
If Ag S0, decreasa
Lemma 2. Ai, is monotonically decreasing in bo and Aj. O.
0.0
Thanks to this monotonicity of A.,, if A can be efficiently computed, a line search over bo E [0, H] will readily find bo Jr. Increase by At, 0, and decrease it if A S Figure summarizes this idea to solve the epigraph form.
0.00 0.26
0.50
0.75
1.00
125
Figure 2: Algorithmic idea to find bo J in Example with (y,8,b) 0,21,),2/3)
To implement this idea, let us assume for now that we have subroutine algorithm of that computes A = min Abp (T) with sufficient accuracy. We will implement s in Section 5.1
Assumption 4 (Subroutine algorithm). We have an algorithm s : R - II that takes a value bo and returns π E II such that (T) min AN. (T') + Eopt, where Eopc 0.
Using this subroutine d, the outer loop conducts bisection search over bo [0, Let K E be the number of iterations. For each iteration k, let (g(k), j(A] C [0, H] be the search space where ((k) < j(k), Set ;(0) = 0 and j(0) = Ht and define 6/ = (i(k) + //2) Additionally, given ((h)
denote the returned policy from s as (1)) == ot (bbb)) and its estimated A value
(k) max (T)) - bn where b0 = 60 [0.N]
(10)
Based on Figure our bisection search increases 60 if (R) > 0; otherwise, it decreases (k),
(A++1
(k) b
if A
0 and ((++)
((())
if A (k) > 0
(11)
(()
otherwise
((K)
otherwise
We summarize the pseudocode of this bisection search in Algorithm || The following Theorem ensures that Algorithm returns near-optimal policy. We provide the proof in Appendix H.S
Theorem 3. Suppose that Algorithm 1 is run with algorithms Jnn and of that satisfy Assumptions and 4 Then, Algorithm returns an E-optimal policy, where = 2(Eopt Eest) + 2 H.
5.2 SUBROUTINE ALGORITIM TO SOLVE min Ang (T)
The remaining task is to implement the subroutine s which satisfies Assumption In other words, for given by, we need to solve the following auxiliary problem:
(Epigraph's 's Auxiliary Problem)
min A (T) xEll
min max max Je., (o)(()))))) b
(12)
well nE[o,N] PEU
The right-hand side of Equation 12 can be seen as an RMDP with additional robustness over the set of modified cost functions Co Cn. bn/ H1), ne Note that since Co2 is not rectangular set,
7

---

Published as a conference paper at ICLR 2025
Algorithm 2 Projected Policy Gradient Subroutine
1: Input: Threshold parameter bo 2 0. learning rate > 0. iteration length T E N. policy
evaluator Jn and subgradient evaluator Já (see Assumptions and
2: Set arbitrary initial policy x:()) E II
3: for = 0, ........... ,
do
4: vn(1) E arg max na In(T(()) bn-
Select the most violated constraint
5: n nT(++1) = (roin(= og) where g()) = (x(1)
Update policy
6: end for
7: return T((") where t* E arg min (1) and (+)) = max (T( bn
even if is rectangular, the combination Co x 24 does not retain rectangularity, As a result, existing RMDP algorithms designed for rectangular sets, such as DP (Iyengar 2005), natural policy gradient & Petrik 2024). are inapplicable.
Li et al. 2022), and convex optimization
Due to this non-rectangularity issue, employ the projected policy gradient method, together with the following subgradient of a (TT). The proof is deferred to Appendix H.3
Lemma 3. Define Gio (TT) = (VT)..P(TT) n, P E arg P)E
Jon P(T) - bn] for
any by E R and π E II. Let conv B denote the convex hull of a set B C RSA, Under Assumption 2 for any II and bu E R, the subgradient of Abp(-) at is given by dAbn (x) conv Gon (T))
We implement the subroutine sf (bo) based on this subgradient lemma. Starting from an arbitrary policy x (0), let ((1), (7(1).... ....,,((T) (TT) be the updated policies where T E N is the iteration length. Using the evaluators Jn. Th and learning rate > O, for a given bo. our subroutine updates policy as follows:
((++1) = (ro agl where g( = ( and (2) E aag arggax./. J. b,
ne[o,N]
(13)
We summarize the pseudocode of this policy update subroutine in Algorithm 2
Remark 1 (Comparison to Lagrange). Recall Equation (5) that the subgradient of the Lagrangian's auxiliary problem, (T). involves a summation of policy gradients over different environments. On the other hand, Equation [3) focuses on the policy gradient of single worst-case environment by taking mo Intuitively, our policy update avoids the sum of conflicting policy gradients, therehy circumventing the gradient conffict challenge discussed in Section Indeed, when the ini- tial distribution satisfies the following coverage assumptior there no local minimum in Asp (T)):
Assumption (Initial distribution coverage). The initial distribution μ E (S)) satisfies p >> 0. Theorem 4 (Optimality of stationary points). Under Assumptions 2 and 5 for any (T, bo) II R, < DH max (IT n'Ell
Ang (T) min ANn (TT)
n',9) Vg (T)
n'Ell
where D max,,
dpp Fa. /vl
with -h E arg min P(..
The detailed proof can be found in Appendix H.4 Our proof is similar to Theorem 3.2 in Wang et al. (2023). but it is more rigorous and corrects a crucial emror that can invalidate their resul Moreover, while their proof is limited to cases where arg maX PT) is finite, ours is not.
We leverage Sion's minimax theorem (Sion 1958) for this refinement.
Thanks to the optimality of stationary points of An, (T) (Theorem 4. Algorithm 2 is guaranteed to solve minzen Ab, (т) and satisfies the requirement of ed (bo) in Assumption as follows:
Theorem 5. Suppose Assumptions 7 2 Woodd Then, there exist problem-dependee constants Co.C,. Ca, Cr > 0 that do not depend on such that, when Algoritium 2 is run with a = Ca and T Cre the evaluators are sufficiently accurate such that Egrd Cgs² and Eest C)E? Algorithm 2
returns a policy ({t") satisfying As, (T(()((t)) min A (T) S
Such coverage assumption is necessary to ensure the global convergence of policy gradient methods Meei 2020). Additionally, note that the Lagrange performs poorly even under Assumption 5 (sec Theorem example, their proof around Equation (32) incorrectly bounds a positive value by negative value.
ct al.
8

---

Published as a conference paper at ICLR 2025
LF
LFv
EpiRC- PGS (Ours)
LF-dp"- (only for IM
(a) RCMDP [144 3)
(b) RCMDP (KL)
(c) CMDP ((4
1)
Violalion
25
0.0
0.
Feasible policies
Feasible policies
Feasible policies
10'
1d
10'
Outer Iteration
Outer Iteration
Outer Iteration
Objective Return
(Smaller is belter)
-52
optimal return
100
to'
16
12
16
1s'
10
Outer iteration
Outer Iteration it
Outer Iteration &
Vialesion
optimal return
X Feasible policies
Feasible policies
Feasible policies
-14
-2
-00
-15
-11
-10
-26 -ts -34 -2
Objective Return (smaller better)
Objective Return (smaller better)
Objective Retur (smaller better)
Figure 3: Comparison of the algorithms different settings (a), (b), and (c), defined in Section 6 The feasible (k) with the smallest return is marked; if none is feasible, the one with the smallest violation is marked. In all the settings, EpiRC PGS quickly identifies a feasible and low-return policy Top row: Constraint violation (y-axis: (
b1). Policies in the blue area satisfy the constraints. Middle row: Objective return relative to the uniform policy (y-axis: Jen 24 (x)) - Jan (T )) Negative values indicate that the policies achieve non-trivial low cumulative objective cots. Bottom row: Constraint violation vs. relative objective return.
We provide the proof and the concrete values of Co, CJ, Co and Cr Appendix H.6 The proof is primarily based on the weakly convex function analysis (Beck) 2017 Wang et al. 2022).
Remark 2 (Best-iterate convergence). Lagrangian-basse -based CMDP algorithms typically rely on
averaging past policies (e.g.. Li et al. (2024); Liu et al.
(202T)) which can be impractical in In contrast, Theorem 5 avoids policy averaging and guarantees that the best policy among (0) . " (T-1)) converges to the solution.
memory-intensive settings, such as deep RL applications.
5.3 COMBINING BISECTION SEARCH WITH THE POLICY GRADIENT SUBROUTINE
Finally, we combine Algorithm | with Algorithm 2 subroutine and refer the combination as EpiRC-PGS According to Theorems 3 5 Ep RC-PGS is ensured to find an e-optimal policy:
Corollary 1. Consider the same settings and notations as Theorem 5 Set Algorithm Das the sub- routine of with parameters (Jn, Jo a. T",, where we set a = C.e²/44 /4, T = 16Crs -4, Then, given inputs Jn and s, Algorithm I returns s-optimal policy after K [log (2H= ') iterations.
Remark (Computational complexity). SpiRC-PGS outputs an e-optimal policy by querying J, and J total of Ō((N + 1)K times. Thus, the computational complexity of F RC-PGS be expressed as Ö(N + 1)KT x [querying cost)). As simple example, consider the case where is finite, where querying (T) and (T) require Ō(S² A(U)) operations Kumar et al. 2024) Using the concrete value of KT,, the computational complexity ofEEiRC- PGS finite 2/ becomes O(DiS$ A* + 1)e-1y 1). Similar analyses can be applied to other types of uncertainty sets.
can
EXPERIMENTS
To support the theoretical guarantees of EpiRC-PGS and demonstrate the limitations of the Lagrangian methods in identifying opar-optimal policies, this section empirically evaluates RpiRC-PGS in three settings with five constraints (N 5):

---

Published as a conference paper at ICLR 2025
(a) RCMDP with U = (Pi....,PP) where each environment P. is randomly generated.
(b) RCMDP with a (s, (...t)rrectagulaa KL uncertainty set (Iyengar 2005). which considers
U Xs,a E (S)) KL P(- s, a)] S CRT.
18 where is nominal environment.
(c) CMDP, which is equivalent to RCMDP with U {P).
Environment construction. In (a). (b), and (c), we randomly generate environments follow- ing the experimental setup of Dann et al. (2017). For each state-action pair (s,a). a), transition probabilities P(- s, a) are independently sampled from a Dirichlet(O.1..... 0.1) distribution. This produces a concentrated yet non-deterministic transition model, resembling the widely used GARNET benchmark with branching factor of (Archibald et al. 1995). Cost values (n,s a) are assigned as (1 with probability 0.1 and 1 otherwise. Initial state probabilities uu(-) are sampled from (O.5, 0.5) distribution. Constraint thresholds bi.... by are set to ensure the existence of feasible policy. Additional environmental parameters are described in Appendix
Baseline algorithms. We compare EpiRC-PGS with a Lagrangian counterpart, denoted L.F. which abstracts most existing Lagrangian-baser algorithms for RCMDPs (e.g.. Russel et al. 2020
Wang et al. 2022). LE aims to solve the problem maxxeR# min (x(=) in Equation 3 by
performing gradient ascent À while using policy gradient subroutine to solve min Lx(
We also evaluate the averaged policies generated by LF, defined as & Ei= (k)) Such policy averaging is employed in Lagrangian methods (Mryoosseti et al. 2019 /Zang al. 2024), though it often lacks theoretical guarantees (see Appendix (..4). In the CMDP setting (c), we further evaluate the averaged occupancy measures, where the k-th policy is derived from Σ}= dp Averaging
dp")) is ensured to identify opar-optimal policy (Zahavy et al. 2021 but is well-defined only when [2[] = 1. We refer to these two averagings as LF (AF-7(()-ag and LF LF-d7 -avg, respectively. Moreover, (c) reports the optimal return value computed via LP method (Altman 1999). The detailed implementation of algorithms are provided in Appendix D
Results. Figure 3 illustrates the performance of the algorithms averaged over 10 random seeds. Across all settings, EpiRC- PGS rapidly converges to a feasible policy with a low objective cost return, while both LF and LF -F--Tle (MF= fail to identify feasible policies in certain settings (e.g., LF=-T( (1) avg in (a) and LE in (b)). In the CMDP (c), EpiRC-PGS and LF-d7" (k) -avg converge to near-optimal policy, but (F- does not. These results empirically validate that EpiRC-PGS] yields a near-optimal policy in RCMDPs, contrasting with the conventional Lagrangian-based algorithm's inability in robust settings.
-vy
7 CONCLUSION AND LIMITATIONS
In this work, we propose Epi RC-RC-2 PGS the first algorithm guaranteed to find a near-optimal policy in RCMDP (Corollary D). At its core, EpiRC-PGS leverages the epigraph form of RCMDPs, which not only ensures the optimal policy n² can be obtained (Section 4 but also enables a policy gradient algorithm efficiently find it (Theorem These features address the optimization challenges encountered in the conventional Lagrangian formulation (Section 3)
Limitations and future work. A double-loop algorithm like EeiRC-PGS is often inefficient when the inner problem requires high computational cost (Lin et al. 2024). Developing single-loop algorithm is a promising direction for future research, and we discuss the challenges in Appendix B
Another research avenue is improving the iteration complexity of our Ō(s-)). This may not be tight, since for RMDPs with (s, rrettatrcta the natural policy gradient method is ensured to find an s-optimal policy with ((s-2) iterations Li et al. (0222).
Finally, the coverage assumption on the initial distribution (Assumption 5) is not necessary in CMDPs (Ding et al. 2024). We leave the removal of Assumption 5
RCMDPs for future work.
STT g] = ExES p(s) In (np())/((()) represents the KI. divergence hetween two probability distributions p > and q defined over S. CKL > 0 is positive constant.
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGMENTS
This work is supported by JST Moonshot R&D Program Grant Number JPMJMS2236. We thank Arnob Ghosh for his advice on improving the expression of assumptions in this paper.
REFERENCES
Jacob D Abernethy and Jun-Kun Wang. On Trank-Wolfs and Equilibrium Computation. In Advances in Neural Information Processing Systems, 2017.
Joshua Achiam, David Held, Aviv Tamar, and Picter Abbeel. Constrained Policy Optimization. In International Conference on Machine Learning, 2017.
Alekh Agarwal, Sham M Kakade, Jason D Lee, and Gaurav Mahajan. On the Theory of Policy Gra- dient Methods: Optimality, Approximation, and Distribution Shift. Journal of Machine Learning Research, 22(98):1 2021.
Eitan Altman. Constrained Markov Decision Processes, volume 7. CRC Press, 1999.
James Anderson, John C Doyle, Steven H Low, and Nikolai Matni. System Level Synthesis. Annual Reviews in Control, 47:364-393, 2019.
TW Archibald, KIM McKinnon, and L.C Thomas. On the Generation of Markov Decision Processes. Journal of the Operational Research Society, 46(3):354-361, 1995.
Amir Beck. First-Order Methods in Optimization. SIAM, 2017.
R. Bellman, R.E. Bellman, and Rand Corporation. Dynamic Programming. Princeton University Press, 1957.
Alberto Bemporad and Manfred Morari. Robust Model Predictive Control: A Survey. In Robustness in Identification and Control, pp. 207-226. Springer, 2007.
Hans-Georg
Hans Georg Beyer and Bernhard Sendhoff. Robust Optimization Comprehensive Survey. Com- puter Methods in Applied Mechanics and Engineering, 196(33-34):1100-3 90-3218, 2007.
Stephen P Boyd and Lieven Vandenberghe. Convex Optimization. Cambridge University Press, 2004.
Archana Bura, Aria HasanzadeZonuzz, Dileep Kalathil, Srinivas Shakkottai. and Jean-Francois Chamberland. DOPE: Doubly Optimistic and Pessimistic Exploration for Safe Reinforcement Learning. Advances in Neural Information Processing Systems, 2022.
Hyeong Soo Chang. Approximate Constrained Discounted Dynamic Programming with Uniform Feasibility and Optimality. arXiv preprint arXiv:2308.03229 2023.
Richard C Chen and Gilmer L Blankenship. Dynamic Programming Equations for Discounted Constrained Stochastic Control. IEEE Transactions on Automatic Control, 49(5)=69,-709, 2004.
Richard Chen and Eugene A Feinberg. Randomzzddd Control of Constrained Markov Decision
Processes. In American Control Conference, 2006.
Yi CCennJJing Dong, and Zhaoran Wang. A Primal-Dual Approach to Constrained Markov Decision Processes. arXiv preprint arXiv:2101. 2021.
Zhi Chen, Penggian Yu, and William B Haskell, Distributionally Robust Optimization for Sequential Decision-Making. Optimization, 68 68(12):2377-2426 2019.
Francis H Clarke, Yuri Ledyaev, Ronald Stern, and Peter R Wolenski. Nonsmooth analysis and Control Theory, volume 178. Springer Science & Business Media, 2008.
Frank H Clarke. Optimization and Nonsmooth Analysis. SIAM, 1990.
Pierre Clavier, Erwan Le Pennec, and Matthieu Geist. Towards minimax Optimality of Model-based Robust Reinforcement Learning. arXiv preprint arXiv:2302.05372, 2023.

---

Published as a conference paper at ICLR 2025
Christoph Dann, Tor Lattimore, and Emma Brunskill. Unifying PAC and Regret: Uniform PAC Bounds for Episodic Reinforcement Learning. In Advances in Neural Information Processing Systems, 2017.
Eric V Denardo. On Linear Programming in a Markov Decision Problem. Management Science, 16 (5):281-288, 1970.
Esther Derman, Matthieu Geist, and Shie Mannor. Twice Regularized MDPs and the Equivalence Between Robustness and Regularization. In Advances in Neural Information Processing Systems, 2021.
Dongsheng Ding, Kaiqing Zhang, Tamer Basar, and Mihailo Jovanovic. Natural Policy Gradient Primal-Dual Method for Constrained Markov Decision Processes. In Advances in Neural Infor- mation Processing Systems, 2020.
Dongsheng Ding, Chen- Yu Wei, Kaiqing Zhang, and Alejandro Ribeiro. Last-Iterate Convergent Policy Gradient Primal-Dual Methods for Constrained MDPs. In Advances in Neural Information Processing Systems, 2024.
John Doyle. Analysis of Feedback Systems with Structured Uncertainties. In IEE Proceedings D-Control Theory and Applications, 1982.
Simon Du, Sham Kakade, Jason Lee, Shachar Lovett, Gaurav Mahajan, Wen Sun, and Ruosong Wang. Bilinear Classes: A Structural Framework for Provable Generalization in RL. In Interna- tional Conference on Machine Learning, 2021.
Simon Du, Yining Wang, Sivaraman Balakrishnan, Pradeep Ravikumar, and Aarti Singh. Robust Nonparametric Regression under Huber's 6-contamination Model. arXiv preprint arXiv:1805.1 10406, 2018.
Yonathan Efroni, Shie Mannor, and Matteo Pirotta. Explorationn-Exllottaiii in Constrained MDPs. arXiv preprint arXiv:2003.02/89, 2020.
Arnob Ghosh. Sample Complexity for Obtaining Sub-optimality and Violation Bound for Distribu- tionally Robust Constrained MDP. In Reinforcement Learning Safety Workshop, 2024.
Vineet Goyal and Julien Grand-Clement. Robust Markov Decision Processes: Beyond Rectangular- ity. Mathematics of Operations Research, 48(1 (161):)33222 2023.
Julien BraaddClémeed and Christian Kroer. Scalable First-Order Methods for Robust Mdps. In AAAI Conference on Artificial Intelligence, 2021.
Julien Grand-Clément and Marek Petrik. On the Convex Formulations of Robust Markov Decision
Processes. Mathematics of Operations Research, 0(0), 2024.
Aria HasanzadeZoonuzy Archana Bura, Dileep Kalathil, and Srinivas Shakkottai. Learning with Safety Constraints: Sample Complexity of Reinforcement Learning for Constrained MDPs. In AAAÍ Conference on Artificial Intelligence, 2021.
Moshe Haviv. On Constrained Markov Decision Processes. Operations Research Letters, 19(1):
25-28, 1996.
Chin Pang Ho, Marek Petrik, and Wolfram Wiesemann. Partial Policy Iteration for L1-Robust Markov Decision Processes. Journal of Machine Learning Research, 22(275):1-46, 2021.
Garud N Iyengar. Robust Dynamic Programming. Mathematics of Operations Research, 30(2): 257-280, 2005.
Nan Jiang. PAC Reinforcement Learning with Imperfect Model. Intellignnce, 2018
Model. In AAAI Conference Artificial
Toshinori Kitamura, Tadashi Kozuno, Masahiro Kato, Yuki Ichihara, Soichiro Nishimori, Akiyoshi Sannai, Sho Sonoda, Wataru Kumagai, and Yutaka Matsuo. A Policy Gradient Primal-Dual Algo- rithm for Constrained MDPs with Uniform PAC Guarantees. arXiv preprint 2401:22401.17780 2024.
12

---

Published as a conference paper at ICLR 2025
A Ya Kruger. On Fréchet Subdifferentials. Journal of Mathematical Sciences, 116(3):3325-3355 2003.
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.
Navdeep Kumar, Esther Derman, Matthieu Geist, Kfir Y Levy, and Shie Mannor. Policy Gradient for Rectangular Robust Markov Decision Processes. In Advances in Neural Information Processing Systems, 2024.
Hoang Le, Cameron Voloshin, and Yisong Yue. Batch Policy Learning Under Constraints. In International Conference on Machine Learning, 2019.
Tianjiao Li, Ziwei Guan, Shaofeng Zou, Tengyu Xu, Yingbin Liang, and Guanghui Lan. Faster Algorithm and Sharper Analysis for Constrained Markov Decision Process. Operations Research Letters, 54:107107, 2024.
Yan Li, Guanghui Lan, and Tuo Zhao. First-Order Policy Optimization for Robust Markov Decision Process. arXiv preprint 200.:92209.0079, 2022.
Zhenwei Lin, Chenyu Xue, Qi Deng, and Yinyu Ye. A Single-Loop Robust Policy Gradient Method for Robust Markov Decision Processes, arXiv preprint arXiv:2406.00274 2024.
Tao Liu, Ruida Zhou, Dileep Kalathil, Panganamala Kumar, and Chao Tian. Learning Policies with Zero or Bounded Constraint Violation for Constrained MDPs. In Advances in Neural Information Processing Systems, 2021.
Tien Mai and Patrick Jaillet. Robust Entropy-Regularizzed Markov Decision Processes. arXiv preprint arXiv:21 2021.
Daniel Mankowitz, Dan A Calian, Rae Jcong. 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.
Jincheng Mei, Chenjun Xiao, Csaba Szepesvari, and Dale Schuurmans. On the Global Convergence Rates of Softmax Policy Gradient Methods. International Conference on Machine Learning, 2020.
VS Mikhalevich, AM Gupal, and VI Norkin. Methods of Nonconvex Optimization. arXiv preprint arXiv:2406. /0406, 2024.
Sobhan Miryoosefi, Kianté Brantley, Hal Daume III, Miro Dudik, and Robert E Schapire. Reinforce- ment Learning with Convex Constraints. In Advances in Neural Information Processing Systems, 2019.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Mare G Belle- mare, Alex Graves, Martin Riedmiller, Andreas Fidjeland, Georg Ostrovski, et al. Human-level Control through Deep Reinforcement Learning. Nature, 518(7540):529-533, 2015.
Adrian Müller, Pragnya Alatur, Volkan Cevher, Giorgia Ramponi, and Niao He. Truly No-Regret Learning in Constrained MDPs. arXiv preprint 1577, 2024.
Ofir Nachum and Bo Dai. Reinforcement Learning via arXiv:2001.01860 2020.
Duality, arXiv preprint
Arnab Nilim and Laurent El Ghaoui. Robust Control of Markov Decision Processes with Uncertain Transition Matrices. Operations Research, 53(5):780-798, 2005.
Kishan Panaganti and Dileep Kalathil. Sample Complexity of Robust Reinforcement Learning with Generative Model. In International Conference on Artificial Intelligence and Statisties, 2022.
Neal Parikh, Stephen Boyd, et al. Proximal algorithms. Foundations and Trends@ in Optimization, 133::177-33, 2014.
13

---

Published as a conference paper at ICLR 2025
Santiago Paternain, Luiz Chamon, Miguel Calvo-Fullana, and Alejandro Ribeiro. Constrained Re- inforcement Learning Has Zero Duality Gap. In Advances in Neural Information Processing Systems, 2019.
Santiago Paternain, Miguel Calvo-Fullana, Luiz FO Chamon, and Alejandro Ribeiro. Safe Policies for Reinforcement Learning via Primal-Dusl Methods. IEEE Transactions on Automatic Control, 68(3):131 2022.
Matteo Pirotta, Marcello Restelli, Alessio Pecorino, and Daniele Calandriello. Safe Policy Iteration. In International Conference on Machine Learning, 2013.
Hamed Rahimian and Sanjay Mehrotra. Distributionally Robust Optimization: Review. arXiv preprint N.Xi::/908.05659, 2019.
R Tyrrell Rockafellar and Roger J-B Wets. Variational Analysis, volume 317. Springer Science & Business Media, 2009.
Reazul Hasan Russel, Mouhacine Benosman, and Jeroen Van Baar. Robust Constrained-
MDPs: Soft-Constrained Robust Policy Optimization under Model Uncertainty, arXiv preprint arxiv:2010.04870, 2020.
Maurice Sion. On General Minimax Theorems. Pacific Journal of Mathematics, 8(1):11 176, 1958.
Oswin So and Chuchu Fan. Solving Stabilize-Avoic Optimal Control via Epigraph Form and Deep Reinforcement Learning. Proceedings of Robotics: Science and Systems, 2023.
Oswin So, Cheng Ge, and Chuchu Fan, Solving Minimum-Cost Reach Avoid using Reinforcement Learning. In Advances in Neural Information Processing Systems, 2024.
Zhongchang Sun, Sihong He, Fei Miao, and Shaofeng Zou. Constrained Reinforcement Learning Under Model Mismatch. arXiv preprint arXiv:2405.01327 2024.
Chen Tessler, Daniel J Mankowitz, and Shie Mannor. Reward Constrained Policy Optimization. In International Conference on Learning Representations, 2018
Qiuhao Wang, Chin Pang Ho, and Marek Petrik. Policy Gradient in Robust MDPs with Global Convergence Guarantee. In International Conference on Machine Learning, 2023.
Yue Wang and Shaofeng Zou. Online Robust Reinforcement Learning with Model Uncertainty. In Advances in Neural Information Processing Systems, 2021.
Yue Wang and Shaofeng Zou. Policy Gradient Method for Robust Reinforcement Learning. In International Conference on Machine Learning, 2022.
Yue Wang, Fei Miao, and Shaofeng Zou. Robust Constrained Reinforcement Learning. arXiv preprint arXiv:2209.066 06866, 2022.
Honghao Wei, Xin Liu, and Lei Ying. Provably-Efficient Model-Free Algorithm for Constrained Markov Decision Processes. arXiv preprint arXiv:2106.01577, 2021
Wolfram Wiesemann, Daniel Kuhn, and Berç Rustem. Robust Markov Decision Processes. Mathe- matics of Operations Research, 38(1):153-183 2013.
Wenhao Yang. Liangyu Zhang, and Zhihua Zhang. Toward Theoretical Understandings of Robust Markov Decision Processes: Sample Complexity and Asymptotics. The Annals of Statistics, 50 (6):3223-3248, 2022.
Wenhao Yang, Han Wang. Tadashi Kozuno, Scott M Jordan, and Zhihua Zhang. Robust Markov Decision Processes without Model Estimation. arXiv preprint arXiv:2302.01244 2023.
Donghao Ying, Yuhao Ding, and Javad Lavaei. A Dual Approach Constrained Markov Decision Processes with Entropy Regularization. International Conference on Artificial Intelligence and Statisties, 2022.
14

---

Published as a conference paper at ICLR 2025
Tom Zahavy, Brendan O'Donoghue, Guillaume Desjardins, and Satinder Singh. Reward is Enough for Convex MDPs. In Advances in Neural Information Processing Systems, 2021.
George Zames. Feedback and Optimal Sensitivity: Model Reference Transformations, Multiplica- tive Seminorms, and Approximate Inverses. IEEE Transactions on Automatic Control, 26(2):
301-320, 1981.
Zhengfei Zhang. Kishan Panaganti, Laixi Shi, Yanan Sui, Adam Wierman, and Yisong Yue. Dis- tributionally Robust Constrained Reinforcement Learning under Strong Duality, arXiv preprint arXiv:2406.1577 15788, 2024.
Liyua Zheng and Lillian Ratliff. Constrained Upper Confidence Reinforcement Learning. In Learning for Dynamics and Control, 2020.
15

---

Contents
Introduction
2
Preliminary
2.1
Constrained Markov Decision Process
2.2
Policy and Value Functions)
2.3
Robust Constrained Markov Decision Process
3
Challenges of Lagrangian Formulation
Epigraph Form of RCMDP
5
EpiRC-PGS Algorithm
5.1
Bisection Search with mil Asn (m) Subroutine
5.2
Subroutine Algorithm to Solve millen As, (TT
5.3
Combining Bisection Search with the Policy Gradient Subroutine
6
Experiments
Conclusion and Limitations
10
Additional Related Work
17
A.I
Constrained Markov Decision Processes
17
Robust Markov Decision Processes)
18
A.3 Robust Constrained Markov Decision Processes
18
A.4 Notes on the Policy-Mixing Technique
19
Discussion on Single-Loop Algorithm
20
Uncertainty Sets and Algorithms for Ab, and Subgradient Evaluators
20
Finite Uncertainty Set
(s, reectacccaa KL Uncertainty Set
21
D Experiment Details
23
Additional definitions
23
Useful Lemmas
24
Proof of Theorem
28
Missing Proofs
30
Proof of Lemma
30
H.2
Proof of Theorem
30
H.3
Proof of Lemmal
H.4
Proof of Theorem
31
H.5
Proof of T'heorem
32
H.6
Proof of Theorem
34
16

---

Published as a conference paper at ICLR 2025
A ADDITIONAL RELATED WORK
This section reviews existing approaches for CMDPs (Appendix A.I). RMDPs (Appendix A.2 and RCMDPs (Appendix A.3)). It also highlights their inherent limitations and the challenges they face when applied to RCMDPs.
A.1 CONSTRAINED MARKOV DECISION PROCESSES
CMDP is a specific subclass of RCMDP where the uncertainty set consists of single element, i.e., U (P). This section describes the primary approaches the CMDP problem: the linear programming (LP) approach, the Lagrangian approach, and the epigraph approach.
Linear programming approach. The L. approach has been extensively studied in the theoretical literature (Efroni et al. 2020; Liu et al. 2021 Bura et al. 2022: ZosanzadeZonuzzy et al., [202]] Zheng& & Ratlifi 2020). Although it is a fundamental method in CMDP, is less popular in practice
due to its difficulty in scaling to high-dimensional problem settings, such as those encountered in deep RL. Additionally, incorporating environmental uncertainty into the LP approach for CMDPs is challenging. The LP approach utilizes the fact that the return minimization problem of an MDP can be formulated as a convex optimization problem with respect to the occupancy measure (Altman) 1999 Nachum & Dai, 2020). However, RMDPs do not permit convex formulation in terms of occupancy measures (yynnaar 2005| Grand-Clément & Petrik 2024). While Grand-Clément &
Petrik (2024) recently introduced convex optimization approach for RMDPs, their formulation is convex for the transformed objective value function, not for the occupancy measure, making challenging incorporate constraints as seen in RCMDPs.
Lagrangian approach. The Lagrangian approach is perhaps the most popular approach to CMDPs both in theory (Ding et al., 2020 Wei et al. 2021 Hasanzade/onuzzy et al. 2021 Kitamura
ct al. 2024) and practice (Achiam et al. 2017 Tessler et al. 2018 Wang et al. al. 2002 Le ct al. 2019
Russel et al. 2020). This popularity stems from its compatibility with policy gradient methods, making it readily extendable to deep RL. The Lagrangian approach benefits from the strong duality in CMDPs. When U consists of single element, it is well established that strong duality holds, meaning that L = J" holds, where L* is from Equation (3) and J is from Equation (Altman
1999 Paternain al. 2019 2022).
The challenge with the Lagrangian method is the identification of an optimal policy. Even if Equa- tion (3) is solved, there's no guarantee that the solution to the inner minimization problem will repre- sent an optimal policy. In some CMDPs, where feasible policies in 1l must be stochastic (Altman) 1999.. the inner minimization may yield a deterministic solution that is infeasible. (Zahavy et al. (2021 Miryoosefi et al. (2019); Chen et al. (202]) Li et al. (2024); [Lu et al. (02T) addressed this challenge by averaging policies (or occupancy measures) obtained during the optimization process. However, policy averaging can be impractical for large-scale algorithms (e.g., deep RL) because necessitates storing all past policies, which is often infeasible. On the other hand, |Ying et al.) (2022) ; Ding et al. (2024); Müller et al. (2024); Kitamura et al. (2024) tackled the issue by introduc- ing entropy regularization into the objective return. However, the regularization can lead to biased solutions and result in policy design that may deviate from what is intended by the cost function.
In contrast, EpiRC PGS requires neither policy averaging nor regularization, thereby offering advantageous properties even in CMDP settings.
Epigraph approach. Few studies have investigated the epigraph form in the CMDP setting. So & Fan (203)) proposed a deep RL. algorithm aimed at system stabilization under constraints, and So et al. (2024) developed a deep RL algorithm for goal-reaching tasks with risk-avoidance con- straints. Although these studies empirically demonstrated the effectiveness of the epigraph form in constrained RL problems, they did not establish theoretical guarantees, such as global convergence. On the other hand, this paper is the first work to provide theoretical guarantees for the epigraph form in CMDPs. Furthermore, unlike existing constrained RL studies, we consider not only constraints but also the robustness against the transition kernel.
17

---

Published as a conference paper at ICLR 2025
A.2 ROBUST MARKOV DECISION PROCESSES
RMDP is a specific subclass of RCMDP where there are no constraints, i... N = O. RMDP is crucial research area for the practical success of RL applications, where the environmental mismatch between the training phase and the testing phase is almost unavoidable. Without robust policy design, even a small mismatch can lead to poor performance of the trained policy in the
testing phase (Li et al. 2022 Jiang 2018).
Dynamic programming approach. Since the seminal work by Lyengar (2005) numerous
studies have explored dynamic programming (DP) approaches for RMDPs (Nilim & El Ghaoui
2005 Clavier et al.] 2023, Panaganti & Kalathil 2022. Mai & Jaillen 2021| Grrand-Clément &
Kroer 2021 Derman al. [021] Wang & Zou 2021 Kumar et al.] 2022 Yang al.) 2023)-
The DP approach decomposes the original problem into smaller sub-problems using Bellman's s
principle of optimality (Bellman et al., 1957). To apply this principle, DP approaches enforce
rectangularity on the uncertainty set, which assumes independent worst-case transitions at each state or acaten pair. However, as pointed out by Goyal assumption can result in very conservative optimal policy. Moreover, applying DP to constrained settings challenging since CMDPs typically do not satisfy the principle of optimality (Haviv) 1996). Although several studies have attempted to apply DP to CMDPs, they face issues such as excessive memory consumption, due to the use of non non-stationary policy classes, or are restricted to deterministic policy classes (Chang 2023 Chen & Blankenship
Grand-Clement (2023), the rectangularity
2004 Chen & Feinberg 2006).
Epigraph application to DP approach. Chen et al. (2019); Wiesemann et al. (2013): Ho et al. (202I) employed the epigraph form to implement a robust DP algorithm for the s-rectangular uncer- lainty set setting. Specifically, they showed that the s-rectangular robust Bellman operator, which the s-rectangular counterpart of Equation (19), can be efficiently implemented using the epigraph form. However, since their algorithms rely on Bellman's 's principle of optimality, similar to standard DP, they are likely to encounter the same challenges in CMDP settings as those discussed above.
Policy gradient approach. Another promising approach for RMDPs is the policy gradient method. Similar to the DP approach, most existing policy gradient algorithms also work only under the rectangularity assumption (Kumar et al.) [024 Wang & Zou| 2022 Li al. [0022), and thus suf- fer from the same conservativeness issue. It is important to note that robust policy evaluation can be ha-hard without any structural assumptions on the uncertainty set (Wiesemann al. 2013), but such assumptions are potentially not required for the robust policy optimization step. Our policy gradient algorithm abstracts the evaluation step by Assumption [ and avoids the need for the rectangularity assumption during the policy optimization phase, similar to the recent work by Wang et al. (2023).
A.3 ROBUST CONSTRAINED MARKOV DECISION PROCESSES
Russel et al. (2020); Mankowitz et al. 2020) proposed heuristic algorithms for RCMDPs, but their approaches lack theoretical guarantees for convergence near-optimal policy. Wang et al. (2022) introduced a Lagrangian approach with convergence guarantee to stationary point. However, they do not ensure the optimality of this stationary point. Moreover, their method is heavily dependent
on the restrictive R-contamination set assumption (Du et al. 2018 Wang & Zou 2021 2022).
Sun et al.] (2024) applied a trust-region method to RCMDPs. The policy is updated to remain sufficiently similar to the previous one, ensuring that performance and constraint adherence do not degrade, even in the face of environmental uncertainty. However, while they ensure that each policy update step maintains performance, convergence to near-optimal policy is not guaranteed.
Ghosh (024) employed penalty approach which considers the optimization problem of the form min, f (T) A maxx((()) 0}. where f and h are defined in Section [ While this approach can yield a near-optimal policy for a sufficiently large value of À > 0, the author does not provide a concrete optimization method for the minimization and instead assumes the availability of an oracle to solve it. As we demonstrate in Section 3 this minimization is intrinsically difficult, making it challenging to implement such oracle.
Finally, Zhang et al. (2024) tackled RCMDPs using the maxicy-mixing technique (Mryyoseeii et al.
2019 Le al. 2019). In this technique, a policy is sampled from finite set of deterministie policies
18

---

Published as a conference paper at ICLR 2025
according sampling distribution at the start of each episode, and it remains fixed throughout the episode. However, even a good sampling distribution is determined, there is no guarantee that the resulting expected policy will be optimal due to the non-convexity of the return function with respect to policies (Agarwal et al. 2021). We discuss the limitations of the policy-mixing technique in Appendix [A.4] Additionally, Zhang al.] (2024) assume R-contamination uncertainty set, limiting its applicability similarly to the work of Wang et al. (2022).
Although the RCMDP problem remains unsolved, the control theory community has long studied the computation of safe controllers under environmental uncertainties. Notable methods include robust model predictive control (Bemporad & Morari 2007) and Ho optimal control (Anderson et all][[201 [2019] Zames] 1981 Doyle 1982). These approaches are specifically tailored for specialized class of MDPs, known as the linear quadratic regulator (I.QR, [u al. (202T)) However, because IQR and tabular MDPs operate within distinct frameworks, these control methods are unsuitable for tabular RCMDPs. Given that most modern RI algorithms, such as DQN (Mnih et al., (015), are based on the tabular MDP framework, our results bridge the gap between the RL and control theory communities, laying the foundation for the development of reliable RL applications in the future.
A.4 NOTES ON THE POLICY-MIXING TECHNIQUE
This section explains the theoretical limitations of the policy-mixing technique (Zhang al. 2024
Miryoosefi et al. 2019 Le et al. 2019) for identifying a near-optimal policy.
Policy-mixing technique. Let πT == {m...... nm } be finite set of policies with m E N. Con- sider a non-robust, single-constraint CMDP (S,A,7,,,P P.C = {co, (c,,,.),, Given a distribution P E g 11 define
Jen p(p)= P(T)))),,P())) and Je, Ep(T)Je.P(t)) mEnl
REN
The policy-mixing technique considers the following optimization problem:
J = min
P(p) such that Jep,((p) S bi
(14)
(E)
min ( AER
max
((s X(Jo,, b1)) min max L(p, A) (n) AER-
*eil
Let p" be the solution of Equation (14) such that p² E arg min Pf maxXER, T(p, A).
In this setting, policy is sampled from p at the start of each episode and remains fixed throughout the episode. The term (p) represents the expected return under the distribution p. Since (p,,A) A) is convex in p and concave in X, under some mild assumptions, Equation (14 can be
solved efficiently by the following standard optimization procedure for min-max problems: At each iteration I, with initial values (0) E R4 and p()) E P 11
1. Update (4) using a no-regret algorithm. For example, with gradient ascent and a learning rate > 0:
(() max (e-1) a (JaJ b1) b1).03.
2. Update (( as (T) 1 n ((()) where
(t) E arg min Jon. P(T) + (Jo, -b)) =
Then, the averaged distribution p(T) = IT (()) converges to p" as T - oo (Aeernethy &
Wang 2017 Zahavy et al. 2021). When II is sufficiently large, we can expect that the optimal value of Equation (14) is equivalent to that of the CMDP problem, i.., J = Jj, where J" is
defined in Equation with 24 = (P).
19

---

Published as a conference paper at ICLR 2025
Limitation of policy-mixing. Even when J J", it crucial to note that, while p( converges
p², there is no guarantee that (()) Σ (2) will converge to n².
Zhang al. (2024) Miryoosefi et al. (2019); Le al. 2019 argued for the convergence of (1) by asserting that the equality (a) in the following equation holds:
Let X = +
Ei=o A())
r
T
L (
10000 200
Σ
(x) + 2 (()))( -b1) -i))
T
= T
(15)
Jen P(F + (T)) Jes Jey,
b1) -11)
(see, for example, Equation (14) Zhang al. around Equation (13) in Miryoosefi et al. (2019)).
2024). Equation (1) in Le et al. (2019), and
However, (a) in Equation 15) does not hold in general because the return function is neither convex nor concave in policy. Even when T = 2, there is an example where Equation (15) fails (see Proof of Lemma 3.1 igarwal al. (02IT)) This invalidates the results Miryoosefi et al. (2019); Le al. (2019); Zhang et al. 2024), thus illustrating the theoretical limitations of the policy-mixing approach for near-optimal policy identification.
B DISCUSSION ON SINGLE-LOOP ALGORITHM
Although Algorithm can identify a near-optimal policy, uses double-loop structure that repetitively solves ein (T)) by Algorithm 2 In practice, single-loop algorithms, such as primal-dual algorithms for CMDPs Efroni et al. (2020); Ding et al. (2024)). are typically more efficient and preferable compared double-loop algorithmss. This section discusses the challenge of designing a single-loop algorithm for the epigraph form.
Since the epigraph form is constrained optimization problem, can further transform it using Lagrangian multiplier E RR,, yielding:
J min max Tepi A) where Lepi(ho, A) bn AA bo XER
(16)
Similar to the typical Lagrangian approach, let's swap the min-max order. We call the resulting formulation the "epigraph-Lagrange" formulation:
(Epigraph-Lagrange) Lepi
max min min by + (T).
(17)
AER, H FEll
Does the strong duality, J Lepi hold? If does, we could design a single-loop algorithm similar to primal-dual CMDP algorithms, performing gradient ascent and descent on Equation [1 Unfortunately, proving the strong duality is challenging.
Essentially, the min-max can be swapped when Lepi(bo:)) in Equation (6] is quasiconvex- quasiconcave (Sion 1958). While Lepi(bo, A) is clearly concave X, the quasiconvexity in by is not obvious. Although 4h, is decreasing due to Lemma] 2 and thus a quasi-convex function, there no guarantee on the guasi-convexity
by + -AA The situation would be resolved if A were convex 6y. However, since A eil As, (Tr) is a pointwise minimum and As, (T) may not be convex in (Agarwal et al. 2021 A may not be convex in bo (Boyd & Vandenberghe 2004).
Therefore, algorithms for the epigraph-Lagrange formulation face a problem similar to the " solution challenge of the Lagrangian formulation (Section 3). Proving strong duality finding alternative ways to circumvent this challenge is a promising direction for future RCMDP research.
C UNCERTAINTY SETS AND ALGORITHMS FOR ATD AND SUBGRADIENT EVALUATORS
This section provides examples of uncertainty set structures and algorithms that realize Jn in Assumption and J in Assumption 3 Jn evaluates (T), and j evaluates of the
20

---

Published as a conference paper at ICLR 2025
Algorithm 3 Evaluators for Finite Uncertainty Set
1: Input: Policy и, uncertainty set L
Pas) .P......
and index [0. N].
2: for m E [1,M]] M] do
3: Qe Pon,Pm
pm
(P E ERSA
4: Jen.Pm (TT)
( Pm (s,a)
5: end for
6: Let m E: arg mE Pen,Pn
7: dp... = -1- () - -11 Pm=) R$
8: return (for Jn): Pmn .m. (TT)
9: return (for ): Hdp (8)Qr, Pm (s,a) ((s,
elements in 0Je, u (T)) In this section, frequently the following useful matrix formulations Pirrotta et al. 2013) for cost TRS.A.
Q2, (I -PII") R
Jo (e)((T)
Σ ( ER
(18)
(x.0)E5xA
dp - -1-
where 7 is an identity matrix and 11 is (X(XxAA) matrix such that II (s. a)) ((, Due to Lemma an element in aJe, u takes the form of:
(V)e,,
p(s AS
C.I FINITE UNCERTAINTY SET
Let U be finite uncertainty such that 21 = (P).... Pm3 where M E N. U clearly satisfies A Assumption 2 The implementation of Jn is trivial by Equation (18). The implementation of J is also straightforward due to Lemma I0 Specifically, it can be implemented by the following subgradient representation:
ÖJe, = conv (m) m E arg max Jen, Pm (TT) } mE[I.M]
Algorithm Algorithm summarizes the implementions of J, and Já. Our experiment (a) in Section 6
C.2 (s, RECAANGUAL KL UNCERTAINTY SET
(s, a) rectangularrt
An uncertainty set is called (s, reretaaggull it satisfies:
= X Us, where Usa S ((S).
For such (s, a) rectanguul uncertainty sets, the following robust DP update is widely-used approach to compute the worst-case Q-function:
(Robust DP)
(((+1) (s. a) = cn(ss + max Ep(s')V(''))
pEld.. YeS
(19)
where co
(5) = Σ T(s d' ( (s.a').
d'EA
By repeatedly applying Equation
19
Q
converges linearly to Q where
Cn
Pa arg maxxeu Je,, ((T) (see, e.g., Corollary 2 in Iyengar (2005)).
21

---

Published as a conference paper at ICLR 2025
Algorithm 4 Evaluators for KL Uncertainty Set
1: Input: Policy nI, nominal transition kernel P, regularization parameter CkL 0, and index
n E N].
2: Repeat Equation 25 and compute its fixed point Q
3: PR(.1 (,,)) P(- a) exp V (+)/CKT)
// Compute the worst-case environment
4: O Qon,p = (1 - (1 E IA
5: (T) = [()))==()))A (s) P. (s,a)
6: d:: (1- -I1 p-i) ERS
7: return (for Jn): Je,,
8: return (for Jo: Hd (8)Qz r., p (8,a) (5,
Once we have Q Px. thanks to the rectangularity, the worst-case environment can be computed by:
Px 8) arg Σ (x(d')E..p:;;)) V(s,a) 68x
(20)
pells,o s'ES
KL uncertainty set. Both Equation (9 and Equation 200 require an efficient computation of maxpeu... (p, v) for some vector IR RR.SThh The KI. uncertainty set one of the most popular choices,
as it allows for efficient computation of this maximization (Iyengar 2005 Yang et al. 2022).
For some positive constant CKI. > 0, if Us satisfies
Ua (p E (S) KT P(- 8, a)) s OKL)
we call U a (s, .e-recanng KL uncertainty set. Here, KL E.es p(s) In p(s) q(a) denotes the KL divergence between E (S) and (SS). Due to Lemma I this U clearly satisfies Assumption
The following lemma is useful for implementing the robust DP update with a KL uncertainty set. Lemma 4 (Lemma in Iyengar 2005)). Let E I and 0 < E (S)). The value of the optimization problem:
min (p,0) v) such that KL[p g1 Ckt. (E))(S)
(21)
equal
min 0- CKI. + Oln exp (xx((-)) 820
(22)
Let 6* be the solution of Equation
Then, the solution of Equation
is
p x q exxp
0-
Using this lemma, Equation 19 can be implemented by
(1t+1)
(s. a) (s(sa) + Σ
Pr
S'SS
vill(()
where Pa & P(. 8, exp
0+
(23)
v:(0 (.)
and 0r = arg min 0 CKL + Aln A20
P(. P(-1s,a),es)
exp
is a convex optimization problem. solving for Regularized alternative. While Equation (22
all P(: 8, a) E S A in Equation 23 computationally extensive in practice.
22

---

Published as a conference paper at ICLR 2025
Rather than the exact constrained problem of Equation 21 following regularized robust DP update:
Yang et al. (2023) proposed the
Qen (s) a)) +
Σ (()))
Ck., KLkpKL/p|IP 8 s.
(24)
PE (E))(S) s'ES
where OKT. is constant. This regularized form has the following efficient analytical solution:
( = (x +
Σ
( (s')
Pr
dEES
(25)
where Ps 6,0 x s(.1s,a) exp
CKL
While this is regularized approximation, the following lemma shows that Equation 25 some exact robust DP with a KL uncertainty set:
solves
Lemma 5 (Adaptation of Proposition 3.1 and Theorem 3.1 in Yang et al. 2023) For any O'KL. > 0. there exists CRT.
such that Equation (24 converges linearly the fixed point of
Equation 23
Algorithm summarizes the regularized DP update to implement the algorithms. Our experiment (b) Section uses Algorithm
D EXPERIMENT DETAILS
The source code for the experiment is available htttpss//gichab..cmmmmmstssoouu RCMDP-E53 -Epigraph
Environment construction. For the settings with finite uncertainty sets (a), the parameters are set as $ = 7, A = 4, 7 0.995. We set = 0.99 for the CMDP setting (c). For the setting with KL uncertainty set (b), we set S 5, = 3, and y 0.99.
For the policy gradient subroutine (Algorithm 2) we set the iter- ation length 7' and the learning rate to ensure that Assumption 4 is satisfied with sufficiently small copt. Specifically, for (a) and (c), we set the iteration length to T 10 and the learning rate to a = x 50 For (b), we set T 10 and a = 5 x 10-1
PBARC--PGSimpllmeee
Notably, parameter tuning for DorppiCC-PP a should meet the conditions of Assumption 4 Since the initial policy in Algorithm[2 can be chosen arbitrarily, the (k: 1) policy from the outer loop is used the initial policy for the k-th policy computation.
straightforward, any sufficiently large 7 and small
For the finite uncertainty set settings (a) and (c), we implement the evaluators J, and J using Algorithm For the KL uncertainty set setting (b), implement Jn, and J using Algorithm with CKL KL 2.0.
LF implementation.
The pseudocode for LF is shown in Algorithm 5 We set the iteration length and learning rate for the inner policy optimization to 10a and Or 10-5 (a, c), and T 103 and ax 5 x 10-4 in (b). Similar to EpiRC-PCG sufficient optimization in the inner loop. We choose a = 0.01 from {0.1, 0.01, 0.001] for the outer updates, balancing between the convergence speed and performance.
these values chosen to expect
E ADDITIONAL DEFINITIONS
Throughout this section, let X' denote set such that X' Rdd with d N.
23

---

Published as a conference paper at ICLR 2025
Algorithm 5 Lagrangian Formulation Policy Gradient Search (LF)
1: Input: Outer iteration length K N, inner iteration length T E N, learning rate for Lagrangian multipliers a O, learning rate for policy Ot > 0
2: Initialize the Lagrangian multipliers (
IR
3: Set an arbitrary initial policy T(") E 11
4: for k = 0.....
K ,
do
5: Set the initial policy 7 (k,00) = (K)) for the inner loop
6: for 0,... , do
7: (R.1) ) (TT
// Compute policy gradient
8: (k,t+1) Projn (T)( (ti)
I/ Policy update
9: end for
Set the new policy: (k++)) = x(hie)) where t* E arg min Lixcss (T(hee1))))
11: Update Lagrangian multipliers: An (k+1) = max An + ax #ax(Jn((T(ht))) - -ba). for all
n E []
end for
Definition 2 (Subgradient (Kruger, 2003)). Let X IRdd be an open set where N. The set of (Fréchet) subgradients of function x - R at point X is defined as the set
f(x') f(x)
(u, x' x)
0f(x) = X
lim inf x'=00,0 tf.
|x' x:
Furthermore, if 0f(x) is singleton, its element is denoted fx(x) and called the (Fréchet) gradient of at x.
Definition 3 (Lipschitz continuity). Let 2 A function f X - R is &-Lipschitz if for any 21,22 X, we have that
(I f(x22)l I f| x22122
Definition (Smoothness). Let 2 0. A function X + I8 is t-smooth for any zı, T2 E X, have that
[[V[(z)) V 3 &f|l>1 - x2ll2-
Definition 5 (Weak convexity). Let l > 0. function f - IR is l-weakly convex if for any g E Ox() and x, X.
1
f(x') - f(x) lg. -x)
x12
Note that f(x) + 111=11/2 is convex in X' if and only if f &-weakly convex.
Definition 6 (Moreau envelope of a weakly convex function). Given a é-weakly convex function X + and parameter < t- the Moreau envelope function of f given by M, f Rdd R such that
(M, o f)(z) = min f(x')+ + 2r
1| x' 2'12
r'e
F USEFUL LEMMAS
Throughout this section, X' denotes compact set such that X Rd, where N.
Lemma (Lemma D.2. in Wang al. 2023) Let & and X IR. be E-smooth function. Then, is a t-weakly convex function.
Lemma 7 (c.g.. Proposition 13.37 in Rockafellar & Wets (009)). Let f x X x R be an l-weakly convex function, and let 0 < < E be parameter. The Moreau envelope function M, f Rd -> is differentiable, and its gradient is given by
1(x V(M, f)(() - 7
arg min E'
f(x')
||x x' x'112)
2T
24

---

Published as a conference paper at ICLR 2025
Lemma 8 (Sion's minimax theorem (Sion set and y C _ convex set. Suppose that f x y + R satisfies the following two properties:
1958 Let m N. Let C CR" be compact convex
(a.-) upper semicontinuous and quasi-concave on y for any a E X.
. {()y) is lower semicontinuous and quasi-conver on X for any E y
Then, mingex SupyEy (ar,u) = suP mingex J J'(r,y).
Lemma 9 (e.g.. Problem 9.13, Page 99 in Clarke et al. 2008)), Let V Rn be a compact and f Rd x y + be a continuous function of two arguments. Consider a point 5 E and let (T)) IRd be its neighborhood. For any (x. v) ((F) x suppose that the gradient V (2, y) exists and is jointly continuous.
Let h())= maxyey J ( y). Then, the subgradient of h is given
ah(z) conv V (..
arg max f(z, f(2,8)
NEY
Lemma 10. Let N E N. Let fo X + for E [1, be t-weakly convex functions for some i 2 O. Define the pointwise maximum function f f: X R as
f(x)
(N(())))))))))) VeEX.
Then, for any X,
0f(x) = conv E l
= =
Proof. The claim directly follows from Theorem 1.3 and Theorem 1.5 in Mikhalevich et al. 2024).
Lemma 11 (Maximum difference inequality). Let N E N. For two sets of real numbers {z, {21)se[1. and (yeNeeLNN where Ii, y) R.
max 2, max yr S max [E[L.N] SELLNN
[z - yk
iE[L.]]
Proof. For any [].
max T; = max 2; y: + 9: S max (x; vi) max y/ []] iE[L,N]
[E[L,N]
max H max yo < max 24 34
[E PE[LN]
se [[.N]]
By the symmetry of r; and yi we have max E| Be S max Bi Z4.
Therefore,
max 2, max y/ < max [ - 3vl
[E[L.]] SE[LNN]
Lemma 12 (Point-wise maximum preserves weak convexity). Let X R and f X' - be ln- and l-weakly convex functions, respectively. Then, g X R defined by g(x)
max(h(z), f(x) for any x E X is t-weakly convex, where == ma,
Proof. By the definition of weak convexity, for any 0 E [0, 1] and xr XX
h(Ox + (1 - 0)y) + Ln 0x + 0)vl13 - 0 [(xx) + ln |0:1 + - 0)
-))((()) ((()) + En - 111
25

---

Published as a conference paper at ICLR 2025
A similar inequality holds for f. Then,
L g(Ox + (1 - (1-))y) + 2 10 + (1 - 0)yl
-max(h(Ox (1 f)y), f0x + (1- 0))) _
= =110x + (1 8)yl12
maxx 1(0x + (1 0)n) + 2 10 + (1 - 0) 1(0x + (1 -0))) + 2 10r + (1 - -0yy11
I max 0h((a) + (1 0)h(y) + L (011=11 + (1 8) || 11 0f(z))) + (1 0)f(y) + 2/2 (011011 + (1 (1- (o)]))1((1)) }
e
-max(Oh(x) + (1 0) (f()) (1- 0))(})) + o |1 (1 0) (wl12)
(axx( + e
2 [1:113] + (1 - 0) max
(h(v), max(((()) f(v) + l |01
-0 g(()) + = + + - 0) g(v) + 2 (1lv18
Therefore, 9 is E-wekkly convex.
Lemma 13. Let (x( be the normal cone of X at x E X, defined as
Nx(x)= = {o E TRd (g. S ()
Vy E).
Define the indicator functionn Ix : R - R such that
Lx(x) 50
fIEX otherwise
8o
Then, 0x((x) (x(x)) any X
Proof. Note that any g E xx)) satisfies
Ix(v) 2 (x(x)+ (g.y x) Vy E RR.
(26)
Suppose that g & Nx(a)). Then, there exists s/ E X' such that (g, x) < (g. v'), which contradicts Equation (6)). Therefore, g E (x) for any g E (1x(x) and thus 0xx(x) C (x)x).
Consider g Nx(z). It satisfies 0 2 (g, y x) for any X. Since x E X and by the definition of 1xx. Equation (26 holds for any y E RRd Therefore, Nx(x)) S. xxx(x)). This concludes the proof.
Lemma 14. Let h: X + R be an l-weakly convex function. For ForO<T= < 1/e, define
Dr arg mig h(x')) 2T 211x x² x'1122
s'EX
Then, there exists subgradient g E Ōh(ī,) such that, for any y E X.
(g. J. - y) < (V(M, o hx)x), Jn - y)
Proof. Let f Rd + TR. be function such that f(x) h(x) (x))
The Moreau envelope function of f satisfies that, for any x E R.d
(M, o f))z)
min z'ERd
h(x²) + =x(xx') +
1 1I x' 12
min x' Ex
h(z')
x 112
27
2T
holds that V(M, fx) = (x - due Lemma 7
Note that
1
xz arg hon'mn()) +
|x x 2²112 arg min argmin Ex(x') (x')+ + 11 x/
x'EX
2r
8'E34
2T
26

---

Published as a conference paper at ICLR 2025
It is clear that Σ, is minimizer of the function oz h(x') + Ix(x') + 2 +11 x' 112 Therefore, holds that 0 (T,( Accordingly,
0 a h(v) ((1))++ + Ix(v)) + 2r
| - v11
-x+ (T+ (T+- a(h(v) + +x((v))) y=
-
y=Ir
Due to Lemma 13 Hl (2)) Nx Therefore, there exists subgradient, g E @h(x;) such that
TT -x) E Nx(T,).
Since any E (2,) satisfies (2. - ΣT) 50 for any E N. it holds that
(-9.V-E)) ( (I+ (I+ -8--)) 2) - Dr Vy E.
1
Then the claim follows from the fact that + (x- [+)= V(M, (x) due Lemma
Lemma 15 (Linear optimization on convex hull), Given e E IRd and a compact set X' C Rd, holds that
min x) = min (c, x) TE
=
Proof. Let x² E arg gin (X} (c,2). The claim holds for x² E N. Suppose that x² & X.
Then, by the definition of the convex hull, there exist y, E X and 0 e (0, 1) such that # and
x = By + (1 2)2.
Since x* minimizer, we have
(c,x*) (c. v) and (c. x*) S (c,
Accordingly,
(c,x²) = 0(c, x²) + (1 ()(,, S f(c, y) + ()( 2) = (c,xx))
The inequality must be an equality, and thus
(c. v) (c, +(1 0) ((c, (c, 0.
20
Since 0 E (0, 1), it holds that
(c (c, 2) (c,x))
The above equality means that both y and X satisfy (c. (c,2) min m (2) (c, x)) Therefore, min (c, minggecovv( (x) (c.
Lemma 16 (Lemma 3.1 in Wang et al. (023 ) Let
h HAVA and 6m = 2yA
For any n. x
{(), p E (S), and e E 1]sA
[Je,((T) J,, < 4pp1 x' 2'112 ( (Jr,,( -V.r()))Va.r(()).. s Eaaul x'1l and (Jeu(T) Je, (T) < 4 <' 1|
Furthermore, ( lam -weakly convex in as follows directly from Lemma 6
Lemma 17 (e.g., Lemma 4.1 in Agarwal et al. (2021) and Lemma E.2 in Wang al. (2023) Let
E (S) such that minses u(8) O. For any क E IT, P S x A T (S), and c E 0, 154
dp
Je,p(T) - Je, < H
max (TT - n', V.e,P(TT) x'ell
11
where tt. E arg min Jzr'(
27

---

Published as a conference paper at ICLR 2025
G PROOF OF THEOREM
Proof Theorem 7 Consider the deterministic RCMDP shown in Figure Ta with N = 1, (Pl P2). S {81, 52, $3,
83, 84), and A {ai, 02). Set the initial distribution such that p(s1) = p(82) = =x(53) = ((44) = 1/4.
First part of Theorem We set
The threshold b can be arbitrary.
Let and be two policies such that 2 always chooses and 22 always chooses in any state. For any 0, we will show two results:
Equation 28 Lx(x2) min Lx(T) 2 Hy 3H6
Equation 30
(VLx(==)((. (2L)( a2).
The former demonstrates the suboptimality of π2. while the latter shows that choosing d2 always decreases Lx, indicating that T2 local minimum.
According to the RCMDP construction, for any E II, we have
H (1 +
v(ss)),,,) (s3) + p(s1) (51)
H (1 7),
((ss) (sa) + vo..) (84)
H (1 7),
((ss) (53) + (sa)
p, (8) = H (1 +1))
((s3) P. (8s) (($4) o,
For Tı and n2, it is easy to verify that
H
((s)) p. (s1) p(s2) p. (s2) (8 + y 726 +..))++.++) + (1 78 + +
(1 (1+8),
4
4
4
H
6
u(si)) 20. (51) ((52 V (82) 7 (6 + 7 + 72 + +...) +
72 +...)
11+))
(82) H
H
((s1) (s1) (1 82) V
(81) (182) P. (82)
2
((si) (s1) (152) C.P. (52) H
H
|l ((s (8)) (s3))V2..,
2
!!
u(s:) (ii) + 11 82) V (82)
(1 26).
((S1) (51) + (1 1T n.P.
(82) (1+7-1 20)
Therefore,
Jon (Ti) = + (7 8) Jc..P,(T)) = H
H H
2 +
2
4
H
H.
Jo = - (3 - 7),, (o.A(()) = (3 + 77)
4
4
(27)
H
H
Jo (Tz2 = (3 +7),
(12)).(T2) = (3 7),
4
4
11 HБ
11
H7
H6
(g.A(ma))
+
2
2
Hence,
Hy
HÒ
Jo1)((m1) = Jeg.13 (m))
+
+
Ja = Jo (TI) = (3 + +7),
2
4
4
4
H
H
H6
(T2) -ea..y (T2)
(3 +
Je)u((2)) = Je..))(T2) =
+
4
2
2
2
28

---

Published as a conference paper at ICLR 2025
Accordingly, since À 1, we have
Hh 3H8
(22 min (T(T) T2(TT)) [x(TT) 2
(28)
well
4
The next task is to show that (VIx(=2));; (VIx(T2)),,,2))
By using Lemma 10 it is easy to show that
(L2(T2) = Ve (T2) + V.
Since dp. dp 0.251 and due to Lemma we have
( = 2 + + H
Note that
4 (VLx(Te))ss),
Qa,n, (1), (1) + TT ($1 (6 Hy) (H H)8),
4
[VLx(Ty))(1 = P 81, 02) + T
($1. 02) = H + H(? 8)
H
(29)
4
H [ZLx(22)
= Q P (82, 01) + 0 (82, 01) ) = 2H
(VLx = Q P. (2, 02) + 0 ($2. 02) = 2H
H
Therefore, since 8 > 0,
(VI2(T2))(51 - (WV4 = -H76 + Hб 25 28>0,
(30)
((VLA a1) (V42()())2 216 > 0.
- Now, with a sufficiently small R > 0, let II, = e - 22l1 S R, π + n2) be policies near T2. When is sufficiently small, due to the Lipshictz continuity of ((.. by Lemma I6 Equation 27 indicates that
Jecas = Jeg. (T) and ( (3 VT E fl.
(31)
Similarly, due to Equation
31 with the Lipshictz continuity of VJar((*) by Lemma 16 Equation 29 and Equation 300 indicate that,
(VL(())((. > (VLA(T))(. VT fil.l
Therefore, since स2 always chooses dg, have LA (T²) < (T) VT ÎI for sufficiently small R > 0. The first part of the claim holds by setting 5 = 7/ with Equation (28).
Second part of Theorem of the proof with 8 = 7/4. For value by E R. define a function V,, R - IR such that
Consider again the deterministic RCMDP given the previous part
Lr, (A) min Je (TT) (Je, Ab1 min Lx(x).
We first show that, when b, ranges from 0 H, the arg supxER_ Mo (A) ranges from to 0.
Since 44 (Pr. P2). Lemma 10 and Lemma D
indicates that, for any À E R and dj IR
0* V (A) S conv(Je,.r() by H E E (2),
(32)
Since μ 1 and due to the construction of the RCMDP in Figure la it is easy to verify that,
VT 4 VT. 1
1
min min Ja,p(T) 2 min min min
xell Pell
well PEU sE (8(55.5))
H
1 (V2,,((5)) + VJ v(4))
max max Jo (TT) <
max max
wlll PEll
HEll PEÙ
29

---

Published as a conference paper at ICLR 2025
By inserting this to Equation
32 for any À E R and b1 R, we have
- b 5 H
4 bj (,,
(33)
4
Therefore,
When bi E [0,1/4),
axVo(A) must satisfy > 0 for any A. Thus, {0o} = arg supxER4 vb (A) for any bi E [0, 1/4). Moreover, supXeR+ Vo, (A) = co.
When b, E (H 1/4, H) 9 0g V, (A) must satisfy 9 0 for any X. Thus, {0} arg maxxxx., Vo, (A) for any b E (H 1 1/4, HJ. Moreover, maxXER, Va, (1) S H.
Next, we will show that there exists b such that E arg MAX b, (A). From now, we only consider sufficiently large b1 such that the value of arg ma Vo, (A) becomes finite.
Let V maxxeR, Vo (A) and S(b,) Vi - Since S(H - 1/5) 0. f(0) -0, and f(b1) ) continuous in bj, the intermediate value theorem ensures that there exists B/ E [0, H such that f(b)) 1. Moreover, the generalized mean value theorem (Theorem 2.3.7 in Clarke 1990)
states that there exists bf E [b4 H]] such that -1 f(K)) E Ōb, Vo:
Let As, be the set that provides maximums of Lb,, i.c., Ao. = arg maxAER, Vo, (A). Using Lemma 9
- 0b, Vi; = convtVo, vo, vo; (A) À E No; conv - - = max Ab;- min Aop
Since Mo, (A) is concave A, any À E [min As, max As,] provides maxiER, Vo, (A). Thus, arg max Voz (A). This proves the existence of b such that 1 mag min (x
H MISSING PROOFS
H.1 PROOF OF LEMMA 2
Proof of Lemma
2
We prove the first claim. Recall the definition of Ab;
T min As, (T) min max Je..ue(T) bn sell wE[o,N]
(34)
wlll
is easy to see that Abr (T) is monotonically decreasing in by- Consider two real numbers x S and let nh arg min,en A (T). Then,
A min A, (T) z (,(T)) < ( = min (T) = A
well
Therefore, A is monotonically decreasing in bo-
Next, we prove the second claim. Suppose that Aj. O. Then, there exists feasible policy и E IIr such that Je (x) < J Jen (T*). This contradicts the definition the optimal policy. Therefore, A 2 0.
Suppose that A). > 0. Since min A, (x) > 0, no feasible policy achieves the objective return J This also contradicts the existence of the optimal policy. Therefore, A 0.
H.2 PROOF OF THROREM 2
Proof of Theorem We first prove Equation
19 by contradiction. Let 0)} and suppose that x Since A3. 0 by Lemma there TI such that (e,
f < exists feasible policy definition of the optimal policy.
min bo [0, H]
J -Jn (T*).. This contradicts the
0 by Lemma any policy क E arg min As, (T) is feasible and satisfies Jen J The claim directly follows from the definition of optimal policy.
We then show that Equation 19 provides n². Since Aj.
30

---

Published as a conference paper at ICLR 2025
H.3 PROOF OF LEMMA
Instead of Lemma
prove the following lemma that includes Lemma
Lemma (Properties of bb)) The following properties hold any by E R.
1. (Lipschitz continuity): For any n, E 11. A (T) - Aou (T') S Eppl 4'll with
Lp == HAVA
2. (Weak convexity): Abo (TT) fam ||
2 2 convex with lam 2yAH3
3. (Subdiffrentiabilitt):: For any 11, the subgradient of Abs at π is given by
a conv (onv(V=Jee (VxJe.,P(T) N.W.
where conv B represents the convex hull set B C RSA
Proof of Lipschitz continuity.
Abu (x)
(T'))
<
max ((()) - bb,} nE[U.N]
max {Jm,eltT)) bm3 me[u.N]
(0) max Je. (e.. bn, (Jee. bn)l S lLplI x'112 nE[o.N]
where (a) uses Lemma 11 and (b) is due to Lemma 16 This concludes the proof of the Lipschitz continuity.
Proof of weak convexity. The weak convexity of Ao, (T) max (T) immediately follows from the weak convexity of (T) due to Lemma 16 with Lemma 12
Proof of subdifferentiahiiity. Suppose that U is finite The claim directly follows from Lemma 10 with the weak convexity of P(T)) due to Lemma 16
Suppose that t/ is compact set such that, for any E ((T..((T)) is continuous with respect to Puu. The envelope theorem (Lemma 9) indicates that, for any n E N].
OJe, conv V.C.. P E arg max Je,, P(T) bn PEll
Then, using Lemma 10 with the weak convexity of Jc, (T) due to Lemma 18
we have
0A (T) conv 9 9 E (J)) where arg max Jon. (x) - bn nE[o.N]
conv V Jen,
n, PE
( bn (M).))(0NN
argmax
H.4 PROOF OF THEOREM 4
Proof of Theorem
We introduce shorthands and W such that
(VJe,,((T) n. Wo, and W
arg max
Je..P(IT) by
(35)
(n,
31

---

Published as a conference paper at ICLR 2025
Let The E arg xel Abo (T)) For any II and by R, have
Abo (T) - bo (T)))
max max Jon. P(T. -bn) nE[o,N] PELl
max max Jo.. P(Tbb) bn ne[o.N] PEL
min P(T) - bn
max max Je,, (((T))) - bn ne[u.N] PEN
nnP
min (Jen, P(T)) bn) (Je..P(TTh) bn)
n.PEW
min P(T) - P(T (Tro)) n.PEW
(36)
min n.PEW
P(T)
min P(())) x'Ell
dp
H min n.PEW
max (NT n V Pc. E'lll
/
20 when is greedy to V. F
DH min max ( n', V VaJen.P(TT))
a.PEW r'ell
DH min max (T n
gE9 e'ell
where (a) uses Lemma 17
The claim holds by showing that
min max (TT x9)
min max ( x',g) geDd. (x) Well
(37)
SEV Ele
Since (g) O (T) due Lemma 18
Equation
holds when there exists
g" arg min gcoonc m x'.9 such that g E g.
Let 2* arg max min mEinggcoo (TT - g' For any g" arg min geconv max n', g). it holds that
max(T - -0'--",00 -',9") = min max (TT - ,') *'ell
gEconv(O) w'lll
max min (T - n g)
s'ell gEconv(g)
(38)
min ( =²,
gEconv (G)
min (T ,g) 9Eg
where (a) uses Sion's minimax theorem (Lemma with the convexity of II and conv and (b)
uses Lemma
Note that
(T 2-- gg) ) S max (TT x'
min
( 1---".90 2* S --- =²'g")
(39)
r'ell
g (g)
where (a) due to the third line of Equation 38
The inequality must be equality. Accordingly.
(
max Fell
n'. x'.9">
min(T ग 2" 29
9Eg
where (a) uses Equation 339 and (b) uses Equation (38). Therefore, g e G and thus Equation 37 holds. This concludes the proof.
H.S PROOF OF THBOREM 3
To facilitate the analysis with estimation error, we present slightly modified version of the epigraph form, Let E IR be admissible violation parameter. We introduce the following formulation:
(Epigraph.)
J == min bn such that At, S E (08
(40)
32

---

Published as a conference paper at ICLR 2025
Note that J is monotonically decreasing in c.
Additionally, we introduce a slightly generalized version of Theorem 2
Lemma 19. For any 81,02 2 0, if by and policy и E satisfy bn S J + + and (bo S eD. then an (51 -ottmiaa policy.
Proof. Note that (F) + directly follows from Definition 1
E1 + E2 and (n.4(=)) bn + for any n [I, The claim and the fact that J = (x="
For any by E [J2, + E2] with some E1, E2 2 0, the subroutine returns a policy = of (bb) such that
(8) min A6, (T') Copt I min A (a²) + Copt E1 + Cupt.
D 50 (T)
e'lll
n'ell
where (a) due to Assumption 4 (b) holds since Abp (T) is monotonically decreasing in by and (c)
follows from Equation (40). Consequently, by applying Lemma 19 क is (E1 + E2 + Eopt -optimal
The following intermediate lemma guarantees that the search space of Algorithm I Jlwaas contains such bg with E Eest and E = Eest. + Eops.
is run with algorithms Jn and sf that satisfy Assumptions and 4 For any k E [0, K]] (i06) ((6) n [Jz S + East Eopt. # 0.
Lemma 20. Suppose that Algorithm
Proof. The claim holds for le 0. Suppose that the claim holds for fixed k. Recall (k)) defined in Equation 10
If
A (k) 0, it holds that
(k)
A (8)
Agg Aon (1)( Eupt I Aggu (Tr()) -opt I A ge J bo (k)
-est Copt
(41)
(b) due Assumption and (c) holds since '² is a feasible policy. Combining this with the induction assumption and the update rule of Equation 11,, have 1(++1) b6 I J Eest + cpp and J ((++1), Hence, (i(++)),((+t)) n y + East + Eopt] * when A (k) > O.
where (a) is due Assumption with (R)
On the other hand, if (1) O, have
( min A by
(T)
A Agess (T(()) < (
Eest East
(42)
Since 6(*) is the feasible solution to Equation 40 it holds that Jč... S (k) ((++1)) Accordingly, we have [i(k+1), ((b+1),j(++11) n [Jém:: J + Eest + Eapt] * 0. Therefore, the claim holds for any 1 E [0, K].
L
We now ready to prove Theorem 3
Proof of Theorem Note that (()
(R)
(5(0) 110))2
H2- due to the update rule of
Equation 11 According to Lemma 20 we have Jim S j(K) J + Eest + Eopt + H2-K K
Additionally, the returned policy Teet satisfies
A A000 (Fret)
min A (TT) Eopt nell
I min A jim (T)) + Eupt S East + Eopt
sell
where (a) uses Assumption and (b) is due J monotonically decreasing in by. Applying this to Lemma 19 with j(K)) < J + + Eopt H2 K concludes the proof.
< {(()) and the fact that min, Ab (अ) is
33

---

Published as a conference paper at ICLR 2025
H.6 PROOF OF THEOREM!
5
We prove the following restatement of Theorem 5 with concrete values.
Theorem 6 (Restatement of Theorem 5). Suppose Assumptions and S hold. Suppose that Algo-
rithm 2 is with algorithms Jn and J that satisfy Assumption 1 and Assumption 3 Let
C
+ 2DHVS 27HVA + 2DHVS
Ō(DHVS).
2fam
when 72
where (ip and fam are defined in Lemma 18 and D is defined in Theorem Assume that the
evaluators J. and Jo are sufficiently accurate such that
Egrd = CgE² where Ca = 1024 VS
and Eest = OJE² where C2 = 1024C
Set a E² and T CTE such that
C. = 64 (Ct Egrd)
and
Cr = 40960A S + =gga)) O(D
Then, Algorithm| returns policy x(()) such that
Abo ( ((()))) min Abp (T) SE.
xell
We first introduce the following useful lemma.
Lemma 21. Let
M Abo)
+ min { Deg (T') + lsuul || - r1]]]
be the Moreau
Zaam
envelope function of Ao, (T) with parameter 1/26 For any policy π E 11.
(T) min Au, (T') - cll
Aoo (
1
T'ell
24mm
Proof. Define π arg min Asg (T') + fam T x 112- According to Lemma with 1/20 there exists subgradient g aA,, (T)) such that, for any x' E II,
g) x
V
M
Abo
(TT). x¹)
Tum
IAE
و o
Abo
(TT)
[||TT - n 112
(43)
W
2/S
M
(T)
24am
where (a) due to the
inequality and (b) uses that, for any T' 11
|| r'|12
(F(, T'(s a)) s VS max
Σ (F(s,a) as)
SES
(44)
I VS max
Σ (s) x' (8) $255.
aEA
Let 2h1 E arg aingmnggen (T). Inserting this result into Theorem
we have
Doy (T))
Aoo (Tbin) S DH max
(
- n'
Gg aD..
x x'ell
$ 2DH
V
M o Ao (T) (T))
24am
Therefore,
Abo (T) Aso (mb,) = Aoo (T) Asp i
bo (T)
(0)
(T) A i
2DH
M 1
100 (T)
b0
8
11 |T - 2|| + 2DH 5
V
M
Aon (TT)
|
M
A
(T)
+2DH
V 1 A (m)
2lam
34

---

Published as a conference paper at ICLR 2025
where (a) is due to Theorem 4 (b) is due to the Lipschitz continuity by Lemma 18 and (c) uses This concludes the proof.
Lemma 7
Lemma 22. Under the settings of Theorem 6
V M
Abn Aln
(
(IT())
16fsm
4T alem (Pip + Egrd) + 46 al VS + 2lamEest)
26am
1=U
Proof. Recall that
((+1) E arg min (1'0, -x(())))
1
x =000
Proin (T((1) - -ag(tt)
+ 2a
Tell
Define =(() = arg min,' (T') + tsca [|T(1) π/ 1 Then, we have
(M 1 A20) (z
= min Aio (TT) + Lam sell
(b++1)
24am
s (TT())) + Lam
n (++1) (+)
-Projn (z(11) |
Ae, + Esm
Projm (1) - -ag(t)
S Ao, + tam
(1) aag #11)
= Aoo (T) + Esm
(0) (0)) 2 + a (000,((0))
x(0)) (1()))))))))))) +o 2
((0) -
fmm
g 2
= =(M Ttam
Ano) (x(11)
(45)
We further upper bound ! and g(t) Ja (T)))). Due to Assumption there exists a vector g' E RSA that satisfies
Recall (1) E arg max,eeo,NT (T) - bn and
g' E VJ iece pro
Pro (T
p(()
E arg max Jo ( (0o) ((T())))) PEZI
and |0000 100--'1 11 E (46)
Thus, using Lemma 16 we have 2 S 11g' 112 + ||g(0) 0²1l2 - Pt + sqn Furthermore, we have
(g() (1) -x((0) 0 (1) - n (10)) + (g g n (t) -1(1)
gg' (1) (0)
90 - 5/1, ((0) - -- T0/ -
x 1
8 g 7(1) T(()) + 23 g VS
where (a) due to the Sauchy-Schward inequality and (b) uses Equation 444
By inserting the above inequalities to Equation (45) using g' defined in Equation 46 we have
26sma (g', 7 - -x(0) x10)
(47)
M A00 (T - (M 2e.m o
Ao0 ) (+ + a² 22lam (L, + Egda) + am Vs.
Temm
(4) (TT) such that Next, we are going to derive the lower bound of 3. Define A 60
(1) Je Je brc0
(48)
Additionally, let 5n and b, be shorthand such that 8n == (eT))( - bn and 8, = Ja( bn-
Then, Due to Assumption [ for any æ,, we have
A bo (T) A (TT)
Jxce
max 8n - A
nE[O.N]
Secol by Assumption
(49)
Eoest + max nE[o,N]
18,
5m
S 28est
35

---

Published as a conference paper at ICLR 2025
where (a) is due to the definition of (2()) and (b) uses Lemma 11
(0) Due to the weak convexity of bu (iz) with respect to π (Lemma 18 and since g' E =0 (T((1)
3 22 = ( x(())
(1) (T) - - (
fam 2
(()) (())
bg
bo (T (0) Aug (0))
bo (F (0) A to (7()
+ + (x - Abo (x
Pum
z10)
x(0
2
Sener by Equatica
49
Senrt by Equation 5v
lam 7(0)
Ano (T((1)
Lsm
(1)) x(1)
Ao (TT( sm (1) T(1)
+
n
2Eest
2
2
= -by - (T) + tam
T (1) 11))
min Ell
Dou (T') + lsm
Tt' x(1)
1
(2)
+
fsm
7(0)
x(1)
| 2Eest
2
2
2
8am
(t) 71))
2Eest
(
aa
V
M
Abo)
(1 (1((0)
M 7(M
V
Abo
( 2Eest
20
27am
8e
24am
where (a) uses Lemma
7 By inserting this Equation 447
M 1 Ano) (x(t)) |
SextamEest
Ttom
{(M Temm
Abo (1r(t))
(M A0w (=(((1))) a (f,, Egaa) + 4al VS.
ztem
By taking summation over Et_
V M
)x)))(())))))
<(MM) A0s) - -(M Aes) (TT(T)
4
24am
26mm
26am
T(a2 + tmaa) + 4alsseggd VS + Salsan
Note that
M 1
Ab0) (z) - M
Ao0 ) (TT(T)
Toom
Tom
min xell
ATp(T) + 2mm
1 (0) π
min well
Abo(T) + Lsm (T)
-Ab, + fum
n (0)
(0)
Abp (F((2))
2sm 7 (T) म (T)
2
1
(Ab((T(T))
+ 4mm
(0) (
A,, (T(T) sam
π (T) - न (T)
<bam (0) π (T)
46amS
where the last inequality uses Equation 44 By combining all the results, we obtain
Σ M Abo ) (1)
16fam 4T
aelam(Phr + egdd 4e 44 grd V8 28 20 Sest
This concludes the proof.
We now ready prove Theorem 6
36

---

Published as a conference paper at ICLR 2025
Proof of Theorem
Let mho arg en Ato (T). Then,
min 1.
Ao (r( - -b (Thh))
11
bo (T Abc (Tii))
t=0
T
M A (TT)
24am
M - (GT)
c
T
1=0
VV
1
4 allm +A(alam
(Cep egra) + 46 erd V Eest
Ta
16
48
lsuul (lpt + Egga + 166 ard VS + SeamFest
8VT
VT
40 CeValnSS S8 18-18-1-1 +
20 22C//omlle + e2 + )87 +40 40 Cam (st V + Veest)
4C 4C Stt (G.p + = + +40 Vovlmm (st EErd + Veett
where (a) uses Lemma 21 (b) uses Lemma 22 (c) replaces with 8/VT, (d) uses
v + vy. and (e) sets V + =
Therefore, when Eest Egrd, a, and T satisfy:
Egrd 1024C VS
East 10240
5
g²
T 409609 P2. S(eL. + eggd)e and
VT
64C
sm (Lt +
8
gdd
we have
3
min Aoy (x(()) s Do, (Tb )
16 0,
1]
4
Finally, ts E arg [0 A (t) satisfies that
Ab)((((1)) = A (e*) + Aio (T((1)) (4)
min
(4)
Eest
t9 1e|0,7 -1] 1]
Abo (z)( + ((0)) Doo (z)()) + East
min
< min
Doo (T)) + 2Eest
1e[0,7-1]
3 < A (Ttt)) + 7 + 25est
< A +
This concludes the proof.
37


Reviews:
[{"review_id": "mMtY4ChaLp", "reviewer": "Reviewer_1d8S", "summary": "This paper proposes the EpiRC-PGS algorithm for solving the robust constrained Markov Decision Process (RCMDP) problem and provides a theoretical proof for identifying an $\\epsilon$-optimal policy. The paper first highlights the limitations of the traditional Lagrangian formulation in RCMDPs, introducing the epigraph form as a more effective approach for handling the policy optimization process. Finally, the authors present the EpiRC-PGS algorithm as a solution, which leverages the epigraph form to address RCMDPs effectively.", "questions": "Currently, experiments appear limited to low-dimensional cases. Extending tests to a more complex environment, like a two-dimensional space (e.g., velocity and distance in driving), could clarify if EpiRC-PGS maintains its time and space efficiency as complexity grows.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "1. This paper identifies key limitations in traditional algorithms for robust constrained Markov Decision Processes (RCMDPs) and presents an innovative, streamlined approach to overcome these challenges. \n2. The shift to an epigraph form represents a significant advancement, simplifying the solution method and providing an effective framework for robust optimization. \n3. The empirical comparison highlights the practical effectiveness of EpiRC-PGS, showing its ability to achieve low-return, constraint-satisfying policies, making it an attractive solution in robust decision-making applications.", "weaknesses": "1. A key area for improvement is a more thorough analysis of the algorithm’s efficiency, especially in higher-dimensional state spaces. \n2. While the $\\epsilon$-optimality proof is solid, addressing any computational overhead in the inner loop for larger state spaces would enhance its applicability to real-world problems.", "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": "", "extra_scores": {}}, {"review_id": "JPffzxIHA1", "reviewer": "Reviewer_KWav", "summary": "This paper reformulate robust constrained MDPs via epigraphical reformulation and propose a bisection algorithm to solve this problem.", "questions": "See weaknesses.\n\n- What do you mean by \"is an unknown value\" in Assumption 4?\n\n- Algorithm 1, how do you set T?", "limitations": "", "rating": 3, "confidence": 4, "soundness": 2, "presentation": 1, "contribution": 1, "strengths": "- This paper addresses an important problem in the field of MDPs\n\n- The idea of bisection search is interesting.", "weaknesses": "- The writing is extremely confusing. For example line 205, it is not clear what does \"Does pi^star \\in...hold?\" mean, given that the exact phrase was given in line 204. Also, there are many diamond-shape notation in the draft, and they should be typos.\n\n- The idea, although is interesting, is very simple. The use of epigraphical reformulation is standard and not surprising and technical. The most technical part should be the evaluation of \\Delta, but the proposed algorithm relies on existing methods to do this step. \n\n- The underlying idea of Algorithm 1 is not clear and the presentation is poor. \n\n- The convergence of the proposed algorithm is not fast, O(eps^-4), and there is no discuss on the complexity. \n\n- Experiments are not working on large-scale problems.", "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": "", "extra_scores": {}}, {"review_id": "CslJAZjLwe", "reviewer": "Reviewer_YFQK", "summary": "The paper aims to develop an algorithm to identify a near-optimal policy in Robust Constrained Markov Decision Processes (RCMDPs). RCMDPs aim to minimize cumulative costs while satisfying constraints in the worst-case scenarios. The authors note that conventional policy gradient approaches to the Lagrangian formulation for RCMDPs often get trapped in suboptimal solutions due to gradient conflicts. To address this, they propose using the epigraph form of the RCMDP problem, which circumvents these conflicts by optimizing the objective or the constraints individually. This approach allows the policy gradient to avoid local minima associated with conflicting gradients. They introduce the Epigraph Robust Constrained Policy Gradient Search (EpiRC-PGS) algorithm, a binary search-based method that iteratively refines policy selection, with theoretical guarantees to find an ε-optimal policy in RCMDPs.", "questions": "1. How does the algorithm perform when Assumption 2 on the initial distribution is partially met but not fully satisfied? Would the relaxation of this assumption degrade the policy quality significantly?\n\n2. Have alternative subgradient methods or other non-gradient-based approaches been considered for this epigraph-form RCMDP problem? If so, how do they compare with the EpiRC-PGS algorithm in terms of robustness and feasibility?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. Applying the epigraph form to RCMDPs is a novel solution to address gradient conflict issues that arise with traditional Lagrangian formulations. \n\n2. The authors offer theoretical proofs that guarantee the proposed algorithm’s convergence to an ε-optimal policy. \n\n3. The paper includes empirical evaluations across several RCMDP settings. The experiments show that the proposed EpiRC-PGS algorithm reliably converges to feasible and low-cost policies, significantly outperforming Lagrangian-based methods in robust settings.", "weaknesses": "1. The double-loop structure of the EpiRC-PGS algorithm, while effective, is computationally intensive. The paper mentions this as a limitation, suggesting that a single-loop alternative could improve efficiency, which is a potential area for improvement.\n\n2. The algorithm’s effectiveness relies on the coverage of the initial distribution (Assumption 2). This assumption may not always hold, especially when the state space is large.", "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": "", "extra_scores": {}}, {"review_id": "VKKpRi8v77", "reviewer": "Reviewer_yT6U", "summary": "The paper present the first algorithm to solve Robust Constrained Markov Decision Process (RCMDP). The proposed algorithm achieves $\\epsilon$-optimality with $\\mathcal{O}(\\epsilon^{-4})$ iteration complexity provided the uncertainty set is known apriori. The paper uses epigraph method which is different from the standard Lagrange approach used in the literature.", "questions": "1. Please categorize the related works into two groups: one that assumes the uncertainty set is fully characterized apriori (see the weakness above) and others that do not. This will help readers put the work into context. \n\n2. What are the challenges in extending this result to the case where the uncertainty set is not fully known apriori?\n\n3. Does the algorithm scale with the size of the state space? Does it scale with the size of the uncertainty set? Some comments on these should be provided in the paper.\n\n4. What is the typical computational complexity to generate a subgradient estimate with $\\mathcal{O}(\\epsilon^2)$ error? Such complexities should be elaborated in the paper.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. Good intuition and presentation.\n2. Mathematically sound results.", "weaknesses": "**Minor Comments**\n\n1. Assumption $5$ is used in Theorem $3$, however it appears later. Please correct it. \n\n**Major Comments**\n\n1. To my understanding, this algorithm works if the uncertainty set is exactly characterized and known (otherwise, getting a subgradient evaluator might be difficult). However, one of the potential application of Robust MDP is to ensure that policies trained on an unknown model $P_0$ does not deviate too much if the actual model $P$ is close to the model $P_0$ in some sense. In this case, one can probably guess the shape of the uncertainty set but cannot fully characterize it since $P_0$ is unknown. For example, if $P$ lies in a ball of radius $r$ centered around $P_0$, then the shape of the uncertainty set is a high dimensional sphere but its centre, $P_0$ is unknown. Information about $P_0$ is available only through a simulator with model $P_0$. My question is: how can the proposed algorithm provide guarantees in such cases? If it cannot, then that should be highlighted in the abstract and introduction as a drawback.", "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": "", "extra_scores": {}}, {"review_id": "SRemkg5vxD", "reviewer": "Reviewer_FLm4", "summary": "The paper introduces Epigraph Robust Constrained Policy Gradient Search, an algorithm designed to identify near-optimal policies in RCMDPs. The epigraph form can address gradient conflicts and theoretical techniques of prior approaches, ensuring convergence to an \n$ϵ-optimal$ policy across uncertain environments while satisfying safety constraints.", "questions": "In robust RL, sample complexity and convergence results typically depend on the gap between the transition kernels in the uncertainty set. Could the authors elaborate on how the results depend on this gap or specify which parts of the analysis are impacted by it?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "This paper is well structured and written, it addresses the difficulties of applying existing CMDP algorithms in RCMDP by providing the first algorithm with theoretical performance guarantees for near-optimal policy identification. The proposed epigraph form effectively resolves gradient conflicts inherent in the Lagrangian formulation. They also include a toy example to show the challenges in RCMDP which makes the paper easy to follow and the empirical results demonstrate that EpiRC-PGS outperforms baselines in various RCMDP settings.", "weaknesses": "The proposed algorithm’s double-loop structure may become computationally intensive in environments with high-dimensional action or state spaces, limiting real-time applicability.  The binary search and the projection in the policy updates are highly computationally inefficient. Assumption 2 requires an initial distribution over all the states, which is impractical, especially in the RCMDP setting, since some states are unsafe. Since the design of the algorithm is based on the monotonical property of $\\Delta_b^*,$ it requires assumptions 3,4,5 to have accurate estimations. The empirical evaluation could benefit from complicated or additional real-world applications to validate the robustness in practical MDP scenarios.\n\ncomments:\nIt is better to discuss all the assumptions before presenting the main theorem.", "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": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)