[datatype=bibtex, overwrite] [fieldset=address, null] [fieldset=publisher,
null] [fieldset=url, null] [fieldset=urldate, null] [fieldset=isbn, null]
[fieldset=issn, null] [fieldset=number, null] [fieldset=doi, null]
[fieldset=abstract, null] [fieldset=volume, null] [fieldset=pages, null]
[fieldset=language, null] [fieldset=month, null] [fieldset=series, null]
[fieldset=file, null] [fieldset=note, null]

# A Primal-Dual-Critic Algorithm for
Offline Constrained Reinforcement Learning

Kihyuk Hong
University of Michigan
<EMAIL_ADDRESS>
&Yuhang Li
University of Michigan
<EMAIL_ADDRESS>
&Ambuj Tewari
University of Michigan
<EMAIL_ADDRESS>

###### Abstract

Offline constrained reinforcement learning (RL) aims to learn a policy that
maximizes the expected cumulative reward subject to constraints on expected
cumulative cost using an existing dataset. In this paper, we propose Primal-
Dual-Critic Algorithm (PDCA), a novel algorithm for offline constrained RL
with general function approximation. PDCA runs a primal-dual algorithm on the
Lagrangian function estimated by critics. The primal player employs a no-
regret policy optimization oracle to maximize the Lagrangian estimate and the
dual player acts greedily to minimize the Lagrangian estimate. We show that
PDCA can successfully find a near saddle point of the Lagrangian, which is
nearly optimal for the constrained RL problem. Unlike previous work that
requires concentrability and a strong Bellman completeness assumption, PDCA
only requires concentrability and realizability assumptions for sample-
efficient learning.

##  1 INTRODUCTION

Offline constrained reinforcement learning (RL) aims to learn a decision
making policy that performs well while satisfying safety constraints given a
dataset of trajectories collected from historical experiments. It enjoys the
benefits of offline RL [22]: not requiring interaction with the environment
enables real-world applications where collecting interaction data is expensive
(e.g., robotics [18, 23]) or dangerous (e.g., healthcare [30]). It also enjoys
the benefits of constrained RL [1]: being able to specify constraints to the
behavior of the agent enables real-world applications with safety concerns
(e.g., smart grid [31], robotics [14]).

Offline constrained RL with function approximation (e.g., neural networks) is
of particular interest because function approximation can encode inductive
biases to allow sample-efficient learning in large state spaces. As is the
case for offline unconstrained RL [29, 32], offline constrained RL with
function approximation requires two classes of assumptions for sample-
efficient learning.

The first class of assumptions, called _representational assumptions_ ,
requires the learner to have access to a sufficiently rich value function
class that models action value functions of policies. The mildest
representational assumption is the realizability assumption that requires the
action value functions of candidate policies to be captured by the function
class. A stronger representational assumption is the Bellman completeness
assumption that requires the function class to be closed under the Bellman
operator.

The second class of assumptions, called _data coverage assumptions_ , requires
the offline dataset to be rich enough to cover the state-action distributions
induced by target policies. The assumptions address a major challenge in
offline RL called _distribution_ shift, which refers to the mismatch of the
state-action distributions induced by candidate policies and the distribution
in the offline dataset. The most commonly used data coverage assumption is
concentrability [26, 27], which limits the norm of the ratio of state-action
distribution induced by candidate policies to that induced by the behavior
policy that generated the offline dataset.

Previous works on offline RL with function approximation require either a
strong assumption on data coverage [33] (stronger than concentrability) or a
strong representational assumption [28, 2, 32, 9] (stronger than
realizability). [5] conjectured that concentrability and realizability of
value functions are not sufficient for sample-efficient offline RL. [12]
confirmed this by providing an information-theoretic lower bound which shows
that concentrability and value function realizability are not sufficient for
sample efficient offline RL.

Recently, a line of research on offline unconstrained RL emerged that only
requires concentrability and realizability assumptions [34, 38, 39]. In
particular, they do not require Bellman completeness assumption, which is a
strong representational assumption [38, 37]. They do not contradict the
impossibility result by [12] because they make an additional realizability
assumption on the marginalized importance weights (MIW; ratio of state-action
distribution induced by policy to data distribution). Motivated by their work,
we propose a sample-efficient algorithm for offline constrained RL with
function approximation that requires concentrability, value function
realizability and MIW realizability assumptions. We make the following
contributions.

  * •

We show a sample complexity bound that scales with a concentrability measure,
$1/\epsilon^{2}$ and a dimensionality measure of function classes, for finding
a nearly optimal policy with suboptimality $\epsilon$ that approximately
satisfies the cost constraints under the assumptions of value function
realizability, concentrability, and MIW realizability of an optimal policy. We
do not require Bellman completeness, a strong representational assumption,
required by previous work.

  * •

Our algorithm takes as an input a target cost threshold. By using a target
cost threshold stricter than the desired threshold, the algorithm can produce
a nearly optimal policy that exactly satisfies the desired constraints with
the same sample complexity.

  * •

We study the case where the function class for MIW is misspecified and does
not realize the MIW of an optimal policy. In this case, our algorithm can
still find a policy at least as good as any policy of which MIW is realized by
the function class but the sample complexity bound is suboptimal and scales
with $1/\epsilon^{4}$.

  * •

Benchmark experiments show that the empirical performance of our algorithm
generally matches or outperforms the state-of-the-art practical algorithms
COptiDICE and CPQ that produce Markovian policies.

###  1.1 Related Work

#### Offline RL without Completeness Assumption

There is a recent line of works on offline _unconstrained_ RL that removes the
Bellman completeness assumption by assuming MIW realizability. [34] propose a
Q-value based algorithm called MABO that learns the optimal Q-value function
by solving a minimax optimization problem. They require all-policy
realizability of value functions, all-policy concentrability and all-policy
marginalized importance weight realizability. [38] propose a linear
programming based algorithm called PRO-RL that regularizes the objective
function to discourage distribution shift. They only require single-policy
realizability of both value function and marginalized importance weight, and
only require single-policy concentrability. However, their sample complexity
is suboptimal ($\sim 1/\epsilon^{6}$). [39] propose an actor-critic based
algorithm called A-Crab. They require all-policy value function realizability,
single-policy concentrability and single-policy marginalized importance weight
realizability.

#### Offline Constrained RL

The only work on provably sample efficient offline constrained RL with
function approximation, to the best of our knowledge, is by [19] who propose a
provably sample-efficient primal-dual algorithm that uses the fitted-Q
iteration algorithm as a subroutine for updating the primal variable and a no-
regret online algorithm for updating the dual variable. Their analysis
requires all-policy concentrability and Bellman completeness assumptions. Our
work improves over [19] by weakening the Bellman completeness assumption.

#### Practical Algorithms for Offline Constrained RL

There are recent works on practical algorithms for offline constrained RL
_without_ provable guarantees. [21] propose an algorithm called COptiDICE,
which is motivated by the linear programming approach for solving RL. [24]
propose CDT, an adaptation of the decision transformer framework for offline
RL [7] to the offline constrained RL setting. [35] propose CPQ, a Q-learning
based algorithm that penalizes out of distribution actions. [25] provide
datasets and benchmarks of aforementioned algorithms.

We compare our theoretical guarantees with previous works in Table 1. The
first three rows are works on offline _unconstrained_ RL with function
approximation that do not assume Bellman completeness. The remaining rows are
works on offline _constrained_ RL with function approximation. The column $N$
shows how the sample complexity bound scales with the error tolerance
$\epsilon$. $Q^{\pi}$ is the value function for the policy $\pi$; $w^{\pi}$ is
the marginalized importance weight of the policy $\pi$; sp is the span
function; $\pi^{\star}$ is the optimal policy. $\mathcal{T}^{\pi}$ is the
Bellman operator and $\forall\pi,\,\mathcal{T}^{\pi}f\in\mathcal{F}$ means
Bellman completeness. The notations used in the table are formally defined in
the next section.

Table 1: Comparison of algorithms for offline (constrained) RL with function approximation Algorithm |  Supports constraints | Assumptions | $N$
---|---|---|---
Representation | Data coverage | MIW
MABO [34] | No | $\forall\pi,Q^{\pi}\in\mathcal{F}$ | $\forall\pi,\|w^{\pi}\|_{2,\mu}\leq C_{\ell_{2}}$ | $\forall\pi,w^{\pi}\in\text{sp}(\mathcal{W})$ | $1/\epsilon^{2}$
PRO-RL [38] | No | $Q^{\pi^{\star}}\in\mathcal{F}$ | $\|w^{\pi^{\star}}\|_{\infty}\leq C_{\infty}^{\star}$ | $w^{\pi^{\star}}\in\mathcal{W}$ | $1/\epsilon^{6}$
A-Crab [39] | No | $\forall\pi,Q^{\pi}\in\mathcal{F}$ | $\|w^{\pi^{\star}}\|_{2,\mu}\leq C_{\ell_{2}}^{\star}$ | $w^{\pi^{\star}}\in\mathcal{W}$ | $1/\epsilon^{2}$
MBCL [19] | Yes | $\forall\pi,f;\mathcal{T}^{\pi}f\in\mathcal{F}$ | $\forall\pi,\|w^{\pi}\|_{\infty}\leq C_{\infty}$ |  | $1/\epsilon^{2}$
PDCA (Ours) | Yes | $\forall\pi,Q^{\pi}\in\mathcal{F}$ | $\forall\pi,\|w^{\pi}\|_{2,\mu}\leq C_{\ell_{2}}$ | $w^{\pi^{\star}}\in\mathcal{W}$ | $1/\epsilon^{2}$

Compared to the work by [19], we relax the Bellman completeness assumption at
the expense of introducing a MIW realizability of an optimal policy. The MIW
realizability is a mild assumption since function class $\mathcal{W}$ only
needs to include the MIW of an _optimal_ policy. Moreover, we show in Theorem
1 that even when $\mathcal{W}$ does not realize the MIW of an optimal policy,
our algorithm can find a policy that is at least as good as any policy whose
MIW is realizable by $\mathcal{W}$. This result allows robustness against
misspecification of $\mathcal{W}$.

##  2 PRELIMINARIES & NOTATIONS

#### Notation

We denote by $\Delta(\mathcal{X})$ the probability simplex over a finite set
$\mathcal{X}$. We denote by $\mathbb{R}_{+}$ the set of nonnegative real
numbers. We write
$\bm{\Delta}^{I}=\\{\bm{x}\in\mathbb{R}_{+}^{I}:\sum_{i=1}^{I}x_{i}\leq 1\\}$.
We denote by $\text{Unif}(\mathcal{X})$ the uniform distribution over
$\mathcal{X}$. We write $[N]=\\{1,\dots,N\\}$ for a natural number $N$. We
write $\bm{1}=(1,\dots,1)$ and $\bm{0}=(0,\dots,0)$. We write
$(\cdot)_{+}=\max\\{0,\cdot\\}$.

###  2.1 Constrained Markov Decision Process

We formulate offline constrained RL using an infinite-horizon discounted
constrained Markov decision process (CMDP)[1] defined by a tuple
$\mathcal{M}=\left(\mathcal{S},\mathcal{A},P,R,\\{C_{i}\\}_{i=1}^{I},\gamma,s_{0}\right)$,
where $\mathcal{S}$ is the state space, $\mathcal{A}$ is the action space,
$P:\mathcal{S}\times\mathcal{A}\rightarrow\Delta(\mathcal{S})$ is the
transition probability kernel,
$R:\mathcal{S}\times\mathcal{A}\rightarrow[0,1]$ is the reward function,
$C_{i}:\mathcal{S}\times\mathcal{A}\rightarrow[0,1],i=1,\dots,I$ are the cost
functions, $\gamma\in(0,1)$ is the discount factor, and $s_{0}\in\mathcal{S}$
is the initial state. We assume $R$ and $C_{i}$, $i=1,\dots,I$ are known to
the learner while $P$ is unknown.

A stationary policy $\pi:\mathcal{S}\rightarrow\Delta(\mathcal{A})$ maps each
state to a probability distribution over the action space. Each policy $\pi$,
together with the transition probability kernel $P$, induces a discounted
occupancy measure $d^{\pi}:\mathcal{S}\times\mathcal{A}\rightarrow[0,1]$
defined as
$d^{\pi}(s,a)\coloneqq(1-\gamma)\sum_{t=0}^{\infty}\gamma^{t}P^{\pi}(s_{t}=s,a_{t}=a)$
where $P^{\pi}$ is the probability measure on the trajectory
$(s_{0},a_{0},s_{1},a_{1},\dots)$ induced by the interaction of $\pi$ and $P$.
The value of a policy $\pi$ for a function
$U:\mathcal{S}\times\mathcal{A}\rightarrow[0,1]$ is the expected discounted
cumulative values when executing $\pi$. It is denoted by
$J_{U}(\pi)\coloneqq\mathbb{E}^{\pi}\left[\sum_{t=0}^{\infty}\gamma^{t}U(s_{t},a_{t})\right]$
where $\mathbb{E}^{\pi}$ is the expectation over the randomness of the
trajectory $(s_{0},a_{0},s_{1},a_{1},\dots)$ induced by $\pi$ and $P$. Note
that $J_{U}(\pi)\in[0,\frac{1}{1-\gamma}]$ and
$(1-\gamma)J_{U}(\pi)=\mathbb{E}_{\pi}[U(s,a)]$ where we use the shorthand
$\mathbb{E}_{\pi}[\cdot]$ for $\mathbb{E}_{(s,a)\sim d^{\pi}}[\cdot]$. The
Q-value function of a policy $\pi$ for a function
$U:\mathcal{S}\times\mathcal{A}\rightarrow[0,1]$ is denoted by
$Q_{U}^{\pi}(s,a)\coloneqq\mathbb{E}^{\pi}\left[\sum_{t=0}^{\infty}\gamma^{t}U(s_{t},a_{t})~{}|~{}s_{0}=s,a_{0}=a\right]$.

###  2.2 Function Approximation

We assume access to a policy class
$\Pi\subseteq(\pi:\mathcal{S}\rightarrow\Delta(\mathcal{A}))$ consisting of
candidate policies. We assume access to a function class
$\mathcal{F}\subseteq(\mathcal{S}\times\mathcal{A}\rightarrow[0,\frac{1}{1-\gamma}])$
that models the Q-value functions for the reward $R$ and the costs
$C_{1},\dots,C_{I}$. We make the following realizability assumption on
$\mathcal{F}$.

######  Assumption A (Value function realizability).

For any policy $\pi\in\Pi$, we have $Q^{\pi}_{R}\in\mathcal{F}$ and
$Q^{\pi}_{C_{i}}\in\mathcal{F}$ for all $i=1,\dots,I$.

Unlike [19], we do not assume Bellman completeness that requires
$\mathcal{T}_{U}^{\pi}f\in\mathcal{F}$ for all $\pi\in\Pi$ and
$f\in\mathcal{F}$ where $\mathcal{T}_{U}^{\pi}$ is the Bellman operator
defined by
$(\mathcal{T}_{U}^{\pi}f)(s,a)=U(s,a)+\gamma\mathbb{E}_{s^{\prime}\sim
P(\cdot|s,a)}[f(s^{\prime},\pi)]$. As [38] and [36] discuss, it is a strong
assumption hard to meet and has an unnatural non-monotone property: adding a
function to the function class may make the function class violate Bellman
completeness.

###  2.3 Offline Constrained RL

Offline constrained RL aims to find a policy
$\pi:\mathcal{S}\rightarrow\Delta(\mathcal{A})$ among a given policy class
$\Pi$ that maximizes $J_{R}(\pi)$ while satisfying the constraints
$J_{C_{i}}(\pi)\leq\tau_{i}$ for all $i=1,\dots,I$, where the thresholds
$\tau_{i}\in[0,\frac{1}{1-\gamma}]$ are given. Offline constrained RL can be
written as an optimization problem $\mathcal{P}(\bm{\tau})$ defined as
follows.

######  Definition 1 (Optimization problem).

Given cost thresholds $\bm{\tau}=(\tau_{1},\dots,\tau_{I})$, we denote by
$\mathcal{P}(\bm{\tau})$ the following optimization problem.

$\displaystyle\max_{\pi\in\mathrm{Conv}(\Pi)}$ $\displaystyle~{}~{}J_{R}(\pi)$
(OPT) $\displaystyle\mathrm{subject\ to}$
$\displaystyle~{}~{}J_{C_{i}}(\pi)\leq\tau_{i},~{}~{}i=1,\dots I.$

As done in [19], instead of optimizing over the policy class $\Pi$, we
optimize over its convex hull denoted by $\text{Conv}(\Pi)$. The convex hull
$\text{Conv}(\Pi)$ contains all policy mixtures of the form
$\sum_{j=1}^{m}\beta_{j}\pi_{j}$ where $\pi_{1},\dots,\pi_{m}\in\Pi$,
$\beta_{j}\geq 0$ for $j=1,\dots,m$ and $\sum_{j=1}^{m}\beta_{j}=1$. A policy
mixture $\sum_{j=1}^{m}\beta_{j}\pi_{j}$ is executed by sampling a single
policy from $\pi_{1},\dots,\pi_{m}$ according to the distribution
$(\beta_{1},\dots,\beta_{m})$, and then executing the sampled policy for the
entire trajectory. Viewing the problem in the occupancy measure space, (OPT)
can be seen as

$\displaystyle\max_{\nu\in\text{Conv}(\mathcal{V})}$
$\displaystyle~{}~{}\langle\nu,R\rangle$ (1) subject to
$\displaystyle~{}~{}\langle\nu,C_{i}\rangle\leq\tau_{i},~{}~{}i=1,\dots,I$

where $\mathcal{V}=\\{d^{\pi}:\pi\in\Pi\\}$ is the set of occupancy measures
of policies in $\Pi$ and $d^{\pi}$, $R$, $C_{i}$, $i=1,\dots I$ are viewed as
a vector in $\mathbb{R}^{|\mathcal{S}||\mathcal{A}|}$. Since we define a
mixture of policies in the trajectory level, the set of occupancy measures of
policies in $\text{Conv}(\Pi)$ is just the convex hull of $\mathcal{V}$. Since
the above is an optimization problem in the space of $\mathbb{R}^{|S||A|}$,
strong duality holds if we assume the following Slater’s condition.

######  Assumption B (Slater’s condition).

There exist a constant $\varphi>0$ and a policy $\pi\in\Pi$ such that
$J_{C_{i}}(\pi)\leq\tau_{i}-\frac{\varphi}{1-\gamma}$ for all $i=1,\dots,I$.
Assume $\varphi$ is known.

