# Cancellation-Free Regret Bounds for Lagrangian Approaches in Constrained
Markov Decision Processes

Adrian Müller  Department of Computer Science, ETH Zürich111Correspondence to:
<EMAIL_ADDRESS>Pragnya Alatur  Department of Computer Science, ETH
Zürich111Correspondence to<EMAIL_ADDRESS>Giorgia Ramponi  Department of
Computer Science, ETH Zürich111Correspondence to<EMAIL_ADDRESS>Niao He
Department of Computer Science, ETH Zürich111Correspondence to:
<EMAIL_ADDRESS>
# Cancellation-Free Regret Bounds for Lagrangian Approaches in Constrained
Markov Decision Processes

Adrian Müller  Department of Computer Science, ETH Zürich111Correspondence to:
<EMAIL_ADDRESS>Pragnya Alatur  Department of Computer Science, ETH
Zürich111Correspondence to<EMAIL_ADDRESS>Giorgia Ramponi  Department of
Computer Science, ETH Zürich111Correspondence to<EMAIL_ADDRESS>Niao He
Department of Computer Science, ETH Zürich111Correspondence to:
<EMAIL_ADDRESS>
###### Abstract

Constrained Markov Decision Processes (CMDPs) are one of the common ways to
model safe reinforcement learning problems, where the safety objectives are
modeled by constraint functions. Lagrangian-based dual or primal-dual
algorithms provide efficient methods for learning in CMDPs. For these
algorithms, the currently known regret bounds in the finite-horizon setting
allow for a cancellation of errors; that is, one can compensate for a
constraint violation in one episode with a strict constraint satisfaction in
another episode. However, in practical applications, we do not consider such a
behavior safe.

In this paper, we overcome this weakness by proposing a novel model-based dual
algorithm OptAug-CMDP for tabular finite-horizon CMDPs. Our algorithm is
motivated by the augmented Lagrangian method and can be performed efficiently.
We show that during $K$ episodes of exploring the CMDP, our algorithm obtains
a regret of $\tilde{O}(\sqrt{K})$ for both the objective and the constraint
violation. Unlike existing Lagrangian approaches, our algorithm achieves this
regret without the need for the cancellation of errors.

###  1 Introduction

In classical reinforcement learning (RL, Sutton and Barto, 2018), the goal is
to learn an optimal policy when interacting with an unknown Markov decision
process (MDP, Bellman, 1957). In MDPs, an agent aims to minimize the
cumulative cost it incurs during an episode of the MDP. However, in practical
scenarios, the learned policy often must also adhere to certain safety
constraints. For example, when navigating a car on a race track, one would
want to avoid crossing the boundaries of the track too often. Such safety
requirements are commonly modeled via constrained Markov decision processes
(CMDPs, Altman, 1999). We consider the problem of learning an optimal feasible
policy in a CMDP. That is, the goal of the agent is to minimize the cost while
satisfying the constraints222i.e., being feasible for the CMDP, which we also
refer to as being safe. Since the CMDP is unknown, we formalize these
desiderata by considering the regret with respect to an optimal feasible
solution for the cost and for the constraint violation, respectively.

Importantly, we do not consider it sufficient to provide an agent whose
cumulative cost suboptimality and cumulative constraint violation are
sublinear. This is because an agent can have a negative constraint violation
(by being very safe but incurring higher cost than an optimal safe policy), or
a positive constraint violation (by being unsafe but incurring lower cost than
an optimal safe policy). Thus, terms from these two cases can cancel each
other out, which we refer to as the so-called cancellation of errors (Efroni
et al., 2020). An agent for which these cumulative terms are sublinear may
violate the safety constraints heavily during learning by oscillating around
an optimal safe policy. While such a method converges on average to an optimal
safe policy333Here, we refer to the value functions with respect to the
underlying CMDP., it neither allows for directly extracting an optimal
feasible policy nor does it guarantee safety during learning. We consider a
stronger notion of regret, which overcomes this issue by considering the sum
of the positive parts of the error terms instead. As pointed out by Efroni et
al. (2020), it is of major theoretical interest whether Lagrangian approaches
can achieve sublinear bounds for this notion of regret.

The approaches to learning CMDPs are split into linear programming (LP) and
Lagrangian approaches444i.e., dual and primal-dual algorithms (Altman, 1999;
Efroni et al., 2020). While LP-based algorithms generally allow for sublinear
regret bounds without the need for cancellations (Efroni et al., 2020), they
can be expensive when dealing with large state-action spaces. In contrast, in
Lagrangian methods, we can solve the optimization problem arising in each
episode using dynamic programming (DP), offering a computational benefit over
solving LPs. However, the currently known bounds for Lagrangian approaches
only concern a weaker form of regret that allows for the aforementioned
cancellation of errors. As Efroni et al. (2020) pointed out, this is due to
the underlying optimization methods rather than a weakness of the analysis.
The main goal of this paper is to provide a Lagrangian-based algorithm that
guarantees sublinear regret without the cancellation of errors. To achieve
this, the key problem we solve is stopping the agent from oscillating around
an optimal safe policy. Our contributions can be summarized as follows:

  * •

We propose a novel model-based dual algorithm, OptAug-CMDP, for learning an
optimal feasible policy in an unknown CMDP (Section 3). The algorithm is split
into a model pre-training phase and an optimistic exploration phase motivated
by the augmented Lagrangian method.

  * •

We show that a sub-problem required for OptAug-CMDP can be reformulated as a
convex optimization problem. We provide an efficient algorithm to solve it
(Section 3), despite the non-linearity introduced by considering the augmented
Lagrangian.

  * •

We prove that with high probability, during $K$ episodes OptAug-CMDP achieves
regrets for the cost and the constraint violations of $\tilde{O}(\sqrt{K})$
when only highlighting the dependency on $K$. Notably, we achieve this bound
for the stronger notion of regret, which does not allow for the cancellation
of errors. This partly settles the open problem posed by Efroni et al. (2020).

####  1.1 Related Work

The most relevant foundation for our work is the work by Efroni et al. (2020),
which reviews model-based algorithms for CMDPs and establishes regret bounds
for them. The authors analyze the LP-based algorithms OptCMDP and OptCMDP-
bonus that achieve sublinear regret without cancellations. However, the
Lagrangian-based algorithms they analyze, OptDual-CMDP and OptPrimalDual-CMDP,
only achieve sublinear regret with cancellations. This is because the
oscillatory behavior of dual and primal-dual descent methods prevents the
individual iterates from being approximately feasible. Therefore, the authors
pose the open question of whether one can devise Lagrangian-based algorithms
that do not suffer from this issue.

The vast majority of relevant work providing guarantees for Lagrangian
approaches to CMDPs is concerned with model-free primal-dual algorithms (Ding
et al., 2020; Bai et al., 2022; Ding et al., 2022a, b) or model-based dual
algorithms (Liu et al., 2021b; Efroni et al., 2020). However, in both cases,
the existing literature does not address the issue of the cancellation of
errors when exploring the CMDP and thus does not provide a method for safely
finding an optimal feasible policy.555That is, there are no guarantees on the
constraint violations of the individual iterates for these methods. While
there is work on analyzing different forms of regularization to the
Lagrangian-based algorithms, their guarantees either require the cancellation
of errors (Liu et al., 2021a) or assume access to exact policy gradients (Ying
et al., 2022; Li et al., 2021b). Moskovitz et al. (2023) propose a first
approach to address the cancellation of errors, by replacing gradients with
their optimistic gradient counterparts in well-known Lagrangian-based RL
algorithms. While they show the empirical success of their methods, their
theoretical analysis is restricted to the case of having access to an exact
policy gradient oracle. Stooke et al. (2020) address the underlying problem of
oscillations of Lagrangian methods for CMDPs via PID control in the context of
deep RL, providing experimental successes but no guarantees. Thus, to the best
of our knowledge, none of the existing works addresses the open question of
Efroni et al. (2020) in the setup of an unknown CMDP.

While there are mentions of using the augmented Lagrangian method for CMDPs
(Li et al., 2021a; Lu, 2022; Krishnamurthy, 2003; Krishnamurthy and Abad,
2011, 2012), all such works are concerned with research questions rather
different from ours. The only one similar to ours is that of Li et al.
(2021a). The authors propose a surrogate reward inspired by the augmented
Lagrangian to promote safety during learning. However, their method
significantly differs from ours as it is concerned with instantaneous
constraints in an infinite-horizon CMDP. Moreover, their analysis only shows
that an optimal policy for their surrogate MDP is optimal for the original
CMDP (under certain assumptions).

###  2 Background and Problem Formulation

Notation: For any $n\in\mathbb{N}$, we use the short-hand notation $[n]$ to
refer to the set of integers $\\{1,\dots,n\\}$. For any finite set $X$, we
denote by $\Delta\left(X\right)$ the probability simplex over $X$, i.e.,
$\Delta\left(X\right)=\\{v\in[0,1]^{X}|\sum_{x\in X}v(x)=1\\}$. For
$a\in\mathbb{R}$, we set $[a]_{+}:=\max\\{0,a\\}$ to be the positive part of
$a$. For a vector $b\in\mathbb{R}^{n}$, we write $[b]_{+}$ for the vector
whose entries are the positive parts of the corresponding entries of $b$.
Similarly, for two vectors $a,b\in\mathbb{R}^{n}$, we write $a\leq b$ as a
short-hand for $a_{i}\leq b_{i}$, for all $i\in[n]$. Throughout the paper, we
denote the Euclidean norm by $\|\cdot\|$.

We define a finite-horizon CMDP as a tuple
$\mathcal{M}=(\mathcal{S},\mathcal{A},H,p,c,(d_{i})_{i\in[I]},(\alpha_{i})_{i\in[I]},s_{1})$
with the following components. $\mathcal{S}$ and $\mathcal{A}$ are the state
and action space, respectively, and $H>0$ denotes the horizon. Every episode
consists of $H$ steps and starts from the initial state $s_{1}\in\mathcal{S}$.
At every step $h\in[H]$, $p_{h}(s^{\prime}|s,a)$ denotes the probability of
transitioning to state $s^{\prime}$ if the current state and action are $s$
and $a$. Moreover, $c_{h}\colon\mathcal{S}\times\mathcal{A}\rightarrow[0,1]$
denotes the objective cost function at step $h$. For $i\in[I]$,
$d_{i,h}\colon\mathcal{S}\times\mathcal{A}\rightarrow[0,1]$ refers to the cost
function of the $i$-th constraint at step $h$, and $\alpha_{i}\in[0,H]$
denotes the threshold for the $i$-th constraint. We assume that the state and
action space are both finite, with cardinalities $S$ and $A$, respectively.
Furthermore, we assume that the agent does not know the transition
probabilities, objective costs, or constraint costs beforehand. Whenever the
agent takes an action $a$ in state $s$ at time $h$, it observes costs sampled
from random variables $C_{h}(s,a)\in[0,1]$ and
$(D_{i,h}(s,a))_{i\in[I]}\in[0,1]^{I}$ such that
$\mathbb{E}[C_{h}(s,a)]=c_{h}(s,a)$ and
$\mathbb{E}[D_{i,h}(s,a)]=d_{i,h}(s,a)$, for all $i\in[I]$. The agent
interacts with the CMDP by playing a policy $\pi=(\pi_{h})_{h\in[H]}$, meaning
that if in state $s$ at step $h\in[H]$, the agent samples its next action from
$\pi_{h}(\cdot|s)\in\Delta\left(\mathcal{A}\right)$. For an arbitrary cost
function $l=(l_{h})_{h\in[H]}$ and transition probabilities
$p^{\prime}=(p_{h}^{\prime})_{h\in[H]}$, the expected cumulative cost under
policy $\pi$ is measured by the value function defined as follows:

$\displaystyle V^{\pi}(l,p^{\prime}):=$
$\displaystyle\mathbb{E}\bigg{[}\sum_{h=1}^{H}l_{h}(s_{h},a_{h})\mid
s_{1},\pi,p^{\prime}\bigg{]},$

where $(s_{h},a_{h})$ denotes the state-action pair at step $h$ under
transitions $p^{\prime}$ and policy $\pi$. We fix an optimal solution of the
CMDP, given by a policy $\pi^{*}$, defined as follows:

$\pi^{*}\in\arg\min_{\pi\in\Pi}\leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ V^{\pi}(c,p)\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\text{s.t.}\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ V^{\pi}(d_{i},p)\leq\alpha_{i}\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\ (\forall
i\in[I]).$ (1)

For brevity, we write
$V^{\pi}((l_{i})_{i\in[I]},p^{\prime}):=(V^{\pi}(l_{1},p^{\prime}),\dots,V^{\pi}(l_{I},p^{\prime}))^{T}\in\mathbb{R}^{I}$
in the presence of $I$ different cost functions $l_{i}=(l_{i,h})_{h\in[H]}$
($i\in[I]$), and $\alpha:=(\alpha_{1},\dots,\alpha_{I})^{T}\in\mathbb{R}^{I}$.
Furthermore, we denote by
$\Pi:=\\{\pi=(\pi_{h})_{h\in[H]}|\pi_{h}:\mathcal{S}\rightarrow\Delta\left(\mathcal{A}\right)\\}$
the entire policy space.

Strong duality and dual methods: Altman (1999); Paternain et al. (2019) proved
that CMDPs possess the strong duality property; i.e., given a feasible CMDP
$\mathcal{M}$, the following relation holds:

$V^{\pi^{*}}(c,p)=\underbrace{\min_{\pi\in\Pi}\max_{\lambda\in\mathbb{R}_{+}^{I}}\leavevmode\nobreak\
\mathcal{L}(\pi,\lambda)}_{\text{Primal
problem}}=\underbrace{\max_{\lambda\in\mathbb{R}_{+}^{I}}\min_{\pi\in\Pi}\leavevmode\nobreak\
\mathcal{L}(\pi,\lambda)}_{\text{Dual problem}},$ (2)

where
$\mathcal{L}(\pi,\lambda):=V^{\pi}(c,p)+\lambda^{T}\left(V^{\pi}((d_{i})_{i\in[I]},p)-\alpha\right)$
denotes the Lagrangian. The strong duality property gives theoretical
justification to dual methods (Altman, 1999; Efroni et al., 2020; Paternain et
al., 2019). These methods are popular, as the dual problem can be solved via a
sequence of (extended666If the CMDP is unknown, backward induction involves an
extra optimization step over the possible transitions (Jin et al., 2019).)
unconstrained MDPs, each of which can be solved efficiently via DP (as opposed
to using LPs for solving a sequence of CMDPs, for which the Bellman optimality
principle does not hold).

In this work, we solve the min-max problem in Eq. 2 using the augmented
Lagrangian method. This is beneficial since the analysis of the augmented
Lagrangian method allows for convergence guarantees concerning the last
iterate, and not just the averaged iterates. Since the occurring sub-problems
are not MDPs anymore, we justify in Section 3 how they can still be solved
efficiently by leveraging a Frank-Wolfe scheme and DP. We are now ready to
state the main problem formulation of our work.

Problem formulation: In our setting, the agent interacts with the unknown CMDP
over a fixed number of $K>0$ episodes. In every episode $k\in[K]$, the agent
plays a policy $\pi_{k}\in\Pi$ and its goal is to (simultaneously) minimize
its regrets, defined as follows:

$\displaystyle\mathcal{R}(K;c)$
$\displaystyle:=\sum_{k\in[K]}[V^{\pi_{k}}(c,p)-V^{\pi^{*}}(c,p)]_{+},$
(Objective strong regret) $\displaystyle\mathcal{R}(K;d)$
$\displaystyle:=\max_{i\in[I]}\sum_{k\in[K]}\left[V^{\pi_{k}}(d_{i},p)-\alpha_{i}\right]_{+}.$
(Constraint strong regret)

For simplicity, we will write regret when referring to the strong regret
throughout the paper. As we pointed out, existing works on Lagrangian-based
algorithms (Liu et al., 2021b; Efroni et al., 2020; Bai et al., 2022; Ding et
al., 2022a, b) only prove sublinear guarantees on a weaker notion of regret,
defined as follows:

$\displaystyle\mathcal{R}_{\pm}(K;c)$
$\displaystyle:=\sum_{k\in[K]}(V^{\pi_{k}}(c,p)-V^{\pi^{*}}(c,p)),$ (Objective
weak regret) $\displaystyle\mathcal{R}_{\pm}(K;d)$
$\displaystyle:=\max_{i\in[I]}\sum_{k\in[K]}\left(V^{\pi_{k}}(d_{i},p)-\alpha_{i}\right).$
(Constraint weak regret)

The weak regrets allow for the aforementioned cancellation of errors; i.e.,
even if they are sublinear in $K$, the agent can continue to compensate for a
constraint violation in one episode with a strict constraint satisfaction in
another episode. On the other hand, a sublinear bound on the stronger notion
of regret guarantees that the agent achieves a low constraint violation in
most of the episodes.777Indeed, fix $\epsilon>0$ and suppose
$\mathcal{R}(K;d)\leq\tilde{O}(\sqrt{K})$. Then there exist at most
$\tilde{O}(\sqrt{K}/\epsilon)$ episodes with a constraint violation of at
least $\epsilon$. In other words, only a small fraction
$\tilde{O}(1/(\epsilon\sqrt{K}))$ of the iterates is not $\epsilon$-safe. In
comparison, this is by no means guaranteed by a sublinear bound on
$\mathcal{R}_{\pm}(K;d)$. While this is crucial for practical applications, it
is strictly more challenging to provide a bound for the strong regrets instead
of the weaker notion.

###  3 Algorithm and Main Result

In this section, we introduce our algorithm OptAug-CMDP (see Algorithm 1) and
state its regret guarantees in Theorem 1. In OptAug-CMDP, the agent interacts
with the unknown CMDP over a fixed number of $K>0$ episodes. To encourage
exploration of the CMDP, the agent follows the well-known optimism in the face
of uncertainty principle (Auer et al., 2008) and builds an optimistic estimate
of the CMDP, in every episode $k\in[K]$. That is, in every episode $k\in[K]$,
the agent builds optimistic estimates $\tilde{c}_{k}$ for the objective cost
$c$, optimistic estimates $\tilde{d}_{i,k}$ for the constraint costs $d_{i}$,
and a set of plausible transition probabilities $B_{k}^{p}$, which we specify
in the following paragraph.

Optimistic estimates: Let
$n_{h}^{k-1}(s,a):=\sum_{l=1}^{k-1}\mathbbm{1}_{\\{s_{h}^{l}=s,\leavevmode\nobreak\
a_{h}^{l}=a\\}}$ count the number of times that the state-action pair $(s,a)$
has been visited at step $h$ before episode $k$. Here, ($s_{h}^{l}$,
$a_{h}^{l}$) denotes the state-action pair that was visited at step $h$ in
episode $l$. First, we compute the empirical averages of the cost and
transition probabilities as follows:

$\begin{gathered}\begin{aligned}
\bar{c}_{h}^{k-1}(s,a):=&\frac{\sum_{l=1}^{k-1}C_{h}^{l}(s,a)\mathbbm{1}_{\\{s_{h}^{l}=s,\leavevmode\nobreak\
a_{h}^{l}=a\\}}}{n_{h}^{k-1}(s,a)\vee 1},\\\
\bar{d}_{i,h}^{k-1}(s,a):=&\frac{\sum_{l=1}^{k-1}D_{i,h}^{l}(s,a)\mathbbm{1}_{\\{s_{h}^{l}=s,\leavevmode\nobreak\
a_{h}^{l}=a\\}}}{n_{h}^{k-1}(s,a)\vee 1}\quad(\forall i\in[I]),\\\
\bar{p}_{h}^{k-1}(s^{\prime}|s,a):=&\frac{\sum_{l=1}^{k-1},\mathbbm{1}_{\\{s_{h}^{l}=s,\leavevmode\nobreak\
a_{h}^{l}=a,\leavevmode\nobreak\
s_{h+1}^{l}=s^{\prime}\\}}}{n_{h}^{k-1}(s,a)\vee
1},\end{aligned}\end{gathered}$

where $a\vee b:=\max\\{a,b\\}$. With this, we define the optimistic costs and
the set of plausible transition probabilities as

$\displaystyle\tilde{c}_{k,h}(s,a)$
$\displaystyle:=\bar{c}_{h}^{k-1}(s,a)-\beta^{c}_{k,h}(s,a),$
$\displaystyle\tilde{d}_{i,k,h}(s,a)$
$\displaystyle:=\bar{d}_{i,h}^{k-1}(s,a)-\beta_{i,k,h}^{d}(s,a)\quad(\forall
i\in[I]),$ (3) $\displaystyle B_{k,h}^{p}(s,a)$
$\displaystyle:=\\{\tilde{p}_{h}(\cdot|s,a)\in\Delta\left(\mathcal{S}\right)\mid\forall
s^{\prime}\in\mathcal{S}\colon|\tilde{p}_{h}(s^{\prime}|s,a)-\bar{p}_{h}^{k-1}(s^{\prime}|s,a)|\leq\beta_{k,h}^{p}(s,a,s^{\prime})\\},$
$\displaystyle B_{k}^{p}$ $\displaystyle:=\\{\tilde{p}\mid\forall
s,a,h\colon\tilde{p}_{h}(\cdot|s,a)\in B_{k,h}^{p}(s,a)\\}.$

