# Safe Posterior Sampling for Constrained MDPs with Bounded Constraint
Violation

###### Abstract

Constrained Markov decision processes (CMDPs) model scenarios of sequential
decision making with multiple objectives that are increasingly important in
many applications. However, the model is often unknown and must be learned
online while still ensuring the constraint is met, or at least the violation
is bounded with time. Some recent papers have made progress on this very
challenging problem but either need unsatisfactory assumptions such as
knowledge of a safe policy, or have high cumulative regret. We propose the
Safe PSRL (posterior sampling-based RL) algorithm that does not need such
assumptions and yet performs very well, both in terms of theoretical regret
bounds as well as empirically. The algorithm achieves an efficient tradeoff
between exploration and exploitation by use of the posterior sampling
principle, and provably suffers only bounded constraint violation by
leveraging the idea of pessimism. Our approach is based on a primal-dual
approach. We establish a sub-linear
$\tilde{\mathcal{O}}\left(H^{2.5}\sqrt{|\mathcal{S}|^{2}|\mathcal{A}|K}\right)$
upper bound on the Bayesian reward objective regret along with a _bounded_ ,
i.e., $\tilde{\mathcal{O}}\left(1\right)$ constraint violation regret over $K$
episodes for an $|\mathcal{S}|$-state, $|\mathcal{A}|$-action, and horizon $H$
CMDP.

Machine Learning, ICML

Krishna C Kalagarla, Rahul Jain, Pierluigi Nuzzo

Ming Hsieh Department of Electrical and Computer Engineering, University of
Southern California, Los Angeles

Email<EMAIL_ADDRESS>

##  1 Introduction

Markov decision processes (MDPs) (Puterman, 1994) are used to model many
scenarios involving sequential decision-making. They are used in a wide
variety of settings like robotics, cyber-physical systems, and safety-critical
autonomous vehicles. However, a traditional reinforcement learning (RL)
formulation which seeks to maximize a single cumulative reward cannot capture
many problems that have multiple objectives. For example, this is the case for
a robot that needs to perform a certain reward-yielding task while ensuring
that the average energy expended is bounded below a threshold. Such scenarios
are well-modeled by constrained MDPs (CMDPs) (Altman, 1999), which extend the
MDP formalism by considering additional constraints on the expected cumulative
performance of a policy. In the CMDP setting, one seeks to find an optimal
policy which maximizes the cumulative objective reward while satisfying
constraints on cost objectives.

In this paper, we consider the problem of online learning for finite-horizon
CMDPs, where an agent interacts with the environment repeatedly in episodes of
fixed length. The transition probability is not known to the agent, thereby
requiring the agent to learn about the system dynamics by observing the past
states and actions. The performance of this agent is measured by the notion of
_cumulative regret_ , i.e., the difference between the cumulative reward of
the learning agent and that of the optimal policy.

This online learning problem thus leads to the well-known trade-off between
_exploration_ and _exploitation_ : should the agent _explore_ the environment
to improve future performance, or _exploit_ the current knowledge for better
short-term performance?

A common approach to balance this exploration-exploitation trade-off is the
‘Optimism in the Face of Uncertainty’ (OFU) principle (Lai & Robbins, 1985).
The idea is that each state and action are assigned optimism bonuses based on
the current knowledge. The agent then chooses a policy which maximizes the
expected return under this optimistic model. The bonuses are designed to
promote exploration of poorly-understood state-action pairs. This approach has
been widely used for online learning in MDPs (Jaksch et al., 2010; Azar et
al., 2017; Jin et al., 2018; Wei et al., 2020; Kalagarla et al., 2021).

Another alternative for efficient exploration is posterior sampling (also
called Thompson sampling) (Thompson, 1933). In this approach, a posterior
distribution is maintained over the unknown transition probability model based
on the prior distribution and dataset about visited trajectories. At the
beginning of each episode, a model is sampled from this posterior
distribution. The agent then chooses a policy which is optimal with respect to
the sampled model and follows it for the duration of the episode. The
advantages of posterior sampling over OFU stem from the fact that (i) known
information about the model can be incorporated into the algorithm through the
prior distribution, and (ii) posterior sampling algorithms have demonstrated
superior empirical performance for online learning over OFU-type algorithms
including in the RL setting (Osband et al., 2013; Ouyang et al., 2017).

In this paper, we use the posterior sampling approach and introduce the Safe
PSRL algorithm for efficient exploration in the finite-horizon CMDP setting.
Our algorithm uses the primal-dual approach for CMDPs wherein the primal part
performs unconstrained MDP planning with a sampled transition probability, and
the dual part updates the Lagrangian variable to track the constraint
violation.

We achieve bounded constraint violation regret by leveraging the idea of
_pessimism_ , introduced earlier in the context of constrained bandits (Liu et
al., 2021b). “Pessimism” is achieved by tightening the constraint of the CMDP
problem in every episode at decreasing levels. The key is, however, how this
tightening is achieved. By appropriately balancing exploration via posterior
sampling and _safe_ learning via pessimism, we show that the Safe PSRL
algorithm achieves sub-linear
$\tilde{\mathcal{O}}\left(\frac{H^{2.5}}{\tau-c^{0}}\sqrt{|\mathcal{S}|^{2}|\mathcal{A}|K}\right)$
reward regret while achieving bounded, i.e.,
$\tilde{\mathcal{O}}(1)$-constraint violation regret for an
$|\mathcal{S}|$-state, $|\mathcal{A}|$-action, and an $H$ episode length CMDP
over $K$ number of episodes. $\tau$ denotes the desired threshold for
constraint violation, and $c^{0}$ is a known feasible expected cumulative
constraint cost of the CMDP.

The contributions of this paper are the following: (i) We present the first
PSRL algorithm for CMDPs that not only achieves
$\tilde{\mathcal{O}}\left(\sqrt{K}\right)$ objective reward regret but also
$\tilde{\mathcal{O}}(1)$ constraint violation regret. Unlike other proposed
algorithms, our algorithm does not need knowledge of a constraint-satisfying
safe policy. (ii) Our Safe PSRL algorithm has better empirical performance
than state-of-the-art OFU-type algorithms for the same setting introduced in
(Liu et al., 2021a; Bura et al., 2022) which need knowledge of a safe policy.
(iii) The algorithm design is simpler than other state-of-the-art algorithms
(Liu et al., 2021a; Bura et al., 2022) for the problem: The key design choice
are two pessimism parameters. The regret analysis involves a novel
decomposition which allows us to leverage posterior sampling regret analysis
and Lyapunov-drift analysis for the dual variables.

##  2 Related Work

Posterior (or Thompson) sampling goes back to the work of (Thompson, 1933),
but attracted less attention for several decades until empirical evidence
(Chapelle & Li, 2011) showed its superior performance for online learning.
Recently, it has been widely applied to various settings like multi-armed
bandits (Kaufmann et al., 2012; Agrawal & Goyal, 2012, 2013), MDPs (Osband et
al., 2013; Gopalan & Mannor, 2015; Osband & Van Roy, 2017; Ouyang et al.,
2017) and POMDPs (Jafarnia-Jahromi et al., 2021c).

Multi-armed bandits (MAB) are a special case of MDPs with a single state and
unknown reward function. Safe online learning has been studied for MABs in
multiple settings (Amani et al., 2019; Khezeli & Bitar, 2020; Pacchiano et
al., 2021; Liu et al., 2021b). However, in comparison, the multi-step and
multi-state MDP settings are more challenging due to the unknown transition
probability.

In the CMDP setting, several existing works (Efroni et al., 2020; Qiu et al.,
2020; Agarwal et al., 2022) leverage OFU or posterior sampling to provide
$\tilde{\mathcal{O}}(\sqrt{K})$ regret for the reward as well as the
constraint objective, where $K$ is the number of episodes. Such an approach,
however, can lead to a large number of constraint violations during learning,
which is unacceptable during various safety-critical tasks such as driving or
power distribution. Thus, the problem of an online RL algorithm that has
sublinear (and hopefully, $\tilde{\mathcal{O}}(\sqrt{K})$) reward regret while
achieving bounded constraint violation regret, particularly one that also has
very good empirical performance, remains open.

OFU-based algorithms have been widely used for efficient learning in CMDPs,
e.g., in the setting of PAC performance guarantees for finite-horizon CMDPs
(HasanzadeZonuzy et al., 2021; Kalagarla et al., 2021), or to provide regret
bounds for CMDPs in the finite-horizon setting (Efroni et al., 2020; Brantley
et al., 2020) and infinite-horizon average cost setting (Singh et al., 2020).
Policy gradient algorithms for CMDPs (Ding et al., 2020, 2021) have also been
studied. However, these algorithms do not provide bounded or zero constraint
violation guarantees.

