Near-Optimal Policy Identification in Robust Constrained Markov Decision Processes via Epigraph Form

## Abstract

Abstract Designing a safe policy for uncertain environments is crucial in real-world control applications.
However, this challenge remains inadequately addressed within the Markov decision process (MDP) framework.
This paper presents the first algorithm capable of identifying 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 Lagrangian max-min formulation with policy gradient methods can become trapped in suboptimal solutions by encountering a sum of conflicting gradients from the objective and constraint functions during its inner minimization problem.
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 binary search algorithm with a policy gradient subroutine and prove that it identifies an ε 𝜀 \varepsilon italic_ε -optimal policy in an RCMDP with 𝒪 ~ ⁢ ( ε − 4 ) ~ 𝒪 superscript 𝜀 4 \widetilde{\mathcal{O}}(\varepsilon^{-4}) over~ start_ARG caligraphic_O end_ARG ( italic_ε start_POSTSUPERSCRIPT - 4 end_POSTSUPERSCRIPT ) policy evaluations.

## 1 Introduction

Designing policies that satisfy safety constraints even in unforeseen environments is crucial for real-world decision-making, as real systems frequently encounter measurement or estimation errors and environmental disturbances (Taguchi et al., ).
Within the Markov decision process (MDP) framework, constraint satisfaction and environmental uncertainty have traditionally been addressed separately, through constrained MDPs (CMDP; e.g., Altman ()) and robust MDPs (RMDP; e.g., Iyengar ()), respectively.
The former aims to minimize costs while satisfying constraints, whereas the latter aims to minimize the worst-case cost in an uncertainty set of possible environments.
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 the significant theoretical progress made in CMDPs and RMDPs (see Appendix A), theoretical results on RCMDPs are currently scarce.
Even in the tabular setting, where the state and action spaces are finite, there exists no algorithm with guarantees to find a near-optimal policy in an RCMDP.

The difficulty of RCMDPs arises from the challenging optimization process, which simultaneously 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, ; Bellman et al., ).
Similarly, the linear programming (LP) approach, commonly used for CMDPs, is inadequate due to the nonconvexity of the robust formulation (Iyengar, ; Grand-Clément & Petrik, ).
Consequently, the policy gradient method with the Lagrangian formulation is the primary remaining option (Russel et al., ; Wang et al., ).
The Lagrangian formulation approximates the RCMDP problem $\min_{\pi}\left\{f(\pi)\mathchoice{\>}{\>}{\,}{\,}\middle|\allowbreak
\mathchoice{\>}{\>}{\,}{\,}\mathopen{}h(\pi)\leq 0\right\}$ by $\max_{\lambda\geq 0}\min_{\pi}f(\pi)+\lambda h(\pi)$, where $f(\pi)$ and $h(\pi)$ represent the worst-case cumulative cost—known as the (cost) return(^1^11We commonly 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*.)—and the worst-case constraint violation of a policy $\pi$, respectively.
There have been a few attempts to provide theoretical guarantees for the Lagrangian approach (Wang et al., ; Zhang et al., ); however, no existing studies offer rigorous and satisfactory guarantees that the max-min problem yields the same solution as the original RCMDP problem.
This leaves us with a fundamental question:

*How can we identify near-optimal policies in an RCMDP?*

We address this question by presenting three key contributions, which are summarized as follows:

#### Gradient conflict in the Lagrangian formulation ( Section 4 ).

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 a viable alternative.
However, our Theorem 4.1 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, $\nabla f(\pi)$ and $\nabla h(\pi)$, conflict with each other, causing their sum $\nabla f(\pi)+\lambda\nabla h(\pi)$ to cancel out, even when the policy $\pi$ is not optimal.
Consequently, the Lagrangian approach for RCMDPs may not reliably lead to a near-optimal policy.

**Table 1: Summary of approaches and the problem settings in which they are ensured to find an $\varepsilon$-optimal policy for each setting. “PG” denotes Policy Gradient. Each cell displays a “✓” indicating the presence of an algorithm with this approach that guarantees yielding an $\varepsilon$-optimal policy. Representative works supporting each “✓” are listed below it. Conversely, “✕” denotes settings where the approach either isn’t suitable or lacks performance guarantees.**
| Approach | MDP | CMDP | RMDP | RCMDP |
| --- | --- | --- | --- | --- |
| Dynamic Programming | $\underset{\text{\cite[citet]{\@@bibref{Authors Phrase1YearPhrase2}{bellman1957<br>dynamic}{\@@citephrase{(}}{\@@citephrase{)}}}}}{\text{\char 51}}$ | ✕ | $\underset{\text{\cite[citet]{\@@bibref{Authors Phrase1YearPhrase2}{iyengar2005<br>robust}{\@@citephrase{(}}{\@@citephrase{)}}}}}{\text{\char 51}}$ | ✕ |
| Linear Programming | $\underset{\text{\cite[citet]{\@@bibref{Authors Phrase1YearPhrase2}{denardo1970<br>linear}{\@@citephrase{(}}{\@@citephrase{)}}}}}{\text{\char 51}}$ | $\underset{\text{\cite[citet]{\@@bibref{Authors Phrase1YearPhrase2}{altman1999<br>constrained}{\@@citephrase{(}}{\@@citephrase{)}}}}}{\text{\char 51}}$ | ✕ | ✕ |
| Lagrangian + PG | $\underset{\text{\cite[citet]{\@@bibref{Authors Phrase1YearPhrase2}{agarwal2021<br>theory}{\@@citephrase{(}}{\@@citephrase{)}}}}}{\text{\char 51}}$ | $\underset{\text{\cite[citet]{\@@bibref{Authors Phrase1YearPhrase2}{ding2020<br>natural}{\@@citephrase{(}}{\@@citephrase{)}}}}}{\text{\char 51}}$ | $\underset{\text{\cite[citet]{\@@bibref{Authors Phrase1YearPhrase2}{wang2023<br>policy}{\@@citephrase{(}}{\@@citephrase{)}}}}}{\text{\char 51}}$ | ✕ |
| Epigraph + PG (Ours) | ✓ | ✓ | ✓ | ✓ |

#### Epigraph form of RCMDP ( Section 5 ).

We then demonstrate that the *epigraph form*, commonly used in constrained optimization literature (Boyd & Vandenberghe, ; Beyer & Sendhoff, ; Rahimian & Mehrotra, ), entirely circumvents the challenges associated with the Lagrangian formulation.
The epigraph form transforms the RCMDP problem into $\min_{y}\left\{y\mathchoice{\>}{\>}{\,}{\,}\middle|\allowbreak\mathchoice{\>}{
\>}{\,}{\,}\mathopen{}\min_{\pi}\max\left\{f(\pi)-y,h(\pi)\right\}\leq 0\right\}$, introducing an auxiliary minimization problem of $\min_{\pi}\max\left\{f(\pi)-y,h(\pi)\right\}$ and minimizing its threshold variable $y$.
Unlike the Lagrangian approach, which necessitates summing $\nabla f(\pi)$ and $\nabla h(\pi)$, policy gradient methods for the auxiliary problem update the policy using either $\nabla f(\pi)$ or $\nabla h(\pi)$, thanks to the maximum operator in the problem.
As a result, the epigraph form avoids the problem of conflicting gradient sums, preventing policy gradient methods from getting stuck in suboptimal minima (Theorem 5.6).

#### A new RCMDP algorithm ( Section 6 ).

Finally, we propose an 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 feasibility of the threshold variable $y$ by performing policy gradients on the auxiliary problem, while the outer loop employs binary search to determine the minimal feasible $y$.
EpiRC-PGS is guaranteed to find an $\varepsilon$-optimal policy(^2^22The definition of an $\varepsilon$-optimal policy is provided in Definition 3.2) with $\widetilde{\mathcal{O}}(\varepsilon^{-4})$ robust policy evaluations (Corollary 6.6), where $\widetilde{\mathcal{O}}(\cdot)$ represents the conventional big-O notation excluding polylogarithmic terms.
Since RCMDP generalizes plain MDP, CMDP, and RMDP, our EpiRC-PGS is applicable to all these types of MDPs, ensuring a near-optimal policy for each.
Table 1 compares existing approaches in various MDP settings.

Notably, EpiRC-PGS does not rely on the rectangularity assumption of the uncertainty set (see, e.g., Iyengar ()), which often leads to overly conservative policies (Goyal & Grand-Clement, ).
EpiRC-PGS remains effective as long as policy evaluation under the worst-case environment is possible (see Assumptions 5.3, 6.1 and 6.2), making it applicable to a wide range of settings.
Additionally, EpiRC-PGS converges in a last-iterate sense.
Many Lagrangian-based algorithms for CMDPs guarantee performance for the average of past policies (Miryoosefi et al., ; Chen et al., ; Li et al., ; Liu et al., ), but they encounter difficulties in scenarios where policy averaging is impractical, such as in deep RL applications. In contrast, EpiRC-PGS does not require policy averaging and ensures that the final policy is near-optimal (Corollary 6.6). We discuss the limitations and potential future directions of our approach in Section 8.

## 2 Related Work

This section reviews existing approaches for RCMDPs.
Additional related work on CMDPs and RMDPs can be found in Appendix A.

Russel et al. (); Mankowitz et al. () proposed heuristic algorithms for RCMDPs, but their approaches lack theoretical guarantees for convergence to near-optimal policies.
Wang et al. () introduced a Lagrangian approach with convergence guarantee to a 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., ; Wang & Zou, ; ).

Sun et al. () 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 a near-optimal policy is not guaranteed.

Ghosh () employed a penalty approach which considers the optimization problem of the form $\min_{\pi}f(\pi)+\lambda\max\{h(\pi),0\}$, where $f$ and $h$ are defined in Section 1.
While this approach can yield a near-optimal policy for a sufficiently large value of $\lambda>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 will demonstrate in Section 4, this minimization is intrinsically difficult, making the practical implementation of such an oracle challenging.

Finally, Zhang et al. () tackled RCMDPs using the policy-mixing technique (Miryoosefi et al., ; Le et al., ). In this technique, a policy is sampled from a finite set of deterministic policies according to a sampling distribution at the start of each episode, and it remains fixed throughout the episode.
However, even if 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., ).
We discuss the limitations of the policy-mixing technique in Section A.3.
Additionally, Zhang et al. () assume an $R$-contamination uncertainty set, limiting its applicability similarly to the work of Wang et al. ().

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, ) and $H_{\infty}$ optimal control (Anderson et al., ; Zames, ; Doyle, ). These approaches are specifically tailored for a specialized class of MDPs, known as the linear quadratic regulator (LQR, Du et al. ()). However, because LQR and tabular MDPs operate within distinct frameworks, these control methods are unsuitable for tabular RCMDPs.
Given that most modern reinforcement learning (RL) algorithms, such as DQN (Mnih et al., ), 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.

## 3 Preliminary

We use the shorthand $\mathbb{R}_{+}\vcentcolon\nolinebreak\mkern-1.2mu=[0,\infty)$.
Without loss of generality, every finite set is assumed to be a subset of integers.
The set of probability distributions over $\mathcal{S}$ is denoted by $\mathscr{P}(\mathcal{S})$.
For two integers $a\leq b$, we define $\llbracket a,b\rrbracket\vcentcolon\nolinebreak\mkern-1.2mu=\left\{a,\dots,b\right\}$.
If $a>b$, $\llbracket a,b\rrbracket\vcentcolon\nolinebreak\mkern-1.2mu=\emptyset$.
For a vector $x\in\mathbb{R}^{N}$, its $n$-th element is denoted by $x_{n}$ or $x(n)$, and we use the convention that $\|x\|_{2}=\sqrt{\sum_{i}{x_{i}^{2}}}$ and $\|x\|_{\infty}=\max_{i}\lvert x_{i}\rvert$.
For two vectors $x,y\in\mathbb{R}^{N}$, we denote $\langle x,y\rangle=\sum_{i}x_{i}y_{i}$.
We let $\mathbf{0}\vcentcolon\nolinebreak\mkern-1.2mu=(0,\ldots,0)^{\top}$ and $\mathbf{1}\vcentcolon\nolinebreak\mkern-1.2mu=(1,\ldots,1)^{\top}$, with their dimensions being clear from the context.
All scalar operations and inequalities should be understood point-wise when applied to vectors and functions.
Given a finite set $\mathcal{S}$, we often treat a function $f:\mathcal{S}\to\mathbb{R}$ as a vector $f\in\mathbb{R}^{\mathcal{S}}$.
Both notations, $f:\mathcal{S}\to\mathbb{R}$ and $f\in\mathbb{R}^{\mathcal{S}}$, are used depending on notational convenience.
Finally, $\partial f(x)$ and $\nabla f(x)$ denote the (Fréchet) subgradient and gradient of $f:\mathcal{X}\to\mathbb{R}$ at a point $x$, respectively.
Their formal definitions are deferred to Definition D.1.

### 3.1 Constrained Markov Decision Process

Let $N\in\mathbb{Z}_{\geq 0}$ be the number of constraints.
An infinite-horizon discounted constrained MDP (CMDP) is defined as a tuple $(\mathcal{S},\mathcal{A},\gamma,P,\mathcal{C},b,\mu)$, where
$\mathcal{S}$ denotes the finite state space with size $S$,
$\mathcal{A}$ denotes the finite action space with size $A$,
$\gamma\in(0,1)$ denotes the discounted factor,
and $\mu\in\mathscr{P}(\mathcal{S})$ denotes the initial state distribution.
For notational brevity, let $H\vcentcolon\nolinebreak\mkern-1.2mu=(1-\gamma)^{-1}$ denotes the effective horizon.
Further, $b\vcentcolon\nolinebreak\mkern-1.2mu=(b_{1},\dots,b_{N})\in[0,H]^{N}$ denotes the constraint threshold vector, where $b_{n}$ is the threshold scalar for the $n$-th constraint,
$\mathcal{C}\vcentcolon\nolinebreak\mkern-1.2mu=\left\{c_{n}\right\}_{n\in
\llbracket 0,N\rrbracket}$ denotes the set of cost functions, where
$c_{n}:\mathcal{S}\times\mathcal{A}\to[0,1]$ denotes the $n$-th cost function and $c_{n}(s,a)$ denotes the $n$-th cost when taking an action $a$ at a state $s$.
$c_{0}$ is for the objective to optimize and $\{c_{1},\dots,c_{N}\}$ are for the constraints.
$P:\mathcal{S}\times\mathcal{A}\to\mathscr{P}(\mathcal{S})$ denotes the transition probability kernel,
which can be interpreted as the environment with which the agent interacts. $P(s^{\prime}\mathchoice{\>}{\>}{\,}{\,}|\allowbreak\mathchoice{\>}{\>}{\,}{\,}
\mathopen{}s,a)$ denotes the state transition probability to a new state $s^{\prime}$ from a state $s$ when taking an action $a$.

### 3.2 Policy and Value Functions

A (Markovian stationary) policy is defined as $\pi\in\mathbb{R}^{\mathcal{S}\times\mathcal{A}}$ such that $\pi(s,\cdot)\in\mathscr{P}(\mathcal{A})$ for any $s\in\mathcal{S}$. $\pi(s,a)$ denotes the probability of taking an action $a$ at state $s$.
The set of all the policies is denoted as $\Pi$, which corresponds to the *direct parameterization* policy class presented in Agarwal et al. ().
Although non-Markovian policies can yield better performance in general RMDP problems (Wiesemann et al., ), for simplicity, we focus on Markovian stationary policies in this paper.
With an abuse of notation, for two functions $\pi,g\in\mathbb{R}^{\mathcal{S}\times\mathcal{A}}$, we denote $\langle\pi,g\rangle=\sum_{s,a\in\mathcal{S}\times\mathcal{A}}\pi(s,a)g(s,a)$.

For a policy $\pi$ and transition kernel $P$, let $d^{\pi}_{P}:\mathcal{S}\to\mathbb{R}_{+}$ denote the occupancy measure of $\pi$ under $P$.
$d^{\pi}_{P}(s)$ represents the expected discounted number of times $\pi$ visits state $s$ under $P$, such that
$d^{\pi}_{P}(s)=(1-\gamma)\mathbb{E}\left[\sum_{h=0}^{\infty}\gamma^{h}\mathbbm
{1}\left\{s_{h}=s\right\}\mathchoice{\>}{\>}{\,}{\,}\middle|\allowbreak
\mathchoice{\>}{\>}{\,}{\,}\mathopen{}s_{0}\sim\mu,\pi,P\right]$.
Here, the notation means that the expectation is taken over all possible trajectories, where $a_{h}\sim\pi(s_{h},\cdot)$ and $s_{h+1}\sim P(\cdot\mathchoice{\>}{\>}{\,}{\,}|\allowbreak\mathchoice{\>}{\>}{
\,}{\,}\mathopen{}s_{h},a_{h})$.

For $\pi\in\mathbb{R}^{\mathcal{S}\times\mathcal{A}}$ and $n$-th cost $c_{n}$, let $Q^{\pi}_{n,P}:\mathcal{S}\times\mathcal{A}\to\mathbb{R}$ be the action-value function such that
(^3^33We do not restrict the domain of the value function to $\Pi$. This allows the policy gradient $\nabla J_{n,P}(\pi)$ to be well-defined for any $\pi\in\Pi$, as demonstrated in Lemma 3.1.)

$$ $Q^{\pi}_{n,P}(s,a)=c_{n}(s,a)+\gamma\sum_{s^{\prime}\in\mathcal{S}}P\left(s^{ \prime}\mathchoice{\>}{\>}{\,}{\,}\middle|\allowbreak\mathchoice{\>}{\>}{\,}{ \,}\mathopen{}s,a\right)\sum_{a^{\prime}\in\mathcal{A}}\pi(s^{\prime},a^{ \prime})Q^{\pi}_{n,P}(s^{\prime},a^{\prime})\quad\forall(s,a)\in\mathcal{S} \times\mathcal{A}\;.$ $$

Let $V^{\pi}_{n,P}:\mathcal{S}\to\mathbb{R}$ be the state-value function such that $V^{\pi}_{n,P}(s)=\sum_{a\in\mathcal{A}}\pi(s,a)Q^{\pi}_{n,P}(s,a)$ for any $s\in\mathcal{S}$.
If $\pi\in\Pi$, $V^{\pi}_{n,P}(s)$ represents the expected cumulative $n$-th cost of $\pi$ under $P$ with an initial state $s$.
We denote the (cost) return function as $J_{n,P}(\pi)\vcentcolon\nolinebreak\mkern-1.2mu=\sum_{s,a\in\mathcal{S}\times
\mathcal{A}}\mu(s)V^{\pi}_{n,P}(s)$.

#### Policy gradient method.

For a problem $\min_{\pi\in\Pi}f(\pi)$ where $f:\Pi\to\mathbb{R}$ is differentiable at a policy $\pi\in\Pi$, policy gradient methods with direct parameterization update $\pi$ to a new policy $\pi^{\prime}$ as follows (Agarwal et al., ):

$$ $\displaystyle\pi^{\prime}\vcentcolon\nolinebreak\mkern-1.2mu=\operatorname{ Proj}_{\Pi}\left(\pi-\alpha\nabla f(\pi)\right)\stackrel{{\scriptstyle \scriptscriptstyle(\mkern-1.5mua\mkern-1.5mu)}}{{=}}\operatorname*{arg\,min}_{ \pi^{\prime}\in\Pi}\left\langle\nabla f(\pi),\pi^{\prime}-\pi\right\rangle+ \frac{1}{2\alpha}\left\lVert\pi^{\prime}-\pi\right\rVert^{2}_{2}\;,$ (1) $$

where $\alpha>0$ is the learning rate and $\operatorname{Proj}_{\Pi}$ denotes the Euclidean projection operator onto $\Pi$.
The equality (a) is a standard result (see, e.g., Parikh et al. ()).
Note that when $\macc@depth\char 1\relax\frozen@everymath{\macc@group}\macc@set@skewchar
\macc@nested@a 111{}\in\Pi$ is a stationary point, meaning it satisfies $\min_{\pi\in\Pi}\langle\pi-\macc@depth\char 1\relax\frozen@everymath{
\macc@group}\macc@set@skewchar\macc@nested@a 111{},\nabla f(\macc@depth\char 1
\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a 111{})
\rangle=0$, Equation 1 outputs the same $\macc@depth\char 1\relax\frozen@everymath{\macc@group}\macc@set@skewchar
\macc@nested@a 111{}$.

The following lemma is a well-known result that provides the gradient of the return function for the direct parameterization policy class $\Pi$ (e.g., Bhandari & Russo ()).

###### Lemma 3.1 (Policy gradient theorem) .

For any $\pi\in\Pi$, transition kernel $P:\mathcal{S}\times\mathcal{A}\to\mathscr{P}(\mathcal{S})$, and $n\in\llbracket 0,N\rrbracket$, the gradient is given by
$\left(\nabla J_{n,P}(\pi)\right)(s,a)=Hd^{\pi}_{P}(s)Q^{\pi}_{n,P}(s,a)\quad
\forall(s,a)\in\mathcal{S}\times\mathcal{A}\;.$

###### Lemma 3.1 (Policy gradient theorem) .

### 3.3 Robust Constrained Markov Decision Process

An infinite-horizon discounted robust constrained MDP (RCMDP) is defined as a tuple $(\mathcal{S},\mathcal{A},\gamma,\mathcal{U},\mathcal{C},b,\mu)$, where $\mathcal{U}$ is a compact set of transition kernels, known as the uncertainty set.

For each $n\in\llbracket 0,N\rrbracket$, let $J_{n,\mathcal{U}}(\pi)\vcentcolon\nolinebreak\mkern-1.2mu=\max_{P\in\mathcal{U
}}J_{n,P}(\pi)$ denote the worst-case (cost) return function, which represents the $n$-th return of $\pi$ under the most adversarial environment within $\mathcal{U}$.

Let $\Pi_{\mathrm{F}}\vcentcolon\nolinebreak\mkern-1.2mu=\left\{\pi\in\Pi
\mathchoice{\>}{\>}{\,}{\,}\middle|\allowbreak\mathchoice{\>}{\>}{\,}{\,}
\mathopen{}\max_{n\in\llbracket 1,N\rrbracket}J_{n,\mathcal{U}}(\pi)-b_{n}\leq
0\right\}$ be the non-empty set of all the feasible policies.
An optimal policy in an RCMDP minimizes the robust objective return while satisfying all the constraints.
We denote an optimal policy as $\pi^{\star}$ and its objective return as $\heartsuit$ such that

$$ $\pi^{\star}\in\operatorname*{arg\,min}_{\pi\in\Pi_{\mathrm{F}}}J_{0,\mathcal{U }}(\pi)\;\text{ and }\;\heartsuit\vcentcolon\nolinebreak\mkern-1.2mu=J_{0, \mathcal{U}}(\pi^{\star})\;.$ (2) $$

We define a near-optimal policy in the following sense(^4^44 To simplify analysis and notation, we allow an $\varepsilon$-optimal policy to violate constraints by up to $\varepsilon$. Designing a near-optimal policy that strictly adheres to the constraints is straightforward by using a slightly stricter threshold $b^{\prime}\vcentcolon\nolinebreak\mkern-1.2mu=b-\varepsilon$ and assuming the existence of a feasible policy under the new threshold $b^{\prime}$.).

###### Definition 3.2 ( $\varepsilon$ -optimality) .