Here, $\beta^{c}_{k,h}(s,a)=\beta_{i,k,h}^{d}(s,a)>0$ denote the exploration
bonus for the costs and $\beta_{k,h}^{p}(s,a,s^{\prime})>0$ denotes the
confidence threshold for the transitions. For any $\delta\in(0,1)$, we specify
the correct values for those quantities in Section E.1, in order to obtain our
regret guarantees with probability at least $1-\delta$. In the next paragraph,
we describe how the agent computes its policy in episode $k$.

Policy update: Given the optimistic CMDP at episode $k$, we derive the next
policy $\pi_{k}$ using a scheme motivated by the augmented Lagrangian method
(cf. Eqs. 4 and 5). We explain how we can perform the optimization step in Eq.
4 efficiently, up to a specified accuracy $\epsilon_{k}$, at the end of this
section. For now, we treat this part of the algorithm as a black-box
subroutine.

Optimistic exploration alone with the augmented Lagrangian, however, is not
sufficient to obtain sublinear regret guarantees for our algorithm. For
technical reasons, our analysis also requires the optimistic CMDPs with costs
$\tilde{c}_{k}$, $(\tilde{d}_{i,k})_{i\in[I]}$ and transitions
$\tilde{p}_{k}\in B_{k}^{p}$ (cf. Eq. 4) to be strictly feasible, in every
episode $k\in[K]$. Our analysis in Section 4.2 explains the need for this
technical assumption. To address this issue, we propose a pre-training phase
before the optimistic exploration phase, which we describe in the following
paragraph.

Pre-training phase: In this phase, the agent repeatedly executes a fixed
policy $\bar{\pi}$ for $K^{\prime}\leq K$ episodes. The policy $\bar{\pi}$
must be strictly feasible with respect to the true CMDP, which we formally
state in the following assumption.

######  Assumption 1 (Strictly feasible policy).

We have access to a policy $\bar{\pi}$ such that
$V^{\bar{\pi}}(d_{i},p)<\alpha_{i}$ for all $i\in[I]$. Furthermore, we assume
that the slack $\gamma$, defined below, is known888In other words, there is a
Slater point for the constraint set of the true CMDP. Note that knowing a
lower bound instead of the exact slack $\gamma$ is sufficient as well.:

$\displaystyle\gamma:=\min_{i\in[I]}\leavevmode\nobreak\
(\alpha_{i}-V^{\bar{\pi}}(d_{i},p))\in(0,H].$

Note that this is stronger than only assuming the existence of a strictly
feasible policy. However, it is realistic to make this assumption in many
practical setups (Liu et al., 2021b; Bura et al., 2022). For example, in the
case of a race car that should not exceed the boundary of a track, it would be
sufficient to have access to the policy of a car that strictly stays within
the boundaries but may be arbitrarily slow. To address the technical issue
mentioned earlier, we need to set $K^{\prime}$ such that the following
condition holds for some $\nu\in(0,1)$, with high probability:

$\displaystyle
V^{\bar{\pi}}(\tilde{d}_{i,k},\tilde{p}_{k})\leq\alpha_{i}-\nu\gamma\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\ (\forall
i\in[I]\leavevmode\nobreak\ \forall k\in\left\\{K^{\prime},\dots,K\right\\}),$

where $\tilde{p}_{k}$ is defined by the update in Eq. 4.999For $k=K^{\prime}$,
we just take any $\tilde{p}_{K^{\prime}}\in B_{K^{\prime}}^{p}$ In particular,
the fixed policy $\bar{\pi}$ is strictly feasible with respect to the
optimistic CMDP at every episode $k\geq K^{\prime}$. Indeed, if the agent
plays $\bar{\pi}$ for the first $K^{\prime}$ episodes of the algorithm with a
large enough constant $K^{\prime}$, then for all future episodes, the
constraint value function of $\bar{\pi}$ under the estimated model is close to
the constraint value function of $\bar{\pi}$ under the true model. Thus, we
can ensure the above condition. Leveraging an adaption of an on-policy error
bound (see Appendix C), we prove that it is sufficient to set $K^{\prime}$ as
follows:

######  Lemma 1.

Suppose that Assumption 1 holds, i.e., the agent has access to a strictly
feasible $\bar{\pi}$ and its slack $\gamma>0$. Fix any $\nu\in(0,1)$, and
suppose the agent executes $\bar{\pi}$ for

$K^{\prime}=\tilde{O}\left(\max\left\\{\frac{(H\sqrt{\mathcal{N}}+S)SAH}{(1-\nu)\gamma},\frac{\mathcal{N}SAH^{3}}{(1-\nu)^{2}\gamma^{2}}\right\\}\right)$

episodes, where $\mathcal{N}:=\max_{s,a,h}|\\{s^{\prime}\mid
p_{h}(s^{\prime}|s,a)>0\\}|$ denotes the maximum number of transitions. Then,
if the agent updates the optimistic CMDP based on the observations from those
episodes (cf. Eq. 3), with probability at least $1-\delta$ the following
condition is satisfied for every $k\in\left\\{K^{\prime},\dots,K\right\\}$:

$\displaystyle
V^{\bar{\pi}}(\tilde{d}_{i,k},\tilde{p}_{k})\leq\alpha_{i}-\nu\gamma\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\ (\forall
i\in[I]).$

The resulting OptAug-CMDP algorithm is described in Algorithm 1.

0: $K$ (total number of episodes), $K^{\prime}\leq K$ (number of pre-training
episodes), $(\eta_{k})_{k\geq K^{\prime}+1}$ (step sizes),
$(\epsilon_{k})_{k\geq K^{\prime}+1}$ (accuracies), $\bar{\pi}$ (strictly
feasible policy), $\alpha$ (constraint thresholds),
$\lambda_{K^{\prime}+1}:=0\in\mathbb{R}^{I}$

// Phase 1: Pre-training the model

for $k=1,\dots,K^{\prime}$ do

Play policy $\pi_{k}=\bar{\pi}$, update estimates of the costs
$\tilde{c}_{k+1}$, $(\tilde{d}_{i,k+1})_{i\in[I]}$ and transitions
$B_{k+1}^{p}$ (Eq. 3).

// Phase 2: Optimistic exploration with pre-trained model

for $k=K^{\prime}+1,\dots,K$ do

Update policy (by finding $\pi_{k}$, $\tilde{p}_{k}$ such that the objective
is $\epsilon_{k}$-close to the minimum):
$\displaystyle\pi_{k},\tilde{p}_{k}:=\arg\min_{\begin{subarray}{c}\pi\in\Pi\\\
p^{\prime}\in
B_{k}^{p}\end{subarray}}\left(V^{\pi}(\tilde{c}_{k},p^{\prime})+\frac{1}{2\eta_{k}}\|[\lambda_{k}+\eta_{k}(V^{\pi}((\tilde{d}_{i,k})_{i\in[I]},p^{\prime})-\alpha)]_{+}\|^{2}\right)$
(4)

Update dual variables:
$\displaystyle\lambda_{k+1}:=[\lambda_{k}+\eta_{k}(V^{\pi_{k}}((\tilde{d}_{i,k})_{i\in[I]},\tilde{p}_{k})-\alpha)]_{+}$
(5)

Play $\pi_{k}$, update estimates of the costs $\tilde{c}_{k+1}$,
$(\tilde{d}_{i,k+1})_{i\in[I]}$ and transitions $B_{k+1}^{p}$ (Eq. 3).

Algorithm 1 OptAug-CMDP

We are now ready to state the regret guarantees for OptAug-CMDP.

######  Theorem 1.

Suppose that Assumption 1 holds, let $\delta\in(0,1)$ and $\nu>0$. Then there
exist
$K^{\prime}=\tilde{O}\left(\max\left\\{\frac{(H\sqrt{\mathcal{N}}+S)SAH}{(1-\nu)\gamma},\frac{\mathcal{N}SAH^{3}}{(1-\nu)^{2}\gamma^{2}}\right\\}\right)$
and $\eta_{k}$, $\epsilon_{k}$ such that with probability at least $1-\delta$,
OptAug-CMDP achieves a total regret of

$\displaystyle\mathcal{R}(K;c)$
$\displaystyle=\tilde{O}\left(\sqrt{\mathcal{N}SAH^{3}K}+(H\sqrt{\mathcal{N}}+S)SAH+K^{\prime}H\right),$
$\displaystyle\mathcal{R}(K;d)$
$\displaystyle=\tilde{O}\left(\sqrt{\mathcal{N}SAH^{3}K}+(H\sqrt{\mathcal{N}}+S)SAH\right).$

We remark that to achieve this bound, using step sizes
$\eta_{K^{\prime}+k}=\Theta(k^{2.5})$ and accuracies
$\epsilon_{K^{\prime}+k}=\Theta(1/\eta_{K^{\prime}+k})$ (when only
highlighting the dependency on $k$) is sufficient, as we discuss in Section
D.3.

Comparison with OptDual-CMDP: Crucially, our bound holds for the stronger
notion of regret, whereas the one for the related OptDual-CMDP algorithm (see
Section A.2) by Efroni et al. (2020) only concerns the weak regret, which
allows for the cancellation of errors. Apart from this, the bound we obtain is
similar in spirit. However, our regret bound does not depend on the number $I$
of constraints, up to polylogarithmic factors. Moreover, note that we get
slightly different (but not worse) constants and the constant extra term
$K^{\prime}H$ that is due to the model pre-training phase. In addition, it is
important to note that we can choose $\eta_{k}$, $\epsilon_{k}$ in terms of
$\gamma$ (Assumption 1) such that in the leading term of the regret bound,
there is no dependency on $\min_{i\in[I]}(\alpha_{i}-V^{\bar{\pi}}(d_{i},p))$,
as opposed to OptDual-CMDP.

Solving the inner problem: We now elaborate on the subroutine for solving the
optimization problem in Eq. 4 that defines the policy update in Algorithm 1.
Importantly, we can reformulate Eq. 4 as a constrained optimization problem
that is convex in the state-action-state occupancy measure (see Section B.1).
However, the resulting problem is neither an LP nor an extended MDP (due to
the nonlinear objective), which prevents solving it with a single call of a DP
or LP solver. Albeit related, it is not a standard convex RL problem either
(due to the additional optimization over the constraint set $B_{k}^{p}$).
Moreover, computing projections onto the high-dimensional domain is
prohibitive in practice, making it impossible to simply run projected gradient
descent.

The projection-free method we propose in Section B.2 overcomes this difficulty
by combining a Frank-Wolfe scheme with DP in a sequence of (extended) MDPs. In
every iteration of this inner method, we consider the linear minimization step
needed for a Frank-Wolfe iteration. When switching back to an optimization
over $\Pi$ and $B_{k}^{p}$, we can then perform this minimization step by
solving an extended but unconstrained MDP via DP.101010Formally, this is
because a version of the Bellman optimality principle applies after dualizing
the constraints, even if we need to optimize over the confidence intervals for
the transitions during backward induction. The smoothness properties of the
objective of Eq. 4 then determine the iteration complexity of the Frank-Wolfe
scheme. Formally, we have the following.

######  Proposition 1.

In episode $k$, fix any accuracy of $\epsilon_{k}>0$. There exists an
algorithm for solving Eq. 4 such that the objective at its output
$(\pi_{k},\tilde{p}_{k})$ is $\epsilon_{k}$-close to the optimum of Eq. 4, by
solving $O\left(\frac{\eta_{k}IS^{2}AH}{\epsilon_{k}}\right)$ (extended) MDPs
via DP.

###  4 Sketch of the Regret Analysis

In this section, we outline the key steps in our proof of Theorem 1 and defer
the detailed proofs to Appendix E. We will condition our regret analysis on a
success event $G$, which we formally define in Section E.1. $G$ ensures that
(a) the optimistic cost estimates in Eq. 3 are in fact optimistic and (b) the
true transitions are contained in the set of plausible models from Eq. 3,
i.e.:

$\displaystyle\tilde{c}_{k}\leq c,\quad\tilde{d}_{i,k}\leq d_{i}\;(\forall
i\in[I]),\quad p\in B_{k}^{p},$

for every episode $k\in[K]$. In the following lemma, we prove that $G$ occurs
with high probability.

######  Lemma 2.

Fix $\delta\in(0,1)$ and define the optimistic model in Eq. 3 accordingly.
Then the success event $G$ occurs with probability at least $1-\delta$, i.e.,
$P[G]\geq 1-\delta$.

We proceed with the regret analysis and first split the regrets between the
two phases of the algorithm:

$\displaystyle\mathcal{R}(K;c)$
$\displaystyle=\underbrace{\sum_{k=1}^{K^{\prime}}[V^{\pi_{k}}(c,p)-V^{\pi^{*}}(c,p)]_{+}}_{\text{Pre-
Training}}+\underbrace{\sum_{k=K^{\prime}+1}^{K}[V^{\pi_{k}}(c,p)-V^{\pi^{*}}(c,p)]_{+}}_{\text{Optimistic
Exploration}},$ $\displaystyle\mathcal{R}(K;d)$
$\displaystyle\leq\underbrace{\max_{i\in[I]}\sum_{k=1}^{K^{\prime}}[V^{\pi_{k}}(d_{i},p)-\alpha_{i}]_{+}}_{\text{Pre-
Training}}+\underbrace{\max_{i\in[I]}\sum_{k=K^{\prime}+1}^{K}[V^{\pi_{k}}(d_{i},p)-\alpha_{i}]_{+}}_{\text{Optimistic
Exploration}}.$

Then, applying Lemma 1, we can trivially bound the objective regret during the
pre-training phase by $K^{\prime}H$. Since $\bar{\pi}$ is strictly feasible,
there is no constraint regret during pre-training. We now focus on the regrets
incurred in the optimistic exploration phase. For this, we further decompose
the regrets as follows (see Section E.1):

$\displaystyle\mathcal{R}(K;c)$ $\displaystyle\leq
K^{\prime}H{+}\underbrace{\sum_{k=K^{\prime}+1}^{K}[V^{\pi_{k}}(c,p){-}V^{\pi_{k}}(\tilde{c}_{k},\tilde{p}_{k})]_{+}}_{\text{Estimation
Error}}{+}\underbrace{\sum_{k=K^{\prime}+1}^{K}[V^{\pi_{k}}(\tilde{c}_{k},\tilde{p}_{k}){-}V^{\pi^{*}}(c,p)]_{+}}_{\text{Optimization
Error}},$ $\displaystyle\mathcal{R}(K;d)$
$\displaystyle\leq\underbrace{\max_{i\in[I]}\sum_{k=K^{\prime}+1}^{K}[V^{\pi_{k}}(d_{i},p){-}V^{\pi_{k}}(\tilde{d}_{i,k},\tilde{p}_{k})]_{+}}_{\text{Estimation
Error}}{+}\underbrace{\max_{i\in[I]}\sum_{k=K^{\prime}+1}^{K}[V^{\pi_{k}}(\tilde{d}_{i,k},\tilde{p}_{k}){-}\alpha_{i}]_{+}}_{\text{Optimization
Error}}.$

We have thus decomposed the regrets into

  1. (A)

estimation errors that are due to the estimated model, and

  2. (B)

optimization errors that we can analyze via the underlying optimization
method.

Conditioning on the success event $G$, we will obtain bounds sublinear in $K$
for both parts of the decomposition. Note that we cannot adapt the analysis by
Efroni et al. (2020) to achieve this goal, since it only allows for bounds on
the averages of the signed optimization errors. We proceed with bounding the
estimation errors in the next section.

####  4.1 Estimation Errors (Optimistic Exploration)

Leveraging on-policy error bounds for optimistic exploration in MDPs (Appendix
C), we establish the desired bound on the estimation errors.

######  Lemma 3 (Estimation errors).

Let $(\pi_{k})_{k=K^{\prime}+1}^{K}$ be the sequence of policies obtained by
OptAug-CMDP. Then, conditioned on $G$, we can bound the estimation errors as
follows:

$\displaystyle\sum_{k=K^{\prime}+1}^{K}[V^{\pi_{k}}(c,p)-V^{\pi_{k}}(\tilde{c}_{k},\tilde{p}_{k})]_{+}\leq$
$\displaystyle\tilde{O}\left(\sqrt{\mathcal{N}SAH^{3}K}+(H\sqrt{\mathcal{N}}+S)SAH\right),$
$\displaystyle\max_{i\in[I]}\sum_{k=K^{\prime}+1}^{K}[V^{\pi_{k}}(d_{i},p)-V^{\pi_{k}}(\tilde{d}_{i,k},\tilde{p}_{k})]_{+}\leq$
$\displaystyle\tilde{O}\left(\sqrt{\mathcal{N}SAH^{3}K}+(H\sqrt{\mathcal{N}}+S)SAH\right).$

We refer to Section E.2 for the proof. Lemma 3 proves that the estimation
errors for both the objective and constraints can indeed be bounded by a term
that is sublinear in $K$. In the next section, we provide a bound for the
optimization errors.

####  4.2 Optimization Errors (Optimistic Exploration)

Recall that by Proposition 1, our solver for the inner problem (Eq. 4) has the
following guarantee, for every episode $k\geq K^{\prime}+1$:

$\displaystyle\mathcal{L}_{k}(\pi_{k},\tilde{p}_{k})$
$\displaystyle\leq\min_{\begin{subarray}{c}\pi\in\Pi\\\ p^{\prime}\in
B_{k}^{p}\end{subarray}}\mathcal{L}_{k}(\pi,p^{\prime})+\epsilon_{k},$

where
$\mathcal{L}_{k}(\pi,p^{\prime}):=V^{\pi}(\tilde{c}_{k},p^{\prime})+\frac{1}{2\eta_{k}}\|[\lambda_{k}+\eta_{k}(V^{\pi}((\tilde{d}_{i,k})_{i\in[I]},p^{\prime})-\alpha)]_{+}\|^{2}$
denotes the objective at episode $k$. If the true CMDP is known, i.e., no
exploration is required, then Xu (2021) proves a sublinear regret bound for
the optimization error if the step sizes $\eta_{k}$ and accuracies
$\epsilon_{k}$ are chosen suitably.111111That is, such that
$\sum_{k=K^{\prime}+1}^{K}1/\eta_{k}=o(K)$ and
$\sum_{k=K^{\prime}+1}^{K}\epsilon_{k}=o(K)$, see Xu (2021, Remark 7). They
obtain this result by bounding the dual variables $\lambda_{k}$ across the
iterations $k$. In our setting, however, since the objective and constraint
set of the optimization problem (Eq. 4) change in every episode, we require a
novel type of analysis.

As a first step, we show that we can bound the optimization errors in episode
$k$ by expressions that depend on the dual variables $\lambda_{k}$ and
$\lambda_{k+1}$.

######  Lemma 4.

Conditioned on G, for each $k\in\\{K^{\prime}+1,\dots,K\\}$, in OptAug-CMDP we
have

$\displaystyle V^{\pi_{k}}(\tilde{c}_{k},\tilde{p}_{k})-V^{\pi^{*}}(c,p)$
$\displaystyle\leq\epsilon_{k}+\frac{\|\lambda_{k}\|^{2}-\|\lambda_{k+1}\|^{2}}{2\eta_{k}},$
$\displaystyle V^{\pi_{k}}(\tilde{d}_{i,k},\tilde{p}_{k})-\alpha_{i}$
$\displaystyle\leq\frac{\lambda_{k+1}(i)-\lambda_{k}(i)}{\eta_{k}}\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\ (\forall
i\in[I]).$

To further bound the norm of the dual iterates, for each episode $k\geq
K^{\prime}$ we consider the $k$-th optimistic CMDP, which we define as
follows:

$\displaystyle\min_{\begin{subarray}{c}\pi\in\Pi\end{subarray}}\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
V^{\pi}(\tilde{c}_{k},\tilde{p}_{k})\leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \text{s.t.}\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
V^{\pi}(\tilde{d}_{i,k},\tilde{p}_{k})\leq\alpha_{i}\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\ (\forall
i\in[I]).$ (6)

Note that Eq. 6 indeed is a CMDP. By Lemma 1, $\bar{\pi}$ is strictly feasible
for Eq. 6 for all $k\geq K^{\prime}$, with a slack of $\geq\nu\gamma$
uniformly bounded away from zero. By strong duality (Paternain et al., 2019),
there exist primal-dual pairs $(\pi_{k}^{*},\lambda_{k}^{*})$ satisfying

$V^{\pi_{k}^{*}}(\tilde{c}_{k},\tilde{p}_{k})=\min_{\begin{subarray}{c}\pi\in\Pi\end{subarray}}\left(V^{\pi}(\tilde{c}_{k},\tilde{p}_{k})+(\lambda_{k}^{*})^{T}(V^{\pi}((\tilde{d}_{i,k})_{i\in[I]},\tilde{p}_{k})-\alpha)\right).$

We formalize this with Lemma 18 in Section E.3.2, by using the fact that we
can formulate Eq. 6 as a convex optimization problem using the LP formulation
of CMDPs (Sections A.3 and A.4). With this, we can establish the following
bound on the dual iterates.

######  Lemma 5.

Let $k\in\\{K^{\prime}+1,\dots,K\\}$ and suppose Eq. 6 is strictly feasible
for every $k^{\prime}\in\\{K^{\prime},\dots,K\\}$. Let
$(\pi_{k^{\prime}}^{*},\lambda_{k^{\prime}}^{*})$ be pairs of primal-optimal
and dual-optimal solutions for Eq. 6. Then the iterates of OptAug-CMDP satisfy

$\displaystyle\|\lambda_{k+1}\|\leq$ $\displaystyle\leavevmode\nobreak\
2\sum_{t=K^{\prime}}^{k}\|\lambda_{t}^{*}\|+\sum_{t=K^{\prime}+1}^{k}\sqrt{2\eta_{t}\epsilon_{t}}.$

