Bayesian Learning of Optimal Policies in Markov Decision Processes with Countably Infinite State-Space
Authors: Saghar Adler
Vijay Subramanian
Venue: NeurIPS 2023 poster (2023)
Keywords: Thompson Sampling
Reinforcement Learning
Queueing theory

Abstract: Models of many real-life applications, such as queueing models of communication networks or computing systems, have a countably infinite state-space. Algorithmic and learning procedures that have been developed to produce optimal policies mainly focus on finite state settings, and do not directly apply to these models. To overcome this lacuna, in this work we study the problem of optimal control of a family of discrete-time countable state-space Markov Decision Processes (MDPs) governed by an unknown parameter $\theta\in\Theta$, 
 and defined on a countably-infinite state-space $\mathcal X=\mathbb{Z}_+^d$, with finite action space $\mathcal A$, and an unbounded cost function. We take a Bayesian perspective with the random unknown parameter $\boldsymbol{\theta}^*$ generated via a given fixed prior distribution on $\Theta$. To optimally control the unknown MDP, we propose an algorithm based on Thompson sampling with dynamically-sized episodes: at the beginning of each episode, the posterior distribution formed via Bayes' rule is used to produce a parameter estimate, which then decides the policy applied during the episode. To ensure the stability of the Markov chain obtained by following the policy chosen for each parameter, we impose ergodicity assumptions. From this condition and using the solution of the average cost Bellman equation, we establish an $\tilde O(dh^d\sqrt{|\mathcal A|T})$ upper bound on the Bayesian regret of our algorithm, where $T$ is the time-horizon. Finally, to elucidate the applicability of our algorithm, we consider two different queueing models with unknown dynamics, and show that our algorithm can be applied to develop approximately optimal control algorithms.

Bayesian Learning of Optimal Policies in Markov Decision Processes with Countably Infinite State-Space
Saghar Adler University of Michigan
Vijay Subramanian
University of Michigan
Abstract
Models of many real-life applications, such as queueing models of communication networks or computing systems, have countably infinite state-space. Algorithmic and learning procedures that have been developed to produce optimal policies mainly focus on finite state settings, and do not directly apply to these models. To overcome this lacuna, in this work we study the problem of optimal control of a family of discrete-ting -ime countable state-space Markov Decision Processes (MDPs) governed by an unknown parameter 0 E θ, and defined on a countably-infinin state-space X' = Z with finite action space A, and an unbounded cost function. We take Bayesian perspective with the random unknown parameter 0* generated via given fixed prior distribution on + To optimally control the unknown MDP, propose algorithm based Thompson sampling with dynamically-sine episodes: at the beginning of each episode, the posterior distribution formed via Bayes' rule is used to produce a parameter estimate, which then decides the policy applied during the episode. To ensure the stability of the Markov chain obtained by impose ergodicity assumptions.
following the policy chosen for each parameter, From this condition and using the solution of the average cost Bellman equation, we establish an (dd VIA(T) upper bound on the Bayesian regret of our algorithm, where I the time-horizon. Finally, elucidate the applicability of our algorithm, we consider two different qucueing models with unknown dynamics, and show that our algorithm can be applied to develop approximately optimal control algorithms.
Introduction
Many real-life applications, such as communication networks, supply chains, and computing systems, are modeled using queueing models with countably infinite state-space. In the existing analysis of these systems, the models are assumed to be known, but despite this, developing optimal control schemes hard, with only a few examples worked out [35] [4]. However, knowing the model, algorithmic procedures exist to produce approximately optimal policies (35) (such as value iteration and linear programming). Given the success of data-driven optimal control design, particular Reinforcement Learning (RL), explore the of such methods for the countable state-space controlled Markov processes. However, current RL methods that focus on finite-state settings do not apply to the mentioned queueing models. With the model unknown, a meta-learning scheme that RI-based but obtains good performance by utilizing algorithms developed when models known. Specifically, we study the problem of optimal control of family of discrete-ting countable state-space MDPs governed by an unknown parameter 0 from a general space θ with each MDP evolving on the countable state-space X' _ and finite action space AA. The cost function is unbounded and polynomially dependent on the state, following the examples of minimizing waiting times in queueing systems. Taking Bayesian view, we assume the model is governed by an unknown parameter 0* E ④ generated from a fixed and known prior distribution. We aim learn a policy that minimizes the optimal policies II with low Bayesian regret with respect to the perrameter-depedeene optimal policy in II.
goal is to develop
average cost over given class of
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

To avoid many technical difficulties in countably infinite state-space settings, it is crucial to establish certain assumptions regarding the class of models from which the unknown system is drawn; some examples are: i) the number of deterministic stationary policies is not finite; and ii) in average cost optimal control problems, without stability/ergodiiity assumptions, an optimal policy may not exist [4], and when it exists, it may not be stationary or deterministic [20]. With these in mind, we assume that for any state-action pair, the transition kernels in the model class are categorical and skip-free to the right, i.e., with finite support with a bound depending on the state only in an additive manner; both are common features of queueing models where an increase in state is due to arrivals. A second set of assumptions ensure stability by assuming that the Markov chains obtained by using different policies in II are geometrically ergodic with uniformity across θ From these assumptions, moments on hitting times are derived in terms of Lyapunov functions for polynomial ergodicity. These assumptions also yield a solution to the average cost optimality equation (ACOE) (9]
Contributions:
To optimally control the unknown MDP, we propose an algorithm based on Thomp- son sampling with dynamically-sized episodes; posterior sampling used based on its broad applica- bility and computational efficiency 46 47]. At the beginning of each episode, posterior distribution is formed using Bayes' rule, and an estimate is realized from this distribution which then decides the policy used throughout the episode. To evaluate the performance of our proposed algorithm, we use the metric of Bayesian regret, which compares the expected total cost achieved by a learning policy TT until time horizon T with the policy achieving the optimal infinite-horizon average cost in the policy class II. We consider regret guarantees in three different settings as follows:
1. In Theorem [1 for II being the set of all policies and assuming that we have oracle access to the optimal policy for each parameter, we establish an Öddh V ( upper bound on the Bayesian regret of this algorithm compared to the optimal policy.
2. In Corollary []] where class II is subset of all stationary policies and where we know the best policy within this subset for each parameter via oracle, we prove an Ö(dh% ((dhVV(AlTT upper bound on the Bayesian regret of our proposed algorithm, relative to the best-in-class policy.
In Theorem 2 we explore a scenario where we have access an approximately optimal policy, rather than the optimal policy in set 1I (which are all assumed to be stationary policies). When the
approximately optimal policies satisfy Assumptions 3 4
we prove an Ódhh VIA(T) regret bound,
((dT"VIAITT
relative to the optimal policy in set II.
Finally, to provide examples of our framework for developing approximately optimal control algo- rithms for stochastic systems with unknown dynamics, we study two different queueing models that meet our technical conditions. The first example is a continuous-time queueing system with two heterogeneous servers with unknown service rates and common infinite buffer with the decision being the use of the slower server. Here, the optimal policy that minimizes the average waiting time is a threshold policy (38] which yields queue-length after which the slower server is always used. The second model is a two-server queueing system, each with separate infinite buffers, to one of which a dispatcher routes an incoming arrival. Here, the optimal policy minimizing the waiting time is a switching-cury (26) with the specifics unknown for general parameter values, so we find the best policy within a commonly used set of switching-curve policies MMx-Weight policies [58 assign the arrival to the queue with minimum weighted queue-length For both models, we verify our assumptions for the class of optimal/best-in-clan policies corresponding to different service rates and conclude that our proposed algorithm can be used to learn the optimal/best-in-clas policy.
59 ) and
Thompson sampling (62). or posterior sampling, has been applied to RL in many contexts of unknown MDPs [55 45) and partially observed MDPs 288; see tutorials 22 50 for a
Related Work:
comprehensive survey. It has been used in the parametric learning context 66 minimize either [ 60 61] or frequentist (3)
23 regret. The bulk of the literature, including 23 analyzes state and finite-action models but with different parameterizations such that a general dependence of the models on the parameters is allowed. The work in [6]] studies general state-space MDPs but with scalar parameterization with a Lipschitz dependence of the underlying models. Our problem formulation specifically considers countable state- saate-space models with the models related via ergodicity, which we believe is a natural choice. Our focus on parametric learning is also connected to older work in adaptive control [ 24 which studies asymptotically optimal learning for general parameter settings but with either a finite or countably infinite number of policies. Learning-based asymptotically optimal control in queues has long history (36] 35) but recently there is increased work that also characterizes finite-time regret performance with respect to well-known good policy the optimal policy; see (63] for a survey. A series of work has studied
Bayesian 46 47 49
2

---

learning with Max- Weight policies to get stability and linear regret A4 30 or just stability [65| A recent related work [8] considers learning optimal paramterized policies in queueing networks when the MDP is known. In a finite countable state-space setting of specific queueing models where the parameters can be estimated, many works _ 17 53
16] have used forced exploration type schemes to obtain either regret that is constant or scaling logarithmically in the time-horizon.
32 31
Another line of work studies the problem of learning the optimal policy in an undiscounted finite- horizon MDP with a bounded reward function. Reference [66] uses a Thompson sampling-ber baased based
learning algorithm with linear value function approximation to study an MDP with a bounded reward function in finite-horizon setting. Reference [5] considers an episodic mrite-horizon MDP with known bounded rewards but unknown transition kernlls modeled using linearly parameterized exponential families. A maximum likelihood (ML) based algorithm coupled with exploration done by constructing high probability confidence sets around the MI. estimate used to learn the unknown parameters. In another work, [48] extends the problem setting of [15] to episodic finite-horizon MDP with unknown rewards and transitions modeled using parametric bilinear exponential families. To learn the unknown parameters, they use a ML based algorithm with exploration done with explicit perturbation. We note that all mentioned works consider a finite-horizon problem. In contrast, our work considers an average cost problem, performance guarantees. In addition, these works focus on an MDP with a bounded reward function. Our focus, however, is learning in MDPs with unbounded rewards with the goal of covering practical queueing examples. We note that the parameterization of transitions used in [48] [55] can be used necessary within our framework. However, similar to work, additional stability assumptions to guarantee asymptotic learning and sub-linear regret. Another issue with exponential transition families is that they do not allow for 0 entries, which limits their applicability in queueing models.
mnfinit-hhorizon setting, and provides finite-time
In another work, [51] studies discounted MDPs with unknown dynamics, and unbounded state-space, but with bounded rewards, and learns online policy that satisfies specific notion of stability. It is also assumed that a Lyapunov function ensuring stability for the optimal policy exists. We note that [5T] ignores optimality and focuses on finding a stable policy, which contrasts with our work that evaluates performance relative to the optimal policy. Secondly, [51] considers a discounted reward problem, essentially finite-time horizon problem. Average cost problems, such as ours, are infinite- time horizon problems, so connections to discounted problems can only be made in the limit of the discount parameter going to 1. Moreover, (51) considers a bounded reward function, simplifying their analysis but not practical for many queueing examples. Further, the assumption of a stable optimal policy with Lyapunov function (as in (51) is highly restrictive for bounded reward settings with discounting. Additionally, average cost problems with bounded costs need strong state-independent recurrence conditions for the existence of (stationary) optimal solutions, which many queueing examples don't it satisfy; see 112.. Further complications can also arise with bounded costs: e.g., 20 shows that stationary average cost optimal policy may not exist.
2 Problem formulation
We consider a family of discrete-time Markov Decision Processes (MDPs) governed by parameter 0 θ with the MDP for parameter 0 described by (X, A, c, P'a). For exposition purposes, we assume that all the MDPs are on (a common) countably infinite state-space X z We denote the finite action space by A, the transition kernel by Pg : X x A - A(X). and the cost function by e: X x A + R4. As mentioned earlier, we will take Bayesian view of the problem and assume that the model is generated using an unknown parameter 0 E O which is generated from a given fixed prior distribution v((-) on O Our goal is to find policy æ X' + A that tries achieve Bayesian optimal performance in policy class IT, i.e., minimizes the expected regret with 0" chosen from the prior distribution v(-). For each value 0 O the minimum infinite-horizon average cost is defined as
1 T
J(0) inf lim sup well T-
E ol (X))).(()))
(1)
Xa(()) E X and A()) E A are the state and action at / E N. Typically, we set this class to be all (causal) policies, but is also possible to consider to be a proper subset of all policies as we will explore in our results. For learning policy TT that aims to select the optimal control without model knowledge but with
where we optimize over a given class of policies II and X()
3

---

knowledge of F and the prior v, the Bayesian regret until time horizon T 2 2 is defined as
T
R(T, TL)= E
Σ (1), - ]] [=1
where the expectation is taken over 0 and the dynamics induced by æ.. Owing underlying challenges in countable state-space MDPs, we require the below assumptions on the cost function.
Assumption 1. The cost function e: X - R+ is assumed to satisfy the following two conditions:
1. For every number 2 2 0 and action a E A. c(x,a) 2 z outside a finite subset of X.
2. The cost function is upper-bounded by multivariate polynomial fc Z4 + R+ which is
increasing in every component on a: E 24 and has maximum degree of (2 1) in any dimension. We can assume that fc(z) = K E for some K >> 0, where x = (z1,..., zz)-
Thus, the cost function increases without bound (in the state) at polynomial rate. This assumption is common in practice-holding costs in queueing models are polynomial in the state components. To avoid technical issues the infinite state-space setting also necessitates some assumptions on the class from which the unknown model is drawn. For instance, irreducibility of Markov chains on such state-spaces does not ensure positive recurrence (and ergodicity). Morcover, for average cost optimal control problems, without stability even the existence of an optimal policy is not guaranteed, and we need more conditions. The following assumption ensures skip-free behaviour for transitions, which holds in many queueing models, where an increase in state corresponds to (new) arrivals.
Assumption 2. From any state-action pair (xz, a), the transition is finite number of states. We also assume that all transition kernels are skip-free to the right: for some h 2 1 which is independent of E O and (x,a) a) E X x A, we have Po(x* xx,a) = for all x' E { 24 ||||| > ||0||| + h}.
Learning necessitates some commonalities within the class of models so that using a policy well-suited to one model provides information on other models too. For us, these are in the form of constraints on the transition kernels of the models and stability assumptions. As simple union bound arguments don't work in the countably infinite state-space setting, will use the stability assumptions instead. In our setting, we consider a class of models, each with policy being well-suited to at least one model in the class, and use the set of policies search within. Using a reduced set of policies is necessary as the number of deterministic stationary policies is infinite. To learn correctly while restricting attention to this subset policy class, requires some regularity assumptions when a policy well-suited to one model is tried on different model. Our ergodicity assumptions are one convenient choice: see Appendix A.. for details. These assumptions let characterize the distributions of the first passage times of the Markov processes via stability conditions; see Lemmas 10 and 11
Assumption 3. For any MDP (X,A, c, Pa) with parameter 0 E O, there exists a unique optimal policy vi that minimizes the infinite-horizor average cost within the class of policies I.. Further- more, for any 01, O2 E O the Markov process with transition kernel p obtained from the MDP (X,A, Po.) by following policy Tēz is irreducible, aperiodic, and geometrically ergodic with geometric ergodicity coefficient 28,00 E (0, 1) and stationary distribution pe,.0.- This is equivalent to the existence of finite set C2 and Lyapunov function VoL,e 02 XX [1, +00) satisfying
01.02
AV 00,00, (xr) S -(1 10,-0,,00 ,0,
00 (x) < +oc, x E C2 Va 01.0g (x)), x E Co and "0 V2
Pø The V Vol (x)
where AVG,
8,,00 01 (x) = Pe V V2 (x) Vol (z)). Setting bg b = max 02
V 0, (2) yields
o - ( (L. + (b "c, (x), x X.
(3)
Then, we have the following assumptions relating all the models in O:
1. The geometric ergodicity coefficient is uniformly bounded below 1: 7 == o0ce in 1.
2. We assume that {04) C C% 0g.02 and C = Upg,9, 0, is finite set. We further assume that b% == supa, 82 6g,02 P2 +00.

---

The uniqueness of the optimal policy is not essential for the validity of our results, provided that all optimal policies satisfy our assumptions. When this condition is not met, we need to select an optimal policy that is geometrically ergodic for all 0 E A. This issue can be avoided by using a smaller subset of policies for which ergodicity can be shown, such as Max- Weight policies.
Remark 1.
Geometric ergodicity implies that all moments of the hitting time of state 0", say Tos from any initial state + 0 are finite as E E [xTTd]] S ci (ax)) (for specific K > and e1), and so, E. [rxc S e1 V (z)) /kl log (it) < +oo for all & E N; see Appendix A.2 Function V is typically exponential in some norm of the state and yields exponential bound for moments of hitting times, and a poor regret bound. To improve the regret bound, we need a different drift equation with function VP with polynomial dependence
norm of the state that bounds certain polynomial moments of Tgx.
Assumption 4. Given 01, 82 E O, Markov process obtained from MDP (X, A, c, Po.) ) by following policy _ē_ is polynomially ergodic through the Foster- Laster-Lyapuno criteria: there exists a finite set C2 C2,09
constants P0,00 .22 Vg _,0 > 0, 000002
&I 1), and function Vi,0, X -> [1, +00) satisfying
AV 02 (a) S -8, 00 (V (z))
(x)) 02,00 02 + Ug JC,,, (a), x E.
Then, we have the following assumptions relating all the models in O:
1. VP, 01,02 is a polynomial with positive coefficients, maximum degree (in any dimension) r0,,03 and sum of coefficients 00,00² We assume r supp,,0 r' < 00 and s. = supe,,0, 00, 02 < co.
S
2. We assume that {0a) E T0..02EC 02 and C. U20 0, is finite set. We further assume that 3 == info, A2 S81,0g > and by := suupp 1/,000 < xc.
3. Let Ke,,0, (x) = 0 2 irreducibility. We assume that it is strictly positive in O: K, == infer,0 milgecr K8,,0 00 (x) >
2-=-2((pp) )"(; 0x), which is positive for any pair 01, 02 E + by
Assumptions 3 4 hold in many models of interest; see Appendix D As average cost optimality is our design criterion, we need ensure the existence of solutions to ACOE when II is the set of all policies, or Poisson equation when II is subset of all policies. We discuss these two cases separately. Case 1: II is the set of all policies. For any parameter A O, the MDP (X, A, c, Po) is said to satisfy the ACOE if there exists constant (() and a unique function u(:;0) X + R such that
J(0) + v( 0) = min {c(x, a) + Σ Polyla, Po(ylor,a)o 0)} with v00d; 0) = 0.
aEA
yEX
From 13 if the following conditions hold, ACOE has solution, Jo is the optimal -nfinit-hhorizon average cost, and there is an optimal stationary policy with ACOE becoming (5): (i) for every (a, a) and = > 0, cost function c(ar, a) z outside finite subset of X:: (ii) there is a stationary policy with an irreducible and aperiodic Markov process with finite average cost; and (iii) from every (ær, a) transition
finite number of states is possible. From Assumptions 3 the above conditions hold. Case 2: II is a proper subset of all policies. Here, we posit that for every E θ and its best in-class policy गद. there exists constant J()), the average cost of zī.. and function v(:: : X + E with
((0) + v( 0) = x. T3 (z)) + Σ Po ()())))(y))))
(5)
yEX
This holds by the solution of the Poisson equation with the appropriate forcing function. For a Markov process X the space X' with transition kernel P and cost function e(-), solution the Poisson equation [41 is a scalar J and function v(-): : X + R such that J + v = c+ Pv, where u(z) = 0 for some z E X. In our setting using [4] Sections 9.6-9.8], for model governed by 0 θ following
policy Tō. we show a solution to the Poisson equation exists and is given by v (0*) 0, and
J(0) C (0²) T [To=] and 50 (a:) C (a:) J(O) (Tor),
Vo E X,
(6)
where (~)) = E Σ Tox c( X (1), T (X (i))) and expectation is over trajectories of Markov
chain X with transition kernel p starting in state æ. Appendix A.3 we present related definitions and show that from Assumptions 3 4 the requirements for the existence and finiteness of the solutions
to Poisson equation are satisfied. Finally, we assume supsce J(O) is finite, which typically holds as result of the boundedness assumptions stated in Asumptions frr along with Assumption I
5

---