A policy $\pi\in\Pi$ is $\varepsilon$-optimal if it satisfies
$J_{0,\mathcal{U}}(\pi)-\heartsuit\leq\varepsilon$
and
$\max_{n\in\llbracket 1,N\rrbracket}J_{n,\mathcal{U}}(\pi)-b_{n}\leq\varepsilon$.

###### Definition 3.2 ( ε 𝜀 \varepsilon italic_ε -optimality) .

## 4 Challenges of Lagrangian Formulation

To motivate our formulations and algorithms presented in subsequent sections, this section illustrates the limitations of using the conventional Lagrangian formulation for RCMDPs.
By introducing Lagrangian multipliers $\lambda\vcentcolon\nolinebreak\mkern-1.2mu=(\lambda_{1},\dots,\lambda_{N})\in
\mathbb{R}^{N}_{+}$, the optimization problem of RCMDP is equivalent to

$$ $(\textbf{RCMDP})\quad\heartsuit=\min_{\pi\in\Pi}\max_{\lambda\in\mathbb{R}^{N} _{+}}J_{0,\mathcal{U}}(\pi)+\sum_{n=1}^{N}\lambda_{n}\left(J_{n,\mathcal{U}}( \pi)-b_{n}\right)\;.$ (3) $$

As this min-max problem is hard to solve, Russel et al. (); Mankowitz et al. (); Wang et al. () swap the min-max and consider the following Lagrangian relaxed formulation (^5^55This is relaxed since $\clubsuit\leq\heartsuit$ holds due to the min-max inequality (Boyd & Vandenberghe, ).):

$$ $\displaystyle(\textbf{Lagrange})\quad\clubsuit\vcentcolon\nolinebreak\mkern-1. 2mu=\max_{\lambda\in\mathbb{R}^{N}_{+}}\min_{\pi\in\Pi}L_{\lambda}(\pi)\;\text { where }\;L_{\lambda}(\pi)\vcentcolon\nolinebreak\mkern-1.2mu=J_{0,\mathcal{U }}(\pi)+\sum_{n=1}^{N}\lambda_{n}\left(J_{n,\mathcal{U}}(\pi)-b_{n}\right)\;.$ (4) $$

To identify an optimal policy $\pi^{\star}$ using Equation 4, two key questions must be addressed:

- $\mathrm{(i)}$
Does Equation 4 yield $\pi^{\star}$ as its solution?
- $\mathrm{(ii)}$
Is it tractable to identify a pair of $(\lambda,\pi)$ that solves Equation 4?

However, answering these questions affirmatively is challenging due to the following issues:

#### Strong duality challenge ( i ) i (\mathrm{i}) ( roman_i ) .

Deriving $\pi^{\star}$ from Equation 4 hinges on establishing strong duality, i.e., $\heartsuit=\clubsuit$.
Once strong duality is confirmed, solving Equation 4 can indeed yield $\pi^{\star}$ since $\pi^{\star}\in\operatorname*{arg\,min}_{\pi\in\Pi}L_{\lambda^{\star}}(\pi)$, where $\lambda^{\star}\in\operatorname*{arg\,max}_{\lambda\in\mathbb{R}^{N}_{+}}\min_
{\pi\in\Pi}L_{\lambda}(\pi)$ (Boyd & Vandenberghe, ).

In the CMDP setting where $\mathcal{U}=\{P\}$, a well-established approach to proving strong duality is to reformulate Equation 4 as $\max_{\lambda\in\mathbb{R}^{N}_{+}}\min_{d\in\mathcal{D}_{P}}\langle c_{0}+
\lambda\left(c_{1}-b_{1}/H\right),d\rangle$, where $\mathcal{D}_{P}$ denotes the set of state-action occupancy measures in the environment $P$
(Altman, ; Paternain et al., ; ).
Since the set $\mathcal{D}_{P}$ is convex (Borkar, ), with a mild assumption of the existence of a strictly feasible policy, Sion’s minimax theorem immediately establishes strong duality.

However, Lemma 1 in Wang et al. () demonstrated that this strategy cannot be directly applied to RCMDPs. When robustness is incorporated, the set of occupancy measures can become non-convex, hindering the application of the minimax theorem.
Consequently, it is challenging to guarantee that Equation 4 will yield $\pi^{\star}$.

Figure: (a) RCMDP presented in Example 4.2, where $\delta>0$.
Refer to caption: x1.png

#### Gradient conflict challenge ( ii ) ii (\mathrm{ii}) ( roman_ii ) .

Unfortunately, even if strong duality holds and $\pi^{\star}$ can be found by $\pi^{\star}\in\operatorname*{arg\,min}_{\pi\in\Pi}L_{\lambda^{\star}}(\pi)$, solving this minimization remains challenging.
Since the sum of robust returns in $L_{\lambda^{\star}}(\pi)$ excludes the use of DP and convex-optimization approaches (Iyengar, ; Altman, ; Grand-Clément & Petrik, ), the policy gradient method such as Equation 1 is the primary remaining option to solve $\min_{\pi\in\Pi}L_{\lambda^{\star}}(\pi)$.
However, the following Theorem 4.1 shows that policy gradient methods can be trapped in a local minimum that does not solve $\min_{\pi\in\Pi}L_{\lambda^{\star}}(\pi)$:

###### Theorem 4.1 .

For any $\gamma\in(0,1)$, there exist a $\macc@depth\char 1\relax\frozen@everymath{\macc@group}\macc@set@skewchar
\macc@nested@a 111{}>0$, a policy $\macc@depth\char 1\relax\frozen@everymath{\macc@group}\macc@set@skewchar
\macc@nested@a 111{}\in\Pi$ and an RCMDP with $\mu>\mathbf{0}$ satisfying the following condition: There exists a positive constant $R>0$ such that, for any $b_{1}\in\mathbb{R}$,

$$ $L_{\macc@depth\char 1\relax\frozen@everymath{\macc@group}\macc@set@skewchar \macc@nested@a 111{}}(\macc@depth\char 1\relax\frozen@everymath{\macc@group} \macc@set@skewchar\macc@nested@a 111{})<L_{\macc@depth\char 1\relax \frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a 111{}}(\pi)\;\; \forall\pi\in\left\{\pi\in\Pi\mathchoice{\>}{\>}{\,}{\,}\middle|\allowbreak \mathchoice{\>}{\>}{\,}{\,}\mathopen{}\left\lVert\pi-\macc@depth\char 1\relax \frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a 111{}\right \rVert_{2}\leq R,\;\pi\neq\macc@depth\char 1\relax\frozen@everymath{ \macc@group}\macc@set@skewchar\macc@nested@a 111{}\right\}\;\;\text{ but }\;\; L_{\macc@depth\char 1\relax\frozen@everymath{\macc@group}\macc@set@skewchar \macc@nested@a 111{}}(\macc@depth\char 1\relax\frozen@everymath{\macc@group} \macc@set@skewchar\macc@nested@a 111{})-\min_{\pi\in\Pi}L_{\macc@depth\char 1 \relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a 111{}}( \pi)\geq\frac{3\gamma H}{16}\;.$ (5) $$

Moreover, there exists a $b_{1}\in(0,H)$ where $\macc@depth\char 1\relax\frozen@everymath{\macc@group}\macc@set@skewchar
\macc@nested@a 111{}$ satisfies $\macc@depth\char 1\relax\frozen@everymath{\macc@group}\macc@set@skewchar
\macc@nested@a 111{}\in\operatorname*{arg\,max}_{\lambda\in\mathbb{R}^{N}_{+}}
\min_{\pi\in\Pi}L_{\lambda}(\pi)$.

The detailed proof is deferred to Appendix G. Essentially, the proof constructs a simple RCMDP where *the policy gradients for the objective and the constraint are in conflict*.

###### Example 4.2 .

Consider the RCMDP with $\mathcal{U}=\{P_{1},P_{2}\}$ presented in Figure 1(a) with $\delta=0$ and set $\lambda=1$ for simplicity.
Let ${\color[rgb]{0,0,1}\pi_{1}}$ and ${\color[rgb]{1,0,0}\pi_{2}}$ be policies that select ${\color[rgb]{0,0,1}a_{1}}$ and ${\color[rgb]{1,0,0}a_{2}}$ for all states, respectively.
For both policies, the objective worst-case is $P_{1}$ and the constraint worst-case is $P_{2}$ (see Appendix G).
Hence, switching from policy ${\color[rgb]{1,0,0}\pi_{2}}$ to taking action ${\color[rgb]{0,0,1}a_{1}}$ decreases the objective return under $P_{1}$ but increases the constraint return under $P_{2}$.
This conflict causes the gradients of ${\color[rgb]{1,0,0}\pi_{2}}$ for the objective $(\nabla J_{0,P_{1}}({\color[rgb]{1,0,0}\pi_{2}}))$ and for the constraint $(\nabla J_{1,P_{2}}({\color[rgb]{1,0,0}\pi_{2}}))$ to sum to a constant vector, i.e.,

$$ $\left(\nabla L_{1}({\color[rgb]{1,0,0}\pi_{2}})\right)(s,\cdot)=\left(\nabla J _{0,P_{1}}({\color[rgb]{1,0,0}\pi_{2}})+\nabla J_{1,P_{2}}({\color[rgb]{1,0,0} \pi_{2}})\right)(s,\cdot)=\mathrm{constant}\cdot\mathbf{1}\quad\forall s\in \mathcal{S}\;,$ $$

showing that ${\color[rgb]{1,0,0}\pi_{2}}$ is a stationary point.
However, ${\color[rgb]{1,0,0}\pi_{2}}$ cannot solve $\min_{\pi\in\Pi}L_{1}(\pi)$ because ${\color[rgb]{0,0,1}\pi_{1}}$ would clearly result in a smaller $L_{1}(\pi)$.
This stationary point becomes a strict local minimum with a positive $\delta>0$, where ${\color[rgb]{1,0,0}\pi_{2}}$ slightly prefers ${\color[rgb]{1,0,0}a_{2}}$ over ${\color[rgb]{0,0,1}a_{1}}$ (see Appendix G for details).

Figure 1(b) computationally illustrates this negative result by plotting the landscape of $L_{1}(\pi)$ in the RCMDP example across all possible policies for $(\gamma,\delta)=(0.4,0.09)$.
We set $b_{1}=0$ as $b_{1}$ does not influence the landscape of $L_{1}(\pi)$.
In this example, ${\color[rgb]{1,0,0}\pi_{2}}$ becomes a local minimum that attracts the policy gradient but fails to solve $\min_{\pi\in\Pi}L_{1}(\pi)$, as ${\color[rgb]{0,0,1}\pi_{1}}$ achieves $L_{\lambda}({\color[rgb]{0,0,1}\pi_{1}})<L_{\lambda}({\color[rgb]{1,0,0}\pi_{2
}})$.

This negative result underscores the difficulty of RCMDPs in contrast to CMDPs.
In CMDP, where $\mathcal{U}=\{P\}$, for any $\lambda\in\mathbb{R}$, the problem $\min_{\pi\in\Pi}L_{\lambda}(\pi)$ reduces to solving a standard MDP with a cost function $c_{0}+\lambda c_{1}$ in the environment $P$.
As a result, the well-known policy gradient analysis by Agarwal et al. () guarantees that the policy gradient method (Equation 1) converges to stationary points that solve $\min_{\pi\in\Pi}L_{\lambda}(\pi)$.
However, the negative result presented above reveals that there exist RCMDPs where Equation 1 fails by encountering a local minimum.

###### Theorem 4.1 .

###### Example 4.2 .

## 5 Alternative RCMDP Formulation

This section introduces the epigraph form of RCMDP, which overcomes the challenges discussed in Section 4.
For any constrained optimization problem of the form $\min_{x}\left\{f(x)\mathchoice{\>}{\>}{\,}{\,}\middle|\allowbreak\mathchoice{
\>}{\>}{\,}{\,}\mathopen{}h(x)\leq 0\right\}$ with $x\in\mathbb{R}^{n}$ and $f,h:\mathbb{R}^{n}\to\mathbb{R}$, its epigraph form is defined as:

$$ $\min_{x,y}y\;\text{ such that }\;f(x)\leq y\;\text{ and }\;h(x)\leq 0$ (6) $$

with variables $x\in\mathbb{R}^{n}$ and $y\in\mathbb{R}$.
It is well-known that $(x,y)$ is optimal for Equation 6 if and only if $x$ is optimal for the original problem and $y=f(x)$ (see, e.g., Boyd & Vandenberghe ()).

### 5.1 Epigraph Form of RCMDP

Based on Equation 6, the RCMDP problem can be equivalently written as:

$$ $\heartsuit=\min_{b_{0}\in[0,H],\pi\in\Pi}b_{0}\;\text{ such that }\;\Delta_{b_ {0}}(\pi)\leq 0\;.$ (7) $$

where we define $\Delta_{b_{0}}:\mathbb{R}^{\mathcal{S}\times\mathcal{A}}\to\mathbb{R}$ such that
$\Delta_{b_{0}}(\pi)=\max_{n\in\llbracket 0,N\rrbracket}J_{n,\mathcal{U}}(\pi)-
b_{n}$.
$\Delta_{b_{0}}(\pi)$ represents the maximum violation of the constraints $\max_{\llbracket 1,N\rrbracket}J_{n,\mathcal{U}}(\pi)-b_{n}\leq 0$ of the policy $\pi$, with the additional constraint $J_{0,\mathcal{U}}(\pi)-b_{0}\leq 0$.
By moving $\min_{\pi\in\Pi}$ to the constraint, Equation 7 can be further transformed as follows:

###### Theorem 5.1 .

Let $\Delta^{\star}_{b_{0}}\vcentcolon\nolinebreak\mkern-1.2mu=\min_{\pi\in\Pi}
\Delta_{b_{0}}(\pi)$. Then,

$$ $({\textbf{Epigraph Form}})\quad\heartsuit=\min_{b_{0}\in[0,H]}b_{0}\;\text{ such that }\;\Delta^{\star}_{b_{0}}\leq 0\;.$ (8) $$

Furthermore, if $b_{0}=\heartsuit$, any policy $\pi\in\operatorname*{arg\,min}_{\pi\in\Pi}\Delta_{b_{0}}(\pi)$ is optimal.

Figure: Figure 2: Behavior of $\Delta^{\star}_{b_{0}}$ in the RCMDP from Example 4.2 with $(\gamma,\delta)=(0.1,0)$ and $b_{1}=2/3$. Adjusting $b_{0}$ by increasing it when $\Delta^{\star}_{b_{0}}\geq 0$ and decreasing it otherwise leads to convergence at $b_{0}=\heartsuit$, where $\Delta^{\star}_{b_{0}}=0$.
Refer to caption: x3.png

The proof is provided in Section H.2.
Instead of Equation 7, we call Equation 8 the epigraph form of RCMDP.
Intuitively, the epigraph form seeks the smallest threshold value $b_{0}$ such that there exists a feasible policy $\pi\in\Pi_{\mathrm{F}}$ that also satisfies $J_{0,\mathcal{U}}(\pi)\leq b_{0}$.
If $\Delta^{\star}_{b_{0}}\leq 0$, such a feasible policy exists; if $\Delta^{\star}_{b_{0}}>0$, no feasible policy $\pi\in\Pi_{\mathrm{F}}$ achieves $J_{0,\mathcal{U}}(\pi)\leq b_{0}$.

Since the epigraph form provides $\heartsuit$ and $\pi^{\star}$, the remaining question is whether Equation 8 can be easily solved.
To address this, the following properties of $\Delta^{\star}_{b_{0}}$ are useful:

###### Lemma 5.2 .

$\Delta^{\star}_{b_{0}}$ is monotonically decreasing in $b_{0}$ and $\Delta^{\star}_{\heartsuit}=0$.

The proof is provided in Section H.1.
Given the monotonicity of $\Delta^{\star}_{b_{0}}$, if $\Delta^{\star}_{b_{0}}$ can be efficiently computed, a line search over $b_{0}\in[0,H]$ will readily yield $b_{0}\approx\heartsuit$.
Increase $b_{0}$ if $\Delta^{\star}_{b_{0}}\geq 0$, and decrease it if $\Delta^{\star}_{b_{0}}\leq 0$, as illustrated in Figure 2.

###### Theorem 5.1 .

###### Lemma 5.2 .

### 5.2 On Computing Δ b 0 ⋆ subscript superscript Δ ⋆ subscript 𝑏 0 \Delta^{\star}_{b_{0}} roman_Δ start_POSTSUPERSCRIPT ⋆ end_POSTSUPERSCRIPT start_POSTSUBSCRIPT italic_b start_POSTSUBSCRIPT 0 end_POSTSUBSCRIPT end_POSTSUBSCRIPT

To compute $\Delta^{\star}_{b_{0}}$, we need to solve the following optimization problem:

$$ $\Delta^{\star}_{b_{0}}=\min_{\pi\in\Pi}\Delta_{b_{0}}(\pi)=\min_{\pi\in\Pi} \max_{n\in\llbracket 0,N\rrbracket}\max_{P\in\mathcal{U}}J_{n,P}(\pi)-b_{n}\;.$ (9) $$

Clearly, the right-hand side of Equation 9 is an RMDP problem with added robustness over the set of modified cost functions $\mathcal{C}_{b_{0}}\vcentcolon\nolinebreak\mkern-1.2mu=\left\{c_{n}-b_{n}/H
\right\}_{n\in\llbracket 0,N\rrbracket}$.
Since $\mathcal{C}_{b_{0}}$ is neither $s$-rectangular nor $(s,a)$-rectangular (see, e.g., Iyengar ()), DP approaches are inadequate for this problem.
Therefore, we employ the policy gradient method to compute $\Delta^{\star}_{b_{0}}$ by assuming the following general structure on the uncertainty set:

###### Assumption 5.3 .

$\mathcal{U}$ is either ($\mathrm{i}$) a finite set or ($\mathrm{ii}$) a compact set such that, for any $\pi\in\Pi$, $\nabla J_{n,P}(\pi)$ is continuous with respect to $P\in\mathcal{U}$.

Then, the subgradient $\partial\Delta_{b_{0}}(\pi)$ is represented as follows, with the proof provided in Section H.3:

###### Lemma 5.4 .

For any $b_{0}\in 0$ and $\pi\in\Pi$, define

$$ $\mathcal{G}_{b_{0}}(\pi)\vcentcolon\nolinebreak\mkern-1.2mu=\left\{\nabla J_{n ,P}(\pi)\mathchoice{\>}{\>}{\,}{\,}\middle|\allowbreak\mathchoice{\>}{\>}{\,}{ \,}\mathopen{}n,P\in\mathcal{W}_{b_{0}}(\pi)\right\}\;\text{ where }\;\mathcal {W}_{b_{0}}(\pi)\vcentcolon\nolinebreak\mkern-1.2mu=\operatorname*{arg\,max}_{ n\in\llbracket 0,N\rrbracket,P\in\mathcal{U}}J_{n,P}(\pi)-b_{n}\;.$ (10) $$

Let $\operatorname{conv}B$ denote the convex hull of a set $B\subset\mathbb{R}^{\mathcal{S}\times\mathcal{A}}$.
Under Assumption 5.3, for any $\pi\in\Pi$ and $b_{0}\in\mathbb{R}$, the subgradient of $\Delta_{b_{0}}(\cdot)$ at $\pi$ is given by
$\partial\Delta_{b_{0}}(\pi)=\operatorname{conv}\mathcal{G}_{b_{0}}(\pi)\;.$

Here, $\operatorname*{arg\,max}$ returns the set $\mathcal{W}_{b_{0}}(\pi)$, which contains all cost and environment pairs that achieve the worst-case for $\pi$, while $\mathcal{G}_{b_{0}}(\pi)$ denotes the set of policy gradients corresponding to $\mathcal{W}_{b_{0}}(\pi)$.
Roughly speaking, while $\partial L_{\lambda}(\pi)$ involves summing policy gradients from return functions across different environments (see Example 4.2), $\partial\Delta_{b_{0}}(\pi)$ can focus on the policy gradient of a single worst-case environment by taking $\max_{n\in\llbracket 0,N\rrbracket}$.
Consequently, $\Delta_{b_{0}}$ avoids the sum of conflicting policy gradients, thereby circumventing the gradient conflict challenge discussed in Section 4.

To formally guarantee that any stationary point of the policy gradient is globally optimal, we introduce the following assumption regarding the coverage of the initial distribution:

###### Assumption 5.5 .

The initial distribution $\mu\in\mathscr{P}(\mathcal{S})$ satisfies $\mu>\mathbf{0}$.

Similar assumptions are used in policy gradient literature for MDPs (Agarwal et al., ), CMDPs (Ying et al., ), and RMDPs (Wang et al., ; Li et al., ).
Additionally, we remark that the Lagrangian approach performs poorly even under Assumption 5.5 as Theorem 4.1 demonstrates.

Assumption 5.5 allows the epigraph form to enjoy the following *gradient-dominance* property (see, e.g., Agarwal et al. ()), which ensures that any stationary point is globally optimal:

###### Theorem 5.6 (Gradient dominance) .

Under Assumptions 6.4 and 5.3, for any $\pi\in\Pi$ and $b_{0}\in\mathbb{R}$,

$$ $\Delta_{b_{0}}(\pi)-\min_{\pi^{\prime}\in\Pi}\Delta_{b_{0}}(\pi^{\prime})\leq DH \max_{\pi^{\prime}\in\Pi}\left\langle\pi-\pi^{\prime},g\right\rangle\quad \forall g\in\partial\Delta_{b_{0}}(\pi)\;,$ $$

where $D\vcentcolon\nolinebreak\mkern-1.2mu=\max_{n,P\in\llbracket 0,N\rrbracket
\times\mathcal{U}}\left\lVert d^{\pi^{\star}_{n,P}}_{P}/\mu\right\rVert_{\infty}$ with $\pi^{\star}_{n,P}\in\operatorname*{arg\,min}_{\pi^{\prime}\in\Pi}J_{n,P}(\pi^{
\prime})$.

The detailed proof can be found in Section H.4.
Our proof is similar to Theorem 3.2 in Wang et al. (), but it is more rigorous and corrects a crucial error that can invalidate their result(^6^66For example, their proof around Equation (32) incorrectly bounds a positive value by a negative value.).
Moreover, while their proof is limited to cases where $\operatorname*{arg\,max}_{P\in\mathcal{U}}J_{0,P}(\pi)$ is finite, ours is not.
We leverage Sion’s minimax theorem (Sion, ) for this refinement.

###### Assumption 5.3 .

###### Lemma 5.4 .

###### Assumption 5.5 .

###### Theorem 5.6 (Gradient dominance) .

## 6 Algorithm

This section introduces a double-loop algorithm to solve the epigraph form (Equation 8) using a subroutine algorithm that approximately solves $\min_{\pi\in\Pi}\Delta_{b_{0}}(\pi)$.
Throughout this section, we assume access to the following oracle that approximately evaluates the value of $\Delta_{b_{0}}(\pi)$.

###### Assumption 6.1 (Evaluation oracle) .

We have an oracle $\mathscr{E}:\mathbb{R}_{+}\times\Pi\to\mathbb{R}_{+}$ that takes a value $b_{0}\geq 0$ and a policy $\pi\in\Pi$, and returns a value $\widehat{\Delta}\geq 0$ such that $\left\lvert\widehat{\Delta}-\Delta_{b_{0}}(\pi)\right\rvert\leq\varepsilon_{
\mathrm{est}}$, where $\varepsilon_{\mathrm{est}}\geq 0$ is an unknown value.