Having achieved a bound on the dual iterates $\lambda_{k+1}$ in terms of the
dual maximizers $\lambda_{k^{\prime}}^{*}$
(${k^{\prime}}\in\\{K^{\prime},\dots,k\\}$), we can now aim to provide bounds
for the latter. Indeed, we can leverage results from constrained convex
optimization (Section A.4) to arrive at the following lemma.

######  Lemma 6.

Suppose Assumption 1 holds. Let $\nu\in(0,1)$ and choose $K^{\prime}$ as in
Lemma 1. Let $k\in\\{K^{\prime},\dots,K\\}$, and let
$(\pi_{k}^{*},\lambda_{k}^{*})$ be a pair of primal-optimal and dual-optimal
solutions for Eq. 6. Then, conditioned on $G$, we have

$\displaystyle\|\lambda_{k}^{*}\|\leq\|\lambda_{k}^{*}\|_{1}\leq\frac{H}{\nu\gamma}.$

Plugging Lemma 5 into the bounds from Lemma 4 and replacing the norms of the
$\lambda^{*}_{k}$ using the bound from Lemma 6, we obtain sublinear
optimization errors when choosing $\eta_{k}$, $\epsilon_{k}$ correctly:

######  Lemma 7 (Optimization errors).

Suppose Assumption 1 holds. Let $\nu\in(0,1)$ and choose $K^{\prime}$ as in
Lemma 1. Suppose that the event $G$ occurs. When using step sizes
$\eta_{K^{\prime}+k}=\Theta(k^{2.5})$ and
$\epsilon_{K^{\prime}+k}=\Theta(1/\eta_{K^{\prime}+k})$, we have

$\displaystyle\sum_{k=K^{\prime}+1}^{K}[V^{\pi_{k}}(\tilde{c}_{k},\tilde{p}_{k})-V^{\pi^{*}}(c,p)]_{+}\leq$
$\displaystyle\sum_{k=K^{\prime}+1}^{K}\bigg{(}\frac{(O(\sigma
k)+\sum_{t=K^{\prime}+1}^{k}\sqrt{2\eta_{t}\epsilon_{t}})^{2}}{2\eta_{k}}+\epsilon_{k}\bigg{)}\leq
O(\sqrt{K}),$
$\displaystyle\max_{i\in[I]}\sum_{k=K^{\prime}+1}^{K}[V^{\pi_{k}}(\tilde{d}_{i,k},\tilde{p}_{k})-\alpha_{i}]_{+}\leq$
$\displaystyle\sum_{k=K^{\prime}+1}^{K}\frac{O(\sigma
k)+\sum_{t=K^{\prime}+1}^{k}\sqrt{2\eta_{t}\epsilon_{k}}}{\eta_{k}}\leq
O(\sqrt{K}),$

where $\sigma=\frac{H}{\nu\gamma}$ and in fact $O(\sigma k)$ can be replaced
by $(2+2(k-K^{\prime}))\sigma$.

Remark: We need to choose $\eta_{k}$ large enough (increasing) and
$\epsilon_{k}$ small enough (decreasing) to ensure a sublinear error bound. At
the same time, we do not want to choose $\eta_{k}$ larger than necessary or
$\epsilon_{k}$ smaller than necessary for computational reasons (see
Proposition 1). We refer to Section D.3 for a discussion. In the case of an
exact subroutine, we can plug in $\epsilon_{k}=0$ to achieve an analogous
result.

According to our regret decomposition, by adding up the errors of the pre-
training phase, the estimation errors in the second phase, and the
optimization errors in the second phase, we can indeed deduce our main result
(Theorem 1). We showed how to bound the estimation errors using the optimism
paradigm (Lemma 3). For the analysis of the optimization errors, we had to
generalize the convergence analysis of the inexact augmented Lagrangian method
(Lemma 7). We showed that if we have access to a safe baseline policy, the
pre-training phase guarantees all assumptions required for this, and adds a
constant term to the regret (Lemma 1).

###  5 Conclusion

In this work, we showed how to overcome the problem of the cancellation of
errors, i.e., the oscillation of standard Lagrangian-based algorithms for
CMDPs around an optimal safe policy. We did so by leveraging the augmented
Lagrangian method to design an algorithm OptAug-CMDP. Unlike the related
OptDual-CMDP algorithm of Efroni et al. (2020), this requires a subroutine
that solves a non-linear optimization problem in each episode. We devised an
efficient algorithm for this, avoiding projections or LP. We then provided a
regret analysis that, unlike previous works, does not require the cancellation
of errors to arrive at sublinear regret guarantees. This means that in
contrast to existing Lagrangian-based algorithms, our algorithm is provably
safe while exploring the unknown CMDP.

This first partial answer to the open problem posed by Efroni et al. (2020)
leads to several further questions: Can we obtain tighter bounds for the inner
sub-routine and the regret, as our problem has a richer structure than the
general convex optimization setup? While OptAug-CMDP enjoys stronger regret
guarantees, the proposed inner subroutine has a higher computational cost than
the one in OptDual-CMDP, which may be possible to improve. Moreover, it
remains open whether one can remove the requirement of access to a strictly
feasible policy. Finally, we aim to extend our approach to the more practical
function approximation setup.

### References

  * Abernethy and Wang (2017) Jacob D Abernethy and Jun-Kun Wang.  On frank-wolfe and equilibrium computation.  _Advances in Neural Information Processing Systems_ , 30, 2017.
  * Altman (1999) Eitan Altman.  _Constrained Markov decision processes_ , volume 7.  CRC press, 1999.
  * Auer et al. (2008) Peter Auer, Thomas Jaksch, and Ronald Ortner.  Near-optimal regret bounds for reinforcement learning.  _Advances in neural information processing systems_ , 21, 2008.
  * Bai et al. (2022) 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_ , volume 36, pages 3682–3689, 2022.
  * Beck (2017) Amir Beck.  _First-order methods in optimization_.  SIAM, 2017.
  * Bellman (1957) Richard Bellman.  A markovian decision process.  _Journal of Mathematics and Mechanics_ , 6(5):679–684, 1957.  ISSN 00959057, 19435274.  URL http://www.jstor.org/stable/24900506.
  * Bertsekas et al. (2003) Dimitri Bertsekas, Angelia Nedic, and Asuman Ozdaglar.  _Convex analysis and optimization_ , volume 1.  Athena Scientific, 2003.
  * Bertsekas (2014) Dimitri P Bertsekas.  _Constrained optimization and Lagrange multiplier methods_.  Academic press, 2014.
  * Borkar (1988) Vivek S. Borkar.  A convex analytic approach to markov decision processes.  _Probability Theory and Related Fields_ , 1988.
  * Bura et al. (2022) Archana Bura, Aria HasanzadeZonuzy, Dileep Kalathil, Srinivas Shakkottai, and Jean-Francois Chamberland.  Dope: Doubly optimistic and pessimistic exploration for safe reinforcement learning.  _Advances in Neural Information Processing Systems_ , 35:1047–1059, 2022.
  * Dann et al. (2017) Christoph Dann, Tor Lattimore, and Emma Brunskill.  Unifying pac and regret: Uniform pac bounds for episodic reinforcement learning.  _Advances in Neural Information Processing Systems_ , 30, 2017.
  * Ding et al. (2020) Dongsheng Ding, Kaiqing Zhang, Tamer Basar, and Mihailo Jovanovic.  Natural policy gradient primal-dual method for constrained markov decision processes.  _Advances in Neural Information Processing Systems_ , 33:8378–8390, 2020.
  * Ding et al. (2022a) Dongsheng Ding, Kaiqing Zhang, Tamer Başar, and Mihailo R Jovanović.  Convergence and optimality of policy gradient primal-dual method for constrained markov decision processes.  In _2022 American Control Conference (ACC)_ , pages 2851–2856. IEEE, 2022a.
  * Ding et al. (2022b) Dongsheng Ding, Kaiqing Zhang, Jiali Duan, Tamer Başar, and Mihailo R Jovanović.  Convergence and sample complexity of natural policy gradient primal-dual methods for constrained mdps.  _arXiv preprint arXiv:2206.02346_ , 2022b.
  * Efroni et al. (2019) Yonathan Efroni, Nadav Merlis, Mohammad Ghavamzadeh, and Shie Mannor.  Tight regret bounds for model-based reinforcement learning with greedy policies.  _Advances in Neural Information Processing Systems_ , 32, 2019.
  * Efroni et al. (2020) Yonathan Efroni, Shie Mannor, and Matteo Pirotta.  Exploration-exploitation in constrained mdps.  _arXiv preprint arXiv:2003.02189_ , 2020.
  * Frank and Wolfe (1956) Marguerite Frank and Philip Wolfe.  An algorithm for quadratic programming.  _Naval research logistics quarterly_ , 3(1-2):95–110, 1956.
  * Geist et al. (2021) Matthieu Geist, Julien Pérolat, Mathieu Laurière, Romuald Elie, Sarah Perrin, Olivier Bachem, Rémi Munos, and Olivier Pietquin.  Concave utility reinforcement learning: the mean-field game viewpoint.  _arXiv preprint arXiv:2106.03787_ , 2021.
  * Hazan et al. (2019) Elad Hazan, Sham Kakade, Karan Singh, and Abby Van Soest.  Provably efficient maximum entropy exploration.  In _International Conference on Machine Learning_ , pages 2681–2691. PMLR, 2019.
  * Hestenes (1969) Magnus R Hestenes.  Multiplier and gradient methods.  _Journal of optimization theory and applications_ , 4(5):303–320, 1969.
  * Jaggi (2013) Martin Jaggi.  Revisiting frank-wolfe: Projection-free sparse convex optimization.  In _International conference on machine learning_ , pages 427–435. PMLR, 2013.
  * Jin et al. (2019) Chi Jin, Tiancheng Jin, Haipeng Luo, Suvrit Sra, and Tiancheng Yu.  Learning adversarial mdps with bandit feedback and unknown transition.  _arXiv preprint arXiv:1912.01192_ , 2019.
  * Krishnamurthy (2003) Vikram Krishnamurthy.  _Self Learning Control of Constrained Markov Decision Processes: a Gradient Approach_.  Groupe d’études et de recherche en analyse des décisions, 2003\.
  * Krishnamurthy and Abad (2012) Vikram Krishnamurthy and Felisa J Vázquez Abad.  Gradient based policy optimization of constrained markov decision processes.  In _Stochastic Processes, Finance and Control: A Festschrift in Honor of Robert J Elliott_ , pages 503–547. World Scientific, 2012.
  * Krishnamurthy and Abad (2011) Vikram Krishnamurthy and Felisa Vazquez Abad.  Real-time reinforcement learning of constrained markov decision processes with weak derivatives.  _arXiv preprint arXiv:1110.4946_ , 2011.
  * Li et al. (2021a) Jingqi Li, David Fridovich-Keil, Somayeh Sojoudi, and Claire J Tomlin.  Augmented lagrangian method for instantaneously constrained reinforcement learning problems.  In _2021 60th IEEE Conference on Decision and Control (CDC)_ , pages 2982–2989. IEEE, 2021a.
  * Li et al. (2021b) Tianjiao Li, Ziwei Guan, Shaofeng Zou, Tengyu Xu, Yingbin Liang, and Guanghui Lan.  Faster algorithm and sharper analysis for constrained markov decision process.  _arXiv preprint arXiv:2110.10351_ , 2021b.
  * Liu et al. (2021a) Tao Liu, Ruida Zhou, Dileep Kalathil, P. R. Kumar, and Chao Tian.  Policy optimization for constrained mdps with provable fast global convergence, 2021a.  URL https://arxiv.org/abs/2111.00552.
  * Liu et al. (2021b) Tao Liu, Ruida Zhou, Dileep Kalathil, Panganamala Kumar, and Chao Tian.  Learning policies with zero or bounded constraint violation for constrained mdps.  _Advances in Neural Information Processing Systems_ , 34:17183–17193, 2021b.
  * Lu (2022) Songtao Lu.  A single-loop gradient descent and perturbed ascent algorithm for nonconvex functional constrained optimization.  In _International Conference on Machine Learning_ , pages 14315–14357. PMLR, 2022.
  * Moskovitz et al. (2023) Ted Moskovitz, Brendan O’Donoghue, Vivek Veeriah, Sebastian Flennerhag, Satinder Singh, and Tom Zahavy.  Reload: Reinforcement learning with optimistic ascent-descent for last-iterate convergence in constrained mdps.  _arXiv preprint arXiv:2302.01275_ , 2023.
  * Mutny et al. (2023) Mojmir Mutny, Tadeusz Janik, and Andreas Krause.  Active exploration via experiment design in markov chains.  In _International Conference on Artificial Intelligence and Statistics_ , pages 7349–7374. PMLR, 2023.
  * Paternain et al. (2019) Santiago Paternain, Luiz FO Chamon, Miguel Calvo-Fullana, and Alejandro Ribeiro.  Constrained reinforcement learning has zero duality gap.  _arXiv preprint arXiv:1910.13393_ , 2019.
  * Powell (1969) M. J. D. Powell.  A method for nonlinear constraints in minimization problems.  1969\.
  * Rockafellar (1976) R Tyrrell Rockafellar.  Augmented lagrangians and applications of the proximal point algorithm in convex programming.  _Mathematics of operations research_ , 1(2):97–116, 1976.
  * Rosenberg and Mansour (2019) Aviv Rosenberg and Yishay Mansour.  Online convex optimization in adversarial markov decision processes.  In _International Conference on Machine Learning_ , pages 5478–5486. PMLR, 2019.
  * Stooke et al. (2020) Adam Stooke, Joshua Achiam, and Pieter Abbeel.  Responsive safety in reinforcement learning by pid lagrangian methods.  In _International Conference on Machine Learning_ , pages 9133–9143. PMLR, 2020.
  * Sutton and Barto (2018) Richard S Sutton and Andrew G Barto.  _Reinforcement learning: An introduction_.  MIT press, 2018.
  * Tarbouriech and Lazaric (2019) Jean Tarbouriech and Alessandro Lazaric.  Active exploration in markov decision processes.  In _The 22nd International Conference on Artificial Intelligence and Statistics_ , pages 974–982. PMLR, 2019.
  * Tarbouriech et al. (2020) Jean Tarbouriech, Shubhanshu Shekhar, Matteo Pirotta, Mohammad Ghavamzadeh, and Alessandro Lazaric.  Active model estimation in markov decision processes.  In _Conference on Uncertainty in Artificial Intelligence_ , pages 1019–1028. PMLR, 2020.
  * Xu (2021) Yangyang Xu.  Iteration complexity of inexact augmented lagrangian methods for constrained convex programming.  _Mathematical Programming_ , 185(1):199–244, 2021\.
  * Yan and He (2020) Shen Yan and Niao He.  Bregman augmented lagrangian method and its acceleration.  _Journal of Environmental Sciences (China) English Ed_ , 2020.
  * Ying et al. (2022) Donghao Ying, Yuhao Ding, and Javad Lavaei.  A dual approach to constrained markov decision processes with entropy regularization.  In _International Conference on Artificial Intelligence and Statistics_ , pages 1887–1909. PMLR, 2022.
  * Zahavy et al. (2021) Tom Zahavy, Brendan O’Donoghue, Guillaume Desjardins, and Satinder Singh.  Reward is enough for convex mdps.  _Advances in Neural Information Processing Systems_ , 34:25746–25759, 2021.
  * Zanette and Brunskill (2019) Andrea Zanette and Emma Brunskill.  Tighter problem-dependent regret bounds in reinforcement learning without domain knowledge using value function bounds.  In _International Conference on Machine Learning_ , pages 7304–7312. PMLR, 2019.

## Appendix

###  Appendix A Background

####  A.1 Review of the Augmented Lagrangian Method

In this section, we review the fundamentals of the augmented Lagrangian method
(Rockafellar, 1976; Bertsekas, 2014), which was first introduced by Hestenes
(1969); Powell (1969). Our review is partly inspired by the review by Yan and
He (2020).

Consider a closed and convex set $\mathcal{X}\subset\mathbb{R}^{n}$ and a
closed convex function $f\colon\mathcal{X}\to\mathbb{R}$. Furthermore, let
$A\in\mathbb{R}^{m\times n}$ and $b\in\mathbb{R}^{m}$. With this, consider the
constrained problem

$\displaystyle\min_{x\in\mathcal{X}}$ $\displaystyle\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ f(x)$ (7) s.t.
$\displaystyle\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
Ax\leq b.$

After initializing $x_{0}\in\mathcal{X}$ and $\lambda_{0}\in\mathbb{R}_{\geq
0}^{m}$, the augmented Lagrangian method performs the following updates in
step $k\geq 0$

$\displaystyle x_{k+1}\in$
$\displaystyle\arg\min_{x\in\mathcal{X}}\left(f(x)+\frac{1}{2\eta_{k}}\|[\lambda_{k}+\eta_{k}(Ax-b)]_{+}\|^{2}\right),$
(8) $\displaystyle\lambda_{k+1}=$
$\displaystyle[\lambda_{k}+\eta_{k}(Ax_{k+1}-b)]_{+}.$ (9)

It can easily be verified that the augmented Lagrangian method is the proximal
point method applied to the Lagrangian dual. Thus, with the Lagrangian
$\mathcal{L}(x,\lambda):=f(x)+\lambda^{T}(Ax-b)$, we have

$\displaystyle(x_{k+1},\lambda_{k+1})\in\arg\max_{\lambda\geq
0}\min_{x\in\mathcal{X}}\left(\mathcal{L}(x,\lambda)-\frac{1}{2\eta_{k}}\|\lambda-\lambda_{k}\|^{2}\right).$

Xu (2021) shows a non-asymptotic convergence result for the augmented
Lagrangian method, including the case of an inexact subroutine for solving Eq.
8. Notably, the convergence result is concerning the last iterate of the
method. That is, if $f^{*}$ is the optimal value of Eq. 7, then $f(x_{k})\to
f^{*}$ as $k\to\infty$, and the convergence rate is determined by the step
sizes $\eta_{k}$ (and, in the case of an inexact subroutine, by the accuracy
parameter $\epsilon_{k}$).

Alternatively, we could apply the dual projected gradient method to Eq. 7. The
updates would then read

$\displaystyle\tilde{x}_{k+1}\in$
$\displaystyle\arg\min_{x\in\mathcal{X}}\left(f(x)+\tilde{\lambda}_{k}^{T}(Ax-b)\right),$
(10) $\displaystyle\tilde{\lambda}_{k+1}=$
$\displaystyle[\tilde{\lambda}_{k}+\tilde{\eta}_{k}(A\tilde{x}_{k+1}-b)]_{+}.$
(11)

While Eq. 11 coincides with Eq. 9, the update of the primal variable differs
from the one in the augmented Lagrangian method. We can view the dual
projected gradient method as iterative play between a primal player $x_{k}$
and a dual player $\lambda_{k}$ in a min-max setup, where the objective is the
Lagrangian $\mathcal{L}(x,\lambda)$. The primal player here plays best
response, while the dual player plays online projected gradient ascent. While
this is similar in spirit to applying the proximal point method to the
Lagrangian dual, the known non-asymptotic convergence guarantees for this
method are ergodic, i.e., they only concern convergence of the averaged
iterates. Indeed, simple simulations show that this is not a weakness in the
analysis, but that indeed the primal and dual iterates oscillate around an
optimal solution pair. This is illustrated in (Beck, 2017, Chapter 8). The
iterates of the dual projected gradient method may alternate between
satisfying $f(x_{k})>f^{*}$ and $Ax_{k}<b$ for a couple of iterations and then
$f(x_{k})<f^{*}$ and $Ax_{k}>b$ for a couple of iterations. While the average
objective value converges to $f^{*}$ and the average constraint violation to
$0$, this is not the case for the individual iterates. Note that these
oscillations are not due to estimating the problem, but are present even if
the optimization problem is fixed, as in the setup above. Apart from the
augmented Lagrangian method, other methods such as extra gradient or
optimistic gradient descent-ascent offer solutions to this issue.

####  A.2 Review of OptDual-CMDP

In this section, we review the related OptDual-CMDP algorithm of Efroni et al.
(2020). This model-based dual algorithm is based on the dual projected
gradient method (see Section A.1) rather than on the augmented Lagrangian
method (but builds the model with the same notion of optimism).

Dual approaches like OptDual-CMDP (Algorithm 2) turn the CMDP into a series of
linearly regularized, (extended) unconstrained MDPs (here with objective
$V^{\pi}(\tilde{c}_{k},p^{\prime})+\eta_{k}\lambda_{k}^{T}(V^{\pi}((\tilde{d}_{i,k})_{i\in[I]},p^{\prime})-\alpha)$),
that can be solved efficiently with DP. With the augmented Lagrangian
approach, the inner problem (Eq. 4) has a more complicated structure. In
Appendix B, we show that the inner problem can be reformulated as a convex
optimization problem and provide an efficient method based on Frank-Wolfe and
DP to solve it.

Set $\eta_{k}:=\sqrt{\frac{\rho^{2}}{H^{2}IK}}$ and
$\lambda_{1}:=0\in\mathbb{R}^{I}$

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