Slater’s condition is a mild assumption commonly made for constrained RL [19,
8, 3, 10] for ensuring strong duality of the optimization problem. It is mild
because given the knowledge of the feasibility of the problem, we can
guarantee that Slater’s condition is met by slightly loosening the cost
threshold.

###  2.4 Offline Dataset

In offline constrained RL, we assume access to an offline dataset
$\mathcal{D}=\\{(s_{j},a_{j},s_{j}^{\prime})\\}_{j=1}^{n}$ where
$(s_{j},a_{j})$ are generated i.i.d. from a data distribution $d^{\mu}$
induced by a behavior policy $\mu$ and $s_{j}^{\prime}\sim
P(\cdot~{}|~{}s_{j},a_{j})$. Such an i.i.d. assumption on the offline dataset
is commonly made in the offline RL literature [32, 38, 6, 39] to facilitate
analysis of concentration bounds. We assume the policy class $\Pi$ contains
$\mu$. We assume that the threshold $\bm{\tau}$ is chosen such that the
optimization problem $\mathcal{P}(\bm{\tau})$ is feasible. However, we do not
require the behavior policy $\mu$ to be feasible for $\mathcal{P}(\bm{\tau})$.
To limit the distribution shift of policies from the data distribution, we
make the following concentrability assumption, where we use the notation
$\|\cdot\|_{2,\mu}=\sqrt{\mathbb{E}_{\mu}[(\cdot)^{2}]}$.

######  Assumption C (Concentrability).

For all $\pi\in\Pi$, we have $\|d^{\pi}/d^{\mu}\|_{2,\mu}\leq C_{\ell_{2}}$.

The concentrability assumption limits distribution shift of candidate policies
from the data distribution. Specifically, the occupancy measure induced by a
policy in $\Pi$ is covered by the data distribution $d^{\mu}$. This assumption
is weaker than the assumption made by [19], who assume that the
$\ell_{\infty}$ norm of the distribution shift of following any nonstationary
policy that uses a policy in $\Pi$ every time step is bounded.

###  2.5 Marginalized Importance Weight

The notion of marginalized importance weight (MIW) is used extensively in the
offline RL literature [34, 6, 38, 39, 21, 20] to correct for the distribution
mismatch between a policy $\pi$ and the behavior policy $\mu$. It is defined
as follows.

######  Definition 2 (Marginalized importance weight).

For a policy $\pi$, we define the marginalized importance weight
$w^{\pi}:\mathcal{S}\times\mathcal{A}\rightarrow\mathbb{R}^{+}$ as
$w^{\pi}(s,a)\coloneqq\frac{d^{\pi}(s,a)}{d^{\mu}(s,a)}$.

Immediately from the definition of MIW, we get the identity
$\mathbb{E}_{\pi}[(\cdot)]=\mathbb{E}_{\mu}[w^{\pi}(s,a)(\cdot)]$, which we
frequently use in the analysis. We assume access to a function class
$\mathcal{W}$ consisting of functions
$w:\mathcal{S}\times\mathcal{A}\rightarrow\mathbb{R}_{+}$ that represents MIW
with respect to the offline data distribution $d^{\mu}$. We assume the
following boundedness assumption on $\mathcal{W}$.

######  Assumption D (Boundedness of $\mathcal{W}$).

Assume $\|w\|_{\infty}\leq C_{\infty}$ and $\|w\|_{2,\mu}\leq C_{\ell_{2}}$
for all $w\in\mathcal{W}$.

Denote by $\pi^{\star}$ an optimal policy of the optimization problem (OPT).
We assume that the MIW of $\pi^{\star}$ is realized by $\mathcal{W}$.

######  Assumption E (Realizability of MIW).

Assume that $w^{\pi^{\star}}\in\mathcal{W}$ for an optimal policy
$\pi^{\star}$.

The single-policy realizability of MIW that requires MIW of an optimal policy
to be realizable by $\mathcal{W}$ is a weaker assumption than the all-policy
realizability of MIW assumption required by [34]. Compared to the set of
assumptions made by [19], we replace the strong Bellman completeness
assumption with a single-policy realizability of MIW.

##  3 ALGORITHM & MAIN RESULTS

In this section, we present our algorithm called Primal-Dual-Critic Algorithm
(PDCA) and then present our main results on the the sample complexity bound.

###  3.1 Primal-Dual Algorithm Structure

The Lagrangian of the optimization problem $\mathcal{P}(\bm{\tau})$
(Definition 1) is
$L(\pi,\bm{\lambda})=J_{R}(\pi)+\bm{\lambda}\cdot(\bm{\tau}-J_{\bm{C}}(\pi))$
where we use the notation
$J_{\bm{C}}(\pi)=(J_{C_{1}}(\pi),\dots,J_{C_{I}}(\pi))$. Our algorithm, like
MBCL algorithm for offline constrained RL proposed by [19], adopts the primal-
dual algorithm structure that updates $\pi$ and $\bm{\lambda}$ alternatively.
The primal-dual algorithm structure can be seen as a sequential game of length
$K$ between the $\pi$-player who tries to maximize $L(\cdot,\bm{\lambda})$ and
the $\lambda$-player who tries to minimize $L(\pi,\cdot)$. Both players try to
minimize their regrets against respective best actions in hindsight.

The key difference of our algorithm from MBCL is that in each round $k$, the
$\pi$-player plays before the $\lambda$-player, while in MBCL, the order is
reversed. Since $\lambda$-player sees what $\pi$-player plays before playing,
the $\lambda$-player can act greedily to minimize the regret. On the other
hand, the $\pi$-player has to use a no-regret policy optimization oracle,
defined below, with a sublinear regret against adversarially chosen sequence
of $\lambda$’s.

######  Definition 3 (No-regret policy optimization oracle).

An algorithm is called a no-regret policy optimization oracle if for any
sequence of functions
$h_{1},\dots,h_{K}:\mathcal{S}\times\mathcal{A}\rightarrow[-1,1]$, the
sequence of policies $\pi_{1},\dots,\pi_{K}\in\Pi$ produced by the algorithm
satisfies

$\frac{1}{K}\sum_{k=1}^{K}\mathbb{E}_{\pi}[h_{k}(s,\pi)-h_{k}(s,\pi_{k})]=\epsilon_{\text{opt}}(K)$

with high probability for any $\pi\in\mathrm{Conv}(\Pi)$ where
$\epsilon_{\text{opt}}(K)\rightarrow 0$ as $K\rightarrow\infty$.

A well-known instance of the oracle is the natural policy gradient algorithm
[17] based on the updates $\pi_{k+1}(a|s)\propto\pi_{k}(a|s)\exp(\eta
h_{k}(s,a))$.

###  3.2 Critics for Lagrangian

We want to estimate the Lagrangian function
$L(\pi,\bm{\lambda})=J_{R}(\pi)+\bm{\lambda}\cdot(\bm{\tau}-J_{\bm{C}}(\pi))$
for all $\pi\in\Pi$ and $\bm{\lambda}\in B\bm{\Delta}^{I}$. We use critics for
$J_{R}(\pi)$ and $J_{\bm{C}}(\pi)$ that are inspired by the reward critic
proposed by [39] for their actor-critic algorithm for offline unconstrained
RL. Our critic for $J_{U}(\pi)$ aims to solve

$\min_{f\in\mathcal{F}}~{}2\mathcal{E}_{\mu}(\pi,f;U)\pm A_{\mu}(\pi,f)$

where the sign of $A_{\mu}$ is appropriately chosen and

$\displaystyle\mathcal{E}_{\mu}(\pi,f;U)$
$\displaystyle\coloneqq\max_{w\in\mathcal{W}}|\mathbb{E}_{\mu}[w(s,a)(f-\mathcal{T}^{\pi}_{U}f)(s,a)]|$
$\displaystyle A_{\mu}(\pi,f)$
$\displaystyle\coloneqq\mathbb{E}_{\mu}[f(s,\pi)-f(s,a)].$

Here,
$\mathcal{T}_{U}^{\pi}:\mathbb{R}^{\mathcal{S}\times\mathcal{A}}\rightarrow\mathbb{R}^{\mathcal{S}\times\mathcal{A}}$
is the Bellman operator with
$(\mathcal{T}_{U}^{\pi}f)(s,a)=U(s,a)+\gamma\mathbb{E}_{s^{\prime}\sim
P(\cdot~{}|~{}s,a)}[f(s^{\prime},\pi)]$ and
$f(s,\pi)=\sum_{a\in\mathcal{A}}\pi(a|s)f(s,a)$. Minimizing the first term
$\mathcal{E}_{\mu}$ in the objective function of the critics encourages
Bellman-consistency. The second term, with appropriate sign, facilitates the
regret bound analysis for the $\pi$-player. Since the data distribution of the
behavior policy $d^{\mu}$ is unknown, we solve an empirical version
$\min_{f\in\mathcal{F}}2\mathcal{E}_{\mathcal{D}}(\pi,f;U)+A_{\mathcal{D}}(\pi,f)$
where

$\displaystyle\mathcal{E}_{\mathcal{D}}(\pi,f;U)$
$\displaystyle\coloneqq\max_{w\in\mathcal{W}}|\mathbb{E}_{\mathcal{D}}[w(s,a)(f(s,a)-U(s,a)-\gamma
f(s^{\prime},\pi))]|$ $\displaystyle A_{\mathcal{D}}(\pi,f)$
$\displaystyle\coloneqq\mathbb{E}_{\mathcal{D}}[f(s,\pi)-f(s,a)].$

Here,
$\mathbb{E}_{\mathcal{D}}[F(s,a,s^{\prime})]=\frac{1}{|\mathcal{D}|}\sum_{(s,a,s^{\prime})\in\mathcal{D}}F(s,a,s^{\prime})$.
The critics for the reward value $J_{R}(\pi)$ and the cost value
$J_{C_{i}}(\pi)$ are chosen to be

Reward critic:
$\displaystyle\quad\min_{f\in\mathcal{F}}2\mathcal{E}_{\mathcal{D}}(\pi,f;R)+A_{\mathcal{D}}(\pi,f)$
(2) Cost critic:
$\displaystyle\quad\min_{g\in\mathcal{F}}2\mathcal{E}_{\mathcal{D}}(\pi,g;C_{i})-A_{\mathcal{D}}(\pi,g).$
(3)

Note that we use the same reward critic as the one used in [39], but we negate
the term $\mathcal{A}_{\mathcal{D}}$ for the cost critic.

###  3.3 Cost Critic for $\lambda$-Player

While the $\pi$-player optimizes for the Lagrangian estimated by critics (2)
and (3) in the previous section, the $\lambda$-player optimizes for
$\bm{\lambda}\cdot(\bm{\tau}-J_{\bm{C}}(\pi_{k}))$ estimated by an offline
policy evaluation (OPE) oracle.

######  Definition 4 (OPE oracle).

Let $\pi$ be a policy and $U$ a utility function. Let $\mathcal{F}$ be a
function class that contains the value function $Q_{U}^{\pi}$. Suppose the
dataset $\mathcal{D}=\\{(s_{j},a_{j},s_{j}^{\prime})\\}_{j=1}^{n}$ is
generated with a behavior policy $\mu$ is a behavior policy with sufficient
coverage such that $\|d^{\pi}/d^{\mu}\|_{2,\mu}\leq C_{\ell_{2}}$. An
algorithm that produces an estimate $h\in\mathbb{R}$ for $J_{U}(\pi)$ such
that

$|h-J_{U}(\pi)|\leq\mathcal{O}\left(\frac{C_{\ell_{2}}}{1-\gamma}\sqrt{\frac{\log(|\mathcal{F}|/\delta)}{n}}\right)$

with probability at least $1-\delta$ is called an OPE oracle.

An example of such an oracle is provided by [36] whose algorithm produces an
estimate with error decreasing at the required rate scaled by a constant
factor called the incompleteness factor inherent to $\mathcal{F}$ that
measures misalignment between $\mathcal{F}$ and
$\mathcal{T}^{\pi}\mathcal{F}$.

######  Remark 1.

We use a separate OPE cost critic for estimating the objective function of the
$\lambda$-player instead of reusing the cost critic (3) used for estimating
the Lagrangian for the $\pi$-player. This is because the regrets for the two
players take different forms. As we show in Section 4.1, the regret of
$\pi$-player is the sum of
$J_{R+\bm{\lambda}_{k}\cdot\bm{C}}(\pi^{\star})-J_{R+\bm{\lambda}_{k}\cdot\bm{C}}(\pi_{k})$
while the regret of $\lambda$-player is the sum of
$(\bm{\lambda}_{k}-\bm{\lambda}^{\star})\cdot(\bm{\tau}-J_{\bm{C}}(\pi_{k}))$.
Since the regret minimizing decision for $\lambda$-player depends on the sign
of $\tau-J_{C_{i}}(\pi_{k})$, we need to estimate $J_{C_{i}}(\pi_{k})$, which
involves calling an OPE oracle. This is why we require concentrability of all
policies in $\Pi$. We leave relaxing to a single-policy concentrability
assumption as future work.

Input: Dataset $\mathcal{D}=\\{(s_{j},a_{j},s_{j}^{\prime})\\}_{j=1}^{n}$,
number of iterations $K$, cost thresholds $\bm{\tau}$, bound $B$, , no-regret
policy optimization oracle PO, offline policy evaluation oracle OPE.

Initialize: $\pi_{1}$: uniform policy.

1 for  _$k=1,\dots,K$_ do

2
$f_{k}\leftarrow\operatorname*{argmin}_{f\in\mathcal{F}}2\mathcal{E}_{\mathcal{D}}(\pi_{k},f;R)+A_{\mathcal{D}}(\pi_{k},f)$.

3
$g_{k}^{i}\leftarrow\operatorname*{argmin}_{g\in\mathcal{F}}2\mathcal{E}_{\mathcal{D}}(\pi_{k},g;C_{i})-A_{\mathcal{D}}(\pi_{k},g)$
for all $i=1,\dots,I$.

4 $h_{k}^{i}\leftarrow\text{OPE}(\pi_{k},C_{i})$ for all $i=1,\dots,I$.

5 $\bm{\lambda}_{k}\leftarrow\operatorname*{argmin}_{\bm{\lambda}\in
B\bm{\Delta}^{I}}\bm{\lambda}\cdot(\bm{\tau}-\bm{h}_{k})$.

6
$\pi_{k+1}\leftarrow\textsc{PO}(\pi_{k},f_{k}+\bm{\lambda}_{k}\cdot(\bm{\tau}-\bm{g}_{k}))$.

7

Return: $\bar{\pi}=\text{Unif}(\pi_{1},\dots,\pi_{K})$

Algorithm 1 Primal-Dual-Critic Algorithm

###  3.4 Proposed Algorithm

We propose an algorithm called Primal-Dual-Critic Algorithm (PDCA) (Algorithm
1) that uses critics for the Lagrangian function and no-regret policy
optimization oracle for the $\pi$-player and a greedy $\lambda$-player. The
algorithm takes cost thresholds $\bm{\tau}$ as an input and runs a primal-dual
algorithm on the estimate of Lagrangian
$L(\pi,\bm{\lambda})=J_{R}(\pi)+\bm{\lambda}\cdot(\bm{\tau}-J_{\bm{C}}(\pi))$.

The algorithm iterates for $K$ steps. In each step $k$, the algorithm
calculates the reward critic $f_{k}$ and the cost critics
$\bm{g}_{k}=(g_{k}^{1},\cdots,g_{k}^{I})$ using the offline dataset
$\mathcal{D}$. Then, the $\pi$-player invokes a no-regret policy optimization
oracle on the estimate $f_{k}+\bm{\lambda}_{k}\cdot(\bm{\tau}-\bm{g}_{k})$.
The OPE oracle is used to estimate $J_{\bm{C}}(\pi_{k})$ by
$\bm{h}_{k}(s_{0},\pi_{k})$, and the $\lambda$-player chooses
$\bm{\lambda}_{k}$ that minimizes $\bm{\lambda}\cdot(\bm{\tau}-\bm{h}_{k})$.

After running the iterations, the algorithm returns the policy
$\bar{\pi}=\text{Unif}(\pi_{1},\dots,\pi_{K})$, which is a uniform mixture of
the policies $\pi_{1},\dots,\pi_{K}$. The uniform mixture policy initially
samples a policy uniformly at random from $\\{\pi_{1},\dots,\pi_{K}\\}$, and
then follows the sampled policy for the entire trajectory.

###  3.5 Main Results

Our main theoretical result is a sample complexity bound of our algorithm
called Primal-Dual-Critic Algorithm (PDCA) (Algorithm 1) for finding a policy
that satisfies the constraints approximately and is $\epsilon$-optimal with
respect to the optimal policy $\pi^{\star}$ for $\mathcal{P}(\bm{\tau})$.

theoremmainthm Under assumptions A,B,C,D and E, the policy $\bar{\pi}$
returned by the PDCA algorithm (Algorithm 1) with the cost threshold
$\bm{\tau}$, bound $B=1+\frac{1}{\varphi}$ and $K$ large enough, satisfies
$J_{C_{i}}(\bar{\pi})\leq\tau_{i}+\mathcal{O}(\epsilon)$ for all
$i=1,\dots,I$, and $J_{R}(\bar{\pi})\geq
J_{R}(\pi^{\star})-\mathcal{O}(\epsilon)$ with probability at least $1-\delta$
where $\pi^{\star}$ is an optimal policy for $\mathcal{P}(\bm{\tau})$ as long
as

$n\geq\Omega\left(\frac{(C_{\ell_{2}})^{2}\log(I|\mathcal{F}||\Pi||\mathcal{W}|/\delta)}{(1-\gamma)^{4}\varphi^{2}\epsilon^{2}}\right).$

The sample complexity bound provided by [19] is
$\Omega(\frac{C_{\infty}(\text{dim}_{F}+\log(I/\delta))}{(1-\gamma)^{10}\epsilon^{2}})$
where $\text{dim}_{F}$ is a complexity measure of the function class they use
for the Lagrangian function, which is analogous to the log cardinality term
$\log|\mathcal{F}|$ in our finite function class setting. Compared to their
bound, our bound saves a factor of $\frac{1}{(1-\gamma)^{6}}$ and depends on
concentrability coefficient $C_{\ell_{2}}$ instead of $C_{\infty}$. As [39]
discuss, $(C_{\ell_{2}})^{2}\leq C_{\infty}$ and $C_{\infty}$ can be
arbitrarily larger than $(C_{\ell_{2}})^{2}$. Also, our algorithm requires
weaker assumptions. While [19] require $\ell_{\infty}$ concentrability for all
sequences of policies, we require $\ell_{2}$ concentrability for fixed
policies. While [19] require Bellman completeness for the value function
class, we only require realizability. The only additional assumption we need
is the single-policy realizability of the marginalized importance weight.