This assumption is mild and easy to meet in practice.
For example, if the uncertainty set incorporates a structural assumption like $s$-rectangularity or $(s,a)$-rectangularity, this evaluation oracle can be efficiently implemented using robust DP methods (Iyengar, ; Kumar et al., ; ).

Note that solving an RMDP is generally NP-hard when the uncertainty set satisfies only Assumption 5.3 (Wiesemann et al., ).
The hardness primarily stems from evaluating $J_{0,\mathcal{U}}(\pi)$.
Assumption 6.1 mitigates this hardness by abstracting the evaluation step, avoiding the need for additional structural assumptions on $\mathcal{U}$.

Figure: Algorithm 1 Projected Policy Gradient Subroutine

Figure: Algorithm 2 Double-Loop Optimization with $\min_{\pi\in\Pi}\Delta_{b_{0}}(\pi)$ Subroutine (also referred to as EpiRC-PGS when using Algorithm 1 as the subroutine)

###### Assumption 6.1 (Evaluation oracle) .

### 6.1 Subroutine Algorithm to Solve min π ∈ Π ⁡ Δ b 0 ⁢ ( π ) subscript 𝜋 Π subscript Δ subscript 𝑏 0 𝜋 \min_{\pi\in\Pi}\Delta_{b_{0}}(\pi) roman_min start_POSTSUBSCRIPT italic_π ∈ roman_Π end_POSTSUBSCRIPT roman_Δ start_POSTSUBSCRIPT italic_b start_POSTSUBSCRIPT 0 end_POSTSUBSCRIPT end_POSTSUBSCRIPT ( italic_π )

The subroutine algorithm updates policies via a policy gradient method.
Starting from an arbitrary initial policy $\pi^{(0)}\in\Pi$, let $\pi^{(1)},\dots,\pi^{(T)}$ be the updated policies where $T\in\mathbb{N}$ is the iteration length.

Recall that $\mathcal{G}_{b_{0}}(\pi)$, defined in Lemma 5.4, is a subset of the subgradient $\partial\Delta_{b_{0}}(\pi)$.
We assume access to an oracle that can approximate a subgradient element in $\mathcal{G}_{b_{0}}(\pi)$.

###### Assumption 6.2 (Gradient estimator) .

Let $\varepsilon_{\mathrm{grd}}\in\mathbb{R}_{+}$ be an unknown value.
We have an oracle $\mathscr{G}:\mathbb{R}_{+}\times\Pi\to\mathbb{R}^{\mathcal{S}\times\mathcal{A}}$ that takes a value $b_{0}\in\mathbb{R}_{+}$ and a policy $\pi\in\Pi$, and returns a vector $g\in\mathbb{R}^{\mathcal{S}\times\mathcal{A}}$ such that
$\min_{g^{\prime}\in\mathcal{G}_{b_{0}}(\pi^{(t)})}\left\lVert g-g^{\prime}
\right\rVert_{2}\leq\varepsilon_{\mathrm{grd}}$.

Similar to Assumption 6.1, this oracle can be efficiently implemented within uncertainty sets with certain structural assumptions (Kumar et al., ; Wang & Zou, ).

Using the gradient oracle $\mathscr{G}$ and a learning rate $\alpha>0$, we update the policy according to the following projected policy gradient, which is similar to Equation 1:

$$ $\displaystyle\pi^{(t+1)}\in\operatorname*{arg\,min}_{\pi\in\Pi}\left\langle g^ {(t)},\pi-\pi^{(t)}\right\rangle+\frac{1}{2\alpha}\left\lVert\pi-\pi^{(t)} \right\rVert^{2}_{2}\;\text{ where }\;g^{(t)}=\mathscr{G}(b_{0},\pi^{(t)})\;.$ (11) $$

We summarize the pseudocode of the policy gradient procedure in Algorithm 1.
The following theorem demonstrates that Algorithm 1 finds a near-minimum point of $\min_{\pi\in\Pi}\Delta_{b_{0}}(\pi)$.

###### Theorem 6.3 .

Suppose Assumptions 5.3, LABEL:, 5.5, LABEL:, 6.1, LABEL: and 6.2 hold.
Then, there exist problem-dependent constants $C_{\mathscr{G}},C_{\alpha},C_{T}>0$ that do not depend on $\varepsilon$ such that, when Algorithm 1 is run with $\alpha=C_{\alpha}\varepsilon^{2}$ and $T=C_{T}\varepsilon^{-4}$, if the gradient estimation is sufficiently accurate such that $\varepsilon_{\mathrm{grd}}=C_{\mathscr{G}}\varepsilon^{2}$, Algorithm 1 returns a policy $\pi^{(t^{\star})}$ satisfying

$$ $\Delta_{b_{0}}(\pi^{(t^{\star})})-\min_{\pi\in\Pi}\Delta_{b_{0}}(\pi)\leq \varepsilon+2\varepsilon_{\mathrm{est}}\;.$ $$

We provide the proof and the concrete values of $C_{\mathscr{G}},C_{\alpha}$ and $C_{T}$ in Section I.1.

###### Assumption 6.2 (Gradient estimator) .

###### Theorem 6.3 .

### 6.2 Binary Search with min π ∈ Π ⁡ Δ b 0 ⁢ ( π ) subscript 𝜋 Π subscript Δ subscript 𝑏 0 𝜋 \min_{\pi\in\Pi}\Delta_{b_{0}}(\pi) roman_min start_POSTSUBSCRIPT italic_π ∈ roman_Π end_POSTSUBSCRIPT roman_Δ start_POSTSUBSCRIPT italic_b start_POSTSUBSCRIPT 0 end_POSTSUBSCRIPT end_POSTSUBSCRIPT ( italic_π ) Subroutine

Our double-loop algorithm employs a binary search method to solve the epigraph form, supported by a subroutine algorithm that satisfies the following assumption.

###### Assumption 6.4 (Subroutine algorithm) .

We have a subroutine algorithm $\mathscr{A}:\mathbb{R}_{+}\to\Pi$ that takes a value $b_{0}\geq 0$ and returns a policy $\pi=\mathscr{A}(b_{0})$ such that $\Delta_{b_{0}}(\pi)\leq\min_{\pi^{\prime}\in\Pi}\Delta_{b_{0}}(\pi^{\prime})+
\varepsilon_{\mathrm{opt}}$ with an unknown $\varepsilon_{\mathrm{opt}}\geq 0$.

As we have shown in Theorem 6.3, Assumption 6.4 can be realized by Algorithm 1.

Let $K\in\mathbb{N}$ be the number of iterations of the binary search.
For each iteration $k$, let $[i^{(k)},j^{(k)}]\subseteq[0,H]$ be the search space where $i^{(k)}<j^{(k)}$.
We set $i^{(0)}=0$ and $j^{(0)}=H$.
We denote $b_{0}^{(k)}\vcentcolon\nolinebreak\mkern-1.2mu=(i^{(k)}+j^{(k)})/2$.
Additionally, given $b_{0}^{(k)}$, we denote the returned policy from $\mathscr{A}$ as $\pi^{(k)}\vcentcolon\nolinebreak\mkern-1.2mu=\mathscr{A}(b^{(k)}_{0})$ and its value evaluated by $\mathscr{E}$ as $\widehat{\Delta}^{(k)}\vcentcolon\nolinebreak\mkern-1.2mu=\mathscr{E}(b^{(k)}_
{0},\pi^{(k)})$.

Our binary search aims to identify the minimum $b_{0}$ such that $\Delta^{\star}_{b_{0}}=0$, as such $b_{0}$ satisfies $b_{0}=\heartsuit$.
Following the strategy illustrated in Figure 2, we increase $b_{0}^{(k)}$ if $\widehat{\Delta}^{(k)}>0$; otherwise, we decrease it.
More concretely, our binary search iteratively narrows down the search space as follows:

$$ $i^{(k+1)}\vcentcolon\nolinebreak\mkern-1.2mu=\begin{cases}b_{0}^{(k)}&\text{ if }\;\widehat{\Delta}^{(k)}>0\\ i^{(k)}&\text{ otherwise }\end{cases}\quad\text{ and }\quad j^{(k+1)} \vcentcolon\nolinebreak\mkern-1.2mu=\begin{cases}j^{(k)}&\text{ if }\;\widehat {\Delta}^{(k)}>0\\ b_{0}^{(k)}&\text{ otherwise }\end{cases}$ (12) $$

We summarize the pseudocode of the algorithm in Algorithm 2.
The following Theorem 6.5 ensures that Algorithm 2 returns a near-optimal policy.
We provide the proof in Section I.2.

###### Theorem 6.5 .

Suppose that Algorithm 2 is run with oracles $\mathscr{E}$ and $\mathscr{A}$ that satisfy Assumptions 6.1, LABEL: and 6.4.
Then, Algorithm 2 returns an $\tilde{\varepsilon}$-optimal policy, where $\tilde{\varepsilon}\vcentcolon\nolinebreak\mkern-1.2mu=2(\varepsilon_{\mathrm{
opt}}+\varepsilon_{\mathrm{est}})+2^{-K}H$.

We refer to Algorithm 2 with Algorithm 1 subroutine as
Epigraph Robust Constrained Policy Gradient Search (EpiRC-PGS).
By applying Theorem 6.3 to Theorem 6.5, the following corollary shows that EpiRC-PGS finds an $\varepsilon$-optimal policy by making $\widetilde{\mathcal{O}}(\varepsilon^{-4})$ queries to the oracles $\mathfrak{E}$ and $\mathfrak{G}$.

###### Corollary 6.6 .

Assume Assumptions 5.3, LABEL: and 5.5 holds.
Suppose we have sufficiently accurate oracles $\mathscr{E}$ and $\mathscr{G}$ that satisfy Assumption 6.1 and Assumption 6.2 with $\varepsilon_{\mathrm{est}}\leq\varepsilon/24$ and $\varepsilon_{\mathrm{grd}}\leq\varepsilon/8$, respectively.
Set Algorithm 1 as the subroutine algorithm $\mathscr{A}$ with parameters $(\mathscr{E},\mathscr{G},\alpha,T)$, where we set $\alpha=C_{\alpha}\varepsilon^{2}/64$, $T=C_{T}\varepsilon^{-4}/4096$, using $C_{\alpha}$ and $C_{T}$ from Theorem 6.3.
Then, given inputs $\mathscr{E}$ and $\mathscr{A}$, Algorithm 2 returns an $\varepsilon$-optimal policy after $K=\lfloor\log\left(2H\varepsilon^{-1}\right)\rfloor$ iteration.

Finally, we remark that EpiRC-PGS converges in a *last-iterate* sense.
While many Lagrangian-based algorithms for CMDPs provide certain performance guarantees for the average of past policies (Miryoosefi et al., ; Chen et al., ; Li et al., ; Liu et al., ), they become problematic in scenarios where policy averaging is impractical, such as in deep RL.
In contrast, Corollary 6.6 does not require policy averaging and ensures that the final policy output is near-optimal.

###### Assumption 6.4 (Subroutine algorithm) .

###### Theorem 6.5 .

###### Corollary 6.6 .

## 7 Experiments

Figure: Figure 3: Comparison of the algorithms in Section 7. Left: Objective return relative to the uniform policy ($y$-axis: $J_{0,\mathcal{U}}(\pi^{(k)})-J_{0,\mathcal{U}}(\pi_{\mathrm{unif}})$). Middle: Constraint violation ($y$-axis: $J_{1,\mathcal{U}}(\pi^{(k)})-b_{1}$). Algorithms in the blue area satisfy the constraint. Right: Violation vs. objective. The feasible $\pi^{(k)}$ with the smallest return is highlighted; if none is feasible, the one with the smallest violation is highlighted. EpiRC-PGS quickly identifies a feasible and low-return policy ( ●) that others do not find.
Refer to caption: x4.png

This section empirically compares our EpiRC-PGS algorithm to a Lagrangian counterpart, which aims to solve the problem $\max_{\lambda\in\mathbb{R}^{N}_{+}}\min_{\pi\in\Pi}L_{\lambda}(\pi)$ in Equation 4 by performing gradient ascent on $\lambda$ while using a policy gradient subroutine to solve $\min_{\pi\in\Pi}L_{\lambda}(\pi)$.
We refer to this Lagrangian-based algorithm as the “Lagrangian Formulation Policy Gradient Search (LF-PGS).”
LF-PGS abstracts some existing Lagrangian-based algorithms for RCMDPs (e.g., (Russel et al., ; Wang et al., )).
The detailed implementation of LF-PGS is provided in Appendix B.

Since Lagrangian-based algorithms typically require averaging the optimization variables obtained during updates (Miryoosefi et al., ; Chen et al., ; Li et al., ; Liu et al., ), we also report the performance of the averaged policies from LF-PGS, where the $k$-th policy is set as $\frac{1}{k}\sum_{j=0}^{k}\pi^{(k)}$.
We refer to this averaging algorithm as LF-PGS-avg.

Figure 3 shows the objective return and constraint violation for algorithms averaged over 20 randomly generated simple RCMDPs with finite uncertainty sets.
The details of the environmental setup are provided in Appendix B.
For each $k$-th outer iteration, we report the objective return minus the return of the uniform policy, i.e., $J_{0,\mathcal{U}}(\pi^{(k)})-J_{0,\mathcal{U}}(\pi_{\mathrm{unif}})$, where $\pi_{\mathrm{unif}}$ represents a uniform policy.
This subtraction accounts for variations in the minimum return across different RCMDPs.

#### Results.

The left and middle figures in Figure 3 demonstrate that EpiRC-PGS rapidly converges to a policy that not only satisfies the constraints but also achieves a low objective return.
In contrast, LF-PGS exhibits oscillatory returns and constraint violations.
Even when averaging its policies (LF-PGS-avg), the objective return remains worse than EpiRC-PGS and continues to exhibit constraint violations, indicating suboptimal performance.
Additionally, the right figure of Figure 3 reveals that any other algorithm does not find the feasible and low-return policy identified by EpiRC-PGS ( ● in the figure).
These findings empirically validate that EpiRC-PGS yields a near-optimal policy, contrasting with the conventional Lagrangian-based algorithm’s inability to do so.

## 8 Conclusion and Limitations

In this work, we propose EpiRC-PGS, the first algorithm guaranteed to find a near-optimal policy in an RCMDP (Corollary 6.6).
At the core of EpiRC-PGS is the use of the epigraph form for RCMDP.
Remarkably, the epigraph form produces the optimal policy $\pi^{\star}$ (Section 5.1) and supports a policy gradient algorithm to find it (Section 5.2).
These features effectively address the optimization challenges encountered in the conventional Lagrangian formulation (Section 4).

#### Limitations and future work.

A double-loop algorithm like EpiRC-PGS is often impractical when the inner problem requires high computational cost (Lin et al., ).
Developing a single-loop algorithm based on the epigraph form is a promising direction for future research.
To support future RCMDP studies, we discuss the potential difficulty in designing such an algorithm in Appendix C.

Another area for future research involves improving iteration complexity. It is known that with a rectangularity assumption, the natural policy gradient method can find an $\varepsilon$-optimal policy in RMDP with $\widetilde{\mathcal{O}}(\varepsilon^{-2})$ iterations Li et al. (). Investigating whether our $\widetilde{\mathcal{O}}(\varepsilon^{-4})$ complexity in RCMDP can be improved is a promising area for future research.

Finally, we leave for future work the exploration of removing the coverage assumption on the initial distribution (Assumption 5.5).
Although this assumption can be readily satisfied in robust policy design using simulators by assigning negligible initial probabilities to all states, it may violate the theoretical guarantees of the designed policy, as optimal policies in CMDP depend on the initial state distribution (Altman, ).

## Appendix A Additional Related Work

This section reviews existing approaches for CMDPs and RMDPs. 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 a single element, i.e., $\mathcal{U}=\{P\}$.
This section describes two primary approaches to the CMDP problem: the linear programming (LP) approach and the Lagrangian approach.

#### Linear programming approach.

The LP approach has been extensively studied in the theoretical literature (Efroni et al., ; Liu et al., ; Bura et al., ; HasanzadeZonuzy et al., ; Zheng & Ratliff, ).
Although it is a fundamental method in CMDP, it 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, ; Nachum & Dai, ).
However, RMDPs do not permit a convex formulation in terms of occupancy measures (Iyengar, ; Grand-Clément & Petrik, ).
While Grand-Clément & Petrik () recently introduced a convex optimization approach for RMDPs, their formulation is convex for the transformed objective value function, not for the occupancy measure, making it challenging to 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., ; Wei et al., ; HasanzadeZonuzy et al., ; Kitamura et al., ) and practice (Achiam et al., ; Tessler et al., ; Wang et al., ; Le et al., ; Russel et al., ).
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 $\mathcal{U}$ consists of a single element, it is well established that strong duality holds, meaning that $\clubsuit=\heartsuit$ holds, where $\clubsuit$ is from Equation 4 and $\heartsuit$ is from Equation 2 (Altman, ; Paternain et al., ; ).

The challenge with the Lagrangian method is the identification of an optimal policy.
Even if Equation 4 is solved, there’s no guarantee that the solution to the inner minimization problem will represent an optimal policy.
In some CMDPs, where feasible policies in $\Pi_{\mathrm{F}}$ must be stochastic (Altman, ), the inner minimization may yield a deterministic solution that is infeasible.
Zahavy et al. (); Miryoosefi et al. (); Chen et al. (); Li et al. (); Liu et al. () 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 it necessitates storing all past policies, which is often infeasible.
On the other hand, Ying et al. (); Ding et al. (); Müller et al. (); Kitamura et al. () tackled the issue by introducing entropy regularization into the objective return.
However, the regularization can lead to biased solutions and result in a 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.

### A.2 Robust Markov Decision Processes

RMDP is a specific subclass of RCMDP where there are no constraints, i.e., $N=0$. RMDP is a 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., ; Jiang, ).

#### Dynamic programming approach.

Since the seminal work by Iyengar (), numerous studies have explored dynamic programming (DP) approaches for RMDPs (Nilim & El Ghaoui, ; Clavier et al., ; Panaganti & Kalathil, ; Mai & Jaillet, ; Grand-Clément & Kroer, ; Derman et al., ; Wang & Zou, ; Kumar et al., ; Yang et al., ).
The DP approach decomposes the original problem into smaller sub-problems using Bellman’s principle of optimality (Bellman et al., ).
To apply this principle, DP approaches enforce rectangularity on the uncertainty set, which assumes independent worst-case transitions at each state or state-action pair.
However, as pointed out by Goyal & Grand-Clement (), the rectangularity assumption can result in a very conservative optimal policy.
Moreover, applying DP to constrained settings is challenging since CMDPs typically do not satisfy the principle of optimality (Haviv, ).
Although several studies have attempted to apply DP to CMDPs, they face issues such as excessive memory consumption, due to the use of non-stationary policy classes, or are restricted to deterministic policy classes (Chang, ; Chen & Blankenship, ; Chen & Feinberg, ).

#### 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., ; Wang & Zou, ; Li et al., ), and thus suffer from the same conservativeness issue.
It is important to note that robust policy evaluation can be NP-hard without any structural assumptions on the uncertainty set (Wiesemann et al., ), but such assumptions are potentially not required for the robust policy optimization step.
Our policy gradient algorithm abstracts the evaluation step by Assumption 6.1 and avoids the need for the rectangularity assumption during the policy optimization phase, similar to the recent work by Wang et al. ().

### A.3 Notes on the Policy-Mixing Technique

This section explains the theoretical limitations of the policy-mixing technique (Zhang et al., ; Miryoosefi et al., ; Le et al., ) for identifying a near-optimal policy.

#### Policy-mixing technique.

Let $\widetilde{\Pi}\vcentcolon\nolinebreak\mkern-1.2mu=\left\{\pi_{1},\dots,\pi_{m
}\right\}$ be a finite set of policies with $m\in\mathbb{N}$.
Consider a non-robust, single-constraint CMDP $\left(\mathcal{S},\mathcal{A},\gamma,P,\mathcal{C}=\left\{c_{0},c_{1}\right\},
b,\mu\right)$.
Given a distribution $\rho\in\mathscr{P}\left(\widetilde{\Pi}\right)$, define

$$ $\widetilde{J}_{0,P}(\rho)\vcentcolon\nolinebreak\mkern-1.2mu=\sum_{\pi\in \widetilde{\Pi}}\rho(\pi)J_{0,P}(\pi)\;\text{ and }\;\widetilde{J}_{1,P}(\rho) \vcentcolon\nolinebreak\mkern-1.2mu=\sum_{\pi\in\widetilde{\Pi}}\rho(\pi)J_{1, P}(\pi)\;.$ $$

The policy-mixing technique considers the following optimization problem:

$$ $\displaystyle\diamondsuit\vcentcolon\nolinebreak\mkern-1.2mu=$ $\displaystyle\min_{\rho\in\mathscr{P}\left(\widetilde{\Pi}\right)}\widetilde{J }_{0,P}(\rho)\;\text{ such that }\;\widetilde{J}_{1,P}(\rho)\leq b_{1}$ (13) $\displaystyle=$ $\displaystyle\min_{\rho\in\mathscr{P}\left(\widetilde{\Pi}\right)}\max_{ \lambda\in\mathbb{R}_{+}}\sum_{\pi\in\widetilde{\Pi}}\rho(\pi)\left(J_{0,P}( \pi)+\lambda\left(J_{1,P}(\pi)-b_{1}\right)\right)=\nolinebreak\mkern-1.2mu \vcentcolon\min_{\rho\in\mathscr{P}\left(\widetilde{\Pi}\right)}\max_{\lambda \in\mathbb{R}_{+}}\widetilde{L}(\rho,\lambda)\;.$ $$

Let $\rho^{\star}$ be the solution of Equation 13 such that
$\rho^{\star}\in\operatorname*{arg\,min}_{\rho\in\mathscr{P}\left(\widetilde{
\Pi}\right)}\max_{\lambda\in\mathbb{R}_{+}}\widetilde{L}(\rho,\lambda)$.

In this setting, a policy is sampled from $\rho$ at the start of each episode and remains fixed throughout the episode.
The term $\widetilde{J}_{0,P}(\rho)$ represents the expected return under the distribution $\rho$.
Since $\widetilde{L}(\rho,\lambda)$ is convex in $\rho$ and concave in $\lambda$, under some mild assumptions, Equation 13 can be solved efficiently by the following standard optimization procedure for min-max problems:
At each iteration $t=1,\dots,T$, with initial values $\lambda^{(0)}\in\mathbb{R}_{+}$ and $\rho^{(0)}\in\mathscr{P}\left(\widetilde{\Pi}\right)$,

- 1.
Update $\lambda^{(t)}$ using a no-regret algorithm. For example, with gradient ascent and a learning rate $\alpha>0$:
$\lambda^{(t)}\vcentcolon\nolinebreak\mkern-1.2mu=\max\left\{\lambda^{(t-1)}+
\alpha\left(\widetilde{J}_{1,P}(\rho^{(t-1)})-b_{1}\right),0\right\}\;.$
- 2.
Update $\rho^{(t)}$ as $\rho^{(t)}(\pi)=\mathbbm{1}\left\{\pi=\pi^{(t)}\right\}$ where
$\pi^{(t)}\in\operatorname*{arg\,min}_{\pi\in\widetilde{\Pi}}J_{0,P}(\pi)+
\lambda^{(t)}\left(J_{1,P}(\pi)-b_{1}\right)\;.$