Recently, some OFU-based approaches for _safe_ learning with bounded or zero
constraint violation guarantees have been proposed (Zheng & Ratliff, 2020;
Chen et al., 2022; Bai et al., 2022; Wei et al., 2022; Liu et al., 2021a). But
these either assume the transition model is known (but reward function is
not), or only satisfy the constraint with high probability, or assume that a
safe policy is known to the algorithm (and can be used by it), e.g., in (Liu
et al., 2021a; Bura et al., 2022). The OptPess-PrimalDual algorithm in (Liu et
al., 2021a) is the closest comparable algorithm but our Safe PSRL algorithm is
better in terms of its dependence on various problem parameters, e.g., it has
$\tilde{\mathcal{O}}(H^{3}|\mathcal{S}|^{1.5})$ dependence as opposed to
$\tilde{\mathcal{O}}(H^{2.5}|\mathcal{S}|)$ for ours.

While the use of the posterior sampling principle for constrained RL problems
is under-explored (despite the promise of better empirical performance),
(Agarwal et al., 2022) indeed introduces a PSRL algorithm for CMDPs but for
the average setting. Moreover, it only achieves a
$\tilde{\mathcal{O}}(\sqrt{K})$ constraint violation regret which is worse
than our $\tilde{\mathcal{O}}(1)$ bound.

##  3 Preliminaries

###  3.1 Notation

We denote the probability simplex over set $S$ by $\Delta_{S}$. We use the
notation $\tilde{\mathcal{O}}$ which has similar meaning as the usual
$\mathcal{O}$ notation but ignores logarithmic factors.

###  3.2 Finite-Horizon MDPs

An episodic finite-horizon MDP (Puterman, 1994) can be formally defined by a
tuple $\mathcal{M}=(\mathcal{S},\mathcal{A},H,s_{1},p,r)$, where $\mathcal{S}$
and $\mathcal{A}$ denote the state and action spaces, respectively. In this
setting, the agent interacts with the environment in episodes of fixed length
$H$, with each episode starting with a random initial state denoted $s_{1}$.
The non-stationary transition probability $p_{h}(s^{\prime}|s,a)$ is the the
probability of transitioning to state $s^{\prime}$ on taking action $a$ at
state $s$ at time step $h\in\left[1:H\right]$ of the episode. The non-
stationary reward obtained on taking action $a$ in state $s$ at time step $h$
of an episode is denoted by a random variable $R_{h}(s,a)\in\left[0,1\right]$,
with mean $r_{h}(s,a)$. We use $r$ as a shorthand to denote the mean reward
vector $r_{1},\ldots,r_{H}$.

A non-stationary randomized policy $\pi=(\pi_{1},\ldots,\pi_{H})\in\Pi$ where
$\pi_{i}:\mathcal{S}\to\Delta_{\mathcal{A}}$, maps each state to a probability
simplex over the action space $\mathcal{A}$. The action $a_{h}$ at time step
$h$ at state $s_{h}$ is taken according to the policy $\pi$,
$a_{h}\sim\pi_{h}(s_{h})$. The value function of a non-stationary randomized
policy $\pi$, $V_{h}^{\pi}(s;r,p)$ (when clear, $s,r,$ and $p$ are omitted) at
a state $s\in\mathcal{S}$ and time step $h\in\left[1:H\right]$ is defined as:

$V_{h}^{\pi}(s;r,p):={\mathbb{E}}_{\pi}\left[\sum_{i=h}^{H}r_{i}(s_{i},a_{i})|s_{h}=s,p\right],$

where the expectation is over the distribution induced by the environment and
policy randomness. Similarly, the Q-value function of a policy $\pi$,
$Q_{h}^{\pi}(s,a;r,p)$, for a state $s\in\mathcal{S}$, an action
$a\in\mathcal{A}$ and time step $h\in\left[1:H\right]$, is defined as

$\displaystyle Q_{h}^{\pi}(s,a;r,p):=r_{h}(s,a)+$ (1)
$\displaystyle{\mathbb{E}}_{\pi}\left[\sum_{i=h+1}^{H}r_{i}(s_{i},a_{i})|s_{h}=s,a_{h}=a,p\right].$

We can always find an optimal non-stationary deterministic policy
$\tilde{\pi}$ (Puterman, 1994) such that
$V_{h}^{\tilde{\pi}}(s)=\tilde{V}_{h}(s)=\text{sup}_{\pi}V_{h}^{\pi}(s)$ and
$Q^{\tilde{\pi}}_{h}(s,a)=\tilde{Q}_{h}(s,a)=\text{sup}_{\pi}Q_{h}^{\pi}(s,a)$.
The optimal policy can be computed by using backward induction on the Bellman
optimality equations (Puterman, 1994):

$\displaystyle\tilde{V_{h}}(s)=\text{max}_{a\in\mathcal{A}}\left[r_{h}(s,a)+p_{h}(\cdot|s,a)\tilde{V}_{h+1}\right],$
(2)
$\displaystyle\tilde{Q}_{h}(s,a)=r_{h}(s,a)+p_{h}(\cdot|s,a)\tilde{V}_{h+1},$

where $\tilde{V}_{H+1}(s)=0$ and
$\tilde{V}_{h}(s)=\text{max}_{a\in\mathcal{A}}\tilde{Q}_{h}(s,a)$. The optimal
policy $\tilde{\pi}$ is then greedy with respect to $\tilde{Q}_{h}$.

###  3.3 Finite-Horizon Constrained MDPs

A finite-horizon constrained MDP (CMDP) (Altman, 1999) is a finite-horizon MDP
with a required upper bound on expectation of on a cost function,
$\\{c,\tau\in(0,H]\\}$. The non-stationary cost obtained on taking action $a$
in state $s$ at time step $h\in\left[1:H\right]$ with respect to the
constraint cost function is denoted by a random variable
$C_{h}(s,a)\in\left[0,1\right]$, with mean $c_{h}(s,a)$. Similar to $r$, we
use $c$ to denote the mean cost vector $c_{1},\ldots,c_{H}$.

The total expected reward (cost) of an episode under policy $\pi$ with respect
to the reward (cost) function $r$ ($c$) is the respective value function from
the initial state $s_{1}$, i.e.,
$V_{1}^{\pi}(s_{1};r,p)(V_{1}^{\pi}(s_{1};c,p))$ (by definition). Our
objective in this CMDP setting is to find a policy which maximizes the total
expected objective reward under the constraint that the total expected
constraint cost is below a desired threshold. Formally,

$\displaystyle\pi^{*}\in\underset{\pi\in\Pi}{\text{ argmax }}$ $\displaystyle
V_{1}^{\pi}(s_{1};r,p)$ (3) s.t. $\displaystyle V_{1}^{\pi}(c,p)\leq\tau.$

The optimal value is denoted by $V^{*}(s_{1};r,p)=V_{1}^{\pi^{*}}(s_{1};r,p)$.
A deterministic optimal policy may not exist, hence we need to consider $\Pi$
to be the class of all randomized policies (Altman, 1999). Since the Bellman
optimality equations may not hold due to the constrained nature of the
problem, we cannot leverage dynamic programming-based backward induction
algorithms to find an optimal policy. However, a linear programming approach
can be given that will find an optimal policy (Altman, 1999).

##  4 The Learning Problem

We consider the setting where an agent repeatedly interacts with a finite-
horizon CMDP $\mathcal{M}=(\mathcal{S},\mathcal{A},H,s_{1},p,r,\\{c,\tau\\})$
over multiple episodes of fixed length $H$, starting each episode from the
same initial state $s_{1}$ and with stationary transition probability (i.e.,
$p_{h}=p,\forall h$). We employ the Bayesian framework and regard the
transition probability $p$ as random with a prior distribution $\mu_{1}$. The
realized transition probability is unknown to the learning agent. We consider
finite-horizon CMDP whose transition probability lies in the set
$\Theta_{c_{0}}$ with the following property:

######  Assumption 1.

For all $\hat{p}\in\Theta_{c_{0}}$, there exists a policy $\pi_{0}^{\hat{p}}$
such that $V_{1}^{\pi_{0}^{\hat{p}}}(c,\hat{p})\leq c_{0}<\tau$.

Moreover, we assume that the support of the prior distribution $\mu_{1}$ is a
subset of $\Theta_{c_{0}}$ and $c_{0}$ is known. Without loss of
generality,111The complexity of learning the cost and reward functions is
dominated by the complexity of learning the transition probability (Auer &
Ortner, 2005). The algorithm can be readily extended to the setting of unknown
cost and reward functions by using their empirical estimate in place of the
known cost and reward functions. we assume that the reward and cost functions
$r$ and $c$ are respectively are known to the learning agent. Note that the
above assumption is not only reasonable but also necessary to ensure the
problem is feasible.

The agent interacts with the environment for $K$ episodes, each of length $H$.
In each episode, the agent starts from a state $s_{1}$ and chooses a Markov
policy $\pi_{k}$ determined by the information gathered until that episode.
This policy is then executed until the end of the episode, while collecting
the rewards and costs. The main objectives of the learning agent are to:

(1) Maximize the expected cumulative reward after K episodes or equivalently,
minimize the Bayesian regret with respect to the reward function defined as:

$\displaystyle\mathfrak{BR}(K;r):={\mathbb{E}}\left[\sum_{k=1}^{K}\left(V_{1}^{\pi^{*}}(s_{1};r,p)-V^{\pi^{k}}_{1}(s_{1};r,p)\right)\right].$
(4)

(2) Minimize the constraint violation or equivalently, minimize the Bayesian
regret with respect to the constraint defined as:

$\displaystyle\mathfrak{BR}(K;c):={\mathbb{E}}\left[\sum_{k=1}^{K}\left(V^{\pi^{k}}_{1}(s_{1};c,p)-\tau\right)\right].$
(5)

With respect to these objectives, we propose an algorithm which is able to
achieve sub-linear regret with respect to the reward objective while ensuring
that regret with respect to the cost constraint is bounded above by a
constant, i.e., independent of the number of episodes $K$.

##  5 The Safe PSRL Algorithm

We propose the Safe Posterior Sampling-based Reinforcement Learning (Safe
PSRL) algorithm for the finite-horizon CMDP model. This algorithm leverages
the idea of posterior sampling to balance exploration and exploitation. It
also takes a primal-dual approach to handle the constraint cost objective
along with reward maximization objective.

We further introduce the idea of pessimism (Liu et al., 2021b) to ensure that
the cost regret is bounded. This “pessimism” is achieved by considering a
“more constrained” CMDP problem as compared to the original problem. This is
done by decreasing the threshold by $\epsilon_{k}$ in each episode $k$.
Formally, we consider the objective:

max $\displaystyle V_{1}^{\pi}(r,p)$ (6) s.t. $\displaystyle
V_{1}^{\pi}(c,p)\leq\tau-\epsilon_{k}.$

This pessimistic term $\epsilon_{k}$ ensures bounded cost regret and it
decreases as the episode count increases.

The algorithm starts with the prior distribution $\mu_{1}$ on the transition
probability. Then, at every time step $t$, the learning agent maintains a
posterior distribution $\mu_{t}$ on the unknown transition probability $p$
given by $\mu_{t}(\Theta)=\mathbb{P}(p\in\Theta|\mathcal{F}_{t})$ for any set
$\Theta\subseteq\Theta_{c_{0}}$. Here $\mathcal{F}_{t}$ is the information
available at time $t$, i.e., the sigma algebra generated by encountered states
and actions upto time $t$, $(s_{1},a_{1},\cdots,s_{t-1},a_{t-1},s_{t})$. On
observing the next state $s_{t+1}$ by taking action $a_{t}$ at state $s_{t}$,
the posterior is updated according to Bayes’s rule:

$\displaystyle\mu_{t+1}(dp)=\frac{p_{t}(s_{t+1}|s_{t},a_{t})\mu_{t}(dp)}{\int
p^{{}^{\prime}}_{t}(s_{t+1}|s_{t},a_{t})\mu_{t}(dp^{\prime})}.$ (7)

In parallel, the algorithm proceeds as follows: At the beginning of each
episode $k$, transition probability $\hat{p}_{k}$ is sampled from the
posterior distribution $\mu_{t_{k}}$ (where $t_{k}$ is the time step
corresponding to beginning of episode $k$). We then consider the Lagrangian
defined as:

$\displaystyle
L_{k}(\pi,\lambda):=V^{\pi}_{1}(r,\hat{p}_{k})+\frac{\lambda_{k}}{\eta_{k}}\left(\tau-\epsilon_{k}-V_{1}^{\pi}(c,\hat{p}_{k})\right),$

The learning agent then chooses a Markov policy $\pi_{k}$ (primal update)
which maximizes the above Lagrangian. We can find such a policy by applying
standard dynamic programming with respect to the reward function
$r-\frac{\lambda_{k}}{\eta_{k}}c$. The (dual) parameter $\lambda_{k}$ is
updated according to the sub-gradient algorithm as follows:

$\displaystyle\lambda_{k+1}=\left(\lambda_{k}+V_{1}^{\pi_{k}}(c,\hat{p}_{k})+\epsilon_{k}-\tau\right)_{+}$

The agent then applies the policy $\pi_{k}$ for the $H$ steps of episode $k$.

We note that while some of the details of the algorithm are natural (as they
are common to PSRL algorithms for various settings) (Ouyang et al., 2017;
Jafarnia-Jahromi et al., 2021c, a, b), the key novelty in the design are the
$\epsilon_{k}$ and $\eta_{k}$ parameters to be used in conjunction with a
primal-dual approach. Their choice is guided by the regret analysis presented
in Section 6.

The Safe PSRL algorithm is summarized next.

Algorithm 1 Safe-PSRL

Input: $K,\mu_{1},c_{0},\tau$

Initialization: $\lambda^{1}\leftarrow 0$

for episodes $k=1,\ldots,K$ do

$\epsilon_{k}\leftarrow\frac{5|H|^{1.5}\sqrt{|\mathcal{S}|^{2}|\mathcal{A}|}(\log
k|\mathcal{S}||\mathcal{A}|H+1)}{\sqrt{k\log k|\mathcal{S}||\mathcal{A}|H}}$

$\eta_{k}\leftarrow(\tau-c_{0})H\sqrt{k}$

$t_{k}=(k-1)H+1$

Generate $\hat{p}_{k}\sim\mu_{t_{k}}(.)$

Compute
$\pi_{k}\in\arg\max_{\pi}V^{\pi}_{1}(r-\frac{\lambda_{k}}{\eta_{k}}c,\hat{p}_{k})$
according to (2) (Policy Update)

$\lambda_{k+1}\leftarrow\max(0,\lambda_{k}+V^{\pi_{k}}_{1}(c,\hat{p}_{k})+\epsilon_{k}-\tau)$
(Dual Update)

for $t=(k-1)H+1,\ldots,kH$ do

Choose action $a_{t}\sim\pi_{k}(s_{t})$

Observe $s_{t+1}\sim p(.|s_{t},a_{t})$

Update the posterior distribution $\mu_{t+1}$ according to (7)

end for

end for

The following theorem then establishes that the Safe PSRL algorithm can
achieve sub-linear $\tilde{\mathcal{O}}(\sqrt{K})$ reward regret while
achieving bounded constraint violation regret.

######  Theorem 1.

Suppose Assumption 1 holds, then the reward and cost regret of the Safe PSRL
algorithm is upper bounded as:

$\displaystyle\mathfrak{BR}(K;r)$
$\displaystyle=\tilde{\mathcal{O}}\left(\frac{H^{2.5}}{\tau-c^{0}}\sqrt{|\mathcal{S}|^{2}|\mathcal{A}|K}\right),~{}\text{and}$
$\displaystyle\mathfrak{BR}(K;c)$
$\displaystyle=\tilde{\mathcal{O}}\left(C^{\prime\prime}(H-\tau)+H^{1.5}\sqrt{|\mathcal{S}|^{2}|\mathcal{A}|C^{\prime\prime}}\right)$
$\displaystyle=\mathcal{O}(1),$

where
$C^{\prime\prime}=\mathcal{O}(\frac{H^{3}|\mathcal{S}|^{2}|\mathcal{A}|}{(\tau-c^{0})^{2}})$
is independent of $K$.

######  Remark 1.

(i) We note that the upper bound on $\mathfrak{BR}(K;r)$ of the OptPess-
PrimalDual algorithm (Liu et al., 2021a) is
$\tilde{\mathcal{O}}\left(H^{3}\sqrt{|\mathcal{S}|^{3}|\mathcal{A}|K}\right)$.
Thus, our upper bound is the same in terms of $|\mathcal{A}|$,$K$ and better
in terms of $|\mathcal{S}|$ and $H$. Both, OptPess-PrimalDual and Safe PSRL
algorithms achieve $\tilde{\mathcal{O}}\left(1\right)$ upper bounds on
$\mathfrak{BR}(K;c)$.

(ii) We note that the upper bound on $\mathfrak{BR}(K;r)$ of the DOPE
algorithm (Bura et al., 2022) is
$\tilde{\mathcal{O}}\left(H^{3}\sqrt{|\mathcal{S}|^{2}|\mathcal{A}|K}\right)$.
Thus, our upper bound is the same in terms of $|\mathcal{A}|,K,|\mathcal{S}|$
and better in terms of $H$. While our bounds are comparable to those of DOPE,
we shall see that the numerical performance is much better. Further, the DOPE
algorithm guarantees zero constraint violations with high probability. But,
this requires a strong assumption, i.e, knowledge of a safe policy that can
satisfy the constraint.

(iii) The CMDP-PSRL algorithm (Agarwal et al., 2022) uses posterior sampling
in the average CMDP setting and achieves
$\tilde{\mathcal{O}}\left(T_{M}|\mathcal{S}|\sqrt{|A|K}\right)$ reward
objective and the same constraint violation regret, where $T_{M}$ is the
mixing time. In comparison, we are able to achieve bounded constraint
violation regret.

