These authors contributed equally to this work.

These authors contributed equally to this work.

[1]Louis-Sébastien Rebuffi

[1]Univ. Grenoble Alpes, Inria, CNRS, Grenoble INP, LIG, Grenoble, 38000,
France

# Learning Optimal Admission Control in Partially Observable Queueing Networks

Jonatha Anselmi<EMAIL_ADDRESS>Bruno Gaujal<EMAIL_ADDRESS><EMAIL_ADDRESS>*

###### Abstract

We present an efficient reinforcement learning algorithm that learns the
optimal admission control policy in a partially observable queueing network.
Specifically, only the arrival and departure times from the network are
observable, and optimality refers to the average holding/rejection cost in
infinite horizon.

While reinforcement learning in Partially Observable Markov Decision Processes
(POMDP) is prohibitively expensive in general, we show that our algorithm has
a regret that only depends _sub-linearly_ on the maximal number of jobs in the
network, $S$. In particular, in contrast with existing regret analyses, our
regret bound does not depend on the _diameter_ of the underlying Markov
Decision Process (MDP), which in most queueing systems is at least exponential
in $S$.

The novelty of our approach is to leverage Norton’s equivalent theorem for
closed product-form queueing networks and an efficient reinforcement learning
algorithm for MDPs with the structure of birth-and-death processes.

###### keywords:

Queueing Networks, Reinforcement Learning, Admission Control

##  1 Introduction

Research in reinforcement learning in Markov Decision Processes (MDPs) has
been thriving since the work of Walkins [1] on Q-learning, the celebrated
model-free learning algorithm. Since then, several extensions of Q-learning
[2], Bayesian [3, 4] or model-based [5] approaches have been proposed to
improve learning efficiency [6, 7] up to the point where the _regret_ of the
most recent algorithms is “asymptotically optimal” in the sense that it
matches a universal lower bound: The regret of the best learning algorithm
with respect to an optimal policy is $\tilde{O}(\sqrt{DSAT})$111The
$\tilde{O}$ notation is a variant of big-O that ignores logarithmic factors.,
where $S$ is the number of states, $A$ the number of actions, $T$ the time
horizon and $D$ the _diameter_ of the MDP; we point the reader to [8] for a
recent overview of this quest for optimal regret.

Since this problem has reached a satisfactory solution, the following natural
question arises: Can one learn _efficiently_ the optimal policy of an MDP not
only when the rewards and the transition kernel are unknown _but also when the
state is partially observable_? Recently, this question has been investigated
under certain assumptions on the structure of model parameters [9, 10, 11]. In
this paper, we address this question in the context of queueing networks where
we assume that the learner has only access to the _total_ number of jobs in
the network, and this makes our problem fall in the family of Partially
Observable MDPs (POMDPs).

###  1.1 Reinforcement learning in POMDPs

It is well-known that POMDPs are prohibitively expensive to solve. If the
parameters are known, the problem of computing an optimal policy is PSPACE-
complete even in finite horizon [12]. Furthermore, it is NP-hard to compute
the optimal memoryless policy [13]. In reinforcement learning, where (some of)
the model parameters are unknown, the lower bound on the average-case
complexity developed in [9, Propositions 1 and 2] confirms with no surprise
that reinforcement learning in POMDPs remains intractable. Matter of fact, the
design of effective exploration–exploitation strategies in POMDPs is still
relatively unexplored; see [10, Section 1] for a detailed discussion. In the
attempt to reduce this computational burden, researchers focused on
reinforcement learning in _subclasses_ of POMDPs [9], and we will also follow
this approach. The algorithm in [14] assumes POMDPs without resets and has
sample complexity scaling exponentially with a certain horizon time. The
Bayesian algorithms proposed in [15, 16] learn POMDPs but bounds on the mean
regret remain unknown for these approaches. A sample-efficient algorithm for
episodic finite POMDPs is given in [9]. Here, it is assumed that the number of
observations is larger than the number of latent states.

The works above have focused on reinforcement learning over a finite or
discounted horizon. In contrast, we will be interested in the (undiscounted)
infinite horizon case, which is technically more challenging. In infinite
horizon, a POMDP algorithm based on spectral methods is proposed in [10]. For
this algorithm, the authors find an order-optimal regret bound with respect to
the optimal memoryless policy. However, it exhibits a linear dependence on the
diameter $D$ of the underlying MDP. This dependence makes this type of bounds
not interesting in the context of queueing systems as the diameter is usually
exponential in the number of states [17]. Although the additional assumptions
on the structure of the model mitigate, to some extent, the intrinsic
complexity of POMDPs, learning algorithms with regret $\tilde{O}(\sqrt{DSAT})$
have remained elusive for all but trivial cases to the best of our knowledge.

###  1.2 Contribution and methodology

In this paper, we propose a learning algorithm for the optimal job-admission
policy in a partially observable queueing network with regret
$\mbox{Reg}(T)\leq\tilde{O}(\sqrt{ST})$. Thus, our main contribution is a
learning algorithm with a regret bound that does not depend on the diameter
$D$, and whose dependence on the state space is very small.

Optimal admission control is one of the most classical control problems in
queues. It has been investigated in several works; see, e.g., [18, 19] and the
references therein. However, these works consider the case where the model
parameters are known, i.e., no learning mechanism is used. The novelty of our
approach is to leverage i) Norton’s equivalence theorem for closed product-
form queueing networks [20] and ii) the efficiency of reinforcement learning
in MDPs with the structure of birth-and-death processes [17]. More
specifically, our result is achieved by using Norton’s theorem to replace the
whole network by a single load-dependent queue in its stationary regime and
relies on the mixing time $\tau_{\rm mix}$ of the network to apply this
equivalence every $\tau_{\rm mix}$ time-steps. The key observation is that
Norton’s theorem helps us to somewhat cast the original partially-observable
MDP to a standard (fully-observable) MDP. In other words, the resulting
asymptotically equivalent POMDP becomes an MDP with the structure of a birth
and death process. This structure is then exploited to construct tight bounds
on the regret of our algorithm by controlling the bias of the current policy
as well as its stationary measure.

###  1.3 Organization

The remainder of the paper is organized as follows. The model of the queueing
network, its practical motivation and Norton’s equivalent queue are presented
in Section 2. Section 2.1 presents the problem addressed in the paper in
detail, Section 4 is dedicated to the presentation of our learning algorithm
(UCRL-M) and Section 5 to the analysis of its regret. In the latter, we state
our main result in Theorem 5.1. Then, Section 6 discusses some technical
aspects of our regret bound. Section 7 showcases the behaviour of the
algorithm on a multi-tier queueing network, and, finally, Section 8 draws the
conclusions of our work.

##  2 Admission control in a queueing network

We consider a Jackson network with $N$ queues (or stations) having service
rates $\mu_{1}^{o},\ldots,\mu_{N}^{o}$, a routing probability matrix
$L=[L_{i,j}:0\leq i,j\leq N]$ and exogenous arrivals occurring with rate
$\lambda$. Here, $L_{0,j}$ (resp. $L_{i,0}$) represents the probability that a
job joins queue $j$ from outside (resp. leaves the network after service at
queue $i$). To guarantee stability, i.e., positive recurrence of the
underlying Markov chain, we require that $\lambda_{i}^{o}<\mu_{i}^{o}$, for
all $i$, where $\lambda_{i}^{o}$ is the arrival rate at queue $i$. It is given
by the unique solution of the traffic equations $\lambda_{i}^{o}=\lambda
L_{0,i}+\sum_{j}\lambda_{j}^{o}L_{j,i}$, for all $i$.

We further assume that the total number of jobs in the network cannot exceed
$S$. Under this constraint, the global system can be seen as a _closed_
network with $S$ jobs. This network is identical to the original one except
for an auxiliary queue, say queue 0, that represents the outside world with
service rate $\lambda$. The departures of queue 0 correspond to the arrivals
of the initial open network (see Figure 1).

$\lambda$admitreject$S-s$jobs outside

Figure 1: Admission control: rejected jobs immediately return to the outside
queue.

Jobs that want to enter the network are subjected to admission control. If a
job is rejected this can be modeled in the closed network as the job being
sent back to the outside queue (see Figure 1). The goal of the admission
controller is to minimize a cost function. For each job, the immediate cost
$c_{t}$ is decomposed into a per-rejection cost $\gamma_{{\rm reject}}$ and a
per-time-unit holding cost $\gamma_{{\rm hold}}$. This cost function is the
long-run average cost per time unit:
$\lim_{T\to\infty}\frac{1}{T}\sum_{t=0}^{T}c_{t}$.

When the controller can observe the state of the network and knows the
parameters of the system $(\lambda,\mu^{o},L)$, this classical problem has
been solved in [19]. In the case where the network is a single M/M/1 queue,
there exists an explicit formula (involving the Lambert $W$ function) for the
optimal admission policy [18].

###  2.1 Problem formulation

In this paper, we consider an admission controller that can only observe
arrivals to and departures from the network. More precisely, the network
topology, internal service rates and routing probabilities are not known, and
the movements of the jobs inside the network are not observable. Our objective
is to design a learning algorithm that learns the optimal admission policy
with a _small_ regret in the sense that its dependence on the network
_complexity_ is minimal.

For the cost to be minimized, we assume that:

  * •

the controller may choose to reject jobs arriving in the network, at the price
of a fixed $\gamma_{{\rm reject}}$ for each rejected job;

  * •

for every time unit in the system, each job induces a holding cost
$\gamma_{{\rm hold}}$ (this is the classical cost function for admission
control, see [18]);

  * •

the controller takes decisions only relying on its set of observations up to
time $t$.

###  2.2 Motivating applications

Our main motivation is the control of computer and software systems. These
systems are composed of multiple interconnected _containers_ , where a
container can be a cluster of servers or a modular software system, and
admission control mechanisms are commonly employed to optimize performance. In
the literature, containers are usually modeled via product-form queueing
networks (for tractability) or layered queueing networks [21, 22], which
justifies our modeling approach. In serverless computing, for instance, users
of the serverless platform can control the overall number of simultaneous
requests that can be processed in a cluster of servers (each with its own
queue) at any given time. In Knative, a Kubernetes-based platform to deploy
and manage modern serverless workloads that is used among others by Google
Cloud Run, admission thresholds are set via the container-concurrency-target-
default global key [23] and the upper limit on the number of jobs that can be
active running at the same time, i.e., $S$, can be controlled via the max-
scale-limit global key. In Kubernetes, an open-source system for the
management of containerized applications, admission controllers are configured
via the \--enable-admission-plugins and \--admission-control-config-file flags
and can be leveraged in case the pod (or application) is requesting too many
resources.

Because of the complex relationships among containers, which can also be
nested in multiple layers, i) a detailed knowledge of the current _state_ is
expensive to obtain at any point in time and ii) the internal container
structure is also subject to estimation errors and may vary over time [24].
This leads us to our learning model, which is meant to capture both of these
aspects: we do not know the network topology, routing probabilities and
service rates as well as the current “state”.

##  3 MDP Model

This section is dedicated to the construction of an MDP model of the system as
well as an artificial aggregated MDP that is equivalent to the original MDP
under its stationary regime. Note however that the learning algorithm
constructed in the following only interacts with the original system, non-
aggregated. The aggregated system is only used for the performance analysis of
the algorithm.

###  3.1 Original MDP

Let us model the problem as an MDP,
$M^{o}=(\mathcal{X}^{o},\mathcal{A}^{o},P^{o},r^{o})$, where the super-index
$o$ stands for “original” throughout the paper. We first use uniformization to
see the process in discrete time. The uniformization constant $U$ is lower
bounded by the sum of the rates: $U\geq\lambda+\sum_{i=1}^{N}\mu_{i}^{o}$.
Thus, the time steps, which will be indexed by $t$, follow a Poisson process
with rate $U$, and events (arrivals, services, routings and control actions)
can only occur at these times. In the following $1/U$ will be seen as one time
unit.

  * •

The state space $\mathcal{X}^{o}$ is the set of all tuples
$(x_{1},\ldots,x_{N})$ given by the number of jobs $x_{i}$ in each queue $i$.

  * •

The action space is $\mathcal{A}^{o}:=\\{\rm 0,1\\}$ where $0$ stands for
rejection and $1$ for admission.

  * •

The transition matrix $P^{o}$ is simply constructed by using the routing
matrix $L$, the arrival rate $\lambda$ and the service rates
$(\mu_{i}^{o})_{i}$.

  * •

The mean rewards $r^{o}$ are constructed from the cost function. The immediate
cost for each state-action pair $(\mathbf{x},a)$, is Bernoulli distributed. It
is decomposed into:
\- a deterministic part, $\frac{1}{U}(\gamma_{{\rm hold}}\sum_{i=1}^{N}x_{i})$
(each present job incurs a cost $\gamma_{{\rm hold}}$ per time unit),
\- and a stochastic part, $\gamma_{{\rm reject}}(1-a){\bf 1}_{\mbox{\tiny job-
arrival}}$ (if a job arrives and the action is reject).

To be consistent with the learning literature, where rewards are used instead
of costs, we first define $r_{\max}:=\frac{\lambda\gamma_{{\rm
reject}}+\gamma_{{\rm hold}}S}{U}$ and for each state-action pair
$(\mathbf{x},a)$, the reward are Bernoulli distributed with expected value

$r^{o}(\mathbf{x},a):=r_{\max}-\frac{\lambda\gamma_{{\rm
reject}}(1-a)+\gamma_{{\rm hold}}s}{U}=\frac{\lambda\gamma_{{\rm
reject}}a+\gamma_{{\rm hold}}(S-s)}{U},$ (1)

where $s:=\sum_{i=1}^{N}x_{i}$.

Let $\Pi^{o}:=\\{\pi:\mathcal{X}^{o}\to\mathcal{A}^{o}\\}$ denote the set of
stationary and deterministic policies. A stationary policy $\pi$ is a
deterministic function from $\mathcal{X}^{o}$ to $\mathcal{A}^{o}$.

Then, the MDP evolves under $\pi$ in the standard Markovian way. At each time-
step $t$, the system is in state $\mathbf{x}_{t}$, the controller chooses the
action $a_{t}=\pi(\mathbf{x}_{t})$ and receives a random reward whose expected
value is $r^{o}(\mathbf{x}_{t},a_{t})$, and the system moves to state
$\mathbf{x}^{\prime}$ at time $t+1$ with probability
$P^{o}(\mathbf{x}^{\prime}\mid\mathbf{x}_{t},a_{t})$. The objective function
is to minimize the long run average cost.

The average reward induced by policy $\pi$ is:

$g^{o}(M^{o},\pi):=\lim_{T\to\infty}\frac{1}{T}\sum_{t=1}^{T}\mathbb{E}[r^{o}(\mathbf{x}_{t},\pi(\mathbf{x}_{t}))].$
(2)

An optimal policy $\pi^{*}$ for the original MDP achieves the best average
reward $g^{o}(M^{o},\pi^{*})=\sup_{\pi\in\Pi^{o}}g^{o}(M^{o},\pi).$

###  3.2 Aggregated model

Let us define an aggregated MDP $M=(\mathcal{S},\mathcal{A},P,r)$ where the
network is replaced by a single queue.

####  3.2.1 Norton equivalent queue

In this subsection, let us consider the system defined in Section 2 without
control (all jobs are admitted).

The stationary measure of the network can be connected to the stationary
measure of a birth-and-death process via Norton’s theorem of queueing networks
[20], also known in the literature as Flow Equivalent Server (FES) method
[25]. Towards this purpose, let $v_{i}$ denote the average number of visits at
queue $i$ relative to queue $0$. Set $v_{0}=1$ and let $(v_{1},\ldots,v_{N})$
be the unique solution of $v_{i}=\sum_{j=0}^{N}L_{j,i}v_{j}$, for all
$i=1,\ldots,N$. Then, when containing $S$ jobs, the vector of the number of
jobs in each queue forms a continuous-time Markov chain with stationary
measure [25]

$\displaystyle\nu^{o}(\mathbf{x})=\frac{1}{G(S)}\prod_{i=0}^{N}\left(\frac{v_{i}}{\mu_{i}}\right)^{x_{i}},$
(3)

for all $\mathbf{x}\in\\{\mathbf{x}\in\mathbb{N}^{N}:|\mathbf{x}|\leq S\\}$,
where $G(S)$ is a normalization constant and $|\cdot|$ denotes the $L_{1}$
norm.

The construction of our equivalent queue works as follows:

  1. 1.

Given the closed Jackson network above, consider the (closed) network where
queue $0$ is short circuited (this means set $\mu^{o}_{0}=\infty$) and let
$\mu(s)$ denote the _throughput_ 222The throughput of a closed Jackson
queueing network with $s$ jobs is the rate at which jobs flow at a reference
queue (queue 0 in our case) and is defined by $\mu(s):=\frac{G(s-1)}{G(s)}$
where $G(s)$ is the normalizing constant appearing in the product-form
expression (3) of the stationary measure $m^{o}$. of the network with $s$ jobs
in total (see Figure 2 for an illustration).

  2. 2.

Consider the original network where all queues except $0$ are all replaced by
a _single_ queue that operates with rate $\mu(s)$ if it contains $s$ jobs.

  3. 3.

Then,

$\displaystyle\sum_{\mathbf{x}:|\mathbf{x}|=s}\nu^{o}(\mathbf{x})=\nu(S-s,s),\quad\forall
s=0,\ldots,S$ (4)

where $\nu(S-s,s)$, for all $s=0,\ldots,S$, is the stationary measure of the
reduced network with two queues.

Norton equivalent queueJackson network

Figure 2: Illustration of Norton Equivalence theorem.

We remark that $\nu(S-s,s)$ is indeed the stationary measure of a birth-and-
death process with birth rate $\lambda\mathds{1}_{s<S}$ and death rate
$\mu(s)$, a fact that will be key in the regret analysis of our learning
algorithm. In particular, we will use the following lemma, which provides some
known properties about the throughput function $\mu(s)$ [26].

######  Lemma 3.1.

The throughput function $s\mapsto\mu(s)$ is increasing, concave and bounded by
$\mu_{\max}:=\sum_{i\leq N}\mu_{i}^{o}$.

The throughput bound $\mu_{\max}$ can be significantly improved [25] but this
will not change the structure of our results.

####  3.2.2 Aggregated MDP

Notice that, in the original MDP $M^{o}$, the rewards do not depend on the
state but only on the number of jobs in the network, therefore, the Norton
equivalent queue can also be used to construct an equivalent MDP.

Define the simplified equivalent MDP $M=(\mathcal{S},\mathcal{A},r,P)$.

  * •

The state space $\mathcal{S}=\\{0,\ldots,S\\}$ consists of all possible
numbers of jobs in the queueing network. We denote by $S^{\prime}:=S+1$ the
number of states of the aggregated MDP.

  * •

The actions are the same as for the original MDP:
$\mathcal{A}=\mathcal{A}^{o}=\\{\rm 0,1\\}$ (reject or accept).

  * •

The original reward in (1) does not depend on the precise position of the jobs
in the network but only on their number. Therefore for $s\in\mathcal{S}$ and
$a\in\mathcal{A}$, we can define the expected reward as

$r(s,a)=\frac{\lambda\gamma_{{\rm reject}}a+\gamma_{{\rm hold}}(S-s)}{U}$ (5)

  * •

The transition probabilities $(P^{\pi})$ are defined as follows.

Let $\pi$ be a policy (a function from $\mathcal{S}\to\mathcal{A}$) on $M$. By
convention, $\pi$ will also be seen as a policy in the original MDP $M^{o}$
using the natural extension, i.e., if $\mathbf{x}\in\mathcal{S}^{o}$, then
$\pi(\mathbf{x}):=\pi(|\mathbf{x}|)$. We can now define the transition matrix
for policy $\pi$ as the transition matrix in the aggregated MDP $M$ under the
stationary measure $\nu^{o,\pi}$:

$P(s^{\prime}\mid
s,\pi(s))=\sum_{\mathbf{x},|\mathbf{x}|=s}\;\sum_{\mathbf{y},|\mathbf{y}|=s^{\prime}}\frac{\nu^{o,\pi}(\mathbf{x})}{\nu^{\pi}(s)}P^{o}(\mathbf{y}\mid\mathbf{x},\pi(\mathbf{x})),$
(6)

where $\nu^{\pi}(s)=\sum_{\mathbf{x},|\mathbf{x}|=s}\nu^{o,\pi}(\mathbf{x})$
is the equivalent stationary measure. Under this construction, these
probabilities are those for the Norton equivalent queue. Also, notice that the
equivalent stationary measure $\nu^{\pi}(s)$ is also the stationary measure of
the Norton equivalent queue with transition matrix $P^{\pi}$ under policy
$\pi$.

Let $\Pi:=\\{\pi:\mathcal{S}\to\mathcal{A}\\}$ denote the set of stationary
and deterministic policies.

######  Definition 3.2.

The average gain induced by policy $\pi$ is:

$g(M,\pi):=\lim_{T\to\infty}\frac{1}{T}\sum_{t=1}^{T}\mathbb{E}[r({{s}}_{t},\pi({s}_{t}))].$
(7)

The optimal policy $\pi^{*}$ achieves

$g(M,\pi^{*}):=g^{*}(M):=\sup_{\pi\in\Pi}g(M,\pi).$ (8)

###  3.3 Comparison between both MDPs

It should be clear that the original MDP $M^{o}$ has a greater set of policies
than the aggregated MDP $M$ because it has more states. Therefore,
$g^{o}(M^{o},\pi^{*})\geq g^{*}(M)$. However, if we only consider the set of
policies in the original MDP $M^{o}$ that take the same action (reject or
accept) in all the states with the same total number of jobs, then optimal
gains coincide. More precisely, let $\Pi^{o}_{sum}$ be the subset of policies
in $M^{o}$ such that for all
$\pi\in\Pi^{o}_{sum},\pi(\mathbf{x})=\pi(\mathbf{y})$ if
$|\mathbf{x}|=|\mathbf{y}|$. Then, the stationary measure on $M^{o}$ under any
policy $\pi$ in $\Pi^{o}_{sum}$, and the stationary measure under $\pi$ on $M$
satisfy
$\sum_{\mathbf{x},|\mathbf{x}|=s}\nu^{o,\pi}(\mathbf{x})=\nu^{\pi}(s)$.
Therefore, we get for all $\pi$ in $\Pi^{o}_{sum}$,

$\displaystyle g^{o}(M^{o},\pi)$ $\displaystyle=$
$\displaystyle\sum_{\mathbf{x}}\nu^{o,\pi}(\mathbf{x})r^{o}(\mathbf{x},\pi(\mathbf{x}))$
$\displaystyle=$
$\displaystyle\sum_{s}\sum_{\mathbf{x},|\mathbf{x}|=s}\nu^{o,\pi}(\mathbf{x})r(s,\pi(s))$
$\displaystyle=$ $\displaystyle\sum_{s}\nu^{\pi}(s)r(s,\pi(s))=g(M,\pi).$

Now taking the maximum over all policies in $\Pi^{o}_{sum}$ yields

$\max_{\pi\in\Pi^{o}_{sum}}g^{o}(M^{o},\pi)=g^{*}(M).$

As for learning when the full state is not observable, the best one can hope
for is to learn $\max_{\pi\in\Pi^{o}_{sum}}g^{o}(M^{o},\pi)$, so we will
consider the regret with respect to the optimal gain $g^{*}(M)$, in the
following.

###  3.4 Bias and diameter

In the following, we will heavily use the bias [27] of a policy on $M$
(although it has no intuitive meaning relative to the original MDP) as well
the _diameter_ of the aggregated MDP.

######  Definition 3.3 (Diameter of an MDP).

Let $\pi:\mathcal{S}\to\mathcal{A}$ be a stationary policy of any MDP $M$ with
initial state ${s}$. Let $T\left({s}^{\prime}|M,\pi,{s}\right):=\min\\{t\geq
0:{s}_{t}=s^{\prime}|{s}_{0}={s}\\}$ be the random variable for the first time
step in which ${s}^{\prime}$ is reached from ${s}$ under $\pi$. Then, we say
that the _diameter_ of $M$ is

$D(M):=\max_{{s}\neq{s}^{\prime}}\min_{\pi:\mathcal{S}\to\mathcal{A}}\mathbb{E}\left[T\left({s}^{\prime}|M,\pi,{s}\right)\right].$

Again, let us point out that we will only consider the diameter on the
aggregated MDP for the computations, as it is needed to control the bias terms
of the aggregated MDP (see Appendix F). We will never need to consider the
bias or the diameter of the original MDP.

###  3.5 Reinforcement learning

Here, we consider a learner that can observe the arrivals and departures of
jobs in the original MDP and makes admission decisions for each arriving job.

####  3.5.1 What does the learner know?

  * •

As mentioned earlier, the learner can observe the external events: arrivals
and departures of jobs. This implies that at any discrete time-step $t$, the
total number of jobs in the system, $s_{t}$ is known to the learner and will
be seen as the partially observed state.

  * •

The expected cost in state-action pair $(s,a)$ is unknown as it depends on the
unknown parameter $\lambda$ (see (5)). However, the parameters $\gamma_{{\rm
reject}}$, $\gamma_{{\rm hold}}$ and the uniformization constant $U$ are
known, and the learner knows how the cost depends on $\lambda$, which will be
important for the definition of the confidence regions. We will often use an
upper bound on the difference of rewards between two neighboring states
$\delta_{\max}:=\gamma_{{\rm reject}}+\frac{\gamma_{{\rm hold}}}{U}$. We will
use $\delta_{\max}$ instead of $r_{\max}$ in the following derivation of the
regret, as $\delta_{\max}$ does not depend on $S$ and this will help us gain a
factor $S$ in the regret bound. We will also make the assumption that the
learner knows the reward function up to the actual value of the arrival rate
$\lambda$, that must be learned.

  * •

The learning algorithm knows $T$, the number of time steps where it can take
observations and actions. This is not a strong requirement as one can make the
algorithm oblivious to $T$ by using a classical doubling trick on $T$.

####  3.5.2 Regret

######  Definition 3.4 (Regret).

The _regret_ at time $T$ of the learning algorithm $\mathcal{L}$ is

$\displaystyle{\rm Reg}(M,\mathcal{L},T):=Tg^{*}(M)-\sum_{t=1}^{T}r_{t}.$ (9)

Here, $g^{*}(M)$ is the optimal gain defined in (8). The reward $r_{t}$ is the
reward of the state visited at time $t$ under the current policy used by the
learning algorithm.

##  4 Learning algorithm

###  4.1 High-level description of the proposed algorithm

Our algorithm is episodic, model-based and optimistic. More precisely, the
interactions of the learner with the MDP $M^{o}$ are decomposed into episodes.
In each episode $k$, of duration $[t_{k},t_{k+1}-1]$, one admission policy
$\pi_{k}$ is used to control the network and the learner observes the system
(arrivals and departures) while collecting rewards under $\pi_{k}$. At the end
of the episode, the estimation of the true transition probabilities and
rewards (the model), $\hat{p}_{k}$ and $\hat{r}_{k}$ respectively, as well as
the confidence region $\mathcal{M}_{k}$ are updated using the samples
collected during the episode. This gives $\hat{p}_{k+1}$, $\hat{r}_{k+1}$ and
$\mathcal{M}_{k+1}$. The next policy $\pi_{k+1}$ is the best policy for the
best MDP inside the confidence region $\mathcal{M}_{k+1}$ (optimism).

In our case with partial observations, the number of jobs at time $t$,
$(s_{t})_{t\leq T}$ is not Markovian, therefore it does not provide enough
information to make good estimates on the underlying MDP. Instead, we collect
a set $\\{s_{1},\ldots,s_{\tau_{\rm mix}}\\}$ of observations and try to learn
using this extended information. If $\tau_{\rm mix}$ is well chosen, i.e.,
larger than the mixing time of the MDP, then each subsequence
$s_{i},s_{i+\tau_{\rm mix}},s_{i+2\tau_{\rm mix}},\ldots$ forms an “almost”
independent sequence and therefore can be used for statistical estimations.

Our learning algorithm is based on the following idea. It can be seen as a
collection of $\tau_{\rm mix}$ learning algorithms
$\mathcal{L}_{1},\ldots,\mathcal{L}_{\tau_{\rm mix}}$, using respectively the
subsequence $(s_{i+k\tau_{\rm mix}})_{k\in\mathbb{N}}$ of observations, which
are called modules in the following. Each learning module $\mathcal{L}_{i}$
behaves similarly as the classical optimistic algorithm described above. There
are no interactions between modules except for the number of visits that
contributes to the construction of the global confidence region, as detailed
in Section 4.4. The main technical difficulties in the control of the behavior
of the algorithm are:

  1. 1.

The observations used by the learning modules
$\mathcal{L}_{1},\ldots,\mathcal{L}_{\tau_{\rm mix}}$ are not independent of
each other, so one must be careful in assessing the interplay between the
modules.

  2. 2.

For each learning module $\mathcal{L}_{i}$, its sequence of observations
$s_{i+\tau_{\rm mix}},s_{i+2\tau_{\rm mix}},s_{i+3\tau_{\rm mix}},\ldots$ is
not really stationary and independent, but only weakly correlated.

###  4.2 Number of modules: $\tau_{\rm mix}$

Let us first give a more precise definition of the $\tau_{\rm mix}$ modules,
where the number $\tau_{\rm mix}$ is yet to be chosen carefully. At the
beginning of the algorithm, each time-step $t$ is attributed a module $m_{t}$,
so that these modules form a partition of the time-steps. For $0\leq
t\leq\tau_{\rm mix}-1$, the module $m_{t}$ is defined in the following way:
first $t\in m_{t}$, then we wait $\tau_{\rm mix}$ steps to add the next time-
step to that module, so that $t,t+\tau_{\rm mix},t+2\tau_{\rm mix},\ldots\in
m_{t}$, until time-step $T$ is reached. More formally one can identify,
$m_{t}=t\mod\tau_{\rm mix}$.

The number of modules $\tau_{\rm mix}$ is chosen using the following
construction. Let us consider the original MDP under any policy $\pi$, with
stationary measure $\nu^{o,\pi}$. There exists $C>0$, $\rho\in(0,1)$ such
that:

$\max_{\pi\in\Pi}\sup_{x_{0}\in\mathcal{S}}\left\|\mathbb{P}^{o,\pi}_{x_{0}}(x_{t}=\cdot)-\nu^{o,\pi}\right\|_{TV}\leq
C\rho^{t}\quad\forall t>0,$ (10)

where $\mathbb{P}^{o,\pi}_{x_{0}}(x_{t}=\cdot)$ is the distribution of the
state at time $t$ under policy $\pi$ in the original MDP, with starting state
$x_{0}$. Let us then define

$\tau_{\rm mix}:=\lceil 5\log T/\log\rho^{-1}\rceil.$ (11)

The reason for this precise choice will appear in the analysis of the regret
(see Section 5) but the general idea behind this choice comes from Lemma D.1
given in appendix, that basically says that after $\tau_{\rm mix}$ steps, the
correlation between the state at time $t$ and the state at time $t+\tau_{\rm
mix}$, under any policy, is smaller than $C^{\prime}\rho^{\tau_{\rm mix}}$,
where $C^{\prime}$ is a constant.

The fact that the number of modules used by the algorithm depends on $\rho$
can be seen as a weakness of our approach because it means that the learner
needs to know a priori a bound on the mixing time of the unknown MDP. This
point will be addressed in Section 6.

###  4.3 UCRL-M: learning with $\tau_{\rm mix}$ modules

Algorithm UCRL-M (Upper Confidence Reinforcement Learning with several
Modules) is given in Algorithm 1. First, the algorithm initializes the
different modules. Here, for each episode $k$ and module $m$, it computes the
empirical estimates of the reward and probability transition as in (15) and
(14). Then, it applies Extended Value Iteration (EVI) (Appendix B) to find a
policy $\tilde{\pi}_{k}$ and an optimistic MDP
$\tilde{M}_{k}\in\mathcal{M}_{k}$ according to (12). Finally, to explore the
MDP at episode $k$, it first iterates on the MDP over $\tau_{\rm mix}$ time-
steps and discards these samples (ramping phase) to start the observations
from the stationary distribution of the current policy. This phase is
necessary to guarantee that observations within a module are nearly
independent. Afterward, UCRL-M explores the true MDP with the optimistic
policy $\tilde{\pi}_{k}$ and updates the empirical estimates with its
observations.

The episode ends when the stopping criterion (18) is met. The next optimistic
policy for the episode $k+1$ is found with respect to the observations
inducing the confidence region $\mathcal{M}_{k}$ that is built using all
modules (see (17)).

Input: $\mathcal{S}$ and $\mathcal{A}$.

1 Set $t=0$, $k=0$;

2 while  _$t\leq T$_ do

3 Initialize episode $k$ with $t_{k}:=t$

4 Compute for all $(s,a)$ the modules $m_{k}(s,a)$ according to (13);

5 Compute the confidence region $\mathcal{M}_{k}$ as in (17);

6 Find a policy $\tilde{\pi}_{k}$ and an optimistic MDP
$\tilde{M}_{k}\in\mathcal{M}_{k}$ with “Extended Value Iteration” such that
$g(\tilde{M}_{k},\tilde{\pi}_{k})\geq\max_{M_{k}\in{\mathcal{M}}_{k}}\max_{\pi}g(M_{k},{\pi})-\frac{\delta_{\max}}{\sqrt{t_{k}}}.$
(12)

7 Ramping phase ($\Phi$): Iterate the MDP with policy $\tilde{\pi}_{k}$ for
$\tau_{\rm mix}$ time-steps, discard the observations and set $t:=t+\tau_{\rm
mix}$.

8 Exploration: while  _ $\quad
V_{k}^{(m_{t})}(s_{t},\tilde{\pi}_{k}(s_{t}))<\max\\{1,N_{t_{k}}^{(m_{t})}(s_{t},\tilde{\pi}_{k}(s_{t}))\\},$
_ do

9

  * 1.

Choose action $a_{t}=\tilde{\pi}_{k}(s_{t})$;

  * 2.

Observe $s_{t+1}$;

  * 3.

Update $V_{k}^{(m_{t})}(s_{t},a_{t}):=V_{k}^{(m_{t})}(s_{t},a_{t})+1$;

  * 4.

Set $t:=t+1$.

10 end while

11

12 end while

Algorithm 1 The UCRL-M algorithm.

###  4.4 Confidence region

As mentioned earlier, the learning algorithm relies on the “Optimism in face
of uncertainty” principle. Here, we provide the explicit construction of a
confidence region $\mathcal{M}_{k}$ based on the observations, which depends
on the visit counts. For each state-action pair $(s,a)$ and each module $m$,
let $N_{t_{k}}^{(m)}(s,a)$ be the cumulative number of visits to $(s,a)$ at
all times $t=m\mod\tau_{\rm mix}$ smaller than $t_{k}$, and excluding the
visits during the ramping phases $\Phi$ (see the UCRL-M algorithm).

We also define the most frequent module for each state-action pair $(s,a)$:
Let $m_{k}(s,a)$ be a module with the highest visit count until episode $k$,

$m_{k}(s,a)\in\arg\max_{m}{N_{t_{k}}^{(m)}(s,a)},$ (13)

so that for this module, the empirical observations are the most accurate, and
we can relate the number of observations for this module to the total number
of visits $N_{t_{k}}(s,a)$ of the pair $(s,a)$ with the inequality:
$N_{t_{k}}^{(m_{k}(s,a))}(s,a)\geq\frac{1}{\tau_{\rm mix}}N_{t_{k}}(s,a)$.

To define the confidence region $\mathcal{M}_{k}$, first define
$\hat{r}_{k}^{(m)}$ and $\hat{p}_{k}^{(m)}$ the empirical reward and
transition estimates in module $m$:

$\displaystyle\hat{p}_{k}^{(m)}(s^{\prime}|s,a)$
$\displaystyle:=\frac{\sum_{t=1}^{t_{k}-1}\mathds{1}_{\\{s_{t}=s,a_{t}=a,s_{t+1}=s^{\prime},m_{t}=m\\}}\mathds{1}_{\left\\{t\notin\Phi\right\\}}}{\max\left\\{1,N_{t_{k}}^{(m)}(s,a)\right\\}}$
(14) $\displaystyle\hat{r}_{k}^{(m)}(s,a)$
$\displaystyle:=\hat{p}_{k}^{(m)}(s+1|s,a)\gamma_{{\rm reject}}+\gamma_{{\rm
hold}}\frac{S-s}{U},$ (15)

where $\Phi$ is the set of the time steps in the ramping phases defined in the
algorithm. $\mathcal{M}_{k}$ is the confidence set of MDPs whose rewards
$\tilde{r}$ and transitions $\tilde{p}$ satisfy:

$\forall(s,a),\quad\left|\tilde{r}(s,a)-\hat{r}_{k}^{(m_{k}(s,a))}(s,a)\right|\leq\delta_{\max}\sqrt{\frac{2\log\left(2At_{k}\right)}{\max\left\\{1,N_{t_{k}}^{(m_{k}(s,a))}(s,a)\right\\}}};$
(16) $\forall(s,a),\quad\|\tilde{p}(\cdot\mid
s,a)-\hat{p}_{k}^{(m_{k}(s,a))}\left(\,\cdot\mid
s,a\right)\|_{1}\leq\sqrt{\frac{8\log\left(2At_{k}\right)}{\max\\{1,N_{t_{k}}^{(m_{k}(s,a))}(s,a)\\}}}.$
(17)

Notice that for each state-action pair $(s,a)$, we only need the empirical
reward and transition estimates for the module $m_{k}(s,a)$: this means that
the confidence region $\mathcal{M}_{k}$ is built from the comparison between
modules from (13), and we do not build a specific confidence region for each
module.

The algorithm finds the best optimistic MDP and policy within this confidence
set, and executes the policy on the true MDP until the stopping criterion is
met, that is when for any module $m$ the number of visits $V_{k}^{(m)}(s,a)$
in the current episode of a state-action pair $(s,a)$ reaches the number of
visits of this pair and module until time $t_{k}$. More formally, if at
episode $k$ we choose the policy $\tilde{\pi}_{k}$, then the stopping
criterion gives the following guarantee:

$\forall(s,m)\quad
V_{k}^{(m)}(s,\tilde{\pi}_{k}(s))\leq\max\\{1,N_{t_{k}}^{(m)}(s,\tilde{\pi}_{k}(s))\\}.$
(18)

###  4.5 Time complexity of UCRL-M

######  Proposition 1.

The time complexity of UCRL-M is $O(KS\tau_{\rm mix}+Kt_{\rm evi}+T)$, where
$K$ is the number of episodes and $t_{\rm evi}$ the time complexity of
extended value iteration. Furthermore, ${\mathbb{E}}(K)=O(\log T)$.

###### Proof.

The time complexity of lines 5 and 6 is $O(KS\tau_{\rm mix})$. The complexity
of line 7 is $O(Kt_{\rm evi})$. The complexity of line 8 is $O(K\tau_{\rm
mix})$. The complexity of line 9 is $O(T-K\tau_{\rm mix})$, the number of
useful observations. As for the expected number of episodes,
${\mathbb{E}}K=O(\log T)$ because of the doubling trick used to end the
episodes (see [5] for example). ∎

Note that the total number of useful samples (excluding the steps made during
the ramping phases ) is $T-K\tau_{\rm mix}$, and each module uses
$\frac{T-K\tau_{\rm mix}}{\tau_{\rm mix}}$ samples. As for the time complexity
of EVI, each iteration of EVI is $O(S^{3})$ and the number of iterations
depends on the starting point and is more difficult to estimate. In total, the
time complexity does not really depend on $\tau_{\rm mix}$ or $t_{\rm evi}$
that only appears at the beginning of each episode, and the number of episodes
is small w.r.t. $T$.

##  5 Regret of UCRL-M

###  5.1 Main result

Let us recall that $S$ is the global bound on the number of jobs,
$S^{\prime}=S+1$ is the number of states, $\gamma_{{\rm reject}}$ is the
rejection cost, $\gamma_{{\rm hold}}$ is the unit-time holding cost and $D$ is
the diameter of the aggregated MDP. Also, $\nu^{\pi^{\max}}(s)$ is the
stationary measure in the aggregated MDP under the policy that accepts all
jobs, $\rho$ is defined in Section 4 and $\mu(i)$ is the service rate in the
aggregated MDP when $i$ jobs are in the system.

Define the constant $C_{1}:=\prod_{i=1}^{i_{0}-1}\frac{\mu(i_{0})}{\mu(i)}\geq
1$, where $i_{0}$ is chosen such that $\mu(i_{0})>\lambda$. Such a $i_{0}$
exists because the unconstrained network is assumed to be stable (see Section
2) regardless of $S$. Hence, the flow equivalent queue is also stable
regardless of $S$. Define also $C_{2}:=\frac{(\lambda\gamma_{{\rm
reject}}+\gamma_{{\rm hold}})C_{1}}{\mu(1)\left(1-\lambda/\mu(i_{0})\right)}$.

######  Theorem 5.1.

Let $M\in\mathcal{M}$. Define
$Q_{\max}:=\left(\frac{10C_{2}(S^{\prime})^{2}}{\nu^{\pi^{\max}}(S)}\right)^{2}\log\left(\left(\frac{10C_{2}(S^{\prime})^{2}}{\nu^{\pi^{\max}}(S)}\right)^{4}\right)$.
Define also the constant $\kappa=228(\gamma_{{\rm reject}}+\frac{\gamma_{{\rm
hold}}}{U})\frac{U}{\mu(1)}C_{1}{\left(1-\sqrt{\frac{\lambda}{\mu(i_{0})}}\right)^{-3}}$.
For the choice $\tau_{\rm mix}=5\frac{\log T}{\log 1/\rho}$, and $A=2$, we
have:

${\mathbb{E}}\left[\mbox{Reg}(M,\mbox{UCRL-M},T)\right]\leq\kappa\log\left(2T\right)\sqrt{T\log^{-1}(1/\rho)}+R_{\rm
LO},$ (19)

where $R_{\rm
LO}:=138r_{\max}D^{2}\max\left\\{Q_{\max},T^{1/4}\right\\}\frac{\log^{4}\left(4T\right)}{\log^{2}1/\rho}$
is a lower order term of the regret.

Before diving into the proof, which involves many technical points, let us
comment on our result. In contrast with most bounds from the literature, the
most remarkable point is that both the diameter and the size of the state
space do not appear in our bound. These are both replaced by
$\log^{-1/2}(1/\rho)$.

Although we do not know any explicit bounds on $\rho$ for all possible
networks, it is quite reasonable to predict that $\log^{-1/2}(1/\rho)$ can be
of order $\sqrt{S}$. In fact, this can be shown for acyclic networks as well
as for hyper-stable networks as it will be shown in Section 6.

This implies that the regret of UCRL-M is $\tilde{O}(\sqrt{ST})$, which is a
major improvement over the best bound for general MDPs, namely
$\tilde{O}(\sqrt{DSAT})$. This further confirms the fact that exploiting the
structure of the learned system actually leads to more efficient algorithms as
well as tighter analysis of their performance.

###  5.2 Outline of the proof

To compute the expected regret $\mathbb{E}[{\rm Reg}]$, we will mainly follow
the strategy from [5, Section 4]. First, we deal with the regret term
corresponding to the initialization phase of each episode, which depends in
the number of episodes. Then, for each episode $k$, we consider the case where
the true MDP $M$ does not belong to the confidence region $\mathcal{M}_{k}$,
and use concentration inequalities along with the independence Lemma D.1 to
show that this regret term will remain low. Then, we consider the case where
the true MDP belongs to the confidence region, and for each episode, we split
the regret into relevant comparisons. Here, we expose terms depending on the
difference of rewards and transitions between the true and optimistic MDPs,
terms depending on the difference of biases, a term depending on the number of
episodes and a term coming from the the computation of the optimistic policy
and MDP with EVI.

To achieve the first split, we need to define:
$R_{k}^{(m)}(s):=\sum_{a}V_{k}^{(m)}(s,a)(\rho^{*}-r(s,a))$ the regret at
episode $k$ induced by state $s$ in module $m$, with $V_{k}^{(m_{t})}(s,a)$
the number of visit of $(s,a)$ during episode $k$ in module $m$. We split the
regret into terms where the true MDP belongs to the confidence region, terms
where it does not, and the terms from initializing the episodes:

$\mathbb{E}\left[\rm Reg\right]\leq\mathbb{E}\left[R_{\rm
in}\right]+\mathbb{E}\left[R_{\rm out}\right]+{\mathbb{E}}\left[R_{\rm
ramp}\right]$ (20)

with $K$ the number of episodes and the regret where the MDP is in the
confidence region being $R_{\rm
in}:=\sum_{m}\sum_{s}\sum_{k=1}^{K}R_{k}^{(m)}(s)\mathds{1}_{M\in\mathcal{M}_{k}}$,
and when it is outside $R_{\rm
out}:=\sum_{m}\sum_{s}\sum_{k=1}^{K}R_{k}^{(m)}(s)\mathds{1}_{M\notin\mathcal{M}_{k}}$
and the regret of the ramping phases $R_{\rm
ramp}=\sum_{k}\sum_{t=t_{k}}^{t_{k}+\tau_{\rm
mix}-1}r(s_{t},\tilde{\pi}_{k}(s,t))$. Each term is then bounded as explained
in Appendix A.

##  6 Controlling the regret bound parameter $\rho$

The efficiency of UCRL-M is critically based on controlling $\tau_{\rm mix}$
and $\rho$. In particular, Theorem 5.1 says that the regret of UCRL-M depends
on $W:=\log^{-1/2}(1/\rho)$.

###  6.1 Bounds using mixing and coupling times

In Section 4, the number of modules $\tau_{\rm mix}$ is defined as $\tau_{\rm
mix}:=5\log T/\log\rho^{-1}$. where $\rho$ is such that

$\max_{\pi}\sup_{x_{0}\in\mathcal{S}}\left\|\mathbb{P}^{o,\pi}_{x_{0}}(x_{t}=\cdot)-\nu^{o}(\pi)\right\|_{TV}\leq
C\rho^{t}\quad\forall t>0.$ (21)

Let us first recall classical results from Markov chain theory [28] relating
$\rho$ with the mixing and coupling time of a Markov chain. Let us consider
any Markov chain with transition matrix $P$ and stationary distribution $\nu$
(in our case, consider the Markov chain under the policy that attains the
maximum in (21)). Let us define
$d(t):=\sup_{x_{0}\in\mathcal{S}}\left\|\mathbb{P}_{x_{0}}(x_{t}=\cdot)-\nu\right\|_{TV}$.
Then, the mixing time of the chain is defined as $t_{mix}:=\min\\{t:d(t)\leq
1/4\\}$.

A classical bound on $\rho$ is then obtained by using the mixing time:

$\rho\leq\frac{1}{2^{t_{mix}^{-1}}}$ (22)

This implies that $W\leq\sqrt{t_{mix}\log(2)}$.

Another bound on $\rho$ can be obtained by using the coupling time. The
coupling time is $\tau_{x,y}:=\min\\{t:X_{t}=Y_{t}\\}$. If $X_{t}$ and $Y_{t}$
are coupled and start at $X_{0}=x$ and $Y_{0}=y$ respectively. Then,
$d(t)\leq\max_{x,y}{\mathbb{P}}(\tau_{x,y}>t)$. By using Markov inequality,
this implies that

$t_{mix}\leq 4\max_{x,y}{\mathbb{E}}[\tau_{x,y}].$ (23)

Therefore, a bound on the expected coupling time translates into a bound on
$\rho$.

####  6.1.1 Acyclic networks

In our model, if the queueing network is acyclic, then the coupling time is
controllable because whenever a queue couples it stays coupled forever.

More precisely, since the total number of states in the network increases with
the admission threshold, the threshold policy under which the coupling time is
the largest is when all jobs are admitted. Under this policy, by monotonicity,
the coupling time is upper bounded by the coupling in an open network where
all the $N$ queues have buffers bounded by $S$. In this case, the coupling
time has been studied in [29, Theorem 5.3], where the following result is
proved in the stable case. Using our notation,

$\max_{x,y}{\mathbb{E}}[\tau_{x,y}]\leq\sum_{i=1}^{N}\frac{U^{2}}{(\lambda_{i}^{o}+\mu_{i}^{o})(\mu_{i}^{o}-\lambda_{i}^{o})}S,$
(24)

where $U$ is the uniformization constant and $(\lambda_{i})_{i\leq N}$ is the
solution of the traffic equations.

According to Equation (22) and (23), this induces the following bound on the
term $W$ in the regret:

$W\leq\kappa_{0}\sqrt{NS},$

where $\kappa_{0}$ is a constant:
$\kappa_{0}=\max_{i}\sum_{i=1}^{N}\frac{U}{\lambda_{i}^{o}+\mu_{i}^{o}}$.

####  6.1.2 Hyperstable networks

This is another type of networks for which an explicit bound on the coupling
time exists. A network is called hyperstable if for each queue $i$,
$\sum_{j}L_{ji}\mu_{j}^{o}+L_{0i}\lambda<\mu_{i}^{o}$.

As in the acyclic case, the threshold policy under which the coupling time is
the largest is when all jobs are admitted. Under this policy, as for the
acyclic case, the coupling time is upper bounded by the coupling in an open
network where all the $N$ queues have buffers bounded by $S$.

Coupling times of hyperstable networks with finite buffer queues have been
studied in [30], where the following bound is given (Theorem 2):

$\max_{x,y}{\mathbb{E}}[\tau_{x,y}]\leq\kappa_{2}N^{2}S\sum_{i=1}^{N}\frac{\lambda_{i}^{o}}{\mu_{i}^{o}-\lambda_{i}^{o}},$
(25)

where $\kappa_{2}$ is a constant. Using Equation (22) and (23), this induces a
similar bound on the term $W$ in the regret:

$W\leq\kappa_{3}N\sqrt{S},$

where $\kappa_{3}$ is yet another constant.

###  6.2 Making the algorithm oblivious to $\rho$

By construction, the current version of UCRL-M uses explicitly $\tau_{\rm
mix}=5\log T/\log\rho^{-1}$ modules. This can be a problem as it implies an a
priori knowledge of $\rho$, and of the mixing time (or at least an upper
bound) of the network being learned.

These types of assumptions are sometimes made in the reinforcement learning
literature. For example, the UCBVI algorithm [31] requires the knowledge of
the diameter of the MDP being learned.

Here, we can patch UCRL-M to make it oblivious to $\rho$ by making sure that
$\tau_{\rm mix}\geq 5\log T/\log\rho^{-1}$ for any large enough $T$. For
example, one can chose $\tau_{\rm mix}:=\log^{2}(T)$, as it is asymptotically
larger than the previous one. This patch adds a multiplicative $\log(T)$ term
in the asymptotic bound of the regret given in Theorem 5.1.

##  7 Numerical experiments

###  7.1 A multi-tier queueing network

To assess the performance of UCRL-M, we rely on a standard multi-tier queueing
network as displayed in Figure 3. The topology of this network is composed of
three tiers. Namely, tiers 1, 2 and 3 represent the web, application and
database stages of a typical web-application request. Each tier is composed of
multiple servers, each with its own queue. After accessing the web tier, a
request may either return back to the issuing user with probability $1-p$ or
flow through the application and database tiers. This multi-tier structure is
common in empirical studies of computer systems [32] and is the default
architecture of web applications deployed on Amazon Elastic Compute Cloud
(EC2) [33].

$1/n$$\lambda$$S-s$jobs outsidereject$1/n$$1/n$$p/n$$1-p$admit

Figure 3: A queueing network model with three interconnected tiers. Each tier
contains $n$ queues and the total capacity is of $S$ jobs.

This model may be studied as an example of the generic case described in
Section 2. Notice that given the routing from Figure 3, the stability
condition is met if $\frac{\lambda}{1-p}<\mu$, where
$\mu=\mu_{1}^{o}=\ldots=\mu_{3n}^{o}$ is the service rate of the queues in the
network.

###  7.2 Regret of UCRL-M on the multi-tier queueing network

We provide the performance of UCRL-M over the queueing network described above
when the number of queues per tier $n$ and the total number of jobs $S$ vary.
In Figure 4, we display the average regret over $66$ runs of the UCRL-M
algorithm when $n$ varies, and with parameters scaling with $n$ to keep the
systems proportionally comparable. More precisely, the scaling in $S$ and
$\mu$ is such that as the number of queues increases, the waiting time in each
tier remains roughly identical for a job in each tier, and the scaling in the
holding cost is also consistent with the increase of the number of jobs in the
system. Notice that for our choice of parameters, the network is not stable,
so that we use the UCRL-M algorithm under more general conditions than those
assumed in Section 6 and even in Section 2.

In Figure 4, we remark that as we let the number of queues $n$ (and the number
of jobs $S$) scales multiplicatively, the regret is increasing in $\log(S)$.
Knowing that the dependency in $S$ of the regret bound from Theorem 5.1 mainly
comes from $\rho$, this is much slower than the square root bounds given in
Section 6 (under strong assumptions). This can be interpreted as the bound of
equation 21 being too large as it considers the mixing from the worst state,
while in average it is more likely for the algorithm to mix from states that
are visited the most, which are already close to stationary states.

Parameter | Value
---|---
$S$ | $\frac{10}{3}n$
$\lambda$ | $0.99$
$\mu$ | $\frac{1}{n}$
$\gamma_{{\rm reject}}$ | $10$
$\gamma_{{\rm hold}}$ | $\frac{4}{3n}$
$U$ | $\lambda+3n\mu$
$p$ | $0.2$
$\tau_{\rm mix}$ | $3$

Figure 4: Regret of the UCRL-M algorithm on the queueing network for different
values of $n$ and scaling parameters. Figure 5: Average threshold chosen as a
function of time.

In Figure 5, we can see the convergence to the optimal threshold for each
value of $n$. It suggests that the optimal threshold is scaling linearly with
$n$, and that the convergence is slower as $S$ increases.

In the previous experiments, the number of modules is arbitrarily fixed to
$\tau_{\rm mix}=3$. Now, we perform another experiment to observe the
dependency of the regret in the choice of $\tau_{\rm mix}$ for this queueing
system. The intuition is the following: as explained in the high-level
description of the algorithm in Subsection 4.1, UCRL-M could be compared to
$\tau_{\rm mix}$ instances of UCRL2 [5], where all modules but the best one is
discarded at each episode. This best module runs on roughly
$\frac{T}{\tau_{\rm mix}}$ time-steps, and its regret can be compared to
$\frac{1}{\tau_{\rm mix}}$ times the expected regret of UCRL-M. With this
intuition in mind, we plot in Figure 6 the regret of UCRL-M, where we rescaled
both the regret and the time-steps by a factor $\frac{1}{\tau_{\rm mix}}$.

Parameter | Value
---|---
$S$ | $20$
$n$ | $6$
$\lambda$ | $0.99$
$\mu$ | $\frac{1}{n}$
$\gamma_{{\rm reject}}$ | $10$
$\gamma_{{\rm hold}}$ | $\frac{4}{3n}$
$U$ | $\lambda+3n\mu$
$p$ | $0.2$

Figure 6: Rescaled regret of the UCRL-M algorithm on the queueing network for
different values of $\tau_{\rm mix}$.

Within the considered queueing model, we notice that the modules do not seem
to bring any practical upside because the regret is almost perfectly linear in
the number of modules. However, they remain necessary to guarantee the
correctness of the confidence sets and to get the theoretical bound on the
regret given in Theorem 5.1.

##  8 Conclusion

In the context of queueing networks, we have shown that efficient learning in
POMDPs is possible. Provided that the learner’s objective is to learn the
optimal admission control policy, which is a problem appearing in a number of
applications as discussed in Section 2, we have proposed UCRL-M, an optimistic
algorithm whose regret is independent of the diameter $D$, i.e., a quantity
that appears in most of the existing regret analyses [5] and that is
exponential in the size of the space $S$ in most queueing systems.

While our result strongly relies on Norton’s equivalent theorem, which only
applies exactly to product-form queueing networks, our main perspective is
that this type of results under partial observations may be found in several
other models from queueing theory. In fact, Norton’s theorem has been
generalized to multiclass networks [34] and also used in the context of non-
product-form queueing networks for approximate analysis [25].

## References

  *   * Walkins [1989] Walkins, C.J.: Learning from delayed rewards. PhD thesis, Cambridge University (1989)
  * Jin et al. [2020] Jin, C., Yang, Z., Wang, Z., Jordan, M.I.: Provably efficient reinforcement learning with linear function approximation. In: Abernethy, J., Agarwal, S. (eds.) Proceedings of Thirty Third Conference on Learning Theory. Proceedings of Machine Learning Research, vol. 125, pp. 2137–2143 (2020)
  * Ouyang et al. [2017a] Ouyang, Y., Gagrani, M., Nayyar, A., Jain, R.: Learning unknown Markov decision processes: A Thompson sampling approach. arXiv preprint arXiv:1709.04570 (2017)
  * Ouyang et al. [2017b] Ouyang, Y., Gagrani, M., Nayyar, A., Jain, R.: Learning unknown markov decision processes: A thompson sampling approach. In: 31st Conference on Neural Information Processing Systems, Long Beach, CA, USA (2017)
  * Jaksch et al. [2010] Jaksch, T., Ortner, R., Auer, P.: Near-optimal regret bounds for reinforcement learning. Journal of Machine Learning Research 11(4), 1563–1600 (2010)
  * Fruit et al. [2018] Fruit, R., Pirotta, M., Lazaric, A., Ortner, R.: Efficient bias-span-constrained exploration-exploitation in reinforcement learning (2018)
  * [7] Tossou, A., Basu, D., Dimitrakakis, C.: Near-optimal Optimistic Reinforcement Learning using Empirical Bernstein Inequalities. https://doi.org/10.48550/ARXIV.1905.12425 . https://arxiv.org/abs/1905.12425
  * [8] Model-free Reinforcement Learning in Infinite-horizon Average-reward Markov Decision Processes. In: Proceedings of the 37th International Conference on Machine Learning. Proceedings of Machine Learning Research, vol. 119. https://proceedings.mlr.press/v119/wei20c.html
  * [9] Jin, C., Kakade, S., Krishnamurthy, A., Liu, Q.: Sample-efficient reinforcement learning of undercomplete pomdps. In: Larochelle, H., Ranzato, M., Hadsell, R., Balcan, M.F., Lin, H. (eds.) Advances in Neural Information Processing Systems, pp. 18530–18539
  * Azizzadenesheli et al. [2016] Azizzadenesheli, K., Lazaric, A., Anandkumar, A.: Reinforcement learning of POMDPs using spectral methods. In: COLT. JMLR Workshop and Conference Proceedings, vol. 49, pp. 193–256 (2016)
  * [11] Guo, Z.D., Doroudi, S., Brunskill, E.: A PAC RL algorithm for episodic pomdps. In: AISTATS. JMLR Workshop and Conference Proceedings, vol. 51, pp. 510–518
  * Papadimitriou and Tsitsiklis [1987] Papadimitriou, C.H., Tsitsiklis, J.N.: The complexity of markov decision processes (1987)
  * Vlassis et al. [2012] Vlassis, N., Littman, M.L., Barber, D.: On the computational complexity of stochastic controller optimization in pomdps (2012)
  * Even-Dar et al. [2005] Even-Dar, E., Kakade, S.M., Mansour, Y.: Reinforcement learning in POMDPs without resets. (2005)
  * [15] Ross, S., Chaib-draa, B., Pineau, J.: Bayes-adaptive POMDPs. In: Platt, J., Koller, D., Singer, Y., Roweis, S. (eds.) Advances in Neural Information Processing Systems
  * Poupart and Vlassis [2008] Poupart, P., Vlassis, N.A.: Model-based bayesian reinforcement learning in partially observable domains. In: International Symposium on Artificial Intelligence and Mathematics (2008)
  * Anselmi et al. [2022] Anselmi, J., Gaujal, B., Rebuffi, L.-S.: Reinforcement Learning in a Birth and Death Process: Breaking the Dependence on the State Space. In: NeurIPS 2022 - 36th Conference on Neural Information Processing Systems, New Orleans, United States (2022). https://hal.science/hal-03799394
  * Borgs et al. [2014] Borgs, C., Chayes, J., Doroudi, S., Harchol-Balter, M., Xu, K.: The optimal admission threshold in observable queues with state dependent pricing. In: Probability in the Engineering and Informational Sciences 28, pp. 101–110 (2014). https://www.microsoft.com/en-us/research/publication/optimal-admission-threshold-observable-queues-state-dependent-pricing/
  * Xia [2014] Xia, L.: Event-based optimization of admission control in open queueing networks (2014)
  * Chandy et al. [1975] Chandy, K.M., Herzog, U., Woo, L.: Parametric analysis of queuing networks. IBM Journal of Research and Development 19(1), 36–42 (1975) https://doi.org/10.1147/rd.191.0036
  * Rolia and Sevcik [1995] Rolia, J.A., Sevcik, K.C.: The method of layers. IEEE Transactions on Software Engineering 21(8), 689–700 (1995) https://doi.org/%****␣questa.bbl␣Line␣325␣****10.1109/32.403785
  * Rolia et al. [2009] Rolia, J., Casale, G., Krishnamurthy, D., Dawson, S., Kraft, S.: Predictive modelling of sap erp applications: Challenges and solutions. (2009)
  * [23] Configuring Concurrency in Knative. https://knative.dev/docs/serving/autoscaling/concurrency/. Online; accessed: 2023-01-30 (2022)
  * Wang et al. [2022] Wang, R., Casale, G., Filieri, A.: Estimating multiclass service demand distributions using markovian arrival processes (2022)
  * Krieger [2008] Krieger, U.R.: Queueing networks and markov chains, 2nd edition by g. bolch, s. greiner, h. de meer, and k.s. trivedi. IIE Transactions 40(5), 567–568 (2008)
  * Kameda [1984] Kameda, H.: A property of normalization constants for closed queueing networks. IEEE Transactions on Software Engineering SE-10(6), 856–857 (1984) https://doi.org/10.1109/TSE.1984.5010314
  * Puterman [2014] Puterman, M.L.: Markov Decision Processes: Discrete Stochastic Dynamic Programming, (2014)
  * Levin et al. [2008] Levin, D.A., Peres, Y., Wilmer, E.L.: Markov Chains and Mixing Times, (2008)
  * Dopper et al. [2006] Dopper, J.G., Gaujal, B., Vincent, J.-M.: Bounds for the coupling time in queueing networks perfect simulation. In: Langville, A.N., Stewart, W.J. (eds.) MAM, 150th Anniversary of A.A. Markov, Charleston, SC (2006)
  * Anselmi and Gaujal [2014] Anselmi, J., Gaujal, B.: Efficiency of simulation in monotone hyper-stable queueing networks. Queueing Systems 76(1), 51–72 (2014) https://doi.org/10.1007/s11134-013-9357-7
  * Azar et al. [2017] Azar, M.G., Osband, I., Munos, R.: Minimax regret bounds for reinforcement learning. In: International Conference on Machine Learning, pp. 263–272 (2017)
  * Urgaonkar et al. [2005] Urgaonkar, B., Pacifici, G., Shenoy, P., Spreitzer, M., Tantawi, A.: An analytical model for multi-tier internet services and its applications (2005)
  * [33] AWS Architecture Center. https://aws.amazon.com/architecture. Online; accessed: 2023-06-19 (2022)
  * Kritzinger et al. [1982] Kritzinger, P.S., van Wyk, S., Krzesinski, A.E.: A generalisation of norton’s theorem for multiclass queueing networks. Performance Evaluation 2(2), 98–107 (1982) https://doi.org/10.1016/0166-5316(82)90002-5
  * Bhandari et al. [2018] Bhandari, J., Russo, D., Singal, R.: A finite time analysis of temporal difference learning with linear function approximation. In: Bubeck, S., Perchet, V., Rigollet, P. (eds.) Proceedings of the 31st Conference On Learning Theory. Proceedings of Machine Learning Research, vol. 75, pp. 1691–1692 (2018)
  * Ipsen and Meyer [1994] Ipsen, I.C.F., Meyer, C.D.: Uniform stability of markov chains. SIAM Journal on Matrix Analysis and Applications 15, 1061–1074 (1994)

##  Appendix A Proof of Theorem 5.1

###  A.1 Terms for the ramping phases

We first briefly deal with the terms coming from the ramping phases $\Phi$ of
the episodes, $R_{\rm ramp}$. We have:

$R_{\rm ramp}=\sum_{k}\sum_{t=t_{k}}^{t_{k}+\tau_{\rm
mix}-1}r(s_{t},\tilde{\pi}_{k}(s,t))\leq K\tau_{\rm mix}r_{\max}\leq
r_{\max}SA\tau_{\rm mix}^{2}\log_{2}\left(\frac{8T}{SA\tau_{\rm mix}}\right),$
(26)

where in the last inequality we used Lemma C.2. Assuming $\tau_{\rm mix}SA\geq
4$, and using $\log(2)\geq\frac{1}{2}$, we rewrite it:

$R_{\rm ramp}\leq 2r_{\max}SA\tau_{\rm mix}^{2}\log(2T).$ (27)

This term is therefore among the lower-order terms of the regret.

###  A.2 Terms in the confidence bound

We start with the terms coming from the case where the MDP is out of the
confidence regions $\mathcal{M}_{k}$. For each episode $k$, we define:

  * •

$V_{k}^{(m)}(s)$ the number of visits of state $s$ during episode $k$ in
module $m$.

  * •

$N_{t}^{(m)}(s)$ is the number of visits of state $s$ until time-step $t$
excluded, in module $m$.

  * •

$\mathcal{M}(t)$ the set of MDPs $\mathcal{M}_{k}$ such that $t_{k}\leq
t<t_{k+1}$

For the terms out of the confidence sets, we have:

$\displaystyle R_{\rm out}$ $\displaystyle\leq
r_{\max}\sum_{m}\sum_{s}\sum_{k=1}^{K}V_{k}^{(m)}(s)\mathds{1}_{M\notin\mathcal{M}_{k}}$
$\displaystyle\leq
r_{\max}\sum_{m}\sum_{s}\sum_{k=1}^{K}N_{t_{k}}^{(m)}(s)\mathds{1}_{M\notin\mathcal{M}_{k}}\text{
using the stopping criterion}$
$\displaystyle=r_{\max}\sum_{t=1}^{T}\sum_{s}\sum_{k=1}^{K}\mathds{1}_{t_{k}=t}N_{t}(s)\mathds{1}_{M\notin\mathcal{M}(t)}\leq
r_{\max}\sum_{t=1}^{T}\sum_{s}N_{t}(s)\mathds{1}_{M\notin\mathcal{M}(t)}$
$\displaystyle=r_{\max}\sum_{t=1}^{T}\mathds{1}_{M\notin\mathcal{M}(t)}\sum_{s}N_{t}(s)\leq
r_{\max}\sum_{t=1}^{T}t\mathds{1}_{M\notin\mathcal{M}(t)}.$

We now need Lemma D.2 to control the probability that the MDP fails to be
within the confidence bounds
$\mathbb{P}\left\\{M\notin\mathcal{M}(t)\right\\}$. Taking the expectations
and using Lemma D.2, we obtain

$\displaystyle\mathbb{E}\left[R_{\rm out}\right]$ $\displaystyle\leq
r_{\max}\sum_{t=1}^{T}t{\mathbb{P}}\left\\{M\notin\mathcal{M}(t)\right\\}\leq
r_{\max}\sum_{t=1}^{T}\frac{S^{\prime}+16CS^{\prime}A}{2t^{2}}\leq
r_{\max}(S^{\prime}+16CS^{\prime}A).$ (28)

This term is constant in $T$ and therefore it does not significantly
contribute to the regret.

###  A.3 Split of confidence bound

We assume that $M\in\mathcal{M}_{k}$ and to simplify the notations, we will
omit the use of the indicator functions ${\mathds{1}}_{M\in\mathcal{M}_{k}}$.
For each episode $k$ and module $m$, let us define

  * •

$R_{{\rm in},k}^{(m)}:=\sum_{s}R_{k}^{(m)}$,

  * •

$\tilde{\pi}_{k}$ the optimistic policy,

  * •

$\tilde{P}_{k}:=\left(\tilde{p}_{k}(s^{\prime}|s,\tilde{\pi}_{k}(s))\right)$
the transition matrix of policy $\tilde{\pi}_{k}$ on the optimistic MDP
$\tilde{M}_{k}$,

  * •

$\mathbf{v}_{k}^{(m)}:=\left(V_{k}(s,\tilde{\pi}_{k}\right)$ the row vector of
visit counts,

  * •

$\mathbf{h}_{k}$ the bias vector of the Markov chain in the true MDP $M$ with
policy $\tilde{\pi}_{k}$.

Now, we split the regret term $R_{\rm in}^{(m)}$ into subterms that have
different meaning. Assuming $M\in\mathcal{M}_{k}$ and using Lemma B.1 on the
accuracy of EVI, we get:

$\displaystyle R_{{\rm in},k}^{(m)}$
$\displaystyle=\sum_{s,a}V_{k}^{(m)}(s,a)(g^{*}-r(s,a))$
$\displaystyle\leq\sum_{s,a}V_{k}^{(m)}(s,a)(\tilde{g}_{k}-r(s,a))+\varepsilon_{k}\sum_{s,a}V_{k}^{(m)}(s,a)$
$\displaystyle=\sum_{s,a}V_{k}^{(m)}(s,a)(\tilde{g}_{k}-\tilde{r}_{k}(s,a))+\sum_{s,a}V_{k}^{(m)}(s,a)(\tilde{r}_{k}(s,a)-r(s,a)+\varepsilon_{k}).$

In the next few steps, we will focus on rewriting the first sum. With (43) and
using the definition of the iterated values from EVI, we have for a given
state $s$ and $a_{s}:=\tilde{\pi}_{k}(s)$:

$\left|\left(\tilde{g}_{k}-\tilde{r}_{k}(s,a_{s})\right)-\left(\sum_{s^{\prime}}\tilde{p}_{k}(s^{\prime}|s,a_{s})u^{(k)}_{i}(s^{\prime})-u^{(k)}_{i}(s)\right)\right|\leq\varepsilon_{k},$

so that:

$R_{{\rm
in},k}^{(m)}\leq\mathbf{v}_{k}^{(m)}\left(\tilde{\mathbf{P}}_{k}-\mathbf{I}\right)\mathbf{u}_{i}+\sum_{s,a}V_{k}^{(m)}(s,a)(\tilde{r}_{k}(s,a)-r(s,a))+\varepsilon_{k}\sum_{s,a}V_{k}^{(m)}(s,a).$

Again, with $\mathbf{\tilde{h}}_{k}$ being the bias of the average optimal
policy for the optimist MDP, define:

$d_{k}(s):=\left(u^{(k)}_{i}(s)-\min_{x}u^{(k)}_{i}(x)\right)-\left(\mathbf{\tilde{h}}_{k}(s)-\min_{x}\mathbf{\tilde{h}}_{k}(x)\right).$

Then for any $s$: $\left|d_{k}(s)\right|\leq\varepsilon_{k}.$

Notice that the unit vector is in the kernel of
$\left(\tilde{\mathbf{P}}_{k}-\mathbf{I}\right)$. Therefore, in the first
term, we can replace $\mathbf{u}_{i}$ by any translation of it. We get:

$\mathbf{v}_{k}^{(m)}\left(\tilde{\mathbf{P}}_{k}-\mathbf{I}\right)\mathbf{u}_{i}=\mathbf{v}_{k}^{(m)}\left(\tilde{\mathbf{P}}_{k}-\mathbf{I}\right)\mathbf{\tilde{h}}_{k}+\mathbf{v}_{k}^{(m)}\left(\tilde{\mathbf{P}}_{k}-\mathbf{I}\right)\mathbf{d}_{k}.$

so that, using the definition of $\varepsilon_{k}$, we have that overall:

$R_{\rm
in}^{(m)}\leq\underbrace{\sum_{k}\mathbf{v}_{k}^{(m)}\left(\tilde{\mathbf{P}}_{k}-\mathbf{I}\right)\mathbf{\tilde{h}}_{k}}_{R_{\rm
bias}^{(m)}}+\underbrace{\sum_{k}\mathbf{v}_{k}^{(m)}\left(\tilde{\mathbf{P}}_{k}-\mathbf{I}\right)\mathbf{d}_{k}+2\delta_{\max}\sum_{k}\sum_{s,a}\frac{V_{k}^{(m)}(s,a)}{\sqrt{t_{k}}}}_{R_{\rm
EVI}^{(m)}}\\\
+\underbrace{\sum_{k}\sum_{s,a}V_{k}^{(m)}(s,a)(\tilde{r}_{k}(s,a)-r(s,a))}_{R_{\rm
rewards}^{(m)}}$

We can already further simplify the term related to EVI. Notice that:

$\displaystyle\mathbf{v}_{k}^{(m)}\left(\tilde{\mathbf{P}}_{k}-\mathbf{I}\right)\mathbf{d}_{k}$
$\displaystyle\leq\sum_{s}V_{k}\left(s,\tilde{\pi}_{k}(s)\right)\cdot\left\|\tilde{p}_{k}\left(\cdot|s,\tilde{\pi}_{k}(s)\right)-\mathds{1}_{s}\right\|_{1}\cdot\sup_{s^{\prime}}|d_{k}(s^{\prime})|$
$\displaystyle\leq
2\varepsilon_{k}\sum_{s}V_{k}^{(m)}\left(s,\tilde{\pi}_{k}(s)\right)\leq
2\delta_{\max}\sum_{s,a}\frac{V_{k}^{(m)}\left(s,a\right)}{\sqrt{t_{k}}}$
$\displaystyle\leq
2\delta_{\max}\sum_{s,a}\frac{V_{k}^{(m)}(s,a)}{\sqrt{\max{\\{1,N_{t_{k}}^{(m_{k}(s,a))}(s,a)\\}}}},$

where in the last inequality we used that
$\max\\{1,N_{t_{k}}^{(m_{k}(s,a))}(s,a)\\}\leq t_{k}\leq T$. Thus, for
$T\geq\frac{e^{2}}{2AT}$ the regret term coming from the consequences and
approximations of EVI satisfies

$R_{\rm
EVI}^{(m)}\leq\delta_{\max}2\sqrt{2\log(2AT)}\sum_{k}\sum_{s,a}\frac{V_{k}^{(m)}(s,a)}{\sqrt{\max{\\{1,N_{t_{k}}^{(m_{k}(s,a))}(s,a)\\}}}}.$
(29)

Let us now deal with the term $R_{\rm rewards}^{(m)}$, as it will be bounded
by a similar term as in equation (29). Indeed, as $M\in\mathcal{M}_{k}$, we
may use that both the optimistic and true rewards are within the confidence
region from equation 16, and use that $t_{k}<T$, so that:

$R_{\rm
rewards}^{(m)}\leq\delta_{\max}2\sqrt{2\log(2AT)}\sum_{k}\sum_{s,a}\frac{V_{k}(s,a)}{\sqrt{\max{\\{1,N_{t_{k}}^{(m_{k}(s,a))}(s,a)\\}}}}$
(30)

On the other hand, we can also split more precisely the term that depends on
the bias. Define $P_{k}$ as the transition matrix of the optimistic policy
$\tilde{\pi}_{k}$ in the true MDP $M$. We get

$R_{\rm
in}^{(m)}\leq\underbrace{\sum_{k}\mathbf{v}_{k}^{(m)}\left(\tilde{\mathbf{P}}_{k}-\mathbf{P}_{k}\right)\mathbf{h}_{k}}_{R_{\rm
trans}^{(m)}}+\underbrace{\sum_{k}\mathbf{v}_{k}^{(m)}\left(\tilde{\mathbf{P}}_{k}-\mathbf{P}_{k}\right)\left(\mathbf{\tilde{h}}_{k}-\mathbf{h}_{k}\right)}_{R_{\rm
diff}^{(m)}}+\underbrace{\sum_{k}\mathbf{v}_{k}^{(m)}\left(\mathbf{P}_{k}-\mathbf{I}\right)\mathbf{\tilde{h}}_{k}}_{R_{\rm
ep}^{(m)}}\\\
+\underbrace{\delta_{\max}4\sqrt{2\log(2AT)}\sum_{k}\sum_{s,a}\frac{V_{k}^{(m)}(s,a)}{\sqrt{\max{\\{1,N_{t_{k}}^{(m_{k}(s,a))}(s,a)\\}}}}}_{R_{\rm
EVI}^{(m)}+R_{\rm rewards}^{(m)}}.$ (31)

Now that we split the regret into several terms, we still need to sum over the
modules and analyze for each term its contribution to the regret. For
instance, we can sum over the modules the terms depending on EVI and the
reward differences to get:

$R_{\rm EVI}+R_{\rm
rewards}=\delta_{\max}4\sqrt{2\log(2AT)}\sum_{k}\sum_{s,a}\frac{V_{k}(s,a)}{\sqrt{\max{\\{1,N_{t_{k}}^{(m_{k}(s,a))}(s,a)\\}}}}.$
(32)

This term is related to the choice of the confidence bounds, and it will
contribute to the main term of the regret. Regarding the other terms, $R_{\rm
trans}^{(m)}$ will also use the confidence bounds on the transition as well as
our knowledge of the bias in the true MDP. $R_{\rm diff}^{(m)}$ will be a
lower order term in the regret, using the confidence bounds for both the
comparisons between the transitions and the biases. Finally, $R_{\rm
ep}^{(m)}$ will be related to the count of episodes, so that it will also be a
lower order term. The discussion for each of these terms will be spread over
the next subsections.

###  A.4 Bound on $R_{\rm trans}^{(m)}$

To bound $R_{\rm trans}^{(m)}$, we can follow the computations from [17]. We
will use our knowledge of the bias $\mathbf{h}_{k}$ and the control on the
transitions in the optimistic MDP to simplify the regret term.

Notice that for a fixed state $1\leq s\leq S-1$:

$\sum_{s^{\prime}}p\left(s^{\prime}|s,\tilde{\pi}_{k}(s)\right)h_{k}(s^{\prime})=\sum_{s^{\prime}}p\left(s^{\prime}|s,\tilde{\pi}_{k}(s)\right)\left(h_{k}(s^{\prime})-h_{k}(s)\right)+h_{k}(s).$

The same is true for $\tilde{p}_{k}$, and knowing the MDP is a birth and death
process:

$\displaystyle R_{\rm trans}^{(m)}$
$\displaystyle=\sum_{k}\sum_{s}\sum_{s^{\prime}}V_{k}^{(m)}\left(s,\tilde{\pi}_{k}(s)\right)\cdot\left(\tilde{p}_{k}\left(s^{\prime}|s,\tilde{\pi}_{k}(s)\right)-p\left(s^{\prime}|s,\tilde{\pi}_{k}(s)\right)\right)\cdot
h_{k}(s^{\prime})$
$\displaystyle=\sum_{k}\sum_{s}\sum_{s^{\prime}}V_{k}^{(m)}\left(s,\tilde{\pi}_{k}(s)\right)\left(\tilde{p}_{k}\left(s^{\prime}|s,\tilde{\pi}_{k}(s)\right)-p\left(s^{\prime}|s,\tilde{\pi}_{k}(s)\right)\right)\cdot\left(h_{k}(s^{\prime})-h_{k}(s)\right)$
$\displaystyle\leq\sum_{k}\sum_{s}V_{k}^{(m)}\left(s,\tilde{\pi}_{k}(s)\right)\left\|\tilde{p}_{k}\left(\cdot|s,\tilde{\pi}_{k}(s)\right)-p\left(\cdot|s,\tilde{\pi}_{k}(s)\right)\right\|_{1}\max\left\\{\Delta^{\tilde{\pi}_{k}}(s),\Delta^{\tilde{\pi}_{k}}(s+1)\right\\}$
$\displaystyle\leq
4\sqrt{2\log\left(2AT\right)}\sum_{k}\sum_{s,a}\frac{\Delta(s+1)V_{k}^{(m)}(s,a)}{\sqrt{\max\\{1,N_{t_{k}}^{(m_{k}(s,a))}(s,a)\\}}},$

where $\Delta$ is the difference of bias in the last inequality, we used the
bound on the variations of the bias from Proposition F.4, and that the
optimistic MDP has transitions close to the true transitions with inequality
(17). Notice that the final term looks similar to the term coming from EVI and
rewards related computations (32). We will deal with these terms together in
the next subsection, as they are both mainly contributing to the regret.

###  A.5 Bound on the main term

In the previous Section A.4, we have shown that:

$R_{\rm trans}^{(m)}\leq
4\sqrt{2\log\left(2AT\right)}\sum_{s,a}\frac{\Delta(s+1)V_{k}^{(m)}(s,a)}{\sqrt{\max\\{1,N_{t_{k}}^{(m_{k}(s,a))}(s,a)\\}}}.$

Summing over the modules $m$, we get:

$R_{\rm trans}\leq
4\sqrt{2\log\left(2AT\right)}\sum_{s,a}\frac{\Delta(s+1)V_{k}(s,a)}{\sqrt{\max\\{1,N_{t_{k}}^{(m_{k}(s,a))}(s,a)\\}}}.$
(33)

We now wish to control this term, $R_{\rm EVI}$ and $R_{\rm rewards}$ using
our knowledge of the bias, rather than bounding it directly with the diameter
$D$. We first sum over the episodes and take the expectation, so that with
Lemma C.1, and using that $N_{t_{k}}^{(m_{k}(s,a))}(s,a)\geq\frac{1}{\tau_{\rm
mix}}N_{t_{k}}(s,a)$ we had from equation (13), we get:

$\displaystyle\mathbb{E}\left[\sum_{s,a}\sum_{k}\frac{\sqrt{\tau_{\rm
mix}}V_{k}(s,a)}{\sqrt{\max\\{1,N_{t_{k}}(s,a)\\}}}\right]$ $\displaystyle\leq
3\mathbb{E}\left[\sum_{s,a}\sqrt{\tau_{\rm mix}N_{T}(s,a)}\right]$
$\displaystyle\leq 3\sum_{s}\sqrt{\tau_{\rm
mix}\mathbb{E}\left[N_{T}(s)\right]A},\,\quad\text{ by Jensen's inequality.}$

Therefore:

$R_{\rm trans}\leq 12\sqrt{2A\tau_{\rm
mix}\log\left(2AT\right)}\sum_{s=0}^{S}\Delta(s+1)\sqrt{{\mathbb{E}}\left[N_{T}(s)\right]}.$
(34)

This is one of the terms mainly contributing to the regret, the other one
being, doing similar computations:

$R_{\rm EVI}+R_{\rm rewards}\leq 12\delta_{\max}\sqrt{2A\tau_{\rm
mix}\log\left(2AT\right)}\sum_{s\geq
0}\sqrt{{\mathbb{E}}\left[N_{T}(s)\right]}$ (35)

Now, let $N_{T}^{\pi^{\max}}$ be the number of visits when the starting state
is sampled randomly from the initial distribution $\nu^{\pi^{\max}}$ and the
policy $\pi^{\max}$ is always chosen. By stochastic ordering, as
$N_{T}(s)\leq_{st}N_{T}^{\pi^{\max}}$, we have
${\mathbb{E}}\left[N_{T}(s)\right]\leq{\mathbb{E}}\left[N_{T}^{\pi^{\max}}\right]=T\nu^{\pi^{\max}}(s)$.
We can therefore rewrite the main contributing term to the regret as:

$12\sqrt{2A\tau_{\rm mix}T\log\left(2A\tau_{\rm
mix}T\right)}\sum_{s=0}^{S}\left(\Delta(s+1)+\delta_{\max}\right)\sqrt{\nu^{\pi^{\max}}(s)}.$
(36)

Replace in the equation the choice $\tau_{\rm mix}=5\log T/\log\rho^{-1}$ and
recall that we had, from Proposition F.4,
$\Delta(s):=2\delta_{\max}\nu^{\pi^{\max}}(0)^{-1}\sum_{i=1}^{s}\frac{U}{\mu(i)}\leq
2\delta_{\max}\nu^{\pi^{\max}}(0)^{-1}\frac{U}{\mu(1)}s$. Using Lemma F.1,
since

$\displaystyle\sum_{s=0}^{S}\left(\Delta(s+1)+\delta_{\max}\right)\sqrt{\nu^{\pi^{\max}}(s)}$
$\displaystyle\leq
3\delta_{\max}\nu^{\pi^{\max}}(0)^{-1}\frac{U}{\mu(1)}\sum_{s=0}^{S}(s+1)\sqrt{\nu^{\pi^{\max}}(s)}$
$\displaystyle\leq
3\delta_{\max}\nu^{\pi^{\max}}(0)^{-1/2}\frac{U}{\mu(1)}\sqrt{C_{1}}\sum_{s\geq
0}s\left(\frac{\lambda}{\mu(i_{0})}\right)^{s/2}$ $\displaystyle\leq
3\delta_{\max}\nu^{\pi^{\max}}(0)^{-1/2}\frac{U}{\mu(1)}\sqrt{C_{1}}\frac{1}{\left(1-\sqrt{\frac{\lambda}{\mu(i_{0})}}\right)^{2}}$
$\displaystyle\leq
3\delta_{\max}\frac{U}{\mu(1)}C_{1}\frac{1}{\left(1-\sqrt{\frac{\lambda}{\mu(i_{0})}}\right)^{3}},$

then, assuming $\tau_{\rm mix}\leq T$, the main term is upper bounded by:

$72\delta_{\max}\frac{U}{\mu(1)}C_{1}{\left(1-\sqrt{\frac{\lambda}{\mu(i_{0})}}\right)^{-3}}\log\left(AT\right)\sqrt{5AT\log^{-1}(\rho^{-1})}.$
(37)

###  A.6 Bound on $R_{\rm diff}^{(m)}$

We now deal with the term involving the difference of bias $R_{\rm
diff}^{(m)}$, defined in equation 31. The proof mainly follows the one from
[17], with a final tweak to relate the visits from a module to the total
number of visits. Notice that we cannot directly use the confidence regions to
control the difference between $\mathbf{\tilde{h}}_{k}$ and $\mathbf{h}_{k}$,
so that we will need Lemma E.4, and we are interested in controlling
$\|\mathbf{\tilde{h}}_{k}-\mathbf{h}_{k}\|_{\infty}$.

Fix the module $m$ and the episode $k$, with policy $\tilde{\pi}_{k}$. Choose
a state minimizing
$N_{t_{k}}^{(m_{k}(s,\tilde{\pi}_{k}(s)))}(s,\tilde{\pi}_{k}(s))$, and call
this state $x_{k}$, $a_{k}:=\tilde{\pi}_{k}(x_{k})$ and
$m^{\prime}:=m_{k}(x_{k},a_{k})$: for this state, the confidence bounds are at
their worst, and
$\sqrt{\frac{\log\left(2At_{k}\right)}{\max\\{1,N_{t_{k}}^{(m^{\prime})}(x_{k},a_{k})\\}}}$
is maximal for episode $k$. This means that controlling the number of visits
of the worst state lets us control the number of visits for any state. As the
true MDP is within the confidence bounds, with a triangle inequality we get:

$\|\tilde{P}_{k}-P_{k}\|_{\infty}\leq
4\sqrt{\frac{2\log\left(2At_{k}\right)}{\max\\{1,N_{t_{k}}^{(m^{\prime})}(x_{k},a_{k})\\}}}.$

We now want to use Lemma E.4. In our case, notice that in the true MDP we have
$D\geq T_{hit}^{\tilde{\pi}_{k}}\geq 1$ for $S$ large enough. Remark also that
$D^{\tilde{\pi}_{k}}$ can be replaced by $D$ in the last inequality of the
proof of E.4, as $\mbox{span}(h^{\tilde{\pi}_{k}})\leq D$ by construction of
$\tilde{\pi}_{k}$ with EVI, following the same argument as in [5, Equation
(11)].

$\|\mathbf{\tilde{h}}_{k}-\mathbf{h}_{k}\|_{\infty}\leq
8r_{\max}D^{2}\sqrt{\frac{2\log\left(2At_{k}\right)}{\max\\{1,N_{t_{k}}^{(m^{\prime})}(x_{k},a_{k})\\}}}.$
(38)

Hence,

$\displaystyle R_{\rm diff}^{(m)}$
$\displaystyle\leq\sum_{s}\sum_{s^{\prime}}V_{k}^{(m)}\left(s,\tilde{\pi}_{k}(s)\right)\cdot\left(\tilde{p}_{k}\left(s^{\prime}|s,\tilde{\pi}_{k}(s)\right)-p\left(s^{\prime}|s,\tilde{\pi}_{k}(s)\right)\right)\cdot(\tilde{h}_{k}(s^{\prime})-h_{k}(s^{\prime}))$
$\displaystyle\leq\sum_{s}V_{k}^{(m)}\left(s,\tilde{\pi}_{k}(s)\right)\cdot\left\|\tilde{p}_{k}\left(\cdot|s,\tilde{\pi}_{k}(s)\right)-p\left(\cdot|s,\tilde{\pi}_{k}(s)\right)\right\|_{1}\|\mathbf{\tilde{h}}_{k}-\mathbf{h}_{k}\|_{\infty}$
$\displaystyle\leq 32D^{2}r_{\max}\log\left(2AT\right)\Sigma^{(m)},$

where in the last inequality we have used (38) and defined

$\Sigma^{(m)}:=\sum_{s,a}\sum_{k}\sum_{t=t_{k}}^{t_{k+1}-1}\frac{{\mathds{1}}_{\left\\{s_{t},a_{t}=s,a\right\\}}{\mathds{1}}_{\left\\{t\in
m\right\\}}}{\sqrt{\max\\{1,N_{t_{k}}^{(m_{k}(s,a))}(s,a)\\}}\sqrt{\max\\{1,N_{t_{k}}^{(m^{\prime})}(x_{k},a_{k})\\}}}.$

By the choice of $x_{k}$, $N_{t_{k}}^{(m^{\prime})}(x_{k},a_{k})\leq
N_{t_{k}}^{(m_{k}(s,a))}(s,a)$ for any state-action pair $(s,a)$, so that we
can compute the sum $\Sigma:=\sum_{m}\Sigma^{(m)}$, with
$I_{k}:=t_{k+1}-t_{k}$ the length of episode $k$:

$\Sigma\leq\sum_{m}\sum_{s,a}\sum_{k}\sum_{t=t_{k}}^{t_{k+1}-1}\frac{{\mathds{1}}_{\left\\{s_{t},a_{t}=s,a\right\\}}{\mathds{1}}_{\left\\{t\in
m\right\\}}}{\max\\{1,N_{t_{k}}^{(m^{\prime})}(x_{k},a_{k})\\}}=\sum_{k}\frac{I_{k}}{\max\\{1,N_{t_{k}}^{(m^{\prime})}(x_{k},a_{k})\\}}.$

Now, define $Q_{\max}:=\left(\frac{10C_{2}S^{\prime
2}}{\nu^{\pi^{\max}}(S)}\right)^{2}\log\left(\left(\frac{10C_{2}S^{\prime
2}}{\nu^{\pi^{\max}}(S)}\right)^{4}\right)$ where we defined the constant
$C_{2}=\frac{(\lambda\gamma_{{\rm reject}}+\gamma_{{\rm
hold}})C_{1}}{\mu(1)\left(1-\lambda/\mu(i_{0})\right)}$, and
$I(T):=\max\left\\{Q_{\max},T^{1/4}\right\\}$. We split the sum depending on
whether the episodes are shorter than $I(T)$ or not, and call $K_{\leq I}$ the
number of such episodes. This yields:

$\Sigma\leq K_{\leq
I}I(T)+\sum_{k,I_{k}>I(T)}\frac{I_{k}}{\max\\{1,N_{t_{k}}^{(m^{\prime})}(x_{k},a_{k})\\}}.$

Using the stopping criterion for episodes, and that we have chosen the module
$m^{\prime}$ in equation (13) to have the inequality
$V_{k}^{(m^{\prime})}(x_{k},a_{k})\geq\frac{1}{\tau_{\rm
mix}}V_{k}(x_{k},a_{k})$:

$\Sigma\leq K_{\leq I}I(T)+\sum_{k,I_{k}>I(T)}\frac{\tau_{\rm
mix}I_{k}}{\max\\{1,V_{k}(x_{k},a_{k})\\}}.$

Now we can end the computations as in [17]. Denote by $\mathcal{E}$ the event:

$\mathcal{E}=\left\\{\forall k\text{ s.t
}I_{k}>I(T),\;\frac{1}{\max\\{1,V_{k}(x_{k},a_{k})\\}}\leq\frac{2}{\nu^{\pi^{\max}}(S)I_{k}}\right\\}.$

By splitting the sum, using the above event, we get:

$\displaystyle\Sigma$ $\displaystyle\leq K_{\leq
I}I(T)+{\mathds{1}}_{\mathcal{E}}\sum_{k,I_{k}>I(T)}\frac{2\tau_{\rm
mix}}{\nu^{\pi^{\max}}(S)}+{\mathds{1}}_{\mathcal{\bar{E}}}\sum_{k,I_{k}>I(T)}\tau_{\rm
mix}I_{k}$ $\displaystyle\leq K_{\leq
I}I(T)+{\mathds{1}}_{\mathcal{E}}\left(K-K_{\leq I}\right)\frac{2\tau_{\rm
mix}}{\nu^{\pi^{\max}}(S)}+{\mathds{1}}_{\mathcal{\bar{E}}}\tau_{\rm mix}T.$

We use Corollary E.6 to get
${\mathbb{P}}\left(\mathcal{\bar{E}}\right)\leq\frac{1}{4T}$, so that when
taking the expectation:

$\displaystyle{\mathbb{E}}\left[\Sigma\right]$
$\displaystyle\leq{\mathbb{E}}\left[K_{\leq
I}\right]I(T)+{\mathbb{E}}\left[\left(K-K_{\leq
I}\right)\right]\frac{2\tau_{\rm mix}}{\nu^{\pi^{\max}}(S)}+\frac{\tau_{\rm
mix}}{4}.$

Now using Lemma C.2, $S^{\prime}A\geq 4$,
$I(T)\geq\frac{2}{\nu^{\pi^{\max}}(S)}$ and that $\frac{1}{\log
2}+\frac{1}{4}\leq 2$:

${\mathbb{E}}\left[\Sigma\right]\leq{\mathbb{E}}\left[K\right]I(T)\tau_{\rm
mix}+\frac{\tau_{\rm mix}}{4}\leq 2S^{\prime}A\tau_{\rm mix}\log(2AT)I(T).$

Therefore, we have that:

${\mathbb{E}}\left[R_{\rm diff}^{(m)}\right]\leq
64r_{\max}S^{\prime}AD^{2}\tau_{\rm mix}I(T)\log^{2}\left(2AT\right).$ (39)

###  A.7 Bound on $R_{\rm ep}$

The last regret term we have to bound is related to the count of episodes.

$R_{\rm
ep}^{(m)}=\sum_{k}\mathbf{v}_{k}^{(m)}\left(\mathbf{P}_{k}-\mathbf{I}\right)\mathbf{\tilde{h}}_{k}.$

We first want to sum over the modules to get the same kind of term as in [5],
written as a martingale difference sequence, and then take the expectation.
Following that proof, we define $X_{t}:=\leavevmode\nobreak\
\left(p(\cdot|s_{t},a_{t})-\mathbf{e}_{s_{t}}\right)\mathbf{\tilde{h}}_{k(t)}\mathds{1}_{M\in\mathcal{M}_{k(t)}}$,
where $k(t)$ is the episode containing step $t$ and $\mathbf{e}_{i}$ the
vector with $i$-th coordinate $1$ and $0$ for the other coordinates. We obtain

$\displaystyle\sum_{c}\mathbf{v}_{k}^{(m)}\left(\mathbf{P}_{k}-\mathbf{I}\right)\mathbf{\mathbf{\tilde{h}}_{k}}$
$\displaystyle\leq\mathbf{v}_{k}\left(\mathbf{P}_{k}-\mathbf{I}\right)\mathbf{\mathbf{\tilde{h}}_{k}}\leq\sum_{t=t_{k}}^{t_{k+1}-1}X_{t}+\mathbf{\tilde{h}}_{k}(s_{t_{k+1}})-\mathbf{\tilde{h}}_{k}(s_{t_{k}})$
$\displaystyle\leq\sum_{t=t_{k}}^{t_{k+1}-1}X_{t}+Dr_{\max},$

and by summing over the episodes we get

$\sum_{m}R_{\rm ep}^{(m)}\leq\sum_{t=1}^{T}X_{t}+KDr_{\max}.$

Notice that $\mathbb{E}\left[X_{t}|s_{1},a_{1},\dots,s_{t},a_{t}\right]=0$, so
that when taking the expectations, only the term in the number of episodes
remains.

On the other hand, using Lemma C.2 on the number of episodes, when taking the
expectation we obtain

$\mathbb{E}\left[\sum_{m}R_{\rm ep}^{(m)}\right]\leq S^{\prime}A\tau_{\rm
mix}\log_{2}\left(\frac{8T}{S^{\prime}A\tau_{\rm mix}}\right)\cdot Dr_{\max}.$

As for the computation of (27), assuming $\tau_{\rm mix}S^{\prime}A\geq 4$:

$\mathbb{E}\left[R_{\rm ep}\right]\leq 2r_{\max}S^{\prime}AD\tau_{\rm
mix}\log(2AT).$ (40)

###  A.8 Total sum

We remind that we showed in subsection A.5 that the main term of the regret
is:

$72\delta_{\max}\frac{U}{\mu(1)}C_{1}{\left(1-\sqrt{\frac{\lambda}{\mu(i_{0})}}\right)^{-3}}\log\left(AT\right)\sqrt{5AT\log^{-1}(\rho^{-1})},$

and it remains now to compute the lower order term of the regret $R_{\rm LO}$.
Using (27), (28), (39) and (40), the lower order term of the regret is upper
bounded by, omitting the $r_{\max}$ factor:

$64S^{\prime}AD^{2}\tau_{\rm
mix}I(T)\log^{2}\left(2AT\right)+2S^{\prime}A\tau_{\rm mix}(D+\tau_{\rm
mix})\log(2AT)+(S^{\prime}+16CS^{\prime}A),$

and for $T$ large enough so that $1+16C\leq\log^{2}(T)$ the upper bound is :

$r_{\max}69S^{\prime}AD^{2}\tau_{\rm mix}^{2}I(T)\log^{2}\left(2AT\right),$

which concludes the proof of Theorem 5.1.

##  Appendix B Lemmas on Extended Value Iteration

We remind the fundamental properties of the Extended Value Iteration (EVI)
algorithm, first described in [5], which is used to find the optimistic MDP
$\tilde{M}_{k}$ and the policy $\tilde{\pi}_{k}$ for each episode $k$ given a
confidence region $\mathcal{M}_{k}$. These properties are useful notably in
the first splits of the regret terms in Section A.3. EVI iteratively computes
values in the following way:

$\displaystyle\begin{cases}u^{(k)}_{0}(s)&=0\\\
u^{(k)}_{i+1}(s)&=\max_{a\in\mathcal{A}}\left\\{r(s,a)+\max_{p(\cdot)\in\mathcal{P}(s,a)}\left\\{\sum_{s\in
S}p(s^{\prime})u^{(k)}_{i}(s^{\prime})\right\\}\right\\},\end{cases}$

where $\mathcal{P}(s,a)$ is the set of probabilities from (17), and the
iterations are stopped with respect to the following lemma [5, Theorem 7].

######  Lemma B.1.

For episode $k$ and accuracy
$\varepsilon_{k}:=\frac{\delta_{\max}}{\sqrt{t_{k}}}$, denote by $i$ the last
step of extended value iteration, stopped when:

$\max_{s}\\{u^{(k)}_{i+1}(s)-u^{(k)}_{i}(s)\\}-\min_{s}\\{u^{(k)}_{i+1}(s)-u^{(k)}_{i}(s)\\}<\varepsilon_{k}.$
(41)

The optimistic MDP $\tilde{M}_{k}$ and the optimistic policy $\tilde{\pi}_{k}$
at the last step of EVI are so that the gain is $\varepsilon_{k}-$ close to
the optimal gain:

$\tilde{g}_{k}:=\min_{s}g(\tilde{M}_{k},\tilde{\pi}_{k},s)\geq\max_{M^{\prime}\in\mathcal{M}_{k},\pi,s^{\prime}}g(M^{\prime},\pi,s^{\prime})-\varepsilon_{k}.$
(42)

Moreover, from [27, Theorem 8.5.6]:

$\left|u^{(k)}_{i+1}(s)-u^{(k)}_{i}(s)-\tilde{g}_{k}\right|\leq\varepsilon_{k},$
(43)

and as the optimal policy yields an aperiodic unichain Markov chain, we have
that $\tilde{g}_{k}=g(\tilde{M}_{k},\tilde{\pi}_{k},s)$ for any $s$, so that
we can define the bias:

$\tilde{h}_{k}(s_{0})=\mathbb{E}_{s_{0}}\left[\sum_{t=0}^{\infty}(\tilde{r}(s_{t},a_{t})-\tilde{g}_{k})\right].$
(44)

Rather than using the last value of EVI in the computations of the regret, we
rely on the bias to show that the last value and the optimistic bias are
nearly equal, up to a translation. By choosing iteration $i$ large enough,
from [27, Equation 8.2.5], we can ensure that:

$\left|u^{(k)}_{i}(s)-(i-1)\tilde{g}_{k}-\tilde{h}_{k}(s)\right|<\frac{\varepsilon_{k}}{2},$
(45)

so that we can define the following difference

$d_{k}(s):=\left|u^{(k)}_{i}(s)-\min_{s}u^{(k)}_{i}(s)-\left(\tilde{h}_{k}(s)-\min_{s}\tilde{h}_{k}(s)\right)\right|<\varepsilon_{k}.$
(46)

##  Appendix C Classical lemmas for the regret computation in UCRL-like
algorithms

We introduce classic lemmas from [5] that are needed for the regret
computations. The first lemma, proven in [5, Appendix C.3], is used to
simplify the main regret terms (32) and (33).

######  Lemma C.1.

For any fixed state action pair $(s,a)$, and time $T$, we have:

$\sum_{t=1}^{T}\frac{\mathds{1}_{\\{s_{t},a_{t}=s,a\\}}}{\sqrt{\max\\{1,N_{t}(s,a)\\}}}\leq
3\sqrt{N_{T+1}(s,a)}.$

The next lemma, proven in [5, Appendix C.2] is useful to bound the term from
in A.1 and in equation (39).

######  Lemma C.2.

Denote by $K_{t}$ the number of episodes up to time $t$, and let
$t>SA\tau_{\rm mix}$. It is bounded by:

$K_{t}\leq S^{\prime}A\tau_{\rm
mix}\log_{2}\left(\frac{8t}{S^{\prime}A\tau_{\rm mix}}\right).$

The next lemma is needed in the proof of Lemma E.5. While it includes the
diameter, this will only impact a lower-order term of the regret.

######  Lemma C.3 (Azuma-Hoeffding inequality).

Let $X_{1},X_{2},\dots$ be a martingale difference sequence with $|X_{i}|\leq
RD$ for all $i$ and some $R>0$. Then, for all $\varepsilon>0$ and
$n\in\mathbb{N}$:

${\mathbb{P}}\left\\{\sum_{i=1}^{n}X_{i}\geq\varepsilon\right\\}\leq\exp\left(-\frac{\varepsilon^{2}}{2nDR}\right).$

##  Appendix D Probability of not being in the confidence region

We compute the probability that the true MDP $M$ fails to be in the confidence
set. This lemma controls the corresponding regret terms in Section A.2 when we
consider the episodes $k$ with $M\notin\mathcal{M}_{k}$.

Let us first prove the key Lemma D.1.

######  Lemma D.1.

Let us consider the original MDP under any policy $\pi$, with stationary
measure $\nu^{\pi}$. There exists $C>0$, $\rho\in(0,1)$ such that:

$\max_{\pi\in\Pi}\sup_{x_{0}\in\mathcal{S}}\left\|\mathbb{P^{\pi}}_{x_{0}}(x_{t}=\cdot)-\nu^{\pi}\right\|_{TV}\leq
C\rho^{t}\quad\forall t>0.$ (47)

Let $t,t^{\prime}>0$ such that $t^{\prime}-\tau_{\rm mix}\geq t$, with
$t^{\prime}$ and $t^{\prime}-\tau_{\rm mix}$ belonging to the same episode.
Let $X$ be a function of the state of the original MDP until time $t$ and $Y$
function of the state of the original MDP from time $t^{\prime}$. Let
$\hat{Y}$ be a random variable following the same distribution as $Y$
independently from $X$. Let $f$ be a real-valued, bounded function. Then:

$\left|\mathbb{E}\left[f(X,Y)\right]-\mathbb{E}\left[f(X,\hat{Y})\right]\right|\leq
4C\|f\|_{\infty}\rho^{\tau_{\rm mix}}.$

###### Proof.

The proof is essentially the same as in [35, Lemma 9], but as states are
sampled from the original MDP and not a single Markov chain, we cannot just
assume that the starting distribution at time $0$ is a stationary
distribution. Instead, we have to make sure that it is the case for each start
of the episodes, hence the initial phase where $\tau_{\rm mix}$ samples of the
aggregated MDP are discarded, so that the original MDP is close to its
stationary distribution. Due to this ramping time, we can make sure that
$t^{\prime}$ and $t^{\prime}-\tau_{\rm mix}$ belong to the same episodes and
can therefore be related to the same stationary distribution.

Let $t,t^{\prime}>0$ such that $t^{\prime}-\tau_{\rm mix}\geq t$, with
$t^{\prime}$ and $t^{\prime}-\tau_{\rm mix}$ belonging to the same episode
$k$. Now, $X$ is a function of the state of the original MDP until time $t$,
so there are $t$ observed transitions but there might be many more that are
hidden. In turn, $Y$ is a function of the state of the original MDP from time
$t^{\prime}$. Let $\hat{Y}$ be a random variable following the same
distribution as $Y$ and independent of $X$. Note that there are at least
$\tau_{\rm mix}$ observed or hidden transitions between $t$ and $t^{\prime}$
on the original MDP.

We also define the distribution
$P:={\mathbb{P}}\left\\{X\in\cdot,Y\in\cdot\right\\}$ and the distribution
$Q\leavevmode\nobreak\ :=\leavevmode\nobreak\
{\mathbb{P}}\left\\{X\in\cdot\right\\}\otimes{\mathbb{P}}\left\\{Y\in\cdot\right\\}$,
and we define the total variation information
$I_{TV}(X,Y):=\sum_{x}{\mathbb{P}}\left\\{X=x\right\\}\left\|{\mathbb{P}}\left\\{Y=\cdot\mid
X=x\right\\}-{\mathbb{P}}\left\\{Y=y\right\\}\right\|_{TV}$. To simplify,
assume that $\|f\|_{\infty}\leq\frac{1}{2}$. By definition of the total
variation distance, we first have that:

$\left|{\mathbb{E}}\left[f(X,Y)\right]-{\mathbb{E}}\left[f(X,\hat{Y})\right]\right|\leq\left\|P-Q\right\|_{TV},$

Then, using the properties of the total variation information related to a
Markov chain described in [35], we obtain

$\displaystyle\left\|P-Q\right\|_{TV}$ $\displaystyle\leq I_{TV}(X,Y)\leq
I_{TV}(x_{t},x_{t^{\prime}})\leq I_{TV}(x_{t^{\prime}-\tau_{\rm
mix}},x_{t^{\prime}})$
$\displaystyle\leq\sum_{x}{\mathbb{P}}\left\\{x_{t^{\prime}-\tau_{\rm
mix}}=x\right\\}\left\|{\mathbb{P}}\left\\{x_{t^{\prime}}=\cdot\mid
x_{t^{\prime}-\tau_{\rm
mix}}=x\right\\}-{\mathbb{P}}\left\\{x_{t}=\cdot\right\\}\right\|_{TV}$

then using a triangle inequality:

$\left\|{\mathbb{P}}\left\\{x_{t^{\prime}}=\cdot\mid x_{t^{\prime}-\tau_{\rm
mix}}=x\right\\}-{\mathbb{P}}\left\\{x_{t}=\cdot\right\\}\right\|_{TV}\leq\left\|{\mathbb{P}}\left\\{x_{t^{\prime}}=\cdot\right\\}-\nu^{\tilde{\pi}_{k}}\right\|_{TV}+\\\
\left\|{\mathbb{P}}\left\\{x_{t^{\prime}}=\cdot\mid x_{t^{\prime}-\tau_{\rm
mix}}=x\right\\}-\nu^{\tilde{\pi}_{k}}\right\|_{TV},$

we get

$\left\|P-Q\right\|_{TV}\leq 2C\rho^{\tau_{\rm mix}},$

where in the last inequality we used assumption (10) twice, as $t^{\prime}$
and $t^{\prime}-\tau_{\rm mix}$ belong to the same episode, and therefore can
be related to the same stationary measure $\nu^{\tilde{\pi}_{k}}$. To clarify,
the exponent $\tau_{\rm mix}$ in the inequality is loose, as $\tau_{\rm mix}$
is the number of time-steps in the aggregated MDP, so there are at least as
many time steps in the original MDP, and the mixing is confirmed. ∎

We can now give the lemma that actually shows that $M$ is likely to be in the
confidence set of MDPs.

######  Lemma D.2.

For $t>1$, the probability that the MDP $M$ is not within the set of plausible
MDPs $\mathcal{M}(t)$ is bounded by:

${\mathbb{P}}\left\\{M\notin\mathcal{M}(t)\right\\}\leq\frac{S^{\prime}}{2t^{3}}+\frac{8CS^{\prime}A}{t^{3}}.$

Compared to [5, Lemma 17], we notice that the first term comes from the choice
of the confidence bound adapted to the birth and death structure of the MDP,
but the second one comes from the imperfect independence of the observations.
To prove this inequality, we will need Lemma D.1 to consider independent
events again, and to be able to use concentration inequalities.

Let us now prove Lemma D.2.

###### Proof.

Fix a state-action pair $(s,a)$, $m$ any module and $n$ the number of visits
of this pair within the module before time $t$. We will first consider the
confidence around the empirical transitions, and then the confidence around
the rewards. Let $\varepsilon_{p}\leavevmode\nobreak\ =\leavevmode\nobreak\
\sqrt{\frac{2}{n}\log\left(16At^{4}\right)}\leq\sqrt{\frac{8}{n}\log\left(2At\right)}.$
Define the events:

$A_{n}=\left(\|\hat{p}^{(m)}(\cdot|s,a)-p(\cdot|s,a)\|_{1}\geq\sqrt{\frac{8}{n}\log\left(2At\right)}\right)$
(48)

Here, we aim to control these events but the difficulty is that the
observations from the state-action pairs are not independent. On the other
hand, we notice that the observations within a fixed module are nearly
independent, which is why we needed to introduce these modules in the first
place.

Define $\hat{p}^{\bot}(\cdot|s,a)$ the empirical transition probabilities from
$n$ independent observations of the state-action pair $(s,a)$. Define events
that are copies of $A_{n}$ but with independent observations:

$A_{n}^{\bot}=\left(\|\hat{p}^{\bot}(\cdot|s,a)-p(\cdot|s,a)\|_{1}\geq\sqrt{\frac{8}{n}\log\left(2At\right)}\right).$
(49)

Similarly, define $A_{n}^{\bot,k}$ events such that the first $n-k$
observations are the same as the ones for $A_{n}$ and the next $k$
observations are independent, so that for example $A_{n}^{\bot,0}=A_{n}$ and
$A_{n}^{\bot,n-1}=A_{n}^{\bot}$. Then, applying $n-1$ times Lemma D.1:

$\displaystyle\left|\mathbb{P}\left\\{A_{n}\right\\}-\mathbb{P}\left\\{A_{n}^{\bot}\right\\}\right|$
$\displaystyle\leq\sum_{k=1}^{n-1}\left|\mathbb{P}\left\\{A_{n}^{\bot,k-1}\right\\}-\mathbb{P}\left\\{A_{n}^{\bot,k}\right\\}\right|\leq
4Cn\rho^{\tau_{\rm mix}}\leq 4CT^{1-5}.$

We can therefore work on the events with independent observations. Knowing
that from each pair, there are at most $3$ transitions, a Weissman’s
inequality gives:

${\mathbb{P}}\left\\{\|\hat{p}^{(m)}(\cdot|s,a)-p(\cdot|s,a)\|_{1}\geq\varepsilon_{p}\right\\}\leq
6\exp\left(-\frac{n\varepsilon_{p}^{2}}{2}\right)$

and we get

${\mathbb{P}}\left\\{A_{n}^{\bot}\right\\}\leq\frac{3}{8At^{4}},$

and within our choice of $\tau_{\rm mix}$,

$\mathbb{P}\left\\{A_{n}\right\\}\leq\frac{3}{8At^{4}}+\frac{4C}{t^{4}}.$

We deal with the rewards in a similar manner. Define the events:

$B_{n}:=\left(|\hat{r}^{(m)}(s,a)-r(s,a)|\geq\delta_{\max}\sqrt{\frac{2}{n}\log\left(2At\right)}\right).$
(50)

By definition of $\hat{r}^{(m)}(s,a)=\gamma_{{\rm
reject}}\hat{p}^{(m)}(s+1|s,a)+\frac{\gamma_{{\rm hold}}}{U}(S-s)$ 15, and
using that $\gamma_{{\rm reject}}\leq\delta_{\max}$, we can write:

${\mathbb{P}}\left\\{B_{n}\right\\}\leq{\mathbb{P}}\left\\{|\hat{p}^{(m)}(s+1|s,a)-p(s+1|s,a)|\geq\sqrt{\frac{2}{n}\log\left(2At\right)}\right\\}.$

Once again, we consider $\hat{p}^{\bot}(s+1|s,a)$ the empirical transition
probabilities from independent observations of $(s,a)$ to $s+1$, and we look
to control the probability of the events $B_{n}^{\bot}$. With the
independence, we may now use the following Hoeffding inequality on the
Bernoulli random variable of parameter $p(s+1|s,a)$:

${\mathbb{P}}\left\\{|\hat{p}^{(m)}(s+1|s,a)-p(s+1|s,a)|\geq\varepsilon_{r}\right\\}\leq
2\exp\left(-2n\varepsilon_{r}^{2}\right),$

where
$\varepsilon_{r}=\sqrt{\frac{1}{2n}\log\left(16At^{4}\right)}\leq\sqrt{\frac{2}{n}\log\left(2At\right)}$.
We therefore get:

${\mathbb{P}}\left\\{B_{n}^{\bot}\right\\}\leq\frac{1}{8At^{4}},$

and with the previous choice of $\tau_{\rm mix}$,

$\mathbb{P}\left\\{B_{n}\right\\}\leq\frac{1}{8At^{4}}+\frac{4C}{t^{4}}.$

Overall:

$\mathbb{P}\left\\{A_{n}\cup
B_{n}\right\\}\leq\frac{1}{2At^{4}}+\frac{8C}{t^{4}}.$

Now, with a union bound for all values of
$n=\max\\{1,N_{t}^{(m)}(s,a)\\}\in\left\\{0,1,\cdots,\left\lceil\frac{t-1}{\tau_{\rm
mix}}\right\rceil\right\\}$ and all $\tau_{\rm mix}$ possible modules, and
also summing over all state-action pairs:

${\mathbb{P}}\left\\{M\notin\mathcal{M}(t)\right\\}\leq\frac{S^{\prime}}{2t^{3}}+\frac{8CS^{\prime}A}{t^{3}}$

as desired. ∎

##  Appendix E Lemmas specific to our regret computations

In this section, we prove generic properties on the difference of biases
between two MDPs. This control on the difference is needed in subsection A.6
to compare the optimistic MDP and the true MDP.

###  E.1 Lemmas on the bias differences

The next three lemmas of this subsection are already proved in [17], for the
sake of completeness, we rewrite them in this appendix. They are used in the
proof of Lemma E.4, to control the difference between the bias of the policy
$\tilde{\pi}_{k}$ in the optimistic MDP and in the true MDP.

######  Lemma E.1.

For an MDP with rewards $r\in[0,r_{\max}]$ and transition matrix $P$, denote
by $J_{s}(\pi,T):={\mathbb{E}}\left[\sum_{t=0}^{T}r(s_{t},\pi(s_{t}))\right]$
the expected cumulative rewards until time $T$ starting from state $s$, under
policy $\pi$. Let $D_{\pi}$ be the diameter under policy $\pi$. The following
inequality holds: $\mbox{span }(J(\pi,T))\leq r_{\max}D_{\pi}$.

###### Proof.

Let $s,s^{\prime}\in\mathcal{S}$ be recurrent states under policy $\pi$. Call
$\tau_{s\to s^{\prime}}$ the random time needed to reach state $s^{\prime}$
from state $s$. Then:

$\displaystyle J_{s}(\pi,T)$
$\displaystyle={\mathbb{E}}\left[\sum_{t=0}^{T}r(s_{t})\right]$
$\displaystyle={\mathbb{E}}\left[\sum_{t=0}^{\tau_{s\to
s^{\prime}}-1}r(s_{t})\right]+{\mathbb{E}}\left[\sum_{t=\tau_{s\to
s^{\prime}}}^{T}r(s_{t})\right]$ $\displaystyle\leq
r_{\max}{\mathbb{E}}\left[\tau_{s\to s^{\prime}}\right]+J_{s^{\prime}}(\pi,T)$
$\displaystyle\leq r_{\max}D_{\pi}+J_{s^{\prime}}(\pi,T),$

which proves the lemma. ∎

######  Lemma E.2.

Consider two unichain MDPs $M$ and $M^{\prime}$. Let
$r=r^{\prime}\in[0,r_{\max}]$ and $P,P^{\prime}$ be the rewards and transition
matrix of MDP $M,M^{\prime}$ under policy $\pi,\pi^{\prime}$ respectively,
where both MDPs have the same state and action spaces. Denote by
$g,g^{\prime}$ the average reward obtained under policy $\pi,\pi^{\prime}$ in
the MDP $M,M^{\prime}$ respectively. Then the difference of the gains is upper
bounded.

$|g-g^{\prime}|\leq r_{\max}D_{\pi}\|P-P^{\prime}\|_{\infty}.$

###### Proof.

Define for any state $s$ the following correction term
$b(s):=r_{\max}D_{\pi}\|p(\cdot|s)-p^{\prime}(\cdot|s)\|_{1}.$ Let us show by
induction that for $T\geq 0$,

$\sum_{t=0}^{T-1}P^{t}r\leq\sum_{t=0}^{T-1}P^{\prime t}(r+b).$

This is true for $T=0$. Assume that the inequality is true for some $T\geq 0$,
then

$\displaystyle\sum_{t=0}^{T}P^{t}r-\sum_{t=0}^{T}P^{\prime t}(r+b)$
$\displaystyle=-b+P\sum_{t=0}^{T-1}P^{t}r-P^{\prime}\sum_{t=0}^{T-1}P^{\prime
t}(r+b)$
$\displaystyle=-b+P^{\prime}\left(\sum_{t=0}^{T-1}P^{t}r-\sum_{t=0}^{T-1}P^{\prime
t}(r+b)\right)+(P-P^{\prime})\sum_{t=0}^{T}P^{t}r$
$\displaystyle\leq-b+(P-P^{\prime})\sum_{t=0}^{T}P^{t}r\text{ by induction
hypothesis.}$

Notice that, for any recurrent state $s$ for policy $\pi$:

$\displaystyle\left((P-P^{\prime})\sum_{t=0}^{T}P^{t}r\right)(s)$
$\displaystyle\leq\|p(\cdot|s)-p^{\prime}(\cdot|s)\|_{1}\cdot\mbox{span
}(J(T))$ $\displaystyle\leq
r_{\max}D_{\pi}\|p(\cdot|s)-p^{\prime}(\cdot|s)\|_{1}\text{ by
Lemma\leavevmode\nobreak\ \ref{Lem:span}}$ $\displaystyle=b(s).$

In the same manner we show that:

$\sum_{t=0}^{T}P^{t}r\geq\sum_{t=0}^{T}P^{\prime t}(r-b).$

Hence, as $P^{\prime}$ has non-negative coefficients, denoting by $e$ the unit
vector:

$\left\|\sum_{t=0}^{T}P^{t}r-\sum_{t=0}^{T}P^{\prime
t}r\right\|_{\infty}\leq\|b\|_{\infty}\left\|\sum_{t=0}^{T}P^{\prime t}\cdot
e\right\|_{\infty}=\|b\|_{\infty}(T+1).$

As $r=r^{\prime}$, with a multiplication by $\frac{1}{T+1}$ and by taking the
Cesáro limit :

$|g-g^{\prime}|\leq\|b\|_{\infty},$

where $\|b\|_{\infty}=r_{\max}D_{\pi}\|P-P^{\prime}\|_{\infty}$. ∎

######  Lemma E.3.

Let $P$ be the stochastic matrix of an ergodic Markov chain with state space
$1,\dots,S$. The matrix $A:=I-P$ has a block decomposition

$A=\begin{pmatrix}A_{S}&b\\\ c&d\end{pmatrix};$

then $A_{S}$, of size $S\times S$ is invertible and
$\|A_{S}^{-1}\|_{\infty}=\sup_{i\in\mathcal{S}}{\mathbb{E}}\,\tau_{i\to S}$,
where ${\mathbb{E}}\,\tau_{i\to S}$ is the expected time to reach state $S$
from state $i$.

Remark that this lemma is true for any state in $\mathcal{S}$.

###### Proof.

$\left({\mathbb{E}}\,\tau_{i\to S}\right)_{i}$ is the unique vector solution
to the system:

$\begin{cases}v(S)=0\\\ \forall i\neq
S,\,v(i)=1+\sum_{j\in\mathcal{S}}P(i,j)v(j)\end{cases}$

We can rewrite this system of equations as: $\tilde{A}v=e-e_{S}$, where
$\tilde{A}$ is the matrix

$\tilde{A}:=\begin{pmatrix}A_{S}&b\\\ 0&1\end{pmatrix},$

$e$ the unit vector and $e_{S}$ the vector with value $1$ for the last state
and $0$ otherwise. Then $\widetilde{A}$ and $A_{S}$ are invertible and we
write:

$\tilde{A}^{-1}=\begin{pmatrix}A_{S}^{-1}&-A_{S}^{-1}b\\\ 0&1\end{pmatrix}.$

Thus, by computing $\tilde{A}^{-1}(e-e_{S})$, for $i\neq S$,
$\left({\mathbb{E}}\,\tau_{i\to S}\right)_{i}=A_{S}^{-1}e$. By definition of
the infinite norm and using that $A_{S}$ is an M-matrix and that its inverse
has non-negative components,
$\|A_{S}^{-1}\|_{\infty}=\sup_{i\in\mathcal{S}}{\mathbb{E}}\,\tau_{i\to S}$. ∎

In the following lemma, we use the same notations as in Lemma E.2 with a
common state space $\\{0,1,\ldots S\\}$.

######  Lemma E.4.

Let the biases $h$, $h^{\prime}$ be the biases of the two MDPs that verify
their respective Bellman equations with the renormalization choice
$h(S)=h^{\prime}(S)=0$, and respective policies $\pi,$ and $\pi^{\prime}$. Let
$\sup_{s\in\mathcal{S}}{\mathbb{E}}\,\tau^{\pi}_{s\to s^{\prime}}$ be the
worst expected hitting time to reach the state $s^{\prime}$ with policy $\pi$,
and call
$T_{hit}:=\inf_{s^{\prime}\in\mathcal{S}}\sup_{s\in\mathcal{S}}{\mathbb{E}}\,\tau_{s\to
s^{\prime}}^{\pi}$. We have the following control of the difference:

$\|h-h^{\prime}\|_{\infty}\leq
2T_{hit}^{\pi}D^{\pi^{\prime}}r_{\max}\|P-P^{\prime}\|_{\infty}.$

Notice that although the biases are unique up to a constant additive term, the
renormalization choice does not matter as the unit vector is in the kernel of
$(P-P^{\prime})$.

###### Proof.

The computations in this proof follow the same idea as in the proof of [36,
Theorem 4.2]. The biases verify the following Bellman equations $r-ge=(I-P)h$,
and also the arbitrary renormalization equations, thanks to the previous
remark: $h(S)=0$. Using the same notations as in the proof of Lemma E.3, we
can write the system of equations $\tilde{A}h=\tilde{r}-\tilde{g}$, with
$\tilde{r}$ and $\tilde{g}$ respectively equal to $r$ and $g$ everywhere but
on the last state, where their value is replaced by $0$.

We therefore have that $h=\tilde{A}^{-1}(\tilde{r}-\tilde{g})$, and with
identical computations,
$h^{\prime}=\tilde{A^{\prime}}^{-1}(\tilde{r^{\prime}}-\tilde{g^{\prime}}).$
By denoting $dX:=X-X^{\prime}$ for any vector or matrix $X$, we get, as
$r=r^{\prime}$:

$dh=-\tilde{A}^{-1}(-d\tilde{g}+d\tilde{A}h^{\prime}).$

The previously defined block decompositions are:

$\tilde{A}^{-1}=\begin{pmatrix}A_{S}^{-1}&-A_{S}^{-1}b\\\
0&1\end{pmatrix}\quad\text{ and }\quad
d\tilde{A}=\begin{pmatrix}A_{S}-A_{S}^{\prime}&b-b^{\prime}\\\
0&0\end{pmatrix}.$

For $s<S$, $dh(s)=-e_{s}^{T}A_{S}^{-1}(dA_{S}h^{\prime}-d\tilde{g})$ and
$dh(S)=0$. Now by taking the norm and using E.1:

$\|dh\|_{\infty}\leq\|A_{S}^{-1}\|_{\infty}(r_{\max}D^{\pi^{\prime}}\|dA_{S}\|_{\infty}+|d\tilde{g}|).$

Notice that $\|dA_{S}\|_{\infty}\leq\|dP\|_{\infty}$ and $|d\tilde{g}|=|dg|$.
Using Lemma E.2 and Lemma E.3, and taking the infimum for the choice of the
state of renormalization implies the claimed inequality for the biases. ∎

###  E.2 Visits of the furthest state

We also need the next lemmas to bound $R_{\rm diff}$ by controlling the number
of visits of the state with the fewest visits. If we can guarantee that each
state receives enough visits, then we will have a good approximation of the
biases and transition probabilities. The proof can be found in [17].

######  Lemma E.5.

Let $\nu^{\pi^{\max}}$ be the stationary measure of the Markov chain under
policy $\pi^{\max}$, such that for every state $s$: $\pi^{\max}(s)=1$, so that
every job is admitted in the network until maximal capacity $S$ is reached.

Let $k$ be an episode and assume that the length of this episode $I_{k}$ is at
least $I(T)=1+\max\left\\{Q_{\max},T^{1/4}\right\\}$, with
$Q_{\max}:=\left(\frac{10C_{2}S^{\prime
2}}{\nu^{\pi^{\max}}(S)}\right)^{2}\log\left(\left(\frac{10C_{2}S^{\prime
2}}{\nu^{\pi^{\max}}(S)}\right)^{4}\right)$,
$C_{2}:=\frac{(\lambda\gamma_{{\rm reject}}+\gamma_{{\rm
hold}})C_{1}}{\mu(1)\left(1-\lambda/\mu(i_{0})\right)}$ and $C_{1}$ as in
Lemma F.1. Then, with probability at least $1-\frac{1}{4T}$:

$V_{k}(x_{k},a_{k})\geq\nu^{\pi^{\max}}(S)I_{k}-5C_{2}S^{\prime
2}\sqrt{I_{k}\log I_{k}}.$

We will now prove Lemma E.5:

###### Proof.

Let $k$ be an episode such that $I_{k}\geq I(T)$, and first consider it is of
fixed length $I$. Let $x_{k}\in\mathcal{S}$ be a recurrent state,
$a_{k}=\tilde{\pi}_{k}(s_{k})$. Denote by $\nu_{k}$ the stationary
distribution under policy $\tilde{\pi}_{k}$. Notice that
$\nu^{\pi^{\max}}(S)\leq\nu_{k}(x_{k})$ for $S$ large enough.

Define a new Markov reward process: consider again the original state space
$\mathcal{S}^{\prime}$ and the transitions $p^{\prime}$ with policy
$\tilde{\pi}_{k}$, but the rewards $\mathring{r}$, where
$\mathring{r}(s^{\prime})=1$ for states $s^{\prime}$ such that
$|s^{\prime}|=x_{k}$ and $0$ otherwise. Denote by
$\mathring{g}_{\tilde{\pi}_{k}}$ the gain associated to the policy
$\tilde{\pi}_{k}$ and similarly define
$\mathbf{\mathring{h}}_{\tilde{\pi}_{k}}$ the bias, translated so that
$\mathring{h}_{\tilde{\pi}_{k}}(S)=0$. Then:

$\displaystyle V_{k}(x_{k},a_{k})$
$\displaystyle=\sum_{u=t_{k}}^{t_{k+1}-1}\mathring{r}(s^{\prime}_{u})$
$\displaystyle=\sum_{u=t_{k}}^{t_{k+1}-1}\mathring{g}_{\tilde{\pi}_{k}}+\mathring{h}_{\tilde{\pi}_{k}}(s^{\prime}_{u})-\left\langle
p^{\prime}\left(\cdot|s^{\prime}_{u},\tilde{\pi}_{k}(s^{\prime}_{u})\right),\mathring{h}_{\tilde{\pi}_{k}}\right\rangle\text{
using a Bellman equation}$
$\displaystyle=\sum_{u=t_{k}}^{t_{k+1}-1}\mathring{g}_{\tilde{\pi}_{k}}+\mathring{h}_{\tilde{\pi}_{k}}(s^{\prime}_{u})-\mathring{h}_{\tilde{\pi}_{k}}(s^{\prime}_{u+1})+\mathring{h}_{\tilde{\pi}_{k}}(s^{\prime}_{u+1})-\left\langle
p^{\prime}\left(\cdot|s^{\prime}_{u},\tilde{\pi}_{k}(s^{\prime}_{u})\right),\mathring{h}_{\tilde{\pi}_{k}}\right\rangle.$

By Azuma-Hoeffding inequality C.3, following the same proof as in section
4.3.2 of [5], notice that
$X_{u}=\mathring{h}_{\tilde{\pi}_{k}}(s^{\prime}_{u+1})-\left\langle
p^{\prime}\left(\cdot\mid
s^{\prime}_{u},\tilde{\pi}_{k}(s^{\prime}_{u})\right),\mathring{h}_{\tilde{\pi}_{k}}\right\rangle$
form a martingale difference sequence with the bound
$|X_{u}|\leq\mbox{span}\,\mathring{h}_{\tilde{\pi}_{k}}$:

${\mathbb{P}}\left\\{\sum_{u=t_{k}}^{t_{k+1}-1}X_{u}\geq C_{2}S^{\prime
2}\sqrt{10I\log I}\right\\}\leq\frac{1}{I^{5}}.$

With Proposition F.4 proved in Appendix F, we have
$\mbox{span}\,\mathring{h}_{\tilde{\pi}_{k}}\leq C_{2}S^{\prime 2}$ with
$C_{2}=\frac{(\lambda\gamma_{{\rm reject}}+\gamma_{{\rm
hold}})C_{1}}{\mu(1)\left(1-\lambda/\mu(i_{0})\right)}$, so that with
probability at least $1-\frac{1}{I^{2}}$:

$V_{k}(x_{k},a_{k})\geq\sum_{u=t_{k}}^{t_{k+1}-1}\mathring{g}_{\tilde{\pi}_{k}}-5C_{2}S^{\prime
2}\sqrt{I\log I}.$

On the other hand:

$\sum_{u=t_{k}}^{t_{k+1}-1}\mathring{g}_{\tilde{\pi}_{k}}=V_{k}(s_{k},a_{k})\nu_{k}(x_{k}),$

so that, using that $\nu_{k}(x_{k})\geq\nu^{\pi^{\max}}(S)$, with probability
at least $1-\frac{1}{I^{5}}$:

$V_{k}(x_{k},a_{k})\geq\nu^{\pi^{\max}}(S)I-5C_{2}S^{\prime 2}\sqrt{I\log I}.$

We now use a union bound over the possible values of the episode lengths
$I_{k}$, between $I(T)+1$ and $T$:

$\displaystyle{\mathbb{P}}\left\\{V_{k}(x_{k},a_{k})<\nu^{\pi^{\max}}(S)I_{k}-5C_{2}S^{\prime
2}\sqrt{I_{k}\log I_{k}}\right\\}$
$\displaystyle\leq\sum_{I=I(T)+1}^{T}\frac{1}{I^{5}}\leq\sum_{I=T^{1/4}+1}^{T}\frac{1}{I^{5}}$
$\displaystyle\leq\frac{1}{4T},$

so that we now have that with probability at least $1-\frac{1}{4T}$:

$V_{k}(x_{k},a_{k})\geq\nu^{\pi^{\max}}(S)I_{k}-5C_{2}S^{\prime
2}\sqrt{I_{k}\log I_{k}}.$

∎

We can show a corollary of Lemma E.5 that we will use for the regret
computations:

######  Corollary E.6.

For an episode $k$ such that its length $I_{k}$ is greater than $I(T)$,with
probability at least $1-\frac{1}{4T}$:

$V_{k}(x_{k},a_{k})\geq\frac{\nu^{\pi^{\max}}(S)}{2}I_{k}.$

###### Proof.

With Lemma E.5, it is enough to show that $5C_{2}S^{\prime 2}\sqrt{I_{k}\log
I_{k}}\leq\frac{\nu^{\pi^{\max}}(S)}{2}I_{k}$, _i.e._ that
$\sqrt{\frac{I_{k}}{\log I_{k}}}\geq\frac{10C_{2}S^{\prime
2}}{\nu^{\pi^{\max}}(S)}=:B$. By monotonicity, as $I_{k}\geq
Q_{\max}={B}^{2}\log{B}^{4}$ we can show instead that
${B}^{2}\log{B}^{4}\geq{B}^{2}\log\left({B}^{2}\log{B}^{4}\right)$.

This last inequality is true, using that $\log x\geq\log(2\log x)$ for $x>1$.
This proves the corollary. ∎

##  Appendix F Properties of the aggregated MDP

In this section, we prove properties on the aggregated MDP that are needed to
control the average number of visits of the states of the MDP under any
policy. We also prove a bound on the bias of the true MDP under any policy,
which is eventually needed to control the main term in subsections A.4 and
A.5.

###  F.1 Properties of the policies in the aggregated MDP

We may only consider policies that are threshold policies, as we are mainly
interested in the average reward scored by these policies, so that we consider
that the policies chosen by EVI are threshold policies. We remind that the
aggregated MDP is stable (as seen in Section 2), so that there exists a
$i_{0}$ large enough for which $i\geq i_{0}$, $\mu(i)\geq\mu(i_{0})>\lambda$.

With the following lemma, we compute the stationary measures $\nu^{\pi}$ and
give a comparison between any $\nu^{\pi}$ with the stationary measure
$\nu^{\pi^{\max}}$ of the maximal policy $\pi^{\max}$, that admits every job
into the queue, by relating these Markov chains to the $M/M/1/S$ queue with
rates $\lambda$ and $\mu(i_{0})$.

######  Lemma F.1.

Denote by $\bar{s}$ the last recurrent state of the MDP for policy $\pi$, so
that $\pi(s)=0$ for $s\geq\bar{s}$. Define the constant
$C_{1}:=\prod_{i=1}^{i_{0}-1}\frac{\mu(i_{0})}{\mu(i)}\geq 1$, independent of
$S$.

We have the following inequalities

  * •

On the stationary measure of the maximal policy:

$\nu^{\pi^{\max}}(0)^{-1}:=\sum_{s^{\prime}=0}^{S}\prod_{i=1}^{s^{\prime}}\frac{\lambda}{\mu(i)}\leq\frac{C_{1}}{1-\frac{\lambda}{\mu(i_{0})}},$

  * •

On the stationary measure of any policy:

$\nu^{\pi}(0)^{-1}:=\sum_{s^{\prime}=0}^{\bar{s}}\prod_{i=1}^{s^{\prime}}\frac{\lambda}{\mu(i)}\leq\nu^{\pi^{\max}}(0)^{-1}\leq\frac{C_{1}}{1-\frac{\lambda}{\mu(i_{0})}},$

  * •

Also we can compute for $s\leq S$:

$\nu^{\pi^{\max}}(s):=\nu^{\pi^{\max}}(0)\prod_{i=1}^{s}\frac{\lambda}{\mu(i)}=\nu^{\pi^{\max}}(0)C_{1}\left(\frac{\lambda}{\mu(i_{0})}\right)^{s}.$

We now remind a definition of the bias for any policy $\pi$ and control its
variations, as they play a major role in the computations of the main term of
the regret (see A.4).

######  Definition F.2 (Bias).

Let $\pi$ be a policy, $P$ the transition matrix and $\nu^{\pi}$ the
stationary measure of the Markov chain under policy $\pi$. The bias
$\mathbf{h}^{\pi}$ of this policy is defined as:

$h^{\pi}(s)=\sum_{t=1}^{\infty}(P^{t}(s,\cdot)-\nu^{\pi})\mathbf{r}.$ (51)

In order to control the variation of the bias of any policy, we will relate
the bias to the expected hitting time to hit the state $0$ from state $s$, so
that we first need to compute the hitting times:

######  Lemma F.3.

Let $\pi$ be any policy, $(X_{t})_{t}$ be the Markov chain with policy $\pi$
and transitions $P$ starting from any state $s$. Denote by $\tau_{s}$ the
random time needed for $X_{t}$ to hit $0$. Then:

$\mathbb{E}\tau_{s}\leq\nu^{\pi}(0)^{-1}\sum_{i=1}^{s}\frac{U}{\mu(i)}$

###### Proof.

We write the expected hitting time equations, and use induction. Let
$\tau_{i}$ be the hitting time to $0$ starting from state $i$, and
$\mathbf{e}$ be the unit vector. We have the system:

${\mathbb{E}}\boldsymbol{\tau}=\mathbf{e}+P\;{\mathbb{E}}\boldsymbol{\tau},$
(52)

with the extra equation $\tau_{0}=0$. The system gives for $s\geq\bar{s}$:

$\mathbb{E}\tau_{s}=1+\mathbb{E}\tau_{s}\frac{1-\mu(s)}{U}+\mathbb{E}\tau_{s-1}\frac{\mu(s)}{U},$

so that:

$\mathbb{E}\tau_{s}=\frac{U}{\mu(s)}+\mathbb{E}\tau_{s-1}$

Then, by induction, we want to prove the equation for $s<\bar{s}$:

$\mathbb{E}\tau_{s}=\mathbb{E}\tau_{s-1}+\frac{U}{\mu(s)}\sum_{s^{\prime}=s}^{\bar{s}}\prod_{i=s+1}^{s^{\prime}}\frac{\lambda}{\mu(i)}\vspace{-0.2cm}$
(53)

For $s<\bar{s}$, assume (53) is true for $\mathbb{E}\tau_{s+1}$:

$\displaystyle\mathbb{E}\tau_{s}$
$\displaystyle=1+\mathbb{E}\tau_{s+1}\frac{\lambda}{U}+\mathbb{E}\tau_{s}\frac{1-\mu(s)-\lambda}{U}+\mathbb{E}\tau_{s-1}\frac{\mu(s)}{U}$
$\displaystyle=1+\mathbb{E}\tau_{s}\frac{1-\mu(s)-\lambda}{U}+\mathbb{E}\tau_{s-1}\frac{\mu(s)}{U}+\mathbb{E}\tau_{s}\frac{\lambda}{U}+\sum_{s^{\prime}=s+1}^{\bar{s}}\prod_{i=s+1}^{s^{\prime}}\frac{\lambda}{\mu(i)}$
$\displaystyle=\frac{U}{\mu(s)}+\mathbb{E}\tau_{s-1}+\frac{U}{\mu(s)}\sum_{s^{\prime}=s+1}^{\bar{s}}\prod_{i=s+1}^{s^{\prime}}\frac{\lambda}{\mu(i)}\text{
by gathering the $\tau_{s}$ terms }$
$\displaystyle=\mathbb{E}\tau_{s-1}+\frac{U}{\mu(s)}\sum_{s^{\prime}=s}^{\bar{s}}\prod_{i=s+1}^{s^{\prime}}\frac{\lambda}{\mu(i)},$

the induction is therefore true, and we have:
$\mathbb{E}\tau_{s}\leq\mathbb{E}\tau_{s-1}+\frac{U}{\mu(s)}\nu^{\pi}(0)^{-1}$.
∎

######  Proposition F.4.

For any policy $\pi$, define for $s\in\left\\{1,\ldots,S\right\\}$ the
variation of the bias

$\Delta^{\pi}(s):=h^{\pi}(s)-h^{\pi}(s-1)=\sum_{t=1}^{\infty}\left(P^{t}(s,\cdot)-P^{t}(s-1,\cdot)\right)\mathbf{r}.$

Remind that
$\delta_{\max}:=\max_{s,a,a^{\prime}}|r(s,a)-r(s-1,a^{\prime})|=\frac{\lambda\gamma_{{\rm
reject}}+\gamma_{{\rm hold}}}{U}$:

$\Delta^{\pi}(s)\leq\Delta(s):=2\delta_{\max}\nu^{\pi^{\max}}(0)^{-1}\sum_{i=1}^{s}\frac{U}{\mu(i)}.$

Using the monotonicity of the rates $\mu$ from Lemma 3.1, we therefore have :

$\Delta(s)\leq 2(\lambda\gamma_{{\rm reject}}+\gamma_{{\rm
hold}})\nu^{\pi^{\max}}(0)^{-1}s\frac{1}{\mu(1)}$

###### Proof.

We will use an optimal coupling, that is, a coupling such that the following
infimum is reached, as defined in [28].

$\left\|P^{t}(s,\cdot)-P^{t}(s-1,\cdot)\right\|_{\rm
TV}=\inf\\{\mathbb{P}(X_{t}\neq Y_{t}):(X_{t},Y_{t})\text{ couples
$P^{t}(s,\cdot)$ and $P^{t}(s-1,\cdot)$}\\}.$ (54)

More precisely, let $X$ and $Y$ be Markov chains with transition matrix $P$
and starting states $X_{1}=s$, $Y_{1}=s-1$, coupled in the following way: For
each time-step $t\geq 2$, let $U_{t}\sim\mathcal{U}([0,1])$ be a sequence of
independent random variables sampled uniformly on $[0,1]$. We have:

$X_{t+1}=\begin{cases}X_{t}-1&\text{if }U_{t}\leq\mu(X_{t})\\\ X_{t}&\text{if
}\mu(X_{t})\leq U_{t}\leq 1-\lambda\\\ X_{t}+1&\text{if }1-\lambda\leq
U_{t}\end{cases}$ (55)

and define $Y_{t+1}$ the same way from $Y_{t}$. This coupling is optimal, but
in particular we have:

$(P^{t}(s,\cdot)-P^{t}(s-1,\cdot))\mathbf{r}\leq 2\mathbb{P}(X_{t}\neq
Y_{t})\delta_{\max}.$

We remind that $\tau_{s}$ is the random time needed for the Markov chain
$X_{t}$ to hit $0$. The coupling time is lower than $\tau_{s}$:

$\mathbb{P}(X_{t}\neq Y_{t})\leq{\mathbb{P}}\left(\tau_{s\to 0}>t\right),$

so that summing over $t$ gives:

$\Delta^{\pi}(s)\leq 2\delta_{\max}\mathbb{E}\tau_{s},$

and using Lemma F.3 and Lemma F.1:

$\Delta^{\pi}(s)\leq
2\delta_{\max}\nu^{\pi^{\max}}(0)^{-1}\sum_{i=1}^{s}\frac{U}{\mu(i)}.$

∎