Then, the averaged distribution ${\macc@depth\char 1\relax\frozen@everymath{\macc@group}\macc@set@skewchar
\macc@nested@a 111{}}^{(T)}\vcentcolon\nolinebreak\mkern-1.2mu=\frac{1}{T}\sum
_{t=0}^{T}\rho^{(t)}$ converges to $\rho^{\star}$ as $T\to\infty$ (Abernethy & Wang, ; Zahavy et al., ).
When $\widetilde{\Pi}$ is sufficiently large, we can expect that the optimal value of Equation 13 is equivalent to that of the CMDP problem, i.e., $\diamondsuit=\heartsuit$, where $\heartsuit$ is defined in Equation 2 with $\mathcal{U}=\{P\}$.

#### Limitation of policy-mixing.

Even when $\diamondsuit=\heartsuit$, it is crucial to note that, while ${\macc@depth\char 1\relax\frozen@everymath{\macc@group}\macc@set@skewchar
\macc@nested@a 111{}}^{(T)}$ converges to $\rho^{\star}$, there is no guarantee that ${\macc@depth\char 1\relax\frozen@everymath{\macc@group}\macc@set@skewchar
\macc@nested@a 111{}}^{(T)}\vcentcolon\nolinebreak\mkern-1.2mu=\frac{1}{T}\sum
^{T}_{t=0}\pi^{(t)}$ will converge to $\pi^{\star}$.

Let ${\macc@depth\char 1\relax\frozen@everymath{\macc@group}\macc@set@skewchar
\macc@nested@a 111{}}^{(T)}\vcentcolon\nolinebreak\mkern-1.2mu=\frac{1}{T}\sum
^{T}_{t=0}\lambda^{(t)}$.
Zhang et al. (); Miryoosefi et al. (); Le et al. () argued for the convergence of ${\macc@depth\char 1\relax\frozen@everymath{\macc@group}\macc@set@skewchar
\macc@nested@a 111{}}^{(t)}$ by asserting that the equality (a) in the following equation holds:

$$ $\displaystyle\frac{1}{T}\sum^{T}_{t=1}\widetilde{L}\left(\rho^{(t)},\lambda^{( t)}\right)$ $\displaystyle=\frac{1}{T}\sum^{T}_{t=1}\left(J_{0,P}(\pi^{(t)})+\lambda^{(t)} \left(J_{1,P}(\pi^{(t)})-b_{1}\right)\right)$ (14) $\displaystyle\stackrel{{\scriptstyle\scriptscriptstyle(\mkern-1.5mua\mkern-1.5 mu)}}{{=}}J_{0,P}({\macc@depth\char 1\relax\frozen@everymath{\macc@group} \macc@set@skewchar\macc@nested@a 111{}}^{(T)})+{\macc@depth\char 1\relax \frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a 111{}}^{(T)} \left(J_{1,P}({\macc@depth\char 1\relax\frozen@everymath{\macc@group} \macc@set@skewchar\macc@nested@a 111{}}^{(T)})-b_{1}\right)$ $$

(see, for example, Equation (14) in Zhang et al. (), Equation (1) in Le et al. (), and around Equation (13) in Miryoosefi et al. ()).

However, (a) in Equation 14 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 14 fails (see Proof of Lemma 3.1 in Agarwal et al. ()).
This invalidates the results of Miryoosefi et al. (); Le et al. (); Zhang et al. (), thus illustrating the theoretical limitations of the policy-mixing approach for near-optimal policy identification.

## Appendix B Experiment Details