##  6 Regret Analysis

We now provide theoretical analysis of the Safe PSRL algorithm by providing
details of the proof of Theorem 1. We first state some relevant results from
the literature on posterior sampling in the context of reinforcement learning.

A key property of posterior sampling (Osband et al., 2013)
is the posterior sampling lemma, i.e., the transition probability
$\hat{p}_{t}$ sampled from the posterior distribution at time $t$ and
transition probability $p$ have the same distribution.

######  Lemma 1.

For any function $f$, we have
${\mathbb{E}}\left[f(\hat{p}_{t})\right]={\mathbb{E}}\left[f(p)\right]$ where
$p$ is the transition probability (with the prior distribution $\mu_{1}$) and
$\hat{p}_{t}$ is the sampled transition probability from the posterior
distribution $\mu_{t}$ at time $t$.

The following is a restatement (Osband et al., 2013) of the sub-linear regret
bound achieved when using posterior sampling for unconstrained finite horizon
MDPs.

######  Lemma 2.

(Osband et al., 2013) The Bayesian regret of the PSRL algorithm for
unconstrained MDPs is given by

$\begin{split}&\sum_{k=1}^{K}{\mathbb{E}}\left[V^{\pi^{k}}_{1}(c,p)-V^{\pi^{k}}_{1}(c,\hat{p}_{k})\right]\\\
&\leq
H^{1.5}\sqrt{30|\mathcal{S}|^{2}|\mathcal{A}|K\log(|\mathcal{S}||\mathcal{A}|KH)}+2H.\end{split}$
(8)

###  6.1 Cost Constraint Violation Analysis

We first present analysis of the cost constraint violation. We can decompose
the constraint violation regret as follows:

$\displaystyle\mathfrak{BR}(K;c):={\mathbb{E}}\left[\sum_{k=1}^{K}\left(V^{\pi^{k}}_{1}(c,p)-\tau\right)\right]$
$\displaystyle=\sum_{k=1}^{K}{\mathbb{E}}\left[V^{\pi^{k}}_{1}(c,p)-V^{\pi^{k}}_{1}(c,\hat{p}_{k})+V^{\pi^{k}}_{1}(c,\hat{p}_{k})-\tau\right]$
$\displaystyle=\sum_{k=1}^{K}{\mathbb{E}}\left[V^{\pi^{k}}_{1}(c,p)-V^{\pi^{k}}_{1}(c,\hat{p}_{k})\right]+\sum_{k=1}^{K}{\mathbb{E}}\left[V^{\pi^{k}}_{1}(c,\hat{p}_{k})-\tau\right]$
$\displaystyle\leq\sum_{k=1}^{K}{\mathbb{E}}\left[V^{\pi^{k}}_{1}(c,p)-V^{\pi^{k}}_{1}(c,\hat{p}_{k})\right]+\sum_{k=1}^{K}{\mathbb{E}}\left[\lambda_{k+1}-\lambda_{k}-\epsilon_{k}\right]$
(by dual update rule of algorithm)
$\displaystyle=\sum_{k=1}^{K}{\mathbb{E}}\left[V^{\pi^{k}}_{1}(c,p)-V^{\pi^{k}}_{1}(c,\hat{p}_{k})\right]+{\mathbb{E}}\left[\lambda_{K+1}\right]-\sum_{k=1}^{K}\epsilon_{k}$
(9) $\displaystyle\leq
H^{1.5}\sqrt{30|\mathcal{S}|^{2}|\mathcal{A}|K\log(|\mathcal{S}||\mathcal{A}|KH)}+2H$
$\displaystyle+{\mathbb{E}}\left[\lambda_{K+1}\right]-\sum_{k=1}^{K}\epsilon_{k}$
(10)

where the last upper bound follows by use of Lemma 2 to upper bound the first
term in (6.1).

We next show that the dual parameter ${\mathbb{E}}\left[\lambda_{K+1}\right]$
can be upper bounded by use of Lyapunov-drift analysis. To that end, we
restate the following lemma (Liu et al., 2021b) which states the Lyapunov-
drift conditions for the boundedness of a random process.

######  Lemma 3.

(Liu et al., 2021b) Consider a random process $S(t)$ with a Lyapunov function
$\Phi(k)$ such that $\Phi(0)=0$ and $\Delta(k)=\Phi(k+1)-\Phi(k)$ is the
Lyapunov drift. Given an increasing sequence $\\{\varphi_{k}\\}$ and constants
$\rho$ and $\nu_{max}$ with $0<\rho\leq\nu_{max}$, if the expected drift
${\mathbb{E}}\left[\Delta(k)|S(k)=s\right]$ satisfies the following
conditions:
(i) There exists constants $\rho>0$ and $\varphi_{k}>0$ s.t.
${\mathbb{E}}\left[\Delta(k)|S(k)=s\right]\leq-\rho$ when
$\Phi(k)\geq\varphi_{k}$, and
(ii) $|\Phi(k+1)-\Phi(k)|\leq\nu_{\max}$ holds with probability $1$, then

$\displaystyle{\mathbb{E}}\left[e^{\zeta\Phi(t)}\right]\leq{\mathbb{E}}\left[e^{\zeta\Phi_{0}}\right]+\frac{2e^{\zeta\left(\nu_{\max}+\varphi_{t}\right)}}{\zeta\rho},$

where $\zeta=\rho/(\nu_{\max}^{2}+\nu_{\max}\rho/3)$.

We divide the episodes into two parts, i.e. $k<C^{\prime\prime}$ and $k\geq
C^{\prime\prime}$ where
$C^{\prime\prime}=\frac{80H^{3}|\mathcal{S}|^{2}|\mathcal{A}|}{(\tau-
c_{0})^{2}}$. We can clearly see that for $k\geq C^{\prime\prime}$, we have
$\epsilon_{k}\leq\frac{\tau-c_{0}}{2}$. Thus, for $k\geq C^{\prime\prime}$,
Problem (6) is feasible for all $\hat{p_{k}}\in\Theta_{c_{0}}$ by Assumption
1.

For $k\geq C^{\prime\prime}$, we show that the Lyapunov function
$\Phi(\lambda)=\lambda$ satisfies the conditions of Lemma 3 and thus provide a
bound on the exponential moment of the dual variable $\lambda$.

######  Lemma 4.

For $k\geq C^{\prime\prime}$, when $\lambda\geq\varphi_{k}$, we have,

$\displaystyle{\mathbb{E}}\left[\lambda_{k+1}-\lambda_{k}|\lambda_{k}=\lambda\right]\leq\rho~{}\text{and}$
$\displaystyle|\lambda_{k+1}-\lambda_{k}|\leq H\quad\text{with probability
1},$

where $\varphi_{k}:=4(H^{2}+\epsilon_{k}^{2}+\eta_{k}H)/(\tau-c^{0})$ and
$\rho:=-(\tau-c_{0})/4$. Thus, we have,

$\displaystyle{\mathbb{E}}\left[e^{\zeta\lambda_{K+1}}\right]\leq{\mathbb{E}}\left[e^{\zeta\lambda_{C^{\prime\prime}}}\right]+\frac{2e^{\zeta\left(H+\varphi_{K+1}\right)}}{\zeta\rho},$
(11)

where $\zeta=\rho/(H^{2}+H\rho/3)$. The above inequality (11) can be
simplified to

$\displaystyle{\mathbb{E}}\left[\lambda_{K+1}\right]$
$\displaystyle\leq\frac{1}{\zeta}\log\frac{11H^{2}}{3\rho^{2}}+H+\sum_{1}^{C^{\prime\prime}}\epsilon_{k}+C^{\prime\prime}(H-\tau)$
$\displaystyle+$
$\displaystyle\frac{4(H^{2}+\epsilon_{K+1}^{2}+\eta_{K+1}H)}{(\tau-c^{0})}.$
(12)

Next, we bound the $sum_{k}\epsilon_{k}$ term:

$\displaystyle\sum_{k=1}^{K}\epsilon_{k}\geq\int_{1}^{K+1}\epsilon_{u}\mathrm{d}u$
$\displaystyle\geq
10H^{1.5}\sqrt{|\mathcal{S}|^{2}|\mathcal{A}|Klog|\mathcal{S}||\mathcal{A}|HK}$
$\displaystyle-10H^{1.5}\sqrt{|\mathcal{S}|^{2}|\mathcal{A}|log|\mathcal{S}||\mathcal{A}|H}.$
(13)

Thus, putting together (10), (4) and (6.1), the leading terms of
$\tilde{\mathcal{O}}(\sqrt{K})$ cancel out and we get

$\mathfrak{BR}(K;c)=\tilde{\mathcal{O}}\left(C^{\prime\prime}(H-\tau)+H^{1.5}\sqrt{|\mathcal{S}|^{2}|\mathcal{A}|C^{\prime\prime}}\right)=\tilde{\mathcal{O}}(1),$