Update policy:
$\displaystyle\pi_{k},\tilde{p}_{k}:=\arg\min_{\begin{subarray}{c}\pi\in\Pi\\\
p^{\prime}\in
B_{k}^{p}\end{subarray}}\left(V^{\pi}(\tilde{c}_{k},p^{\prime})+\lambda_{k}^{T}(V^{\pi}((\tilde{d}_{i,k})_{i\in[I]},p^{\prime})-\alpha)\right)$
(12)

Update dual variables:
$\displaystyle\lambda_{k+1}:=[\lambda_{k}+\eta_{k}(V^{\pi_{k}}((\tilde{d}_{i,k})_{i\in[I]},\tilde{p}_{k})-\alpha)]_{+}$
(13)

Play $\pi_{k}$, update estimates of the costs $\tilde{c}_{k+1}$,
$(\tilde{d}_{i,k+1})_{i\in[I]}$ and transitions $B_{k+1}^{p}$ (Eq. 3).

Algorithm 2 OptDual-CMDP

For OptDual-CMDP, we have the following guarantee (Efroni et al., 2020,
Theorem 5).

######  Theorem 2.

Suppose there exists a strictly feasible policy $\pi$ such that for all
$i\in[I]$ we have $V^{\pi}(d_{i},p)<\alpha_{i}$. Set

$\displaystyle\rho:=\frac{V^{\pi}(c,p)-V^{\pi^{*}}(c,p)}{\min_{i\in[I]}(\alpha_{i}-V^{\pi}(d_{i},p))}.$

Then, for any $\delta\in(0,1)$, with probability at least $1-\delta$, OptDual-
CMDP achieves the following regret bounds:

$\displaystyle\mathcal{R}_{\pm}(K;c)$
$\displaystyle=\tilde{O}\bigg{(}\sqrt{S\mathcal{N}H^{4}K}+\rho\sqrt{H^{2}IK}+(\sqrt{\mathcal{N}}+H)H^{2}SA\bigg{)},$
$\displaystyle\mathcal{R}_{\pm}(K;d)$
$\displaystyle=\tilde{O}\bigg{(}(1+\frac{1}{\rho})(\sqrt{IS\mathcal{N}H^{4}K}+(H\sqrt{\mathcal{N}}+S)\sqrt{I}H^{2}SA)\bigg{)}.$

######  Remark 1.

Notably, this bound only covers the weak regret. This is because the dual
projected gradient method does not allow for a non-ergodic convergence
analysis, and their iterates will generally oscillate around an optimal
feasible solution.

It is worth mentioning that unlike LP-based approaches (OptCMDP and OptCMDP-
bonus of Efroni et al. (2020)), the related primal-dual method OptPrimalDual-
CMDP of Efroni et al. (2020) suffers from the same problem as OptDual-CMDP.

Moreover, we remark that this is not just a hypothetical issue, but that
indeed Lagrangian-based algorithms suffer from the mentioned oscillations in
practical applications (Stooke et al., 2020; Moskovitz et al., 2023).

####  A.3 CMDPs and Occupancy Measures

We summarize the relevant quantities of the CMDP $\mathcal{M}$ as follows.

Discrete state space |  $\mathcal{S}$, with cardinality $S$
---|---
Discrete action space |  $\mathcal{A}$, with cardinality $A$
# of constraints | $I$
Initial state |  $s_{1}$, same for each episode
Time horizon |  $H$, same for each episode
Transition probability | $P[s_{h+1}=s^{\prime}\mid s_{h}=s,a_{h}=a]=p_{h}(s^{\prime}|s,a)$
Max. # transitions | $\mathcal{N}:=\max_{s,a,h}|\\{s^{\prime}\mid p_{h}(s^{\prime}|s,a)>0\\}|$
Objective cost | Random variable $C_{h}(s,a)\in[0,1]$, with $\mathbb{E}[C_{h}(s,a)]=c_{h}(s,a)$
Constraint cost ($i\in[I]$) | Random variable $D_{i,h}(s,a)$ with $\mathbb{E}[D_{i,h}(s,a)]=d_{i,h}(s,a)$
Constraint encoding |  $(d_{i},\alpha_{i})_{i\in[I]}$, with $d_{i}=(d_{i,h})_{h\in[H]}$ and $\alpha_{i}\in[0,H]$
Policy |  $\pi=(\pi_{1},\dots,\pi_{H})\in\Pi$ with $\pi_{h}\colon\mathcal{S}\to\Delta\left(\mathcal{A}\right)$ (non-stationary)
Value function | $V^{\pi}(s;c,p)=\mathbb{E}[\sum_{h=1}^{H}c_{h}(s_{h},a_{h})\mid s_{1},p,\pi]$
Constraint value function ($i\in[I]$) | $V^{\pi}(s;d_{i},p)=\mathbb{E}[\sum_{h=1}^{H}d_{i,h}(s_{h},a_{h})\mid s_{1},p,\pi]$
Table 1: Summary of CMDP notation

To view the CMDP as a convex optimization problem, we will express it via the
common notion of occupancy measures (Borkar, 1988).

######  Definition 1.

The state-action occupancy measure $q^{\pi}$ of a policy $\pi$ for a CMDP
$\mathcal{M}$ is defined as

$\displaystyle
q_{h}^{\pi}(s,a;p):=\mathbb{E}\left[\mathbbm{1}_{\\{s_{h}=s,a_{h}=a\\}}\mid
s_{1},p,\pi\right]=P[s_{h}=s,a_{h}=a\mid s_{1},p,\pi],$

for $s\in\mathcal{S}$, $a\in\mathcal{A}$, $h\in[H]$. We denote the stacked
vector of these values as $q^{\pi}(p)\in\mathbb{R}^{SAH}$, with the element at
index $(s,a,h)$ being $q_{h}^{\pi}(s,a;p)$.

For transition probabilities $p^{\prime}$, we can now define

$\displaystyle
Q(p^{\prime}):=\left\\{q^{\pi}(p^{\prime})\in\mathbb{R}^{SAH}\mid\pi\in\Pi\right\\}$

as the state-action occupancy measure polytope. Note that $Q(p^{\prime})$ is
indeed a polytope (Altman, 1999; Efroni et al., 2020). Moreover, for any
$p^{\prime}$ we have a surjective map $\pi\mapsto q^{\pi}(p^{\prime})$ between
$\Pi$ and $Q(p^{\prime})$, for which we can explicitly compute an element in
the pre-image of $q\in Q(p^{\prime})$ via
$\pi_{h}(s|a)=q_{h}(s,a)/(\sum_{a^{\prime}}q_{h}(s,a^{\prime}))$.

We can stack the expected costs $c_{h}(s,a)$ and constraint costs
$d_{ih}(s,a)$ in the same way as $q_{h}(s,a)$ to obtain vectors
$c\in\mathbb{R}^{SAH}$ and $d_{i}\in\mathbb{R}^{SAH}$. Note that we then have
$V^{\pi}(c,p)=\sum_{h,s,a}q^{\pi}_{h}(s,a;p)c_{h}(s,a)=c^{T}q^{\pi}(p)$ by
linearity of expectation. Similarly, for all $i\in[I]$, we have
$V^{\pi}(d_{i},p)=d_{i}^{T}q^{\pi}(p)$. Moreover, if we stack
$D=(d_{i})_{i\in[I]}\in\mathbb{R}^{I\times SAH}$ and
$\alpha=(\alpha_{i})_{i\in[I]}\in\mathbb{R}^{I}$ as

$\displaystyle D:=\left(\begin{matrix}d_{1}^{T}\\\ \vdots\\\
d_{I}^{T}\end{matrix}\right),\hskip
28.45274pt\alpha:=\left(\begin{matrix}\alpha_{1}\\\ \vdots\\\
\alpha_{I}\end{matrix}\right),$

we obtain $V^{\pi}(D,p)=Dq^{\pi}(p)\in[0,H]^{I}$ for the vector of the
constraint value functions. We can thus write

$\displaystyle\pi^{*}\in\arg\min_{\pi\in\Pi}\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
V^{\pi}(c,p)\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \text{s.t.}\leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\
V^{\pi}(d_{i},p)\leq\alpha_{i}\leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ (\forall i\in[I])$

equivalently as

$\displaystyle q^{\pi^{*}}\in\arg\min_{q^{\pi}\in Q(p)}\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
c^{T}q^{\pi}(p)\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \text{s.t.}\leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ Dq^{\pi}(p)\leq\alpha,$

which is an LP. In particular, by compactness of the state-action occupancy
polytope and continuity of the objective, there exists an optimal solution
$\pi^{*}$ if we assume feasibility.

####  A.4 Convex Optimization Preliminaries

We state some well-known results from constrained convex optimization that
will be useful to bound the dual iterates $\lambda_{k}$ appearing in Lemma 4.
The results are standard and we refer, for example, to the work by Beck
(2017).

Consider the (primal) optimization problem

$\displaystyle f^{*}:=\min\leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ $ $\displaystyle f(x)$ s.t. $\displaystyle g(x)\leq 0$
(14) $\displaystyle x\in X$

with the following assumptions.

######  Assumption 2 (Assumption 8.41, Beck (2017)).

In Eq. 14,

  * (a)

$X\subset\mathbb{R}^{n}$ is convex

  * (b)

$f\colon\mathbb{R}^{n}\to\mathbb{R}$ is convex

  * (c)

$g(\cdot):=(g_{1}(\cdot),\dots,g_{m}(\cdot))^{T}$ with
$g_{i}\colon\mathbb{R}^{n}\to\mathbb{R}$ convex

  * (d)

Eq. 14 has a finite optimal value $f^{*}$, which is attained by exactly the
elements of $X^{*}\neq\emptyset$

  * (e)

There exists $\bar{x}\in X$ such that $g(\bar{x})<0$

  * (f)

For all $\lambda\in\mathbb{R}_{\geq 0}^{m}$, $\min_{x\in
X}(f(x)+\lambda^{T}g(x))$ has an optimal solution

In this setup, we define the dual objective as

$\displaystyle q(\lambda):=\min_{x\in X}\left(f(x)+\lambda^{T}g(x)\right),$

where $\mathcal{L}\colon\mathbb{R}^{n}\times\mathbb{R}^{m}\to\mathbb{R}$,
$\mathcal{L}(x;\lambda):=f(x)+\lambda^{T}g(x)$ is the Lagrangian of the
problem in Eq. 14. The dual problem is then defined as

$\displaystyle q^{*}:=\max\leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ $ $\displaystyle q(\lambda)$ s.t.
$\displaystyle\lambda\geq 0.$

In this setup, we have the following results connecting the primal and the
dual problem.

######  Theorem 3 (Theorem A.1, Beck (2017)).

Under Assumption 2, strong duality holds in the following sense: We have

$\displaystyle f^{*}=q^{*}$

and the optimal solution of the dual problem is attained, with the set of
optimal solutions $\Lambda^{*}\neq\emptyset$.

###### Proof.

Proposition 6.4.4 of Bertsekas et al. (2003) gives a proof of the more general
Theorem A.1 of Beck (2017). We remark that if we assume affine constraints $g$
and $X$ being a polytope, then we can drop assumption (e) (Beck, 2017, Theorem
A.1). ∎

######  Theorem 4.

Suppose Assumption 2 holds. Let $x^{*}\in X^{*}$, $\lambda^{*}\in\Lambda^{*}$
and $x\in X$. Then

$\displaystyle f(x)-f(x^{*})+(\lambda^{*})^{T}g(x)\geq 0.$

###### Proof.

We have

$\displaystyle f(x)=$ $\displaystyle
f(x)+(\lambda^{*})^{T}g(x)-(\lambda^{*})^{T}g(x)$ $\displaystyle\geq$
$\displaystyle q(\lambda^{*})-(\lambda^{*})^{T}g(x)$
$\displaystyle\text{(definition of }q(\cdot)\text{)}$ $\displaystyle=$
$\displaystyle f(x^{*})-(\lambda^{*})^{T}g(x)$ $\displaystyle\text{(since by
\lx@cref{creftype~refnum}{thm:duality}, }q^{*}=f^{*}\text{)}$

and rearranging this proves the claim. Again, we see that we can drop
assumption (e) if we consider affine constraints $g$ and a polytope $X$. ∎

######  Theorem 5.

Under Assumption 2, for all $\lambda^{*}\in\Lambda^{*}$ and $\bar{x}$ as in
(e), we have

$\displaystyle\|\lambda^{*}\|\leq\|\lambda^{*}\|_{1}\leq\frac{f(\bar{x})-f^{*}}{\min_{i\in[m]}(-g_{i}(\bar{x}))}.$

###### Proof.

The first relation holds since $\lambda^{*}\geq 0$. We show the second
relation as follows (cf. Beck (2017, Theorem 8.42)). We have

$\displaystyle f(x^{*})=$ $\displaystyle q(\lambda^{*})$ (Theorem 3)
$\displaystyle\leq$ $\displaystyle f(\bar{x})+(\lambda^{*})^{T}g(\bar{x})$
$\displaystyle\text{(definition of }q(\cdot)\text{)}$ $\displaystyle\leq$
$\displaystyle f(\bar{x})+\|\lambda^{*}\|_{1}\max_{i\in[m]}g_{i}(\bar{x})$
$\displaystyle\text{(since }\lambda^{*}\geq 0\text{)}$ $\displaystyle=$
$\displaystyle f(\bar{x})-\|\lambda^{*}\|_{1}\min_{i\in[m]}(-g_{i}(\bar{x}))$

and rearranging this proves the claim. We remark that for this theorem, we do
need assumption (e) even in the affine case. ∎

###  Appendix B Solving the Inner Optimization Problem

There are numerous works leveraging Frank-Wolfe schemes for RL (including
planning) with convex objectives, most commonly in the context of pure/active
exploration (Hazan et al., 2019; Tarbouriech and Lazaric, 2019; Tarbouriech et
al., 2020; Mutny et al., 2023).

To the best of our knowledge, only Tarbouriech and Lazaric (2019, Appendix
A.3) remark that a combination of Frank-Wolfe UCB and planning in extended
MDPs would be possible in the presence of a convex objective and plausible
transitions. Tarbouriech et al. (2020) follow this approach but solve an
extended LP rather than an extended MDP in each Frank-Wolfe iteration.
Therefore, we make the former idea explicit and show how we can devise an
efficient algorithm for our case.

####  B.1 Derivation of the Policy Update via Frank-Wolfe

In the following, we provide an efficient algorithm for solving the inner
optimization problem in Eq. 4 based on the extended LP formulation of CMDPs,
Frank-Wolfe, and DP. Recall the first update in OptAug-CMDP, when rewriting
the value functions in terms of occupancy measures (see Section A.3):

$\displaystyle\pi_{k},\tilde{p}_{k}:=\arg\min_{\begin{subarray}{c}\pi\in\Pi\\\
p^{\prime}\in
B_{k}^{p}\end{subarray}}\left(\tilde{c}_{k}^{T}q^{\pi}(p^{\prime})+\frac{1}{2\eta_{k}}\left\|[\lambda_{k}+\eta_{k}(\tilde{D}_{k}q^{\pi}(p^{\prime})-\alpha)]_{+}\right\|^{2}\right),$
(15)

where $q^{\pi}(p^{\prime})\in\mathbb{R}^{SAH}$,
$\tilde{D}_{k}\in\mathbb{R}^{I\times SAH}$ and
$\tilde{c}_{k}\in\mathbb{R}^{SAH}$ are defined as in Section A.3.

We first use the extended LP trick (Rosenberg and Mansour, 2019; Efroni et
al., 2020) to switch to a convex optimization problem in the state-action-
state occupancy measure. That is, in the problem above substitute

$\displaystyle
z_{h}(s,a,s^{\prime}):=z_{h}^{\pi}(s,a,s^{\prime};p^{\prime}):=$
$\displaystyle p^{\prime}_{h}(s^{\prime}|s,a)q_{h}^{\pi}(s,a;p^{\prime})$ (16)

and note that

$\displaystyle
q^{\pi}_{h}(s,a;p^{\prime})=\sum_{s^{\prime}}z_{h}^{\pi}(s,a,s^{\prime};p^{\prime}).$
(17)

Stacked across $(s,a,h)\in\mathcal{S}\times\mathcal{A}\times[H]$, this simply
reads

$\displaystyle
q^{\pi}(p^{\prime})=\sum_{s^{\prime}}z^{\pi}(s^{\prime};p^{\prime})\in\mathbb{R}^{SAH},$

for all $s^{\prime}\in\mathcal{S}$. The objective of Eq. 15 then reads

$\displaystyle
f(z):=\sum_{s^{\prime}}\tilde{c}_{k}^{T}z(s^{\prime})+\frac{1}{2\eta_{k}}\|[\lambda_{k}+\eta_{k}(\sum_{s^{\prime}}\tilde{D}_{k}z(s^{\prime})-\alpha)]_{+}\|^{2},$

and we need to minimize it over the set $Z\subset\mathbb{R}^{S^{2}AH}$ which
is given by the constraints

$\displaystyle\begin{cases}\sum_{a,s^{\prime}}z_{h}(s,a,s^{\prime})=\sum_{s^{\prime},a^{\prime}}z_{h-1}(s^{\prime},a^{\prime},s)\hskip
28.45274pt&(\forall h>1,s)\\\\[7.0pt]
\sum_{a,s^{\prime}}z_{1}(s,a,s^{\prime})=\mu(s)\hskip 28.45274pt&(\forall
s)\\\\[7.0pt] z_{h}(s,a,s^{\prime})\geq 0\hskip 28.45274pt&(\forall
s,a,s^{\prime},h)\\\\[7.0pt]
z_{h}(s,a,s^{\prime})-(\bar{p}^{k-1}_{h}(s^{\prime}|s,a)+\beta_{k,h}^{p}(s,a,s^{\prime}))\sum_{s^{\prime\prime}}z_{h}(s,a,s^{\prime\prime})\leq
0\hskip 28.45274pt&(\forall s,a,s^{\prime},h)\\\\[7.0pt]
-z_{h}(s,a,s^{\prime})+(\bar{p}^{k-1}_{h}(s^{\prime}|s,a)-\beta_{k,h}^{p}(s,a,s^{\prime}))\sum_{s^{\prime\prime}}z_{h}(s,a,s^{\prime\prime})\leq
0\hskip 28.45274pt&(\forall s,a,s^{\prime},h),\end{cases}$

where $\mu(s)=1$ if $s=s_{1}$ and $0$ otherwise. Note that $Z$ is a bounded
polytope and thus compact and convex. We can thus equivalently solve

$\displaystyle\min_{z\in Z}f(z),$ (18)

which is a standard convex optimization problem. Note that even with the
convex formulation in Eq. 18, Eq. 4 cannot be written as an LP due to the
nonlinear objective. It cannot be rewritten as a standard convex RL problem
(Zahavy et al., 2021; Geist et al., 2021) either since the transition
probabilities are part of the optimization and we thus had to switch to the
extended convex program in the state-action-state occupancy measure $z$. Note
that for efficiency reasons, we aim to avoid LP (which is needed for solving
CMDPs due to the lack of the Bellman optimality principle), and projections
onto the high-dimensional constraint set $Z$. Instead, we will make use of DP
and gradient-based methods.

If we can approximately solve Eq. 18, we can later retrieve transitions and
policy via

$\displaystyle\tilde{p}_{k,h}(s^{\prime}|s,a)$
$\displaystyle:=\frac{z_{h}(s,a,s^{\prime})}{\sum_{s^{\prime\prime}}z_{h}(s,a,s^{\prime\prime})},$
(19) $\displaystyle\pi_{k,h}(a|s)$
$\displaystyle:=\frac{\sum_{s^{\prime}}z_{h}(s,a,s^{\prime})}{\sum_{a^{\prime},s^{\prime}}z_{h}(s,a^{\prime},s^{\prime})}.$
(20)

To solve Eq. 18, we make use of Frank-Wolfe. Frank-Wolfe is a well-known
iterative method for constrained nonlinear optimization, which allows to
minimize a smooth convex function over a convex domain and avoids projections.
To apply it to Eq. 18, we need a linear minimization oracle (LMO) that in step
$t$ (of episode $k$) solves

$\displaystyle\min_{g\in Z}g^{T}\nabla f(z^{t})$ (21)

and then, after finding a minimizer $g$, updates

$\displaystyle z^{t+1}:=(1-\gamma_{t})z^{t}+\gamma_{t}g,$

where $\gamma_{t}:=2/(t+2)$. It is well known that Frank-Wolfe converges with
a rate of $O(1/T)$ for smooth objectives. This is given here, but the
smoothness parameter depends on $\eta_{k}$. We refer to Abernethy and Wang
(2017); Jaggi (2013); Frank and Wolfe (1956) for the relevant background.

It remains to show that we can provide an efficient LMO that uses DP instead
of LP and avoids projections onto $Z$. Let $(\nabla
f(z))(s,a,s^{\prime},h):=\frac{\partial f}{\partial z_{h}(s,a,s^{\prime})}(z)$
be the gradient of $f$ with respect to $z$ at index $(s,a,s^{\prime},h)$. Then
the $s^{\prime}$-th component of the gradient of $f$ with respect to $z$ is

$\displaystyle(\nabla
f(z))(\cdot,\cdot,s^{\prime},\cdot)=\tilde{c}_{k}+\tilde{D}_{k}^{T}[\lambda_{k}+\eta_{k}(\tilde{D}_{k}\sum_{s^{\prime\prime}}z(s^{\prime\prime})-\alpha)]_{+}\in\mathbb{R}^{SAH},$
(22)