With different choices of inputs to the PDCA algorithm, we get the following
results. See Appendix E for the formal statements and proofs.

#### Arbitrary Comparator Policy

(Theorem 1) Without the Slater’s condition and the MIW realizability
assumptions, running PDCA with the cost threshold $\bm{\tau}$ and the bound
$B=\frac{1}{(1-\gamma)\epsilon}$ gives a policy $\bar{\pi}$ that is nearly
feasible and satisfies near-optimality ($J_{R}(\bar{\pi})\geq
J_{R}(\pi_{c})-\mathcal{O}(\epsilon)$) against any comparator policy
$\pi_{c}\in\text{Conv}(\Pi)$ of which MIW is realizable by $\mathcal{W}$.
However, the sample complexity bound is of $\mathcal{O}(1/\epsilon^{4})$.

#### Exact Feasibility

(Theorem 2) With the same sample complexity as in Theorem 3.5, running PDCA
with a tightened cost threshold $\bm{\tau}-\eta\bm{1}$ where
$\eta=\mathcal{O}(\epsilon)$ and the bound $B=\mathcal{O}(\frac{1}{\varphi})$
gives a policy $\bar{\pi}$ that is exactly feasible
($J_{\bm{C}}(\bar{\pi})\leq\bm{\tau}$) and nearly optimal
($J_{R}(\bar{\pi})\geq J_{R}(\pi^{\star})-\mathcal{O}(\epsilon)$).

##  4 ANALYSIS

In this section, we provide a proof sketch for Theorem 3.5. We show in Section
4.1 that PDCA finds a near saddle point of the Lagrangian. We show in Section
4.2 that the near saddle point approximately solves the optimization problem
(OPT). We use the notation $a\lesssim b$ to indicate $a\leq b+\zeta(n,K)$ and
$a\approx b$ to indicate $a=b+\zeta(n,K)$ where $\zeta(n,K)\rightarrow 0$ as
$n,K\rightarrow\infty$.

###  4.1 PDCA Finds a Near Saddle Point

We show that PDCA run with thresholds $\bm{\tau}$ and bound $B$ finds a near
saddle point of the Lagrangian
$L(\pi,\bm{\lambda})=J_{R}(\pi)+\bm{\lambda}\cdot(\bm{\tau}-J_{\bm{C}}(\pi))$:
the policy $\bar{\pi}$ returned by PDCA and
$\bar{\bm{\lambda}}=\frac{1}{K}\sum_{k=1}^{K}\bm{\lambda}_{k}$ for
sufficiently large $K$ satisfy

$L(\pi,\bar{\bm{\lambda}})\leq
L(\bar{\pi},\bm{\lambda})+\mathcal{O}(\epsilon_{\text{stat}})$

for all $\pi\in\text{Conv}(\Pi)$ with $w^{\pi}\in\mathcal{W}$ and
$\bm{\lambda}\in B\bm{\Delta}^{I}$ where
$\epsilon_{\text{stat}}=\mathcal{O}(1/\sqrt{n})$ is a statistical error term
for estimating $\mathcal{E}_{\mu}$ and $A_{\mu}$. See Appendix B for the full
analysis of $\epsilon_{\text{stat}}$. To show that
$(\bar{\pi},\bar{\bm{\lambda}})$ is a near saddle point, we decompose
$L(\pi,\bar{\bm{\lambda}})-L(\bar{\pi},\bm{\lambda})$ into regrets of the
$\pi$-player and the $\lambda$-player, and bound each regret separately as
follows. See Appendix C for full proof.

#### Regret Bound for $\pi$-Player

Regret of $\pi$-player
$\frac{1}{K}\sum_{k=1}^{K}L(\pi,\bm{\lambda}_{k})-\frac{1}{K}\sum_{k=1}^{K}L(\pi_{k},\bm{\lambda}_{k})$
simplifies to
$\frac{1}{K}\sum_{k=1}^{K}(J_{R}(\pi)-J_{R}(\pi_{k}))+\frac{1}{K}\sum_{k=1}^{K}\bm{\lambda}_{k}\cdot(J_{\bm{C}}(\pi_{k})-J_{\bm{C}}(\pi))$.
Decomposing $J_{R}(\pi)-J_{R}(\pi_{k})$ by performance difference lemma (Lemma
12 in [9]) and using the properties of the critics give

$(1-\gamma)(J_{R}(\pi)-J_{R}(\pi_{k}))\lesssim\mathbb{E}_{\pi}[f_{k}(s,\pi)-f_{k}(s,\pi_{k})]$

which shows the performance difference with respect to the reward function $R$
can be upper bounded by the difference of the reward critic. Similarly, we
have

$(1-\gamma)(J_{C_{i}}(\pi_{k})-J_{C_{i}}(\pi))\lesssim\mathbb{E}_{\pi}[g_{k}^{i}(s,\pi_{k})-g_{k}^{i}(s,\pi)],$

for all $i=1,\dots,I$, and it follows that

$\displaystyle\textstyle\frac{1}{K}$
$\displaystyle\textstyle\sum_{k=1}^{K}L(\pi,\bm{\lambda}_{k})-\frac{1}{K}\textstyle\sum_{k=1}^{K}L(\pi_{k},\bm{\lambda}_{k})$
$\displaystyle\lesssim\textstyle\frac{1}{K}\textstyle\sum_{k=1}^{K}\mathbb{E}_{\pi}[z_{k}(s,\pi)-z_{k}(s,\pi_{k})]\leq\frac{1}{K}\epsilon_{\text{opt}}(K)$

where $z_{k}=f_{k}+\bm{\lambda}_{k}\cdot(\bm{\tau}-\bm{g}_{k})$ is the input
to policy optimization oracle (Definition 3) used by $\pi$-player; the last
inequality is by the property of the oracle.

#### Regret Bound for $\lambda$-Player

The regret of the $\lambda$-player
$\frac{1}{K}\sum_{k=1}^{K}L(\pi_{k},\bm{\lambda}_{k})-L(\bar{\pi},\bm{\lambda})$
can be simplified to
$\frac{1}{K}\sum_{k=1}^{K}(\bm{\lambda}_{k}-\bm{\lambda})\cdot(\bm{\tau}-J_{\bm{C}}(\pi_{k}))$.
Recall that PDCA calls OPE oracle to estimate $J_{C_{i}}(\pi_{k})\approx
h_{k}^{i}$. Since the $\lambda$-player greedily chooses $\bm{\lambda}_{k}\in
B\bm{\Delta}^{I}$ that minimizes $\bm{\lambda}\cdot(\bm{\tau}-\bm{h}_{k})$, we
have for all $\bm{\lambda}\in B\bm{\Delta}^{I}$ that

$\textstyle\frac{1}{K}\textstyle\sum_{k=1}^{K}(\bm{\lambda}_{k}-\bm{\lambda})\cdot(\bm{\tau}-J_{\bm{C}}(\pi_{k}))\approx\textstyle\frac{1}{K}\textstyle\sum_{k=1}^{K}(\bm{\lambda}_{k}-\bm{\lambda})\cdot(\bm{\tau}-\bm{h}_{k})\leq
0.$

###  4.2 A Near Saddle Point Nearly solves OPT

We can show that if the Slater’s condition (Assumption B) holds, then a near
saddle point $(\bar{\pi},\bar{\bm{\lambda}})$ of $L(\cdot,\cdot)$ that
satisfies $L(\pi,\bar{\bm{\lambda}})\leq L(\bar{\pi},\bm{\lambda})$ for all
$\pi\in\text{Conv}(\Pi)$ with $w^{\pi}\in\mathcal{W}$ and $\bm{\lambda}\in
B\bm{\Delta}^{I}$, then

$\displaystyle J_{R}(\bar{\pi})$ $\displaystyle\geq J_{R}(\pi^{\star})-\xi$
$\displaystyle J_{C_{i}}(\bar{\pi})$
$\displaystyle\leq\tau_{i}+\textstyle\frac{\xi}{B-1/\varphi},\quad
i=1,\dots,I$

where $\pi^{\star}\in\text{Conv}(\Pi)$ is the optimal policy for
$\mathcal{P}(\bm{\tau})$. See Appendix D for the proof of the above result.
Combining the results in Section 4.1 and Section 4.2, Theorem 3.5 follows. See
Appendix E for the full proof.

##  5 EXPERIMENTS

To demonstrate the empirical performance of our algorithm, we compare with
MBCL [19], the only previous work with provable guarantees, and the following
practical algorithms for offline constrained RL: COptiDICE [21], CDT [24], CQP
[35]. For comparing with MBCL, we use tabular setting since MBCL can only run
with discrete action set. For computational efficiency in solving the min-max
optimization problems in Line 1,1 of Algorithm 1, we take
$\mathcal{W}=[0,C_{\infty}]^{\mathcal{S}\times\mathcal{A}}$ where the bound
$C_{\infty}$ is treated as a hyperparameter. Such $\mathcal{W}$ reduces
$\mathcal{E}_{\mathcal{D}}(\pi,f;U)$ to

$\displaystyle\mathcal{E}_{\mathcal{D}}(\pi,f;U)$
$\displaystyle=\max_{w\in\mathcal{W}}|\mathbb{E}_{\mathcal{D}}[w(s,a)(f(s,a)-U(s,a)-\gamma
f(s^{\prime},\pi))]|$
$\displaystyle=C_{\infty}\max\\{\mathbb{E}_{\mathcal{D}}[(f(s,a)-U(s,a)-\gamma
f(s^{\prime},\pi))_{+}],\mathbb{E}_{\mathcal{D}}[(U(s,a)+\gamma
f(s^{\prime},\pi)-f(s,a))_{+}]\\}.$

Following experimental settings of previous works, we use a single cost signal
($I=1$) for all experiments. For experimental details, see Appendix G.

Figure 1: Tabular CMDP experiment

###  5.1 Tabular Experiments

Following [21], we randomly generate tabular CMDP with 10 states and 5 actions
and prepare an offline dataset using a data distribution induced by a mixture
of uniform policy and the optimal policy. We compare the performance of PDCA
to MBCL and COptiDICE on datasets of varying sizes. For each dataset size, we
repeat the experiments 10 times and report the average of the reward value and
the cost value. Figure 1 shows the result. The shaded region indicates the
standard error. Overall, PDCA outperforms MBCL and is comparable to COptiDICE.

###  5.2 Real-World RL Benchmark Experiments

Input: Dataset $\mathcal{D}=\\{(s_{j},a_{j},s_{j}^{\prime})\\}_{j=1}^{n}$

Initialize: Network $f_{\theta}$ for reward critic; $g^{i}_{\theta^{i}}$,
$i=1,\dots,I$ for cost critics; $h^{i}_{\vartheta^{i}}$, $i=1,\dots,I$ for
OPE. Policy network $\pi_{\psi}$.

1 for  _$k=1,2,\dots,K$_ do

2 Sample a minibatch $\mathcal{D}_{\text{mini}}$ from dataset $\mathcal{D}$.

// Update critics

3
$\ell_{\text{reward}}(\theta)=2\mathcal{E}_{\mathcal{D}_{\text{mini}}}(f_{\theta},\pi_{\psi})+A_{\mathcal{D}_{\text{mini}}}(f_{\theta},\pi_{\psi})$.

4
$\ell_{\text{cost}}(\theta^{i})=2\mathcal{E}_{\mathcal{D}_{\text{mini}}}(g^{i}_{\theta^{i}},\pi_{\psi})-A_{\mathcal{D}_{\text{mini}}}(g^{i}_{\theta^{i}},\pi_{\psi})$
for $i=1,\dots,I$.

5
$\ell_{\text{ope}}(\theta^{i})=\mathcal{E}_{\mathcal{D}_{\text{mini}}}(g^{i}_{\theta^{i}},\pi_{\psi})$
for $i=1,\dots I$.

6
$\theta\leftarrow\textsc{Adam}(\pi_{\psi},\nabla\ell_{\text{reward}}(\theta),\eta_{\text{fast}})$.

7
$\theta^{i}\leftarrow\textsc{Adam}(\pi_{\psi},\nabla\ell_{\text{cost}}(\theta^{i}),\eta_{\text{fast}})$,
$i=1,\dots,I$.

8
$\vartheta^{i}\leftarrow\textsc{Adam}(\pi_{\psi},\nabla\ell_{\text{ope}}(\vartheta^{i}),\eta_{\text{fast}})$,
$i=1,\dots,I$.

// Update $\pi$.

9
$\ell_{\text{actor}}(\psi)=-A_{\mathcal{D}_{\text{mini}}}(f_{\theta}+\sum_{i=1}^{I}\lambda_{i}(\tau_{i}-g^{i}_{\theta^{i}}),\pi_{\psi})$.

10 $\psi\leftarrow\textsc{Adam}(\ell_{\text{actor}},\eta_{\text{slow}})$.

// Update $\lambda$.

11 $z_{i}\leftarrow\tau_{i}-h^{i}_{\theta^{i}}(s_{0},\pi_{\psi})$, for
$i=1,\dots,I$

12 $\lambda_{i}\leftarrow B$ if $z_{i}<0$ otherwise $\lambda_{i}\leftarrow 0$,
$i=1,\dots,I$.

Algorithm 2 Practical Version of PDCA

We follow the experimental setup in [21] and run the algorithms on 4
environments provided in the Real-World RL (RWRL) suite [11]. For the
benchmark experiments, we use a practical version of PDCA shown in Algorithm
2. We parameterize the function class $\mathcal{F}$ with neural networks. The
reward critic uses a neural network $f_{\theta}$ parameterized by $\theta$ and
each cost critic for the cost $C_{i}$ uses a neural network
$g^{i}_{\theta^{i}}$ parameterized by $\theta^{i}$. For solving the
optimization problems, the reward critic uses stochastic gradient descent
algorithm with a learning rate $\eta_{\text{fast}}$ on the loss
$2\mathcal{E}_{\mathcal{D}}(f_{\theta},\pi)+A_{\mathcal{D}}(f_{\theta},\pi)$.
Similarly, the cost critic uses stochastic gradient descent algorithm with the
same learning rate $\eta_{\text{fast}}$ on the loss
$2\mathcal{E}_{\mathcal{D}}(f_{\theta},\pi)-A_{\mathcal{D}}(f_{\theta},\pi)$.
Following the practical version of no-regret policy optimization oracle
implemented by [9], we use a policy network to parameterize $\Pi$. The
$\pi$-player uses a neural network $\pi_{\psi}$ parameterized by $\psi$ and
use a stochastic gradient descent algorithm on the loss
$-A_{\mathcal{D}}(f_{\theta}+\bm{\lambda}\cdot(\bm{\tau}-\bm{g}_{\bm{\theta}}),\pi_{\psi})$.
For the OPE oracle, we use a neural network $h^{i}_{\vartheta^{i}}$
parameterized by $\vartheta^{i}$ and use a stochastic gradient descent
algorithm on the loss $\mathcal{E}_{\mathcal{D}}(h^{i}_{\vartheta^{i}},\pi)$
with learning rate $\eta_{\text{fast}}$. The $\lambda$-player acts greedily
and chooses $\bm{\lambda}\in B\bm{\Delta}^{I}$ that minimizes
$\bm{\lambda}\cdot(\bm{\tau}-\bm{h}_{\vartheta}(s_{0},\pi_{\psi}))$. See
Appendix G.2 for hyperparameter tuning details.

#### Environments

We run experiments on four environments provided in the Real-World RL (RWRL)
Benchmark suite [11] used by [21]: Cartpole, Walker, Quadruped, and Humanoid.
Following [21], for each environment, we choose the most challenging safety
condition among the multiple safety conditions provided by RWRL suite. We give
the cost of 1 if the safety condition is violated at each time step. The
thresholds on the expected discounted cumulative costs are 0.05 for Cartpole
and Walker, and 0.01 for Quadruped and Humanoid. We follow the same safety
coefficient parameters (difficulty levels provided by RWRL suite) used by
[21]: for Cartpole and Walker we use 0.3, and for Quadruped and Humanoid we
use 0.5.

#### Offline Dataset Generation

Since RWRL suite does not provide an offline dataset we generate one for each
environment by a policy trained by an online RL algorithm using a reward
function penalized by cost function, $R-\lambda C$, where we vary $\lambda$.
Specifically, for each environment, we choose three different $\lambda$ values
and for each $\lambda$, we run the soft actor-critic algorithm (SAC) [15] with
the reward function $R-\lambda C$. The SAC algorithm is run for 1,000,000
steps. For each policy trained with different $\lambda$ values, we generate
1,000 trajectories. During trajectory generation, actions are perturbed with
Gaussian noise with mean=0 and std=0.15. The three sets of trajectories, one
for each $\lambda$, are mixed to form an offline dataset consisting of 3,000
trajectories. For the $\lambda$ values, we use $0.3,0.8,1$ for Cartpole,
$1,1.8,2$ for Walker, $0,0.1,0.5$ for Quadruped, $0,0.4,0.5$ for Humanoid.

#### Evaluation

Every 1000 iterations, we evaluate the policy by running it on the environment
online and recording the trajectories 5 times. We report the average
discounted cumulative reward and cost and their standard errors. Figure 2
shows comparison of the performance of our algorithm and COptiDICE on 4 RWRL
environments. The black dotted horizontal line indicates the cost threshold.
The blue and red lines indicate the cumulative cost and reward for PDCA and
COptiDICE respectively. For the Cartpole environment, PDCA outperforms
COptiDICE. For the Walker environment, PDCA requires more iterations to
converge and the performance is comparable to COptiDICE. For the Quadruped
environment, the cumulative rewards for PDCA and COptiDICE are comparable, but
COptiDICE tends to produce a policy that is constraint-violating. For the
Humanoid environment, PDCA is comparable to COptiDICE.

Figure 2: RWRL Benchmark Experiments

###  5.3 Safety Gym Benchmark Experiments

We run PDCA on the bullet safety gym [13] with offline datasets provided by
[25] and compare the performance of PDCA to CDT [24], CPQ [35] and COptiDICE
[21]. See Appendix G.3 for the details of the offline datasets and
hyperparameter tuning procedure.

#### Environments

The Bullet Safety Gym [13] provides environments based on physics simulator
where the agent can move around the physical environment scattered with
obstacles. The layout of the obstacles is not fixed and randomly generated in
each episode. For our benchmark experiments, we use the three different
agents: ball that can move freely on a plane and is controlled by a two-
dimensional force vector; car that can control wheel velocities and steering
angle; ant that is quadrupedal composed of nine rigid bodies with each leg
controlled by two actuators. We use two different tasks. The circle task
encourages the agent to move on a circle. The reward signal depends on the
speed of the agent and the proximity of the agent to the boundary. Costs are
incurred when the agent leaves the circle. The run task rewards the agent for
running through an avenue between two safety boundaries. The agent incurs
costs when exceeding speed limit.