Algorithm 1 Thompson Sampling with Dynamically-sized Episodes (TSDE)
1: Input: Vo
2: Initialization: (1) = 0" t t+] -1
3: for episodes k: = 2, do
4: la 4-
5: Generate 02 ~ Ut2
6: while t S t + Th and N1 a) - 2N,,, (z, a) for all (a, a) E & do
7:
Apply action A(t) = _Ø. (X (t)
8:
N₂ (X (t) (t)) t Nr (X (t), +
9:
Observe new state X (t+1)
Update Vt+1 according to & t ++1
11:
12:
end while
13:
Th +- 1- bE
14:
while X (1) + 0 do
15:
Apply action A() T0 (X (1)) Observe state X (t 1) end while
16:
17:
18:
Th +- t to
19:
end for
Remark 2. In Assumption 4 we can use any other policy R0, such that the Markov process obtained from MDP (X,A, Po.) by following policy ne, irreducible and polynomially ergodic via the Foster-Lyapunov criteria with the uniformity discussed. Irreducibility is important as the policy will be used at times when the state is not known advance, specifically Steps 14-17 in Algorithm
Assumption 5. We assume that J supace J(0) < +00.
3 Thompson sampling based learning algorithm
We will use the learning algorithm Thompson sampling with dynamically-sized episodes from 49 learn the unknown parameter 0" θ and the corresponding policy, Tे.. but suitably modify it for our countable state-space setting. Consider the prior distribution vo defined on Ô from which 0* sampled. At each time N, the posterior distribution 242 updated according to Bayes' rule as
Po (X (t X (t) A (t)) (d00
(c0) Jwee Per (X (1+ X (1) A (1)) (d0'))
and the posterior estimate 0c+1, if generated, is from the posterior distribution 1/+1- The modified Thompson-same sampling with synamically-sizer episodes algorithm (TSDE) is presented in Algorithm The TSDE algorithm operates in episodes: at the beginning of episode k parameter 0₂ is sampled from the posterior distribution Vr, and during episode is, actions are generated from the stationary policy according to 2z. i.c., - Let tę be the time the k-th episode begins. Define fx+1 as the first time after tu that the conditions of Line 6 of Algorithm D triggered and f as the first time at after i441 where state o is visited; for the last episode started before or at T, we ensure that ty and ft are less than or equal + 1. Explicitly, 4 = and for k 1, 4 = min(/ (1 2 le X (1) = 0 or >> T}. fk+1 - tx be the length the k-th episode and set Tj = tx+1 - tę with the convention T. = 1. For any state-action pair (x) a), we define N2 a) = 0 and for > 1,
Let Tj
N1 a) = (tx S i < fx+1 S t for some 2 1: (X A(1) = (xr.a)}l-
Notice that for all state-action pairs (z, a) and fx+11 S 5 f,41, we have N.(x, Ni (æ, a).
We denote Ky as the number of episodes started by or time or Ky max t4 s T). The
length of episode k < Kr is not fixed and is determined according to two stopping criteria: (1)
t t> to + Tk-1, (2) Ne(x, a) > 2N, (x, a) for some state-action pair (x, a). After either criterion is met, the system will still follow policy Tī. until the first time at which state Od is visited: see Line 14
and Figure 1 We use this settling period to 0 because the system state can be arbitrary when the

---

1/4 updated
Dy not updated
X (1+)== = 0a start of episode
X (1++1) = 0
end of episode l
tk
fx+1
bx+1
Th
Figure 1: MDP evolution in episode i < KT.
first stopping criterion is met. As the countable state-space setting precludes a simple union-bound argument overcome this uncertainty (as in the literature for finite state settings), we let the system reach the special state 0 Another (essentially equivalent) option is to wait until the state hits the finite set C or C? and then use a union bound argument for all states in either set. For analytical convenience, we only use the state samples observed before arrival fx-1 to update the posterior distribution. The posterior update halted during the settling period 0 as we have no control on the states visited during it, despite it being finite in duration (by our assumptions).
4 Regret analysis of Algorithm 1
The performance of any learning policy TL is evaluated using the metric of expected regret compared the optimal expected average cost of true parameter 0", namely, /(0"). In this section, we evaluate the performance of Algorithm [ and derive an upper bound for R(T, TTSDE), its expected regret up time T. In Section we argued that at time in episode (tg t < f&++1), there exist a constant J(xx) and a unique function vl:; 0k)
): X + IR such that v (0"; 02) = 0 and
J(Ox) + v ((X((); c( (t), To. (X()))) + Σ Po. (t) To, (X(t)))u(): 0x), (8) DEX
in which n². is the optimal or best-in-class policy (depending on the context) according to parameter 0g and ((x) is the average cost for the Markov process obtained from MDP (X, c, Pa,) by following = We derive bound for the expected regret R(T, ÆTSDE) following the proof steps of
[49] while extending it to the countable state-space setting of our problem. Using (8) the regret is decomposed into three terms and each term is bounded separately:
Kr
M
R(T, (TSDE) = E
(((()), (X - -T (T)) = Ro + BS + R2,
(9)
k=1
Kr
with Ro E
J [0xx] TE)
(10)
Ky 14+1 1
R1 = E
-((()+ (x:(++):000)]]
(11)
k=1
Kr M
R₂ =
[v(X(1 1):0,) - Σ (x)) (X(1)))())))))) 0w)]]- (12)
NEX
Before bounding the above regret terms, we address the complexities arising from the countable state-space setting. Firstly, we need to study the maximum state (with respect to the -norm) visited up to time T' in the MDP AX c, Po-) following Algorithm I denote this maximum state by MT. In Appendix C derive upper bounds the moments of hitting times of state Odd and utilize this to bound the moments of random variable M2. which then lets us study the number of episodes Ky by time T. Another challenge in analyzing the regret is that the relative value function v(:; f) is unlikely to be bounded in the countable for the relative value function in terms of hitting time Ty= from the initial state æ. Based on these results, provide an upper bound for the regret of Algorithm in Theorem
space setting. Hence, in 13) and (14), find bounds
Maximum state norm under polynomial and geometric ergodicity. Here we state the results that characterize the maximum log norm of the state vector achieved up until and including time T, and
7

---