which we can compute explicitly and efficiently. We note that this gradient
does not depend on $s^{\prime}$ and thus the gradient of $f$ with respect to
the whole vector $z\in\mathbb{R}^{S^{2}AH}$ is simply the vector above,
repeatedly stacked $S$ times.

We now show how switching back to the optimization over $\Pi\times B_{k}^{p}$
allows for an efficient LMO via DP. For $g\in Z$, there are $\pi$,
$p^{\prime}$ such that

$\displaystyle
g_{h}(s,a,s^{\prime})=g_{h}^{\pi}(s,a,s^{\prime};p^{\prime})=p_{h}(s^{\prime}|a,s)q_{h}^{\pi}(s,a;p),$

via Eqs. 20 and 19. The LMO then needs to minimize

$\displaystyle g^{T}\nabla f(z^{t})=$
$\displaystyle\sum_{s,a,s^{\prime},h}g_{h}(s,a,s^{\prime})(\nabla
f(z^{t}))(s,a,1,h)$ $\displaystyle=$
$\displaystyle\sum_{s,a,s^{\prime},h}p^{\prime}_{h}(s^{\prime}|a,s)q_{h}^{\pi}(s,a;p^{\prime})(\nabla
f(z^{t}))(s,a,1,h)$ $\displaystyle=$
$\displaystyle\sum_{s,a,h}q_{h}^{\pi}(s,a;p^{\prime})(\nabla
f(z^{t}))(s,a,1,h)$ (23)

over $\pi\in\Pi$ and $p^{\prime}\in B_{k}^{p}$. This corresponds to solving
the extended MDP
$\mathcal{M}^{+}:=\\{(M=(\mathcal{S},\mathcal{A},r^{+},p^{+}))\mid\forall
s,a,h\colon r^{+}_{h}(s,a):=\nabla f(z^{t})(s,a,1,h),\leavevmode\nobreak\
p_{h}^{+}(\cdot|s,a)\in B_{k,h}^{p}(s,a)\\}$. We can do so via backward
induction (i.e., DP) that optimizes

$\displaystyle Q_{h}^{k}(s,a):=r_{h}^{+}(s,a)+\min_{p^{\prime}(\cdot|s,a)\in
B_{k,h}^{p}(s,a)}\sum_{s^{\prime}}p^{\prime}(s^{\prime}|s,a)\min_{a^{\prime}}Q_{h+1}^{k}(s^{\prime},a^{\prime})$
(24)

and starts with $Q_{H+1}^{k}(s,a)=0$. We can retrieve the transitions and the
policy by storing the minimizers in each step of the DP. To compute the
solution $g$ of the LMO from $\pi$, $p^{\prime}$, one can then use a simple
and efficient DP scheme to compute $q_{h}^{\pi}(p^{\prime})$, which is
explained in Section B.2. We can use this, in turn, to retrieve $g$ using the
substitution in Eq. 16. Then, we perform the second step of Frank-Wolfe to get
a convex combination of $g$ and $z^{t}$, which concludes the Frank-Wolfe
iteration.

We can already see that the computational complexity of the $k$-th step of
OptAug-CMDP is larger than the one of OptDual-CMDP by a factor of
$O(1/\epsilon_{k})$ (and a dependency on $\eta_{k}$) because we need this many
Frank-Wolfe iterations, which is the price we pay for the stronger regret
bound. We provide a full analysis of the iteration complexity in Section D.2.

####  B.2 Pseudocode for the Inner Problem

More formally, the algorithm for solving the inner problem (Eq. 4) reads as
follows.

Input: Current estimates $\tilde{c}_{k}$, $\tilde{D}_{k}$, $B_{k}^{p}$, and
$\lambda_{k}$
Output: Next policy $\pi_{k}$ and $\tilde{p}_{k}$ according to Eq. 15

Set $T=\frac{2\eta_{k}IS^{2}AH}{\epsilon_{k}}$, $\gamma_{t}=2/(2+t)$

Initialize $z^{0}\in Z$ arbitrarily

for $t=0,\dots,T-1$ do

Compute $\nabla f(z^{t})$ according to Eq. 22

Minimize Eq. 23 via DP algorithm from Eq. 24 to find $\pi^{t}$, $p^{t}$

Retrieve minimizer $g^{t}$ from $\pi^{t}$, $p^{t}$ via DP algorithm from Eq.
26 and Eq. 16

Set $z^{t+1}:=\gamma_{t}g^{t}+(1-\gamma_{t})z^{t}$

Construct $\pi_{k}$, $\tilde{p}_{k}$ from $z^{T}$ via Eqs. 20 and 19

return $\pi_{k}$, $\tilde{p}_{k}$

Algorithm 3 InnerOpt-FW

As a final step, we now describe how to retrieve $q:=q^{\pi}(p^{\prime})$ from
$\pi$ and $p^{\prime}$ in Line 6 (Jin et al., 2019). For $s\in\mathcal{S}$,
set

$q_{h}(s):=P[s_{h}=s|s_{1};p^{\prime},\pi]=\sum_{a^{\prime}\in\mathcal{A}}q_{h}(s,a^{\prime}).$

Given a policy $\pi$ and transition probabilities $p^{\prime}$, we need to
compute

$\displaystyle q_{h}(s,a)=q_{h}(s)\cdot\pi_{h}(a|s),$ (25)

for every $h\in[H]$, $s\in\mathcal{S}$ and $a\in\mathcal{A}$. This is easily
achieved via DP. Indeed, we have

$\displaystyle q_{1}(s)=\begin{cases}1\hskip 28.45274pt(s=s_{1})\\\ 0\hskip
28.45274pt(\text{else}),\end{cases}$

and for $h>1$

$\displaystyle q_{h}(s)=$ $\displaystyle P[s_{h}=s|s_{1};p^{\prime},\pi]$
$\displaystyle=$
$\displaystyle\sum_{s^{\prime}\in\mathcal{S}}P[s_{h}=s|s_{h-1}=s^{\prime};s_{1},p^{\prime},\pi]P[s_{h-1}=s^{\prime}|s_{1};p^{\prime}]$
$\displaystyle=$
$\displaystyle\sum_{s^{\prime}\in\mathcal{S}}\sum_{a\in\mathcal{A}}\pi_{h-1}(a|s^{\prime})p_{h-1}(s|s^{\prime},a)P[s_{h-1}=s^{\prime}|s_{1},;p^{\prime}]$
$\displaystyle=$
$\displaystyle\sum_{s^{\prime}\in\mathcal{S}}\sum_{a\in\mathcal{A}}\pi_{h-1}(a|s^{\prime})p_{h-1}(s|s^{\prime},a)q_{h-1}(s^{\prime}),$
(26)

which together with Eq. 25 enables us to retrieve the state-action occupancy
measure. Clearly, the above DP scheme can be performed efficiently.

###  Appendix C On-Policy Error Bounds

We consider arbitrary polices $(\pi_{k})_{k\in[K]}$. We suppose that in the
CMDP $\mathcal{M}$, the agent plays $\pi_{k}$ in episode $k\in[K]$ and uses it
to update the optimistic model according to Eq. 3, with some fixed
$\delta=3\delta^{\prime}>0$.

We first establish Lemmas 8, 9 and 10, which will allow us to bound the
estimation errors (Lemma 3). For a definition of the occupancy measure
$q^{\pi}(s,a;p)$, see Section A.3. We write $\lesssim$ for an inequality up to
polylogarithmic factors.

######  Lemma 8 (Lemma 36, Efroni et al. (2020)).

Suppose for all $s$, $a$, $h$, $k\in[K]$ we have

$\displaystyle n_{h}^{k-1}(s,a)$
$\displaystyle>\frac{1}{2}\sum_{j<k}q_{h}^{\pi_{j}}(s,a;p)-H\log\left(\frac{SAH}{\delta^{\prime}}\right).$

Then for all $K^{\prime}\leq K$

$\displaystyle\sum_{k^{\prime}=1}^{K^{\prime}}\sum_{h=1}^{H}\mathbb{E}\left[\frac{1}{\sqrt{n^{k^{\prime}-1}_{h}(s_{h}^{k^{\prime}},a_{h}^{k^{\prime}})}}\mid\mathcal{F}_{k^{\prime}-1}\right]\leq\tilde{O}(\sqrt{SAHK^{\prime}}+SAH),$

where $\mathcal{F}_{k^{\prime}-1}$ is the $\sigma$-algebra induced by all
random variables up to and including episode $k^{\prime}-1$.

###### Proof.

We refer to Efroni et al. (2019, Lemma 38) for a proof of the statement. ∎

######  Lemma 9 (Lemma 37, Efroni et al. (2020)).

Suppose for all $s$, $a$, $h$, $k\in[K]$ we have

$\displaystyle n_{h}^{k-1}(s,a)$
$\displaystyle>\frac{1}{2}\sum_{j<k}q_{h}^{\pi_{j}}(s,a;p)-H\log\left(\frac{SAH}{\delta^{\prime}}\right).$

Then for all $K^{\prime}\leq K$

$\displaystyle\sum_{k^{\prime}=1}^{K^{\prime}}\sum_{h=1}^{H}\mathbb{E}\left[\frac{1}{n^{k^{\prime}-1}_{h}(s_{h}^{k^{\prime}},a_{h}^{k^{\prime}})}\mid\mathcal{F}_{k^{\prime}-1}\right]\leq\tilde{O}(SA),$

where $\mathcal{F}_{k^{\prime}-1}$ is the $\sigma$-algebra induced by all
random variables up to and including episode $k^{\prime}-1$.

###### Proof.

We refer to Zanette and Brunskill (2019, Lemma 13) for a proof of the
statement. ∎

The following lemma provides an on-policy error bound based on the value
difference lemma. Together with the preliminaries from Section E.1, it allows
us to bound the estimation error.

######  Lemma 10 (On-policy errors; Lemma 29, Efroni et al. (2020)).

Consider an MDP with transition dynamics $p$ and arbitrary estimated
transition dynamics $\hat{p}_{k}$ (for $k\in[K]$, each forming a conditional
probability measure). Consider policy iterates $(\pi_{k})_{k\in[K]}$ and
suppose $\pi_{k}$ is played in episode $k\in[K]$ and used to update the
counters. Let $l_{h}(s,a)$, $\tilde{l}_{k,h}(s,a)$ be the cost and
corresponding optimistic cost with $l=c$ or $l=d_{i}$ as discussed in Eq. 3.
For a policy $\pi$, let $V^{\pi}_{h}(s;l,p)$,
$V^{\pi}_{h}(s;\tilde{l}_{k},\hat{p}_{k})$ be the values of $\pi$ according to
the true resp. estimated model. Assume that for all $s,a,h,k$ we have

$\displaystyle n_{h}^{k-1}(s,a)$
$\displaystyle>\frac{1}{2}\sum_{j<k}q_{h}^{\pi_{j}}(s,a;p)-H\log\left(\frac{SAH}{\delta^{\prime}}\right),$
(a) $\displaystyle|\tilde{l}_{k,h}(s,a)-l_{h}(s,a)|$
$\displaystyle\leq\tilde{O}\left(\frac{1}{\sqrt{n_{h}^{k-1}(s,a)\vee
1}}\right),$ (b)
$\displaystyle|\hat{p}_{k,h}(s^{\prime}|s,a)-p_{h}(s^{\prime}|s,a)|$
$\displaystyle\leq\tilde{O}\left(\sqrt{\frac{p_{h}(s^{\prime}|s,a)L_{\delta}^{p}}{n_{h}^{k-1}(s,a)\vee
1}}+\frac{L_{\delta}^{p}}{n_{h}^{k-1}(s,a)\vee 1}\right).$ (c)

Then we have

$\displaystyle\sum_{k=1}^{K}|V^{\pi_{k}}(l,p)-V^{\pi_{k}}(\tilde{l}_{k},\hat{p}_{k})|\leq\tilde{O}\left(\sqrt{\mathcal{N}SAH^{3}K}+(H\sqrt{\mathcal{N}}+S)SAH\right).$
(27)

###### Proof.

From the value difference lemma (Dann et al., 2017, Lemma E.15), we get

$\displaystyle\sum_{k=1}^{K}|V^{\pi_{k}}(l,p)-V^{\pi_{k}}(\tilde{l}_{k},\hat{p}_{k})|$
$\displaystyle\leq$
$\displaystyle\sum_{k=1}^{K}\sum_{h=1}^{H}\mathbb{E}[|l_{h}(s_{h},a_{h})-\tilde{l}_{k,h}(s_{h},a_{h})|\mid
s_{1},p,\pi_{k}]$ $\displaystyle+$
$\displaystyle\sum_{k=1}^{K}\sum_{h=1}^{H}\mathbb{E}\bigg{[}\sum_{s^{\prime}}|p_{h}(s|s_{h},a_{h})-\hat{p}_{k}(s|s_{h},a_{h})|V_{h+1}^{\pi_{k}}(s^{\prime};\tilde{l}_{k},\hat{p}_{k})\mid
s_{1},p,\pi_{k}\bigg{]}.$

We can bound the first of the two terms as follows.

$\displaystyle\sum_{k=1}^{K}\sum_{h=1}^{H}\mathbb{E}[|l_{h}(s_{h},a_{h})-\tilde{l}_{k,h}(s_{h},a_{h})|\mid
s_{1},p,\pi_{k}]$ $\displaystyle\overset{(b)}{\lesssim}$
$\displaystyle\sum_{k=1}^{K}\sum_{h=1}^{H}\mathbb{E}\bigg{[}\frac{1}{\sqrt{n^{k-1}_{h}(s_{h},a_{h})\vee
1}}\mid s_{1},p,\pi_{k}\bigg{]}$ $\displaystyle=$
$\displaystyle\sum_{k=1}^{K}\sum_{h=1}^{H}\mathbb{E}\bigg{[}\frac{1}{\sqrt{n^{k-1}_{h}(s_{h}^{k},a_{h}^{k})\vee
1}}\mid\mathcal{F}_{k-1}\bigg{]}$
$\displaystyle\overset{\text{\lx@cref{creftype~refnum}{lem:l36-efroni}}}{\leq}$
$\displaystyle\tilde{O}\left(\sqrt{SAHK}+SAH\right),$

where the second to last inequality holds since $\pi_{k}$ is played in episode
$k$, and Lemma 8 applies due to assertion (a). For the second term, we first
note that $|V_{h+1}^{\pi_{k}}(s^{\prime};\tilde{l}_{k},\hat{p}_{k})|\lesssim
H$ since $|\tilde{l}_{k,h}(s,a)|\leq
l_{h}(s,a)+\frac{1}{\sqrt{n^{k-1}_{h}(s,a)\vee 1}}$ by (b). Hence

$\displaystyle\sum_{k=1}^{K}\sum_{h=1}^{H}\mathbb{E}\bigg{[}\sum_{s^{\prime}}|p_{h}(s|s_{h},a_{h})-\hat{p}_{k}(s|s_{h},a_{h})|V_{h+1}^{\pi_{k}}(s^{\prime};\tilde{l}_{k},\hat{p}_{k})\mid
s_{1},p,\pi_{k}\bigg{]}$ $\displaystyle\overset{(c)}{\lesssim}$ $\displaystyle
H\sum_{k=1}^{K}\sum_{h=1}^{H}\mathbb{E}\bigg{[}\frac{1}{\sqrt{n^{k-1}_{h}(s_{h},a_{h})\vee
1}}\big{(}\sum_{s^{\prime}}\sqrt{p_{h}(s^{\prime}|s_{h},a_{h})}\big{)}+\frac{S}{n^{k-1}_{h}(s_{h},a_{h})\vee
1}\mid s_{1},p,\pi_{k}\bigg{]}$ $\displaystyle\overset{\text{Jensen}}{\leq}$
$\displaystyle
H\sum_{k=1}^{K}\sum_{h=1}^{H}\mathbb{E}\bigg{[}\frac{1}{\sqrt{n^{k-1}_{h}(s_{h},a_{h})\vee
1}}\sqrt{\mathcal{N}}\sqrt{\sum_{s^{\prime}}p_{h}(s^{\prime}|s_{h},a_{h})}+\frac{S}{n^{k-1}_{h}(s_{h},a_{h})\vee
1}\mid s_{1},p,\pi_{k}\bigg{]}$ $\displaystyle=$ $\displaystyle
H\sum_{k=1}^{K}\sum_{h=1}^{H}\mathbb{E}\bigg{[}\frac{\sqrt{\mathcal{N}}}{\sqrt{n^{k-1}_{h}(s_{h}^{k},a_{h}^{k})\vee
1}}+\frac{S}{n^{k-1}_{h}(s_{h}^{k},a_{h}^{k})\vee
1}\mid\mathcal{F}_{k-1}\bigg{]}$ $\displaystyle\lesssim$ $\displaystyle
H\sqrt{\mathcal{N}}\cdot\sqrt{SAHK}+H\sqrt{\mathcal{N}}\cdot SAH+HS\cdot SA$
$\displaystyle=$
$\displaystyle\sqrt{\mathcal{N}SAH^{3}K}+(H\sqrt{\mathcal{N}}+S)SAH,$

where the second to last relation holds due to Lemma 8 and Lemma 9 (which in
turn apply due to assertion (a)), and the one before holds since $\pi_{k}$ is
played in episode $k$. ∎

Next, we prove Lemma 13, which is a variation of Lemma 10 and will allow us to
establish the bound on the pre-training duration in Lemma 1. For this, we
first need to establish Lemmas 11 and 12, which are a consequence of Lemmas 8
and 9, respectively.

######  Lemma 11.

Let $K^{\prime}\in[K]$. Assume that for all $s$, $a$, $h$, $k\in[K]$ we have

$\displaystyle n_{h}^{k-1}(s,a)$
$\displaystyle>\frac{1}{2}\sum_{j<k}q_{h}^{\pi_{j}}(s,a;p)-H\log\left(\frac{SAH}{\delta^{\prime}}\right).$

Let $\pi$ be any fixed policy and suppose that in episode $k\in[K]$, policy
$\pi_{k}$ is played, with $\pi_{k^{\prime}}=\pi$ for all
$k^{\prime}\in[K^{\prime}]$. Then for all $k\geq K^{\prime}$ we have

$\displaystyle\sum_{h=1}^{H}\mathbb{E}\left[\frac{1}{\sqrt{n^{k-1}_{h}(s_{h},a_{h})\vee
1}}\mid
s_{1},\pi,p\right]\leq\tilde{O}\left(\sqrt{SAH}(K^{\prime})^{-1/2}+SAH(K^{\prime})^{-1}\right).$

###### Proof.

Note that for any realization of all random variables up to and including
episode $K$, we have (for $k\in\\{0,\dots,K-1\\}$)

$\displaystyle n^{k+1}_{h}(s,a)\geq n^{k}_{h}(s,a),$

since the counters can only increase across episodes, and thus for all
$k^{\prime}\leq K^{\prime}<k$ we have

$\displaystyle\frac{1}{\sqrt{n^{k-1}_{h}(s_{h},a_{h})\vee
1}}\leq\frac{1}{\sqrt{n^{k^{\prime}-1}_{h}(s_{h},a_{h})\vee 1}}.$

For $k\geq K^{\prime}$, we thus find

$\displaystyle\sum_{h=1}^{H}\mathbb{E}\bigg{[}\frac{1}{\sqrt{n^{k-1}_{h}(s_{h}^{k},a_{h}^{k})}}\mid
s_{1},\pi,p\bigg{]}\leq$
$\displaystyle\frac{1}{K^{\prime}}\sum_{k^{\prime}=1}^{K^{\prime}}\sum_{h=1}^{H}\mathbb{E}\bigg{[}\frac{1}{\sqrt{n^{k^{\prime}-1}_{h}(s_{h},a_{h})}}\mid
s_{1},\pi,p\bigg{]}$ $\displaystyle=$
$\displaystyle\frac{1}{K^{\prime}}\sum_{k^{\prime}=1}^{K^{\prime}}\sum_{h=1}^{H}\mathbb{E}\bigg{[}\frac{1}{\sqrt{n^{k^{\prime}-1}_{h}(s_{h}^{k^{\prime}},a_{h}^{k^{\prime}})}}\mid\mathcal{F}_{k^{\prime}-1}\bigg{]}$
$\displaystyle\leq$
$\displaystyle\frac{1}{K^{\prime}}\tilde{O}(\sqrt{SAHK^{\prime}}+SAH),$

where $\mathcal{F}_{k^{\prime}-1}$ is the $\sigma$-algebra induced by all
random variables up to and including episode $k^{\prime}-1$ and where the
first relation holds by monotonicity of the counters, the second relation
holds since $\pi$ is played in the $k^{\prime}$-th episode, and the final
relation holds by Lemma 8. ∎

######  Lemma 12.

Let $K^{\prime}\in[K]$. Assume that for all $s$, $a$, $h$, $k\in[K]$ we have

$\displaystyle
n_{h}^{k-1}(s,a)>\frac{1}{2}\sum_{j<k}q_{h}^{\pi_{j}}(s,a;p)-H\log\left(\frac{SAH}{\delta^{\prime}}\right).$

Let $\pi$ be any fixed policy and suppose that in episode $k\in[K]$, policy
$\pi_{k}$ is played, with $\pi_{k^{\prime}}=\pi$ for all
$k^{\prime}\in[K^{\prime}]$. Then for all $k\geq K^{\prime}$ we have

$\displaystyle\sum_{h=1}^{H}\mathbb{E}\left[\frac{1}{n^{k-1}_{h}(s_{h},a_{h})\vee
1}\mid s_{1},\pi,p\right]\leq\tilde{O}\left(SA(K^{\prime})^{-1}\right).$