#### Evaluation

Following the evaluation protocol by [25], we run with cost thresholds set to
10, 20, 40. For each of the cost threshold, we run with 3 random seeds. We
report the average performance across the 9 runs for each environment. To
approximate the uniform mixture of historical policies produced by PDCA, we
take policies every 2500 iterations and report the average of the performance
of the policies. The performance of each policy is measured by running the
policy on the corresponding environment for 20 episodes and taking the average
of the discounted cumulative reward/cost. When reporting, the cost value is
normalized so that the cost threshold is scaled to 1. See Table 2 for the
results. The column R is the reward and C the cost averaged over three random
seeds and three cost thresholds. Cost is normalized such that the threshold
value is 1. Boldfaced numbers indicate cost values that exceed the threshold.
The performance of PDCA is generally not dominated by CPQ and COptiDICE in the
sense that none of the algorithms outperform PDCA in terms of both reward and
cost violation. The transformer based algorithm CDT generally outperforms
other algorithms. We believe that this is because CDT learns non-Markovian
policies, which may be better suited for the benchmark environments.

Table 2: Safety Gym Results (Cost Threshold = 1.00) Task | CDT | CPQ | COptiDICE | PDCA
---|---|---|---|---
R | C | R | C | R | C | R | C
AntCircle | 0.54 | 1.78 | 0.00 | 0.00 | 0.17 | 5.04 | 0.22 | 3.53
AntRun | 0.72 | 0.91 | 0.03 | 0.02 | 0.61 | 0.94 | 0.28 | 0.93
BallCircle | 0.77 | 1.07 | 0.64 | 0.76 | 0.70 | 2.61 | 0.63 | 2.29
BallRun | 0.39 | 1.16 | 0.22 | 1.27 | 0.59 | 3.52 | 0.55 | 3.38
CarCircle | 0.75 | 0.95 | 0.71 | 0.33 | 0.49 | 3.14 | 0.22 | 2.42

##  6 CONCLUSION

We propose a primal-dual algorithm PDCA for offline constrained RL with
function approximation. PDCA is sample-efficient under concentrability, value
function realizability and MIW realizability assumptions, which relaxes
Bellman completeness assumption required by previous work. PDCA requires all-
policy concentrability only to guarantee the concentration bound on the
estimates returned by OPE. Relaxing this to the single-policy concentrability
assumption is an interesting future work that will likely require using
pessimistic estimates for the costs and modifying the strategy of the
$\lambda$-player to work with pessimistic estimates.

## Bibliography

  * [1] Eitan Altman  “Constrained Markov Decision Processes: Stochastic Modeling”, 1999
  * [2] András Antos, Csaba Szepesvári and Rémi Munos  “Learning near-optimal policies with Bellman-residual minimization based fitted policy iteration and a single sample path”  In _Machine Learning_ , 2008
  * [3] Qinbo Bai, Amrit Singh Bedi, Mridul Agarwal, Alec Koppel and Vaneet Aggarwal  “Achieving Zero Constraint Violation for Constrained Reinforcement Learning via Primal-Dual Approach”  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , 2022
  * [4] Stephen P. Boyd and Lieven Vandenberghe  “Convex optimization”, 2004
  * [5] Jinglin Chen and Nan Jiang  “Information-Theoretic Considerations in Batch Reinforcement Learning”  In _Proceedings of the 36th International Conference on Machine Learning_ , 2019
  * [6] Jinglin Chen and Nan Jiang  “Offline reinforcement learning under value and density-ratio realizability: The power of gaps”  In _Proceedings of the Thirty-Eighth Conference on Uncertainty in Artificial Intelligence_ , 2022
  * [7] Lili Chen, Kevin Lu, Aravind Rajeswaran, Kimin Lee, Aditya Grover, Misha Laskin, Pieter Abbeel, Aravind Srinivas and Igor Mordatch  “Decision transformer: Reinforcement learning via sequence modeling”  In _Advances in neural information processing systems_ , 2021
  * [8] Yi Chen, Jing Dong and Zhaoran Wang  “A Primal-Dual Approach to Constrained Markov Decision Processes”, 2021
  * [9] Ching-An Cheng, Tengyang Xie, Nan Jiang and Alekh Agarwal  “Adversarially Trained Actor Critic for Offline Reinforcement Learning”  In _Proceedings of the 39th International Conference on Machine Learning_ , 2022
  * [10] Dongsheng Ding, Kaiqing Zhang, Tamer Basar and Mihailo Jovanovic  “Natural Policy Gradient Primal-Dual Method for Constrained Markov Decision Processes”  In _Advances in Neural Information Processing Systems_ , 2020
  * [11] Gabriel Dulac-Arnold, Nir Levine, Daniel J. Mankowitz, Jerry Li, Cosmin Paduraru, Sven Gowal and Todd Hester  “An empirical investigation of the challenges of real-world reinforcement learning”, 2020
  * [12] Dylan J. Foster, Akshay Krishnamurthy, David Simchi-Levi and Yunzong Xu  “Offline Reinforcement Learning: Fundamental Barriers for Value Function Approximation”, 2022
  * [13] Sven Gronauer  “Bullet-Safety-Gym: A Framework for Constrained Reinforcement Learning”, 2022
  * [14] Shixiang Gu, Ethan Holly, Timothy Lillicrap and Sergey Levine  “Deep reinforcement learning for robotic manipulation with asynchronous off-policy updates”  In _2017 IEEE International Conference on Robotics and Automation (ICRA)_ , 2017
  * [15] Tuomas Haarnoja, Aurick Zhou, Pieter Abbeel and Sergey Levine  “Soft Actor-Critic: Off-Policy Maximum Entropy Deep Reinforcement Learning with a Stochastic Actor”  In _Proceedings of the 35th International Conference on Machine Learning_ , 2018
  * [16] Sham Kakade and John Langford  “Approximately Optimal Approximate Reinforcement Learning”  In _Proceedings of the Nineteenth International Conference on Machine Learning_ , 2002
  * [17] Sham M Kakade  “A Natural Policy Gradient”  In _Advances in Neural Information Processing Systems_ , 2001
  * [18] Aviral Kumar, Anikait Singh, Stephen Tian, Chelsea Finn and Sergey Levine  “A Workflow for Offline Model-Free Robotic Reinforcement Learning”, 2021
  * [19] Hoang Le, Cameron Voloshin and Yisong Yue  “Batch Policy Learning under Constraints”  In _Proceedings of the 36th International Conference on Machine Learning_ , 2019
  * [20] Jongmin Lee, Wonseok Jeon, Byungjun Lee, Joelle Pineau and Kee-Eung Kim  “OptiDICE: Offline Policy Optimization via Stationary Distribution Correction Estimation”  In _Proceedings of the 38th International Conference on Machine Learning_ , 2021
  * [21] Jongmin Lee, Cosmin Paduraru, Daniel J. Mankowitz, Nicolas Heess, Doina Precup, Kee-Eung Kim and Arthur Guez  “COptiDICE: Offline Constrained Reinforcement Learning via Stationary Distribution Correction Estimation”, 2022
  * [22] Sergey Levine, Aviral Kumar, George Tucker and Justin Fu  “Offline Reinforcement Learning: Tutorial, Review, and Perspectives on Open Problems”, 2020
  * [23] Sergey Levine, Peter Pastor, Alex Krizhevsky, Julian Ibarz and Deirdre Quillen  “Learning hand-eye coordination for robotic grasping with deep learning and large-scale data collection”  In _The International Journal of Robotics Research_ , 2018
  * [24] Zuxin Liu, Zijian Guo, Yihang Yao, Zhepeng Cen, Wenhao Yu, Tingnan Zhang and Ding Zhao  “Constrained decision transformer for offline safe reinforcement learning”  In _arXiv preprint arXiv:2302.07351_ , 2023
  * [25] Zuxin Liu et al.  “Datasets and Benchmarks for Offline Safe Reinforcement Learning”  In _arXiv preprint arXiv:2306.09303_ , 2023
  * [26] Rémi Munos  “Error bounds for approximate policy iteration”  In _Proceedings of the Twentieth International Conference on International Conference on Machine Learning_ , 2003
  * [27] Rémi Munos  “Error bounds for approximate value iteration”  In _Proceedings of the 20th national conference on Artificial intelligence - Volume 2_ , 2005
  * [28] Rémi Munos and Csaba Szepesvári  “Finite-Time Bounds for Fitted Value Iteration”  In _Journal of Machine Learning Research_ , 2008
  * [29] Asuman E Ozdaglar, Sarath Pattathil, Jiawei Zhang and Kaiqing Zhang  “Revisiting the linear-programming framework for offline rl with general function approximation”  In _International Conference on Machine Learning_ , 2023  PMLR
  * [30] Shengpu Tang and Jenna Wiens  “Model Selection for Offline Reinforcement Learning: Practical Considerations for Healthcare Settings”  In _Proceedings of the 6th Machine Learning for Healthcare Conference_ , 2021
  * [31] Wei Wang, Nanpeng Yu, Yuanqi Gao and Jie Shi  “Safe Off-Policy Deep Reinforcement Learning Algorithm for Volt-VAR Control in Power Distribution Systems”  In _IEEE Transactions on Smart Grid_ , 2020
  * [32] Tengyang Xie, Ching-An Cheng, Nan Jiang, Paul Mineiro and Alekh Agarwal  “Bellman-consistent pessimism for offline reinforcement learning”  In _Advances in neural information processing systems_ , 2021
  * [33] Tengyang Xie and Nan Jiang  “Batch Value-function Approximation with Only Realizability”  In _Proceedings of the 38th International Conference on Machine Learning_ , 2021
  * [34] Tengyang Xie and Nan Jiang  “Q* Approximation Schemes for Batch Reinforcement Learning: A Theoretical Comparison”  In _Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI)_ , 2020
  * [35] Haoran Xu, Xianyuan Zhan and Xiangyu Zhu  “Constraints penalized q-learning for safe offline reinforcement learning”  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , 2022
  * [36] Andrea Zanette  “When is Realizability Sufficient for Off-Policy Reinforcement Learning?”, 2022
  * [37] Andrea Zanette and Martin J. Wainwright  “Bellman Residual Orthogonalization for Offline Reinforcement Learning”, 2022
  * [38] Wenhao Zhan, Baihe Huang, Audrey Huang, Nan Jiang and Jason Lee  “Offline Reinforcement Learning with Realizability and Single-policy Concentrability”  In _Proceedings of Thirty Fifth Conference on Learning Theory_ , 2022
  * [39] Hanlin Zhu, Paria Rashidinejad and Jiantao Jiao  “Importance Weighted Actor-Critic for Optimal Conservative Offline Reinforcement Learning”, 2023

Supplementary Materials

##  A PERFORMANCE DIFFERENCE LEMMAS

In this section, we provide two generalizations of the classical performance
difference lemma [16]. For completeness, we first state the classical
performance difference lemma below.

######  Lemma 1 (Performance Difference Lemma. [16]).

$(1-\gamma)(J_{U}(\widehat{\pi})-J_{U}(\pi))=A_{\pi}(\widehat{\pi},Q_{U}^{\widehat{\pi}})$
(4)

The following is the first generalization of the performance difference lemma.
It decomposes the difference in performance of two policies, where the
performance of one of the policies is measured with respect to an arbitrary
Q-value function $f$. The same result is proved as an intermediate step in the
proof of Lemma 12 in [9]. We state it as a separate lemma and provide a
simplified proof below.

######  Lemma 2.

For any functions $U,f:\mathcal{S}\times\mathcal{A}\rightarrow\mathbb{R}$ and
any policies $\pi,\widehat{\pi}:\mathcal{S}\rightarrow\Delta(\mathcal{A})$, we
have

$(1-\gamma)(f(s_{0},\widehat{\pi})-J_{U}(\pi))=A_{\pi}(\widehat{\pi},f)+\mathbb{E}_{\pi}[(f-\mathcal{T}_{U}^{\widehat{\pi}}f)(s,a)].$

###### Proof.

Note that

$\displaystyle\mathbb{E}_{(s,a)\sim d^{\pi}}[f(s,\widehat{\pi})]$
$\displaystyle=(1-\gamma)\mathbb{E}^{\pi}\left[\sum_{t=0}^{\infty}\gamma^{t}f(s_{t},\widehat{\pi})\right]$
$\displaystyle=(1-\gamma)\mathbb{E}^{\pi}\left[f(s_{0},\widehat{\pi})+\sum_{t=0}^{\infty}\gamma^{t}\mathbb{E}^{\pi}\left[\gamma
f(s_{t+1},\widehat{\pi})\mid s_{t},a_{t}\right]\right]$
$\displaystyle=(1-\gamma)f(s_{0},\widehat{\pi})+(1-\gamma)\mathbb{E}^{\pi}\left[\sum_{t=0}^{\infty}\gamma^{t}\mathcal{T}_{0}^{\widehat{\pi}}f(s_{t},a_{t})\right]$
$\displaystyle=(1-\gamma)f(s_{0},\widehat{\pi})+\mathbb{E}_{(s,a)\sim
d^{\pi}}[\mathcal{T}_{0}^{\widehat{\pi}}f(s,a)].$

Rearranging, we get

$\displaystyle(1-\gamma)f(s_{0},\widehat{\pi})$
$\displaystyle=\mathbb{E}_{(s,a)\sim
d^{\pi}}[(f-\mathcal{T}_{0}^{\widehat{\pi}}f)(s,a)]-\mathbb{E}_{(s,a)\sim
d^{\pi}}[f(s,a)-f(s,\widehat{\pi})]$ $\displaystyle=\mathbb{E}_{(s,a)\sim
d^{\pi}}[(f-\mathcal{T}_{0}^{\widehat{\pi}}f)(s,a)]+A_{\pi}(\widehat{\pi},f).$

Using $(1-\gamma)J_{U}(\pi)=\mathbb{E}_{(s,a)\sim d^{\pi}}[U(s,a)]$, we get

$\displaystyle(1-\gamma)(f(s_{0},\widehat{\pi})-J_{U}(\pi))$
$\displaystyle=\mathbb{E}_{\pi}[(f-\mathcal{T}_{0}^{\widehat{\pi}}f)(s,a)]+A_{\pi}(\widehat{\pi},f)-\mathbb{E}_{\pi}[U(s,a)]$
$\displaystyle=A_{\pi}(\widehat{\pi},f)+\mathbb{E}_{\pi}[(f-\mathcal{T}_{U}^{\widehat{\pi}}f)(s,a)].$

∎

Note that when we set $f=Q_{U}^{\widehat{\pi}}$ in the lemma above, we recover
the classical performance difference lemma. Now, we state the second
generalization of the performance difference lemma. The same lemma is stated
and proved in [9] and also used in [39]. We state the lemma and provide a
simpler proof below.

######  Lemma 3 (Performance difference decomposition. Lemma 12 in [9]).

For any policies
$\pi,\widehat{\pi},\mu:\mathcal{S}\rightarrow\Delta(\mathcal{A})$ and any
functions $U:\mathcal{S}\times\mathcal{A}\rightarrow\mathbb{R}$ and
$f:\mathcal{S}\times\mathcal{A}\rightarrow\mathbb{R}$, we have

$\displaystyle(1-\gamma)(J_{U}(\pi)-J_{U}(\widehat{\pi}))$
$\displaystyle=\mathbb{E}_{\mu}[(f-\mathcal{T}^{\widehat{\pi}}_{U}f)(s,a)]+\mathbb{E}_{\pi}[(\mathcal{T}^{\widehat{\pi}}_{U}f-f)(s,a)]$
$\displaystyle\quad\quad\quad+\mathbb{E}_{\pi}[f(s,\pi)-f(s,\widehat{\pi})]+A_{\mu}(\widehat{\pi},f)-A_{\mu}(\widehat{\pi},Q_{U}^{\widehat{\pi}}).$

###### Proof.

We have

$\displaystyle(1$ $\displaystyle-\gamma)(J_{U}(\pi)-J_{U}(\widehat{\pi}))$
$\displaystyle=(1-\gamma)(J_{U}(\pi)-f(s_{0},\widehat{\pi}))+(1-\gamma)(f(s_{0},\widehat{\pi})-J_{U}(\mu))+(1-\gamma)(J_{U}(\mu)-J_{U}(\widehat{\pi}))$
$\displaystyle=-(A_{\pi}(\widehat{\pi},f)+\mathbb{E}_{\pi}[(f-\mathcal{T}_{U}^{\widehat{\pi}}f)(s,a)])+(A_{\mu}(\widehat{\pi},f)+\mathbb{E}_{\mu}[(f-\mathcal{T}_{U}^{\widehat{\pi}}f)(s,a)])-A_{\mu}(\widehat{\pi},Q_{U}^{\pi})$

where the second inequality uses the generalized performance difference lemma
(Lemma 2) for the first two terms and the classical performance difference
lemma (Lemma 1) for the third term. Rearranging and observing that
$A_{\pi}(\widehat{\pi},f)=\mathbb{E}_{\pi}[f(s,\widehat{\pi})-f(s,\pi)]$
complete the proof. ∎

Indeed, the lemma above is a generalization because setting $\mu=\pi$ reduces
to the classical performance difference lemma (Lemma 1).

##  B CONCENTRATION INEQUALITIES

In this section, we provide concentration inequalities for relating
$\mathcal{E}_{\mu}$ and $A_{\mu}$ to the empirical versions
$\mathcal{E}_{\mathcal{D}}$ and $A_{\mathcal{D}}$ respectively. First, we show
a concentration bound on $\mathbb{E}_{\mathcal{D}}[w(s,a)(f(s,a)-U(s,a)-\gamma
f(s^{\prime},\pi))]$, which will be used to show a concentration bound on
$\mathcal{E}_{\mathcal{D}}(\pi,f,U)$.

######  Lemma 4 (Concentration of Bellman error).

Let $w:\mathcal{S}\times\mathcal{A}\rightarrow\mathbb{R}_{+}$ with $\|w\|\leq
C_{\infty}$ and $\|w\|_{2,\mu}\leq C_{\ell_{2}}$. Let
$f:\mathcal{S}\times\mathcal{A}\rightarrow[0,\frac{1}{1-\gamma}]$ and
$U:\mathcal{S}\times\mathcal{A}\rightarrow[0,1]$ be any functions. Let
$\pi:\mathcal{S}\rightarrow\Delta(\mathcal{A})$ be any policy. With
probability at least $1-\delta$, we have