The source code for the experiment is available at [https://github.com/matsuolab/RCMDP-Epigraph](https://github.com/matsuolab/RCMDP-Epigraph).

#### Environment construction.

We conduct the experiment on randomly generated simple RCMDP instances, whose uncertainty set is finite with $\left\lvert\mathcal{U}\right\rvert=5$.
We employ a construction strategy similar to that of Dann et al. ().
Each transition kernel $P\in\mathcal{U}$ is randomly instantiated.
For all $s,a$, the transition probabilities $P\left(\cdot\mathchoice{\>}{\>}{\,}{\,}\middle|\allowbreak\mathchoice{\>}{\>}{
\,}{\,}\mathopen{}s,a\right)$ are independently sampled from $\operatorname{Dirichlet}(0.05,\dots,0.05)$.
This transition probability kernel is concentrated yet encompasses non-deterministic transition probabilities.

The parameters are set as follows: $S=15$, $A=5$, $\gamma=0.99$, and $N=1$.
The cost values for the objective $c_{0}(s,a)$ are set to 0 0 with probability $0.5$ and are uniformly chosen at random from $[0,1]$ otherwise.
The cost values for the constraint $c_{1}(s,a)$ are set to $1-c_{1}(s,a)$.
Thus, the constraint and objective are in conflict in this CMDP.
This aligns with the CMDP construction strategy proposed by Moskovitz et al. () to generate a hard CMDP instance.

The initial state probabilities $\mu(\cdot)$ are independently sampled from $\operatorname{Dirichlet}(0.1,\dots,0.1)$.
The constraint threshold is set so that the uniform policy violates the threshold while ensuring that a feasible policy does exist.

#### EpiRC-PGS implementation.

For the policy gradient subroutine (Algorithm 1), we set the iteration length to $T=1000$ and the learning rate to $\alpha=0.001$.
These values are selected to ensure that Assumption 6.1 is satisfied with a sufficiently small
$\varepsilon_{\mathrm{est}}$.
Since the initial policy in Algorithm 1 can be chosen arbitrarily, the $(k-1)$-th policy from the outer loop is used as the initial policy for the $k$-th policy computation.

#### LF-PGS implementation.

The pseudocode for LF-PGS is shown in Algorithm 3.
We set the iteration length and learning rate for the inner policy optimization to $T=1000$ and $\alpha_{\pi}=0.001$.
Similar to EpiRC-PGS, these values are chosen to ensure sufficiently accurate optimization in the inner loop.
After a hyperparameter tuning, we choose $\alpha_{\lambda}=0.1$ for the outer updates, balancing between the convergence speed and performance.

Figure: Algorithm 3 Lagrangian Formulation Policy Gradient Search

## Appendix C Discussion on Single-Loop Algorithm

Although Algorithm 2 can identify a near-optimal policy, it uses a double-loop structure that repetitively solves $\min_{\pi\in\Pi}\Delta_{b_{0}}(\pi)$ by Algorithm 1.
In practice, single-loop algorithms, such as primal-dual algorithms for CMDPs (e.g., Efroni et al. (); Ding et al. ()), are typically more efficient and preferable compared to double-loop algorithms.
This section discusses the challenge of designing a single-loop algorithm for the epigraph form.

Since the epigraph form is a constrained optimization problem, we can further transform it using a Lagrangian multiplier $\lambda\in\mathbb{R}_{+}$, yielding:

$$ $\heartsuit=\min_{b_{0}\in[0,H]}\max_{\lambda\in\mathbb{R}_{+}}L_{\mathrm{epi}} (b_{0},\lambda)\;\text{ where }\;L_{\mathrm{epi}}(b_{0},\lambda)\vcentcolon \nolinebreak\mkern-1.2mu=b_{0}+\lambda\Delta^{\star}_{b_{0}}\;.$ (15) $$

Similar to the typical Lagrangian approach, let’s swap the min-max order. We call the resulting formulation the “epigraph-Lagrange” formulation:

$$ $\displaystyle({\textbf{Epigraph-Lagrange}})\quad\clubsuit_{\mathrm{epi}}=\max_ {\lambda\in\mathbb{R}_{+}}\min_{b_{0}\in[0,H]}\min_{\pi\in\Pi}b_{0}+\lambda \Delta_{b_{0}}(\pi)\;.$ (16) $$

Does the strong duality, $\heartsuit=\clubsuit_{\mathrm{epi}}$, hold?
If it does, we could design a single-loop algorithm similar to primal-dual CMDP algorithms, performing gradient ascent and descent on Equation 16.
Unfortunately, proving the strong duality is challenging.

Essentially, the min-max can be swapped when $L_{\mathrm{epi}}(b_{0},\lambda)$ in Equation 15 is quasiconvex-quasiconcave (Sion, ).
While $L_{\mathrm{epi}}(b_{0},\lambda)$ is clearly concave in $\lambda$, the quasiconvexity in $b_{0}$ is not obvious. Although $\Delta^{\star}_{b_{0}}$ is decreasing due to Lemma 5.2 and thus a quasi-convex function, there is no guarantee on the quasi-convexity of $b_{0}+\lambda\Delta^{\star}_{b_{0}}$. The situation would be resolved if $\Delta^{\star}_{b_{0}}$ were convex in $b_{0}$.
However, since $\Delta^{\star}_{b_{0}}=\min_{\pi\in\Pi}\Delta_{b_{0}}(\pi)$ is a pointwise minimum and $\Delta_{b_{0}}(\pi)$ may not be convex in $\pi$ (Agarwal et al., ), $\Delta^{\star}_{b_{0}}$ may not be convex in $b_{0}$ (Boyd & Vandenberghe, ).

Therefore, algorithms for the epigraph-Lagrange formulation face a problem similar to the strong duality challenge of the Lagrangian formulation (Section 4).
Proving strong duality or finding alternative ways to circumvent this challenge is a promising direction for future RCMDP research.

## Appendix D Additional definitions

Throughout this section, let $\mathcal{X}$ denote a set such that $\mathcal{X}\subset\mathbb{R}^{d}$ with $d\in\mathbb{N}$.

###### Definition D.1 (Subgradient (Kruger, 2003 ) ) .

Let $\mathcal{X}\subset\mathbb{R}^{d}$ be an open set where $d\in\mathbb{N}$.
The (Fréchet) subgradient of a function $f:\mathcal{X}\to\mathbb{R}$ at a point $x\in\mathcal{X}$ is defined as the set

$$ $\partial f(x)\vcentcolon\nolinebreak\mkern-1.2mu=\left\{u\in\mathcal{X} \mathchoice{\>}{\>}{\,}{\,}\middle|\allowbreak\mathchoice{\>}{\>}{\,}{\,} \mathopen{}\liminf_{x^{\prime}\to x,x^{\prime}\neq x}\frac{f(x^{\prime})-f(x)- \left\langle u,x^{\prime}-x\right\rangle}{\left\lVert x^{\prime}-x\right\rVert _{2}}\geq 0\right\}\;.$ $$

Furthermore, if $\partial f(\mathbf{x})$ is a singleton, its element is denoted as $\nabla f(\mathbf{x})$ and called the (Fréchet) gradient of $f$ at $x$.

###### Definition D.2 (Lipschitz continuity) .

Let $\ell\geq 0$.
A function $f:\mathcal{X}\to\mathbb{R}$ is $\ell$-Lipschitz if for any $x_{1},x_{2}\in\mathcal{X}$, we have that

$$ $\left\lVert f(x_{1})-f(x_{2})\right\rVert_{2}\leq\ell\left\lVert x_{1}-x_{2} \right\rVert_{2}\;.$ $$

###### Definition D.3 (Smoothness) .

Let $\ell\geq 0$.
A function $f:\mathcal{X}\to\mathbb{R}$ is $\ell$-smooth if for any $x_{1},x_{2}\in\mathcal{X}$, we have that

$$ $\left\lVert\nabla f(x_{1})-\nabla f(x_{2})\right\rVert_{2}\leq\ell\left\lVert x _{1}-x_{2}\right\rVert_{2}\;.$ $$

###### Definition D.4 (Weak convexity) .

Let $\ell>0$.
A function $f:\mathcal{X}\to\mathbb{R}$ is $\ell$-weakly convex if for any $g\in\partial f(x)$ and $x,x^{\prime}\in\mathcal{X}$,

$$ $f(x^{\prime})-f(x)\geq\langle g,x^{\prime}-x\rangle-\frac{\ell}{2}\left\lVert x ^{\prime}-x\right\rVert_{2}^{2}\;.$ $$

Note that $f(x)+\frac{\ell}{2}\left\lVert x\right\rVert_{2}^{2}$ is convex in $\mathcal{X}$ if and only if $f$ is $\ell$-weakly convex.

###### Definition D.5 (Moreau envelope of a weakly convex function) .

Given a $\ell$-weakly convex function $f:\mathcal{X}\to\mathbb{R}$ and a parameter $0<\tau<\ell^{-1}$, the Moreau envelope function of $f$ is given by $\operatorname{M}_{\tau}\circ\;f:\mathbb{R}^{d}\to\mathbb{R}$ such that

$$ $\left(\operatorname{M}_{\tau}\circ\;f\right)(x)=\min_{x^{\prime}\in\mathcal{X} }\left\{f(x^{\prime})+\frac{1}{2\tau}\left\|x-x^{\prime}\right\|^{2}_{2}\right \}\;.$ $$

###### Definition D.1 (Subgradient (Kruger, 2003 ) ) .

###### Definition D.2 (Lipschitz continuity) .

###### Definition D.3 (Smoothness) .

###### Definition D.4 (Weak convexity) .

###### Definition D.5 (Moreau envelope of a weakly convex function) .

## Appendix E Useful Lemmas

Throughout this section, $\mathcal{X}$ denotes a compact set such that $\mathcal{X}\subset\mathbb{R}^{d}$, where $d\in\mathbb{N}$.

###### Lemma E.1 ( Lemma D.2. in Wang et al. ( 2023 ) ) .

Let $\ell\geq 0$ and $h:\mathcal{X}\rightarrow\mathbb{R}$ be an $\ell$-smooth function. Then, $h$ is a $\ell$-weakly convex function.

###### Lemma E.2 (e.g., Proposition 13.37 in Rockafellar & Wets ( 2009 ) ) .

Let $f:\mathcal{X}\to\mathbb{R}$ be an $\ell$-weakly convex function, and let $0<\tau<\ell$ be a parameter.
The Moreau envelope function $\operatorname{M}_{\tau}\circ\;f:\mathbb{R}^{d}\to\mathbb{R}$ is differentiable, and its gradient is given by

$$ $\nabla(\operatorname{M}_{\tau}\circ\;f)(x)=\frac{1}{\tau}\left(x-\operatorname *{arg\,min}_{x^{\prime}\in\mathcal{X}}\left(f(x^{\prime})+\frac{1}{2\tau}\left \lVert x-x^{\prime}\right\rVert_{2}^{2}\right)\right)\;.$ $$

###### Lemma E.3 (Sion’s minimax theorem (Sion, 1958 ) ) .

Let $n,m\in\mathbb{N}$.
Let $\mathcal{X}\subset\mathbb{R}^{n}$ be a compact convex set and $\mathcal{Y}\subset\mathbb{R}^{m}$ a convex set.
Suppose that $f:\mathcal{X}\times\mathcal{Y}\to\mathbb{R}$ satisfies the following two properties:

- •
$f(x,\cdot)$ is upper semicontinuous and quasi-concave on $\mathcal{Y}$ for any $x\in\mathcal{X}$.
- •
$f(\cdot,y)$ is lower semicontinuous and quasi-convex on $\mathcal{X}$ for any $y\in\mathcal{Y}$.

Then,
$\min_{x\in\mathcal{X}}\sup_{y\in\mathcal{Y}}f(x,y)=\sup_{y\in\mathcal{Y}}\min_
{x\in\mathcal{X}}f(x,y)$.

###### Lemma E.4 (e.g., Problem 9.13, Page 99 in Clarke et al. ( 2008 ) ) .

Let $\mathcal{Y}\subset\mathbb{R}^{m}$ be a compact set and $f:\mathbb{R}^{d}\times\mathcal{Y}\to\mathbb{R}$ be a continuous function of two arguments.
Consider a point $\bar{x}\in\mathbb{R}^{d}$ and let $\Omega(\bar{x})\subset\mathbb{R}^{d}$ be its neighborhood.
For any $(x,y)\in\Omega(\bar{x})\times\mathcal{Y}$, suppose that the gradient $\nabla_{x}f(x,y)$ exists and is jointly continuous.

Let $h(\bar{x})\vcentcolon\nolinebreak\mkern-1.2mu=\max_{y\in\mathcal{Y}}f(\bar{x},y)$.
Then, the subgradient of $h$ at $\bar{x}$ is given by

$$ $\partial h(\bar{x})=\operatorname{conv}\left\{\nabla_{x}f(\bar{x},y) \mathchoice{\>}{\>}{\,}{\,}\middle|\allowbreak\mathchoice{\>}{\>}{\,}{\,} \mathopen{}y\in\operatorname*{arg\,max}_{y\in\mathcal{Y}}f(\bar{x},y)\right\}\;.$ $$

###### Lemma E.5 .

Let $N\in\mathbb{N}$.
Let $f_{i}:\mathcal{X}\to\mathbb{R}$ for $i\in\llbracket 1,N\rrbracket$ be $\ell$-weakly convex functions for some $\ell\geq 0$.
Define the pointwise maximum function $f:\mathcal{X}\to\mathbb{R}$ as

$$ $f(x)=\max\left\{f_{1}(x),\cdots,f_{N}(x)\right\}\quad\forall x\in\mathcal{X}\;.$ $$

Then, for any $x\in\mathcal{X}$,

$$ $\partial f(x)=\operatorname{conv}\left\{g\in\mathbb{R}^{d}\mathchoice{\>}{\>}{ \,}{\,}\middle|\allowbreak\mathchoice{\>}{\>}{\,}{\,}\mathopen{}g\in\partial f _{i}(x),f_{i}(x)=f(x)\right\}\;.$ $$

###### Proof.

The claim directly follows from Theorem 1.3 and Theorem 1.5 in Mikhalevich et al. ().
∎

###### Lemma E.6 (Maximum difference inequality) .

Let $N\in\mathbb{N}$.
For two sets of real numbers $\left\{x_{i}\right\}_{i\in\llbracket 1,N\rrbracket}$ and $\left\{y_{i}\right\}_{i\in\llbracket 1,N\rrbracket}$, where $x_{i},y_{i}\in\mathbb{R}$,

$$ $\left\lvert\max_{i\in\llbracket 1,N\rrbracket}x_{i}-\max_{i^{\prime}\in \llbracket 1,N\rrbracket}y_{i^{\prime}}\right\rvert\leq\max_{i\in\llbracket 1, N\rrbracket}\left\lvert x_{i}-y_{i}\right\rvert\;.$ $$

###### Proof.

For any $i\in\llbracket 1,N\rrbracket$,

$$ $\displaystyle\max_{i\in\llbracket 1,N\rrbracket}x_{i}=\max_{i\in\llbracket 1,N \rrbracket}x_{i}-y_{i}+y_{i}\leq\max_{i\in\llbracket 1,N\rrbracket}(x_{i}-y_{i })+\max_{i^{\prime}\in\llbracket 1,N\rrbracket}y_{i^{\prime}}$ $\displaystyle\Longrightarrow$ $\displaystyle\max_{i\in\llbracket 1,N\rrbracket}x_{i}-\max_{i^{\prime}\in \llbracket 1,N\rrbracket}y_{i^{\prime}}\leq\max_{i\in\llbracket 1,N\rrbracket} x_{i}-y_{i}\;.$ $$

By the symmetry of $x_{i}$ and $y_{i}$, we have
$\max_{i\in\llbracket 1,N\rrbracket}y_{i}-\max_{i^{\prime}\in\llbracket 1,N
\rrbracket}x_{i^{\prime}}\leq\max_{i\in\llbracket 1,N\rrbracket}y_{i}-x_{i}$.
Therefore,

$$ $\left\lvert\max_{i\in\llbracket 1,N\rrbracket}x_{i}-\max_{i^{\prime}\in \llbracket 1,N\rrbracket}y_{i^{\prime}}\right\rvert\leq\max_{i\in\llbracket 1, N\rrbracket}\left\lvert x_{i}-y_{i}\right\rvert\;.$ $$

∎

###### Lemma E.7 (Point-wise maximum preserves weak convexity) .

Let $h:\mathcal{X}\to\mathbb{R}$ and $f:\mathcal{X}\to\mathbb{R}$ be $\ell_{h}$- and $\ell_{f}$-weakly convex functions, respectively.
Then, $g:\mathcal{X}\to\mathbb{R}$ defined by $g(x)=\max\{h(x),f(x)\}$ for any $x\in\mathcal{X}$ is $\ell$-weakly convex, where $\ell\vcentcolon\nolinebreak\mkern-1.2mu=\max\{\ell_{h},\ell_{f}\}$.

###### Proof.

By the definition of weak convexity, for any $\theta\in[0,1]$ and $x,y\in\mathcal{X}$,

$$ $\displaystyle h(\theta x+(1-\theta)y)+\frac{\ell_{h}}{2}\left\lVert\theta x+(1 -\theta)y\right\rVert^{2}_{2}\leq\theta\left(h(x)+\frac{\ell_{h}}{2}\left \lVert x\right\rVert^{2}_{2}\right)+(1-\theta)\left(h(y)+\frac{\ell_{h}}{2} \left\lVert y\right\rVert^{2}_{2}\right)\;.$ $$

A similar inequality holds for $f$.
Then,

$$ $\displaystyle g(\theta x+(1-\theta)y)+\frac{\ell}{2}\left\lVert\theta x+(1- \theta)y\right\rVert^{2}_{2}$ $\displaystyle=$ $\displaystyle\max\{h(\theta x+(1-\theta)y),f(\theta x+(1-\theta)y)\}+\frac{ \ell}{2}\left\lVert\theta x+(1-\theta)y\right\rVert^{2}_{2}$ $\displaystyle=$ $\displaystyle\max\left\{h(\theta x+(1-\theta)y)+\frac{\ell}{2}\left\lVert \theta x+(1-\theta)y\right\rVert^{2}_{2},f(\theta x+(1-\theta)y)+\frac{\ell}{2 }\left\lVert\theta x+(1-\theta)y\right\rVert^{2}_{2}\right\}$ $\displaystyle\leq$ $\displaystyle\max\left\{\theta h(x)+(1-\theta)h(y)+\frac{\ell}{2}\left(\theta \left\lVert x\right\rVert^{2}_{2}+(1-\theta)\left\lVert y\right\rVert^{2}_{2} \right),\theta f(x)+(1-\theta)f(y)+\frac{\ell}{2}\left(\theta\left\lVert x \right\rVert^{2}_{2}+(1-\theta)\left\lVert y\right\rVert^{2}_{2}\right)\right\}$ $\displaystyle=$ $\displaystyle\max\left\{\theta h(x)+(1-\theta)h(y),\theta f(x)+(1-\theta)f(y) \right\}+\frac{\ell}{2}\left(\theta\left\lVert x\right\rVert^{2}_{2}+(1-\theta )\left\lVert y\right\rVert^{2}_{2}\right)$ $\displaystyle\leq$ $\displaystyle\theta\left(\max\left\{h(x),f(x)\right\}+\frac{\ell}{2}\left \lVert x\right\rVert_{2}^{2}\right)+(1-\theta)\left(\max\left\{h(y),f(y)\right \}+\frac{\ell}{2}\left\lVert y\right\rVert^{2}_{2}\right)$ $\displaystyle=$ $\displaystyle\theta\left(g(x)+\frac{\ell}{2}\left\lVert x\right\rVert_{2}^{2} \right)+(1-\theta)\left(g(y)+\frac{\ell}{2}\left\lVert y\right\rVert_{2}^{2} \right)\;.$ $$

Therefore, $g$ is $\ell$-weakly convex.
∎

###### Lemma E.8 .

Let $N_{\mathcal{X}}(x)$ be the normal cone of $\mathcal{X}$ at $x\in\mathcal{X}$, defined as

$$ $N_{\mathcal{X}}(x)\vcentcolon\nolinebreak\mkern-1.2mu=\left\{g\in\mathbb{R}^{d }\mathchoice{\>}{\>}{\,}{\,}\middle|\allowbreak\mathchoice{\>}{\>}{\,}{\,} \mathopen{}\langle g,y\rangle\leq\langle g,x\rangle\quad\forall y\in\mathcal{X }\right\}\;.$ $$

Define the indicator function $\mathbb{I}_{\mathcal{X}}:\mathbb{R}^{d}\to\mathbb{R}$ such that

$$ $\mathbb{I}_{\mathcal{X}}(x)=\begin{cases}0&\text{ if }\;x\in\mathcal{X}\\ \infty&\text{ otherwise }\end{cases}\;.$ $$

Then, $\partial\mathbb{I}_{\mathcal{X}}(x)=N_{\mathcal{X}}(x)$ for any $x\in\mathcal{X}$.

###### Proof.

Note that any $g\in\partial\mathbb{I}_{\mathcal{X}}(x)$ satisfies

$$ $\mathbb{I}_{\mathcal{X}}(y)\geq\mathbb{I}_{\mathcal{X}}(x)+\langle g,y-x \rangle\quad\forall y\in\mathbb{R}^{d}\;.$ (17) $$

Suppose that $g\notin N_{\mathcal{X}}(x)$.
Then, there exists $y^{\prime}\in\mathcal{X}$ such that $\langle g,x\rangle<\langle g,y^{\prime}\rangle$, which contradicts Equation 17.
Therefore, $g\in N_{\mathcal{X}}(x)$ for any $g\in\partial\mathbb{I}_{\mathcal{X}}(x)$ and thus $\partial\mathbb{I}_{\mathcal{X}}(x)\subseteq N_{\mathcal{X}}(x)$.

Consider $g\in N_{\mathcal{X}}(x)$.
It satisfies $0\geq\langle g,y-x\rangle$ for any $y\in\mathcal{X}$.
Since $x\in\mathcal{X}$ and by the definition of $\mathbb{I}_{\mathcal{X}}$, Equation 17 holds for any $y\in\mathbb{R}^{d}$.
Therefore, $N_{\mathcal{X}}(x)\subseteq\partial\mathbb{I}_{\mathcal{X}}(x)$.
This concludes the proof.
∎

###### Lemma E.9 .

Let $h:\mathcal{X}\to\mathbb{R}$ be an $\ell$-weakly convex function.
For $0<\tau<1/\ell$, define

$$ $\macc@depth\char 1\relax\frozen@everymath{\macc@group}\macc@set@skewchar \macc@nested@a 111{x}_{\tau}\in\operatorname*{arg\,min}_{x^{\prime}\in\mathcal {X}}h(x^{\prime})+\frac{1}{2\tau}\left\lVert x-x^{\prime}\right\rVert^{2}_{2}\;.$ $$

Then, there exists a subgradient $g\in\partial h(\macc@depth\char 1\relax\frozen@everymath{\macc@group}
\macc@set@skewchar\macc@nested@a 111{x}_{\tau})$ such that, for any $y\in\mathcal{X}$,

$$ $\left\langle g,\macc@depth\char 1\relax\frozen@everymath{\macc@group} \macc@set@skewchar\macc@nested@a 111{x}_{\tau}-y\right\rangle\leq\left\langle \nabla(\operatorname{M}_{\tau}\circ\;h)(x),\macc@depth\char 1\relax \frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a 111{x}_{\tau}-y\right\rangle$ $$

###### Proof.

Let $f:\mathbb{R}^{d}\to\mathbb{R}$ be a function such that $f(x)=h(x)+\mathbb{I}_{\mathcal{X}}(x)$.

The Moreau envelope function of $f$ satisfies that, for any $x\in\mathbb{R}^{d}$,

$$ $\left(\operatorname{M}_{\tau}\circ\;f\right)(x)=\min_{x^{\prime}\in\mathbb{R}^ {d}}\left\{h(x^{\prime})+\mathbb{I}_{\mathcal{X}}(x^{\prime})+\frac{1}{2\tau} \left\lVert x-x^{\prime}\right\rVert^{2}_{2}\right\}=\min_{x^{\prime}\in \mathcal{X}}\left\{h(x^{\prime})+\frac{1}{2\tau}\left\lVert x-x^{\prime}\right \rVert^{2}_{2}\right\}\;.$ $$

It holds that $\nabla\left(\operatorname{M}_{\tau}\circ\;f\right)(x)=\frac{1}{\tau}(x-
\macc@depth\char 1\relax\frozen@everymath{\macc@group}\macc@set@skewchar
\macc@nested@a 111{x}_{\tau})$ due to Lemma E.2.

Note that

$$ $\macc@depth\char 1\relax\frozen@everymath{\macc@group}\macc@set@skewchar \macc@nested@a 111{x}_{\tau}\in\operatorname*{arg\,min}_{x^{\prime}\in\mathcal {X}}h(x^{\prime})+\frac{1}{2\tau}\left\lVert x-x^{\prime}\right\rVert^{2}_{2}= \operatorname*{arg\,min}_{x^{\prime}\in\mathbb{R}^{d}}h(x^{\prime})+\mathbb{I} _{\mathcal{X}}(x^{\prime})+\frac{1}{2\tau}\left\lVert x-x^{\prime}\right\rVert ^{2}_{2}\;.$ $$

It is clear that $\macc@depth\char 1\relax\frozen@everymath{\macc@group}\macc@set@skewchar
\macc@nested@a 111{x}_{\tau}$ is a minimizer of the function $\phi_{x}(x^{\prime})\vcentcolon\nolinebreak\mkern-1.2mu=h(x^{\prime})+\mathbb{
I}_{\mathcal{X}}(x^{\prime})+\frac{1}{2\tau}\left\lVert x-x^{\prime}\right
\rVert^{2}_{2}$.
Therefore, it holds that $\mathbf{0}\in\partial\phi_{x}(\macc@depth\char 1\relax\frozen@everymath{
\macc@group}\macc@set@skewchar\macc@nested@a 111{x}_{\tau})$. Accordingly,

$$ $\left.\mathbf{0}\in\partial\left(h(y)+\mathbb{I}_{\mathcal{X}}(y)+\frac{1}{2 \tau}\left\lVert x-y\right\rVert_{2}^{2}\right)\right|_{y=\macc@depth\char 1 \relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a 111{x}_{ \tau}}\Longrightarrow-\frac{1}{\tau}\left(\macc@depth\char 1\relax \frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a 111{x}_{\tau}-x \right)\in\left.\partial\left(h(y)+\mathbb{I}_{\mathcal{X}}(y)\right)\right|_{ y=\macc@depth\char 1\relax\frozen@everymath{\macc@group}\macc@set@skewchar \macc@nested@a 111{x}_{\tau}}\;.$ $$

Due to Lemma E.8, $\partial\mathbb{I}_{\mathcal{X}}(x)=N_{\mathcal{X}}(x)$.
Therefore, there exists a subgradient $g\in\partial h(\macc@depth\char 1\relax\frozen@everymath{\macc@group}
\macc@set@skewchar\macc@nested@a 111{x}_{\tau})$ such that

$$ $-g-\frac{1}{\tau}(\macc@depth\char 1\relax\frozen@everymath{\macc@group} \macc@set@skewchar\macc@nested@a 111{x}_{\tau}-x)\in N_{\mathcal{X}}( \macc@depth\char 1\relax\frozen@everymath{\macc@group}\macc@set@skewchar \macc@nested@a 111{x}_{\tau})\;.$ $$

Since any $z\in N_{\mathcal{X}}(\macc@depth\char 1\relax\frozen@everymath{\macc@group}
\macc@set@skewchar\macc@nested@a 111{x}_{\tau})$ satisfies $\langle z,y-\macc@depth\char 1\relax\frozen@everymath{\macc@group}
\macc@set@skewchar\macc@nested@a 111{x}_{\tau}\rangle\leq 0$ for any $y\in\mathcal{X}$, it holds that

$$ $\left\langle-g,y-\macc@depth\char 1\relax\frozen@everymath{\macc@group} \macc@set@skewchar\macc@nested@a 111{x}_{\tau}\right\rangle\leq\left\langle \frac{1}{\tau}\left(\macc@depth\char 1\relax\frozen@everymath{\macc@group} \macc@set@skewchar\macc@nested@a 111{x}_{\tau}-x\right),y-\macc@depth\char 1 \relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a 111{x}_{ \tau}\right\rangle,\quad\forall y\in\mathcal{X}\;.$ $$

Then the claim follows from the fact that $\frac{1}{\tau}\left(x-\macc@depth\char 1\relax\frozen@everymath{\macc@group}
\macc@set@skewchar\macc@nested@a 111{x}_{\tau}\right)=\nabla(\operatorname{M}_
{\tau}\circ\;h)(x)$ due to Lemma E.2.
∎

###### Lemma E.10 (Linear optimization on convex hull) .

Given $c\in\mathbb{R}^{d}$ and a compact set $\mathcal{X}\subset\mathbb{R}^{d}$, it holds that

$$ $\min_{x\in\mathcal{X}}\langle c,x\rangle=\min_{x\in\operatorname{conv}\{ \mathcal{X}\}}\langle c,x\rangle\;.$ $$

###### Proof.

Let $x^{\star}\in\operatorname*{arg\,min}_{x\in\operatorname{conv}\{\mathcal{X}\}}
\langle c,x\rangle$.
The claim holds for $x^{\star}\in\mathcal{X}$.
Suppose that $x^{\star}\notin\mathcal{X}$. Then, by the definition of the convex hull, there exist $y,z\in\mathcal{X}$ and $\theta\in(0,1)$ such that $y\neq z$ and

$$ $x^{\star}=\theta y+(1-\theta)z\;.$ $$

Since $x^{\star}$ is a minimizer, we have

$$ $\langle c,x^{\star}\rangle\leq\langle c,y\rangle\;\text{ and }\;\langle c,x^{ \star}\rangle\leq\langle c,z\rangle\;.$ $$

Accordingly,

$$ $\langle c,x^{\star}\rangle=\theta\langle c,x^{\star}\rangle+(1-\theta)\langle c ,x^{\star}\rangle\leq\theta\langle c,y\rangle+(1-\theta)\langle c,z\rangle= \langle c,x^{\star}\rangle\;.$ $$

The inequality must be an equality, and thus

$$ $\theta\underbrace{\left(\langle c,y\rangle-\langle c,x^{\star}\rangle\right)}_ {\geq 0}+(1-\theta)\underbrace{\left(\langle c,z\rangle-\langle c,x^{\star} \rangle\right)}_{\geq 0}=0\;.$ $$

Since $\theta\in(0,1)$, it holds that

$$ $\langle c,y\rangle=\langle c,z\rangle=\langle c,x^{\star}\rangle\;.$ $$

The above equality means that both $y$ and $z\in\mathcal{X}$ satisfy $\langle c,y\rangle=\langle c,z\rangle=\min_{x\in\operatorname{conv}\{\mathcal{
X}\}}\langle c,x\rangle$.
Therefore, $\min_{x\in\mathcal{X}}\langle c,x\rangle=\min_{x\in\operatorname{conv}\{
\mathcal{X}\}}\langle c,x\rangle$.
∎

###### Lemma E.1 ( Lemma D.2. in Wang et al. ( 2023 ) ) .

###### Lemma E.2 (e.g., Proposition 13.37 in Rockafellar & Wets ( 2009 ) ) .

###### Lemma E.3 (Sion’s minimax theorem (Sion, 1958 ) ) .

###### Lemma E.4 (e.g., Problem 9.13, Page 99 in Clarke et al. ( 2008 ) ) .

###### Lemma E.5 .

###### Proof.

###### Lemma E.6 (Maximum difference inequality) .

###### Proof.

###### Lemma E.7 (Point-wise maximum preserves weak convexity) .

###### Proof.

###### Lemma E.8 .

###### Proof.

###### Lemma E.9 .

###### Proof.

###### Lemma E.10 (Linear optimization on convex hull) .

###### Proof.

## Appendix F Useful Lemmas for MDPs

###### Lemma F.1 ( Lemma 3.1 in Wang et al. ( 2023 ) ) .

Let

$$ $\displaystyle\ell_{\mathrm{Lp}}\vcentcolon\nolinebreak\mkern-1.2mu=H^{2}\sqrt{ A}\quad\mathrm{and}\quad\ell_{\mathrm{sm}}\vcentcolon\nolinebreak\mkern-1.2mu= 2\gamma AH^{3}\;.$ $$

For any $\pi,\pi^{\prime}\in\Pi$, $P:\mathcal{S}\times\mathcal{A}\to\mathscr{P}(\mathcal{S})$, $\mu\in\mathscr{P}(\mathcal{S})$, and $n\in\llbracket 0,N\rrbracket$,

$$ $\displaystyle\left\lvert J_{n,P}(\pi)-J_{n,P}(\pi^{\prime})\right\rvert\leq \ell_{\mathrm{Lp}}\left\lVert\pi-\pi^{\prime}\right\rVert_{2}\;,\;\left\lVert \nabla J_{n,P}(\pi)-\nabla J_{n,P}(\pi)\right\rVert_{2}\leq\ell_{\mathrm{sm}} \left\lVert\pi-\pi^{\prime}\right\rVert_{2}\;,$ and $\displaystyle\left\lvert J_{n,\mathcal{U}}(\pi)-J_{n,\mathcal{U}}(\pi)\right \rvert\leq\ell_{\mathrm{Lp}}\left\lVert\pi-\pi^{\prime}\right\rVert_{2}\;.\;$ $$

Furthermore, $J_{n,P}(\pi)$ is $\ell_{\mathrm{sm}}$-weakly convex in $\Pi$, as follows directly from Lemma E.1.

###### Lemma F.2 (e.g., Lemma 4.1 in Agarwal et al. ( 2021 ) and Lemma E.2 in Wang et al. ( 2023 ) ) .

Let $\mu\in\mathscr{P}(\mathcal{S})$ such that $\min_{s\in\mathcal{S}}\mu(s)>0$.
For any $\pi\in\Pi$, $P:\mathcal{S}\times\mathcal{A}\to\mathscr{P}(\mathcal{S})$, and $n\in\llbracket 0,N\rrbracket$,

$$ $J_{n,P}(\pi)-J_{n,P}(\pi^{\star}_{n,P})\leq H\left\lVert\frac{d^{\pi^{\star}_{ n,P}}_{P}}{\mu}\right\rVert_{\infty}\max_{\pi^{\prime}\in\Pi}\left\langle\pi- \pi^{\prime},\nabla J_{n,P}(\pi)\right\rangle\;,$ $$

where $\pi^{\star}_{n,P}\in\operatorname*{arg\,min}_{\pi^{\prime}\in\Pi}J_{n,P}(\pi^{
\prime})$.

###### Lemma F.1 ( Lemma 3.1 in Wang et al. ( 2023 ) ) .

###### Lemma F.2 (e.g., Lemma 4.1 in Agarwal et al. ( 2021 ) and Lemma E.2 in Wang et al. ( 2023 ) ) .

## Appendix G Proof of Theorem 4.1

###### Proof of Theorem 4.1 .

Consider the deterministic RCMDP shown in Figure 1(a) with $N=1$, $\mathcal{U}=\{P_{1},P_{2}\}$, $\mathcal{S}=\{s_{1},s_{2},s_{3},s_{4}\}$, and $\mathcal{A}=\{a_{1},a_{2}\}$.
Set the initial distribution such that $\mu(s_{1})=\mu(s_{2})=\mu(s_{3})=\mu(s_{4})=1/4$.

###### Proof of Theorem 4.1 .

#### First part of Theorem 4.1 .

Set $\lambda=1$.
The threshold $b_{1}$ can be arbitrary.

Let $\pi_{1}$ and $\pi_{2}$ be two policies such that $\pi_{1}$ always chooses $a_{1}$ and $\pi_{2}$ always chooses $a_{2}$ in any state.
For any $\delta>0$, we will show two results:

- •
Equation 19: $L_{\lambda}(\pi_{2})-\min_{\pi\in\Pi}L_{\lambda}(\pi)\geq\frac{H\gamma}{4}-
\frac{3H\delta}{4}$ .
- •
Equation 21: $\left(\nabla L_{\lambda}(\pi_{2})\right)(\cdot,a_{1})>\left(\nabla L_{\lambda}
(\pi_{2})\right)(\cdot,a_{2})$.

The former shows the suboptimality of $\pi_{2}$, and the latter indicates that $\pi_{2}$ is a local minimum.

According to the RCMDP construction, for any $\pi\in\Pi$, we have

$$ $\displaystyle\mu(s_{3})V^{\pi}_{0,P_{1}}(s_{3})+\mu(s_{4})V^{\pi}_{0,P_{1}}(s_ {4})=\frac{H}{4}(1+\gamma)\;,$ $\displaystyle\mu(s_{3})V^{\pi}_{0,P_{2}}(s_{3})+\mu(s_{4})V^{\pi}_{0,P_{2}}(s_ {4})=\frac{H}{4}(1-\gamma)\;,$ $\displaystyle\mu(s_{3})V^{\pi}_{1,P_{1}}(s_{3})+\mu(s_{4})V^{\pi}_{1,P_{1}}(s_ {4})=\frac{H}{4}(1-\gamma)\;,$ $\displaystyle\mu(s_{3})V^{\pi}_{1,P_{2}}(s_{3})+\mu(s_{4})V^{\pi}_{1,P_{2}}(s_ {4})=\frac{H}{4}(1+\gamma)\;.$ $$

For $\pi_{1}$ and $\pi_{2}$, it is easy to verify that

$$ $\displaystyle\mu(s_{1})V^{\pi_{1}}_{0,P_{1}}(s_{1})+\mu(s_{2})V^{\pi_{1}}_{0,P _{1}}(s_{2})=\frac{1}{4}\left(\delta+\gamma+\gamma^{2}\delta+\cdots\right)+ \frac{1}{4}\left(1+\gamma\delta+\gamma^{2}+\cdots\right)=\frac{H}{4}(1+\delta)\;,$ $\displaystyle\mu(s_{1})V^{\pi_{1}}_{0,P_{2}}(s_{1})+\mu(s_{2})V^{\pi_{1}}_{0,P _{2}}(s_{2})=\frac{1}{4}\left(\delta+\gamma+\gamma^{2}+\cdots\right)+\frac{1}{ 4}\left(1+\gamma+\gamma^{2}+\cdots\right)=\frac{H}{4}(1+\gamma)+\frac{\delta}{ 4}\;,$ $\displaystyle\mu(s_{1})V^{\pi_{1}}_{1,P_{1}}(s_{1})+\mu(s_{2})V^{\pi_{1}}_{1,P _{1}}(s_{2})=\frac{H}{2}\;,\quad\mu(s_{1})V^{\pi_{1}}_{1,P_{2}}(s_{1})+\mu(s_{ 2})V^{\pi_{1}}_{1,P_{2}}(s_{2})=\frac{H}{2}\;,$ $\displaystyle\mu(s_{1})V^{\pi_{2}}_{0,P_{1}}(s_{1})+\mu(s_{2})V^{\pi_{2}}_{0,P _{1}}(s_{2})=\frac{H}{2}\;,\quad\mu(s_{1})V^{\pi_{2}}_{0,P_{2}}(s_{1})+\mu(s_{ 2})V^{\pi_{2}}_{0,P_{2}}(s_{2})=\frac{H}{2}\;,$ $\displaystyle\mu(s_{1})V^{\pi_{2}}_{1,P_{1}}(s_{1})+\mu(s_{2})V^{\pi_{2}}_{1,P _{1}}(s_{2})=\frac{H}{4}(1+\gamma-2\delta)\;,$ $\displaystyle\mu(s_{1})V^{\pi_{2}}_{1,P_{2}}(s_{1})+\mu(s_{2})V^{\pi_{2}}_{1,P _{2}}(s_{2})=\frac{H}{4}(1+\gamma-2\delta)\;.$ $$

Therefore,

$$ $\displaystyle J_{0,P_{1}}(\pi_{1})$ $\displaystyle=\frac{H}{2}+\frac{H}{4}\left(\gamma+\delta\right)\;,\quad J_{0,P _{2}}(\pi_{1})=\frac{H}{2}+\frac{\delta}{4}\;,$ (18) $\displaystyle J_{1,P_{1}}(\pi_{1})$ $\displaystyle=\frac{H}{4}\left(3-\gamma\right)\;,\quad J_{1,P_{2}}(\pi_{1})= \frac{H}{4}\left(3+\gamma\right)\;,$ $\displaystyle J_{0,P_{1}}(\pi_{2})$ $\displaystyle=\frac{H}{4}\left(3+\gamma\right)\;,\quad J_{0,P_{2}}(\pi_{2})= \frac{H}{4}\left(3-\gamma\right)\;,$ $\displaystyle J_{1,P_{1}}(\pi_{2})$ $\displaystyle=\frac{H}{2}-\frac{H\delta}{2}\;,\quad J_{1,P_{2}}(\pi_{2})=\frac {H}{2}+\frac{H\gamma}{2}-\frac{H\delta}{2}\;,$ $$

Hence,

$$ $\displaystyle J_{0,\mathcal{U}}(\pi_{1})$ $\displaystyle=J_{0,P_{1}}(\pi_{1})=\frac{H}{2}+\frac{H\gamma}{4}+\frac{H\delta }{4}\;,\quad J_{1,\mathcal{U}}(\pi_{1})=J_{1,P_{2}}(\pi_{1})=\frac{H}{4}\left( 3+\gamma\right)\;,$ $\displaystyle J_{0,\mathcal{U}}(\pi_{2})$ $\displaystyle=J_{0,P_{1}}(\pi_{2})=\frac{H}{4}\left(3+\gamma\right)\;,\quad J_ {1,\mathcal{U}}(\pi_{2})=J_{1,P_{2}}(\pi_{2})=\frac{H}{2}+\frac{H\gamma}{2}- \frac{H\delta}{2}\;.$ $$

Accordingly, since $\lambda=1$, we have

$$ $L_{\lambda}(\pi_{2})-\min_{\pi\in\Pi}L_{\lambda}(\pi)\geq L_{\lambda}(\pi_{2}) -L_{\lambda}(\pi_{1})\geq\frac{H\gamma}{4}-\frac{3H\delta}{4}\;.$ (19) $$

The next task is to show that $\left(\nabla L_{\lambda}(\pi_{2})\right)(\cdot,a_{1})>\left(\nabla L_{\lambda}
(\pi_{2})\right)(\cdot,a_{2})$.

By using Lemma E.5, it is easy to show that

$$ $\nabla L_{\lambda}(\pi_{2})=\nabla J_{0,P_{1}}(\pi_{2})+\nabla J_{1,P_{2}}(\pi _{2})\;.$ $$

Since $d^{\pi_{2}}_{P_{1}}(s)=d^{\pi_{2}}_{P_{2}}(s)=0.25\mathbf{1}$ and due to Lemma 3.1, we have

$$ $\frac{4}{H}\nabla L_{\lambda}(\pi_{2})=Q^{\pi_{2}}_{0,P_{1}}+Q^{\pi_{2}}_{1,P_ {2}}\;.$ $$

Note that

$$ $\displaystyle\frac{4}{H}\left(\nabla L_{\lambda}(\pi_{2})\right)(s_{1},a_{1})$ $\displaystyle=Q^{\pi_{2}}_{0,P_{1}}(s_{1},a_{1})+Q^{\pi_{2}}_{1,P_{2}}(s_{1},a _{1})=\left(\delta+H\gamma\right)+\left(H-H\gamma\delta\right)\;,$ (20) $\displaystyle\frac{4}{H}\left(\nabla L_{\lambda}(\pi_{2})\right)(s_{1},a_{2})$ $\displaystyle=Q^{\pi_{2}}_{0,P_{1}}(s_{1},a_{2})+Q^{\pi_{2}}_{1,P_{2}}(s_{1},a _{2})=H+H(\gamma-\delta)\;,$ $\displaystyle\frac{4}{H}\left(\nabla L_{\lambda}(\pi_{2})\right)(s_{2},a_{1})$ $\displaystyle=Q^{\pi_{2}}_{0,P_{1}}(s_{2},a_{1})+Q^{\pi_{2}}_{1,P_{2}}(s_{2},a _{1})=2H\;,$ $\displaystyle\frac{4}{H}\left(\nabla L_{\lambda}(\pi_{2})\right)(s_{2},a_{2})$ $\displaystyle=Q^{\pi_{2}}_{0,P_{1}}(s_{2},a_{2})+Q^{\pi_{2}}_{1,P_{2}}(s_{2},a _{2})=2H(1-\delta)\;.$ $$

Therefore, since $\delta>0$,

$$ $\displaystyle\frac{4}{H}\left(\left(\nabla L_{\lambda}(\pi_{2})\right)(s_{1},a _{1})-\left(\nabla L_{\lambda}(\pi_{2})\right)(s_{1},a_{2})\right)$ $\displaystyle=\delta-H\gamma\delta+H\delta=\delta+H\delta(1-\gamma)>0\;,$ (21) $\displaystyle\frac{4}{H}\left(\left(\nabla L_{\lambda}(\pi_{2})\right)(s_{2},a _{1})-\left(\nabla L_{\lambda}(\pi_{2})\right)(s_{2},a_{2})\right)$ $\displaystyle=2H\delta>0\;.$ $$

Now, with a sufficiently small $R>0$, let $\widetilde{\Pi}_{2}\vcentcolon\nolinebreak\mkern-1.2mu=\left\{\pi\in\Pi
\mathchoice{\>}{\>}{\,}{\,}\middle|\allowbreak\mathchoice{\>}{\>}{\,}{\,}
\mathopen{}\left\lVert\pi-\pi_{2}\right\rVert_{2}\leq R,\;\pi\neq\pi_{2}\right\}$ be policies near $\pi_{2}$.
When $R$ is sufficiently small, due to the Lipshictz continuity of $J_{n,P}(\pi)$ by Lemma F.1,
Equation 18 indicates that

$$ $J_{0,\mathcal{U}}(\pi)=J_{0,P_{1}}(\pi)\;\text{ and }\;J_{1,\mathcal{U}}(\pi)= J_{1,P_{2}}(\pi)\quad\forall\pi\in\widetilde{\Pi}_{2}\;.$ (22) $$

Similarly, due to Equation 22 with the Lipshictz continuity of $\nabla J_{n,P}(\pi)$ by Lemma F.1, Equation 20 and Equation 21 indicate that,

$$ $\left(\nabla L_{\lambda}(\pi)\right)(\cdot,a_{1})>\left(\nabla L_{\lambda}(\pi )\right)(\cdot,a_{2})\quad\forall\pi\in\widetilde{\Pi}_{2}\;.$ $$

Therefore, since $\pi_{2}$ always chooses $a_{2}$, we have $L_{\lambda}(\pi_{2})<L_{\lambda}(\pi)\;\;\forall\pi\in\widetilde{\Pi}_{2}$ for a sufficiently small $R>0$.
The first part of the claim holds by setting $\delta=\gamma/4$ with Equation 19.

#### Second part of Theorem 4.1 .

Consider again the deterministic RCMDP given in the previous part of the proof with $\delta=\gamma/4$.
For a value $b_{1}\in\mathbb{R}$, define a function $\Psi_{b_{1}}:\mathbb{R}\to\mathbb{R}$ such that

$$ $\Psi_{b_{1}}(\lambda)=\min_{\pi\in\Pi}J_{0,\mathcal{U}}(\pi)+\lambda J_{1, \mathcal{U}}(\pi)-\lambda b_{1}=\min_{\pi\in\Pi}L_{\lambda}(\pi)\;.$ $$

Since $\mathcal{U}=\left\{P_{1},P_{2}\right\}$, Lemma E.5 and Lemma 3.1 indicates that, for any $\lambda\in\mathbb{R}$ and $b_{1}\in\mathbb{R}$,

$$ $\partial\Psi_{b_{1}}(\lambda)\subseteq\operatorname{conv}\left\{J_{1,P}(\pi)-b _{1}\mathchoice{\>}{\>}{\,}{\,}\middle|\allowbreak\mathchoice{\>}{\>}{\,}{\,} \mathopen{}\pi\in\Pi,P\in\{P_{1},P_{2}\}\}\;.Since\mu=\frac{1}{4}\cdot\mathbf{ 1}andduetotheconstructionoftheRCMDPin\lx@cref{creftype~refnum}{fig:non-grad-CM DP},itiseasytoverifythat,$ $$

$$ $Byinsertingthisto\lx@cref{creftype~refnum}{eq:Psi-subgrad-tmp1},forany\lambda \in\mathbb{R}andb_{1}\in\mathbb{R},$ $$

- b_1 ≤g ≤H - 14 - b_1  ∀g ∈∂Ψ_b_1(λ) .

$$ $\par Therefore,\begin{itemize} \par\itemize@item@$g\in\partial\Psi_{0}(\lambda)$ must satisfy $g\geq\frac{1}{ 4}$ for any $\lambda$. Thus, $\left\{\infty\right\}=\operatorname*{arg\,max}_{ \lambda\in\mathbb{R}_{+}}\Psi_{0}(\lambda)$. \par\itemize@item@$g\in\partial\Psi_{H}(\lambda)$ must satisfy $g\leq-\frac{1} {4}$ for any $\lambda$. Thus, $\left\{0\right\}=\operatorname*{arg\,max}_{ \lambda\in\mathbb{R}_{+}}\Psi_{H}(\lambda)$. \par\end{itemize}\par Now,define\lambda^{\star}_{b_{1}}\geq 0suchthat\lambda^{ \star}_{b_{1}}=\min\left\{\operatorname*{arg\,max}_{\lambda\in\mathbb{R}_{+}} \Psi_{b_{1}}(\lambda)\right\}.Since\Psi_{b_{1}}(\lambda)isconcavein\lambda, itiseasytoseethat\lambda^{\star}_{b_{1}}iscontinuousinb_{1}.Thus,since\lambda^ {\star}_{0}=0and\lambda^{\star}_{H}=\infty, theintermediatevaluetheoremindicatesthatthereexistsb_{1}\in(0,H)suchthat \lambda^{\star}_{b_{1}}=1.Thisconcludestheproof.\qed\end@proof\par$ (23) $$

## Appendix H Missing Proofs in Section 5

### H.1 Proofs of Lemma 5.2

###### Proof of Lemma 5.2 .

We prove the first claim.
Recall the definition of $\Delta^{\star}_{b_{0}}$:

$$ $\displaystyle\Delta^{\star}_{b_{0}}=\min_{\pi\in\Pi}\Delta_{b_{0}}(\pi)=\min_{ \pi\in\Pi}\max_{n\in\llbracket 0,N\rrbracket}J_{n,\mathcal{U}}(\pi)-b_{n}\;.$ (24) $$

It is easy to see that $\Delta_{b_{0}}(\pi)$ is monotonically decreasing in $b_{0}$.
Consider two real numbers $x\leq y$ and let $\pi^{x}\in\operatorname*{arg\,min}_{\pi\in\Pi}\Delta_{x}(\pi)$. Then,

$$ $\Delta^{\star}_{y}=\min_{\pi\in\Pi}\Delta_{y}(\pi)\leq\Delta_{y}(\pi^{x})\leq \Delta_{x}(\pi^{x})=\min_{\pi\in\Pi}\Delta_{x}(\pi)=\Delta^{\star}_{x}\;.$ $$

Therefore, $\Delta^{\star}_{b_{0}}$ is monotonically decreasing in $b_{0}$.

Next, we prove the second claim.
Suppose that $\Delta^{\star}_{\heartsuit}<0$.
Then, there exists a feasible policy $\pi\in\Pi_{\mathrm{F}}$ such that $J_{0,\mathcal{U}}(\pi)<\heartsuit=J_{0,\mathcal{U}}(\pi^{\star})$.
This contradicts the definition of the optimal policy.
Therefore, $\Delta^{\star}_{\heartsuit}\geq 0$.

Suppose that $\Delta^{\star}_{\heartsuit}>0$.
Since $\min_{\pi\in\Pi}\Delta_{\heartsuit}(\pi)>0$,
no feasible policy achieves the objective return $\heartsuit$.
This also contradicts the existence of the optimal policy.
Therefore, $\Delta^{\star}_{\heartsuit}=0$.
∎

###### Proof of Lemma 5.2 .

### H.2 Proofs of Theorem 5.1

###### Proof of Theorem 5.1 .

We first prove Equation 8 by contradiction.
Let $x\vcentcolon\nolinebreak\mkern-1.2mu=\min\left\{b_{0}\in[0,H]\mathchoice{\>}{
\>}{\,}{\,}\middle|\allowbreak\mathchoice{\>}{\>}{\,}{\,}\mathopen{}\Delta^{
\star}_{b_{0}}\leq 0\right\}$ and suppose that $x<\heartsuit$.
Since $\Delta^{\star}_{\heartsuit}=0$ by Lemma 5.2, there exists a feasible policy $\pi\in\Pi_{\mathrm{F}}$ such that $J_{0,\mathcal{U}}(\pi)\leq x<\heartsuit=J_{0,\mathcal{U}}(\pi^{\star})$.
This contradicts the definition of the optimal policy.

We then show that Equation 8 provides $\pi^{\star}$.
Since $\Delta^{\star}_{\heartsuit}=0$ by Lemma 5.2, any policy $\pi\in\operatorname*{arg\,min}_{\pi\in\Pi}\Delta_{b_{0}}(\pi)$ is feasible and satisfies $J_{0,\mathcal{U}}(\pi)=\heartsuit$.
The claim directly follows from the definition of an optimal policy.
∎

###### Proof of Theorem 5.1 .

### H.3 Proofs of Lemma 5.4

Instead of Lemma 5.4, we prove the following lemma that includes Lemma 5.4.

###### Lemma H.1 (Properties of $\Delta_{b_{0}}$ ) .

The following properties hold for any $b_{0}\in\mathbb{R}$.

- 1.
(Lipschitz continuity): For any $\pi,\pi^{\prime}\in\Pi$, $\left\lvert\Delta_{b_{0}}(\pi)-\Delta_{b_{0}}(\pi^{\prime})\right\rvert\leq
\ell_{\mathrm{Lp}}\left\lVert\pi-\pi^{\prime}\right\rVert_{2}$ with $\ell_{\mathrm{Lp}}\vcentcolon\nolinebreak\mkern-1.2mu=H^{2}\sqrt{A}$.
- 2.
(Weak convexity): $\Delta_{b_{0}}(\pi)+\frac{\ell_{\mathrm{sm}}}{2}\left\lVert\pi\right\rVert^{2}
_{2}$ is convex in $\pi$ with $\ell_{\mathrm{sm}}\vcentcolon\nolinebreak\mkern-1.2mu=2\gamma AH^{3}$.
- 3.
(Subdifferentiability):
For any $\pi\in\Pi$, the subgradient of $\Delta_{b_{0}}$ at $\pi$ is given by
$\partial\Delta_{b_{0}}(\pi)=\operatorname{conv}\left\{\nabla_{\pi}J_{n,P}(\pi)
\mathchoice{\>}{\>}{\,}{\,}\middle|\allowbreak\mathchoice{\>}{\>}{\,}{\,}
\mathopen{}n,P\in\mathcal{W}\right\}\;,$
where $\operatorname{conv}B$ represents the convex hull of a set $B\subset\mathbb{R}^{\mathcal{S}\times\mathcal{A}}$.

###### Proof of Lipschitz continuity.

$$ $\displaystyle\left\lvert\Delta_{b_{0}}(\pi)-\Delta_{b_{0}}(\pi^{\prime})\right\rvert$ $\displaystyle\leq\left\lvert\max_{n\in\llbracket 0,N\rrbracket}\left\{J_{n, \mathcal{U}}(\pi)-b_{n}\right\}-\max_{m\in\llbracket 0,N\rrbracket}\left\{J_{m ,\mathcal{U}}(\pi^{\prime})-b_{m}\right\}\right\rvert$ $\displaystyle\stackrel{{\scriptstyle\scriptscriptstyle(\mkern-1.5mua\mkern-1.5 mu)}}{{\leq}}\max_{n\in\llbracket 0,N\rrbracket}\left\lvert J_{n,\mathcal{U}}( \pi)-b_{n}-\left(J_{n,\mathcal{U}}(\pi^{\prime})-b_{n}\right)\right\rvert \stackrel{{\scriptstyle\scriptscriptstyle(\mkern-1.5mub\mkern-1.5mu)}}{{\leq}} \ell_{\mathrm{Lp}}\left\lVert\pi-\pi^{\prime}\right\rVert_{2}$ $$

where (a) uses Lemma E.6 and (b) is due to Lemma F.1.
This concludes the proof of the Lipschitz continuity.
∎

###### Proof of weak convexity.

The weak convexity of
$\Delta_{b_{0}}(\pi)=\max_{n\in\llbracket 0,N\rrbracket}J_{n,\mathcal{U}}(\pi)-
b_{n}$
immediately follows from the weak convexity of $J_{n,\mathcal{U}}(\pi)$ due to Lemma F.1 with Lemma E.7.
∎

###### Proof of subdifferentiability.

Suppose that $\mathcal{U}$ is a finite set. The claim directly follows from Lemma E.5 with the weak convexity of $J_{n,P}(\pi)$ due to Lemma F.1.

Suppose that $\mathcal{U}$ is a compact set such that, for any $\pi\in\Pi$, $\nabla J_{n,P}(\pi)$ is continuous with respect to $P\in\mathcal{U}$.
Danskin’s theorem (Lemma E.4) indicates that, for any $n\in\llbracket 0,N\rrbracket$,

$$ $\partial J_{n,\mathcal{U}}(\pi)=\operatorname{conv}\left\{\nabla J_{n,P}(\pi) \mathchoice{\>}{\>}{\,}{\,}\middle|\allowbreak\mathchoice{\>}{\>}{\,}{\,} \mathopen{}P\in\operatorname*{arg\,max}_{P\in\mathcal{U}}J_{n,P}(\pi)-b_{n} \right\}\;.$ $$

Then, using Lemma E.5 with the weak convexity of $J_{n,\mathcal{U}}(\pi)$ due to Lemma H.1, we have

$$ $\displaystyle\partial\Delta_{b_{0}}(\pi)$ $\displaystyle=\operatorname{conv}\left\{g\mathchoice{\>}{\>}{\,}{\,}\middle| \allowbreak\mathchoice{\>}{\>}{\,}{\,}\mathopen{}g\in\partial J_{n,\mathcal{U} }(\pi)\;\text{ where }\;n\in\operatorname*{arg\,max}_{n\in\llbracket 0,N \rrbracket}J_{n,\mathcal{U}}(\pi)-b_{n}\right\}$ $\displaystyle=\operatorname{conv}\left\{\nabla J_{n,P}(\pi)\mathchoice{\>}{\>} {\,}{\,}\middle|\allowbreak\mathchoice{\>}{\>}{\,}{\,}\mathopen{}n,P\in \operatorname*{arg\,max}_{n\in\llbracket 0,N\rrbracket,P\in\mathcal{U}}J_{n,P} (\pi)-b_{n}\right\}\;.$ $$

∎

###### Lemma H.1 (Properties of Δ b 0 subscript Δ subscript 𝑏 0 \Delta_{b_{0}} roman_Δ start_POSTSUBSCRIPT italic_b start_POSTSUBSCRIPT 0 end_POSTSUBSCRIPT end_POSTSUBSCRIPT ) .

###### Proof of Lipschitz continuity.

###### Proof of weak convexity.

###### Proof of subdifferentiability.

### H.4 Proof of Theorem 5.6

###### Proof of Theorem 5.6 .

Recall that, $\mathcal{G}_{b_{0}}(\pi)$ and $\mathcal{W}_{b_{0}}(\pi)$ defined in Equation 10, are given by:

$$ $\mathcal{G}_{b_{0}}(\pi)=\left\{\nabla J_{n,P}(\pi)\mathchoice{\>}{\>}{\,}{\,} \middle|\allowbreak\mathchoice{\>}{\>}{\,}{\,}\mathopen{}n,P\in\mathcal{W}_{b_ {0}}(\pi)\right\}\;\text{ and }\;\mathcal{W}_{b_{0}}(\pi)=\operatorname*{arg\, max}_{n\in\llbracket 0,N\rrbracket,P\in\mathcal{U}}J_{n,P}(\pi)-b_{n}\;.$ (25) $$

For simplicity, this proof uses the shorthand $\mathcal{G}\vcentcolon\nolinebreak\mkern-1.2mu=\mathcal{G}$ and $\mathcal{W}\vcentcolon\nolinebreak\mkern-1.2mu=\mathcal{W}$.

Let $\pi^{\star}_{b_{0}}\in\operatorname*{arg\,min}_{\pi\in\Pi}\Delta_{b_{0}}(\pi)$.
For any $\pi\in\Pi$ and $b_{0}\in\mathbb{R}$, we have

$$ $\displaystyle\Delta_{b_{0}}(\pi)-\Delta_{b_{0}}(\pi^{\star}_{b_{0}})$ (26) $\displaystyle=\left(\max_{n\in\llbracket 0,N\rrbracket}\max_{P\in\mathcal{U}}J _{n,P}(\pi)-b_{n}\right)-\left(\max_{n\in\llbracket 0,N\rrbracket}\max_{P\in \mathcal{U}}J_{n,P}(\pi^{\star}_{b_{0}})-b_{n}\right)$ $\displaystyle=\left(\min_{n,P\in\mathcal{W}}J_{n,P}(\pi)-b_{n}\right)-\left( \max_{n\in\llbracket 0,N\rrbracket}\max_{P\in\mathcal{U}}J_{n,P}(\pi^{\star}_{ b_{0}})-b_{n}\right)$ $\displaystyle\leq\min_{n,P\in\mathcal{W}}\left(J_{n,P}(\pi)-b_{n}\right)-\left (J_{n,P}(\pi^{\star}_{b_{0}})-b_{n}\right)$ $\displaystyle=\min_{n,P\in\mathcal{W}}J_{n,P}(\pi)-J_{n,P}(\pi^{\star}_{b_{0}})$ $\displaystyle\leq\min_{n,P\in\mathcal{W}}J_{n,P}(\pi)-\min_{\pi^{\prime}\in\Pi }J_{n,P}(\pi^{\prime})$ $\displaystyle\stackrel{{\scriptstyle\scriptscriptstyle(\mkern-1.5mua\mkern-1.5 mu)}}{{\leq}}H\min_{n,P\in\mathcal{W}}\left\lVert\frac{d^{\pi^{\star}_{n,P}}_{ P}}{\mu}\right\rVert_{\infty}\underbrace{\max_{\pi^{\prime}\in\Pi}\left\langle \pi-\pi^{\prime},\nabla_{\pi}J_{n,P}(\pi)\right\rangle}_{\geq 0\text{ when $ \pi^{\prime}$ is greedy to $\nabla_{\pi}J_{n,P}(\pi)$}}$ $\displaystyle\leq DH\min_{n,P\in\mathcal{W}}\max_{\pi^{\prime}\in\Pi}\left \langle\pi-\pi^{\prime},\nabla_{\pi}J_{n,P}(\pi)\right\rangle$ $\displaystyle=DH\min_{g\in\mathcal{G}}\max_{\pi^{\prime}\in\Pi}\left\langle\pi -\pi^{\prime},g\right\rangle\;,$ $$

where (a) uses Lemma F.2.

The claim holds by showing that

$$ $\min_{g\in\mathcal{G}}\max_{\pi^{\prime}\in\Pi}\left\langle\pi-\pi^{\prime},g \right\rangle=\min_{g\in\partial\Delta_{b_{0}}(\pi)}\max_{\pi^{\prime}\in\Pi} \left\langle\pi-\pi^{\prime},g\right\rangle\;.$ (27) $$

Since $\operatorname{conv}\{\mathcal{G}\}=\partial\Delta_{b_{0}}(\pi)$ due to Lemma H.1, Equation 27 holds when there exists a $g^{\star}\in\operatorname*{arg\,min}_{g\in\operatorname{conv}\{\mathcal{G}\}}
\max_{\pi^{\prime}\in\Pi}\langle\pi-\pi^{\prime},g\rangle$ such that $g^{\star}\in\mathcal{G}$.

Let $z^{\star}\in\operatorname*{arg\,max}_{\pi^{\prime}\in\Pi}\min_{g\in
\operatorname{conv}\{\mathcal{G}\}}\langle\pi-\pi^{\prime},g\rangle$.
For any $g^{\star}\in\operatorname*{arg\,min}_{g\in\operatorname{conv}\{\mathcal{G}\}}
\max_{\pi^{\prime}\in\Pi}\langle\pi-\pi^{\prime},g\rangle$, it holds that

$$ $\displaystyle\max_{\pi^{\prime}\in\Pi}\langle\pi-\pi^{\prime},g^{\star}\rangle$ $\displaystyle=\min_{g\in\operatorname{conv}\{\mathcal{G}\}}\max_{\pi^{\prime} \in\Pi}\langle\pi-\pi^{\prime},g\rangle$ (28) $\displaystyle\stackrel{{\scriptstyle\scriptscriptstyle(\mkern-1.5mua\mkern-1.5 mu)}}{{=}}\max_{\pi^{\prime}\in\Pi}\min_{g\in\operatorname{conv}\{\mathcal{G} \}}\langle\pi-\pi^{\prime},g\rangle$ $\displaystyle=\min_{g\in\operatorname{conv}\{\mathcal{G}\}}\langle\pi-z^{\star },g\rangle$ $\displaystyle\stackrel{{\scriptstyle\scriptscriptstyle(\mkern-1.5mub\mkern-1.5 mu)}}{{=}}\min_{g\in\mathcal{G}}\langle\pi-z^{\star},g\rangle$ $$

where (a) uses Sion’s minimax theorem (Lemma E.3) with the convexity of $\Pi$ and $\operatorname{conv}\left\{\mathcal{G}\right\}$, and (b) uses Lemma E.10.

Note that

$$ $\displaystyle\langle\pi-z^{\star},g^{\star}\rangle\leq\max_{\pi^{\prime}\in\Pi }\langle\pi-\pi^{\prime},g^{\star}\rangle\stackrel{{\scriptstyle \scriptscriptstyle(\mkern-1.5mua\mkern-1.5mu)}}{{=}}\min_{g\in\operatorname{ conv}\left\{\mathcal{G}\right\}}\langle\pi-z^{\star},g\rangle\leq\langle\pi-z^ {\star},g^{\star}\rangle\;,$ (29) $$

where (a) is due to the third line of Equation 28.
The inequality must be equality.
Accordingly,

$$ $\langle\pi-z^{\star},g^{\star}\rangle\;\stackrel{{\scriptstyle \scriptscriptstyle(\mkern-1.5mua\mkern-1.5mu)}}{{=}}\max_{\pi^{\prime}\in\Pi} \langle\pi-\pi^{\prime},g^{\star}\rangle\stackrel{{\scriptstyle \scriptscriptstyle(\mkern-1.5mub\mkern-1.5mu)}}{{=}}\min_{g\in\mathcal{G}} \langle\pi-z^{\star},g\rangle\;,$ $$

where (a) uses Equation 29 and (b) uses Equation 28.
Therefore, $g^{\star}\in\mathcal{G}$ and thus Equation 27 holds.
This concludes the proof.
∎

###### Proof of Theorem 5.6 .

## Appendix I Missing Proofs in Section 6

### I.1 Proof of Theorem 6.3

We prove the following restatement of Theorem 6.3 with concrete values.

###### Theorem I.1 (Restatement of Theorem 6.3 ) .

Suppose Assumptions 5.3, LABEL: and 5.5 hold.
Suppose that Algorithm 1 is run with oracles $\mathscr{E}$ and $\mathscr{G}$ that satisfy Assumption 6.1 and Assumption 6.2.
Let

$$ $C\vcentcolon\nolinebreak\mkern-1.2mu=\frac{\ell_{\mathrm{Lp}}}{2\ell_{\mathrm{ sm}}}+2DH\sqrt{S}\;,$ $$

where $\ell_{\mathrm{Lp}}$ and $\ell_{\mathrm{sm}}$ are defined in Lemma H.1 and $D$ is defined in Theorem 5.6.
Assume that the gradient estimation is sufficiently accurate such that

$$ $\varepsilon_{\mathrm{grd}}=C_{\mathscr{G}}\varepsilon^{2}\;\text{ where }\;C_{ \mathscr{G}}\leq\frac{1}{64C^{2}\ell_{\mathrm{sm}}\sqrt{S}}\;.$ $$

Set $\alpha=C_{\alpha}\varepsilon^{2}$ and $T=C_{T}\varepsilon^{-4}$ such that

$$ $C_{\alpha}\leq\frac{1}{64C^{2}\ell_{\mathrm{sm}}(\ell_{\mathrm{Lp}}^{2}+ \varepsilon_{\mathrm{grd}})}\;\text{ and }\;C_{T}\geq 4096C^{4}\ell_{\mathrm{ sm}}^{2}S(\ell_{\mathrm{Lp}}^{2}+\varepsilon_{\mathrm{grd}})\;.$ $$

Then, Algorithm 2 returns a policy $\pi^{(t^{\star})}$ such that

$$ $\Delta_{b_{0}}(\pi^{(t^{\star})})-\min_{\pi\in\Pi}\Delta_{b_{0}}(\pi)\leq \varepsilon+2\varepsilon_{\mathrm{est}}\;.$ $$

We first introduce the following useful lemma.

###### Lemma I.2 .

Let $\left(\operatorname{M}_{\frac{1}{2\ell_{\mathrm{sm}}}}\circ\;\Delta_{b_{0}}
\right):\pi\mapsto\min_{\pi^{\prime}\in\Pi}\left\{\Delta_{b_{0}}(\pi^{\prime})
+\ell_{\mathrm{sm}}\left\lVert\pi-\pi^{\prime}\right\rVert^{2}_{2}\right\}$
be the Moreau envelope function of $\Delta_{b_{0}}(\pi)$ with parameter $1/2\ell_{\mathrm{sm}}$.
For any policy $\pi\in\Pi$,

$$ $\Delta_{b_{0}}(\pi)-\min_{\pi^{\prime}\in\Pi}\Delta_{b_{0}}(\pi^{\prime})\leq C \left\lVert\nabla\left(\operatorname{M}_{\frac{1}{2\ell_{\mathrm{sm}}}}\circ\; \Delta_{b_{0}}\right)(\pi)\right\rVert_{2}\;.$ $$

###### Proof.

Define $\macc@depth\char 1\relax\frozen@everymath{\macc@group}\macc@set@skewchar
\macc@nested@a 111{}\vcentcolon\nolinebreak\mkern-1.2mu=\operatorname*{arg\,
min}_{\pi^{\prime}\in\Pi}\Delta_{b_{0}}(\pi^{\prime})+\ell_{\mathrm{sm}}\left
\lVert\pi-\pi^{\prime}\right\rVert_{2}^{2}$.
According to Lemma E.9 with $\tau=1/2\ell_{\mathrm{sm}}$, there exists a subgradient $g\in\partial\Delta_{b_{0}}(\macc@depth\char 1\relax\frozen@everymath{
\macc@group}\macc@set@skewchar\macc@nested@a 111{})$ such that, for any $\pi^{\prime}\in\Pi$,

$$ $\displaystyle\left\langle\macc@depth\char 1\relax\frozen@everymath{\macc@group }\macc@set@skewchar\macc@nested@a 111{}-\pi^{\prime},g\right\rangle$ $\displaystyle\leq\left\langle\nabla\left(\operatorname{M}_{\frac{1}{2\ell_{ \mathrm{sm}}}}\circ\;\Delta_{b_{0}}\right)(\pi),\macc@depth\char 1\relax \frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a 111{}-\pi^{ \prime}\right\rangle$ (30) $\displaystyle\stackrel{{\scriptstyle\scriptscriptstyle(\mkern-1.5mua\mkern-1.5 mu)}}{{\leq}}\left\lVert\nabla\left(\operatorname{M}_{\frac{1}{2\ell_{\mathrm{ sm}}}}\circ\;\Delta_{b_{0}}\right)(\pi)\right\rVert_{2}\left\lVert\macc@depth \char 1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a 11 1{}-\pi^{\prime}\right\rVert_{2}$ $\displaystyle\stackrel{{\scriptstyle\scriptscriptstyle(\mkern-1.5mub\mkern-1.5 mu)}}{{\leq}}2\sqrt{S}\left\lVert\nabla\left(\operatorname{M}_{\frac{1}{2\ell_ {\mathrm{sm}}}}\circ\;\Delta_{b_{0}}\right)(\pi)\right\rVert_{2}\;,$ $$

where (a) is due to the Cauchy–Schwarz inequality and (b) uses that, for any $\pi^{\prime}\in\Pi$

$$ $\displaystyle\left\|\macc@depth\char 1\relax\frozen@everymath{\macc@group} \macc@set@skewchar\macc@nested@a 111{}-\pi^{\prime}\right\|_{2}$ $\displaystyle=\sqrt{\sum_{s\in\mathcal{S}}\sum_{a\in\mathcal{A}}\left( \macc@depth\char 1\relax\frozen@everymath{\macc@group}\macc@set@skewchar \macc@nested@a 111{}(s,a)-\pi^{\prime}(s,a)\right)^{2}}\leq\sqrt{S}\max_{s\in \mathcal{S}}\sqrt{\sum_{a\in\mathcal{A}}\left(\macc@depth\char 1\relax \frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a 111{}(s,a)-\pi^ {\prime}(s,a)\right)^{2}}$ (31) $\displaystyle\leq\sqrt{S}\max_{s\in\mathcal{S}}\sum_{a\in\mathcal{A}}\left| \macc@depth\char 1\relax\frozen@everymath{\macc@group}\macc@set@skewchar \macc@nested@a 111{}(s,a)-\pi^{\prime}(s,a)\right|\leq 2\sqrt{S}\;.$ $$

Let $\pi^{\star}_{b_{0}}\in\operatorname*{arg\,min}_{\pi\in\Pi}\Delta_{b_{0}}(\pi)$.
Inserting this result into Theorem 5.6, we have

$$ $\displaystyle\Delta_{b_{0}}(\macc@depth\char 1\relax\frozen@everymath{ \macc@group}\macc@set@skewchar\macc@nested@a 111{})-\Delta_{b_{0}}(\pi^{\star} _{b_{0}})$ $\displaystyle\leq DH\max_{\pi^{\prime}\in\Pi}\left\langle\macc@depth\char 1 \relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a 111{}-\pi ^{\prime},g\right\rangle\quad\forall g\in\partial\Delta_{b_{0}}(\macc@depth \char 1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a 11 1{})$ $\displaystyle\leq 2DH\sqrt{S}\left\lVert\nabla\left(\operatorname{M}_{\frac{1} {2\ell_{\mathrm{sm}}}}\circ\;\Delta_{b_{0}}\right)(\pi)\right\rVert_{2}\;.$ $$

Therefore,

$$ $\displaystyle\Delta_{b_{0}}(\pi)-\Delta_{b_{0}}(\pi_{b_{0}}^{\star})$ $\displaystyle=\Delta_{b_{0}}(\pi)-\Delta_{b_{0}}(\macc@depth\char 1\relax \frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a 111{})+\Delta_{ b_{0}}(\macc@depth\char 1\relax\frozen@everymath{\macc@group} \macc@set@skewchar\macc@nested@a 111{})-\Delta_{b_{0}}(\pi^{\star}_{b_{0}})$ $\displaystyle\stackrel{{\scriptstyle\scriptscriptstyle(\mkern-1.5mua\mkern-1.5 mu)}}{{\leq}}\Delta_{b_{0}}(\pi)-\Delta_{b_{0}}(\macc@depth\char 1\relax \frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a 111{})+2DH\sqrt {S}\left\lVert\nabla\left(\operatorname{M}_{\frac{1}{2\ell_{\mathrm{sm}}}} \circ\;\Delta_{b_{0}}\right)(\pi)\right\rVert_{2}$ $\displaystyle\stackrel{{\scriptstyle\scriptscriptstyle(\mkern-1.5mub\mkern-1.5 mu)}}{{\leq}}\ell_{\mathrm{Lp}}\left\lVert\pi-\macc@depth\char 1\relax \frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a 111{}\right \rVert_{2}+2DH\sqrt{S}\left\lVert\nabla\left(\operatorname{M}_{\frac{1}{2\ell_ {\mathrm{sm}}}}\circ\;\Delta_{b_{0}}\right)(\pi)\right\rVert_{2}$ $\displaystyle\stackrel{{\scriptstyle\scriptscriptstyle(\mkern-1.5muc\mkern-1.5 mu)}}{{\leq}}\frac{\ell_{\mathrm{Lp}}}{2\ell_{\mathrm{sm}}}\left\lVert\nabla \left(\operatorname{M}_{\frac{1}{2\ell_{\mathrm{sm}}}}\circ\;\Delta_{b_{0}} \right)(\pi)\right\rVert_{2}+2DH\sqrt{S}\left\lVert\nabla\left(\operatorname{M }_{\frac{1}{2\ell_{\mathrm{sm}}}}\circ\;\Delta_{b_{0}}\right)(\pi)\right\rVert _{2}\;,$ $$

where (a) is due to Theorem 5.6, (b) is due to the Lipschitz continuity by Lemma H.1, and (c) uses Lemma E.2.
This concludes the proof.
∎

###### Lemma I.3 .

Under the settings of Theorem I.1,

$$ $\sum^{T-1}_{t=0}\left\lVert\nabla\left(\operatorname{M}_{\frac{1}{2\ell_{ \mathrm{sm}}}}\circ\;\Delta_{b_{0}}\right)(\pi^{(t)})\right\rVert_{2}^{2}\leq \frac{16\ell_{\mathrm{sm}}S}{\alpha}+4T\left(\alpha\ell_{\mathrm{sm}}(\ell_{ \mathrm{Lp}}^{2}+\varepsilon_{\mathrm{grd}})+4\ell_{\mathrm{sm}}\varepsilon_{ \mathrm{grd}}\sqrt{S}\right)\;.$ $$

###### Proof.

Define ${\macc@depth\char 1\relax\frozen@everymath{\macc@group}\macc@set@skewchar
\macc@nested@a 111{}}^{(t)}\vcentcolon\nolinebreak\mkern-1.2mu=\operatorname*{
arg\,min}_{\pi^{\prime}}\Delta_{b_{0}}(\pi^{\prime})+\ell_{\mathrm{sm}}\left
\lVert\pi^{(t)}-\pi^{\prime}\right\rVert^{2}_{2}$.
Recall that

$$ $\pi^{(t+1)}\in\operatorname*{arg\,min}_{\pi\in\Pi}\left\langle g^{(t)},\pi-\pi ^{(t)}\right\rangle+\frac{1}{2\alpha}\left\lVert\pi-\pi^{(t)}\right\rVert^{2}= \operatorname{Proj}_{\Pi}\left(\pi^{(t)}-\alpha g^{(t)}\right)\;.$ $$

Then,

$$ $\displaystyle\left(\operatorname{M}_{\frac{1}{2\ell_{\mathrm{sm}}}}\circ\; \Delta_{b_{0}}\right)(\pi^{(t+1)})$ $\displaystyle=\min_{\pi\in\Pi}\Delta_{b_{0}}(\pi)+\ell_{\mathrm{sm}}\left \lVert\pi^{(t+1)}-\pi\right\rVert^{2}_{2}$ (32) $\displaystyle\leq\Delta_{b_{0}}({\macc@depth\char 1\relax\frozen@everymath{ \macc@group}\macc@set@skewchar\macc@nested@a 111{}}^{(t)})+\ell_{\mathrm{sm}} \left\lVert\pi^{(t+1)}-{\macc@depth\char 1\relax\frozen@everymath{\macc@group} \macc@set@skewchar\macc@nested@a 111{}}^{(t)}\right\rVert^{2}_{2}$ $\displaystyle=\Delta_{b_{0}}({\macc@depth\char 1\relax\frozen@everymath{ \macc@group}\macc@set@skewchar\macc@nested@a 111{}}^{(t)})+\ell_{\mathrm{sm}} \left\lVert\operatorname{Proj}_{\Pi}\left(\pi^{(t)}-\alpha g^{(t)}\right)- \operatorname{Proj}_{\Pi}\left({\macc@depth\char 1\relax\frozen@everymath{ \macc@group}\macc@set@skewchar\macc@nested@a 111{}}^{(t)}\right)\right\rVert^{ 2}_{2}$ $\displaystyle\leq\Delta_{b_{0}}({\macc@depth\char 1\relax\frozen@everymath{ \macc@group}\macc@set@skewchar\macc@nested@a 111{}}^{(t)})+\ell_{\mathrm{sm}} \left\lVert\pi^{(t)}-\alpha g^{(t)}-{\macc@depth\char 1\relax\frozen@everymath {\macc@group}\macc@set@skewchar\macc@nested@a 111{}}^{(t)}\right\rVert^{2}_{2}$ $\displaystyle=\underbrace{\Delta_{b_{0}}({\macc@depth\char 1\relax \frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a 111{}}^{(t)})+ \ell_{\mathrm{sm}}\left\lVert\pi^{(t)}-{\macc@depth\char 1\relax \frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a 111{}}^{(t)} \right\rVert^{2}_{2}}_{=\left(\operatorname{M}_{\frac{1}{2\ell_{\mathrm{sm}}}} \circ\;\Delta_{b_{0}}\right)\left(\pi^{(t)}\right)}+2\ell_{\mathrm{sm}}\alpha \left\langle g^{(t)},{\macc@depth\char 1\relax\frozen@everymath{\macc@group} \macc@set@skewchar\macc@nested@a 111{}}^{(t)}-\pi^{(t)}\right\rangle+\alpha^{2 }\ell_{\mathrm{sm}}\left\lVert g^{(t)}\right\rVert^{2}_{2}\;.$ $$

Due to Assumption 6.2 and $g^{(t)}=\mathscr{G}(b_{0},\pi^{(t)})$, there exists an vector $g^{\prime}\in\mathbb{R}^{\mathcal{S}\times\mathcal{A}}$ such that
$g^{\prime}\in\left\{\nabla J_{n^{(t)},P^{(t)}}(\pi^{(t)})\mathchoice{\>}{\>}{
\,}{\,}\middle|\allowbreak\mathchoice{\>}{\>}{\,}{\,}\mathopen{}n^{(t)},P^{(t)
}\in\mathcal{W}_{b_{0}}(\pi^{(t)})\right\}$ satisfying
$\left\lVert g^{(t)}-g^{\prime}\right\rVert_{2}^{2}\leq\varepsilon_{\mathrm{grd
}}^{2}$.
Accordingly,

$$ $\left\lVert g^{(t)}\right\rVert^{2}_{2}\leq\left\lVert g^{\prime}\right\rVert^ {2}_{2}+\underbrace{\left\lVert g^{(t)}-g^{\prime}\right\rVert^{2}_{2}}_{\leq \varepsilon_{\mathrm{grd}}^{2}}\leq\ell_{\mathrm{Lp}}^{2}+\varepsilon_{\mathrm {grd}}^{2}\;,$ $$

where the last inequality uses Lemma F.1.
Furthermore,

$$ $\displaystyle\left\langle g^{(t)},{\macc@depth\char 1\relax\frozen@everymath{ \macc@group}\macc@set@skewchar\macc@nested@a 111{}}^{(t)}-\pi^{(t)}\right\rangle$ $\displaystyle=\left\langle g^{\prime},{\macc@depth\char 1\relax \frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a 111{}}^{(t)}- \pi^{(t)}\right\rangle+\left\langle g^{(t)}-g^{\prime},{\macc@depth\char 1 \relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a 111{}}^{( t)}-\pi^{(t)}\right\rangle$ $\displaystyle\stackrel{{\scriptstyle\scriptscriptstyle(\mkern-1.5mua\mkern-1.5 mu)}}{{\leq}}\left\langle g^{\prime},{\macc@depth\char 1\relax \frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a 111{}}^{(t)}- \pi^{(t)}\right\rangle+\left\lVert g^{(t)}-g^{\prime}\right\rVert_{2}\left \lVert{\macc@depth\char 1\relax\frozen@everymath{\macc@group} \macc@set@skewchar\macc@nested@a 111{}}^{(t)}-\pi^{(t)}\right\rVert_{2} \stackrel{{\scriptstyle\scriptscriptstyle(\mkern-1.5mub\mkern-1.5mu)}}{{\leq}} \left\langle g^{\prime},{\macc@depth\char 1\relax\frozen@everymath{\macc@group }\macc@set@skewchar\macc@nested@a 111{}}^{(t)}-\pi^{(t)}\right\rangle+2 \varepsilon_{\mathrm{grd}}\sqrt{S}$ $$

where (a) is due to the Cauchy–Schwarz inequality and (b) uses Equation 31.
Inserting this result to Equation 32, we have

$$ $\displaystyle 2\ell_{\mathrm{sm}}\alpha\left\langle g^{\prime},\pi^{(t)}-{ \macc@depth\char 1\relax\frozen@everymath{\macc@group}\macc@set@skewchar \macc@nested@a 111{}}^{(t)}\right\rangle$ (33) $\displaystyle\leq\left(\operatorname{M}_{\frac{1}{2\ell_{\mathrm{sm}}}}\circ\; \Delta_{b_{0}}\right)(\pi^{(t)})-\left(\operatorname{M}_{\frac{1}{2\ell_{ \mathrm{sm}}}}\circ\;\Delta_{b_{0}}\right)(\pi^{(t+1)})+\alpha^{2}\ell_{ \mathrm{sm}}(\ell_{\mathrm{Lp}}^{2}+\varepsilon_{\mathrm{grd}}^{2})+4\ell_{ \mathrm{sm}}\alpha\varepsilon_{\mathrm{grd}}\sqrt{S}\;.$ $$

Due to the weak convexity of $\Delta_{b_{0}}(\pi)$ (Lemma H.1) and since $g^{\prime}\in\partial\Delta_{b_{0}}(\pi^{(t)})$, we have

$$ $\displaystyle\left\langle g^{\prime},\pi^{(t)}-{\macc@depth\char 1\relax \frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a 111{}}^{(t)}\right\rangle$ $\displaystyle\geq\Delta_{b_{0}}(\pi^{(t)})-\Delta_{b_{0}}({\macc@depth\char 1 \relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a 111{}}^{( t)})-\frac{\ell_{\mathrm{sm}}}{2}\left\lVert{\macc@depth\char 1\relax \frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a 111{}}^{(t)}- \pi^{(t)}\right\rVert_{2}^{2}$ $\displaystyle=\Delta_{b_{0}}(\pi^{(t)})+\ell_{\mathrm{sm}}\left\lVert\pi^{(t)} -\pi^{(t)}\right\rVert_{2}^{2}-\Delta_{b_{0}}({\macc@depth\char 1\relax \frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a 111{}}^{(t)})- \ell_{\mathrm{sm}}\left\lVert{\macc@depth\char 1\relax\frozen@everymath{ \macc@group}\macc@set@skewchar\macc@nested@a 111{}}^{(t)}-\pi^{(t)}\right \rVert_{2}^{2}+\frac{\ell_{\mathrm{sm}}}{2}\left\lVert{\macc@depth\char 1 \relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a 111{}}^{( t)}-\pi^{(t)}\right\rVert_{2}^{2}$ $\displaystyle=\Delta_{b_{0}}(\pi^{(t)})+\ell_{\mathrm{sm}}\left\lVert\pi^{(t)} -\pi^{(t)}\right\rVert_{2}^{2}-\min_{\pi^{\prime}\in\Pi}\left(\Delta_{b_{0}}( \pi^{\prime})+\ell_{\mathrm{sm}}\left\lVert\pi^{\prime}-\pi^{(t)}\right\rVert_ {2}^{2}\right)+\frac{\ell_{\mathrm{sm}}}{2}\left\lVert{\macc@depth\char 1 \relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a 111{}}^{( t)}-\pi^{(t)}\right\rVert_{2}^{2}$ $\displaystyle\geq\frac{\ell_{\mathrm{sm}}}{2}\left\lVert{\macc@depth\char 1 \relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a 111{}}^{( t)}-\pi^{(t)}\right\rVert_{2}^{2}\stackrel{{\scriptstyle\scriptscriptstyle( \mkern-1.5mua\mkern-1.5mu)}}{{=}}\frac{\ell_{\mathrm{sm}}}{2}\left\lVert\frac{ 1}{2\ell_{\mathrm{sm}}}\nabla\left(\operatorname{M}_{\frac{1}{2\ell_{\mathrm{ sm}}}}\circ\;\Delta_{b_{0}}\right)(\pi^{(t)})\right\rVert_{2}^{2}=\frac{1}{8 \ell_{\mathrm{sm}}}\left\lVert\nabla\left(\operatorname{M}_{\frac{1}{2\ell_{ \mathrm{sm}}}}\circ\;\Delta_{b_{0}}\right)(\pi^{(t)})\right\rVert_{2}^{2}\;,$ $$

where (a) uses Lemma E.2.
By inserting this to Equation 33 and taking summation $\sum^{T-1}_{t=0}$,

$$ $\displaystyle\frac{\alpha}{4}\sum^{T-1}_{t=0}\left\lVert\nabla\left( \operatorname{M}_{\frac{1}{2\ell_{\mathrm{sm}}}}\circ\;\Delta_{b_{0}}\right)( \pi^{(t)})\right\rVert_{2}^{2}$ $\displaystyle\leq$ $\displaystyle\left(\operatorname{M}_{\frac{1}{2\ell_{\mathrm{sm}}}}\circ\; \Delta_{b_{0}}\right)(\pi^{(0)})-\left(\operatorname{M}_{\frac{1}{2\ell_{ \mathrm{sm}}}}\circ\;\Delta_{b_{0}}\right)(\pi^{(T)})+T\left(\alpha^{2}\ell_{ \mathrm{sm}}(\ell_{\mathrm{Lp}}^{2}+\varepsilon_{\mathrm{grd}}^{2})+4\ell_{ \mathrm{sm}}\alpha\varepsilon_{\mathrm{grd}}\sqrt{S}\right)\;.$ $$

Note that

$$ $\displaystyle\left(\operatorname{M}_{\frac{1}{2\ell_{\mathrm{sm}}}}\circ\; \Delta_{b_{0}}\right)(\pi^{(0)})-\left(\operatorname{M}_{\frac{1}{2\ell_{ \mathrm{sm}}}}\circ\;\Delta_{b_{0}}\right)(\pi^{(T)})$ $\displaystyle=$ $\displaystyle\min_{\pi\in\Pi}\left\{\Delta_{b_{0}}(\pi)+\ell_{\mathrm{sm}} \left\lVert\pi^{(0)}-\pi\right\rVert^{2}_{2}\right\}-\min_{\pi\in\Pi}\left\{ \Delta_{b_{0}}(\pi)+\ell_{\mathrm{sm}}\left\lVert\pi^{(T)}-\pi\right\rVert^{2} _{2}\right\}$ $\displaystyle=$ $\displaystyle\Delta_{b_{0}}({\macc@depth\char 1\relax\frozen@everymath{ \macc@group}\macc@set@skewchar\macc@nested@a 111{}}^{(0)})+\ell_{\mathrm{sm}} \left\lVert\pi^{(0)}-{\macc@depth\char 1\relax\frozen@everymath{\macc@group} \macc@set@skewchar\macc@nested@a 111{}}^{(0)}\right\rVert^{2}_{2}-\Delta_{b_{0 }}({\macc@depth\char 1\relax\frozen@everymath{\macc@group}\macc@set@skewchar \macc@nested@a 111{}}^{(T)})-\ell_{\mathrm{sm}}\left\lVert\pi^{(T)}-{ \macc@depth\char 1\relax\frozen@everymath{\macc@group}\macc@set@skewchar \macc@nested@a 111{}}^{(T)}\right\rVert^{2}_{2}$ $\displaystyle\leq$ $\displaystyle\Delta_{b_{0}}({\macc@depth\char 1\relax\frozen@everymath{ \macc@group}\macc@set@skewchar\macc@nested@a 111{}}^{(T)})+\ell_{\mathrm{sm}} \left\lVert\pi^{(0)}-{\macc@depth\char 1\relax\frozen@everymath{\macc@group} \macc@set@skewchar\macc@nested@a 111{}}^{(T)}\right\rVert^{2}_{2}-\Delta_{b_{0 }}({\macc@depth\char 1\relax\frozen@everymath{\macc@group}\macc@set@skewchar \macc@nested@a 111{}}^{(T)})-\ell_{\mathrm{sm}}\left\lVert\pi^{(T)}-{ \macc@depth\char 1\relax\frozen@everymath{\macc@group}\macc@set@skewchar \macc@nested@a 111{}}^{(T)}\right\rVert^{2}_{2}$ $\displaystyle\leq$ $\displaystyle\ell_{\mathrm{sm}}\left\lVert\pi^{(0)}-{\macc@depth\char 1\relax \frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a 111{}}^{(T)} \right\rVert^{2}_{2}\leq 4\ell_{\mathrm{sm}}S\;,$ $$

where the last inequality uses Equation 31.

By combining all the results, we obtain

$$ $\sum^{T-1}_{t=0}\left\lVert\nabla\left(\operatorname{M}_{\frac{1}{2\ell_{ \mathrm{sm}}}}\circ\;\Delta_{b_{0}}\right)(\pi^{(t)})\right\rVert_{2}^{2}\leq \frac{16\ell_{\mathrm{sm}}S}{\alpha}+4T\left(\alpha\ell_{\mathrm{sm}}(\ell_{ \mathrm{Lp}}^{2}+\varepsilon_{\mathrm{grd}}^{2})+4\ell_{\mathrm{sm}} \varepsilon_{\mathrm{grd}}\sqrt{S}\right)\;.$ $$

This concludes the proof.
∎

We are now ready to prove Theorem I.1.

###### Proof of Theorem I.1 .

Let $\pi^{\star}_{b_{0}}\in\operatorname*{arg\,min}_{\pi\in\Pi}\Delta_{b_{0}}(\pi)$.
Then,

$$ $\displaystyle\min_{t\in\llbracket 0,T-1\rrbracket}\Delta_{b_{0}}(\pi^{(t)})- \Delta_{b_{0}}(\pi_{b_{0}}^{\star})$ $\displaystyle\leq\frac{1}{T}\sum^{T-1}_{t=0}\Delta_{b_{0}}(\pi^{(t)})-\Delta_{ b_{0}}(\pi_{b_{0}}^{\star})$ $\displaystyle\stackrel{{\scriptstyle\scriptscriptstyle(\mkern-1.5mua\mkern-1.5 mu)}}{{\leq}}\frac{1}{T}C\sum^{T-1}_{t=0}\left\lVert\nabla\left(\operatorname{ M}_{\frac{1}{2\ell_{\mathrm{sm}}}}\circ\;\Delta_{b_{0}}\right)(\pi)\right \rVert_{2}$ $\displaystyle\leq C\sqrt{\frac{1}{T}\sum^{T-1}_{t=0}\left\lVert\nabla\left( \operatorname{M}_{\frac{1}{2\ell_{\mathrm{sm}}}}\circ\;\Delta_{b_{0}}\right)( \pi)\right\rVert_{2}^{2}}$ $\displaystyle\stackrel{{\scriptstyle\scriptscriptstyle(\mkern-1.5mub\mkern-1.5 mu)}}{{\leq}}C\sqrt{\frac{16\ell_{\mathrm{sm}}S}{T\alpha}+4\left(\alpha\ell_{ \mathrm{sm}}(\ell_{\mathrm{Lp}}^{2}+\varepsilon_{\mathrm{grd}}^{2})+4\ell_{ \mathrm{sm}}\varepsilon_{\mathrm{grd}}\sqrt{S}\right)}$ $\displaystyle\stackrel{{\scriptstyle\scriptscriptstyle(\mkern-1.5muc\mkern-1.5 mu)}}{{=}}C\sqrt{\frac{16\ell_{\mathrm{sm}}S}{\delta\sqrt{T}}+\frac{4\delta}{ \sqrt{T}}\ell_{\mathrm{sm}}(\ell_{\mathrm{Lp}}^{2}+\varepsilon_{\mathrm{grd}}^ {2})+16\ell_{\mathrm{sm}}\varepsilon_{\mathrm{grd}}\sqrt{S}}$ $\displaystyle\stackrel{{\scriptstyle\scriptscriptstyle(\mkern-1.5mud\mkern-1.5 mu)}}{{\leq}}4C\sqrt{\ell_{\mathrm{sm}}S\delta^{-1}}T^{-\frac{1}{4}}+2C\sqrt{ \ell_{\mathrm{sm}}(\ell_{\mathrm{Lp}}^{2}+\varepsilon_{\mathrm{grd}}^{2}) \delta}T^{-\frac{1}{4}}+4CS^{\frac{1}{4}}\sqrt{\ell_{\mathrm{sm}}\varepsilon_{ \mathrm{grd}}}$ $\displaystyle\stackrel{{\scriptstyle\scriptscriptstyle(\mkern-1.5mue\mkern-1.5 mu)}}{{=}}4C\sqrt{\ell_{\mathrm{sm}}}S^{\frac{1}{4}}(\ell_{\mathrm{Lp}}^{2}+ \varepsilon_{\mathrm{grd}}^{2})^{\frac{1}{4}}T^{-\frac{1}{4}}+4CS^{\frac{1}{4} }\sqrt{\ell_{\mathrm{sm}}\varepsilon_{\mathrm{grd}}}$ $$

where (a) uses Lemma I.2, (b) uses Lemma I.3, (c) inserts $\alpha=\delta/\sqrt{T}$, (d) uses $\sqrt{x+y}\leq\sqrt{x}+\sqrt{y}$,
and (e) sets $\delta=\sqrt{S/(\ell_{\mathrm{Lp}}^{2}+\varepsilon_{\mathrm{grd}}^{2})}$.

Therefore, when $\varepsilon_{\mathrm{grd}}$ and $T$ satisfy
$\varepsilon_{\mathrm{grd}}\leq\frac{1}{64C^{2}\ell_{\mathrm{sm}}\sqrt{S}}$
and
$T\geq 4096C^{4}\ell_{\mathrm{sm}}^{2}S(\ell_{\mathrm{Lp}}^{2}+\varepsilon_{
\mathrm{grd}}^{2})\varepsilon^{-4}$, we have

$$ $\min_{t\in\llbracket 0,T-1\rrbracket}\Delta_{b_{0}}(\pi^{(t)})\leq\Delta_{b_{0 }}(\pi_{b_{0}}^{\star})+\varepsilon\;.$ $$

Finally, $t^{\star}\in\operatorname*{arg\,min}_{t\in\llbracket 0,T-1\rrbracket}\widehat{
\Delta}^{(t)}$ satisfies that

$$ $\displaystyle\Delta_{b_{0}}(\pi^{(t^{\star})})$ $\displaystyle=\widehat{\Delta}^{(t^{\star})}+\Delta_{b_{0}}(\pi^{(t^{\star})}) -\widehat{\Delta}^{(t^{\star})}$ $\displaystyle\leq\min_{t\in\llbracket 0,T-1\rrbracket}\widehat{\Delta}^{(t)}+ \varepsilon_{\mathrm{est}}$ $\displaystyle\leq\min_{t\in\llbracket 0,T-1\rrbracket}\Delta_{b_{0}}(\pi^{(t)} )+\widehat{\Delta}^{(t)}-\Delta_{b_{0}}(\pi^{(t)})+\varepsilon_{\mathrm{est}}$ $\displaystyle\leq\min_{t\in\llbracket 0,T-1\rrbracket}\Delta_{b_{0}}(\pi^{(t)} )+2\varepsilon_{\mathrm{est}}$ $\displaystyle\leq\Delta_{b_{0}}(\pi_{b_{0}}^{\star})+\varepsilon+2\varepsilon_ {\mathrm{est}}\;.$ $$

This concludes the proof.
∎

###### Theorem I.1 (Restatement of Theorem 6.3 ) .

###### Lemma I.2 .

###### Proof.

###### Lemma I.3 .

###### Proof.

###### Proof of Theorem I.1 .

### I.2 Proof of Theorem 6.5

To facilitate the analysis with estimation error, we present a slightly modified version of the epigraph form.
Let $\varepsilon\in\mathbb{R}$ be an admissible violation parameter.
We introduce the following formulation:

$$ $({\textbf{Epigraph}_{\varepsilon}})\quad\heartsuit_{\varepsilon}\vcentcolon \nolinebreak\mkern-1.2mu=\min_{b_{0}\in[0,H]}b_{0}\;\text{ such that }\;\Delta ^{\star}_{b_{0}}\leq\varepsilon\;.$ (34) $$

Note that $\heartsuit_{\varepsilon}$ is monotonically decreasing in $\varepsilon$.

Additionally, we introduce a slightly generalized version of Theorem 5.1:

###### Lemma I.4 .

For any $\varepsilon_{1},\varepsilon_{2}\geq 0$, if $b_{0}$ and a policy $\pi\in\Pi$ satisfy $b_{0}\leq\heartsuit+\varepsilon_{2}$ and $\Delta_{b_{0}}(\pi)\leq\varepsilon_{1}$, then $\pi$ is an $(\varepsilon_{1}+\varepsilon_{2})$-optimal policy.

###### Proof.

Note that
$J_{0,\mathcal{U}}(\pi)\leq\heartsuit+\varepsilon_{1}+\varepsilon_{2}$ and $J_{n,\mathcal{U}}(\pi)\leq b_{n}+\varepsilon_{1}$ for any $n\in\llbracket 1,N\rrbracket$.
The claim directly follows from Definition 3.2 and the fact that $\heartsuit=J_{0,\mathcal{U}}(\pi^{\star})$.
∎

For any $\macc@depth\char 1\relax\frozen@everymath{\macc@group}\macc@set@skewchar
\macc@nested@a 111{b}_{0}\in[\heartsuit_{\varepsilon_{1}},\heartsuit+
\varepsilon_{2}]$ with some $\varepsilon_{1},\varepsilon_{2}\geq 0$, the subroutine returns a policy $\macc@depth\char 1\relax\frozen@everymath{\macc@group}\macc@set@skewchar
\macc@nested@a 111{}=\mathscr{A}(\macc@depth\char 1\relax\frozen@everymath{
\macc@group}\macc@set@skewchar\macc@nested@a 111{b}_{0})$ such that

$$ $\Delta_{\macc@depth\char 1\relax\frozen@everymath{\macc@group} \macc@set@skewchar\macc@nested@a 111{b}_{0}}(\macc@depth\char 1\relax \frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a 111{})\stackrel {{\scriptstyle\scriptscriptstyle(\mkern-1.5mua\mkern-1.5mu)}}{{\leq}}\min_{\pi ^{\prime}\in\Pi}\Delta_{\macc@depth\char 1\relax\frozen@everymath{\macc@group} \macc@set@skewchar\macc@nested@a 111{b}_{0}}(\pi^{\prime})+\varepsilon_{ \mathrm{opt}}\stackrel{{\scriptstyle\scriptscriptstyle(\mkern-1.5mub\mkern-1.5 mu)}}{{\leq}}\min_{\pi^{\prime}\in\Pi}\Delta_{\heartsuit_{\varepsilon_{1}}}( \pi^{\prime})+\varepsilon_{\mathrm{opt}}\stackrel{{\scriptstyle \scriptscriptstyle(\mkern-1.5muc\mkern-1.5mu)}}{{\leq}}\varepsilon_{1}+ \varepsilon_{\mathrm{opt}},$ $$

where (a) is due to Assumption 6.4, (b) holds since $\Delta_{b_{0}}(\pi)$ is monotonically decreasing in $b_{0}$, and (c) follows from Equation 34.
Consequently, by applying Lemma I.4, $\macc@depth\char 1\relax\frozen@everymath{\macc@group}\macc@set@skewchar
\macc@nested@a 111{}$ is $(\varepsilon_{1}+\varepsilon_{2}+\varepsilon_{\mathrm{opt}})$-optimal.

The following intermediate lemma guarantees that the search space of Algorithm 2 always contains such $\macc@depth\char 1\relax\frozen@everymath{\macc@group}\macc@set@skewchar
\macc@nested@a 111{b}_{0}$ with $\varepsilon_{1}=\varepsilon_{\mathrm{est}}$ and $\varepsilon_{2}=\varepsilon_{\mathrm{est}}+\varepsilon_{\mathrm{opt}}$.

###### Lemma I.5 .

Suppose that Algorithm 2 is run with oracles $\mathscr{E}$ and $\mathscr{A}$ that satisfy Assumptions 6.1, LABEL: and 6.4.
For any $k\in\llbracket 0,K\rrbracket$,
$[i^{(k)},j^{(k)}]\cap[\heartsuit_{\varepsilon_{\mathrm{est}}},\heartsuit+
\varepsilon_{\mathrm{est}}+\varepsilon_{\mathrm{opt}}]\neq\emptyset$.

###### Proof.

The claim holds for $k=0$.
Suppose that the claim holds for a fixed $k$.
If $\widehat{\Delta}^{(k)}>0$, it holds that

$$ $-\varepsilon_{\mathrm{est}}-\varepsilon_{\mathrm{opt}}\stackrel{{\scriptstyle \scriptscriptstyle(\mkern-1.5mua\mkern-1.5mu)}}{{<}}\widehat{\Delta}^{(k)}- \left\lvert\widehat{\Delta}^{(k)}-\Delta_{b_{0}^{(k)}}(\pi^{(k)})\right\rvert- \varepsilon_{\mathrm{opt}}\leq\Delta_{b_{0}^{(k)}}(\pi^{(k)})-\varepsilon_{ \mathrm{opt}}\stackrel{{\scriptstyle\scriptscriptstyle(\mkern-1.5mub\mkern-1.5 mu)}}{{\leq}}\Delta_{b^{(k)}_{0}}(\pi^{\star})\stackrel{{\scriptstyle \scriptscriptstyle(\mkern-1.5muc\mkern-1.5mu)}}{{=}}\heartsuit-b_{0}^{(k)}$ (35) $$

where (a) is due to Assumption 6.1 with $\widehat{\Delta}^{(k)}>0$, (b) is due to Assumption 6.4, and (c) holds since $\pi^{\star}$ is a feasible policy.
Combining this with the induction assumption and the update rule of Equation 12, we have $i^{(k+1)}=b_{0}^{(k)}\leq\heartsuit+\varepsilon_{\mathrm{est}}+\varepsilon_{
\mathrm{opt}}$ and $\heartsuit_{\varepsilon_{\mathrm{est}}}\leq j^{(k+1)}$.
Hence, $[i^{(k+1)},j^{(k+1)}]\cap[\heartsuit_{\varepsilon_{\mathrm{est}}},\heartsuit+
\varepsilon_{\mathrm{est}}+\varepsilon_{\mathrm{opt}}]\neq\emptyset$ when $\widehat{\Delta}^{(k)}>0$.

On the other hand, if $\widehat{\Delta}^{(k)}\leq 0$, we have

$$ $\min_{\pi}\Delta_{b_{0}^{(k)}}(\pi)\leq\Delta_{b_{0}^{(k)}}(\pi^{(k)})\leq \widehat{\Delta}^{(k)}+\varepsilon_{\mathrm{est}}\leq\varepsilon_{\mathrm{est} }\;.$ (36) $$

Since $b_{0}^{(k)}$ is the feasible solution to Equation 34, it holds that $\heartsuit_{\varepsilon_{\mathrm{est}}}\leq b^{(k)}_{0}=j^{(k+1)}$.
Accordingly, we have $[i^{(k+1)},j^{(k+1)}]\cap[\heartsuit_{\varepsilon_{\mathrm{est}}},\heartsuit+
\varepsilon_{\mathrm{est}}+\varepsilon_{\mathrm{opt}}]\neq\emptyset$.
Therefore, the claim holds for any $k\in\llbracket 0,K\rrbracket$.
∎

We are now ready to prove Theorem 6.5.

###### Proof of Theorem 6.5 .

Note that $j^{(k)}-i^{(k)}\leq\left(j^{(0)}-i^{(0)}\right)2^{-k}=H2^{-k}$ due to the update rule of Equation 12.
According to Lemma I.5, we have
$\heartsuit_{\varepsilon_{\mathrm{est}}}\leq j^{(K)}\leq\heartsuit+\varepsilon_
{\mathrm{est}}+\varepsilon_{\mathrm{opt}}+H2^{-K}$.
Additionally, the returned policy $\pi_{\mathrm{ret}}$ satisfies

$$ $\Delta_{j^{(K)}}(\pi_{\mathrm{ret}})\stackrel{{\scriptstyle\scriptscriptstyle( \mkern-1.5mua\mkern-1.5mu)}}{{\leq}}\min_{\pi\in\Pi}\Delta_{j^{(K)}}(\pi)+ \varepsilon_{\mathrm{opt}}\stackrel{{\scriptstyle\scriptscriptstyle(\mkern-1.5 mub\mkern-1.5mu)}}{{\leq}}\min_{\pi\in\Pi}\Delta_{\heartsuit_{\varepsilon_{ \mathrm{est}}}}(\pi)+\varepsilon_{\mathrm{opt}}\leq\varepsilon_{\mathrm{est}}+ \varepsilon_{\mathrm{opt}}\;,$ $$

where (a) uses Assumption 6.4 and (b) is due to $\heartsuit_{\varepsilon_{\mathrm{est}}}\leq j^{(K)}$ and the fact that $\min_{\pi}\Delta_{b_{0}}(\pi)$ is monotonically decreasing in $b_{0}$.
Applying this to Lemma I.4 with $j^{(K)}\leq\heartsuit+\varepsilon_{\mathrm{est}}+\varepsilon_{\mathrm{opt}}+H2
^{-K}$ concludes the proof.
∎

###### Lemma I.4 .

###### Proof.

###### Lemma I.5 .

###### Proof.

###### Proof of Theorem 6.5 .

## Peer Reviews

confidence: 3
contribution: 3
initial_rating: 6
presentation: 3
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.
soundness: 4
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. 
2. The shift to an epigraph form represents a significant advancement, simplifying the solution method and providing an effective framework for robust optimization. 
3. 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.
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.
weaknesses: 1. A key area for improvement is a more thorough analysis of the algorithm’s efficiency, especially in higher-dimensional state spaces. 
2. 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.

---

confidence: 4
contribution: 1
initial_rating: 3
presentation: 1
questions: See weaknesses.

- What do you mean by "is an unknown value" in Assumption 4?

- Algorithm 1, how do you set T?
soundness: 2
strengths: - This paper addresses an important problem in the field of MDPs

- The idea of bisection search is interesting.
summary: This paper reformulate robust constrained MDPs via epigraphical reformulation and propose a bisection algorithm to solve this problem.
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.

- 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. 

- The underlying idea of Algorithm 1 is not clear and the presentation is poor. 

- The convergence of the proposed algorithm is not fast, O(eps^-4), and there is no discuss on the complexity. 

- Experiments are not working on large-scale problems.

---

confidence: 4
contribution: 3
initial_rating: 6
presentation: 3
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?

2. 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?
soundness: 3
strengths: 1. Applying the epigraph form to RCMDPs is a novel solution to address gradient conflict issues that arise with traditional Lagrangian formulations. 

2. The authors offer theoretical proofs that guarantee the proposed algorithm’s convergence to an ε-optimal policy. 

3. 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.
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.
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.

2. 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.

---

confidence: 4
contribution: 3
initial_rating: 8
presentation: 3
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. 

2. What are the challenges in extending this result to the case where the uncertainty set is not fully known apriori?

3. 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.

4. 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.
soundness: 3
strengths: 1. Good intuition and presentation.
2. Mathematically sound results.
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.
weaknesses: **Minor Comments**

1. Assumption $5$ is used in Theorem $3$, however it appears later. Please correct it. 

**Major Comments**

1. 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.

---

confidence: 4
contribution: 3
initial_rating: 6
presentation: 3
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?
soundness: 4
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.
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 
$ϵ-optimal$ policy across uncertain environments while satisfying safety constraints.
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.

comments:
It is better to discuss all the assumptions before presenting the main theorem.

Meta-review: This paper studies the problem of identifying near-optimal policies in Robust Constrained Markov Decision Processes (RCMDPs) using a novel approach based on the epigraph formulation. It achieves theoretical guarantees with convergence to an $\epsilon$-optimal policy, addressing key limitations in traditional Lagrangian methods through binary search and policy gradient subroutines. The reviewers highlighted the significant theoretical contributions, such as addressing gradient conflicts in robust optimization and demonstrating limitations of existing approaches, while also raising concerns about computational efficiency and the scope of experiments. During the rebuttal phase, the authors effectively clarified these points, emphasizing the foundational nature of the work and the relevance of their theoretical framework in advancing robust reinforcement learning. Although one rejecting reviewer criticized the lack of large-scale experiments, this critique appears misplaced, given the paper’s focus on theoretical advancements. Overall, the paper makes a substantial contribution to the theory of RCMDPs and is well-positioned for acceptance based on its foundational impact.

Decision: Accept (Poster)