i.e., constraint violation regret is a constant, and does not grow with $K$.

###  6.2 Reward Objective Regret Analysis

We next provide regret analysis of the reward objective. Let
$\pi^{\epsilon_{k},*}$ be the optimal policy for the pessimistic optimization
problem (where $p$ is the true transition probability of the MDP):

max $\displaystyle V_{1}^{\pi}(r,p)$ (14) s.t. $\displaystyle
V_{1}^{\pi}(c,p)\leq\tau-\epsilon_{k}.$

Let $\pi^{\epsilon_{k},\hat{p}_{k}}$ be the optimal policy for the pessimistic
optimization problem (where $\hat{p}_{k}$ is the sampled transition
probability of the MDP):

max $\displaystyle V_{1}^{\pi}(r,\hat{p}_{k})$ (15) s.t. $\displaystyle
V_{1}^{\pi}(c,\hat{p}_{k})\leq\tau-\epsilon_{k}.$

We can decompose the reward regret term as follows:

$\displaystyle\mathfrak{BR}(K;r)={\mathbb{E}}\left[\sum_{k=1}^{K}\left(V_{1}^{\pi^{*}}(r,p)-V^{\pi^{k}}_{1}(r,p)\right)\right]$
$\displaystyle=\sum_{k=1}^{C^{{}^{\prime\prime}}-1}{\mathbb{E}}\left[V_{1}^{\pi^{*}}(r,p)-V^{\pi^{k}}_{1}(r,p)\right]$
$\displaystyle+\sum_{k=C^{\prime\prime}}^{K}{\mathbb{E}}\left[V_{1}^{\pi^{*}}(r,p)-V^{\pi^{k}}_{1}(r,p)\right]$
(splitting the sum across the sets of episodes)
$\displaystyle=\sum_{k=1}^{C^{{}^{\prime\prime}}-1}{\mathbb{E}}\left[V_{1}^{\pi^{*}}(r,p)-V^{\pi_{k}}_{1}(r,p)\right]$
$\displaystyle+\sum_{k=C^{\prime\prime}}^{K}{\mathbb{E}}\left[V_{1}^{\pi^{*}}(r,p)-V^{\pi^{\epsilon_{k},*}}_{1}(r,p)\right]$
$\displaystyle+\sum_{k=C^{\prime\prime}}^{K}{\mathbb{E}}\left[V_{1}^{\pi^{\epsilon_{k},*}}(r,p)-V^{\pi^{\epsilon_{k},\hat{p}_{k}}}_{1}(r,\hat{p}_{k})\right]$
$\displaystyle+\sum_{k=C^{\prime\prime}}^{K}{\mathbb{E}}\left[V_{1}^{\pi^{\epsilon_{k},\hat{p}_{k}}}(r,\hat{p}_{k})-V^{\pi_{k}}_{1}(r,\hat{p}_{k})\right]$
$\displaystyle+\sum_{k=C^{\prime\prime}}^{K}{\mathbb{E}}\left[V_{1}^{\pi_{k}}(r,\hat{p}_{k})-V^{\pi_{k}}_{1}(r,p)\right]$
(splitting the second sum into four parts) $\displaystyle\leq
C^{{}^{\prime\prime}}H+\sum_{k=C^{\prime\prime}}^{K}{\mathbb{E}}\left[V_{1}^{\pi^{*}}(r,p)-V^{\pi^{\epsilon_{k},*}}_{1}(r,p)\right]$
$\displaystyle+\sum_{k=C^{\prime\prime}}^{K}{\mathbb{E}}\left[V_{1}^{\pi^{\epsilon_{k},*}}(r,p)-V^{\pi^{\epsilon_{k},\hat{p}_{k}}}_{1}(r,\hat{p}_{k})\right]$
$\displaystyle+\sum_{k=C^{\prime\prime}}^{K}{\mathbb{E}}\left[V_{1}^{\pi^{\epsilon_{k},\hat{p}_{k}}}(r,\hat{p}_{k})-V^{\pi_{k}}_{1}(r,\hat{p}_{k})\right]$
$\displaystyle+\sum_{k=C^{\prime\prime}}^{K}{\mathbb{E}}\left[V_{1}^{\pi_{k}}(r,\hat{p}_{k})-V^{\pi_{k}}_{1}(r,p)\right]$
$\displaystyle\leq
C^{{}^{\prime\prime}}H+\sum_{k=C^{\prime\prime}}^{K}{\mathbb{E}}\left[V_{1}^{\pi^{*}}(r,p)-V^{\pi^{\epsilon_{k},*}}_{1}(r,p)\right]+0$
$\displaystyle+\sum_{k=C^{\prime\prime}}^{K}{\mathbb{E}}\left[V_{1}^{\pi^{\epsilon_{k},\hat{p}_{k}}}(r,\hat{p}_{k})-V^{\pi_{k}}_{1}(r,\hat{p}_{k})\right]$
$\displaystyle+\sum_{k=C^{\prime\prime}}^{K}{\mathbb{E}}\left[V_{1}^{\pi_{k}}(r,\hat{p}_{k})-V^{\pi_{k}}_{1}(r,p)\right]$
$\displaystyle(\text{by the posterior sampling property in Lemma \ref{lem:
pseq}})$ $\displaystyle\leq
C^{{}^{\prime\prime}}H+\sum_{k=C^{\prime\prime}}^{K}{\mathbb{E}}\left[V_{1}^{\pi^{*}}(r,p)-V^{\pi^{\epsilon_{k},*}}_{1}(r,p)\right]$
$\displaystyle+\sum_{k=C^{\prime\prime}}^{K}{\mathbb{E}}\left[V_{1}^{\pi^{\epsilon_{k},\hat{p}_{k}}}(r,\hat{p}_{k})-V^{\pi_{k}}_{1}(r,\hat{p}_{k})\right]$
$\displaystyle+H^{1.5}\sqrt{30|\mathcal{S}|^{2}|\mathcal{A}|K\log(|\mathcal{S}||\mathcal{A}|KH)}+2H$
$\displaystyle(\text{by the regret bound in Lemma \ref{lem: psrlreg}})$

The other terms are bounded as follows. Similar to Lemma 5.7 in (Liu et al.,
2021a), we can define a probabilistic mixed policy of $\pi^{*}$ and
$\pi_{0}^{p}$ to prove the following lemma:

######  Lemma 5.

The first summation term above can be bounded as

$\displaystyle\sum_{k=C^{\prime\prime}}^{K}{\mathbb{E}}\left[V_{1}^{\pi^{*}}(r,p)-V_{1}^{\pi^{\epsilon_{k},*}}(r,p)\right]$
$\displaystyle\leq\sum_{k=C^{\prime\prime}}^{K}\frac{\epsilon_{k}H}{\tau-c^{0}}=\tilde{\mathcal{O}}\left(\frac{H^{2.5}}{\tau-c^{0}}\sqrt{|\mathcal{S}|^{2}|\mathcal{A}|K}\right).$
(16)

By optimality of $\pi_{k}$ and the nature of the update of the dual parameter
$\lambda_{k}$, we can prove the following lemma:

######  Lemma 6.

$\sum_{k=C^{\prime\prime}}^{K}{\mathbb{E}}\left[V_{1}^{\pi^{\epsilon_{k},\hat{p}_{k}}}(r,\hat{p}_{k})-V^{\pi_{k}}_{1}(r,\hat{p}_{k})\right]=\tilde{\mathcal{O}}\left(\frac{H}{\tau-c^{0}}\sqrt{K}\right)$

The proof of this lemma can be found in the Appendix.

Now, putting together (6.2), Lemma 5 and lemma 6, we get that

$\mathfrak{BR}(K;r)=\tilde{\mathcal{O}}\left(\frac{H^{2.5}}{\tau-c^{0}}\sqrt{|\mathcal{S}|^{2}|\mathcal{A}|K}\right).$

######  Remark 2.

We note that we can improve the upper bound on $\mathfrak{BR}(K;r)$ from
$\tilde{\mathcal{O}}\left(H^{2.5}\sqrt{|\mathcal{S}|^{2}|\mathcal{A}|K}\right)$
to $\tilde{\mathcal{O}}\left(H^{2.5}\sqrt{|\mathcal{S}||\mathcal{A}|K}\right)$
by using the leveraging an improved regret bound (Osband & Van Roy, 2017)
i.e.,
$\tilde{\mathcal{O}}\left(H^{1.5}\sqrt{|\mathcal{S}||\mathcal{A}|K}\right)$
for the PSRL algorithm and appropriate scaling of the $\epsilon_{k}$ terms.
But, this would require an assumption that the transition probability has an
independent Dirichlet prior.

##  7 Experimental Results

