Quantifying the Cost of Learning in Queueing Systems
Authors: Daniel Freund
Thodoris Lykouris
Wentao Weng
Venue: NeurIPS 2023 poster (2023)
Keywords: bandits
learning
queueing systems
optimal control

Abstract: Queueing systems are widely applicable stochastic models with use cases in communication networks, healthcare, service systems, etc. 
Although their optimal control has been extensively studied, most existing approaches assume perfect knowledge of the system parameters. Of course, this assumption rarely holds in practice where there is parameter uncertainty, thus motivating a recent line of work on bandit learning for queueing systems. This nascent stream of research focuses on the asymptotic performance of the proposed algorithms. 

In this paper, we argue that an asymptotic metric, which focuses on late-stage performance, is insufficient to capture the intrinsic statistical complexity of learning in queueing systems which typically occurs in the early stage. Instead, we propose the *Cost of Learning in Queueing (CLQ)*, a new metric that quantifies the maximum increase in time-averaged queue length caused by parameter uncertainty.
We characterize the CLQ of a single-queue multi-server system, and then extend these results to multi-queue multi-server systems and networks of queues. In establishing our results, we propose a unified analysis framework for CLQ that bridges Lyapunov and bandit analysis, provides guarantees for a wide range of algorithms, and could be of independent interest.

