Jonatha Anselmi
email: jonatha.anselmi@inria.fr

Bruno Gaujal
email: bruno.gaujal@inria.fr

Louis-Sébastien Rebuffi
email: louis-sebastien.rebuffi@univ-grenoble-alpes.fr

Learning Optimal Admission Control in Partially Observable Queueing Networks

Keywords: Product-form queueing networks, Norton's theorem, admission control, reinforcement learning, regret

We develop 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, optimality refers to the average holding/rejection cost in infinite horizon, and efficiency is with respect to regret performance. While reinforcement learning in partially-observable Markov Decision Processes (MDP) is prohibitively expensive in general, we show that the regret at time T induced by our algorithm is Õ( T log(1/ρ)) where ρ ∈ (0, 1) is connected to the mixing time of the underlying MDP. In contrast with existing regret bounds, ours does not depend on the diameter (D) of the underlying MDP, which in most queueing systems is at least exponential in S, i.e., the maximal number of jobs in the network. Instead, the role of the diameter is played by the log(1/ρ) term, which may depend on S but we find that such dependence is "minimal". In the case of acyclic or hyperstable queueing networks, we prove that log(1/ρ) = O(S), which overall provides a regret bound of the order of Õ( √ T S). In the general case, numerical simulations support the claim that the term log(1/ρ) remains extremely small compared to the diameter. The novelty of our approach is to leverage Norton's theorem for queueing networks and an efficient reinforcement learning algorithm for MDPs with the structure of birth-and-death processes.

Introduction

Research on reinforcement learning in Markov Decision Processes (MDP) has been flourishing since Walkins' work on Q-learning [START_REF] Walkins | Learning from delayed rewards[END_REF], the celebrated model-free learning algorithm. Since then, several extensions of Q-learning [START_REF] Jin | Provably efficient reinforcement learning with linear function approximation[END_REF], Bayesian [START_REF] Ouyang | Learning unknown Markov decision processes: A Thompson sampling approach[END_REF][START_REF] Ouyang | Learning unknown markov decision processes: A thompson sampling approach[END_REF] or modelbased [START_REF] Jaksch | Near-optimal regret bounds for reinforcement learning[END_REF] approaches have been proposed to improve learning efficiency [START_REF] Fruit | Efficient bias-span-constrained exploration-exploitation in reinforcement learning[END_REF][START_REF] Tossou | Near-optimal Optimistic Reinforcement Learning using Empirical Bernstein Inequalities[END_REF] 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 Õ( √ DSAT ) 1 , 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 [START_REF] Wei | Model-free Reinforcement Learning in Infinite-horizon Average-reward Markov Decision Processes[END_REF] 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 [START_REF] Jin | Sample-efficient reinforcement learning of undercomplete pomdps[END_REF][START_REF] Azizzadenesheli | Reinforcement learning of POMDPs using spectral methods[END_REF][START_REF] Guo | A PAC RL algorithm for episodic pomdps[END_REF]. In this paper, we address this question in the context of queueing networks assuming that the learner only has access to the total number of jobs in the network. This places our problem in the family of Partially Observable MDPs (POMDPs).

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 [START_REF] Papadimitriou | The complexity of markov decision processes[END_REF]. Furthermore, it is NP-hard to compute the optimal memoryless policy [START_REF] Vlassis | On the computational complexity of stochastic controller optimization in pomdps[END_REF]. 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 [START_REF] Jin | Sample-efficient reinforcement learning of undercomplete pomdps[END_REF], and we will also follow this approach. The algorithm in [START_REF] Even-Dar | Reinforcement learning in POMDPs without resets[END_REF] assumes POMDPs without resets and has sample complexity scaling exponentially with a certain horizon time. The Bayesian algorithms proposed in [START_REF] Ross | Bayes-adaptive POMDPs[END_REF][START_REF] Poupart | Model-based bayesian reinforcement learning in partially observable domains[END_REF] learn POMDPs but bounds on the mean regret remain unknown for these approaches. A sampleefficient algorithm for episodic finite POMDPs is given in [START_REF] Jin | Sample-efficient reinforcement learning of undercomplete pomdps[END_REF]. 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 [START_REF] Azizzadenesheli | Reinforcement learning of POMDPs using spectral methods[END_REF]. For this algorithm, the authors find an orderoptimal 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 [START_REF] Anselmi | Reinforcement Learning in a Birth and Death Process: Breaking the Dependence on the State Space[END_REF]. Although the additional assumptions on the structure of the model mitigate, to some extent, the intrinsic complexity of POMDPs, learning algorithms with regret Õ( √ DSAT ) have remained elusive for all but trivial cases to the best of our knowledge.

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 Õ( T log(1/ρ)), where ρ ∈ (0, 1) is a parameter that is connected to the mixing time of the underlying MDP; see Section 5.2. Thus, our main contribution is a learning algorithm with a regret bound that does not depend on the diameter D; we recall that D grows exponentially in the size of the state space, denoted by S, even in the simple case of an M/M/1 queue with a finite buffer [START_REF] Anselmi | Reinforcement Learning in a Birth and Death Process: Breaking the Dependence on the State Space[END_REF]. In general, ρ depends on S but we claim that such dependence is minimal. In the case of acyclic or hyperstable networks, we show that log(1/ρ) = O(S), which overall provides a regret bound of the order of Õ( √ T S), while in the general case, this is corroborated by numerical simulations.

Optimal admission control is one of the most classical control problems in queues. It has been investigated in several works; see, e.g., [START_REF] Borgs | The optimal admission threshold in observable queues with state dependent pricing[END_REF][START_REF] Xia | Event-based optimization of admission control in open queueing networks[END_REF] and the references therein. However, these works consider the case where the model parameters are known, i.e., no learning mechanism is employed. The novelty of our approach is to leverage i) Norton's theorem for closed product-form queueing networks [START_REF] Chandy | Parametric analysis of queuing networks[END_REF] and ii) the efficiency of reinforcement learning in MDPs with the structure of birth-and-death processes [START_REF] Anselmi | Reinforcement Learning in a Birth and Death Process: Breaking the Dependence on the State Space[END_REF]. More specifically, our result uses Norton's theorem to replace the whole network by a single load-dependent queue in its stationary regime and relies on the mixing time τ mix of the network to apply this equivalence every τ mix time-steps. We notice that Norton's theorem is only used for the performance analysis of the algorithm. The key observation is that Norton's theorem helps us to somewhat cast the original partiallyobservable 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.

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 3 presents the problem addressed in the paper in detail and Section 4 presents how reinforcement learning works in the considered context. Section 5 is dedicated to the presentation of our learning algorithm (UCRL-M) and Section 6 to the analysis of its regret. In the latter, we state our main result in Theorem 6.1. Then, Section 7 discusses some technical aspects of our regret bound. Section 8 showcases the behavior of our algorithm on a multi-tier queueing network, and, finally, Section 9 draws the conclusions of our work.

Admission control in a queueing network

We consider an (open) Jackson network with N queues (or stations) having service rates µ o 1 , . . . , µ o N , routing probability matrix L = [L i,j : 0 ≤ i, j ≤ N ] and exogenous arrivals occurring with rate λ. 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). We assume that I + L + L 2 + • • • is convergent, which implies that all jobs eventually leave the network. Let also λ o i be the arrival rate at queue i, which is given by the unique solution of the traffic equations λ o i = λL 0,i + j λ o j L j,i , for all i. For all i, we assume that λ o i < µ o i , which ensures stability (positive recurrence). We further assume that the total number of jobs in the network cannot exceed S.

Before joining the network, jobs go through an admission controller. The purpose of the admission controller is to either admit or reject jobs in order to minimize some cost function. For each job, the immediate cost c t is decomposed into a per-rejection cost γ reject and a per-time-unit holding cost γ hold . This cost function is the long-run average cost per time unit:

lim T →∞ 1 T T t=0 c t .
When the controller can observe the state of the network and knows the parameters of the system (λ, µ o , L), this classical problem has been solved in [START_REF] Xia | Event-based optimization of admission control in open queueing networks[END_REF]. In the degenerate 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 [START_REF] Borgs | The optimal admission threshold in observable queues with state dependent pricing[END_REF].

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 γ reject for each rejected job; • for every time unit in the system, each job induces a holding cost γ hold (this is the classical cost function for admission control, see [START_REF] Borgs | The optimal admission threshold in observable queues with state dependent pricing[END_REF]); • the controller makes decisions only relying on its set of observations up to time t.

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 [START_REF] Rolia | The method of layers[END_REF][START_REF] Rolia | Predictive modelling of SAP ERP applications: Challenges and solutions[END_REF], 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 [START_REF]Configuring Concurrency in Knative[END_REF] 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 [START_REF] Wang | Estimating multiclass service demand distributions using markovian arrival processes[END_REF]. 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".

Markov Decision Process Formulation

In this section, we construct an MDP model for the system under investigation (referred to as "original MDP") as well as an artificial MDP (referred to as "aggregate MDP") that will be 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. The aggregate system is only used for the performance analysis of the algorithm.

Before introducing the original MDP, we notice that under the constraint that at most S jobs can circulate in the network, the open Jackson network above is equivalent to a closed network with S jobs. This closed network, illustrated in Figure 1, is identical to the open one except for an auxiliary queue, say queue 0, that represents the outside world and has service rate λ. The departures of queue 0 correspond to the arrivals of the initial open network (see Figure 1). In this setting, if a job is rejected, it can be represented in the closed network as the job being returned to the external queue.

We are now in a position to define both the original and aggregate MDPs for the closed queueing network.

Original MDP

Let us model the problem as an MDP, M o = (X o , A o , P o , r o ), where the superscript o stands for "original" throughout the paper. We first use uniformization to see the process in discrete time. The uniformization constant U (defined later, see Eq. ( 9)) is lower bounded by the sum of the rates: U ≥ λ + N i=1 µ o i . 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 X o is the set of all tuples (x 1 , . . . , x N ) given by the number of jobs x i in each queue i. • The action space is A o := {0, 1} where 0 stands for rejection and 1 for admission. To be consistent with the learning literature, where rewards are used instead of costs, we first define r max :=

λγreject+γ hold S U
and for each state-action pair (x, a), the reward are Bernoulli distributed with expected value

r o (x, a) := r max - λγ reject (1 -a) + γ hold s U = λγ reject a + γ hold (S -s) U , (1)
where s := N i=1 x i . Let Π o := {π : X o → A o } denote the set of stationary and deterministic policies. A stationary policy π is a deterministic function from X o to A o .

Then, the MDP evolves under π in the standard Markovian way. At each time-step t, the system is in state x t , the controller chooses the action a t = π(x t ) and receives a random reward whose expected value is r o (x t , a t ), and the system moves to state x ′ at time t + 1 with probability P o (x ′ | x t , a t ). The objective function is to minimize the long run average cost.

The average reward induced by policy π is:

g o (M o , π) := lim T →∞ 1 T T t=1 E[r o (x t , π(x t ))]. (2)
An optimal policy π * for the original MDP achieves the best average reward

g o (M o , π * ) = sup π∈Π o g o (M o , π).

Aggregate model

Let us define an aggregate MDP M = (S, A, P, r) where the network is replaced by a single queue.

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 [START_REF] Chandy | Parametric analysis of queuing networks[END_REF], also known in the literature as Flow Equivalent Server (FES) method [START_REF] Krieger | Queueing networks and markov chains, 2nd edition by g. bolch, s. greiner, h. de meer, and k.s. trivedi[END_REF]. When containing S jobs, the vector of the number of jobs in each queue forms a continuous-time Markov chain with stationary measure [START_REF] Krieger | Queueing networks and markov chains, 2nd edition by g. bolch, s. greiner, h. de meer, and k.s. trivedi[END_REF]

ν o (x) = 1 G(S) N i=0 λ o i µ i xi , (3)
for all x ∈ {x ∈ N N : |x| ≤ S}, where G(S) is a normalization constant, | • | denotes the L 1 norm and λ o i was defined in Section 2. The construction of our equivalent queue works as follows: 1. Given the closed Jackson network above, consider the (closed) network where queue 0 is short circuited (this means set µ o 0 = ∞) and let µ(s) denote the throughput 2 of the network with s jobs in total (see Figure 2 for an illustration). 2. Consider the original network where all queues except 0 are all replaced by a single queue that operates with rate µ(s) if it contains s jobs.

Then,

x:|x|=s ν o (x) = ν(Ss, s), ∀s = 0, . . . , S

where ν(Ss, s), for all s = 0, . . . , S, is the stationary measure of the reduced network with two queues. We remark that ν(Ss, s) is indeed the stationary measure of a birth-and-death process with birth rate λ1 s<S and death rate µ(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 µ(s) [START_REF] Kameda | A property of normalization constants for closed queueing networks[END_REF]. Lemma 3.1. The throughput function s → µ(s) is increasing, concave and bounded by µ max := i≤N µ o i .

2

The 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 µ(s) :=

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 . The throughput bound µ max can be significantly improved [START_REF] Krieger | Queueing networks and markov chains, 2nd edition by g. bolch, s. greiner, h. de meer, and k.s. trivedi[END_REF] but this will not change the structure of our results.

Norton equivalent queue Jackson network

Aggregate 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 = (S, A, r, P ).

• The state space S = {0, . . . , S} consists of all possible numbers of jobs in the queueing network. We denote by S ′ := S + 1 the number of states of the aggregate MDP. • The actions are the same as for the original MDP: A = A o = {0, 1} (reject or accept). • The original reward in [START_REF] Walkins | Learning from delayed rewards[END_REF] does not depend on the precise position of the jobs in the network but only on their number. Therefore for s ∈ S and a ∈ A, we can define the expected reward as r(s, a) = λγ reject a + γ hold (Ss) U .

(

) 5
On a side note that anticipates on the future, we will use an upper bound on the difference of expected rewards between two neighboring states δ max := γ reject + γ hold U . We will use δ max instead of r max (defined in Section 3.1) in the following derivation of the regret, as δ max does not depend on S and this will help us gain a factor S in the regret bound. • The transition probabilities (P π ) are defined as follows.

Let π be a policy (a function from S → A) on M . By convention, π will also be seen as a policy in the original MDP M o using the natural extension, i.e., if x ∈ S o , then π(x) := π(|x|). We can now define the transition matrix for policy π as the transition matrix in the aggregate MDP M under the stationary measure ν o,π :

P (s ′ | s, π(s)) = x,|x|=s y,|y|=s ′ ν o,π (x) ν π (s) P o (y | x, π(x)), (6)
where ν π (s) = x,|x|=s ν o,π (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 ν π (s) is also the stationary measure of the Norton equivalent queue with transition matrix P π under policy π. Let Π := {π : S → A} denote the set of stationary and deterministic policies. Definition 3.2. The average gain induced by policy π is:

g(M, π) := lim T →∞ 1 T T t=1 E[r(s t , π(s t ))]. (7)
The optimal policy π * achieves

g(M, π * ) := g * (M ) := sup π∈Π g(M, π). ( 8
)

Comparison between both MDPs

It should be clear that the original MDP M o has a greater set of policies than the aggregate MDP M because it has more states. Therefore,

g o (M o , π * ) ≥ 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 Π o sum be the subset of policies in

M o such that for all π ∈ Π o sum , π(x) = π(y) if |x| = |y|.
Then, the stationary measure on M o under any policy π in Π o sum , and the stationary measure under π on M satisfy x,|x|=s ν o,π (x) = ν π (s). Therefore, we get for all π in Π o sum ,

g o (M o , π) = x ν o,π (x)r o (x, π(x)) = s x,|x|=s ν o,π (x)r(s, π(s)) = s ν π (s)r(s, π(s)) = g(M, π).

Now taking the maximum over all policies in

Π o sum yields max π∈Π o sum g o (M o , π) = g * (M ).
When the full state is not observable, the best one can aim for is to learn max π∈Π o sum g o (M o , π). Therefore, in the following we will consider the regret with respect to this oblivious optimal gain g * (M ).

Bias and diameter

In the following, we will heavily use the bias [START_REF] Puterman | Markov Decision Processes: Discrete Stochastic Dynamic Programming[END_REF] of a policy on M (although it has no intuitive meaning relative to the original MDP) as well the diameter of the aggregate MDP. Definition 3.3 (Diameter of an MDP). Let π : S → A be a stationary policy of any MDP M with initial state s. Let T (s ′ |M, π, s) := min{t ≥ 0 : s t = s ′ |s 0 = s} be the random variable for the first time step in which s ′ is reached from s under π. Then, we say that the diameter of M is

D(M ) := max s̸ =s ′ min π:S→A E [T (s ′ |M, π, s)] .
Again, let us point out that we will only consider the diameter on the aggregate MDP for the computations, as it is needed to control the bias terms of the aggregate MDP (see Appendix F). We will never need to consider the bias or the diameter of the original MDP.

Reinforcement Learning

This section presents how reinforcement learning works in this context. The basic idea is that the learner can observe the external behavior of the network but has no information about its internal behavior. Despite this lack of information, it decides which jobs to admit to eventually be as efficient as if it knew everything about the system.

What does the learner know?

• The learner has some static information about the system. It knows an upperbound on the number of servers (N ≤ N max ) inside the network and on their service rates (∀i,

µ o i < µ max i
). This means that the partial uniformization constant

U 1 = Nmax i=1 µ max i is known by the learner.
• The expected cost in state-action pair (s, a) is unknown as it depends on the unknown parameter λ (see ( 5)). However, the cost parameters γ reject and γ hold are known. • On the dynamic side, the learner can observe the external events, i.e., the arrivals and the departures of jobs. This implies that at any time 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 learning algorithm knows T , i.e., the number of time steps where it can take observations and actions. Notice that this is not a strong requirement as one can make the algorithm oblivious to T by using a classical doubling trick on T [START_REF] Jaksch | Near-optimal regret bounds for reinforcement learning[END_REF]. All these assumptions are either classical in reinforcement learning (as for example the bounds on the parameters) or natural in this context.

When does the learner acts?

The queueing system evolves in continuous time. Its external events are the arrival and departure processes. We assume that the learning algorithm is equipped with an independent Poisson clock that ticks at rate U 1 . The algorithm will take decisions at every tick of its own clock as well as at each arrival and departure.

10

Notice that since we assume that the network is a stable Jackson network, then, under its stationary state, the arrival process and the departure process are both Poisson with rate λ and independent (this is a classical property of stable Jackson networks, see for example Corollary 5.7.3 in [START_REF] Ross | Stochastic Processes. Wiley series in probability and mathematical statistics[END_REF]). Therefore, the total point process indicating when the learner acts forms a Poisson process with a unknown rate

U = 2λ + Nmax i=1 µ max i . (9)
The rate U is used as the uniformization constant to see the continuous time MDP as a discrete time one as in Section 3.

How do we measure the learner performance?

We will use the classical definition on the regret to assess the learning performance. Definition 4.1 (Regret). The regret at time T of the learning algorithm L is

Reg(M, L, T ) := T g * (M ) - T t=1 r L t . (10)
Here, g * (M ) is the oblivious optimal gain defined in [START_REF] Wei | Model-free Reinforcement Learning in Infinite-horizon Average-reward Markov Decision Processes[END_REF]. The reward r L t is the reward of the state visited at time t by the learning algorithm.

5 Learning Algorithm with Modules: UCRL-M

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, spanning over the interval [t k , t k+1 -1], one admission policy π k is used to control the network and the learner observes the system (arrivals and departures) while collecting rewards under π k . At the end of the episode, the estimation of the true transition probabilities and rewards (the model), pk and rk respectively, as well as the confidence region M k are updated using the samples collected during the episode. This gives pk+1 , rk+1 and M k+1 . The next policy π k+1 is the best policy for the best MDP inside the confidence region M k+1 (optimism); with 'best MDP', we mean the MDP that is returned by Extended Value Iteration (EVI) as discussed in Appendix B.

In our case with partial observations, the number of jobs at time t, (s t ) t≤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 , . . . , s τmix } of observations and try to learn using this extended information. If τ mix is well chosen, i.e., larger than the mixing time of the MDP, then each subsequence s i , s i+τmix , s i+2τmix , . . . 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 τ mix learning algorithms L 1 , . . . , L τmix , using respectively the subsequence (s i+kτmix ) k∈N of observations, which are called modules in the following. The behavior of the modules in illustrated in Figure 3. Each learning module L i behaves similarly as the classical

• • • • • • • • L 1 L 2 L 3 L 1 L 2 L 3 L 1 L 2
Figure 3: Illustration of the interleaving of the modules over time with τ mix = 3.

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 5.3. The main technical difficulties in the control of the behavior of the algorithm are:

1. The learning modules L 1 , . . . , L τmix are not independent of each other, so one must be careful in assessing the interplay between the modules. 2. For each learning module L i , its own sequence of observations s i+τmix , s i+2τmix , s i+3τmix , . . . is not really stationary and independent, but only weakly correlated.

Number of modules: τ mix

Let us first give a more precise definition of the modules, where their number τ 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 ≤ t ≤ τ mix -1, the module m t is defined in the following way: first t ∈ m t , then we wait τ mix steps to add the next time-step to that module, so that t, t+τ mix , t+2τ mix , . . . ∈ m t , until time-step T is reached. More formally one can identify, m t = t mod τ mix .

The number of modules τ mix is chosen using the following construction. Let us consider the original MDP under any policy π, with stationary measure ν o,π . There exists C > 0, ρ ∈ (0, 1) such that:

max π∈Π sup x0∈S P o,π x0 (x t = •) -ν o,π T V ≤ Cρ t ∀t > 0, (11)
where P o,π x0 (x t = •) is the distribution of the state at time t under policy π in the original MDP, with starting state x 0 . Let us then define

τ mix := ⌈5 log T / log ρ -1 ⌉. (12)
The reason for this precise choice will appear in the analysis of the regret (see Section 6) but the general idea behind this choice comes from Lemma D.1 given in appendix, that basically says that after τ mix steps, the correlation between the state at time t and the state at time t + τ mix , under any policy, is smaller than C ′ ρ τmix , where C ′ is a constant.

The fact that the number of modules used by the algorithm depends on ρ 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 7.

Confidence region

As mentioned earlier, our learning algorithm relies on the "Optimism in face of uncertainty" principle. Here, we provide the explicit construction of a confidence region 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 (m) t k (s, a) be the cumulative number of visits to (s, a) at all times t = m mod τ mix smaller than t k , and excluding the visits during the ramping phases Φ (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) ∈ arg max m N (m) t k (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 (m k (s,a)) t k (s, a) ≥ 1 τmix N t k (s,
p(m) k (s ′ |s, a) := t k -1 t=1 1 {st=s,at=a,st+1=s ′ ,mt=m} 1 {t / ∈Φ} max 1, N (m) t k (s, a) (14) r(m) k (s, a) := p(m) k (s + 1|s, a)γ reject + γ hold S -s U , (15)
where Φ is the set of the time steps in the ramping phases defined in the algorithm. M k is the confidence set of MDPs whose rewards r and transitions p satisfy:

∀(s, a), r(s, a) - r(m k (s,a)) k (s, a) ≤ δ max 2 log (2At k ) max 1, N (m k (s,a)) t k (s, a) ; (16)
∀(s, a), ∥p(• | s, a) - p(m k (s,a)) k ( • | s, a) ∥ 1 ≤ 8 log (2At k ) max{1, N (m k (s,a)) t k (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 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, formally defined below, finds the best optimistic MDP and policy within this confidence set using Extended Value Iteration, 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 (m) k (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 πk , then the stopping criterion gives the following guarantee:

∀(s, m) V (m) k (s, πk (s)) ≤ max{1, N (m) t k (s, πk (s))}. (18)
5.4 UCRL-M: learning with τ mix modules

We are now in a position to give our learning algorithm, UCRL-M (Upper Confidence Reinforcement Learning with several Modules), 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 πk and an optimistic MDP Mk ∈ M k according to [START_REF] Xia | Event-based optimization of admission control in open queueing networks[END_REF]. Finally, to explore the MDP at episode k, it first iterates on the MDP over τ mix time-steps and discards these samples (ramping phase) to start the observations closer to the stationary distribution of the current policy. This phase is necessary to guarantee that observations within a module are nearly independent. Afterwards, UCRL-M explores the true MDP with the optimistic policy π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 M k that is built using all modules (see [START_REF] Anselmi | Reinforcement Learning in a Birth and Death Process: Breaking the Dependence on the State Space[END_REF]).

Algorithm 1:

The UCRL-M algorithm.

Input: S and A. ), the number of useful observations. As for the expected number of episodes, EK = O(log T ) because of the doubling trick used to end the episodes (see [START_REF] Jaksch | Near-optimal regret bounds for reinforcement learning[END_REF] for example).

1 Set t = 0, k = 0; 2 while t ≤ T do 3 Initialize episode k with t k := t;
M k ∈M k max π g(M k , π) - δ max √ t k . ( 19
)
Note that the total number of useful samples (excluding the steps made during the ramping phases ) is T -Kτ mix , and each module uses T -Kτmix τ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 τ mix or t evi that only appears at the beginning of each episode, and the number of episodes is small w.r.t. T .

6 Regret of UCRL-M

Main result

Let us recall that S is the global bound on the number of jobs, S ′ = S + 1 is the number of states, γ reject is the rejection cost, γ hold is the unit-time holding cost and D is the diameter of the aggregate MDP. Also, ν π max (s) is the stationary measure in the aggregate MDP under the policy that accepts all jobs, ρ ∈ (0, 1) is such that (11) holds true and µ(i) is the service rate in the aggregate MDP when i jobs are in the system.

Define the constant

C 1 := i0-1 i=1 µ(i0) µ(i) ≥ 1
, where i 0 is chosen such that µ(i 0 ) > λ. We notice that i 0 exists because the open (unconstrained) network defined in Section 2 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 :=

(λγreject+γ hold )C1 µ(1)(1-λ/µ(i0)) . Theorem 6.1. Let M ∈ M. Define Q max := 10C2S ′2 ν π max (S) 2 log 10C2S ′2 ν π max (S) 4 . Define also the constant κ = 228(γ reject + γ hold U ) U µ(1) C 1 1 - λ µ(i0) -3
. For the choice τ mix = 5 log T log 1/ρ and A = 2, and assuming τ mix S ≥ 2 and T > max e 2 4T , τ mix , it holds that

E [Reg(M, UCRL-M, T )] ≤ κ log (2T ) T log -1 (1/ρ) + R LO , (20)
where R LO := 138r max D 2 max Q max , T 1/4 log 4 (4T ) log 2 1/ρ 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/ρ).

Although we do not know any explicit bounds on ρ for all possible networks, it is quite reasonable to predict that log -1/2 (1/ρ) can be of order √ S. In fact, this can be shown for acyclic networks as well as for hyper-stable networks as it will be shown in Section 7. This implies that the regret of UCRL-M is Õ( √ ST ), which is a major improvement over the best bound for general MDPs, namely Õ( √ 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.

Outline of the proof

To compute the expected regret E[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 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

(m) k (s) := a V (m) k
(s, a)(ρ *r(s, a)) the regret at episode k induced by state s in module m, with V (mt) k (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:

E [Reg] ≤ E [R in ] + E [R out ] + E [R ramp ] (21)
with K the number of episodes and the regret where the MDP is in the confidence region being R in :=

m s K k=1 R (m) k (s)1 M ∈M k ,

and when it is outside

R out := m s K k=1 R (m) k (s)1 M /
∈M k and the regret of the ramping phases R ramp = k t k +τmix-1 t=t k r(s t , πk (s, t)). Each term is then bounded as explained in Appendix A.

Controlling the regret bound parameter ρ

The efficiency of UCRL-M is critically based on controlling τ mix and ρ. In particular, Theorem 6.1 says that the regret of UCRL-M depends on W := log -1/2 (1/ρ).

Bounds using mixing and coupling times

In Section 5, the number of modules τ mix is defined as τ mix := 5 log T / log ρ -1 . where ρ is such that

max π sup x0∈S P o,π x0 (x t = •) -ν o (π) T V ≤ Cρ t ∀t > 0. (22)
Let us first recall classical results from Markov chain theory [START_REF] Levin | Markov Chains and Mixing Times[END_REF] relating ρ with the mixing and coupling time of a Markov chain. Let us consider any Markov chain with transition matrix P and stationary distribution ν (in our case, consider the Markov chain under the policy that attains the maximum in [START_REF] Rolia | Predictive modelling of SAP ERP applications: Challenges and solutions[END_REF]). Let us define d(t) := sup x0∈S ∥P x0 (x t = •) -ν∥ T V . Then, the mixing time of the chain is defined as

t mix := min{t : d(t) ≤ 1/4}.
A classical bound on ρ is then obtained by using the mixing time:

ρ ≤ 1 2 t -1 mix (23)
This implies that W ≤ t mix log(2).

Another bound on ρ can be obtained by using the coupling time. The coupling time is τ 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) ≤ max x,y P(τ x,y > t). By using Markov inequality, this implies that

t mix ≤ 4 max x,y E[τ x,y ]. (24)
Therefore, a bound on the expected coupling time translates into a bound on ρ.

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 [START_REF] Dopper | Bounds for the coupling time in queueing networks perfect simulation[END_REF]Theorem 5.3], where the following result is proved in the stable case. Using our notation,

max x,y E[τ x,y ] ≤ N i=1 U 2 (λ o i + µ o i )(µ o i -λ o i ) S, (25)
where U is the uniformization constant and (λ i ) i≤N is the solution of the traffic equations.

According to Equations ( 23) and ( 24), this induces the following bound on the term W in the regret:

W ≤ κ 0 √ N S,
where κ 0 is a constant:

κ 0 = max i N i=1 U λ o i +µ o i .

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, j L ji µ o j + L 0i λ < µ o i . 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 [START_REF] Anselmi | Efficiency of simulation in monotone hyper-stable queueing networks[END_REF], where the following bound is given (Theorem 2):

max x,y E[τ x,y ] ≤ κ 2 N 2 S N i=1 λ o i µ o i -λ o i , (26)
where κ 2 is a constant. Using Equations ( 23) and ( 24), this induces a similar bound on the term W in the regret:

W ≤ κ 3 N √ S,
where κ 3 is yet another constant.

Making the algorithm oblivious to ρ

By construction, the current version of UCRL-M uses explicitly τ mix = 5 log T / log ρ -1 modules. This can be a problem as it implies an a priori knowledge of ρ, 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 [START_REF] Azar | Minimax regret bounds for reinforcement learning[END_REF] requires the knowledge of the diameter of the MDP being learned.

Here, we can patch UCRL-M to make it oblivious to ρ by making sure that τ mix ≥ 5 log T / log ρ -1 for any large enough T . For example, one can chose τ 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 6.1.

Numerical experiments

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 4. 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 1p or flow through the application and database tiers. This multi-tier structure is common in empirical studies of computer systems [START_REF] Urgaonkar | An analytical model for multi-tier internet services and its applications[END_REF] and is the default architecture of web applications deployed on Amazon Elastic Compute Cloud (EC2) [34]. This model may be studied as an example of the generic case described in Section 2. Notice that given the routing from Figure 4, the stability condition is met if λ 1-p < µ, where µ = µ o 1 = . . . = µ o 3n is the service rate of the queues in the network.

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 5, 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 µ 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 7 and even in Section 2. In Figure 5, we remark that as we let the number of queues n (and the number of jobs S) scales multiplicatively, the regret increases as log(S). Knowing that the dependency in S of the regret bound from Theorem 6.1 mainly comes from ρ, this is much slower than the square root bounds given in Section 7 (under strong assumptions). This can be interpreted as the bound of Equation [START_REF] Rolia | Predictive modelling of SAP ERP applications: Challenges and solutions[END_REF] being too large as it considers the mixing from the worst state, while on average it is more likely for the algorithm to mix from states that are visited the most, which are already close to stationary states.

We see in Figure 6 that the chosen policy does not converge to the optimal threshold, as the algorithm needs to ensure exploration phases. Its Cesarò sum however does converge 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 τ mix = 3. Now, we perform another experiment to observe the dependency of the regret in the choice of τ mix for this queueing system. The intuition is the following: as explained in the high-level description of the algorithm in Subsection 5.1, UCRL-M could be compared to τ mix instances of UCRL2 [START_REF] Jaksch | Near-optimal regret bounds for reinforcement learning[END_REF], where all modules but the best one is discarded at each episode. This best module runs on roughly T τmix time-steps, and its regret can be compared to 1 τmix times the expected regret of UCRL-M. With this intuition in mind, we plot in Figure 7 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. In this particular example, the observations behave as if they were independent even if the algorithm only uses a single module. Intuitively, the system remains close to stationarity despite the policy changes, which could explain the limited effect of the 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 6.1.

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 [START_REF] Jaksch | Near-optimal regret bounds for reinforcement learning[END_REF] and that is exponential in the size of the space S in most queueing systems.

While our result strongly relies on Norton's equivalence 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 [START_REF] Kritzinger | A generalisation of norton's theorem for multiclass queueing networks[END_REF] and also used in the context of non-product-form queueing networks for approximate analysis [START_REF] Krieger | Queueing networks and markov chains, 2nd edition by g. bolch, s. greiner, h. de meer, and k.s. trivedi[END_REF][START_REF] Anselmi | Approximate solution of multiclass queuing networks with region constraints[END_REF].

• M(t) the set of MDPs M k such that t k ≤ t < t k+1 For the terms out of the confidence sets, we have:

R out ≤ r max m s K k=1 V (m) k (s)1 M / ∈M k ≤ r max m s K k=1 N (m) t k (s)1 M / ∈M k using the stopping criterion = r max T t=1 s K k=1 1 t k =t N t (s)1 M / ∈M(t) ≤ r max T t=1 s N t (s)1 M / ∈M(t) = r max T t=1 1 M / ∈M(t) s N t (s) ≤ r max T t=1 t1 M / ∈M(t) .
We now need Lemma D.2 to control the probability that the MDP fails to be within the confidence bounds P {M / ∈ M(t)}. Taking the expectations and using Lemma D.2, we obtain

E [R out ] ≤ r max T t=1 tP {M / ∈ M(t)} ≤ r max T t=1 S ′ + 16CS ′ A 2t 2 ≤ r max (S ′ + 16CS ′ A). ( A3
)
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 ∈ M k and to simplify the notations, we will omit the use of the

R (m) in,k = s,a V (m) k (s, a)(g * -r(s, a)) ≤ s,a V (m) k (s, a)(g k -r(s, a)) + ε k s,a V (m) k (s, a) = s,a V (m) k (s, a)(g k -rk (s, a)) + s,a V (m) k (s, a)(r k (s, a) -r(s, a) + ε k ).
In the next few steps, we will focus on rewriting the first sum. With (B18) and using the definition of the iterated values from EVI, we have for a given state s and a s := πk (s):

(g k -rk (s, a s )) - s ′ pk (s ′ |s, a s )u (k) i (s ′ ) -u (k) i (s) ≤ ε k , so that: R (m) in,k ≤ v (m) k Pk -I u i + s,a V (m) k (s, a)(r k (s, a) -r(s, a)) + ε k s,a V (m) k (s, a).
Again, with hk being the bias of the average optimal policy for the optimist MDP, define:

d k (s) := u (k) i (s) -min x u (k) i (x) -hk (s) -min x hk (x) . Then for any s: |d k (s)| ≤ ε k .
Notice that the unit vector is in the kernel of Pk -I . Therefore, in the first term, we can replace u i by any translation of it. We get:

v (m) k Pk -I u i = v (m) k Pk -I hk + v (m) k Pk -I d k .
so that, using the definition of ε k , we have that overall:

R (m) in ≤ k v (m) k Pk -I hk R (m) bias + k v (m) k Pk -I d k + 2δ max k s,a V (m) k (s, a) √ t k R (m) EVI + k s,a V (m) k (s, a)(r k (s, a) -r(s, a)) R (m) rewards
We can already further simplify the term related to EVI. Notice that:

v (m) k Pk -I d k ≤ s V k (s, πk (s)) • ∥p k (•|s, πk (s)) -1 s ∥ 1 • sup s ′ |d k (s ′ )| ≤ 2ε k s V (m) k (s, πk (s)) ≤ 2δ max s,a V (m) k (s, a) √ t k ≤ 2δ max s,a V (m) k (s, a) max {1, N (m k (s,a)) t k (s, a)} ,
where in the last inequality we used that max{1, N

(m k (s,a)) t k (s, a)} ≤ t k ≤ T . Thus, for T ≥ e 2
2AT the regret term coming from the consequences and approximations of EVI satisfies

R (m) EVI ≤ δ max 2 2 log(2AT ) k s,a V (m) k (s, a) max {1, N (m k (s,a)) t k (s, a)} . (A4)
Let us now deal with the term R (m) rewards , as it will be bounded by a similar term as in equation (A4). Indeed, as M ∈ 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 (m) rewards ≤ δ max 2 2 log(2AT ) k s,a V k (s, a) max {1, N (m k (s,a)) t k (s, a)} (A5)
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 πk in the true MDP M . We get

R (m) in ≤ k v (m) k Pk -P k h k R (m) trans + k v (m) k Pk -P k hk -h k R (m) diff + k v (m) k (P k -I) hk R (m) ep + δ max 4 2 log(2AT ) k s,a V (m) k (s, a) max {1, N (m k (s,a)) t k (s, a)} R (m) EVI +R (m) rewards . (A6)
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 EVI + R rewards = δ max 4 2 log(2AT ) k s,a V k (s, a) max {1, N (m k (s,a)) t k (s, a)} . ( A7
)
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

trans will also use the confidence bounds on the transition as well as our knowledge of the bias in the true MDP. R (m) diff 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 (m) ep 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 (m) trans

To bound R (m) trans , we can follow the computations from [START_REF] Anselmi | Reinforcement Learning in a Birth and Death Process: Breaking the Dependence on the State Space[END_REF]. We will use our knowledge of the bias h k and the control on the transitions in the optimistic MDP to simplify the regret term.

Notice that for a fixed state 1 ≤ s ≤ S -1:

s ′ p (s ′ |s, πk (s)) h k (s ′ ) = s ′ p (s ′ |s, πk (s)) (h k (s ′ ) -h k (s)) + h k (s).
The same is true for pk , and knowing the MDP is a birth and death process:

R (m) trans = k s s ′ V (m) k (s, πk (s)) • (p k (s ′ |s, πk (s)) -p (s ′ |s, πk (s))) • h k (s ′ ) = k s s ′ V (m) k (s, πk (s)) (p k (s ′ |s, πk (s)) -p (s ′ |s, πk (s))) • (h k (s ′ ) -h k (s)) ≤ k s V (m) k (s, πk (s))∥p k (•|s, πk (s))-p (•|s, πk (s))∥ 1 max ∆ πk (s), ∆ πk (s + 1) ≤ 4 2 log (2AT ) k s,a ∆(s + 1)V (m) k (s, a) max{1, N (m k (s,a)) t k (s, a)} ,
where ∆ 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 [START_REF] Anselmi | Reinforcement Learning in a Birth and Death Process: Breaking the Dependence on the State Space[END_REF]. Notice that the final term looks similar to the term coming from EVI and rewards related computations (A7). 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. [START_REF] Ouyang | Learning unknown markov decision processes: A thompson sampling approach[END_REF], we have shown that: We now wish to control this term, R EVI and R 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

(m k (s,a)) t k (s, a) ≥ 1 τmix N t k (s,
∆(s + 1) E [N T (s)]. (A9)
This is one of the terms mainly contributing to the regret, the other one being, doing similar computations:

R EVI + R rewards ≤ 12δ max 2Aτ mix log (2AT ) s≥0 E [N T (s)] (A10)
Now, let N π max T be the number of visits when the starting state is sampled randomly from the initial distribution ν π max and the policy π max is always chosen. By stochastic ordering, as N T (s)

≤ st N π max T , we have E [N T (s)] ≤ E N π max T = T ν π max (s).
We can therefore rewrite the main contributing term to the regret as:

12 2Aτ mix T log (2Aτ mix T ) S s=0 (∆(s + 1) + δ max ) ν π max (s). (A11)
Replace in the equation the choice τ mix = 5 log T / log ρ -1 and recall that we had, from Proposition F.4, ∆(s) := 2δ max ν π max (0

) -1 s i=1 U µ(i) ≤ 2δ max ν π max (0) -1 U µ(1) s. Using Lemma F.1, since S s=0 (∆(s + 1) + δ max ) ν π max (s) ≤ 3δ max ν π max (0) -1 U µ (1) S s=0
(s + 1) ν π max (s)

≤ 3δ max ν π max (0) -1/2 U µ(1) C 1 s≥0 s λ µ(i 0 ) s/2 ≤ 3δ max ν π max (0) -1/2 U µ(1) C 1 1 1 - λ µ(i0) 2 ≤ 3δ max U µ(1) C 1 1 1 - λ µ(i0) 3 ,
then, assuming τ mix ≤ T , the main term is upper bounded by:

72δ max U µ(1) C 1 1 - λ µ(i 0 ) -3 log (AT ) 5AT log -1 (ρ -1 ). (A12) A.6 Bound on R (m) diff
We now deal with the term involving the difference of bias R (m) diff , defined in equation A6. The proof mainly follows the one from [START_REF] Anselmi | Reinforcement Learning in a Birth and Death Process: Breaking the Dependence on the State Space[END_REF], 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 hk and h k , so that we will need Lemma E.4, and we are interested in controlling ∥ hkh k ∥ ∞ .

Fix the module m and the episode k, with policy πk . Choose a state minimizing N (m k (s,π k (s))) t k (s, πk (s)), and call this state x k , a k := πk (x k ) and m ′ := m k (x k , a k ):

for this state, the confidence bounds are at their worst, and

log(2At k ) max{1,N (m ′ ) t k (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:

∥ Pk -P k ∥ ∞ ≤ 4 2 log (2At k ) max{1, N (m ′ ) t k (x k , a k )} .
We now want to use Lemma E.4. In our case, notice that in the true MDP we have D ≥ T πk hit ≥ 1 for S large enough. Remark also that D πk can be replaced by D in the last inequality of the proof of E.4, as span(h πk ) ≤ D by construction of πk with EVI, following the same argument as in [START_REF] Jaksch | Near-optimal regret bounds for reinforcement learning[END_REF]Equation (11)].

∥ hk -h k ∥ ∞ ≤ 8r max D 2 2 log (2At k ) max{1, N (m ′ ) t k (x k , a k )} . (A13) Hence, R (m) diff ≤ s s ′ V (m) k (s, πk (s)) • (p k (s ′ |s, πk (s)) -p (s ′ |s, πk (s))) • ( hk (s ′ ) -h k (s ′ )) ≤ s V (m) k (s, πk (s)) • ∥p k (•|s, πk (s)) -p (•|s, πk (s))∥ 1 ∥ hk -h k ∥ ∞ ≤ 32D 2 r max log (2AT ) Σ (m) ,
where in the last inequality we have used (A13) and defined

Σ (m) := s,a k t k+1 -1 t=t k 1 {st,at=s,a} 1 {t∈m} max{1, N (m k (s,a)) t k (s, a)} max{1, N (m ′ ) t k (x k , a k )} . By the choice of x k , N (m ′ ) t k (x k , a k ) ≤ N (m k (s,a)) t k
(s, a) for any state-action pair (s, a), so that we can compute the sum Σ := m Σ (m) , with I k := t k+1t k the length of episode k:

Σ ≤ m s,a k t k+1 -1 t=t k 1 {st,at=s,a} 1 {t∈m} max{1, N (m ′ ) t k (x k , a k )} = k I k max{1, N (m ′ ) t k (x k , a k )} . Now, define Q max := 10C2S ′2 ν π max (S) 2 log 10C2S ′2 ν π max (S) 4
where we defined the constant

C 2 = (λγreject+γ hold )C1
µ(1)(1-λ/µ(i0)) , and I(T ) := max Q max , T 1/4 . We split the sum depending on whether the episodes are shorter than I(T ) or not, and call K ≤I the number of such episodes. This yields:

Σ ≤ K ≤I I(T ) + k,I k >I(T ) I k max{1, N (m ′ ) t k (x k , a k )} .
Using the stopping criterion for episodes, and that we have chosen the module m ′ in equation ( 13) to have the inequality

V (m ′ ) k (x k , a k ) ≥ 1 τmix V k (x k , a k ): Σ ≤ K ≤I I(T ) + k,I k >I(T ) τ mix I k max{1, V k (x k , a k )} .
Now we can end the computations as in [START_REF] Anselmi | Reinforcement Learning in a Birth and Death Process: Breaking the Dependence on the State Space[END_REF]. Denote by E the event:

E = ∀k s.t I k > I(T ), 1 max{1, V k (x k , a k )} ≤ 2 ν π max (S)I k .
By splitting the sum, using the above event, we get:

Σ ≤ K ≤I I(T ) + 1 E k,I k >I(T ) 2τ mix ν π max (S) + 1 Ē k,I k >I(T ) τ mix I k ≤ K ≤I I(T ) + 1 E (K -K ≤I ) 2τ mix ν π max (S) + 1 Ē τ mix T.
We use Corollary E.6 to get P Ē ≤ 1 4T , so that when taking the expectation:

E [Σ] ≤ E [K ≤I ] I(T ) + E [(K -K ≤I )] 2τ mix ν π max (S) + τ mix 4 . Now using Lemma C.2, S ′ A ≥ 4, I(T ) ≥ 2 ν π max (S) and that 1 log 2 + 1 4 ≤ 2: E [Σ] ≤ E [K] I(T )τ mix + τ mix 4 ≤ 2S ′ Aτ mix log(2AT )I(T ).
Therefore, we have that:

E R (m) diff ≤ 64r max S ′ AD 2 τ mix I(T ) log 2 (2AT ) . (A14) A.7 Bound on R ep
The last regret term we have to bound is related to the count of episodes.

R (m) ep = k v (m) k (P k -I) hk .
We first want to sum over the modules to get the same kind of term as in [START_REF] Jaksch | Near-optimal regret bounds for reinforcement learning[END_REF], written as a martingale difference sequence, and then take the expectation. Following that proof, we define

X t := (p(•|s t , a t ) -e st ) hk(t) 1 M ∈M k(t) ,
where k(t) is the episode containing step t and e i the vector with i-th coordinate 1 and 0 for the other coordinates. We obtain

c v (m) k (P k -I) hk ≤ v k (P k -I) hk ≤ t k+1 -1 t=t k X t + hk (s t k+1 ) -hk (s t k ) ≤ t k+1 -1 t=t k X t + Dr max ,
and by summing over the episodes we get

m R (m) ep ≤ T t=1 X t + KDr max .
Notice that E [X t |s 1 , a 1 , . . . , s t , a t ] = 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

E m R (m) ep ≤ S ′ Aτ mix log 2 8T S ′ Aτ mix • Dr max .
As for the computation of (A2), assuming τ mix S ′ A ≥ 4:

E [R ep ] ≤ 2r max S ′ ADτ mix log(2AT ). (A15) ≤ x P {x t ′ -τmix = x} ∥P {x t ′ = • | x t ′ -τmix = x} -P {x t = •}∥ T V
then using a triangle inequality:

∥P {x t ′ = • | x t ′ -τmix = x} -P {x t = •}∥ T V ≤ P {x t ′ = •} -ν πk T V + P {x t ′ = • | x t ′ -τmix = x} -ν πk T V , we get ∥P -Q∥ T V ≤ 2Cρ τmix ,
where in the last inequality we used assumption [START_REF] Guo | A PAC RL algorithm for episodic pomdps[END_REF] twice, as t ′ and t ′τ mix belong to the same episode, and therefore can be related to the same stationary measure ν πk . To clarify, the exponent τ mix in the inequality is loose, as τ mix is the number of timesteps in the aggregate 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 M(t) is bounded by:

P {M / ∈ M(t)} ≤ S ′ 2t 3 + 8CS ′ 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

ε p = 2 n log (16At 4 ) ≤ 8
n log (2At). Define the events:

A n = ∥p (m) (•|s, a) -p(•|s, a)∥ 1 ≥ 8 n log (2At) (D23)
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.

Proof. Let s, s ′ ∈ S be recurrent states under policy π. Call τ s→s ′ the random time needed to reach state s ′ from state s. Then:

J s (π, T ) = E T t=0 r(s t ) = E τ s→s ′ -1 t=0 r(s t ) + E   T t=τ s→s ′ r(s t )   ≤ r max E [τ s→s ′ ] + J s ′ (π, T ) ≤ r max D π + J s ′ (π, T ),
which proves the lemma.

Lemma E.2. Consider two unichain MDPs M and M ′ . Let r = r ′ ∈ [0, r max ] and P, P ′ be the rewards and transition matrix of MDP M, M ′ under policy π, π ′ respectively, where both MDPs have the same state and action spaces. Denote by g, g ′ the average reward obtained under policy π, π ′ in the MDP M, M ′ respectively. Then the difference of the gains is upper bounded.

|g -g ′ | ≤ r max D π ∥P -P ′ ∥ ∞ .
Proof. Define for any state s the following correction term b(s

) := r max D π ∥p(•|s) - p ′ (•|s)∥ 1 .
Let us show by induction that for T ≥ 0,

T -1 t=0 P t r ≤ T -1 t=0 P ′t (r + b).
This is true for T = 0. Assume that the inequality is true for some T ≥ 0, then Notice that, for any recurrent state s for policy π:

(P -P ′ ) T t=0 P t r (s) ≤ ∥p(•|s) -p ′ (•|s)∥ 1 • span (J(T )) ≤ r max D π ∥p(•|s) -p ′ (•|s)∥ 1 by Lemma E.1 = b(s).
In the same manner we show that:

T t=0 P t r ≥ T t=0 P ′t (r -b).
Hence, as P ′ has non-negative coefficients, denoting by e the unit vector:

T t=0 P t r - T t=0 P ′t r ∞ ≤ ∥b∥ ∞ T t=0 P ′t • e ∞ = ∥b∥ ∞ (T + 1).
As r = r ′ , with a multiplication by 1 T +1 and by taking the Cesáro limit :

|g -g ′ | ≤ ∥b∥ ∞ ,
where ∥b∥ ∞ = r max D π ∥P -P ′ ∥ ∞ .

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

A = A S b c d ; then A S , of size S × S is invertible and ∥A -1 S ∥ ∞ = sup i∈S E τ i→S
, where E τ i→S is the expected time to reach state S from state i.

Remark that this lemma is true for any state in S.

Proof. (E τ i→S ) i is the unique vector solution to the system:

v(S) = 0 ∀i ̸ = S, v(i) = 1 + j∈S P (i, j)v(j)
We can rewrite this system of equations as: Ãv = ee S , where à is the matrix à := A S b 0 1 , e the unit vector and e S the vector with value 1 for the last state and 0 otherwise. Then A and A S are invertible and we write:

Ã-1 = A -1 S -A -1 S b 0 1 .
Thus, by computing Ã-1 (ee S ), for i ̸ = S, (E τ i→S ) i = A -1 S 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 -1 S ∥ ∞ = sup i∈S E τ i→S . In the following lemma, we use the same notations as in Lemma E.2 with a common state space {0, 1, . . . S}. Lemma E.4. Let the biases h, h ′ be the biases of the two MDPs that verify their respective Bellman equations with the renormalization choice h(S) = h ′ (S) = 0, and respective policies π, and π ′ . Let sup s∈S E τ π s→s ′ be the worst expected hitting time to reach the state s ′ with policy π, and call T hit := inf s ′ ∈S sup s∈S E τ π s→s ′ . We have the following control of the difference:

∥h -h ′ ∥ ∞ ≤ 2T π hit D π ′ r max ∥P -P ′ ∥ ∞ .
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 ′ ).

Proof. The computations in this proof follow the same idea as in the proof of [START_REF] Ipsen | Uniform stability of markov chains[END_REF]Theorem 4.2]. The biases verify the following Bellman equations rge = (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 Ãh = rg, with r and 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 = Ã-1 (rg), and with identical computations, h ′ = Ã′ -1 ( r′ -g′ ). By denoting dX := X -X ′ for any vector or matrix X, we get, as r = r ′ : dh = -Ã-1 (-dg + d Ãh ′ ).

The previously defined block decompositions are:

Ã-1 = A -1 S -A -1 S b 0 1 and d à = A S -A ′ S b -b ′ 0 0 .
For s < S, dh(s) = -e T s A -1 S (dA S h ′dg) and dh(S) = 0. Now by taking the norm and using E.1:

∥dh∥ ∞ ≤ ∥A -1 S ∥ ∞ (r max D π ′ ∥dA S ∥ ∞ + |dg|). Notice that ∥dA S ∥ ∞ ≤ ∥dP ∥ ∞ and |dg| = |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 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 [START_REF] Anselmi | Reinforcement Learning in a Birth and Death Process: Breaking the Dependence on the State Space[END_REF].

F.1 Properties of the policies in the aggregate 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 aggregate MDP is stable (as seen in Section 2), so that there exists a i 0 large enough for which i ≥ i 0 , µ(i) ≥ µ(i 0 ) > λ.

With the following lemma, we compute the stationary measures ν π and give a comparison between any ν π with the stationary measure ν π max of the maximal policy π max , that admits every job into the queue, by relating these Markov chains to the M/M/1/S queue with rates λ and µ(i 0 ). Lemma F.1. Denote by s the last recurrent state of the MDP for policy π, so that π(s) = 0 for s ≥ s. Define the constant C 1 := i0-1 i=1 µ(i0) µ(i) ≥ 1, independent of S. We have the following inequalities • On the stationary measure of the maximal policy:

ν π max (0) -1 := S s ′ =0 s ′ i=1 λ µ(i) ≤ C 1 1 -λ µ(i0) ,
• On the stationary measure of any policy:

ν π (0) -1 := s s ′ =0 s ′ i=1 λ µ(i) ≤ ν π max (0) -1 ≤ C 1 1 -λ µ(i0) ,
• Also we can compute for s ≤ S: ν π max (s) := ν π max (0)

s i=1 λ µ(i) = ν π max (0)C 1 λ µ(i 0 ) s .
We now remind a definition of the bias for any policy π 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 π be a policy, P the transition matrix and ν π the stationary measure of the Markov chain under policy π. The bias h π of this policy is defined as:

h π (s) = ∞ t=1 (P t (s, •) -ν π )r.
(F26)

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 π be any policy, (X t ) t be the Markov chain with policy π and transitions P starting from any state s. Denote by τ s the random time needed for X t to hit 0. Then:

Eτ s ≤ ν π (0) -1 s i=1 U µ(i)
Proof. We write the expected hitting time equations, and use induction. Let τ i be the hitting time to 0 starting from state i, and e be the unit vector. We have the system:

Eτ = e + P Eτ , (F27) with the extra equation τ 0 = 0. The system gives for s ≥ s:

Eτ s = 1 + Eτ s 1 -µ(s) U + Eτ s-1 µ(s) U ,
so that:

Eτ s = U µ(s) + Eτ s-1
Then, by induction, we want to prove the equation for s < s:

Eτ s = Eτ s-1 + U µ(s) s s ′ =s s ′ i=s+1 λ µ(i) (F28)
For s < s, assume (F28) is true for Eτ s+1 : Using the monotonicity of the rates µ from Lemma 3.1, we therefore have :

Eτ s = 1 + Eτ s+1 λ U + Eτ s 1 -µ(s) -λ U + Eτ s-1 µ(s) U = 1 + Eτ s 1 -µ(s) -λ U + Eτ s-1 µ(s) U + Eτ s λ U + s s ′ =s+1 s ′ i=s+1 λ µ(i) = U µ(s) + Eτ s-1 + U µ(s)
∆(s) ≤ 2(λγ reject + γ hold )ν π max (0) -1 s 1 µ(1)

Figure 1 :

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

Figure 2 :

 2 Figure 2: Illustration of Norton Equivalence theorem.

  a). To define the confidence region M k , first define r(m) k and p(m) k the empirical reward and transition estimates in module m:

4 5 Compute 6 Find

 56 Compute for all (s, a) the modules m k (s, a) according to[START_REF] Vlassis | On the computational complexity of stochastic controller optimization in pomdps[END_REF]; the confidence region M k as in[START_REF] Anselmi | Reinforcement Learning in a Birth and Death Process: Breaking the Dependence on the State Space[END_REF]; a policy πk and an optimistic MDP Mk ∈ M k with "Extended Value Iteration" such that g( Mk , πk ) ≥ max

Figure 4 :

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

Figure 6 :

 6 Figure 6: Comparison between the average threshold and its Cesarò sum.

Figure 7 :

 7 Figure 7: Rescaled regret of the UCRL-M algorithm on the queueing network for different values of τ mix .

indicator functions 1 M

 1 ∈M k . For each episode k and module m, let us define • R (m) in,k := s R (m) k , • πk the optimistic policy, • Pk := (p k (s ′ |s, πk (s))) the transition matrix of policy πk on the optimistic MDP Mk , • v (m) k := (V k (s, πk ) the row vector of visit counts, • h k the bias vector of the Markov chain in the true MDP M with policy πk . Now, we split the regret term R (m) in into subterms that have different meaning. Assuming M ∈ M k and using Lemma B.1 on the accuracy of EVI, we get:

R.

  Summing over the modules m, we get:R trans ≤ 4 2 log (2AT ) s,a ∆(s + 1)V k (s, a) max{1, N (m k (s,a))

P 1 t=0P t r -P ′ T - 1 t=0P 1 t=0P t r - T - 1 t=0P

 1111 ′t (r + b) = -b + P T -′t (r + b) = -b + P ′ T -′t (r + b) + (P -P ′ ) T t=0 P t r ≤ -b + (P -P ′ ) T t=0 P t r by induction hypothesis.

  therefore true, and we have: Eτ s ≤ Eτ s-1 + U µ(s) ν π (0) -1 . Proposition F.4. For any policy π, define for s ∈ {1, . . . , S} the variation of the bias∆ π (s) := h π (s)h π (s -1) = ∞ t=1 P t (s, •) -P t (s -1, •) r.Remind that δ max := max s,a,a ′ |r(s, a)r(s -1, a ′ )| = λγreject+γ hold U : ∆ π (s) ≤ ∆(s) := 2δ max ν π max (0)

  • The transition matrix P o is simply constructed by using the routing matrix L, the arrival rate λ and the service rates (µ o i ) i . • The mean rewards r o are constructed from the cost function.

		The immediate cost
	for each state-action pair (x, a), is Bernoulli distributed. It is decomposed into:
	-a deterministic part, 1 U (γ hold time unit),	N i=1 x i ) (each present job incurs a cost γ hold per
	-and a stochastic part, γ reject (1 -a)1 job-arrival (if a job arrives and the action is reject).

  Proposition 1. The time complexity of UCRL-M is O(KSτ mix + Kt evi + T ), where K is the number of episodes and t evi the time complexity of extended value iteration. Furthermore, E(K) = O(log T ).Proof. The time complexity of lines 5 and 6 is O(KSτ mix ). The complexity of line 7 is O(Kt evi ). The complexity of line 8 is O(Kτ mix ). The complexity of line 9 is O(T -Kτ mix

	5.5 Time complexity of UCRL-M
	11 end

7

Ramping phase (Φ): Iterate the MDP with policy πk for τ mix time-steps, discard the observations and set t := t + τ mix . 8 Exploration: while criterion (18) is true do 1. Use policy πk ; // choose action a t = πk (s t ) and observe state s t+1 ; 2. Set t := t + 1; 9 end 10 k := k + 1;

  Regret of the UCRL-M algorithm on the queueing network for different values of n and scaling parameters.

		×10 6
		2.0	Regret with 3 queues per tier Regret with 6 queues per tier							Parameter Value
			Regret with 12 queues per tier Regret with 24 queues per tier						S	10 3 n
		1.5												λ	0.99
	Regret	1.0												µ γ reject	1 n 10
														γ hold	4 3n
		0.5												U	λ + 3nµ
														p	0.2
		0.0												τ mix	3
		0.00		0.25	0.50	0.75	1.00	1.25	1.50		1.75	2.00
							Time-steps					×10 7
	0.25 Figure 5: 0.00 0 10 20 30 40 50 70 80 Threshold 60	0.50	0.75	1.00	1.25 Policy with 3 queues per tier 1.50 1.75 2.00 Policy with 6 queues per tier Policy with 12 queues per tier Policy with 24 queues per tier Optimal thresholds	Threshold	0 10 20 30 40 50 70 80 60	0.00	0.25	0.50	0.75	1.00	1.25 Policy with 3 queues per tier 1.50 1.75 2.00 Policy with 6 queues per tier Policy with 12 queues per tier Policy with 24 queues per tier Optimal thresholds
					Time-steps			×10 7					Time-steps	×10 7
			(a) Average threshold over time.		(b) Cesarò sum of the average threshold.

  a) we had from Equation (13), we get:

	E	s,a k	√ τ mix V k (s, a) max{1, N t k (s, a)}	≤ 3E	s,a		τ mix N T (s, a)
				≤ 3	s	τ mix E [N T (s)] A,	by Jensen's inequality.
	Therefore:					S
			R trans ≤ 12 2Aτ mix log (2AT )	s=0

The Õ notation is a variant of big-O that ignores logarithmic factors.

Appendix A Proof of Theorem 6.1

The proof of Theorem 6.1 is quite cumbersome and is decompsed into many lemmas. The scheme in Figure A1 gives an overall picture of the interactions between them. Th. [START_REF] Fruit | Efficient bias-span-constrained exploration-exploitation in reinforcement learning[END_REF]

A.1 Terms for the ramping phases

We first briefly deal with the terms coming from the ramping phases Φ of the episodes, R ramp . We have:

r(s t , πk (s, t)) ≤ Kτ mix r max ≤ r max SAτ 2 mix log 2 8T SAτ mix , (A1) where in the last inequality we used Lemma C.2. Assuming τ mix SA ≥ 4, and using log(2) ≥ 1 2 , we rewrite it:

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 M k . For each episode k, we define:

(s) the number of visits to state s during episode k in module m. • N (m) t (s) is the number of visits to state s until time-step t excluded, in module m.

A.8 Total sum

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

and now it remains to compute the lower order term of the regret R LO . Using (A2), (A3), (A14) and (A15), the lower order term of the regret is upper bounded by, omitting the r max factor:

and for T large enough so that 1 + 16C ≤ log 2 (T ) the upper bound is :

which concludes the proof of Theorem 6.1.

Appendix B Lemmas on Extended Value Iteration

We remind the fundamental properties of the Extended Value Iteration (EVI) algorithm, first described in [START_REF] Jaksch | Near-optimal regret bounds for reinforcement learning[END_REF], which is used to find the optimistic MDP Mk and the policy πk for each episode k given a confidence region 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:

where P(s, a) is the set of probabilities from [START_REF] Anselmi | Reinforcement Learning in a Birth and Death Process: Breaking the Dependence on the State Space[END_REF], and the iterations are stopped with respect to the following lemma [START_REF] Jaksch | Near-optimal regret bounds for reinforcement learning[END_REF]Theorem 7]. Lemma B.1. For episode k and accuracy

, denote by i the last step of extended value iteration, stopped when:

The optimistic MDP Mk and the optimistic policy πk at the last step of EVI are so that the gain is ε kclose to the optimal gain:

Moreover, from [START_REF] Puterman | Markov Decision Processes: Discrete Stochastic Dynamic Programming[END_REF]Theorem 8.5.6]:

and as the optimal policy yields an aperiodic unichain Markov chain, we have that gk = g( Mk , πk , s) for any s, so that we can define the bias:

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:

so that we can define the following difference

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

We introduce classic lemmas from [START_REF] Jaksch | Near-optimal regret bounds for reinforcement learning[END_REF] that are needed for the regret computations. The first lemma, proven in [START_REF] Jaksch | Near-optimal regret bounds for reinforcement learning[END_REF]Appendix C.3], is used to simplify the main regret terms (A7) and (A8). Lemma C.1. For any fixed state action pair (s, a), and time T , we have:

The next lemma, proven in [5, Appendix C.2] is useful to bound the term from in A.1 and in equation (A14). Lemma C.2. Denote by K t the number of episodes up to time t, and let t > SAτ mix . It is bounded by:

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 , . . . be a martingale difference sequence with |X i | ≤ RD for all i and some R > 0. Then, for all ε > 0 and n ∈ N:

.

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 / ∈ M k . Let us first prove the key Lemma D.1. Lemma D.1. Let us consider the original MDP under any policy π, with stationary measure ν π . There exists C > 0, ρ ∈ (0, 1) such that:

Proof. The proof is essentially the same as in [37, 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 τ mix samples of the aggregate 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 ′ and t ′τ mix belong to the same episodes and can therefore be related to the same stationary distribution. Let t, t ′ > 0 such that t ′τ mix ≥ t, with t ′ and t ′τ 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 ′ . Let Ŷ be a random variable following the same distribution as Y and independent of X. Note that there are at least τ mix observed or hidden transitions between t and t ′ on the original MDP.

We also define the distribution P := P {X ∈ •, Y ∈ •} and the distribution Q := P {X ∈ •} ⊗ P {Y ∈ •}, and we define the total variation information

. By definition of the total variation distance, we first have that:

Then, using the properties of the total variation information related to a Markov chain described in [START_REF] Bhandari | A finite time analysis of temporal difference learning with linear function approximation[END_REF], we obtain

Define p⊥ (•|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:

Similarly, define A ⊥,k n events such that the first nk observations are the same as the ones for A n and the next k observations are independent, so that for example

Then, applying n -1 times Lemma D.1:

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:

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

By definition of r(m) (s, a) = γ reject p(m) (s + 1|s, a) + γ hold U (Ss) 15, and using that γ reject ≤ δ max , we can write:

Once again, we consider p⊥ (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 . With the independence, we may now use the following Hoeffding inequality on the Bernoulli random variable of parameter p(s + 1|s, a):

where ε r = 1 2n log (16At 4 ) ≤ 2 n log (2At). We therefore get:

and with the previous choice of τ mix ,

Overall:

Now, with a union bound for all values of

and all τ mix possible modules, and also summing over all state-action pairs:

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 [START_REF] Anselmi | Reinforcement Learning in a Birth and Death Process: Breaking the Dependence on the State Space[END_REF], 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 πk in the optimistic MDP and in the true MDP. Lemma E.1. For an MDP with rewards r ∈ [0, r max ] and transition matrix P , denote by J s (π, T ) := E T t=0 r(s t , π(s t )) the expected cumulative rewards until time T starting from state s, under policy π. Let D π be the diameter under policy π. The following inequality holds: span (J(π, T )) ≤ r max D π .

Lemma E.5. Let ν π max be the stationary measure of the Markov chain under policy π max , such that for every state s: π 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

and C 1 as in Lemma F.1. Then, with probability at least 1 -1 4T :

We will now prove Lemma E.5:

Proof. Let k be an episode such that I k ≥ I(T ), and first consider it is of fixed length I. Let x k ∈ S be a recurrent state, a k = πk (s k ). Denote by ν k the stationary distribution under policy πk . Notice that ν π max (S) ≤ ν k (x k ) for S large enough.

Define a new Markov reward process: consider again the original state space S ′ and the transitions p ′ with policy πk , but the rewards r, where r(s ′ ) = 1 for states s ′ such that |s ′ | = x k and 0 otherwise. Denote by gπ k the gain associated to the policy πk and similarly define hπ k the bias, translated so that hπ k (S) = 0. Then:

By Azuma-Hoeffding inequality C.3, following the same proof as in section 4.3.2 of [START_REF] Jaksch | Near-optimal regret bounds for reinforcement learning[END_REF], notice that

, hπ k form a martingale difference sequence with the bound |X u | ≤ span hπ k :

With Proposition F.4 proved in Appendix F, we have span

µ(1)(1-λ/µ(i0)) , so that with probability at least 1 -1 I 2 :

On the other hand:

so that, using that ν k (x k ) ≥ ν π max (S), with probability at least 1 -1 I 5 :

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

, so that we now have that with probability at least 1 -1 4T :

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 -1 4T :

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

Appendix F Properties of the aggregate MDP

In this section, we prove properties on the aggregate 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.

Proof. We will use an optimal coupling, that is, a coupling such that the following infimum is reached, as defined in [START_REF] Levin | Markov Chains and Mixing Times[END_REF]. P t (s, •)-P t (s-1, •) TV = inf{P(X t ̸ = Y t ) : (X t , Y t ) couples P t (s, •) and P t (s-1, •)}.

(F29) 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 ≥ 2, let U t ∼ U([0, 1]) be a sequence of independent random variables sampled uniformly on [0, 1]. We have:

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

(P t (s, •) -P t (s -1, •))r ≤ 2P(X t ̸ = Y t )δ max .

We remind that τ s is the random time needed for the Markov chain X t to hit 0. The coupling time is lower than τ s :

P(X t ̸ = Y t ) ≤ P (τ s→0 > t) , so that summing over t gives:

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

.