# Concave Utility Reinforcement Learning with Zero-Constraint Violations

Mridul Agarwal, Qinbo Bai, Vaneet Aggarwal The authors are with Purdue
University, West Lafayette IN 47907, USA, email:{agarw180, bai113,
<EMAIL_ADDRESS>
###### Abstract

We consider the problem of tabular infinite horizon concave utility
reinforcement learning (CURL) with convex constraints. Various learning
applications with constraints, such as robotics, do not allow for policies
that can violate constraints. To this end, we propose a model-based learning
algorithm that achieves zero constraint violations. To obtain this result, we
assume that the concave objective and the convex constraints have a solution
interior to the set of feasible occupation measures. We then solve a tighter
optimization problem to ensure that the constraints are never violated despite
the imprecise model knowledge and model stochasticity. We also propose a novel
Bellman error based analysis for tabular infinite-horizon setups which allows
to analyse stochatic policies. Combining the Bellman error based analysis and
tighter optimization equation, for $T$ interactions with the environment, we
obtain a regret guarantee for objective which grows as
$\tilde{O}(1/\sqrt{T})$, excluding other factors.

##  1 Introduction

Reinforcement Learning is being increasingly applied to various interesting
Markov Decision Processes (MDP) setups where the system model is not known
apriori Sutton and Barto (2018); Recht (2019). Various algorithms have been
developed to learn efficient policies using deep neural networks Mnih et al.
(2015); Schulman et al. (2017); Haarnoja et al. (2018). Much work is also done
to develop algorithms that are provably sample-efficient Jaksch et al. (2010);
Agrawal and Jia (2017); Jin et al. (2018). However, in many applications, the
learning agent (or algorithm) needs to satisfy certain constraints while
maximizing an objective Altman and Schwartz (1991).

For example, in robotics, a good policy for reaching a target pose should
avoid hazardous poses which may damage the environment Achiam et al. (2017).
Also, consider the example of autonomous vehicles, the goal is not just to
reach the destination as early as possible, but also to ensure the safety of
the surroundings Le et al. (2019); Tessler et al. (2018). Further, there are
certain environments in which the agent is required to ensure the constraint
violations are reduced while optimizing the objective as well Leike et al.
(2017); Ray et al. (2019).

Owing to the importance of RL with constraints, recently, there has been
significant work in the area. For episodic setup, there is a significant line
of work ranging from model based algorithms Brantley et al. (2020); Yu et al.
(2021) to primal-dual based model-free algorithms Ding et al. (2021). Much
recently, Wei et al. (2021) proposed TripleQ algorithm which achieves zero
constraint violations111We note that even with zero constraint violations, an
agent can violate constraints in the initial learning periods. Hence, zero
constraints violations should be treated as $O(1/T)$, i.e., $O(1)$ violations
in time $T$. at the expense of an increased regret order of $O(T^{-1/5})$.
However, for the episodic setup, the majority of the current work considers
the weaker regret definition specified by Efroni et al. (2020). Averaging over
value function of multiple episodes allows for oscillations for constraints
values around bounds, and does not imply that the policy (and the
corresponding value function) necessarily converge to the optimal policy (and
the corresponding value function) which satisfies the constraints.

We note that the definition which considers the average over time makes sense
when considering an infinite horizon setup as the long-term average is
naturally defined Puterman (2014). For a tabular infinite-horizon setup, Singh
et al. (2020) proposed an epoch-based algorithm which bounds the regret by
$O(S\sqrt{A/T^{5}})$ with convergence in policy. We improve on this result by
three folds, first by reducing the regret order from $O(T^{-1/4})$ to
$O(T^{-1/2})$, second by considering convex function for objectives and
constraints, and last by providing algorithm which can bound the constraint
violations with $O(1/T)$. We compare the algorithms with different related
works in Table 1.

In this work, we consider the problem of maximizing concave utility of the
expected rewards while also ensuring that a set of convex constraints of the
expected rewards are also satisfied. Moreover, we aim to develop algorithms
that can also ensure that the constraints are not violated during the training
phase as well. We work with tabular MDP with infinite horizon. For such setup,
our algorithm updates policies as it learns the system model. Further, our
approach also bound the accumulated observed constraint violations as compared
to the expected constraint violations.

Algorithm(s) | Setup | Regret | Constraint Violation | Non-Linear
---|---|---|---|---
UCRL2 Jaksch et al. (2010) | IH | $\tilde{O}(DS\sqrt{A/T})$ | Not Applicable | No
conRL Brantley et al. (2020) | FH | $\tilde{O}(LH^{3/2}S\sqrt{A/T})$ | $O(H^{3/2}S\sqrt{A/T})$ | Yes
MOMA Yu et al. (2021) | FH | $\tilde{O}(LH^{3/2}\sqrt{SA/K})$ | $\tilde{O}(H^{3/2}\sqrt{SA/K})$ | Yes
TripleQ Wei et al. (2021) | FH | $\tilde{O}(\frac{1}{\delta}H^{4}\sqrt{SA}/K^{0.2})$ | $\tilde{O}(1/K)$ | No
UCRL-CMDP Singh et al. (2020) | IH | $\tilde{O}(S\sqrt{A}/T^{0.25})$ | $\tilde{O}(S\sqrt{A/T^{0.5}})$ | No
UC-CURL (This work) | IH | $\tilde{O}(\frac{1}{\delta}LT_{M}S\sqrt{A/T}+\frac{T_{M}S\log T}{1-\rho})$ | $O(1/T)$ | Yes
Table 1: Overview of work for constrained reinforcement learning setups. For
infinite horizon (IH) setups, $D$ denotes diameter of the MDP, $T_{M}$ denotes
the mixing time of the MDP, and $T$ is the time for which algorithm runs. For
finite horizon (FH) setups, $H$ is the episode length and $K$ is the number of
episodes for which the algorithm runs. $L$ is the Lipschitz constant.

To achieve this result, we propose UC-CURL algorithm which proceeds in epochs
$e$. At each epoch, we solve for a policy which considers constraints tighter
by $\epsilon_{e}$ than the true bounds. Further, as the knowledge of the model
improves with increased interactions with the environment, we reduce this
tightness. This $\epsilon_{e}$-sequence is critical to our algorithm as, if
the sequence decays too fast, the constraints violations cannot be bounded by
zero. And, if this sequences decays too slow, the objective regret may not
decay fast enough. Further, using the $\epsilon_{e}$-sequence, we do not
require the knowledge of the total time $T$ for which the algorithm runs.

We bound our regret by bounding the gap between the optimal policy in the
feasible region and the optimal policy for the optimization problem with
$\epsilon_{e}$ tight constraints. We bound this gap with a multiplicative
factor of $O(1/\delta)$, where $\delta$ is Slater’s parameter. Based on our
analysis using the Slater’s parameter $\delta$, we consider a case where a
lower bound $T_{l}$ on the time horizon $T$ is known. This knowledge of
$T_{l}$ allows us to relax our assumption on $\delta$.

Further, the regret analysis of the proposed UC-CURL algorithm is also novel.
We define and use Bellman error for infinite horizon setup to bound the
difference between the performance of optimistic policy on the optimistic MDP
and the true MDP. Compared to analysis of Jaksch et al. (2010), this allows us
to work with stochastic policies.

Combining these two tricks, we bound our regret as
$\tilde{O}(\frac{1}{\delta}LdT_{M}S\sqrt{A/T})$ and constraint violations as
$O(1/T)$, where $S$ and $A$ are the number of states and actions respectively,
$L$ is the Lipschitz constant of the objective and constraint functions, $d$
is the number of costs the agent is trying to optimize, and $T_{M}$ is the
mixing time of the MDP. We note that ours is the first result with a suitable
regret definition, on non-linear objective and constraints, and the result
achieves zero-constraint violations.

##  2 Related Works

Unconstrained RL: Much work has been done to understand finite time
performance of algorithms for the tabular setup. Jaksch et al. (2010) provided
epoch based UCRL2 algorithm which achieves a regret bound of
$\tilde{O}(DS\sqrt{A/T})$ for infinite horizon setup using optimism and proved
a lower bound of $O(\sqrt{DSA/T}$ for MDPs with diameter $D$. Fruit et al.
(2018) provided an improved epoch based SCAL algorithm with regret
$O(D\sqrt{SA/T})$. The analysis of both UCRL2 and SCAL algorithm have an
additional regret which increases linearly in the number of epochs coming from
the fact that triggering a new policy takes few steps to converge to the
stationary distribution. However, the algorithm bound the number of epochs in
logarithmic order of time horizon $T$.

Constrained RL: The work by Altman (1999) summarized the requirements for the
study of constrained reinforcement learning, along with the formulation for
constrained MDPs and algorithms for obtaining policies with known transition
models. Similar to the unconstrained setup, recently there is progress towards
understanding the convergence properties of the algorithms along with finite
time performance. (Zheng and Ratliff, 2020) considered an episodic CMDP and
use an optimism based algorithm to bound the constraint violation as
$\tilde{O}(1/T^{0.25})$ with high probability. (Kalagarla et al., 2020) also
considered the episodic setup to obtain PAC-style bound for an optimism based
algorithm. (Ding et al., 2021) considered the setup of $H$-episode length
episodic CMDPs with $d$-dimensional linear function approximation to bound the
constraint violations as $\tilde{O}(d\sqrt{H^{5}/T})$ by mixing the optimal
policy with an exploration policy. (Efroni et al., 2020) proposes a linear-
programming and primal-dual policy optimization algorithm to bound the regret
as $O(S\sqrt{H^{3}/T})$. (Qiu et al., 2020) proposed an algorithm which
obtains a regret bound of $\tilde{O}(S\sqrt{AH^{2}/T})$ for the problem of
adversarial stochastic shortest path. Wei et al. (2021) considered the problem
of ensuring zero constraint violations using a model-free algorithm for
tabular MDPs with linear rewards and constraints. However, they achieve that
result at the expense of an increased regret bound of $O(T^{-1/5})$. Compared
to these works, we focus on setting with infinite horizon long-term average
constraints.

Xu et al. (2020) consider an infinite horizon discounted setup with
constraints and obtain global convergence using policy gradient algorithms.
Ding et al. (2020) also considers an infinite horizon discounted setup. They
use a natural policy gradient to update the primal variable and sub-gradient
descent to update the dual variable. Singh et al. (2020) considered the setup
of infinite-horizon CMDPs with long-term average constraints with an optimism
based algorithm and forced explorations. We consider a similar setting with
unichain CMDP and propose an optimism based algorithm to bound the regret as
$\tilde{O}(LdT_{M}S\sqrt{A/T})$ using explorations assisted by the ergodicity
of the MDP. Very recently, Gattami et al. (2021) analyzed the asymptotic
performance for Lagrangian based algorithms for infinite-horizon long-term
average constraints, however they only show convergence guarantees without
explicit convergence rates.

Concave Utility RL: Another major research area related to constrained RL is
concave utility RL Hazan et al. (2019). Along this direction, Cheung (2019)
considered a concave function of expected per-step vector reward and developed
an algorithm using Frank-Wolfe gradient of the concave function for tabular
infinite horizon MDPs. Agarwal and Aggarwal (2019) also considered the same
setup, but proposed a posterior sampling based algorithm. Recently, Brantley
et al. (2020) combined concave utility reinforcement learning and constrained
reinforcement learning for an episodic setup. Yu et al. (2021) also considered
the case of episodic setup with concave utility RL. However, both Brantley et
al. (2020) and Yu et al. (2021) consider the weaker regret definition by
Efroni et al. (2020), and Cheung (2019) and Yu et al. (2021) do not target the
convergence of the policy. Further, these works do not target zero-constraint
violations.

Compared to prior works, we consider the constrained reinforcement learning
with convex constraints and concave objective function. Using infinite-horizon
setup, we consider the tightest possible regret definition. Further, we
achieve zero constraint violations with objective regret tight in $T$ using an
optimization problem with decaying tightness. A quick comparative survey of
prior works and our work is also presented in Table 1.

##  3 Problem Formulation

We consider a tabular infinite-horizon constrained Markov Decision Process
$\mathcal{M}=(\mathcal{S},\mathcal{A},r,f,c_{1},\cdots,c_{d},g,P)$ with
bounded diameter $D$. $\mathcal{S}$ is finite set of $S$ states, and
$\mathcal{A}$ is a finite set of $A$ actions.
$P:\mathcal{S}\times\mathcal{A}\to\Delta(\mathcal{S})$ denotes the transition
probability distribution such that on taking action $a\in\mathcal{A}$ in state
$s\in\mathcal{S}$, the system moves to state $s^{\prime}\in\mathcal{S}$ with
probability $P(s^{\prime}|s,a)$. $r:\mathcal{S}\times\mathcal{A}\to[0,1]$ and
$c_{i}:\mathcal{S}\times\mathcal{A}\to[0,1],i\in{1,\cdots,d}$ denotes the
average reward obtained and average costs incurred in state action pair
$(s,a)\in\mathcal{S}\times\mathcal{A}$.

The agent interacts with $\mathcal{M}$ in time-steps $t\in{1,2,\cdots}$ for a
total of $T$ time-steps. We note that $T$ is possibly unknown. At each time
$t$, the agent observes state $s_{t}$, plays action $a_{t}$. The agent selects
an action on observing the state $s$ using a policy
$\pi:\mathcal{S}\to\Delta(\mathcal{A})$, where $\Delta(\mathcal{A})$ is the
probability simplex on the action space. On following a policy $\pi$, the
long-term average reward of the agent is denoted as:

$\displaystyle\lambda_{\pi}^{P}$
$\displaystyle=\lim_{\tau\to\infty}\mathbb{E}_{\pi,P}\left[\frac{1}{\tau}\sum\nolimits_{t=1}^{\tau}r(s_{t},a_{t})\right]$
(1)

where $\mathbb{E}_{\pi,P}[\cdot]$ denotes the expectation over the state and
action trajectory generated from following $\pi$ on transitions $P$. The long-
term average reward can also be represented as:

$\displaystyle\lambda_{\pi}^{P}$ $\displaystyle=\lim_{\gamma\to
1}(1-\gamma)V_{\gamma}^{\pi,P}(s)\ \ \ \forall s\in\mathcal{S}$ (2)
$\displaystyle=\sum\nolimits_{s,a}\rho_{\pi}^{P}(s,a)r(s,a)$ (3)

where $V_{\gamma}^{\pi,P}(s)$ is the discounted cumulative reward on following
policy $\pi$, and $\rho_{\pi}^{P}\in\Delta(\mathcal{S}\times\mathcal{A})$ is
the steady-state occupancy measure generated from following policy $\pi$ on
MDP with transitions $P$ Puterman (2014). Similarly, we also define the long-
term average costs as follows:

$\displaystyle\zeta_{\pi}^{P}(i)$
$\displaystyle=\lim_{\tau\to\infty}\mathbb{E}_{\pi,P}\left[\frac{1}{\tau}\sum\nolimits_{t=1}^{\tau}c_{i}(s_{t},a_{t})\right]$
(4) $\displaystyle=\lim_{\gamma\to 1}(1-\gamma)V_{\gamma}^{\pi,P}(s;i)\ \ \
\forall s\in\mathcal{S}$ (5)
$\displaystyle=\sum_{s,a}\rho_{\pi}^{P}(s,a)c_{i}(s,a)$ (6)

The agent interacting with the CMDP $\mathcal{M}$ aims to maximize a function
$f:[0,1]\to\mathbb{R}$ of the average per-step reward. Further, the agent
attempts to ensure that a function of average per-step costs
$g:[0,1]^{d}\to\mathbb{R}$ is at most $0$. The goal is represented
mathematically as:

$\displaystyle\max_{\pi}f\left(\lambda_{\pi}^{P}\right)$ (7) $\displaystyle
s.t.\ g\left(\zeta_{\pi}^{P}(1),\cdots,\zeta_{\pi}^{P}(d)\right)\leq 0,$ (8)

###### Remark 1

Note that the model, the proposed algorithm, and the analysis can be easily
extended to $M$ convex constraints $g_{1}\cdots,g_{M}$ by applying union
bounds.

We are now ready to introduce our initial assumptions on the MDP
$\mathcal{M}$.

Let $P^{t}_{\pi,s}$ denote the $t$-step transition probability on following
policy $\pi$ in MDP $\mathcal{M}$ starting from state $s$. Also, let $T_{s\to
s^{\prime}}^{\pi}$ denotes the time taken by the Markov chain induced by the
policy $\pi$ to hit state $s^{\prime}$ starting from state $s$. Building on
these variables, $P^{t}_{\pi,s}$ and $T_{s\to s^{\prime}}^{\pi}$, we make our
first assumption as follows:

###### Assumption 1

The MDP $\mathcal{M}$ is ergodic, or

$\displaystyle\|P^{t}_{\pi,s}-P_{\pi}\|\leq C\rho^{t}$ (9)

where $P_{\pi}$ is the long-term steady state distribution induced by policy
$\pi$, and $C>0$ and $\rho<1$ are problem specific constants. Also, we have

$\displaystyle T_{M}:=\max_{\pi}\mathbb{E}[T^{\pi}_{s\to s^{\prime}}]<\infty$
(10)

where $T_{M}$ is the finite mixing time of the MDP $\mathcal{M}$.

###### Assumption 2

The rewards $r(s,a)$, the costs $c_{i}(s,a);\forall\ i$ and the functions $f$
and $g$ are known to the agent.

We note that in most of the problems, rewards are engineered according to the
problem. Hence, Assumption 2 is justified in many setups. However, the system
dynamics are stochastic and typically not known.

Our next assumption is on the functions $f$ and $g$. We have

###### Assumption 3

The scalarization function $f$ is jointly concave and the constraints $g$ are
jointly convex. Hence for any arbitrary distributions $\mathcal{D}_{1}$ and
$\mathcal{D}_{2}$, the following holds.

$\displaystyle f\left(\mathbb{E}_{x\sim\mathcal{D}_{1}}\left[x\right]\right)$
$\displaystyle\geq\mathbb{E}_{x\sim\mathcal{D}_{1}}\left[f\left(x\right)\right]$
(11) $\displaystyle
g\left(\mathbb{E}_{\mathbf{x}\sim\mathcal{D}_{2}}\left[\mathbf{x}\right]\right)$
$\displaystyle\leq\mathbb{E}_{\mathbf{x}\sim\mathcal{D}_{2}}\left[g\left(\mathbf{x}\right)\right];\
\mathbf{x}\in\mathbb{R}^{d}$ (12)

Many practically implemented fairness objectives are concave (Kwan et al.,
2009), or the agent want to explore all possible state action pairs by
maximizing the entropy of the long-term state-action distribution (Hazan et
al., 2019), or the agent may want to minimize divergence with respect to a
certain expert policy (Ghasemipour et al., 2020).

We impose an additional assumption on the functions $f$ and $g$. We assume
that the functions are continuous and Lipschitz continuity in particular. We
have,

###### Assumption 4

The function $f$ and $g$ are assumed to be a $L-$ Lipschitz function, or

$\displaystyle\left|f\left(x\right)-f\left(y\right)\right|$ $\displaystyle\leq
L|x-y|;\ x,y\in\mathbb{R}$ (13)
$\displaystyle\left|g\left(\mathbf{x}\right)-g\left(\mathbf{y}\right)\right|$
$\displaystyle\leq L\left\lVert\mathbf{x}-\mathbf{y}\right\rVert_{1};\
\mathbf{x},\mathbf{y}\in\mathbb{R}^{d}$ (14)

Lipschitz continuity is a common assumption for optimization literature
(Bubeck et al., 2015; Jin et al., 2017; Zhang et al., 2020). Additionally, in
practice this assumption is validated, often by adding some regularization.

Next, we assume the following Slater’s condition to hold.

###### Assumption 5

There exists a policy $\pi$, and one constant $\delta>LdST_{M}\sqrt{A}$ such
that

$\displaystyle
g\left(\zeta_{\pi}^{P}(1),\cdots,\zeta_{\pi}^{P}(d)\right)\leq-\delta$ (15)

Further, if the agent has access to a lower bound of time-horizon,
$T_{l}\geq\exp{(1)}$, then we only require $\delta>LdST_{M}\sqrt{A(\log
T_{l})/T_{l}}$. This assumption is again a standard assumption in the
constrained RL literature (Efroni et al., 2020; Ding et al., 2021, 2020; Wei
et al., 2021). $\delta$ is referred as Slater’s constant. (Ding et al., 2021)
assumes that the Slater’s constant $\delta$ is known. (Wei et al., 2021)
assumes that the number of iterations of the algorithm is at least
$\tilde{\Omega}(SAH/\delta)^{5}$ for episode length $H$. On the contrary, we
simply assume the existence of $\delta$ and a lower bound on the value of
$\delta$ which can be relaxed as the agent acquires more time to interact with
the environment.

Any online algorithm starting with no prior knowledge will require to obtain
estimates of transition probabilities $P$ and obtain reward $r$ and costs
$c_{k},\forall\ k\in\\{1,\cdots,d\\}$ for each state action pair. Initially,
when algorithm does not have good estimate of the model, it accumulates a
regret as well as violates constraints as it does not know the optimal policy.
We define reward regret $R(T)$ as the difference between the average
cumulative reward obtained vs the expected rewards from running the optimal
policy $\pi^{*}$ for $T$ steps, or

$\displaystyle R(T)$
$\displaystyle=f\left(\lambda_{\pi^{*}}^{P}\right)-f\left(\frac{1}{T}\sum\nolimits_{t=1}^{T}r(s_{t},a_{t})\right)$

Additionally, we define constraint regret $C(T)$ as the gap between the
constraint function and incurred and constraint bounds, or

$\displaystyle C(T)$
$\displaystyle=\left(g\left(\frac{1}{T}\sum_{t=1}^{T}c_{1}(s_{t},a_{t}),\cdots,\frac{1}{T}\sum_{t=1}^{T}c_{1}(s_{t},a_{t})\right)\right)_{+}$

where $(x)_{+}=\max(0,x)$.

In the following section, we present a model-based algorithm to obtain this
policy $\pi^{*}$, and reward regret and the constraint regret accumulated by
the algorithm.

##  4 Algorithm

Algorithm 1 UC-CURL

Parameters: $K$
Input: $S$, $A$, $r$, $d$, $c_{i}\ \forall\ i\in[d]$

1: Let $t=1$, $e=1,\epsilon_{e}=K\sqrt{\frac{\ln t}{t}}$

2: for $(s,a)\in\mathcal{S}\times\mathcal{A}$ do

3: $\nu_{e}(s,a)=0,N_{e}(s,a)=0,\widehat{P}(s^{\prime},a,s)=0\forall\
s^{\prime}\in\mathcal{S}$

4: end for

5: Solve for policy $\pi_{e}$ using Eq. (25)

6: for $t\in\\{1,2,\cdots\\}$ do

7: Observe $s_{t}$, and play $a_{t}\sim\pi_{e}(\cdot|s_{t})$

8: Observe $s_{t+1}$, $r(s_{t},a_{t})$ and $c_{i}(s_{t},a_{t})\ \forall\
i\in[d]$

9: $\nu_{e}(s_{t},a_{t})=\nu_{e}(s_{t},a_{t})+1$

10: $\widehat{P}(s_{t},a_{t},s_{t+1})=\widehat{P}(s_{t},a_{t},s_{t+1})+1$

11: if $\nu_{e}(s,a)=\max\\{1,N_{e}(s,a)\\}$ for any $s,a$ then

12: for $(s,a)\in\mathcal{S}\times\mathcal{A}$ do

13: $N_{e+1}(s,a)=N_{e}(s,a)+\nu_{e}(s,a)$

14: $e=e+1$

15: $\nu_{e}(s,a)=0$

16: end for

17: $\epsilon_{e}=K\sqrt{\frac{\ln t}{t}}$

18: Solve for policy $\pi_{e}$ using Eq. (25)

19: end if

20: end for

We now present our algorithm UC-CURL and the key ideas used in designing the
algorithm. Note that if the agent is aware of the true transition $P$, it can
solve the following optimization problem for the optimal feasible policy.

$\displaystyle\max_{\rho(s,a)}f\big{(}\sum_{s,a}r(s,a)\rho(s,a)\big{)}$ (16)

with the following set of constraints,

$\displaystyle\sum\nolimits_{s,a}\rho(s,a)=1,\ \ \rho(s,a)\geq 0$ (17)
$\displaystyle\sum\nolimits_{a\in\mathcal{A}}\rho(s^{\prime},a)=\sum\nolimits_{s,a}P(s^{\prime}|s,a)\rho(s,a)$
(18) $\displaystyle
g\big{(}\sum_{s,a}c_{1}(s,a)\rho(s,a),\cdots,\sum_{s,a}c_{d}(s,a)\rho(s,a)\big{)}\leq
0$ (19)

for all $s^{\prime}\in\mathcal{S},~{}\forall~{}s\in\mathcal{S},$ and
$\forall~{}a\in\mathcal{A}$. Equation (18) denotes the constraint on the
transition structure for the underlying Markov Process. Equation (17) ensures
that the solution is a valid probability distribution. Finally, Equation (19)
are the constraints for the constrained MDP setup which the policy must
satisfy. Using the solution for $\rho$, we can obtain the optimal policy as:

$\displaystyle\pi^{*}(a|s)=\frac{\rho(s,a)}{\sum_{b\in\mathcal{A}}\rho(s,b)}\forall\
s,a$ (20)

However, the agent does not have the knowledge of $P$ to solve this
optimization problem, and thus starts learning the transitions with an
arbitrary policy. We first note that if the agent does not have complete
knowledge of the transition $P$ of the true MDP $\mathcal{M}$, it should be
conservative in its policy to allow room to violate constraints. Based on this
idea, we formulate the $\epsilon$-tight optimization problem by modifying the
constraint in Equation (19) as.

$\displaystyle
g\big{(}\sum_{s,a}(c_{1}\rho_{\epsilon})(s,a),\cdots,\sum_{s,a}(c_{1}\rho_{\epsilon})(s,a)\big{)}\leq-\epsilon$
(21)

Let $\rho_{\epsilon}$ be the solution of the $\epsilon$-tight optimization
problem, then the optimal conservative policy becomes:

$\displaystyle\pi_{\epsilon}^{*}(a|s)=\frac{\rho_{\epsilon}(s,a)}{\sum_{b\in\mathcal{A}}\rho_{\epsilon}(s,b)}\forall\
s,a$ (22)

We are now ready to design our algorithm UC-CURL which is based on the
optimism principle Jaksch et al. (2010). The UC-CURL algorithm is presented in
Algorithm 1. The algorithm proceeds in epochs $e$. The algorithm maintains
three key variables $\nu_{e}(s,a)$, $N_{e}(s,a)$, and
$\hat{P}(s,a,s^{\prime})$ for all $s,a$. $\nu_{e}(s,a)$ stores the number of
times state-action pair $(s,a)$ are visited in epoch $e$. $N_{e}(s,a)$ stores
the number of times $(s,a)$ are visited till the start of epoch $e$.
$\hat{P}(s,a,s^{\prime})$ stores the number of times the system transitions to
state $s^{\prime}$ after taking action $a$ in state $s$. Another key parameter
of the algorithm is $\epsilon_{e}=K\sqrt{(\log t_{e})/t_{e}}$ where $t_{e}$ is
the start time of the epoch $e$ and $K$ is a configurable constant. Using
these variables, the agent solves for the optimal $\epsilon_{e}$-conservative
policy for the optimistic MDP by replacing the constraints in Equation (18)
by:

$\displaystyle\sum\nolimits_{a\in\mathcal{A}}\rho_{e}(s^{\prime},a)=\sum\nolimits_{s,a}\tilde{P}_{e}(s^{\prime}|s,a)\rho(s,a)$
(23) $\displaystyle\|\tilde{P}_{e}(\cdot|s,a)-\frac{\hat{P}(s,a,\cdot)}{1\vee
N_{e}(s,a)}\|_{1}\leq\sqrt{\frac{14S\log(2At)}{1\vee N_{e}(s,a)}}$ (24)

for all $s^{\prime}\in\mathcal{S},~{}\forall~{}s\in\mathcal{S},$ and
$\forall~{}a\in\mathcal{A}$. Equation (24) ensures that the agent searches for
optimistic policy in the confidence intervals of the transition probability
estimates.

Let $\rho_{e}$ be the solution for $\epsilon_{e}$-tight optimization equation
for the optimistic MDP. Then, we obtain the optimal conservative policy for
epoch $e$ as:

$\displaystyle\pi_{e}(a|s)=\frac{\rho_{e}(s,a)}{\sum_{b\in\mathcal{A}}\rho_{e}(s,b)}\forall\
s,a$ (25)

The agent plays the optimistic conservative policy $\pi_{e}$ for epoch $e$.
Note that the conservative parameter $\epsilon_{e}$ decays with time. As the
agent interacts with the environment, the system model improves and the agent
does not need to be as conservative as before. This allows us to bound both
constraint violations and the objective regret.

For the UC-CURL algorithm described in Algorithm 1, we choose
$\\{\epsilon_{e}\\}=\\{K\sqrt{(\log t_{e})/t_{e}}\\}$. However, if the agent
has access to a lower bound $T_{l}$ (Assumption 5) on the time horizon $T$,
the algorithm can change the $\epsilon_{e}$ in each epoch $e$ as follows.

$\displaystyle\epsilon_{e}=K\sqrt{\frac{\ln(t_{e}\vee T_{l})}{t_{e}\vee
T_{l}}}\leq\delta$ (26)

Note that if $T_{l}=0$, $\epsilon_{e}$ becomes as specified in Algorithm 1 and
if $T_{l}=T$, $\epsilon_{e}$ becomes constant for all epochs $e$.

##  5 Regret Analysis

After describing UC-CURL algorithm, we now perform the regret and constraint
violation analysis using Bellman error. We note that the standard analysis for
infinite horizon tabular MDPs of UCRL2 Jaksch et al. (2010) cannot be directly
applied as the policy $\pi_{e}$ is possibly stochastic for every epoch.
Another peculiar aspect of the analysis of the UCRL2 algorithm is the regret
grows linearly with the number of epochs. The analysis still bounds the regret
by $\tilde{O}(DS\sqrt{A/T})$ as the number of epochs are bounded by $O(SA\log
T)$. However, the analysis is counter-intuitive as the agent is able to work
with a better policy at every time-step not just for an epoch. We also note
that the analysis of UCRL-CMDP Singh et al. (2020) bounds the deviations with
value function instead of bias resulting in regret scaling as $O(T^{-1/4})$.
Compared to these works, our analysis works with stochastic policies, obtains
regret independent to number of epochs, and scales as $\tilde{O}(1/\sqrt{T})$.
Hence, our analysis can be used as a tool to tightly analyze other learning
algorithms for tabular infinite horizon MDPs.

Before diving into the details, we first define few important variables which
are key to our analysis. The first variable is the standard $Q$-value
function. We define $Q_{\gamma}^{\pi,P}$ as the long term expected reward on
taking action $a$ in state $s$ and then following policy $\pi$ for the MDP
with transition $P$. Mathematically, we have

$\displaystyle
Q_{\gamma}^{\pi,P}(s,a)=r(s,a)+\gamma\sum_{s^{\prime}\in\mathcal{S}}P(s^{\prime}|s,a)V_{\gamma}^{\pi,P}(s^{\prime}).$
(27)

We also define Bellman error $B^{\pi,\tilde{P}}(s,a)$ for the infinite horizon
MDPs as the difference between the cumulative expected rewards obtained for
deviating from the system model with transition $\tilde{P}$ for one step by
taking action $a$ in state $s$ and then following policy $\pi$. We have:

$\displaystyle B^{\pi,\tilde{P}}(s,a)$ $\displaystyle=\lim_{\gamma\to
1}\Big{(}Q_{\gamma}^{\pi,\tilde{P}}(s,a)-r(s,a)-\gamma\sum\nolimits_{s^{\prime}\in\mathcal{S}}P(s^{\prime}|s,a)V_{\gamma}^{\pi,\tilde{P}}(s,a)\Big{)}$
(28)

After defining the key variables, we can now jump into bounding the objective
regret $R(T)$. Intuitively, the algorithm incurs regret on three accounts.
First source is following the conservative policy which we require to limit
the constraint violations. Second source of regret is solving for the policy
which is optimal for the optimistic MDP. Third source of regret is the
stochastic behavior of the system. We also note that the constraints are
violated because of the imperfect MDP knowledge and the stochastic behavior.
However, the conservative behavior actually allows us to violate the
constraints within some limits which we will discuss in the later part of this
section.

We start by stating our first lemma which relates the regret because we solve
for a conservative policy. We define $\epsilon_{e}$-tight optimization problem
as optimization problem for the true MDP with transitions $P$ with
$\epsilon=\epsilon_{e}$. We bound the gap between the value of function $f$ at
the long-term expected reward of the policy for $\epsilon_{e}$-tight
optimization problem and the true optimization problem (Equation (16)-(19)) in
the following lemma.

###### Lemma 1

Let $\lambda_{\pi^{*}}^{P}$ be the long-term average reward following the
optimal feasible policy $\pi^{*}$ for the true MDP $\mathcal{M}$ and let
$\lambda_{\pi_{e}}^{P}$ be the long-term average rewards following the optimal
policy $\pi_{e}$ for the $\epsilon_{e}$ tight optimization problem for the
true MDP $\mathcal{M}$, then for $\epsilon_{e}\leq\delta$, we have,

$\displaystyle
f\left(\lambda_{\pi^{*}}^{P}\right)-f\left(\lambda_{\pi_{e}}^{P}\right)\leq\frac{2L\epsilon_{e}}{\delta}$
(29)

Proof [Proof Sketch] We construct a policy for which the steady state
distribution is the weighted average of two steady state distributions. First
distribution is for the optimal policy for the true optimization problem.
Second distribution is for the policy which satisfies Assumption 5. Now, we
show that this constructed policy satisfies the $\epsilon_{e}$-tight
constraints. Now, using Lipschitz continuity, we convert the difference
between function value into the difference between the long-term average
reward to obtain the required result.

The detailed proof is provided in Appendix A.

Lemma 1 and our construction of $\epsilon_{e}$ sequence allows us to limit the
growth of regret because of conservative policy by
$\tilde{O}(LdT_{M}S\sqrt{A/T})$.

To bound the regret from the second source, we propose a novel Bellman error
based analysis. In our next lemma, we show that the difference between the
performance of a policy on two different MDPs is bounded by long-term averaged
Bellman error. Formally, we have:

###### Lemma 2

The difference of long-term average rewards for running the optimistic policy
$\pi_{e}$ on the optimistic MDP, $\lambda_{\pi_{e}}^{\tilde{P}_{e}}$, and the
average long-term average rewards for running the optimistic policy $\pi_{e}$
on the true MDP, $\lambda_{\pi_{e}}^{P}$, is the long-term average Bellman
error as

$\displaystyle\lambda_{\pi_{e}}^{\tilde{P}_{e}}-\lambda_{\pi_{e}}^{P}=\sum_{s,a}\rho_{\pi_{e}}^{P}B^{\pi_{e},\tilde{P}_{e}}(s,a)$
(30)

Proof [Proof Sketch] We start by writing $Q_{\gamma}^{\pi_{e},\tilde{P}_{e}}$
in terms of the Bellman error. Now, subtracting $V_{\gamma}^{\pi_{e},P}$ from
$V_{\gamma}^{\pi_{e},\tilde{P}_{e}}$ and using the fact that
$\lambda_{\pi_{e}}^{P}=\lim_{\gamma\to 1}V_{\gamma}^{\pi,P}$ and
$\lambda_{\pi_{e}}^{\tilde{P}_{e}}=\lim_{\gamma\to
1}V_{\gamma}^{\pi,{\tilde{P}_{e}}}$ we obtain the required result.

A complete proof is provided in Appendix B.
After relating the gap between the long-term average rewards of policy
$\pi_{e}$ on the two MDPs, we now want to bound the sum of Bellman error over
an epoch. For this, we first bound the Bellman error for a particular state
action pair $s,a$ in the form of following lemma. We have,

###### Lemma 3

With probability at least $1-1/t_{e}^{6}$, the Bellman error
$B^{\pi_{e},\tilde{P}_{e}}(s,a)$ for state-action pair $s,a$ in epoch $e$ is
upper bounded as

$\displaystyle
B^{\pi_{e},\tilde{P}_{e}}(s,a)\leq\sqrt{\frac{14S\log(2AT)}{1\vee
N_{e}(s,a)}}\tilde{h}(\cdot)$ (31)

Proof [Proof Sketch] We start by noting that the Bellman error essentially
bounds the impact of the difference in value obtained because of the
difference in transition probability to the immediate next state. We bound the
difference in transition probability between the optimistic MDP and the true
MDP using the result from Weissman et al. (2003). This approach gives the
required result.

A complete proof is provided in Appendix B.

To bound the regret because of the imperfect knowledge of the system model, we
can now use Lemma 2 and Lemma 3. We now bound the expected Bellman error in
epoch $e$ starting from state $s_{t_{e}}$ and action $a_{t_{e}}$ by
constructing a Martingale sequence with filtration
$\mathcal{F}_{t}=\\{s_{1},a_{1},\cdots,s_{t-1},a_{t-1}\\}$ and using Azuma’s
inequality Bercu et al. (2015). Using the Azuma’s inequality, we can also
bound the deviations because of the stochasticity of the Markov Decision
Process. The result is stated in the following lemma.

###### Lemma 4

With probability at least $1-T^{-5/4}$, the regret incurred from imperfect
model knowledge and process stochastics is bounded by

$\displaystyle O\left(T_{M}S\sqrt{A(\log AT)/T}+\frac{CT_{M}S\log
T}{1-\rho}\right)$ (32)

(a) Regret decay w.r.t. time

(b) Service constraints w.r.t. time

(c) Flow constraints w.r.t. time

Figure 1: Performance of the proposed UC-CURL algorithm on a flow and service
control problem for a single queue with respect to algorithmic parameter $K$
and choice of policy update times. The algorithm does not violates the
constraints for higher value of $K$ at the expense of rewards regret.

The regret analysis framework also prepares us to bound the constraint
violations as well. We again start by quantifying the reasons for constraint
violations. The major reason the agent violates the constraint is because it
is playing with the imperfect knowledge of the MDP and the stochasticity of
the MDP which results in the deviation from the average costs. We note that
the conservative policy $\pi_{e}$ for every epoch does not violate the
constraints, but instead allows the agent to manage the constraint violations
because of the imperfect model knowledge and the system dynamics.

We note that the Lipschitz continuity of the constraint function $g$ allows us
to convert the function of $d$ averaged costs to the sum of $d$ averaged
costs. Further, we note that we can treat the cost similar to rewards Brantley
et al. (2020). This property allows us to bound the cost incurred incurred in
a way similar to how we bound the gap from the optimal reward by
$LdT_{M}S\sqrt{A(\log AT)/T}+(CT_{M}S\log T)/(1-\rho)$. We now want that the
slackness provided by the conservative policy should allow
$LdT_{M}S\sqrt{A(\log AT)/T}+(CT_{M}S\log T)/(1-\rho)$ constraint
violations222We thank the authors of Chen et al. (2022) for pointing out a
mistake in the previous version where we erroneously bounded the regret using
the diameter of the MDP instead of the mixing time of the MDP. We have fixed
that in our updated analysis using Lemma 8 which bounds the span by following
the reward optimal policy for the optimistic MDP in the true MDP till it
reaches a target state.. This is ensured by our chosen $\epsilon_{e}$
sequence. We formally state that result in the following lemma proven in parts
in Appendix B and Appendix C.

###### Lemma 5

The cumulative sum of the $\epsilon_{e}$ sequence is upper and lower bounded
as,

$\displaystyle\sum\nolimits_{e=1}^{E}(t_{e+1}-t_{e})\epsilon_{e}=\Theta\left(LdT_{M}S\sqrt{AT\log
T}\right)$ (33)

After giving the details on bounds on the possible sources of regret and
constraint violations, we can formally state the result in the form of
following theorem.

###### Theorem 1

For all $T$ and $K=\Theta(LdT_{M}S\sqrt{A})$, the regret $R(T)$ of UC-CURL
algorithm is bounded by

$\displaystyle R(T)=O\left(\frac{1}{\delta}LdT_{M}S\sqrt{A\frac{\log
AT}{T}}+\frac{C\log T}{1-\rho}\right)$ (34)

and the constraints are bounded as $C(T)=O(1/T)$, with probability at least
$1-\frac{1}{T^{5/4}}$.

Our Bellman error based analysis allows us remove the dependency on bounding
the number of epochs for infinite-horizon MDPs algorithms. We believe this is
an important step to possibly close the gap between the finite-horizon MDP
algorithms infinite-horizon MDP algorithms. Further, our decaying conservative
parameter $\epsilon_{e}$ also clears way to reduce dependency on parameter
knowledge of $T$ for practical algorithms.

The agent solves for the $\epsilon_{e}$-tight optimization problem for the
optimistic MDP at every epoch which may be a computationally inefficient step.
Thus, an can still prefer to choose a lesser number of epochs to reduce this
computational cost. Thus, an agent can choose a tradeoff between sample
efficiency by updating policy frequently and computational efficiency of the
logarithmic number of epochs.

##  6 Experimental Studies

We now evaluate the empirical performance of the proposed UC-CURL algorithm
using the flow and service control in a single-server queue, which is
introduced in (Altman and Schwartz, 1991).

We consider a discrete-time queue with a buffer of finite size $L$. The state
is the number of customers waiting in the queue with $S=L+1$. The system has
two types of actions, service and flow, to control the number of customers. At
time $t$, the agent takes action $a_{t}=(a_{t}(1),a_{t}(2))$ from a finite
subset of $[0,1]\times[0,1]$, where $a_{t}(1)$ is the service action and
$a_{t}(2)$ is the flow action. The service action $a_{t}(1)$ reduces the queue
length by $1$ with probability $a_{t}(1)$, and the flow action increases the
queue by $1$ with probability $a_{t}(2)$. Also, we assume that there is no
customer arriving when the queue is full. The precise environment and
implementation details are provided in Appendix E.

For $a_{t}\sim\pi$, the optimization problem is defined as

$\begin{split}\max_{\pi}&\quad\lim\limits_{T\rightarrow\infty}\frac{1}{T}\sum\nolimits_{t=1}^{T}(5-s_{t})\\\
s.t.&\quad\lim\limits_{T\rightarrow\infty}\frac{1}{T}\sum\nolimits_{t=1}^{T}(6-10a_{t}(1))\geq
0\\\
&\quad\lim\limits_{T\rightarrow\infty}\frac{1}{T}\sum\nolimits_{t=1}^{T}(2-8(1-a_{t}(2))^{2})\geq
0\end{split}$ (35)

We use the length of horizon $T=10^{5}$ and run 100 independent simulations of
the proposed UC-CURL algorithm. The result is shown in the Figure 1. The
average values of the long-term averaged reward and the constraint functions
are shown in the solid lines, and the shadow region denotes the standard
deviation. In order to compare this result to the optimal, we assume that the
full information of the transition dynamics is known and then use Linear
Programming to solve the problem. The optimal expected reward from LP is
$4.08$ for the true MDP. We now make the following observations based on the
simulation results.

Effect of the frequency of policy updates: We compare the UC-CURL algorithm in
Algorithm 1 with a modified algorithm which updates the policy after every
interaction with the environment. The number of epochs in Algorithm 1 is
bounded by $O(SA\log(T))$ (Jaksch et al., 2010, Proposition 18) whereas the
number of epochs of the modified algorithm is $T$. Our claim that the proposed
regret bounds does not depend on the number epochs, is empirically evident in
Figure 1(a). The regret of the doubling epoch based algorithm 1 matches the
regret guarantees of the everytime policy update strategy, however it does not
match the performance empirically. However, the doubling epoch based algorithm
obtains lower constraint violations as the agent plays $\epsilon_{e}$\-
conservative policy for longer duration, thus violating constraints less
(Figure 1(c) and Figure 1(b)). Compared to this, the agent which updates the
policy after every interaction, plays a lesser conservative policy and this
results in empirically increased constraints violations.

Effect of the parameter $K$ in UC-CURL algorithm: We note that in practice the
optimal $K=LdT_{M}S\sqrt{A}$ may be difficult to precisely calculate. Hence,
we evaluate the proposed UC-CURL algorithm for various values of $K$. If we
choose the multiplication factor $K=0$, we will not be achieving zero
constraint violations but still bounding the constraint violations with
$\tilde{O}(LdT_{M}S\sqrt{A/T})$. Note that as we increase the value of $K$,
the constraint violations decrease in Figure 1(b) and Figure 1(c). However,
this results in a lower reward value as observed in Figure 1(a). In principle,
the agent must select $K$ which allows to obtain a feasible policy and reduce
the violations.

##  7 Conclusion

We considered the problem of constrained Markov Decision Process with concave
objective and convex constraint. For this problem, we proposed UC-CURL
algorithm which works on the principle of optimism. To bound the constraint
violations, we solve for a conservative policy using an optimistic model for
an $\epsilon$-tight optimization problem. Using a novel analysis based on
Bellman error for infinite-horizon MDPs, we show the UC-CURL algorithm
achieves $O(1/T)$ constraint violations with a regret bound of
$\tilde{O}(LdT_{M}S\sqrt{A/T})$. A major limitation of the work in its current
form is the algorithm parameter $K$. Dynamically configuring $K$ is an
interesting direction for future work. Other future works include making the
algorithm more computationally efficient and creating model-free algorithms.

## References

  * Achiam et al. (2017) Joshua Achiam, David Held, Aviv Tamar, and Pieter Abbeel.  Constrained policy optimization.  In _International Conference on Machine Learning_ , pages 22–31. PMLR, 2017.
  * Agarwal and Aggarwal (2019) Mridul Agarwal and Vaneet Aggarwal.  Reinforcement learning for joint optimization of multiple rewards.  _arXiv preprint arXiv:1909.02940_ , 2019.
  * Agrawal and Jia (2017) Shipra Agrawal and Randy Jia.  Optimistic posterior sampling for reinforcement learning: worst-case regret bounds.  In _Advances in Neural Information Processing Systems_ , pages 1184–1194, 2017.
  * Altman and Schwartz (1991) E. Altman and A. Schwartz.  Adaptive control of constrained markov chains.  _IEEE Transactions on Automatic Control_ , 36(4):454–462, 1991.  doi: 10.1109/9.75103.
  * Altman (1999) Eitan Altman.  _Constrained Markov decision processes_ , volume 7.  CRC Press, 1999.
  * Bercu et al. (2015) Bernard Bercu, Bernard Delyon, and Emmanuel Rio.  _Concentration inequalities for sums and martingales_.  Springer, 2015.
  * Brantley et al. (2020) Kianté Brantley, Miroslav Dudik, Thodoris Lykouris, Sobhan Miryoosefi, Max Simchowitz, Aleksandrs Slivkins, and Wen Sun.  Constrained episodic reinforcement learning in concave-convex and knapsack settings.  _arXiv preprint arXiv:2006.05051_ , 2020.
  * Bubeck et al. (2015) Sébastien Bubeck et al.  Convex optimization: Algorithms and complexity.  _Foundations and Trends® in Machine Learning_ , 8(3-4):231–357, 2015.
  * Chen et al. (2022) Liyu Chen, Rahul Jain, and Haipeng Luo.  Learning infinite-horizon average-reward markov decision processes with constraints.  _arXiv preprint arXiv:2202.00150_ , 2022.
  * Cheung (2019) Wang Chi Cheung.  Regret minimization for reinforcement learning with vectorial feedback and complex objectives.  _Advances in Neural Information Processing Systems_ , 32:726–736, 2019.
  * 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, 2020.
  * Ding et al. (2021) Dongsheng Ding, Xiaohan Wei, Zhuoran Yang, Zhaoran Wang, and Mihailo Jovanovic.  Provably efficient safe exploration via primal-dual policy optimization.  In _International Conference on Artificial Intelligence and Statistics_ , pages 3304–3312. PMLR, 2021.
  * Efroni et al. (2020) Yonathan Efroni, Shie Mannor, and Matteo Pirotta.  Exploration-exploitation in constrained mdps.  _arXiv preprint arXiv:2003.02189_ , 2020.
  * Fruit et al. (2018) Ronan Fruit, Matteo Pirotta, Alessandro Lazaric, and Ronald Ortner.  Efficient bias-span-constrained exploration-exploitation in reinforcement learning.  In _International Conference on Machine Learning_ , pages 1578–1586. PMLR, 2018.
  * Gattami et al. (2021) Ather Gattami, Qinbo Bai, and Vaneet Aggarwal.  Reinforcement learning for constrained markov decision processes.  In _International Conference on Artificial Intelligence and Statistics_ , pages 2656–2664. PMLR, 2021.
  * Ghasemipour et al. (2020) Seyed Kamyar Seyed Ghasemipour, Richard Zemel, and Shixiang Gu.  A divergence minimization perspective on imitation learning methods.  In _Conference on Robot Learning_ , pages 1259–1277. PMLR, 2020.
  * Haarnoja et al. (2018) Tuomas Haarnoja, Aurick Zhou, Pieter Abbeel, and Sergey Levine.  Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with a stochastic actor.  In _International conference on machine learning_ , pages 1861–1870. PMLR, 2018.
  * 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.
  * Jaksch et al. (2010) Thomas Jaksch, Ronald Ortner, and Peter Auer.  Near-optimal regret bounds for reinforcement learning.  _Journal of Machine Learning Research_ , 11(Apr):1563–1600, 2010.
  * Jin et al. (2017) Chi Jin, Rong Ge, Praneeth Netrapalli, Sham M Kakade, and Michael I Jordan.  How to escape saddle points efficiently.  In _International Conference on Machine Learning_ , pages 1724–1732. PMLR, 2017.
  * Jin et al. (2018) Chi Jin, Zeyuan Allen-Zhu, Sebastien Bubeck, and Michael I Jordan.  Is q-learning provably efficient?  In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, editors, _Advances in Neural Information Processing Systems_ , volume 31. Curran Associates, Inc., 2018.  URL https://proceedings.neurips.cc/paper/2018/file/d3b1fb02964aa64e257f9f26a31f72cf-Paper.pdf.
  * Kalagarla et al. (2020) Krishna C Kalagarla, Rahul Jain, and Pierluigi Nuzzo.  A sample-efficient algorithm for episodic finite-horizon mdp with constraints.  _arXiv preprint arXiv:2009.11348_ , 2020.
  * Kwan et al. (2009) Raymond Kwan, Cyril Leung, and Jie Zhang.  Proportional fair multiuser scheduling in lte.  _IEEE Signal Processing Letters_ , 16(6):461–464, 2009.
  * Langford and Kakade (2002) J Langford and S Kakade.  Approximately optimal approximate reinforcement learning.  In _Proceedings of ICML_ , 2002.
  * Le et al. (2019) Hoang Le, Cameron Voloshin, and Yisong Yue.  Batch policy learning under constraints.  In _International Conference on Machine Learning_ , pages 3703–3712. PMLR, 2019.
  * Leike et al. (2017) Jan Leike, Miljan Martic, Victoria Krakovna, Pedro A Ortega, Tom Everitt, Andrew Lefrancq, Laurent Orseau, and Shane Legg.  Ai safety gridworlds.  _arXiv preprint arXiv:1711.09883_ , 2017.
  * Mnih et al. (2015) Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Marc G Bellemare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, et al.  Human-level control through deep reinforcement learning.  _nature_ , 518(7540):529–533, 2015.
  * Puterman (2014) Martin L Puterman.  _Markov decision processes: discrete stochastic dynamic programming_.  John Wiley & Sons, 2014.
  * Qiu et al. (2020) Shuang Qiu, Xiaohan Wei, Zhuoran Yang, Jieping Ye, and Zhaoran Wang.  Upper confidence primal-dual reinforcement learning for cmdp with adversarial loss.  In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin, editors, _Advances in Neural Information Processing Systems_ , volume 33, pages 15277–15287. Curran Associates, Inc., 2020.  URL https://proceedings.neurips.cc/paper/2020/file/ae95296e27d7f695f891cd26b4f37078-Paper.pdf.
  * Ray et al. (2019) Alex Ray, Joshua Achiam, and Dario Amodei.  Benchmarking safe exploration in deep reinforcement learning.  _arXiv preprint arXiv:1910.01708_ , 7, 2019.
  * Recht (2019) Benjamin Recht.  A tour of reinforcement learning: The view from continuous control.  _Annual Review of Control, Robotics, and Autonomous Systems_ , 2:253–279, 2019.
  * Schulman et al. (2017) John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov.  Proximal policy optimization algorithms.  _arXiv preprint arXiv:1707.06347_ , 2017.
  * Singh et al. (2020) Rahul Singh, Abhishek Gupta, and Ness B Shroff.  Learning in markov decision processes under constraints.  _arXiv preprint arXiv:2002.12435_ , 2020.
  * Sutton and Barto (2018) Richard S Sutton and Andrew G Barto.  _Reinforcement learning: An introduction_.  MIT press, 2018.
  * Tessler et al. (2018) Chen Tessler, Daniel J Mankowitz, and Shie Mannor.  Reward constrained policy optimization.  In _International Conference on Learning Representations_ , 2018.
  * Wei et al. (2021) Honghao Wei, Xin Liu, and Lei Ying.  A provably-efficient model-free algorithm for constrained markov decision processes.  _arXiv preprint arXiv:2106.01577_ , 2021.
  * Weissman et al. (2003) Tsachy Weissman, Erik Ordentlich, Gadiel Seroussi, Sergio Verdu, and Marcelo J Weinberger.  Inequalities for the l1 deviation of the empirical distribution.  _Hewlett-Packard Labs, Tech. Rep_ , 2003.
  * Xu et al. (2020) Tengyu Xu, Yingbin Liang, and Guanghui Lan.  A primal approach to constrained policy optimization: Global optimality and finite-time analysis.  _arXiv preprint arXiv:2011.05869_ , 2020.
  * Yu et al. (2021) Tiancheng Yu, Yi Tian, Jingzhao Zhang, and Suvrit Sra.  Provably efficient algorithms for multi-objective competitive rl.  In Marina Meila and Tong Zhang, editors, _Proceedings of the 38th International Conference on Machine Learning_ , volume 139 of _Proceedings of Machine Learning Research_ , pages 12167–12176. PMLR, 18–24 Jul 2021.
  * Zhang et al. (2020) Junyu Zhang, Alec Koppel, Amrit Singh Bedi, Csaba Szepesvari, and Mengdi Wang.  Variational policy gradient method for reinforcement learning with general utilities.  _Advances in Neural Information Processing Systems_ , 33:4572–4583, 2020.
  * Zheng and Ratliff (2020) Liyuan Zheng and Lillian Ratliff.  Constrained upper confidence reinforcement learning.  In _Learning for Dynamics and Control_ , pages 620–629. PMLR, 2020\.

##  A Proof of Lemma 1

Proof  Note that $\rho^{P}_{\pi^{*}}$ denotes the stationary distribution of
the optimal solution which satisfies

$\displaystyle
g\left(\sum_{s,a}\rho^{P}_{\pi^{*}}(s,a)c_{1}(s,a),\cdots,\sum_{s,a}\rho^{P}_{\pi^{*}}(s,a)c_{d}(s,a)\right)\leq
C$ (36)

Further, from Assumption 5, we have a feasible policy $\pi$ for which

$\displaystyle
g\left(\sum_{s,a}\rho^{P}_{\pi}(s,a)r_{1}(s,a),\cdots,\sum_{s,a}\rho^{P}_{\pi}(s,a)r_{K}(s,a)\right)\leq
C-\delta$ (37)

We now construct a stationary distribution $\rho^{P}$ obtain the corresponding
$\pi_{e}^{\prime}$ as:

$\displaystyle\rho^{P}(s,a)=\left(1-\frac{\epsilon_{e}}{\delta}\right)\rho^{P}_{\pi^{*}}(s,a)+\frac{\epsilon_{e}}{\delta}\rho^{P}_{\pi}(s,a)$
(38)
$\displaystyle\pi_{e}^{\prime}=\rho^{P}(s,a)/\left(\sum_{s,b}\rho^{P}(s,b)\right)$
(39)

For this new policy, for the convex constraint $g$, we observe that,

$\displaystyle
g\left(\sum_{s,a}\rho^{P}_{\pi}(s,a)c_{1}(s,a),\cdots,\sum_{s,a}\rho^{P}_{\pi}(s,a)c_{d}(s,a)\right)$
(40)
$\displaystyle=g\left(\sum_{s,a}\right(\left(1-\frac{\epsilon_{e}}{\delta}\right)\rho^{P}_{\pi^{*}}+\frac{\epsilon_{e}}{\delta}\rho^{P}_{\pi}\left)(s,a)r_{1}(s,a),\cdots,\sum_{s,a}\left(\left(1-\frac{\epsilon_{e}}{\delta}\right)\rho^{P}_{\pi^{*}}+\frac{\epsilon_{e}}{\delta}\rho^{P}_{\pi}\right)(s,a)r_{K}(s,a)\right)$
(41)
$\displaystyle\leq\left(1-\frac{\epsilon_{e}}{\delta}\right)g\left(\sum_{s,a}\rho^{P}_{\pi^{*}}(s,a)c_{1}(s,a),\cdots,\sum_{s,a}\rho^{P}_{\pi^{*}}(s,a)c_{d}(s,a)\right)$
$\displaystyle~{}~{}~{}+\frac{\epsilon_{e}}{\delta}g\left(\sum_{s,a}\rho^{P}_{\pi}(s,a)c_{1}(s,a),\cdots,\sum_{s,a}\rho^{P}_{\pi}(s,a)c_{d}(s,a)\right)$
(42)
$\displaystyle\leq\left(1-\frac{\epsilon_{e}}{\delta}\right)C+\frac{\epsilon_{e}}{\delta}\left(C-\delta\right)$
(43) $\displaystyle=C-\delta\leq C-\epsilon_{e}$ (44)

where Equation (42) follows from the convexity of the constraints. Equation
(43) follows from Equation (36) and Equation (37)
Now, note that the policy $\pi_{e}^{\prime}$ corresponding to stationary
distribution constructed in Equation (38) satisfies the $\epsilon_{e}$-tight
constraints. Further, we find $\pi_{e}^{*}$ as the optimal solution for the
$\epsilon_{e}$-tight optimization problem. Hence, we have

$\displaystyle
f\left(\sum_{s,a}\rho^{P}_{\pi^{*}}(s,a)r(s,a)\right)-f\left(\sum_{s,a}\rho^{P}_{\pi_{e}^{*}}(s,a)r(s,a)\right)$
$\displaystyle\leq
f\left(\sum_{s,a}\rho^{P}_{\pi^{*}}(s,a)r(s,a)\right)-f\left(\sum_{s,a}\rho^{P}(s,a)r(s,a)\right)$
(45) $\displaystyle\leq
L\Big{|}\sum_{s,a}\left(\rho^{P}_{\pi^{*}}(s,a)-\rho^{P}(s,a)\right)r(s,a)\Big{|}$
(46) $\displaystyle\leq
L\Big{|}\sum_{s,a}\left(\rho^{P}_{\pi^{*}}(s,a)-\left(1-\frac{\epsilon_{e}}{\delta}\right)\rho^{P}_{\pi^{*}}(s,a)-\frac{\epsilon_{e}}{\delta}\rho^{P}_{\pi}(s,a)\right)r_{d}(s,a)\Big{|}$
(47) $\displaystyle\leq
L\frac{\epsilon_{e}}{\delta}\Big{|}\sum_{s,a}\left(\rho^{P}_{\pi^{*}}(s,a)-\rho^{P}_{\pi}(s,a)\right)r(s,a)\Big{|}$
(48) $\displaystyle\leq
L\frac{\epsilon_{e}}{\delta}\Big{|}\sum_{s,a}\rho^{P}_{\pi^{*}}r(s,a)\Big{|}+L\frac{\epsilon_{e}}{\delta}\Big{|}\sum_{s,a}\rho^{P}_{\pi}(s,a)r(s,a)\Big{|}$
(49) $\displaystyle\leq 2L\frac{\epsilon_{e}}{\delta}$ (50)

where, Equation (46) follows from the Lipschitz assumption on the joint
objective $f$. Equation (50) follows from the fact that $r_{k}(s,a)\leq 1$ for
all $k\in[K]$ and for all $(s,a)\in\mathcal{S}\times\mathcal{A}$.

##  B Objective Regret Bound

To bound the regret $R(T)$, we first consider two cases. First case is where
the confidence intervals in Equation (24).

For the second case now holds with probability at-least $1-\frac{1}{T^{5/4}}$,
we break the regret into multiple components. We can then bound these
components individually.

### Regret breakdown

We first break down our regret into multiple parts which will help us bound
the regret.

$\displaystyle R(T)$
$\displaystyle=f(\lambda_{*}^{P})-f\left(\frac{1}{T}\sum_{t=1}^{T}r_{t}(s_{t},a_{t})\right)$
(51)
$\displaystyle=f(\lambda_{*}^{P})-\frac{1}{T}\sum_{e=1}^{E}T_{e}f(\lambda_{\pi_{e}^{*}}^{P})+\frac{1}{T}\sum_{e=1}^{E}T_{e}f(\lambda_{\pi_{e}^{*}}^{P})-f\left(\frac{1}{T}\sum_{t=1}^{T}r_{t}(s_{t},a_{t})\right)$
(52)
$\displaystyle=\frac{1}{T}\sum_{e=1}^{E}T_{e}\left(f(\lambda_{*}^{P})-f(\lambda_{\pi_{e}^{*}}^{P})\right)+\frac{1}{T}\sum_{e=1}^{E}T_{e}f(\lambda_{\pi_{e}^{*}}^{P})-f\left(\frac{1}{T}\sum_{t=1}^{T}r_{t}(s_{t},a_{t})\right)$
(53)
$\displaystyle\leq\frac{1}{T}\sum_{e=1}^{E}T_{e}\left(f(\lambda_{*}^{P})-f(\lambda_{\pi_{e}^{*}}^{P})\right)+\frac{1}{T}\sum_{e=1}^{E}T_{e}f(\lambda_{\pi_{e}}^{\tilde{P}_{e}})-f\left(\frac{1}{T}\sum_{t=1}^{T}r_{t}(s_{t},a_{t})\right)$
(54)
$\displaystyle\leq\frac{1}{T}\sum_{e=1}^{E}T_{e}\left(f(\lambda_{*}^{P})-f(\lambda_{\pi_{e}^{*}}^{P})\right)+f\left(\frac{1}{T}\sum_{e=1}^{E}T_{e}\lambda_{\pi_{e}}^{\tilde{P}_{e}}\right)-f\left(\frac{1}{T}\sum_{t=1}^{T}r_{t}(s_{t},a_{t})\right)$
(55)
$\displaystyle\leq\frac{1}{T}\sum_{e=1}^{E}T_{e}\left(f(\lambda_{*}^{P})-f(\lambda_{\pi_{e}^{*}}^{P})\right)+L\Big{|}\frac{1}{T}\sum_{e=1}^{E}T_{e}\lambda_{\pi_{e}}^{\tilde{P}_{e}}-\frac{1}{T}\sum_{t=1}^{T}r_{t}(s_{t},a_{t})\Big{|}$
(56)
$\displaystyle=\frac{1}{T}\sum_{e=1}^{E}T_{e}\left(f(\lambda_{*}^{P})-f(\lambda_{\pi_{e}^{*}}^{P})\right)+L\Big{|}\frac{1}{T}\sum_{e=1}^{E}\sum_{t=t_{e}}^{t_{e+1}-1}\left(\lambda_{\pi_{e}}^{\tilde{P}_{e}}-\lambda_{\pi_{e}}^{P}+\lambda_{\pi_{e}}^{P}-r_{t}(s_{t},a_{t})\right)\Big{|}$
(57)
$\displaystyle\leq\frac{1}{T}\sum_{e=1}^{E}T_{e}\left(f(\lambda_{*}^{P})-f(\lambda_{\pi_{e}^{*}}^{P})\right)+L\Big{|}\frac{1}{T}\sum_{e=1}^{E}\sum_{t=t_{e}}^{t_{e+1}-1}\left(\lambda_{\pi_{e}}^{\tilde{P}_{e}}-\lambda_{\pi_{e}}^{P}\right)\Big{|}+L\Big{|}\frac{1}{T}\sum_{e=1}^{E}\sum_{t=t_{e}}^{t_{e+1}-1}\left(\lambda_{\pi_{e}}^{P}-r_{t}(s_{t},a_{t})\right)\Big{|}$
(58) $\displaystyle=R_{1}(T)+R_{2}(T)+R_{3}(T)$ (59)

where Equation (54) comes from the fact that the policy $\pi_{e}$ is for the
optimistic CMDP and provides a higher value of the function $f$. Equation 55
comes from the concavity of the function $f$, and Equation 56 comes from the
Lipschitz continuity of the function $f$. The three terms in Equation (59) are
now defined as:

$\displaystyle R_{1}(T)$
$\displaystyle=\frac{L}{T}\sum_{e=1}^{E}T_{e}\left(f(\lambda_{*}^{P})-f(\lambda_{\pi_{e}^{*}}^{P})\right)$
(60)

$R_{1}(T)$ denotes the regret incurred from not playing the optimal policy
$\pi^{*}$ for the true optimization problem in Equation (16) but the optimal
policy $\pi_{e}^{*}$ for the $\epsilon_{e}$-tight optimization problem in
epoch $e$.

$\displaystyle R_{2}(T)$
$\displaystyle=\frac{L}{T}\Big{|}\sum_{e=1}^{E}\sum_{t=t_{e}}^{t_{e+1}-1}\left(\lambda_{\pi_{e}}^{\tilde{P}_{e}}-\lambda_{\pi_{e}}^{P}\right)\Big{|}$
(61)

$R_{2}(T)$ denotes the gap between expected rewards from playing the optimal
policy $\pi_{e}$ for $\epsilon_{e}$-tight optimization problem on the
optimistic MDP instead of the true MDP. We further upper bound the $R_{2}(T)$
term by choosing an MDP in the confidence interval which maximizes the rewards
for $\pi_{e}$. To reduce notational clutter, we relabel this MDP as
$\tilde{P}_{e}$ or

$\tilde{P}_{e}=\max_{P_{e}}\lambda_{\pi_{e}}^{P_{e}},$

where $P_{e}$ are the transition probabilities in the confidence intervals at
epoch $e$. Hence, we get,

$\displaystyle R_{2}(T)$
$\displaystyle\leq\frac{L}{T}\Big{|}\sum_{e=1}^{E}\sum_{t=t_{e}}^{t_{e+1}-1}\left(\lambda_{\pi_{e}}^{\tilde{P}_{e}}-\lambda_{\pi_{e}}^{P}\right)\Big{|}$
(62)

$\displaystyle R_{3}(T)$
$\displaystyle=\frac{L}{T}\Big{|}\sum_{e=1}^{E}\sum_{t=t_{e}}^{t_{e+1}-1}\left(\lambda_{\pi_{e}}^{P}-r_{t}(s_{t},a_{t})\right)\Big{|}$
(63)

$R_{3}(T)$ denotes the gap between obtained rewards from playing the optimal
policy $\pi_{e}$ for $\epsilon_{e}$-tight optimization problem the true MDP
and the expected per-step reward of playing the optimal policy $\pi_{e}$ for
$\epsilon_{e}$-tight optimization problem the true MDP.

### Bounding $R_{1}(T)$

Bounding $R_{1}(T)$ requires using Lemma 1. We have the following set of
equations:

$\displaystyle R_{1}(T)$
$\displaystyle=\frac{1}{T}\sum_{e=1}^{E}\sum_{t=t_{e}}^{t_{e+1}-1}\left(f(\lambda_{*}^{P})-f(\lambda_{\pi_{e}^{*}}^{P})\right)$
(64)
$\displaystyle\leq\frac{1}{T}\sum_{e=1}^{E}\sum_{t=t_{e}}^{t_{e+1}-1}\frac{2L\epsilon_{e}}{\delta}$
(65)
$\displaystyle=\frac{2L}{T\delta}\sum_{e=1}^{E}\sum_{t=t_{e}}^{t_{e+1}-1}\sqrt{\frac{\log
t}{t}}$ (66)
$\displaystyle\leq\frac{2L}{T\delta}\sum_{e=1}^{E}\sum_{s,a}\nu_{e}(s,a)\sqrt{\frac{\log
T}{N_{e}(s,a)}}$ (67) $\displaystyle\leq\frac{2L\sqrt{\log
T}}{T\delta}\sum_{s,a}\sum_{e=1}^{E}\frac{\nu_{e}(s,a)}{\sqrt{N_{e}(s,a)}}$
(68) $\displaystyle\leq(\sqrt{2}+1)\frac{2L\sqrt{\log
T}}{T\delta}\sum_{s,a}\sqrt{N(s,a)}$ (69)
$\displaystyle\leq(\sqrt{2}+1)\frac{2L\sqrt{\log
T}}{T\delta}\sqrt{(\sum_{s,a}1)\sum_{s,a}N(s,a)}$ (70)
$\displaystyle\leq(\sqrt{2}+1)\frac{2L\sqrt{\log T}}{T\delta}\sqrt{SAT}$ (71)

where Equation (67) follows from the fact that $\log t\leq\log T$ for all
$t\leq T$ and $N_{e}(s,a)\leq t_{e}\leq t$ for all $t$. The bound on summation
over $e$ in Equation (69) follows from (Jaksch et al., 2010, Lemma 19).
Finally, equation (70) follows from the Cauchy-Schwarz inequality.

### Bounding $R_{2}(T)$

We relate the difference between long-term average rewards for running the
optimistic policy $\pi_{e}$ on the optimistic MDP
$\lambda_{\pi_{e}}^{\tilde{P}_{e}}$ and the long-term average rewards for
running the optimistic policy $\pi_{e}$ on the true MDP
($\lambda_{\pi_{e}}^{P}$) with the Bellman error. Formally, we have the
following lemma:

###### Lemma 6

The difference of long-term average rewards for running the optimistic policy
$\pi_{e}$ on the optimistic MDP, $\lambda_{\pi_{e}}^{\tilde{P}_{e}}$, and the
average long-term average rewards for running the optimistic policy $\pi_{e}$
on the true MDP, $\lambda_{\pi_{e}}^{P}$, is the long-term average Bellman
error as

$\displaystyle\lambda_{\pi_{e}}^{\tilde{P}_{e}}-\lambda_{\pi_{e}}^{P}=\sum_{s,a}\rho_{\pi_{e}}^{P}B^{\pi_{e},\tilde{P}_{e}}(s,a)$
(72)

Proof  Note that for all $s\in\mathcal{S}$, we have:

$\displaystyle V_{\gamma}^{\pi_{e},\tilde{P}_{e}}(s)$
$\displaystyle=\mathbb{E}_{a\sim\pi_{e}}\left[Q_{\gamma}^{\pi_{e},\tilde{P}_{e}}(s,a)\right]$
(73)
$\displaystyle=\mathbb{E}_{a\sim\pi_{e}}\left[B^{\pi_{e},\tilde{P}_{e}}(s,a)+r(s,a)+\gamma\sum_{s^{\prime}\in\mathcal{S}}P(s^{\prime}|s,a)V_{\gamma}^{\pi_{e},\tilde{P}_{e}}(s^{\prime})\right]$
(74)

where Equation (74) follows from the definition of the Bellman error for state
action pair $s,a$.

Similarly, for the true MDP, we have,

$\displaystyle V_{\gamma}^{\pi_{e},P}(s)$
$\displaystyle=\mathbb{E}_{a\sim\pi_{e}}\left[Q_{\gamma}^{\pi_{e},}(s,a)\right]$
(75)
$\displaystyle=\mathbb{E}_{a\sim\pi_{e}}\left[r(s,a)+\gamma\sum_{s^{\prime}\in\mathcal{S}}P(s^{\prime}|s,a)V_{\gamma}^{\pi_{e},P}(s^{\prime})\right]$
(76)

Subtracting Equation (76) from Equation (74), we get:

$\displaystyle
V_{\gamma}^{\pi_{e},\tilde{P}_{e}}(s)-V_{\gamma}^{\pi_{e},P}(s)$
$\displaystyle=\mathbb{E}_{a\sim\pi_{e}}\left[B^{\pi_{e},\tilde{P}_{e}}(s,a)+\gamma\sum_{s^{\prime}\in\mathcal{S}}P(s^{\prime}|s,a)\left(V_{\gamma}^{\pi_{e},\tilde{P}_{e}}-V_{\gamma}^{\pi_{e},\tilde{P}_{e}}\right)(s^{\prime})\right]$
(77)
$\displaystyle=\mathbb{E}_{a\sim\pi_{e}}\left[B^{\pi_{e},\tilde{P}_{e}}(s,a)\right]+\gamma\sum_{s^{\prime}\in\mathcal{S}}P_{\pi_{e}}\left(V_{\gamma}^{\pi_{e},\tilde{P}_{e}}-V_{\gamma}^{\pi_{e},\tilde{P}_{e}}\right)(s^{\prime})$
(78)

Using the vector format for the value functions, we have,

$\displaystyle\bar{V}_{\gamma}^{\pi_{e},\tilde{P}_{e}}-\bar{V}_{\gamma}^{\pi_{e},P}$
$\displaystyle=\left(I-\gamma
P_{\pi_{e}}\right)^{-1}\overline{B}_{\pi_{e}}^{\pi_{e},\tilde{P}_{e}}$ (79)

Now, converting the value function to average per-step reward we have,

$\displaystyle\lambda_{\pi_{e}}^{\tilde{P}_{e}}\bm{1}_{S}-\lambda_{\pi_{e}}^{P}\bm{1}_{S}$
$\displaystyle=\lim_{\gamma\to
1}(1-\gamma)\left(\bar{V}_{\gamma}^{\pi_{e},\tilde{P}_{e}}-\bar{V}_{\gamma}^{\pi_{e},P}\right)$
(80) $\displaystyle=\lim_{\gamma\to 1}(1-\gamma)\left(I-\gamma
P_{\pi_{e}}\right)^{-1}\overline{B}_{\pi_{e}}^{\pi_{e},\tilde{P}_{e}}$ (81)
$\displaystyle=\left(\sum_{s,a}\rho_{\pi_{e}}^{P}B^{\pi_{e},\tilde{P}_{e}}(s,a)\right)\bm{1}_{S}$
(82)

where the last equation follows from the definition of occupancy measures by
Puterman (2014).

###### Remark 2

Note that the Bellman error is not to be confused by Advantage function and
policy improvement lemma Langford and Kakade (2002). The policy improvement
lemma relates the performance of two policies on same MDP whereas we bounded
the performance of one policy on two different MDPs in Lemma 6

We now want to bound the Bellman errors to bound the gap between the average
per-step reward $\lambda_{\pi_{e}}^{\tilde{P}_{e}}$, and
$\lambda_{\pi_{e}}^{P}$. From the definition of Bellman error and the
confidence intervals on the estimated transition probabilities, we obtain the
following lemma:

###### Lemma 7

With probability at least $1-1/t_{e}^{6}$, the Bellman error
$B^{\pi_{e},\tilde{P}_{e}}(s,a)$ for state-action pair $s,a$ in epoch $e$ is
upper bounded as

$\displaystyle
B^{\pi_{e},\tilde{P}_{e}}(s,a)\leq\sqrt{\frac{14S\log(2AT)}{1\vee
N_{e}(s,a)}}\|\tilde{h}\|_{\infty}$ (83)

Proof  Starting with the definition of Bellman error in Equation (28), we get

$\displaystyle B^{\pi_{e},\tilde{P}_{e}}(s,a)$ $\displaystyle=\lim_{\gamma\to
1}\left(Q_{\gamma}^{\pi_{e},\mathcal{P}}(s,a)-\left(r(s,a)+\gamma\sum_{s^{\prime}\in\mathcal{S}}P(s^{\prime}|s,a)V_{\gamma}^{\pi_{e},\tilde{P}_{e}}\right)\right)$
(84) $\displaystyle=\lim_{\gamma\to
1}\left(\left(r(s,a)+\gamma\sum_{s^{\prime}\in\mathcal{S}}\tilde{P}_{e}(s^{\prime}|s,a)V_{\gamma}^{\pi_{e},\tilde{P}_{e}}(s^{\prime})\right)-\left(r(s,a)+\gamma\sum_{s^{\prime}\in\mathcal{S}}P(s^{\prime}|s,a)V_{\gamma}^{\pi_{e},\tilde{P}_{e}}(s^{\prime})\right)\right)$
(85) $\displaystyle=\lim_{\gamma\to
1}\gamma\sum_{s^{\prime}\in\mathcal{S}}\left(\tilde{P}_{e}(s^{\prime}|s,a)-P(s^{\prime}|s,a)\right)V_{\gamma}^{\pi_{e},\tilde{P}_{e}}(s^{\prime})$
(86) $\displaystyle=\lim_{\gamma\to
1}\gamma\left(\sum_{s^{\prime}\in\mathcal{S}}\left(\tilde{P}_{e}(s^{\prime}|s,a)-P(s^{\prime}|s,a)\right)V_{\gamma}^{\pi_{e},\tilde{P}_{e}}(s^{\prime})+V_{\gamma}^{\pi_{e},\tilde{P}_{e}}(s)-V_{\gamma}^{\pi_{e},\tilde{P}_{e}}(s)\right)$
(87) $\displaystyle=\lim_{\gamma\to
1}\gamma\left(\sum_{s^{\prime}\in\mathcal{S}}\left(\tilde{P}_{e}(s^{\prime}|s,a)-P(s^{\prime}|s,a)\right)V_{\gamma}^{\pi_{e},\tilde{P}_{e}}(s^{\prime})-\sum_{s^{\prime}\in\mathcal{S}}\tilde{P}_{e}(s^{\prime}|s,a)V_{\gamma}^{\pi_{e},\tilde{P}_{e}}(s)+\sum_{s^{\prime}\in\mathcal{S}}P(s^{\prime}|s,a)V_{\gamma}^{\pi_{e},\tilde{P}_{e}}(s)\right)$
(88) $\displaystyle=\lim_{\gamma\to
1}\gamma\left(\sum_{s^{\prime}\in\mathcal{S}}\left(\tilde{P}_{e}(s^{\prime}|s,a)-P(s^{\prime}|s,a)\right)\left(V_{\gamma}^{\pi_{e},\tilde{P}_{e}}(s^{\prime})-V_{\gamma}^{\pi_{e},\tilde{P}_{e}}(s)\right)\right)$
(89)
$\displaystyle=\left(\sum_{s^{\prime}\in\mathcal{S}}\left(\tilde{P}_{e}(s^{\prime}|s,a)-P(s^{\prime}|s,a)\right)\lim_{\gamma\to
1}\gamma\left(V_{\gamma}^{\pi_{e},\tilde{P}_{e}}(s^{\prime})-V_{\gamma}^{\pi_{e},\tilde{P}_{e}}(s)\right)\right)$
(90)
$\displaystyle=\left(\sum_{s^{\prime}\in\mathcal{S}}\left(\tilde{P}_{e}(s^{\prime}|s,a)-P(s^{\prime}|s,a)\right)h(s^{\prime})\right)$
(91)
$\displaystyle\leq\Big{\|}\left(\tilde{P}_{e}(\cdot|s,a)-P(\cdot|s,a)\right)\Big{\|}_{1}$
(92) $\displaystyle\leq 2\sqrt{\frac{14S\log(2At)}{1\vee
N_{e}(s,a)}}\|\tilde{h}(\cdot)\|_{\infty}$ (93) $\displaystyle\leq
2\sqrt{\frac{14S\log(2AT)}{1\vee N_{e}(s,a)}}\|\tilde{h}(\cdot)\|_{\infty}$
(94)

where Equation (86) comes from the assumption that the rewards are known to
the agent. Equation (90) follows from the fact that the difference between
value function at two states is bounded. Equation (91) comes from the
definition of bias term Puterman (2014). Equation (92) follows from Hölder’s
inequality. In Equation (93). Also, the $\ell_{1}$ norm of probability vector
is bounded using Lemma 11 for start time $t_{e}$ of epoch $e$.

Additionally, note that the $\ell_{1}$ norm in Equation (92) is bounded by
$2$. Thus the Bellman error is loose upper bounded by
$2\|\tilde{h}(\cdot)\|_{\infty}$ for all state-action pairs.

We still now need to bound the bias of the optimistic MDP
$\|\tilde{h}(\cdot)\|_{\infty}$ to problem specific variables to obtain a
meaningful bound. For this, note that we $\tilde{h}(\cdot)$ is the bias of the
MDP for which policy $\pi_{e}$ obtains the maximum average reward in the
confidence interval. Based on this observation, we obtain the following lemma:

###### Lemma 8

For a MDP with rewards $r(s,a)$ and transition probabilities $\tilde{P}_{e}$,
using policy $\pi_{e}$, the difference of bias of any two states $s$, and
$s^{\prime}$ is bounded as $\tilde{h}(s)-\tilde{h}(s^{\prime})\leq
T_{M}~{}\forall~{}s,s^{\prime}\in\mathcal{S}$.

Proof  Note that
$\lambda_{\pi_{e}}^{\tilde{P}_{e}}\geq\lambda_{\pi_{e}}^{P_{e}}$ for all
$P_{e}$ in the confidence set. Now, consider the following Bellman equation

$\displaystyle\tilde{h}(s)$
$\displaystyle=r_{\pi_{e}}(s,a)-\lambda_{\pi_{e}}^{P_{e}}+(\tilde{P}_{\pi_{e},e}(\cdot|s))^{T}\tilde{h}$
$\displaystyle:=T\tilde{h}(s)$

where $r_{\pi_{e}}(s)=\sum_{a}\pi_{e}(a|s)r(s,a)$ and
$\tilde{P}_{\pi_{e},e}(s^{\prime}|s)=\sum_{a}\pi(a|s)\tilde{P}_{e}(s^{\prime}|s,a)$.

Consider two states $s,s^{\prime}\in\mathcal{S}$. Also, let $\tau=\min\\{t\geq
1:s_{t}=s^{\prime},s_{1}=s\\}$ be a random variable. With
$P_{\pi_{e}}(\cdot|s)$ $=\sum_{a}\pi_{e}(a|s)P(s^{\prime}|s,a)$, we also
define another operator,

$\displaystyle\bar{T}h(s)$
$\displaystyle=(\min_{s,a}r(s,a)-\lambda_{\pi_{e}}^{P_{e}}+(P_{\pi_{e}}(\cdot|s))^{T}h)\mathbf{1}(s\neq
s^{\prime})+h_{\pi_{e}}^{P_{e}}(s^{\prime})\mathbf{1}(s=s^{\prime}).$

Note that $\bar{T}\tilde{h}(s)\leq T\tilde{h}(s)=\tilde{h}(s)$ for all $s$
since $P_{e}$ maximizes the reward $r$ over all the transition probabilities
in the confidence set of Equation (24) including the true transition
probability $P$. Further, for any two vectors $u,v\in\mathbb{R}^{S}$ with
$u(s)\geq v(s)\forall s$, we have $\bar{T}u\geq\bar{T}v$. Hence, we have
$\bar{T}^{n}\tilde{h}(s)\leq\tilde{h}(s)$ for all $s$. Hence, we have

$\displaystyle\tilde{h}(s)$ $\displaystyle\geq\bar{T}^{n}(s)$
$\displaystyle=\mathbb{E}\big{[}-(\lambda_{\pi_{e}}^{P_{e}}-\min_{s,a}r(s,a))(n\wedge\tau)+\tilde{h}(s_{n\wedge\tau})\big{]}$

Taking $\lim n\to\infty$, we have
$\tilde{h}(s)\geq\tilde{h}(s^{\prime})-T_{M}$, thus completing the proof.

Combining Lemma 8 with Lemma 7, we get the following result

$\displaystyle
B^{\pi_{e},\tilde{P}_{e}}(s,a)\leq\sqrt{\frac{14S\log(2AT)}{1\vee
N_{e}(s,a)}}\|\tilde{h}\|_{\infty}\leq\sqrt{\frac{14S\log(2AT)}{1\vee
N_{e}(s,a)}}T_{M}$ (95)

Note that we have converted the difference of average rewards into the average
Bellman error. Also, we have bounded the Bellman error of a state-action pair.
We now need to bound the expected value in Equation (72). We bound the average
Bellman error of an epoch using the realizations of Bellman error at state-
action pairs visited in an epoch. For this, we present the following lemma.

###### Lemma 9

With probability at least $1-1/T^{6}$, the cumulative expected bellman error
is bounded as:

$\displaystyle\sum_{e=1}^{E}(t_{e+1}-t_{e})\mathbb{E}_{\pi_{e},P}\left[B^{\pi_{e},\tilde{P}_{e}}(s,a)\right]\leq\sum_{e=1}^{E}\sum_{t=t_{e}}^{t_{e+1}-1}B^{\pi_{e},\tilde{P}_{e}}(s_{t},a_{t})+4D\sqrt{6T\log(T)}+\frac{2CT_{M}ES}{1-\rho}$
(96)

Proof  Note that conditioned on filtration
$H_{t_{e}}=\\{s_{1},a_{1},\cdots,s_{t_{e}},a_{t_{e}}\\}$ the two expectations
$\mathbb{E}_{s,a\sim\pi_{e},P}[\cdot]$ and
$\mathbb{E}_{s,a\sim\pi_{e},P}[\cdot|H_{t_{e}-1}]$ are not equal as the former
is the expected value of the long-term state distribution and the later is the
long-term state distribution condition on initial state $s_{t_{e}-1}$. We now
use Assumption 1 to obtain the following set of inequalities.

$\displaystyle\mathbb{E}_{(s,a)\sim\pi_{e},P}[B^{\pi_{e},\tilde{P}_{e}}(s,a)]$
$\displaystyle=\mathbb{E}_{(s,a)\sim\pi_{e},P}[B^{\pi_{e},\tilde{P}_{e}}(s,a)]\pm\mathbb{E}_{(s_{t},a_{t})\sim\pi_{e},P}[B^{\pi_{e},\tilde{P}_{e}}(s_{t},a_{t})|H_{t_{e}-1}]$
(97)
$\displaystyle=\mathbb{E}_{(s_{t},a_{t})\sim\pi_{e},P}[B^{\pi_{e},\tilde{P}_{e}}(s_{t},a_{t})|H_{t_{e}-1}]$
$\displaystyle~{}~{}+\left(\mathbb{E}_{(s,a)\sim\pi_{e},P}[B^{\pi_{e},\tilde{P}_{e}}(s,a)]-\mathbb{E}_{(s_{t},a_{t})\sim\pi_{e},P}[B^{\pi_{e},\tilde{P}_{e}}(s_{t},a_{t})|H_{t_{e}-1}]\right)$
(98)
$\displaystyle=\mathbb{E}_{(s_{t},a_{t})\sim\pi_{e},P}[B^{\pi_{e},\tilde{P}_{e}}(s_{t},a_{t})|H_{t_{e}-1}]$
$\displaystyle~{}~{}+2T_{M}\left(\|\pi_{e}(a|s)d_{\pi_{e}}(s)-\pi_{e}(a|s)P_{\pi,s_{t_{e}-1}}^{t-t_{e}+1}(s)\|_{TV}\right)$
(99)
$\displaystyle=\mathbb{E}_{(s_{t},a_{t})\sim\pi_{e},P}[B^{\pi_{e},\tilde{P}_{e}}(s_{t},a_{t})|H_{t_{e}-1}]+2CT_{M}S\rho^{t-t_{e}}$
(100)

where Equation 99 comes from Assumption 1 for running policy $\pi_{e}$
starting from state $s_{t_{e}-1}$ for $t-t_{e}+1$ steps and from Lemma 3.
Equation (100) follows from bounding the total-variation distance for all
states and from the fact that $\sum_{a}\pi(a|s)=1$.

Using Equation (100) we get,

$\displaystyle\sum_{e=1}^{E}(t_{e+1}-t_{e})\mathbb{E}_{\pi_{e},P}\left[B^{\pi_{e},\tilde{P}_{e}}(s,a)\right]$
$\displaystyle=\sum_{e=1}^{E}\sum_{t=t_{e}}^{t_{e+1}-1}\mathbb{E}_{(s_{t},a_{t})\sim\pi_{e},P}[B^{\pi_{e},\tilde{P}_{e}}(s_{t},a_{t})|H_{t_{e}-1}]+\sum_{e=1}^{E}\sum_{t=t_{e}}^{t_{e+1}-1}2CT_{M}S\rho^{t-t_{e}}$
(101)
$\displaystyle=\sum_{e=1}^{E}\sum_{t=t_{e}}^{t_{e+1}-1}\mathbb{E}_{(s_{t},a_{t})\sim\pi_{e},P}[B^{\pi_{e},\tilde{P}_{e}}(s_{t},a_{t})|H_{t_{e}-1}]+\frac{2ECT_{M}S}{1-\rho}$
(102)

where Equation (102) follows from summation of series $\rho^{t-t_{e}}$ for
$t\to\infty$.

We can now construct a Martingale sequence to bound the summation in Equation
(LABEL:eq:bound_on_restart_deviations). We construct a Martingale sequence as

$\displaystyle
X_{t}^{e}=\mathbb{E}_{(s_{t},a_{t})\sim\pi_{e},P}[\sum_{t=t_{e}}^{t_{e+1}-1}B_{\pi_{e}}^{P_{e}^{k},k}(s_{t},a_{t})|H_{t-1}];t_{e}\leq
t<t_{e+1}$ (103)

such that $|X_{t}^{e}-X_{t-1}^{e}|\leq 4D$ for all $t,e$. We can now use
Azuma-Hoeffding’s inequality to bound $\sum_{e=1}^{E}X_{t_{e}}^{e}$ as:

$\displaystyle\Bigg{|}\sum_{e=1}^{E}\left(X_{t}^{e}-\sum_{t=t_{e}}^{t_{e+1}-1}B_{\pi_{e}}^{P_{e}^{k},k}(s_{t},a_{t})\right)\Bigg{|}\leq
4T_{M}\sqrt{6T\log(2T)}$ (104)

with probability at least $1-1/T^{6}$.

We are now ready to bound $R_{2}(T)$ using Lemma 6, Lemma 7, and Lemma 9. We
have the following set of equations:

$\displaystyle R_{2}(T)$
$\displaystyle=\frac{L}{T}\Big{|}\sum_{e=1}^{E}\sum_{t=t_{e}}^{t_{e+1}-1}\left(\lambda_{\pi_{e}}^{\tilde{P}_{e}}-\lambda_{\pi_{e}}^{P}\right)\Big{|}$
(105)
$\displaystyle=\frac{L}{T}\Big{|}\sum_{e=1}^{E}\sum_{t=t_{e}}^{t_{e+1}-1}\sum_{s,a}\rho_{\pi_{e}}^{P}B^{\pi_{e},\tilde{P}_{e}}(s,a)\Big{|}$
(106)
$\displaystyle\leq\frac{L}{T}\Big{|}\sum_{e=1}^{E}\sum_{t=t_{e}}^{t_{e+1}-1}B^{\pi_{e},\tilde{P}_{e}}(s_{t},a_{t})+4T_{M}\sqrt{6T\log(2T)}+\frac{4CET_{M}S}{1-\rho}\Big{|}$
(107)
$\displaystyle\leq\frac{L}{T}\Big{|}\sum_{e=1}^{E}\sum_{t=t_{e}}^{t_{e+1}-1}T_{M}\sqrt{\frac{14S\log(2AT)}{1\vee
N_{e}(s_{t},a_{t})}}+4T_{M}\sqrt{6T\log(2T)}+\frac{4CET_{M}S}{1-\rho}\Big{|}$
(108)
$\displaystyle\leq\frac{L}{T}\Big{|}\sum_{e=1}^{E}\sum_{t=t_{e}}^{t_{e+1}-1}\sum_{s,a}\bm{1}_{\\{s_{t}=s,a_{t}=a\\}}T_{M}\sqrt{\frac{14S\log(2AT)}{1\vee
N_{e}(s,a)}}+4T_{M}\sqrt{6T\log(2T)}+\frac{4CET_{M}S}{1-\rho}\Big{|}$ (109)
$\displaystyle\leq\frac{L}{T}\Big{|}\sum_{e=1}^{E}\sum_{s,a}\nu_{e}(s,a)T_{M}\sqrt{\frac{14S\log(2AT)}{1\vee
N_{e}(s,a)}}+4T_{M}\sqrt{6T\log(2T)}+\frac{4CET_{M}S}{1-\rho}\Big{|}$ (110)
$\displaystyle\leq\frac{L}{T}\Big{|}\sum_{s,a}T_{M}\sqrt{14S\log(2AT)}\sum_{e=1}^{E}\frac{\nu_{e}(s,a)}{\sqrt{1\vee
N_{e}(s,a)}}+4T_{M}\sqrt{6T\log(2T)}+\frac{4CET_{M}S}{1-\rho}\Big{|}$ (111)
$\displaystyle\leq\frac{L}{T}\Big{|}\sum_{s,a}T_{M}(\sqrt{2}+1)\sqrt{14S\log(2AT)}\sqrt{N(s,a)}+4T_{M}\sqrt{6T\log(2T)}+\frac{4CET_{M}S}{1-\rho}\Big{|}$
(112)
$\displaystyle\leq\frac{L}{T}\Big{|}T_{M}(\sqrt{2}+1)\sqrt{14S\log(2AT)}\sqrt{\left(\sum_{s,a}1\right)\left(\sum_{s,a}N(s,a)\right)}+4T_{M}\sqrt{6T\log(2T)}+\frac{4CET_{M}S}{1-\rho}\Big{|}$
(113)
$\displaystyle\leq\frac{L}{T}\Big{|}T_{M}(\sqrt{2}+1)\sqrt{14S\log(2AT)}\sqrt{SAT}+4T_{M}\sqrt{6T\log(2T)}+\frac{4CT_{M}S\log
T}{1-\rho}\Big{|}$ (114)

where Equation (106) follows from Lemma 6, Equation (107) follows from Lemma
9, and Equation (108) follows from Lemma 9. Equation (112) follows from
(Jaksch et al., 2010, Lemma 19) and Equation (113) follows from Cauchy-Schwarz
inequality. Further, the value of $E$ is bounded by $\log T$ from (Jaksch et
al., 2010, Proposition 18).

### Bounding $R_{3}(T)$

Bounding $R_{3}(T)$ follows mostly similar to Lemma 9. At each epoch, the
agent visits states according to the occupancy measure $\rho_{\pi_{e}}^{P}$
and obtains the rewards. We bound the deviation of the observed visitations to
the expected visitations to each state action pair in each epoch.

###### Lemma 10

With probability at least $1-1/T^{6}$, the difference between the observed
rewards and the expected rewards is bounded as:

$\displaystyle\Big{|}\sum_{e=1}^{E}(t_{e+1}-t_{e})\mathbb{E}_{\pi_{e},P}\left[r(s,a)\right]-\sum_{e=1}^{E}\sum_{t=t_{e}}^{t_{e+1}-1}r(s_{t},a_{t})\Big{|}\leq
4\sqrt{6T\log(T)}+\frac{4CES}{1-\rho}$ (115)

##  C Bounding Constraint Violations

To bound the constraint violations $C(T)$, we break it into multiple
components. We can then bound these components individually.

### Constraint breakdown

We first break down our regret into multiple parts which will help us bound
the regret.

$\displaystyle C(T)$
$\displaystyle=\left(g\left(\frac{1}{T}\sum_{t=1}^{T}c_{1}(s_{t},a_{t}),\cdots,\frac{1}{T}\sum_{t=1}^{T}c_{d}(s_{t},a_{t})\right)\right)_{+}$
(116)
$\displaystyle=\left(g\left(\frac{1}{T}\sum_{t=1}^{T}c_{1}(s_{t},a_{t}),\cdots,\frac{1}{T}\sum_{t=1}^{T}c_{d}(s_{t},a_{t})\right)+\frac{1}{T}\sum_{e=1}^{E}T_{e}g\left(\zeta_{\pi_{e}}^{\tilde{P}_{e}}(1),\cdots,\zeta_{\pi_{e}}^{\tilde{P}_{e}}(d)\right)-\frac{1}{T}\sum_{e=1}^{E}T_{e}g\left(\zeta_{\pi_{e}}^{\tilde{P}_{e}}(1),\cdots,\zeta_{\pi_{e}}^{\tilde{P}_{e}}(d)\right)\right)_{+}$
(117)
$\displaystyle\leq\left(g\left(\frac{1}{T}\sum_{t=1}^{T}c_{1}(s_{t},a_{t}),\cdots,\frac{1}{T}\sum_{t=1}^{T}c_{d}(s_{t},a_{t})\right)-\frac{1}{T}\sum_{e=1}^{E}T_{e}g\left(\zeta_{\pi_{e}}^{\tilde{P}_{e}}(1),\cdots,\zeta_{\pi_{e}}^{\tilde{P}_{e}}(d)\right)-\frac{1}{T}\sum_{e=1}^{E}T_{e}\epsilon_{e}\right)_{+}$
(118)
$\displaystyle\leq\left(g\left(\frac{1}{T}\sum_{t=1}^{T}c_{1}(s_{t},a_{t}),\cdots,\frac{1}{T}\sum_{t=1}^{T}c_{d}(s_{t},a_{t})\right)-g\left(\frac{1}{T}\sum_{e=1}^{E}T_{e}\zeta_{\pi_{e}}^{\tilde{P}_{e}}(1),\cdots,\frac{1}{T}\sum_{e=1}^{E}T_{e}\zeta_{\pi_{e}}^{\tilde{P}_{e}}(d)\right)-\frac{1}{T}\sum_{e=1}^{E}T_{e}\epsilon_{e}\right)_{+}$
(119)
$\displaystyle\leq\left(L\sum_{i=1}^{d}\Big{|}\frac{1}{T}\sum_{e=1}^{E}\sum_{t=t_{e}}^{t_{e+1}-1}\left(c_{i}(s_{t},a_{t})-\zeta_{\pi_{e}}^{\tilde{P}_{e}}(i)\right)\Big{|}-\frac{1}{T}\sum_{e=1}^{E}T_{e}\epsilon_{e}\right)_{+}$
(120)
$\displaystyle\leq\left(L\sum_{i=1}^{d}\Big{|}\frac{1}{T}\sum_{e=1}^{E}\sum_{t=t_{e}}^{t_{e+1}-1}\left(c_{i}(s_{t},a_{t})-\zeta_{\pi_{e}}^{P}(i)+\zeta_{\pi_{e}}^{P}(i)-\zeta_{\pi_{e}}^{\tilde{P}_{e}}(i)\right)\Big{|}-\frac{1}{T}\sum_{e=1}^{E}T_{e}\epsilon_{e}\right)_{+}$
(121)
$\displaystyle\leq\left(\frac{L}{T}\sum_{i=1}^{d}\Big{|}\sum_{e=1}^{E}\sum_{t=t_{e}}^{t_{e+1}-1}\left(c_{i}(s_{t},a_{t})-\zeta_{\pi_{e}}^{P}(i)\right)\Big{|}+\frac{L}{T}\sum_{i=1}^{d}\Big{|}\sum_{e=1}^{E}\sum_{t=t_{e}}^{t_{e+1}-1}\left(\zeta_{\pi_{e}}^{P}(i)-\zeta_{\pi_{e}}^{\tilde{P}_{e}}(i)\right)\Big{|}-\frac{1}{T}\sum_{e=1}^{E}T_{e}\epsilon_{e}\right)_{+}$
(122) $\displaystyle\leq\left(C_{3}(T)+C_{2}(T)-C_{1}(T)\right)_{+}$ (123)

where Equation (54) comes from the fact that the policy $\pi_{e}$ is for the
optimistic CMDP and provides a higher value of the function $f$. Equation 55
comes from the concavity of the function $f$, and Equation 56 comes from the
Lipschitz continuity of the function $f$. The three terms in Equation (59) are
now defined as:

$\displaystyle C_{1}(T)$
$\displaystyle=\frac{1}{T}\sum_{e=1}^{E}T_{e}\epsilon_{e}$ (124)

$C_{1}(T)$ denotes the gap left by playing the policy for $\epsilon_{e}$-tight
optimization problem on the optimistic MDP.

$\displaystyle C_{2}(T)$
$\displaystyle=\frac{L}{T}\sum_{i=1}^{d}\Big{|}\sum_{e=1}^{E}\sum_{t=t_{e}}^{t_{e+1}-1}\left(\zeta_{\pi_{e}}^{P}(i)-\zeta_{\pi_{e}}^{\tilde{P}_{e}}(i)\right)\Big{|}$
(125)

$C_{2}(T)$ denotes the difference between long-term average costs incurred by
playing the policy $\pi_{e}$ on the true MDP with transitions $P$ and the
optimistic MDP with transitions $\tilde{P}$. This term is bounded similar to
the bound of $R_{2}(T)$.

$\displaystyle C_{3}(T)$
$\displaystyle=\frac{L}{T}\sum_{i=1}^{d}\Big{|}\sum_{e=1}^{E}\sum_{t=t_{e}}^{t_{e+1}-1}\left(c_{i}(s_{t},a_{t})-\zeta_{\pi_{e}}^{P}(i)\right)\Big{|}$
(126)

$C_{3}(T)$ denotes the difference between long-term average costs incurred by
playing the policy $\pi_{e}$ on the true MDP with transitions $P$ and the
realized costs. This term is bounded similar to the bound of $R_{3}(T)$.

### Bounding $C_{1}(T)$

Note that $C_{1}(T)$ allows us to violate constraints by not having the
knowledge of the true MDP and allowing deviations of incurred costs from the
expected costs. We now want to lower bound $C_{1}$ to allow us sufficient
slackness. With this idea, we have the following set of equations.

$\displaystyle C_{1}(T)$
$\displaystyle=\frac{1}{T}\sum_{e=1}^{E}\sum_{t=t_{e}}^{t_{e+1}-1}\epsilon_{e}$
(127)
$\displaystyle=\frac{1}{T}\sum_{e=1}^{E}\sum_{t=t_{e}}^{t_{e+1}-1}K\sqrt{\frac{\log
t_{e}}{t_{e}}}$ (128) $\displaystyle\geq
K\frac{1}{T}\sum_{e=E^{\prime}}^{E}\sum_{t=t_{e}}^{t_{e+1}-1}\sqrt{\frac{\log(T/4)}{t_{e}}}$
(129) $\displaystyle\geq
K\frac{1}{T}\sum_{e=E^{\prime}}^{E}\sum_{t=t_{e}}^{t_{e+1}-1}\sqrt{\frac{\log(T/4)}{T}}$
(130)
$\displaystyle=K\frac{1}{T}\left(T-t_{E^{\prime}}\right)\sqrt{\frac{\log(T/4)}{T}}$
(131) $\displaystyle\geq K\frac{1}{2}\sqrt{\frac{\log(T/4)}{T}}$ (132)
$\displaystyle\geq K\frac{1}{4}\sqrt{\frac{\log T}{T}}$ (133)

where $E^{\prime}$ is some epoch for which $T/4\leq t_{E^{\prime}}<{T/2}$.

### Bounding $C_{2}(T)$, and $C_{3}(T)$

We note that costs incurred in $C_{2}(T)$, and $C_{3}(T)$ follows the same
bound as $R_{2}(T)$ and $R_{3}(T)$ respectively.

Summing the three terms gives the required bound and choosing
$K=\Theta(LdT_{M}S\sqrt{A})$.

##  D Concentration bound results

We want to bound the deviation of the estimates of the estimated transition
probabilities of the Markov Decision Processes $\mathcal{M}$. For that we use
$\ell_{1}$ deviation bounds from (Weissman et al., 2003). Consider, the
following event,

$\displaystyle\mathcal{E}_{t}=\left\\{\|\hat{P}(\cdot|s,a)-P(\cdot|s,a)\|_{1}\leq\sqrt{\frac{14S\log(2AT)}{\max\\{1,n(s,a)\\}}}\forall(s,a)\in\mathcal{S}\times\mathcal{A}\right\\}$
(134)

where
$n=\sum_{t^{\prime}=1}^{t}\bm{1}_{\\{s_{t^{\prime}}=s,a_{t^{\prime}}=a\\}}$.
Then we have, the following lemma:

###### Lemma 11

The probability that the event $\mathcal{E}_{t}$ fails to occur us upper
bounded by $\frac{1}{20t^{6}}$.

Proof  From the result of (Weissman et al., 2003), the $\ell_{1}$ distance of
a probability distribution over $S$ events with $n$ samples is bounded as:

$\displaystyle\mathbb{P}\left(\|P(\cdot|s,a)-\hat{P}(\cdot|s,a)\|_{1}\geq\epsilon\right)\leq(2^{S}-2)\exp{\left(-\frac{n\epsilon^{2}}{2}\right)}\leq(2^{S})\exp{\left(-\frac{n\epsilon^{2}}{2}\right)}$
(135)

This, for
$\epsilon=\sqrt{\frac{2}{n(s,a)}\log(2^{S}20SAt^{7})}\leq\sqrt{\frac{14S}{n(s,a)}\log(2At)}\leq\sqrt{\frac{14S}{n(s,a)}\log(2AT)}$
gives,

$\displaystyle\mathbb{P}\left(\|P(\cdot|s,a)-\hat{P}(\cdot|s,a)\|_{1}\geq\sqrt{\frac{14S}{n(s,a)}\log(2At)}\right)$
$\displaystyle\leq(2^{S})\exp{\left(-\frac{n(s,a)}{2}\frac{2}{n(s,a)}\log(2^{S}20SAt^{7})\right)}$
(136) $\displaystyle=2^{S}\frac{1}{2^{S}20SAt^{7}}$ (137)
$\displaystyle=\frac{1}{20ASt^{7}}$ (138)

We sum over the all the possible values of $n(s,a)$ till $t$ time-step to
bound the probability that the event $\mathcal{E}_{t}$ does not occur as:

$\displaystyle\sum_{n(s,a)=1}^{t}\frac{1}{20SAt^{7}}\leq\frac{1}{20SAt^{6}}$
(139)

Finally, summing over all the $s,a$, we get,

$\displaystyle\mathbb{P}\left(\|P(\cdot|s,a)-\hat{P}(\cdot|s,a)\|_{1}\geq\sqrt{\frac{14S}{n(s,a)}\log(2At)}~{}\forall
s,a\right)\leq\frac{1}{20t^{6}}$ (140)

The second lemma is the Azuma-Hoeffding’s inequality, which we use to bound
Martingale difference sequences.

######  Lemma 12 (Azuma-Hoeffding’s Inequality)

Let $X_{1},\cdots,X_{n}$ be a Martingale difference sequence such that
$|X_{i}|\leq c$ for all $i\in\\{1,2,\cdots,n\\}$, then,

$\displaystyle\mathbb{P}\left(|\sum_{i=1}^{n}X_{i}|\geq\epsilon\right)\leq
2\exp{\left(-\frac{\epsilon^{2}}{2nc^{2}}\right)}$ (141)

###### Corollary 2

Let $X_{1},\cdots,X_{n}$ be a Martingale difference sequence such that
$|X_{i}|\leq c$ for all $i\in\\{1,2,\cdots,n\\}$, then,

$\displaystyle\mathbb{E}\left(|\sum_{i=1}^{n}X_{i}|\right)\leq\mathcal{O}(c\sqrt{n\log
n})$ (142)

We can now use the Azuma-Hoeffding’s inequality to upper bound the expected
value of the expected value of the absolute value of the sum of the $n$ terms
of the Martingale difference sequence $\\{X_{i}\\}_{i=1}^{n}$.

Proof

$\displaystyle\mathbb{E}\left(|\sum_{i=1}^{n}X_{i}|\right)$ $\displaystyle\leq
c\sqrt{n\log n}\mathbb{P}\left(|\sum_{i=1}^{n}X_{i}|\leq c\sqrt{n\log
n}\right)+cn\mathbb{P}\left(|\sum_{i=1}^{n}X_{i}|\geq c\sqrt{n\log n}\right)$
(143) $\displaystyle\leq c\sqrt{n\log n}+cn\left(2\exp{\left(-\frac{c^{2}n\log
n}{2nc^{2}}\right)}\right)$ (144) $\displaystyle=c\sqrt{n\log
n}+cn\left(2\exp{\left(-\frac{\log n}{2}\right)}\right)$ (145)
$\displaystyle=c\sqrt{n\log n}+cn\frac{2}{\sqrt{n}}$ (146)
$\displaystyle=3c\sqrt{n\log n}$ (147)

where Equation (144) follows by putting $\epsilon=c\sqrt{n\log n}$ in Equation
(141).

##  E Simulation Details

To validate the performance proposed UC-CURLalgorithm and the understanding of
our analysis, we run the simulation on the flow and service control in a
single-serve queue, which is introduced in (Altman and Schwartz, 1991). A
discrete-time single-server queue with a buffer of finite size $L$ is
considered in this case. The number of the customer waiting in the queue is
considered as the state in this problem and thus $|S|=L+1$. Two kinds of the
actions, service and flow, are considered in the problem and control the
number of customers together. The action space for service is a finite subset
$A$ in $[a_{min},a_{max}]$, where $0<a_{min}\leq a_{max}<1$. Given a specific
service action $a$, the service a customer is successfully finished with the
probability $b$. If the service is successful, the length of the queue will
reduce by 1. Similarly, the space for flow is also a finite subsection $B$ in
$[b_{min},b_{max}]$. In contrast to the service action, flow action will
increase the queue by $1$ with probability $b$ if the specific flow action $b$
is given. Also, we assume that there is no customer arriving when the queue is
full. The overall action space is the Cartesian product of the $A$ and $B$.
According to the service and flow probability, the transition probability can
be computed and is given in the Table 2.

Table 2: Transition probability of the queue system Current State | $P(x_{t+1}=x_{t}-1)$ | $P(x_{t+1}=x_{t})$ | $P(x_{t+1}=x_{t}+1)$
---|---|---|---
$1\leq x_{t}\leq L-1$ | $a(1-b)$ | $ab+(1-a)(1-b)$ | $(1-a)b$
$x_{t}=L$ | $a$ | $1-a$ | $0$
$x_{t}=0$ | $0$ | $1-b(1-a)$ | $b(1-a)$

(a) Reward growth w.r.t. time

(b) Service constraints w.r.t. time

(c) Flow constraints w.r.t. time

Figure 2: Performance of the proposed UC-CURL algorithm on a flow and service
control problem for a single queue with respect to algorithmic parameter $K$
and choice of policy update times.

Define the reward function as $r(s,a,b)$ and the constraints for service and
flow as $c^{1}(s,a,b)$ and $c^{2}(s,a,b)$, respectively. Define the stationary
policy for service and flow as $\pi_{a}$ and $\pi_{b}$, respectively. Then,
the problem can be defined as

$\begin{split}\max_{\pi_{a},\pi_{b}}&\quad\lim\limits_{T\rightarrow\infty}\frac{1}{T}\sum_{t=1}^{T}r(s_{t},\pi_{a}(s_{t}),\pi_{b}(s_{t}))\\\
s.t.&\quad\lim\limits_{T\rightarrow\infty}\frac{1}{T}\sum_{t=1}^{T}c^{1}(s_{t},\pi_{a}(s_{t}),\pi_{b}(s_{t}))\geq
0\\\
&\quad\lim\limits_{T\rightarrow\infty}\frac{1}{T}\sum_{t=1}^{T}c^{2}(s_{t},\pi_{a}(s_{t}),\pi_{b}(s_{t}))\geq
0\end{split}$ (149)

According to the discussion in (Altman and Schwartz, 1991), we define the
reward function as $r(s,a,b)=5-s$, which is an decreasing function only
dependent on the state. It is reasonable to give higher reward when the number
of customer waiting in the queue is small. For the constraint function, we
define $c^{1}(s,a,b)=-10a+6$ and $c^{2}=-8(1-b)^{2}+2$, which are dependent
only on service and flow action, respectively. Higher constraint value is
given if the probability for the service and flow are low and high,
respectively.

In the simulation, the length of the buffer is set as $L=5$. The service
action space is set as $[0.2,0.4,0.6,0.8]$ and the flow action space is set as
$[0.5,0.6,0.7,0.8]$. We use the length of horizon $T=10^{5}$ and run 100
independent simulations of the proposed UC-CURL algorithm. The result is shown
in the Figure 1. The average values of the cumulative reward and the
constraint functions are shown in the solid lines. Also, we plot the standard
deviation around the mean value in the shadow to show the random error. It is
found that the cumulative reward convergences to about 4. The service and flow
constraints converge to 0 as expected. In order to compare this result to the
optimal, we assume that the full information of the transition dynamics is
known and then use Linear Programming to solve the problem. The optimal
cumulative reward from LP is shown to be 4.08. We note that the reward of the
proposed UC-CURL algorithm becomes closer the optimal reward as the algorithm
proceeds.