Jiang, Ye

Approaching Constrained Markov Decision Process

Achieving $\tilde{O}(1/\varepsilon)$ Sample Complexity for Constrained Markov
Decision Process

$\text{Jiashuo Jiang}^{{\dagger}}$, $\leavevmode\nobreak\ \text{Yinyu
Ye}^{{\ddagger}\S}$

${\dagger}\leavevmode\nobreak\ $Department of Industrial Engineering &
Decision Analytics, Hong Kong University of Science and Technology
${\ddagger}\leavevmode\nobreak\ $Institute for Computational and Mathematical
Engineering, Stanford University
$\S\leavevmode\nobreak\ $Department of Management Science & Engineering,
Stanford University

We consider the reinforcement learning problem for the constrained Markov
decision process (CMDP), which plays a central role in satisfying safety or
resource constraints in sequential learning and decision-making. In this
problem, we are given finite resources and a MDP with unknown transition
probabilities. At each stage, we take an action, collecting a reward and
consuming some resources, all assumed to be unknown and need to be learned
over time. In this work, we take the first step towards deriving optimal
problem-dependent guarantees for the CMDP problems. We derive a logarithmic
regret bound, which translates into a
$O(\frac{\kappa}{\varepsilon}\cdot\log^{2}(1/\varepsilon))$ sample complexity
bound, with $\kappa$ being a problem-dependent parameter, yet independent of
$\varepsilon$. Our sample complexity bound improves upon the state-of-art
$O(1/\varepsilon^{2})$ sample complexity for CMDP problems established in the
previous literature, in terms of the dependency on $\varepsilon$. To achieve
this advance, we develop a new framework for analyzing CMDP problems. To be
specific, our algorithm operates in the primal space and we resolve the primal
LP for the CMDP problem at each period in an online manner, with adaptive
remaining resource capacities. The key elements of our algorithm are: i). an
eliminating procedure that characterizes one optimal basis of the primal LP,
and; ii) a resolving procedure that is adaptive to the remaining resources and
sticks to the characterized optimal basis.

Constrained MDP, Reinforcement Learning, Online Packing/Linear Programming,
Problem-dependent Bound

##  1 Introduction

Reinforcement learning (RL) is pivotal in the realm of dynamic decision-making
under uncertainty, where the objective is to maximize total reward through
ongoing interaction with and learning from an enigmatic environment. Markov
Decision Processes (MDPs) are a prevalent framework for encapsulating
environmental dynamics. MDPs have been instrumental in various domains, such
as video gaming (Mnih et al. 2013), robotics (Kober et al. 2013), recommender
systems (Shani et al. 2005), and beyond. Yet, they fall short in accommodating
additional constraints that may influence the formulation of the optimal
policy and the decision-maker’s engagement with the uncertain environment.
Often, in MDP applications, there are stringent constraints on utilities or
costs, emanating from areas like safe autonomous driving (Fisac et al. 2018),
robotics (Ono et al. 2015), and financial management (Tamar et al. 2012).
These constraints might also symbolize limitations on resources within
resource allocation contexts with applications to revenue management (Jia et
al. 2023, Jiang 2023, Li et al. 2023). Constrained MDPs (CMDPs), as introduced
in Altman (1999), enhance MDPs to factor in constraints affecting long-term
policy results. In CMDPs, the decision-maker aims to optimize cumulative
rewards while adhering to these constraints. Our paper focuses on CMDPs, and
we aim to develop efficient algorithmic solutions.

The significance of RL in CMDP contexts has garnered substantial attention in
recent years. A variety of methods for tackling CMDPs have been developed,
including the primal-dual technique (Efroni et al. 2020, Liu et al. 2021a, Wei
et al. 2021, Ding et al. 2021, Li et al. 2021a, Ghosh et al. 2022, Gladin et
al. 2023), which leverages the Lagrangian dual of CMDPs and implements an
online learning strategy for the iterative update of dual variables. Other
methods encompass constrained optimization (Achiam et al. 2017), the Lyapunov
technique (Chow et al. 2018), among others. Previous research has established
minimax bounds for CMDPs, representing the optimal regret that can be achieved
for the most challenging problem within a specific class of problems.
Nonetheless, these minimax regret bounds and worst-case scenarios can be
overly conservative, leading to a disconnect between theoretical guarantees
and practical performance for specific problem instances. A more tailored
approach is warranted—one that ensures great performance on every single
problem instance and furnishes problem-dependent guarantees. Our research
takes the first step towards deriving optimal problem-dependent guarantees for
CMDP problems.

###  1.1 Main Results and Contributions

In the exploration of the $\gamma$-discounted infinite horizon CMDP problem
within a tabular context, we leverage a generative model that, for each state-
action pair, yields a sample from the unknown stochastic reward, costs, and
state transitions. The main result of our research is the introduction of a
novel algorithm that promises a $O(\kappa\cdot\log N)$ regret upper bound for
both the cumulative reward and constraint violations, where $N$ is the number
of queries to the generative model and $\kappa$ is a problem-specific
parameter, yet independent of $N$. This translates into a
$\tilde{O}\left(\frac{1}{\varepsilon}\right)$ sample complexity bound, where
$\tilde{O}(\cdot)$ hides a term polynomial in $\log(1/\varepsilon)$. Note that
the state-of-the-art sample complexity bound under the worst-case scenarios is
$O(1/\varepsilon^{2})$, which has been established in a series of work (Wang
2020, Jin and Sidford 2020, Efroni et al. 2020). Though the $O(1/\varepsilon)$
or better iteration complexity has been achieved in Li et al. (2021a), Liu et
al. (2021b), Zhou et al. (2022), Gladin et al. (2023), it comes with a sample
complexity bound worse than $O(1/\varepsilon^{2})$. Our algorithm enjoys a
sample complexity bound that has a better dependency in terms of
$\varepsilon$.

To achieve these problem-dependent guarantees, we have devised a new
algorithmic framework to analyze CMDP problems, inspired by the online
packing/linear programming (LP) literature (Agrawal et al. 2014, Kesselheim et
al. 2014, Li and Ye 2022, Li et al. 2021b). Specifically, we utilize a linear
programming reformulation of the CMDP problem, where policies are delineated
via occupancy measures (Altman 1999). The optimal policy emerges from the LP’s
solution; however, the indeterminate model parameters mean the LP cannot be
solved directly but must be approached online as we obtain more samples from
the generative model. Each generative model query leads to solving an
empirical LP with accrued samples, and our final policy is derived from
averaging these solutions—an approach akin to the methodology in online LP. A
critical feature of our algorithm is the adaptiveness of the LP constraints’
right-hand side to the input samples, a technique demonstrated to achieve
logarithmic regret in online LP literature, which we now apply to CMDP
problems.

Furthermore, we extend our contributions to the online LP literature. The
prevalent assumption of non-degeneracy in online LP, which postulates a unique
LP solution, is not a requirement in our approach. We introduce an innovative
method to identify and consistently apply one optimal LP basis, even when
multiple bases exist. Aligning with a single optimal basis—as opposed to
requiring uniqueness—affords the same benefits and leads to logarithmic
regret. To delve into details, our algorithm enhances performance through two
new components. The first is a systematic procedure to pinpoint a particular
optimal LP basis from potentially several (outlined in Algorithm 1), diverging
from the traditional literature that presupposes a sole optimal solution and
basis. The second component is a resolving procedure that capitalizes on the
structure of the identified optimal basis. Once an optimal basis is selected,
we can determine the corresponding optimal solution by solving a set of linear
equations, which involves only the non-zero basic variables and the active
constraints. This resolving process transforms the algorithmic idea of
resolving an LP, as seen in previous works (Agrawal et al. 2014, Bumpensanti
and Wang 2020, Li and Ye 2022, Vera and Banerjee 2021, Li et al. 2021b), into
solving specific linear equations based on the chosen optimal basis (detailed
in Algorithm 2). Previous research relies on the non-degeneracy assumption to
stabilize the optimal basis throughout the resolving process. However, our two
innovative elements enable our algorithm to consistently adhere to one optimal
basis, thus removing the non-degeneracy assumption. This not only simplifies
the algorithm’s execution (from resolving LP to resolving linear equations)
but also extends its applicability, freeing it from assumptions that have
traditionally limited the scope of online LP techniques.

We finally discuss the dependency of our sample complexity bound on problem
parameters other than $\varepsilon$. We restrict to the MDP context without
resource constraints. Denote by $\mathcal{S}$ the state set and $\mathcal{A}$
the action set. We show a sample complexity bound of
$O\left(\frac{|\mathcal{S}|^{4}\cdot|\mathcal{A}|}{(1-\gamma)^{4}\cdot\mathrm{gap}_{\min}}\cdot\frac{\log^{2}(1/\varepsilon)}{\varepsilon}\right)$,
where $\mathrm{gap}_{\min}$ is a constant that represents the gap between the
optimal policy and the best “sub-optimal” policy that takes a non-optimal
action given a state. Such a policy sub-optimal gap shows up widely in
(logarithmic) problem-dependent guarantees for online decision-making problems
such as multi-arm-bandit (Lai and Robbins 1985) or reinforcement learning
(Auer et al. 2008), and the gap characterizes the hardness of the underlying
problem instance (e.g. Simchowitz and Jamieson (2019)). Compared to the
optimal worst-case sample complexity
$O\left(\frac{|\mathcal{S}|\cdot|\mathcal{A}|}{(1-\gamma)^{3}\cdot\varepsilon^{2}}\right)$
that is achieved in a series of work (Sidford et al. 2018, Wainwright 2019,
Wang 2020, Agarwal et al. 2020, He et al. 2021), our bound has a worse
dependency over $|\mathcal{S}|$ and $1-\gamma$. This is due to our algorithm
being LP-based and the dimension of the LP ($|\mathcal{S}|$ and $1-\gamma$)
will influence our final bounds. However, our bound enjoys a better dependency
in terms of $\varepsilon$. For the general CMDP problem, our bound will depend
additionally on the conditional number of the constraint matrix in the LP
formulation, which is a byproduct of the resolving LP heuristics (Vera and
Banerjee 2021, Li et al. 2021b). However, our $\tilde{O}(1/\varepsilon)$
sample complexity bound depends polynomially on other parameters including
$|\mathcal{S}|$, $|\mathcal{A}|$, $1-\gamma$, and the number of constraints.

In summary, our work presents a new algorithm for CMDP problems to achieve the
problem-dependent logarithmic regret or $\tilde{O}(1/\varepsilon)$ sample
complexity bound, for the first time in the literature. Firstly, we have
pioneered the application of the online LP framework to analyze CMDP problems.
Our algorithm operates in the primal space, in contrast to the primal-dual
framework associated with worst-case guarantees (e.g. Ding et al. (2021)).
Secondly, our novel approach to online LP results in logarithmic regret
without the non-degeneracy assumption, expanding its applicability and
providing new insights into both CMDP and online LP problems.

###  1.2 Further Related Work

Deriving the (logarithmic) problem-dependent guarantees is a long-standing
topic in online decision-making (Lai and Robbins 1985, Graves and Lai 1997).
Notably, there has been a recent trend of deriving (logarithmic) problem-
dependent guarantees for reinforcement learning problems, where a series of
work (Zanette and Brunskill 2019, Simchowitz and Jamieson 2019, Dann et al.
2021, Wagenmaker et al. 2022, Wagenmaker and Foster 2023) has proposed various
ways to characterize the hardness of the problem instance. A prevalent way to
characterize the hardness is to define a constant that represents the policy
sub-optimality gap between the optimal policy and a policy that takes a sub-
optimal action given a state. Then, the logarithmic guarantees depend on this
constant. Compared to the previous approaches and guarantees, our guarantees
adopt this idea of policy sub-optimal gap. Moreover, our approach can handle
resource or safety constraints that need to be satisfied by the policy. In
this way, our approach generalizes to multi-objective (safe) RL problems.

Our method is motivated by the online LP literature. The online LP problem
(Molinaro and Ravi 2014, Agrawal et al. 2014, Gupta and Molinaro 2014) covers
a wide range of applications through different ways of specifying the
underlying LP, including secretary problem (Ferguson 1989), online knapsack
problem (Arlotto and Xie 2020), quantity-based network revenue management
problem (Jasin and Kumar 2012), network routing problem (Buchbinder and Naor
2009), matching problem (Mehta et al. 2007), etc. Notably, the problem has
been studied under either (i) the stochastic input model where the coefficient
in the objective function, together with the corresponding column in the
constraint matrix is drawn from an unknown distribution $\mathcal{P}$, or (ii)
the random permutation model where they arrive in a random order (Molinaro and
Ravi 2014, Agrawal et al. 2014, Kesselheim et al. 2014, Gupta and Molinaro
2014). With an additional non-degeneracy assumption, the logarithmic regret
has been derived for the quantity-based network revenue management problem
(Jasin and Kumar 2012), the online LP problem (Li and Ye 2022), and the more
general convex allocation problem (Ma et al. 2022). The non-degeneracy
assumption has been relaxed for the network revenue management problem in a
series of work (Bumpensanti and Wang 2020, Vera and Banerjee 2021, Jiang et
al. 2022) under various settings.

###  1.3 Roadmap

In Section 2, we describe the formal problem formulation and introduce the
notations that we use in the paper. In Section 3, we present the linear
programming reformulation of our problem and we give a general overview of our
approach to illustrate the main idea. Then, in Section 4, we describe how to
construct the estimates of the LP reformulation of the CMDP problems, which
will be used in our algorithm. The formal algorithm is presented in Section 5
and the corresponding theoretical analysis is conducted in Section 6.

##  2 Preliminaries

We consider a CMDP problem with a finite set of states
$\mathcal{S}=\\{1,2,\dots,|\mathcal{S}|\\}$ and a finite set of actions
$\mathcal{A}=\\{1,2,\dots,|\mathcal{A}|\\}$. We denote by $\gamma\in(0,1)$ a
discount factor. We also denote by
$P:\mathcal{S}\times\mathcal{A}\rightarrow\mathcal{D}(\mathcal{S})$ the
probability transition kernel of the CMDP, where $\mathcal{D}(\mathcal{S})$
denotes a probability measure over the state space $\mathcal{S}$. Then,
$P(s^{\prime}|s,a)$ denotes the probability of transiting from state $s$ to
state $s^{\prime}$ when the action $a$ is executed. The initial distribution
over the states of the CMDP is denoted by $\mu_{1}$.

There is a stochaastic reward function
$r:\mathcal{S}\times\mathcal{A}\rightarrow\mathcal{D}[0,1]$ and $K$ stochastic
cost functions $c_{k}:\mathcal{S}\times\mathcal{A}\rightarrow\mathcal{D}[0,1]$
for each $k\in[K]$. We also denote by $\hat{r}(s,a)=\mathbb{E}[r(s,a)]$ for
each $(s,a)$ and $\hat{c}(s,a)=\mathbb{E}[c_{k}(s,a)]$ for each $(s,a)$. For
any Markovian policy $\pi$, where the action of $\pi$ depends only on the
current state and the action of $\pi$ is allowed to be randomized, we denote
by $V_{r}(\pi,\mu_{1})$ the infinite horizon discounted reward of the policy
$\pi$, with the formulation of $V_{r}(\pi,\mu_{1})$ given below:

$V_{r}(\pi,\mu_{0})=\mathbb{E}\left[\sum_{t=0}^{\infty}\gamma^{t}\cdot
r(s_{t},a_{t})\mid\mu_{1}\right],$ (1)

where $(s_{t},a_{t})$ is generated according to the policy $\pi$ and the
transition kernel $P$ with the initial state distribution $\mu_{1}$. For each
$k\in[K]$, the infinite horizon discounted cost of the policy $\pi$ is denoted
by $V_{k}(\pi,\mu_{1})$, and the following constraint needs to be satisfied by
the policy $\pi$,

$V_{k}(\pi,\mu_{1})=\mathbb{E}\left[\sum_{t=0}^{\infty}\gamma^{t}\cdot
c_{k}(s_{t},a_{t})\mid\mu_{1}\right]\leq\alpha_{k},\leavevmode\nobreak\
\leavevmode\nobreak\ \forall k\in[K].$ (2)

To solve the CMDP problem, we aim to find an optimal Markovian policy, denoted
by $\pi^{*}$, that maximizes the reward in (1) while satisfying the cost
constraint (2) for each $k\in[K]$, with
$\alpha_{k}\in\left[0,\frac{1}{1-\gamma}\right]$ being a pre-specified value
for each $k\in[K]$. Importantly, we assume that the reward function $r$, the
cost functions $\\{c_{k}\\}_{k=1}^{K}$, and the transition kernel $P$, are all
unknown to the decision maker. Our goal is to obtain a policy $\pi$ that
approximates the optimal policy $\pi^{*}$ with as few samples as possible. We
now describe the sampling procedure and present the performance measure of our
policy.

We assume the existence of a stylized generative model $\mathcal{M}$. The
model $\mathcal{M}$ satisfies the following condition. For each state and
action pair $(s,a)$, we can query the model $\mathcal{M}$ to obtain an
observation of $r(s,a)$, $c_{k}(s,a)$ for each $k\in[K]$, and the new state
$s^{\prime}\in\mathcal{S}$, where the transition from $s$ to $s^{\prime}$
follows the probability kernel $P(s^{\prime}|s,a)$ independently.

Note that in reinforcement learning for CMDP problems, querying the generative
model $\mathcal{M}$ can be costly. Therefore, it is desirable to query the
model $\mathcal{M}$ as less as possible, while guaranteeing the near
optimality of the approximate policy. To this end, we study two measures of
the performance of our policy. One is regret, i.e., conditioning on we can
query the model $\mathcal{M}$ at most $N$ times, we aim to derive a policy
$\pi$ and bound

$\text{Regret}_{r}(\pi,N):=V_{r}(\pi^{*},\mu_{1})-V_{r}(\pi,\mu_{1})\text{\leavevmode\nobreak\
\leavevmode\nobreak\ and\leavevmode\nobreak\ \leavevmode\nobreak\
}\text{Regret}_{k}(\pi,N):=V_{k}(\pi,\mu_{1})-\alpha_{k},\leavevmode\nobreak\
\forall k\in[K].$ (3)

The other one is sample complexity, i.e., for any $\varepsilon$, we aim to
find an $\varepsilon$-accurate policy $\pi$ such that

$V_{r}(\pi^{*},\mu_{1})-V_{r}(\pi,\mu_{1})\leq\varepsilon\text{\leavevmode\nobreak\
\leavevmode\nobreak\ and\leavevmode\nobreak\ \leavevmode\nobreak\
}V_{k}(\pi,\mu_{1})-\alpha_{k}\leq\varepsilon,\leavevmode\nobreak\ \forall
k\in[K],$ (4)

with as few samples as possible. Indeed, these two measures can be transferred
to each other, and in our analysis, we derive the sample complexity bound from
the regret bound.

Remark. Note that there are other formulations of the constraints in CMDP, for
example,

$V_{k}(\pi,\mu_{1})=\mathbb{E}\left[\sum_{t=0}^{\infty}\gamma^{t}\cdot
c_{k}(s_{t},a_{t})\mid\mu_{1}\right]\geq\lambda_{k},\leavevmode\nobreak\
\leavevmode\nobreak\ \forall k\in[K].$ (5)

in a series of work that studies safe reinforcement learning. However, the
formulation (5) can be transferred from the formulation (2). One can set
$\alpha_{k}=\frac{1}{1-\gamma}-\lambda_{k}$ for each $k\in[K]$, and it is easy
to see that the two inequalities are equivalent to each other,

$\mathbb{E}\left[\sum_{t=0}^{\infty}\gamma^{t}\cdot
c_{k}(s_{t},a_{t})\mid\mu_{1}\right]\geq\lambda_{k}\Leftrightarrow\mathbb{E}\left[\sum_{t=0}^{\infty}\gamma^{t}\cdot(1-c_{k}(s_{t},a_{t}))\mid\mu_{1}\right]\leq\alpha_{k}.$

Therefore, we can equivalently use formulation (2) with the cost function
defined as $1-c_{k}$ for each $k\in[K]$.

###  2.1 Notations

Throughout the paper, we use $n\in[N]$ to denote the time step. For the
infinite horizon discounted problem in Section 2, we can query the generative
model $\mathcal{M}$ for each $(s,a)\in\mathcal{S}\times\mathcal{A}$ for one
time, for a time step $n\in[N]$.

For a matrix $A$, we denote by $\mathcal{J}$ a row index set and $\mathcal{I}$
a column index set. Then, $A(:,\mathcal{I})$ denotes a sub-matrix of $A$ with
columns drawn from the index set $\mathcal{I}$, and $A(\mathcal{J},:)$ denotes
a sub-matrix of $A$ with rows drawn from the index set $\mathcal{J}$.
Similarly, $A(\mathcal{J},\mathcal{I})$ denotes a sub-matrix of $A$ with rows
drawn from $\mathcal{J}$ and columns drawn from $\mathcal{I}$. For any vector
$\bm{\beta}$, we use $\bm{\beta}_{\mathcal{J}}$ to denote a sub-vector of
$\bm{\beta}$ with element drawn from the index set $\mathcal{J}$.

##  3 Problem Reformulation and Overview of Our Approach

The infinite horizon discounted setting described in Section 2 admits a linear
programming reformulation. To be specific, due to the existence of the
constraints, the optimal policy of a CMDP can be randomized policies (e.g.
Altman (1999)), where it is optimal to take a stochastic action given the
current state. Therefore, it is convenient to represent a policy through the
occupation measure, which gives us the desired linear programming
reformulations of the CMDP problems.