$\displaystyle|\mathbb{E}_{\mu}[w(s,a)(f-\mathcal{T}_{U}^{\pi})(s,a)]-\mathbb{E}_{\mathcal{D}}$
$\displaystyle[w(s,a)(f(s,a)-U(s,a)-\gamma f(s^{\prime},\pi))]|$
$\displaystyle\leq\mathcal{O}\left(\frac{C_{\ell_{2}}}{1-\gamma}\sqrt{\frac{\log(1/\delta)}{n}}+\frac{C_{\infty}}{1-\gamma}\frac{\log(1/\delta)}{n}\right).$

###### Proof.

Define

$X_{j}=w(s_{j},a_{j})(f(s_{j},a_{j})-U(s_{j},a_{j})-\gamma
f(s_{j}^{\prime},\pi)).$

Note that $\mathbb{E}_{\mathcal{D}}[w(s,a)(f(s,a)-U(s,a)-\gamma
f(s^{\prime},\pi))]=\frac{1}{n}\sum_{j=1}^{n}X_{j}$. By assumption of the data
distribution, $X_{1},\dots,X_{n}$ are i.i.d. By the boundedness assumption on
$w$ and $f$, we have $|X_{j}|\leq\mathcal{O}(C_{\infty}/(1-\gamma))$. Also, we
have

$\displaystyle\mathbb{E}[X_{j}]$ $\displaystyle=\mathbb{E}_{(s,a)\sim
d^{\mu},s^{\prime}\sim P(\cdot|s,a)}[w(s,a)(f(s,a)-U(s,a)-\gamma
f(s^{\prime},\pi))]$ $\displaystyle=\mathbb{E}_{(s,a)\sim
d^{\mu}}[\mathbb{E}_{s^{\prime}\sim P(\cdot|s,a)}[w(s,a)(f(s,a)-U(s,a)-\gamma
f(s^{\prime},\pi))|s,a]]$
$\displaystyle=\mathbb{E}_{\mu}[w(s,a)(f-\mathcal{T}_{U}^{\pi}f)(s,a)].$

By Bernstein’s inequality, we have with probability at least $1-\delta$ that

$\displaystyle\Bigg{|}\mathbb{E}_{\mu}[w(s,a)(f$
$\displaystyle-\mathcal{T}_{U}^{\pi}f)(s,a)]-\frac{1}{n}\sum_{j=1}^{n}X_{j}\Bigg{|}$
$\displaystyle\leq\mathcal{O}\left(\sqrt{\frac{\text{Var}_{\mu}[w(s,a)(f-\mathcal{T}_{U}^{\pi}f)(s,a)]\log(1/\delta)}{n}}+\frac{C_{\infty}\log(1/\delta)}{(1-\gamma)n}\right)$

The variance term $\text{Var}_{\mu}[w(s,a)(f-\mathcal{T}_{U}^{\pi}f)(s,a)]$
can be bounded as follows.

$\displaystyle\text{Var}_{\mu}[w(s,a)(f-\mathcal{T}_{U}^{\pi}f)(s,a)]$
$\displaystyle\leq\mathbb{E}_{\mu}[w(s,a)^{2}(f-\mathcal{T}_{U}^{\pi}f)^{2}(s,a)]$
$\displaystyle\leq\mathcal{O}(\|w\|_{2,\mu}^{2}/(1-\gamma)^{2})$
$\displaystyle\leq\mathcal{O}((C_{\ell_{2}})^{2}/(1-\gamma)^{2})$

where the second inequality uses the boundedness assumption on $f$ and the
last inequality uses the boundedness assumption on $w$. Hence, we have

$\Bigg{|}\mathbb{E}_{\mu}[w(s,a)(f-\mathcal{T}_{U}^{\pi}f)(s,a)]-\frac{1}{n}\sum_{j=1}^{n}X_{j}\Bigg{|}\leq\mathcal{O}\left(\frac{C_{\ell_{2}}}{1-\gamma}\sqrt{\frac{\log(1/\delta)}{n}}+\frac{C_{\infty}\log(1/\delta)}{(1-\gamma)n}\right).$

This completes the proof. ∎

The following lemma relates $\mathcal{E}_{\mu}$ to
$\mathcal{E}_{\mathcal{D}}$. The proof closely follows that of Lemma 4 in
[39], which shows the same result for a single reward function.

######  Lemma 5 (Concentration of Bellman error term).

Under Assumption D, with probability at least $1-\delta$, we have

$\displaystyle|\mathcal{E}_{\mu}(\pi,f;R)-\mathcal{E}_{\mathcal{D}}(\pi,f;R)|$
$\displaystyle\leq\mathcal{O}(\epsilon_{\text{stat}})$
$\displaystyle|\mathcal{E}_{\mu}(\pi,g_{i};C_{i})-\mathcal{E}_{\mathcal{D}}(\pi,g_{i};C_{i})|$
$\displaystyle\leq\mathcal{O}(\epsilon_{\text{stat}})~{}~{}\text{for
all}~{}i=1,\dots,I,$

for any $\pi\in\Pi$, $f\in\mathcal{F}$ and $g_{i}\in\mathcal{F}$,
$i=1,\dots,I$, where

$\epsilon_{\text{stat}}\coloneqq\frac{C_{\ell_{2}}}{1-\gamma}\sqrt{\frac{\log(I|\mathcal{F}||\Pi||\mathcal{W}|/\delta)}{n}}+\frac{C_{\infty}\log(I|\mathcal{F}||\Pi||\mathcal{W}|/\delta)}{(1-\gamma)n}.$

###### Proof.

It is enough to show that, with probability $1-\delta$, we have
$|\mathcal{E}_{\mu}(\pi,h;U)-\mathcal{E}_{\mathcal{D}}(\pi,h;U)|\leq\mathcal{O}(\epsilon_{\text{stat}})$
for any policy $\pi\in\Pi$, any function $h\in\mathcal{F}$ and any function
$U\in\\{R,C_{1},\dots,C_{I}\\}$. Fix $\pi\in\Pi$, $h\in\mathcal{F}$ and
$U\in\\{R,C_{1},\dots,C_{I}\\}$, and define

$X_{j}(w)=w(s_{j},a_{j})(h(s_{j},a_{j})-U(s_{j},a_{j})-\gamma
h(s_{j}^{\prime},\pi))$

where $w\in\mathcal{W}$. By Lemma 4, we have

$\Bigg{|}\mathbb{E}_{\mu}[w(s,a)(h-\mathcal{T}_{U}^{\pi}h)(s,a)]-\frac{1}{n}\sum_{j=1}^{n}X_{j}(w)\Bigg{|}\leq\mathcal{O}\left(\frac{C_{\ell_{2}}}{1-\gamma}\sqrt{\frac{\log(1/\delta)}{n}}+\frac{C_{\infty}\log(1/\delta)}{(1-\gamma)n}\right).$

Since the inequality above holds for all $w\in\mathcal{W}$, it follows by a
union bound over $w\in\mathcal{W}$ that

$\displaystyle\mathcal{E}_{\mu}$
$\displaystyle(\pi,h;U)-\mathcal{E}_{\mathcal{D}}(\pi,h;U)=\max_{w\in\mathcal{W}}\left|\mathbb{E}_{\mu}\left[w(s,a)(h-\mathcal{T}_{U}^{\pi}h)(s,a)\right]\right|$
$\displaystyle\quad\quad-\max_{w\in\mathcal{W}}\left|\mathbb{E}_{\mathcal{D}}\left[w(s,a)(h(s,a)-U(s,a)-\gamma
h(s^{\prime},\pi))\right]\right|$
$\displaystyle\leq\left|\mathbb{E}_{\mu}\left[w^{\star}(s,a)(h-\mathcal{T}_{U}^{\pi}h)(s,a)\right]\right|-\left|\mathbb{E}_{\mathcal{D}}\left[w^{\star}(s,a)(h(s,a)-U(s,a)-\gamma
h(s^{\prime},\pi))\right]\right|$
$\displaystyle\leq\left|\mathbb{E}_{\mu}\left[w^{\star}(s,a)(h-\mathcal{T}_{U}^{\pi}h)(s,a)\right]-\mathbb{E}_{\mathcal{D}}\left[w^{\star}(s,a)(h(s,a)-U(s,a)-\gamma
h(s^{\prime},\pi))\right]\right|$
$\displaystyle=\Bigg{|}\mathbb{E}_{\mu}[w^{\star}(s,a)(h-\mathcal{T}_{U}^{\pi}h)(s,a)]-\frac{1}{n}\sum_{j=1}^{n}X_{j}(w^{\star})\Bigg{|}$
$\displaystyle\leq\mathcal{O}\left(\frac{C_{\ell_{2}}}{1-\gamma}\sqrt{\frac{\log(|\mathcal{W}|/\delta)}{n}}+\frac{C_{\infty}\log(|\mathcal{W}|/\delta)}{(1-\gamma)n}\right)$

where in the first inequality, we use the notation
$w^{\star}=\operatorname*{argmax}_{w\in\mathcal{W}}|\mathbb{E}_{\mu}[w(s,a)(f-\mathcal{T}_{U}^{\pi}f)(s,a)]|$;
the second inequality follows by the identity $|a|-|b|\leq|a-b|$; and the last
inequality uses the previous result. The bound of
$\mathcal{E}_{\mathcal{D}}(\pi,h;U)-\mathcal{E}_{\mu}(\pi,h;U)$ follows
similarly, and the union bound of the two bounds gives

$|\mathcal{E}_{\mu}(\pi,h;U)-\mathcal{E}_{\mathcal{D}}(\pi,h;U)|\leq\mathcal{O}\left(\frac{C_{\ell_{2}}}{1-\gamma}\sqrt{\frac{\log(|\mathcal{W}|/\delta)}{n}}+\frac{C_{\infty}\log(|\mathcal{W}|/\delta)}{(1-\gamma)n}\right).$

A union bound on all
$(h,\pi,U)\in\mathcal{F}\times\Pi\times\\{R,C_{1},\dots,C_{I}\\}$ completes
the proof. ∎

The following lemma relates $A_{\mu}$ to $A_{\mathcal{D}}$. The proof closely
follows that of Lemma 5 in [39], which shows the same result for a single
reward function.

######  Lemma 6 (Concentration of the advantage function).

With probability at least $1-\delta$, for any $\pi\in\Pi$, $f\in\mathcal{F}$,
we have

$|A_{\mu}(\pi,f)-A_{\mathcal{D}}(\pi,f)|\leq\mathcal{O}\left(\sqrt{\frac{\log(|\mathcal{F}||\Pi|/\delta)}{n(1-\gamma)^{2}}}\right)\leq\mathcal{O}(\epsilon_{\text{stat}})$

where $\epsilon_{\text{stat}}$ is defined in Lemma 5.

###### Proof.

Note that $\mathbb{E}[A_{\mathcal{D}}(\pi,f)]=A_{\mu}(\pi,f)$ and
$|f(s_{i},\pi)-f(s_{i},a_{i})|\leq\mathcal{O}(\frac{1}{1-\gamma})$. Fixing
$\pi\in\mathcal{F}$ and $f\in\mathcal{F}$ and applying Hoeffding’s inequality,
we have with probability at least $1-\delta$ that

$|A_{\mu}(\pi,f)-A_{\mathcal{D}}(\pi,f)|\leq\mathcal{O}\left(\sqrt{\frac{\log(1/\delta)}{n(1-\gamma)^{2}}}\right).$

Applying union bound on $(\pi,f)\in\Pi\times\mathcal{F}$ completes the proof.
∎

##  C PDCA PRODUCES A NEAR SADDLE POINT

In this section, we show that our algorithm PDCA (Algorithm 1) produces a near
saddle point.

######  Lemma 7.

Consider the policy $\bar{\pi}$ produced by the algorithm PDCA (Algorithm 1)
with threshold $\bm{\tau}$ and bound $B$. Let
$\bar{\bm{\lambda}}\coloneqq\frac{1}{K}\sum_{k=1}^{K}\bm{\lambda}_{k}$ where
$\bm{\lambda}_{1},\dots,\bm{\lambda}_{K}\in B\bm{\Delta}^{I}$ is the sequence
of Lagrange multipliers produced by the $\lambda$-player in the algorithm.
Then, under Assumption A,C,D and E, with probability at least $1-\delta$, we
have for any $\pi\in\text{Conv}(\Pi)$ satisfying $w^{\pi}\in\mathcal{W}$ and
any $\bm{\lambda}\in B\bm{\Delta}^{I}$ that

$L(\pi,\bar{\bm{\lambda}})\leq
L(\bar{\pi},\bm{\lambda})+\frac{1+2B}{(1-\gamma)^{2}}\epsilon_{\text{opt}}(K)+\mathcal{O}\left(\frac{B\epsilon_{\text{stat}}}{1-\gamma}\right).$

We prove Lemma 7 by bounding the regrets of the $\pi$-player and
$\lambda$-player against their best actions in hindsight.

###  C.1 Bounding the Regret of the $\pi$-Player

######  Lemma 8.

Under Assumption A,D and E, with probability at least $1-\delta$, the
sequences $\pi_{1},\dots,\pi_{K}\in\Pi$ and
$\bm{\lambda}_{1},\dots,\bm{\lambda}_{K}\in B\bm{\Delta}^{I}$ produced by the
algorithm PDCA using the cost threshold $\bm{\tau}$ and the bound $B$ satisfy

$L(\pi,\bar{\bm{\lambda}})-\frac{1}{K}\sum_{k=1}^{K}L(\pi_{k},\bm{\lambda}_{k})\leq\frac{1+2B}{(1-\gamma)^{2}}\epsilon_{\text{opt}}(K)+\mathcal{O}\left(\frac{B\epsilon_{\text{stat}}}{1-\gamma}\right)$

for all $\pi\in\text{Conv}(\Pi)$ with $w^{\pi}\in\mathcal{W}$ where
$L(\pi,\bm{\lambda})=J_{R}(\pi)+\bm{\lambda}\cdot(\bm{\tau}-J_{\bm{C}}(\pi))$.

###### Proof.

Fix a policy $\pi\in\text{Conv}(\Pi)$ satisfying $w^{\pi}\in\mathcal{W}$. Such
a policy exists by Assumption E. By the definition of $L(\cdot,\cdot)$, we get

$L(\pi,\bar{\bm{\lambda}})-\frac{1}{K}\sum_{k=1}^{K}L(\pi_{k},\bm{\lambda}_{k})=\frac{1}{K}\sum_{k=1}^{K}(\underbrace{J_{R}(\pi)-J_{R}(\pi_{k})}_{(a)})+\frac{1}{K}\sum_{k=1}^{K}\sum_{i=1}^{I}\lambda_{k}^{i}(\underbrace{J_{C_{i}}(\pi_{k})-J_{C_{i}}(\pi)}_{(b)}).$

By a union bound with $\delta$ scaled appropriately, the concentration bounds
for $\mathcal{E}_{\mathcal{D}}$ and $A_{\mathcal{D}}$ in Lemma 5 and Lemma 6,
and the regret bound of the oracle used by the $\pi$-player (Definition 3)
hold with probability at least $1-\delta$. For the rest of the proof, we
assume these events hold.

#### Bounding $(a)$

We use the performance difference lemma (Lemma 3) to bound $(a)$ as follows.

$\displaystyle(1-\gamma)$ $\displaystyle(J_{R}(\pi)-J_{R}(\pi_{k}))$
$\displaystyle=\mathbb{E}_{\mu}[(f_{k}-\mathcal{T}_{R}^{\pi_{k}}f_{k})(s,a)]+\mathbb{E}_{\pi}[(\mathcal{T}_{R}^{\pi_{k}}f_{k}-f_{k})(s,a)]$
$\displaystyle\quad\quad\quad+\mathbb{E}_{\pi}[f_{k}(s,\pi)-f_{k}(s,\pi_{k})]+A_{\mu}(\pi_{k},f_{k})-A_{\mu}(\pi_{k},Q_{R}^{\pi_{k}})$
$\displaystyle\leq
2\mathcal{E}_{\mu}(\pi_{k},f_{k};R)+\mathbb{E}_{\pi}[f_{k}(s,\pi)-f_{k}(s,\pi_{k})]+A_{\mu}(\pi_{k},f_{k})-A_{\mu}(\pi_{k},Q_{R}^{\pi_{k}})$
$\displaystyle\leq\mathbb{E}_{\pi}[f_{k}(s,\pi)-f_{k}(s,\pi_{k})]+\underbrace{2\mathcal{E}_{\mathcal{D}}(\pi_{k},f_{k};R)+A_{\mathcal{D}}(\pi_{k},f_{k})}_{(\star)}-A_{\mathcal{D}}(\pi_{k},Q_{R}^{\pi_{k}})+\mathcal{O}(\epsilon_{\text{stat}})$

where the first inequality follows by $w^{\pi}\in\mathcal{W}$ which implies
$|\mathbb{E}_{\pi}[(f-\mathcal{T}_{U}^{\pi}f)(s,a)]|\leq\mathcal{E}_{\mu}(\pi,f;U)$;
and the second inequality follows by the concentration results in Lemma 5 and
Lemma 6. Recall that the reward critic chooses $f_{k}\in\mathcal{F}$ that
minimizes
$2\mathcal{E}_{\mathcal{D}}(\pi_{k},\cdot;R)+A_{\mathcal{D}}(\pi_{k},\cdot)$.
We have $Q_{R}^{\pi_{k}}\in\mathcal{F}$ by the realizability assumption
(Assumption A). Hence,

$2\mathcal{E}_{\mathcal{D}}(\pi_{k},f_{k};R)+A_{\mathcal{D}}(\pi_{k},f_{k})\leq
2\mathcal{E}_{\mathcal{D}}(\pi_{k},Q_{R}^{\pi_{k}};R)+A_{\mathcal{D}}(\pi_{k},Q_{R}^{\pi_{k}}).$

Using this inequality for bounding $(\star)$ and continuing the bound of
$J_{R}(\pi)-J_{R}(\pi_{k})$, we get

$\displaystyle(1-\gamma)(J_{R}(\pi)-J_{R}(\pi_{k}))$
$\displaystyle\leq\mathbb{E}_{\pi}[f_{k}(s,\pi)-f_{k}(s,\pi_{k})]+2\mathcal{E}_{\mathcal{D}}(\pi_{k},Q_{R}^{\pi_{k}};R)+\mathcal{O}(\epsilon_{\text{stat}})$
$\displaystyle\leq\mathbb{E}_{\pi}[f_{k}(s,\pi)-f_{k}(s,\pi_{k})]+2\mathcal{E}_{\mu}(\pi_{k},Q_{R}^{\pi_{k}};R)+\mathcal{O}(\epsilon_{\text{stat}})$
$\displaystyle=\mathbb{E}_{\pi}[f_{k}(s,\pi)-f_{k}(s,\pi_{k})]+\mathcal{O}(\epsilon_{\text{stat}})$