###### Proof.

Note that for any realization of all random variables up to and including
episode $K$, we have (for $k\in\\{0,\dots,K-1\\}$)

$\displaystyle n^{k+1}_{h}(s,a)\geq n^{k}_{h}(s,a),$

since the counters can only increase across episodes, and thus for all
$k^{\prime}\leq K^{\prime}<k$ we have

$\displaystyle\frac{1}{n^{k-1}_{h}(s_{h},a_{h})\vee
1}\leq\frac{1}{n^{k^{\prime}-1}_{h}(s_{h},a_{h})\vee 1}.$

For $k\geq K^{\prime}$, we thus find

$\displaystyle\sum_{h=1}^{H}\mathbb{E}\bigg{[}\frac{1}{n^{k-1}_{h}(s_{h},a_{h})}\mid
s_{1},\pi,p\bigg{]}\leq$
$\displaystyle\frac{1}{K^{\prime}}\sum_{k^{\prime}=1}^{K^{\prime}}\sum_{h=1}^{H}\mathbb{E}\bigg{[}\frac{1}{n^{k^{\prime}-1}_{h}(s_{h},a_{h})}\mid
s_{1},\pi,p\bigg{]}$ $\displaystyle=$
$\displaystyle\frac{1}{K^{\prime}}\sum_{k^{\prime}=1}^{K^{\prime}}\sum_{h=1}^{H}\mathbb{E}\bigg{[}\frac{1}{n^{k^{\prime}-1}_{h}(s_{h}^{k^{\prime}},a_{h}^{k^{\prime}})}\mid\mathcal{F}_{k^{\prime}-1}\bigg{]}$
$\displaystyle\leq$ $\displaystyle\frac{1}{K^{\prime}}\tilde{O}(SA),$

where $\mathcal{F}_{k^{\prime}-1}$ is the $\sigma$-algebra induced by all
random variables up to and including episode $k^{\prime}-1$ and where the
first relation holds by monotonicity of the counters, the second relation
holds since $\pi$ is played in the $k^{\prime}$-th episode, and the final
relation holds by Lemma 9. ∎

We are now ready to prove the needed variation of Lemma 10.

######  Lemma 13.

(Last-iterate fixed policy errors) Consider an MDP with transition dynamics
$p$ and arbitrary estimated transition dynamics $\hat{p}_{k}$ (for $k\in[K]$,
each forming a probability measure). Consider policy iterates
$(\pi_{k})_{k\in[K]}$ and suppose $\pi_{k}$ is played in episode $k\in[K]$ and
used to update the counters. Let $l_{h}(s,a)$, $\tilde{l}_{k,h}(s,a)$ be cost
and corresponding optimistic cost with $l=c$ or $l=d_{i}$ as discussed in Eq.
3. Consider $K^{\prime}\in[K]$ and a policy $\pi$. Suppose that for all
$k^{\prime}\in[K^{\prime}]$, $\pi_{k^{\prime}}=\pi$. Let $V^{\pi}_{h}(s;l,p)$,
$V^{\pi}_{h}(s;\tilde{l}_{k},\hat{p}_{k})$ be the values of $\pi$ according to
the true and estimated model, respectively. Assume that for all $s,a,h,k$ we
have

$\displaystyle n_{h}^{k-1}(s,a)$
$\displaystyle>\frac{1}{2}\sum_{j<k}q_{h}^{\pi_{j}}(s,a;p)-H\log\left(\frac{SAH}{\delta^{\prime}}\right),$
(a) $\displaystyle|\tilde{l}_{k,h}(s,a)-l_{h}(s,a)|$
$\displaystyle\leq\tilde{O}\left(\frac{1}{\sqrt{n_{h}^{k-1}(s,a)\vee
1}}\right),$ (b)
$\displaystyle|\hat{p}_{k,h}(s^{\prime}|s,a)-p_{h}(s^{\prime}|s,a)|$
$\displaystyle\leq\tilde{O}\left(\sqrt{\frac{p_{h}(s^{\prime}|s,a)L_{\delta}^{p}}{n_{h}^{k-1}(s,a)\vee
1}}+\frac{L_{\delta}^{p}}{n_{h}^{k-1}(s,a)\vee 1}\right).$ (c)

Then for all $k\geq K^{\prime}$ we have

$\displaystyle|V^{\pi}(l,p)-V^{\pi}(\tilde{l}_{k},\hat{p}_{k})|\leq\tilde{O}\left(\sqrt{\mathcal{N}SAH^{3}}(K^{\prime})^{-1/2}+(H\sqrt{\mathcal{N}}+S)SAH(K^{\prime})^{-1}\right).$

In words, if the agent plays $\pi$ for the first $K^{\prime}$ episodes, then
for all future episodes, the value differences for $\pi$ are upper bounded by
the value on the RHS.

###### Proof.

From the value difference lemma (Dann et al., 2017, Lemma E.15) we get

$\displaystyle|V^{\pi}(l,p)-V^{\pi}(\tilde{l}_{k},\hat{p}_{k})|$
$\displaystyle\leq$
$\displaystyle\sum_{h=1}^{H}\mathbb{E}[|l_{h}(s_{h},a_{h})-\tilde{l}_{h}(s_{h},a_{h})|\mid
s_{1},p,\pi]$ $\displaystyle+$
$\displaystyle\sum_{h=1}^{H}\mathbb{E}\bigg{[}\sum_{s^{\prime}}|p_{h}(s|s_{h},a_{h})-\hat{p}_{k}(s|s_{h},a_{h})|V_{h+1}^{\pi}(s^{\prime};\tilde{l}_{k},\hat{p}_{k})\mid
s_{1},p,\pi\bigg{]}.$

We can bound the first of the two terms as follows.

$\displaystyle\sum_{h=1}^{H}\mathbb{E}[|l_{h}(s_{h},a_{h})-\tilde{l}_{h}(s_{h},a_{h})|\mid
s_{1},p,\pi]$ $\displaystyle\overset{(b)}{\lesssim}$
$\displaystyle\sum_{h=1}^{H}\mathbb{E}\bigg{[}\frac{1}{\sqrt{n^{k-1}_{h}(s_{h},a_{h})\vee
1}}\mid s_{1},p,\pi\bigg{]}$
$\displaystyle\overset{\text{\lx@cref{creftype~refnum}{lem:sqrt-sum}}}{\leq}$
$\displaystyle\tilde{O}\left(\sqrt{SAH}(K^{\prime})^{-1/2}+SAH(K^{\prime})^{-1}\right),$

where Lemma Lemma 11 applies due to assertion (a). For the second term, we
first note that $|V_{h+1}^{\pi}(s^{\prime};\tilde{l}_{k},\hat{p}_{k})|\lesssim
H$ since $|\tilde{l}_{k,h}(s,a)|\leq
l_{h}(s,a)+\frac{1}{\sqrt{n^{k-1}_{h}(s,a)\vee 1}}$ by (b). Hence

$\displaystyle\sum_{h=1}^{H}\mathbb{E}\bigg{[}\sum_{s^{\prime}}|(p_{h}(s|s_{h},a_{h})-\hat{p}_{k}(s|s_{h},a_{h}))V_{h+1}^{\pi}(s^{\prime};\tilde{l}_{k},\hat{p}_{k})\mid
s_{1},p,\pi\bigg{]}$ $\displaystyle\overset{(c)}{\lesssim}$ $\displaystyle
H\sum_{h=1}^{H}\mathbb{E}\bigg{[}\frac{1}{\sqrt{n^{k-1}_{h}(s_{h},a_{h})\vee
1}}\big{(}\sum_{s^{\prime}}\sqrt{p_{h}(s^{\prime}|s_{h},a_{h})}\big{)}+\frac{S}{n^{k-1}_{h}(s_{h},a_{h})\vee
1}\mid s_{1},p,\pi\bigg{]}$ $\displaystyle\overset{\text{Jensen}}{\leq}$
$\displaystyle
H\sum_{h=1}^{H}\mathbb{E}\bigg{[}\frac{1}{\sqrt{n^{k-1}_{h}(s_{h},a_{h})\vee
1}}\sqrt{\mathcal{N}}\sqrt{\sum_{s^{\prime}}p_{h}(s^{\prime}|s_{h},a_{h})}+\frac{S}{n^{k-1}_{h}(s_{h},a_{h})\vee
1}\mid s_{1},p,\pi\bigg{]}$ $\displaystyle\lesssim$ $\displaystyle
H\sqrt{\mathcal{N}}\cdot\sqrt{SAH}(K^{\prime})^{-1/2}+H\sqrt{\mathcal{N}}\cdot
SAH(K^{\prime})^{-1}+HS\cdot SA(K^{\prime})^{-1}$ $\displaystyle=$
$\displaystyle\sqrt{\mathcal{N}SAH^{3}}(K^{\prime})^{-1/2}+(H\sqrt{\mathcal{N}}+S)SAH(K^{\prime})^{-1},$

where the second to last relation holds due to Lemma 11 and Lemma 12 (which in
turn apply due to assertion (a)). ∎

###  Appendix D Omitted Proofs for Section 3

####  D.1 Pre-Training Phase

We now establish which constant duration $K^{\prime}$ of playing $\bar{\pi}$
is sufficient to guarantee the desired strict feasibility of Eq. 6 (with the
choice of $K^{\prime}$ favoring readability over tightness). Note that the
conclusion holds conditioned on the success event $G$.

See 1

###### Proof.

Condition on the success event $G$, which by Lemma 2 happens with probability
$\geq 1-\delta$. Then by construction of $G$, the assumptions (a) and (b) in
Lemma 13 are met for $l=d_{i}$ for all constraints $i$. By Lemma 14 also the
assumption (c) in Lemma 13 is met with $\hat{p}_{k}:=\tilde{p}_{k}$ from the
$k$-th iteration of OptAug-CMDP. Thus, the conclusion from Lemma 13 holds for
$\pi=\bar{\pi}$ and $l_{h}(s,a)=d_{i,h}(s,a)$ (for all $i\in[I]$) and we have
for all $i\in[I]$ and $k\geq K^{\prime}$

$\displaystyle|V^{\pi}(d_{i},p)-V^{\pi}(\tilde{d}_{i,k},\tilde{p}_{k})|\leq
b(K^{\prime})^{-1/2}+a(K^{\prime})^{-1},$

where

$\displaystyle
b=\tilde{O}\left(\sqrt{\mathcal{N}SAH^{3}}\right),\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ a=\tilde{O}\left((H\sqrt{\mathcal{N}}+S)SAH\right).$

Thus, if
$K^{\prime}\geq\max\left\\{\frac{2(H\sqrt{\mathcal{N}}+S)SAH}{(1-\nu)\gamma},\frac{4\mathcal{N}SAH^{3}}{(1-\nu)^{2}\gamma^{2}}\right\\}$,
we have

$\displaystyle|V^{\bar{\pi}}(d_{i},p)-V^{\bar{\pi}}(\tilde{d}_{i,k},\tilde{p}_{k})|\leq\tilde{O}((1-\nu)\gamma).$

By further correcting for the missing polylogarithmic terms, this shows that
there exists
$K^{\prime}=\tilde{O}\left(\max\left\\{\frac{(H\sqrt{\mathcal{N}}+S)SAH}{(1-\nu)\gamma},\frac{\mathcal{N}SAH^{3}}{(1-\nu)^{2}\gamma^{2}}\right\\}\right)$
such that for all $i\in[I]$ and $k\geq K^{\prime}$, we have

$\displaystyle|V^{\bar{\pi}}(d_{i},p)-V^{\bar{\pi}}(\tilde{d}_{i,k},\tilde{p}_{k})|\leq(1-\nu)\gamma.$

At the same time, Assumption 1 guarantees

$\displaystyle V^{\bar{\pi}}(d_{i},p)\leq\alpha_{i}-\gamma.$

Hence

$\displaystyle V^{\bar{\pi}}(\tilde{d}_{i,k},\tilde{p}_{k})=$ $\displaystyle
V^{\bar{\pi}}(\tilde{d}_{i,k},\tilde{p}_{k})-V^{\bar{\pi}}(d_{i},p)+V^{\bar{\pi}}(d_{i},p)$
$\displaystyle\leq$ $\displaystyle(1-\nu)\gamma+\alpha_{i}-\gamma$
$\displaystyle=$ $\displaystyle\alpha_{i}-\nu\gamma,$

which proves the claim. ∎

######  Remark 2.

Notice that we chose $K^{\prime}$ such that both the terms
$b(K^{\prime})^{-1/2}$ and $a(K^{\prime})^{-1}$ are less than $1/2$, which is
sufficient. For a tighter but less concise bound, we can alternatively solve
the quadratic equation

$\displaystyle b(K^{\prime})^{-1/2}+a(K^{\prime})^{-1}\leq(1-\nu)\gamma$ (28)

for $K^{\prime}$ to obtain the smallest possible pre-training time, up to
polylogarithmic factors. Furthermore, note that since $a$, $b$ are only
specified in $\tilde{O}$-notation, we only have an asymptotic bound up to
polylogarithmic factors on how large to choose $K^{\prime}$. An exact bound
could be established by carrying along all factors dropped in the
$\tilde{O}$-notation, but for brevity we only specify how large to choose
$K^{\prime}$ asymptotically. In practice, one can take the bound above and
choose $K^{\prime}$ slightly larger.

####  D.2 Iteration Complexity of the Inner Method

Recall Proposition 1:

See 1

In Corollary 1, we prove Proposition 1 by showing that the method proposed in
Appendix B achieves the desired iteration complexity for solving Eq. 4. As
seen in Section B.1, every iteration of the Frank-Wolfe scheme InnerOpt-FW
(Algorithm 3) above can be performed efficiently via DP, i.e., in (low-degree)
polynomial time in the parameters defining the CMDP. To analyze the number of
such Frank-Wolfe iterations needed to reach an $\epsilon_{k}$-close solution,
we recall the following result due to Jaggi (2013).

######  Theorem 6.

The iterates $(z_{k})_{k\geq 0}$ of the Frank-Wolfe algorithm with an exact
LMO applied to a convex objective $f\colon\mathcal{D}\to\mathbb{R}$ (with
closed, convex and bounded domain $\mathcal{D}\subset\mathbb{R}^{d}$) satisfy

$\displaystyle f(z_{k})-f(z^{*})\leq\frac{2C_{f}}{k+2},$ (29)

where $z^{*}$ is a minimizer of $f$ over $\mathcal{D}$ and $C_{f}$ is the
curvature constant of $f$.
Moreover, if $\nabla f$ is $L$-Lipschitz continuous w.r.t. an arbitrary norm
$\|\cdot\|_{c}$ on $\mathbb{R}^{d}$, then

$\displaystyle C_{f}\leq\text{diam}_{\|\cdot\|_{c}}(\mathcal{D})^{2}L.$ (30)

In our case, this yields the following bound on the iteration complexity of
the inner optimization procedure.

######  Corollary 1.

After $T=\frac{2\eta_{k}IS^{2}AH}{\epsilon_{k}}$ Frank-Wolfe steps, InnerOpt-
FW returns an $\epsilon_{k}$-close solution to the inner problem (Eq. 4).

###### Proof.

Consider the problem of minimizing $f$ over $Z$, as defined in Section B.1.
Let $y,z\in Z$. With respect to $\|\cdot\|_{c}=\|\cdot\|_{\infty}$ we have,
using the expression of the gradients from Eq. 22,

$\displaystyle\|\nabla f(y)-\nabla f(z)\|_{\infty}$ $\displaystyle=$
$\displaystyle\|(\nabla f(y))(\cdot,\cdot,1,\cdot)-(\nabla
f(z))(\cdot,\cdot,1,\cdot)\|_{\infty}$ $\displaystyle=$
$\displaystyle\|\tilde{D}_{k}^{T}[\lambda_{k}+\eta_{k}(\tilde{D}_{k}\sum_{s^{\prime\prime}}y(s^{\prime\prime})-\alpha)]_{+}-\tilde{D}_{k}^{T}[\lambda_{k}+\eta_{k}(\tilde{D}_{k}\sum_{s^{\prime\prime}}z(s^{\prime\prime})-\alpha)]_{+}\|_{\infty}$
$\displaystyle\leq$
$\displaystyle\|\tilde{D}_{k}^{T}\|_{\infty}\cdot\|[\lambda_{k}+\eta_{k}(\tilde{D}_{k}\sum_{s^{\prime\prime}}y(s^{\prime\prime})-\alpha)]_{+}-[\lambda_{k}+\eta_{k}(\tilde{D}_{k}\sum_{s^{\prime\prime}}z(s^{\prime\prime})-\alpha)]_{+}\|_{\infty}$
$\displaystyle\text{and using}[a]_{+}-[b]_{+}\leq[a-b]_{+}\leq|a-b|$
$\displaystyle\leq$
$\displaystyle\|\tilde{D}_{k}^{T}\|_{1}\cdot\|[\lambda_{k}+\eta_{k}(\tilde{D}_{k}\sum_{s^{\prime\prime}}y(s^{\prime\prime})-\alpha)]-[\lambda_{k}+\eta_{k}(\tilde{D}_{k}\sum_{s^{\prime\prime}}z(s^{\prime\prime})-\alpha)]\|_{\infty}$
$\displaystyle=$
$\displaystyle\|\tilde{D}_{k}^{T}\|_{\infty}\cdot\eta_{k}\|\tilde{D}_{k}\sum_{s^{\prime\prime}}(y(s^{\prime\prime})-z(s^{\prime\prime}))\|_{\infty}$
$\displaystyle\leq$
$\displaystyle\|\tilde{D}_{k}^{T}\|_{\infty}\cdot\eta_{k}\|\tilde{D}_{k}\|_{\infty}\sum_{s^{\prime\prime}}\|y(s^{\prime\prime})-z(s^{\prime\prime})\|_{\infty}$
$\displaystyle\leq$ $\displaystyle SAH\cdot\eta_{k}\cdot I\cdot
S\|y-z\|_{\infty},$

where the final bound holds since the entries of $\tilde{D}_{k}$ are in
$[0,1]$. Thus, $\nabla f(\cdot)$ is $(S^{2}AH\cdot\eta_{k}\cdot I)$-Lipschitz
continuous and thus $f$ is $(S^{2}AH\cdot\eta_{k}\cdot I)$-smooth. Moreover,
for all $z\in Z$ we have $0\leq z_{h}(s,a,s^{\prime})\leq 1$ in every
component, so for $y,z\in Z$ we have $\|z-y\|_{\infty}\leq 1$. Thus
$\text{diam}_{\|\cdot\|_{\infty}}(Z)^{2}\leq 1$. Plugging both into Theorem 6
yields the result. ∎

Note that it may be possible to improve this bound by using a norm different
from $\|\cdot\|_{c}=\|\cdot\|_{\infty}$ for the analysis.

####  D.3 Main Result

Our main result shows that with probability $1-\delta$, OptAug-CMDP achieves a
regret that is sublinear in the number of episodes $K$ and polylogarithmic in
$1/\delta$.

See 1

###### Proof.

According to our regret decomposition (Observation 2), we have

$\displaystyle\mathcal{R}(K;c)$ $\displaystyle\leq
K^{\prime}H{+}\underbrace{\sum_{k=K^{\prime}+1}^{K}[V^{\pi_{k}}(c,p){-}V^{\pi_{k}}(\tilde{c}_{k},\tilde{p}_{k})]_{+}}_{\text{Estimation
Error}}{+}\underbrace{\sum_{k=K^{\prime}+1}^{K}[V^{\pi_{k}}(\tilde{c}_{k},\tilde{p}_{k}){-}V^{\pi^{*}}(c,p)]_{+}}_{\text{Optimization
Error}},$ $\displaystyle\mathcal{R}(K;d)$
$\displaystyle\leq\underbrace{\max_{i\in[I]}\sum_{k=K^{\prime}+1}^{K}[V^{\pi_{k}}(d_{i},p){-}V^{\pi_{k}}(\tilde{d}_{i,k},\tilde{p}_{k})]_{+}}_{\text{Estimation
Error}}{+}\underbrace{\max_{i\in[I]}\sum_{k=K^{\prime}+1}^{K}[V^{\pi_{k}}(\tilde{d}_{i,k},\tilde{p}_{k}){-}\alpha_{i}]_{+}}_{\text{Optimization
Error}}.$

Suppose the success event $G$ occurs, which happens with probability at least
$1-\delta$ as shown in Lemma 2. By Lemma 3, the estimation errors satisfy

$\displaystyle\sum_{k=K^{\prime}+1}^{K}[V^{\pi_{k}}(c,p)-V^{\pi_{k}}(\tilde{c}_{k},\tilde{p}_{k})]_{+}\leq$
$\displaystyle\tilde{O}\left(\sqrt{\mathcal{N}SAH^{3}K}+(H\sqrt{\mathcal{N}}+S)SAH\right),$
$\displaystyle\max_{i\in[I]}\sum_{k=K^{\prime}+1}^{K}\left[V^{\pi_{k}}(d_{i},p)-V^{\pi_{k}}(\tilde{d}_{i,k},\tilde{p}_{k})\right]_{+}\leq$
$\displaystyle\tilde{O}\left(\sqrt{\mathcal{N}SAH^{3}K}+(H\sqrt{\mathcal{N}}+S)SAH\right).$

By Lemma 7, the optimization errors satisfy