In this section, we evaluate the empirical performance of the Safe PSRL
algorithm and compare it with the state-of-the-art DOPE algorithm (Bura et
al., 2022), which has been shown to perform better than other comparable
algorithms (e.g., the OptPess-LP in (Liu et al., 2021a)). The empirical
performance is evaluated with respect to (i) the objective regret and (ii) the
constraint regret.

We consider the setting of a media streaming service (Bura et al., 2022) from
a wireless base station. The base station provides the streaming service at
two different speeds. These speeds follow independent Bernoulli distributions
denoted by parameters $\mu_{1}=0.9$ and $\mu_{2}=0.1$, with $\mu_{1}$
corresponding to the faster service. The data packets arriving at the device
are stored in a buffer and sent out according to a Bernoulli random process
with mean $\gamma$. The buffer size $s_{h}$ evolves as
$s_{h+1}=\min\left(\max\left(0,s_{h}+A_{h}-B_{h}\right),N\right)$ where
$A_{h}$ is the number of packet arrivals, $B_{h}$ is the number of packet
departures, and $N=10$ is the maximum size of the buffer. The device desires
to minimize the cost of running out of packets, i.e., an empty buffer, while
restricting the use of the faster service. We model this scenario as a finite
horizon CMDP with the state representing the buffer size and actions
$\\{1,2\\}$ denoting the choice of speed. We set the objective cost as
$r(s,a)=\mathbbm{1}\\{s=0\\}$ and the constraint cost as
$c(s,a)=\mathbbm{1}\\{a=1\\}$. The episode length $H$ is 10 and the constraint
threshold $\tau$ is 5.

We evaluate the cumulative regret for the Safe PSRL and the DOPE algorithm.
The transition probability is fixed and not sampled from a prior distribution.
For the Safe PSRL algorithm, we consider a Dirichlet prior for the transition
probability with parameters $[0.1,\ldots,0.1]$. The Dirichlet prior is a good
choice since it is a conjugate prior for multinomial and categorical
distributions. We further scale the $\epsilon_{k}$ parameters of the Safe PSRL
algorithm by $0.05$ to avoid excessive pessimism.

The performance of our algorithm is compared against the DOPE algorithm, which
requires a known safe policy. We choose the optimal policy of the given CMDP
with a tighter constraint threshold $c_{0}=1$ as the safe policy. The same
$c_{0}$ is also used in the Safe PSRL algorithm as the satisfiable constraint
threshold.

The algorithms are evaluated over $K=400,000$ episodes. All the experiments
are performed on a 2019 MacBook Pro with 1.4 GHz Quad-Core Intel Core i5
processor and 16GB RAM.

Figure 1: Plots showing (a) cumulative objective regret and (b) cumulative
constraint regret for the Safe PSRL and DOPE algorithms.

Figure 2: Plots showing (a) average objective regret and (b) average
constraint regret for the Safe PSRL and DOPE algorithms.

Fig. 1(a) shows that the Safe PSRL algorithm greatly outperforms the DOPE
algorithm in terms of objective regret. The objective regret for the DOPE
algorithm grows almost linearly for a very large number of episodes. In
comparison, the Safe PSRL attains $\sqrt{K}$ behavior much earlier. Fig. 2(a)
for the average objective regret shows this behavior more clearly.

In Fig. 1(b), we see that the constraint regrets for both the Safe PSRL and
the DOPE algorithm are negative for almost all of the episodes. This implies
that the constraint was satisfied in almost all of the episodes and matches
with the theoretical guarantees for both the algorithms.

We observe the initial jumps in Fig. 2(a) and Fig. 2(b) with respect to the
Safe PSRL regret plots because a few initial policies returned by the Safe
PSRL algorithm fail to satisfy the constraint while achieving better reward
objective performance.

This behavior occurs because the dual parameter $\lambda$, which starts from
$0$, has not yet caught up with the appropriate value which would ensure
optimal objective performance while satisfying the constraint. We can infer
from the regret plot that this appropriate $\lambda$ value is reached fairly
quickly by the Safe PSRL algorithm. The DOPE algorithm, on the other hand,
relies on the safe policy for too long before it starts to explore.

We thus show that the Safe PSRL algorithm is able to achieve superior
objective regret performance while satisfying the constraint for almost all
the episodes. This result is further achieved without the knowledge of a safe
policy.

##  8 Conclusions

We addressed the problem of safe online learning for episodic MDPs with
constraints and unknown transition probabilities. The Safe PSRL is the first
posterior sampling algorithm that achieves bounded constraint violation regret
while achieving near-optimal cumulative reward regret. The algorithm has
better empirical performance than other state-of-the-art algorithms (e.g., the
DOPE algorithm) for the same setting and does not need to assume knowledge of
a safe policy. The algorithm can be extended to the infinite-horizon setting.
Incorporating chance or risk constraints would be another interesting
direction for future work.