where the last equality uses the fact that $Q_{R}^{\pi}$ solves
$f-\mathcal{T}_{R}^{\pi}f=0$, which gives
$\mathcal{E}_{\mu}(\pi_{k},Q_{R}^{\pi_{k}};R)=\max_{w\in\mathcal{W}}|\mathbb{E}_{\mu}[w(s,a)(Q_{R}^{\pi_{k}}-\mathcal{T}_{R}^{\pi_{k}}Q_{R}^{\pi_{k}})]|=0$.

#### Bounding $(b)$

Similarly, we can bound $(b)$ as follows.

$\displaystyle(1-\gamma)$ $\displaystyle(J_{C_{i}}(\pi_{k})-J_{C_{i}}(\pi))$
$\displaystyle=\mathbb{E}_{\mu}[(\mathcal{T}_{C_{i}}^{\pi_{k}}g_{k}^{i}-g_{k}^{i})(s,a)]+\mathbb{E}_{\pi}[(g_{k}^{i}-\mathcal{T}_{C_{i}}^{\pi_{k}}g_{k}^{i})(s,a)]$
$\displaystyle\quad\quad\quad+\mathbb{E}_{\pi}[g_{k}^{i}(s,\pi_{k})-g_{k}^{i}(s,\pi)]-A_{\mu}(\pi_{k},g_{k}^{i})+A_{\mu}(\pi_{k},Q_{C_{i}}^{\pi_{k}})$
$\displaystyle\leq
2\mathcal{E}_{\mu}(\pi_{k},g_{k}^{i};C_{i})+\mathbb{E}_{\pi}[g_{k}^{i}(s,\pi_{k})-g_{k}^{i}(s,\pi)]-A_{\mu}(\pi_{k},g_{k}^{i})+A_{\mu}(\pi_{k},Q_{C_{i}}^{\pi_{k}})$
$\displaystyle\leq\mathbb{E}_{\pi}[g_{k}^{i}(s,\pi_{k})-g_{k}^{i}(s,\pi)]+2\mathcal{E}_{\mathcal{D}}(\pi_{k},g_{k}^{i};C_{i})-A_{\mathcal{D}}(\pi_{k},g_{k}^{i})+A_{\mathcal{D}}(\pi_{k},Q_{C_{i}}^{\pi_{k}})+\mathcal{O}(\epsilon_{\text{stat}})$
$\displaystyle\leq\mathbb{E}_{\pi}[g_{k}^{i}(s,\pi_{k})-g_{k}^{i}(s,\pi)]+2\mathcal{E}_{\mathcal{D}}(\pi_{k},Q_{C_{i}}^{\pi_{k}};C_{i})+\mathcal{O}(\epsilon_{\text{stat}})$
$\displaystyle\leq\mathbb{E}_{\pi}[g_{k}^{i}(s,\pi_{k})-g_{k}^{i}(s,\pi)]+2\mathcal{E}_{\mu}(\pi_{k},Q_{C_{i}}^{\pi_{k}};C_{i})+\mathcal{O}(\epsilon_{\text{stat}})$
$\displaystyle=\mathbb{E}_{\pi}[g_{k}^{i}(s,\pi_{k})-g_{k}^{i}(s,\pi)]+\mathcal{O}(\epsilon_{\text{stat}})$

where the third inequality uses the realizability assumption (Assumption A)
for $Q_{C_{i}}^{\pi_{k}}\in\mathcal{F}$ and the fact that the cost critic
chooses $g_{k}^{i}\in\mathcal{F}$ that minimizes
$2\mathcal{E}_{\mathcal{D}}(\pi_{k},\cdot;C_{i})-A_{\mathcal{D}}(\pi_{k},\cdot)$.

#### Using the Property of $\pi$-Player

Using the bounds for $(a)$ and $(b)$ and continuing, we get

$\displaystyle\frac{1-\gamma}{K}\sum_{k=1}^{K}$
$\displaystyle(L(\pi,\bm{\lambda}_{k})-L(\pi_{k},\bm{\lambda}_{k}))$
$\displaystyle=\frac{1-\gamma}{K}\sum_{k=1}^{K}(J_{R}(\pi)-J_{R}(\pi_{k}))+\frac{1-\gamma}{K}\sum_{k=1}^{K}\sum_{i=1}^{I}\lambda_{k}^{i}(J_{C_{i}}(\pi_{k})-J_{C_{i}}(\pi))$
$\displaystyle\leq\frac{1}{K}\sum_{k=1}^{K}\Bigg{(}\mathbb{E}_{\pi}[f_{k}(s,\pi)-f_{k}(s,\pi_{k})]+\sum_{i=1}^{I}\lambda_{k}^{i}\mathbb{E}_{\pi}[g_{k}^{i}(s,\pi_{k})-g_{k}^{i}(s,\pi)]\Bigg{)}+\mathcal{O}\left(B\epsilon_{\text{stat}}\right)$
$\displaystyle=\frac{1}{K}\sum_{k=1}^{K}\mathbb{E}_{\pi}[z_{k}(s,\pi)-z_{k}(s,\pi_{k})]+\mathcal{O}\left(B\epsilon_{\text{stat}}\right)$
$\displaystyle\leq\frac{1+2B}{1-\gamma}\epsilon_{\text{opt}}(K)+\mathcal{O}\left(B\epsilon_{\text{stat}}\right)$

where $z_{k}=f_{k}+\sum_{i=1}^{I}\lambda_{k}^{i}(\tau_{i}-g_{k}^{i})$ and the
last inequality follows by the property of the policy optimization oracle
(Definition 3) employed by the $\pi$-player and the fact that
$|z_{k}(s,a)|\leq\frac{1+2B}{1-\gamma}$ for all $s\in\mathcal{S}$ and
$a\in\mathcal{A}$. Rearranging completes the proof. ∎

###  C.2 Bound the Regret of the $\lambda$-Player

######  Lemma 9.

Under Assumption A,C,D and E, with probability at least $1-\delta$, the
sequences $\pi_{1},\dots,\pi_{K}\in\Pi$ and
$\bm{\lambda}_{1},\dots,\bm{\lambda}_{K}\in B\bm{\Delta}^{I}$ produced by the
algorithm PDCA using the cost threshold $\bm{\tau}$ and the bound $B$ satisfy

$\frac{1}{K}\sum_{k=1}^{K}L(\pi_{k},\bm{\lambda}_{k})\leq\frac{1}{K}\sum_{k=1}^{K}L(\pi_{k},\bm{\lambda})+\mathcal{O}\left(\frac{B\epsilon_{\text{stat}}}{1-\gamma}\right)$

for all $\bm{\lambda}\in B\bm{\Delta}^{I}$ where
$L(\pi,\bm{\lambda})=J_{R}(\pi)+\bm{\lambda}\cdot(\bm{\tau}-J_{\bm{C}}(\pi))$.

###### Proof.

Recall that the OPE oracle produces an estimate $h$ for the value of $\pi$
with respect to a utility function $U$ that satisfies
$|J_{U}(\pi)-h|\leq\mathcal{O}(\frac{C_{\ell_{2}}}{1-\gamma}\sqrt{\frac{\log(|\mathcal{F}|/\delta)}{n}})\leq\mathcal{O}(\epsilon_{\text{stat}})$
with probability at least $1-\delta$. By applying a union bound on
$(\pi,U)\in\Pi\times\\{C_{1},\dots,C_{I}\\}$, we have with probability at
least $1-\delta$ that

$(1-\gamma)|J_{C_{i}}(\pi_{k})-h_{k}^{i}|\leq\mathcal{O}(\epsilon_{\text{stat}})$

for all $k=1,\dots,K$ and all $i=1,\dots,I$. Hence,

$\displaystyle\frac{1}{K}\sum_{k=1}^{K}L(\pi_{k},\bm{\lambda}_{k})-\frac{1}{K}\sum_{k=1}^{K}L(\pi_{k},\bm{\lambda})$
$\displaystyle=\frac{1}{K}\sum_{k=1}^{K}\sum_{i=1}^{I}(\lambda_{k}^{i}-\lambda^{i})(\tau_{i}-J_{C_{i}}(\pi_{k}))$
$\displaystyle\leq\frac{1}{K}\sum_{k=1}^{K}\sum_{i=1}^{I}(\lambda_{k}^{i}-\lambda^{i})(\tau_{i}-h_{k}^{i})+\mathcal{O}\left(\frac{B\epsilon_{\text{stat}}}{1-\gamma}\right).$

The first term in the last expression is
$\frac{1}{K}\sum_{k=1}^{K}\bm{\lambda}_{k}\cdot(\bm{\tau}-\bm{h}_{k})-\frac{1}{K}\sum_{k=1}^{K}\bm{\lambda}\cdot(\bm{\tau}-\bm{h}_{k})\leq
0$ since the $\lambda$-player chooses $\bm{\lambda}_{k}$ greedily that
minimizes $\bm{\lambda}\mapsto\bm{\lambda}\cdot(\bm{\tau}-\bm{h}_{k})$, and we
are done. ∎

###  C.3 Proof of Lemma 7

Combining the results of Lemma 8 and Lemma 9, we can show that the pair
$(\bar{\pi},\bar{\bm{\lambda}})$ is approximately a saddle point where
$\bar{\pi}$ is the policy returned by PDCA and $\bar{\bm{\lambda}}$ is the
average of the sequence of Lagrange multipliers
$\bm{\lambda}_{1},\dots,\bm{\lambda}_{K}$ produced by PDCA.

######  Proof of 1 (Lemma 7).

Fix a policy $\pi\in\text{Conv}(\Pi)$ and a Lagrange multiplier
$\bm{\lambda}\in B\bm{\Delta}^{I}$. Then,

$\displaystyle L(\pi,\bar{\bm{\lambda}})$
$\displaystyle\leq\frac{1}{K}\sum_{k=1}^{K}L(\pi_{k},\bm{\lambda}_{k})+\frac{1+2B}{(1-\gamma)^{2}}\epsilon_{\text{opt}}(K)+\mathcal{O}\left(\frac{B\epsilon_{\text{stat}}}{1-\gamma}\right)$
$\displaystyle\leq\frac{1}{K}\sum_{k=1}^{K}L(\pi_{k},\bm{\lambda})+\frac{1+2B}{(1-\gamma)^{2}}\epsilon_{\text{opt}}(K)+\mathcal{O}\left(\frac{B\epsilon_{\text{stat}}}{1-\gamma}\right)$

where the first inequality uses Lemma 8 and the second inequality uses Lemma
9. Observing that
$\frac{1}{K}\sum_{k=1}^{K}L(\pi_{k},\bm{\lambda})=L(\bar{\pi},\bm{\lambda})$
by the linearity of $L(\cdot,\bm{\lambda})$ completes the proof.

##  D PROPERTIES OF A NEAR SADDLE POINT

In this section, we study the properties of a near saddle point formally
defined below.

######  Definition 5.

We say $(\bar{x},\bar{y})$ is a $\xi$-near saddle point for a function
$L(\cdot,\cdot)$ with respect to the input space
$\mathcal{X}\times\mathcal{Y}$ if $L(x,\bar{y})\leq L(\bar{x},y)+\xi$ for all
$x\in\mathcal{X}$ and $y\in\mathcal{Y}$.

######  Lemma 10.

Suppose $(\bar{\pi},\bar{\bm{\lambda}})$ is a $\xi$-near saddle point for
$L(\cdot,\cdot)$ with respect to $\widetilde{\Pi}\times B\bm{\Delta}^{I}$
where $\widetilde{\Pi}\subseteq\text{Conv}(\Pi)$ is a class of mixtures of
policies and at least one mixture policy in $\widetilde{\Pi}$ is feasible for
$\mathcal{P}(\bm{\tau})$. Then, we have

$\displaystyle J_{R}(\bar{\pi})$ $\displaystyle\geq J_{R}(\pi_{c})-\xi$
(Optimality) $\displaystyle J_{C_{i}}(\bar{\pi})$
$\displaystyle\leq\tau_{i}+\frac{\xi}{B}+\frac{1}{B(1-\gamma)},\quad\text{for
all}~{}i=1,\dots I$ (Feasibility)

where $\pi_{c}$ is any feasible policy in $\widetilde{\Pi}$.

###### Proof.

We first prove $J_{R}(\bar{\pi})\geq J_{R}(\pi_{c})-\xi$, near optimality of
$\bar{\pi}$.

#### Optimality

Since $(\bar{\pi},\bar{\bm{\lambda}})$ is a $\xi$-near saddle point for
$L(\cdot,\cdot)$ with respect to $\widetilde{\Pi}\times B\bm{\Delta}^{I}$ and
$\pi_{c}\in\widetilde{\Pi}$, we have $L(\pi_{c},\bar{\bm{\lambda}})\leq
L(\bar{\pi},\bm{\lambda})+\xi$ for all $\bm{\lambda}\in B\bm{\Delta}^{I}$.
Choosing $\bm{\lambda}=\bm{0}$, we get

$L(\pi_{c},\bar{\bm{\lambda}})\leq L(\bar{\pi},0)+\xi=J_{R}(\bar{\pi})+\xi.$

Rearranging, we get

$\displaystyle J_{R}(\bar{\pi})$ $\displaystyle\geq
J_{R}(\pi_{c})+\bar{\bm{\lambda}}\cdot(\bm{\tau}-J_{\bm{C}}(\pi_{c}))-\xi$
$\displaystyle\geq J_{R}(\pi_{c})-\xi$

where the second inequality uses the feasibility of $\pi_{c}$ for
$\mathcal{P}(\bm{\tau})$. This proves the near optimality of $\bar{\pi}$ with
respect to $\pi_{c}$.

#### Feasibility

Now, to prove near feasibility of $\bar{\pi}$, recall from the proof of the
near optimality that $L(\pi_{c},\bar{\bm{\lambda}})\leq
L(\bar{\pi},\bm{\lambda})+\xi$ for all $\bm{\lambda}\in B\bm{\Delta}^{I}$
holds since $(\bar{\pi},\bar{\bm{\lambda}})$ is a $\xi$-near saddle point.
Choosing $\bm{\lambda}$ such that $\lambda_{j}=B$ for
$j=\operatorname*{argmin}_{i\in[I]}(\tau_{i}-J_{C_{i}}(\bar{\pi}))$ and
$\lambda_{j}=0$ for other $j$’s, and defining
$m=\min_{i\in[I]}(\tau_{i}-J_{C_{i}}(\bar{\pi}))$, we get

$L(\pi_{c},\bar{\bm{\lambda}})\leq
L(\bar{\pi},\bm{\lambda})+\xi=J_{R}(\bar{\pi})+Bm+\xi.$

On the other hand, the feasibility of $\pi_{c}$ for $\mathcal{P}(\bm{\tau})$
gives

$L(\pi_{c},\bar{\bm{\lambda}})=J_{R}(\pi_{c})+\bar{\bm{\lambda}}\cdot(\bm{\tau}-J_{\bm{C}}(\pi_{c}))\geq
J_{R}(\pi_{c}).$

Combining the previous two inequalities, we get

$Bm+\xi\geq J_{R}(\pi_{c})-J_{R}(\bar{\pi})\geq-\frac{1}{1-\gamma}$

where the last inequality uses $0\leq J_{R}(\cdot)\leq\frac{1}{1-\gamma}$.
Rearranging, and using the fact that $m\leq\tau_{i}-J_{C_{i}}(\bar{\pi})$ for
all $i=1,\dots,I$, we get

$\tau_{i}-J_{C_{i}}(\bar{\pi})\geq m\geq-\frac{1}{B(1-\gamma)}-\frac{\xi}{B}$

for all $i=1,\dots,I$. and it follows that

$J_{C_{i}}(\bar{\pi})\leq\tau_{i}+\frac{\xi}{B}+\frac{1}{B(1-\gamma)}.$

∎

Now, we study the case where PDCA is run with a tightened cost threshold
$\bm{\tau}-\eta\bm{1}$ where $\eta\geq 0$. We denote by
$L_{\eta}(\pi,\bm{\lambda})=J_{R}(\pi)+\bm{\lambda}\cdot(\bm{\tau}-\eta\bm{1}-J_{\bm{C}}(\pi))$
the Lagrangian for the tightened problem $\mathcal{P}(\bm{\tau}-\eta\bm{1})$.
The following lemma shows the property of a $\xi$-near saddle point for
$L_{\eta}(\cdot,\cdot)$.

######  Lemma 11.

Assume that Slater’s condition (Assumption B) holds and that
$\eta<\frac{\phi}{1-\gamma}$ so that $\mathcal{P}(\bm{\tau}-\eta\bm{1})$ also
satisfies Slater’s condition. Suppose $(\bar{\pi},\bar{\bm{\lambda}})$ is a
$\xi$-near saddle point for $L_{\eta}(\cdot,\cdot)$ with respect to
$\widetilde{\Pi}\times B\bm{\Delta}^{I}$. Let
$(\pi_{\eta}^{\star},\bm{\lambda}_{\eta}^{\star})$ be a primal-dual solution
to $\mathcal{P}(\bm{\tau}-\eta\bm{1})$ and
$\pi_{\eta}^{\star}\in\widetilde{\Pi}$. Assume
$B>\|\bm{\lambda}_{\eta}^{\star}\|_{1}$. Then, we have

$\displaystyle J_{R}(\bar{\pi})$ $\displaystyle\geq
J_{R}(\pi_{\eta}^{\star})-\xi$ (Optimality) $\displaystyle
J_{C_{i}}(\bar{\pi})$
$\displaystyle\leq\tau_{i}-\eta+\frac{\xi}{B-\|\bm{\lambda}_{\eta}^{\star}\|_{1}},\quad\text{for
all}~{}i=1,\dots,I$ (Feasibility)

###### Proof.

We first prove near optimality of $\bar{\pi}$.

#### Optimality

Since $(\bar{\pi},\bar{\bm{\lambda}})$ is a $\xi$-near saddle point for
$L_{\eta}(\cdot,\cdot)$ with respect to $\widetilde{\Pi}\times
B\bm{\Delta}^{I}$ and $\pi_{\eta}^{\star}\in\widetilde{\Pi}$, we have
$L_{\eta}(\pi_{\eta}^{\star},\bar{\bm{\lambda}})\leq
L_{\eta}(\bar{\pi},\bm{\lambda})+\xi$ for all $\bm{\lambda}\in
B\bm{\Delta}^{I}$. Choosing $\bm{\lambda}=\bm{0}$, we get