$\displaystyle\sum_{k=K^{\prime}+1}^{K}[V^{\pi_{k}}(\tilde{c}_{k},\tilde{p}_{k})-V^{\pi^{*}}(c,p)]_{+}\leq$
$\displaystyle\sum_{k=K^{\prime}+1}^{K}\bigg{(}\frac{(O(\sigma
k)+\sum_{t=K^{\prime}+1}^{k}\sqrt{2\eta_{t}\epsilon_{t}})^{2}}{2\eta_{k}}+\epsilon_{k}\bigg{)}\leq
O(\sqrt{K}),$
$\displaystyle\max_{i\in[I]}\sum_{k=K^{\prime}+1}^{K}[V^{\pi_{k}}(\tilde{d}_{i,k},\tilde{p}_{k})-\alpha_{i}]_{+}\leq$
$\displaystyle\sum_{k=K^{\prime}+1}^{K}\frac{O(\sigma
k)+\sum_{t=K^{\prime}+1}^{k}\sqrt{2\eta_{t}\epsilon_{k}}}{\eta_{k}}\leq
O(\sqrt{K}),$

where $\sigma=\frac{H}{\nu\gamma}$ and the term $O(\sigma k)$ can be replaced
by $(2+2(k-K^{\prime}))\sigma$. As shown in Lemma 7, we can choose step sizes
$\eta_{K^{\prime}+k}=\Theta(k^{2.5})$ and
$\epsilon_{K^{\prime}+k}=\Theta(1/\eta_{K^{\prime}+k})$ such that both of the
above bounds are $O(\sqrt{K})$ up to constant factors. Summing up concludes
the proof. ∎

######  Remark 3.

Note that while the bound for the estimation errors does not depend on the
choices for $\eta_{k}$ and $\epsilon_{k}$, the one for the optimization errors
does. For any such choice, the general regret bound we obtain reads

$\displaystyle\mathcal{R}(K;c)$
$\displaystyle\leq\tilde{O}\left(\sqrt{\mathcal{N}SAH^{3}K}+(H\sqrt{\mathcal{N}}+S)SAH+K^{\prime}H\right)$
$\displaystyle+\sum_{k=K^{\prime}+1}^{K}\bigg{(}\frac{(O(\sigma
k)+\sum_{t=K^{\prime}+1}^{k}\sqrt{2\eta_{t}\epsilon_{t}})^{2}}{2\eta_{k}}+\epsilon_{k}\bigg{)},$
(31) $\displaystyle\mathcal{R}(K;d)$
$\displaystyle\leq\tilde{O}\left(\sqrt{\mathcal{N}SAH^{3}K}+(H\sqrt{\mathcal{N}}+S)SAH\right)+\sum_{k=K^{\prime}+1}^{K}\frac{O(\sigma
k)+\sum_{t=K^{\prime}+1}^{k}\sqrt{2\eta_{t}\epsilon_{k}}}{\eta_{k}},$

where $\sigma=\frac{H}{\nu\gamma}$ and the term $O(\sigma k)$ can be replaced
by $(2+2(k-K^{\prime}))\sigma$.

We remark that there are multiple ways to choose $\eta_{k}$, $\epsilon_{k}$ in
the bound above that yield different regret guarantees and complexities of the
inner algorithm InnerOpt-FW. One possible way is to choose a decreasing
approximation error $\epsilon_{k}$ in every episode and $\eta_{k}$ large
enough so that the parameter-dependent terms above are of order $O(\sqrt{K})$.
This yields vanishing average regret for both the objective and the
constraints. One such choice is121212Note that if $\gamma$ is not known,
having an estimate of $\sigma=\frac{H}{\nu\gamma}$ that is larger than the
true value is clearly sufficient.

$\displaystyle\epsilon_{K^{\prime}+k}$
$\displaystyle:=\frac{1}{2\eta_{K^{\prime}+k}}\hskip 28.45274pt(k\geq 1),$
$\displaystyle\eta_{K^{\prime}+k}$ $\displaystyle:=((2+3k)\sigma)^{2.5}\hskip
28.45274pt(k\geq 1),$

as we discuss in Lemma 7.

It is worth noting that, when choosing $\eta_{k}$ very large and
$\epsilon_{k}$ very small, the bound we get on the parameter-dependent terms
in Eq. 31 gets better, and even becomes constant when choosing $\eta_{k}$,
$\epsilon_{k}$ exponential in $k-K^{\prime}$. However, the inner problem (Eq.
4) that we solve in every episode becomes computationally harder. This is due
to the changing smoothness of the objective (with respect to the occupancy
measure). Indeed, Proposition 1 quantifies the resulting iteration complexity,
formalizing this tradeoff between statistical guarantees and computational
efficiency. Thus, in practice, it is advised to choose $\eta_{k}$ as large
($\epsilon_{k}$ as small) as needed to ensure sublinear regret but as small as
possible to avoid a higher computational cost.

###  Appendix E Omitted Proofs for Section 4

####  E.1 Preliminaries

#####  E.1.1 Preliminary Confidence Bounds

Fix an arbitrary number of episodes $K$ and $0<\delta<1$, corresponding to a
confidence of $1-\delta$. Moreover, let $(\pi_{k})_{k=1}^{K}$ be the policies
according to which the optimistic estimates are updated (Section 3).

Define the following confidence sets

$\displaystyle B_{k,h}^{p}(s,a)$
$\displaystyle:=\left\\{\tilde{p}_{h}(\cdot|s,a)\in\Delta\left(\mathcal{S}\right)S\mid\forall
s^{\prime}\in\mathcal{S}\colon|\tilde{p}_{h}(s^{\prime}|s,a)-\bar{p}_{h}^{k-1}(s^{\prime}|s,a)|\leq\beta_{k,h}^{p}(s,a,s^{\prime})\right\\},$
$\displaystyle B_{k,h}^{c}(s,a)$
$\displaystyle:=\left[\bar{c}_{h}^{k-1}(s,a)-\beta_{k,h}^{c}(s,a),\bar{c}_{h}^{k-1}(s,a)+\beta_{k,h}^{c}(s,a)\right],$
$\displaystyle B_{i,k,h}^{d}(s,a)$
$\displaystyle:=\left[\bar{d}_{i,h}^{k-1}(s,a)-\beta_{i,k,h}^{d}(s,a),\bar{d}_{i,h}^{k-1}(s,a)+\beta_{i,k,h}^{d}(s,a)\right],$

where (derived using Hoeffding for the costs and empirical Bernstein for the
transitions)

$\displaystyle\beta_{k,h}^{p}(s,a,s^{\prime}):=$ $\displaystyle
2\sqrt{\frac{\bar{p}_{h}^{k-1}(s^{\prime}|s,a)(1-\bar{p}_{h}^{k-1}(s^{\prime}|s,a))L_{\delta}^{p}}{n_{h}^{k-1}(s,a)\vee
1}}+\frac{\frac{14}{3}L_{\delta}^{p}}{n_{h}^{k-1}(s,a)\vee 1},$
$\displaystyle\beta_{k,h}^{c}(s,a):=\beta_{i,k,h}^{d}(s,a):=$
$\displaystyle\sqrt{\frac{L_{\delta}}{n_{h}^{k-1}(s,a)\vee 1}},$

with

$\displaystyle L_{\delta}^{p}:=\log\left(\frac{6SAHK}{\delta}\right)$
$\displaystyle\hskip
28.45274ptL_{\delta}:=\log\left(\frac{6SAH(I+1)K}{\delta}\right).$

We want that, with probability at least $1-\delta$, the true MDP is contained
within these bounds across all $k\in[K]$. This will be needed for bounding the
optimization error.

With the same thresholds $\beta_{k,h}^{p}$, $\beta_{k,h}^{c}$,
$\beta_{i,k,h}^{d}$ as above we define the following failure events

$\displaystyle F_{k}^{p}$ $\displaystyle:=\left\\{\exists
s,a,s^{\prime},h\colon|p_{h}(s^{\prime}|s,a)-\bar{p}_{h}^{k-1}(\cdot|s,a)|>\beta_{k,h}^{p}(s,a,s^{\prime})\right\\},$
$\displaystyle F_{k}^{c}$ $\displaystyle:=\left\\{\exists
s,a,h\colon|\bar{c}_{h}^{k-1}(s,a)-c_{h}(s,a)|>\beta_{k,h}^{c}(s,a)\right\\},$
$\displaystyle F_{k}^{d}$ $\displaystyle:=\left\\{\exists
s,a,i,h\colon|\bar{d}_{i,h}^{k-1}(s,a)-d_{i,h}(s,a)|>\beta_{k,h}^{d}(s,a)\right\\},$
$\displaystyle F_{k}^{N}$ $\displaystyle:=\left\\{\exists s,a,h\colon
n_{h}^{k-1}(s,a)\leq\sum_{j<k}q_{h}^{\pi_{j}}(s,a;p)-H\log\left(\frac{SAH}{\delta^{\prime}}\right)\right\\},$

where we set $\delta^{\prime}:=\delta/3$. With this notation, set
$F^{p}:=\cup_{k=1}^{K}F^{p}_{k}$, $F^{c}:=\cup_{k=1}^{K}F^{c}_{k}$,
$F^{d}:=\cup_{k=1}^{K}F^{d}_{k}$, $F^{N}:=\cup_{k=1}^{K}F^{N}_{k}$ and finally
denote the event that none of the failure events ever occurs by

$\displaystyle G:=\overline{\left(F^{p}\bigcup F^{c}\bigcup F^{d}\bigcup
F^{N}\right)},$

which we will refer to as the success event.

By construction of $G$ and the optimistic estimates, we immediately have the
following.

######  Observation 1.

Conditioned on the success event $G$, for every $k\in[K]$ the CMDP with cost
$\tilde{c}_{k}$ and constraint costs $(\tilde{d}_{i,k})_{i\in[I]}$ is
optimistic and all $B_{k}^{p}(s,a)$ contain the true respective transition
probability distribution, i.e.,

$\displaystyle\tilde{c}_{k}\leq c,\hskip 28.45274pt\tilde{d}_{i,k}\leq
d_{i,k},\hskip 28.45274pt\text{and}\hskip 28.45274ptp\in B_{k}^{p},$

where $B_{k}^{p}:=\\{\tilde{p}\mid\forall
s,a,h\colon\tilde{p}_{h}(\cdot|s,a)\in B_{k,h}^{p}(s,a)\\}$ is the set of
plausible transition probabilities.

Concentration bounds on the individual random variables together with a union
bound over all indices now allow us to establish the following result. In
Section D.3, we show that conditioned on $G$, the regrets are sublinear in $K$
and polylogarithmic in $1/\delta$.

See 2

###### Proof.

Efroni et al. (2020, Appendix A.1) give a proof of this. Note that the proof
does not require any specific properties of the used policy iterates
$(\pi_{k})_{k\in[K]}$ but only uses that the collected costs and transitions
are i.i.d.. ∎

Moreover, we have the following result, which will allow us to bound the
estimation error. The absolute constants could in fact be specified via a
short calculation, but we omit this for brevity.

######  Lemma 14 (Lemma 8, Jin et al. (2019)).

In the setup above, conditioned on $G$, there exist absolute constants
$C_{1},C_{2}>0$ such that for all indices $k,h,s,a,s^{\prime}$ we have

$\displaystyle|p_{h}(s^{\prime}|s,a)-\bar{p}_{h}^{k-1}(s^{\prime}|s,a)|\leq
C_{1}\sqrt{\frac{p_{h}(s^{\prime}|s,a)L_{\delta}^{p}}{n_{h}^{k-1}(s,a)\vee
1}}+C_{2}\frac{L_{\delta}^{p}}{n_{h}^{k-1}(s,a)\vee 1},$

with $L_{\delta}^{p}=\log\left(\frac{6SAHK}{\delta}\right)$ as before.

###### Proof.

We refer to Jin et al. (2019, Lemma 8) for a proof. ∎

#####  E.1.2 Regret Decomposition

The simple observation that we can decompose the regrets can be seen as
follows.

######  Observation 2 (Regret decomposition).

$\displaystyle\mathcal{R}(K;c)$ $\displaystyle\leq
K^{\prime}H{+}\underbrace{\sum_{k=K^{\prime}+1}^{K}[V^{\pi_{k}}(c,p){-}V^{\pi_{k}}(\tilde{c}_{k},\tilde{p}_{k})]_{+}}_{\text{Estimation
Error}}{+}\underbrace{\sum_{k=K^{\prime}+1}^{K}[V^{\pi_{k}}(\tilde{c}_{k},\tilde{p}_{k}){-}V^{\pi^{*}}(c,p)]_{+}}_{\text{Optimization
Error}}$ $\displaystyle\mathcal{R}(K;d)$
$\displaystyle\leq\underbrace{\max_{i\in[I]}\sum_{k=K^{\prime}+1}^{K}[V^{\pi_{k}}(d_{i},p){-}V^{\pi_{k}}(\tilde{d}_{i,k},\tilde{p}_{k})]_{+}}_{\text{Estimation
Error}}{+}\underbrace{\max_{i\in[I]}\sum_{k=K^{\prime}+1}^{K}[V^{\pi_{k}}(\tilde{d}_{i,k},\tilde{p}_{k}){-}\alpha_{i}]_{+}}_{\text{Optimization
Error}}$

###### Proof.

We first split the regrets between the two phases of the algorithm.

$\displaystyle\mathcal{R}(K;c)$
$\displaystyle=\underbrace{\sum_{k=1}^{K^{\prime}}[V^{\pi_{k}}(c,p)-V^{\pi^{*}}(c,p)]_{+}}_{\text{Pre-
Training, }\leq
K^{\prime}H}+\underbrace{\sum_{k=K^{\prime}+1}^{K}[V^{\pi_{k}}(c,p)-V^{\pi^{*}}(c,p)]_{+}}_{\text{Optimistic
Exploration}}$ $\displaystyle\mathcal{R}(K;d)$
$\displaystyle\leq\underbrace{\max_{i\in[I]}\sum_{k=1}^{K^{\prime}}[V^{\pi_{k}}(d_{i},p)-\alpha_{i}]_{+}}_{\text{Pre-
Training,
}=0}+\underbrace{\max_{i\in[I]}\sum_{k=K^{\prime}+1}^{K}[V^{\pi_{k}}(d_{i},p)-\alpha_{i}]_{+}}_{\text{Optimistic
Exploration}}$

We can trivially bound the objective regret during the pre-training phase by
$K^{\prime}H$ (since the expected costs are in $[0,1]$ and the time horizon is
$H$, so the value functions are in $[0,H]$). Since $\bar{\pi}$ is strictly
feasible, there is no constraint regret during pre-training.

We now focus on the regrets incurred in the optimistic exploration phase. We
split the sum and use that $[a+b]_{+}\leq[a]_{+}+[b]_{+}$. For the objective
regret we have

$\displaystyle\mathcal{R}(K;c)=$ $\displaystyle
K^{\prime}H+\sum_{k=K^{\prime}+1}^{K}[V^{\pi_{k}}(c,p)-V^{\pi^{*}}(c,p)]_{+}$
$\displaystyle=$ $\displaystyle
K^{\prime}H+\sum_{k=K^{\prime}+1}^{K}[V^{\pi_{k}}(c,p)-V^{\pi_{k}}(\tilde{c}_{k},\tilde{p}_{k})+V^{\pi_{k}}(\tilde{c}_{k},\tilde{p}_{k})-V^{\pi^{*}}(c,p)]_{+}$
$\displaystyle\leq$ $\displaystyle
K^{\prime}H+\sum_{k=K^{\prime}+1}^{K}[V^{\pi_{k}}(c,p)-V^{\pi_{k}}(\tilde{c}_{k},\tilde{p}_{k})]_{+}+\sum_{k=K^{\prime}+1}^{K}[V^{\pi_{k}}(\tilde{c}_{k},\tilde{p}_{k})-V^{\pi^{*}}(c,p)]_{+}$

and similarly, for the constraint regret we get

$\displaystyle\mathcal{R}(K;d)=$ $\displaystyle
0+\max_{i\in[I]}\left(\sum_{k=K^{\prime}+1}^{K}\left[V^{\pi_{k}}(d_{i},p)-\alpha_{i}\right]_{+}\right)$
$\displaystyle=$
$\displaystyle\max_{i\in[I]}\sum_{k=K^{\prime}+1}^{K}\left[V^{\pi_{k}}(d_{i},p)-\alpha_{i}-(V^{\pi_{k}}(\tilde{d}_{i,k},\tilde{p}_{k})-\alpha_{i})+(V^{\pi_{k}}(\tilde{d}_{i,k},\tilde{p}_{k})-\alpha_{i})\right]_{+}$
$\displaystyle\leq$
$\displaystyle\max_{i\in[I]}\left(\sum_{k=K^{\prime}+1}^{K}\left[V^{\pi_{k}}(d_{i},p)-V^{\pi_{k}}(\tilde{d}_{i,k},\tilde{p}_{k})\right]_{+}+\sum_{k=K^{\prime}+1}^{K}\left[V^{\pi_{k}}(\tilde{d}_{i,k},\tilde{p}_{k})-\alpha_{i}\right]_{+}\right)$
$\displaystyle\leq$
$\displaystyle\max_{i\in[I]}\sum_{k=K^{\prime}+1}^{K}\left[V^{\pi_{k}}(d_{i},p)-V^{\pi_{k}}(\tilde{d}_{i,k},\tilde{p}_{k})\right]_{+}+\max_{i\in[I]}\sum_{k=K^{\prime}+1}^{K}\left[V^{\pi_{k}}(\tilde{d}_{i,k},\tilde{p}_{k})-\alpha_{i}\right]_{+}.$

∎

####  E.2 Omitted Proofs for Section 4.1

We leverage the on-policy error bound from Lemma 10 and the preliminaries from
Section E.1.1 to establish the desired bound on the estimation errors.

See 3

###### Proof.

Condition on the success event $G$. Then by construction of $G$, the
assumptions (a) and (b) in Lemma 10 are met for $l=c$ and $l=d_{i}$ for all
constraints $i\in[I]$. By Lemma 14, also assumption (c) in Lemma 10 is met
with $\hat{p}_{k}:=\tilde{p}_{k}$ from the $k$-th iteration of OptAug-CMDP.

First, consider the terms
$[V^{\pi_{k}}(c,p)-V^{\pi_{k}}(\tilde{c}_{k},\tilde{p}_{k})]_{+}$. For the
cost $l=c$, the values of the true and the estimated MDPs are
$V^{\pi_{k}}(c,p)$ and $V^{\pi_{k}}(\tilde{c}_{k},\tilde{p}_{k})$,
respectively. Thus, invoking Lemma 10 we find

$\displaystyle\sum_{k=K^{\prime}+1}^{K}[V^{\pi_{k}}(c,p)-V^{\pi_{k}}(\tilde{c}_{k},\tilde{p}_{k})]_{+}\leq$
$\displaystyle\sum_{k=K^{\prime}+1}^{K}|V^{\pi_{k}}(c,p)-V^{\pi_{k}}(\tilde{c}_{k},\tilde{p}_{k})|$
$\displaystyle\leq$
$\displaystyle\sum_{k=1}^{K}|V^{\pi_{k}}(c,p)-V^{\pi_{k}}(\tilde{c}_{k},\tilde{p}_{k})|$
$\displaystyle\leq$
$\displaystyle\tilde{O}\left(\sqrt{\mathcal{N}SAH^{3}K}+(H\sqrt{\mathcal{N}}+S)SAH\right).$

Similarly, let $i\in[I]$ and consider the terms
$[V^{\pi_{k}}(d_{i},p)-V^{\pi_{k}}(\tilde{d}_{i,k},\tilde{p}_{k})]_{+}$. For
the cost $l=d_{i}$, the values of the true and the estimated MDPs are
$V^{\pi_{k}}(d_{i},p)$ and $V^{\pi_{k}}(\tilde{d}_{i,k},\tilde{p}_{k})$,
respectively. Thus, invoking Lemma 10 we find

$\displaystyle\sum_{k=K^{\prime}+1}^{K}[V^{\pi_{k}}(d_{i},p)-V^{\pi_{k}}(\tilde{d}_{i,k},\tilde{p}_{k})]_{+}\leq$
$\displaystyle\sum_{k=1}^{K}|V^{\pi_{k}}(d_{i},p)-V^{\pi_{k}}(\tilde{d}_{i,k},\tilde{p}_{k})|$
$\displaystyle\leq$
$\displaystyle\tilde{O}\left(\sqrt{\mathcal{N}SAH^{3}K}+(H\sqrt{\mathcal{N}}+S)SAH\right).$

∎

####  E.3 Omitted Proofs for Section 4.2

For notational convenience, we write $D=(d_{i})_{i\in[I]}$ and
$\tilde{D}_{k}=(\tilde{d}_{i,k})_{i\in[I]}$ throughout this section.

#####  E.3.1 Preliminary Bounds

Recall that in OptAug-CMDP, we find an $\epsilon_{k}$-close solution to the
inner problem Eq. 4 in every episode $k\in\\{K^{\prime}+1,\dots,K\\}$.

See 4

###### Proof.

We first bound the error for the objective cost. Let
$k\in\\{K^{\prime}+1,\dots,K\\}$. Conditioned on the success event, we have
(componentwise) $c\geq\tilde{c}_{k}$, $D\geq\tilde{D}_{k}$ and $p\in
B^{p}_{k}$ (Observation 1), and thus