For the infinite horizon discounted problem, the occupancy measure is defined
as $q_{\pi}(s,a)$ for any state $s$, action $a$, and policy $\pi$. Note that
$q_{\pi}(s,a)$ represents the total expected discounted time spent on the
state-action pair $(s,a)$, under policy $\pi$. Then, following Altman (1999),
the optimal policy (and the optimal occupancy measure) can be obtained from
the following linear programming.

$\displaystyle V^{\mathrm{Infi}}=\leavevmode\nobreak\ \max\ $
$\displaystyle\sum_{s\in\mathcal{S}}\sum_{a\in\mathcal{A}}\hat{r}(s,a)\cdot
q(s,a)$ (6a) $\displaystyle\mathrm{s.t.\ }$
$\displaystyle\sum_{s\in\mathcal{S}}\sum_{a\in\mathcal{A}}\hat{c}_{k}(s,a)\cdot
q(s,a)\leq\alpha_{k}$ $\displaystyle\forall k\in[K]$ (6b)
$\displaystyle\sum_{s^{\prime}\in\mathcal{S}}\sum_{a\in\mathcal{A}}q(s^{\prime},a)\cdot(\delta_{s,s^{\prime}}-\gamma\cdot
P(s|s^{\prime},a))=(1-\gamma)\cdot\mu_{1}(s)$ $\displaystyle\forall
s\in\mathcal{S}$ (6c) $\displaystyle q(s,a)\geq 0$ $\displaystyle\forall
s\in\mathcal{S},a\in\mathcal{A},$ (6d)

where $\delta_{s,s^{\prime}}=\mathbbm{1}_{s=s^{\prime}}$, and $\mu_{1}(s)$
denotes the probability for the first state to be realized as
$s\in\mathcal{S}$ following the initial distribution $\mu_{1}$. Note that for
an optimal solution $\\{q^{*}(s,a)\\}_{\forall s\in\mathcal{S},\forall
a\in\mathcal{A}}$ to (6), the corresponding optimal policy $\pi^{*}$ will be

$P(\pi^{*}(s)=a)=\left\\{\begin{aligned}
&\frac{q^{*}(s,a)}{\sum_{a^{\prime}\in\mathcal{A}}q^{*}(s,a^{\prime})},&&\text{if\leavevmode\nobreak\
}\sum_{a^{\prime}\in\mathcal{A}}q^{*}(s,a^{\prime})>0\\\
&1/|\mathcal{A}|,&&\text{if\leavevmode\nobreak\
}\sum_{a^{\prime}\in\mathcal{A}}q^{*}(s,a^{\prime})=0,\end{aligned}\right.$
(7)

where $\pi^{*}(s)$ denotes the probability for the policy $\pi^{*}$ to take
the action $a\in\mathcal{A}$ given the state $s\in\mathcal{S}$. In fact, when
$\sum_{a^{\prime}\in\mathcal{A}}q^{*}(s,a^{\prime})=0$, we can take an
arbitrary action. In what follows, we rely on the linear programming
formulation (6) to derive our results.

###  3.1 Overview of Our Approach

We illustrate our approach to solving the CMDP problems and present the formal
algorithms. Our approach is based on the linear programming reformulations
presented in (6). We now rewrite the LP (6) into the following standard
formulation to proceed with our illustration.

$\displaystyle V=$ $\displaystyle\max$
$\displaystyle\hat{\bm{r}}^{\top}\bm{q}$ (8) s.t. $\displaystyle
C\bm{q}\leq\bm{\alpha}$ $\displaystyle B\bm{q}=\bm{\mu}$
$\displaystyle\bm{q}\geq 0.$

For the infinite horizon discounted problem described in Section 2, the matrix
$B\in\mathbb{R}^{|\mathcal{S}|\times|\mathcal{S}||\mathcal{A}|}$ and the
element at $s$-th row and $(s^{\prime},a^{\prime})$th column of the matrix $B$
is $(\delta_{s,s^{\prime}}-\gamma\cdot P(s|s^{\prime},a^{\prime}))$. The
matrix $C\in\mathbb{R}^{K\times|\mathcal{S}|}$, and the element at the $k$-th
row and $(s,a)$-th column of the matrix $C$ is $\hat{c}_{k}(s,a)$. The vector
$\bm{\mu}\in\mathbb{R}^{|\mathcal{S}|}$ and the $s$-th element of $\bm{\mu}$
is $(1-\gamma)\cdot\mu_{1}(s)$, for $s\in\mathcal{S}$.

For our approach, we identify the optimal actions and then stick to the
optimal actions. With the linear programming reformulations (8), identifying
the optimal actions corresponds to finding an optimal solution of the linear
program. However, there can be multiple optimal solutions of the LP (8). We
characterize one optimal solution and we exploit its structure during the
entire horizon. We first observe the following result regarding an optimal
solution to the LP (8), which follows from standard LP theory. The proof of
Lemma 3.1 is relegated to Section 8.

###### Lemma 3.1

Denote by $b$ the number of rows in the matrix $B$. Then, there exists a
subset $\mathcal{J}\subset[K]$ with $K^{\prime}=|\mathcal{J}|$ and an optimal
solution $\bm{q}^{*}$ to LP (8) such that there are $b+K^{\prime}$ variables
in $\bm{q}^{*}$ are non-zero. Moreover, we denote by $\mathcal{I}$ the index
set of the non-zero element in $\bm{q}^{*}$. Then, the optimal solution
$\bm{q}^{*}$ can be uniquely determined as the solution to the linear system

$\displaystyle
C(\mathcal{J},\mathcal{I})\bm{q}_{\mathcal{I}}=\bm{\alpha}_{\mathcal{J}},$
(9a) $\displaystyle B(:,\mathcal{I})\bm{q}_{\mathcal{I}}=\bm{\mu},$ (9b)
$\displaystyle\bm{q}_{\mathcal{I}^{c}}=0.$ (9c)

with $\mathcal{I}^{c}$ being the complementary set of the index set
$\mathcal{I}$.

In the first part, we aim to identify the set $\mathcal{I}$ and $\mathcal{J}$.
By doing so, we also obtain the optimal actions to take given each state (and
each period), by noting the relationship between the optimal actions and the
optimal solution (occupancy measure) in (7). In the second part, we aim to
obtain the optimal solution (occupancy measure) by solving the linear
equations (9). However, since the parameters of the linear equations (9) are
unknown, we cannot directly solve (9). Instead, we need to use historical
samples to construct estimates of the parameters of (9) and gradually
approximate the optimal solution. To this end, we seek tools from the online
packing/linear programming literature (e.g. Agrawal et al. (2014), Li and Ye
(2022), Vera and Banerjee (2021), Bumpensanti and Wang (2020)), where we
interpret the right-hand side (RHS) of the linear equations (9) as resource
capacities. Note that a crucial element in deriving the logarithmic or better
problem-dependent regret in the previous literature is to let our algorithm be
adaptive to the remaining resource capacities in real time. We adopt this
adaptive resolving idea in our algorithm.

In the remaining part, we first describe how to construct estimates of unknown
parameters for the CMDP problem and we present our formal algorithms. We show
how to identify one optimal basis, and how to approximate the optimal solution
with an adaptive constraint design.

##  4 Construct Estimates in CMDP

In this section, we describe how to construct estimates for LP (8). To this
end, for a round $N_{0}$, we denote by $\mathcal{F}_{N_{0}}$ the filtration of
all the information collected up to round $N_{0}$. Then, we denote by
$\bar{C}_{N_{0}}$ (resp. $\bar{B}_{N_{0}}$) an estimate of the matrix $C$
(resp. $B$), constructed using the information in the set
$\mathcal{F}_{N_{0}}$. We also denote by $\bar{\bm{r}}_{N_{0}}$ and estimate
of $\hat{\bm{r}}$ constructed from the information in the set
$\mathcal{F}_{N_{0}}$. Then, similar to Efroni et al. (2020), we can use the
following LP to obtain an estimate of $V$ (8).

$\displaystyle\bar{V}_{N_{0}}=$ $\displaystyle\max$
$\displaystyle(\bar{\bm{r}}_{N_{0}})^{\top}\bm{q}$ (10) s.t.
$\displaystyle\bar{C}_{N_{0}}\bm{q}\leq\bm{\alpha}+\lambda_{N_{0}}$
$\displaystyle\bar{B}_{N_{0}}\bm{q}\leq\bm{\mu}+\lambda_{N_{0}}$
$\displaystyle\bar{B}_{N_{0}}\bm{q}\geq\bm{\mu}-\lambda_{N_{0}}$
$\displaystyle\bm{q}\geq 0,$

with $\lambda_{N_{0}}$ being a parameter that we specify later for both the
infinite horizon discounted problem and the finite horizon episodic problem.
To bound the estimation gap, it is useful to bound the optimal dual solution
to (8). To this end, we adopt the approach in Hiriart-Urruty and Lemaréchal
(1996), Nedić and Ozdaglar (2009) that utilizes Slater’s condition, which is
imposed as an assumption below. There exists a policy $\bar{\pi}$ such that
all the resource constraints are satisfied strictly. In other words, there
exists an occupancy measure $\bar{\bm{q}}$ such that $B\bar{\bm{q}}=\bm{\mu}$
and $C\bar{\bm{q}}<\bm{\alpha}$. In fact, for each state $s\in\mathcal{S}$,
there exists a null action that consumes no resource. The Slater point
$\bar{\bm{q}}$ can be set as the policy that takes the null action given each
state. The estimation error will be related to the gap between the Slater
point $\bar{\bm{q}}$ and the optimal point $\bm{q}^{*}$. We then define the
lower gap as

$\mathrm{Gap}_{1}(N_{0},\varepsilon)\geq V-\bar{V}_{N_{0}}$ (11)

and the upper gap as

$\mathrm{Gap}_{2}(N_{0},\varepsilon)\geq\bar{V}_{N_{0}}-V$ (12)

with both inequalities (11) and (12) hold with probability at least
$1-\varepsilon$.

###  4.1 Estimates for the Infinite Horizon Discounted Problem

We define the following empirical estimates over the LP parameters.

$\bar{r}_{N_{0}}(s,a)=\frac{\sum_{n=1}^{N_{0}}r^{n}(s,a)}{N_{0}},\bar{c}_{k,N_{0}}(s,a)=\frac{\sum_{n=1}^{N_{0}}c^{n}_{k}(s,a)}{N_{0}},\text{\leavevmode\nobreak\
and\leavevmode\nobreak\
}\bar{P}_{N_{0}}(s^{\prime}|s,a)=\frac{\sum_{n=1}^{N_{0}}\mathbbm{1}_{s^{n}(s,a)=s^{\prime}}}{N_{0}},$
(13)

where $r^{n}(s,a)$ denotes the $n$-th observation of the reward, and
$c^{n}_{k}(s,a)$ denotes the $n$-th observation of the $k$-th cost, and
$s^{n}(s,a)$ denotes the $n$-th observation of the state transition for the
state-action pair $(s,a)$, for $n\in[N_{0}]$. We denote by

$\mathrm{Rad}(N_{0},\varepsilon)=\sqrt{\frac{\log(2/\varepsilon)}{2N_{0}}}.$

Following the standard Hoeffding’s inequality, we know that
$|\bar{r}_{N_{0}}(s,a)-\hat{r}(s,a)|$,
$|\bar{c}_{k,N_{0}}(s,a)-\hat{c}_{k}(s,a)|$, and
$|\bar{P}_{N_{0}}(s^{\prime}|s,a)-P(s^{\prime}|s,a)|$ are all upper bounded by
$\mathrm{Rad}(N_{0},\varepsilon)$ with probability at least $1-\varepsilon$.
Then, we use the following LP with empirical estimates to approximate the
value of $V^{\mathrm{Infi}}$, as given in (10). Here,
$\bar{C}_{N_{0}}\in\mathbb{R}^{K\times|\mathcal{S}|}$, and the element at the
$k$-th row and $(s,a)$-th column of the matrix $\bar{C}_{N_{0}}$ is
$\bar{c}_{k,N_{0}}(s,a)$.
$\bar{B}_{N_{0}}\in\mathbb{R}^{|\mathcal{S}|\times|\mathcal{S}||\mathcal{A}|}$,
and the element at $s$-th row and $(s^{\prime},a^{\prime})$-th column of the
matrix $\bar{B}_{N_{0}}$ is
$(\delta_{s,s^{\prime}}-\gamma\cdot\bar{P}_{N_{0}}(s|s^{\prime},a^{\prime}))$.
$\bar{\bm{r}}_{N_{0}}\in\mathbb{R}^{|\mathcal{S}||\mathcal{A}|}$ with the
$(s,a)$-th element being $\bar{r}_{N_{0}}(s,a)$. We have the following result,
where the proof is relegated to Section 9.

###### Lemma 4.1

As long as $\lambda_{N_{0}}=\mathrm{Rad}(N_{0},\varepsilon)$, the following
inequality

$\displaystyle V\leq\bar{V}_{N_{0}}+\mathrm{Rad}(N_{0},\varepsilon)\leq
V+\mathrm{Rad}(N_{0},\varepsilon)+\frac{2\mathrm{Rad}(N_{0},\varepsilon)}{\min_{k\in[K]}\\{\alpha_{k}\\}}\cdot\left(1+\frac{|\mathcal{S}|}{1-\gamma}\right)+\frac{\mathrm{Rad}^{2}(N_{0},\varepsilon)}{\min_{k\in[K]}\\{\alpha_{k}\\}}\cdot\left(|\mathcal{S}|+\frac{|\mathcal{S}|^{2}}{1-\gamma}\right).$
(14)

holds with probability at least
$1-(K|\mathcal{S}||\mathcal{A}|-|\mathcal{S}|^{2}|\mathcal{A}|)\cdot\varepsilon$.

Therefore, we can simply set

$\mathrm{Gap}_{1}(N_{0},\varepsilon)=\mathrm{Rad}(N_{0},\varepsilon)$ (15)

and

$\mathrm{Gap}_{2}(N_{0},\varepsilon)=\frac{2\mathrm{Rad}(N_{0},\varepsilon)}{\min_{k\in[K]}\\{\alpha_{k}\\}}\cdot\left(1+\frac{|\mathcal{S}|}{1-\gamma}\right)+\frac{\mathrm{Rad}^{2}(N_{0},\varepsilon)}{\min_{k\in[K]}\\{\alpha_{k}\\}}\cdot\left(|\mathcal{S}|+\frac{|\mathcal{S}|^{2}}{1-\gamma}\right).$
(16)

##  5 Algorithm Design

In this section, we present our algorithms for solving the CMDP problem. We
first show how to identify one optimal basis of LP (8) and then present the
formal algorithm to achieve a logarithmic level regret bound.

###  5.1 Characterize One Optimal Basis

We now describe how to identify one optimal basis of the LP (8), by
sequentially discarding the sub-optimal actions and the redundant constraints.
We will use the estimates constructed in the previous Section 4 to carry out
the discarding procedure. The formal algorithm to identify such non-zero
elements and the constraints is given in Algorithm 1.

Algorithm 1 Algorithm for identifying one optimal basis

1:Input: the historical sample set $\mathcal{F}_{N_{0}}$ that contains $N_{0}$
samples for each $(s,a)\in\mathcal{S}\times\mathcal{A}$.

2:Compute the value of $\bar{V}_{N_{0}}$ as in (10).

3:Initialize $\mathcal{I}$ to be the whole index set that contains every row
index of matrix $B$ in (8) and $\mathcal{J}=[K]$.

4:for $i\in\mathcal{I}$ do

5: Let $\mathcal{I}^{\prime}=\mathcal{I}\backslash\\{i\\}$.

6: Compute the value of $\bar{V}_{\mathcal{I}^{\prime},N_{0}}$ as in (17).

7: If $|\bar{V}_{\mathcal{I}^{\prime},N_{0}}-\bar{V}_{N_{0}}|\leq
2\mathrm{Gap}_{1}(N_{0},\varepsilon)+2\mathrm{Gap}_{2}(N_{0},\varepsilon)$,
then we set $\mathcal{I}=\mathcal{I}^{\prime}$.

8:end for

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

10: Let $\mathcal{J}^{\prime}=\mathcal{J}\backslash\\{q\\}$.

11: Compute the value of
$\text{Dual}_{\mathcal{J}^{\prime},\mathcal{I},N_{0}}$ as in (20).

12: If
$|\bar{V}_{N_{0}}-\text{Dual}_{\mathcal{J}^{\prime},\mathcal{I},N_{0}}|\leq
2\mathrm{Gap}_{1}(N_{0},\varepsilon)+2\mathrm{Gap}_{2}(N_{0},\varepsilon)$,
then we set $\mathcal{J}=\mathcal{J}^{\prime}$.

13:end for

14:Output: the set of indexes $\mathcal{I}$ and $\mathcal{J}$.

We now explain the intuition why Algorithm 1 works. Denote by $\bm{q}^{*}$ an
optimal solution to LP (8). We describe how to identify the non-zero elements
in $\bm{q}^{*}$ and how to identify the constraints such that the values of
the non-zero elements of $\bm{q}^{*}$ can be uniquely determined by the
corresponding linear equation. For each $i$-th element of $\bm{q}^{*}$, we
compare the value of $V$ (8) against $V$ with an additional constraint that
$q_{i}=0$. If the two values are different, we identify a non-zero element. To
this end, for an index set $\mathcal{I}$, we define an LP, as well as its
estimate, as follows.

$\displaystyle V_{\mathcal{I}}=$ $\displaystyle\max$
$\displaystyle\hat{\bm{r}}^{\top}\bm{q}$
$\displaystyle\bar{V}_{\mathcal{I},N_{0}}=$ $\displaystyle\max$
$\displaystyle(\bar{\bm{r}}_{N_{0}})^{\top}\bm{q}$ (17) s.t. $\displaystyle
C\bm{q}\leq\bm{\alpha}$ s.t.
$\displaystyle\bar{C}_{N_{0}}\bm{q}\leq\bm{\alpha}+\lambda_{N_{0}}$
$\displaystyle B\bm{q}=\bm{\mu}$
$\displaystyle|\bar{B}_{N_{0}}\bm{q}-\bm{\mu}|\leq\lambda_{N_{0}}$
$\displaystyle\bm{q}_{\mathcal{I}^{c}}=0$
$\displaystyle\bm{q}_{\mathcal{I}^{c}}=0$ $\displaystyle\bm{q}\geq 0,$
$\displaystyle\bm{q}\geq 0.$

where $\mathcal{I}^{c}$ denotes the complementary set of $\mathcal{I}$. Note
that if $V-V_{\mathcal{I}}>0$, we know that $\mathcal{I}^{c}$ contains a non-
zero basic variable. The steps 4-8 in Algorithm 1 reflect this point. Starting
from $\mathcal{I}$ denoting the whole index set, we sequentially delete one
element $i$ (denoting $(s,a)$ in the infinite horizon discounted problem and
$(s,a,h)$ in the finite horizon episodic problem) from the set $\mathcal{I}$.
Once we detected that $V-V_{\mathcal{I}\backslash\\{i\\}}>0$, we know that $i$
is a non-zero basic variable and we add $i$ back into the set $\mathcal{I}$.
In this way, we can classify all the basic variables into the set
$\mathcal{I}$. However, since we do not know the exact value of $V$ and
$V_{\mathcal{I}}$, we use the estimates and compare the value of
$\bar{V}_{N_{0}}$ and $\bar{V}_{\mathcal{I},N_{0}}$. For this comparison to be
valid, the estimation error has to be smaller than the intrinsic gap between
$V$ and $V_{\mathcal{I}}$. We define a constant

$\delta_{1}=\min_{\mathcal{I}}\\{V-V_{\mathcal{I}}:V-V_{\mathcal{I}}>0\\}$
(18)

and we need $N_{0}$ to be large enough such that the estimation gap is smaller
than $\delta_{1}/2$. The quantity $\delta_{1}$ plays a similar role as the gap
between the optimal arm and the sub-optimal arm in the multi-arm-bandit
problem when deriving a problem-dependent bound (e.g. Lai and Robbins (1985)).

Denote by $M$ the number of non-zero basic variables detected in Algorithm 1.
We then denote by $M^{\prime}$ the number of binding constraints corresponding
to the optimal solution given by the optimal basis we detected. Our goal is to
identify the linearly independent binding constraints such that the non-zero
basic variables can be uniquely determined as the solution to a linear
equation, as described in Lemma 3.1.

To tell which constraints are redundant and thus can be deleted, we consider
the dual program of $V_{\mathcal{I}}$, where $\mathcal{I}$ is determined in
steps 4-8 in Algorithm 1, and similarly, we test which dual variable can be
set to $0$ without influencing the dual objective value. For a dual variable
index subset $\mathcal{J}\subset[K]$, we consider the dual program as follows.

$\displaystyle\text{Dual}_{\mathcal{J},\mathcal{I}}=\min\leavevmode\nobreak\
\leavevmode\nobreak\ $
$\displaystyle\bm{\alpha}^{\top}\bm{y}+\bm{\mu}^{\top}\bm{z}$ (19a) s.t.
$\displaystyle(C(:,\mathcal{I}))^{\top}\bm{y}+(B(:,\mathcal{I}))^{\top}\bm{z}\geq\hat{\bm{r}}_{\mathcal{I}}$
(19b) $\displaystyle\bm{y}_{\mathcal{J}^{c}}=0$ (19c) $\displaystyle\bm{y}\geq
0,\bm{z}\geq-\infty,$ (19d)

where $\mathcal{J}^{c}=[K]\backslash\mathcal{J}$. The estimate of
$\text{Dual}_{\mathcal{J},\mathcal{I}}$, can be obtained from the estimate of
its dual, which is given below.

$\displaystyle\text{Dual}_{\mathcal{J},\mathcal{I},N_{0}}=\bar{V}_{\mathcal{J},\mathcal{I},N_{0}}=\max\leavevmode\nobreak\
\leavevmode\nobreak\ $ $\displaystyle(\bar{\bm{r}}_{N_{0}})^{\top}\bm{q}$
(20a) s.t.
$\displaystyle\bar{C}_{N_{0}}(\mathcal{J},:)\bm{q}\leq\bm{\alpha}+\lambda_{N_{0}}$
(20b) $\displaystyle|\bar{B}_{N_{0}}\bm{q}-\bm{\mu}|\leq\lambda_{N_{0}}$ (20c)
$\displaystyle\bm{q}_{\mathcal{I}}=0$ (20d) $\displaystyle\bm{q}\geq 0,$ (20e)

Similarly, we compare the value of $\text{Dual}_{\mathcal{I}}$, where
$\text{Dual}_{\mathcal{I}}=\text{Dual}_{\mathcal{J}^{\prime},\mathcal{I}}$
with $\mathcal{J}^{\prime}=[K]$, and $\text{Dual}_{\mathcal{J},\mathcal{I}}$.
However, we can only compare the value of their estimates
$\text{Dual}_{\mathcal{I},N_{0}}$ and
$\text{Dual}_{\mathcal{J},\mathcal{I},N_{0}}$. To this end, we define a
constant

$\delta_{2}=\min_{\mathcal{J}\subset[K]}\\{\text{Dual}_{\mathcal{J},\mathcal{I}}-\text{Dual}_{\mathcal{I}}:\text{Dual}_{\mathcal{J},\mathcal{I}}-\text{Dual}_{\mathcal{I}}>0\\}.$
(21)

For the comparison to be valid, we need $N_{0}$ to be large enough such that
the estimation error is smaller than $\delta_{2}/2$. In this way, we identify
the linearly independent binding constraints corresponding to $\bm{q}^{*}$, as
described in steps 9-13 of Algorithm 1.

###  5.2 Our Formal Algorithm

We now describe our formal algorithm. From the output of Algorithm 1, we
characterize one optimal solution. If the sample size $n$ is used in Algorithm
1, we denote by $\mathcal{I}_{n}$ and $\mathcal{J}_{n}$ the output of
Algorithm 1. To be specific, we have $\bm{q}^{*}_{\mathcal{I}_{n}^{c}}=0$ and
the non-zero elements $\bm{q}^{*}_{\mathcal{I}_{n}}$ can be given as the
solution to

$\left[\begin{aligned} &C(\mathcal{J}_{n},\mathcal{I}_{n})\\\
&B(:,\mathcal{I}_{n})\end{aligned}\right]\cdot\bm{q}^{*}_{\mathcal{I}_{n}}=\left[\begin{aligned}
&\bm{\alpha}_{\mathcal{J}_{n}}\\\
&(1-\gamma)\cdot\bm{\mu}\end{aligned}\right].$ (22)

However, in practice, both the matrices $C(\mathcal{J}_{n},\mathcal{I}_{n})$
and $B(:,\mathcal{I}_{n})$ are unknown. We aim to use the samples to learn the
matrices $C(\mathcal{J}_{n},\mathcal{I}_{n})$ and $B(:,\mathcal{I}_{n})$ such
that the $\bm{q}^{*}_{\mathcal{I}_{n}}$ can also be determined. Our formal
algorithm is given in Algorithm 2. The steps 3-8 in Algorithm 2 is to use
Algorithm 1 as a subroutine to identify the set $\mathcal{I}$ and
$\mathcal{J}$ that satisfy the conditions in Lemma 3.1. We can show that as
long as $n\geq N_{0}^{\prime}$, where $N_{0}^{\prime}$ is a threshold that
depends on the problem parameters, Algorithm 1 correctly obtains the set
$\mathcal{I}$ and $\mathcal{J}$ satisfying the conditions in Lemma 3.1.
Therefore, we exponentially increase the value of $n$ as input to Algorithm 1
to reach $N_{0}^{\prime}$.

Algorithm 2 The Adaptive-resolving Algorithm

1:Input: the number of samples $N$ for each
$(s,a)\in\mathcal{S}\times\mathcal{A}$.

2:Initialize $\mathcal{F}_{1}=\emptyset$, $\bm{\alpha}^{1}=N\cdot\bm{\alpha}$
and $\bm{\mu}^{1}=N\cdot\bm{\mu}$.

3:for $n=1,\dots,N$ do

4: if $n=2^{m}$ for an integer $m$ then

5: Obtain the output $\mathcal{I}_{n}$ and $\mathcal{J}_{n}$ from Algorithm 1
with the input $\mathcal{F}_{n}$.

6: else

7: set $\mathcal{I}_{n}=\mathcal{I}_{n-1}$ and
$\mathcal{J}_{n}=\mathcal{J}_{n-1}$.

8: end if

9: Construct estimates $\bar{C}^{n}(\mathcal{J}_{n},\mathcal{I}_{n})$ and
$\bar{B}^{n}(:,\mathcal{I}_{n})$ using the sample set $\mathcal{F}_{n}$.

10: Construct a solution $\tilde{\bm{q}}^{n}$ such that
$\tilde{\bm{q}}^{n}_{\mathcal{I}_{n}^{c}}=0$ and
$\tilde{\bm{q}}^{*}_{\mathcal{I}_{n}}$ is the solution to
$\left[\begin{aligned} &\bar{C}^{n}(\mathcal{J}_{n},\mathcal{I}_{n})\\\
&\bar{B}^{n}(:,\mathcal{I}_{n})\end{aligned}\right]\cdot\tilde{\bm{q}}^{n}_{\mathcal{I}_{n}}=\left[\begin{aligned}
&\frac{\bm{\alpha}^{n}_{\mathcal{J}_{n}}}{N-n+1}\\\
&\frac{\bm{\mu}^{n}}{N-n+1}\end{aligned}\right].$ (23)

11: Project $\tilde{\bm{q}}^{n}$ to the set $\\{\bm{q}:\|\bm{q}\|_{1}\leq
2\\}$ to obtain $\bm{q}^{n}$.

12: For each $(s,a)\in\mathcal{I}_{n}\subset\mathcal{S}\times\mathcal{A}$, we
query the model $\mathcal{M}$ to obtain a sample of the reward $r^{n}(s,a)$
and the costs $c^{n}_{k}(s,a)$ for each $k\in\mathcal{J}_{n}\subset[K]$, as
well as the state transition $s^{n}(s,a)$.

13: Update
$\mathcal{F}_{n+1}=\mathcal{F}_{n}\cup\left\\{r^{n}(s,a),c^{n}_{k}(s,a),s^{n}(s,a),\forall(s,a)\in\mathcal{S}\times\mathcal{A},\forall
k\in[K]\right\\}$.

14: Denote by $\bm{c}^{n}(s,a)=(c^{n}_{k}(s,a))_{\forall k\in\mathcal{J}_{n}}$
and do the update:
$\bm{\alpha}^{n+1}_{\mathcal{J}_{n}}=\bm{\alpha}^{n}_{\mathcal{J}_{n}}-\sum_{(s,a)\in\mathcal{I}_{n}}\bm{c}^{n}(s,a)\cdot
q^{n}(s,a).$ (24)

15: Do the update:
$\bm{\mu}^{n+1}(s^{\prime})=\bm{\mu}^{n}(s^{\prime})-\sum_{(s,a)\in\mathcal{I}}q^{n}(s,a)\cdot(\delta_{s^{\prime},s}-\gamma\mathbbm{1}_{\\{s^{\prime}=s^{n}(s,a)\\}}),\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \forall s^{\prime}\in\mathcal{S}.$
(25) where $\mathbbm{1}_{\\{s^{\prime}=s^{n}(s,a)\\}}$ is an indicator
function of whether the state transition $s^{n}(s,a)$ equals $s^{\prime}$.

16:end for

17:Output: $\bm{q}^{1},\dots,\bm{q}^{N}$.

A crucial element in Algorithm 2 (step 10) is that we adaptively update the
value of $\bm{\alpha}^{n}_{\mathcal{J}_{n-1}}$ and $\bm{\mu}^{n}(s^{\prime})$
as in (24) and (25). We then use the updated
$\bm{\alpha}^{n}_{\mathcal{J}_{n-1}}$ and $\bm{\mu}^{n}(s^{\prime})$ to obtain
the value of $\tilde{\bm{q}}^{n}_{\mathcal{I}_{n}}$ as in (23). Such an
algorithmic design has the following natural interpretation and is the key for
us to achieve a logarithmic-level regret. Note that if we adopt a static way
to compute $\bm{q}^{n}$, for example, we simply solve (22) with the matrices
$C(\mathcal{J}_{n},\mathcal{I}_{n})$ and $B(:,\mathcal{I}_{n})$ replaced by
their estimates, then the gap between $\bm{q}^{n}$ and $\bm{q}^{*}$ will be at
the same order of the estimation error of $C(\mathcal{J}_{n},\mathcal{I}_{n})$
and $B(:,\mathcal{I}_{n})$, which is $O(1/\sqrt{n})$. Thus, the gap between
$\frac{\sum_{n=1}^{N}\bm{q}^{n}}{N}$ and $\bm{q}^{*}$ will be at the order of
$O(1/\sqrt{N})$, which translates into $O(\sqrt{N})$ regret bound. Instead, we
use $\bm{\alpha}^{n}_{\mathcal{J}_{n-1}}$ and $\bm{\mu}^{n}(s^{\prime})$ that
are adaptive to the historical information. To be specific, if for one
$n\in[N]$ and one binding constraint $k\in\mathcal{J}$, the constraint value
under the action $\sum_{n^{\prime}=1}^{n}\bm{q}^{n^{\prime}}/n$ is below the
target $\alpha_{k}$, we know that $\alpha^{n}_{k}/(N-n+1)$ is greater than
$\alpha_{k}$, which results in a greater constraint value for
$\tilde{\bm{q}}^{n+1}$ (it is in fact $\alpha^{n}_{k}/(N-n+1)$ beyond the
target $\alpha_{k}$). In this way, any gap between the real-time constraint
value and the target will be self-corrected in the next period as we
adaptively obtain $\tilde{\bm{q}}^{n+1}$. Therefore, such an adaptive design
can re-adjust the possible constraint violation by itself, which results in a
regret bound of a lower order. In step 11, we further project
$\tilde{\bm{q}}^{n+1}$ to the set $\\{\bm{q}\geq 0:\|\bm{q}\|_{1}\leq 2\\}$ to
obtain $\bm{q}^{n+1}$. This prevents $\tilde{\bm{q}}^{n}$ from behaving ill
when $n$ is not large and the estimates of
$C(\mathcal{J}_{n},\mathcal{I}_{n})$ and $B(:,\mathcal{I}_{n})$ are not
accurate enough. We can show that when $n$ is large enough,
$\tilde{\bm{q}}^{n+1}$ automatically belongs to the set $\\{\bm{q}\geq
0:\|\bm{q}\|_{1}\leq 2\\}$.

Remark. Note that the adaptive resolving step (23) is akin to the idea of
resolving an LP in online LP, Bandits with Knapsacks, online allocation
problems, where logarithmic or better regret is obtained in a series of work
Flajolet and Jaillet (2015), Arlotto and Gurvich (2019), Li and Ye (2022), Li
et al. (2021b), Vera and Banerjee (2021), Vera et al. (2021), Bumpensanti and
Wang (2020), Jiang et al. (2022). However, since we have identified the
optimal basis $\mathcal{I}$ and $\mathcal{J}$ and we stick to this optimal
basis to avoid the non-degeneracy assumption, resolving the LP would become
resolving the linear equations in (23).

##  6 Theoretical Analysis

In this section, we conduct our theoretical analysis. The analysis can be
divided into two parts. In the first part, we show that Algorithm 1 can
successfully help us identify one optimal basis to work with. In the second
part, we show how to learn the optimal distribution over the optimal basis we
have identified.

###  6.1 High Probability Bound for Identifying One Optimal Basis

We now present the theorem showing that Algorithm 1 indeed helps us identify
one optimal basis with a high probability. In practice, the value of
$\varepsilon$ will be set to $1/N$ in the following theorem.

###### Theorem 6.1

For any $\varepsilon>0$, as long as $N_{0}$ satisfies the condition

$2\mathrm{Gap}_{1}(N_{0},\varepsilon)+2\mathrm{Gap}_{2}(N_{0},\varepsilon)\leq\min\\{\delta_{1},\delta_{2}\\}$
(26)

the outputs $\mathcal{I}_{N_{0}}$ and $\mathcal{J}_{N_{0}}$ of Algorithm 1
satisfy the conditions described in Lemma 3.1 with probability at least
$1-(K|\mathcal{S}||\mathcal{A}|-|\mathcal{S}|^{2}|\mathcal{A}|)\cdot\varepsilon$.
Moreover, the sets $\mathcal{I}_{n}$ and $\mathcal{J}_{n}$ will be common for
any $n\geq N_{0}$ satisfying (26), which we denote by $\mathcal{I}^{*}$ and
$\mathcal{J}^{*}$.

The formal proof of Theorem 6.1 is relegated to Section 10. Note that there
can be multiple optimal bases to the LP (8), and our approach essentially
identifies one particular optimal basis. To see this point, we sort all the
elements of the solution $\bm{q}$, and in Algorithm 1, we try to delete each
element $i$ from the set $\mathcal{I}$ from the first one to the last one in
this order. For a collection of non-zero basic variables denoted as
$(i_{1},\dots,i_{M})$, our approaches identifies the collection with $i_{1}$
being the largest among all collections. Then, among all collections with
$i_{1}$ being the first element, our approach identifies the collection with
$i_{2}$ being the largest, so on and so forth. Our Algorithm 1 identifies such
a collection of non-zero basic variables. Similarly, for the redundant
constraints, our approach deletes these constraints from the smallest index in
the set $[K]$. Therefore, as long as $n$ (which is $2^{m}$ for an integer $m$)
is large enough, our Algorithm 1 outputs the same index sets $\mathcal{I}$ and
$\mathcal{J}$ that satisfies the conditions in Lemma 3.1, which we denote by
$\mathcal{I}^{*}$ and $\mathcal{J}^{*}$ from now on.

An important problem parameter related to $\mathcal{I}^{*}$ and
$\mathcal{J}^{*}$ can be described as follows. Define

$A^{*}=\left[\begin{aligned} &C(\mathcal{J}^{*},\mathcal{I}^{*})\\\
&B(:,\mathcal{I}^{*})\end{aligned}\right].$ (27)

We then denote by
$\\{\sigma_{1}(A^{*}),\dots,\sigma_{|\mathcal{S}|+K^{\prime}}(A^{*})\\}$ the
eigenvalues of the matrix $A^{*}$. We define $\sigma$ as

$\sigma=\min\left\\{|\sigma_{1}(A^{*})|,\dots,|\sigma_{|\mathcal{S}|+K^{\prime}}(A^{*})|\right\\}.$
(28)

From the non-singularity of the matrix $A$, we know that $\sigma>0$.

Remark. It is clear to see that $\sigma$ in (28) relates to the conditional
number of the matrix $A^{*}$. In fact, it holds that
$\kappa(A^{*})\leq\frac{|\mathcal{S}|+K}{\sigma}$, where $\kappa(A^{*})$
denotes the conditional number of the matrix $A^{*}$. The value of $\sigma$
will show up in our final bounds as it characterizes how hard it is to learn
the matrix $A^{*}$. Also, $\sigma$ gives a natural upper bound of the range of
the optimal dual variable corresponding to the optimal basis $\mathcal{I}^{*}$
and $\mathcal{J}^{*}$. Note that in previous literature that establishes
logarithmic regret for online LP/resource allocation (e.g. Vera and Banerjee
(2021), Li et al. (2021b), Jiang et al. (2022)), the conditional number of the
constraint matrix will also show up in the final bounds. Therefore, we regard
the existence of $\sigma$ as the consequence of adopting the online
LP/resource allocation framework. On the other hand, for the MDP problem
without resource constraints, the matrix $A^{*}$ can simply be represented as
the probability transition matrix and one can easily show that $\sigma\geq
1-\gamma$. We will use this bound when deriving our guarantees for MDP
problems without resource constraints.

###  6.2 Regret Bounds

We now show that Algorithm 2 achieves a logarithmic regret, as defined in (3).
The next lemma shows that to analyze the regret, it suffices to consider the
remaining constraint capacities belonging to the binding constraints. The
formal proof is relegated to Section 11.

###### Lemma 6.2

For the optimal basis identified in Algorithm 1 and the corresponding optimal
solution $\bm{q}^{*}$, we denote by $\mathcal{I}^{*}$ and $\mathcal{J}^{*}$
the output sets as long as $N_{0}$ satisfies the condition (26). We also
denote by $(\bm{y}^{*},\bm{c}^{*})$ the corresponding optimal dual solution.
Then, it holds that

$N\cdot
V_{r}(\pi^{*},\mu_{1})-\sum_{n=1}^{N}\hat{\bm{r}}^{\top}\mathbb{E}[\bm{q}^{n}]\leq\sum_{j\in\mathcal{J}^{*}}y^{*}_{j}\cdot\mathbb{E}[\alpha^{N}_{j}]+\sum_{s\in\mathcal{S}}z^{*}_{s}\cdot\mathbb{E}[\mu^{N}_{s}].$
(29)

Therefore, it suffices to analyze how the “remaining resources”
$(\bm{\alpha}_{\mathcal{J}^{*}}^{n},\bm{\mu}^{n})$ behave. We now define

$\tilde{\alpha}_{k}(n)=\frac{\alpha^{n}_{k}}{N-n},\leavevmode\nobreak\ \forall
k\in\mathcal{J}^{*}\text{\leavevmode\nobreak\ and\leavevmode\nobreak\
}\tilde{\mu}_{s}(n)=\frac{\mu^{n}_{s}}{N-n},\leavevmode\nobreak\ \forall
s\in\mathcal{S},\forall n\in[N].$ (30)

The key is to show that the stochastic process $\tilde{\alpha}_{k}(n)$ and
$\tilde{\mu}_{s}$ possess some concentration properties such that they will
stay within a small neighborhood of their initial value $\alpha^{1}_{k}$ and
$\mu^{1}_{s}$ for a sufficiently long time. We denote by $\tau$ the time that
one of $\tilde{\alpha}_{k}(n)$ for each $k\in\mathcal{J}^{*}$ and
$\tilde{\mu}_{s}$ for each $s\in\mathcal{S}$ escape this neighborhood. Then,
both $\text{Regret}_{r}(\pi,N)$ and $\text{Regret}_{k}(\pi,N)$ for each
$k\in[K]$ can be upper bounded by $\mathbb{E}[N-\tau]$. From the update rule
(24) and (25), we know that

$\tilde{\alpha}_{k}(n+1)=\tilde{\alpha}_{k}(n)-\frac{\sum_{(s,a)\in\mathcal{I}^{*}}\bm{c}^{n}(s,a)\cdot
q^{n}(s,a)-\tilde{\alpha}_{k}(n)}{N-n-1},\leavevmode\nobreak\ \forall
k\in\mathcal{J}^{*}$ (31)

and

$\tilde{\mu}_{s}(n+1)=\tilde{\mu}_{s}(n)-\frac{\sum_{(s,a)\in\mathcal{I}^{*}}q^{n}(s,a)\cdot(\delta_{s^{\prime},s}-\gamma\mathbbm{1}_{\\{s^{\prime}=s^{n}(s,a)\\}})-\tilde{\mu}_{s}(n)}{N-n-1}.$
(32)

Ideally, both $\tilde{\alpha}_{k}(n+1)$ and $\tilde{\mu}_{s}(n+1)$ will have
the same expectation as $\tilde{\alpha}_{k}(n)$ and $\tilde{\mu}_{s}(n)$ such
that they become a martingale. However, this is not true since we have
estimation error over $C(\mathcal{J}^{*},\mathcal{I}^{*})$ and
$B(:,\mathcal{I}^{*})$, and we only use their estimates to compute
$\bm{q}^{n}$. Nevertheless, we can show that $\tilde{\alpha}_{k}(n)$ for each
$k\in\mathcal{J}^{*}$ and $\tilde{\mu}_{s}$ for each $s\in\mathcal{S}$ behave
as a sub-martingale. Then, from the concentration property of the sub-
martingale, we upper bound $\mathbb{E}[\alpha^{N}_{k}]$ for each
$k\in\mathcal{J}^{*}$ and $\mathbb{E}[\mu^{N}_{s}]$ for each
$s\in\mathcal{S}$. The term $|\mathbb{E}[\alpha^{N}_{k}]|$ for each
$k\in[K]\backslash\mathcal{J}^{*}$ can be upper bounded as well. The results
are presented in the following theorem. The formal proof is relegated to
Section 12 and we provide a brief sketch of the proof for illustration.

###### Theorem 6.3

Denote by $\bar{\pi}^{N}$ the output policy of Algorithm 2 and denote by $N$
the number of rounds. Then, it holds that

$N\cdot
V_{r}(\pi^{*},\mu_{1})-\sum_{n=1}^{N}\hat{\bm{r}}^{\top}\mathbb{E}[\bm{q}^{n}]\leq
O\left(\frac{(|\mathcal{S}|+K)^{3}}{\alpha\cdot\sigma\cdot\min\\{\sigma^{2},(1-\gamma)^{2}\cdot\delta^{2}\\}}\cdot\frac{\log(N)}{N}\right)$

where the parameters $\alpha=\min_{k\in[K]}\\{\alpha_{k}\\}$,
$\delta=\min\\{\delta_{1},\delta_{2}\\}$ with $\delta_{1}$ given in (18) and
$\delta_{2}$ given in (21), $\sigma$ given in (28). Also, for any $k\in[K]$,
we have

$N\cdot\alpha_{k}-\sum_{n=1}^{N}\hat{\bm{c}}_{k}^{\top}\mathbb{E}\left[\bm{q}^{n}\right]\leq
O\left(\frac{(|\mathcal{S}|+K)^{3}}{\alpha\cdot\sigma\cdot\min\\{\sigma^{2},(1-\gamma)^{2}\cdot\delta^{2}\\}}\cdot\frac{\log(N)}{N}\right).$
(33)

#### Sketch of proof.

We first note that following Theorem 6.1, as long as $n\geq N_{0}$ (or
$2N_{0}$ when $N_{0}$ cannot be expressed as the exponent of $2$), we
correctly identify the basis $\mathcal{I}^{*}$ and $\mathcal{J}^{*}$ (with a
high probability at least $1-O(1/T)$). Then, the resolving step (23) simply
becomes

$\left[\begin{aligned} &\bar{C}^{n}(\mathcal{J}^{*},\mathcal{I}^{*})\\\
&\bar{B}^{n}(:,\mathcal{I}^{*})\end{aligned}\right]\cdot\tilde{\bm{q}}^{n}_{\mathcal{I}^{*}}=\left[\begin{aligned}
&\frac{\bm{\alpha}^{n}_{\mathcal{J}^{*}}}{N-n+1}\\\
&\frac{\bm{\mu}^{n}}{N-n+1}\end{aligned}\right].$ (34)

Our remaining proof can be classified into the following two steps.

  * 1.

For a fixed $\nu>0$, we define a set

$\mathcal{X}=\\{\bm{\alpha}^{\prime}\in\mathbb{R}^{|\mathcal{J}^{*}|}:\alpha^{\prime}_{k}\in[\alpha_{k}-\nu,\alpha_{k}+\nu],\forall
k\in\mathcal{J}^{*}\\},$ (35)

and

$\mathcal{Y}=\\{\bm{\mu}^{\prime}\in\mathbb{R}^{|\mathcal{S}|}:\mu^{\prime}_{s}\in[\mu_{s}-\nu,\mu_{s}+\nu],\forall
s\in\mathcal{S}\\}.$ (36)

We can show that $\tilde{\bm{\alpha}}(n)$ and $\tilde{\bm{\mu}}(n)$ behave
well as long as they stay in the region $\mathcal{X}$ and $\mathcal{Y}$. To be
specific, it automatically satisfies that
$\|\tilde{\bm{q}}^{n}_{\mathcal{I}^{*}}\|_{1}\leq 2$ and thus
$\bm{q}^{n}_{\mathcal{I}^{*}}$ can be expressed as the solution to the linear
equations (34).

We can also show that $\tilde{\bm{\alpha}}(n)$ and $\tilde{\bm{\mu}}(n)$ stay
in the region $\mathcal{X}$ and $\mathcal{Y}$ for a sufficiently long time. To
this end, we define a stopping time

$\tau=\min_{n\in[N]}\\{\tilde{\bm{\alpha}}(n)\notin\mathcal{X}\text{\leavevmode\nobreak\
or\leavevmode\nobreak\ }\tilde{\bm{\mu}}(n)\notin\mathcal{Y}\\}.$ (37)

and we derive an upper bound of $\mathbb{E}[N-\tau]$, which scales as
$O(\log(N))$.

  * 2.

By using our upper bound of $\mathbb{E}[N-\tau]$ and combining with Lemma 6.2,
we show that the gap over the reward $N\cdot
V_{r}(\pi^{*},\mu_{1})-\sum_{n=1}^{N}\hat{\bm{r}}^{\top}\mathbb{E}[\bm{q}^{n}]$
and the gap over the constraint
$N\cdot\alpha_{k}-\sum_{n=1}^{N}\hat{\bm{c}}_{k}^{\top}\bm{q}^{n}$ for
$k\in\mathcal{J}^{*c}$ can all be upper bounded at the order of $O(\log(N))$.
By further exploiting the structure of the matrix $A^{*}$, we can show that
the gap over the constraint
$N\cdot\alpha_{k}-\sum_{n=1}^{N}\hat{\bm{c}}_{k}^{\top}\bm{q}^{n}$ for
$k\in\mathcal{J}^{*}$ can be bounded at the order of $O(\log(N))$ as well.

$\Halmos$

###  6.3 Sample Complexity Bounds

Denote by $\bm{q}^{1},\dots,\bm{q}^{N}$ the output of Algorithm 2. Then, We
define $\bar{\bm{q}}^{N}$ such that $\bar{\bm{q}}^{N}_{\mathcal{I}^{*c}}=0$
and

$\bar{\bm{q}}^{N}_{\mathcal{I}^{*}}=\frac{1}{N}\cdot\sum_{n=1}^{N}\bm{q}^{n}_{\mathcal{I}_{N}}.$

Here, $\mathcal{I}^{*}$ can be replaced by $\mathcal{I}_{N}$, the output of
Algorithm 1 with the input sample size $N$. From Theorem 6.1, as long as
$N\geq N_{0}$ where $N_{0}$ satisfies the condition (26), we know that
$\mathcal{I}_{N}=\mathcal{I}^{*}$ with a high probability. We can construct a
policy $\bar{\pi}^{N}$ as follows. For each
$(s,a)\in\mathcal{S}\times\mathcal{A}$, it holds

$P(\bar{\pi}^{N}(s)=a)=\left\\{\begin{aligned}
&\frac{\bar{q}^{N}(s,a)}{\sum_{a^{\prime}\in\mathcal{A}}\bar{q}^{N}(s,a^{\prime})},&&\text{if\leavevmode\nobreak\
}\sum_{a^{\prime}\in\mathcal{A}}\bar{q}^{N}(s,a^{\prime})>0\\\
&1/|\mathcal{A}|,&&\text{if\leavevmode\nobreak\
}\sum_{a^{\prime}\in\mathcal{A}}\bar{q}^{N}(s,a^{\prime})=0.\end{aligned}\right.$
(38)

We aim to bound the gap between $V_{r}(\pi^{*},\mu_{1})$ and
$V_{r}(\bar{\pi}^{N},\mu_{1})$, as well as $V_{k}(\bar{\pi}^{N},\mu_{1})$ and
$\alpha_{k}$ for each $k\in[K]$. Note that in the definition (38), the value
of $\bar{\pi}^{N}$ is essentially random, where the randomness comes from the
filtration $\mathcal{F}_{N}$ that decides the value of
$\bm{q}^{1},\dots,\bm{q}^{N}$. Therefore, in the definition of
$V_{r}(\bar{\pi}^{N},\mu_{1})$ and $V_{k}(\bar{\pi}^{N},\mu_{1})$ for each
$k\in[K]$, we take expectation over the filtration $\mathcal{F}_{N}$. With the
above definitions, the regret bound established in Theorem 6.3 can be
transferred into the sample complexity bound of the policy $\bar{\pi}^{N}$
given below. The formal proof is relegated to Section 13.

###### Theorem 6.4

With a sample complexity bound of

$O\left(\frac{(|\mathcal{S}|+K)^{3}\cdot|\mathcal{S}|\cdot|\mathcal{A}|}{\alpha^{2}\cdot\xi\cdot\sigma(1-\gamma)\cdot\min\\{\sigma^{2},(1-\gamma)^{2}\cdot\delta^{2}\\}}\cdot\frac{\log^{2}(1/\varepsilon)}{\varepsilon}\right),$

where $\xi=\min_{(s,a)\in\mathcal{I}^{*}}\left\\{q^{*}(s,a)\right\\}$ and
$\bm{q}^{*}$ denotes the optimal soluton to LP (8) corresponding to the
optimal basis $\mathcal{I}^{*}$ and $\mathcal{J}^{*}$, we obtain a policy
$\bar{\pi}^{N}$ from Algorithm 2 (defined in (38)) such that

$V_{r}(\pi^{*},\mu_{1})-V_{r}(\bar{\pi}^{N},\mu_{1})\leq\varepsilon\text{\leavevmode\nobreak\
\leavevmode\nobreak\ and\leavevmode\nobreak\ \leavevmode\nobreak\
}V_{k}(\bar{\pi}^{N},\mu_{1})-\alpha_{k}\leq\varepsilon,\leavevmode\nobreak\
\forall k\in[K].$

Note that one caveat in transferring the bounds in Theorem 6.3 into the sample
complexity bound of the policy $\bar{\pi}^{N}$ is that the vector
$\bar{\bm{q}}^{N}$ is not an occupancy measure since there is a gap between
$B\bar{\bm{q}}^{N}$ and $\bm{\mu}$, though bounded at the order of $O(\log
N/N)$. However, one can utilize the structure (22) to show a bound over the
gap between $\bar{\bm{q}}^{N}$ and $\bm{q}^{*}$, pointwise. In this way, the
gap between their state value functions can be bounded, which induces an
additional $O(\log(N))$ term. Therefore, we obtain our final sample complexity
bounds, scales as $\frac{O(\log^{2}(1/\varepsilon))}{\varepsilon}$.

Our Algorithm 2 can be directly applied to solving MDP problems without
resource constraints and our bounds in Theorem 6.3 and Theorem 6.4 still hold.
Note that in the MDP problems, the parameter $\sigma$ can be lower bounded by
$1-\gamma$, which follows from the fact that the matrix $A^{*}$ can simply be
represented by the probability transition matrix. Then, we have the following
sample complexity bound for our Algorithm 2.

###### Proposition 6.5

For the MDP problems without resource constraints, i.e., $K=0$, with a sample
complexity bound of

$O\left(\frac{|\mathcal{S}|^{4}\cdot|\mathcal{A}|}{(1-\gamma)^{4}\cdot\xi\cdot\delta^{2}}\cdot\frac{\log^{2}(1/\varepsilon)}{\varepsilon}\right),$
(39)

we obtain a policy $\bar{\pi}^{N}$ from Algorithm 2 (defined in (38)) such
that

$V_{r}(\pi^{*},\mu_{1})-V_{r}(\bar{\pi}^{N},\mu_{1})\leq\varepsilon\text{\leavevmode\nobreak\
\leavevmode\nobreak\ and\leavevmode\nobreak\ \leavevmode\nobreak\
}V_{k}(\bar{\pi}^{N},\mu_{1})-\alpha_{k}\leq\varepsilon,\leavevmode\nobreak\
\forall k\in[K].$

Note that one significant term in our sample complexity bound in Proposition
6.5 is $\xi\cdot\delta^{2}$. Recall that $\xi$ represents the minimal mass of
the optimal occupancy measure and $\delta$ represents the change of the
objective value of LP (8) if we restrict one non-zero basic variable in an
optimal solution to be $0$. In this sense, $\xi\cdot\delta^{2}$ can be
understood as the gap between the value of the optimal policy and the value of
a sub-optimal policy that is restricted from taking the optimal action given a
state. Such a problem-dependent gap shows up broadly in the literature for
online decision-making with (logarithmic) problem-dependent guarantees, for
example, in the multi-arm-bandit problem (Lai and Robbins 1985) and the
reinforcement learning problem (Auer et al. 2008).

In terms of the dependency of our sample complexity bound on other problem
parameters such as $|\mathcal{S}|$, $|\mathcal{A}|$, and $1-\gamma$, we
compare to the series of work (Sidford et al. 2018, Wainwright 2019, Wang
2020, Agarwal et al. 2020, He et al. 2021), that subsequently achieves a
sample complexity bound of
$O\left(\frac{|\mathcal{S}|\cdot|\mathcal{A}|}{(1-\gamma)^{3}\cdot\varepsilon^{2}}\right)$,
where the dependency over $|\mathcal{S}|$, $|\mathcal{A}|$, and $1-\gamma$ is
optimal (Gheshlaghi Azar et al. 2013, Lattimore and Hutter 2012). Our sample
complexity bound in (39) has a worse dependency in terms of $|\mathcal{S}|$
and $1-\gamma$. This is because we construct an empirical LP to estimate the
value of LP (8) and resolve the linear equation as in (23), where the size of
the LP (which is $|\mathcal{S}|$) and the eigenvalues of the matrix $A^{*}$
(which is bounded by $1-\gamma$) will play a part. However, our bound (39)
enjoys a better dependency in terms of $\varepsilon$.

##  7 Concluding Remarks

In this work, we present a new algorithm that achieves logarithmic regrets or
$\tilde{O}(1/\varepsilon)$ sample complexity bound for the CMDP problems, for
the first time in the literature. To achieve these improvements, we develop a
new algorithmic framework to analyze the CMDP problems, motivated by the
online LP literature. We consider the LP reformulation of the CMDP problems
and we solve the LP in an online manner. Besides introducing the online LP
framework, our method is new even compared to the online LP literature, as we
do not require the non-degeneracy assumption to derive the logarithmic regret.
In our research, we adopt the basic tabular setting to derive our results. We
leave the logarithmic regret and $\tilde{O}(1/\varepsilon)$ sample complexity
for more involved setting in CMDP problems for future research.

## References

  * Achiam et al. [2017] J. Achiam, D. Held, A. Tamar, and P. Abbeel.  Constrained policy optimization.  In _International conference on machine learning_ , pages 22–31. PMLR, 2017.
  * Agarwal et al. [2020] A. Agarwal, S. Kakade, and L. F. Yang.  Model-based reinforcement learning with a generative model is minimax optimal.  In _Conference on Learning Theory_ , pages 67–83. PMLR, 2020.
  * Agrawal et al. [2014] S. Agrawal, Z. Wang, and Y. Ye.  A dynamic near-optimal algorithm for online linear programming.  _Operations Research_ , 62(4):876–890, 2014.
  * Altman [1999] E. Altman.  _Constrained Markov decision processes_.  vol7. CRCPress, 1999.
  * Arlotto and Gurvich [2019] A. Arlotto and I. Gurvich.  Uniformly bounded regret in the multisecretary problem.  _Stochastic Systems_ , 9(3):231–260, 2019.
  * Arlotto and Xie [2020] A. Arlotto and X. Xie.  Logarithmic regret in the dynamic and stochastic knapsack problem with equal rewards.  _Stochastic Systems_ , 10(2):170–191, 2020.
  * Auer et al. [2008] P. Auer, T. Jaksch, and R. Ortner.  Near-optimal regret bounds for reinforcement learning.  _Advances in neural information processing systems_ , 21, 2008.
  * Buchbinder and Naor [2009] N. Buchbinder and J. Naor.  Online primal-dual algorithms for covering and packing.  _Mathematics of Operations Research_ , 34(2):270–286, 2009.
  * Bumpensanti and Wang [2020] P. Bumpensanti and H. Wang.  A re-solving heuristic with uniformly bounded loss for network revenue management.  _Management Science_ , 66(7):2993–3009, 2020\.
  * Chow et al. [2018] Y. Chow, O. Nachum, E. Duenez-Guzman, and M. Ghavamzadeh.  A lyapunov-based approach to safe reinforcement learning.  _Advances in neural information processing systems_ , 31, 2018.
  * Dann et al. [2021] C. Dann, T. V. Marinov, M. Mohri, and J. Zimmert.  Beyond value-function gaps: Improved instance-dependent regret bounds for episodic reinforcement learning.  _Advances in Neural Information Processing Systems_ , 34:1–12, 2021.
  * Ding et al. [2021] D. Ding, X. Wei, Z. Yang, Z. Wang, and M. 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] Y. Efroni, S. Mannor, and M. Pirotta.  Exploration-exploitation in constrained mdps.  _arXiv preprint arXiv:2003.02189_ , 2020.
  * Ferguson [1989] T. S. Ferguson.  Who solved the secretary problem?  _Statistical science_ , 4(3):282–289, 1989.
  * Fisac et al. [2018] J. F. Fisac, A. K. Akametalu, M. N. Zeilinger, S. Kaynama, J. Gillula, and C. J. Tomlin.  A general safety framework for learning-based control in uncertain robotic systems.  _IEEE Transactions on Automatic Control_ , 64(7):2737–2752, 2018.
  * Flajolet and Jaillet [2015] A. Flajolet and P. Jaillet.  Logarithmic regret bounds for bandits with knapsacks.  _arXiv preprint arXiv:1510.01800_ , 2015.
  * Gheshlaghi Azar et al. [2013] M. Gheshlaghi Azar, R. Munos, and H. J. Kappen.  Minimax pac bounds on the sample complexity of reinforcement learning with a generative model.  _Machine learning_ , 91:325–349, 2013.
  * Ghosh et al. [2022] A. Ghosh, X. Zhou, and N. Shroff.  Achieving sub-linear regret in infinite horizon average reward constrained mdp with linear function approximation.  In _The Eleventh International Conference on Learning Representations_ , 2022.
  * Gladin et al. [2023] E. Gladin, M. Lavrik-Karmazin, K. Zainullina, V. Rudenko, A. Gasnikov, and M. Takac.  Algorithm for constrained markov decision process with linear convergence.  In _International Conference on Artificial Intelligence and Statistics_ , pages 11506–11533. PMLR, 2023.
  * Graves and Lai [1997] T. L. Graves and T. L. Lai.  Asymptotically efficient adaptive choice of control laws incontrolled markov chains.  _SIAM journal on control and optimization_ , 35(3):715–743, 1997.
  * Gupta and Molinaro [2014] A. Gupta and M. Molinaro.  How experts can solve lps online.  In _European Symposium on Algorithms_ , pages 517–529. Springer, 2014\.
  * He et al. [2021] J. He, D. Zhou, and Q. Gu.  Nearly minimax optimal reinforcement learning for discounted mdps.  _Advances in Neural Information Processing Systems_ , 34:22288–22300, 2021.
  * Higham [2002] N. J. Higham.  _Accuracy and stability of numerical algorithms_.  SIAM, 2002.
  * Hiriart-Urruty and Lemaréchal [1996] J.-B. Hiriart-Urruty and C. Lemaréchal.  _Convex analysis and minimization algorithms I: Fundamentals_ , volume 305.  Springer science & business media, 1996.
  * Horn and Johnson [2012] R. A. Horn and C. R. Johnson.  _Matrix analysis_.  Cambridge university press, 2012.
  * Jasin and Kumar [2012] S. Jasin and S. Kumar.  A re-solving heuristic with bounded revenue loss for network revenue management with customer choice.  _Mathematics of Operations Research_ , 37(2):313–345, 2012.
  * Jia et al. [2023] J. Jia, H. Li, K. Liu, Z. Liu, J. Zhou, N. Gravin, and Z. G. Tang.  Online resource allocation in markov chains.  In _Proceedings of the ACM Web Conference 2023_ , pages 3498–3507, 2023.
  * Jiang [2023] J. Jiang.  Constant approximation for network revenue management with markovian-correlated customer arrivals.  _arXiv preprint arXiv:2305.05829_ , 2023.
  * Jiang et al. [2022] J. Jiang, W. Ma, and J. Zhang.  Degeneracy is ok: Logarithmic regret for network revenue management with indiscrete distributions.  _arXiv preprint arXiv:2210.07996_ , 2022.
  * Jin and Sidford [2020] Y. Jin and A. Sidford.  Efficiently solving mdps with stochastic mirror descent.  In _International Conference on Machine Learning_ , pages 4890–4900. PMLR, 2020.
  * Kesselheim et al. [2014] T. Kesselheim, A. Tönnis, K. Radke, and B. Vöcking.  Primal beats dual on online packing lps in the random-order model.  In _Proceedings of the forty-sixth annual ACM symposium on Theory of computing_ , pages 303–312, 2014.
  * Kober et al. [2013] J. Kober, J. A. Bagnell, and J. Peters.  Reinforcement learning in robotics: A survey.  _The International Journal of Robotics Research_ , 32(11):1238–1274, 2013.
  * Lai and Robbins [1985] T. L. Lai and H. Robbins.  Asymptotically efficient adaptive allocation rules.  _Advances in applied mathematics_ , 6(1):4–22, 1985.
  * Lattimore and Hutter [2012] T. Lattimore and M. Hutter.  Pac bounds for discounted mdps.  In _Algorithmic Learning Theory: 23rd International Conference, ALT 2012, Lyon, France, October 29-31, 2012. Proceedings 23_ , pages 320–334. Springer, 2012.
  * Li et al. [2021a] T. Li, Z. Guan, S. Zou, T. Xu, Y. Liang, and G. Lan.  Faster algorithm and sharper analysis for constrained markov decision process.  _arXiv preprint arXiv:2110.10351_ , 2021a.
  * Li et al. [2023] W. Li, P. Rusmevichientong, and H. Topaloglu.  Revenue management with calendar-aware and dependent demands: Asymptotically tight fluid approximations.  _Available at SSRN 4543277_ , 2023.
  * Li and Ye [2022] X. Li and Y. Ye.  Online linear programming: Dual convergence, new algorithms, and regret bounds.  _Operations Research_ , 70(5):2948–2966, 2022\.
  * Li et al. [2021b] X. Li, C. Sun, and Y. Ye.  The symmetry between arms and knapsacks: A primal-dual approach for bandits with knapsacks.  In _International Conference on Machine Learning_ , pages 6483–6492. PMLR, 2021b.
  * Liu et al. [2021a] T. Liu, R. Zhou, D. Kalathil, P. Kumar, and C. Tian.  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] T. Liu, R. Zhou, D. Kalathil, P. Kumar, and C. Tian.  Policy optimization for constrained mdps with provable fast global convergence.  _arXiv preprint arXiv:2111.00552_ , 2021b.
  * Ma et al. [2022] W. Ma, Y. Cao, D. H. Tsang, and D. Xia.  Optimal regularized online convex allocation by adaptive re-solving.  _arXiv preprint arXiv:2209.00399_ , 2022.
  * Mehta et al. [2007] A. Mehta, A. Saberi, U. Vazirani, and V. Vazirani.  Adwords and generalized online matching.  _Journal of the ACM (JACM)_ , 54(5):22–es, 2007\.
  * Mnih et al. [2013] V. Mnih, K. Kavukcuoglu, D. Silver, A. Graves, I. Antonoglou, D. Wierstra, and M. Riedmiller.  Playing atari with deep reinforcement learning.  _arXiv preprint arXiv:1312.5602_ , 2013.
  * Molinaro and Ravi [2014] M. Molinaro and R. Ravi.  The geometry of online packing linear programs.  _Mathematics of Operations Research_ , 39(1):46–59, 2014.
  * Nedić and Ozdaglar [2009] A. Nedić and A. Ozdaglar.  Subgradient methods for saddle-point problems.  _Journal of optimization theory and applications_ , 142:205–228, 2009.
  * Ono et al. [2015] M. Ono, M. Pavone, Y. Kuwata, and J. Balaram.  Chance-constrained dynamic programming with application to risk-aware robotic space exploration.  _Autonomous Robots_ , 39:555–571, 2015.
  * Shani et al. [2005] G. Shani, D. Heckerman, R. I. Brafman, and C. Boutilier.  An mdp-based recommender system.  _Journal of Machine Learning Research_ , 6(9), 2005.
  * Sidford et al. [2018] A. Sidford, M. Wang, X. Wu, L. Yang, and Y. Ye.  Near-optimal time and sample complexities for solving markov decision processes with a generative model.  _Advances in Neural Information Processing Systems_ , 31, 2018.
  * Simchowitz and Jamieson [2019] M. Simchowitz and K. G. Jamieson.  Non-asymptotic gap-dependent regret bounds for tabular mdps.  _Advances in Neural Information Processing Systems_ , 32, 2019.
  * Tamar et al. [2012] A. Tamar, D. Di Castro, and S. Mannor.  Policy gradients with variance related risk criteria.  In _Proceedings of the twenty-ninth international conference on machine learning_ , pages 387–396, 2012.
  * Vera and Banerjee [2021] A. Vera and S. Banerjee.  The bayesian prophet: A low-regret framework for online decision making.  _Management Science_ , 67(3):1368–1391, 2021\.
  * Vera et al. [2021] A. Vera, S. Banerjee, and I. Gurvich.  Online allocation and pricing: Constant regret via bellman inequalities.  _Operations Research_ , 69(3):821–840, 2021.
  * Wagenmaker and Foster [2023] A. J. Wagenmaker and D. J. Foster.  Instance-optimality in interactive decision making: Toward a non-asymptotic theory.  In _The Thirty Sixth Annual Conference on Learning Theory_ , pages 1322–1472. PMLR, 2023.
  * Wagenmaker et al. [2022] A. J. Wagenmaker, M. Simchowitz, and K. Jamieson.  Beyond no regret: Instance-dependent pac reinforcement learning.  In _Conference on Learning Theory_ , pages 358–418. PMLR, 2022.
  * Wainwright [2019] M. J. Wainwright.  Variance-reduced $q$-learning is minimax optimal.  _arXiv preprint arXiv:1906.04697_ , 2019.
  * Wang [2020] M. Wang.  Randomized linear programming solves the markov decision problem in nearly linear (sometimes sublinear) time.  _Mathematics of Operations Research_ , 45(2):517–546, 2020.
  * Wei et al. [2021] H. Wei, X. Liu, and L. Ying.  A provably-efficient model-free algorithm for constrained markov decision processes.  _arXiv preprint arXiv:2106.01577_ , 2021.
  * Zanette and Brunskill [2019] A. Zanette and E. Brunskill.  Tighter problem-dependent regret bounds in reinforcement learning without domain knowledge using value function bounds.  In _International Conference on Machine Learning_ , pages 7304–7312. PMLR, 2019.
  * Zhou et al. [2022] R. Zhou, T. Liu, D. Kalathil, P. Kumar, and C. Tian.  Anchor-changing regularized natural policy gradient for multi-objective reinforcement learning.  _Advances in Neural Information Processing Systems_ , 35:13584–13596, 2022.

##  8 Proof of Lemma 3.1

Let $\bm{q}^{*}$ be a basic optimal solution to LP (8). We also denote by
$\mathcal{I}$ the index set of $\bm{q}^{*}$ such that
$\bm{q}^{*}_{\mathcal{I}}>0$. We then denote by $\mathcal{J}^{\prime}\in[K]$
the set of active constraints at $\bm{q}^{*}$. Then, the following linear
equations must be satisfied by $\bm{q}^{*}$.

$C(\mathcal{J}^{\prime},\mathcal{I})\bm{q}_{\mathcal{I}}^{*}=\bm{\alpha}_{\mathcal{J}^{\prime}}\text{\leavevmode\nobreak\
\leavevmode\nobreak\ and\leavevmode\nobreak\ \leavevmode\nobreak\
}B(:,\mathcal{I})\bm{q}_{\mathcal{I}}^{*}=\bm{\mu}.$ (40)

From the property of the basic optimal solution, we must have
$|\mathcal{J}^{\prime}|+b\geq|\mathcal{I}|$.

If $|\mathcal{J}^{\prime}|+b=|\mathcal{I}|$, then we know that we already find
the desired index set $\mathcal{I}$ and $\mathcal{J}=\mathcal{J}^{\prime}$.

Otherwise, if $|\mathcal{J}^{\prime}|+b>|\mathcal{I}|$, then we know that the
LP (8) is degenerate. However, now the linear system (40) is over-determined,
i.e., there must be $|\mathcal{J}^{\prime}|+b-|\mathcal{I}|$ number of
equations can be implied by the others. It only remains to show that those
redundant equations are all in the set $\mathcal{J}^{\prime}$. This step can
be done can showing that the matrix $B(:,\mathcal{I})$ has a full row rank. We
prove this by showing contradiction.

For the infinite horizon discounted problem, suppose that $B(:,\mathcal{I})$
does not have full row rank, there must exists
$\bm{\beta}\in\mathbb{R}^{|\mathcal{S}|}$ such that

$\bm{\beta}^{\top}B(:,\mathcal{I})=\bm{0}.$ (41)

On the other hand, denote by $\pi^{*}$ the optimal policy corresponding to
$\bm{q}^{*}$. We then define a matrix
$\Gamma\in\mathbb{R}^{|\mathcal{I}|\times\mathcal{S}}$ such that the $s$-th
column of $\Gamma$ is a vector that takes $0$ for all the
$(s^{\prime},a)\in\mathcal{I}$-th element if $s^{\prime}\neq s$, and take a
value of $\pi^{*}(a|s)$ for all $a$ such that $(s,a)\in\mathcal{I}$. We know
that

$B(:,\mathcal{I})\Gamma=I-\gamma\cdot P^{\pi^{*}}$

with $I\in\mathbb{R}^{|\mathcal{S}|\times|\mathcal{S}|}$ being the identify
matrix and $P^{\pi^{*}}$ being the transition probability matrix under the
policy $\pi^{*}$, with the element at the $s$-th row and $s^{\prime}$-th
column denoting the probability of transiting from state $s$ to state
$s^{\prime}$ under the policy $\pi^{*}$. It is well known that the matrix
$I-\gamma\cdot P^{\pi^{*}}$ is non-singular (see for example the Gersgorin’s
Theorem in Horn and Johnson [2012]). Therefore, for any vector
$\bm{\beta}\in\mathbb{R}^{|\mathcal{S}|}$, we know that

$\bm{\beta}^{\top}B(:,\mathcal{I})\Gamma=\bm{\beta}^{\top}(I-\gamma\cdot
P^{\pi^{*}})\neq 0$

which contradicts with (71). Our proof is thus completed.

##  9 Proof of Lemma 4.1

We now condition on the event that $|\bar{r}_{N_{0}}(s,a)-\hat{r}(s,a)|$,
$|\bar{c}_{k,N_{0}}(s,a)-\hat{c}_{k}(s,a)|$, and
$|\bar{P}_{N_{0}}(s^{\prime}|s,a)-P(s^{\prime}|s,a)|$ for each $k\in[K]$,
$(s,a)\in\mathcal{S}\times\mathcal{A}$ and $s^{\prime}\in\mathcal{S}$ are all
bounded by $\mathrm{Rad}(N_{0},\varepsilon)$. From the union bound, we know
that this event happens with probability at least
$1-(K|\mathcal{S}||\mathcal{A}|-|\mathcal{S}|^{2}|\mathcal{A}|)\cdot\varepsilon$.

Note that for LP (6), by summing up the constraint (6c) for all
$s\in\mathcal{S}$, we obtain that any feasible solution $\bm{q}$ for LP (6)
would satisfy

$\|\bm{q}\|_{1}=1.$ (42)

We first upper bound the gap $V-\bar{V}_{N_{0}}$. Denote by $\bm{q}^{*}$ one
optimal solution to $V$. Then, from the feasibility of $\bm{q}^{*}$, we know
that

$\bar{C}_{N_{0}}\bm{q}^{*}=C\bm{q}^{*}+(\bar{C}_{N_{0}}-C)\bm{q}^{*}\leq\bm{\alpha}+\mathrm{Rad}(N_{0},\varepsilon)\leq\bm{\alpha}+\lambda_{N_{0}}$
(43)

where the first inequality follows from $\|\bm{q}^{*}\|_{1}=1$ (42) and all
elements of $\bar{C}_{N_{0}}-C$ are upper bounded by
$\mathrm{Rad}(N_{0},\varepsilon)$. Also, we know that

$\bar{B}_{N_{0}}\bm{q}^{*}=B\bm{q}^{*}+(\bar{B}_{N_{0}}-B)\bm{q}^{*}\leq(1-\gamma)\cdot\bm{\mu}+\gamma\cdot\mathrm{Rad}(N_{0},\varepsilon)\leq(1-\gamma)\cdot\bm{\mu}+\lambda_{N_{0}}$
(44)

where the first inequality follows from $\|\bm{q}^{*}\|_{1}=1$ (42) and all
elements of $\bar{B}_{N_{0}}-B$ are upper bounded by
$\gamma\cdot\mathrm{Rad}(N_{0},\varepsilon)$. Similarly, we have that

$\bar{B}_{N_{0}}\bm{q}^{*}=B\bm{q}^{*}+(\bar{B}_{N_{0}}-B)\bm{q}^{*}\geq(1-\gamma)\cdot\bm{\mu}-\gamma\cdot\mathrm{Rad}(N_{0},\varepsilon)\geq(1-\gamma)\cdot\bm{\mu}-\lambda_{N_{0}}.$
(45)

Therefore, as long as

$\lambda_{N_{0}}\geq\mathrm{Rad}(N_{0},\varepsilon),$ (46)

we know that $\bm{q}^{*}$ is a feasible solution to $\bar{V}_{N_{0}}$. We have
that

$\bar{\bm{r}}_{N_{0}}^{\top}\bm{q}^{*}\geq\hat{\bm{r}}^{\top}\bm{q}^{*}-\mathrm{Rad}(N_{0},\varepsilon)$
(47)

by noting $\|\bm{q}^{*}\|_{1}=1$ (42) and all elements of
$\bar{\bm{r}}_{N_{0}}-\hat{\bm{r}}$ are upper bounded by
$\mathrm{Rad}(N_{0},\varepsilon)$. Therefore, we can obtain the bound

$V-\mathrm{Rad}(N_{0},\varepsilon)\leq\bar{\bm{r}}_{N_{0}}^{\top}\bm{q}^{*}\leq\bar{V}_{N_{0}}.$
(48)

We then lower bound the gap $V-\bar{V}_{N_{0}}$. We first define

$\displaystyle\bar{V}_{N_{0}}(\lambda^{\prime}_{N_{0}})=$ $\displaystyle\max$
$\displaystyle(\bar{\bm{r}}_{N_{0}}-\lambda^{\prime}_{N_{0}})^{\top}\bm{q}$
(49) s.t. $\displaystyle\bar{C}_{N_{0}}\bm{q}\leq\bm{\alpha}+\lambda_{N_{0}}$
$\displaystyle\bar{B}_{N_{0}}\bm{q}\leq\bm{\mu}+\lambda_{N_{0}}$
$\displaystyle\bar{B}_{N_{0}}\bm{q}\geq\bm{\mu}-\lambda_{N_{0}}$
$\displaystyle\bm{q}\geq 0,$

for any constant $\lambda^{\prime}_{N_{0}}$. Clearly, any optimal solution
$\bar{\bm{q}}^{*}$ to $\bar{V}_{N_{0}}$ will be a feasible solution to
$\bar{V}_{N_{0}}(\lambda^{\prime}_{N_{0}})$. Moreover, by summing up the
constraints $\bar{B}_{N_{0}}\bm{q}\leq\bm{\mu}+\lambda_{N_{0}}$ for all
$s\in\mathcal{S}$, we know that

$\|\bar{\bm{q}}^{*}\|_{1}\leq
1+\frac{|\mathcal{S}|}{1-\gamma}\cdot\lambda_{N_{0}}.$ (50)

Then, it holds that

$\bar{V}_{N_{0}}\leq(\bar{\bm{r}}_{N_{0}}-\lambda^{\prime}_{N_{0}})^{\top}\bar{\bm{q}}^{*}+\lambda^{\prime}_{N_{0}}\cdot\|\bar{\bm{q}}^{*}\|_{1}\leq\bar{V}_{N_{0}}(\lambda^{\prime}_{N_{0}})+\lambda^{\prime}_{N_{0}}+\frac{|\mathcal{S}|}{1-\gamma}\cdot\lambda_{N_{0}}\lambda^{\prime}_{N_{0}}.$
(51)

We then compare the value between $\bar{V}_{N_{0}}(\lambda^{\prime}_{N_{0}})$
and $V$. The dual of $\bar{V}_{N_{0}}(\lambda^{\prime}_{N_{0}})$ is given
below.

$\displaystyle\text{Dual}^{\prime}_{N_{0}}(\lambda^{\prime}_{N_{0}})=$
$\displaystyle\min$
$\displaystyle\bm{\alpha}^{\top}\bm{y}+\bm{\mu}^{\top}(\bm{z}_{1}-\bm{z}_{2})+\lambda_{N_{0}}\cdot(\|\bm{y}\|_{1}+\|\bm{z}_{1}\|_{1}+\|\bm{z}_{2}\|_{1})$
(52) s.t.
$\displaystyle\bar{C}_{N_{0}}^{\top}\bm{y}+\bar{B}_{N_{0}}^{\top}(\bm{z}_{1}-\bm{z}_{2})\geq\bar{\bm{r}}_{N_{0}}-\lambda^{\prime}_{N_{0}}$
$\displaystyle\bm{y}\geq 0,\bm{z}_{1}\geq 0,\bm{z}_{2}\geq 0.$

Denote by $\bm{y}^{*}$ and $\bm{z}^{*}$ one optimal solution to the dual of LP
(8), given below.

$\displaystyle\text{Dual}=$ $\displaystyle\min$
$\displaystyle\bm{\alpha}^{\top}\bm{y}+\bm{\mu}^{\top}\bm{z}$ (53) s.t.
$\displaystyle C^{\top}\bm{y}+B^{\top}\bm{z}\geq\hat{\bm{r}}$
$\displaystyle\bm{y}\geq 0,\bm{z}\geq-\infty.$

We now show that $\bm{y}^{*}$ and $\bm{z}^{*}$ is also a feasible solution to
$\text{Dual}^{\prime}_{N_{0}}$, with
$\lambda^{\prime}_{N_{0}}=\frac{1}{\min_{k\in[K]}\\{\alpha_{k}\\}}\cdot\left(1+\frac{|\mathcal{S}|}{1-\gamma}\right)\cdot\mathrm{Rad}(N_{0},\varepsilon)$.
We have the following claim regarding the upper bound on
$\|\bm{y}^{*}\|_{\infty}$ and $\|\bm{z}^{*}\|_{\infty}$.

###### Claim 1

There exists an optimal solution $\bm{y}^{*}$ and $\bm{z}^{*}$ to the Dual
(53) such that

$\|\bm{y}^{*}\|_{1}\leq\frac{1}{\min_{k\in[K]}\\{\alpha_{k}\\}}\text{\leavevmode\nobreak\
\leavevmode\nobreak\ and\leavevmode\nobreak\ \leavevmode\nobreak\
}\|\bm{z}^{*}\|_{\infty}\leq\frac{1}{1-\gamma}\cdot\frac{1}{\min_{k\in[K]}\\{\alpha_{k}\\}}.$

Then, we define $\bar{\bm{y}}^{*}=\bm{y}^{*}$,
$\bm{z}_{1}^{*}=\max\\{0,\bm{z}^{*}\\}$ and
$\bm{z}_{2}^{*}=\max\\{0,-\bm{z}^{*}\\}$. We have

$\displaystyle\bar{C}_{N_{0}}^{\top}\bar{\bm{y}}^{*}+\bar{B}_{N_{0}}^{\top}(\bm{z}_{1}^{*}-\bm{z}_{2}^{*})$
$\displaystyle\geq
C^{\top}\bm{y}^{*}+B^{\top}\bm{z}^{*}-\mathrm{Rad}(N_{0},\varepsilon)\cdot\left(\|\bm{y}^{*}\|_{1}+\|\bm{z}^{*}\|_{1}\right)$
$\displaystyle\geq
C^{\top}\bm{y}^{*}+B^{\top}\bm{z}^{*}-\mathrm{Rad}(N_{0},\varepsilon)\cdot\frac{1}{\min_{k\in[K]}\\{\alpha_{k}\\}}\cdot\left(1+\frac{|\mathcal{S}|}{1-\gamma}\right)$
$\displaystyle\geq\hat{\bm{r}}-\frac{1}{\min_{k\in[K]}\\{\alpha_{k}\\}}\cdot\left(1+\frac{|\mathcal{S}|}{1-\gamma}\right)\cdot\mathrm{Rad}(N_{0},\varepsilon).$

Thus, we know that $\bar{\bm{y}}^{*}$ and $\bm{z}_{1}^{*},\bm{z}_{2}^{*}$ is
also a feasible solution to $\text{Dual}_{N_{0}}(\lambda^{\prime}_{N_{0}})$,
and we have

$\text{Dual}^{\prime}_{N_{0}}(\lambda^{\prime}_{N_{0}})\leq\text{Dual}+\lambda_{N_{0}}\cdot(\|\bm{y}^{*}\|_{1}+\|\bm{z}^{*}\|_{1})\leq\text{Dual}+\frac{\mathrm{Rad}(N_{0},\varepsilon)}{\min_{k\in[K]}\\{\alpha_{k}\\}}\cdot\left(1+\frac{|\mathcal{S}|}{1-\gamma}\right).$
(54)

Combing (54) with (51) and also noting that
$\bar{V}_{N_{0}}(\lambda^{\prime}_{N_{0}})=\text{Dual}^{\prime}_{N_{0}}(\lambda^{\prime}_{N_{0}})$,
we have

$\bar{V}_{N_{0}}\leq
V+\frac{2\mathrm{Rad}(N_{0},\varepsilon)}{\min_{k\in[K]}\\{\alpha_{k}\\}}\cdot\left(1+\frac{|\mathcal{S}|}{1-\gamma}\right)+\frac{\mathrm{Rad}^{2}(N_{0},\varepsilon)}{\min_{k\in[K]}\\{\alpha_{k}\\}}\cdot\left(|\mathcal{S}|+\frac{|\mathcal{S}|^{2}}{1-\gamma}\right)$

which completes our proof.

#### Proof of 1.

We first bound $\|\bm{y}^{*}\|_{\infty}$. We utilize the approach in Hiriart-
Urruty and Lemaréchal [1996], Nedić and Ozdaglar [2009]. We define a
Lagrangian function, with only $\bm{y}$ as the Lagrangian dual variable.

$L(\bm{y},\bm{q}):=\bm{\alpha}^{\top}\bm{y}+\hat{\bm{r}}^{\top}\bm{q}-\bm{y}^{\top}C\bm{q}$
(55)

where the feasible set for $\bm{q}$ is $\\{\bm{q}\geq 0:B\bm{q}=\bm{\mu}\\}$
and the feasible set for $\bm{y}$ is $\\{\bm{y}\geq 0\\}$. Following Lemma 3
in Nedić and Ozdaglar [2009], it is without loss of generality to restrict the
feasible set of $\bm{y}$ to the set $\\{\bm{y}\geq
0:\|\bm{y}\|_{1}\leq\rho\\}$, where the constant $\rho$ is defined as

$\rho=\frac{\hat{\bm{r}}^{\top}\bm{q}^{*}-\hat{\bm{r}}^{\top}\bar{\bm{q}}}{\min_{k\in[K]}\left\\{\alpha_{k}-C(k,:)\bar{\bm{q}}\right\\}}$
(56)

where $\bar{\bm{q}}$ is the occupancy measure that satisfies Slater’s
condition as stated in Section 4. Note that we have

$\rho\leq\frac{1}{\min_{k\in[K]}\\{\alpha_{k}\\}}.$

Therefore, we obtain the following bound on $\bm{y}^{*}$:

$\|\bm{y}^{*}\|_{1}\leq\rho.$ (57)

We now proceed to bound $\bm{z}^{*}$. Denote by $\bm{q}^{*}$ the optimal
solution corresponding to the optimal dual solution $(\bm{y}^{*},\bm{z}^{*})$,
with $\bm{y}^{*}$ bounded as in (57). We also denote by $\pi^{*}$ the optimal
policy corresponding to $\bm{q}^{*}$. Then, from the complementary slackness
condition, as long as $\bm{q}^{*}(s,a)>0$ for a $(s,a)$, we must have

$C(:,(s,a))^{\top}\bm{y}^{*}+B(:,(s,a))^{\top}\bm{z}^{*}=\hat{r}(s,a).$ (58)

We now multiply both sides of (58) by
$q^{*}(s,a)/\sum_{a^{\prime}\in\mathcal{A}}q^{*}(s,a^{\prime})$, and sum up
over $a$, for each state $s$. Then we get

$(C^{\pi^{*}})^{\top}\bm{y}^{*}+B^{\pi^{*}}\bm{z}^{*}=\hat{\bm{r}}^{\pi^{*}}.$
(59)

Here, $C^{\pi^{*}}\in\mathbb{R}^{K\times|\mathcal{S}|}$ and the element at
$k$-th row and $s$-th column is
$\sum_{a\in\mathcal{A}}c_{k}(s,a)\cdot\frac{q^{*}(s,a)}{\sum_{a^{\prime}\in\mathcal{A}}q^{*}(s,a^{\prime})}$.
$B^{\pi^{*}}=I-\gamma\cdot
P^{\pi^{*}}\in\mathbb{R}^{|\mathcal{S}|\times\mathcal{S}}$, where
$P^{\pi^{*}}(s,s^{\prime})=\sum_{a\in\mathcal{A}}\pi^{*}(a|s)\cdot
P(s^{\prime}|s,a)$ denotes the transition probability matrix under the policy
$\pi^{*}$. Also, $\hat{\bm{r}}^{\pi^{*}}\in\mathbb{R}^{|\mathcal{S}|}$ with
$\hat{r}^{\pi^{*}}(s)=\sum_{a\in\mathcal{A}}\hat{r}(s,a)\cdot\frac{q^{*}(s,a)}{\sum_{a^{\prime}\in\mathcal{A}}q^{*}(s,a^{\prime})}$.
Then, we have

$\bm{z}^{*}=(B^{\pi^{*}})^{-1}\cdot\left(\hat{\bm{r}}^{\pi^{*}}-(C^{\pi^{*}})^{\top}\bm{y}^{*}\right)$
(60)

From Jin and Sidford [2020], we know that

$\|(B^{\pi^{*}})^{-1}\|_{\infty}\leq\frac{1}{1-\gamma}.$ (61)

Also, from the bound on $\bm{y}^{*}$ in (57), we know that

$\left\|\hat{\bm{r}}^{\pi^{*}}-(C^{\pi^{*}})^{\top}\bm{y}^{*}\right\|_{\infty}\leq\rho.$
(62)

Therefore, we have that

$\|\bm{z}^{*}\|_{\infty}\leq\frac{\rho}{1-\gamma},$ (63)

which completes our proof. $\Halmos$

##  10 Proof of Theorem 6.1

We now condition on the event that $|\bar{r}_{N_{0}}(s,a)-\hat{r}(s,a)|$,
$|\bar{c}_{k,N_{0}}(s,a)-\hat{c}_{k}(s,a)|$, and
$|\bar{P}_{N_{0}}(s^{\prime}|s,a)-P(s^{\prime}|s,a)|$ for each $k\in[K]$,
$(s,a)\in\mathcal{S}\times\mathcal{A}$ and $s^{\prime}\in\mathcal{S}$ are all
bounded by $\mathrm{Rad}(N_{0},\varepsilon)$. We know that this event happens
with probability at least
$1-(K|\mathcal{S}||\mathcal{A}|-|\mathcal{S}|^{2}|\mathcal{A}|)\cdot\varepsilon$.

Following the procedure in Algorithm 1, we identify an index set
$\mathcal{I}$, where we set $\bm{q}_{i}=0$ for each $i\in\mathcal{I}^{c}$.
Note that we cannot further delete one more $i$ from the set $\mathcal{I}$.
Otherwise, when deleting this particular $i$ in $\mathcal{I}$ by setting
$\mathcal{I}^{\prime}=\mathcal{I}\backslash\\{i\\}$, we will have
$V_{\mathcal{I}^{\prime}}=V$ and as a result of Lemma 4.1, we have

$|\bar{V}_{N_{0}}-\bar{V}_{\mathcal{I}^{\prime},N_{0}}|\leq|V-V_{\mathcal{I}^{\prime}}|+2\mathrm{Gap}_{1}(N_{0},\varepsilon)+2\mathrm{Gap}_{2}(N_{0},\varepsilon)=2\mathrm{Gap}_{1}(N_{0},\varepsilon)+2\mathrm{Gap}_{2}(N_{0},\varepsilon)$
(64)

Therefore, if it is feasible (objective value does not change) to delete one
more $i$ from the index set $\mathcal{I}$, our algorithm will already do so.

We denote by $\bm{q}^{*}$ the optimal solution to LP (8), corresponding to the
optimal basis $\mathcal{I}$ identified by Algorithm 1. We know that
$\bm{q}^{*}_{\mathcal{I}}>0$ and $\bm{q}^{*}_{\mathcal{I}^{c}}=0$, which
implies that

$\displaystyle V=V_{\mathcal{I}}=$ $\displaystyle\max$
$\displaystyle(\hat{\bm{r}}_{\mathcal{I}})^{\top}\bm{q}$ (65) s.t.
$\displaystyle C(:,\mathcal{I})\bm{q}\leq\bm{\alpha}$ $\displaystyle
B(:,\mathcal{I})\bm{q}=\bm{\mu}$ $\displaystyle\bm{q}\geq 0,$

Note that in the formulation of (65), we simply discard the columns of the
constraint matrix in the index set $\mathcal{I}$. Thus, one optimal solution
to (65) will just be $\bm{q}^{*}_{\mathcal{I}}$. The dual of (65) is

$\displaystyle\text{Dual}_{\mathcal{I}}=\min\leavevmode\nobreak\
\leavevmode\nobreak$
$\displaystyle\bm{\alpha}^{\top}\bm{y}+\bm{\mu}^{\top}\bm{z}$ (66) s.t.
$\displaystyle(C(:,\mathcal{I}))^{\top}\bm{y}+(B(:,\mathcal{I}))^{\top}\bm{z}\geq\hat{\bm{r}}(\mathcal{I})$
$\displaystyle\bm{y}\geq 0,\bm{z}\geq-\infty,$

From the complementary slackness condition, we know that for the optimal dual
variable corresponding to $\bm{q}^{*}_{\mathcal{I}}$, all the constraints in
(66) must hold with equality. Therefore, we have the following result.

###### Claim 2

It holds that

$\displaystyle
V=V_{\mathcal{I}}=\text{Dual}_{\mathcal{I}}=\min\leavevmode\nobreak\
\leavevmode\nobreak$
$\displaystyle\bm{\alpha}^{\top}\bm{y}+\bm{\mu}^{\top}\bm{z}$ (67) s.t.
$\displaystyle(C(:,\mathcal{I}))^{\top}\bm{y}+(B(:,\mathcal{I}))^{\top}\bm{z}=\hat{\bm{r}}(\mathcal{I})$
$\displaystyle\bm{y}\geq 0,\bm{z}\geq-\infty.$

The proof of the claim is relegated to the end of this proof. We now show that
Algorithm 1 identify the linearly independent binding constraints for
$\bm{q}^{*}$ such that the conditions in Lemma 3.1 are satisfied.

Denote by $C(\mathcal{J},\mathcal{I})$ a sub-matrix of $C$ such that the rows
in the index set $\mathcal{J}\subset[K]$ and the columns in the index set
$\mathcal{I}$ of the matrix $C$ remain. Now if the matrix

$A=[C(\mathcal{J},\mathcal{I});B(:,\mathcal{I})]$ (68)

is singular, there must be

  * (i).

one row in $C(\mathcal{J},\mathcal{I})$ can be expressed as the linear
combination of the other rows in $A$ (we know that the matrix
$B(:,\mathcal{I})$ has full row rank from Lemma 3.1);

  * (ii).

or one column in $A$ can be expressed as the linear combination of other
columns.

We consider the situation (i). Denote this row as $k^{\prime}$ and we know
that restricting $y_{k^{\prime}}=0$ will not change the objective value of
$\text{Dual}_{\mathcal{I}}$, which implies that $k^{\prime}$ will be added to
the index set $\mathcal{J}$. This is because $y_{k^{\prime}}$ cannot be a
basic variable, otherwise, the optimal basis of the Dual (67) will be linearly
dependent. Therefore, we obtain a contradiction and we know that the matrix
$A$ must have full row rank. Thus, situation (i) will not happen.

We then consider the situation (ii). Note that we have

$\displaystyle
V=\text{Dual}_{\mathcal{J},\mathcal{I}}=\min\leavevmode\nobreak\
\leavevmode\nobreak$
$\displaystyle\bm{\alpha}_{\mathcal{J}}^{\top}\bm{y}+\bm{\mu}^{\top}\bm{z}$
(69) s.t.
$\displaystyle(C(\mathcal{J},\mathcal{I}))^{\top}\bm{y}+(B(:,\mathcal{I}))^{\top}\bm{z}\geq\hat{\bm{r}}_{\mathcal{I}}$
$\displaystyle\bm{y}\geq 0,\bm{z}\geq-\infty,$

Comparing the formulation (69) to the formulation (66), we only remain the
rows of the matrix $C(:,\mathcal{I})$ in the index set $\mathcal{J}$, where it
is feasible (objective value does not change) to set
$\bm{y}_{\mathcal{J}^{c}}=0$. The dual of (69) is

$\displaystyle V=V_{\mathcal{J},\mathcal{I}}=$ $\displaystyle\max$
$\displaystyle(\hat{\bm{r}}_{\mathcal{I}})^{\top}\bm{q}$ (70) s.t.
$\displaystyle C(\mathcal{J},\mathcal{I})\bm{q}\leq\bm{\alpha}_{\mathcal{J}}$
$\displaystyle B(:,\mathcal{I})\bm{q}=\bm{\mu}$ $\displaystyle\bm{q}\geq 0.$

If situation (ii) happens and one column of $A$ can be expressed as the linear
combination of the other columns in $A$, then we denote the index of this
column by $i^{\prime}$ and we know that we can simply restrict
$q_{i^{\prime}}=0$ without changing the objective value of (70). This is
because $q_{i^{\prime}}$ cannot be a basic variable otherwise the
corresponding optimal basis will be linearly dependent. However, the index
$i^{\prime}\in\mathcal{I}$. This means that we cannot further delete
$i^{\prime}$ from the index set $\mathcal{I}$ by restricting
$q_{i^{\prime}}=0$ without changing the objective value of LP (6). The above
argument leads to a contradiction. Therefore, we know that situation (ii)
cannot happen.

Given the arguments above, we know that the matrix $A$ is a non-singular
matrix and thus the conditions in Lemma 3.1 are satisfied with the variable
index set $\mathcal{I}$ and the constraint index set $\mathcal{J}$. It only
remains to show that we can tell whether the objective value of
$V^{\mathrm{Infi}}$ or $\text{Dual}_{\mathcal{I}}$ has changed by restricting
one variable to be $0$. Following the same steps as in Lemma 4.1, we can show
that for index sets $\mathcal{I}^{\prime}$ and $\mathcal{J}^{\prime}$, it
holds that

$\mathrm{Gap}_{1}(N_{0},\varepsilon)\geq
V_{\mathcal{J}^{\prime},\mathcal{I}^{\prime}}-\bar{V}_{\mathcal{J}^{\prime},\mathcal{I}^{\prime},N_{0}}$
(71)

and the upper gap as

$\mathrm{Gap}_{2}(N_{0},\varepsilon)\geq\bar{V}_{\mathcal{J}^{\prime},\mathcal{I}^{\prime},N_{0}}-V_{\mathcal{J}^{\prime},\mathcal{I}^{\prime}}$
(72)

with the formulation of $\mathrm{Gap}_{1}(N_{0},\varepsilon)$ and
$\mathrm{Gap}_{2}(N_{0},\varepsilon)$ given in (15) and (16). Therefore, as
long as

$2\mathrm{Gap}_{1}(N_{0},\varepsilon)+2\mathrm{Gap}_{2}(N_{0},\varepsilon)\geq\min\\{\delta_{1},\delta_{2}\\},$
(73)

where $\delta_{1}$ is defined in (18) and $\delta_{2}$ is defined in (21), we
can tell whether $V^{\mathrm{Infi}}$ is different from
$V^{\mathrm{Infi}}_{\mathcal{I}^{\prime}}$ and whether
$\text{Dual}_{\mathcal{I}^{\prime}}$ is different from
$\text{Dual}_{\mathcal{J}^{\prime},\mathcal{I}^{\prime}}$. Our proof is thus
completed.

#### Proof of Claim 2.

We first show that

$\displaystyle V=V_{\mathcal{I}}=$ $\displaystyle\max$
$\displaystyle(\hat{\bm{r}}_{\mathcal{I}})^{\top}\bm{q}$ (74) s.t.
$\displaystyle C(:,\mathcal{I})\bm{q}\leq\bm{\alpha}$ $\displaystyle
B(:,\mathcal{I})\bm{q}=\bm{\mu}$ $\displaystyle\bm{q}\geq 0.$

Denote by $\bm{q}^{*}$ the optimal solution to $V$ corresponding to the
optimal basis $\mathcal{I}$. It is clear to see that
$\bm{q}^{*}_{\mathcal{I}}$ is a feasible solution to $V_{\mathcal{I}}$ with
the same objective value. Then, we have

$V\leq V_{\mathcal{I}}.$ (75)

On the other hand, we denote by $\hat{\bm{q}}$ one optimal solution to
$V_{\mathcal{I}}$, and we construct

$\tilde{\bm{q}}_{\mathcal{I}}=\hat{\bm{q}}\text{\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ and\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\
}\tilde{\bm{q}}_{\mathcal{I}^{c}}=0.$

It is clear to see that $\tilde{\bm{q}}$ is a feasible solution to $V$ with
the same objective value, which implies that

$V_{\mathcal{I}}\leq V.$ (76)

Therefore, (74) is proved from combining (75) and (76). The dual of
$V_{\mathcal{I}}$ is given by

$\displaystyle\text{Dual}_{\mathcal{I}}=\min\leavevmode\nobreak\
\leavevmode\nobreak$
$\displaystyle\bm{\alpha}^{\top}\bm{y}+\bm{\mu}^{\top}\bm{z}$ (77) s.t.
$\displaystyle(C(:,\mathcal{I}))^{\top}\bm{y}+(B(:,\mathcal{I}))^{\top}\bm{z}\geq\hat{\bm{r}}(\mathcal{I})$
$\displaystyle\bm{y}\geq 0,\bm{z}\geq-\infty.$

We denote by $\bm{y}^{*},\bm{z}^{*}$ the optimal dual variable to $V$
corresponding to $\bm{q}^{*}$. It is easy to see that $\bm{y}^{*},\bm{z}^{*}$
is also feasible to $\text{Dual}_{\mathcal{I}}$ and

$\text{Dual}_{\mathcal{I}}=V_{\mathcal{I}}=V=\bm{\alpha}^{\top}\bm{y}^{*}+\bm{\mu}^{\top}\bm{z}^{*}$

where the first equality follows from the strong duality between
$V_{\mathcal{I}}$ and $\text{Dual}_{\mathcal{I}}$, the second equality follows
from (74), and the third equality follows from the strong duality between $V$
and its dual. Therefore, we know that $\bm{y}^{*}$ and $\bm{z}^{*}$ is also an
optimal solution to $\text{Dual}_{\mathcal{I}}$. Moreover, note that from the
complementary slackness condition, since $\bm{q}^{*}_{\mathcal{I}}>0$, we must
have

$(C(:,\mathcal{I}))^{\top}\bm{y}^{*}+(B(:,\mathcal{I}))^{\top}\bm{z}^{*}=\hat{\bm{r}}(\mathcal{I}).$
(78)

We know that $\bm{y}^{*},\bm{z}^{*}$ is a feasible solution to

$\displaystyle\text{Dual}^{\prime}_{\mathcal{I}}=\min\leavevmode\nobreak\
\leavevmode\nobreak$
$\displaystyle\bm{\alpha}^{\top}\bm{y}+(1-\gamma)\cdot\bm{\mu}^{\top}\bm{z}$
(79) s.t.
$\displaystyle(C(:,\mathcal{I}))^{\top}\bm{y}+(B(:,\mathcal{I}))^{\top}\bm{z}=\hat{\bm{r}}(\mathcal{I})$
$\displaystyle\bm{y}\geq 0,\bm{z}\geq-\infty,$

which implies that

$\text{Dual}^{\prime}_{\mathcal{I}}\leq\text{Dual}_{\mathcal{I}}.$

On the other hand, any feasible solution to
$\text{Dual}^{\prime}_{\mathcal{I}}$ must be a feasible solution to
$\text{Dual}_{\mathcal{I}}$, and we have

$\text{Dual}^{\prime}_{\mathcal{I}}\geq\text{Dual}_{\mathcal{I}}.$

Therefore, we must have
$\text{Dual}^{\prime}_{\mathcal{I}}=\text{Dual}_{\mathcal{I}}$ and our proof
is completed. $\Halmos$

##  11 Proof of Lemma 6.2

Note that the distribution of $\bm{q}^{n}$ is independent of the distribution
of $\bm{r}^{n}$. We know that

$\displaystyle\mathbb{E}\left[\sum_{n=1}^{N}(\bm{r}^{n})^{\top}\bm{q}^{n}\right]=\sum_{n=1}^{N}(\hat{\bm{r}})^{\top}\mathbb{E}[\bm{q}^{n}]=\sum_{n=1}^{N}(\hat{\bm{r}}_{\mathcal{I}^{*}})^{\top}\mathbb{E}\left[\bm{q}^{n}_{\mathcal{I}^{*}}\right]$

Denote by $\bm{q}^{*}$ and $\bm{y}^{*},\bm{z}^{*}$ the optimal primal-dual
variable corresponding to the optimal basis $\mathcal{I}^{*}$ and
$\mathcal{J}^{*}$. From the complementary slackness condition and noting that
$\bm{q}^{*}_{\mathcal{I}^{*}}>0$, we know that

$(C(\mathcal{J}^{*},\mathcal{I}^{*}))^{\top}\bm{y}_{\mathcal{J}^{*}}^{*}+(B(:,\mathcal{I}^{*}))^{\top}\bm{z}^{*}=\hat{\bm{r}}_{\mathcal{I}^{*}}.$
(80)

Also, we can define a matrix $C^{n}(\mathcal{J}^{*},\mathcal{I}^{*})$ such
that the element of $C^{n}(\mathcal{J}^{*},\mathcal{I}^{*})$ at the
$k\in\mathcal{J}^{*}$ row and $(s,a)\in\mathcal{I}^{*}$ column is
$c^{n}_{k}(s,a)$. We can also define a matrix $B^{n}(:,\mathcal{I}^{*})$ such
that the element of $B^{n}(:,\mathcal{I}^{*})$ at the
$s^{\prime}\in\mathcal{S}$ row and $(s,a)\in\mathcal{I}^{*}$ column is
$\delta_{s^{\prime},s}-\gamma\cdot\mathbbm{1}_{\\{s^{\prime}=s^{n}(s,a)\\}}$.
It is easy to see that

$\mathbb{E}[C^{n}(\mathcal{J}^{*},\mathcal{I}^{*})]=C(\mathcal{J}^{*},\mathcal{I}^{*})\text{\leavevmode\nobreak\
and\leavevmode\nobreak\
}\mathbb{E}[B^{n}(:,\mathcal{I}^{*})]=B(:,\mathcal{I}^{*}).$

Then, it holds that

$\displaystyle\sum_{n=1}^{N}(\hat{\bm{r}}_{\mathcal{I}^{*}})^{\top}\mathbb{E}\left[\bm{q}^{n}_{\mathcal{I}^{*}}\right]$
$\displaystyle=\sum_{n=1}^{N}\left((C(\mathcal{J}^{*},\mathcal{I}^{*}))^{\top}\bm{y}_{\mathcal{J}^{*}}^{*}+(B(:,\mathcal{I}^{*}))^{\top}\bm{z}^{*}\right)^{\top}\mathbb{E}[\bm{q}^{n}_{\mathcal{I}^{*}}]$
(81)
$\displaystyle=\mathbb{E}\left[\sum_{n=1}^{N}\left((C^{n}(\mathcal{J}^{*},\mathcal{I}^{*}))^{\top}\bm{y}_{\mathcal{J}^{*}}^{*}+(B^{n}(:,\mathcal{I}^{*}))^{\top}\bm{z}^{*}\right)^{\top}\bm{q}^{n}_{\mathcal{I}^{*}}\right]$
$\displaystyle=\mathbb{E}\left[\sum_{n=1}^{N}\left((\bm{y}^{*})^{\top}(C^{n}(\mathcal{J}^{*},\mathcal{I}^{*}))\bm{q}^{n}_{\mathcal{I}^{*}}+(\bm{z}^{*})^{\top}(B^{n}(:,\mathcal{I}^{*}))\bm{q}^{n}_{\mathcal{I}^{*}}\right)\right]$

Note that we have

$\sum_{n=1}^{N}C^{n}(\mathcal{J}^{*},\mathcal{I}^{*}))\bm{q}^{n}_{\mathcal{I}^{*}}=\bm{\alpha}^{1}_{\mathcal{J}^{*}}-\bm{\alpha}^{N}$
(82)

and

$\sum_{n=1}^{N}B^{n}(:,\mathcal{I}^{*}))\bm{q}^{n}_{\mathcal{I}^{*}}=\bm{\mu}^{1}-\bm{\mu}^{N}.$
(83)

Plugging (82) and (83) back into (81), we get that

$\sum_{n=1}^{N}(\hat{\bm{r}}_{\mathcal{I}^{*}})^{\top}\mathbb{E}\left[\bm{q}^{n}_{\mathcal{I}^{*}}\right]=(\bm{y}_{\mathcal{J}^{*}}^{*})^{\top}\bm{\alpha}^{1}_{\mathcal{J}^{*}}+(\bm{z}^{*})^{\top}\bm{\mu}^{1}-(\bm{y}_{\mathcal{J}^{*}}^{*})^{\top}\mathbb{E}\left[\bm{\alpha}^{N}_{\mathcal{J}^{*}}\right]-(\bm{z}^{*})\top\mathbb{E}\left[\bm{\mu}^{N}\right].$

Note that

$V_{r}(\pi^{*},\mu_{1})=(\bm{y}_{\mathcal{J}^{*}}^{*})^{\top}\bm{\alpha}^{1}_{\mathcal{J}^{*}}+(\bm{z}^{*})^{\top}\bm{\mu}^{1}$

that holds from the strong duality of $V^{\mathrm{Infi}}$ (6). Then, we have
that

$\displaystyle N\cdot
V_{r}(\pi^{*},\mu_{1})-\sum_{n=1}^{N}(\hat{\bm{r}})^{\top}\mathbb{E}[\bm{q}^{n}]\leq(\bm{y}_{\mathcal{J}^{*}}^{*})^{\top}\mathbb{E}\left[\bm{\alpha}^{N}_{\mathcal{J}^{*}}\right]+(\bm{z}^{*})^{\top}\mathbb{E}\left[\bm{\mu}^{N}\right].$
(84)

Our proof is thus completed.

##  12 Proof of Theorem 6.3

We now condition on the event that $|\bar{r}_{n}(s,a)-\hat{r}(s,a)|$,
$|\bar{c}_{k,n}(s,a)-\hat{c}_{k}(s,a)|$, and
$|\bar{P}_{n}(s^{\prime}|s,a)-P(s^{\prime}|s,a)|$ for each $k\in[K]$,
$(s,a)\in\mathcal{S}\times\mathcal{A}$ and $s^{\prime}\in\mathcal{S}$ are all
bounded by $\mathrm{Rad}(n,\varepsilon)$, for any $n\in[N]$. We know that this
event happens with probability at least
$1-N\cdot(K|\mathcal{S}||\mathcal{A}|-|\mathcal{S}|^{2}|\mathcal{A}|)\cdot\varepsilon$.
From now on, we set $\varepsilon=\frac{1}{N^{2}}$ to guarantee that the event
happens with probability at least
$1-\frac{K|\mathcal{S}||\mathcal{A}|+|\mathcal{S}|^{2}|\mathcal{A}|}{N}$.

We consider the stochastic process $\tilde{\alpha}_{k}(n)$ and
$\tilde{\mu}_{s}(n)$ defined in (30). For a fixed $\nu>0$ which we specify
later, we define a set

$\mathcal{X}=\\{\bm{\alpha}^{\prime}\in\mathbb{R}^{|\mathcal{J}^{*}|}:\alpha^{\prime}_{k}\in[\alpha_{k}-\nu,\alpha_{k}+\nu],\forall
k\in\mathcal{J}^{*}\\},$ (85)

and

$\mathcal{Y}=\\{\bm{\mu}^{\prime}\in\mathbb{R}^{|\mathcal{S}|}:\mu^{\prime}_{s}\in[\mu_{s}-\nu,\mu_{s}+\nu],\forall
s\in\mathcal{S}\\}.$ (86)

It is easy to see that initially, $\tilde{\bm{\alpha}}(1)\in\mathcal{X}$ and
$\tilde{\bm{\mu}}(1)\in\mathcal{Y}$. We show that $\tilde{\bm{\alpha}}(n)$ and
$\tilde{\bm{\mu}}(n)$ behave well as long as they stay in the region
$\mathcal{X}$ and $\mathcal{Y}$ for a sufficiently long time. To this end, we
define a stopping time

$\tau=\min_{n\in[N]}\\{\tilde{\bm{\alpha}}(n)\notin\mathcal{X}\text{\leavevmode\nobreak\
or\leavevmode\nobreak\ }\tilde{\bm{\mu}}(n)\notin\mathcal{Y}\\}.$ (87)

Note that in Algorithm 2, to stop $\bm{q}^{n}$ from behaving ill when $n$ is
small, we project it to a set that guarantees $\|\bm{q}^{n}\|_{1}\leq 2$. We
now show in the following lemma that when $n$ is large enough but smaller than
the stopping time $\tau$, there is no need to do projection.

###### Lemma 12.1

There exist two constants $N^{\prime}_{0}$ and $\nu_{0}$. When
$\max\\{N_{0},N_{0}^{\prime}\\}\leq n\leq\tau$, and $\nu\leq\nu_{0}$, it holds
that $\|\tilde{\bm{q}}_{\mathcal{I}^{*}}^{n}\|_{1}\leq 2$, where
$\tilde{\bm{q}}_{\mathcal{I}^{*}}^{n}$ denotes the solution to the linear
equations (23). Specifically, $N_{0}$ is given in (26) and $N_{0}^{\prime}$ is
given as follows

$N_{0}^{\prime}=16\cdot\frac{(|\mathcal{S}|+K)^{2}}{\sigma^{2}}\cdot\log(1/\varepsilon)$
(88)

Also, $\nu_{0}$ is given as follows

$\nu_{0}:=16\cdot\frac{\sigma\cdot(1-\gamma)}{(|\mathcal{S}|+K)^{2}}.$ (89)

We set $\nu$ satisfy the condition $\nu\leq\nu_{0}$ with $\nu_{0}$ satisfies
the condition in Lemma 12.1. We bound $\mathbb{E}[N-\tau]$ in the following
lemma.

###### Lemma 12.2

Let the stopping time $\tau$ be defined in (87). It holds that

$\mathbb{E}[N-\tau]\leq\max\\{N_{0},N_{0}^{\prime}\\}+2(K+|\mathcal{S}|)\cdot\exp(-\nu^{2}/8)$

where $N_{0}$ is given in (26) and $N_{0}^{\prime}$ is given in (88), as long
as

$N\geq\max\\{N_{0},N_{0}^{\prime}\\}\text{\leavevmode\nobreak\
\leavevmode\nobreak\ and\leavevmode\nobreak\ \leavevmode\nobreak\
}N\geq\frac{8}{\nu^{2}}\geq\frac{8}{\nu^{2}_{0}}=\frac{(|\mathcal{S}|+K)^{4}}{32\sigma^{2}\cdot(1-\gamma)^{2}}.$
(90)

Also, for any $N^{\prime}$ such that $\max\\{N_{0},N_{0}^{\prime}\\}\leq
N^{\prime}\leq N$, it holds that

$P(\tau\leq
N^{\prime})\leq\frac{(K+|\mathcal{S}|)\cdot\nu^{2}}{4}\cdot\exp\left(-\frac{\nu^{2}\cdot(N-N^{\prime}+1)}{8}\right).$
(91)

From the definition of the stopping time $\tau$ in (87), we know that for each
$k\in\mathcal{J}^{*}$, it holds

$\alpha_{k}^{\tau-1}\in[(N-\tau+1)\cdot(\alpha_{k}-\nu),(N-\tau+1)\cdot(\alpha_{k}+\nu)]$

Thus, we have that

$|\alpha_{k}^{N}|\leq|\alpha_{k}^{\tau-1}|+\sum_{t=\tau}^{N}\sum_{(s,a)\in\mathcal{I}^{*}}c_{k}^{n}(s,a)\cdot
q^{n}(s,a)$ (92)

and thus

$\left|\mathbb{E}[\alpha_{k}^{N}]\right|\leq 4\mathbb{E}[N-\tau]\leq
4\max\\{N_{0},N_{0}^{\prime}\\}+8(K+|\mathcal{S}|)\cdot\exp(-\nu^{2}/8).$ (93)

Following the same procedure, we can show that for each $s\in\mathcal{S}$, it
holds that

$\left|\mathbb{E}[\mu^{N}(s)]\right|\leq 4\mathbb{E}[N-\tau]\leq
4\max\\{N_{0},N_{0}^{\prime}\\}+8(K+|\mathcal{S}|)\cdot\exp(-\nu^{2}/8).$ (94)

We finally consider the other constraints $k\in\mathcal{J}^{*c}$. Note that
following the definition of $\bm{\alpha}^{n}$ and $\bm{\mu}^{n}$, we have that

$A^{*}\cdot\left(\sum_{n=1}^{N}\mathbb{E}[\bm{q}^{n}_{\mathcal{I}^{*}}]\right)=[\bm{\alpha}_{\mathcal{J}^{*}}^{1}-\mathbb{E}\left[\bm{\alpha}^{N}_{\mathcal{J}^{*}}\right];\bm{\mu}^{1}-\mathbb{E}\left[\bm{\mu}^{N}\right]].$
(95)

Also, from the bindingness of $\bm{q}^{*}$ regarding the optimal basis
$\mathcal{I}^{*}$ and $\mathcal{J}^{*}$, we have

$N\cdot
A^{*}\cdot\bm{q}^{*}_{\mathcal{I}^{*}}=[\bm{\alpha}^{1}_{\mathcal{J}^{*}};\bm{\mu}^{1}].$
(96)

Therefore, it holds that

$\sum_{n=1}^{N}\mathbb{E}\left[\bm{q}^{n}_{\mathcal{I}^{*}}\right]=N\cdot\bm{q}^{*}_{\mathcal{I}^{*}}-(A^{*})^{-1}\cdot\left[\mathbb{E}\left[\bm{\alpha}_{\mathcal{J}^{*}}^{N}\right];\mathbb{E}\left[\bm{\mu}^{N}\right]\right],$
(97)

and

$\left\|\sum_{n=1}^{N}\mathbb{E}\left[\bm{q}^{n}_{\mathcal{I}^{*c}}\right]\right\|_{1}\leq
2N_{0}.$ (98)

Finally, for any $k\in\mathcal{J}^{*c}$, we have

$\displaystyle(\hat{\bm{c}}_{k})^{\top}\left(\sum_{n=1}^{N}\mathbb{E}\left[\bm{q}^{n}\right]\right)$
$\displaystyle=N\cdot(\hat{\bm{c}}_{k})^{\top}\bm{q}^{*}_{\mathcal{I}^{*}}-(\hat{\bm{c}}_{k})^{\top}\cdot(A^{*})^{-1}\cdot\left[\mathbb{E}\left[\bm{\alpha}_{\mathcal{J}^{*}}^{N}\right];\mathbb{E}\left[\bm{\mu}^{N}\right]\right]+2N_{0}$
(99)
$\displaystyle=N\cdot(\hat{\bm{c}}_{k})^{\top}\bm{q}^{*}-(\hat{\bm{c}}_{k})^{\top}\cdot(A^{*})^{-1}\cdot\left[\mathbb{E}\left[\bm{\alpha}_{\mathcal{J}^{*}}^{N}\right];\mathbb{E}\left[\bm{\mu}^{N}\right]\right]+2N_{0}$

From the feasibility of $\bm{q}^{*}$, we know that

$N\cdot\alpha_{k}\geq N\cdot(\hat{\bm{c}}_{k})^{\top}\bm{q}^{*}.$

Therefore, for any $k\in\mathcal{J}^{*c}$, it holds that

$\displaystyle
N\cdot\alpha_{k}-\sum_{n=1}^{N}\hat{\bm{c}}_{k}^{\top}\mathbb{E}\left[\bm{q}^{n}\right]$
$\displaystyle\leq(\hat{\bm{c}}_{k})^{\top}\cdot(A^{*})^{-1}\cdot\left[\mathbb{E}[\bm{\alpha}_{\mathcal{J}^{*}}^{N}];\mathbb{E}[\bm{\mu}^{N}]\right]+2N_{0}$
(100)
$\displaystyle\leq\frac{K+|\mathcal{S}|}{\sigma}\cdot\left(4\max\\{N_{0},N_{0}^{\prime}\\}+8(K+|\mathcal{S}|)\cdot\exp(-\nu^{2}/8)\right)+2N_{0}.$

Moreover, the definition of $\sigma$ in (28) implies that following upper
bound on the norm of the dual variable $\bm{y}^{*}$ and $\bm{z}^{*}$.

$\|\bm{y}^{*}\|_{1}+\|\bm{z}^{*}\|_{1}=\|(A^{*\top})^{-1}\cdot\hat{\bm{r}}_{\mathcal{J}^{*}}\|_{1}\leq\frac{|\mathcal{S}|+K}{\sigma}.$
(101)

Therefore, we know that the regret over the reward and the regret over the
constraint violation can all be bounded by using (93), (94), and (100). We
present the bounds as follows.

$N\cdot
V_{r}(\pi^{*},\mu_{1})-\sum_{n=1}^{N}\hat{\bm{r}}^{\top}\mathbb{E}[\bm{q}^{n}]\leq\frac{K+|\mathcal{S}|}{\sigma}\cdot\left(4\max\\{N_{0},N_{0}^{\prime}\\}+8(K+|\mathcal{S}|)\cdot\exp(-\nu^{2}/8)\right).$
(102)

Meanwhile, the constraint violations are bounded by (93), (94), and (100). Our
proof is thus completed.

###  12.1 Proof of Lemma 12.1

Denote by $\bm{q}^{*}$ the optimal solution corresponding to the optimal basis
$\mathcal{I}^{*}$ and $\mathcal{J}^{*}$. Then, it holds that

$\left[\begin{aligned} &C(\mathcal{J}^{*},\mathcal{I}^{*})\\\
&B(:,\mathcal{I}^{*})\end{aligned}\right]\cdot\bm{q}^{*}_{\mathcal{I}^{*}}=\left[\begin{aligned}
&\bm{\alpha}_{\mathcal{J}^{*}}\\\ &\bm{\mu}\end{aligned}\right].$ (103)

We compare $\tilde{\bm{q}}^{n}_{\mathcal{I}^{*}}$ with
$\bm{q}^{*}_{\mathcal{I}^{*}}$ when $n$ large enough. Note that when $n\geq
N_{0}$, $\tilde{\bm{q}}^{n}$ is the solution to the following linear equations

$\left[\begin{aligned} &\bar{C}^{n}(\mathcal{J}^{*},\mathcal{I}^{*})\\\
&\bar{B}^{n}(:,\mathcal{I}^{*})\end{aligned}\right]\cdot\tilde{\bm{q}}^{n}_{\mathcal{I}^{*}}=\left[\begin{aligned}
&\frac{\bm{\alpha}^{n}_{\mathcal{J}^{*}}}{N-n+1}\\\
&\frac{\bm{\mu}^{n}}{N-n+1}\end{aligned}\right].$ (104)

When $n\leq\tau$, we know that

$\left|\bm{\alpha}_{\mathcal{J}^{*}}-\frac{\bm{\alpha}^{n}_{\mathcal{J}^{*}}}{N-n+1}\right|\leq\nu$
(105)

and

$\left|\bm{\mu}-\frac{\bm{\mu}^{n}}{N-n+1}\right|\leq\nu.$ (106)

Moreover, we know that the absolute value of each element of
$\bar{C}^{n}(\mathcal{J}^{*},\mathcal{I}^{*})-C(\mathcal{J}^{*},\mathcal{I}^{*})$,
and $\bar{B}^{n}(:,\mathcal{I}^{*})-B(:,\mathcal{I}^{*})$ is upper bounded by
$\mathrm{Rad}(n,\varepsilon)$. We now bound the distance between the solutions
to the linear equations (103) and (104). The perturbation of the matrix is
denoted as

$\Delta A^{*}=\left[\begin{aligned}
&C(\mathcal{J}^{*},\mathcal{I}^{*})-\bar{C}^{n}(\mathcal{J}^{*},\mathcal{I}^{*})\\\
&B(:,\mathcal{I}^{*})-\bar{B}(:,\mathcal{I}^{*})\end{aligned}\right].$

Clearly, it holds that

$\|\Delta A^{*}\|_{1}\leq\mathrm{Rad}(n,\varepsilon)\cdot(K+|\mathcal{S}|).$
(107)

Therefore, as long as

$\|\Delta
A^{*}\|_{1}\leq\mathrm{Rad}(n,\varepsilon)\cdot(K+|\mathcal{S}|)\leq\frac{1}{2\|(A^{*})^{-1}\|_{1}}\leq\frac{1}{2\sigma},$
(108)

following standard perturbation analysis of linear equations [Higham, 2002],
we have that

$\displaystyle\frac{\|\tilde{\bm{q}}^{n}_{\mathcal{I}^{*}}-\bm{q}^{*}_{\mathcal{I}^{*}}\|_{1}}{\|\bm{q}^{*}_{\mathcal{I}^{*}}\|_{1}}$
$\displaystyle\leq\frac{\kappa(A^{*})}{1-\kappa(A^{*})\cdot\frac{\|\Delta
A^{*}\|_{1}}{\|A^{*}\|_{1}}}\cdot\left(\frac{\|\Delta
A^{*}\|_{1}}{\|A^{*}\|_{1}}+\frac{(|\mathcal{S}+K|\cdot\nu)}{\|[\bm{\alpha}_{\mathcal{J}^{*}};\bm{\mu}]\|_{1}}\right)$
(109) $\displaystyle\leq 2\cdot\kappa(A^{*})\cdot\left(\frac{\|\Delta
A^{*}\|_{1}}{\|A^{*}\|_{1}}+\frac{(|\mathcal{S}+K|\cdot\nu)}{\|[\bm{\alpha}_{\mathcal{J}^{*}};\bm{\mu}]\|_{1}}\right)$
$\displaystyle\leq 2\cdot\kappa(A^{*})\cdot\left(\frac{\|\Delta
A^{*}\|_{1}}{\|A^{*}\|_{1}}+\frac{(|\mathcal{S}|+K))\cdot\nu}{1-\gamma}\right),$

where $\kappa(A^{*})=\|A^{*}\|_{1}\cdot\|(A^{*})^{-1}\|_{1}$ denotes the
conditional number of $A^{*}$. The last inequality follows from
$\|[\bm{\alpha}_{\mathcal{J}^{*}};\bm{\mu}]\|_{1}\geq 1-\gamma$. Further, note
that $\|\bm{q}^{*}_{\mathcal{I}^{*}}\|_{1}=1$. Therefore, in order to satisfy
the condition $\|\tilde{\bm{q}}^{n}_{\mathcal{I}^{*}}\|_{1}\leq 2$, we only
need the right hand side of (109) to be upper bounded by 1. Clearly, as long
as $n$ satisfies the condition (108) and the following condition

$2\cdot\kappa(A^{*})\cdot\frac{\|\Delta A^{*}\|_{1}}{\|A\|_{1}}\leq
2\cdot\frac{\mathrm{Rad}(n,\varepsilon)\cdot(K+|\mathcal{S}|)}{\sigma}\leq\frac{1}{2},$
(110)

we only need to select a $\nu$ such that

$2\cdot\kappa(A^{*})\cdot\frac{(|\mathcal{S}|+K)\cdot\nu}{1-\gamma}\leq\frac{1}{2}.$
(111)

Combining (108) and (110), we know that $n$ needs to satisfy the following
conditions: $n\geq N_{0}$ and

$n\geq
N^{\prime}_{0}:=16\cdot\frac{(|\mathcal{S}|+K)^{2}}{\sigma^{2}}\cdot\log(1/\varepsilon).$
(112)

Also, $\nu$ is selected to satisfy the following condiont

$\nu\leq\nu_{0}:=16\cdot\frac{\sigma\cdot(1-\gamma)}{(|\mathcal{S}|+K)^{2}}.$
(113)

Our proof is thus completed.

###  12.2 Proof of Lemma 12.2

Now we fix a $k\in\mathcal{J}^{*}$. We specify a
$\bar{N}_{0}=\max\\{N_{0},N_{0}^{\prime}\\}$. For any $\bar{N}_{0}\leq
N^{\prime}\leq N$, it holds that

$\tilde{\alpha}_{k}(N^{\prime})-\tilde{\alpha}_{k}(\bar{N}_{0})=\sum_{n=\bar{N}_{0}}^{N^{\prime}-1}(\tilde{\alpha}_{k}(n+1)-\tilde{\alpha}_{k}(n)).$

We define $\xi_{k}(n)=\tilde{\alpha}_{k}(n+1)-\tilde{\alpha}_{k}(n)$. Then, we
have

$\tilde{\alpha}_{k}(N^{\prime})-\tilde{\alpha}_{k}(\bar{N}_{0})=\sum_{n=\bar{N}_{0}}^{N^{\prime}-1}(\xi_{k}(n)-\mathbb{E}[\xi_{k}(n)|\mathcal{F}_{n}])+\sum_{n=\bar{N}_{0}}^{N^{\prime}-1}\mathbb{E}[\xi_{k}(n)|\mathcal{F}_{n}].$

where $\mathcal{F}_{n}$ denotes the filtration of information up to step $n$.
Note that due to the update in (31), we have

$\xi_{k}(n)=\frac{\tilde{\alpha}_{k}(n)-\sum_{(s,a)\in\mathcal{I}^{*}}c_{k}^{n}(s,a)\cdot
q^{n}(s,a)}{N-n-1}.$

Then, it holds that

$|\xi_{k}(n)-\mathbb{E}[\xi_{k}(n)|\mathcal{F}_{n}]|\leq\frac{2}{N-n+1}$ (114)

where the inequality follows from the fact that the value of
$\tilde{\alpha}_{k}(n)$ is deterministic given the filtration
$\mathcal{F}_{n}$ and $\|\bm{q}^{n}\|_{1}\leq 2$ for any $n$. Note that

$\\{\xi_{k}(n)-\mathbb{E}[\xi_{k}(n)|\mathcal{F}_{n}]\\}_{\forall
n=\bar{N}_{0},\dots,N^{\prime}}$

forms a martingale difference sequence. Following Hoeffding’s inequality, for
any $N^{\prime\prime}\leq N^{\prime}$ and any $b>0$, it holds that

$\displaystyle
P\left(\left|\sum_{n=\bar{N}_{0}}^{N^{\prime\prime}}(\xi_{k}(n)-\mathbb{E}[\xi_{k}(n)|\mathcal{F}_{n}])\right|\geq
b\right)$ $\displaystyle\leq
2\exp\left(-\frac{b^{2}}{2\cdot\sum_{n=\bar{N}_{0}}^{N^{\prime\prime}}1/(N-n+1)^{2}}\right)$
$\displaystyle\leq
2\exp\left(-\frac{b^{2}\cdot(N-N^{\prime\prime}+1)}{2}\right).$

Therefore, we have that

$\displaystyle
P\left(\left|\sum_{n=\bar{N}_{0}}^{N^{\prime\prime}}(\xi_{k}(n)-\mathbb{E}[\xi_{k}(n)|\mathcal{F}_{n}])\right|\geq
b\text{\leavevmode\nobreak\ for\leavevmode\nobreak\ some\leavevmode\nobreak\
}\bar{N}_{0}\leq N^{\prime\prime}\leq N^{\prime}\right)$ (115)
$\displaystyle\leq$
$\displaystyle\sum_{N^{\prime\prime}=\bar{N}_{0}}^{N^{\prime}}2\exp\left(-\frac{b^{2}\cdot(N-N^{\prime\prime}+1)}{2}\right)\leq
b^{2}\cdot\exp\left(-\frac{b^{2}\cdot(N-N^{\prime}+1)}{2}\right)$

holds for any $b>0$.

We now bound the probability that $\tau>N^{\prime}$ for one particular
$N^{\prime}$ such that $\bar{N}_{0}\leq N^{\prime}\leq N$. Suppose that
$N^{\prime}\leq\tau$, then, from Lemma 12.1, for each $n\leq N^{\prime}$, we
know that $\|\tilde{\bm{q}}^{n}\|_{1}\leq 2$ and therefore
$\bm{q}^{n}=\tilde{\bm{q}}^{n}$ as the solution to (23). We have

$\tilde{\alpha}_{k}(n)=\sum_{(s,a)\in\mathcal{I}^{*}}\bar{c}_{k,n}(s,a)\cdot
q^{n}(s,a).$

It holds that

$\left|\mathbb{E}[\xi_{k}(n)|\mathcal{F}_{n}]\right|\leq\frac{1}{N-n+1}\cdot\sum_{(s,a)\in\mathcal{I}^{*}}q^{n}(s,a)\cdot\left|\mathbb{E}[\bar{c}_{k,n}(s,a)]-\hat{c}_{k}^{n}(s,a)\right|\leq\frac{2\mathrm{Rad}(n,\varepsilon)}{N-n+1}.$
(116)

Then, we know that

$\displaystyle\sum_{n=\bar{N}_{0}}^{N^{\prime}-1}\left|\mathbb{E}[\xi_{k}(n)|\mathcal{F}_{n}]\right|$
$\displaystyle\leq\sqrt{\frac{\log(2/\varepsilon)}{2}}\cdot\sum_{n=\bar{N}_{0}}^{N^{\prime}-1}\frac{1}{\sqrt{n}\cdot(N-n)}\leq\sqrt{\frac{\log(2/\varepsilon)}{2}}\cdot\sqrt{N^{\prime}-1}\cdot\sum_{n=\bar{N}_{0}}^{N^{\prime}-1}\frac{1}{n\cdot(N-n)}$
(117)
$\displaystyle=\sqrt{\frac{\log(2/\varepsilon)}{2}}\cdot\frac{\sqrt{N^{\prime}-1}}{N}\cdot\sum_{n=\bar{N}_{0}}^{N^{\prime}-1}\left(\frac{1}{n}+\frac{1}{N-n}\right)$
$\displaystyle\leq\sqrt{2\log(2/\varepsilon)}\cdot\frac{\sqrt{N^{\prime}-1}}{N}\cdot\log(N)\leq\frac{\sqrt{2\log(2/\varepsilon)}}{\sqrt{N}}\cdot\log(N)\leq\frac{\nu}{2}$

for a $N$ large enough such that

$N\geq\frac{8}{\nu^{2}}\geq\frac{8}{\nu^{2}_{0}}=\frac{(|\mathcal{S}|+K)^{4}}{32\sigma^{2}\cdot(1-\gamma)^{2}}$
(118)

Combining (117) and (115) with $b=\nu/2$, and apply a union bound over all
$k\in\mathcal{J}^{*}$ and $s\in\mathcal{S}$, we know that

$P(\tau\leq
N^{\prime})\leq\frac{(K+|\mathcal{S}|)\cdot\nu^{2}}{4}\cdot\exp\left(-\frac{\nu^{2}\cdot(N-N^{\prime}+1)}{8}\right).$
(119)

Therefore, we know that

$\mathbb{E}[N-\tau]=\sum_{N^{\prime}=1}^{N}P(\tau\leq
N^{\prime})\leq\bar{N}_{0}+\sum_{N^{\prime}=\bar{N}_{0}}^{N}P(\tau\leq
N^{\prime})\leq\bar{N}_{0}+2(K+|\mathcal{S}|)\cdot\exp(-\nu^{2}/8)$

which completes our proof.

##  13 Proof of Theorem 6.4

Note that in the proof of Theorem 6.3, we have shown the following bounds.

$\left|\mathbb{E}[\alpha_{k}^{N}]\right|\leq 4\mathbb{E}[N-\tau]\leq
4\max\\{N_{0},N_{0}^{\prime}\\}+8(K+|\mathcal{S}|)\cdot\exp(-\nu^{2}/8).$
(120)

holds for the each $k\in\mathcal{J}^{*}$. For each $s\in\mathcal{S}$, it holds
that

$\left|\mathbb{E}[\mu^{N}(s)]\right|\leq 4\mathbb{E}[N-\tau]\leq
4\max\\{N_{0},N_{0}^{\prime}\\}+8(K+|\mathcal{S}|)\cdot\exp(-\nu^{2}/8).$
(121)

The caveat of directly transferring the bound of (120) and (121) into the
regret bounds (3) of the policy $\bar{\pi}^{N}$ is that, the vector
$\bar{\bm{q}}^{N}$ does not directly characterize an occupancy measure. This
point can be seen by noting that there is a gap between $B\bar{\bm{q}}^{N}$
and $\bm{\mu}$, though bounded by $O(\log(N)/N)$ by setting
$\varepsilon=1/N^{2}$. However, we can show that the gap between
$\bar{\bm{q}}^{N}$ and $\bm{q}^{*}$ is upper bounded by $O(\log(N)/N)$, which
implies a bound over the gap between the policy $\bar{\pi}^{N}$ and the
optimal policy $\pi^{*}$ that corresponds to the occupancy measure
$\bm{q}^{*}$. This bound over the gap between the policy distributions can be
then transferred into the bound over the gap between the state-value functions
under the policy $\bar{\pi}^{N}$ and $\pi^{*}$. The regret bounds can be
obtained then.

We first bound the gap between $\bar{\bm{q}}^{N}$ and $\bm{q}^{*}$. Note that
as long as $n\geq N_{0}$, we have $\mathcal{I}_{n}=\mathcal{I}^{*}$ following
Theorem 6.1. Then, by noting $\mathcal{I}_{N}=\mathcal{I}^{*}$, we know that

$\bar{\bm{q}}^{N}_{\mathcal{I}^{*c}}=\bm{q}^{*}_{\mathcal{I}^{*c}}.$ (122)

Also, note that following the definition of $\bm{\alpha}^{n}$ and
$\bm{\mu}^{n}$, we have that

$A^{*}\cdot\left(\sum_{n=1}^{N}\mathbb{E}[\bm{q}^{n}_{\mathcal{I}^{*}}]\right)=[\bm{\alpha}_{\mathcal{J}^{*}}^{1}-\mathbb{E}\left[\bm{\alpha}^{N}_{\mathcal{J}^{*}}\right];\bm{\mu}^{1}-\mathbb{E}\left[\bm{\mu}^{N}\right]].$
(123)

Also, from the bindingness of $\bm{q}^{*}$ regarding the optimal basis
$\mathcal{I}^{*}$ and $\mathcal{J}^{*}$, we have

$N\cdot
A^{*}\cdot\bm{q}^{*}_{\mathcal{I}^{*}}=[\bm{\alpha}^{1}_{\mathcal{J}^{*}};\bm{\mu}^{1}].$
(124)

Then, from (123) and (124), we know that

$\displaystyle\left\|\mathbb{E}\left[\bar{\bm{q}}^{N}_{\mathcal{I}^{*}}\right]-\bm{q}^{*}_{\mathcal{I}^{*}}\right\|_{\infty}$
$\displaystyle=\left\|\bm{q}^{*}_{\mathcal{I}^{*}}-\frac{1}{N}\cdot\sum_{n=1}^{N}\mathbb{E}\left[\bm{q}^{n}_{\mathcal{I}^{*}}\right]\right\|_{\infty}=\frac{\left\|(A^{*})^{-1}\cdot\left[\mathbb{E}\left[\bm{\alpha}^{N}_{\mathcal{J}^{*}}\right];\mathbb{E}\left[\bm{\mu}^{N}\right]\right]\right\|_{\infty}}{N}\leq\frac{\left\|\left[\mathbb{E}\left[\bm{\alpha}^{N}_{\mathcal{J}^{*}}\right];\mathbb{E}\left[\bm{\mu}^{N}\right]\right]\right\|_{\infty}}{\sigma\cdot
N}$ (125) $\displaystyle\leq\frac{1}{\sigma\cdot
N}\cdot\left(4\max\\{N_{0},N_{0}^{\prime}\\}+8(K+|\mathcal{S}|)\cdot\exp(-\nu^{2}/8)\right).$

From Markov’s inequality, for each $i\in\mathcal{I}^{*}$ and any $a>0$, we
know that

$P\left(|\bar{\bm{q}}^{N}_{i}-\bm{q}^{*}_{i}|>g\right)\leq\frac{1}{g\cdot\sigma\cdot
N}\cdot\left(4\max\\{N_{0},N_{0}^{\prime}\\}+8(K+|\mathcal{S}|)\cdot\exp(-\nu^{2}/8)\right).$
(126)

We denote by

$\xi=\min_{(s,a)\in\mathcal{I}^{*}}\left\\{q^{*}(s,a)\right\\}.$ (127)

The policy $\bar{\pi}^{N}$ is essentially random by noting that $\bm{q}^{N}$
is a random variable, where the randomness comes from the randomness of the
filtration $\mathcal{F}_{N}$. For each $s\in\mathcal{S}$ and
$a\in\mathcal{A}$, we denote by $\bar{\pi}(a|s)$ the (ex-ante) probability
that the random policy $\bar{\pi}$ takes the action $a$ given the state $s$.
Then, for any $0<g\leq\xi/2$, we note that

$|\bm{q}^{N}_{i}-\bm{q}^{*}_{i}|\leq g\text{\leavevmode\nobreak\
for\leavevmode\nobreak\ each\leavevmode\nobreak\
}i=(s,a)\in\mathcal{I}^{*}\text{\leavevmode\nobreak\
implies\leavevmode\nobreak\ that\leavevmode\nobreak\
}\left|\frac{\bm{q}^{N}(s,a)}{\sum_{a^{\prime}\in\mathcal{A}}\bm{q}^{N}(s,a^{\prime})}-\frac{\bm{q}^{*}(s,a)}{\sum_{a^{\prime}\in\mathcal{A}}\bm{q}^{*}(s,a^{\prime})}\right|\leq\frac{2g}{\xi},$
(128)

for each $i=(s,a)\in\mathcal{I}^{*}$. For any $0<g\leq\xi/2$, note that

$P\left(|\bm{q}^{N}_{i}-\bm{q}^{*}_{i}|\leq g\text{\leavevmode\nobreak\
for\leavevmode\nobreak\ each\leavevmode\nobreak\
}i=(s,a)\in\mathcal{I}^{*}\right)\geq
1-\frac{|\mathcal{S}|+K}{g\cdot\sigma\cdot
N}\cdot\left(4\max\\{N_{0},N_{0}^{\prime}\\}+8(K+|\mathcal{S}|)\cdot\exp(-\nu^{2}/8)\right),$
(129)

where the inequality follows from the bound (126) and the union bound over
$i\in\mathcal{I}^{*}$. Therefore, for any $0<g\leq\xi/2$ and any $(s,a)$, we
know that

$P\left(\left|\bar{\pi}^{N}(a|s)-\pi^{*}(a|s)\right|\leq\frac{2g}{\xi}\right)\geq
1-\frac{|\mathcal{S}|+K}{g\cdot\sigma\cdot
N}\cdot\left(4\max\\{N_{0},N_{0}^{\prime}\\}+8(K+|\mathcal{S}|)\cdot\exp(-\nu^{2}/8)\right).$
(130)

From the above inequality, for any $(s,a)$, we have that

$\displaystyle\left|\mathbb{E}\left[\bar{\pi}^{N}(a|s)\right]-\pi^{*}(a|s)\right|$
$\displaystyle\leq\mathbb{E}\left[\left|\bar{\pi}^{N}(a|s)-\pi^{*}(a|s)\right|\right]\leq\frac{2}{N\xi}+\frac{2}{\xi}\cdot\int_{g=\frac{1}{N}}^{\xi/2}P\left(\left|\bar{\pi}^{N}(a|s)-\pi^{*}(a|s)\right|\geq\frac{2g}{\xi}\right)dg$
(131)
$\displaystyle\leq\frac{2}{N\xi}+\frac{2(|\mathcal{S}|+K)}{\xi\cdot\sigma\cdot
N}\cdot\left(4\max\\{N_{0},N_{0}^{\prime}\\}+8(K+|\mathcal{S}|)\cdot\exp(-\nu^{2}/8)\right)\cdot\int_{g=\frac{1}{N}}^{\xi/2}\frac{dg}{g}$
$\displaystyle=\frac{2}{N\xi}+\frac{2(|\mathcal{S}|+K)}{\xi\cdot\sigma\cdot
N}\cdot\left(4\max\\{N_{0},N_{0}^{\prime}\\}+8(K+|\mathcal{S}|)\cdot\exp(-\nu^{2}/8)\right)\cdot\left(\log(N)+\log(\xi/2)\right).$

We finally transfer the bound (131) into the regret bounds of policy
$\bar{\pi}^{N}$. We use the state-value functions $V_{r}(\pi,s)$, defined for
any initial state $s$ and any policy $\pi$ as follows

$V_{r}(\pi,s)=\mathbb{E}\left[\sum_{t=0}^{\infty}\gamma^{t}\cdot
r(s_{t},a_{t})\mid s\right],$ (132)

where $(s_{t},a_{t})$ is generated according to the policy $\pi$ and the
transition kernel $P$ with the initial state $s$. Note that the value of
$V_{r}(\pi,s)$ for any $s\in\mathcal{S}$ can be obtained from solving
Bellman’s equation under policy $\pi$

$V_{r}(\pi,s)=\mathbb{E}_{a\sim\pi(\cdot|s)}\left[\hat{r}(s,a)+\gamma\cdot\mathbb{E}_{s^{\prime}\sim
P(\cdot|s,a)}[V_{r}(\pi,s^{\prime})]\right].$ (133)

We define a matrix $B^{\pi}\in\mathbb{R}^{|\mathcal{S}|\times|\mathcal{S}|}$
such that the $s$-th row $s^{\prime}$-th column element is

$B^{\pi}(s,s^{\prime})=\delta_{s,s^{\prime}}-\gamma\cdot\sum_{a\in\mathcal{A}}\pi(a|s)\cdot
P(s^{\prime}|s,a).$ (134)

Then, the matrix $B^{\pi}$ represents the state transition probability matrix
under the policy $\pi$. Denote by

$\bm{V}_{r}(\pi)=(V_{r}(\pi,s))_{\forall s\in\mathcal{S}}$

and

$\hat{\bm{r}}(\pi)=(\sum_{a\in\mathcal{A}}\pi(a|s)\cdot\hat{r}(s,a))_{\forall
s\in\mathcal{S}}.$

We have that the state values $\bm{V}_{r}(\pi)$ is the solution to the linear
equation

$B^{\pi}\bm{V}_{r}(\pi)=\hat{\bm{r}}(\pi)$ (135)

To bound the regret, we bound the solution to the linear equation (135) with
$\pi$ being $\bar{\pi}^{N}$ and $\pi^{*}$ separately. The perturbation of the
right hand of the equation (135) is

$\Delta\hat{\bm{r}}=\hat{\bm{r}}(\bar{\pi}^{N})-\hat{\bm{r}}(\pi^{*}).$

Clearly, we have that

$\|\Delta\hat{\bm{r}}\|_{\infty}\leq\frac{2}{N\xi}+\frac{2(|\mathcal{S}|+K)}{\xi\cdot\sigma\cdot
N}\cdot\left(4\max\\{N_{0},N_{0}^{\prime}\\}+8(K+|\mathcal{S}|)\cdot\exp(-\nu^{2}/8)\right)\cdot\left(\log(N)+\log(\xi/2)\right).$
(136)

The perturbation of the matrix is denoted as

$\Delta B=B^{\bar{\pi}^{N}}-B^{\pi^{*}}.$

Clearly, it holds that

$\|\Delta
B\|_{\infty}\leq\frac{2\gamma}{N\xi}+\frac{2\gamma(|\mathcal{S}|+K)}{\xi\cdot\sigma\cdot
N}\cdot\left(4\max\\{N_{0},N_{0}^{\prime}\\}+8(K+|\mathcal{S}|)\cdot\exp(-\nu^{2}/8)\right)\cdot\left(\log(N)+\log(\xi/2)\right).$
(137)

We plug the formulation of $N_{0}$ in (26) and $N^{\prime}_{0}$ in (88) into
the bound (136) and (137). We obtain

$\|\Delta\hat{\bm{r}}\|_{\infty}\leq
C_{1}\cdot\frac{(|\mathcal{S}|+K)^{3}}{\alpha^{2}\cdot\xi\cdot\sigma\cdot\min\\{\sigma^{2},(1-\gamma)^{2}\cdot\delta^{2}\\}}\cdot\frac{\log^{2}(N)}{N}$
(138)

where $C_{1}$ is a constant, $\alpha=\min_{k\in[K]}\\{\alpha_{k}\\}$, and
$\delta=\min\\{\delta_{1},\delta_{2}\\}$ with $\delta_{1}$ given in (18) and
$\delta_{2}$ given in (21). We also obtain

$\|\Delta B\|_{\infty}\leq
C_{1}\cdot\frac{\gamma\cdot(|\mathcal{S}|+K)^{3}}{\alpha^{2}\cdot\xi\cdot\sigma\cdot\min\\{\sigma^{2},(1-\gamma)^{2}\cdot\delta^{2}\\}}\cdot\frac{\log^{2}(N)}{N}$
(139)

Therefore, as long as

$C_{1}\cdot\frac{(|\mathcal{S}|+K)^{3}}{\alpha^{2}\cdot\xi\cdot\sigma\cdot\min\\{\sigma^{2},(1-\gamma)^{2}\cdot\delta^{2}\\}}\cdot\frac{\log^{2}(N)}{N}\leq
1/\|(B^{\pi^{*}})^{-1}\|_{\infty}=1/\sigma^{\prime},$ (140)

following standard perturbation analysis of linear equations [Higham, 2002],
we have that

$\frac{\|\bm{V}_{r}(\bar{\pi}^{N})-\bm{V}_{r}(\pi^{*})\|_{\infty}}{\|\bm{V}_{r}(\pi^{*})\|_{\infty}}\leq
C_{2}\cdot\kappa(B^{\pi^{*}})\cdot\left(\frac{\|\Delta
B\|_{\infty}}{\|B^{\pi^{*}}\|_{\infty}}+\frac{\|\Delta\hat{\bm{r}}\|_{\infty}}{\|\hat{\bm{r}}(\pi^{*})\|_{\infty}}\right),$
(141)

where
$\kappa(B^{\pi^{*}})=\|B^{\pi^{*}}\|_{\infty}\cdot\|(B^{\pi^{*}})^{-1}\|_{\infty}$
denotes the conditional number of $B^{\pi^{*}}$, and $C_{2}$ is a constant.
Note that we have the regret

$\displaystyle\text{Regret}_{r}(\bar{\pi}^{N},N)$
$\displaystyle=\bm{\mu}^{\top}(\bm{V}_{r}(\bar{\pi}^{N})-\bm{V}_{r}(\pi^{*}))\leq(1-\gamma)\|\bm{V}_{r}(\bar{\pi}^{N})-\bm{V}_{r}(\pi^{*})\|_{\infty}$
(142) $\displaystyle\leq