$L_{\eta}(\pi_{\eta}^{\star},\bar{\bm{\lambda}})\leq
L_{\eta}(\bar{\pi},0)+\xi=J_{R}(\bar{\pi})+\xi.$

Rearranging, we get

$J_{R}(\bar{\pi})\geq
J_{R}(\pi_{\eta}^{\star})+\bar{\bm{\lambda}}\cdot(\bm{\tau}-\eta\bm{1}-J_{\bm{C}}(\pi_{\eta}^{\star}))-\xi\geq
J_{R}(\pi_{\eta}^{\star})-\xi$

where the second inequality uses the feasibility of $\pi_{\eta}^{\star}$ for
$\mathcal{P}(\bm{\tau}-\eta\bm{1})$. Now, we prove feasibility of $\bar{\pi}$.

#### Feasibility

Recall that $(\pi_{\eta}^{\star},\bm{\lambda}_{\eta}^{\star})$ is a primal-
dual solution to the optimization problem $\mathcal{P}(\bm{\tau}-\eta\bm{1})$
and $L_{\eta}(\cdot,\cdot)$ is the Lagrangian function corresponding to the
problem $\mathcal{P}(\bm{\tau}-\eta\bm{1})$. By strong duality,
$(\pi_{\eta}^{\star},\bm{\lambda}_{\eta}^{\star})$ is a saddle point for
$L_{\eta}(\cdot,\cdot)$ with respect to
$\text{Conv}(\Pi)\times\mathbb{R}_{+}^{I}$. Hence, we have

$L_{\eta}(\bar{\pi},\bm{\lambda}_{\eta}^{\star})\leq
L_{\eta}(\pi_{\eta}^{\star},\bm{\lambda}_{\eta}^{\star})=J_{R}(\pi_{\eta}^{\star})+\bm{\lambda}_{\eta}^{\star}\cdot(\bm{\tau}-\eta\bm{1}-J_{\bm{C}}(\pi_{\eta}^{\star}))=J_{R}(\pi_{\eta}^{\star})$

where the first inequality follows from the fact that
$(\pi_{\eta}^{\star},\bm{\lambda}_{\eta}^{\star})$ is a saddle point of
$L_{\eta}(\cdot,\cdot)$ and the last equality follows from the complementary
slackness property of the solution
$(\pi_{\eta}^{\star},\bm{\lambda}_{\eta}^{\star})$. Rearranging, we get

$J_{R}(\pi_{\eta}^{\star})-J_{R}(\bar{\pi})\geq\bm{\lambda}_{\eta}^{\star}\cdot(\bm{\tau}-\eta\bm{1}-J_{\bm{C}}(\bar{\pi}))\geq(m-\eta)\|\bm{\lambda}_{\eta}^{\star}\|_{1}$
(5)

where we define $m=\min_{i\in[I]}(\tau_{i}-J_{C_{i}}(\bar{\pi}))$. Now, to
upper bound $J_{R}(\pi_{\eta}^{\star})-J_{R}(\bar{\pi})$, we first use the
feasibility of $\pi_{\eta}^{\star}$ for $\mathcal{P}(\bm{\tau}-\eta\bm{1})$ as
follows.

$L_{\eta}(\pi_{\eta}^{\star},\bar{\bm{\lambda}})=J_{R}(\pi_{\eta}^{\star})+\bar{\bm{\lambda}}\cdot(\bm{\tau}-\eta\bm{1}-J_{\bm{C}}(\pi_{\eta}^{\star}))\geq
J_{R}(\pi_{\eta}^{\star}).$

On the other hand, since $(\bar{\pi},\bar{\bm{\lambda}})$ is a $\xi$-near
saddle point for $L_{\eta}(\cdot,\cdot)$ with respect to
$\widetilde{\Pi}\times B\bm{\Delta}^{I}$ and
$\pi_{\eta}^{\star}\in\widetilde{\Pi}$, we have
$L_{\eta}(\pi_{\eta}^{\star},\bar{\bm{\lambda}})\leq
L_{\eta}(\bar{\pi},\bm{\lambda})+\xi$ for any $\bm{\lambda}\in
B\bm{\Delta}^{I}$. By choosing $\bm{\lambda}$ such that $\lambda_{j}=B$ for
$j=\operatorname*{argmin}_{i\in[I]}(\tau_{i}-J_{C_{i}}(\bar{\pi}))$ and
recalling $m=\min_{i\in[I]}(\tau_{i}-J_{C_{i}}(\bar{\pi}))$, we get

$L_{\eta}(\pi_{\eta}^{\star},\bar{\bm{\lambda}})\leq
L_{\eta}(\bar{\pi},\bm{\lambda})+\xi=J_{R}(\bar{\pi})+B(m-\eta)+\xi.$

Combining the previous two results (upper bound and lower bound of
$L_{\eta}(\pi_{\eta}^{\star},\bar{\bm{\lambda}})$), we get

$J_{R}(\pi_{\eta}^{\star})-J_{R}(\bar{\pi})\leq B(m-\eta)+\xi.$ (6)

Combining the lower bound (5) and the upper bound (6) of
$J_{R}(\pi_{\eta}^{\star})-J_{R}(\bar{\pi})$ and rearranging, we get

$m-\eta\geq\frac{-\xi}{B-\|\bm{\lambda}_{\eta}^{\star}\|_{1}}.$

Since $\tau_{i}-\eta-J_{C_{i}}(\bar{\pi})\geq m-\eta$ for all $i\in[I]$,
rearranging the above gives

$J_{C_{i}}(\bar{\pi})\leq\tau_{i}-\eta+\frac{\xi}{B-\|\bm{\lambda}_{\eta}^{\star}\|_{1}}$

for all $i=1,\dots,I$. ∎ Note that the lemma above requires
$B>\|\bm{\lambda}_{\eta}^{\star}\|_{1}$. We will show in Theorem 2 that with
Slater’s condition, we can upper bound $\|\bm{\lambda}_{\eta}^{\star}\|_{1}$
so that we can choose $B$ that indeed satisfies
$B>\|\bm{\lambda}_{\eta}^{\star}\|_{1}$.

##  E PROOF OF MAIN RESULTS

###  E.1 Proof of Theorem 3.5

We restate the theorem for convenience:

*

###### Proof.

Recall from Lemma 5 that
$\epsilon_{\text{stat}}\coloneqq\frac{C_{\ell_{2}}}{1-\gamma}\sqrt{\frac{\log(I|\mathcal{F}||\Pi||\mathcal{W}|/\delta)}{n}}+\frac{C_{\infty}\log(I|\mathcal{F}||\Pi||\mathcal{W}|/\delta)}{(1-\gamma)n}$.
The bound on $n$ guarantees

$\epsilon_{\text{stat}}\leq\mathcal{O}((1-\gamma)\varphi\,\epsilon).$

Invoking Lemma 7 with cost threshold $\bm{\tau}$ and bound
$B=1+\frac{1}{\varphi}$, we get with probability at least $1-\delta$ that

$L(\pi,\bar{\bm{\lambda}})\leq
L(\bar{\pi},\bm{\lambda})+\epsilon_{\text{saddle}}$

for all $\pi\in\text{Conv}(\Pi)$ with $w^{\pi}\in\mathcal{W}$ and
$\bm{\lambda}\in B\bm{\Delta}^{I}$ where
$\epsilon_{\text{saddle}}\coloneqq\frac{1+2B}{(1-\gamma)^{2}}\epsilon_{\text{opt}}(K)+\mathcal{O}\left(\frac{B\epsilon_{\text{stat}}}{1-\gamma}\right)$.
Since PDCA chooses $K$ such that
$\frac{1+2B}{(1-\gamma)^{2}}\epsilon_{\text{opt}}(K)\leq\epsilon$ and the
bound on $n$ guarantees
$\epsilon_{\text{stat}}\leq\mathcal{O}((1-\gamma)\varphi\,\epsilon)$, we have
$\epsilon_{\text{saddle}}\leq\mathcal{O}(\epsilon)$. Hence, invoking Lemma 11
with $\xi=\epsilon_{\text{saddle}}$, $B=1+\frac{1}{\varphi}$ and $\eta=0$, we
get

$\displaystyle J_{R}(\bar{\pi})$ $\displaystyle\geq
J_{R}(\pi_{c})-\epsilon_{\text{saddle}}\geq
J_{R}(\pi_{c})-\mathcal{O}(\epsilon)$ $\displaystyle J_{C_{i}}(\bar{\pi})$
$\displaystyle\leq\tau_{i}+\frac{\epsilon_{\text{saddle}}}{1+\frac{1}{\varphi}-\|\bm{\lambda}^{\star}\|_{1}}\leq\tau_{i}+\mathcal{O}(\epsilon),\quad
i=1,\dots,I$

where $\bm{\lambda}^{\star}$ is the optimal dual variable for the problem
$\mathcal{P}(\bm{\tau})$ and the last inequality uses
$\|\bm{\lambda}^{\star}\|_{1}\leq\frac{1}{\varphi}$, which follows by the
Slater’s condition (Assumption B) and Lemma 13.

∎

###  E.2 Result for arbitrary competing policy

######  Theorem 1.

Under assumptions A,C,D and E, the policy $\bar{\pi}$ returned by the PDCA
algorithm (Algorithm 1) with the cost threshold $\bm{\tau}$ and bound
$B=\frac{1}{(1-\gamma)\epsilon}$ satisfies
$J_{C_{i}}(\bar{\pi})\leq\tau_{i}+\mathcal{O}(\epsilon)$ for all
$i=1,\dots,I$, and $J_{R}(\pi)\geq J_{R}(\pi^{\star})-\mathcal{O}(\epsilon)$
with probability at least $1-\delta$ where $\pi^{\star}$ the optimal policy
for $\mathcal{P}(\bm{\tau})$ as long as

$n\geq\Omega\left(\frac{(C_{\ell_{2}})^{2}\log(I|\mathcal{F}||\Pi||\mathcal{W}|/\delta)}{(1-\gamma)^{6}\epsilon^{4}}\right).$

###### Proof.

Recall from Lemma 5 that
$\epsilon_{\text{stat}}\coloneqq\frac{C_{\ell_{2}}}{1-\gamma}\sqrt{\frac{\log(I|\mathcal{F}||\Pi||\mathcal{W}|/\delta)}{n}}+\frac{C_{\infty}\log(I|\mathcal{F}||\Pi||\mathcal{W}|/\delta)}{(1-\gamma)n}$.
The choice
$n\geq\Omega\left(\frac{(C_{\ell_{2}})^{2}\log(I|\mathcal{F}||\Pi||\mathcal{W}|/\delta)}{(1-\gamma)^{6}\epsilon^{4}}\right)$
guarantees

$\epsilon_{\text{stat}}\leq\mathcal{O}((1-\gamma)^{2}\epsilon^{2}).$

Invoking Lemma 7 with cost threshold $\bm{\tau}$ and bound
$B=\frac{1}{(1-\gamma)\epsilon}$, we get with probability at least $1-\delta$
that

$L(\pi,\bar{\bm{\lambda}})\leq
L(\bar{\pi},\bm{\lambda})+\epsilon_{\text{saddle}}$

for all $\pi\in\text{Conv}(\Pi)$ and
$\bm{\lambda}\in\frac{1}{(1-\gamma)\epsilon}\bm{\Delta}^{I}$ where
$\epsilon_{\text{saddle}}\coloneqq\frac{1+2B}{(1-\gamma)^{2}}\epsilon_{\text{opt}}^{\pi}(K)+\frac{2B}{1-\gamma}\epsilon_{\text{opt}}^{\lambda}(K)+\mathcal{O}\left(\frac{B\epsilon_{\text{stat}}}{1-\gamma}\right)$.
Since PDCA chooses $K$ such that
$\frac{1+2B}{(1-\gamma)^{2}}\epsilon_{\text{opt}}^{\pi}(K)\leq\epsilon$ and
$\frac{2B}{1-\gamma}\epsilon_{\text{opt}}^{\lambda}(K)\leq\epsilon$, and $n$
is chosen to guarantee
$\epsilon_{\text{stat}}\leq\mathcal{O}((1-\gamma)^{2}\epsilon^{2})$, we have
$\epsilon_{\text{saddle}}\leq\mathcal{O}(\epsilon)$. Hence, invoking Lemma 10
with $\xi=\epsilon_{\text{saddle}}$ and $B=\frac{1}{(1-\gamma)\epsilon}$, we
get

$\displaystyle J_{R}(\bar{\pi})$ $\displaystyle\geq
J_{R}(\pi_{c})-\epsilon_{\text{saddle}}\geq
J_{R}(\pi_{c})-\mathcal{O}(\epsilon)$ $\displaystyle J_{C_{i}}(\bar{\pi})$
$\displaystyle\leq\tau_{i}+\frac{\epsilon_{\text{saddle}}}{B}+\frac{1}{B(1-\gamma)}\leq\tau_{i}+\mathcal{O}(\epsilon),\quad
i=1,\dots,I.$

∎

###  E.3 Learning policy satisfying constraints exactly

Note that results in previous sections provide a bound on sample complexity
for finding a nearly optimal policy that approximately satisfies the
constraints. In this section, we provide a bound for finding a nearly optimal
policy that satisfies the constraints exactly by running PDCA with tightened
constraints. We need the following additional technical assumption on MIW
realizability.

######  Assumption F.

Suppose the Slater’s condition holds (Assumption B). For some constant
$\alpha\in[\frac{\varphi}{c(1-\gamma)},\frac{\varphi}{1-\gamma}]$ where $c\geq
0$, we have $w^{\pi^{\star}_{\alpha}}\in\mathcal{W}$ where
$\pi^{\star}_{\alpha}$ denotes an optimal policy of the optimization problem
$\mathcal{P}(\bm{\tau}-\alpha\bm{1})$.

######  Theorem 2.

Let $\epsilon\in(0,\frac{1}{2}]$ be given. Under assumptions A,B,C,D,E and F,
the policy $\bar{\pi}$ returned by the PDCA algorithm (Algorithm 1) with the
cost threshold $\bm{\tau}-\eta\bm{1}$, where $\eta=\varphi\epsilon$, and bound
$B=\frac{5}{\varphi}$ satisfies $J_{C_{i}}(\bar{\pi})\leq\tau_{i}$ for all
$i=1,\dots,I$, and $J_{R}(\pi)\geq J_{R}(\pi^{\star})-\mathcal{O}(\epsilon)$
with probability at least $1-\delta$, where $\pi^{\star}$ is an optimal policy
for $\mathcal{P}(\bm{\tau})$ as long as

$n\geq\Omega\left(\frac{(C_{\ell_{2}})^{2}\log(I|\mathcal{F}||\Pi||\mathcal{W}|/\delta)}{(1-\gamma)^{4}\varphi^{2}\epsilon^{2}}\right).$

###### Proof.

Recall from Lemma 5 that
$\epsilon_{\text{stat}}\coloneqq\frac{C_{\ell_{2}}}{1-\gamma}\sqrt{\frac{\log(I|\mathcal{F}||\Pi||\mathcal{W}|/\delta)}{n}}+\frac{C_{\infty}\log(I|\mathcal{F}||\Pi||\mathcal{W}|/\delta)}{(1-\gamma)n}$.
The bound on $n$ in the theorem guarantees
$\epsilon_{\text{stat}}\leq\mathcal{O}((1-\gamma)\varphi\,\epsilon)$. Invoking
Lemma 7 with cost threshold $\bm{\tau}-\eta\bm{1}$ and bound
$B=\frac{5}{\varphi}$, we get with probability at least $1-\delta$ that

$L_{\eta}(\pi,\bar{\bm{\lambda}})\leq
L_{\eta}(\bar{\pi},\bm{\lambda})+\epsilon_{\text{saddle}}$ (7)

for all $\pi\in\text{Conv}(\Pi)$ satisfying $w^{\pi}\in\mathcal{W}$ and
$\bm{\lambda}\in\frac{5}{\varphi}\bm{\Delta}^{I}$ where
$L_{\eta}(\cdot,\cdot)$ is the Lagrangian for
$\mathcal{P}(\bm{\tau}-\eta\bm{1})$ and
$\epsilon_{\text{saddle}}\coloneqq\frac{1+2B}{(1-\gamma)^{2}}\epsilon_{\text{opt}}(K)+\mathcal{O}\left(\frac{\epsilon_{\text{stat}}}{(1-\gamma)\varphi}\right)$.
Since PDCA chooses $K$ such that
$\frac{1+2B}{(1-\gamma)^{2}}\epsilon_{\text{opt}}(K)\leq\epsilon$ and $n$ is
chosen to guarantee
$\epsilon_{\text{stat}}\leq\mathcal{O}((1-\gamma)\varphi\,\epsilon)$, we have
$\epsilon_{\text{saddle}}\leq 2\epsilon$ (with appropriate scaling of $n$ by a
universal constant).

Let $\pi^{\star}$ be an optimal policy for $\mathcal{P}(\bm{\tau})$ and
$\pi^{\star}_{\alpha}$ for $\mathcal{P}(\bm{\tau}-\alpha\bm{1})$. By the MIW
realizability assumptions E and F, we have
$w^{\pi^{\star}},w^{\pi^{\star}_{\alpha}}\in\mathcal{W}$ and it follows from
(7) that

$\displaystyle L_{\eta}(\pi^{\star},\bar{\bm{\lambda}})$ $\displaystyle\leq
L_{\eta}(\bar{\pi},\bm{\lambda})+2\epsilon$ (8) $\displaystyle
L_{\eta}(\pi^{\star}_{\alpha},\bar{\bm{\lambda}})$ $\displaystyle\leq
L_{\eta}(\bar{\pi},\bm{\lambda})+2\epsilon$ (9)

for all $\bm{\lambda}\in\frac{5}{\varphi}\bm{\Delta}^{I}$. Now, we show near
optimality and exact feasibility from these inequalities.

#### Near Optimality

Setting $\bm{\lambda}=\bm{0}$ in (8) and rearranging, we get

$\displaystyle J_{R}(\bar{\pi})$ $\displaystyle\geq
J_{R}(\pi^{\star})+\bar{\bm{\lambda}}\cdot(\bm{\tau}-\eta\bm{1}-J_{\bm{C}}(\pi^{\star}))-2\epsilon$
$\displaystyle\geq
J_{R}(\pi^{\star})-\eta\|\bar{\bm{\lambda}}\|_{1}-\mathcal{O}(\epsilon)$
$\displaystyle\geq J_{R}(\pi^{\star})-\mathcal{O}(\epsilon)$