Quantifying the Cost of Learning in Queueing Systems
Daniel Freund MIT Cambridge, MA 02139 dfreund@mite t..mmiteee
Thodoris Lykouris MIT Cambridge, MA 02139 lykouris@mit. edu
Wentao Weng MIT Cambridge, MA 02139 wwengdmit. edu
Abstract
Queueing systems are widely applicable stochastic models with use cases com- munication networks, healthcare, service systems, etc. Although their optimal control has been extensively studied, most existing approaches assume perfect knowledge of the system parameters. Of course, this assumption rarely holds in practice where there parameter uncertainty. thus motivating recent line work bandit learning for queueing systems. This nascent stream of research focuses on the asymptotic performance of the proposed algorithms.
In this paper, we argue that an asymptotic metric, which focuses on late-stage performance, insufficient to capture the intrinsic statistical complexity learning in queueing systems which typically occurs in the early stage. Instead, we propose the Cost of Learning in Queueing (CI.Q), a new metric that quantifies the maximum increase in time-averaged queue length caused by parameter uncertainty. We characterize the CLQ of a single-queue multi-server system, and then extend these results to multi-queue multi-server systems and networks of queues. In establishing our results, we propose a unified analysis framework for CLQ that bridges Lyapunov and bandit analysis, provides guarantees for wide range of algorithms, and could be of independent interest
Introduction
Queueing systems are widely used stochastic models that capture congestion when services are limited. These models have two main components: jobs and servers. Jobs wait in queues and have different types. Servers differ in capabilities and speed. For example, in content moderation of online platforms (28), jobs are user posts with types defined by contents, languages and suspected violation types; servers are human reviewers who decide whether post is benign or harmful. Moreover, job types can change over time upon receiving service. For instance, in a hospital, patients and doctors be modeled as jobs and servers. A patient in the queue for emergent in the queue for surgery after seeing a doctor at the emergency department 3 That is, queues can form network due to jobs transitioning in types. Queueing systems also find applications in other domains such as call centers [16], communication networks (36] and computer systems [17..
become a patient
The single-queue multi-server model is simple example to illustrate the dynamics and decisions in queueing systems. this model. there is one queue and K servers operating in discrete periods. In each period,
job arrives with probability X. Servers have different service rates (1. AKK- The decision maker (DM) selects a server to serve the first job in the queue there is any. server is selected, the first job in the queue leaves with probability 1tj- The DM aims minimize the average wait of each job, which is equivalent to minimizing the queue length. The optimal policy thus selects the server with the highest service rate μ max, μy; the usual regime of interest is one where the system stabilizable, i.e., μ* > X, which ensures that the queue length does not grow to
A full version of this paper [12 can be found at httppp::///aar..oo//b///////./00
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

infinity under an optimal policy, Of course, this policy requires perfect knowledge of the service rates, Under parameter uncertainty, the DM must balance the trade-off between exploring a server with an uncertain rate exploiting a server with the highest observed service rate.
A recent stream of work studies efficient learning algorithms for queueing systems. First proposed by [41], and later used by [24] queueing regret is a common metric to evaluate learning efficiency in queueing systems. In the single-queue multi-server model, let QT,, πT) and (Z') be the number of jobs in period I'' under a policy and under the optimal policy respectively. Queueing regret is defined as either the last-iterate difference in expected queue length, i.e., E [Q(T., .T) - Q" (T) 44 or
the time-average version | E Q(t, x) Q (t)
B8. In the stabilizable case (A μ²), the
goal is to bound its scaling relative to the time horizon; examples include o(T) ((1/T)
and ( 38
In this paper. we argue that an asymptotic metric for per-period queue length does not capture the statistical complexity of learning in queueing systems. This is because, in a queueing system, learning happens in initial periods while queueing regret focuses only on late periods. Whereas cumulative regret in multi-armed bandits is non-decreasing in T. the difference in queue lengths between learning policy and the benchmark optimal policy eventually decreases since the policy eventually learns the parameters (see Figure This leads to the two main questions of this paper:
What metric characterizes the statistical complexity of learning in queueing systems?
What are efficient learning algorithms for queueing systems?
Our work studies these questions in general queueing systems that go beyond the single-queue multi-server model and can capture settings such the hospital and content moderation examples.
Benchmark
Q-UCB
120
120
100
Time Time averagee queue length
100
Cost Leaminng in Queueing
80.
80-
Queue length
40
40-
20
20-
Queuning regrot
10a
10
10
10a
10
10
10a
16
10a
10a
16*
10
Perfods
Perlods
Figure 1: Expected per-period and time-averaged queue lengths of UCB and Q-UCB 24 in single- queue setting with K 5, X = 0.45, μ (0.045, 0.35, 0.35, 0.35, 0.55); results are averaged over 50 runs. The difference between both algorithms'' queue lengths is indistinguishable asymptotically (left figure) though they clearly differ in their learning efficiency for early periods as illustrated by Cost of Learning in Queueing, the metric that our work introduces (right figure).
Cost of learning in queueing. Tackling the first question, we propose the Cost of Learning in Queueing (CLQ) capture the efficiency of a learning algorithm in queueing systems. The CLQ of a learning policy is defined as the maximum difference of its time-averaged queue length and that of any other policy (with knowledge of parameters) over the entire horizon (see Fig TigTon on the right). In contrast to queueing regret, CLQ is 1) finite-time metric that captures the learning efficiency in early periods and focused on time-averaged queue length instead of per-period queue length. This is favorable as for any periods 1, ..... T, the time-averaged queue length is related to the average wait time by Little's Law. The formal definition of CL.Q can found in Section
Lower bound of CLQ (Theorem 1..
To characterize the statistical complexity of learning in queueing systems, we consider the simplest non-trivial stabilizable setting that involves one queue and servers. It known that the queue length scales as O(1/e) under the optimal policy, where μ² A is the traffic slackness of the system. Fixing and the number of servers K, we establish

---

a worst-case lower bound 92( K) of CLQ. That is, for any E, K and a fixed policy, there always exists setting of arrival and service rates, such that the CLQ of this policy is at least Q2 K Combined with the ((1/E) optimal queue length, this lower bound result shows that the effect of learning dominates the performance of queueing systems when K is large (as it may increase the maximum time-averaged queue length by factor of K). This is shown in Figure [
(right) where the peak of time-averaged queue lengths of the optimal policy with knowledge of parameters is much lower than that of the other two policies (our Algorithm| T and Q-UCB (24).
An efficient algorithm for single-queue multi-server systems (Theorem 2)
Given the above
lower bound, we show that the Upper Confidence Bound (UCB) algorithm attains an optimal CLQ up to logarithmic factor in the single-queue multi-server setting. Our analysis is motivated by Fig. 1 (right) where the time-averaged queue length initially increases and then decreases. Based on this pattern, we divide the horizon into an initial learning stage and a later regenerate stage.
In the learning stage, the queue length increases similar to the multi-armed bandit regret. We formalize this observation by coupling the queue under a policy with nearly-optimal queue and show that their difference is captured by the satisficing regrer of æ. Satisficing regret resembles the classical multi-armed bandit regret but disregards the loss of choosing nearly optimal server (see Eq. (o); this concept is studied from a Bayesian perspective in multi-armed bandits [32 Nevertheless, our result in the learning stage is not sufficient as the satisficing regret eventually goes to infinity.
In the regenerate stage, queue lengths decrease as the policy has learned the parameters sufficiently well; the queue then behaves similarly as under the optimal policy and stabilizes the system. To capture this observation, we use Lyapunov analysis and show that the time-averaged queue length for the imitial T periods scales as the optimal queue length. but with an additional term depending on the second moment of satisficing regret divided by T. Hence, as T increases, the impact of learning gradually disappears. Combining the results in the learning and regenerate stages, we obtain a tight CLQ bound of UCB for the single-queue multi-server setting.
Efficient algorithms for queueing networks (Theorem We next generalize the above result to queueing networks that include multiple queues, multiple servers, and transitions of served jobs from servers to queues. For this setting, we build on the celebrated BACKPRESSURE policy that stabilizes a queueing network with knowledge of system parameters [39]. We propose BACKPRESSUREE UCB as a new algorithm to transform BACKKRESSUS
into a learning algorithm with appropriate estimates for system parameters and show that its cost of learning scales near-optimally as ((1E) with respect to the traffic slackness (Definition 2). This result extends framework for single-queue multi-server settings through a coupling approach that reduces the loss incurred by learning in a high-dimensional vector of queue-lengths scalar-valued potential function. To the best of our knowledge, this is the first efficient learning algorithm for general queueing networks (see related work for a discussion).
Related work A recent line of work studies online learning in queueing systems To capture uncertainty in services, [4] studies a single-queue setting in which the DM selects a mode of service in each period and the job service time varies between modes (the dependence is a priori unknown and revealed to the DM after the service). The metric of interest is the queueing regret, i.e., the difference of queue length between an algorithm and the optimal policy, for which the authors show a sublinear bound. (24) considers the same single-queue multi-server setting ours and show that a forced exploration algorithm achieves queueing regret scaling of Ó(1/T) (under strong structural assumptions this result extends to multiple queues). (38] shows that by probing servers when the queue is idle, it is possible to give an algorithm with queueing regret converging O(1/T). However, with respect to the traffic slackness E > +0t both bounds yield suboptimal CLQ: [24]
gives at least (l)==²) and (38) gives at least O(1/e*) (see Appendices A. A.2 in (12). In the analysis of (24), foreed exploration is used for low adaptive regret, i.c., regret over any interval
19: no such guarantee is known for adaptive exploration. But as noted by our Figure I and 24 exploration
Figure 2], an adaptive exploration algorithm like UCB has a better early-stage performance than Q-UCB. Using our framework in Section 4 we show that UCB indeed has near-optimal CLQ that scales as O & In K ). Our framework also allows us to show that Q-UCB enjoys a CLQ scaling
as O K In K. + In
3 K) (Appendix A.I in [2].. This improves the guarantee implied by 224 and
3

---

shows the inefficiency due to forced exploration is about O(n x) and that Q-UCB has both strong transient (CLQ) and asymptotic (queueing regret) performance.
Focusing on the scaling of queueing regret, 23 and
43 study the scheduling in multi-queue settings
14 study learning for a load balancing model, 8 studies pricing and capacity sizing for single-queue single-server model with unknown parameters. For more general settings, I designs a Bayesian learning algorithm for Markov Decision Processes with countable state spaces (of which queueing systems are special cases) where parameters are sampled from a known prior over a restricted parameter space; in contrast, our paper does not assume any prior of the unknown parameters. The main difference between all of these works and ours is that we focus on how the maximum dineraveraged queue lengths scales with respect to system parameters (traffic slackness and number of queues and servers), not on how the queue lengths scale as time grows. Apart from the stochastic learning setting we focus on, there are works that tackle adversarial learning in queueing systems [21 26]; these require substantially different algorithms and analyses.
(with 43 also considering job abandonment), 9
Going beyond queueing regret, there are papers focusing on finite-time queue length guarantees. In a multi-queue multi-server setting, it is known that the Max Weight algorithm has a polynomial queue length for stabilizable systems. However, requires knowledge of system parameters. For a joint scheduling and utility maximization problem, [30] combines Max Weight with forced exploration to handle parameter uncertainty. By selecting a suitable window for sample collection, their guarantee corresponds to CLQ bound of at least O(K /E") for our single-queue setting (see Appendix A.3 in [2). 37 studies multi-queue multi-server setting and propose a frame-based learning algorithm based on Max Weight. They focus on a greedy approximation which has polynomial queue lengths when the system is stabilizable with twice of the arrival rates. [42] considers a non-stationary setting and shows that combining Max Weight with discounted UCB estimation leads to stability and polynomial queue length that scales as 0(1/s²) (Appendix A.4 in [22). There is also line of work studying decentralized learning in multi-queue multi-server settings. [15] assumes queues are selfish and derives conditions under which a no-regret learning algorithm is stable; this is generalized to queueing networks in which queues and servers form a directed acyclic graph by [3]
(33 allows
collaborative agents and gives algorithm with maximum stability, although the queue length scales exponentially in the number of servers. [1] designs a decentralized learning version of Max Weight and shows that the algorithm always stabilizes the system with polynomial queue lengths ((1/s²) (Appendix A.5 in (2).. In contrast to the above, our work shows for the centralized setting that Max Weight with UCB achieves the near-optimal time-averaged queue length guarantec of O(1/s).
Our paper extends the ability of online learning to general single-class qucueing networks 77]. The literature considers different complications that arise in these settings, including jobs of different classes and servers that give service simultaneously to different jobs [39 10 7l. For the class of networks we consider, it is known that of system parameters 39.. Noted in (7]. one potential drawback of BACK PRESSURE is its need of full knowledge of job transition probabilities. In this regard, our paper contributes to the literature by proposing the first BACKPRESSURF--aace algorithm that stabilizes queueing networks without knowledge of system parameters.
can stabilize the system with knowledge
Moving beyond our focus on uncertainties in services, an orthogonal line of work studies uncertainties in job types. (2) considers single server setting where an arriving job belongs to one of two types; but the true type is unknown and is learned by services. They devise a policy that optimizes a linear function of the numbers of correctly identified jobs and the waiting time. [6] studies a similar setting with two types of servers where jobs can route from one server to the others. They focus on the impact on stability due to job type uncertainties.
consider multiple job types and server types. Viewing Bayesian updates as job type transitions, they use queueing networks to model the job learning process and give stable algorithms based on BACK
29 34
[2 20 consider online matchings between jobs with unknown payoffs and servers where the goal is to maximize the total payoff's subject to stability. As noted in [29] 34 22), one key assumption of this line of work is the perfect knowledge of server types and transition probability. Our result thus serves as a step to consider both server uncertainties and job uncertainties, at least in a context without payoffs.
Concurrently to our work, 31 proposes a frame-based Max Weight algorithm with sliding- window UCB for scheduling in general multi-queue multi- system with non-stationary service rates. With a suitable frame size (depending on the traffic slackness), they show stability of the algorithm and obtain queue length bound of ( in the stationary setting (Appendix A.6 in 12 ).

---

2 Model
We consider a sequential learning setting where a decision maker (DM) repeatedly schedules jobs to a set of servers of unknown quality over discrete time periods t = 1, 1,2,.... For any T, we refer to the initial T periods as the time horizon T. To ease exposition, we first describe the simpler setting where there is only one job type (queue) and subsequently extend our approach to a general setting with multiple queues that interact through a network structure.
Single-queue multi-server system. A single-queue multi-server system is specified by tuple (K,, A, po). There is one queue of jobs and set of servers IC with [K] = K. The arrival rate of jobs is X, that is, in each period there is probability that new job arrives to the queue. The service rate of a server & E K., that is, the probability it successfully serves the job it is scheduled to work on, is pk.. Let (t) be the number of jobs at the start of period Initially there is no job and Q(1) = 0.
Figure 2 summarizes the events that occur each period L. If there is no job in the queue, i.e.. Q(1)= = O, then the DM selects no server; to ease notation, they select the null server [(] Otherwise, the DM selects a server J(t) E K. and requests service for the first job in the queue. The
Yes
Start Period
Queue: Q((
DM Selects Server f(t)
Service Job from Queue
No
Unsuccessful
Successful
Job Leaves System (Proh. (ate))
New Joh Arrival (Pinh X)
Start of Period 1++
Figure 2: Flowchart for a single-queue multi-server system.
service request is successful with probability μu,(()) and the job then leaves the system; otherwise. it remains in the queue. At the end of the period, a new job arrives with probability X. We assume that arrival and service events are independent. Let A(t) and (t)) be a set of independent Bernoulli random variables such that E [A(t)] = À and E [t) μa for l E IC; for the null server, TT (t) = for all t. The queue length dynamics are thus given by
Q(t + Qtt) (t) A(t).
A non-anticipatory policy for the DM maps for every period t the historical observations until f, i.e., server J() e K. {1}. We define Q(t, .T as the queue length in period under policy The DM's goal is to select non-anticipatory policy such that for any time horizon T 2 1, the expected time-averaged queue length T Eigr IE (Q(1, T) ]
is as small as possible.
When service rates known, the policy x² selecting the server with the highest service rate jz* in every period (unless the queue is empty) minimizes the expected time-averaged queue length for any time horizon (24 33). If À > μ², even under π`, the expected time-averaged queue length goes to infinity as the time horizon increases. We thus assume À < ju", in which case, the system is stabilizable, i.e., the expected averagee queue length under x² is bounded by constant over the entire time horizon. We next define the traffic slackness of this system:
Definition 1. A single-queue multi-served system has a traffic slackness E E (f,1)
larger traffic slackness implies that system is easier to stabilize. Is known that the policy " obtains an expected time-averaged queue length of the order of [36]
Queueing network. queueing network extends the above case by having multiple queues and probabilistic job transitions after service completion; our model here resembles the one in [.]. queueing network defined by tuple (N,K, A, μ., A, B,B.D,D.. such that ΣneNu(L) Pk, = 1, Vk. In contrast to the single-queue case, there is now set of queues A with cardinality N and a virtual queue 1 to which jobs transition once they leave the system. Each queue n E N has a set of servers B,, each which
D. P) where
{B,, hev
D = hee and P = (eE.)))e,,neAL.
*Compared to common assumptions in the literature, e.g., 38 setting as algorithms cannot leam service rates by querying servers in periods when they have jobs.
22 this makes for more challenging
5

---

belongs to a single queue. As before, the service rate of server k is Pk- The set Dj contains the destination queues of server & (and can include the virtual queue 1).
In each period i, the DM selects a set of servers to schedule jobs to and, if a service request from queue n. to server k is successful, a job from queue n transitions to queue n' DD with probability Pk.n (this implies Pk,n' = 0 if n' & Dz). The selected set of servers comes from set of feasible schedules Σ C {0, 1jx, which captures interference between servers. We require that for any queue, the number of selected servers is no larger than the number of jobs in this queue [
Formally, letting ak = 1 if schedule o E Σ selects server k and denoting Q(1) = (Qn (D)) as the queue length vector at the beginning of period I, the of feasible schedules in this period
Σ. = fo E E: Σ oR S (n())
KEB,
and the DM's decision in period is select a schedule (t) E Σ. Following 39 we assume that any subset of a feasible schedule is still feasible, i.e., if o E Σ and 0j ox Ak E K. then o' E E.
We now formalize the arrival and service dynamics in every period, which are captured by the independent random variables {t)) {Sx (1) The arrival vector A() = (An consists of (possibly correlated) random variables (t) taking value in A f0. 13 we denote its distribution by A and let E (t)] = (A) with À = (An, mA)) The service S (t) for each server l K is a Bernoulli random variable indicating whether the selected service request was successful [ To formalize the job transition, let (t) (Ia.. (1)) (()))) be random vector over {0. ()
for server l independent of other randomness such that P[LK, n (4) 1} = Pk.n and Emenu(L) Lx,n (1) = 1. The queueing dynamic is given by
Σ (x.())s(()) + (n)+) REB
Σ KEEK
We assume that the DM has knowledge of which policies are allowed, i.e., they know Σ and B, but has no prior knowledge of the rates X, jr, P and the set D In period f, the observed history is the set (T)))r))
o<(r)=1)+<< r<t that includes transition information on top of arrivals and services. Note that job transition is only observed when the server is selected and the service is successful. Similar to before, non-anticipatory policy maps an observed history to a feasible schedule; we let Qn,t,, T) be the length of queue n in period t under this policy.
(T)
Unlike the single-queue case, it is usually difficult to find the optimal policy for queueing network even with known system parameters. Fortunately, if the system is stabilizable, i.e., lim;-xo 7 EisT E [I) < under some scheduling policy, then the arrival rate vector must be within the capacity region of the servers [39]. Formally, let o = {Ø E [0, _J=D Eoes & = 1} be the probability simplex over Σ. A distribution & in & can be viewed as the frequency of policy using each schedule a E E, and the effective service rate queue n can get is given by pe (Ø) = = &. (EreB, OkAlke -EKex ok p o ,.) this includes both job inflow and out- flow. We denote the effective service rate vector for a schedule distribution & by 1="((() Then, the capacity region is S(u, Σ, 13, P)
{1ret( & E } For queueing network to be stabilizable, we must have X(A) E S(H, Σ, B. P) 39 As in the single-queue case, we further assume that the
system has a positive traffic slackness and let 1 denote a vector of 1s with suitable dimension.
Definition 2. A queueing network has traffic slackness E E (0, 1] if X(A) + el E S(n, Σ, P).
We also study a special case of queueing networks, multi-queue multi-server systems, where jobs immediately leave after successful service, i.c.. D: = {1} for all & E KC; this extends the models in 42) mentioned above. Since the transition probability matrix P is trivial (ph.1 = 1, Vk), we denote the capacity region of multi-queue multi-server system by S(p, B).
'Though this reflects the feature from the single-queue setting, that Q(1) 0 = J(t) = 1, it maintains the flexibility to have queue that has multiple jobs served in a single period.
"This formulation captures settings where arrivals are independent the history, such as example each
queue having independent arrivals (e.g., the bipartite queueing model in [1] and the example of feature- queues [35] where jobs have features: each type of feature has one queue; at most one job arrives among all queues in each period. Our formulation cannot capture dependent arrivals such queues with balking [18].

---

3 Main results: the statistical complexity of learning in queueing
This section presents our main results on the statistical complexity of learning in queueing systems. We first define the Cost of Learning in Queneing, or CLQ as shorthand, metric capturing this complexity and provide a lower bound for the single-queue multi--erver setting. Motivated by this, we design an efficient algorithm for the single-queue multi-server setting with matching CLQ and then extend this to the multi-queue multi- server and queueing network systems.
3.1 Cost of Learning in Queueing
We first consider learning in the single-queue multi-server setting. Previous works on learning in queueing systems focus the queueing regret [Q x) Q(T, x*)] in the asymptotic regime of T' - oc. The starting point of our work stems from the observation that an asymptotic metric, which measures performance in late periods, cannot capture the complexity of learning learning happens in initial periods (recall the left of Figure T.. In addition, guarantee on per-period queue length cannot easily translate to the service experience (or wait time) of jobs.
Motivated by the above insufficiency of queueing regret, we define the Cost of Learning in Queueing (or CLQQ) the maximum increase in expected time-averaged queue lengths under policy compared with the optimal policy. Specifically, we define the single-quens CLQ as:
E El Li=1
(Q(t. T) Q(t,
CLQ single (L,
max T21
(2)
T
As shown in Figure I (right), CLQ is finite-time metric and explicitly takes into account how fast learning occurs in the initial periods. In addition, a bound on the maximum increase in time-averaged queue length translates approximately (via Little's ' Law (7 job wait times.
bound on the increase in average
Given that the traffic slackness measures the difficulty of stabilizing a system, we also consider the worst-case cost learning in queueing over all pairs of (X, (1) with a fixed traffic slackness e. In slight abuse of notation, we overload CLQsingle to also denote this worst-case value, i.e.
CL.Q (K, (esinglo(K,,,tt (K,,T))
sup xe(0,1), >+eğmaxi
CL.Quingle (A, (,, R).
(3)
Our goal is to design a policy æ, without knowledge of the arrival rate, the service rates, and the traffic slackness, that achieves low worst-case cost of learning a single-queue multi-server system.
We can extend the definition of CLQ to the multi-queue multi-server and the qucueing network settings. Since the optimal policy is difficult design, we instead define CLQ for policy æ by comparing it with any non-anticipatory policy (which makes decisions only based on the history):
Σ EnEx E (1Q(t,, Qn(t,
CLQmulti/ (A, μ. B.
max non-anticipatory xf T21
max
(4)
ΣV 1= EnEN E 11
(n((7'))
(A, E,,,D,,,
mAx
non-anticipatory x' T21
T
As in the single-queue setting, we can define the worst-case cost of learning for a fixed structure A, E, B, D and traffic slackness the supremum across all arrival, service, and transition rates with this traffic slackness. With the same slight abuse of notation as before, we denote these quantities by CLQuuiti (A, Σ, B, T) and CL.Quet (A, Σ, B, D. T).
3.2 Lower bound on the cost of learning in queueing
Our first result establishes a lower bound on CLO (KeinggeeKK,,a &, r)). In particular, for any feasible policy т, we show a lower bound of Ω K) for sufficiently large K. With known parameters, the optimal time-averaged queue length is of the order of l/e. Hence, our result shows that the cost of learning non- non-negligible in queueing systems when there are many servers. For fixed K and E, our lower bound considers the cost of learning of the worst-case setting and is mustance-independee
K Theorem 1. For K > 24, (0, 0.25] and feasible policy have CLQ single (LQ,ingl(KKee 2 211
7

---

Although our proof is based on the distribution-fii free lower bound 9 ((VKT) for classical multi-armed bandits [5] this result does not apply directly to our setting. In particular, suppose the queue in our system is never empty. Then the accumulated loss in service of policy is exactly the regref in bandits and the lower bound implies that any feasible policy serves at least (TV jobs fewer than the optimal policy in the first T periods. However, due the traffic slackness, the queue does get empty under the optimal policy, and in periods when this occurs, the optimal policy also does not receive service. As result, the queue length of a learning policy could be lower than D(vKT) despite the loss of service compared with the optimal policy.
We next discuss the intuition (formal proof in Appendix C.I of [2)). Fixing K and e, suppose the gap in service rates between the optimal server and others is 2e. Then for any in a time horizon T T= 0 (x)) the number of arrivals in the first periods is around Xt and the potential service of the optimal server around (A + E)t. By the multi-armen bandit lower bound, the total service of policy at most around Åt + - vKi I A since S = O Then the combined service rate of servers chosen in the first I periods, i.c., EtST (.(()) is strictly bounded from above by the total arrival rate At. A carefully constructed example shows that the number of unserved jobs is around for every S and thus the time-averaged queue length for the horizon of the order of ET = (
Remark 1. In 124 Proposition 31, the authors established instunce-dependent lower bound on E [Q(,, m)) Q- (t) The implied CL.Q lower bound is weaker than ours (S2(K), see Appendix C.2 in (22) and is constrained to a acconsist policy x (see definition in (24) whereas ours does not.
3.3 Upper bound on the cost of learning in queueing
Motivated by the lower bound, we propose efficient algorithms with a focus on heavy-trafit optimality, i.e. ensuring CLQ O(%e)) as E - 0+. The rationale is that stabilizing the system with unknown parameters is more difficult when the traffic slackness is lower as an efficient algorithm must strive to learn parameters more accurately. We establish below that the classical upper confidence bound policy (UCB, see Algorithm 1 achieves near-optimal CL.Q = Ō K) for any K and e in the single-queue multi-server setting with no prior information of any system parameters.
Theorem 2. For any K 2 1, E (0, CLQsingge (K, UCB) < KK
The proof of the theorem (Section 4) bridges Lyapunov and bandit analysis, makes an interesting connection to satisficing regret, and is a main technical contribution of our work.
We next extend our approach the queueing network setting. Fixing the system structure A, Σ, B, D, we define MA = max A A,, and Mε,8 max EnEN EkEB, ok, to be the maxi- mum number of new job arrivals and the maximum number of selected servers per period. Further, for queueing networks, we also define the quantity MD = EkEK [D&|", related to the number of queues each server may see its jobs transition to. The following result shows that the worst-case cost of learning of our algorithm has optimal dependence on? :. The proof of this Theorem is provided [22 Section 6].
UCB BUB as short-hand [12] Algorithm 3])
Theorem 3. For any A, B. D and traffic slackness E E (0, 1]. we have
VN (32MA + 21 (1 In(MaMp.Ms.
CLQQ net (, BP-UCB) <
Our proof builds on the special case of multi-queue multi-server systems, for which we provide Algorithm MAXWEIGHT-U UCB with corresponding performance guarantee (see [2] Section 5]).
4 Proof for the single-queue multi-server setting (Theorem 2
In this section, we bound the CLQ of UCB for the single-queue multi-server setting (Theorem 2 In each period f, when the queue is non-empty, UCB selects server with the highest upper confidence bound estimation T& (t) min (1, (t) V Cx(2
where (tx(t) is the sample mean of services and (t) is the number of times server & is selected in the first - 1 periods.
2ln(t)
8

---

Algorithm 1: UCB for a single-queue multi-server system
Sample mean (1) < 0, number of samples Ci(() t for E (EEUULL))) queue Q(1) < 0
for ( = 1....... do
(x) min 1, (t) +
2ln(2)
E
Ci(l)
if Q(t) > 0 then J(t) +- arg max; Th (t); else [(t) t-1
/* Update queue length & estimates based on (t)) A(t), and J(t)
*/
Q(++1) - Q(t) (t) A(t)
(t + + (t)) +1, [st((+1))+ Creol0h@no00--=:eo ()n((++)
for k + (t) set Ca(t 1 Ca(t), iu(t+ 1) (t)
We establish framework to upper bound CLQ for any policy by considering separately the initial learning stage and the later regenerate stage. The two stages are separated by a parameter Ti that appears in our analysis: intuitively, during the learning stage (t < Ti), the loss in total service of a policy compared with the optimal server's outweighs the slackness e the system (Definition) D ie.. Ei=1 14" PJ(+) > tE and thus the queue length grows linearly with respect to the left-hand side. After the learning stage (t T1). when Σ 1C* [)(r)) < te, the queue regenerates to K bound on CLQuingle we couple the queue with an "auxiliary" queue where the DM always chooses nearly optimal server in the learning stage. Then we utilize a Lyapunov analysis to bound the queue length during the regenerate stage.
constant length independent tf To prove the Ō
The framework establishes connection between CLQQiinge (X, p4, and the satisficing regret defined as follows. For any horizon T, the satisficing regret SaRsingle (T, T) the total service rate gap between the optimal server and the server selected by и except for the periods where the gap is less than 2
5 or the queue length is zero. That is, the selected server is satisficing as long as its service rate nearly optimal or the queue is empty. To formally define it, we denote max( (ar, 0) by xt and define the satisficing regret of policy over the first T periods by
E) ") (Q(()= 2 1) SaRsingle TT, Σ n - 150
(6)
We use the satisficing regret notation because our motivation is similar to that in multi-armed bandits [2]. initially considered for infinite horizon and Bayesian setting. In multi-armed bandits, optimal bounds on regret Ein (n* (p* -Pr()) are either instance-dependent O (Ex: muCH" (n"
In
4 instance-indeependet (VVTT) [5] However, both are futile to establish a (Ō( bound for CLQ single [K, =): The first bound depends on the minimum gap (which can be infinitesimal), whereas the second is insufficient
explain in the discussion after Lemma 4.2
We cireumvent these obstacles by connecting the time-averaged queue length of the system with the satisficing regret of the policy via Lemma 4.1 (for the learning stage) and Lemma 4.2 (for the regenerate stage). Lemma 4.1 explicitly bounds the expected queue length through the expected satisficing regret; this is useful during the learning stage but does not give strong bound for the and is particularly useful during the latter regenerate stage. We then show that the satisficing regret of UCB is O K KInT) (Lemma 4.3 Combining these results, we establish a tight bound for the cost of learning of UCB.
regenerate stage. Lemma 4.2 gives a bound that depends on $aR="n""(=,T))
T
Formally, Lemma 4.1 shows that the expected queue length under π in period t is at most that under a nearly optimal policy plus the expected satisficing regret up that time.
Lemma 4.1. For any policy and horizon T, we have ΣT Z(O()))
3 + SaR (M,, T)
Lemma 4.1 is established by coupling the queue with an auxiliary queue that always selects a nearly optimal server. However, it cannot provide useful bound on the cost of learning. For large T, it is
known that E SaRRingge T) must grow with rate of at least O log T
25 Hence, Lemma 4.1
only meaningrully bounds the queue length for small T (learning stage). For large (regenerate stage), we instead have the following bound (Lemma

---

Lemma 4.2. For any policy and horizon T, we have Ei 3(Q(0)
S 4 +
E E[SaR (xr,))
T
This lemma shows that the impact of learning, reflected by E SaR (TT r)
decays at rate
of T Therefore, as long as SaR (TT, T) is of smaller order than T, the impact of learning eventually disappears. This also explains why the instance-ing indeanceindeeeedennt O KT) regret bound for multi-armed bandits insufficient for our analysis: the second moment of the regret scales linearly with the horizon and does not allow us to show decreasing impact of learning queue lengths.
Lemma 4.2 suffices to show stability (limy->se Σ E[Q()) < oo), but gives a suboptimal bound for
T
small T' Specifically, when SaR single (TT, T)² 2 T. this bound is of the order of 9 (3)) We thus need both Lemma 4.1 and Lemma
establish tight bound on the cost of learning in queues.
The following result bounds the first and second moments of the satisficing regret of UCB.
Lemma 4.3. For any horizon T, we have
16K (l (ti) E SaR SaRainglo single
2 (2 (
(i) E si (UCB.T) (UCR
<
T)
E
g²
We next offer proof sketch of Theorem
2 The theorem and lemmas proven in [12 Section 4].
Proof sketch of Theorem 2 Fix any pair of X, with maxtek μ4 = A t.. Let (2****+-²²
We bound CLQ single (X, μa, UCB) by considering T < Ti (learning stage) and T Ti (regenerate
stage) separately. For T $ Tı, we have
3 + E Singingle (UCB, T)) S
323K + (In 21
E
EST
where we use Lemmas 4.1
and (i). For T > Ti, we have
8 Sansingle (UCB,T)²
Σ
BIQU0
<
4
323K + 64K(In K + +2m 1/c)
T
6
IST
where we use Lemmas
4.2 and
4.3 ii).
Remark 2. Although the CLQ metric is focused on the entire horizon, our analysis extends to bounding the maximum expected time- averaged queue lengths in the later horizon, which is formalized
as maxT2T Eisr BQQ(0)
for any Ti. In particular, for Ti Z 212
Lemma 4.2 shows that
T
E.sT =(Q(0) T
< 5, UCB thus enjoys the optimal asymptotic queue length scaling of O( !
maxT27,
5 Conclusions
Motivated by the observation that queueing regret does not capture the complexity of learning which tends to occur in the initial stages, propose an alternative metric (CLQ) to encapsulate statistical complexity of learning in queueing systems. For single-queue multi-server system with K servers and traffic slackness E, we derive a lower bound Ω [(x) on CLQ, thus establishing that learning incurs a nog-negligible increase in queue lengths. We then show that the classical UCB algorithm has a matching upper bound of Ō K) Finally, we extend our result to multi-queue WEIGITT-UCD and BACKPRESSURES UCB, whose CLQ has near optimal ((1/s) dependence traffic slackness.
multi-sever systems and general queueing networks by providing algorithms,
Having introduced a metric that captures the complexity of learning in queueing systems, our work can serve as a starting point for interesting extensions that can help shed further light on the area. In particular, future research may focus on beyond worst case guarantees for CLQ, non- -tattttttonayy settings, improved bounds using contextual information, etc.
'This is suboptimal long in the second term of Lemma 4.2 we have exponent greater than 1 for 1/e.
10

---

References
[1] Saghar Adler and Vijay Subramanian. Bayesian learning of optimal policies in markov decision processes with countably infinite state-space. arXiv preprint arXiv:2306. 020.00274, 2023.
[2] Saed Alizamir, Francis De Véricourt, and Peng Sun. Diagnostic accuracy under congestion. Management Science, 59(1)1157-171, 2013.
[3] Mor Armony, Shlomo Israelit, Avishai Mandelbaum, Yariv N Marmor, Yulia Tseytlin, and Galit B Yom-Tov. On patient flow in hospitals: A data-based queueing-science perspective. Stochastic systems, 5(1):146-114 2015.
[4] Peter Auer, Nicolò Cesa-Bianchi, and Paul Fischer. Finite-time analysis of the multiarmed handit problem. Mach. Learn., 47(2-3):235-256 2002.
[5] Peter Auer, Nicolò Cesa-Bianchi Yoav Freund, and Robert E. Schapire. The nonstochastic multiarmed bandit problem. SIAM J. Comput., 32(1):48-77, 2002.
[6] Kostas Bimpikis and Mihalis G Markakis. Learning and hierarchies in service systems. Man- agement Science 1268- 1285, 2019.
[7] Maury Bramson, Bernardo D' Auria, and Neil Walton. Stability and instability of the maxweight policy. Math. Oper. Res., 46(4):1611 2021.
[8] Xinyun Chen, Yunan Liu, and Guiyu Hong. An online learning approach to dynamic pricing and capacity sizing in service systems. Operations Research, 2023.
[9] Tuhinangshu Choudhury, Gauri Joshi, Weina Wang, and Sanjay Shakkottai. Job dispatching policies for queueing systems with unknown service rates. In Proceedings of the Twenty-second International Symposium on Theory, Algorithmic Foundations, and Protocol Design for Mobile Networks and Mobile Computing, pages 181-190, 2021.
[10] Jim G.
Dai and Wuqin Lin. Maximum pressure policies in stochastic processing networks. Oper. Res., 53(2):197-218, 2005.
[11] Daniel Freund, Thodoris Lykouris, and Wentao Weng. Efficient decentralized multi-agent learning in asymmetric bipartite queueing systems. Operations Research, 2023.
[12] Daniel Freund, Thodoris Lykouris, and Wentao Weng. Quantifying the cost of learning in queueing systems. arXiv preprint arXiv:2308.078177 2023.
[13] Hu Fu, Qun Hu, and Jia' nan Lin. Stability of decentralized queueing networks beyond complete bipartite cases. Kristoffer Amsfelt Hansen, Tracy Xiao Liu, and Azarakhsh Malekian, editors, Web and Internet Economics 18th International Conference. WINE 2022, Troy, NY, USA, December 12-15, 2022, Proceedings, volume 13778 of Lecture Notes in Computer Science, pages 96-196911199 114. Springer, 2022.
[14] Xinzhe Fu and Eytan Modiano. Optimal routing to parallel servers with unknown bandit with queues. IEEE/ACM Transactions on Networking, 2022.
[15] Jason Gaitonde and Éva Tardos. The price of anarchy of strategic queuing systems. Journal of the ACM, 2023.
[16] Noah Gans, Ger Koole, and Avishai Mandelbaum. Telephone call centers: Tutorial, review, and research prospects. Manuf. Serv. Oper. Manag., 5(2):79 141, 2003.
[17] Mor Harchol-Balter, Performance modeling and design of computer systems: queueing theory in action. Cambridge University Press, 2013.
[18] Refael Hassin and Moshe Haviv. To queue or not to queue: Equilibrium behavior queueing systems, volume 59, Springer Science & Business Media, 2003.
11

---

[19] Elad Hazan and C. Seshadhri. Efficient learning algorithms for changing environments. In Andrea Pohoreckyj Danyluk, Léon Bottou, and Michael Littman, editors, Proceedings of the 26th Annual International Conference on Machine Learning, ICMI. 2009, Monireal, Quebec, Canada, June 14-18, 2009, volume 382 of ACM International Conference Proceeding Series, pages 393-400. ACM, 2009.
[20] Wei-Kang Hsu, Jiaming Xu, Xiaojun Lin, and Mark R Bell. Integrated online learning and adaptive control in queueing systems with uncertain payoffs. Operations Research, 70(2):1166- 1181, 2022.
[21] Jiatai Huang. Leana Golubchik, and Longbo Huang. Queue scheduling with adversarial bandit learning. arXiv preprint arXiv:2303.0177. 2023.
[22] Ramesh Johari, Vijay Kamble, and Yash Kanoria. Matching while learning. Operations Research, (22):655-881, 2021.
[23] Subhashini Krishnasamy, Ari Arapostathis, Ramesh Johari, and Sanjay Shakkotta.. On learning the ep rule in single and parallel server networks. arXiv preprint arXiv: 1802.06233 2018.
[24] Subhashini Krishnasamy, Rajat Sen, Ramesh Johari, and Sanjay Shakkottai. Learning unknown service rates in queues: A multiarmed bandit approach. Oper. Res., 69(1)315--330 2021.
[25] TL Lai and Herbert Robbins. Asymptotically efficient adaptive allocation rules. Advances in Applied Mathematics, 6(1):4-22, 1985.
[26] Qingkai Liang and Eytan Modiano. Minimizing queue length regret under adversarial network models. Proceedings of the ACM on Measurement and Analysis of Computing Systems, 2(1):1- 32, 2018.
[27] John DC Little. A proof for the queuing formula: I-= À w. Operations research, 933)3333-387, 1961.
[28] Rahul Makhijani, Parikshit Shah, Vashist Avadhanula, Caner Goomen, Nicolás E. Stier Moses, and Julián Mestre. QUEST: queue simulation for content moderation at scale. CoRR, abs/2103. 16816, 2021.
[29] Laurent Massoulié and Kuang Xu. On the capacity of information processing systems. Opera- lions Research, 66(2):668-586 2018
[30] Michael J. Neely, Scott Rager, and Thomas F. La Porta. Max weight learning algorithms for scheduling in unknown environments. IEEE Trans. Autom. Control., 57(5):1179-1199 2012.
[31] Quang Minh Nguyen and Eytan Modiano. Learning to schedule in non-stationary wireless networks with unknown statistics. arXiv preprint 2xXiv:2308.02734, 2023.
[32] Daniel Russo and Benjamin Van Roy. Satisficing in time-sensitive bandit learning. Mathematics of Operations Research, 47(4):2815 15-9999, 2022.
[33] Flore Sentenac, Etienne Boursier, and Vianney Perchet. Decentralized learning in online queuing systems. pages 18501-18512, 2021.
[34] Virag Shah, Lennart Gulikers, Laurent Massoulié, and Milan Vojnovic. Adaptive matching for expert systems with uncertain task types. Oper: Res., 68(5):1403-1424, 2020.
[35] Simrita Singh. Itai Gurvich, and Jan A Van Mieghem. Feature-based priority queuing. Available SSRN 3731865, 2022.
[36] R. Srikant and Lei Ying. Communication networks: an optimization, control, and stochastic networks perspective. Cambridge University Press, 2014.
[37] Thomas Stahlbuhk, Brooke Shrader, and Eytan H. Modiano. Learning algorithms for scheduling in wireless networks with unknown channel statistics. Ad Hoc Networks, 85:131-144, 2019.
[38] Thomas Stahlbuhk, Brooke Shrader, and Eytan H. Modiano. Learning algorithms for minimizing queue length regret. IEEE Trans. Inf. Theory, 1759 2021.
12

---

[39] Leandros Tassiulas. Stability properties of constrained queueing systems and scheduling policies for maximum throughput in multihop radio networks. IEEE TRANSACTIONS ON AUTOMATIC CONTROI, 31(2), 1992.
[40] Neil Walton and Kuang Xu. Learning and information in stochastic networks and queues. In Tutorials in Operations Research: Emerging Optimization Methods and Modeling Techniques with Applications, pages 161-198. INFORMS, 2021.
[41] Neil S. Walton. Two queues with non-stochastic arrivals. Oper. Res. Lett., 42(1)):3--57 2014.
[42] 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.
[43] Yueyang Zhong, John R Birge, and Amy Ward. Learning the scheduling policy in time-varying multiclass many server queues with abandonment. Available at SSRN, 2022.
13


Reviews:
[{"review_id": "KzjtdzJq0T", "reviewer": "Reviewer_vTq6", "summary": "The authors consider online queuing systems in a discrete time setting. They study settings with single class queue and multi-class queues, and they propose to consider a metric CLQ that serves as a conservative measure on how the queue length(s) could grow across every time point in a horizon. The authors propose a natural UCB algorithm, and demonstrate that it has a near optimal CLQ in a single queue setting. The authors also derive similar bounds in a queueing network setting.", "questions": "- Can I confirm if $\\{B_n\\}_{n\\in{\\cal N}}$ is a partition on ${\\cal K}$, since the authors say that each server in $B_n$ belongs to one queue?\n\n- While I find the CLQ notion interesting, I still find that it might not have told us the whole story on who the queue length fluctuate under a policy. Let's stick with the single queue model for our discussion sake. For example, let say we have a policy $\\pi$ that achieve a CLQ of $\\text{constant} \\times K/\\epsilon$, which is optimal, within a constant factor. Knowing that $\\mathbf{E}[Q(t, \\pi^*)] = O(1/\\epsilon)$ for a large $t$ (I think you can show this by a similar logic to how we derive the average queue length of a stable M/M/1), achieving an optimal CLQ stated above actually does not prevent us from having $\\mathbf{E}[Q(t, \\pi)] = O(K/\\epsilon)$ for all sufficiently large $t$. In this way, achieving an optimal CLQ does not necessarily mean that we converge to the optimal queue length when $t$ grows. \n\nA priori, this might not be a critical issue since the authors aspire to investigate a short time horizon regime and not only a long one, and IMHO I regard CLQ as a conservative measure that tells us how long the queue length could be over all possible horizon lengths.  But I am wondering if the authors could also consider a worst case over the horizon lengths in $\\{\\tau, \\tau+1, \\ldots \\}$ instead of $\\{1, 2, \\ldots \\}$, for an arbitrary $\\tau$? More precisely, do the authors' analysis inform us of a bound on (3) with the range of maximum $\\{1, 2, \\ldots \\}$ replaced with $\\{\\tau, \\tau+1, \\ldots \\}$ for and arbitrary $\\tau$?\n\n- What is the difference between the two definitions (5), (6)?\n", "limitations": "There is no potential societal impact to my best knowledge. This is a theoretical paper.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The analysis is quite novel. In addition, the definition of the CLQ and its analysis is new to the best of my knowledge. In particular, the consideration of the satisficing regret is quite interesting. \n- The authors achieve a nearly tight result in the case of one queue. Overall, the technical results are solid.\n- The notion of CLQ seems adequate as an alternate metric for online queueing systems, but I still have some question (see Question 2 in ``Question'')", "weaknesses": "1. The discussions on queueing networks could be benefited from more details. While the authors stated that they will provide additional examples on settings modeled by their queueing networks model in Appendix A, Appendix A does not seem to contain much details. To overcome this weakness, the authors should provide a detail account on how \n \n  - the model on the bipartite queueing system in [11] (Line 187), \n  - the model on the multi-server system in [39] (Line 190),\n\nare modeled by the queueing network formulation used by the authors. In particular, it will be crucial for the authors to highlight what are the individual element in the instance tuple (Line 170) in these models. While there could be quite a fair bit of details, I believe that the authors could include them in the Appendix A so that useful details are provided without violating the page limit.\n\n2. There is no simulation to showcase the results. \n\n3. The notion of CLQ seems not to tell us the long term behavior of a policy, since it is taking a worst case over all horizon lengths $1, 2, ....$ (See Question 2)", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Long-term optimality (Question 2/Weakness 3).**\nWe thank the reviewer for pointing out that we may get a better bound for a larger $\\tau$. Indeed, our analysis directly extends to show that UCB converges to the optimal $O(1/\\varepsilon)$ scaling (for the single-queue setting). By combining Lemma 4.2 and 4.3 we can obtain a bound of $\\tilde{O}(1/\\varepsilon + K^2/(T \\varepsilon^4))$ for the time-averaged queue length in the initial $T$ periods. As a result, if $\\tau \\geq K^2/\\varepsilon^4$, the maximum of time-averaged queue lengths for $T \\geq \\tau$ will be bounded by $O(1/\\varepsilon)$ with no dependence on $K$. \n\n**Clarification comments (Question 1, Question 3, and Weakness 2).** \nThe reviewer is right that $\\\\{\\mathcal{B}_n\\\\}$ is a partition of $\\mathcal{K}$. The difference between (5) and (6) is that (5) is tailored to the multi-queue multi-server system, i.e., the DM knows that there are no queue transitions; this is a special case of the queueing networks whose CLQ we define in (6). The reviewer is right that we do not have a subsection for simulation results, but we highlight that Figure 1 includes some numerical evidence for the performance of our algorithm (see also the PDF uploaded with an updated figure). \n\n**More details on the queueing models (Weakness 1).** In a bipartite queueing system [11], there are $N$ agents and $M$ workers. In period $t$, a new job arrives to each agent $n$’s queue with probability $\\lambda_n$. The DM selects a matching $\\sigma_{n,m}$ between agents and workers such that $\\sum_{m’\\in[M]} \\sigma_{n,m’}\\leq 1,\\sum_{n’\\in [N]} \\sigma_{n’,m} \\leq 1, \\forall n \\in [N], m\\in [M]$. If $\\sigma_{n,m}=1$, then the first job in agent $n$’s queue (if any) is cleared with probability $\\mu_{n,m}$. Otherwise, the job stays in the queue. All arrivals and services are independent across queues, servers and periods. To translate this model into our queueing network formulation (lines 168-204), let $\\mathcal{N} = [N], \\mathcal{K} = [N] \\times [M] = \\\\{(n,m), n\\in [N],m\\in [M]\\\\}$. $\\Lambda$ corresponds to $N$ independent Bernoulli random variables. For each $k=(n,m) \\in \\mathcal{K}$, we have $\\mu_k = \\mu_{n,m}$. The set $\\mathcal{A} = \\\\{0,1\\\\}^{\\mathcal{N}}$.\n$\\Sigma$ is the set of subsets $\\boldsymbol{\\sigma}$ of $\\mathcal{K}$, such that $\\sum_{k=(n,m’)} \\sigma_k \\leq 1, \\sum_{k=(n’,m)} \\sigma_k \\leq 1, \\forall n\\in[N],m\\in[M]$. $\\mathcal{B}_n = \\\\{k=(n,m), m \\in [M]\\\\}$. $\\mathcal{D}_n = \\emptyset$ for all $n$, and $P$ only includes transitions to the virtual queue.\n \nThe multi-server system [39] is similarly defined but instead of selecting a matching between agents and workers, the DM can match an agent with multiple workers, as long as there are sufficiently many jobs assigned to different workers. Therefore, the only change compared with the bipartite queueing system would be that $\\Sigma$ consists of all $\\boldsymbol{\\sigma}$ such that $\\sum_{k=(n’,m)} \\sigma_k \\leq 1, \\forall m \\in [M]$."}, {"review_id": "x0KVTcWroN", "reviewer": "Reviewer_aVzT", "summary": "This paper studies a problem that involves both learning with queueing.\nIn the simple setting, there is a single queue served by multiple\nservers. However, the service rate at each server is unknown and needs\nto be learned. Intuitively, the combination of the learning policy and\nthe scheduling policy will impact the queue length dynamics of the\nsystem.  Prior work mostly focuses on the queue length performance in\nthe late stage of the system. However, due to the nature of queueing\nsystems, this late-stage performance is relatively invariant to the\nlearning policy, and thus the late-stage metric does not adequately\ncapture the impact of learning. In contrast, the first contribution of\nthis paper is to propose a new metric, called CLQ (Cost-of-Learning).\nCLQ takes the difference between the time-averaged queue length of a\ngiven policy and that of the optimal, and then takes the maximum over time. \nThis maximization over the entire time-horizon allows CLQ to capture the\nearly-stage dynamics of the system, where the impact of learning is more\nobvious.  Then, the authors provide both lower bounds and achievable\nbounds for this new metrics, which differ only by a logarithmic factor\nin the number of servers.  Finally, the results are also extended to\nmore general multi-queue multi-server systems.", "questions": "1. The work in [39] also provides any-time queueing bounds. I wonder if\nthey can be translated into an achieveable result for CLQ. Can the\nauthors comment on how the any-time bound from [39] may compare with the\nachieveable bound in this paper?\n\n2. The lower bound involves a very large $K > 2^14 \\approx 16000$. Can\nthe authors comment on what will happen when $K$ is not this large? \n\nPost rebuttal phase:\n\nThe reviewer wishes to thank the authors for their response, which clarifies the relation to [39].", "limitations": "I do not find discussions on limitations or potential negative societal\nimpact.", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "1. The new notion of CLQ captures the impact of learning more accurately\nthan existing studies, by including the early-stage dynamics of the\nqueue. This is a significant contribution. \n\n2. The lower-bound and achievable-bound are nice and differ only by a\nlogarithmic factor.\n\n3. The results are extended to general multi-queue multi-server systems. \n\n4. The proof idea based on satisfying regret is also very interesting.", "weaknesses": "I don't find major weaknesses.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Comparison to [39] (Question 1).**\nThe reviewer is right that the guarantee in [39, Theorem 1] can be translated into a CLQ bound. In particular, it implies a cost of learning of $O(\\frac{N^4M^4}{\\varepsilon^3})$ for a stationary multi-server system with $N$ agents and $M$ workers. This is suboptimal compared with our guarantee (Theorem 4 in the supplementary material), which shows that the cost of learning under \\textsc{MW-UCB} is bounded by $O\\left(\\frac{N^{3.5}M^3}{\\varepsilon}\\right)$ (see line 123).\n\n**$K$ required in lower bound (Question 2).**\n The goal of Theorem 1 is to characterize the statistical complexity of learning in queueing and we did not optimize the constant. The exact lower bound we derive (for any $K$) is $\\frac{K}{2^{13}\\varepsilon}-\\frac{1}{2\\varepsilon}-1$ (line 522 in the supplementary material); a more careful analysis may be able to reduce the constant in this bound and give a non-vacuous lower bound for small $K$."}, {"review_id": "8qQlDwPLoe", "reviewer": "Reviewer_KN9r", "summary": "In this paper, the authors propose a new metric to quantify the cost of learning in queueing networks. This notion is required to capture the differences between holding costs in queues and, say costs accumulated in a bandit setting; the latter having a monotonicity property (in expectation). The authors then derive a worst-case lower bound for this metric, and propose UCB based algorithms that come `close' to the lower bound in the order sense. ", "questions": "This is not a serious issue for me, but I did not get what the authors meant in saying that the guarantee on time averaged queue lengths translates to one on wait times via Little's Law. This statement seems somewhat vague. Can CLQ be formally be related to a sub-optimality on average wait times?", "limitations": "Not applicable.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "1. The CLQ metric proposed here is meaningful, and quite appropriate for queueing systems. Prior work uses a standard regret metric, which may not be very appropriate given that queue tend to regenerate.\n\n2. The UCB-based analysis appears quite novel; the authors have to bound the CLQ differently in the initial learning phase and subsequently; this issue does not arise in standard UCB analyses for bandits.\n\n3. The analysis extends to queueing networks.", "weaknesses": "No significant weaknesses here. I would have liked to see some more exposition in certain places, including a description of the algorithms, and a comparison between the lower and upper bounds derived here. But I can see that the authors have done the best they could to tell the story within the space constraints.\n\nI do have some (minor) suggestions though.\n\n1. I think it is worth highlighting around Theorem 1 that the bound derived is not instance-dependent, but worst-case in nature.\n\n2. The following sentence on Line 270 on Page 7 \"Therefore, in expectation, the queue under .... never empties.\" was unclear to me.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Non-instance dependent guarantees (Weakness 1).**\nWe appreciate and will adopt the reviewer's suggestion to discuss this further around Theorem 1, and not just in the conclusion (as we currently do).\n\n**Confusing sentence on page 7 (Weakness 2).**\n We agree that this sentence was confusing; we intended to say that, for any policy, the expected combined service is less than the expected number of arrivals up to this point (which is still confusing); we will try to give a clearer description of this intuition in the camera-ready.\n\n**Connection to suboptimality of wait time (Question 1).**\n The relationship can be approximately justified through the following derivation. Let $W^{\\pi}(T)$ be the average wait time of all jobs up to period $T$ under a policy $\\pi$ and $Y(T)$ be the number of arrivals (to all queues) in the first $T$ periods. Then, we obtain from a sample-path version of Little’s Law $$\\frac{\\sum_{t \\leq T} Q^{\\pi}(t)}{T} = W^{\\pi}(T) * \\frac{Y(T)}{T}\\text{ and therefore } \\frac{\\sum_{t \\leq T} Q^{\\pi}(t)-Q^{\\star}(t)}{T} = \\left(W^{\\pi}(T)-W^{\\star}(T)\\right) * \\frac{Y(T)}{T}.$$ Since $Y(T)$ concentrates near $\\lambda T$, the maximum increase in average wait time is approximately $CLQ/\\lambda$."}, {"review_id": "uiD43arWB2", "reviewer": "Reviewer_ZtnW", "summary": "In this paper, the authors introduce a new regret metric, called Cost of Learning in Queueing (CLQ), to quantify the rate at which an optimal scheduling policy can be learned to minimize the time average queue lengths. The authors derive a lower bound to CLQ and show that an UCB-based policy comes close to achieving the lower bound. They also extend their policy to multiple queues in a network setting by combining the UCB policy with the celebrated Backpressure policy. ", "questions": "1.\tPlease respond to Comment 1 above by arguing why Theorem 2 gives a stronger bound than [34].\n2.\tSince the proposed UCB-based policy directly estimates the mean service rate, it might not work in the non-stationary setting, although the classic Max-weight (or Backpressure) might be able to stabilize the queues. Can the authors shed light on this aspect?\n", "limitations": "This is a theoretical work and does not seem to have any potentially negative societal impact.", "rating": 4, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "1. The dependence of the regret bound with respect to the slack parameter (epsilon) is optimal.\n2. Bounding the CLQ metric in terms of satisficing regret is intriguing.\n", "weaknesses": "1.\tThe paper [34] considers an unnormalized version of the same metric proposed in this paper. However, the results presented in this paper give a potentially weaker bound (linearly increasing) than the result in [34]. To be more specific, Theorem 2 proves a constant (let’s denote it by $c$) upper bound to the CLQ metric. Plugging this upper bound into Eq (3) yields the following linear bound on the queue length regret:\n\n   $\\sum_{t=1}^T \\mathbb{E}\\left[(Q(t, \\pi)) -  Q(t, \\pi^*) \\right]\\leq cT, ~ \\forall T \\geq 1 $\n\nBut it is already known from [34, Theorem 2, 3] that there exist simple dynamic policies under which the queue-length regret (i.e., the LHS of the above equation) can be bounded by a constant. Clearly, the CLQ metric fails to capture this strong result and paints an overly pessimistic picture. It is also not clear if the result presented in this paper strictly and quantitatively improves upon [34], even for smaller horizon lengths. \n\n2.\tThe proposed algorithm directly uses UCB, and its analysis does not present any new technical insights.  \n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Comparison to [34] (Question 1 and Weakness 1).**\nThe reviewer is right that the analysis in~[34] gives a stronger asymptotic  queue length bound. However, the setting in [34] that resembles our single-queue setting ([34, Theorem 4]) gives a bound with worse dependence on  $\\epsilon$. In fact, we show below (at the end of our response) that their bound on $\\sum_{t\\leq T} Q(t)-Q^{\\star}(t)$ is of order $1/\\varepsilon^8$, compared to our $\\sum_{t\\leq T}\\frac{Q(t)-Q^\\star(t)}{T}\\leq \\tilde{O}(K/\\epsilon)$. In that regard, our bound is stronger for small $T$, whereas the bound in [34] is stronger for large $T$ (even ignoring the gap dependence of their bound). To illustrate that their algorithm has a worse transient performance we simulated the algorithm from [34, Figure 7] under the setting of Fig. 1 in our paper (note that they propose some heuristics for their simulations, though they do not prove theoretical guarantees for these). The figure in the attached PDF shows that their algorithm has a significantly worse transient behavior despite its optimal asymptotic regret scaling. We view this as additional evidence that one should consider a metric focused on early stages, e.g., CLQ.\n\n\n**Technical novelty (Weakness 2).**\nThe reviewer is right that our algorithm for the single-queue setting is just UCB; however, the extension to general queueing networks requires a more careful adaptation. Indeed, for learning in general queueing networks, to the best of our knowledge, we provide the first guarantees of any kind. Moreover, our optimal dependence on $\\varepsilon$ involves a novel separation of the horizon in two stages (learning and regenerate), which should be of independent interest for analyses of learning in queueing systems. An additional technical benefit of our analysis is that by applying UCB directly, we avoid the inefficiencies induced by forced exploration (which is a common tool for learning in queueing systems [20,34]). Finally, as noted on page 1771 of [34], although forced exploration allows an \"easier way to analyze\", UCB is \"generally a better method and should be used in practice\"; and an \"interesting direction\" is to analyze how UCB can achieve good performance while interacting with the queue's dynamic. Our work serves as an advancement in this direction.\n\n\n\n**Connection to [39] (Question 2).**\n The reviewer is right that our UCB-based policies may not work in a non-stationary setting. Most closely connected, we highlight that [39] adapts an exponentially decaying rule to the UCB estimation and gives an any-time queue length bound. However, applying their bound in the stationary setting (which is the focus of our paper) does not give a tight dependence on $1/\\varepsilon$. As listed in our conclusion (line 365), extending our approach to the nonstationary setting is an exciting future direction.\n\n**Derivation of the $1/\\varepsilon^8$ bound for [34, Theorem 4].**\nIn the proof of Theorem 4 on page 1770 in [34], the authors shows in Eq. (16) and thereafter that \n$$\nR^{\\pi_3}_{(\\lambda,\\mu)}(T) \\leq \\sum\\_{p=1}^{p_0-1}(M_2p^2+\\beta_2) + \\sum\\_{p = p_0}^T (M_2p^2+\\beta_2)M_0e^{-\\chi p}\n$$\n\nwhere $R^{\\pi_3}_{(\\lambda,\\mu)}(T) = \\sum\\_{t \\leq T} (Q^{\\pi_3}(t) - Q^{\\star}(t))$ and $\\pi_3$ is their policy in [34, Figure 7].  The constants $M_0,\\chi$ are from Lemma 6 and $M_2,\\beta_2$ are from Lemma 8. We obtain lower bounds of these constants from the corresponding proofs as follows.\n\nFor $M_0, \\chi$, the last inequality (after Eq. (28)) in the proof of Lemma 6 on page 1776 requires $M_0e^{-\\chi p}$ to be at least $e^{-\\frac{1}{2}p\\delta^2} + 2(N-1)e^{-2\\frac{p}{N}\\gamma^2}$. Here $N$ is the number of servers (i.e., $K$ in our paper), $\\gamma$ is the minimum service rate suboptimality gap, and $\\delta$ is at most the expected decrease in queue lengths by choosing the fastest server, which is thus at most the traffic slackness $\\varepsilon$ in our paper.\n\nFor $M_2p^2 + \\beta_2$, Eq. (34) in the proof of Lemma 8 on page 1778 requires $M_2 \\geq 0$ and $\\beta_2 \\geq 2\\sum_{n=0}^{\\infty} n^2e^{-c_3 n}$ and $c_3$ is a constant from Lemma 10. Checking the proof of Lemma 10 on page 1780, after Eq. (41), one can see that $c_3$ is at least $2\\delta^2$ and $\\delta$ is at most the traffic slackness $\\varepsilon$ in our paper (see the definition of $\\delta$ after Eq. (40)). Therefore, $\\beta_2 \\geq \\sum_{n=0}^{\\infty} n^2e^{-\\varepsilon^2 n} = O(\\frac{1}{\\varepsilon^6})$ since $\\int_0^{\\infty} x^2e^{-\\alpha x} dx = \\frac{2}{\\alpha^3}$ for any $\\alpha > 0$.\n\nPutting these constants together, the upper bound in [34, Theorem 4] is at least (for $T \\geq \\frac{1}{\\varepsilon^2}$)\n$$\n\\sum_{p=1}^{p_0-1} (M_2p^2+\\beta_2)+\\sum_{p=p_0}^T (M_2p^2+\\beta_2)M_0e^{-\\chi p}  \\geq O\\left(\\sum_{p=1}^{T} \\frac{e^{-\\frac{1}{2}p\\varepsilon^2}}{\\varepsilon^6}\\right) \\geq O\\left(\\frac{(1-e^{-\\frac{1}{2}T\\varepsilon^2})}{\\varepsilon^8}\\right)\\geq O\\left(\\frac{1}{\\varepsilon^8}\\right).\n$$"}]

Author rebuttal:
We conducted a new simulation with the algorithm from [34, Figure 7] under the same setting of Figure 1 in our paper. The figure in the attached PDF shows that their algorithm has a significantly worse transient behavior despite its optimal asymptotic regret scaling. 

Meta-review: The paper investigates a queueing system where the service rates of the servers are initially unknown. The servers at a given queue are not working in parallel (which greatly simplifies the analysis), and corresponds more to a channel selection problem in radio communication systems. The authors introduce the CLQ metric defined as the maximum over time of the empirical expected simple regret. The latter is the difference between the queue length under the considered algorithm and the oracle algorithm (knowing the servers' rates). The authors establish a lower bound on the CLQ valid only for specific systems, and prove that UCB achieves this lower bound when it comes to the scaling of the slackness parameter (the distance to having an unstable system -- heavy traffic regime). These contributions are acknowledged by the reviewers.

However there are serious concerns about the way the related work is treated in the paper, and the connection to [20] and [34]. It is true that [34] and the current submission do not look at the same metric, as [34] is mainly concerned with the asymptotic regime when $T$ grows large. And the CLQ metric is of interest because it captures the transient behavior of the learning process. Nevertheless, the authors should explain the differences in the paper in more detail.

An exhaustive comparison with [20] seems even more important. In [20], the authors study both the asymptotic regime as $T$ grows large, and the transient regime in heavy traffic. The current submission only addresses the latter regime. Most of the qualitative observations made in the current submission are made in [20]: https://arxiv.org/pdf/1604.06377.pdf. See e.g. Fig. 1, Sections 5 and 6. 

-	In particular, in Section 5 of [20], the authors study the early stage regime, and they already prove a lower bound. The authors should compare it to their lower bound presented in Theorem 1. To be more precise, in Proposition 7, [20] establishes that on an interval of the type $[a,b/\epsilon]$, the regret per round is greater than $K\log(t)/\log\log(t)$. This seems like a very precise result. Fortunately, as it seems, the lower bound presented in Theorem 1 cannot be deduced from this result. The lower bound on the CLQ you would obtain from Proposition 7 in [20] would be much smaller than that in the current submission. Note however that the lower bound presented in Theorem 1 is valid only for seepcific cases, for $K\ge 2^{14}$.

-	Section 6 [20] presents nice numerical results illustrating the early and late stages. [20] already noticed that UCB was better in early stages.

-	In [20], the regret upper bound of Q-UCB for the early stage scales as $1/\epsilon^2$, not $1/\epsilon$ as it should and as the UCB algorithm studied in the present submission. On the other hand, UCB has worse performance in the late stage. 

The paper has in view the above discussion interesting results compared to [20], but the authors should provide a proper and fair comparison with [20]. 

An additional remark is that the CLQ metric is defined as a maximum over time, and hence it does not tell us when the CLQ value is achieved. If you wish to focus your attention on the early stages, then looking at the evolution of the simple regret is more precise. This is what is done in [20]. There, the authors give the shape of the evolution of the simple regret (see their Figure 1).
Decision: Accept (poster)