## References

  * Agarwal et al. (2022) Agarwal, M., Bai, Q., and Aggarwal, V.  Regret guarantees for model-based reinforcement learning with long-term average constraints.  In _The 38th Conference on Uncertainty in Artificial Intelligence_ , 2022.
  * Agrawal & Goyal (2012) Agrawal, S. and Goyal, N.  Analysis of thompson sampling for the multi-armed bandit problem.  In _Conference on learning theory_ , pp. 39–1. JMLR Workshop and Conference Proceedings, 2012.
  * Agrawal & Goyal (2013) Agrawal, S. and Goyal, N.  Thompson sampling for contextual bandits with linear payoffs.  In _International Conference on Machine Learning_ , pp. 127–135. PMLR, 2013.
  * Altman (1999) Altman, E.  _Constrained Markov Decision Processes_ , volume 7.  CRC Press, 1999.
  * Amani et al. (2019) Amani, S., Alizadeh, M., and Thrampoulidis, C.  Linear stochastic bandits under safety constraints.  _Advances in Neural Information Processing Systems_ , 32, 2019.
  * Auer & Ortner (2005) Auer, P. and Ortner, R.  Online regret bounds for a new reinforcement learning algorithm.  In _Proceedings 1st Austrian Cognitive Vision Workshop_ , 2005.
  * Azar et al. (2017) Azar, M. G., Osband, I., and Munos, R.  Minimax regret bounds for reinforcement learning.  In _Proceedings of the 34th International Conference on Machine Learning-Volume 70_ , pp. 263–272. JMLR. org, 2017.
  * Bai et al. (2022) Bai, Q., Bedi, A. S., Agarwal, M., Koppel, A., and Aggarwal, V.  Achieving zero constraint violation for constrained reinforcement learning via primal-dual approach.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 36, pp. 3682–3689, 2022.
  * Brantley et al. (2020) Brantley, K., Dudik, M., Lykouris, T., Miryoosefi, S., Simchowitz, M., Slivkins, A., and Sun, W.  Constrained episodic reinforcement learning in concave-convex and knapsack settings.  _Advances in Neural Information Processing Systems_ , 33:16315–16326, 2020.
  * Bura et al. (2022) Bura, A., Hasanzadezonuzy, A., Kalathil, D., Shakkottai, S., and Chamberland, J.-F.  Dope: Doubly optimistic and pessimistic exploration for safe reinforcement learning.  In _Advances in Neural Information Processing Systems_ , 2022.
  * Chapelle & Li (2011) Chapelle, O. and Li, L.  An empirical evaluation of thompson sampling.  _Advances in neural information processing systems_ , 24:2249–2257, 2011.
  * Chen et al. (2022) Chen, L., Jain, R., and Luo, H.  Learning infinite-horizon average-reward markov decision processes with constraints.  _arXiv preprint arXiv:2202.00150_ , 2022.
  * Ding et al. (2020) Ding, D., Zhang, K., Basar, T., and Jovanovic, M.  Natural policy gradient primal-dual method for constrained markov decision processes.  _Advances in Neural Information Processing Systems_ , 33:8378–8390, 2020.
  * Ding et al. (2021) Ding, D., Wei, X., Yang, Z., Wang, Z., and Jovanovic, M.  Provably efficient safe exploration via primal-dual policy optimization.  In _International Conference on Artificial Intelligence and Statistics_ , pp. 3304–3312. PMLR, 2021.
  * Efroni et al. (2020) Efroni, Y., Mannor, S., and Pirotta, M.  Exploration-exploitation in constrained mdps.  _arXiv preprint arXiv:2003.02189_ , 2020.
  * Gopalan & Mannor (2015) Gopalan, A. and Mannor, S.  Thompson sampling for learning parameterized markov decision processes.  In _Conference on Learning Theory_ , pp. 861–898. PMLR, 2015.
  * HasanzadeZonuzy et al. (2021) HasanzadeZonuzy, A., Bura, A., Kalathil, D., and Shakkottai, S.  Learning with safety constraints: Sample complexity of reinforcement learning for constrained mdps.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 35, pp. 7667–7674, 2021.
  * Jafarnia-Jahromi et al. (2021a) Jafarnia-Jahromi, M., Chen, L., Jain, R., and Luo, H.  Online learning for stochastic shortest path model via posterior sampling.  _arXiv preprint arXiv:2106.05335_ , 2021a.
  * Jafarnia-Jahromi et al. (2021b) Jafarnia-Jahromi, M., Jain, R., and Nayyar, A.  Learning zero-sum stochastic games with posterior sampling.  _arXiv preprint arXiv:2109.03396_ , 2021b.
  * Jafarnia-Jahromi et al. (2021c) Jafarnia-Jahromi, M., Jain, R., and Nayyar, A.  Online learning for unknown partially observable mdps.  _arXiv preprint arXiv:2102.12661_ , 2021c.
  * Jaksch et al. (2010) Jaksch, T., Ortner, R., and Auer, P.  Near-optimal regret bounds for reinforcement learning.  _Journal of Machine Learning Research_ , 11(Apr):1563–1600, 2010.
  * Jin et al. (2018) Jin, C., Allen-Zhu, Z., Bubeck, S., and Jordan, M. I.  Is Q-learning provably efficient?  In _Advances in Neural Information Processing Systems_ , pp. 4863–4873, 2018.
  * Kalagarla et al. (2021) Kalagarla, K. C., Jain, R., and Nuzzo, P.  A sample-efficient algorithm for episodic finite-horizon mdp with constraints.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 35, pp. 8030–8037, 2021.
  * Kaufmann et al. (2012) Kaufmann, E., Korda, N., and Munos, R.  Thompson sampling: An asymptotically optimal finite-time analysis.  In _International conference on algorithmic learning theory_ , pp. 199–213. Springer, 2012.
  * Khezeli & Bitar (2020) Khezeli, K. and Bitar, E.  Safe linear stochastic bandits.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 34, pp. 10202–10209, 2020.
  * Lai & Robbins (1985) Lai, T. L. and Robbins, H.  Asymptotically efficient adaptive allocation rules.  _Advances in applied mathematics_ , 6(1):4–22, 1985.
  * Liu et al. (2021a) Liu, T., Zhou, R., Kalathil, D., Kumar, P., and Tian, C.  Learning policies with zero or bounded constraint violation for constrained mdps.  _Advances in Neural Information Processing Systems_ , 34:17183–17193, 2021a.
  * Liu et al. (2021b) Liu, X., Li, B., Shi, P., and Ying, L.  An efficient pessimistic-optimistic algorithm for stochastic linear bandits with general constraints.  _Advances in Neural Information Processing Systems_ , 34:24075–24086, 2021b.
  * Osband & Van Roy (2017) Osband, I. and Van Roy, B.  Why is posterior sampling better than optimism for reinforcement learning?  In _International Conference on Machine Learning_ , pp. 2701–2710. PMLR, 2017.
  * Osband et al. (2013) Osband, I., Russo, D., and Van Roy, B.  (more) efficient reinforcement learning via posterior sampling.  _Advances in Neural Information Processing Systems_ , 26, 2013.
  * Ouyang et al. (2017) Ouyang, Y., Gagrani, M., Nayyar, A., and Jain, R.  Learning unknown markov decision processes: A thompson sampling approach.  In _Advances in Neural Information Processing Systems_ , pp. 1333–1342, 2017.
  * Pacchiano et al. (2021) Pacchiano, A., Ghavamzadeh, M., Bartlett, P., and Jiang, H.  Stochastic bandits with linear constraints.  In _International Conference on Artificial Intelligence and Statistics_ , pp. 2827–2835. PMLR, 2021.
  * Puterman (1994) Puterman, M. L.  _Markov Decision Processes: Discrete Stochastic Dynamic Programming_.  John Wiley & Sons, Inc., New York, NY, USA, 1st edition, 1994.  ISBN 0471619779.
  * Qiu et al. (2020) Qiu, S., Wei, X., Yang, Z., Ye, J., and Wang, Z.  Upper confidence primal-dual reinforcement learning for cmdp with adversarial loss.  _Advances in Neural Information Processing Systems_ , 33:15277–15287, 2020.
  * Singh et al. (2020) Singh, R., Gupta, A., and Shroff, N. B.  Learning in markov decision processes under constraints.  _arXiv preprint arXiv:2002.12435_ , 2020.
  * Thompson (1933) Thompson, W. R.  On the likelihood that one unknown probability exceeds another in view of the evidence of two samples.  _Biometrika_ , 25(3/4):285–294, 1933.
  * Wei et al. (2020) Wei, C.-Y., Jafarnia-Jahromi, M., Luo, H., Sharma, H., and Jain, R.  Model-free reinforcement learning in infinite-horizon average-reward markov decision processes.  In _International Conference on Machine Learning_ , pp. 10170–10180. PMLR, 2020.
  * Wei et al. (2022) Wei, H., Liu, X., and Ying, L.  Triple-q: A model-free algorithm for constrained reinforcement learning with sublinear regret and zero constraint violation.  In _International Conference on Artificial Intelligence and Statistics_ , pp. 3274–3307. PMLR, 2022.
  * Zheng & Ratliff (2020) Zheng, L. and Ratliff, L.  Constrained upper confidence reinforcement learning.  In _Learning for Dynamics and Control_ , pp. 620–629. PMLR, 2020\.

##  Appendix A Proofs

###  A.1 Proof of Lemma 4

###### Proof.

Now for $k\geq C^{\prime\prime}$, consider:

$\displaystyle\frac{{\lambda_{k+1}}^{2}}{2}-\frac{{\lambda_{k}}^{2}}{2}$
$\displaystyle=\lambda_{k}(\lambda_{k+1}-\lambda_{k})+\frac{1}{2}(\lambda_{k+1}-\lambda_{k})^{2}$
$\displaystyle=\lambda_{k}(V^{\pi_{k}}_{1}(c,\hat{p}_{k})+\epsilon_{k}-\tau)+\frac{1}{2}(V^{\pi_{k}}_{1}(c,\hat{p}_{k})+\epsilon_{k}-\tau)^{2}$
$\displaystyle=\lambda_{k}(V^{\pi_{k}}_{1}(c,\hat{p}_{k})+\epsilon_{k}-\tau)-\eta_{k}V^{\pi_{k}}_{1}(r,\hat{p}_{k})$
$\displaystyle+\eta_{k}V^{\pi_{k}}_{1}(r,\hat{p}_{k})+\frac{1}{2}(V^{\pi_{k}}_{1}(c,\hat{p}_{k})+\epsilon_{k}-\tau)^{2}$
$\displaystyle\leq\lambda_{k}(V^{\pi_{k}}_{1}(c,\hat{p}_{k})+\epsilon_{k}-\tau)-\eta_{k}V^{\pi_{k}}_{1}(r,\hat{p}_{k})$
$\displaystyle+\eta_{k}H+\frac{1}{2}(V^{\pi_{k}}_{1}(c,\hat{p}_{k})+\epsilon_{k}-\tau)^{2}$
$\displaystyle\leq\lambda_{k}(V^{\pi_{k}}_{1}(c,\hat{p}_{k})+\epsilon_{k}-\tau)-\eta_{k}V^{\pi_{k}}_{1}(r,\hat{p}_{k})$
$\displaystyle+\eta_{k}H+(V^{\pi_{k}}_{1}(c,\hat{p}_{k})-\tau)^{2}+\epsilon_{k}^{2}$
$\displaystyle(\text{ Using }\frac{(a+b)^{2}}{2}\leq a^{2}+b^{2})$
$\displaystyle\leq\lambda_{k}(V^{\pi_{k}}_{1}(c,\hat{p}_{k})+\epsilon_{k}-\tau)-\eta_{k}V^{\pi_{k}}_{1}(r,\hat{p}_{k})$
$\displaystyle+\eta_{k}H+H^{2}+\epsilon_{k}^{2}$
$\displaystyle\leq\lambda_{k}(V^{\pi_{0}^{\hat{p}_{k}}}_{1}(c,\hat{p}_{k})+\epsilon_{k}-\tau)-\eta_{k}V^{\pi_{0}^{\hat{p}_{k}}}_{1}(r,\hat{p}_{k})$
$\displaystyle+\eta_{k}H+H^{2}+\epsilon_{k}^{2}$ $\displaystyle(\text{ By
optimality of $\pi_{k}$ in primal update })$
$\displaystyle\leq\lambda_{k}(c_{0}+\epsilon_{k}-\tau)+\eta_{k}H+H^{2}+\epsilon_{k}^{2}$
$\displaystyle\leq-\frac{\lambda_{k}(\tau-
c_{0})}{2}+\eta_{k}H+H^{2}+\epsilon_{k}^{2}$ $\displaystyle(\text{ as for
}k\geq C^{\prime\prime},\epsilon_{k}\leq\frac{(\tau-c_{0})}{2})$

Now for $\lambda\geq\varphi_{k}$ where
$\varphi_{k}:=4(H^{2}+\epsilon_{k}^{2}+\eta_{k}H)/(\tau-c^{0})$, we have:

$\displaystyle{\mathbb{E}}\left[\lambda_{k+1}-\lambda_{k}|\lambda_{k}=\lambda\right]\leq{\mathbb{E}}\left[\frac{\lambda_{k+1}^{2}-\lambda_{k}^{2}}{2\lambda_{k}}|\lambda_{k}=\lambda\right]$
$\displaystyle(\text{Using }x-y\leq\frac{x^{2}-y^{2}}{2y},\text{for }y>0)$
$\displaystyle=\frac{1}{\lambda}{\mathbb{E}}\left[\frac{\lambda_{k+1}^{2}-\lambda_{k}^{2}}{2}|\lambda_{k}=\lambda\right]$
$\displaystyle\leq\frac{1}{\lambda}{\mathbb{E}}\left[-\frac{\lambda_{k}(\tau-
c_{0})}{2}+\eta_{k}H+H^{2}+\epsilon_{k}^{2}|\lambda_{k}=\lambda\right]$
$\displaystyle=-\frac{(\tau-
c_{0})}{2}+\frac{\eta_{k}H+H^{2}+\epsilon_{k}^{2}}{\lambda}$
$\displaystyle\leq-\frac{(\tau-c_{0})}{2}+\frac{(\tau-c_{0})}{4}$
$\displaystyle=-\frac{(\tau-c_{0})}{4}:=\rho$

Further,
$|\lambda_{k+1}-\lambda_{k}|=|V^{\pi_{k}}_{1}(c,\hat{p}_{k})+\epsilon_{k}-\tau|\leq
H$ with probability 1. Thus, by lemma 3, we have :

$\displaystyle{\mathbb{E}}\left[e^{\zeta\lambda_{K+1}}\right]\leq{\mathbb{E}}\left[e^{\zeta\lambda_{C^{\prime\prime}}}\right]+\frac{2e^{\zeta\left(H+\varphi_{K+1}\right)}}{\zeta\rho},$

where $\zeta=\rho/(H^{2}+H\rho/3)$.

$\displaystyle\implies
e^{\zeta{\mathbb{E}}\left[\lambda_{K+1}\right]}\leq{\mathbb{E}}\left[e^{\zeta\lambda_{C^{\prime\prime}}}\right]+\frac{2e^{\zeta\left(H+\varphi_{K+1}\right)}}{\zeta\rho}$
(By Jensen’s inequality)
$\displaystyle\implies{\mathbb{E}}\left[\lambda_{K+1}\right]\leq\frac{1}{\zeta}\log\left[{\mathbb{E}}\left[e^{\zeta\lambda_{C^{\prime\prime}}}\right]+\frac{2e^{\zeta\left(H+\varphi_{K+1}\right)}}{\zeta\rho}\right]$

Further,

$\displaystyle\lambda_{C^{\prime\prime}}$
$\displaystyle\leq\lambda_{1}+\sum_{1}^{C^{\prime\prime}-1}(V^{\pi^{k}}_{1}(c,\hat{p}_{k})+\epsilon_{k}-\tau)_{+}$
$\displaystyle\leq\sum_{1}^{C^{\prime\prime}}\epsilon_{k}+C^{\prime\prime}(H-\tau)$
$\displaystyle:=\lambda_{C^{\prime\prime}}^{\max}$

Continuing,

$\displaystyle{\mathbb{E}}\left[\lambda_{K+1}\right]$
$\displaystyle\leq\frac{1}{\zeta}\log\left[e^{\zeta\lambda_{C^{\prime\prime}}^{\max}}+\frac{2e^{\zeta\left(H+\varphi_{K+1}\right)}}{\zeta\rho}\right]$
$\displaystyle\leq\frac{1}{\zeta}\log\left[e^{\zeta\lambda_{C^{\prime\prime}}^{\max}}+\frac{8H^{2}e^{\zeta\left(H+\varphi_{K+1}\right)}}{3\rho^{2}}\right]$
$\displaystyle(\text{ Using }\zeta\geq\frac{3(\tau-c_{0})}{13H^{2}})$
$\displaystyle\leq\frac{1}{\zeta}\log\left[\frac{11H^{2}}{3\rho^{2}}e^{\zeta\left(H+\varphi_{K+1}+\lambda_{C^{\prime\prime}}^{\max}\right)}\right]$
$\displaystyle=\frac{1}{\zeta}\log\frac{11H^{2}}{3\rho^{2}}+H+\varphi_{K+1}+\lambda_{C^{\prime\prime}}^{\max}$
$\displaystyle=\frac{1}{\zeta}\log\frac{11H^{2}}{3\rho^{2}}+H+\sum_{1}^{C^{\prime\prime}}\epsilon_{k}+C^{\prime\prime}(H-\tau)$
$\displaystyle+\frac{4(H^{2}+\epsilon_{K+1}^{2}+\eta_{K+1}H)}{(\tau-c^{0})}$

∎

###  A.2 Proof of Lemma 6

###### Proof.

$\displaystyle\sum_{k=C^{\prime\prime}}^{K}{\mathbb{E}}\left[V_{1}^{\pi^{\epsilon_{k},\hat{p}_{k}}}(r,\hat{p}_{k})-V^{\pi_{k}}_{1}(r,\hat{p}_{k})\right]$
$\displaystyle=\sum_{k=C^{\prime\prime}}^{K}{\mathbb{E}}\left[\frac{\lambda_{k}}{\eta_{k}}\left(V_{1}^{\pi^{\epsilon_{k},\hat{p}_{k}}}(c,\hat{p}_{k})-V^{\pi_{k}}_{1}(c,\hat{p}_{k})\right)\right]$
$\displaystyle+\sum_{k=C^{\prime\prime}}^{K}{\mathbb{E}}\left[\left(V_{1}^{\pi^{\epsilon_{k},\hat{p}_{k}}}(r,\hat{p}_{k})-\frac{\lambda_{k}}{\eta_{k}}V_{1}^{\pi^{\epsilon_{k},\hat{p}_{k}}}(c,\hat{p}_{k})\right)\right]$
$\displaystyle-\sum_{k=C^{\prime\prime}}^{K}{\mathbb{E}}\left[\left(V_{1}^{\pi^{k}}(r,\hat{p}_{k})-\frac{\lambda_{k}}{\eta_{k}}V_{1}^{\pi^{k}}(c,\hat{p}_{k})\right)\right]$
$\displaystyle\leq\sum_{k=C^{\prime\prime}}^{K}{\mathbb{E}}\left[\frac{\lambda_{k}}{\eta_{k}}\left(V_{1}^{\pi^{\epsilon_{k},\hat{p}_{k}}}(c,\hat{p}_{k})-V^{\pi_{k}}_{1}(c,\hat{p}_{k})\right)\right]+0$
$\displaystyle(\text{ By optimality of $\pi_{k}$ in primal update })$
$\displaystyle\leq\sum_{k=C^{\prime\prime}}^{K}{\mathbb{E}}\left[\frac{\lambda_{k}}{\eta_{k}}\left(\tau-\epsilon_{k}-V^{\pi_{k}}_{1}(c,\hat{p}_{k})\right)\right]$
$\displaystyle\leq\sum_{k=C^{\prime\prime}}^{K}{\mathbb{E}}\left[\frac{1}{\eta_{k}}((\lambda_{k}(\lambda_{k+1}-\lambda_{k})+\tau^{2})\right]$
(By update rule for $\lambda_{k}$)
$\displaystyle\leq{\mathbb{E}}\left[\sum_{k=C^{\prime\prime}}^{K}\frac{1}{\eta_{k}}(\frac{\lambda_{k}^{2}}{2}-\frac{\lambda_{k+1}^{2}}{2})+\sum_{k=C^{\prime\prime}}^{K}\frac{1}{2\eta_{k}}(\lambda_{k+1}-\lambda_{k})^{2}\right.$
$\displaystyle\left.+\sum_{k=C^{\prime\prime}}^{K}\frac{\tau^{2}}{\eta_{k}}\right]$
$\displaystyle\leq{\mathbb{E}}\left[\frac{(\lambda_{C^{\prime\prime}})^{2}}{2\eta_{C^{\prime\prime}}}\right]+\sum_{k=C^{\prime\prime}}^{K}\frac{H^{2}}{2\eta_{k}}+\sum_{k=C^{\prime\prime}}^{K}\frac{H^{2}}{\eta_{k}}$
(As $\eta_{k}$ increases with $k$)
$\displaystyle\leq\frac{(\sum_{k=1}^{C^{\prime\prime}}\epsilon_{k}+C^{{}^{\prime\prime}}(H-\tau))^{2}}{2\eta_{C^{\prime\prime}}}+\frac{3H}{2}\sum_{C^{\prime\prime}}^{K}\frac{1}{(\tau-
c_{0})\sqrt{k}}$
$\displaystyle=\tilde{\mathcal{O}}\left(\frac{H}{\tau-c^{0}}\sqrt{K}\right)$

∎