where the second inequality follows by the feasibility of $\pi^{\star}$ for
$\mathcal{P}(\bm{\tau})$ and
$\epsilon_{\text{saddle}}\leq\mathcal{O}(\epsilon)$; the last inequality
follows by $\eta\|\bar{\bm{\lambda}}\|_{1}\leq\eta B=\mathcal{O}(\epsilon)$.
This proves near optimality of $\bar{\pi}$ Now we prove that $\bar{\pi}$ is
(exactly) feasible for $\mathcal{P}(\bm{\tau})$.

#### Exact Feasibility

Define $m=\min_{i\in[I]}(\tau_{i}-J_{C_{i}}(\bar{\pi}))$. If $m\geq 0$ then
$\tau_{i}-J_{C_{i}}(\bar{\pi})\geq 0$ for all $i=1,\dots,I$ and exact
feasibility trivially holds. We only consider the case where $m<0$. Define a
mixture policy
$\widetilde{\pi}=(1-\zeta)\pi^{\star}+\zeta\pi_{\alpha}^{\star}$ where
$\zeta\in(0,1)$ is to be determined later. Since
$L_{\eta}(\cdot,\bm{\bar{\lambda}})$ is linear, a linear combination of (8)
and (9) with coefficients $1-\zeta$ and $\zeta$ respectively, we get

$L_{\eta}(\widetilde{\pi},\bar{\bm{\lambda}})\leq
L_{\eta}(\bar{\pi},\bm{\lambda})+2\epsilon.$

Choosing $\bm{\lambda}$ such that $\lambda_{j}=B$ for
$j=\operatorname*{argmin}_{i\in[I]}(\tau_{i}-J_{C_{i}}(\bar{\pi}))$ and
$\lambda_{j}=0$ for all other indices, we get

$\displaystyle L_{\eta}(\widetilde{\pi},\bar{\bm{\lambda}})$
$\displaystyle\leq
J_{R}(\bar{\pi})+\bm{\lambda}\cdot(\bm{\tau}-\eta\bm{1}-J_{\bm{C}}(\bar{\pi}))+2\epsilon$
$\displaystyle=J_{R}(\bar{\pi})+B(m-\eta)+2\epsilon.$

On the other hand, using the fact that $\widetilde{\pi}$ is feasible for
$\mathcal{P}(\bm{\tau}-\zeta\alpha\bm{1})$, we get

$\displaystyle L_{\eta}(\widetilde{\pi},\bar{\bm{\lambda}})$
$\displaystyle=J_{R}(\widetilde{\pi})+\bar{\bm{\lambda}}(\bm{\tau}-\eta\bm{1}-J_{\bm{C}}(\widetilde{\pi}))$
$\displaystyle\geq
J_{R}(\widetilde{\pi})+(\zeta\alpha-\eta)\|\bar{\bm{\lambda}}\|_{1}.$

Combining the previous two results (upper bound and lower bound of
$L_{\eta}(\widetilde{\pi},\bar{\bm{\lambda}})$) and rearranging, we get

$J_{R}(\widetilde{\pi})-J_{R}(\bar{\pi})\leq
B(m-\eta)-(\zeta\alpha-\eta)\|\bar{\bm{\lambda}}\|_{1}+2\epsilon.$ (10)

Now, to get a lower bound of $J_{R}(\widetilde{\pi})-J_{R}(\bar{\pi})$, let
$(\widetilde{\pi}^{\star},\widetilde{\bm{\lambda}}^{\star})$ be a primal-dual
solution of $\mathcal{P}(\bm{\tau}-\zeta\alpha\bm{1})$. Note that
$\mathcal{P}(\bm{\tau}-\zeta\alpha\bm{1})$ is feasible by the Slater’s
condition assumption B and the fact that
$\zeta\alpha\in(0,\frac{\varphi}{1-\gamma})$. Since
$(\widetilde{\pi}^{\star},\widetilde{\bm{\lambda}}^{\star})$ is a saddle point
of
$L_{\zeta\alpha}(\pi,\bm{\lambda})=J_{R}(\pi)+\bm{\lambda}\cdot(\bm{\tau}-\zeta\alpha\bm{1}-J_{\bm{C}}(\pi))$
with respect to $\text{Conv}(\Pi)\times\mathbb{R}_{+}^{I}$, we get

$L_{\zeta\alpha}(\bar{\pi},\widetilde{\bm{\lambda}}^{\star})\leq
L_{\zeta\alpha}(\widetilde{\pi}^{\star},\widetilde{\bm{\lambda}}^{\star})=J_{R}(\widetilde{\pi}^{\star})\leq
J_{R}(\pi^{\star})\leq\frac{1}{1-\zeta}J_{R}(\widetilde{\pi})$

where the equality follows by the complementary slackness property; the second
inequality follows since the feasibility set of $\mathcal{P}(\bm{\tau})$
contains that of $\mathcal{P}(\bm{\tau}-\zeta\alpha\bm{1})$; and the last
inequality follows by
$J_{R}(\widetilde{\pi})=(1-\zeta)J_{R}(\pi^{\star})+\zeta
J_{R}(\pi_{\alpha}^{\star})\geq(1-\zeta)J_{R}(\pi^{\star})$. Rearranging, we
get

$\displaystyle J_{R}(\widetilde{\pi})-J_{R}(\bar{\pi})$
$\displaystyle\geq-\zeta
J_{R}(\bar{\pi})+(1-\zeta)\widetilde{\bm{\lambda}}^{\star}\cdot(\bm{\tau}-\zeta\alpha\bm{1}-J_{\bm{C}}(\bar{\pi}))$
$\displaystyle\geq\frac{-\zeta}{1-\gamma}+(1-\zeta)(m-\zeta\alpha)\|\widetilde{\bm{\lambda}}^{\star}\|_{1}$

where the second inequality follows by $J_{R}(\cdot)\leq\frac{1}{1-\gamma}$
and the definition of $m$. Combining with the upper bound of
$J_{R}(\widetilde{\pi})-J_{R}(\bar{\pi})$ shown in (10) and rearranging, we
get

$(B-(1-\zeta)\|\widetilde{\bm{\lambda}}^{\star}\|_{1})m\geq
B\eta+(\zeta\alpha-\eta)\|\bar{\bm{\lambda}}\|_{1}-\frac{\zeta}{1-\gamma}-(1-\zeta)\zeta\alpha\|\widetilde{\bm{\lambda}}^{\star}\|_{1}-2\epsilon.$
(11)

Now, we choose our parameters as follows.

$\zeta=(1-\gamma)\epsilon,\quad
B=\frac{5c}{\varphi},\quad\eta=\frac{\varphi\epsilon}{c}.$

Note that $B\eta=5\epsilon$ and $\zeta\alpha\geq\eta$. Also, since
$\widetilde{\bm{\lambda}}^{\star}$ is a dual solution of
$\mathcal{P}(\bm{\tau}-\zeta\alpha\bm{1})$, which has a margin of
$\frac{\varphi}{1-\gamma}-\zeta\alpha$, Lemma 13 gives
$\|\widetilde{\bm{\lambda}}^{\star}\|_{1}\leq\frac{1}{\varphi-(1-\gamma)\zeta\alpha}$.
Hence,

$\zeta\alpha\|\widetilde{\bm{\lambda}}^{\star}\|_{1}\leq\frac{\zeta\alpha}{\varphi-(1-\gamma)\zeta\alpha}\leq\frac{1}{1-\gamma}\frac{\zeta\varphi}{\varphi-\varphi\zeta}\leq\frac{2\zeta}{1-\gamma}\leq
2\epsilon$

where the second inequality uses $\alpha\leq\frac{\varphi}{1-\gamma}$ and the
fact that $h(x)=\frac{x}{\varphi-x}$ is increasing for $x\in(0,\varphi)$; and
the third inequality uses the fact that $\zeta\leq\frac{1}{2}$. Note that
$\|\widetilde{\bm{\lambda}}^{\star}\|_{1}\leq\frac{\epsilon}{\zeta\alpha}=\frac{1}{(1-\gamma)\alpha}<B$
so that $B-(1-\zeta)\|\widetilde{\bm{\lambda}}^{\star}\|_{1}>0$. Hence, the
previous result (11) gives

$\displaystyle(B-(1-\zeta)\|\widetilde{\bm{\lambda}}^{\star}\|_{1})m$
$\displaystyle\geq
B\eta+(\zeta\alpha-\eta)\|\bar{\bm{\lambda}}\|_{1}-\frac{\zeta}{1-\gamma}-(1-\zeta)\zeta\alpha\|\widetilde{\bm{\lambda}}^{\star}\|_{1}-2\epsilon$
$\displaystyle\geq 5\epsilon+0-\epsilon-2\epsilon-2\epsilon$
$\displaystyle=0.$

Since $B-(1-\zeta)\|\widetilde{\bm{\lambda}}^{\star}\|_{1}>0$, we have $m\geq
0$ which implies $\tau_{i}-J_{C_{i}}(\bar{\pi})\geq 0$ for all $i=1,\dots,I$.
This completes the proof.

∎

##  F CONVEX OPTIMIZATION

######  Lemma 12.

Let $(\pi^{\star},\lambda^{\star})$ be optimal primal dual solutions to the
constrained optimization problem $\mathcal{P}(\tau)$. Let
$(\widetilde{\pi}^{\star},\widetilde{\lambda}^{\star})$ be optimal primal dual
solutions to the perturbed problem $\mathcal{P}(\widetilde{\bm{\tau}})$ where
$\widetilde{\bm{\tau}}=\bm{\tau}-\eta\bm{1}$. Then, we have

$J_{R}(\widetilde{\pi}^{\star})\geq
J_{R}(\pi^{\star})-\eta\|\widetilde{\bm{\lambda}}^{\star}\|_{1}.$

###### Proof.

The proof follows Chapter 5.6 in [4]. By strong duality of the optimization
problem $\mathcal{P}(\widetilde{\bm{\tau}})$, we have
$J_{R}(\widetilde{\pi}^{\star})=d(\widetilde{\bm{\lambda}}^{\star})$ where
$d(\bm{\lambda})=\max_{\pi\in\text{Conv}(\Pi)}L(\pi,\bm{\lambda};\widetilde{\bm{\tau}})$
is the dual function of $\mathcal{P}(\widetilde{\bm{\tau}})$. Hence,

$\displaystyle J_{R}(\widetilde{\pi}^{\star})$
$\displaystyle=d(\widetilde{\bm{\lambda}}^{\star})$ $\displaystyle\geq
J_{R}(\pi^{\star})+\widetilde{\bm{\lambda}}^{\star}\cdot(\widetilde{\bm{\tau}}-J_{\bm{C}}(\pi^{\star}))$
$\displaystyle=J_{R}(\pi^{\star})+\widetilde{\bm{\lambda}}^{\star}\cdot(\bm{\tau}-J_{\bm{C}}(\pi^{\star}))-\widetilde{\bm{\lambda}}^{\star}\cdot\eta\bm{1}$
$\displaystyle\geq
J_{R}(\pi^{\star})-\widetilde{\bm{\lambda}}^{\star}\cdot\eta\bm{1}$

where the first inequality follows from the definition of the dual function
$d(\cdot)$ and the second follows by the feasibility of $\pi^{\star}$ for
$\mathcal{P}(\bm{\tau})$. ∎

######  Lemma 13.

Consider a constrained optimization problem $\mathcal{P}(\bm{\tau})$ with
threshold $\bm{\tau}=(\tau_{1},\dots,\tau_{I})$ with $\tau_{i}>0$ for all
$i=1,\dots,I$. Suppose the problem satisfies Slater’s condition with margin
$\frac{\varphi}{1-\gamma}>0$, in other words, there exists $\pi\in\Pi$ that
satisfies the constraint $J_{C_{i}}(\pi)\leq\tau_{i}-\frac{\varphi}{1-\gamma}$
for all $i=1,\dots,I$. Then, the optimal dual variable $\bm{\lambda}^{\star}$
of the problem satisfies $\|\bm{\lambda}^{\star}\|_{1}\leq\frac{1}{\varphi}$.

###### Proof.

Let $\pi^{\star}$ be an optimal policy of the optimization problem
$\mathcal{P}(\bm{\tau})$. Define the dual function
$f(\bm{\lambda})=\max_{\pi\in\Pi}J_{R}(\pi)+\bm{\lambda}\cdot(\bm{\tau}-J_{\bm{C}}(\pi))$.
Let
$\bm{\lambda}^{\star}=\operatorname*{argmin}_{\bm{\lambda}\in\mathbb{R}_{+}^{I}}f(\bm{\lambda})$.
Trivially, $\lambda_{i}^{\star}\geq 0$ for all $i=1,\dots,I$. Also, by strong
duality, we have $f(\bm{\lambda}^{\star})=J_{R}(\pi^{\star})$. Let
$\widehat{\pi}$ be a feasible policy with
$J_{\bm{C}}(\widehat{\pi})\leq\bm{\tau}-\frac{\varphi}{1-\gamma}\bm{1}$ where
the inequality is component-wise and $\bm{1}=(1,\dots,1)$. Such a policy
exists by the assumption of this lemma. Then,

$J_{R}(\pi^{\star})=f(\bm{\lambda}^{\star})\geq
J_{R}(\widehat{\pi})+\bm{\lambda}^{\star}\cdot(\bm{\tau}-J_{\bm{C}}(\widehat{\pi}))\geq
J_{R}(\widehat{\pi})+\bm{\lambda}^{\star}\cdot\frac{\varphi}{1-\gamma}\bm{1}=J_{R}(\widehat{\pi})+\frac{\varphi}{1-\gamma}\|\bm{\lambda}^{\star}\|_{1}.$

Rearranging and using $1/(1-\gamma)\geq J_{R}(\pi^{\star})\geq
J_{R}(\widehat{\pi})\geq 0$ completes the proof:

$\|\bm{\lambda}^{\star}\|_{1}\leq\frac{J_{R}(\pi^{\star})-J_{R}(\widehat{\pi})}{\varphi/(1-\gamma)}\leq\frac{1}{\varphi}.$

∎

##  G EXPERIMENTS

In this section, we empirically demonstrate the performance of our algorithm
PDCA by running it in various environments and comparing the performance to
COptiDICE. For the parameter tuning and the experiments, we used an internal
cluster of nodes with 20-core 2.40 GHz CPU and Nvidia Tesla V100 GPU. The
total amount of computing time was around 600 hours.

###  G.1 Tabular CMDP Experiments

In this section, we provide details of the experiment run on a randomly
generated CMDP discussed in Section 5. We follow a similar experimental
protocol as [21].

#### CMDP Generation

We set the number of states to 10 and the number of actions to 5. The
transition probability is randomly generated by drawing from a Dirichlet
distribution with all parameters $(1,\dots,1)$ for generating each
$P(\cdot|s,a)$. We set the number of cost functions $I$ to 1. The reward
function $R$ is randomly drawn from $[0,1]$ uniformly for each $R(s,a)$. The
cost function $C_{1}$ is randomly drawn from a beta distribution with
parameters 0.2, 0.2 for each $C_{1}(s,a)$. We choose the discount factor
$\gamma=0.8$ and the cost threshold $\tau=0.5$. We repeat the random
generation policy until the cost threshold is not slack for the optimal
policy.

####  $\pi$-Player

We use the natural policy gradient algorithm with exponential weight updating
scheme for the $\pi$ player (Algorithm 3).

Input: Learning rate $\eta$, sequence of functions
$h_{1},\dots,h_{K}\in(\mathcal{S}\times\mathcal{A}\rightarrow[-1,1])$

Initialize: $\pi_{1}$ a uniform policy.

1 for  _$k=1,\dots,K-1$_ do

2 for  _$s\in\mathcal{S}$_ do

3 $\pi_{k+1}(a|s)\propto\pi_{k}(a|s)\exp(\eta h_{k}(s,a))$ normalized to sum
to 1 across $a\in\mathcal{A}$.

4

Return: Sequence $\pi_{1},\dots,\pi_{K}$

Algorithm 3 Natural policy gradient

#### Offline Dataset

We set behavior policy $\mu$ to be a mixture of $\pi_{\text{uniform}}$ and
$\pi^{\star}$ where $\pi_{\text{uniform}}$ is the uniform policy that takes
actions uniformly at random from the action space $\mathcal{A}$ at every
state, and $\pi^{\star}$ is the optimal solution to the generated CMDP. We
exactly solve for the occupancy measure $d^{\mu}$ of the behavior policy
$\mu$. We repeatedly sample the $(s,a)$ pair from $d^{\mu}$ and then sample
$s^{\prime}$ according to $P(\cdot|s,a)$.

#### Hyperparameters

The learning rate for the $\pi$-player is chosen using grid search in
$\\{1,2,5,10\\}$. The bound $B$ for the $\lambda$-player is chosen by grid
search in $\\{2,5,10\\}$. The bound $C_{\infty}$ for $\mathcal{W}$ is chosen
by a grid search in $\\{2,5,10\\}$.

###  G.2 RWRL Benchmark Experiments

#### Hyperparameters

We do a grid search on $\\{0.00005,0.0001,0.0003,0.0005,0.001\\}$ for
determining the learning rate $\eta_{\text{fast}}$ for the critics and a grid
search on $\\{0.00005,0.0001,0.0002\\}$ for determining the learning rate
$\eta_{\text{slow}}$ for the $\pi$-player. The chosen learning rates are
$\eta_{\text{fast}}=0.0003$ and $\eta_{\text{slow}}=0.0001$. We use the batch
size 1024. We run $K=30000$ iterations for Cartpole, Walker, Quadruped
environments and $K=50000$ iterations for the Humanoid environment. For the
policy network and the networks for the critics, we use fully-connected neural
networks with two hidden layers of width 256.

###  G.3 Bullet Safety Gym Benchmark Experiments

In this section, we provide details of the experiments run on Bullet Safety
Gym benchmark environments.

#### Offline Datasets

We use the offline datasets provided by [25]. They collect dataset for each
environment by merging trajectories generated by algorithms trained with
various cost thresholds and hyperparameters. After merging, they run a post-
processing of filtering redundant trajectories to ensure a diverse set of
trajectories. For details, refer to their paper.

#### Hyperparameters

Following the setup used by [25], we set the learning rate
$\eta_{\text{fast}}$ for the critics to $0.001$ and the learning rate
$\eta_{\text{slow}}$ for the $\pi$-player to $0.0001$. We use the batch size
512. We run $K=100,000$ iterations. For the policy network and the networks
for the critics, we use fully-connected neural networks with two hidden layers
of width 256. We do a grid search on $\\{2,5,10\\}$ for the bound $B$ for the
$\lambda$-player. We do a grid search on $\\{2,5,10\\}$ for the bound
$C_{\infty}$ for $\mathcal{W}$.