Reinforcement Learning in a Birth and Death Process: Breaking the Dependence on the State Space
Authors: Jonatha Anselmi
Bruno Gaujal
Louis-Sébastien Rebuffi
Venue: NeurIPS 2022 Accept (2022)
Keywords: Markov decision processes
structured reinforcement learning
regret analysis
queueing systems

Abstract: In this paper, we revisit  the regret of  undiscounted  reinforcement learning in MDPs  with a birth and death structure. Specifically, we consider a controlled queue  with impatient jobs and the main objective is to optimize a trade-off between energy consumption and user-perceived performance. Within this setting, the diameter $D$ of the MDP is $\Omega(S^S)$, where $S$ is the number of states. Therefore, the existing lower and upper bounds on the regret at time $T$, of  order $O (\sqrt{DSAT})$ for MDPs with $S$ states and $A$ actions, may suggest that reinforcement learning is inefficient here. 
In our main result however, we exploit the structure of our MDPs to show that the regret of a slightly-tweaked version of the classical learning algorithm UCRL2 is in fact upper bounded by $\tilde{\mathcal{O}} (\sqrt{E_2AT})$ where $E_2$ is a weighted second moment of the stationary measure of a reference policy. Importantly, $E_2$ is bounded independently of $S$. Thus, our bound is asymptotically independent of the number of states and of the diameter. This result is based on a careful study of the number of visits performed by the learning algorithm to the states of the MDP, which is highly non-uniform.