the resulting bounds on the number of episodes executed until time T. Owing to space constraints the details (including formal statements) are presented in Appendix [B] The results are listed as below: (i) In 6 we bound the moments of the maximum length of recurrence times of state 09, using the ergodicity assumptions 4 This, along with the skip-free property, allows us to prove that the p-th moment of maxi oo and Mg- are both of order O(log" T).
(ii) In Lemma we find an upper bound for the number of episodes in which the second stopping criterion is met or there exists a state-action pair for which (2, a) has increased more than twice. (iii) In Lemma g we bound the total number of episodes Kr by time T by bounding the number of episodes triggered by the first stopping criterion, using the fact that in such episodes, Tx = -Tk-1 1 Moreover, to account for the settling time of each episode, we use geometric ergodicity and Lemma 6 It follows that the expected value of the number of episodes Kr is of the order (V<1(A))
Regret analysis. Next, we bound regret terms Ro. R1 and R2 using the approach of [49] along with additional arguments to extend their result to countably infinite state-space. We consider the
relative value function v(;; 0) of policy z introduced for the optimal policy in ACOE or for the best in-class policy in the Poisson equation. In either of these cases, policy Tे satisfies (5). which the corresponding Poisson equation with forcing function c(æ, (z)) in Markov chain with
transition matrix P. In (o), we presented the solution (J, v) to the Poisson equation, which yields the following upper bound for the relative value function, as argued in Appendix A.3
v(x;0) < Č (a) S E [Kd (||=|| + loTa=) Toa]
(13)
We can similarly lower bound the relative value function using Assumption 5
v( 0) 2 J(O)E
[Tod] J [To=]
(14)
From Assumption Bl all moments of Toa and thus, the derived bounds are finite. Also, in Lemma IO we bound the moments of The of order i S r 1 using the polynomial Lyapunov function Vg e which is then used to bound the expected regret. We next bound the first regret term Rg from the first stopping criterion in terms of the number of episodes KT and the settling time of each episode k.
Lemma 1. The first regret term Rg satisfies Ru S J (maxisiss 7o + 1)].
((0) Proof of Lemma is given in Appendix B.4 From Lemma all moments of max <igr Toa are bounded by a polylogarithmic function. Futhermore, as result of Lemma 8 expected value of the number of episodes Kr is of the order Ó / hd4 (AT)) which leads a Ö / hd A(TT) regret term Ro- Next, an upper bound on R, defined in (TT) is derived. In the proof of Lemma 2 we argue that as the relative value function is equal to 0 at all time instances lg for k < Kr, the only term that contributes to the regret is the value function at the end of time horizon T. We use the lower bound derived in (14) to show that the second regret term Rí is Õ(1); the proof is given in Appendix B.5
Lemma 2. The second regret term R1 satisfies R1 S c2 (M " + where = - (3E) and c3 = (=3) 2 (2h)*² + (((KK)
From Lemma 6 [[(M 1r1 is Ologg - T); hence, R1 is upper bounded by polylogarithmic function of the order r.. Finally, in Lemmal we derive an upper bound for the third regret term
R2 defined in (2) using the bound derived for the relative value function in 13). To bound R2, we characterize it in terms of the difference between the empirical and true unknown transition kernel
and following the concentration method used in [64 10 49 7 8 we argue that with high probability the total variation distance between the two distributions is small; for proof, see Appendix [.6
Lemma 3. For problem- dependent constant Cpg and polynomial Q(T) = Cpa (Th) /48, we have R2 < (log(hT + h) + 1)a2 + Cps VATT loga (2)AII²Q((T) E [MM + hi)trrt? max [19)]
The above Lemma results in Ö(KrdJ"n4t2++t VATTT regret term as a result of Lemma 6 where h is the skip-free parameter defined in Assumption 2 d is the dimension of the state-space, K and r are the cost function parameters defined in Assumption [ J is the supremum on the optimal cost, of is defined in Assumption 4 and where Ô hides logarithmic factors in problem parameters one of which is log d+r++?++ (T)). For simplicity, we have not included the Lyapunov
8

---

functions related parameters in the regret. Finally, from Lemmas 2 3 along with the Cauchy- Schwarz inequality, we conclude that the regret of Algorithm R TTSDE){ Ro + Ri + RR) is
O(KrdJ* 1 [[) for brevity, we will state that regret is of the order Ödh V(ATT).
Theorem 1. Under Assumptions the regret of Algorithm R(T, TTSDE), is VIAIT)
Theorem 1 can be extended to the problem of finding the best policy within a sub-class of policies in set II, which may or may not contain the optimal policy. In Section _
we stated that Assumptions 3 and 4 hold for policies in IT and we used this to argue that the Poisson equation has a solution given in 66. As a result, repeating the same arguments as in Theorem [ with the modification that To is the best in-class policy of the MDP governed by parameter 0, yields the following corollary.
Corollary 1. Under Assumptions 7 [hhoough 5
the regret of Algorithm /
when using the best in-class
policy is Oddh (IATT)
Requirement of an optimal policy oracle. To implement our algorithm. we need to find the optimal policy for each model sampled by the algorithm optimal policy for Theorem I and optimal policy within policy class II for Corollary [ In the finite state-space setting, [49] provides a schedule of values and selects c-optimal policies to obtain Õ(VT) regret guarantees. The issue with extending the analysis of 49 to the countable state-space setting is that we need ensure (uniform) ergodicity for the chosen e-optimal policies. Another issue is that, to the best of our knowledge, there isn' 't general structural characterization of all e-optimal stationary policies for countable state-space MDPs or even a characterization of the policy within this set that is selected by any computational procedure in the literature; current results only discuss characterization of the stationary optimal policy. In the absence of such results, stability assumptions with the same uniformity across models as in our submission will be needed, which are likely too strong to be useful. However, if we could verify the stability requirements of Assumptions B and und4foor for a subset of policies, the optimal oracle is not needed, and instead, by choosing approximately optimal policies within this subset, we can follow the same proof steps as [49] to guarantee regret performance similar to Corollary (without knowledge of model parameters). Thus, in Theoremp 2
we extend the previous regret guarantees to the algorithm employing e-optimal policy; proof is given in Appendix B.8
Theorem 2. Consider non-negative sequence {c& li such that for every k E N, c is bounded above by 1 and an ex-optimal policy satisfying Assumptions Band 4 is given. The regret incurred ETT by Algorithm 7 while using the eg eo-ootimal policy during any episode is Ö(dhé VATT).
5 Evaluation and Conclusion: Application of Algorithm T to queueing models
Next, we present an evaluation of our algorithm. We study two different queueing models shown in Figure 2 each with Poisson arrivals at rate X, and two heterogeneous servers with exponentially distributed services times with unknown service rate vector 0 = (81, 85). Vector 0 is sampled from the prior distribution v defined on the space O given as θ = { (01, 02) E R2 0,+0, S 146 1 S l1 0, S R). for fixed R 2 and 8 E (0, 0.5). The first condition ensures the stability of the queueing models, while the second guarantees the compactness of the parameter space of the parameterized policies. In both systems, the goal of the dispatcher is to minimize the expected sojourn time of jobs, which by Little's law (52 is equivalent minimizing the average number of jobs in the system. After verifying Assumptions 5 in Appendix E for the cost function c(x) = ||æ|||2 Theorem 1 yields a Bayesian regret of order O ( for Algorithm
A
Model I. Two-server queueing system with common buffer. We consider the continuous-tima
queueing system of Figure 2a where the countable state space is X' = {æ = (xo, x1, I2) E E4 x (0, 1]2). where z6 is the queue length, and x,, = 1,2 2 equal if server i is busy. The action space is A = (h. b, 1, 2}. where h means no action, b sends a job to both servers, and i = 1, assigns a a.job to server In (38), is shown that by uniformization [39 and sampling the continuous time Markov process at rate À + 0 + 0g. discrete-time Markov chain is obtained, which converts the original continuous
problem to an equivalent discrete- time problem where we need minimize lim sup Diー [X)]) Further, [38] shows that the optimal policy is a threshold policy Te(or) with optimal finite threshold t(0") E N: always assign job to the faster (first) server when free, and to the second server if it is free and ||æ||] t(0") and take no action otherwise. In

---

Infinite queue
Infinite queue
07
6i
Dispatcher
Dispatcher
H
8g
(a) Queueing system with a common buffer.
(b) Two parallel queues.
Figure 2: Two-server queueing systems with heterogeneous service rates.
0.3
A 0.3
À 0.5
0.5
À 0.7
0.7
Regret
30
Regret
100
0.0
2.5
(a) Queueing system of Figure 2a
(b) Queueing system of Figure 2b
Figure Regret performance for À 0.3, 0.5, 0.7. Shaded region shows the toa area of mean regret.
Appendix argue that the discrete-time Markov process governed by 0 θ and following threshold policy x, for any threshold t belonging to a compact set satisfies Assumptions
15
Model 2. Two heterogeneous parallel queues. We consider the continuous-time queueing system of Figure 2b with countable state space X' { (x) x2) E Z ). where x; the number of jobs in the server-queue pair i. The action space is A = (1,2). where action sends the arrival to queue We obtain the discrete-time MDP by sampling the queueing system at the arrivals, and then aim to find the average cost minimizing policy within the class IT (mw; w E -
CR 2 1. Policy Tw : X + AA routes arrivals based on the weighted queue lengths: xx. = arg min (1 + Ii, (1 + z2)) with ties broken for 1. Even with the transition kernel fully specified (by the values of arrival and service rates), the optimal policy in 1I is not known except when 01 = 02 where the optimal value = 1, and to learn it, we will use Proximal Policy Optimization for countable state-space MDPs [8]. Note that 18] requires full model knowledge, which holds in our scheme
parameters sampled from the posterior for choosing the policy the beginning of each episode. In Appendix
E.2 we argue that the discrete-time Markov process governed by parameter 0 O and following policy Tu for [cnR) R satisfies Assumptions
Next, we report the numerical results of Algorithm|] iin the two queueing models of Figure 2 and calculate regret using (2). The regret is averaged over 2000 simulation runs and plotted against the number of transitions in the sampled discrete-time Markov process. Figure 3 shows the behavior of the regret of the two qucuing models for three different arrival rates and service rates distributed according to Dirichlet prior over [0.5, 1.9]a. observe that the regret sub-linear in time and grows the arrival rate increases. For the queueing model of Figure 2a the minimum average cost ((e) and optimal policy z are known explicitly [38] for every E O, which are used in Algorithm| and for regret calculation. Conversely, for the second queueing model, (J() and g not known. The PPO algorithm [88 is used to empirically find both the optimal weight and the policy's 's average cost. Additional details of the simulations and more plots are presented in Appendix
Conclusions and future work. We studied the problem learning optimal policies countable state-space MDPs governed by unknown parameters. We proposed learning policy based on Thompson sampling and established finite-time performance guarantees on the Bayesian regret. We highlighted the practicality of our proposed algorithm by considering two different queuing models and showing that our algorithm can be applied to develop optimal control policies. For future work plan two directions to explore: generalize our algorithm to consider polices that might not all be stabilizing, and also to simplify the algorithm using ideas from 57]
10

---

Disclosure of Funding
SA's research was supported by NSF via grants ECCS2038416, CCF2008130 130, and CNS1955777, and grant from General Dynamics via MIDAS at the University of Michigan, Ann Arbor. VS's research is supported in part by NSF via grants ECCS2038416, CCF2008130, CNS1955777, and CMM12240981.

---

References
[1] Yasin Abbasi-Yadkori and Csaba Szepesvari. Bayesian optimal control of smoothly param- eterized systems: The lazy posterior sampling algorithm. arXiv preprint arXiv: 1xX6v:400 2014.
[2] Saghar Adler, Mchrdad Moharrami, and Vijay Subramanian. Learning a discrete set of optimal allocation rules in queueing systems with unknown service rates. arXiv preprint arXiv:220.022419, 2022.
[3] R. Agrawal, D. Teneketzis, and V. Anantharam. Asymptotically efficient adaptive allocation schemes for controlled Markov chains: Finite parameter space. IEEE Transactions on Automatic Control, (4)1))11249-12)) 1989.
[4] Rajeev Agrawal and Demosthenis Teneketzis. Certainty equivalence control with forcing: Revisited. Systems & Control Letters, 13(5):405-412, 1989.
[5] Shipra Agrawal and Randy Jia. Optimistic posterior sampling for reinforcement learning: Worst-case regret bounds. Advances Neural Information Processing Systems, 30, 2017.
[6] Shipra Agrawal and Randy Jia. Learning in structured MDPs with convex cost functions: Improved regret bounds for inventory management. In Proceedings of the 2019 ACM Conference on Economics and Computation, pages 743-744, 2019.
[7] Nima Akbarzadeh and Aditya Mahajan. On learning Whittle index policy for restless bandits with scalable regret. arXiv preprint arXiv:2202.034663 2022.
[8] Nima Akbarzadeh and Aditya Mahajan. On learning Whittle index policy for restless bandits with scalable regret. IEEE Transactions on Control of Network Systems, 2023.
[9] Aristotle Arapostathis, Vivek S Borkar, Emmanuel Fernández--Gauchhraame Mrinal Ghosh, and Steven Marcus. Discrete-time controlled Markov processes with average cost criterion: A survey. SIAM Journal on Control and Optimization, 31(2):282-344 -344, 1993.
[10] Peter Auer, Thomas Jaksch, and Ronald Ortner. Near-optimal regret bounds for reinforcement learning. Advances in Neural Information Processing Systems, 21, 2008
[11] Borkar. The
scheme revisited. Journal of Optimization Theory and Applications, 66:289-309, 1990.
[12] Rolando Cavazos Cavazos-Cadena. Necessary conditions for the optimality equation in wverage-reward Markov decision processes. Applied Mathematics and Optimization, 19(1):97-112 1989.
[13] Rolando Cavazos-Cadena. Weak conditions for the existence of optimal stationary policies in average Markov decision chains with unbounded costs. Kybernetika, 25(3):145- 1989.
[14] Tuhinangshu Choudhury, Gauri Joshi, Weina Wang, and Sanjay Shakkottai. Job dispatching policies for queueing systems with unknown service rates. In Proceedings of the Twenty-Secone International Symposium on Theory, Algorithmic Foundations, and Protocol Design for Mobile Networks and Mobile Computing, MobiHoc '21, page 181-190, New York, NY, USA, 2021. Association for Computing Machinery.
[15] Sayak Ray Chowdhury, Aditya Gopalan, and Adalric-Ambryee Maillard. Reinforcement learning parametric MDPs with exponential families. In International Conference on Artificial Intelligence and Statistics, pages 1855-1880 PMLR, 2021.
[16] Asaf Cohen, Vijay Subramanian, and Yili Zhang. Learning-based optimal admission control in a single-server queuing system. Stochastic Systems, 2024.
[17] Asaf Cohen, Vijay G. Subramanian, and Yili Zhang. Learning-based optimal admission control single server queuing system. http://axxi..oog/bb/2222111 2022.
[18] Jim G Dai and Mark Gluzman. Queueing network controls via deep reinforcement learning. Stochastic Systems, 12(1):30-67, 2022.
12

---

[19] Anthony Ephremides, Pravin Varaiya, and Jean Walrand. A simple dynamic routing problem. IEEE Transactions on Automatic Control, 25(4):690 -9006699,9999999 1980.
[20] Lloyd Fisher and Sheldon M Ross. An example in denumerable decision processes. The Annals of Mathemalical Statistics, 39(2)674-675, 1968.
[21] Daniel Freund, Thodoris Lykouris, and Wentao Weng. Efficient decentralized multi-agent learning in asymmetric queuing systems. Conference on Learning Theory, pages 4080-4084. PMLR, 2022.
[22] Mohammad Ghavamzadeh, Shie Mannor, Joelle Pineau, and Aviv Tamar. Bayesian reinforce- ment learning: A survey. Foundations and Trends@ in Machine Learning, 8(5-6):359-485 2015.
[23] Aditya Gopalan and Shie Mannor. Thompson sampling for learning parameterized Markov decision processes. In Conference on Learning Theory, pages 861-898. PMLR, 2015.
[24] Todd L Graves and Tze-Leung Lai. Asymptotically efficient adaptive choice of control laws incontrolled Markov chains. SIAM Journal Control and Optimization, 35(3):715-743, 1997.
[25] Bruce Hajek. Hitting-time and occupation-time bounds implied by drift analysis with applica- tions. Advances in Applied Probability, 14(3):502-525, 1982.
[26] Bruce Hajek. Optimal control of two interacting service stations. IEEE Transactions on Automatic Control, 29(6):491-499 1984.
[27] Arie Hordijk and Flora Spieksma. On ergodicity and recurrence properties of a Markov chain by an application to an open Jackson network. Advances in Applied Probability, 24(2):343-376 1992.
[28] Mehdi Jafarnia Jahromi, Rahul Jain, and Ashutosh Nayyar. Online learning for unknown partially observable MDPs. In International Conference on Artificial Intelligence and Statistics, pages 1712-1732. PMLR, 2022.
[29] Soren F Jarner and Gareth O Roberts. Polynomial convergence rates of Markov chains. The Annals of Applied Probability, 12(1):224-247, 2002.
[30] Subhashini Krishnasamy, PT Akhil, Ari Arapostathis, Rajesh Sundaresan, and Sanjay Shakkottai. Augmenting Max- Reight with explicit learning for wireless scheduling with switching costs. IEEE/ACM Transactions Networking, 26(6):2501-2514, 2018.
[31] Subhashini Krishnasamy, Ari Arapostathis, Ramesh Johari, and Sanjay Shakkottai. On learning the ep rule in single and parallel server networks. https://arxiv.org//// http://wwwww.o..b/////////.///// wttp://b//00..0072223.333 2018.
[32] Subhashini Krishnasamy, Rajat Sen, Ramesh Johari, and Sanjay Shakkottai. Learning unknown service rates in queues: A multiarmed bandit approach. Operations Research, 691):315-3330 2021.
[33] P R Kumar and A Becker. A new family of optimal adaptive controllers for Markov chains. IEEE Transactions on Automatic Control, 27(1):137-146, 1982.
[34] R Kumar and Woei Lin. Optimal adaptive controllers for unknown Markov chains. IEEE Transactions on Automatic Control, 27(4)7665-774 1982.
[35] P R Kumar and Pravin Varaiya. Stochastic systems: Estimation, identification. and adaptive control. SIAM, 2015.
[36] Tze-Leung Lai and Sidney Yakowitz. Machine learning and nonparametric bandit theory. IEEE Transactions on Automatic Control, 40(7):1199-1222 1995.
[37] Ronald Larsen. Control of multiple exponential servers with application to computer systems. PhD thesis, University of Maryland, 1981
[38] Woei Lin and P PR Kumar. Optimal control of queueing system with two heterogeneous servers. IEEE Transactions on Automatic Control, 29(8):66--73, 1984.
13

---

[39] Steven A Lippman. Applying new device in the optimization of exponential queuing systems. Operations Research, 23(4):687-710, 1975.
[40] Ashok P. Maitra. Dynamic programming for countable state systems. PhD thesis, University of California, Berkeley, 1963.
[41] Armand M Makowski and Adam Shwartz. The Poisson equation for countable Markov chains: Probabilistic methods and interpretations. Handbook of Markov Decision Processes: Methods and Applications, pages 269-303, 2002.
[42] Akshay Mete, Rahul Singh, Xi Liu, and P R Kumar. Reward biased maximum likelihood estimation for reinforcement learning. In Learning for Dynamics and Control, pages 11-827.. PMLR, 2021.
[43] Sean Meyn and Richard L Tweedie. Markov chains and stochastic stability. Springer Science & Business Media, 2012.
[44] Michael Neely, Scott T Rager, and Thomas La Porta. Max- lax-Weight learning algorithms for scheduling in unknown environments. IEEE Transactions on Automatic Control, 57(5):177- 1191, 2012.
[45] Pedro A Ortega and Daniel A Braun. A minimum relative entropy principle for learning and acting. Journal of Artificial Intelligence Research, 38:475-511, 2010.
[46] Ian Osband, Daniel Russo, and Benjamin Van Roy. (More) Efficient reinforcement learning via posterior sampling. Advances in Neural Information Processing Systems, 26, 2013.
[47] Ian Osband and Benjamin Van Roy. Why is posterior sampling better than optimism for reinforcement learning? In International Conference on Machine Learning, pages 2701-2710.
PMLR, 2017.
[48] Reda Ouhamma, Debabrota Basu, and Odalric Maillard. Bilinear exponential family of MDPs: Frequentist regret bound with tractable exploration and planning. In Proceedings of the AAAI Conference Artificial Intelligence, volume 37, pages 9336-9344, 2023.
[49] Yi Ouyang, Mukul Gagrani, Ashutosh Nayyar, and Rahul Jain. Learning unknown Markov de- cision processes: A Thompson sampling approach. Advances in Neural Information Processing Systems, 30, 2017.
[50] Daniel Russo, Benjamin Van Roy, Abbas Kazerouni, Ian Osband, and Zheng Wen. A tutorial on Thompson sampling. Foundations and Trends@ in Machine Learning, 11(1):1-96, 2018.
[51] Devavrat Shah, Qiaomin Xie, and Zhi Xu. Stable reinforcement learning with unbounded state space. arXiv preprint arXiv:2006. 04353, 2020.
[52] R. Srikant and Lei Ying. Communication networks: An optimization, control, and stochastic networks perspective. Cambridge University Press, 2013.
[53] Thomas Stahlbuhk, Brooke Shrader, and Eytan Modiano. Learning algorithms for minimizing queue length regret. IEEE Transactions on Information Theory, (7(3):1759-1781 2021.
[54] Shaler Stidham and Richard Weber. A survey of Markov decision models for control of networks of queues. Queueing Systems, 13:291-314, 1993.
[55] Malcolm Strens. A Bayesian framework for reinforcement learning. In ICML., volume 2000, pages 943-950, 2000.
[56] Wojeiech Szpankowski and Vernon Rego. Yet another application of binomial recurrence order statistics. Computing, 43(4):401-410, 1990.
[57] Dengwang Tang, Rahul Jain, Botao Hao, and Zheng Wen. Efficient online learning with offline datasets for infinite horizon MDPs: Bayesian approach. arXiv preprint arXiv:2310. 1531, 2023.
14

---

[58] Leandros Tassiulas and Anthony Ephremides. Jointly optimal routing and scheduling in packet ratio networks. IEEE Transactions on Information Theory, 38(1):165-168, 1992.
[59] Leandros Tassiulas and Anthony Ephremides. Dynamic server allocation to parallel queues with randomly varying connectivity. IEEE Transactions Information Theory, 39(2)466-477, 1993.
[60] Georgios Theocharous, Zheng Wen, Yasin Abbasi-Yadkori, and Nikos Vlassis. Posterior sampling for large scale reinforcement learning. arXiv preprint arXiv:171L.07979, 20177
[61] Georgios Theocharous, Zheng Wen, Yasin Abbasi Yadkori, and Nikos Vlassis. Scalar posterior sampling with applications. Advances in Neural Information Processing Systems, 31, 2018.
[62] William R Thompson. On the likelihood that one unknown probability exceeds another in view of the evidence of two samples. Biometrika, 25(3-4):285-294 1933.
[63] Neil Walton and Kuang Xu. Learning and information stochastic networks and queues. In Tutorials in Operations Research: Emerging Optimization Methods and Modeling Techniques with Applications, pages 161-198. INFORMS, 2021.
[64] Tsachy Weissman, Erik Ordentlich, Gadiel Seroussi, Sergio Verdu, and Marcelo J Weinberger. Inequalities for the Lı deviation of the empirical distribution. Hewleet- Labs, Tech. Rep, 2003.
[65] Zixian Yang, R Srikant, and Lei Ying. Learning while scheduling in multi-server systems with unknown statistics: Maxweight with discounted UCB. In International Conference on Artificial Intelligence and Statistics, pages 4275 4312. PMLR, 2023.
[66] Andrea Zanette, David Brandfoobrennr, Emma Brunskill, Matteo Pirotta, and Alessandro Lazaric. Frequentist regret bounds for randomized least-squares value iteration. In International Conference Artificial Intelligence and Statistics, pages 1954-1964. PMLR, 2020.
15

---

A Proofs related to problem formulation
A.1 Ergodicity definitions
Suppose that Markov process X on X' with transition kernel P is irreducible, aperiodic and positive recurrent with stationary distribution μ and let f X' + [1, oc) be measurable function such that (uff) == [f()] < +00 with Y ~ ps. We are interested in conditions under which for a sequence of positive numbers p = (p(n)) (2())))20
lim p(m) P" (z. ,(-)), 00 n=+00
Va E E
(15)
where for signed measure jı on X. رااااا sup s/ |/(g)) The sequence is interpreted as the rate function, and three different notions of ergodicity are distinguished based on the following rate functions: p(n) L, p(n) <" for < > 1, and p(n) n for Ç 2 1. Further, for each rate function A. we state the Laapur- characterization of ergodicity of the Markov process X, which provides sufficient conditions for (15) to hold.
1. If p(n) for all n 2 0, the Markov process X satisfying (15) is said be f-ergddic. From 43 for an irreducible and aperiodic chain, ferrgodicity is equivalent to the existence of function V X + [0, 00), a finite set C. and positive constant b such that
(16)
where AV = PV V with (v := En'ex P(x, <')). The drift condition (66) implies positive recurrence of the Markov process, existence of a unique stationary distribution μu, and p(ʃ) S b < +o0 (43) Theorem 14.3.7).
2. If p(n) n"h for some Ç > 1, the Markov process X satisfying (13 is said to be f- geometrically ergodic. From [43) for an irreducible and aperiodic chain, f f-geometric
ergodicity is equivalent the existence of function V X' + [1. oo), finite set C, constant E (0, 1) and positive constant 6 such that
AV -1 (1-7) + blc..
(17)
The drift condition 117 implies positive recurrence of the Markov process, existence of a unique stationary distribution μ4, and μ(V) S 1-7 < +oo (14), Theorem 14.3.7).
Moreover, if f(-) = in (5),, then the Markov process X is called geometrically ergodic.
3. If p(n) = n for some Ç 1, the Markov process X satisfying (15) is said to be f- polynomially ergodic. From 443 29] for an irreducible and aperiodic chain, the existence of a function V : X' + [1, oc), ,, a finite set C, a constant a E [0, 1), and positive constants c and such that
AV < -cVa + blc
(18)
implies Ve-polynomial ergodicity of X at rate p(n) n5-1 for all < E [1.1/C - a) with Vg- = V)-(( The drift condition (18) implies positive recurrence of the Markov process, existence of unique stationary distribution μ,, and ((Va) < a +0c
A.2 Lemma
Lemma 4. For any state x + 0%, there exists constants K 1 and ei such that the following holds for the hitting time of state 0d, Tga,
E. [n [od] S ci (xx).
Proof. We define V = Dn oa Pa where 0t pm is the n-step taboo probability 43 defined as
A P = P. (X, E TA > n).
for A, B X, and Ta is the first hitting time of set A. We also let A A In(x). We have
0 Pv(x)= = Σ Pay (v) = Σ Σ
Pay 0a PR (z)
n=0
pu+ V9 V(x)) ((()))((())))
(x)
0
n= 2z
16

---

In Appendix D.3 we argue that there exists ba > such that Viy)= - (y) for all E X, which
leads to
PV
V
V
V
1
V.
(19)
0
b
b
Define Lyapunov function
(1 + 28 V
if +
(x(x)=
1 + (25
i 09.
From the above equation and 19 we get
(
Σ Pay (y) Pro (7((
3402
Σ
Pay (1 (b) + Paos (1+ 2h
1
(1+ 26") (<<)
+ 11
2ha
(1 26 ( + +1+
1
S
1
v(x)
1
260
1
(1+ 26²)
2/0
Thus,
1
(1
1
(V
1
V ( +
(1 25 (o0)
DE X.
20
26
To find an upper bound for E. [ot)) J. we apply 43 Theorem 15.2.5], which is generalization of
Lemma 12 For any
S R <
20 there exists > 0 such that
28
Eg Σ
(x,,))
(v))))
As (y( 2 for all y E X, we have
Tod
E [KTTo]] xR
V (X;;) )x( (
1=0
=
1 + 2
(xx) < -1 (1 + +20)) vo(x),
and the claim holds for any K E [1,
25
and cj = -1 [1 + 250)
2b
26
A.3 Poisson equation
For an irreducible Markov process on the countably-infinite space X' with time-homogeneous transi- tion kernel P and cost function a(.). a solution pair to the Poisson equation 41 is scalar and function v(-) X + R such that J + č Pv, where u(z) 0 for some z E X. If the Markov process is also positive recurrent and E. Σ - (((X (i)) < oo, where Ty is the first hitting time
of some state y E X, then solution pair (J, v) given as
[(X( ==
y
and v(x) E,
Ta(X (1))
JEE [Ty),
Va E X,
Eyy [Ty
is solution to the Poisson equation J + T+ Po with v(x) = 41 Theorem 9.5].
17

---

Lemma 5. Consider Markov Decision Processes AA, c, Po) governed by parameter 0 E Q
following the best-in-class policy Tg. Then the pair (J (6), v given
CTa (09) and v²0 (x)) C (x) ) J(O) " [TOu]. Vx X,
((0)
of [Taa]
is a solution to the Poisson equation v + J = c + P v, where vnh = 0 and C (a:) =
E
Tue
1), (i))
1=
Theorem 9.5], a solution pair to the Poisson equation exists E [Te]] and C (x) finite for all æ E X. The former follows from positive recurrence assumed in Assumption B and for the latter, from Assumptions and
Proof. From 41
Tad
Tad
d
Th (x: = Ex
X (1), (
(1))
< E
Σ K (X,
Tad
Kd [[[]=|]>>> hi)" < Ex
[Kd (1|2) + h To=l:
which is finite from geometric ergodicity (Assumption 3 and the diseussion following that.
B Proofs of regret analysis
In this section, we state the proofs related to regret analysis of Section 4 We first note a key property of Thompson sampling from [49], which states that for any episode measurable function f. and H4, measurable random variable , we have
E [( r)]
= [((or y)).
(20)
where 74 := (X (1) (1)..... ...... X (1), A (1) (t 1)) for all E N. We start with deriving upper bounds the hitting times of state 0d using the ergodicity conditions of Assumptions 3 and
4 Previous works 225 27 29] have already established bounds on hitting times in geometrically and polynomially ergodic chains in terms of their corresponding Lyapunov function. However, our objective is to provide a precise characterization of all constants included in these bounds in terms of the constants of the drift equations 3 and 4 This characterization allows us derive uniform bounds across the model class. In Appendix C.1 using the polynomial Lyapunov function provided in Assumption 4 we establish upper bounds on the i-th moment of hitting time of state 0d from any state X and for 1 S r + 1. Importantly, the derived bound is polynomial in terms of any component of the state x;, Additionally, in Appendix C.22, we characterize the tail probabilities the return time to state 0 starting from 0 in terms of the geometric Lyapunov function of Assumption 3 The derived tail bounds will be used Lemma derive upper bounds for all moments of hitting times the model class. These bounds, along with the skip-free behavior of the model, allow to study the maximum state (with respect to f -nom) achieved up to time T in MDP (X, c, P following Algorithm I as follows.
Lemma 6. For p E N, the p-th moment of maxigisT Tot and My. that the maximum -oo- of the state vector achieved up until and including time T is Olog" T).
we make use of geometric ergodicity of the chain and the fact that hitting times have geometric tails to find an upper bound for moments of M Using this, we aim to bound the number of episodes started before or at T. denoted by Kr. We first find an upper bound for the number of episodes which the second stopping criterion is met or there exists a saute-action pair for which N2(x, a) has increased more than twice. In the following lemma, we bound the number of such episodes, which we denote by KM, in terms of random variable Mí- and other
In the proof of Lemma 6 dgiven in Appendix B.I
constants. Proof of Lemma 7 is given in Appendix B.2
Lemma 7. The number of episodes triggered by the second stopping criterion and started before or at time T. denoted by KM, satisfies KM S 2.A (M² + 1)dd log, T a.s.
18

---

We next bound the total number of episodes Kr by bounding the number of episodes triggered by the first stopping criterion, using the fact that in such episodes, T' = T + 1. Moreover, to address the
settling time of each episode k, shown by Eg- Tı Tk. we use the geometric ergodicity property
and Lemma 6 Finally, the proof of Lemma 8
given Appendix [B.3
Lemma 8. The number of episodes started by T satisfies Kr I VAAIM + 1)dT T a.s.
From Lemma 8 the upper bound given in Lemma for moments of My. and Sauchy-Schward in-
equality, it follows that the expected value of the number of episodes Kr is of the order Ö( O(vh4) [ This term has a crucial role in determining the overall order of the total regret up time T. In the rest of this section, we present a detailed proof of the lemmas and other results used to prove Theorem [
Remark 3. The skip-free to the right property in Assumption Dyields a polynomially-sizer subset of function Tf This polynomially-sizer subset
the underlying state-space that can be explored can be viewed as the effective finite-size of the system in the worst-case, and then, directly applying finite-state problem bounds [49] would result in a regret of order Ö(Td+0.5); since 2 1, such coarse bound is not helpful even for asserting asymptotic optimality! However, to achieve a regret of Õ(VT), it is essential to carefully understand and characterize the distribution of My and then its moments, as demonstrated in Lemma 6
Remark 4. The derived regret bound can be extended to a larger class of MDPs which consist of transient states in addition to the single irreducible class. Specifically, for any 0,, 02 E O the Markov
process with transition kernel P obtained from the MDP (X,A, c, Po. ) by following policy T2 has single irreducible class 92 and a set of transient states 02- Furthermore, Assumptions 3 and 4 hold for the single irreducible class. The reasoning behind the proof remains true in this case using the following argument: each episode k starts at 0d which is in the irreducible set for the chosen policy Tbe hence, throughout the episode the algorithm remains in the irreducible set that is positive recurrent and never visits any transient states. In other words, episodes starting and ending at O with fixed episode dependent policy implies that reachable set of is all that can be explored, which is positive recurrent by our assumptions. As a result, we can restrict our proof derivations to the subset that is reachable from 0a in each episode and follow the same analysis. The Lyapunov function based bounds apply to the positive recurrent states, and hence, restricting attention to states reachable from 0f within each episode, we can use these bounds for our assessment of regret using norms of the state. Thereafter, the coarse bounds on the norms of the state can be applied as carried out in our proof.
parameters, we refer to the parameters that characterize the complexity or size of the model class θ These parameters just a function of the size of the state- space and diameter of the MDP (as mentioned in the literature on finite-size problems 23 49)), as stability needs to be accounted for in the countable state-space setting. The dependence is, thus, more complex and requires the inclusion of stability parameters, such as Lyapunov functions, petite sets, and ergodicity coefficients that are discussed in Assumptions 7
Remark 5. By
Remark 6. In the subsequent sections, several equalities and inequalities in the proofs are between random variables and hold almost surely (a.s.). Throughout the remainder, we will omit the explicit mention of a.s., but any such statement should be interpreted in this context.
B.1 Proof of Lemma 6
Proof. Let {0:)120 be the sequence of hitting times of state 01d starting from 0 (set ag 0). Define (6)
The as the length of the i-th recurrence time of state 0d for i E N, i.e., Tod = a; Q;-1- For simplicity, we take Ty= = Tge ((1) Each such recurrence time is generated using policy गद. that is determined using the algorithm in operation in an MDP governed by parameter 0*. Furthermore, (6)
fTo kEN are independent with length at least 1, but they need not be identically distributed. The time T can be in the middle of one of these recurrence times, hence the current recurrence interval ((6)
(()) count is (T) = inf(n= Ei_ To= 2 T3. Note that the lower bound of on every To says that (T) < T a.s. Further, from the skip-free to the right property, the most any component of state can (4)
increase in during recurrence time The is h7(") Hence, the most any component of the state (and also
the || Il norm of the state) can increase is given by / max To where the random variables
(8)
19

---

are independent with geometrically decaying tails with a worst case rate of
sup 30 11.002 9
=
sup 02.0
07 %,,0,)
see Lemma 11 From Lemma 10 we have
36% .0 +1 1
68 0,,02
IC2 01,00 ,,, 12 mmax (I.
E [Toel)
max
1
00,00
"E 1100)
36% +1 11
|0 max (1,
on (1)
(1) 01,02 (2) + D/ a0% (o))
Vp
sup uEC2\/0"> 01. P2.0
1 - 7
36% + 1
|C max 1,
(se (0 /21l 10
1/ .0
1 7
sup ue 0,000
P8.00
min
K0 (z)
312 +
| max (1,
K_ 1))))
0.
< 1 7
sup W0O)
+
(21)
Be
b2,
and we define 7. = 1- (b2)- From the definition of 01.02 in Assumption 3
greater than
or equal to 2. Thus, ,/,00 2 and we have
2
68
6
62
01.02
sup 0,,02 0200
sup
I
01 n,c0
01
6
and as a result of Lemma
Po (T (2) > n) S (n
1SiST.
(22)
(1) We upper bound E [Mg-]] using the independence of { (T heN and the above equation,
E
[M
< h E
max IsisT
(i) T0a h
P( max (i) ISST 7ud n)
20
2
T
h
1
P( max T0 S 5n) h ISiST
P
00
S m))
n=0
Σ 1 - (1 (1- c (72) (7:2) (,:))~n0)
hno + h
Σ 1 - 1 - (1 mm2))=))) T
< h(nn + 1) + h
-=
where no is the smallest n 2 0 such that cl (72) < 1. By Reimann sum approximation, we get
80
E [MA-] S h(no + +1 Σ 1- (1- (12))
h(no + +1) + h 1 1- (T du
h
nT du
=h(no + +1)+ +
log 7
1 u
h
S shnno + 1)
(log T + 1),
log
20

---

where the last inequality follows from Σ n- I log T + and thus E [Mg.]] is O(h log T). We now extend the result to moments of order greater than one. From (22 for S T.
(6) Pos (T n) <. c (74) no (n2)a
(1²)
For 2 no, let no and Y; max (i)
o2 no. 0) to get
(1) Po, 1) Da (T no > t) (n.9)
which means random variables (Y:) are stochastically dominated by independent and identically distributed geometric random variables with parameter - Furthermore, [56] argues that the p-th moment of the maximum of I independent and identically distributed geometric random variables is Ollog T). Thus, the p-th moment of maxişisT Y; is Ollog T)) and
max Y max (1) ISST
no: 0) max (1) o0 ..... 00d no) no
(7)
no:
max Toa
no 2 -1 MM no:
02
which gives
(MZ-)"
S hPE
max (1)
) S hP
max Y; + no
)
I8ST T0d
USSSST
Since the right-hand side of the above equation is Oh log T), the claim is proved.
B.2 Proof of Lemma
Proof. Let (M a) be the number of episodes it such that 1 < k S K and in which the number of visits to the state-action pair (ar, a) increased more than twice at episode k,
K M (z, a.) 1 = Kr Ni (æ, a) > 2N. (æx, a)}
As for every episode in the above set the number of visits to (æ,, a) doubles,
KM (x, s (o +1.
and upper bound KM follows
KM = Σ
aM(
Σ
(M(
SM
aEA
Σ
(1 log, N (Z,
|A ( + +1)" (1 + loga T).
æI] S... a
This completes the proof.
B.3 Proof of Lemma g
Proof. We define macro episodes with start times bags k = 1,2, KM + where byy t1. Inxat1 T' + 1 (which is equivalent 71 KT 1), and for
KM +1
fnee min(ty > t.. (2, > 2N,,-, (z, a) for some (x, a.)
which are episodes wherein the second stopping criterion triggered. Any episode (except for the last episode) in macro episode must be triggered by the first stopping criterion; equivalently,
T, = T 1 for all j ny. n& 1,..., M&+1 2. For k KMs let T. Ej T₁ be
the length of the k-th macro episode. We have
74-1- T.M
BE+1-1
Σ
T
Σ
1,21+
Σ j=nk
(j nk + 2) 0.5(m -4)(n4+1 - ng 1).
j=
21

---

Consequently, Rx+1 nk 1 V for all 1 S & KM. From this, we obtain
KM
M
KT -
[nk-
na)
Using the above equation and the fact that Σ
Ek=1 k=
Kas
T.M.
T we get
M
KT
2T S
KM
2T 2K
k=1
Finally, from Lemma we get
KT S 22NT S 22 (Mg. +1) 1lgg2 T.
This completes the proof.
B.4 Proof of Lemma 1
Proof. Let F = Tи - Tx 2 be the settling time needed to return to state 0d after a stopping
criterion is realized in episode k. We have
Kr T(Ok)
Ro
E
- TE J(0T)
Kr ((0z)
(0.(( - -TE [(()]] [TE(J())
E
T
+
(23)
k=1
We first simplify the first term in the above summation. From the monotone convergence theorem,
KT
ToJ(ON)) = Σ (T
1=
Note that the first stopping criterion Algorithm ensures that Tú S Tr- + at episodes Hence
E (((aa SE (T 1)J((a))
Since 4TsTT (Th-1 1) is measurable with respect Hig by (00) get
E Hunsry(Tu-1 + (1)(1+ =E [Fuss] (i +))((0)
Therefore,
K Th ((w))
Kr
E
E [TusT) + 1)J(0)) (1)()))))1())))))) E Σ <
(T + 1))(
Rm
Thus,
KT TE [(0))]
Kr
Kr [((0))
T (Bk)
E ((0")
Σ kml
(T + 1)]
Σ
Tx
Kr
E
((00)) Kr + 1 - TKr
Σ
Bx)]
1=1
S E [((0))T]
(24)
22

---

For the second term in
(23
from Assumption 5
Kr
E
(0k)
S E
Ek S J
K
max IsisT
70d =02)
(25)
km
Substitutinh
24 and
25
in
23 we get
Ro S E [KTJ
KT
max (1) I de
JJ [KT] + J K
max (5)
IsisT T0
}
J B KT
max 15:sT
B.5 Proof of Lemma 2
Proof. We note that the state of the MDP is equal to 0 at the beginning of all episodes and the relative value function v(æ; 0) is equal to 0 at æ 0t for all 0. Thus,
KT
c++1
Ox) - + (x (e+ 1); Ow.) ]]
R =
E
t=
E
(X (lx); (x :x)
Kr-
e (04: - v (04 | + (04;0k,) - (X + +1;0kp]
= Ele (X + 1);0k)))
From the lower bound derived for the relative value function in (4).
J
6e
(x;;0) S J'E [Tou] S
3
K.
where the second inequality follows from 21 in the proof of Lemma 6 ao S Mg- + h. Thus,
We also note that |X (T
R = Elu (X (T + +1; 0x < E
(M + +h)
3
K
From the inequality (a + b)" < 2" + b*), we have
R1 <
J d
E
(Mr)
-8
+
J
5 (2h)
6e +
3
K.
B.6 Proof of Lemma 3
Proof. Let Z (1) = (x (1), Tb. (X (1)) be the state-action pair at ly S l < 1241. Ro can be upper
bounded as
Kr 1
(X + 1);00) Σ Po. (y (t) ne. (X (1)) v (yy: 0x)
Ra E
VEX
<
E
Po- (v) (t)) Po. (v) (1)
yEX
E
max kr || S.TT-
|u(x;
|Po (. (t)) Po. ( Z (t))l1
(26)
1=1
23

---

We have Por (-I((t) Po. (1Z S P (+I( -a
P.. (1I( + Po, (1Z Po. (-1(
where Po. [y] (t)) is the empirical transition probability defined as
No. (Z (t), y)
Po. (z) (t)) max No. (Z (t)))
and for any tuple (x), a, y). we define N1 (æ. a, y) = and for t > 1,
(Z a. y) l[tz S i f I for some 1: (X (i) ( (i+ (2,a,)))
Thus, from 26 and defining random variable UM max k |u(2;; 0x)l
a Ll
R2
E 1=1
E UM Po (-IZ (t)) Po. (-1 (t))1 + Σ
un PurllPo (-I2 P/ (- (t))l
(27)
We define set B& as the set of parameters 0 for which the transition kernel Po(-12) is close to the empirical transition kernel P. (-1z) at episode k for every state-action pair = (z, a) E X' A. or
B& {0: 1Poo(-111>)) Po. (-1=)11 S 3<(z), z = (xr, a) E 1, ,47) d x A}
where 3x(2) 1411 (zi+h)
I.NN, [=]] log ( for x (æ1, Rz) and some 0 < 3 < 1, which will be determined later. We simplify the fi-difference of the real and empirical transition kernels as follows
Po (+1Z (4)) Po. (1Z (4))
= [( Po. (+1Z (t)) Pa. (1Z (t)) + I T(o (1 - Pa. (. (t))ll
< (0 {B.) 3x (Z (t)).
Similarly, we have
Po. (-I Z (1)) Pa. (12 (1)]l S 10 + Bx (Z (1)).
Substituting in (27) we get
Kr Ax
Kr 4 1-1
Ra S
20m EBo EB&t + [0L
+ E
M 3n (Z (1))
(28)
k=
t=
t=
We first find an upper bound for UM = max ISAgKr | 1
|u(x;; 0x)] using the bounds derived in 13
and
From
v( 0k) <
E Te
[Kd + hTT Taa]
s E
[2' Kd (| + h" (TTz)") Tpa]
[d(2]|<]1>o)) )" "E Thh [To=] + Kd(2h) the [(oo))++
Kd2" (1|=) + W²) E ((
& Kd(r + 1)2"d (| + h²) og (r + 1) (V2. (x) + bg, ac;
< Kddr+ + 1)2" (|==I + 1²) ob (r + 1) [>>||==|33 + (g( (k
(29)
where the second line follows from the inequality (a + b)" S (a" + b²), the fifth line from Lemma TO and the last line from Assumption 4 and 21). We further have
26 (r 1)
2 + (j 1) acp 01.63 0%1,02)
1=1
00.0g
r++
r r+1
22- + (j 11) (K.) -1bb) .o))
min(1,
(P)
24

---

where using the definition of b%,00 in (38),
(2)
91 +ny +ny max (1, B8 (8,00))
(0b + 1119-11/11000 01.00) 11+ 0y S.
00.02
We also define
1+1 r+1
0- + = II
(1- 03 +,,+))))))
min(1, 8.)
j=1
We next find a lower bound for vo 0z) using (14 as follows:
6e
v(x;; 0%) 2 -= [Toe]
(
3
K.
Combining (29) and the above equation, we get uniform upper bound for |w( 0x)] over O which we use to upper bound Vas = max 1rk5Kr [0( 0s)l as below
| SM
UM S (J + Kddr + 1)2") 2i 1) ((M3)) + +t²) (s% (M1--) + +g((K))-))
= Cpi ((M))' + +w) (s" (M..) (((K)))
I Cp2 (M rtr!
(30)
where the constant terms are defined as
Cp1 == (J Kd(r + 1)2") or + 1), Cp2 := m max (1, Gp. (h" + 1)(s + (((K))
deterministic upper bound on UM can also be found from the above equation. Noting that from until time T only states with each component less than equal to hT are visited,
Assumption 2
have
UM S Cp2 (MT-) S Cp,(TT) (Th)+** == QTT),
where Q(T) is a polynomial defined as above. Using the bounds derived for UM, we bound R starting with the first term the right-hand side of (28 We have
f++1-1
20M [B [0
s 2Q(T)
1(0 + [(one
Ky
< 2TQ(T)) E
[ + [00eB.))
<2TQ(T) >
IF
[T0 + (0
k=1
$ 4TQQ())
Σ
p(0" $ Bx).
(31)
where the last inequality follows from (0) and the fact that set B3 is He, -eeauurabl.. To further simplify the first term in (88). we find an upper bound for TP (0" & B&) using [64]. For a fixed = (a. a) and independent samples of the distribution Po- (-12), the de-viiiition of the true distribution Po- (.[z) and empirical distribution at the end of episode k, Pa. (-1z), is bounded in 10)
14 14 (0. + h)
2(A(T) 8
IP
|PP (-1z) Po_ (11z)11 2
log
20 A| I
Ti= (z. + h)
Therefore,
5
P P- (-120-(-122Pppp (11))) 2 Bx(z)
(z) = =n]
20 11
(x, + h))
25

---

and
P Po. Po.(11)) (-12) Pa. (+12)112 2 36(2))
Po (-12) Pa (1)) 2 Br(()) ( No,
=m) P(N, =n]
| II (z, + h)
The probability that at episode k S T, the true parameter 0* does not belong to the confidence set Bg be bounded using the above and union bound as
P(O" $ B&}
Σ
PP
P(l1Po-(12 (-1z)
P-a (-12)]1 2 [x()))
ATMAA
8
Σ
A II
(xt + h))
ze (0.1, A
= j 2076
[ (x: + h)
8
(log (h(T + 1)) 1)a
2076
8
(log (h(T + 1)) + 1)a
2016
In the summation in the above equation, we have simplified the expression by summing x; I hT instead of considering the more detailed summation over x; I My. However, this simplification does not affect the final evaluation of regret, this term is not dominant and only contributes to logarithmic term in the regret bound. Substituting in (31)
E
2Pm [Bo + [ooeBall
(TQ(T)
plo B&}
Xrmm
kml
8 (log (h(T + 1)) 1)a TQ(T)
K.
< (log (1) 1))
(32)
We now upper bound the second term in
28 From 330
KT Ck fx-1-1
Ky f
3 (Z (t))
S 2cpa E (Mā.)
Σ
Σ
3x (Z (2))
(33)
t=
k=
t=ty
To bound the regret term resulting from the summation of Bg (Z (t)), we note that from the second stopping criterion, N₂ (Z (t)) S 2N, (Z (t)) for all 4 I tt < 4++1 and
Kr 1++1-1
(Z (t))
1=
ta41-1
14 == (X; (1) + hh)
log 2)ATTT))
max (1, No. (Z (t))
2|A[T))
Kr & -1111
2 I
d i-
(X (t) +h)
Kr fr111
5 14log
Σ
Σ Σ
(x, (1) +
8
max
(1, (Z (1))
(34)
26

---

The first summation can be simplified as
Kr 1--1-1
2 (X; (t)+
Kr B611-1 2
$ 2 + h11a
(Z (t))
/max Ne Z (t))
- / +h)
E
V NN)+1
=E(0,1, Mg-
3 (/2 + h)d
E
Nx+1(Z)
=E(O.)." sE(0.L,"..Mg-''"
3/ 2 + h)d,
where the second inequality is due to the following arguments,
Kr
1-1-1
Nr-1(x)-1 1
1
Σ
[(N111(=)20) +
Σ
k= tl V (1,
Vi
=E(0,1,-- (.00,,,.,,G..... M..
1=1
<3
Σ
VNT+1(2).
For the second term in
we get
Kr 1+4-11
(t) hh) = v (Mg. + h1aa Kr
Σ
Ek
S KT
Tod ISiST
max (a)
V (Mă. + +
< 2 T
max (1) 18i5T Tou
(MG- + h1)a
where Fg. Tk Th. and Ky is bounded from Lemma bounded as
8
Thus
ΣKT Kr
Elets- -1 BB (Z (4)) is
KT 1441-1
(2LATT) 8
Σ
Σ
BR (1) 2 [AIT log, log
max ISiST
(Mo h)²
1=1
t=tk
Substituting the above bound in (33
Ky lx+1
20 Br (Z (())
k=1
I=
< 48Cpp
|||Tlog, T log
22/
E
(M--) rtr? (My + h)aa
ISiST -0
max (1)
)
S Cps |A|T logg T log
2 8
E (Ma + hidtr+t??
ISiST Tos }
max (5)
where Eps
= 48cp2 Finally, from the above equation, and 28
R₂ < N (log (A(T + 1)) + 1)a TQ(T)
22(A(T")
+ +cra AlTlog T Tlog
E (MO- 6- + 1))+r++?
15iST T
max (8)
5
By choosing 3 = TQ(T)) get
R₂
s (log(h(T + 1)) + 1)dd + Cps VAA/TToo,,TToo///1177 E (M + hidtrt+??
max 7(0 )
ISiST
(log(h(T + 1)) + 1)d Cpa /l. (21A(72Q(TT) E (Mg. + hidtt+t?
-16 [
max
15.T
27

---

where Q(T) Cps (Th)
B.7 Proof of Theorem |
Proof. Lemmas 1 2 and [ along with Cauchy-Schward inequality showed that the regret terms Ro and R2 are the order OKKrdJ* hd+2rtr2 V(A and the term RG is (J)"))))) There- fore, from TTSDE) = Ro + Rí + R2. the regret of Algorithm ] TTSDE), is [KKrdJnd422+rr VIAT).
B.8 Requirement an optimal policy oracle.
To implement our algorithm, we need to find the optimal policy for each model sampled by the
algorithm-optimal policy for Theorem and optimal policy within policy class IT for Corollary [ this has also been used in past work [23 24 36]. In the finite state-space setting, [49] provides schedule of e values and selects e-optimal policies to obtain ((VT) regret guarantees. The issue with
extending the analysis of [49] the countable state-space setting is that we need to ensure (uniform) ergodicity for the chosen e-optimal policies; the lim sup or lim inf of the time-average expected reward (used define the average cost problem) being finite doesn't 't imply ergodicity. In other words, we must formulate (and verify) ergodicity assumptions for potentially large set of close-to-or to-tmmmall algorithms whose structure is undetermined. Another issue that, to the best of our knowledge, there isn't general structural characterization of all c-optimal stationary policies for countable state-space MDPs or even a characterization of the policy within this set that is selected by any computational procedure in the literature; current results only discuss existence and characterization of the stationary optimal policy. In the absence of such results, stability assumptions with the same uniformity across models as in our submission will be needed, which are likely too strong to be useful.
If we could verify the stability requirements of Assumptions B and for a subset of policies, the optimal oracle is not needed, and instead, by choosing approximately optimal policies within this subset, we can follow the same proof steps as [49] guarantee regret performance similar to Corollary
[ (without knowledge of model parameters). To theoretically analyze the performance of the algorithm that follows an approximately optimal policy rather than the optimal one, we assume that for specific sequence of {<x 1 k=1, an ex-optimal policy is given, which is defined below.
Definition 1. Policy π E II is called an e-optimal policy for every 0 E O.
((x))
Σ yEX
0) S c(ar, (z(x))
Σ
Po a (((x)))((3; + te,
yEN
where σ is the optimal policy in the policy class II corresponding parameter @ and v(:; is the solution to Poisson equation (5).
Given c-optimal policies that satisfy Assumptions and in Theorem 2 extend the regret
guarantees of Corollary to the algorithm employing e-optimal policy, instead of the best-in-class policy, and show that the same regret upper bounds continue apply.
Theorem 3. Consider non non-negative sequence {e such that for every k E N, en is bounded above by T+T and an ex-optimal policy satisfying Assumptions 3ndd 4 given. The regret incurred Jand
by Algorithm 7 while using the ex-optimal policy during any episode k is Ö(dha V(ATT).
Proof. For the ea -pptimall policy used in episode k. shown by tht we have
c(x, 1 c (x)) + Σ Po, (yla,, 7h (x))o(y) 0x) S c(xx Tū, (a:) + Σ Po (ulo, TØ (x))) 0k) + 6x
NEX
VEX
= =(Ox) + v( 0k) Ek.
28

---

Thus,
Kr
Kr
R(T, STSDE) = E
Σ
ax (E Ro Rg R₂
Tcch
Kr
with
Ro EE
ThJ (0x)
- -E [](Or]
k=1
Kr f6-1-1
R1
u( ((X());0) (( 11:++1);0))))
Kr 1--111
R2
(X((++1);0 Σ x (X())))) VEN
T
We assumed that given e-optimal policies satisfy Assumptions and As result, utilize the proof of Theorem |
to deduce that the term Ru R1 + R2 is of the order Odhh VIATT). Moreover, Σ EK=
can simplify the term E
Thes
below:
KT ThEk
Kr
Kr
E
E
TRER
+ E
ERER
(35)
k=1
From the second stopping condition of Algorithm 1 have Th T 15 .... S k and
KT
TRCE
S [((r))
where we have used the assumption that 6 I
For the second term of 35 from 25
R+1
KT
Kr
KT
Es
E
EacK
E
E
max ISST
max ISST
To
log(Kr
+1
t:
1=1
k=1
k=
(36)
where in the last inequality we have used Σ I 1 log(n). Finally, as a result of Lemma and Lemma 8 the result follows.
C Bounds on hitting times under polynomial and geometric ergodicity
C.1 Polynomial upper bounds for the moments of hitting time of state 0d
For any 01, 02 O, consider the Markov process with transition kernel P dib obtained from the MDP (X, A, c, Po.) ) by following policy πæ,- (2 Lemma 3.5) establishes that if the process
polynomially ergodic, equivalently satisfies (4), then for every 0 < 1, there exists constants
99 by ,g > such that the following holds:
(o'.on )" (a) < -B3 (Vo, (x))
20 1-
+
67 02 10, (x), x E E,
(37)
where for 17 E (0, 1), 08 = min (ain 1) and
S6 = - 08,00 (0%,.o, )" n max 1, (B.
(ob (0 + (10 0,)) (38)
and for 7) 1, "3, -, and by by f, Consequently, the following result is immediate from the proof of (29 Theorem 3.6]; for completeness, provide the proof in Appendix D.I
29

---

Lemma 9. Suppose finite set 01.02 constants Po 02 00.00 > 0, r/ + S < < and
function 0,,0, X [1, +00) exist such that (4) holds. Then, there exist sequence of non-negative
functions Vo,00g 00,00 - [1, [1,+ for = 0,...,r , that satisfy the following system of drift
equations for finite sets C21,02' constants 0/ 02 2 0 and 501.02 00
AV 01,02 (x) S 00 Vú, (x) os,,o (x), x xE
(39)
Notice that is the maximum degree of the cost function defined in Assumption ! Following the proof and approach of [29] and using the set of equations (39), we can find an upper-bound for Ex (T for i L, ......7 + in Lemma 10 In order to establish upper bounds for the first
+ 1 moments of Tps. it is crucial to choose the value of 06 greater than equal to F+I as demonstrated in the proof of Lemma i0 Appendix[D.2
Lemma 10. For 1,...,, r and for all æ E
Ex Th
((To=) |1 10 (i) VP 01,02 (x) + by 10 00%
where o (1)
I1;
2 + + - 1) ac2 by D2) ti -1 1)(1 00100)
Pyj
0, and Pbi, defined in (38). and aC,
mminyecr, Ko o.))
Based Lemma 10, we impose the conditions of Assumption to obtain uniform (over model class) and polynomial (in norm of the state) upper-bounds on the moments of hitting times to 0 Moreover, these conditions lead to uniform characterization of parameters of Lemma 10 over all models in class.
C.2 Distribution return times state 0dd
For any 01, 02 E O, consider the Markov process with transition kernel P obtained from the MDP (X, c, Po,) by following policy тे.- In the following lemma, we show that the tail probabilities of the return times to the common state 0d, again Tgo, converge geometrically fast to O, and characterize convergence parameters in terms of the constants given in Assumption Explicitly, we show
Fos n) c0 (52 (5
for problem and policy dependent constants L0 02 and 7/ .00-- We will follow the method outlined in 27 with the goal to identify problem dependent parameters that will be relevant to our results. Proof of the following lemma is given in Appendix and and follows the methodology of (27).
Lemma 11. For every 0,, O2 E θ in the Markov process obtained from the Markov decision process (X, A, Po.) following policy Tb, the return time state O starting from state O satisfies the following:
Pos n) S cg (59 (70,02)
where
2
68. 82
68 00,002
cg 00,00
and
70.00 ,0 = 1
bb, Az
0,,02
with
bg .2
31g
91,80 82
+1
CC 0z
max
max "EEC, og ((04)
E [Toe]
1
78.00
obtain uniform tail probability bounds on Tye for all model parameters, and policy choices in 6. Moreover, these conditions lead to uniform characterization of #1.02 and 10..02 over Ô. Furthermore, as result of
Based on Lemma 11 necessary to impose the conditions in Assumption
Lemma 10 and uniformity conditions of Assumption 4 E Téa [Toe] has uniform bound over θ and Cg,,02 {0d). which can be characterized in terms of the polynomial Lyapunov function.
30

---

D Proofs of hitting time bounds
D.I Proof of Lemma
Proof. the proof, to avoid cumbersome notation we will drop the indices 01, 02. Following the proof of Theorem 3.6 in (2)), we choose
(i - 1)(1 - a²) for .,..., + and note that
as 1 1), we have Tji ( 1J. As result, we can apply (37) to each Y to get
A (VP)T (x) mh (z)())) it1 + 6thh Lcr i= 1...
Thus, the system of drift equations
39
hold for
V (V/) -1(1=a")
8 0, + 1, I..., r 1,
3 3hh
b; = 6":
i + 1, 1,
C. C",
where 5hh and 8h are defined in (38)
D.2 Proof of Lemma 10
The proof of Lemma 10 uses the following lemma.
Lemma 12 (Proposition 11.3.2, [43). Suppose for faateegativeefunntion f. 9. and V on the state space X and every E Z4. the following holds:
(X & V(X)) - f(Xx) +g(x))
Then, for any initial condition and stopping time T
E2
Σ ((xx) < <V(x)
Σ (Xxx) A=0
Proof of Lemma 10 Following (29]. the proof uses an induction argument. will use the notation of Lemma K(.), and 0,,0' V/, 00, 89, 0., C,, as V,, b, B, C₁.
2 for simplicity. Similarly, in this proof will also denote 00 (1) @(i), Ke, o, (-) as
X, K(x) is positive and finite. Considering the system of drift equations found in Lemma 9 C = C is finite set for all = 1,...,r + 1. Thus, mingec, K(y) strictly positive. For all X' and i i....,r + 1, we have
From irreducibility, for all
(x) S
min K ((y) yEC.
K(x)).
(40)
We set acp = (minyec, K(y))-1 = (minyecr K K(y)) From Lemma for j = 1 and x E X
AVo(#) (z) +bb bTTo, (w))
By applying Lemma 12 for all x E we get
Tad
Tad
Ex
Vi (Xx)
Vo(x) + E,
Σ h=
De (Xx)
(41)
K=
Using
and 41 followed by noting that
K(x)= = Σ n pm (x, (x,
Σ 2 n Ex !llo (Xx))}
n=0
n=U
31

---

we get
Tan -1
bacc
Tdd
Ex
Vi (Xx)
$ B1
Vo(ar) +
En
Mha (X ktn)
31
k=
n=0
k=0
Tdd
- 1+n
B1 Vo(x)) + blacr
Ex
Σ
n
Ine (xx)
31
n=U
Rmn
Tad
Tod-1+
Vo(ar) + blace
<
Em
12
Σ
Ins (Xx)
B1
$1
n=
A=VVTo
bIaCP
00
Vo(x))
2- 2 1)
31
31
baa
Vo(x) 31
As Vi(x) 2 1, this gives bound Es [To=] as follows:
bac
Ex/To=]
Vo(x)
31
31
Assume for 2 1, by the induction assumption we have
Ep
Σ (ke
(
S (0(1 (Vo(z)) + b.a)).
(42)
k=
Set j = i + in 39
which yields
AVi(=) S -B++1Vi21a2 + (2t)
Define Z = k V k) From the above equation, we have
k X < (k: + 1)x (V, (X 31+1
bit1llca (Xx))
S Z + (k V (k 1) (Xx) (k: + 1) (
By applying Lemma
to the above equation, we get
1
(k+ V+++ (Xx)
Taa-1
Fad
< 2
Σ A=
(I: + 10+-) (Xx)
b Ex
Σ
(k 1) (Xx)
(V)(() b acr E. (m
(43)
where the second inequality follows from (40) and the induction hypothesis
Thereafter, from
(by using integral lower bound after using Vi 2 1), we have
Tad -1
Ea (TO4 ) s Ex
Σ k=
(k + 11)1
I <() (Vo(z) + bjac)).
Substituting in 443 we get
Fad
B411E
Σ
(k 11'V44''44 (Xx)
2' (Vo(())VV(())) + b1ace) (b)4 (Vo(x) + bjace)
(2' + (b ((i) (Vo(=)) blacr)
Bii + 1) (Vo(z) b1ace).
This completes the proof.
32

---

D.3 Proof of Lemma 11
Proof. the proof, to avoid cumbersome notation we will drop the indices 0,, 02, Based on Assumption 3 there exists finite set C9, constants 69, 7 E (0, 1), and function V X + [1, (00) satistying
(v) S -1 bo x xE
(44)
For n 2 1. define the n-step taboo probabilitics [3 as
A P = Pa (X,, E B.TA>
where A, S H, and TA is the first hitting time of set A. We also let A Læ(x) and V9 = En=o PMV3. Applying the last exit decomposition on C# (04) for all a E X, we obtain
(x))
pa (z) 0 my
n= DEX
= =V((x) +
O Pn Vz
== YEX
DC
Σ
0 Pa
az C0 PoPP pn-m ()
+ ΣE
ge co
sy V2
yEA m=1 (SU))
n=1 yEX =ECO
=V((x) +
O Pn (z)
(45)
yEA
Σ E VEX (EX22EC0((0))
Σ \m=1
pm uz
Σ Cop V V
Σ
E
go Paz V2)),,
(46)
zy
ZECo (od)
Term
Term 2
where we break up the trajectories starting at state x and reaching state y while avoiding state 0d into two: ones that never visit the set C9, and the others that visit C99 \ {(0)) up until time m but not afterwards and exit C {0*) at time
We first bound Term in (46) by finding an upper bound for the probability term Σm pa pm using
the first entrance decomposition on C9 \ {0a3 while noting that z E C \ {0d):
pm mz
8a Po Pll-tPu oe pm-
m
1=1
uEC (0
vdCO
Σ
Σ
O Pl PooPou Pur
Σ
d pm
mECo\fON)
1=00 udCo
m==
Σ
pm
0
uz
MECV (04) m=0
P. Poe > m)
wECV ((0) m=0
< |091
max uEC*>(00)
Eu (Toel
(47)
(0a)
where the third line follows from the fact that E Eugeo co Pt. to C9 through u E C9 \ {0), so it less than 1. Irreducibility and positive recurrence combined with |C*] < imply that max Eu [ou] co, which shows Σm= o² pm is finite. Next,
Pou Pou is the probability of entrance
33

---

by induction we prove that for n 2 1 and z E Ca \ {0r) we have
Σ
Co zy
(g - (79)a 89.
(48)
yER
For I, we have using Assumption B that
Σ
oa Pay Poy -
Σ Pzy ( 5.
VEX
NEX
Assuming that (48
holds for for + 1 we have
Σ VEN
19 v
Pay V 50 Σ
Pa. (9
(Using (44)
Ca
zu
VEX
DgCa
eg
Σ
Pa (v) S (79)*
(By induction step)
Ca
vEA
so 48 is shown. We collect these bounds later on for our result on Term 2.
We now simplify the summation in 45 Similar to previous arguments, we will use induction for and show for all X
Σ yEX
c pa wy
(3 S (+9
(49)
For = 1. we have
Σ cs Pey (3)
Pay { +
yEX
yEX
Assuming that
(49
holds for n, for n + 1 we have
Σ
put my
(g))
Σ
co pm
EPsg (y 5000 Σ
Co p (2)
az
VEA
#dC=
VEX
=$C*
$ 7
C9
P zz
V9 < (79)" (x)
=EX
where the first and second inequalities follow from the definition of taboo probabilities and 44 Thus, (49) proved. Lastly, for Term in 46), note
Σ
Σ 0o Pm (2) <
max yECo (o0g)
V y
Σ
0a ax
n=1 (04)
ZEC ((d)
x=1
69
C
max (od)
Eu [To4]
(From 47
From the above equation,
47
48
and
49 we bound (x as follows:
(x)
< +V
+ (z) - 69) Σ (1 + 1C89288 weCH)((d)
max En [Toe] 1+ Σ
(
n=1
n=1
< (x)
3|C02b0
max 1, max Eu [Tou] "uECoi(O")
79
1-
(360 +
(C9]2man (1,
max BulToe]) ))
< (*)))
(1..
(I-90
where the last line is due to (x 2 Taking
31 + (109p2 max (1,
3 = 1 1-
max Ee (Foel) > >1,
"Ec
34

---

we have shown that
(x) I (z), ZE
(50)
We now upper-bound (Tge n) for all n 2 1 in inductive manner, starting with P Poa(To As part of showing this, for every * 0 we argue that for all
1).
PT > n) S (1(x)) (1-
1 - b0
(51)
First note that
(x(x)) 2 V2(x0) 2 1.
(52)
Thus,
(To
P
=
E
galay ay
Σ ge mn (z)
yEA'
VEX
8
Σ
Pay
pi
(z)= = Σ
pa
(z).
(53)
0
0 yz
0 mz
yEX
n=0 ZEN
sEXR=
We now apply the bound in 50
to get
P (To >
(1-8))
(54)
j0
ZEX
With the base of induction established, we assume the statement (51) is true for n. and show that continues to hold for n + 1 as follows:
(T > n +
Σ
Pay PayPyyCe
(To > n)
yzoa
I 1
Σ
Pay (3(
80
(1
n+1
S (z())
69
where the final inequality uses the same arguments as in (53) and
Finally, using the tail probabilities of hitting time of state 0 from any state x + 04, we bound the tail probability of the return time to state 0d (starting from 0d) as follows
Σ Po Pa n) S (1 (1-
Por(Toe > +1+1)==
Σ
Pon (9())
69
) Pow (x) S b989
1 (1-
Σ
1
60
60
where the final inequality follows from the definition of b9, and we have
b i9
1
70
and c
3g
80 -
and the proof is complete.
E
Queueing model examples
F.1
Model 1: Two-server queueing system with a common buffer
We consider continuous-time queueing system with two heterogeneous servers with unknown service rate vector 0' (01.0% and a common infinite buffer, shown Figure 2a Arrivals to the system are according a Poisson process with rate À and service times are exponentially distributed
35

---

with parameter , depending on the assigned server. The service rate vector 0" is sampled from the prior distribution V/ defined on the space 4 given as
1-8 8 15 =Rj. 02
01
(01,02)
02) E R.
01 02 S
R
(55)
1+6
for fixed 8 E (0,0.5) and R 2 1. Note that for any (2), E O, we have 0 2 0g and the stability requirement À < 81 + 02 holds. The countable state space X' is defined as X = (æ = (.ro 31; ;2) 20 E NU (0), II, 22 E [0,1]}, in which ag is the length of the queue, and 2;, i = 1, 2 is equal to if server is busy serving job. At each time instance r E R4, the dispatcher can assign jobs from the (non-empty) buffer to an available server. Thus, the action space A is equal to
A = {h, b. 1,2].
where h indicates no action, b sends a job to both of the servers, and i = 1, assigns a job to server i. The goal of the dispatcher is to minimize the expected sojourn time of customers, which by Litte's law 52 is equivalent to minimizing the average number of customers in the system, or
1
/."
inf lim sup sum WEll T-+00 T [Ix())) dr,
(56)
where X Xr) the state of the system at time r E 18,,, immediately after the arrival/depatture and just before the action is taken. In (38), it is argued that from uniformization [39] and sampling the continuous-time Markov process at rate of x 0ī + 0% a discrete-time Markov chain is obtained, which converts the original continuous- tarimuous-time problem shown in (56) to an equivalent discrete time problem as below:
TEll T-000 T /-" [|X(r)ll dr
inf lim sup
dr= = inf lim sup xell T- T
I
Σ T=0
|
(1)..
(57)
To obtain a uniform sampling rate of X + 07 + +8% the continuous-time system is sampled at arrivals, real and dummy customer departures. In (38), it is further shown that the optimal policy that achieves the infimum in (57) is a threshold policy Ty with the optimal finite threshold ((0) E N, with the policy defined as below:
h if [oo- = 0} or { [|æ=||a S tt .1 = 1) or far = I2 -}
(z)
1 if (zo 2 1, = 0}
2 if (zo 2 || 2 1, 00; 0}:
note that action b is not used. Policy Te assigns job to the faster (first) server whenever there is a job waiting in the queue and the first server is available. In contrast, ग. dispatches a job to the second server only if the number of jobs in the system are greater than threshold and the second server is available. If neither of these conditions hold, no action or h is taken. Consequently, we can restrict the set of all policies IT in (57) to the set I,, which is the set of all possible threshold policies corresponding to some t E N.
In the rest of this subsection, our aim is to show that Assumptions 1-5 are satisfied for the discrete-time Markov process obtained by uniformization of the described queueing system and hence, conclude that Algorithm [ can be used to learn the unknown service rate vector 0" with the expected regret of order O(VT).
Assumption Cost function given as c(x,a) = || which satisfies Assumption with fa( = .n I1 + I2 and K = =1 1.
Assumption 2. For any state-action pair (x, a) and 0 O. we have Po (A(Ax));; a) where A(z) = [y E X: ||ll|l, - ||| > 1}; thus, Assumption 2 holds with f = 1.
Assumption 3. Consider queueing system with parameter 0 following threshold policy n, for some t E The uniformized discrete-time Markov chain is irreducible and aperiodic on a subset of state space given as Xr = X \ (((é 0) 2 min(t, } U {(0, 1, 1))). In [88. it is proved that for every t, the chain consists of a single positive recurrent class and the corresponding average number of customers, depieted by J²()), is calculated. Moreover, it is shown that for every 0 θ the optimal threshold (0) can be numerically found as the smallest E N for which J³(O) < J (0). Define the set T the set of all optimal thresholds corresponding at least one O or
I (t :t:t t(O) for 0 θ}.
36

---

Remark 7. There is discrepancy between the class of MDPs defined in this section and in Section 2 as the former the MDPs are not irreducible in the whole state space X. Specifically, for every Markov process generated by a queueing system with parameter 0 following threshold policy wh, irreducibility holds on X, C X. Nevertheless, the results of Section 4 are valid as starting from state (0, 0), the visited states are positive recurrent; see Remark
In the following proposition, we verify the geometric ergodicity the discrete-time chain governed by any parameter 0 E θ and obtained by following any threshold policy for t T"; proof is given in Appendix F.T
Proposition 1. The discrete-time Markov process obtained from the queueing system governed by parameter 0 = (0).02) & ④ and following threshold policy nt for some E T is geometrically ergodic. Equivalently, the following holds
AV S - (1--18,) (z) + b/ 18,11cz, x E Ns
for
V/9 (z: = exp( log(1 - 5)(1=(11); 8,
Cg. {(r0, 11, 0) 4o < t) U {(0. 0, 1)),
(58)
1, max exp (- log(11 8) (||=)|a +))
(59)
=EC,
70.t 2 2(01 + 02 + A) (0) 02) - 6) X(1 81
(60)
Having described all the terms explicitly, we verify the rest of the conditions of Assumption which lead to uniform (over model class) apper-bounde the moments of hitting time to 0 as follows:
1. From (60). suPpee.Ee 18, S 1/2 < 1.
2. From 588. we can see that state (0, 0) belongs to C% for all 0 E O and t E T" In order for
C Usee Cg, to be finite set, the supremum of the optimal threshold t(0) over θ should be finite. In (37) with service rate vector (01, 02), it is shown that the optimal threshold is bounded above by /2,//0,. which further gives
t(0) < v2 0 O2
S V2R.
(61)
Thus, supase (00) S /2R, which is finite. To confirm a uniform upper bound for 6g,0- we note that from (59)
8 5
sup 8
bg.
max exp(- ()][= xEC
8
which is finite as |C < 00.
Assumption 4. To find an upper bound on the second moment of hitting times, we verify Assumption and show that there exists finite C. constants Tr b%, 0, r/(r + 1) ag 1, and function Vola Xe + [1, +00) satisfying
A AVG, S -bb, (v2,(a)) ab.
+ Nog, (x), x E Xr.
(62)
Proposition The discrete-time Markav process obtained from the queueing system governed by parameter 0 (0,, 02) θ and following threshold policy for some t E T is polynomially
37

---

ergodic. This is true because 662
holds for
Vū, (z) |
(63)
C = {(x0, I1, 0) : -o < < (10. :20 <
21
21
+
22
2
21
1
(64)
01 + 02
b0 = max
(||=|1 + 1))),
(65)
2A
8 01 + 02 +
(66)
0g.1 2'
(67)
Proof of Proposition is given in Appendix F.2
We define the normalized rates as Ā x+01+02
and f2 x+0 +0p for 1, 2. From the choice of parameter space O, we have Ā S 0.5 0.58.
81 02 0.5 0.50, and 01 0.25 0.258. We verify the remaining conditions of Assumption
as follows:
1. From (63). the first condition holds with r 2 and s 2.
2. From 64 we can see that state (0, 0) belongs to C2 for all 0 e O and i E T". Furthermore,
2A
1-8
sup A
01 02 X
which follows from the stability condition Ā S 0.5 0.58. Thus, from the definition of Cg in (64). and the fact that supece (0)) S /2R as argued in in 61 CT Usge. Cp.e is finite set. We also note that supsee, ig is finite as |C_) < co. remains to show that infeee.ET= S. is positive, which is equivalent to verifying that supsee, Ā 1/2, which follows from the stability condition À < 0.5 - 0.56.
We need to show that (o,((r)= == En= 2- (P))" (ar, 04) strictly bounded away from zero We notice that from any non-zero state æ. the queueing system hits 0d in ||>/|| transitions only all transitions are real departures. Hence,
(x) 2 2 2-12:: (P))
||=|||
(xx, 0d)
||>|||
O2 ||a|||
2 2 2-12211 l+1l
{g]
2||21||1
2 221120 æll: 22 -2R-111 22-12201
sell
0
2|
2 2011: |ll| -21-111 اlll
where the third and fourth incqualities follow from the definition of in (55). Thus, the infimum of (o)( over the finite set C? and sets θ and T* is strictly greater than zero.
Assumption 5. We finally verify Assumption 5 which asserts that supace [() is finite. We have
((O) Ex- [c(X) Ex Ex-=oo.co [1] x Ex-po
0,000) (X)
where (e)) is the stationary distribution of the discrete-time process governed by parameter 0 and following the optimal policy according to 0. From (62) and 43 Theorem 14.3.7).
(o (v Vi (x)
V
which is finite from the the previously verified assumption. Consequently,
D
sup)
sup ((0) <
oo.
oc
38

---

E.2 Model 2: Two heterogeneous parallel queues
We consider two parallel queues with infinite buffers, each with its own single server, and unknown service rate vector 0* = (of, (2)) shown in Figure 2b The service rate vector 9 sampled from the prior distribution defined on the space ④ given
{ (02,02) E R
1- 8
81 02
+
R
(68)
81 + 02
1 1
for fixed E (0, 0.5) and R 2 1, which ensures the stability of the queueing system. Consider the discrete-time MDP (X, A, Po.,c c) obtained by sampling the queueing system the Poisson arrival sequence. The countably infinite state space X' is defined as below
X = x = (.1, r2)
E N {0)},
where the state of the system is the number of jobs in the server-queue pair i just before an arrival. Furthermore, the action space A is equal to
A = {1,2),
where action i E AA indicates the arrival dispatched to queue i. The unbounded cost function e X' x A N [0) is defined the total number of jobs in the queueing system, i.e., c(x, a) =||=|| For every w E R4. we define policy Tw : X - A, which routes the arrival according to the weighted queue lengths, as
Tw (x) = arg min (1 + z1, w (1 + x22)
where the tie broken in favor of the first server. We also define policy class II as the of policies Tw such that w belongs to a compact interval; in other words,
1
ñ
Twi w
CRR cuR
where is defined in (68) and CR 2 We aim minimize the infinite-horizon average cost in the policy class 11, that is,
((0) = inf sim reft T-+00
E c x (1) A())
(69)
T
where X(I) (X) X2(()) is the occupancy vector of the queueing system just before arrival I. Even with the controlled Markov process transition kernel fully-specified (by the values the arrival rate and the two service rates), the optimal policy that satisfies (69) in policy class is not known except when 0, O2 where the optimal value is 1, and so, to learn it, will use Proximal Policy Optimization for countable state-space controlled Markov processes as developed in [18] Note that [8] requires full knowledge of the controlled Markov process, which holds in our learning scheme since we use the parameters sampled from the posterior for determining the policy at the beginning of each episode. Furthermore, for each policy in the set of applicable policies 1I. 18 also requires that the resulting Markov process be geometrically ergodic, which we will establish below.
Proposition 3. The discrete-time Markov process obtained from the queueing system governed by parameter 0 = (01, 02) E θ and following policy aw E Ói is geometrically ergodic. Equivalently, the following holds
AV (x) < 1 (1 ) (x) + bg bg (z), x DEA X,
(70)
'When 0, = Oz. then the policy with w (Join- (Join-the-Shhe thee-Shotest- (eartest-Queue) is the optimal policy 19 for the underling MDP.
39

---

for
0w (x)
w+1 exp ag x -
w + exp
(ag (x2 1))
- 0.58
log 1 - 0.58 8
5(1 - 82)
mg min wlog(1 0), log(1 8) w log
(71)
-
4en Ri(1 0.56)
C (21, X : S max
0)
, 1,2]
(72)
2w ww1
3i 2
2
(g (x2 + (o++2)) 2)))
60
max =EC 6,
exp
dg
+
exp
(73)
w
w
++1
1
22, S1,8
2,
(0)
70.
+
max
exp
+ 1 ++
1 w +
exp
w
1+
(74)
and problem-dependeen constants 25
and L,,, for i, = =1,
Proof of Proposition B is given in Appendix H3
the rest of this subsection, our aim is to show that Assumptions 1-5 are satisfied for the discrete-tims time MDP and conclude that Algorithm caa be used to learn the unknown service rate vector 0" with expected regret of order Ö(
Assumption Cost function given as c(x, a) = ||>|||,, which satisfies Assumption with fa(x) = FD I1 + I2 and K = 1.
Assumption 2. For any state-action pair (x,, a) and 0 O we have (a(A()); x. a) where A(x)= - (y E X |/||| æ | > 1}: thus, the MDP is skip-free to the right with h = 1. Moreover, from any (x, a). the finite set { X' ITlll s ||||| 1] is only accessible in one step; thus,
Assumption 2 holds.
Assumption 3. In Proposition
verified the geometric ergodicity of the discrete-time chain governed by parameter 0 (0,, 02) E θ and following policy Th E 1l and thus, it only remains verify the uniform model conditions. We define the normalized rates as
x40.+0, and B. x for i 1,2. From the choice of parameter space O, we have S 0.5 0.56,
0
0 + 02 2 0.5 0.50, and 0, 2 0.25 + 0.256.
1. We first argue that ww is bounded away from 1 as follows
1 - 1000 =1
01
A
0
1
exp
a
42
0
exp
0.+h
c-cxp
cxp
81+A
01
1xexp exp
((((t))-11
9
01
(1 exp
a
(o.(en
01 + A
RnR
RnR
a
(o,(enR)-1
(0.25 + 0.258)
1- exp
CRR
where the first line follows from the definition (1.9.w in Appendix F3 the second line from 71 and the definition of policy class î.. As ag does not depend on 0, supsee.eel ( en.) (1,0,w < 1. Furthermore, by similar arguments it can be shown that Ç2,0.u is bounded away from 1. We next argue that 01.0 exp
62.6.. is bounded away from using an upper bound found in +
1+
1tw
40

---

Appendix F.3 as below,
g exp
40,
2,
1 + w
w
+ w
1tw
2
010 So
X x 020
Ss02 (AGa (1t1()+
2
+ +C3 (81 + 02) 22(a)
+ on Saw
1)(A + 82a
(Grag ( 0,00
w(1 + O1 02 Sow ()
Saw
020
(Coag) (cn R2) )2 (0.25 0.256)² CR R2 CRRCca3 (C...R(soo.....
(75)
where La = (1 + 8) 44
1-0.54 and we have used the arguments of Appendix show that f1ewWw
F.3 and
I-
the definition of O Using similar argument, bounded away from one, and finally, conclude that supoeo, 28.0 1.
It
$2.0.
exp
سg
is
2. From 72p. can see that state (0,0) belongs C for all 0 O and w Le
CRIl.. In
99 order for C to be finite set, the supremum of x i00, over θ and II should be finite. From the
definition of 2: 1,0,
in Appendix F3
(CRR + 1) exp(cRRaç..)
W log
110,0
(w + 1)7d.m w(1,0,0 exp
4 C2.9.u
CRR
(enR 1) Rap
log
0 (cn
(w + 1)1 w5100w exp
62.
and we can derive lower bound for the denominator from 75 Similarly, show that 22 @ Rn [t] 2,0. finite. We next find a uniform upper bound for 220 from Ap-
pendix F3
2 2,0
(G1.0.0 exp
(ag (bb-x
(cnR+ 1) exp(enRaaa + wexp
ag
78.
log
0g
Tiw
$2,0,0
119 + +2)
(2cRR + 1) exp
CR Ra
1
en
log
(c(cRR)-1
80,0
which is uniformly bounded as 78... is unformly bounded away from and the second line follows from 774 and the fact that 70.. 52,0 2 1 1-71- Arguments verifying the finiteness of the
supremum of x:92 TT follow similarly, and we conclude that |C*| < To confirm uniform
upper bound for bm... we note that from 73).
6 < max 22exp ZEC!
og (2) (2) + +)) + 2exp (ag (I2 + 2)))
(I2+
sup WE RRR
which is finite ag ag independent of the choice of 0 and |C co.
Assumption 4. We next verify Assumption 4 and show that there exists a finite set C% constants
So 62.m 0.r/(r 1) ag 1, and function ViL. X + (oc+ satisfying
A AV (x) S -86m. (Von. ab. + 16 16,,Jor (x)) x E X.
(76)
41

---

Proposition 4. The discrete-time Markov process obtained from the queueing system governed by
parameter 0 (01. 02) E è and following policy Tw E 11 is polynomially ergodic. This follow
because 76 holds for
VP 0,
(z)
2
(77)
w
X+
(01.
(16c R3 101cRR)
1.2
(78)
02
02
01 82 x
0g
01
m min
(79)
22(02 + ++V+++++ +I (0) + 02 + A) I
2(0g > 2(01 + 1) 2)
( 1)
mm20 =1% +)
max
+ (x2 + 1)²
(80)
xE 8,w
0g
(81)
2'
Proof of Proposition 4 is given in Appendix F.4
Next, we verify the remaining conditions of
Assumption 4
1. From and the fact that w E LogR CRRl.. the first condition holds with r = 2 and o =
1 .c 12] 86, = cn R +
2. From 78 state (0,0) belongs to Cr for all A θ and w legn: cRR). Furthermore, for
i i= 1,2,
X+ 02
1
R
4R 1+8
sup enR
sup
sup
(82)
WE Ft
0,
#e 02
AE 0
which follows from the fact that 0₁ S RO₂ and 0, 2 0.25 + 0.258. Thus, from the definition of 0, in (78). C. Up en Cg is finite set. We next verify that the infimum of
pe found in (7).. is positive. In (82). we showed that infimum of A+0: by 1+5 4.
0, over O is lower bounded
From this, the fact that w belongs to compact set, and 01 + 02 + A 2 8, it follows that
inf infoge an P8 O. Furthermore, it is easy to see that _ VeRR. Hence, from
80
(o 1)2
sup WEO g [gll
sup WE क. CR
(g + 1) max
+ (x2 + 1)²
w
I (v CnR 11
max (CnR(z, + 1)² + (x2 + +1)). EEC2
which is finite as |C_| < 00.
3. We need to show that (x) := En 2 (P.")" (x, 0 is strictly bounded away from
zero. We show this using the fact that from any state æ, the queueing system hits (0, 0) in one step with positive probability. Take &i,0, = max 24 for = 1, 2. We have
inf W T Gn aECo..
min
K(x) >
inf
min P(ax, 04) wcCo.
000,EE क AR M
inf 00 मम =R
P ((<11ee)
The infimum in the right-hand side of the above equation is attained for the minimum normalized service rates possible for each server, or 0, = 1+5 and 0g Kg,w(x) (z)) over the finite set C., O and interval [o CRR is strictly greater than zero.
1+5 4R Therefore, the infimum of
Assumption 5. We finally verify that supace J(0) is finite. We first note that for æ = (x1, x2),
z + 23 = 2 max(w" (O), 1)V2 0,0- 10),
(x) + x2)² < 2 max(2" (mxxx,,))))))))))))))))))) 1)), (0)
(z).
42

---

From the above equation.
(0) = Exxuua p (0) [c(X)]
= Ex~po (0)
X [1]
2 max (w* (0), 1) xo..
VP (0) (X)
where (() is the stationary distribution of the discrete-time process governed by parameter 0 and following the best in-class policy according to 0, shown by (a)- From [43. Theorem 14.3.7,
suPoeG LoRR CRR 0g
VoL (0) (x)
| (0)
3
which is finite from the the previous verified assumption. Thus,
V2cgR
su enl) (8
sup 6EN
J(0)= S
< 00.
F Proofs related to the queueing model examples
F.1 Proof of Proposition
!
Proof. We define the normalized rates as
A A x
0,
8,
(83)
X + 01 +0
- for = 1.2. From the choice of parameter space 9, we have A 0 01 + + 2 0.5 0.55, and 01 2 0.25 + 0.255. To prove geometric ergodicity, from the discussions of Section 2 suffices to show that there exists a finite set Cg constants 02 > 0, 18. (0. 1), and function
V0, X. [1, +00) satisfying
AV, S
0,1 (x) + by Cc, (z). EE X. - - (1-
(84)
Take V2, exp(ag ||=1|=] for some og., O. For i and 11, PAV (t, 1, ÄV 1,,,, Vz, where P is the corresponding transition kernel. Thus,
(1, 0,
(1,,),
P V2 (i, 1, (1 (8.
-exp (og, (1 (1+3) + (01 + 02) exp (ag, (i +1) (1 (1. (ag, (i (i+2)
=exp (cg. (i 11) (Xexp(2ag.)) ) + 0, + 02 - (1 - -0,1) exp(an,))
Take āg,e- exp(a),). We need to find āg.; > and 0 < <gg, < such that
dao (1 9 )ā, , + 0 + 82 < 0.
(85)
Take āg.z= (1- -1-1) 6)-1 >
and
(1+ + A( - (1-6)-1) 6)-1)
T0. = 70. = 2
We need have 50,6 < which follows from the stability condition À 5 0.5 0.55 as below:
1
50.
+
(1 1)(1 - 6) (1= 1-8
1 1- 1(1 - 8) + 1-
2
2
2
2
1
1
1- 1-8 + \ 1 1- (1 (1-
1 8 + x 5(2 - (
+
2
2
1- 8
2
2
1-8
1
1
8(2 - 8)
82
+
1-8+
=
<1 1.
2
2
2
4
43

---

We now verify 85
X
1
1- X
X
Xāg, (1 10. ae,
01 +
+ +1- X
(1 (1- 6
2(1 - 6)
2
2(1 - 8)2
X
1 X
+
2(1 5)2
2
2(1 - 8)
1
(7+ (1 1)(1 8)2 (1 61)
2(1 8)3
8
(0 (6-1 - Aσ + +2Ī
2(1 8)3
8
(2 6) + -
2(1 5)2
< 0,
where the last line follows from À < 0.5 0.58 < (1 6)/ 6).
For x = (i,0, 1) and 2 1, we have
(i, = (i, 6
1,0, 02V2, 1,1,0).
and
Pav2 (1,00,, - (1 Vo.
-eep (o), (i + 2) + (01 + 02) exp (a,,)) - (1--2,)) (o),
(i (i+1))
= cxp (age)) (xxxp(2a),)) + 0 + 02 (1 10.0 exp(().))
which results in the same conditions as previously discussed. When x = (i, 1, 0) and 2 also same argument holds.
Finally, (84) holds for
C { I1, vo u ((,,0)))
d log(1 8),
1 1
(11 (1- 1) 6) x(1 - 5) b)-
18.1 2
2
6. (x: exp(ag,.las) 1=x11l)))=))
0,t max exp(o) exp(og,11=111) (exp(a),)) - 1).
=EC,
where the last line holds because (V) & (v) for y such that || = ||0||| + 1.
F.2 Proof of Proposition]
2
Proof. In order to show polynomially ergodicity, we will verify 62) We define (x) = || and
aggt = 1/2, which is equal to r/(r + 1) for r = r is defined in Assumption For x = (i,
and 2 1,
Pd VV, XVg (1,
1,0,1) + O.V, 1,1,0),
which A. 0, and 02 are the normalized rates defined in 83 Thus,
=i(++2 (0) + - 88 (i+1)
=i(4 - 22 (. 1 B8
44

---

For pg.t 1 2X, the right-hand side of above equation is non-positive for 2 a = (i) and 2 t,
23 For 1-2X
1,1,0).
Thus,
(2, -2,00 (,, V2 (i,
- 11+ (0)
Ro + +
=i(4} - 2+ (.,) + - P..
-
which is also non-positive under the same conditions as the previous case. For i 2 1 and x = (i, 1),
PaVE, (1, -
8, 1,0).
Thus,
96. (1,,, (
x)i+3)² + (0) + (1 ()) - (i + 2)² (i + 2)
-i(4- 2+ (g,) + - 22%
which is non-positive under the same conditions the first case. Finally, 62 holds for
21
C₁ ((r0, x1, 0) so < <1 (10, : 20
<
31 + 32 2
1 - 2X
8 27,
P
0,
2'
||00|
0.0
max (||=)1 + 1)3). C
8,r
where the last line holds because PVZ, I (v) for y such that ||y|| ||æ:|| 1.
F33
Proof Proposition 3
Proof. To show geometric ergodicity of the chain that follows Two we verify 70p. Take ag > 0 and
6, (x)
exp
+
+
w exp (1o.w (22 + +1)
(86)
w
First, we find PV3 (z) for the function defined above. We have
0,0
mg x2(2)+1)
]
E exp (a) (X2(2) + 11]
PV. PV (x) E
exp
w+1
(87)
where X(2)= (X, (2), (2)) is the state of the system the second arrival, starting from state To find the above expectations, we first find the corresponding transition probabilities. If the number of departures from server during fixed interval with length less than the total number of jobs in the queue of that server, the number of departures follows Poisson distribution with parameter 0tt. Let IP ((11, x22)
(a1. X)) be the probability of transitioning from a system with x; jobs in server-queue pair i (just after the assignment of the arrival) to queueing system with x jobs in the first server-queue pair (just before the upcoming arrival). For x
I 21, we have
P ((11,22) (1), = [ -exp(-Xt))
(01t)=1-2)
A
S1 #1-0f
exp( 00t) dt
(x) xf)!
0
+ 0
01+1
(88)
45

---

and
P (((11 + (0, = -11 x
(x(4x)
01 0
(89)
+ X
i=1
Assume + < (1 x2), which results in the new arrival being assigned to the first server. For the first term in (87). we have
X1(2) ]
w B
1
exp
_
P ((01 + 1,22) + (i) exp
1=0
81
21+1
+1+1
i
A
01
a1t1-i
exp
ag w
01 +
01
01 +
i=
01
21+1
A
I1 +1
exp
88,0
#1+1
11
81
exp
01 +
0 +
1
exp
B1+A
P1
01
#1+1
A
I1
1
exp
(90)
01 +
0 +
w
00.u
81
exp
81
Similarly, for the second term in 187.
we have
E
exp
X2(2) -
82
22
A
exp
(ag (2
(91)
02 +
02 +
exp
(-00
P2+x
8
To satisfy 70 for some 0 < 20.0 and all but finitely many æ, the following should hold,
PVg (x) S 28.0 V (x),
or from 86 and 87
E km
w exp
(2)
+ E x
exp (ag_ (X2(2) + +1)
w
In +1
aag (I2 + (12+11))
S 28.
w weep
+ exp
w
Notice that
O1
#1+1
(
(
O2
22
S scaR+1
+
0g + x
From
90 and 91 suffices to have
z1t2
(ag (x2 + 1)
(CRR + 1) exp(cR w 0,+1 cxp
ag
w
Ozta
exp
+
exp
ag...
U1+1
H1
exp
(-og.w)
02
02
21 +1 w
abp (02 + 1))
S 700 wexp ag
+ exp
(92)
Define
A
$1,0,0
01+
$2.0,00 - exp
0s+
1
exp
01+X
01
(0g
0g
Simplifying 992 we need the following to hold
(b x1 a1+11
I (1ow exp
(gg.0
(cnR + 1) exp(en + w exx
(
78.00
w
+exp (niw (x2 + 11) (5,,0,0 - 70,00
5.
(93)
46

---

As 20 < 1, there exists 20.0 such that
S2 < 10, < 1.
From the assumption 1 + xι w(1 x2) and the above equation,
(93) be further simplified as
1) +exp
exp (0g
x1 + ")
[WG1e00 exp
m
$2.0, - (w +
1)
S
w
w
(94)
For the above to hold outside finite set, need have
S1. 1+
22.0 l+
exp
'0.w
(95)
w
Define
1 1 0.56
53 1+8' S1
(96)
1-6
Note that (3 < and Ç4 > 1. Defining function (w) == -++(v--exp(x) we note that for S log Ca+ f(v) > 0, where log Ç4 the maximizer of f(y). Similarly, taking g(y) == Czy/ exp(-1) -y),
for y S - -og (3. gly) > 0, where - log Ç3 is the maximizer of g(y). Thus, conclude that for
ag S min log C3. log {3, w log C1).
سي w
exp( y) S Szy holds for y S max
(97)
cxp(y)= S 1 + Say holds for
(98)
To guarantee the existence of < 28m < that satisfies 955.. we need to ensure the left-hand side of
(95 strictly less than 1. Using the bounds found in 97 and (98 and the definition of Ç1,8,0 and
$2,0,0 we simplify (95) to get
w + aa
I+
< 1,
A 01ag.0
A + O2ag
which is equivalent
ag SzO2 AC1 (301(1+w)
AC3 (01 + +0)
X2
(99)
w
To make sure there exists a% > 0 that satisfies which follows as below:
99 the right-hand side of (99) needs to be positive,
01 + 02
1 0.50
AC3 (01 + 02) - 2²5a A
X
1+0
1
1
1 0.56
A(01 02 + A)
1+ 8
1-6
1
1
1- 0.50
A(1 + 02 + A)
1 0
1 8
=1-
1
1-8 8
1
1 1 0.50
2 1(1 02 +
+
1+
2
1+
1-
1 x(0 + +0
(100)
where 5. 0, and 0g are the normalized rates defined in (83 and we have used the stability condition
< 0.5 - 0.56. We further simplify the left-hand side of (99 as
Cz02 (AÇa (3 w < 02dCaCa <
1 0.56
(0 + 02 + A)A.
1 82
47

---

From the above equation and 100
00
needs to satisfy
8(1 - 82) 0,0 S
8(1 0.56)
Finally, we take س as
6(1-6% 8²²)
0 min (-wlog Ca, -log Ca, w log Ca.
8(1 - 0.56)
After finding an appropriate ym we can choose 0 < <0w <
such that 995 holds or
1+ St.ao 2
1
62,0,0
9 Ne
exp
1 w
1
Moreover, from (44 lower bound =7. for xı is derived; In other words. From (33, we can find the corresponding 22,0, and take wi (2f,0.. 22 By repeating the same arguments when + 21 < w(1 + 22), we finally conclude that
(4 holds for 21 > "i,
AV 8. (a) S - (1-70w)) 78.w) (a)) + 18ow Jog (2)), mEA X
for
Vi (x) =
w
exp ag =1 +
exp
0g20 (I2 + +1))
w w+1
w +
1 1 0.50
log 1 0.55
5(1 - 82)
a. = min wlog(1 + log(1 + 8) w log
1 8
1-8
4cn (en 0.56)
Cg = (2)) E x:
max
(/ 0)
, = 1,2),
mg
+ S2,a SLo
+ $2,0
exp (18m))
70w
9
2
2
max
G200::500000
1 w
exp
1 1+ 1+
1
2w
+
2
(g (x2 + 2))
0g max =EC
exp
+
exp
w +1
+
8,
A
$1,0.0
0
1 - exp
8,
+
1 exp
0g
02+
(CRR + 1) exp(cnRaa,
#1,0,
.1
g log
w
mg
(w + 1)78. w(1.e. exp
(cRR+ + exx + weep
ag sioutl
exp (cbzz)
-2
log
2,0,,
agow
28w C2
7
(cRR + 1) exp((eRRaa
.22
log
2,0,
g
0g
(w + 1)1w. W(I,0. $2,0 cxp (gBw))
(cRR 1)exp(cn + exp (1 + +1)
exp (1g..) 70,00
92
log
11
w 18,0 $1,0,0)
48

---

E4 Proof of Proposition 4
=² + 23. and س/ = 1/2. Assume that x1 = 0 and 22 > (1 /w which means the new job will be assigned the first server. The transition probabilities of the discrete- time chain sampled at Poisson arrivals is given in (88) and (89) and we calculate PV 6 (x) as
Proof. Define Vi (z)
22
A
O2
82-1
32
A
02
カ2-6
PV (x)
<CRR+]
w(++ 01)
A 0g
02
+
+ 0g
02
+ X
(101)
We define di := 00, + +)) for i = 1, 2 and
A
02
テ2-
À + 02
82 + A
(d2 + d2)
+ + 22 + 2xz + 1) + d2 (-2x3 2rz + 1) x2)
(1 d2)²
((1 - d (d2 + 2) + 3 (c 2d2 + + x2 (2d2- -2d2))
(1 d2) )2
2dz
(1 (1- d (d2 + d3)
22
2
122
(102)
d2
(1 d
From 101
2dz
(1 d2 (d2 + d2)
PVP (x)
8,w0 (x)
+
D 22
88
<
+
82 +
+ R.
1 d2
(1
d2)²
Outside a finite set, we need the above equation to be non nos-iositiee; which is equivalent to
(-2+ 88.0 1-d2 d2
(1 d3 (1 d2)
1 1- d2
x2 +
+ C
S
d2
d2
d2
As d2 <1, 1,
1 d2
= + d2 +...... +... + dg S
for y 2 1.
(103)
1 - d2
Thus,
1 1- d2
(1 -1ddt
do2 (1 + d2)
+ CRRR" 1-d2
-2 + P0w
82 +
d2
d2
d2
d2
1- d2
S d2 - 1+ 0,w
82 + C
d2
d2
By taking 8. S d2/2, 2, it suffices for the following to be non non-positive
1
1 d2
2 x2 + CRR
< 0
d2
which holds for 22 > R2nR/dd dg. Thus, for xı 0 and x2 2 max R(c + +2)) (1- w)/w)
RCR + O2) /2,) (6) holds. The case of x2 = 0 and non-zero 21 follows same arguments and (76)
holds for B S d x2- = 0, and 1 Z max (2cR + 0, 01)/0,, - 1) = 22 R(> + 0,) 01)/0/ We now consider the case of æ1, x2 > 0 and x + 1 A w(x2 + 1), and note that
of w
/
(I1 1)2
+ 2 S
+ (x2+1)2 + S vw 1(x2 + 1).
w
Hence, it suffices to find finite set Cg.s. constants
U//m0 and Bh > 0, such that the following holds
for VP VP)
= + 23.
AVP (x) S -V + 1,00
(12 + 1) - by tog 6,a
0,00 (I2
(2).
0,w0
49

---

+15 As +1 I w(22 + 1), the new arrival is assigned to the first queue and we find AV (x) +
0,00
Vw= + 15 + 1) using the same calculations as 102
AV (x) + VW + 1 (22 + 1)
2d1
(1 - of oi (d1 - di) oì
(xi + 1)²
(1) + +11 +
w
1 dj
(1 (1-d))
2dz
(1 d2)) (d2 + dg)
D2 +
+ VW + 100 0,00 (I2 +1)
1 d2
(1 - d2)²
T1
2d1
+ 1- 3d1
(1 (1- (- [di + di)
2
(104)
w
d1
w(1 d1)
w(1 d,)²
(111- 2d2
2dz
(1- d)")) (d2 + d))
+ (I2 + 1)
+ Vw + 1,8
+ 1 - d2
+
(105)
d2
(1 d2)²
We next consider two different cases based on the value of d1 and analyze them separately.
One. 0.8 < di < 1
We first notice that the coefficient of 01 in (104) is negative, as d₁ > 1/2. For
T1 2 1, 104 is equal to
1
(2 (2-4d) 4dh )21 4d
+1 3d, + (d1 + d
d
w(1 d1)
i=0
カ1-2
(2 4)))(()))
d1)
Σ
(1+ 7dg
w(1 - d1)
((2 - 4di) (2) - 1) + d1 + di) 1) + d: + +1)) +3 7di)
w11 d1)
((d) + of - 4d +2) - 1) + di (1+ d1) +3- 7d1) -dd
w1 (1 d1)
d 2d 2d +
R 3d +3
(11 1) +
0, w
w
where the third line follows from
103
and the last line from the fact that when 0.8 < d1 < 1, both
terms -d - 2dl 2d1 + 2 and
3d1 + 3 are negative. Next, we notice that (055) is equal to
2dz
+ (1- E2 (d2 + de)
42
+ VW
+ VW
d2
(1 )2)
2dz
+ d2 + dz
S 32
+
Vw +
+13gg0
02 + V/ + 108
1 1- d2
1 d2
2dz
d2 + d
D2
+
+ V + 11.0
+ V + 18
1 d2
1 d2
-d2 + VW
+ 13
+ VWw
+ p,
where the second line follows from
103) Taking 38 S d2/22 W + I, we get
2dz
+ V + 188.... + Vw + 13g + (1 - d (d2 + d2)
d2
d2
82
- d2
<
x2 +
(1 - -22)
2
2
which is non-iisitive for x2 2 1. Finally, when 0.8 S d1 < 21, 22 > 0. and 1ι + +1 w(22 + 1), (76) holds for 3y.m < d ///////w I.
50

---

Two. d1 < 0.8: : Taking 36 -
(w+I(1-da) we note that the coefficient of 22 in 1005 is negative.
d2
Thus, from I1 + 1 S (I2 + 1), (144) and (05).
AV 6,u
(x) + VW + 15 0, (22 + +1
21
+1
2d1
(1 (1-d% (1-dit+1 + (dl + df)
2 1 d1
+
w
w(1 - d2)²
F1 +1
2dz
2dz
(1 - (1-d2²) d (d2 + d))
+
+ Vw
+
158 0,w
+ 1- d2
w
- d2
(1 - d2)²
21 + 1
2d1
2dz
2d2 +
d1 + d2
d2 + d2
2
+ VV - 18/
+ 1 1- d2
+
w
1 di
1 1 d2
w d1 )2
(1 - d2)
(106)
As d2 0,/(0; + X) in terms of the normalized rates, we get
2d1
2dz
20
201
-2(01 + 02 X)
2 1 di
= 2
1- d2
x X
which is negative from the stability condition. For 3y
- from (06) we get
Avu+1
AVP 0, + VW + I 1)
(0) + 02- 2)
2d2
d1 + di
d2 + d3
(I1 (II+ + +1)+ +
+
+
wÁ
1- d2
w(1 d
(1 d2)²
(0) + 02 ))
20g
0
0,00 + 2))
(2 + X)
(51 +11+
+
+
x
wi2
X2
which is non-positive for
8200, + X) + w0, 3A)
11 + 12
i(0, 0₂2 2)
As d1 < 0.8, we can see that π > / thus,
0, (20, + Y) + (2 + 35) 40, (20) + 2) + 4w0z (20g + +3x
Rcn 22) < 5
S R.
A + 02 - X)
0, (0, 02 2)
where we have used the fact that 0, 2 oz w S CgR, 0, + 02- x 6, and ā < 0.5 0.56 and suffices for 21 to be greater than or equal to Rc For x1 Re (044) can be upper bounded as
Sc R w
1- 3d2 w(1 - di)
di + df
Scg
2
8c R + 50 w
w1 d2
w
w01
d
where in the last inequality we have used d1 < 0.8. From 105) and taking
S d2/2 0,
AVP. (x) + V/ -
18 1
(x2
+1)
8cR: R
50
2dz
+ d2
2dz
(1
d: d2 d3)
+
(I2 +1) +
+
W
1 - d2
2
1- d2
(1 d2)
2dz
d2
d2
+
L
2
82
+
d2
Scg + 50
dn
2
1
d2
2
w
d2
d2
Sc
50
W2
+
2
2
w
which is negative for
16 R + 100
32 1+
wdz
51

---

Finally, when 21 x1+1 ++
1
w(x2 + 1) and 21, 22
> 0,
76
holds for S S
ve+I min 82 2
((0++ 01 + 02 - 2). 21 2 AcRR, and
22
2
+
Repeating 76) holds for P S
R6c0R+100
wdo
the same arguments when 21; 3/2
> and x1 1 w
1).
Vu+I min +x0
01 + 02 - 2): 21 2 + u(16cn +100) and x2 2 Rc Finally, (76)
d1
holds with
2 21
VP (x)
+ I222
2
W
A+0;
C2u = (21,
E X: : S (16c2 R² + 101cen
8; , 1,2
02
01 + 02 -
02
0,
P8 min
2((2 1) w +1
VW +1
2(02 + x) 2(0 + Vo
(x1 (01+ + 1)²
1//0 = =88
+1 max 200%
+ (x2 + 1)3)
w
0g 0,0 2'
where the fourth line holds since (x) S Vo
for y = (3). 1/2) such that y; = x; + 1 for
i = 1,2.
G Numerical results
G.1 Comparison of Algorithm with other learning algorithms
We first note that due to the countably infinite state-space setting of our problem, we are unable to directly compare our algorithm to other learning algorithms proposed in the literature. One potential candidate algorithm uses the reward biased maximum likelihood estimation (RBMLE) [33 34 [1 42). which estimates the unknown model parameter with the likelihood perturbed vanishing bias towards parameters with a larger long-term average reward (i.c., optimal value). This scheme also uses the principle of "optimism in the face of uncertainty" in how it perturbs the maximum likelihood estimate. The naive version of the RMBLE algorithm does not apply to our examples due the following key assumption: over all parameters (and the control policies used for them), the transition probabilities are assumed to be mutually absolutely continuous; this is critical for the proofs and also allows the use of log-likelihood functions for computations. Similarly, naive use of the algorithms in [6) and [24] is not possible, again due to a similar absolutely continuity assumption which critical for the proofs. Our posterior computations avoid such issues as the true parameter always has non-zero mass during the execution of the algorithm: episode k always starts in state 0dd which is positive recurrent for the Markov chain with true parameter 0" and policy used Th. The RBMLE algorithm has yet another issue in that it requires knowledge of the optimal value function, and hence, for our examples, may only apply to Model for which the value function is known analytically. Finally, whereas we do get to observe inter-arrival times for both model, we never directly observe completed service times owing to the sampling employed, and this precludes the direct use of U (ipper-CoffidenceBBonn Bound based parameter estimation followed by certainty equivalent control algorithms. Owing to these issues, at this point in time, we're unable to perform empirical comparisons of Algorithm| to other candidate algorithms with theoretical performance guarantees in a countable state setting.
As discussed in the previous paragraph. learning algorithms with theoretical performance guarantees are established in the finite state setting. One such algorithm is the certainty equivalence control with forcing, which is proposed and discussed in detail in 4.. To assess the finite-time performance of our algorithm, in Figure we compare the performance of our proposed learning algorithm, denoted Reference 4
as TSDE, with the algorithm introduced in 4.. referred to as AgrawalTennketzin proposes a certainty equivalence control law with forced exploration, which operates in episodes with increasing lengths and priori fixed sequences of forcing times. Specifically, at the beginning of each episode, all possible stationary control laws are explored for one recurrence interval of state (0, 0). Subsequently, based on this exploration, empirical estimate of the average collected reward
52

---

10a
10a
Regret
Regret
102
10a
TSDE AgrawalTeneketzls
10"
TSDE AgrawaaTenekktzz
109
0.127
0.357
0.0237
0.1570.8
102
102
10a
10a
10a
10*
10
(a) Model Queueing system of Figure 2a
(b) Model 2: Queueing system of Figure 2b
Figure 4: Comparison of the regret performance of Algorithm | (referred to as TSDE) with the
algorithm proposed by 4 (denoted AgrawalTeneketzis) for the queueing models of Figure]
1.0
Total variation distance.
0
Total variation distance
0.3
0.7
=
0=5
A= A
0
0.4
0.1
0.1
0.0
2.5
T
(a) Model 1: Qucueing system of Figure
2a
(b) Model 2: Queueing system of Figure
2b
Figure 5: Total variation distance between the posterior and real distribution for 0.3, 0.5, 0.7. The y axis is plotted on a logarithmic scale to display the differences clearly.
is formed, and the control law resulting in the maximum average reward is implemented for the remainder the episode. The length of the episodes are determined according to sequence {a, 2 defined as following:
0g
0 + ip.
for 2 1,
where p is the number of possible stationary control laws and by = exp (iriz) for any d > 0. Specifically, episode terminates after completing additional a, 0;-1 recurrence intervals state (0, O). Both algorithms are implemented the two queueing systems of Figure 2
where the arrival rate 0.5 and service rates are distributed according to Dirichlet prior over [0.5, 1.9]2. In Figures 4a and 4b we set å = 3.5 and = 3, respectively. Moreover, in Figure the goal is to find the optimal weight w in the set (1.5, 2.5, 3, 3.5). The results Figure 4 show that both algorithms exhibit a sublinear regret performance. Specifically, Algorithm 1 TSDE, achieves an Ö(VT) as predicted in our theoretical results of Theorem and Corollary Furthermore, in both queueing models, our proposed algorithm consistently outperforms the algorithm presented in terms of regret order.
53

---

32
1(6)
14
14
14
1.0
0
02
02
(a) Model Queueing system of Figure 2a
(b) Model 2: Queueing system of Figure 2b
Figure 6: Optimal policy parameters for different service rate vectors in the two exemplary queuing systems in Model and Model 2 with À 0.5.
Average cost
0.4
01 11-1,1,0
-
0
113,, 02 - 0.5
0 115, 0 0.5
7.5
T
Figure 7: Estimated average cost of Model for three different service rate vectors.
G.2 Model Two-server queueing system with a common buffer.
Figure 3b illustrates the behavior of the regret of Model for three different arrival rate values and averaged 2000 simulation runs. In these simulations, the parameter space is selected
O {0), 02) E [0.5, 0.6. 1.9 A < 0, 02, O2 < 0
which results in a prior size of 105. As depicted in Figure 3a| the regret has a sub-linear behavior and increases with the arrival rate. The total variation distance between the posterior and real distribution, a point-mass on the random 0", are plotted in Figure As expected, the distance diminishes towards indicating the learning of the true parameter. As mentioned in Appendix E.I the optimal policy minimizing the average number of jobs in a system with parameter 6, is a threshold policy T((Ø) with optimal finite threshold t(0) E N, which can numerically determined as the smallest E for which (²) J (0), calculated in (38). We compute the optimal threshold t(0) for every 0 E θ and present the results in Figure 6a We can see that the threshold increases as the ratio of the service grows. Specifically, this is why in Appendix G imposed conditions O ensure that the ratio between the service rates is both upper and lower bounded.
G.3 Model Two heterogeneous parallel queues
Figure 3b illustrates the behavior of the regret of Model 2 for three different arrival rate values and averaged over 2000 simulation runs. We note that the regret is sub-linear and increases with higher arrival rates. In these simulations, the parameter space is selected
= (01 02) E [0.5, 0.7, 1.9 À < 0, + 02 02 < 01}.
which results in prior size of 28. discussed earlier, our goal find the average cost minimizing policy within the class of policies II {nwi [[cRR)-1 RRR), CR 1, where (x)
54

---

arg min (1 + #1, w (1 + z2)) with ties broken for 1. As discussed before, even with the transition kernel fully specified (by the values of arrival and service rates). the optimal policy in II is not known except when 01 O2 where the optimal value is = 1, and so, to learn it, we will use Proximal Policy Optimization with approximating martingale-procer
(AMP) method for countable state-space MDPs [18]. We run the algorithm for 200 policy iterations, using 20 actors for each iteration. We take the state (0, 0) as a regeneration state and simulate 1500 independent regenerative cycles per actor in each algorithm iteration. To approximate the value function, employ fully connected feed-forward neural network with one hidden layer consisting
x units and ReLU activation functions. The AMP method is also employed for variance reduction in value function estimation. The optimal w for every 8 E θ is shown Figure [b] indicating that w increases as the ratio of the service rates grows. Therefore, it is necessary to ensure that the ratio between the service rates is bounded from above and below. Furthermore, to evaluate the regret numerically, the value of J (() is required for every 0 θ, which is not known. Thus, after finding the optimal using the PPO algorithm, we perform a separate simulation to approximate the optimal average cost. Figure 7 we plot the estimated average cost for three different service rate vectors, demonstrating that the optimal average cost decreases as the service rates increase. In Figure 55) we also depict the total variation distance between the posterior and real distribution, which is point-mass the random 0*, and observe that the distance is converging to zero.
55


Reviews:
[{"review_id": "lKvaMeAFhf", "reviewer": "Reviewer_MJCc", "summary": "The authors consider the average reward Markov decision process framework with countable state spaces. The considered objective is to perform closed-loop optimal control for a family of MDPs parameterized in a compact space; this is a particularly interesting setting as the cost function is not assumed to be bounded. The authors propose a Thompson Sampling based algorithm and analyze its regret under suitable assumptions. They are able to show a finite time $\\sqrt{|\\mathcal{A}| T}$ bayesian regret bound. The authors also show the practical significance of their algorithm by an empirical application to queuing models.  \n", "questions": "- In line 203, where is $\\pi_{\\theta_k}^*$ defined? How is this implemented in the examples? \n\n- From your understanding of your assumptions, is the stability ensured by default? Or does Thompson sampling just ensure it by some magic in the proof? If the latter, and since you have a bound on the maximum $\\ell_\\infty$ norm of the states, is it not more straightforward to use existing RL algorithms? I guess what I’m asking is how necessary the Lyapunov-type analysis is in this case?\n\n- Why aren’t there comparisons with other RL algorithms in the experiments? especially since you implement PPO in the second model for your experiment, isn’t it possible to compare directly against it and other deep RL methods?\n\n", "limitations": "The proposed work and algorithms is theoretical and does direct societal impacts. The possible theoretical limitations are detailed to some extent in the paper and to be addressed in future work.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- This paper is very relevant to the community as it opens the way towards studying RL in continuous spaces without the assumptions of bounded reward functions. Therefore tightening the connection of reinforcement learning theory and optimal control.\n\n- Although certain assumptions are somehow stringent, it is nice that the paper is able to convert an infinite horizon setting to a somewhat episodic setting. The latter usually allow for simpler analyses.\n\n- The application to a queuing model is also appreciated, a nice change from the standard RL benchmarks. \n\n- I would like to clarify that I did not go through the theoretical proofs and can therefore not comment on their correctness apart from the general intuition that such results should be possible given appropriate assumptions on stability and dynamics.\n", "weaknesses": "- The assumptions seem somewhat stringent. For example, the finite support of transitions can be challenged even in the specific example of queuing models when large amounts of arrivals are possible. More importantly, assumption 3 seems quite limiting, can the authors elaborate on what this implies for stability? I am not very knowledgeable in optimal control but it seems that you are assuming stability of all policies? \n\n- The paper is sometimes very dense and not straightforward to follow. For example, lines 173 to 192 requires prior knowledge of several papers and definitions, e.g. Poisson equation’s link to the problem at hand/ forcing function and other similar passages in the text. I would advise the authors to add the relevant definitions and Lemmas at least in the appendix to make the paper self contained.\n\n- The paper fails to cite many RL works in the continuous spaces setting. Namely, the entire line of function approximation in RL, for example: 1) “Frequentist Regret Bounds for Randomized Least-Squares Value Iteration” by Zanette et al. which provides a algorithm based on Thompson Sampling as well, and many other works (see references therein) in the model-free paradigm 2) “Bilinear Exponential Family of MDPs: Frequentist Regret Bound with Tractable Exploration and Planning” which also provides similar algorithms for MDPs that seem to include the queuing models presented here, see references therein for model-based approaches to RL in continuous spaces.  \n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "\nWe thank the reviewer for their constructive review and references (which we will cite). We will add related definitions in the appendix of the final version. The references depicted with a number indicate a reference in the submission, whereas the references marked with a letter are listed at the end of the response.\n\n>Weakness 1. Necessity of assumptions. \n\nA: The state-dependent support of the transition kernel is finite for every state-action pair, but we do not assume that the supremum of the number of possible transitions is finite over the state-space. Many queueing models fit this setting-see our examples at Section 5 and reference [52] (arrivals have an explicit bound). Generalizing to allow for an arbitrarily large number of arrivals at any instance will necessitate adjustments to our proof, but with reasonable assumptions (like finite moment generating function), we expect the results to continue to hold. As noted in Appendix A.1, Assumption 3 imposes stability criterion---geometric ergodicity---that applies uniformly across policies, models, and states: for any $\\theta_1,\\theta_2 \\in \\Theta$, sequence $\\{(P_{\\theta_1}^{\\pi^*_{\\theta_2}})^n\\}$ converges geometrically fast to the stationary distribution $\\mu_{\\theta_1,\\theta_2}$, where $P_{\\theta_1}^{\\pi^*_{\\theta_2}}$ is the transition kernel of the Markov process obtained from the MDP $\\left(\\mathcal{X},\\mathcal{A},c,P_{\\theta_1}\\right)$ by following policy $\\pi^*_{\\theta_2}$. This is a stronger compared to positive recurrence-beyond the existence of a stationary distribution, it enforces a geometric convergence rate to the stationary distribution. In our context, we assume this convergence for all optimal policies $\\pi^*_{\\theta}$ corresponding to some $\\theta \\in \\Theta$. We need this assumption to upper bound the first $r+1$ moments of the maximum state norms and hitting times of state $0^d$. At present, we don't know if we can weaken the requirement from geometric ergodicity and to polynomial ergodicity (see Assumption 4). Please see Remark 1 in the global response for more discussion on the importance of stability.\n\n> Weakness 3. Citation of RL works Zanette et al. [A] & Ouhamma et al. B].\n\nA: We differentiate our work from [A,B] as follows. Both works [A,B] consider a finite-horizon problem. In contrast, our work considers an average cost problem which is an infinite-horizon setting, and provides finite-time performance guarantees; asymptotic optimality of our algorithm is then immediate. In addition, [A] studies an MDP with a bounded reward function. Our focus, however, is learning in MDPs with unbounded rewards with the goal of covering practical examples from queueing systems. The reviewer is correct that parameterization of transition kernels used in [B] and the prior work [C], can be used within the framework of our problem. However, similar to our work, additional assumptions, importantly stability conditions proposed in our problem, are necessary to guarantee asymptotic learning and sub-linear regret. As there aren't general necessary and sufficient conditions on the parameters to ensure stability, posterior updates can be complicated with this parameterization. Another issue with exponential families of transition kernels is that they do not allow for $0$ entries (except through parameters increasing without bound), and so will not be directly applicable to queueing models (like our examples).\n\n>Question 1. Definition of $\\pi^*_{\\theta_k}$.\n\nA: In Assumption 3, we have defined $\\pi^*_{\\theta_k}$ as the unique optimal policy that minimizes the infinite-horizon average cost for MDP $\\left(\\mathcal{X},\\mathcal{A},c,P_{\\theta_k}\\right)$ within the policy class $\\Pi$; Thm 1 considers all policies, and Cor 1 uses a subset of all policies. Here, $\\theta_k$ is the sample generated from the posterior distribution at the beginning of episode $k$. In the queueing model of Figure 2a (illustrating Thm 1), $\\Pi$ is the set of all policies, and the optimal policy corresponding to any parameter $\\theta$ in $\\Pi$ is explicitly characterized in [29], which is a threshold policy with an explicitly determined (finite) threshold. In the queueing model of Figure 2b (illustrating Cor 1), we find the average cost-minimizing policy within a subset of weighted Max-Weight policies, which route arrivals based on weighted queue lengths. The optimal policy even in this set is not known except when $\\theta_1=\\theta_2$ where the optimal value is ${\\omega}=1$, and so, to learn it, we use Proximal Policy Optimization (PPO) for countable state-space MDPs [13]; see Figure 5b in Appendix. Hence, in both cases, the optimal oracle can be implemented.\n\n>Question 2. Necessity of stability.\n\nA: Please see Remark 1 in the global response.\n\n>Question 3. Comparisons with other RL algorithms.\n\nA: The PPO algorithm of [13] \\textbf{requires} model knowledge and finds the optimal average-cost policy using PPO for an MDP with known transition kernels. In our second queueing model in Figure 2b, we have used the PPO algorithm to find the best in-class policy (illustrating Cor 1), utilized in Line 7 of Algorithm 1 after realizing parameter $\\theta^*_k$ from the posterior distribution. We are not aware of any RL algorithms with provable low regret in the setting of countably infinite spaces with an unknown model.\n___ \n[A] Zanette, A., et al. Frequentist regret bounds for randomized least-squares value iteration. International Conference on Artificial Intelligence and Statistics. PMLR, 2020.\n\n[B] Ouhamma, R., Debabrota B., and Odalric M. Bilinear Exponential Family of MDPs: Frequentist Regret Bound with Tractable Exploration & Planning. Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 37. No. 8. 2023.\n \n[C] Chowdhury, S. R., Gopalan, A., & Maillard, O. A. Reinforcement learning in parametric MDPs with exponential families. In International Conference on Artificial Intelligence and Statistics, pages 1855–1863. PMLR, 2021."}, {"review_id": "NND2ioAjkf", "reviewer": "Reviewer_Raj1", "summary": "This paper present an adaptation of TSDE to parametric MDPs with unbounded state space.\n\nThe regret is sqrt{T} which is good but that is  under strong ergodic assumptions and lower order terms can harm the behavior of the algorithm for small values of T.", "questions": "1. The assumption on the unicity of the optimal policy is not related with all the other assumptions and is not discussed. This is actually a strong assumption restricting the class of MDPs that can be learned. This deserves some discussion why it is needed here.\n\n\n2. The authors should discuss the practical aspect of their approach. In particular, can one check whether all the assumptions are satisfied while the MDP is unknown?\n\n3. The Q-learning approach seems more natural than a model based approach under unbounded space spaces, where only the visited states are used for learning. Several papers have already taken this option successfully and are not discussed here (see for example \"Stable reinforcement learning with unbounded state space\" by  D Shah, Q Xie, Z Xu )\n", "limitations": "I cannot see any limitations", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper is sound technically. (I quickly checked the proofs)\n\n- The problem of learning unbounded MDP is a natural and important question to address.\n", "weaknesses": "1. The strong conditions (especially  Ass 4) are not  necessary and sufficient conditions for existence of an optimal policy, nor for the existence of a solution of the Bellman equation.\n\n2. The queueing examples are not really convincing: The optimal service rates can be computed efficiently by just estimating the arrival rate and solving the optimal control problem for the expected sojourn time. Also, numerically,  the growing rate of the regret gets worse as the arrival rate increases. \n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their constructive review, and reference suggestions (which we will cite). The references depicted with a number indicate a reference in the submission and the references marked with a letter are listed at the end of the response.\n\n>Weakness 1.  Necessity of assumptions. \n\nA. Assumptions 1 & 2, combined with the positive recurrence from Assumption 3, ensure the existence of an optimal policy and a solution to the average cost optimality equation (ACOE) & Poisson equation; see Section 2. Assumptions 3 & 4 are required for our analysis, as we need bounds on the moments of the maximum state norm reached by time $T$ as well as the hitting time to state $0^d$, which we found using the Lyapunov functions in Assumptions 3 & 4. For the average cost problem in countable spaces, establishing necessary and sufficient results for the existence of stationary optimal policies, or for solutions of the average cost optimality equation are open problems. We used conditions from [9] (that are satisfied using our assumptions). The weakest conditions are in [A], and using them is for future work, but we note the importance of the existence of stabilizing policies with finite average cost even in this paper; see [B] for a comparison of different conditions in the literature. Bounded costs can be problematic in the countable setting as they do not cover practical examples from queueing systems. Thus, we impose Assumption 1: our cost function is unbounded.\n\n>Weakness 2. Queueing examples.\n\nA. Whereas it may be possible to establish asymptotic optimality for a scheme employing rate estimates (using a modified MLE a'la adaptive control), to the best of our knowledge, there are no finite-time regret guarantees provided for such schemes. Existing related results-[18] (finite number of policies) and [27] (countable or uncountable number of policies)-prove asymptotic optimality but assume further structure on the transition kernels, which our examples do not satisfy. \n\nLet $\\rho$ be the normalized load. Then, the gap from the capacity boundary is a linear function of 1-$\\rho$. Thereafter, the regret growing as the normalized load goes to 1, i.e., gap going to 0, is expected, since the system gets closer to the stability boundary as the arrival rate increases. Based on Remark 3 in the global response, our regret bound depends on $J^*$ and, thus, on the gap from the capacity boundary and will increase as $\\rho$ goes to 1, which reinforces our earlier comment.\n\n>Question 1. Unicity of the optimal policy.\n\nA. Uniqueness of the optimal policy is not essential for the validity of our results, provided that all optimal policies satisfy our assumptions. When this condition is not met, we need to select an optimal policy that is geometrically ergodic for all parameters. This could entail searching over all optimal policies when non-uniqueness holds. This issue can be avoided by using a smaller subset of policies, such as Max-Weight policies, for which the ergodicity can be established for all possible models. We will clarify this in the final version.\n\n>Question 2. Practicality of our approach. \n\nA. For a given parameter set $\\Theta$, the assumptions can be verified for all MDPs corresponding to any $\\theta\\in\\Theta$, as in Appendix E for queuing models of Figure 2. Whereas there isn't an algorithmic way to find Lyapunov functions, queueing systems have accumulated a repository of Lyapunov functions over the years, making queueing systems a reasonable application domain to consider.\n\n>Question 3. Q-learning based on Shah et al. [E]\n\nA. The differences with our work are as follows: 1. [E] ignores optimality and focuses on finding a stable policy, which contrasts with our work that evaluates performance relative to the optimal policy. 2.[E] considers a discounted reward problem, essentially a finite-time horizon problem (given the geometrically distributed lifetime). Average cost problems (as studied by us) are infinite-time horizon problems, so connections to discounted problems can only be made in the limit of the discount parameter going to 1. 3. Moreover, [E] considers a bounded reward function which simplifies their analysis, but is not a practical assumption for many queueing examples. Further, for bounded reward settings with discounting, the assumption of a stable optimal policy with a Lyapunov function (as in [E]) is extremely restrictive: e.g., if the rewards increase to a bounded value as the state goes to infinity, then the stationary discount-cost optimal policy will likely be unstable as the goal will be to increase the state as much as possible. Additionally, bounded costs for average cost problems need strong state-independent recurrence conditions for the existence of (stationary) optimal solutions, which many queueing examples don't satisfy: see [C] for necessary conditions, plus [D] shows that a stationary average cost optimal policy may not exist. Finally, we are not aware of any other RL algorithms with provable low regret for the average cost problem in the countably infinite setting with an unknown model.\n___\n[A] Sennott, L l. Average cost optimal stationary policies in infinite state Markov decision processes with unbounded costs. Operations Research 37.4 (1989): 626-633.\n\n[B] Cavazos-Cadena, R., Sennott, L. I. Comparing recent assumptions for the existence of average optimal stationary policies. Operations Research Letters 11.1 (1992): 33-37.\n\n[C] Cavazos-Cadena, R. Necessary conditions for the optimality equation in average-reward Markov decision processes. Applied Mathematics and Optimization 19.1 (1989): 97-112.\n\n[D] Fisher, L., Ross, S. M. An example in denumerable decision processes. The Annals of Mathematical Statistics 39.2 (1968): 674-675.\n\n[E] Shah, D., Xie, Q., Xu, Z. Stable reinforcement learning with unbounded state space. arXiv preprint arXiv:2006.04353 (2020)."}, {"review_id": "j2xhchJuVZ", "reviewer": "Reviewer_5uHS", "summary": "The authors study Bayesian learning of the problem of optimal control\nof a family of discrete-time countable state-space MDPs governed by an unknown parameter $\\theta$ from a general parameter space $\\Theta$ with each MDP evolving on a common countably-infinite state space $X$ and finite action space $A$.\nAs the setting is Bayesian, they assume that the model is governed by an unknown\nparameter $\\theta_\\star \\in \\Theta $ generated from a fixed and known prior distribution. \nThe learning goal: Bayesian regret minimization where the value function is the infinite-horizon average cost, and the regret is measured with respect to best policy in $\\Pi$.\nThey prove a $\\sqrt{TA}$ regret bound, up to poly-logarithmic factors, but the dependency in the complexity of the function class is unclear to me. \n\nDisclaimer: I am not much familiar with this area of RL literature and hence might not understand the results correctly. Also, I could not fully verify the correctness of the presented results.\nI gave that assessment  as the paper was very hard to follow for an unfamiliar reader.\n", "questions": "See weakness.", "limitations": "N/A.", "rating": 5, "confidence": 2, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "\n1.\tI think the results are a nice contribution to the Bayesian  RL community. \n2.\tThe two examples presented contribute to the richness of the paper. \n3.\tThe presented bounds seem reasonable.\n4.\tThe adaption of Thompson sampling to countable state spaces might be useful in other RL settings.\n", "weaknesses": "\n1.\tAbstract is quite long and parts of it seems like copy-paste of the introduction.\n2.\tWriting requires improvement: (1) lightening the contribution compared to existing literature, (2) notation is hard to follow and makes proof reading hard, (3) complexity of $\\Pi$ or the dimension $d$ should appear in the presented bounds, even if the dependency on them is logarithmic, those parameters are not negligible. \n3.\tNeed to mention the dependency in complexity of the function class is in the regret bound. Is it logarithmic for finite $\\Pi$?  Is the regret dependent on the covering number? I would be happy if the authors could clarify that point.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "\nWe thank the reviewer for the suggestions on the presentation of the paper and other remarks, and we will make changes in the final version. We note that the references marked with a letter are listed at the end of the response and are not included in the submission.\n\nFor discussion on the dependence of our regret bound on problem parameters, please see Remark 3 in the global response.\n\nRegarding dependence of the regret on the complexity of $\\Pi$, using our method and assumptions, it is not easy to characterize the regret in terms of complexity and associate Lyapunov-type conditions with covering numbers. The complexity implicitly determines the uniformity conditions of Assumptions 3, 4, and 5, and it is challenging to characterize the regret separately in terms of complexity of $\\Pi$. In essence, the bounds are akin to instance bounds. This is easily understood when $\\Pi$ is finite, as the quantities $J^*$ and $r_*^p$ above are the result of the maximization of similar parameters over a finite number of policies and models.\n\nTo address the dependency on the covering number, we will need to explore model mismatch/perturbations more carefully, but such results are not available currently for countable state-space MDPs (to the best of our knowledge). Our assumptions result in $\\Pi$ being compact, and so it is totally bounded, and given any error terms, we can get a finite cover of the parameter space. By using the centers of these covers---sampling from posterior and projecting to the closer center that covers the sample---a theoretical analysis may be feasible for the general problem if the transition kernels depend smoothly on the parameters. To make the analysis work, we will need results that can compare the performance of optimal policies of two close models (close as per metrics suggested in [A] based on the closeness of the parameters). While such perturbation-related results are available in general state-space problems for finite-horizon and discounted cost problems, they only exist in the finite state-space setting for average cost optimal problems:  [A] discusses the results for finite-horizon and discount cost problems; and\nthe results of [B] can be extended to the average cost problem in the finite state-space setting by the vanishing discount method (taking a limit as the discount factor converges to $1$).\n\n___\n[A] Müller, A. ``How does the value function of a Markov decision process depend on the transition probabilities?\" Mathematics of Operations Research 22.4 (1997): 872-885.\n\n[B] Subramanian, J., Sinha, A., & Mahajan, A. ``Robustness and sample complexity of model-based MARL for general-sum Markov games.\" Dynamic Games and Applications 13.1 (2023): 56-88.\n"}, {"review_id": "LxEAATe8xq", "reviewer": "Reviewer_5dJh", "summary": "This paper focuses on an online learning setting for Markov Decision Processes (MDPs) with a countably infinite number of states. It adopts a Bayesian learning perspective, assuming that the parameters of the MDP follow a prior distribution over a known parameter space. The paper proposes a Thompson-sampling-like approach to solve the MDP in an online fashion. This approach assumes access to an optimal policy oracle, where the parameters of the MDP are provided as inputs, and it also relies on specific assumptions about the features of the parameter space.", "questions": "Is there a heuristic for designing the parameter space and policy space to ensure that Assumption 3 holds for a queueing system? What would happen to the algorithm if this assumption fails? It would be beneficial to test the algorithm in a more general system, such as the ones described in [41, 52].\n\nHow crucial is the requirement for an optimal policy oracle? Would the analysis still hold true if the policy space is restricted to, for example, the MaxWeight policy? It would be highly valuable if the results were presented in a form such as \"the total queue lengths of this algorithm minus that of the MaxWeight policy is less than or equal to \\sqrt{T}\". This would also eliminate the need for the optimal oracle.\n\nCould you discuss the dependence of the regret on the system size? Why does the dependence on T for the regret hold more significance than these constants?\n\nPlease maintain consistency by using either \"queueing\" or \"queuing\" throughout the paper, but not both.\n\nIn line 122, after \"ergodicity)\", there should be a period.", "limitations": "N/A", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The model investigated in this paper exhibits a high degree of generality, and the results presented contribute significantly to the field of theoretical reinforcement learning by offering near-optimal algorithms for MDPs without a bounded state space. The inherent complexity of the problem necessitates intricate proofs, and although I haven't examined the complete proof in detail, I have confidence in the correctness of the underlying intuitions. The proof combines Lyapunov analysis with the proof presented in [38] for Bayesian learning in an MDP with a bounded state space, thus offering a potentially valuable contribution for future research. Additionally, the simulations conducted in the paper, which demonstrate the scaling of the algorithm's regret, are appreciated for providing empirical evidence supporting the algorithm's performance.", "weaknesses": "The results of the paper rely on a set of assumptions that may be difficult to verify. Of particular concern is Assumption 3, which assumes stability of the optimal algorithm under one set of parameters for the MDP, even when considering another set of parameters. Establishing this property for more general systems can be challenging and requires careful calibration of the parameter space and policy space.\n\nThe algorithm presented in the paper is heavily dependent on access to an oracle capable of solving the optimal policy, which itself is a complex problem for general queueing systems. This reliance on an oracle can limit the practical applicability of the algorithm.\n\nThe algorithm necessitates returning to state 0 (line 14) at the end of each episode. This requirement could result in an exponential dependence on the maximum queue length, potentially rendering the algorithm less relevant for practical implementation. As a result, the claim of practicality made in line 345 may not be adequately supported.\n\nIn relation to the previous point, the paper obscures many constants within the theoretical results. These constants, associated with the system's dimension and ergodicity, could play a crucial role in determining practical performance and should be given more attention and consideration.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the suggestions on the presentation of the paper. We will make changes in the final version based on the suggestions.\n\n>Weakness 1. Necessity of assumptions.\n\nA. Given a specific parameter class $\\Theta$, the assumptions can be verified for all MDPs corresponding to $\\theta \\in \\Theta$, as  demonstrated in Appendix E for the two queuing models of Figure 2. While there isn't a programmatic/algorithmic way to find Lyapunov functions, queueing systems have accumulated a repository of Lyapunov functions (for classes of models and policies) over the years, making queueing systems a reasonable application domain to consider.  Assumption 3 is reasonable for queueing models since policies such as weighted Max-Weight are stabilizing for a large class of models. However, to the best of our knowledge, proving geometric ergodicity in such settings is an open problem; we prove it for the example of Figure 2b as we're using weighted Max-Weight.\n\n>Weakness 2. Requirement of an optimal policy oracle.\n\nA. For the requirement of an optimal policy oracle, please see Remark 2 in the global response.\n\n>Weakness 3. Bounds on hitting time of state $0^d$.\n\nA. Assumption 4 bounds the first $r+1$ moments of hitting time of state $0^d$ from any initial state $\\boldsymbol{x}$ using the polynomial Lyapunov function (from Assumption 4); see Lemma 10. In contrast to the Lyapunov function used to prove geometric ergodicity (from Assumption 3) which is usually an exponential function of some norm of the state, the Lyapunov function used to show polynomial ergodicity (from Assumption 4) is often a polynomial function of the state, which then leads to the hitting time to $0^d$ being polynomially dependent on the initial state $\\mathbf{x}$. Our queueing examples in Appendix E employ exponential Lyapunov functions to prove geometric ergodicity, and quadratic Lyapunov functions to establish polynomial ergodicity, with the latter leading to polynomial bounds for the hitting time of state $0^d$.\n\n>Weakness 4.  Dependence of regret bound on problem parameters.\n\nA. Please see Remark 3 in the global response. \n\n>Question 1. Requirement of Assumption 3.\n\nA. Assumption 3 needs to be verified on a case-by-case basis for the optimal policy of each model that can occur; see Figure 2a example. This is challenging since optimal policies have been characterized only for a small number of systems. However, within a given policy class, more general statements can be made-e.g., checking Assumption 3 for Max-Weight policies for a large class of queueing systems is feasible. However, even for MaxWeight policies establishing geometric ergodicity would be a new contribution to the literature, as the bulk of existing results establish ergodicity using a quadratic Lyapunov function. Note that the queueing model of Figure 2b (exemplifying Cor 1) uses MaxWeight policies a'la [52], and is illustrative of such settings. The geometric ergodicity characterization for this queueing model is new in the literature, so for the models in [52] too a geometric ergodicity result is needed (we expect this to hold based on their model assumptions).\n\nWhereas at present we don't know how to weaken Assumption 3 to an assumption similar to Assumption 4, we believe that stability assumptions across models are likely necessary for the countable space setting, and for the following reasons. First, in contrast to finite-state MDPs, where stability and existence of a stationary distribution are assured in a simple manner-via irreducibility or the existence of a single recurrent class, and aperiodicity-, the countable state-space setting needs additional conditions to ensure that the Markov process resulting from using any stationary policy $\\pi \\in \\Pi$ is positive recurrent or ergodic. Furthermore, recovering after either using an unstable policy or starting in a transient state can be problematic, and with a countable set of transient states $S^{\\mathrm{tr}}$, the expected time to exit $S^{\\mathrm{tr}}$ can be infinite.\n\n>Question 2. Requirement of an optimal policy oracle.\n\nA. Please see Remark 2 in the global response. We also want to note that the queueing model of Figure 2b uses a weighted Max-Weight policy-we are selecting the best set of weights for each model within a class of weighted Max-Weight policies using the optimal oracle (the PPO algorithm used in simulations), and then regret is compared relative to the performance of the best weighted Max-Weight algorithm.\n\n>Question 3. Dependence of the regret on the problem parameters. \n\nA. Please see Remark 3 in the global response. We conclude by emphasizing that our sub-linear regret guarantee provides a rate of convergence characterization for asymptotic optimality results developed in past work, such as [18,27]."}]

Author rebuttal:
Below we address questions and remarks to common questions.

>Remark 1. The necessity of stability assumptions.

Stability needs to be imposed separately, so we use Assumption 3. This is due to the following reasons. In contrast to finite-state MDPs, where stability and existence of a stationary distribution are easily assured-via irreducibility or the existence of a single recurrent class, and aperiodicity-, the countable state-space setting needs additional conditions to ensure that the Markov process resulting from using any stationary policy $\pi \in \Pi$ is positive recurrent or ergodic. Furthermore, recovering after either using an unstable policy or starting in a transient state can be problematic, and with a countable set of transient states $S^{\mathrm{tr}}$, the expected time to exit $S^{\mathrm{tr}}$ can be infinite. See [A,B] for more discussion on importance of stability.

To analyze the regret, we use the independence structure resulting from recurrent visits to state $0^d$ (with inter-visit durations being well-behaved), which may not occur without stability assumptions. Furthermore, to characterize the regret, we also require bounds on the moments of the (random) maximum state norm $l_\infty$ reached by time $T$ and on the hitting time to state $0^d$, for which we used the Lyapunov functions of Assumptions 3 & 4. Reference [13] also uses Lyapunov function-based arguments for finding the average cost optimal policy in countable-state MDPs with \textbf{known} transition kernels. The authors impose geometric ergodicity and utilize Lyapunov function-based arguments to analyze their proposed PPO policy's performance.

To further clarify the necessity of stability assumptions,  consider the queueing model in Figure 2a (illustrating Thm 1), which has a set of countable transient states $S^{\mathrm{tr}}$-all states where the second server is occupied above the threshold. Our algorithm avoids this set (or other transient states) by always remaining within the (policy-dependent) reachable set of states from $0^d$ (which are positive recurrent by the stability assumptions). 

Finally, the stability assumption gives probabilistic control on the random $l_\infty$ and number of episodes, both of which are crucial to the result. Just using the skip-free to right property yields a state-space (plus memory use, and regret) bound, i.e., $l_\infty$, that is exponential in the time-horizon $T$, so directly using RL algorithms and state-of-the-art results for such algorithms will yield too high a regret bound (one that scales exponentially in $T$).

>Remark 2. Requirement of an optimal policy oracle.

To implement our algorithm, when we determine regret with-respect-to an optimal policy, we necessarily need to find the optimal policy for each model sampled by the algorithm-optimal policy for Thm 1 and optimal within policy class for Cor 1; this has also been used in past work [17,18,27]. In the finite state-space setting, [38] provide a schedule of $\epsilon$ values to select $\epsilon$-optimal policies such that $\tilde{O}(\sqrt{T})$ regret results. The issue with extending the analysis of [38] to the countable state-space setting is that we need to formulate (and verify) ergodicity assumptions for a potentially large set of close-to-optimal algorithms whose structure is undetermined. Another issue is that, to the best of our knowledge, there isn't a general structural characterization of all $\epsilon$-optimal stationary policies for countable state-space MDPs, or even a characterization of the policy within this set that is selected by any computational procedure in the literature; current results only discuss existence and characterization of the stationary optimal policy. In the absence of such results, stability assumptions with the same uniformity across models as in our submission, will be needed. At present we don't know how to verify such an assumption for any example, but nevertheless the conditions required are likely to be too strong to be useful.

If we could verify the stability requirements of Assumptions 3 & 4 for a subset of policies, the optimal oracle is not needed, and instead by choosing approximately optimal policies within this subset, we can follows the same proof steps as [38] to guarantee regret performance similar to Corollary 1 (without knowledge of model parameters). For instance, in the queueing model of Figure 2b, if instead of the optimal weight, we have access to an (performance-wise) $\epsilon$-optimal weight policy, we can easily see that the approximate policy satisfies the stability assumptions and the sub-linear regret bounds carry through following arguments similar to those in [38], section 3.2.  We will add this extension to the final version.

>Remark 3. Dependence of expected regret on problem parameters.

We would like to clarify that our expected regret depends on the skip-free parameter defined in Assumption 2, $h$, and the dimension of the state space, $d$, the cost function parameters defined in Assumption 1, $K$ and $r$ , supremum on the optimal cost $J^*$, and  $r^p_*$ that is defined in Assumption 4 as $\tilde O(Kr\ d\ J^*\ h^{d+2r+r_*^p}\ \sqrt{|\mathcal A| T })$, where $\tilde O$ hides logarithmic factors in problem parameters-one of which is $\log^{d+r+r_*^p+2}(T)$. For simplicity, we have not included the Lyapunov functions related parameters in the regret, but we will add the order accounting for the parameters associated with the problem structure to our final version. 
___ 

[A] Sennott, Linn I. Average cost optimal stationary policies in infinite state Markov decision processes with unbounded costs. Operations Research 37.4 (1989): 626-633.

[B] Cavazos-Cadena, Rolando, and Linn I. Sennott. Comparing recent assumptions for the existence of average optimal stationary policies. Operations Research Letters 11.1 (1992): 33-37.

Meta-review: The paper considers the problem of online RL in MDPs with countably infinite state-space. The authors provided sufficient support the interest in expanding existing theory to this setting. While the core algorithmic idea and some of the technical tools clearly derive from previous literature, the final result requires non-trivial technical steps and it is interesting. Overall, there is consensus that the paper is worth accepting.

I would still suggest the authors to consider improving the original submission by integrating the discussion with the reviewers, in particular the following aspects:

While the queuing model is interesting and it is important on its own, it would be helpful to have other examples of real-world problems that can be modeled as MDPs with countably infinite state-space.
Clarify the intuition of why the assumptions are needed.
Provide more details about the experiments.
Decision: Accept (poster)