$\displaystyle V^{\pi^{*}}(c,p)$ $\displaystyle=$
$\displaystyle\left(V^{\pi^{*}}(c,p)+\frac{1}{2\eta_{k}}\|[\lambda_{k}+\eta_{k}(V^{\pi^{*}}(D,p)-\alpha)]_{+}\|^{2}\right)-\frac{1}{2\eta_{k}}\|[\lambda_{k}+\eta_{k}(V^{\pi^{*}}(D,p)-\alpha)]_{+}\|^{2}$
$\displaystyle\geq$
$\displaystyle\left(V^{\pi^{*}}(\tilde{c}_{k},p)+\frac{1}{2\eta_{k}}\|[\lambda_{k}+\eta_{k}(V^{\pi^{*}}(\tilde{D}_{k},p)-\alpha)]_{+}\|^{2}\right)-\frac{1}{2\eta_{k}}\|[\lambda_{k}+\eta_{k}(V^{\pi^{*}}(D,p)-\alpha)]_{+}\|^{2}$
$\displaystyle\geq$ $\displaystyle\min_{\begin{subarray}{c}\pi\in\Pi\\\
p^{\prime}\in
B_{k}^{p}\end{subarray}}\left(V^{\pi}(\tilde{c}_{k},p^{\prime})+\frac{1}{2\eta_{k}}\|[\lambda_{k}+\eta_{k}(V^{\pi}(\tilde{D}_{k},p^{\prime})-\alpha)]_{+}\|^{2}\right)$
$\displaystyle-\frac{1}{2\eta_{k}}\|[\lambda_{k}+\eta_{k}(V^{\pi^{*}}(D,p)-\alpha)]_{+}\|^{2}$
$\displaystyle\geq$
$\displaystyle\left(V^{\pi_{k}}(\tilde{c}_{k},\tilde{p}_{k})+\frac{1}{2\eta_{k}}\|[\lambda_{k}+\eta_{k}(V^{\pi_{k}}(\tilde{D}_{k},\tilde{p}_{k})-\alpha)]_{+}\|^{2}-\epsilon_{k}\right)$
$\displaystyle-\frac{1}{2\eta_{k}}\|[\lambda_{k}+\eta_{k}(V^{\pi^{*}}(D,p)-\alpha)]_{+}\|^{2}$
$\displaystyle=$ $\displaystyle
V^{\pi_{k}}(\tilde{c}_{k},\tilde{p}_{k})-\epsilon_{k}+\frac{1}{2\eta_{k}}\|[\lambda_{k}+\eta_{k}(V^{\pi_{k}}(\tilde{D}_{k},\tilde{p}_{k})-\alpha)]_{+}\|^{2}$
$\displaystyle-\frac{1}{2\eta_{k}}\|[\lambda_{k}+\eta_{k}(V^{\pi^{*}}(D,p)-\alpha)]_{+}\|^{2},$

where the first inequality is due to optimism and monotonicity of
$\|[\cdot]_{+}\|^{2}$, the second due to $p\in B^{p}_{k}$, and the third due
to the $\epsilon_{k}$-closeness of $\pi_{k}$, $\tilde{p}_{k}$. Now since
$\pi^{*}$ is primal-feasible we have $V^{\pi^{*}}(D,p)-\alpha\leq 0$ and thus
$\|[\lambda_{k}+\eta_{k}(V^{\pi^{*}}(D,p)-\alpha)]_{+}\|^{2}\leq\|\lambda_{k}\|^{2}$
by monotonicity of $\|[\cdot]_{+}\|^{2}$. Plugging in the update for
$\lambda_{k+1}$ thus shows

$\displaystyle\frac{1}{2\eta_{k}}\|[\lambda_{k}+\eta_{k}(V^{\pi_{k}}(\tilde{D}_{k},\tilde{p}_{k})-\alpha)]_{+}\|^{2}-\frac{1}{2\eta_{k}}\|[\lambda_{k}+\eta_{k}(V^{\pi^{*}}(D,p)-\alpha)]_{+}\|^{2}$
$\displaystyle\geq$
$\displaystyle\frac{1}{2\eta_{k}}\|[\lambda_{k}+\eta_{k}(V^{\pi_{k}}(\tilde{D}_{k},\tilde{p}_{k})-\alpha)]_{+}\|^{2}-\frac{1}{2\eta_{k}}\|\lambda_{k}\|^{2}$
$\displaystyle=$
$\displaystyle\frac{1}{2\eta_{k}}\|\lambda_{k+1}\|^{2}-\frac{1}{2\eta_{k}}\|\lambda_{k}\|^{2},$

concluding the proof after plugging this into the previous inequality and
rearranging.

We now proceed by proving the bound on the constraint cost. Let
$k\in\\{K^{\prime}+1,\dots,K\\}$. Let $i\in[I]$ and recall that
$\lambda_{k+1}=[\lambda_{k}+\eta_{k}(V^{\pi_{k}}(\tilde{D}_{k},\tilde{p}_{k})-\alpha)]_{+}$.
If $\lambda_{k+1}(i)>0$, then we have
$\lambda_{k+1}(i)-\lambda_{k}(i)=\eta_{k}(V^{\pi_{k}}(\tilde{d}_{i,k},\tilde{p}_{k})-\alpha_{i})$
with equality. On the other hand, if $\lambda_{k+1}(i)=0$, then
$\lambda_{k}(i)+\eta_{k}(V^{\pi_{k}}(\tilde{d}_{i,k},\tilde{p}_{k})-\alpha_{i})\leq
0$ and thus
$\lambda_{k+1}(i)-\lambda_{k}(i)=-\lambda_{k}(i)\geq(\lambda_{k}(i)+\eta_{k}(V^{\pi_{k}}(\tilde{d}_{i,k},\tilde{p}_{k})-\alpha_{i}))-\lambda_{k}(i)=\eta_{k}(V^{\pi_{k}}(\tilde{d}_{i,k},\tilde{p}_{k})-\alpha_{i})$.
Thus in both cases
$\lambda_{k+1}(i)-\lambda_{k}(i)\geq\eta_{k}(V^{\pi_{k}}(\tilde{d}_{i,k},\tilde{p}_{k})-\alpha_{i})$,
which proves the claim. ∎

#####  E.3.2 Bounding the Dual Iterates

In order to prove Lemma 19, which implies Lemma 5, we first establish (Lemmas
15, 16 and 17), following the analysis of Xu (2021).

######  Lemma 15.

Let $k\in\\{K^{\prime}+1,\dots,K\\}$. In the $k$-th iteration of OptAug-CMDP
we have, for all $\lambda\in\mathbb{R}_{\geq 0}^{I}$,

$\displaystyle\frac{1}{2\eta_{k}}\left(\|\lambda_{k+1}-\lambda\|^{2}-\|\lambda_{k}-\lambda\|^{2}+\|\lambda_{k+1}-\lambda_{k}\|^{2}\right)$
$\displaystyle=\sum_{i=1}^{I}(\lambda_{k+1}(i)-\lambda(i))\max\\{-\frac{\lambda_{k}(i)}{\eta_{k}},(V^{\pi_{k}}(\tilde{D}_{k},\tilde{p}_{k})-\alpha)_{i}\\}.$

###### Proof.

Using $2u^{T}v=\|u\|^{2}+\|v\|^{2}-\|u-v\|^{2}$ with
$u=\lambda_{k+1}-\lambda_{k}$, $v=\lambda_{k+1}-\lambda$ we find that the LHS
in the Lemma reads

$\displaystyle\frac{1}{2\eta_{k}}\left(\|\lambda_{k+1}-\lambda\|^{2}-\|\lambda_{k}-\lambda\|^{2}+\|\lambda_{k+1}-\lambda_{k}\|^{2}\right)=\frac{1}{2\eta_{k}}2(\lambda_{k+1}-\lambda)^{T}(\lambda_{k+1}-\lambda_{k}).$

The update rule of for $\lambda_{k+1}$ can equivalently be written as

$\displaystyle\lambda_{k+1}(i)=\lambda_{k}(i)+\eta_{k}\max\\{-\frac{\lambda_{k}(i)}{\eta_{k}},(V^{\pi_{k}}(\tilde{D}_{k},\tilde{p}_{k})-\alpha)_{i}\\},$

for all $i\in[I]$, from which we obtain
$\lambda_{k+1}(i)-\lambda_{k}(i)=\eta_{k}\max\\{-\frac{\lambda_{k}(i)}{\eta_{k}},(V^{\pi_{k}}(\tilde{D}_{k},\tilde{p}_{k})-\alpha)_{i}\\}$.
Plugging this into the equation above proves the Lemma. ∎

######  Lemma 16.

Let $k\in\\{K^{\prime}+1,\dots,K\\}$. In the $k$-th iteration of OptAug-CMDP
we have for, any $\lambda\in\mathbb{R}_{\geq 0}^{I}$,

$\displaystyle\sum_{i=1}^{I}(\lambda_{k+1}(i)-\lambda(i))\max\\{-\frac{\lambda_{k}(i)}{\eta_{k}},(V^{\pi_{k}}(\tilde{D}_{k},\tilde{p}_{k})-\alpha)_{i}\\}$
$\displaystyle\leq\sum_{i=1}^{I}(\lambda_{k+1}(i)-\lambda(i))(V^{\pi_{k}}(\tilde{D}_{k},\tilde{p}_{k})-\alpha)_{i}.$

###### Proof.

Fix $k$ and set
$I_{+}:=\\{i\in[I]\mid\lambda_{k}(i)+\eta_{k}(V^{\pi_{k}}(\tilde{D}_{k},\tilde{p}_{k})-\alpha)_{i}>0\\}=\\{i\in[I]\mid-\frac{\lambda_{k}(i)}{\eta_{k}}<(V^{\pi_{k}}(\tilde{D}_{k},\tilde{p}_{k})-\alpha)_{i}\\}$
and $I_{-}:=[I]\setminus I_{+}$. Then subtracting the RHS from the LHS in the
Lemma we get

$\displaystyle\sum_{i=1}^{I}(\lambda_{k+1}(i)-\lambda(i))\max\\{-\frac{\lambda_{k}(i)}{\eta_{k}},(V^{\pi_{k}}(\tilde{D}_{k},\tilde{p}_{k})-\alpha)_{i}\\}$
$\displaystyle-\sum_{i=1}^{I}(\lambda_{k+1}(i)-\lambda(i))(V^{\pi_{k}}(\tilde{D}_{k},\tilde{p}_{k})-\alpha)_{i}$
$\displaystyle=$ $\displaystyle\sum_{i\in
I_{+}}(\lambda_{k+1}(i)-\lambda(i))((V^{\pi_{k}}(\tilde{D}_{k},\tilde{p}_{k})-\alpha)_{i}-(V^{\pi_{k}}(\tilde{D}_{k},\tilde{p}_{k})-\alpha)_{i})$
$\displaystyle+\sum_{i\in
I_{-}}\lambda(i)((V^{\pi_{k}}(\tilde{D}_{k},\tilde{p}_{k})-\alpha)_{i}+\frac{\lambda_{k}(i)}{\eta_{k}})$
$\displaystyle=$ $\displaystyle\sum_{i\in
I_{-}}\lambda(i)((V^{\pi_{k}}(\tilde{D}_{k},\tilde{p}_{k})-\alpha)_{i}+\frac{\lambda_{k}(i)}{\eta_{k}}),$

and using that $\lambda\geq 0$ as well as
$(V^{\pi_{k}}(\tilde{D}_{k},\tilde{p}_{k})-\alpha)_{i}+\frac{\lambda_{k}(i)}{\eta_{k}}\leq
0$ for $i\in I_{-}$ shows that this is $\leq 0$, which proves the claim. ∎

Combining the previous two lemmas we find the analogous result of the one-step
progress inequality of the standard inexact augmented Lagrangian method
analysis:

######  Lemma 17 (One-step progress of iALM).

Let $k\in\\{K^{\prime}+1,\dots,K\\}$. In step $k$ of OptAug-CMDP, for all
$\pi\in\Pi$ and all $\lambda\geq 0$ we have

$\displaystyle
V^{\pi_{k}}(\tilde{c}_{k},\tilde{p}_{k})+\lambda^{T}(V^{\pi_{k}}(\tilde{D}_{k},\tilde{p}_{k})-\alpha)+\frac{1}{2\eta_{k}}\|\lambda_{k+1}-\lambda\|^{2}$
$\displaystyle\leq\tilde{L}_{k}(\pi,\lambda_{k})+\frac{1}{2\eta_{k}}\|\lambda_{k}-\lambda\|^{2}+\epsilon_{k},$

where for notational convenience

$\displaystyle\tilde{L}_{k}(\pi,\lambda):=V^{\pi}(\tilde{c}_{k},\tilde{p}_{k})+\frac{1}{2\eta_{k}}\|[\lambda+\eta_{k}(V^{\pi}(\tilde{D}_{k},\tilde{p}_{k})-\alpha)]_{+}\|^{2}-\frac{1}{2\eta_{k}}\|\lambda\|^{2}.$

###### Proof.

By $\epsilon_{k}$-closeness, for all $\pi\in\Pi$ we have

$\displaystyle
V^{\pi_{k}}(\tilde{c}_{k},\tilde{p}_{k})+\frac{1}{2\eta_{k}}\|\lambda_{k+1}\|\leq$
$\displaystyle
V^{\pi}(\tilde{c}_{k},\tilde{p}_{k})+\frac{1}{2\eta_{k}}\|\left[\lambda_{k}+\eta_{k}(V^{\pi}(\tilde{D}_{k},\tilde{p}_{k})-\alpha)]_{+}\right\|^{2}+\epsilon_{k}$
$\displaystyle=$
$\displaystyle\tilde{L}_{k}(\pi,\lambda_{k})+\frac{1}{2\eta_{k}}\|\lambda_{k}\|^{2}+\epsilon_{k}.$
(32)

In addition, again by distinguishing between indices in $I_{+}$ and $I_{-}$
(see proof of Lemma 16), we see

$\displaystyle\frac{1}{2\eta_{k}}\|[\lambda_{k}+\eta_{k}(V^{\pi_{k}}(\tilde{D}_{k},\tilde{p}_{k})-\alpha)]_{+}\|^{2}-\frac{1}{2\eta_{k}}\|\lambda_{k}\|^{2}$
$\displaystyle-\sum_{i\in[I]}[\lambda_{k}(i)+\eta_{k}(V^{\pi_{k}}(\tilde{D}_{k},\tilde{p}_{k})-\alpha)_{i}]_{+}(V^{\pi_{k}}(\tilde{D}_{k},\tilde{p}_{k})-\alpha)_{i}$
$\displaystyle=$ $\displaystyle\frac{1}{2\eta_{k}}\sum_{i\in
I_{+}}\bigg{(}(\lambda_{k}(i)+\eta_{k}(V^{\pi_{k}}(\tilde{D}_{k},\tilde{p}_{k})-\alpha)_{i})^{2}-\lambda_{k}(i)^{2}$
$\displaystyle-2(\lambda_{k}(i)+\eta_{k}(V^{\pi_{k}}(\tilde{D}_{k},\tilde{p}_{k})-\alpha)_{i})\eta_{k}(V^{\pi_{k}}(\tilde{D}_{k},\tilde{p}_{k})-\alpha)_{i}\bigg{)}-\frac{1}{2\eta_{k}}\sum_{i\in
I_{-}}\lambda_{k}(i)^{2}$ $\displaystyle=$
$\displaystyle\frac{1}{2\eta_{k}}\sum_{i\in
I_{+}}-(\eta_{k}(V^{\pi_{k}}(\tilde{D}_{k},\tilde{p}_{k})-\alpha)_{i})^{2}-\frac{1}{2\eta_{k}}\sum_{i\in
I_{-}}\lambda_{k}(i)^{2}$ $\displaystyle=$
$\displaystyle\frac{1}{2\eta_{k}}\sum_{i\in
I_{+}}-(\lambda_{k+1}(i)-\lambda_{k}(i))^{2}-\frac{1}{2\eta_{k}}\sum_{i\in
I_{-}}(\lambda_{k+1}(i)-\lambda_{k}(i))^{2}$ $\displaystyle=$
$\displaystyle-\frac{1}{2\eta_{k}}\|\lambda_{k+1}-\lambda_{k}\|^{2},$

and with Eq. 32 this shows

$\displaystyle
V^{\pi_{k}}(\tilde{c}_{k},\tilde{p}_{k})+\sum_{i\in[I]}[\lambda_{k}(i)+\eta_{k}(V^{\pi_{k}}(\tilde{D}_{k},\tilde{p}_{k})-\alpha)_{i}]_{+}(V^{\pi_{k}}(\tilde{D}_{k},\tilde{p}_{k})-\alpha)_{i}$
$\displaystyle-\frac{1}{2\eta_{k}}\|\lambda_{k+1}-\lambda_{k}\|^{2}$
$\displaystyle=$ $\displaystyle
V^{\pi_{k}}(\tilde{c}_{k},\tilde{p}_{k})+\frac{1}{2\eta_{k}}\|\lambda_{k+1}\|^{2}-\frac{1}{2\eta_{k}}\|\lambda_{k}\|^{2}$
$\displaystyle\overset{\lx@cref{creftype~refnum}{eq:lagr1}}{\leq}$
$\displaystyle\tilde{L}_{k}(\pi,\lambda_{k})+\epsilon_{k}.$ (33)

Now combining Lemma 15 and Lemma 16, we also have

$\displaystyle\frac{\|\lambda_{k+1}-\lambda\|^{2}-\|\lambda_{k}-\lambda\|^{2}+\|\lambda_{k+1}-\lambda_{k}\|^{2}}{2\eta_{k}}$
$\displaystyle\leq$
$\displaystyle\sum_{i\in[I]}([\lambda_{k}(i)+\eta_{k}(V^{\pi_{k}}(\tilde{D}_{k},\tilde{p}_{k})-\alpha)_{i}]_{+}-\lambda(i))(V^{\pi_{k}}(\tilde{D}_{k},\tilde{p}_{k})-\alpha)_{i}.$

Hence

$\displaystyle
V^{\pi_{k}}(\tilde{c}_{k},\tilde{p}_{k})+\frac{1}{2\eta_{k}}\|\lambda_{k+1}-\lambda\|^{2}-\frac{1}{2\eta_{k}}\|\lambda_{k}-\lambda\|^{2}$
$\displaystyle\leq$ $\displaystyle V^{\pi_{k}}(\tilde{c}_{k},\tilde{p}_{k})$
$\displaystyle+\sum_{i\in[I]}([\lambda_{k}(i)+\eta_{k}(V^{\pi_{k}}(\tilde{D}_{k},\tilde{p}_{k})-\alpha)_{i}]_{+}-\lambda(i))(V^{\pi_{k}}(\tilde{D}_{k},\tilde{p}_{k})-\alpha)_{i}$
$\displaystyle-\frac{1}{2\eta_{k}}\|\lambda_{k+1}-\lambda_{k}\|^{2}$
$\displaystyle\overset{\lx@cref{creftype~refnum}{eq:lagr2}}{\leq}$
$\displaystyle-\sum_{i\in[I]}\lambda(i)(V^{\pi_{k}}(\tilde{D}_{k},\tilde{p}_{k})-\alpha)_{i}+\tilde{L}_{k}(\pi,\lambda_{k})+\epsilon_{k},$

and rearranging this yields the desired inequality. ∎

Before proving Lemma 5, we finally need to establish Lemma 18. This result is
based on standard properties from constrained convex optimization (Section
A.4) and the LP formulation of CMDPs (Section A.3). Recall that we have
$V^{\pi}(\tilde{c}_{k},\tilde{p}_{k})=\tilde{c}_{k}^{T}q^{\pi}(\tilde{p}_{k})$
and
$V^{\pi}(\tilde{D}_{k},\tilde{p}_{k})=\tilde{D}_{k}q^{\pi}(\tilde{p}_{k})$,
where $q^{\pi}(\tilde{p}_{k})\in\mathbb{R}^{SAH}$,
$\tilde{c}_{k}\in\mathbb{R}^{SAH}$, $\tilde{d}_{i,k}\in\mathbb{R}^{SAH}$, and
$\tilde{D}_{k}\in\mathbb{R}^{I\times SAH}$ are defined as in Section A.3.
Thus, when switching to occupancy measures, the optimistic problem (Eq. 6)
equivalently reads

$\displaystyle\min_{\begin{subarray}{c}q^{\pi}\in
Q\end{subarray}(\tilde{p}_{k})}\leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\
\tilde{c}_{k}^{T}q^{\pi}\leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \text{s.t.}\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\tilde{D}_{k}q^{\pi}-\alpha\leq 0,$ (34)

where $Q(\tilde{p}_{k})\subset\mathbb{R}^{SAH}$ is defined as in Section A.3.
This is a convex optimization problem over the set of occupancy measures
$Q(\tilde{p}_{k})$.

Formally, we make the following assumption. By Lemma 1, the assumption will be
guaranteed to hold with (with $\pi^{0}=\bar{\pi}$ and
$\sigma=\frac{H}{\nu\gamma}$), conditioned on $G$.

######  Assumption 3 (Slater points).

There exists $\pi^{0}\in\Pi$ such that for all $k\in\\{K^{\prime},\dots,K\\}$
and all $i\in[I]$ we have
$V^{\pi^{0}}(\tilde{d}_{i,k},\tilde{p}_{k})<\alpha_{i}$. In particular, Eq. 6
is feasible. Let $\pi^{*}_{k}$ be an optimal solution for Eq. 6 and suppose
there is a fixed constant $\sigma>0$ such that, for all
$k\in\\{K^{\prime},\dots,K\\}$,