Reinforcement Learning in a Birth and Death Process: Breaking the Dependence on the State Space
Jonatha Anselmi
jonatha. anselmi@inria.... fr
Univ. Grenoble Alpes, Inria, CNRS, Grenoble INP, LIG, 38000 Grenoble, France.
Bruno Gaujal
bruno. . gwwjallinria..a........
Univ. Grenoble Alpes, Inria, CNRS, Grenoble INP, LIG, 38000 Grenoble, France.
Louis Sébastien Rebuffi
louis- sewastien....eeeeeeee.ee..eeeebe wweeassten.rrbuffeeee rebuff wew.riinnnnuufeffuiiiii.eee wwwpeiii--geoobeeaaalaaae Univ. Grenoble Alpes, Inria, CNRS, Grenoble INP, LIG, 38000 Grenoble, France.
Abstract
In this paper, we revisit the regret of undiscounted reinforcement learning in MDPs with birth and death structure. Specifically, consider controlled queue with impatient jobs and the main objective to optimize a trade-off between energy consumption and user-perceived performance. Within this setting, the diameter D of the MDP is ((S)), where is the number of states. Therefore, the existing lower and upper bounds on the regret at time I", of order O(VDSAT) for MDPs with states and A actions, may suggest that reinforcement learning is inefficient here. In our main result however, we exploit the structure of our MDPs to show that the regret of a slightly-tweaked -weaked version of the classical learning algorithm UCRL2 is in fact upper bounded by (()E2AT) where Eg related to the weighted second moment of the stationary measure of a reference policy. Importantly, E2 is bounded independently of S. Thus, our bound is asymptotically independent the number of states and of the diameter. This result is based on careful study of the number of visits performed by the learning algorithm to the states of the MDP, which is highly non-uniform.
Introduction
In the context of undiscounted reinforcement learning in Markov decision processes (MDPs), it has been shown the seminal work [I] that the total regret of any learning algorithm with respect to an optimal policy is lower bounded by Ω ((VDSTT) where S is the number of states, the number of actions, T the time horizon and D the diameter of the MDP. Roughly speaking, the diameter is the mean time to move from any state to any other state s' within an appropriate policy. In the literature, several efforts have been dedicated approach this lower bound. As result, learning algorithms have been developed with total regret of Õ(DS AT) in [1]. Ö(DVSAT) in (3) and even O(VDS AT") according to (21 (25) These results may give a sense of optimality since the lower bound is attained up to some universal constant. However, lower bounds are based on the minimax approach, which relies on the worst possible MDP with given D, and This means that when reinforcement learning algorithm is used on given MDP, one can expect much better performance.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

One way to alleviate the minimax lower bound is to consider structured reinforcement learning, or equivalently MDPs with some specific structure. The exploitation of such structure may yield more efficient learning algorithms tighter regret analyses of existing learning algorithms. In this context, a first example is to consider factored MDPs 6 91. i.e., MDPs where the state space can be factored into a number of components; in this case, roughly speaking, 5 = K where n. is the number of "factors" and K is the number of states in each factor. The regret of learning algorithms in factored MDPs has been analyzed in [20] 17 24 [4] and it is found that the S term of existing upper bounds can be replaced by nk. A similar approach is used in [ to learn the optimal policy in stochastic bandits with regret that is logarithmic in the number of states. There is also a line of research works that exploit the parametric nature of MDPs. Inspired by parametric bandits, a d-linear additive model was introduced in [12] where it is shown that an optimistic modification of Least-Squares Value Iteration, see [15.. achieves regret over a finite horizon H of
factoree
HOT) where d is the ambient dimension of the feature space (the number of unknown parameters). In this case, the regret does not depend on the number of states and actions and the diameter is replaced by the horizon. A discussion about the inapplicability of this approach to our case is postponed to Section
Learning in Queueing Systems. The control of queueing systems is undoubtedly one of the main application areas of MDPs; see, e.g., [16] Chapters 1 1-3] and [3] Within the rich literature of structured reinforcement learning however, few papers are dedicated to reinforcement learning in queueing systems, see [22] Section 5]. and this motivates us to examine the total regret in this context. Typical control problems on queues have the following distinguishing characteristies:
1. No discount. Discounting costs or rewards is common practice in the reinforcement learning literature, especially in Q-learning algorithms [19]. However, in queues one is typically interested in optimizing with respect to the average cost.
2. Large diameter: Queueing systems are usually investigated under a drift condition that makes the system stable, i.e positive recurrent. This condition implies that some states are hard to reach. In fact, for many queueing control problems, the diameter D is exponential in the size of the state space. Even in the simple case of an M/M/1 queue with finite buffer, or equivalently a birth-death process with finite state space and constant birth and death rates, the diameter is exponential the size of the state space.
3. Structured transition matrices. Queueing models describe how jobs join and leave queues, and this yields bounded state transitions. As a result, MDPs on queues have sparse and structured transition matrices.
The regret bounds discussed above and item 2 may suggest that the total regret of existing learning algorithm, when applied to queueing systems, is large. However, they often work well in practice and this bring us to consider the following question: When the underlying MDP has the structure of queueing system, do the diameter D or the number of states actually play a role in the regret?
Our Contribution. In this paper, we examine the previous question with respect to the class of control problems presented in M. Specifically, an infinite sequence of jobs joins service system over time to receive some processing according to the first-come first-served scheduling rule; the system can buffer at most 5 - 1 jobs and in fact it corresponds to an M/M/1/S-1 queue. In addition, each job comes with deadline constraint, and if a job is not completed before its deadline, then it becomes obsolete and is removed from the system. The controller chooses the server processing speed and the objective is to design a speed policy for the server that minimizes its average energy consumption plus an obsolescence cost per deadline miss. Although this may look quite specific, this problem captures the typical characteristies of a controlled queue: i) the transition matrix has the structure of birth and death process with jump probabilities that are affine functions of the state and ii) the reward is linear in the state and convex in the action. For any MDP in this class, defined in full details in Section 3 we show that the diameter is D = 2 2): see Appendix B.3 Thus, without exploiting the particular structure of this MDP, the existing lower and upper bounds do not justify the reason why standard learning algorithms work efficiently here.
We provide slight variation of the learning algorithm UCRL2, introduced in [Л and show in our main result that the resulting regret is upper bounded by O(vF2A7) where Eg is a term that depends on the stationary measure of a reference policy defined Section (31] Importantly, F2 does not depend on S. Thus, efficient reinforcement learning can be achieved independently of the number
2

---

of states by exploiting the stationary structure of the MDP. Let us provide some intuition about our result. First, one may think that any learning algorithm should visit each state a sufficient number of times, which justifies why the diameter of an MDP appears in existing regret analyses. However, this point of view does not take into account the fact that the value of an MDP the scalar product of the reward and the stationary measure of the optimal policy. If this stationary measure is "highly non-uniform", then some states are rarely visited under the optimal policy and barely contribute to the value. In this case, we claim that the learner may not need to visit the rare states that often to get a good estimation the value, and thus may not need to pay for the diameter.
2 Reinforcement Learning Framework
We consider unichain Markov Decision Process (MDP) M (S,A, P.r) r) in discrete time where S the finite state space, A the finite action space, P the transition probabilities and the expected reward function [16]. Let also S := |S| and A == |A] where is the set cardinality operator. The model-based reinforcement learning problem consists that chooses actions to maximize a cumulative reward over a finite time horizon T. At each time step t N, the system is in state 8 E and the learner chooses an action ag E A. When executing at, the learner receives random reward ra (5( ax) with mean r(s,, az) and the system moves, at time step ++ 1, to state s' with probability P(s" 18,, at). The learning algorithm does not know the MDP M except for the sets S and A.
finding a learning algorithm, or learner,
For simplicity, in the following we consider weakly communicating MDPs. Since will be interested in the long-run average cost, this will let us remove the dependence on the initial state for several quantities of interest.
2.1 Undiscounted Regret
Given MDP M, let II == {# S - A) denote the set of stationary and deterministic policies and let
T
p(M := lim T0
E[r(s T (s:))]
(I)
denote the average reward induced by policy т. Since M has finite state and action spaces, we notice that i) The limit in (T) always exists, ii) It does not depend the initial state so when M unichain (16) and iii) The restriction to stationary and deterministic policies is not loss of
optimality [16] Theorem 8.4.5].
Let also p² == p² (M) == max p(M, π) be the optimal average reward. Definition 2.1 (Regret). The regret at time T' of the learning algorithm L
Reg M,L = TP
(2)
t=1
The r is natural benchmark for evaluating the performance of a learning algorithm. In []]. a universal lower bound on Reg(M [M, IL,T) T) has been developed terms of the diameter of the underlying MDP.
Definition 2.2 (Diameter of an MDP). Let S + A be a stationary policy of M with initial state Let T (s',,,,, 8) == minf! 2 0 8; = 8 8'|80 = 8} be the random variable for the first time step in which s' is reached from under Then, say that the diameter of M is
D(M) sya a A
min E T (s'[M, nT
It should be clear that the diameter of an MDP can be large if there exist states that are hard to reach. Within the set of structured MDPs considered in this paper, this will be the case and we will show that D = S( -2). The following result shows that all learning algorithms have a regret that eventually increase with VD.
3

---

Theorem 2.3 (Universal lower bound (T]). For any learning algorithm LL, any natural numbers
S.A 2 10, D 2 20 log S. and T 2 DSA, there an MDP M with S states, A actions, and diameter D such that for any initial state 8 S
L,,,,, T)] Z 0.015V [M, L,
In view of this result, the diameter an MDP and its state space appear to be critical parameters for evaluating the performance of learning algorithm.
2.2 The UCRL2 Algorithm
We now focus UCR1.2, classical reinforcement learning algorithm introduced in [1] that is variant of UCRL [2] While more efficient algorithms have been proposed for the general case (see for example 3 21), we will show that UCRL2 already achieves a very low regret, namely (v independent of so using more refined algorithms can only bring marginal gains.
UCRL2 based on episodes. For each episode k. let l. denote start time. For each state a and action a, let vx(s, a) denote the number of visits of (s, a) during episode & and let NN(ss, a) #(T #(T<t:: t: 8, = 5, ay = a} denote the number of visits of (s, a) until timestep t. Let Let MMg be the confidence set of MDPs with transition probabilities P and rewards F that are "close" to the empirical MDP at episode k, fa and fk. i.e,, á and satisfy
7lgg (2SAtt//))
V(s,a), (F(s,a) Fx(s, S Fmax
max N1, ())
14.5 (2At./6)
((s,a), (p((ls,)) P1 a)ls,))l1
(5)
max a))
With these quantities, a pseudocode for UCRL2 is given in Algorithm 1 We notice that UCRL2 relies on Extended Value Iteration (EVI), that is a variant of the celebrated Value Iteration (VI) algorithm [16]; for further details about EVI, point the reader III Section 3.1]. Let comment on how UCRL2 works. There are three main steps. First, at the start of each episode, UCRL2
Algorithm 1: The UCRI.2 algorithm.
Input: A confidence parameter E (0, S and A. Output:
Set É := and observe 81
for episodes l = 1,2.... do
3
Compute the estimates f(s, a) and pa |s, a) as in Use "Extended Value Iteration" to find policy ä and an optimistic MDP M, E M₁ such that
p p(Mg. #x)
max pMM MEMME
(6)
VT
while vn(se, (s:)) < max (1 Ne, (st, (s:)) do Choose action a; it (8t), obtain reward ri and observe 81+1; (n ax) vn(s,, ae) t:= ++1;
end
10 end
computes the empirical estimates
Dhe-1 r (a==oa a)) max (1, (s,
pE(s'ls,a) Σne (0
max (1, NI, (s,
of the reward and probability transitions, respectively, where 1g is the indicator function of E. Then, it applies Extended Value Iteration (EVT) find a policy गेz and an optimistic MDP MA M, such that (6) holds true. Finally, it executes policy से until finds a state-action pair (8, a) whose count within episode & is greater than the corresponding state-action count prior episode k.

---

3 Controlled Birth and Death Processes for Energy Minimization
Now, we focus on a specific class of MDPs that has been introduced in []. which provides a rather general example of controlled birth and death process with convex costs the actions and linear rates. We will denote by M the set of MDPs with the structure described below. The MDPs in .M have been proposed to represent Dynamic Voltage and Frequency Scaling (DVFS) processor executing jobs with soft obsolescence deadlines. Here, jobs arrive according to a Poisson process with rate [0, Amax] in buffer of size S - 1. If the buffer is full and job arrives, then the job is rejected. Each job has a deadline and a size, i.e., amount of work, which are exponentially distributed random variables with rates j [0, MMmax] and one, respectively. Job deadlines and sizes are all independent random variables. a job misses its deadline, which is real time constraint activated at the moment of its arrival, it is removed from the queue without being served and cost C' is paid. The processor serves jobs under any work-conserving scheduling discipline, c.g., first-come first-served, with a processing speed that belongs to the finite set ( speed policy that minimizes the sum of the long term power dissipation and the cost induced by jobs missing their deadlines. When the processor works speed E Amsx it processes units of work per second while its power dissipation is w(a).
Amax): J. The objective is design
After uniformization, it is shown in [1 that this control problem can be modeled as an MDP in discrete time with a "birth-and-death" transition matrix of size S. Specifically, we have an MDP M A, r.r) where S {0, ,.,...,,.. system, and A = {O..... Amax ). with a E A representing the processor speed. Then, the transition probabilities under policy æ are given by
1}, with S representing the number of jobs in the
if < if > 0 and j = ii
1 and j = =i+1 +1
T (T(()
+ip)
Pa)(a)=
P.
if j otherwise,
0
where U = Amax + (S Ummx + Amax is uniformization constant, Pa: (U - -;-; - n (i))
the decaying arrival rate. We have replaced the constant arrival rate by decaying arrival rate A because we want to learn optimal policy that does not exploit the buffer size - 1; see [ for further details. For conciseness, Figure T displays the transition diagram the Markov chain induced by policy n.
and A := A (1- 5-T)
Pa
d U
i+1
S-1
T (ifu + xi))
Figure 1: Transition diagram of the Markov chain induced by policy æ of an MDP in M.
Finally, the reward is combination of C, the constant cost due to departing job missing its deadline and w(a), an arbitrary convex function of a, giving the energy cost for using speed a. The immediate cost c(s, a) in state under action is random variable whose value is w(a) C' with probability áu/U (missed deadline) and wa) otherwise. To keep in line with the use of rewards instead of costs, we introduce bound on the cost, Tmax C' + (Xmmax)) so that the reward in state under action is a positive and bounded random variable given by
r(s, a) == Tmax - c(s.a).
(8)
p (*(M) is the optimal average cost and p(M, is the average cost induced by policy where belongs to the set of deterministic and stationary policies II. Since the underlying
As in Section 2.1
5

---

Markov chain induced by any policy is ergodic, we observe that
5
pM,
Σ [sr(s, (s)))
==0
where m is the stationary measure under policy и. In [. it has been shown that the optimal policy unique and will be denoted by n².
3.1 Properties of M
the following, we will use the "reference" (or bounding) policy =s)s) = for all E S, which thus assigns speed to all states. This policy provides stochastic bound on all policies in the following sense. Let 87 be the state under policy и and let Sat denote the stochastic order [18]; given two random variables X and Y on R,, we recall that X Sa Y if P(X 2 s) S P(Y s) for all s.
Lemma 3.1. Consider an MDP in M. For all and policy a E II. sy Sat si provided that 80 Set s0
Proof. (sketch) The proof follows by simple coupling argument between the two policies. Roughly speaking, each time the Markov chain under π decreases from s to because of the speed π (s). stays state s under policy x²
Therefore, P( 2 8) S P(5 2 8) for all s and f, which also implics that the respective stationary measures are comparable, i.e., Ei=o m. S Eizs mē".
Let us now consider (s), the bias at state of the optimal policy n², defined by
H(s) = E,.
Σ (r oo 1=1
x =5((5)))) - -
.g = vO so (10)
Let also (H(s) = (s) ((s 1) be the local variation of the bias.
The following result was shown
Lemma 3.8].
Lemma 3.2. The local variation of the bias, (H()), (s), is negative, decreasing in and bounded:
(s)(s) < (s) with < (ss) s C for all s S S
Both m and A will play a major role in our analysis the regret.
3.2 Applying UCRL.2 in M
We assume that the bounds Amax and Pmax are fixed so that Tmax is known to the learner. This is classical assumption, often replaced by assuming that rewards live in [0, 1].
In the remainder, we will apply UCRL2 over an MDP in M with a change the confidence bounds take into account the support of P. The confidence bounds in (resp. (5)) are replaced by
llgg(AAr) max [.N,,, (8.0) (resp. ma, (s,a)) We also impose that the confidence set M₁ only
log((AAt))
Tmmx
contains matrices with the same support as P. Removing 5 in the confidence bounds does help to
reduce the regret. However, by using existing analysis, this only removes a factor VS in the regret bound (for example, see [4]).
Finally, note that UCRL2 does not benefit from the parametric nature the MDPs in M. which essentially defined by three parameters (A, i and C)) and the real convex function wr wr.-).
4 Regret of UCRL2 on M
Our objective to develop an upper bound on the regret of the learning algorithm UCRL2 when applied to MDPs in our class M. The driving idea is to construct bound that exploits the structure of the stationary measure all policies, as they all make some states hard to reach, and to control the number of visits to these states to get new type of bound.

---

4.1
Main Result
The following theorem gives an upper bound on the regret that does not depend on the classical parameters such as the size of the state space nor on global quantities such as the diameter of the MDP nor the span of the bias of some policy, Instead, the regret bound below mainly depends on the weighted second moment of the stationary measure of the reference policy n², which is bounded independently of the size of the state space.
We consider the policy x max such that x (s) Amax for all 8 and m ma its stationary measure.
Let us also recall that m= is the stationary measure of the Markov chain under policy . (T) 0 for all s and that A
Ft is a function bounding the local variations of the optimal bias. Let
Eg = F E (A + rmax)) ( with f 8 + max(L.a(s-1)) and := E.es f(s)= Here, Eg
(A())
is closely related to the second moment of the measure m weighted by the bias variations and the maximal reward.
Theorem 4.1. Let M M. Define Qunax == := (mmmao(s_1) log
(S
E [Reg (M, UCRL2, 7)] & 19 AZ log (2AT)
+ 97T max D2 SA 1 log (2AA)). (11)
Here, Eg S 12r max (1 (1+ ) that the regret satisfies
E [Reg M, UCRL2, T)] O ''max V AT
(1
12) 122
log (AT)
Before giving a sketch of the proof, let us comment on the bound 11 Although the first term is of order /T with a multiplicative constant independent of S as desired the second term, of order T contains very large terms. Its interest however, lies in the novel approach used in the proof that uses the stationary behavior of the algorithm.
4.2 Comparison with Other Bounds
Let us compare our upper bound with the ones existing in the literature, as we claim that ours of different nature.
First, let us compare with the bound given in [11]. which states that with probability 1 8, Re S 34DS AT AT (T) for any T > 1. For any M M, the diameter grows as S (see Appendix B.3) thus this bound is very loose here. More recent works have improved this bound by replacing the term D by the local diameter of the MDP (5). In Appendix B.3 we show that the local diameter grows again as S for any M E .M, and thus these results do not yield significant improvements. Other papers show that the diameter can be replaced by the span of the bias, 7 25 This has a big impact because the span of the bias, for any M M, is linear in S (instead of S for the diameter); see Appendix B.3 However, this is still not as good as the bound given Theorem 4.1 which independent of S.
Now, let us compare with existing bounds for parametric MDPs, as mentioned in the introduction. The d-linear additive model, d < S, introduced in [12] assumes that P(.|s, a) (Ø(s. a), a),0()) 0())). where o(s, a) is a known feature mapping and 0 is unknown measure on Rd This form of P(-Is, a) implies that the transition kernel is of rank d. Unfortunately, this property does not hold true in birth and death processes. In fact, the kernel of any M E MM has almost full rank under all policies. The linear mixture model introduced in [26] assumes instead that P(s'|s, a) = (ó(s'la (s, a), 0). E Rdd. This is more adapted our case, which can be (almost) seen as a linear mixture model of dimension d = 3. The bound on the discounted regret of the algorithm proposed in (6) is Reg(M, 7) < dvT/(1 7)2 where 7 is discount factor. In contrast to our work, this regret analysis holds for discounted problems, where we remark that both the diameter and the span are irrelevant. On the other hand, both are replaced by term of the form (I -2, which implies
7

---

that the previous bound grows to infinity as f 1. More recently, regret bound of Odd'DT) has been proven (3 in the undiscounted case, that the case considered our work. However, the algorithm presented in that reference highly depends on the diameter and is unsuitable for MDPs with birth and death structure.
Finally, our bound depends on the second moment of the stationary measure of reference policy, ie.. Lig, which can be bounded independently of the state space size. This structurally different from the ones existing in the literature. We believe that this structure holds as well in class of MDPs much larger than M. particular, if m the stationary measure of some bounding/reference policy, and if the critical quantity Em [A f] is small for a well chosen function f. then the regret of learning algorithm navigating the MDP should also be small. A deeper analysis is left as future work.
4.3 Sketch of the Proof
Our proof for Theorem 4.1 is technical and is provided in the supplementary material. this section, present the main ideas and its general structure. It initially relies on the regret analysis of UCRL2 developed in [T], and the differences are highlighted below. First, we consider the mean rewards and split the regret into episodes separately treat the cases where the true MDP is in the confidence set of optimistic MDPs Mr or not. Thus, let Ra == Es, (k (e - T(s, a)) denote the regret in episode k. This split can be written:
EE [Reg(M,, S EE [ + EE [Rout],
where Rin :- E. RRlMEM, and Rout En R..MMM.
To control Rout, we use, as in M.. the stopping criterion and the confidence bounds. This gives E [Rout] I S, so that the regret due to episodes where the confidence regions fail will be negligible next to the main terms. Then, when the true MDP belongs to the confidence region, we use the properties of Extended Value Iteration (EVI) to decompose Rin into
-( (s(s, (F - r(s,a)) + Σv
Pk 11)
1) h4
Ev V. PR -11 1) dg + 2r max
MR (8, a)
th
k
k.,.0
Brewards
Buino
Rgvi
where is the vector of the state-action counts 1/k 's P& and h& are respectively the transition matrix and the bias in Mr under policy Tu. and dy is the profile difference between the last step of EVI and the bias (see Appendix AA.).
We now show how to handle Reewards. REVI, Ruias- First, we deal with the terms that do not involve the bias. Using the confidence bound the rewards (see Appendix A.3.I
Uk (8,
Brewards S 2max2 2ians2/2loge 222ooo (2AT)
(12)
max {1, Ne,
8.0
Now, let consider RgvI. Since dy becomes arbitrarily small after enough iterations of EVI (see e
Appendix A.1 p. for T 2 2AT we get
Ph (k a)
REVI Tmax 2v log 2AT)
Σ
(13)
max (1, Ni, (s.
5,a
The analysis of Roins is different from the one in II: While in I1 the bias is directly bounded by the diameter, the transitions in the true MDP under ih. Roiss is further decomposed into:
the variations of the bias control the regret more precisely. Using Pk, i.e.
Σ Vk Pr -P h Σ ve P -
PPx
[hu h")
+
Σ k
(P hss
Berana
Raie
Rep
The term Rep can be treated in a similar manner as in by bounding the bias terms with the diameter apply Azuma-Hogfidding inequality (see Appendix A.3.5). Here, we obtain
8T
Repl S SAD Tix log,
SA

---

Next, we show in A.3.2 that Raif does not contribute to the main term of the regret. This is one of the hard point in our proof. First, linear algebra techniques are used to bound ||h h01l by ma2rmaxD
P* + || rool)))) Each norm is then bounded using Hoeffding inequality. This introduces the special quantity N2, (IRR, T& (xx)) that yields to the worst confidence bound in episode k. Then, adaptation of McDiarmid's inequality Markov chains is used show that Ni. (2y, (2+)) 2 (tx+1 tx) Im m (S 1)/2 with high probability, where " - 1) is the stationary measure of state S under the uniform policy mmx (s) Amax. This eventually implies
that
E |aurl - 96r 96rmax D max Qmax. T2/4] log (2AT),
where Qmax :=
10D
log
10D
m
Then, to deal with the main term Rtraus: exploit the optimal bias. The unit vector being in the kernel of Pk- - Pk.
rewrite:
Rtrans ΣΣΣ un (s, (s)) (fx (x)) p fx)) -n(())))('sss)))
and, thus, using the confidence bound and the bounded variations of the bias,
A (x
Rerans S 2lg (2AT)
ΣΣ
max [1, Nr, (8)
k s,a
We can now aggregate Rurass, Rrewards and REVI compute the main term of the regret (see Appendix A.3.4). A.3.4) Here, the key ingredient is to bound
(A(s) Tmax (
independently of S. This is the second main difference with [Л]. Instead of exploring the MDP uniformly, we know that the algorithm will mostly visit the first states of the MDP, regardless of the chosen policy. As shown in 11, for fixed state
(s a)
ΣΣ
S (N
mL No, (s, a}}
Now, instead of summing over the states, we can use properties of stochastic ordering to compare the mean number of visits of state with the probability measure m=* here, strongly rely the birth and death structure of the MDPs in M. For any non-negative non-decreasing function f f S - RR we obtain
E
Σ (6)).(s))
< 1 f(s)m (s). #20
(14)
#20
Let us choose f : 8 +
La and let = f(s s 3(C + rmax) Let also (A(a)
Eg = FE,,. [A + Tmax )2 fl. Then.
(A(s) + mmax) /max(1, No, (s,
S <3v EZAT.
In Appendix A.3.4 we further show that Eg < 3(C + rmaa)) (1+ ). Therefore, for the three main terms, obtain
Rtrans + Rrewards + REVil S 19 ETAT log (2AT)
(15)
and we conclude our proof by combining all of these terms.

---

Conclusions
For learning in a class of birth and death processes, we have shown that exploiting the stationary measure in the analysis of classical learning algorithms yields a K regret, where K only depends on the stationary measure of the system under a well chosen policy. Thus, the dependence on the size of the state space as well as on the diameter of the MDP its span disappears. We believe that this type of results can be generalized to other cases such as optimal routing, admission control and allocation problems queuing systems, as the stationary distribution under policies is uneven between the states.
References
[1] Jonatha Anselmi, Bruno Gaujal, and Louis Sébastien Rebuffi. Optimal Speed Profile of a DVFS Processor under Soft Deadlines. Performance Evaluation, 152, December 2021.
[2] Peter Auer and Ronald Ortner. Logarithmic online regret bounds for undiscounted reinforcement learning. In B. Schölkopf. Platt, and T. Hoffman, editors, Advances in Neural Information Processing Systems, volume 19. MIT Press, 2006.
[3] Mohammad Gheshlaghi Azar, Ian Osband, and Rémi Munos. Minimax regret bounds for reinforcement learning. In International Conference on Machine Learning, pages 263-272.
PMLR, 2017.
[4] Mohammad Gheshlaghi Azar, Ian Osband, and Rémi Munos. Minimax regret bounds for reinforcement learning. In International Conference on Machine Learning, pages 263-272, 2017.
[5] Hippolyte Bourel, edalric-Ambryn Maillard, and Mohammad Sadegh Talebi. Tightening exploration in upper confidence reinforcement learning. In Proceedings of the 37th International Conference on Machine Learning. ICML'20. JMLR.org. 2020.
[6] Craig Boutilier, Richard Dearden, and Moisés Goldszmidt. Stochastic dynamic programming with factored representations. Artif. Intell., 121(1-2):9--07, aug 2000.
[7] Ronan Fruit, Matteo Pirotta, Alessandro Lazaric, and Ronald Ortner. Efficient bias-span- constrained apploration-eeploiittioon in reinforcement learning. 02 2018.
[8] Nicolas Gast, Bruno Gaujal, and Kimang Khun. Reinforcement learning for Markovian bandits: Is posterior sampling more scalable than optimism? Technical Report hal-03262006, HAL-Innia, June 2021.
[9] Carlos Guestrin, Daphne Koller, Ronald Parr, and Shobha Venkataraman. Efficient solution algorithms for factored MDPs. Journal of Artificial Intelligence Research, 19(1):399 468, October 2003.
[10] Isse C. F. Ipsen and Carl Dean Meyer. Uniform stability of markov chains. SIAM Journal on Matrix Analysis and Applications, 15:1061-1074, 1994.
[11] T. Jaksch, R. Ortner, and P. Auer. Near-optimal regret bounds for reinforcement learning. Journal of Machine Learning Research, 11(4):5663-1600 2010.
[12] Chi Jin, Zhuoran Yang, Zhaoran Wang, and Michael Jordan. Provably efficient reinforcement learning with linear function approximation. In Jacob Abernethy and Shivani Agarwal, editors, Proceedings of Thirty Third Conference on Learning Theory, volume 125 of Proceedings of Machine Learning Research, pages 2137-2143. PMLR, 09-12 Jul 2020.
[13] Quan-Lin Li, Jing- Yu Ma, Rui-Na Fan, and Li Xia. An Overview for Markov Decision Processes in Queues and Networks, pages 44-71. Springer Singapore, Singapore, 2019.
[14] Ian Osband and Benjamin Van Roy. Near-optimal reinforcement learning in factored MDPs. In Proc. of the 27th Int. Conf. on Neural Information Processing Systems- Volume NTPS' 14, pages 604-604660 612, Montreal, Canada, December 2014. MIT Press.
10

---

[15] Ian Osband, Benjamin Van Roy, and Zheng Wen. Generalization and exploration via random- ized value functions. In Proceedings of the 33rd International Conference on International Conference Machine Learning Volume 48, ICMI116, page 2377-2386. JMLR.org. 2016.
[16] Martin L. Puterman. Markov Decision Processes: Discrete Stochastic Dynamic Programming. Wiley Series in Probability and Statistics. Wiley, edition, April 1994.
[17] Aviv Rosenberg and Yishay Mansour. Effici-Ef Reinforcement Learning in Factored MDPs with Unknown Structure. 20XX::2000900988 [es, stat), September 2020.
[18] Moshe Shaked and George Shanthikumar. Stochastic orders and their applications. Academic Pr, 1994.
[19] R. S. Sutton and A. G. Barto. Reinforcement Learning: An Introduction. MIT Press, Cambridge, MA, 1998.
[20] Yi Tian, Jian Qian, and Suvrit Sra. Towards minimax optimal reinforcement learning in factored markov decision processes. In Proceedings of the 34th International Conference Neural Information Processing Systems, NIPS 20, Red Hook, NY, USA, 2020. Curran Associates Inc.
[21] Aristide Tossou, Debabrota Basu, and Christos Dimitrakakis. Near-optimal optimistic reinforce- ment learning using empirical bernstein inequalities, 2019.
[22] Neil Walton and Kuang Xu. Learning and information in stochastic networks and queues, 2021.
[23] Yue Wu, Dongruo Zhou, and Quanquan Gu. Nearly minimax optimal regret for learning infinite-horizon average-reward mdps with linear function approximation. In Gustau Camps- Valls, Francisco J. Ruiz, and Isabel Valera, editors, Proceedings of 25th International Conference on Artificial Intelligence and Statistics, volume 151 of Proceedings of Machine Learning Research, pages 3883-3913. PMLR, 28-30 Mar 2022.
[24] Ziping Xu and Ambuj Tewari. Reinforcement learning in factored mdps: Oracle-efficient algo- rithms and tighter regret bounds for the non-episodic setting. In Hugo Larochelle, Marc' Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan- Tien Lin, editors, Advances in Neural Information Processing Systems 33: Annual Conference Neural Information Processing Systems 2020, NeurlPS 2020, December 6-12, 2020, virtual, 2020.
[25] Zihan Zhang and Xiangyang Ji. Regret minimization for reinforcement learning by evaluating the optimal bias function, 2019.
[26] Dongruo Zhou, Jiafan He, and Quanquan Gu. Provably efficient reinforcement learning for discounted mdps with feature mapping. In Marina Meila and Tong Zhang, editors, Proceedingss of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 12793-12808 PMLR, 24 Jul 2021.


Reviews:
[{"review_id": "zafrLo7W4q", "reviewer": "Reviewer_NyfN", "summary": "This paper proposed a new undiscounted MDP setting with a birth and death structure. Then the authors modified the classical UCRL2 algorithm to achieve an $\\widetilde{O}(\\sqrt{E_2AT})$, which has no dependence on the number of the states and the diameter. This is achieved by leveraging the special structure of the queueing system. ", "questions": "- I didn't see why $E_2$ can be interpreted as the second moment from the definition in Line 225. Can the authors elaborate more on this point?\n- What is the upper bound on $E_2$?", "limitations": "I am not aware of any potential negative societal impact", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- This paper formulated queueing as an MDP with birth and death structure and proposed an efficient algorithm, which is important as the queueing system is widely applied in many different areas. \n- The regret bound has no dependence on the number of states or the diameter thanks to the special structure. On the other hand, it depends on $E_2$, which is a weighted second moment of the stationary measure of a reference policy. This result is interesting as it is specialized to the problem structure. \n\nWeakness:\n- The writing part can be improved. I didn't understand why $E_2$ can be interpreted as the second moment and why dependence on the number of states or the diameter can be removed. As a result, I am not certain about the correctness o this paper. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "PvvaLmINn5d", "reviewer": "Reviewer_sAR5", "summary": "This paper revisits the regret of undiscounted reinforcement learning in MDPs with a birth and death structure. Specifically, they consider a controlled queue with impatient jobs and the main objective is to optimize a trade-off between energy consumption and user-perceived performance. They exploit the structure of the MDP and give a tighter upper bound on the regret of a slightly-tweaked version of the classical learning algorithm UCRL2.  Their bound is asymptotically independent of the number of states and of the diameter. ", "questions": "1. Are there any lower bounds on the setting considered in this paper?\n2. Can the authors conduct numerical experiments to shoe the effectiveness of the method?", "limitations": "The authors have adequately addressed the limitations and potential negative societal impact of their work.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\nOver all, this paper studies a special case of MDP with a birth and death structure. The MDP case is commonly used in practice, and is worth studying. In theoretical analysis, the authors studies a slightly-tweaked version of the classical learning algorithm UCRL2, which is relatively simple and widely used. By exploiting the structure of the MDP, they provide a much tighter upper bound on the performance of UCRL2, which, surprisingly, is independent of the number of states, and improves previous naive results which exponentially depends on S. This paper is interesting, and is important to RL theory.\n\nWeaknesses:\n1. There are no corresponding lower bounds, so we do not know whether the upper bound is tight or not.\n2. It will be better if the authors can provide experiment results to support their algorithm.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "KBkTxotWPBq", "reviewer": "Reviewer_SMUj", "summary": "This paper studies RL in undiscounted MDPs. The authors break the minimax lower bound which depends on the MDP diameter (shown to be as large as $\\Omega(S^S)$) by restricting the MDPs to a structured class of birth-death processes and showing that a tweaked version of the classic UCRL2 algorithm achieves an upper bound independent of the diameter and state size. This bound is obtained by carefully analyzing the stationary measure for this restricted MDP class and exploiting its high non-uniformity.", "questions": "Why did you consider UCRL instead of UCB?", "limitations": "The work is theoretical.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths** \n\n- The problem studied in this paper is related to finding structures in RL that facilitate efficient learning is an important topic. Many existing works in finite-sample analysis of RL have focused on algorithms that are nearly optimal in a minimax sense, where the optimality is measure w.r.t. the most difficult MDP. However, this does not explain why RL works well in certain environments. Studying structed RL is important to bridge the gap between theory and practice and this paper contributes to this line of research.\n- The paper considers a specific structure (birth death) related to queueing systems, which itself has important applications and seems to be motivated by practical implications. Moreover, this structure is different from usual structures considered in RL theory literature such as low rank MDPs. Although the minimax lower bound depends on diameter (which is large for birth death process), the paper carefully analyzes regret for this restricted class of MDPs to identify whether there is a diameter or state size dependency. The authors show that a variant of UCRL2 achieves a regret independent of these parameters. \n- The technical contributions are insightful and may inspire future work. For instance, although UCRL2 does not exploit the parameteric form of MDP, it still achieves a regret independent of diameter and state size. Another technique used in the regret guarantee is exploiting the highly non-uniform stationary measure in the restricted MDP class.\n- The paper is very well-written and thorough comparison with prior related theoretical results and their implications is provided. \n\n**Weaknesses**\n\n- The structure considered in this work may be more limited compared to other structures in prior works such as factored MDPs, which may limit the significance and impact of this work.\n- The paper shows that a variation of UCRL2 achieves a regret independent of diameter and state size. It remains unclear whether the tweak was necessary, the regret is optimal, and other popular methods such as UCB also enjoy similar guarantees. Additional theoretical and/or empirical results can strengthen the work. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "3s0aze7khEX", "reviewer": "Reviewer_Sx4m", "summary": "This work studies RL on a special class of MDPs called the birth and death process (BDP for short). The authors claim that by applying the UCRL2 algorithm to BDP, a state-independent regret can be obtained, which improves the existing best-known regret bounds that depend on the state space cardinality explicitly. ", "questions": "+ Can the authors highlight their theoretical contributions?\n+ Can the authors compare their work and Wu et al., 2022? ", "limitations": "Yes. ", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n+ The presentation is clear. \n+ The theoretical results are technically sound. \n\nWeaknesses:\n\n+ The importance of this work remains unclear. This work does not propose either a new algorithm or a new proof approach. It seems that the only difference between their algorithm and proof and those of [10] is some more refined analysis which depends on the quantity $r_{max}$, as they showed in (12, 13). However, the difficulty to analyze it is unknown, and I feel it is not important enough to be the main contribution of a NeurIPS paper. \n\n+ The comparison of some highly related works lacks. In Section 4.2, the authors claim that BDPs can be regarded as a special class of linear mixture MDPs, and existing algorithms for linear mixture MDPs are for discounted MDPs and can not be directly applied to BDPs . It is not true since Wu et al., 2022 have already studied linear mixture MDPs with average rewards. Given the existing results, it is hard to judge the contribution of this work. \n\n\nWu, Y., Zhou, D., & Gu, Q. (2022, May). Nearly minimax optimal regret for learning infinite-horizon average-reward mdps with linear function approximation. In International Conference on Artificial Intelligence and Statistics (pp. 3883-3913). PMLR.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept