Queueing Matching Bandits with Preference Feedback
Authors: Jung-hun Kim
Min-hwan Oh
Venue: NeurIPS 2024 poster (2024)
Keywords: Bandits
Queue
Preference Feedback
Primary area: bandits
TL;DR: Bandit algorithms for queueing matching under a preference model

Abstract: In this study, we consider multi-class multi-server asymmetric queueing systems consisting of $N$ queues on one side and $K$ servers on the other side, where jobs randomly arrive in queues at each time. The service rate of each job-server assignment is unknown and modeled by a feature-based Multi-nomial Logit (MNL) function. At each time, a scheduler assigns jobs to servers, and each server stochastically serves at most one job based on its preferences over the assigned jobs. The primary goal of the algorithm is to stabilize the queues in the system while learning the service rates of servers. To achieve this goal, we propose algorithms based on UCB and Thompson Sampling, which achieve system stability with an average queue length bound of $O(\min\\{N,K\\}/\epsilon)$ for a large time horizon $T$, where $\epsilon$ is a traffic slackness of the system. Furthermore, the algorithms achieve sublinear regret bounds of $\tilde{O}(\min\\{\sqrt{T}Q_{\max},T^{3/4}\\})$, where $Q_{\max}$ represents the maximum queue length over agents and times. 
 Lastly, we provide experimental results to demonstrate the performance of our algorithms.

Queueing Matching Bandits with Preference Feedback
Jung-hun Kim Seoul National University Seoul, South Korea junghunkiim@nnu.ca ac kr
Min-hwan Oh Seoul National University Seoul, South Korea minoh@snu ac kr
Abstract
In this study, we consider multi-class multi-server asymmetric queueing systems consisting of N queues on one side and K servers on the other side, where jobs ran- domly arrive in queues at each time. The service rate of cach job-server assignment is unknown and modeled by a feature-based Multi-nomial Logit (MNL) function. At each time, scheduler assigns jobs to servers, and each server stochastically serves at most one job based on its preferences over the assigned jobs. The primary goal of the algorithm is to stabilize the queues in the system while learning the service rates of servers. To achieve this goal, we propose algorithms based on UCB and Thompson Sampling, which achieve system stability with an average queue length bound of (min ( KJ/e for large time horizon T, where e traffic slackness of the system. Furthermore, the algorithms achieve sublinear regret bounds of (min mTQ T3/41), where Qmax represents the maximum queue length over agents and times. Lastly, we provide experimental results to demonstrate the performance of our algorithms.
Introduction
Multi-class multi-server queueing systems, which have been extensively studied by 20 19 37 g 4 are motivated by real-world applications such as ride-hailing platforms, where riders are assigned to online job markets, where applicants are recommended for employment, and online labor service markets, where tasks are recommended to freelance workers. In these systems, there are two sides: queues (agents) on one side and servers (arms) on the other. At each time step. jobs stochastically arrive in multiple queues and are then assigned to multiple servers by matchmaking scheduler algorithm stabilize the systems. Importantly, the previous work assumes that the service rates for each server are known for scheduling jobs.
drivers. Other examples
However, real-world observations reveal that the service rate may not be known beforehand. Therefore, learning the service rates associated with the stochastic behavior of servers is essential for real- world applications. Furthermore, the behavior of servers may depend their (relative) preferences over assigned jobs. For example, in ride-hailing platforms where there are riders and drivers, the preferences of drivers over riders (not necessarily based personal information but rather rider's pick-up location, destination, etc.) may not known in advance to riders or even the systems, necessitating the learning of drivers' preferences through preference feedback over assigned riders.
Learning service rates in an online manner, based on partial feedback from each scheduling. is highly associated with multi armed bandit problems [33] These problems are fundamental sequential learning tasks where, for queueing systems, a job is assigned to a server and receives feedback on whether the job is served or not. The utilization of bandit strategies for queueing systems has been recently studied by Choudhury et al. [12], Stahlbuhk et [48) Gaitonde and Tardos 17
Freund
al. [15] Hsu et al. (22), Krishnasamy et al. [30 31 32), Sentenac et al. [46), Yang al. [52) Huang
et al. (23), which primary focus naturally on establishing stability of the systems while learning service rates.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

bbb
Sccopted/Senned job
Server/Arm
Bejectedd/ Remriinnggee oob
Ubitt
Assigned
Accepted Rajected
Quens/Aget
(a) Jobs randomly arrive in queues (agents) there are unknown different values of utility between queues and servers (arms) closely related to preferences.
(h) Each queue is assigned server based on scheduler.
(c) Each server accepts at one the assigned jobs based on its preference. A job of each accepted queue is served while jobs of rejected queues remain.
Figure 1: Illustration of queueing process with 4 queues/agents (N 4) and 3 servers/arms (K 3)
However, there still gaps between the previous models and the real-world applications. In all previous work, the inherent service rates for each job-server assignment are determined regardless of other jobs assigned to the same server (or is not allowed to assign multiple jobs the same server). This differs from real-world scenarios where service rate may depend on (relative) preference over multiple assigned jobs, as seen in online labor markets or ride-hailing platforms. Additionally, in which is closely related work to our study regarding multi-class multi-server queueing systems with asymmetric service rates, it was allowed to assign job in an empty queue to server to obtain feedback (null request), which may not be realistic. Furthermore, all of the previous work considers a simple model without generalizable structure or utilizing features for service rates.
Freund et al. [15], Krishnasamy et al. 31 32]
Another line of related work is matching bandits, in which there the behavior arms is based on their preferences [36 45 35
sides (agents and arms), and 54 29 However, their focus is on work considers dynamic job arrivals in queues. Additionally, it is worth mentioning online matching problems [27 39
static settings, whereas
[6] 28). where the sole focus is on optimizing matching rather than learning underlying models from bandit feedback. In contrast, our study concentrates on bandit problems related to learning latent utilities by managing the tradeoff between exploration and exploitation while establishing the stability of the queueing systems. Importantly, neither previous work on matching bandits nor online matching problems addresses the stability of queueing systems, which our primary focus.
40 18
In this work, we propose a novel and practical framework for queueing matching bandits under preference feedback. In the following, we describe our setting accompanied by an illustration in [ (a) Multiple queues (agents) and servers (arms) are involved, with jobs arriving randomly in queues. Additionally, there unknown utility values between queues and servers regarding preferences. (b) Nonempty queue are then assigned to servers based on a scheduling policy. (c) Subsequently, each server stochastically accepts most one of the assigned queues based on its unknown preference and serves one unit of job the accepted queue. The rejected jobs remain the queues. The processes of (a), (b), and (c) are repeated over time.
Summary of Our Contributions
We propose novel and practical framework for queueing matching bandits, where N agents and arms are involved, and jobs randomly arrive in agents' queues each round. Subsequently, a scheduler assigns agents to arms, and the service rates for the assigned agents depend on the arms' unknown preferences over them. These service rates are modeled using feature-based multinomial logit function. To the best of our knowledge, paper is the first to investigate either a feature-based service function or preference feedback using a multinomial logit function for service rates.
We propose algorithms based Upper Confidence Bound (UCB) and Thompson Sampling (TS), which achieve stability with average queue length bounds of O min min(N.K) for large time horizon T,, under a traffic slackness of e.

---

Furthermore, the algorithms achieve sublinear regret bounds of Ó(min STTVVTQQuue max: TT/44) where Qmax represents the maximum queue length over agents and times. It worth mentioning that regret analysis has not been studied in the closely related queueing bandit
literature such as Sentenac et al. [46], Freund et al. [55. Yang et al. [22.
Finally, we present experimental results demonstrating the stability and regret performance of our algorithms with comparison to previously suggested methods.
2 Related Work
Bandits for Queues. Learning the unknown service rates for queueing systems in an online manner
under bandit feedback has recently gained widespread attention [12 47 48 22 32
46 52 23].
While Stahlbuhk al. [47.. Krishnasamy et al. [30), Choudhury et al. 12 focused on a single queue with multiple servers, aiming to efficiently assign the queue to the optimal server while learning the service rates, subsequent study of Krishnasamy et al. [32 expanded this scope to encompass multiple queues and multiple servers. However, this extension relied on a strong structural assumption that each agent possesses unique and distinctly optimal server without sharing the same optimal server. Consequently, the algorithms employed in such scenarios do not necessarily consider the dynamic queue lengths when scheduling jobs; instead, they concentrate solely on learning service rates to achieve optimal matching. As the closest work to our study, another line of work of Sentenac et al. [6). Freund al. 131. Yang et al. [52] has focused more on dynamic queue lengths for multi-queue and multi-server scenarios without assuming the unique and distinct optimal servers for each agent. In this context, all of the previous work aimed to achieve queue length stability.
However, to the best of our knowledge, none of the previous works has focused on a structured model with features for service rates. Furthermore, previous studies either did not allow the assignment of different types of jobs to server simultaneously B2 52], or, if they did, as in Sentenac et al. 46). Freund al. [15], the inherent values of service rates for each job-server assignment remained constant regardless of the entire assignments. Additionally, the server's 's behavior given multiple assigned jobs was either simple or deterministic, based on the uniform-randomly selected job among the assigned jobs [46], or the job with the highest bid generated from the algorithm [15], respectively. However, these approaches may not reflect real-world scenarios, where the service rates depend on the relative preferences among the assigned jobs. Lastly, in [5 32). it was allowed to assign job to a server from an empty queue for obtaining feedback, which may not be realistic.
In our study, we adopt structured model incorporating features for unknown asymmetric service rates. We enable the assignment of multiple agents to the same server, where the server stochastically selects at most one of the assigned agents based its undisclosed (relative) preference. Also, the assignment of an agent is available only when the queue of the agent is not empty. This scenario mirrors common situations in real-world applications such as ride-hailing platforms and online labor markets where available multiple riders or tasks can he assigned to a driver or a worker, respectively, and the driver worker behaves stochastically depending its unknown preference.
It is noteworthy that we focus not only on the stability of the systems regarding queue lengths but also on regret against an oracle, while the closely related works by [46] 15 [2], which considered multi-class multi-server queueing systems, only addressed stability analysis. Regret analysis has only
been studied under some limited scenarios, such as a single-server (23) a single-queue [48] or the strong assumption that each agent has a unique and well-separated optimal server [32]
Matching Bandits. Next, we investigate two-sided matching bandits, a topic initially explored
by Liu et al. (36) and subsequently studied by Sankararaman al. [45). Liu et al. [35), Basu et al. 191. Zhang et al. [54], Kong and Li [29]. The primary goal is to minimize regret by attaining an optimal stable matching by learning agents' side preferences through stochastic reward feedback under static settings and deterministic behavior of arms with known preferences. Our study aligns with the model, wherein agents select arms based on preferences. However, our study sets itself apart from prior work on matching bandits in several key aspects. Firstly, we consider dynamic environments with job arrivals for agents. Secondly, we propose that arm behavior is stochastie, with unknown preferences, necessitating the learning of arms' preferences. Lastly, our main target is to stabilize the queue lengths in the systems rather than find stable matching for stable marriage problems.
MNL Bandits. Lastly, we examine MNL bandits which were initially proposed by Agrawal et al. 6 and followed by Agrawal et al. [7]. Chen et al. [T]] Oh and Iyengar [3] 44). In MNL bandits,
3

---

the goal is to select assortments of arms to maximize reward, which is based on preferences over the arms in the selected assortment. In our study, we adopt the MNL model for arms' choice preferences in dynamic systems, which, to the best of our knowledge, is the first consideration of bandits for queueing systems.
3 Problem Statement
There are N agents (queues) and K arms (servers). At each time, a job for each agent [N] arrives randomly following Bernoulli distribution with an unknown arrival rate X, E [0, Then each time & E [T' where T is the time horizon, each agent E [M] is assigned to an arm n,t E [K] by policy т. For notational simplicity, we use kn,t for Kã when there is no confusion. Let (t) be the length of the queue for jobs of agent E [N] at the beginning of time slot t in the system. We consider that at most agents can be assigned to each arm [K] at each time and N < KL to ensure that all agents can be assigned to arms. Then, we define the set of agents (assortment)
assigned to arm & by policy π at time as Sk,, {n [M] kn, = Qn()) + 0}, considering only available agents with nonempty queues.
Now we explain the structure of our model. Each agent n has known d-dimensional feature informa- tion of n,, E Rd, and each arm k has latent (unknown) parameter 02 Rd for preference utilities over agents. We adopt the Multi-nomial Logit (MNL) function commonly studied for preference feedback 43 44 6 [T]. Then given assortment Sk arm k serves a job of agent Sk, with service probability (service rate) determined by the MNL model as
exp(xr,, 0%)
p(n|Sk,,,00) 0x) 1 E exp exp(2
We note that [[n]SS,,,, 0s) represents the preference of arm k agent n the assigned agents Sa.r- The service rate of each n depends on the assigned agents rather than static by reflecting real-world scenarios, which is different from the conventional queueing problems. Following the MNI. function, the arm is allowed not to serve any agents (or allowed to serve null agent no) with the probability of (Tog Se,e, 0k)
Me,,, exp(z), 6x) Under the MNL model for the service rate, each time,
each arm accepts at most one agent and serves that agent's ' job. The queue lengths for the accepted agents are each reduced by one, while the queue lengths for the refused agents remain the same.
Objective Function. Here we provide the goal of this problem. For describing the stochastic process in the systems, at each time I, let A, (1) E {0, } be a random variable with mean An. which denotes whether new job arrives in the queue of agent E [N] (here, 1 denotes arrival). Also, E {0, 1} be a random variable with mean
given that is assigned to arm kn,t, let (t) [n]|Ss.,... d ()...), which represents whether the assigned agent n, given Sk,,,. is accepted by arm kn.r (here 1 denotes acceptance). Then the queue length of the agent n evolves as Qn.( + 1) (1) + (!) - D,, SE, where x denotes max 0} for & E R.
As in the previous work of queueing bandits for multiple types of agents and servers 46 which are closely related work to ours, our primary focus is stabilizing the dynamic systems regarding queue lengths. For analyzing the stability of the systems, we define the average queue lengths over horizon time T
15 52 23
Q(T)
EE MEΣBN E (Q)(
1 T (E(T] RE[N]
Then the goal of this problem is to design an online matching algorithm to assign the agents to arms for stabilizing the systems by bounding Q(T). We define the system stability as follows.
Definition 1. The systems are denoted to be stable when limr Q(T) < xx.
'Our study can be easily extended to the multi-une unit case where random variable A.,(t) lies in [0, M] for some M > 0 with mean An E [0, M).

---

The same stability definition was considered in Neely 41
42
Freund et al. [1] Yang et al.
[52], Huang al. [23]. noteworthy that according stability condition of Definition] is denoted to be strongly stable
42 15). the system satisfying this
For the analyses, first present the regularity conditions.
Assumption 1. || l2 & for all n E [N] and ||0x1l2 & for all [K].
Assumption 2. There exists K > 0 such that inf p(n|S, ()p(no)) K for any E S and 5 C [N].
These regularity conditions commonly taken into account in the logistic and MNL bandit literature We note that, in the worst-case, 1/n = O
13
43 44].
We define the set of feasible disjoint assortments given any N s [N] as M(N) = (Si,.... 5k): Sk S N, |S&l S L Ak E SK) ns Ak + UkEkK] Ss =M..
Then, we consider the condition of traffic slackness for stability follows.
Assumption 3. For some traffic slackness < < 1, there exists {Sk]RE[K] E MM(N)) such that An + + p(n|Sk. for all Sy and E [K].
We note that similar slackness assumptions have been commonly considered in queueing bandits
15 52 23 As decreases, achieving stability in our setting becomes more challenging. discussion for refined version of can be found in Appendix A.2 A.2
4 Preliminary Study: An Oracle Algorithm of Max MaxWeight
For queueing systems, Max Weight (50] has been proven to have optimal throughput keeping the queues in networks stable under known service rates [51 38 37 49). Here, we analyze the oracle policy using Max Weight under known 02 's. We define the set of agents having non-empty queues at time as N₁ = (n E [N]] (1) + 0}. Then, the oracle policy using Max Weight in our setting defined as {Sx,()<E[K] where priority in the assortment scheduling is on queues with either large queue lengths high service rates. We provide an analysis of stability of the Max Weight oracle for known 0g as follows.
argmax (Sx h' (E). Σ Σnes: (n()))(n)
(n]], Sk. 0x),
Proposition 1. Given the prior knowledge of On for all l E [K]. the average queue length of MaxWeight is bounded as Q(T) = O min(N.K). ) which implies that the algorithm achieves stability.
Proof. The proof is provided in Appendix A.3
We note that the term of min (N, K} in the average queue length is a result of the system's 's variance. Additionally, as decreases, the stability of the system deteriorates due to the reduced traffic slackness. Further discussion regarding can be found in Appendix A.2
Since the oracle algorithm requires prior knowledge of 0g's for the service rate, we cannot directly in our bandit setting. In the following section, we propose algorithms incorporating an efficient learning procedure to achieve stability in our setting.
Algorithms and Analyses
5.1 UCB-based Algorithm
We first propose an algorithm based on the UCB strategy, UCB-QMB (Algorithm D We define the negative log- ligeliikl as fe. := Emest, Vn. log [ e. 8) where yn,t E {0, 1) is observed preference feedback (1 denotes service acceptance, and 0 denotes refusal) and define the gradient of the likelihood as
(0) = Vefn.(())
Σ (m(n))Se.e 0) Vn..).n. HES
(I)
As mentioned in 42 15]. in general, this stability condition is stronger than the mean rate stability of weaker than the uniform stability B[EnEIN Qn.()) S C
3 [v] Q. (2)
lim
for some constant C 0.
5

---

Then, we construct the estimator of oN. from online updates applying online newton step studied by
21
53
24
14
8R argmingge I (0x,c-1) 1 0 + コ b116 f where O {0
R
}) and VR,, Ala + 2 E.=1 Eneg, Fn Using the estimator, define the UCB index for agent in assortment Sy as
||0||2
exp(h
(n( 0k,t) = 1 Emss exp(1 m.k.t)
where LUCB = 0 Be 1 with B, CiVA A n,
log(1 + 'LK) for some constant
dx
C O. We utilize the Max HaxWeight with the UCB indexes by setting À = 1.
Algorithm UCB- Queueing Matching Bandit (UCB-QMB
Input: X, R, C1 0 for f I...., do
for k E [K] do
Ont + argmingge Sh,t- (00,-1(0K,A-1)) 111 1 with
{Sk, [SK,]RE[K]]
argmax (LL))) kE[A] nES,
Σ (2(t) (n|Skr On.e) with 2
Offer (SKK) and observe preference feedback yn,t E {0, 13 for all n E Sk,e. h E [K]
5.1.1 Stability Analysis of UCB-QMB
Here we provide an analysis for the stability of UCB-QMB (Algorithm D
Theorem 1. The average queue length of Algorithm
bounded
Q(T)
O M. N² polplg((T) which implies that the algorithm achieves stability
lim Q(T) = mmin min((N (N,K) K)
T-00
We note that Algorithm achieves the same average queue length bound of O min [N.) with the oracle Max Max Weight (Proposition D when is large enough.
Proof sketch. Here we provide a proof sketch and the full version is provided in Appendix A.4 We define the set of queues Q(t) (t) n [N] and a Lyapunov function as V(Q(t))
ΣMEIN) (t)? 2 For simplicity, we use (t) for (utt)Sk....)) and (t) for (t ..) when there is no confusion. Then we analyze the Lyapunov drift as follows:
Σ V(Q(t + 1)) v((())
1E|TI
E
Σ (Qn(1) + An(1) - 22) Qn)
tE[T] N]
ΣΣ (Qx(1 + An( - (2)
Σ (Q^(1 + A.(1) D2(0)) (3)
*E(T) ME[N]
(E(T) ME[N]
For the first two terms in Eq. 3. with Assumption 3] we can show that
Σ Σ ([(Qn(t) + (t) (2) (t)
Σ Σ
2eE[Qn(t) + mN, KYT.
(E(T]NE[M)
RE NE[N]
(4)
For the last two terms in Eq.3. we have
Σ Σ (Qn(t) (t) +2)
ΣΣ
Σ (Qn(t) + An(t)-
(T(T]
NE[N]
FE(T) ME(N]
2F
Σ
Σ
(m(n)SEr, Ok:,) p Gx, (1Q()))) +5min KYTT (5)
(E|T N

---

where the first term of the last inequality is closely related to the regret analysis of the bandit strategy. In the following. we focus on analyzing the last term in Eq. We define events E; {1l0,,- - -10x.=0%illv, ve, I 3. for all & E [K]] and E = fmaxmes.,. || v I C2c/25, for k
for some constant C2 > O. We can show that E, holds with high probability so here we only consider the case when E holds. Then we have
E
Σ
Σ
p(nlSki... en Okin.) (nn OR Ok. (..
tE nE[N]
$ Σ
Σ
[[(u(n]Sk: ae Ow:.)) - p(n|Sum.eits On.,, (1,, +((,,,))))) (6)
tE[T] NE
Then for the first term of Eq. from the UCB strategy and E we can show that
Σ E
Σ
(n Ocz,.) plnl Ok ( (1.. C2e Σ Σ [[Q((()
AE|T]
NE(N]
RE(T]
Now we provide a bound for the second term of Eq. For some constant C3 > 0, we can show that
Σ EETT] nE(N]
Σ
Bl(u(n)Sk Okz u(n)Skk..... (1)
N2
Σ
Σ
(Q,0))
(8)
2:
:E[T] ME(N]
By putting the results of Eqs.
4..
66
(
altogether, we can obtain
Σ v(Q(++ ((Q()) LE(T]
N2 B4.
7imn
(1/Ca) - 1)e Σ Σ (0)x ONN log())) + tE(T) RE|M]
x265
Finally, with positive constants C22 C3 satisfying C2 + (1/Cg) < 1, from ((()1) = and V(Q + 1)) 2 0, by using telescoping for the above inequality and rearrangement, can conclude proof by + Erer EnE[N] (() O N.K d' N² polylog( (T))
5.1.2 Regret Analysis of UCB-QMB
In addition to the stability analysis, we examine the cumulative regret of UCB-QMB (Algorithm) I The regret is defined as the discrepancy between the performance of the oracle policy of Max WeiWhight T²" which operates with the knowledge the true parameters 0₂ 's, and that of our policy m. Given the queue lengths at each time t, we denote the oracle assignments as
[SEA) =
argmax (MN)N)))EM(NN kE(K] nES,
Σ Σ (n(t)u(n(Ss...))
We show that this oracle policy achieves stability in Proposition kn" Then, the cumulative regret under π is defined as
| For simplicity, ki for
(²(T)=
E (u(n|Sk Owt,) ( Ok.,, (1) (E NE(N]
Σ
We define Qmax E[max (n). Then the algorithm achieves the following regret bound.
Theorem 2. The policy N of Algorithm achieves a regret bound of
<NNK min K33 1/4
r8/11).
Rs R²(T) = δ min
KTQQmax
K:2e3
7

---

We emphasize that our algorithms achieve sublinear regret bound, even in the worst-case scenario regarding queue lengths from the minimum in regret. In contrast, [33 achieves regret bound of ((max (VQQQQQQmm max; T })) for a stationary setting, where the worst-case bound is not guaranteed to be sublinear from the maximum in regret.
Proof sketch. Here we provide a proof sketch and the full version is provided in Appendix AA.5 We first provide the proof for regret bound of (T) O (mTQm)x). We define Be vk E [K]] which holds with high probabil-
event Fy (ll0r, Vil.,. ity. Therefore, here we only consider the case when E. holds. Then we can show that B[Qn EnEIN IIQ.. (()( - )-p(n((Skner Okn.))] - Ene(N) BIQn (Tk (m) Smmie ORnD)l I ExE(K] E[28 maxnESe, lxally, Qn((). From the inequality, with Et max || V. I (Ad/n) log(1 + (TL/dA)), we have
Σ
E (t) Okz,) (u(n/Sknnn O kkn,)]]
RE'I nE(Ni
< 2E
max [E(T)).E[[]]
Qn(1)T
KT Σ E
max IESE. [E[T]
||
=6(= KKTK@mmax).co
Now
we
provide the proof for the worst-case regret bound of R²(T) =
1/4 T8/4 the following. We additionally define event
(N kin
(maxmess..
| I for & = knnt for some constant C2 > Under El
have
Rd (T)
El(p(n) Okr.)) ) u[n]Ska..... ON., (t)
[E[2] ME[N]
Σ
Σ
[[(((n)Ss Ok..))
0k (1, (((E)))))
DE|N]
(1I)
Then for the first term of Eq. II have
Σ E
(m(n)Skr, Okn,) - [(n]SSkmned Sk., Ok.. ()),(()
NE
Σ
23 2. kn,e. (1(
$
ΣΣ> 28 (Q))
(12)
[ET
[RE[N]
(E[T]
where the last inequality is obtained from EZ,t- By analyzing the selected number of agent n with (E2,)) we can show that
Σ
Σ
B[(a(n|Se:..t Ok:.)) ) - 1-(nn//Sk..... Ok.,, (Q)((())(((())))))))))))))))))))
T] NE(N]
Σ (2)))) + NK
Σ
(13)
RC3
nE[[]
By putting the results of Eqs.
12
13 and Theorem by setting Ç
(eNK/ KYTK88) 1/4 for large enough T, we have
NK
Rd (T) 0
Ç3T Σ
Σ (() + KC3
+ N log(T))
LETT
NE[N]
dNK min K3
1/4
=ō
73/4
(14)
2
which conclude the proof combined with Eq.
10

---

Algorithm 2 Thompson Sampling- Queiiingguuuuinng Matching Bandit (TS-QMB)
Input: X, M, K, C1 > for t 1..... do
for k [K] do
dx,c a 9k.--1(0,,-11) 2110 0x.e-1lii. with !
(0 (e independently from NV(0,... V..)
Sample
{Sk,) f
argmax (MK)
Σ Σ Qn(() (n|Sk: (0 (E(M) with (5
KE[K] neS,
Offer (SKR)kE[R] and observe preference feedback Un,r {0, 13 for all Sk,e [K]
5.2 Thompson Sampling-based Algorithm
Here, we propose an algorithm based Thompson Sampling, TS-QMB (Algorithm 2). As in the previous algorithm, we construct the estimator as 0x. argmingge Jk. 1 (fx,t-1) T +
1,, To facilitate exploration, sample several 0 for [M] from Gaussian distribution of N( V and construct the Thompson Sampling (TS) index for assortment S₃
exp(h
14's (n|Sk, 10 (..hhEE))) = 1+ Σ Ems. exp(h
(15)
where A7 n,,,t m x, (00) and B. Ci A+ C d "log(1 + ILK for some constant C1 > dd
Then we utilize the Max Weight with TS indexes. We set À = 1 and M log(1 1/4/em)
log(
5.2.1 Stability Analysis of TS-QMB
Here provide stability analysis for TS-QMB (Algorithm 2
Theorem 3. The average queue length of Algorithm 2 is bounded as Q(T)
Mik N² polylog(()) which implies that the algorithm achieves stability as
lim Q(T) min(N,
T-000
Proof.
The proof is provided in Appendix A.6
5.2.2 Regret Analysis of TS-QMB
We provide regret analysis of TS-QMM (Algorithm 2 for the regret definition of (9) in the following.
Theorem 4. The policy π of Algorithm achieves a regret bound of
13/2
d min( KJ
1/1
T3/4 )
Rd (T( = δ min
/KTQQaar max: max::
226
Proof. The proof provided in Appendix A.7
We note that the performance of Algorithm I and Algorithm in the analysis results shows similar trends. However, the TS- Algorithm incurs a loss with respect to compared to the UCB-based
Algorithm 1 as commonly seen in previous TS-based algorithms 5 2 43
Here, we briefly discuss the combinatorial optimization argmax ( M ΣLEKK] fa(S)) for some function Sa S C [N] R in our algorithms. The exact optimization can be expensive due to its NP-hard nature. To address this, we can utilize the technique of a-approximation oracle with 0 < 1, first introduced in Kakade et al. (25), which is deferred to Appendix A.9

---

ETC-GS
MaX
Q-UCB
DAM-UCB
UCB- QMB (Algorithm 1)
TS-QMB (Algorithm 2)
Oracle (MaxWeight)
1.0
1e2
Average Queue Length
2.0 1e5
Regret
0.8
1.5
0.6
R(0
0.5
0.2
0.0
0.0
5000
10000
15000
20000
5000
10000
15000
20000
Time step t
Time step
Figure 2: Experimental results for (left) average queue length and (right) regret
Experiments
Here, we provide experimental results to demonstrate the performance of our algorithms For the synthetic experiments, we consider
4, K 2, I. and 2. Each element in z, and Og is uniformly generated from [0. 1] and then normalized, and A, 's are determined with 0.1.
Even though no dedicated benchmark exists for our queueing matching scenario, we compare our algorithms with previously suggested ones for queueing bandits matching bandits: Q-UCB (32), DAM-UCB [1]. and MaxWeight-UCG [52) for multi-queue multi-server bandits with asymmetric we can observe that our algorithms ! and 2) outperform the previously suggested ones except for the oracle (Max Weight) operated under known (latent) service rates. We demonstrate that our algorithms achieve stability, similar to the oracle in the left figure, which matches the results our stability analysis (Theorems and 3). Regarding regret shown in the right figure, the previously suggested algorithms exhibit superlinear performance due to the increasing Qn (t), while our algorithms show relatively small regret (Theorems 2) and 4). Additional experiments can be found in Appendix A..0
service rates and ETC-GS 34]] for matching bandits. In Figure 2
(Algorithms
7 Conclusion
In this paper, introduce novel framework for queueing matching bandits with preference feedback. To achieve stability this framework, we propose UCB and TS- based algorithms uti- lizing the Max Weight strategy. The algorithms achieve system stability with average queue length bound Omin N, Ke)e). Furthermore, the algorithms achieve sublinear regret bounds of Oming mmx, T 8//4)). Lastly, we demonstrate our algorithms using synthetic datasets.
8 Acknowledgements
The authors thank Milan Vojnović for helpful discussions and Hyunjun Choi for providing useful code. JK was supported by the Global-LAMP Program the National Research Foundation of Korea (NRF) grant funded by the Ministry of Education (No. RSS2023-003011966 MO was supported by the NRF grant funded by the Korea governmen(MMSTT (No. 2022RIC1C100 IC1C1006859 and 2022RIA4A (4410009799 and by AI-Bio Research Grant through Scoul National University.
References
[1] Yasin Abbasi- Yadkori, Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. Advances in neural information processing systems, 24, 2011.
[2] Marc Abeille and Alessandro Lazaric. Linear thompson sampling revisited. In Artificial Intelligence and Statistics, pages 176-184. PMLR, 2017.
'The source
code is available
http:///ggthuub..cmmmuguuuuuuuuu
Queueing- Matching- Bandits-ddeeeeee with wwweeeerrnee--eebbeee
10

---

[3] Mare Abeille, Louis Faury, and Clément Calauzènes. Instance-wise minimax optimal algorithms for logistic bandits. In International Conference on Artificial Intelligence and Statistics, pages 3691-3699. PMLR, 2021.
[4] Philipp Afeche, Rene Caldentey, and Varun Gupta. On the optimal design of a bipartite matching queueing system. Operations Research, 70(1):363-401, 2022.
[5] Shipra Agrawal and Navin Goyal. Thompson sampling for contextual bandits with linear payoffs. In International conference machine learning, pages 127-135. PMLR, 2013.
[6] Shipra Agrawal, Vashist Avadhanula, Vineet Goyal, and Assaf 7eevi. Mnl-bandit: A dynamic learning approach to assortment selection. arXiv preprint arXiv: 2017.
[7] Shipra Agrawal, Vashist Avadhanula, Vineet Goyal, and Assaf Zeevi. Thompson sampling for the man-bandit. In Conference on learning theory, pages 76-78. PMLR, 2017.
[8] Urtzi Ayesta, Peter Jacko, and Vladimir Novak. Scheduling of multi-class multi-server queueing systems with abandonments. Journal of Scheduling, 20:129-1444 2017.
[9] Soumya Basu, Karthik Abinav Sankararaman, and Abishek Sankararaman. Beyond log" (t) regret for decentralized bandits in matching markets. In International Conference on Machine Learning, pages 705-715. PMLR, 2021.
[10] Gruia Calineseu, Chandra Chekuri, Martin Pal, and Jan Vondrák. Maximizing a monotone submodular function subject to a matroid constraint. SIAM Journal Computing, 40(6): 1740-1766, 2011.
[11] Xi Chen, Akshay Krishnamurthy, and Yining Wang. Robust dynamic assortment optimization in the presence of outlier customers. Operations Research, 2023.
[12] 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 Protocal Design for Mobile Networks and Mobile Computing, pages 181-190, 2021.
[13] Louis Faury, Mare Abeille, Clément Calauzènes, and Olivier Fercoq. Improved optimistic algorithms for logistic bandits. International Conference on Machine Learning, pages 2062- PMLR, 2020.
[14] Louis Faury, Marc Abeille, Kwang-Sung Jun, and Clément Calauzènes. Jointly efficient and optimal algorithms for logistic bandits. International Conference on Artificial Intelligence and Statistics, pages 546-580. PMIR, 2022.
[15] Daniel Freund, Thodoris Lykouris, and Wentao Weng. Efficient decentralized multi-agent learning in asymmetric queuing systems. In Conference on Learning Theory, pages 4080-4084. PMLR, 2022.
[16] Bernhard Fuchs, Winfried Hochstättler, and Walter Kern. Online matching on a line. Theoretical Computer Science, 332(1-3):251 -644, 2005.
[17] Jason Gaitonde and Éva Tardos. Stability and learning in strategic queuing systems. In Proceedings of the 21 ACM Conference on Economics and Computation, pages 319-347, 2020.
[18] Buddhima Gamlath, Michael Kapralov, Andreas Maggiori, Ola Svensson, and David Waje. Online matching with general arrivals. In 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS), pages 26-37. IEEE, 2019.
[19] Kevin D Glazebrook and José Niño-MMra. Parallel scheduling of multiclass m/m/m queues: Approximate and heavy-traffic optimization of achievable performance. Operations Research, 49 (9) 623, 2001.
[20] J Michael Harrison. Heavy traffic analysis of a system with parallel servers: asymptotic optimality of discrete-review policies. The Annals of Applied Probability, 8(3):822-844 -48, 1998.
11

---

[21] Elad Hazan, Amit Agarwal, and Satyen Kale. Logarithmic regret algorithms for online convex optimization. Machine Learning, 69(2):169 192, 2007.
[22] Wei-Kang Hsu, Jiaming Xu, Xiaojun Lin, and Mark R Bell. Integrated online learning and adaptive control in queueing systems with uncertain payoff'. Operations Research, 70(2): 1166-1181, 2022.
[23] Jiatai Huang, Leana Golubchik, and Longbo Huang. When дyаршnov drift based queue schedul- ing meets adversarial bandit learning. IEEE/ACM Transactions on Networking, 2024.
[24] Kwang- Sung Jun, Aniruddha Bhargava, Robert Nowak, and Rebecca Willett. Scalable gen- eralized linear bandits: Online computation and hashing. Advances in Neural Information Processing Systems, 30, 2017.
[25] Sham M Kakade, Adam Tauman Kalai, and Katrina Ligett. Playing games with approximation algorithms. In Proceedings of the thirty-ninth annual ACM symposium on Theory of computing. pages 546-555, 2007.
[26] Michael Kapralov, Ian Post, and Jan Vondrák. Online submodular welfare maximization: Greedy is optimal. In Proceedings of the twenty-fourth annual ACM-SIAM symposium on Discrete algorithms, pages 1216-1225. SIAM, 2013.
[27] Richard M Karp, Umesh V Vazirani, and Vijay V Vazirani. An optimal algorithm for on-line bipartite matching. In Proceedings of the twenty-secone annual ACM symposium on Theory of computing, pages 352-358 1990.
[28] Thomas Kesselheim, Klaus Radke, Andreas Tönnis, and Berthold Vöcking. An optimal online algorithm for weighted bipartite matching and extensions to combinatorial auctions. In European symposium on algorithmss, pages 589-600. Springer, 2013.
[29] Fang Kong and Shuai Li. Player-optimal stable regret for bandit learning in matching markets. In Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1512-1522. SIAM, 2023.
[30] Subhashini Krishnasamy, Rajat Sen, Ramesh Johari, and Sanjay Shakkottai. Regret of queueing bandits. Advances in Neural Information Processing Systems, 29, 2016.
[31] Subhashini Krishnasamy, Ari Arapostathis, Ramesh Johari, and Sanjay Shakkottai. On learning the cμ rule: Single and multi-server settings. Available at SSRN 3123545, 2018
[32] Subhashini Krishnasamy, Rajat Sen, Ramesh Johari, and Sanjay Shakkottai. Learning unknown service rates in queues: A multiarmed bandit approach. Operations research, 69(1):315-22) 2021.
[33] Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
[34] Lydia T Liu, Horia Mania, and Michael Jordan. Competing bandits in matching markets. In International Conference on Artificial Intelligence and Statistics, pages 1618-1628. PMLR, 2020.
[35] Lydia T Liu, Feng Ruan, Horia Mania, and Michael Jordan. Bandit learning in decentralized matching markets. The Journal of Machine Learning Research, 22(1):9612-96)) 2021.
[36] Nan Liu, Yuhang Ma, and Huseyin Topaloglu. Assortment optimization under the multinomial logit model with sequential offerings. INFORMS Journal on Computing, 32(3):835-885 2020.
[37] Avishai Mandelbaum and Alexander L Stolyar. Scheduling flexible servers with convex delay costs: Heavy-trafis optimality of the generalized cu-rule. Operations Research, 52(6):836-88) -555 2004.
[38] Nick McKeown, Adisak Mekkittikul, Venkat Anantharam, and Jean Walrand. Achieving 100% throughput in an input-queued switch. IEEE Transactions on Communications, 47(8):
1260-1261 1999.
12

---

[39] Aranyak Mehta, Amin Saberi, Umesh Vazirani, and Vijay Vazirani. Adwords and generalized online matching. Journal of the ACM (JACM), 54(5):22-cs es, 2007.
[40] Aranyak Mehta et al. Online matching and ad allocation. Foundations and Trends& in Theoretical Computer Science, 8(4):265-368, 2013.
[41] Michael J Neely. Queue stability and probability convergence via Iyapunov optimization. arXiv preprint arXiv: 2010.
[42] Michael J Neely. Stability and capacity regions or discrete time queueing networks. arXiv preprint arXiv: arXiv: 1003.339,, 2010.
[43] Min-hwan Oh and Garud Iyengar. Thompson sampling for multinomial logit contextual bandits. Advances in Neural Information Processing Systems, 32, 2019.
[44] Min-hwan Oh and Garud Iyengar. Multinomial logit contextual bandits: Provable optimality and practicality, In Proceedings of the AAAI conference on artificial intelligence, volume 35, pages 9205-92133 2021.
[45] Abishek Sankararaman, Soumya Basu, and Karthik Abinav Sankararaman. Dominate delete: Decentralized competing bandits with uniform valuation. arXiv preprint arXiv:2006. 1616,, 2020.
[46] Flore Sentenac, Etienne Boursier, and Vianney Perchet. Decentralized learning in online queuing systems. Advances in Neural Information Processing Systems, 34:18501-18512, 2021.
[47] Thomas Stahlbuhk, Brooke Shrader, and Eytan Modiano. Learning algorithms for scheduling in wireless networks with unknown channel statistics. Proceedings of the Eighteenth ACM International Symposium on Mobile Ad Hoc Networking and Computing, pages 31 40-40, 2018.
[48] Thomas Stahlbuhk, Brooke Shrader, and Eytan Modiano. Learning algorithms for minimizing queue length regret. IEEE Transactions on Information Theory, 1755):755-11811 2021.
[49] Alexander L Stolyar. Maxweight scheduling in a generalized switch: State space collapse and workload minimization in heavy traffic. The Annals of Applied Probability, 14(1):1-53, 2004.
[50] Leandros Tassiulas and Anthony Ephremides. Stability properties of constrained queueing systems and scheduling policies for maximum throughput in multihop radio networks. In 29th IEEE Conference on Decision and Control, pages
IEEE, 1990.
[51] Leandros Tassiulas and Anthony Ephremides. Dynamic server allocation to parallel queues with randomly varying connectivity. IEEE Transactions Information Theory, 39(2):666-47,, 1993.
[52] Zixian Yang, R Srikant, and Lei Ying. Learning while scheduling in multi-server systems with unknown statistics: Maxweight with discounted ucb. In International Conference Artificial Intelligence and Statistics, pages 4275-4312 PMLR, 2023.
[53] Lijun Zhang, Tianbao Yang, Rong Jin, Yichi Xiao, and Zhi-Hua Zhou. Online stochastic linear optimization under one-bit feedback. In International Conference on Machine Learning, pages 392-401, PMLR, 2016.
[54] Yirui Zhang, Siwei Wang, and Zhixuan Fang. Matching in multi-arm bandit with collision. Advances Neural Information Processing Systems, 35:9552-9563. 2022.
13

---

A Appendix
A.1 Limitations Discussion
We leave several questions open for future research. Firstly, it remains an open problem establish lower bounds for queue lengths and regret. However, we helieve that constructing a lower bound would be much more challenging compared to other parametric bandit problems. Additionally, improving the dependency on for queue length and regret bounds from the structure of MNL would be an interesting avenue for future work.
Regarding computation efficiency, we note that updating estimators in our algorithms computa- tionally efficient because they are based online updates with convex optimization for updating estimators. Concerning combinatorial optimization in our algorithms, we can alleviate computational costs using a-approximation oracle algorithms, discussed in Appendix A.9 Note that almost all combinatorial bandit problems, including our proposed matching bandit framework, involve a combinatorial optimization step which often relies some type of approximation optimization oracles. Hence, this is not particular limitation specific to our study. However, developing an improved approximation oracle would also be an interesting direction for future research.
A.2 Discussion on Traffic Slackness Parameter e
As in the closely related works of [15 52 23], the traffic slackness remains constant regardless of the number of agents and the number of servers K as c 6g for some < ED < 1. However, this may not align with intuition,
large K might be beneficial in terms of traffic slackness, while large min(N .K) This reflects N could have the opposite effect. To address this, we can consider c cg N
that when N 2 K, due to the lack of servers, increasing K' is critical for increasing traffic slackness, while increasing N could decrease it. When < K implying there are enough servers, however, the value of N doesn't impact the traffic slackness because each agent can be assigned to at most one server at each time, and there are sufficient servers handle the agents.
we consider the traffic slackness as = ED N.k( the oracle strategy of Max Weight achieves Q(T) = ( N from Proposition This result shows that as N increases, causing the traffic slackness to decrease, the average queue length increases. Meanwhile, the positive influence of K on traffic slackness is neutralized in the average queue length bound due system variance.
A.3 Proof of Proposition I
Define the set of queues Q(1) = (1)(1) E [N]] and a Lyapunov function as V(Q()) = EnE[N] (t)2. For simplicity, we use (t) for Dz(t Sk....) when there no confusion. We observe that Σ nn [N] (() I Ene[N] An S Ene(n M(n|Sa, 0x) < K for some S₃ from
Assumption 3 and EMEIN An S N. This implies | [t) KJ.. We also have EnE(N) E[p(n|Sa,, 0x)] S min(K, N3. Then we have
ΣMEINY E[D,, (t)
ETV(Q(+ + 1)) - V(((t))
Σ (Q)(t) (t) + + (Q(())
=E
NE(N]
E
E
Σ (Qa(1) - An(1) Dx(1)= Qn112²
E
Σ Qn(()An() -2 Σ Qn(()))(()) - Σ An())a(()++ Σ An DuCOP
nE[N]
ME[M]
HE|N]
REIM
ME|M
E
Σ (n(1)An())) -2 Σ (t) Σ A,(1) Σ (!)())
NE[N]
ME[N]
nE[N]
ME[N]
E
2 Σ Qu(t)An(t)-2 - E (t) m (N,
(16)
DE(N]
DE[N]
14

---

From Assumption 3. we define the corresponding assortments as (St E MMM), which satisfies E [.. Then we define the set of non-empty queues in S% time Sy, {n S Qn(()) * 0}. From the property of the MNL function, we can observe that yu(n S 0x) I p(n|Sk,e 0x) for all n E Sk.e We also note that [Sk,tReEKK &M(G). Then have
An + I uunn k Bt) for all n Sy and k
Σ (An + e)Qn(t) REIN]
E
Σ
p(n|s (t)
kE|K] nEs
Σ
Σ
p(m|Sk (t)
k n
Σ
M(m|Sk,r. 0%. (n))
kE|K] nESk,
where the second inequality is obtained from (k, (.) S p(n|Sk 0x Qm)) when E Ne. and otherwise ( Og (l) , Qn)((()) = 0.
This implies
E
Σ E KE NES
(n(t)Dn(t))
=E
E kE[K]
E (,(t) Q(t)
Σ
Σ
Qn(D)(n/SEsss 0s)
AE kE[K] nESt
Σ KE|K] nES
Σ
Qn(t)u(nSSE,..0 0k)
2 Σ N
(An + (t))
(17)
From Eqs. 16) and 17 have
ED(Q + 1)) V(Q()))
E
Σ (x(()An(1) - Σ (x(())n(t)
+ min (N, K}
nE[N]
nE[N]
E
Σ (n(t)An - Σ (n(t)Dx(t)) Q(t)
mmin (N, K}
REIN]
NEIN]
<
E
Σ 1n)a(1) - 2(), +0)(((()))
+ m2nin(N, K}
[
< -E
2E
(t)
+ 2 mi,
NE(N]
which implies from VTQ(T + 1)) 2 0 and V(Q(1)) = 0.
Σ (E[T]
EQ(Q(++ + 1) (()))) = V(Q(T + +1)
S - Σ E Σ (x) + KK.T
:E[T]
nE[N]
Finally, we can conclude that Q(T) (1/7) E [ EE
3 (x) 2min (N,n(NK))) K}/e.
15

---

A.4 Proof of Theorem
We first define the set of queues Q - (Qn(1): : E [N]] and Lyapunov function as V(Q = EnEIN) (1)2. For simplicity, there no confusion. Then analyze the Lyapunov drift follows.
(1,(1) for (.(()S.....)) and (1) for D (4]Sk .t) when
Σ v(Q(+ + 1)) v(Q(t))
1E|21
E
Σ (Qn(1) + An(1) - - -(((t)
NETT REIM]
Σ Σ (Qn(1) + An(1) - D2(1)² Qn)
tE[T] REIN]
3Σ (Qn(1) + An(1) (2)
ΣΣ (Qn(1) + D2(0)². (18) AE(T] ME[M]
(E(T] ME[N]
We observe that Σneiv B[A,([] S EnENN An E p 0k) K for some S₃ from Assumption 3 and EmEiN] An I N. This implies [n
(An(t) S [N, KK. We also have ΣNEIN (t) = EnENN) [[p(n] 0%) I min (, N.. For the first two terms in Eq. 18 by following the same procedure of Eq..(16) and we can obtain
E Σ (t) + An (2)()) Qn((t
4E|2" BEIN]
$ Σ
Σ (A u(n (al0An-umnsst..0 0z))),. + min m KYT
EE|T) ME[M]
< Σ
Σ
2c (1) + 2 m KYT,
(19)
(E(T] NE[N]
where the last incquality is obtained using Assumption 3
For the last two terms in Eq. 18 we have
Σ Σ (Qn(t) + An ?
Σ Σ (Qn(t) + An(t) (t))
tE[T]
RE[M]
1 nE(N)
Σ
Σ
(t) - (1) 2A, - (t) - (t))))
(E(T) NE[M]
Σ
Σ (x(,) - D2)()) Σ Σ (1 + Σ Σ D.(()²
() [N[N]
NE(N
RE(T) DE[M]
+2 2 Σ Σ
(1) (1))))n()))
(E[T] RE[M]
Σ Σ
(t +2 Σ Σ (D) (x(t)) + ( KYT
(ETT] nE[N]
1E|T) NEIN
2 Σ Σ (t,(t)
(.) + min (N, KYT.
(20)
[ NEIN
Now we provide a bound for Eq. (20). We first provide some lemmas for the concentration of estimators.
Using the above lemma, can show the following lemma of the concentration.
Lemma (Lemma 9 in Oh and Iyengar 44)). For 2 1 and some constant C₁ > 0, with probability least 1/t2. all l E [K] have
l10r.t 0xllva,, BB
Proof. For the completeness, provide the proof in Appendix A.8
16

---

Define event E, {10k, - V. B, for all h /+ CIVA+
[K]] where Se
Ci
log(1 + tLK/dA), which holds with high probability as P(EE) 2 1/t2 from the above lemma. We also define F (maxmese. | lolllv, S C2e/228 /2, for kn,e) for some constant C2 > 0. Then, we have
Σ (t( D.(()Q..())
TE(T] ME[M]
Σ
B[E((DA(1) D2(()Q=(0)))0000)
AE (T) [E[M]
p(n|Sk; en Okn..) - ((Tr)SSS...a Ok... ()Q((()]
(E(T] ME[M]
Σ
Σ
[[((( Ska. Oui..) ( Ok.. ()Q,(())())))))))))))))) n E2,0
RE(T) ME[M]
Σ
Σ
Pn... B[[u(n]Sue Sue, Okz (Q0 + ((EE,))))
KETT
(21)
Now we provide a lemma for bounding the first term in 21)
Lemma 2. Under E,, for any n [N]. we have jit B Okm,ee) - 1 pn 0kn,)) S
Proof. Let Un,ktt = N O2. Under F), for any E [N] and l: E [K] we have xr Az. Bellxnllv.; S
a. 0g S x. Ox, 3r lanllyy which implies 0 S JUCB un,ktt S 2/ al Then by the mean value theorem, there exists Un (1 UCB + cun,k,t for some E (0, 1) satisfying, for any n E Sk. Sx C [N], and E [K].
n.K.t
exp (HC
exp(un,k.)
UCB (n|Se, Ov.e) (un1)nn) Se, 0x)
1 Emss. exp(hUCB)
Emes, exp(Um,tet)
exp(U,)
Ven
(hi,ke
kn.k.)
I Σ Emes, exp(Um)
expl Üm, (..
un,kee)
n.kil
1 Enes, exp(ūn,,,))
<
UBB
n,,k!
Unnke
< 2,3 In cnlly-t
Since z/(1+ + xx) a non non-decreasing function for > -1 and x Osz, S xx Ok. + Bella Verla
under Ed, we have p(]|Skt,, 0z: C/C (n|Sk:.. :n:...) Then for the first term of Eq. 21)
17

---

we have
Σ
(u(nlSki..tt in Okg.)) - pa(n) (k... Okn, ()Q n F
tE(T]
MEIN
Fi
C (nlKk, Oki - ()2m.))))(())11())))) n EE.))
(E(T)
nE(N]
Σ 1E(T)
E
(UCB [ Osm..t) - p((TSSnn.n . ()Q((()1(())))) E
nE(N]
Σ AETT)
E
Σ
28 Qu(()((E) n Enne)
nEIN
C2
Σ
Σ
(1),
(22)
1E[T] nE[N]
where the second inequality comes from the UCB strategy of the algorithm, the last second inequality obtained from Lemma 2 and the last inequality is obtained from F
Now provide bound for the second term of Eq. 21 We first have
Σ
Σ
(u(n))SE Okn.)) - p(n) Ok (1
KE|T NEIN
Σ
Σ
((E))))((EE)))
1E|T] RE(N]
Σ
Σ (P((E)))
KE|T] RE(N]
= Σ Σ ((/ee) (E(T] NE(N)
= ON log(T)),
(23)
where the second inequality is obtained from Qt) S t.
Here utilize some techniques introduced in Freund et al. 11). Let Tn be the set of time steps t [T] such that Q (t) A 0 and let eT = ΣnEIN EieT, I((E2,) and = [Cget/e] for some constant C3 > O. Then if t < h. we have (t)(t) I tt h. Otherwise, we have
Qn(t) < Σ (1/h)(Qn(s) + (t- 3)) s (1/h) Qn(s) + (1/h)12= (1/h) Σ Qn(s) hh.
1+
18

---

Then, from the above inequality, we have
E SK Ox - umnlSkmee.. (0..)))
1E NEi
Σ
B[(u(n|Sk .. (b. ((E),)))
nE[N] T.
x Σ
Σ
(((2,))
nE[N]
Σ
E B[((e/C3eTT
Qn + 2Cgee/e)111 ( Σ
nE[N]
<
(e/Ca)
E NE[N]
Σ
+E [2/20g0//e]
Σ Σ (() + ///6/6
(t))
(24)
REMT
Now we provide bound for E[e7]. Define Nn,(()) E 1(n Su.a) and Vanned
Ex=1 Enerr. Inz Then, we have
EE Σ
Σ 1((E2,))
=-
RE[N] TET,
Σ
Σ
1(1 Vanle 2 C2t/23)
WE[N]IET
Σ Σ
1(1
Cge/23))
RETN
Σ
Σ
1(1/N.....d 20) 2 (x/2)((cx</28)))
NE|N
Σ
Σ (.N.A....) (2)
IET
Σ
Σ 1(Naa()) S (2/x))23r/C22)) and kn, = k)
< NK(2)
From the above we have Ele2] <
Then from Eq. 24 we have
Σ Σ
B[(u(n|/S
- 1 (0.
1E NE
Σ Σ RE(N
(25)
19

---

By putting the results of Eqs.
18
19
20
23
25
altogether, we can obtain
V(Q(L+ + 1))-1))---0 ((Q))))
FE|T]
mii N, KJT 22 Σ
Σ
B [(Qx(0)) +2 E Σ
E (D) D
EE(T) [E[M]
1E[T] NE(N]
< mminn KJT - 2e
Σ
Σ
[[Qx(0] + 2C2e Σ
Σ [[2((0)
NE[T]
RE[N]
NE[T] DE[N]
+O (o(Nlog((T)) + (2e/Ca)
Σ
Σ
E ((] + O(N2 K2 24))22)
(E[T)
[i, KYT + 2(C + (1/Cg) - 1)c Σ E BQQ, (t) + O(N log(T)) OONN
(E[T) NEIN]
Finally, with positive constants C22 C3 > 0 satisfying C2 + (1/Cg) < 1. from v(Q = 0 and
VQQ(T + 1)) 2 by using telescoping for the above inequality, we conclude the proof by
T Σ
Σ
1 Σ
[(Q, o min (N.K) K}
T k/e6 polylog(T))
1 N2
(26)
(E[T]
NE[N]
A.5 Proof of Theorem 2
We first provide the proof for regret bound of (T) 5 (4VKTQQUM
We define event Eg = [llθ,, - 0gllve, S Be Ak E [K] which holds at least probability of 1 - 1/t2
from Lemma [
Lemma 3. Under for any S& C [N], we have
Σ nES
(m4 (n) 0k.)) - [([|S&,, (t)) s 23, max
| 2, (t).
neS,
Proof. Let Un, = TTJ 2z- Under F,,, for any n E [N] and & E [K] we have x. 0z. - Bell vel S TT 0g S xx On, + Br (ainnlll,,, which implies 0 S N.C.B Undket S 2Br 1l Ilv. Then by the mean value theorem, there exists Un,det (1 c) + CUn,k,, i for some E (0, 1) satisfying, for any S c [N],
UCB (n|Sk. 0x,1) ((n)Ss, (mt
nESk
exp(hCCB)
exp(un,k.)
Σ nESt
Qn(t)
1+ 1+ Emes. exp(hUiR)
1+ Emes, exp(um,.id
exp(en)
V
(N un,k. Q((()
1+ Emes, exp(em)
neSt
Enes, ())(ū,,k.:)) exp(ūn..e))
(NUCB Un (n,
(1 E nEs, exp in k))
Enes, exp(ūn,k.:))) exp exp(un,Ae (u,, (NUCB (n))
Enes, exp((nn,,.))
exp(ūn.t.t)
( Qn((
1 Emes, exp( exp(ūmmk,.) k.),
neSt
< max
max(h
(N un,k. (1)
UCB
nESt
2,, max | Qz( nES;
20

---

Under E, from Lemma 3 we have
Σ
(T (n S Be.) - (xn]s,,,,,)))0n. 2 max || 15 nEStit
(27)
and since x/ (1+z) is non-decreasing function for -1 and x ORa. S x o ki t.eelannlly
under Ey we have
p 8k
14
UBB
(n|ski G (r
(28)
Now we provide an elliptical potential lemma.
Lemma 4. For any [K], we have
T
Σ
| l S (4dfk) log(1 (1 + (TI/dX)).
max
NESt..
Proof. First, we can show that det(Vx.))
det
Vi + (15/2)
Σ
In T
RES
= dct((Ve.--1) det
Ia +x/21/2
k,1-1 2n (V
nESt.t-1
2 det((Ve,-))
(x//2)
Σ
|
nES
1-1
2 det(ALa)
II
1+ (x/2)
Σ
|amile
xd II
1 (x/2))
Σ
|| 1i--
nES
neS
From the above, using the fact that æ s 2 log(1 + x) for any x E [0, and (</ (x:/2)|[Emll 12, S
(x/2))[z> 11 from K have
Σ max (k/2) | 12nl
S min
max (x/2)
Inn v. ke
nESt.
nESt.
*E(T]
< 2 Σ
log
1+ Σ
(E[T]
nESt.
2 2og II
1+ Σ
(x/2)|lz:n111>
(E[T]
nESI.
del(VV.T+1)
< 2og
(29)
Ad
From Lemma 10 in Abbasi- Yadkori al. [ with 1, we can show that
det(V < (A + (TL/d))
Then from the above inequality and Eg 29
conclude the proof.
21

---

Then from Eqs.
27
28
and Lemma we can conclude that
(T) = Σ
Σ
([Qn(t)u(()) Swi OK:..) - pl(n Sr..k....t Okn..)))
tE[T] RE[N]
Σ
Σ
(() SK Saa Oki..) p((]SSkn.et 0knn. (E)()
(E[T] NEIN]
+ Σ
Σ
(( en OK.,) ) (n( Skmnr (k..)))(((E))
(E[T] nE[N]
Σ
Σ
((Qu(()(u(()Ss SK. BKg,.) pu(nSSkn Ok 1)
Σ Σ {P((E))))
1Ef2 NEIN]
tE/2 NEiN
< Σ
Σ
(1Q4(
UBB (m) SEz ai OAn - ju(n|Skm, Ok... () O(N/T)
tEfT REIN]
Σ
Σ
(n) Sk O ( (e. + (1Q4
(E[T) REIM]
= Σ
B Σ
Σ
- -0100
LE|T
kE[K] NESk,t
s 2E
3T Σ
E
max nESa.
| (0l22((()) Qn(t)
+ +O(N/T)
(E(T) kE(K]
S 2E
max Qn(1)3r
Σ E
max nESk.l
+N(N/T)
<E [E]
(E[T] RE[K]
< 2E
max [E]T),EE[N]
Qu(1)
KT Σ
max Σ
|anll V
+NN/T)
nESt.
1E|T KE[K]
- d 1KKQQma
where the last equality comes from Lemma
Now we provide the worst-case regret bound of Rd (T) = Ō (( min SaainnNN.ae (N.K3
1/4 T3/4 in the
N"c
following.
We define event E,
[1(0,, 0fllve. S Br for all e [K]] where 8, v A + d log(1 + tLK/dA), which holds with high probability as IP(E)) 2 1/t² from Lemma We also define F? (maxmesu. || llve S Ç for t kn,)) for some constant
Ci
C2 0.
Then have
RT(T)- Σ
Σ
Bl(u(n|Ska.de Okz p(n]S On.,. (1)
EE[T]
M
Σ
Sk( ne Owz.) (nn.))pp(nSss..... OR.,, (t)x(() n =
1E|T NEIN]
[(((nn)Sk Ok..) ) (n (L) +1((++1(100000 1(( )))
nE
(30)
22

---

Since x/(1+z) x) is non-decreasing function for > -1 and x Ox:, S Sxn 0x + Bella y
under Ey. we have p(n]Skr...t 0k S 1tl F [ (n|Sk=, (.),.)). Then for the first term of Eq.30)) we have
Σ
(u(nlSki.ens Ok - pann Okn, ()Qm)))) n E,
tE[T]
MEIN]
Fi [ CnCCBn (n - p(nlSkr... Ok., () EE.
(E(T]
nEIN
Σ TE(T)
(UCB ( (m|Sk...r Osm..t) - pl (K ))Qm)))))()))))))))))))))))))))) E
(i
nE(N]
Σ E
23ell=nllve Qu(())(E) n E2,))
LE|T)
[E|NN]
Σ
2 (0)(
(31)
(E(T) ME[N]
where the second inequality comes from the UCB strategy of the algorithm, the last second inequality obtained from Lemma and the last inequality obtained from F
Now we provide bound for the second term of Eq. (30) From Eq.
23
we have
ΣΣ TE[T] nE(N]
E Sui On. - p(n) Ska.ert OR., (20
Σ ((1/3) (E|T)
=O(N log(T))
(32)
Let Tn be the set of time steps t E [T] such that Qn A 0 and let = Ene(N EIET, I((E22))
and h = [1/G3r]. Then if t < h, we have (t. < t < h. Otherwise, we have
Qn(1)s < Σ (1/4)(Q())) (1- 8) (1/h) Σ Qn(s) + (1/N)/² Σ Qn(s) h.
Then, by following the steps in Eq. 24 we have
Σ Σ
B[[u(n]SSc, Okz .) Monnul(nSSSaaaaaa De.. (())))))
17 NE[N]
Σ Σ (3TE(Qn(1) 2E(er)/(3r. RE(N
(33)
23

---

Now we provide a bound for B[erl- Define (t, E 1(n E Sk.a) and Vr. E1=1 Eneoe.. Inin. Then, have
= E E 1((E))))
REIN TET
Σ
Σ
1(1 Ven... 20)
nE[M] TET
Σ
1(1 V.r
20) Eajei
ME TE
E
Σ
1(1/Nm.o., (t) (x/2){²²
RE|M
Σ
Σ
INN.A,, (0 (2/K(())
ME|N] TE
Σ
E
Σ
1(N.,(1) S 2/x(2 and kn, k)
NEIN KE(K] TET
s 2NK/RC².
(34)
Then from Eqs.
33
34
have
Σ
Σ
[[[u(n]SSE..dt ) - p(nlSSa..... (0,))))
1E NN
Σ
Σ
(35)
KE[T] nE[N]
By putting the results of Eqs. 30
32
35
and Theorem by setting <
(eNK/ m//mm,n(N, K KYTx383))/4 1/4, for large enough T, we can obtain
R²(T) =0
G3T ΣΣ
(()x +
NK RC3
+ Nlog(T)
*E(T] PE(N]
( min(mi (N,KKI
NK
+ +Nlog)))
KC
///2T/// (NNKS/A(KNANNA min (N, K3311/1
+ N log(T)
3/4
(NNK min N, KJS) 1/4
T3/1
(36)
R26
A.6 Proof of Theorm 3
We first define the set of queues Q(!) (Q) n [N]] and Lyapunov function V(Q())
EnE[N] Qn)))). For simplicity, we use (t) for D (t)tSS,....) (t(() for (nt()Sks, e). and
TTS
24g (n)))..) for (n]SSn) (0 (E(M)) when there is confusion. Then we analyze the Lya-
24

---

punov drift as follows.
E
E + -
T
E
Σ
E
(1)(1)+ + An(t) (=(())+²===- - Qn((t)²
#E|T] nE[N]
Σ
Σ
T [(0n()) + An(1) D2(1)) Qn(119)
AE(T] ME[N]
Σ
E
B (On(t) + An(t) - Dx(+))+² (((()))=-(000))) + A.(t)) -
(E[T] NE(N]
S 7 (ainnNNKY2 K|T-
E E +2
Σ Σ
( (x)+))),,),,,,, (37)
BE|2" NEIN]
LE[2] nE|N]
where the last inequality can be obtained by following Eqs.(T9) and 20
f10k.. OellvE. I 3, for all Ci Civ A log(1 + tLK/dA), which holds with high probability as P(E))
Define event
E.
[K]] where 8e
1/t² from
Lemma We let 7/- = Br / log(MKt) and filtration Fz be the o-algebra generated by random variables before time t.
Lemma 5 (Lemma 10 in Oh and Iyengar (3)). For any given Fi-1, with probability least
1 - O(1/t),, for all n E [N] and & E [K], we have
hh n, x 0x.1 alllallve!!
Lemma 6. With probability at least (. for all [N] and [K], we have
WT*(n|Se.d - [(n|Sk. dx.e) S rellanllvz!
Proof. From Lemma 5 with probability at least 1 (11(2), we have 1 xTorrl S x Os.e- Then by the mean value theorem, there exists Un (1 - c)hTT + Cun,kkt for some E (0, 1) satisfying, for any n E Sk, and ls E [K].
Vol rellanllv-.. Let Unkket
exp(hTT.
exp(um.k.t)
14 3T. (n|Sk.) u(n|Sk, 0k.1) 1+ E exp(hTs m.k.)
Emese, exp(um,k,t)
Emesm, exp(um)
V.n un
TS Un.k.)
1 1 Emesa. exp(Um)
ex exp(ūn,kk.))1ip Unkktt
1 + Eneso, (xp((nnx.)))
n,k,t un,a.e
7e nel1x=llv
Then we define E3 = ( - Sn(r On.e) S ullualllz E [N], vh: [K]] which
holds with probability at least (11(12) from Lemma also define E = { {11xally-- S
25

---

c/C2(n + VK E [K]} for some constant C2 2 V7VET. Then, for bounding Eq. 37 we have
Σ
E
(1( D2(tt)x(())
EE ne(N]
Σ
Σ
( (x((()Q((()))..(()
tE[T] NEIN]
E E
Σ
p(n (k: ((nnSkk.,,tt 0km, Q))((t)
1E|2 nEIN]
Σ
Σ
Bl(u(n) Sk: ant OK..)) ulm|Sk... OR.,, (t ()Q n n
tE|T] [E[N]
Σ
Σ
[[((n||S S ens Osn.)) - On. (1) (((E))) + ((E))))))))))))) )))-
(E(T] [E[N]
(38)
We provide bound for the first term of Eq. 38 We first have
Σ Σ
[[[p(n|SM Oki.)) un( Ow. ()Q,()) n E n E3,)
(E[T] nE[N]
Σ
Σ
E[(((n) Sue. Okn. TS (n Skm,).))
KE[T] NEIN]
+ P1 (n) - p(nlSkk..ee Ok.. Oa. (t)(()) n EE n E2,01
(39)
exp(h
Recall that 2 (n|Ss, = 1+2 exp(hoogg) Then we can show that since x/(1 + x) is
under Et, with a non-decreasing function for x > -1 and x O S x O + &ell knnee
Lemma 2 we have
[nnlSkanad p(n|Skan.tt Bkn,)) S Pt BUCB
(n|Sknrre 0.m, (n Ox..) S 25 || -
From the above inequality, the last two terms in E9) are bounded as
Σ
1i Sk..S.....)
( Ok... (1 n E
KE|2"
N
Σ
Σ
E [ T9 (m) Sk..))...) pnnnSSk........ Ō Bk.,.st
tE[T] RE(N]
Br.. (). E E Qt)(t) E (nl St....)) p(n)Skmeett Okm.et) 23p 2.32 1 100 n E² E
+ Skn Bkm.e.t)
Σ Σ
1E[T] RE(N]
ΣE
Σ nES
TTT (n(Sk.)) ( B2.)) + 21 n E n B
26

---

EEE NE(K]
Σ nESL.
(7x 23x) (5allv (x(() n Ej En.
(ot + 2/x)cc C2l1 + B()
ΣEE [E(])e([K]
E
Σ
Qn(t)](E) E E
(ot + 28r)c
Σ NE(T] KE(K]
Σ
E
Σ
Qn (t))
C2(Ti + B.)
n
(7h + 2.r Qn Fi Fi-1 P(E))F(11)
ΣEBB
E
(40)
C2(1 Bc)
KE
RESE
Now we provide bound for the first two terms in Eq. 39.
39
define sets
+. =110 D
max NT, TT
xx 0K
sollaully Vn [M, va E 181] and
iE[M]
6,me - -(18") HEGMIAEIMAAEI
E Σ
MT (n) Jretan)
KE[R] RESU.
Σ kE|K] neSt
(n nā.
Then we define event E,(0) = -10% E ",rh). Recall T5 = max x. 0. Then we have
E
E
Σ
Σ
Σ
pe TTS (n|S 100 (e2 1(E) nE? ER,
KE[K]
nEST.
nES,,1
E
E
Σ Σ
M(n)SE,,
(E(K)NEST
inf
max
Σ
Σ
p. T (n|Se. (0 HeMM))(() I(E) n E? E
10 Heete Eθ, (Se)NEIkjEMONi)
kE[K] nESt
E
E
Σ
Σ (nn)Se,..4))..l
NEST
max HEeee E (Se)NEINJEM(N))
inf
Σ Σ
( 100h (e) I(E1 E3? n F2 Ei(0)
(of))
KEIK] nES.
E
E
Σ
Σ
ITS (m)
(n) Sk,t (eE))))
kE(K) nESke
inf
Σ Σ
प.. T Sw,er 100h BEM)) (.(()((E) n EE (EEE) ER E,(0)
(0 heIM c KE[K] nESu.
27

---

E
E
sup
ΣΣ
M ( (m|Sk.e: (0.
(0 NEIM E KE(K] nESk.
1ot (nlSk, 10 hEEM))
) Q.(()) n E n F E.
E
E
sup
E
E
n,K,t
max x, ( TT() Qu(t)](E) n E n E | (0)
(0(1) JE CO kE(K) nESk.
JEIM]
E
E
sup
Σ
Σ
h n,K, In On, + x O2,t max xn 06 jE(M]
JEIM KE nESE
xQn(1)((E) n E n Ex F E, (0)
< 2
Σ KE[K] nESk.
Σ
E 1. n E |F Ei E00
E C2(T1 B1) On(() n E n 1 E2(0
< 2
kE(K] nESp.
(n(()((E)) Fx(0
$ B
E
C2(T + Be)
KE(K) K) nESk.
24/
Σ KE[K] nES!
Σ
[Qn(tt)F=LLEd000 Ei| x (())
C22( + 3.)
2/E
Σ Σ [Qa(())F=111 Ex ((E)) vE[K]nESL.
(41)
C2(7. + 3.)
where the first inequality is obtained by the event E? the second inequality is obtained from E, (0). the third inequality can be easily obtained by following some of the proof steps in Lemma 2 the third last inequality is obtained from the definition of +, and event (0). and the last equality comes from independence between E and (0) given F,-1.
We provide lemma below for further analysis.
Lemma 7. For all ( [T], we have
P
Σ Σ kE[K] neSu.
MT'S (n))
Σ Σ kE[K] nESt.
2 1/4VET.
Proof. Given Ft-1, x ( follows Gaussian distribution with mean x., 0.., and standard deviation 8ellznllv.. Then have
IP max x, 0. T. F. (E[M]
=1 P
Ji 0K
x. Os: Vi [M]]F- Ft))
Z, T 02
xx7 T
=1 - P
vi [M] Eb!
B x ll
21 - P (Z < 1)
28

---

where Z₁ and Z are standard normal random variables. Then we can show that
P
Σ
Σ
Pi
(n (n))))))
E kE[K] n
E
AE SE.
P
Σ
Σ
TS M1
(n) (2)(())))
E
Σ
KE]K] NES
KE[K] nES
2 P max I k,t
T. In PR: vn E 2h Ak E [K]]FF-111 F
iEIM
2 1 LKP(2 Z - 1)
2 LK(1 1/4 M
Aven
where the second last inequality is obtained from P(Z < 1) 1 1/4vem using the anti-
concentration of standard normal distribution, and the last inequality comes from M = []
lng KT.
log 1/4vem)
From Lemmas and for 2 to for some constant to > O, we have
((E,(0)(F-11.))
=P
Σ Σ kE[K] nESt.
(m(SkA))
Σ
Σ
p(n|Sk, 0x) and (0 (OLINEIN G.IFF.1, Fij
kE[K] NESt,
P Σ
Σ (1(sa)))
Σ KE|K]mEST
Σ
KE|K] nES...
SEMMM & (.(FF,,,EE) P((1k))
2 114Ver-001
2 1/8VET.
For simplicity of the proof, we ignore the time steps before (constant) ty. which does not affect our final result. Hence, we have
E Σ
Σ
(u(
KE[K] SE.
E
Σ
Σ
Q,(0)=-,,,E) ELOEEEE))LLL
K]
nESk.
E
Σ
Σ
Qa(0)=--1, F,, (0()
(42)
K] NES
With 41
and
we have
E
u(nlSk... 0n)
Σ
Σ
M
TS (010 n E n [I
K nESt.
kE[K] nESt.t
27 C2l1 + 36)
E
Σ Σ kE|K] nESK.
EO))), E P(E
16V C2(1 + 3)))
E
Σ Σ
E
(43)
nESt.
29

---

Then for the first term of Eq. 38 from Eqs. 39
400
43
for some C3 > 0 we have
Σ
Σ
in ok;.)) - (((1) Skm,. Pk.. ))Q.((t)(E)))))))) E n E
(E[T] ME[N]
Σ
Σ ([((nnSSkiitt Okū.) 14g T (m (km,,))))))
(E[T] NE[N]
+ pl V (nl (m|Sk..it) - uu(nSk..... ( n E E2D) (17VeTH: + 23.)c 2n Q.((6))7--1EEE/((EEE11.
Σ Σ
EE Σ
C2(7 + 81)
(E[T] KE(K]
nESNJ
Σ Σ
FL F(-1)
tE[T] nE[N]
Σ
E
(()
AETT DE|N]
Σ Σ (t)) AE(T] DE[N]
(44)
where the second last inequality comes from C22 2 17. For the second term of Eq.
38). we first have
Σ
Σ
E
.. Ok;..) - 1( (1))
[
Σ
Σ
((E)))
(E[T] NE(N]
Σ
Σ (P((E))
(E|T] NE[N]
Σ Σ w//e3) -N log(T)),
= =
(45)
LE|2 NEIN)
and
Σ Σ
E (H Ok) (t (12)))))))))))))
1E|2 nE(N]
Σ
Σ
((23))
(E[T] nE[N]
Σ Σ (P((E)))
NE(N]
o
Σ Σ (1/02) Eu/e) KE|T]
=O(N log()).
(46)
Let Ta be the set of time steps [T] such that Qx * 0 and let er = =EnE(N] ELET, {((E )
and h = [C4eT/E] for some constant C4 > Then if t S h, we have Qn(1) S15 h. Otherwise, we have
Qn(1) 5
Σ (1/h)(Qn(s) + (t- 3)) s (1/h) Σ Qn(s) + (1/1)62 ((/h) Σ Qn(s) + hh. s+t
30

---

From the above, we have
Σ
Σ
B[(unn]Ska,.n .i Oxz - p Oz... (
1E IN
Σ
Σ
[[[an]]Skk..... OKI,)) Ot.
ME| TT
Σ
Σ
((
nc[N] LET
T Qn(s) + 2C ((F%))))
Σ
Bl(le/C(eT) Σ
nE[N] LET
< E
(e/Ca)
Σ
Σ (s)
+ +B [2/20ee//e
NE(N]
Σ
Σ
(Q,,))
+ 2C
(47)
NE|N
Now we provide a bound for B[e7]- Define (1))(1) Et 1(1 E Sk.s) and Va, (x/2) E Zn Then, have
CT c- Σ Σ 1((E),)))
ME(N] LET
< Σ Σ
1(1 AIIEanlVET 2 2c/O2/m + Bc)
NE[N] TE
Σ
Σ
1(|
2c/C2ln + 3))
MET
< Σ
Σ
(122))(cc/(((xxx+1 + +,))))
nE[N] TT
Σ Σ 1(Nr,k., (2/x)
s
BET
< ΣΣΣ (NN,a(1) < (2/x) + =2)) and kin,s k))
(E[N] KE
From the above we have Eje2] S N²K334/=2) + Br)/e)². Then from Eq, 47) we have
Σ Σ B[(u(n|SS,,....
17 NE[N]
Σ Σ (1/C)) +x7) RE(N
(48)
31

---

By putting the results of Eqs.
37
38
39
40
45
446
48
altogether, we can obtain
V(Q(++ 1)) - V(Q(())
EE(T]
(N, KJT - -2 Σ (E [N(N]
Σ
[[Q((0))+ +2 + EE
[(( Pa(O)Qa(1))
AE(T] NE[N]
7 (N, - 2e Σ
Σ
[[Qn(1)+ + 203e Σ Σ [[Qn(!)
NE[N
NE(T]
+ +O + (2e/C4)
Σ
( (B + (T)
TE(T]
RE[M]
< 7min + 2(ss + (1/C,) - 1)E
Σ Σ AE[T] NE[
[IQx(0)+ + (T))
Finally, with positive constants C3, C4 > 0 satisfying C3 + (1/C4) < 1, from v(Q(1)) 0 and
VQQ(T + 1)) 2 0, by using telescoping for the above inequality, we can conclude the proof by
+ Σ ((Q)())) o
min [
N. K
T 6/66 polylog(T))
1 N2
(49)
NE
A.7 Proof of Theorem 4
We first provide the proof for the regret bound of δ ( 1 VKTQ 1max We define event E!
(1|0c.. 0% lva. BB Vk [K]] which holds at least probability of 1 1/t from Lemma 1 We let
T/ 3, / /l//lo/(/)) Then we also define Fi? = { ( x; 0r.l s m mel Vn E [M, 4k E
[K]). which holds at least probability of - 1/12 from Lemma 5
Then we have
(T(T)= = Σ (t) Bk:.)) ) - p(n|Skn 0k.. 0kn.))l
1E|T NEIN]
Σ Σ (t( .. Ok..)) - pi. (n|SSnnn + Tht ( (n) Skn...)) [(m]Skmme.t kkn,,)))) ))]
1E|T nE[N]
Σ
Σ
((Q Ok2.)) 1hg (n (nl(Sk....))) + TTS (n) Sk.....) p(nlSSk...t Ok., )) n E?]
(E[T] nE(N]
Σ
Σ
-TS (0((M))) Ocs..) ) The
( Skrl + -TS ( (P)((n)Sknn) (n(Sk....t) p(n On ())(()
(E[T] REIN]
Σ
Σ
(1
.n, 0v.,)) TTS Sk....)..)) + 14 5T5 (nl (n| (k....)) p(n|S OR... ()E(())))
[E[T]RE[M
(50)
Lemma 8. Under EZ all k E [K], we have
Σ
(n) p(n|S (r.1))n 3 max neSt,
(51)
4.5
Proof. Let Un,k,t = 2., 0u.t. Under E?, for any & E [K] we have |hTs un S Nh rell=nllv.t Then by the mean value theorem, there exists Un (1 e). t + cun,k, k. for some (0,
32

---

satisfying,
Σ nESk
(r4 (n|Sk) (((n(Se,0)))04
exp(h
exp(un.ke))
E nESu,
Qn(1)
1 Σ Emes, mh.ph
mes, explumaks)
Emesr. exp(Um)
Σ Vva nESke
(M (n,,k,)Qn(1
1 I+Emes cxp(Um) Un
(1+ Enest cxp(In.kt)) exp(an,t,))1 n.k.C (n,t,,)((((t))
(1+ L.+Enss, (xp()n,).)))
CEESS, exp(ūn.k,))) (\) exp ki (h (n,
(1 Enes, exp( x))
1 kn Qn)
Emesk. exp (mp()))
DESL,
max nES,,
1,,,,t (n(k,)/(n(t) S Tt max | Qn) (t).
neSu.
Lemma 9. Under Et, for all &s E [K] we have
Σ DE,
(n(n|Sa,,, 0n.1) - (x))), s 23, max neSt,
E VEuly.2 lll - Qn (t).
Proof. Since x/(1 + x)) non-decreasing function for > -1 and x -T S x T. Oxmeet Bell Bel under F7,, with the definition of iht TCB (n)Sa,r, we have
Σ (H(n)Se.,.aa.)) ((n|Sa.., (x)) nES
Σ (HUCB(n(SL.)) (4)),. nESE,
Then let Un,k. = Tz. Oz. Under EJ. for any [N] and & E [K] we have xr TT, -Blllanal ll S x. 0s 5 x. 0n, + By /aally which implies <
JUBB a.k.t Un.ke S 2.3.|l
Then by the
33

---

mean value theorem, there exists Un = (1 - c)h, + kun,k,t for some E (0, 1) satisfying,
Σ
(BUC (nlcc(n|Sk,k. 0x,e) - pl Qn))
nE SE.
exp(
(xp(un,ke.))
Qn(t)
1+ E EmsLL. exp() m,k.t
1+ Σ EEs... exp(um,,kd (mm.ke))
n
exp(Un)
V 1+ exp(Um)
(,, kn Qm)
UCB
(1+ E Enes, exp(an.kt)))
UCBB niKtt Un Qn)
(1+ +nEEs exp((n,k,t)
EnEse, (E exp(Un,k. CNU Und un QQn(1))
(1+ Enese, exp( kx)(
exp(Un,k.t)
(n (n()))))(((1)
1 1+EmEso, exp(um,k:!
DESE,
max (LUCB nESz
Un Un,kk.t) (n)
23, max ||iullyz, (n) n
Then we first focus on the first term in the above. From Lemmas 8 and 9
we have
Σ
Σ
B
Bl7
(n/SSee (km,..)) p(n]SSmn..t. Ok., (())) n E?)]
(E[T]
N
Σ
BI (m (k...s) punllSkk...tt Ok.,..t)
(E[T] RE[N]
+ * 0m...it - (1 ET)
Σ
Σ
Σ ( - M(n|Sk.e:0k.)
(E[T] KE[K] nES..
+ [u[n]Se... - (4
Σ
Σ
E[( 2Bx) max || V- (1) nESk.
1E[T] KE[K]
Σ
Σ
E[E((T + 25.) max
(52)
nES
k.t
LE|T KE[K]
We define sets
0.=(10%
@, - 10h% FEEMMIMEEK
Σ (o (TTS Sx. }eE(a)) - p(n) Sx.e. (1)
nESt.
%t max nESt.t | | (n()n(t)); Vk E [K]]
and
pppt (06 HEIM))E[R]
Σ Σ
p (n|S (m] 10(
(((())) D
KE]R] nESt.
ΣΣ
m(n|Si, (h0
kE|K] NEST..
34

---

We define event (, -1(0 [[0gHEEN E ). Then by following the proof steps in Eq. 41
we have
Σ
( 0x)0(()) - Σ
Σ
(n|Sk. (0))em))))1))) 1( n E
[K(K] NES
KE[K] NESE,t
E
E
Σ
Σ
p Qx)Q((t)
kE[K] R.
inf E
Σ
TT.s (m|Sk,t 10 ( (etn)) I(E) Ef) Er(0)
(0(0) KEIM) c kE[K] NESt.t
E
I
sup Σ
Σ
Th (n/Sk.t (elan))
[K[ NESk.
(m|Sk, (0 BETAN) ( 13)
E
sup
Σ Σ
(m) 10 (ORthE(a)) u(n|Sk,.. u(m 0x.1)
HCMICI Eb kE[K] nES
+ SK, (x,e) - (n)Sk,e 10 10% hE(M) ( 13) Ex
$ 2x
max MESL,
AEE K]
Bx
Σ
max mESt,t
RE(K)
2%
Σ
max nESe
(onnll,.20((()FF-11111 E
P(E
KE(K] K
Vee/emrye <32veTT> E
E
Σ
max nESk.
P(F
kE[K]
(53)
where the last inequality is obtained from C2 > O, we have
42
Then from Eqs. 52 and (53). for some constant
Σ Σ
(((((t) Ok: 5 (n|Sk,,).))) + PT (n) (n)Sa....)) W(nlSknn..ds 0x., (),,) n nE))
1E|2 NE(N)
<
Σ
E E
max RESt.
(33vemy) +
(E[T] KE[R]
$ C2 Σ
Σ
E
max (Te 1l Qn()) 1,,0 DES
(E(T) KE[K]
$ Co ΣΣ
Σ
E
max (re 1l) Qn(() S
1E/2 KE[K]
(54)
35

---

For the second and third terms of (5, we have
Σ
Σ
E
(u(n]Skk
ei Ok - (0.
TE|T
N
Σ
Σ
((E)))
(E|T] NE(N]
Σ Σ )P((E)))
rE[T] nE[N]
=0 Σ Σ
E ((1/8) (N log(T)),
(55)
(E[T] NE(N)
and
ΣΣ
E
E [ui Okn.) (K Okm (0200)))))))
(E NE(N]
Σ
Σ
E ((ON())(((E)))
(E[T] NE[N]
Σ
Σ {P((E)))
1E|2] NE[N
Σ
Σ
E(L/E)
O(N (oo))).
(56)
(E(T) NE(N)
Finally from Eqs.
54). 55) and (56.. we can conclude that
-
E max (7e + B₂) 8,)1 (n(()) + N Vlog(T) mESt,
(E[T) kE[K]
=0
B max [E(T",nE(N]
Qn(t) Σ Σ
max neSk.
| + N log(T)
KE[T] KE
BT NE(
max Qn(t)
KT Σ
Σ
max neSu.
| v + N log(T))
KE KE(K]
IE
d3/2
VKTQ Quax
where the last equality is obtained from Lemma
Here, we provide the proof for the worst-case regret bound of Ō ((fNK min ming
1/4 Tu/s).
We define event E.
[l|0,, 8xllve. s 3, for all E [K]] where 3,
Ci Ci/As A d log(1 + tLK/dA), which holds with high probability as I(EE) 2 1/t2 from
Lemma We also define E? (7TT ( OR.)) S 7h I 1oailly,,;, ,;An E [N], 4k
[K]), which holds with high probability as P(F 2 (1 ((()))), and define F {1 vi! S
Vi e [K]].
36

---

Then we have
R" (T)
Σ
Σ
((Qn()) Oki u(n a(n]Skm,ete (k...))]
1E[T] nE[N]
Σ
Σ
Bl(u(n] Skc ee Okz u Ok... (1) n EE EER)))
(E[T] NE[N]
Σ
[[((n|Sk Okn.))
( 1((B)))))
[E[T] ME|N]
(57)
We provide bound for the first term of (5) We first have
Σ
[[(p(n) Su: i. Ok: [ Sk BN., ()Q((()1(E)) n E n E.)))
*E[T] [E[N]
Σ
Σ
E[(u(n] Sp Ok:.)) 1ht ( (n|Sum,eit)
TE[T] [C[N]
T8 (n(SS....:)) pumnSsa.. ()n (1),()) EZ B2
Pi
(58)
By following the steps Eq.40) the last two terms in Eq.58) (58 are bounded as
ΣΣ Σ
E (n))).....)
u(n)Skm...t On (11) n F n (F
(E(T] nE[N]
ΣΣ
Σ (n 28))
P(EAFE-1))
(59)
AE(T] RE[K]
nESt,
Now we provide a bound for the first two terms in 58.
We define sets
+, 10,00 HEEEMAEEEE
max T., T.(0 (E[M]
xx, 0n. S <0llanlly, Vn E [N], vk E [K]]
and
(mlSE..::0).. Ino.
110"
(0%%)
Σ Σ
T4's (m|Sk, 100 Q())))
> Σ Σ
kE[K] nESe.
kE(K] nESt,
By following the steps Eq.44) with Eq.
we have
EBK
Σ Σ RE[K] nESt
u(n|Sk 0n)
J TS (n|SEe (00 E D [.
kE[K] n
2ncE
Σ
Σ
E Qn) 10 1 6.mt El P(E ((-1)
kE[K] nESE.t
< 16
Σ Σ e.(0) F(E..F..).. KE[K] RESE,
(60)
37

---

Then for the first term of Eq. 57 from Eqs. 55 for some C3 >> 0 we have
Σ
Bl[p(n|Sk:... Ok:..) p((n) Sk OKn. .)),(()))(E))) E2 Ex,)
1e[2] nE[N]
[[( OK TTS ( (n)Ska,,.t)
-
+ YT' (nl (m|Sk..att) uun]sSemmntt OR ()Qn(1) n E n E
Σ
E
Σ + E P(E
(E(T] KE(K]
nES
- Σ
Σ
17VeTT + -4
(T PE[N]
Σ Σ
(17VeT7) (3))(((((((((((((()))))
LEIT DEIN]
& (17VERYT + 2387)c Σ Σ (t)
(61)
For the second term of Eq. (7). by following the steps in Eqs. 45 (46) we have
Σ ΣΣ tE[T] mE[N]
(u(m) Okn.)) - u(nlSkmmeett (e.. (1.))))))) = O(Nlog(T)), (62)
and
ΣΣ *E[T] RE[N]
E (u(n)SSi Ski Ok:.)) p(n|Skm,,.s Ok.,, (km (22 O(N log(T)). (63)
Let Tn be the set of time steps & E [T] such that (x) * 0 and let er Eme(n] ELET, ((F2,))
and h [1/ + 23. Then if I h, have Qn(t) I t $ h. Otherwise, we have
Qn(t) 5 Σ (1/h)(Qn(s) (t s)) (L/h) Σ
(1/h) Σ Qn(s) + h.
#=1
Then, by following the steps in Eq. 47). have
Σ Σ
E[[p(n) Skz D...S
KE[2] nE[N]
Σ Σ (17 (8.) nE(N]
2 2.r (64)
38

---

Now we provide a bound for E[erl- Define (t, E 1(n E Sk.a) and Vr.
(k/2) E Enesh, In Then, have
ex Σ
E
((E
ME TE
Σ
Σ
Fareel 25)
nE|N TE
Σ
Σ
(11
Kn...t 20)
ME[N] TET.
E
E
1(/NN (4) (x/2){2)
NEIN TET
E Σ
1NNn,nn (1) 22/K<()
IET,
ΣE>
Σ
1(Nax s 2/k62 and kn, = k)
MEIN RE[K] TETn
$ 2NK/KC2.
(65)
Then from Eqs.
64
65
we have
Σ
Σ
B[[u(n|/Sa,...t Ok:..) plnlSSk.edd Ok. () ()
TE NE
Σ
Σ C(3r E()Qxtt)
NK < + mT)
(66)
NETINEIN
66). and Theorem Ç = (cNK/min (N, K) + Yr) 12)1/1 for large enough we can obtain
By putting the results of Eqs. (7
(58)
59
6
by setting
NK
(T(T)= = 0
<(Br + TT) Σ Σ (t) +
N Wogg(T)
(BT TT)
(E(T] NE[N]
C(Br + (T) min(N, Main(N,KKT KYT
NK
+ (lgg(T)
<C3 +
(Ar 7T) 2/27 (NK min (N, KJ3)1/1
(logg(T)
1//4
(dNKK (NNKKin(N, KJay 1/4
T3/1
A.8 Proof of Lemma 1
We first define
= -1) and (0)
where Fi-1 is the filtration contains outcomes for time such that S 6-1 and = (Vnnt E Sk.).
From Lemma in Oh and Iyengar 44) by taking expectation over y gives
(r.)( S Fr.)(Ok) + ( 0x) 2
(0x 00.)) T T.,, Wr, Bx.).
39

---

where Wa,t = Enese. In Then with fk,((0%) S fk,e(Ox,e) from Lemma 12 in Oh and Iyengar
44 we have
0 (x.)(n,))) Sm,c(0k)
S (0k.)) T(Ok. 0k.)
R
000 el.ellie.
2
=0n,((km.)) T(Ok, 0n)
)(
1 Pn. In.eliir.. + (gn,)((k.)) I (Ox,))) 0%)
2
S 119k,e (0H,:) 112-1 + 11 0 0xlli 2210x.111 - 0k Vi.
- Kr 11
+ (āx, (l,,(O (Bu,. 0k)
1 _l0k.t 0x 0x11
1 |1 - 0 0
2 max
|
+ 2
nESkit
2
1: 110 0R.11lia..
+ +@xx.(0n..)) (0))(( ((a,, 0k)
2
2 max |1mnlle
+ 2 1116,. - 0xl12e, + H6 1110,1 - Bullive. 2 11 - 0x -0x1122
nESt,
- 2 110 01
+ (On.)( (T.(0,,)))((aa) - Ow)
1 210 0x Vil..e. 11 -= Oxllive. 10 0& 0xllize44
2 max
|| |ornlliy-1 hill =
nESk.t
+ (O,.)) (fx.)) (0x.. - 0k),
(67)
where the third inequality comes from Lemma in Oh and Iyengar 44 and the fourth inequality comes from Lemma 13 in Oh and lyengar [44). We note that, although our estimator lies in O, we can still utilize Lemma Il from Oh and Iyengar [44] by following the same proof steps.
Hence, from the above, we have
||0,,++
B& 1
4 max |a
K ~1102: +110:.00all..
Axl +2(0 (0x.e) (Ox,))) (Or. 0k) -bx.
n
6,6+1
Then using telescoping by summing the above over with at least probability 5, we have
|
11111
Σ
nESk..
max
|| (
6,071
2
Σ 110 0x 0xll l
(āk,s (0k,s) 9k, (0k,)) T0 0k)
==1
max n
||
2
16
|10 - 0k Pxllwa.
k,et1
2
8=1
s=1
K
| 0 1l.1
+
201
log((log K(1)
2
20
< X + 4
max
||
11?
1
+
log( k())
WESt.
6,011
2C1
X 16(d/k) log(1 + (LL/dX)) +
log( (L)og/LL)KK//)))
(68)
K
where the second inequality obtained from Lemma 14 in Oh and Iyengar and the last one obtained from Lemma
Then with 8 1/t², we can conclude that
[10,,c Oxllve, S SC. A log(1 tLK/dX).
40

---

A.9 a-approximation Oracle
In this section, we provide a detailed explanation for a-approxiamtion oracle to reduce the computa- tion. Instead of obtaining the exact solution, the a-approximation oracle, denoted by 09, outputs {S% ]ee[K] satisfying [ [x({)) 2 (aAX(S))xa ΣkE[k] of4((S)) Such an oracle can be constructed using straightforward greedy policy as outlined in prior work [26 [0]. Then for assortments ke for E [2] from Algorithms and 2 using O we can obtain the same
queue length bounds and regret bounds for a-regret in Theorems
and under an a-slackness
assumption, respectively.
We first consider the following traffic slackness assumption with 0
instead of Assumption 3
Assumption 4. For some traffic slackness < < 1, for each t E [T], there exists {Sk,)kEEKK M(N) which satisfies X + c (xl(n) Sk.t 8%) for all n E Sk,t and [K].
A.9.1 a-approximation Oracle for Algorithm |
Here we introduce an algorithm (Algorithm 3) by modifying Algorithm I Jusing an a-approximation oracle. We explain the distinct parts of the algorithm as follows. We define an oracle O", which outputs {5%, (KE,) satisfying
E kE[K] nESp
Σ
(Q (n)Sk, 0n.z) S Σ Σ Qn())t (n|Sg 0n,)). kE[K] nESE,
(
max (SE)
(69)
Algorithm 3 c-aappooximaeed UCB- UCB-Queueing Matching Bandit
Input: fi, C1 0
for t = I...., T do
for k E [K]do do
02tt= t argmingee 9v. (0.,(0 0,,1-1) + 111 0x,t-111
{S + 0 from (69
Offer (5 and observe preference feedback Vn,t E 10,1} for all n E Sk,t. E [K]
For the stability analysis, we provide the following theorem.
Theorem 5. The time average expected queue length of Algorithm 3 is bounded as
Q(T) o - - (min(N,,) K}
1 N2
x26 polylog(T))
which implies that the algorithm achieves stability
min (N
lim Q(T) o +
E
Proof. Here provide only the proof parts which are different from Theorem I I Lyapunov drift as follows.
We analyze the
V(Q(L+ +1) - V(Q(1))
(E(T)
Σ Σ (Qn(1) + An(1) - 2=(1))+² QQ((1)
(E|T) NE
Σ Σ (Q.(t) + A.(()) - aaD;(1) - Q1,
LE|1 RE
Σ Σ (Qx(1) + A.(() (1)+ Σ
((a(t) +.(() -(D) (70)
(EIT
41

---

For the first two terms in Eq. 70,, by following the same procedure of Eqs. Assumption
16 and
17
under
we can obtain
Σ
Σ
B[(Qn(() + A,(1) - -DD(()))
TE[T] NEIN
I Σ
Σ
- -
2NT
15 1E nE[N]
- Σ
Σ
2c + (2, KYT
(71)
EE N
For the last two terms in Eq. 18
by following the steps for Eq. 20 we have
Σ E (Qn(t) + A.))) (n(+))+
Σ Σ (Qn(t) A.( at)
1E[7] [N(N]
[E[]
$ Σ Σ
An(t) +2 2 Σ (aD; D2,()) + min KYT
sE[T] NE[N]
TE[T]ME(N
2 Σ
Σ (aD)(t) - (n(t))Qnnt) + 5 mi,
(72)
(E[T] nE[N]
We also have
Σ Σ (((aD((1) (a(()((())
RE[T] ME[M]
[[(ap(n]SS; .n Onn,e) u(n) S u OR,, Oa. ((Q n E
(E(T] ME[M]
Σ
Σ
[[[au(n|Se On:,)) On 200 + (((E))))))
WE[N]
(73)
Then for the first term of Eq. 73 we have
E
(ap(n|Sk: so Ouz.e) - ulnlsE On ((,(()) n Ehee)
1E12)
DEIN]
E
(apte
-CC ( (A - (nnnSp...dt OR. (f n n E
1E[2]
< Σ [E[T]
E
UCB (n St. (14
kr Ok...t) u(nl Ou.. (1Q n E?.))
mEIN]
<
Σ
E
1 lly (n(t)
Najese
(E(T]
[C[NN]
Cze Σ
Σ [()(..))
(74)
1E[T]
NE[N]
The rest of the proofs can be easily obtained from the proof steps in Theorem 1
Now, we investigate the regret of Algorithm 3 The a-regret regarding policy æ is defined as
0. (T) = Σ Σ
(a w Okr,)) - ((n) Sk., 6x. (1)
KETT MEIN]
The algorithm achieves the following regret bound.
42

---

Theorem 6. The policy π of Algorithm 3
achieves a regret bound of
1/4 <NNK min
7T/44 1)
d
R. (T) Ō min
VKTQum max: k
x2E3
Proof. In this proof, provide only the parts that are different from the proof of Theorem
We first provide the proof for regret bound of Ra. (T) Ö HkVKQmma
We can show that
Ra (T) E
Σ
B[Qn(0(au(mISsr... Oki..) annlSknnee. Ok...)) .)]
TE(TT [N
Σ
Σ
(t)((()( OK.,) p(n1 kn.,,t OR... )){(E))
(E ME[M]
Σ
Σ
E[Q. [[)p(t)(p(( . OK p(n St Sta.ets Ok. ())((())))))
(E[T] RE[N]
E
Σ
B(Q,
Okr.) ) p(nlS )){
+ 6E|2 REIN]
Σ Σ tP((E)))1
(E|T) NE[N]
$ Σ
Σ E(Qn(t)
CBT (mlSk: BALL1)) u(n|SS 8k O(N/T)
TE]TINIIN
Σ
Σ
(n|SR Okn,et) unn|Sp On +
(E[T] NE[N]
Σ
Σ
Σ
Q2(M ( - -.(
(E[T]
kE[K] nESt,t
S 21E
8T Σ
Σ
max
|| Menlly, (l +ONN/2)
REST.
NE(T) KE(K]
S 2E
max (E(
(n(()
Σ Σ
max nesk,
|| v
+NNNT)
TE(T] kE[K]
< 2E
max EE(T]
(n(3)T
KT Σ
Σ
max nesg.
| V + +(N/T))
RE(K]
/ /KTQmax
By following the similar steps above and the proofs for Theorem
2 we can easily obtain the worst-case
regret bound of Ro. (T) = Ō (( [dNN min
KN 1/4 T3/1) which conclude the proof.
Li
A.9.2 a-approximation Oracle for Algorithm
2
We can obtain similar results for Algorithm aa in the case of Algorithm 3 Here introduce an algorithm (Algorithm 4 by modifying Algorithm 2 Jusing an a-approximation oracle. We explain the distinct parts of the algorithm follows. We define an oracle 0 which outputs [S satisfying
Σ KE(K] nESk
Σ QQn(t)TT (n|Sk. (M) 10 he(n) S Σ KE[K] RESK.
Σ
he(M)
max [So 1SEKK EM(AN)
(75)
43

---

Algorithm 4 c-approximated Thompson Sampling -ueiiiingguuui Matching Bandit
Input: X, M, K, C1 > 0
for t 1..... ,T do
for k E [K] do
d f- - (t,r(0x,c-1) (0 (me-1)) 2/10 0x 1l ll
Sample (0 (e
independently from N N(0n,e 33 V
[St,]ke[[] < 0 from 75
Offer (Sk, ]NE[K] and observe preference feedback Vn,t E {0, 13 for all n E Sk,t, E [K]
For the stability analysis, we provide the following theorem. Theorem 7. The time average expected queue length of Algorithm Di bounded as d' N K2
2(T)= min(N, K}
T k polylog(T))
which implies that the algorithm achieves stability
lim Q(T) = o (min(N,K) T
Proof. Here provide only the proof parts which are different from Theorem We analyze the Lyapunov drift as follows with Assumption 4
EDI(Q+++ 1)) V(Q()))
BE(T
Σ
Σ
E (Qn(t) + (.(() - Da(t))+² -
(E(T] [E[M
Σ
Σ
E
(1))(() + Ax(1) -
<E[T] ME[M]
Σ
Σ
(Q)(1) + (t) (t)++ - (Qn(t) + - -
(E[T] NE[M
7 minn N, KYT
Σ Σ ++]
+2 Σ Σ B(( - (7)
(E NE[
*E[T] RE[M]
Then, for bounding 76). we have
Σ Σ
Bl(a (2,
(E[T] nE(N]
Σ
Σ
B[[ap([]|Sk: Ow..) - p(n) ()...)) n E² 2 E
(E[T] NE[N]
Σ
Σ
[[((p(n|Ss; ..t. Ox:.) u(n|Sp Gr (1) +1(()))))))))))))))))))))))))))) + ((E)))
[E[T] ME[N]
(77)
We provide bound for the first term of Eq. (7). We first have
Σ
Σ
B[[ap(n|/S: to Bn: p(n) (n Ot... ((1 n E2 Fl.)
RE
<
Σ
Σ
Bl[oy(n|SS Skn Okn.)) - M.. TTS (n)
tE|T]RE[M
+ TS (n|Se p(n) t On., (1)((()) n E? n B
(78)
44

---

Now we provide bound for the first two terms in Eq. 78).
We define
: { 1 HEIMMIEENN
max I TT In 0u. iEIM]
S 7:l1@nllv, Vn [M] AA E [K] and
=EEM)NEEMMMMII 0pp0 = ={10 JEEM
Σ E
14 " (n|Sk 10% heen))))))))
kE[K] nESE,
(uln|sSk.:000000 no. kE[K] nESt.
Then we define event (0) = (10 E 6.rh). Recall n.k,t = max x T. Then we have
E
Σ
Σ nESE,
TS The (n/S ( ((11)))))) 1 n E n E F,
KE[K]
RES
E
E
Σ
WE(K] nESt
inf Σ
IS (m|Sh 10-00 hEM)))))))))) 1()) n F2 n F F.(0))
10 Ke kE(K] nESE.
Σ Σ
3 (n Sh (0 (e
E
kE(K] mEsa,
inf
Σ
Σ
8 (n) 10 )EEw)) Qn(() n ngg Ex,))F-,1, Ea(0)
(0 [EIM), E kE(K) nESt.
24
Σ Σ
Ed( E: P(E E
C2(7 + 3.)
kEIK] k.!
(79)
We provide lemma below for further analysis.
Lemma 10. For all E [2], we have
P
Σ Σ [E(K]
Σ
Σ
04) Fr 2 1/4VeT
KE JE,K)ESS
Proof. Given F, x 0 follows Gaussian distribution with mean x 0u,e and standard deviation Bel1 &<|==nll,,, Then we have
IP max x; 0. F. F.
=1 P
T Ji 0Rt
x. TT Vi [M]]F-
(E[M]
Z, v. 02 xx7 T
=1 - P
[M]FF-1, E.! vi
B x ll
2 21 - P (Z 1)
45

---

where Z₁ and Z are standard normal random variables. Then we can show that
P
Σ Σ kE[K] R
(n.))))))))))))))
> E
Σ
E
ke[K] n
P
Σ kE[K] RESE
TS ajt (n (n)))))
Σ
Σ
kE[K] nE
P
Σ
Σ
TS ajt
Qn))))))))))>>>>>>>)))))))))))))
E
E
ap(n|Si,,, 0.)0,
kE(K] n
kE[K] neSt.
P
Σ
Σ
14 (n)))
E
E
BL), E.
KE[K] nES
kE(K) nESt
2 P max I, T01))
> In Ox: Vn E Sk Vk E [r]]FF-1,1 Ei
ktt
M
2 1 - LKP Z I 1)M
2 1 LK(1 1/4VeT) M
IV 4Ver*
where the second last inequality is obtained from P(Z < 1) < 1 1/4vem using the anti-
concentration of standard normal distribution, and the last inequality comes from M
log KL.
log(1- (1/1//))
The rest of the proof can be easily obtained by following the proof steps in Theorem
Now, we investigate the regret of Algorithm
The a-regret regarding policy is defined
a. RTT(TT) = Σ Σ
(auln]St Ow;,) - (Sn)SS Ok 0).m.)))
*E(T] [E[N]
The algorithm achieves the following regret bound.
Theorem 8. The policy æ of Algorithm 4 achieves a regret bound of
3/2
ddNK min KJ3
1/4
Ra (T)= = δ min
KTQQmax
22
Proof. Here we provide only the proof parts which are different from Theorem
We first provide the proof for the regret bound of Ō ( VKTQuuxx. We have
6//2
RJT (T) = Σ Σ (0( 0s - p(n|Sh..... Okn.)))
LE|T" NE[N]
Σ (t) Ok.,)) TTS (TS(n1Sp (n.Sk....))
+ TT 1TT5(m)S)) (n|Sp punnsSh Oz. )) n E?)
1E|2 nE[N]
Σ
Σ
+ Tht (nt (nlSS 1l(nS Bs. (L ..t OK..)) T4: (n Sp
LE[T] ME[M]
Σ
Σ
(OQ O2:.) Fi: (n (
TTS
+ 1h TS (nISS uinnSS OR ())(()))))
(E(T] RE[N]
46

---

By following the similar proof steps in Theorem 7 we can obtain
Σ Σ ElQn(t)(ap(() Okn,)) ieg (n) sk..,))
LELT MEIN]
p4 (n|S kn..
pL(1) Sh. s Okn () n E)]
S C2 KC(K]
EE
max (7h 3e) 1l, Qn(()) nES
The rest of the proof can be easily obtained from the proof steps in Theorem by incorporating techniques in the proof of Theorem
A.10
Additional Experiments
MaxWeight-UC3
Q-UCB
UCS-QMB (Algoritim 11
TS-QMB (Algorithm 2)
Orade (MaxWeight)
1.0
Average Quese Length
2.0
Regret
0.0
1.5
0.6
1.0
0.4
0.2
0.5
0.0
0
5000
10000
15000
20000
0.0
5000
10000 15000
20000
Time stop
Time stop
Figure 3: Experimental results with N 4, K 3, L and (right) regret
2, d 2 for (left) average queue length
A.11 Notation Table
Table I: Notation Table.
Time horizon
N
Number of agents (queues)
K
Number of arms (servers)
d
Dimension of model parameters and features
En
Feature vector of agent
Os
Model parameter vector of arm k Length of agent n at time Traffic slackness parameter
Qn(()
(()) 0%)
Service rate of arm & with 0₂ for a job in agent n given assortment S₁
no
Null agent
Xa
Job arrival rate for agent
(= kn.))
A server that agent is assigned at time according to æ (simply kn.t)
An(1)
The number of arrival jobs in agent at time (; Random variable with mean X,
The number of departure job in agent by arm & given S Random variable with mean (( Sk. 0g)
Q(T)
Average queue lengths over horizon time T
RT(T)
Cumulative regret under π over Regularity parameter for MNL Set non-empty agents at time Set of feasible disjoint assortments given set of agents Set agents assigned to arm by policy π Set of agents assigned arm by the oracle =² A server that agent n is assigned by x at time Preference feedback, {0, 1}. for assigned agent time
Ni
M(
Sk.t
Sk.t
k k
Vn.t
47

---

NeurIPS Paper Checklist
1. Claims
Do the main claims made in the abstract and introduction accurately reflect paper's contributions and scope?
Question:
Answer: [Yes]
Justification: Through the abstract and introduction, we explain our setting with providing motivation examples and summarize our contributions.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
we provide several avenues for interesting future work. We also discuss the computational efficiency of our algorithms.
Justification: In the limitations section (Section A.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section their paper.
The paper should point any strong assumptions and how robust the results are violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). ). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best
48

---

judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: We provide assumptions in Section 3 and proof sketches of some of the main theorems in the main text, with complete proofs for theorems in the appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: Section
we provide all the information necessary for conducting the
synthetic experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, No answer this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often good way to accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of model checkpoint, other means that appropriate to the research performed.
also be provided via detailed
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm.
49

---

(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (c.g.. a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d)
We recognize that reproducibility may be tricky in some cases, in which case authors welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification:
There is link to our code in Section
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (kttps://nips.co
for more details.
While we encourage the release of code and data, we understand that this might be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed run reproduce the results. See the NeurlPS code and data submission guidelines (https //tps/ccc/pbllc//uuieeeee
Set.esuuee//CoSuummiii ssi ssionPolicy for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question:
Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: We use synthetic datasets and provide details on how to generate them in Section
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented the core the paper to level of detail that is necessary to appreciate the results and make sense of them.
50

---

The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: our experimental results in Section we include error bars of standard deviation along with expectation values.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emoor bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [No]
Justification:
The conducted experiments do not require significant computing power.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
51

---

Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics http:/pppw..aapppp.cccaaaaaaaaaa
Question:
Answer: [Yes]
Justification:
We have reviewed the NeurIPS Code of Ethies.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: Given that this study primarily focuses on theoretical analysis, we do not foresee any negative social consequences.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out, For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, scraped datasets)?
Question:
Answer: [NA]
Justification:
This paper poses such risks.
Guidelines:
The answer NA means that the paper poses such risks.
52

---

Released models that have high risk for misuse or dual use should be released with necessary safeguards to allow for controlled use of the model. for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (c.g., code, data, models), used in the paper, properly credited and the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification: This paper does not use existing assets.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re- re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
This paper does not release new assets.
Guidelines:
The answer NA means that the paper does release new assets.
Researchers should communicate the details the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
53

---

Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: This paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Question:
Answer: [NA]
Justification: This paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
54


Reviews:
[{"review_id": "2Fo3oLWVdu", "reviewer": "Reviewer_c5Ej", "summary": "This paper studies queueing matching bandits. It proposes a framework that involves multiple queues and multiple servers: in each round, jobs arrive randomly at each queue; the learner assigns jobs to servers; and each server picks and serves its preferred job according to a feature-based linear model. The goal is to stabilize the system, so that the average queue length is finite as the horizon grows to infinity. The paper proposes two algorithms, one based on Upper Confidence Bound and the other based on Thompson sampling. They achieve system stability as well as sublinear regret.", "questions": "- While the paper presents regret bounds, it is unclear to me what they tell us beyond the stability result. Could you provide some intuition behind the definition of cumulative regret, specifically how $Q_n(t)$ is incorporated and what it signifies?\n\n- Could you briefly discuss the technical challenges in the analysis due to having a feature-based service function and only preference feedback, given existing works on bandits for queues and MLN bandits?", "limitations": "Limitations have been discussed.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "- The proposed framework seems interesting and introduces a few novel elements, including a feature-based service function and a preference-based job assignment model. The setting is motivated by important real-world applications, such as ride-hailing platforms.\n\n- The paper proposes two algorithms, and they both achieve the same asymptotic bound on the average queue length as an oracle baseline.\n\n- The paper also provides regret analyses for the algorithms, which are not considered in the closely related works.", "weaknesses": "- Both algorithms require solving an NP-hard combinatorial optimization problem, which may be impractical in large-scale systems.\n\n- The empirical evaluation is limited to synthetic data.\n\n- The presentation can be improved. Since the setting is rather specialized, the first two sections can be challenging for readers who do not know much about queueing systems. For example, in the introduction section, it would be nice if the authors could provide explanations for key terms such as service rates, stability of systems, multi-class queueing, etc. In addition, in Section 5, there are detailed, step-by-step descriptions of the algorithms, but not a discussion on the intuition behind (which probably would not take too long).\n\n- Different jobs from each queue have a common, known representation $x_n$, which may not reflect real-world scenarios.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate your feedback and positive evaluation of our work. Below, we address each comment.\n\n**Require solving an NP-hard optimization:**\n\nNP-hardness is common in almost all assortment (and many other combinatorial) optimization problems. Hence, we do not think that this is particularly a weakness of our method. Rather, our work includes the results under approximation optimization addressing this challenge! As mentioned in lines 295-298, we can overcome the computational challenges using an $\\alpha$-approximation oracle. In short, by employing a greedy policy [26, 10] with the $\\alpha$-approximation oracle to solve the combinatorial problem, and under an approximated stability assumption (Assumption 4), our algorithms (Algorithms 3 and 4) achieve stability and a sublinear $\\alpha$-regret bound. Please refer to Appendix A.8 for more details.\n\n**The empirical evaluation is limited to synthetic data:**\n\nAlmost all bandit literature uses synthetic data because real-time online feedback is required to compute regret in each round. Specifically, true reward values are needed for this evaluation. While offline datasets from the real world can be used, they eventually need to be adapted for the online setting, making them semi-synthetic. This adaptation assumes some true reward function, thus still classifying the experiment as \"synthetic.\"\n\nWe emphasize that the main contribution of this work is to propose a novel problem and propose new algorithms with theoretical analysis. We also point out that many works on bandits for queues [15,46,52,30,32] and on matching bandits [34,45,35,9,52,29] have conducted experiments solely on synthetic datasets, similar to our paper. \n\n**The presentation can be improved. For example..:**\n\nWe sincerely appreciate your suggestions. We will incorporate your comments into our final version.\n\n**Different jobs from each queue have a common representation $x_n$:**\n\nWhile our work focuses on $x_n$ for $n \\in [N]$, we emphasize that *previous queueing bandit literature [15, 52, 23, 46, 32] typically considers unstructured MAB models for service rates even without feature information at all.* To the best of our knowledge, our work is the first to consider a structured model with features for service rates.  An extension to varying features with respect to time would be an interesting direction for future work. A more detailed explanation of the novelty of our setting is provided in lines 98–114 of our paper. \n\n**Intuition behind the definition of cumulative regret, specifically how $Q_n(t)$ is incorporated:**\n\nThe goal of this problem is to stabilize the queues in the system. To achieve this, we consider maximizing the weighted service rates $Q_n(t)\\mu(n|S,\\theta)$, where priority in the assortment scheduling is given to queues with either large queue lengths or high service rates. For instance, if the service rates are similar across queues, the optimization prioritizes scheduling queues with large queue lengths to stabilize the overall system.\n\nThen the oracle strategy of MaxWeight, denoted as $\\\\{S_{k,t}^*\\\\}\\_{k\\in[K]}$, is based on maximizing weighted service rate $\\sum\\_{k} \\sum_{n\\in S_{k,t}^*} Q_n(t) \\mu(n|S_{k,t}^*, \\theta_k)$ under known $\\theta\\_k$, which are known to have optimal throughput keeping the queues in networks stable [51, 38, 37, 49]. By analyzing regret, we can estimate the performance of our algorithms in comparison to the Oracle (MaxWeight) directly. We note that our algorithms (Algorithms 1,2), operated under unknown $\\theta_k$, are based on this MaxWeight strategy by maximizing $\\sum\\_k \\sum\\_n Q\\_n(t) \\tilde{\\mu\\_t}^{UCB, TS}(n|S\\_k, \\hat{\\theta}\\_{k,t}) $ where $\\tilde{\\mu\\_t}^{UCB, TS}$ is an estimator for the service rate. One natural way to compare our algorithm against the oracle is to measure the difference between $\\sum_{k\\in[K]}\\sum_{n\\in S_{k,t}^*}Q_n(t)\\mu(n|S_{k,t}^*,\\theta_k)$ and $\\sum_{k\\in[K]}\\sum_{n\\in S_k}Q_n(t)\\mu(n|S_{k,t},\\theta_k)$, as in our regret definition, where $S_{k,t}$ is the output of our algorithms. We point out that the closely related work on queueing bandits [46, 15, 52] only conducted stability analysis, without considering regret analysis.\n\n**Technical challenges in the analysis:**\n\nWe emphasize that this is the first work to connect the two distinct problems of queues and MNL bandits. We note that previous queueing bandits did not deal with preference feedback, and previous MNL bandits did not deal with stability analysis under a dynamic environment.  Therefore, we needed to design a framework that integrates the two different problems.\n\nIn the stability analysis, it is crucial how to relate a term regarding queue lengths and a term regarding learning MNL model. For this purpose, we examine the Lyapunov function drift, and derive a bound regarding the summation of queue lengths and learning part in the MNL bandit strategy, as shown in Eqs.(2), (3). By further analyzing the learning parts as in Eqs. (4),(5), and (6), and by rearranging the results, we can finally obtain a bound for average queue lengths.\n\nFor regret analysis, due to our regret definition, we need to consider not only the difference between the service rate of our algorithm and oracle, but also the queue length of the system at each time, which is the main difference from previous MNL bandits. We first derive a regret bound of $\\widetilde{\\mathcal{O}}(\\sqrt{T}Q_{\\max})$ using $Q_{\\max}$ with the techniques from bandits. Next, to establish the worst-case bound of $\\tilde{O}(T^{3/4})$, we integrate the regret analysis with the queue length bound results of our stability analysis, by carefully analyzing the event of bounded elliptical potentials with the optimally tuned parameter $\\zeta$ as in Eqs. (9), (10). We believe our framework for regret analysis could be useful for this line of future research.", "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": "", "extra_scores": {}}, {"review_id": "nbuSoIcFnC", "reviewer": "Reviewer_117Z", "summary": "The work introduces a new bandits framework that handles the problem of matching queuing jobs (agents) with preferential servers (arms). The work extends beyond the match making problem with the objective of stabilizing the queue by learning the preferential nature of agents to arms. The authors propose two new algorithms based on UCB and Thompson sampling algorithms and analyze theoretical guarantees with respect to stabilizing the length of the queues. They also extend their study by analyzing the regret bound for the proposed algorithms.", "questions": "* How does this work in terms of theory compares with some of the existing algorithm in this problem space. A discussion on regret comparison can help draw conclusion on the performance of the algorithms in this work.\n\n* The experimental section compares the authors’ proposed algorithm QCB-QMB and TS-QMB with others algorithms that are applicable to this problem. The experiments compare them in one settings when N=KL. Also, experimental setting when N<KL can help the behavior of the proposed algorithms in different operating regimes. \n\n* The regret analysis in Theorems 2 and 4 provides bounds in terms of the maximum queue length $Q_{max}$. But, the relationship between $Q_{max}$ and the system parameters N, K, \\& \\epsilon is not clearly established. Providing insights on Q_{max} in terms of these parameters would give more insight into the regret performance.\n\n* The experimental results in Section 6 compare the proposed algorithms with previously suggested methods for queueing bandits or matching bandits. However, the choice of baselines seems limited. Providing comparisons with a wider range of relevant algorithms, such as those handling contextual bandits with queueing constraints, would strengthen the empirical evaluation.\n\n* The paper establishes sublinear regret bounds, but it does not provide any lower bounds on the regret. Deriving problem-specific lower bounds would give a better understanding of the optimality of the proposed algorithms and highlight any potential gaps between the upper and lower bounds.", "limitations": "* The proposed framework is evolutionary extension to the existing framework of bandits for queues & match making problem. \n\n* The experimental section only studies setting in certain regimes when N=KL and lacks detailed empirical study and a proper baseline algorithms to be compared.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "* The authors develops a new bandits formulation for addressing queueing matching fixing some of the nuances of the earlier developed framework for the same. \n\n* The work captures the important aspect of this problem with a structured model using features for estimating service rates in comparison with bandits for queues or earlier works. Also, the consideration of availability of assignment of an agent available only in an non-empty queue is an welcome addition.\n\n* The formulation is reasonable and interesting mathematically and the work studies the stability of the queueing matching problem and analyses the theoretical guarantees with regards to regret as well.\n\n* The authors developed two new algorithms for the framework and showed theoretical bounds for the same highlighting the stability comparing it with the existing work.", "weaknesses": "* The developed bandits framework is an incremental extension of bandits for queues & match making problem discussed in the work. Though the work highlights some important consideration, the previous algorithm seem to work for the proposed algorithm. \n\n* In the experiments, the authors have only studied the setting when N=KL and One does wonder why the other regime N<KL is not included.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate your feedback and positive evaluation of our work. Below, we address each of your comments.\n\n**The previous algorithm seems to work for the proposed algorithm:**\n\nOur problem includes novel factors, which are inspired by the real-world such as online job markets or ride-hailing platforms. *Due to the unique aspects of our problem, the existing algorithms (either in queuing bandits or in matching bandits) do not provide a tight regret guarantee in our problem*. Below, we outline the novelty of our problem compared to previous works.\n \nIn queueing bandits, to our best knowledge, none of the previous works has focused on a structured model with features for service rates. Furthermore, earlier studies either did not allow the assignment of different types of jobs to a server simultaneously [32, 52], or, if they did [46,15], the service rates for each job-server assignment remained constant regardless of the entire assignment. In contrast, we adopt a structured model incorporating features for unknown asymmetric service rates. We also enable the assignment of multiple agents to the same server, where the server stochastically selects at most one of the assigned agents based on its undisclosed (relative) preference. More details can be found in lines 98–114.\n\nRegarding matching bandits, the primary goal of the previous work [34,45,35,9,54,29] has been to minimize regret by achieving an optimal stable matching through learning agents' side preferences via stochastic reward feedback under static settings and deterministic arm behavior with known preferences. In contrast, we consider dynamic environments with job arrivals for agents. Additionally, we propose that arm behavior is stochastic with unknown preferences, requiring the learning of arms' preferences. Our main objective is to stabilize queue lengths rather than finding a stable matching. Hence, the existing matching bandit methods cannot solve our problem. More details are provided in lines 120–129.\n\nAs mentioned in the introduction, it is also worth mentioning online matching problems [27,39,40,18,16,28], where the sole focus is on optimizing matching rather than learning underlying models from bandit feedback. In contrast, our study concentrates on bandits related to learning latent utilities by managing the exploration&exploitation tradeoff while establishing the stability of the queueing systems. Importantly online matching problems do not address the stability of systems.  \n\n**In the experiments, $N<KL$ is not included:**\n\nOur model is a preference-based structured model, allowing that multi-agent can be assigned to an arm, which aligns with real-world applications such as the online job market, where multiple applicants (agents) are applying to employers (arms). Therefore, with $N$ agents and $K$ arms, we used an instance of $N>K$ with $N=4$, $K=2$, and $L=2$, in our experiments. \nIncorporating your feedback, we have included additional experiments for $N<KL$ in the attached pdf, where our algorithm still performs superior to the other algorithms (except the oracle that knows the true preference). We will include these additional experimental results in the final.\n\n**A discussion on regret comparison with other work:**\n\nFirst, we emphasize that previous studies on multi-class multi-server systems closely related to our work, [46,15,52], have not considered regret analysis, whereas our work addresses both stability and regret analysis. Additionally, the algorithms proposed in prior studies do not apply to our setting, as we use a structured model with features and allow multiple queues to be assigned to a server with preference feedback. Therefore, a direct theoretical comparison is not available. However, we provide an existing result for regret to clarify our contribution.\n\nThere exists a prior work [23] that studied regret analysis regarding $Q_n(t)\\mu(n|S_k,\\theta_k)$, as in our regret definition, under single-server.  In [23], a regret bound is provided as $\\tilde{O}(\\max\\\\{\\sqrt{T}Q_{\\max},T^{3/4}\\\\})$ (with $\\delta=1/2$ for a stationary setting in Lemma 5.7). In the previous work, the worst-case bound is not guaranteed from the maximum in regret. We emphasize that our algorithms achieve a sublinear regret bound of $\\tilde{O}(\\min\\\\{\\sqrt{T}Q_{\\max},T^{3/4}\\\\})$ (Theorems 2,4), even in the worst-case from the minimum in regret. We also note that our algorithms achieve stability results (Theorems 1,3) (specifically, $\\mathcal{Q}(T)=O(N/\\epsilon)$ when $T$ is sufficiently large), which match that for the Oracle (Proposition 1).\n\n **Providing insights on $Q_{max}$ in regret in terms of model parameters:**\n\n In our analysis of the regret bound of $\\min\\\\{\\sqrt{T}Q_{\\max},T^{3/4}\\\\}$ (Theorems 2,4), we allow for $Q_{\\max}$ to be instance-dependent. However, regardless of how $Q_{\\max}$ is bounded, we can still obtain the worst-case sublinear regret bound of $T^{3/4}$ by using our stability results in Theorem 1 or 3 (More details are shown in the proof sketch in Theorem 2). While we can obtain the worst-case bound without a bound for $Q_{\\max}$, it would be an interesting future work to analyze $Q_{\\max}$ directly.\n\n **The choice of baselines seems limited:**\n\nTo our knowledge, we have considered appropriate baseline algorithms, such as [32, 15, 52], for multi-queue multi-server bandits with asymmetric service rates, which are the most closely related work. We also include the algorithm from [34] as a baseline, which is proposed for matching bandits. We would be more than happy to include additional baselines in our final if there are any others we need to consider.\n\n**It does not provide lower bounds on the regret:**\n\n It remains an open problem to establish regret lower bounds, as mentioned in Appendix A.1. However, we highlight that the regret analysis has not been studied in closely related studies [46,15,52], and our sublinear regret could be the first step towards no regret algorithm for queuing matching bandits.", "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": "", "extra_scores": {}}, {"review_id": "356GY9BEJ8", "reviewer": "Reviewer_9oLk", "summary": "This study examines multi-class multi-server asymmetric queueing systems, where jobs arrive randomly, and unknown job-server service rates are modeled by a feature-based Multinomial Logit (MNL) function. The proposed UCB and Thompson Sampling algorithms aim to stabilize the queues while learning service rates, achieving system stability with an average queue length bound and sublinear regret, and demonstrating their performance through experimental results.", "questions": "How about the performance and calculation efficiency when N, K, L, and d become larger?", "limitations": "na", "rating": 7, "confidence": 1, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The authors propose a novel and practical framework for queueing matching bandits, introducing feature-based multinomial logit functions for service rates and preference feedback, which are investigated for the first time. Their UCB and Thompson Sampling algorithms achieve stability with average queue length bounds and sublinear regret, outperforming previously suggested methods, as demonstrated by their experimental results.", "weaknesses": "The quality of the figures can be improved.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate your feedback and positive evaluation of our work. Below, we address each of your comments.\n\n\n**The quality of the figures can be improved:**\n\nWe will make sure to improve the quality of the figures in our final version. \n\n**How about the performance and calculation efficiency when N, K, L, and d become larger?**\n\nWe provided stability and regret analysis in Theorems 1,2,3, and 4. Specifically, our algorithms (Algorithms 1 and 2) achieve stability with $\\mathcal{Q}(T)=\\mathcal{O}(N/\\epsilon)$ for large $T$. They also achieves regret bound of $\\mathcal{R}(T)=\\mathcal{O}(\\min\\\\{(d/\\kappa)\\sqrt{KT}Q_{\\max},N(dK/\\epsilon^3\\kappa)^{1/4}T^{3/4}\\\\})$ and $\\mathcal{R}(T)=\\mathcal{O}(\\min\\\\{(d^{3/2}/\\kappa)\\sqrt{KT}Q_{\\max},N(d^2K/\\epsilon^3\\kappa)^{1/4}T^{3/4}\\\\})$, respectively. \n\nRegarding computational cost, the exact combinatorial optimization is NP-hard (so is true for almost all other combinatorial optimization problems). However, as mentioned in lines 295-298, we can overcome these computational issues using an $\\alpha$-approximation oracle, as described in Appendix A.8. In summary, by employing a straightforward greedy policy [26, 10] with the $\\alpha$-approximation oracle to solve the combinatorial problem, under an approximated stability assumption (Assumption 4), our algorithms (Algorithms 3 and 4) achieve both stability and a sublinear $\\alpha$-regret bound. Please refer to Appendix A.8 for more details.", "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": "", "extra_scores": {}}, {"review_id": "qf05YoxCpt", "reviewer": "Reviewer_PAuc", "summary": "This paper proposes an algorithm that learn optimal allocation in a multi-arm bandit problem involving queues.\nThe algorithm  ensures the system stability while having a sub-linear regret.", "questions": "1. The authors explain that the notion of stability that they use is the existence of Cezaro limit of the queue sizes. This is weaker than what they call uniform stability (expected queue lengths are bounded).\nThen they introduce $ Q_{max}$ the expectation of the maximum queue length over $T$ steps. $Q_{max}$  appears in the regret bound as a constant independent of $T$. This seems to imply that the stability is uniform. But this is not the case here. Can you explain where is the catch?", "limitations": "The authors claim that their model fill up a gap between previous models and real-applications. This claimed is not backed up by any concrete example. Furthermore, the assumptions that they add about Bernoulli arrivals, unit size jobs, information patterns known/unknown  by the learner, the technical assumptions  (esp. assumption 3 that is strictly stronger than a stability condition because it involves the fixed allocation $\\mu$), and the need of well-defined posterior distributions for their algorithm does not go in the direction of practical applications. \n\n\n\nThe stability assumption (assumption 3) uses the predefined allocation $\\mu$ while in general it should not depend on the decisions of the scheduler.", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The algorithm leverages on both max-weight and UCB (or TS) to provide stability and no-regret in a multi-arm bandit problem involving queueing.", "weaknesses": "- There are notation confusions.\n\n - The use of $\\mu_{n,k} (S| \\theta)$, $\\mu_t(n | S, \\theta)$, $\\mu (n | S, \\theta)$, $\\mu (n|S)$  make reading the technical parts very hard to understand and confusing\n\n-V is the classical Lyapounov function and also used for the norm of $x$.\nThe norm $|| . ||_{V_{k,y}^{-1}} $ is used for both $\\theta$ ( a matrix) and $x_n$ (a vector) while only defined using  $x$. This is not clear to me.\n\n\n- Some constants are not well explained, for example, $\\lambda$ is used in line 225 and 227 without any explanation, then disappears in all further results.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate your time to review our paper and comments. Below, we address each comment.\n\n**There are notation confusions:**\n\nWe appreciate your helpful comments in clarifying our paper. We will include a notation table in our final (Please refer to Table 1 in the attached PDF). As mentioned in line 238, we use $\\mu(n|S_k)$ instead of $\\mu(n|S_k,\\theta_k)$ for simplicity when there is no confusion. Additionally, we have identified some notation errors: $\\mu_t(n|S_k,\\theta_k)$, $\\mu_{n,k}(S_k|\\theta_k)$ should each be replaced by $\\mu(n|S_k,\\theta_k)$. We will correct these in the final version. To reduce notation confusion, we will also use $\\mathcal{V}$ for the Lyapunov function in the final.\n\n**$||\\cdot||\\_{V\\_{k,t}^{-1}}$ is used for $\\theta$ without definition for a matrix:**\n\nParameter $\\theta$ for the model of service rate is a d-dimensional vector rather than a matrix. Therefore, $||\\cdot||\\_{V\\_{k,t}^{-1}}$ can be defined for $\\theta$.\n\n**$\\lambda$ disappears in results:**\n\nAs mentioned in lines 228 and 282, we set the regularizer factor $\\lambda=1$, which does not affect the order of bounds for stability or regret. For instance, $\\beta_t$ includes $\\lambda$ as $\\sqrt{\\lambda+\\frac{d}{\\kappa}\\log(1+tLK/(d\\lambda))}$. The stability bound contains $O(\\beta\\_T^4)$ as in Eq.(6), which can be bounded by $O((d^2/\\kappa^2)\\text{polylog}(T))$ ignoring constant $\\lambda$ for large enough $T$.\n\n**$Q_{max}$ appears in regret bound as a constant independent of $T$:**\n\nOur regret bounds of $\\tilde{O}(\\min\\\\{\\sqrt{T}Q_{\\max},T^{3/4}\\\\})$ consist of the two terms. We argue that the bound of $T^{3/4}$ must hold for the worst case and this does not have to imply that $Q_{\\max}$ is a constant. The two terms in the regret bound are obtained from separate regret analyses as shown in proof sketch of Theorem 2. Indeed, to obtain the worst-case bound of $T^{3/4}$, we utilize our stability results for average queue lengths in Theorems 1,3, as briefly shown in Eq.(10) and following lines 271-273.\n\n**Evidence that the model fills up a gap between previous models and real-applications:**\n\nAs mentioned in lines 40–49, in real-world, the service rate may be influenced by the relative preferences among multiple assigned jobs, as in ride-hailing platforms and online job markets. For example, in ride-hailing platforms, a driver may receive multiple rider requests and select one based on their preferences. Additionally, a job in an empty queue cannot be assigned to a server for feedback, reflecting real-world where a non-existent rider cannot be recommended to a driver. Lastly, real-world scenarios often involve observable feature information, such as details about locations of riders. All of these practical considerations have not been addressed in the previous literature while addressed in our model.\n\n**Concerns about assumptions:**\n\n**Bernoulli arrivals with unit size jobs:** The Bernoulli arrival with unit job model has been considered in queueing bandit [15, 48, 32], and our setting follows this. However, we can easily extend binary random arrival $A_n(t)\\in\\\\{0,1\\\\}$ to the case where random variable $A_n(t)$ lies in $[0,M]$ for some $M>0$ with mean $\\lambda_n\\in[0,M]$. This extension allows for multi-unit jobs rather than just single-unit jobs.  For instance, under the extended setting, Eq. (2) becomes $\\sum_t\\sum_n \\mathbb{E}[(Q_n(t)+A_n(t)-D_n^*(t))^2-Q_n(t)^2] \\le -\\sum_t\\sum_n 2\\epsilon \\mathbb{E}[Q_n(t)]+(M^2+1)NT.$ This leads to achieve stability with $\\mathcal{Q}(T)=O((M^2+1)N/\\epsilon)$.\n\n**Information patterns:**  We assume that features for jobs are known, but the service rate for each server is unknown. The unknown service rates have been considered in almost all queueing matching bandits [32,52,46,15,23,48]. Importantly, our setting is more general than the existing works because we use a feature-based model for the service rate while the previous work typically considers a non-contextual MAB setting. Additionally, the known feature information is the most standard setting in many contextual bandits [1,2,3,5,33,43,44].\n\n**Assumption 3 is stronger than a stability condition and depends on the scheduler decision:** We emphasize that Assumption 3 is *not strictly stronger* than a stability condition (Definition 1). This is because, through Assumption 3, we can only guarantee the existence of assortments $S\\_k$'s such that, for some $0<\\epsilon<1$, $\\lambda_n+\\epsilon \\le \\mu(n|S_k,\\theta_k)$ for $n\\in S_k$ and $k\\in[K]$.  For instance, in the worst case, there is a unique allocation assortment $S_k$ satisfying $\\lambda_n+\\epsilon \\le \\mu(n|S\\_k,\\theta\\_k)$ for all $n\\in S_k$ and $k\\in[K]$. In our setting of unknown $\\theta_k$, our algorithm does not know such $S\\_k$'s which satisfies the Assumption 3. Therefore, our algorithms require finding such allocation assortment $S\\_k$ for stabilizing queues by learning $\\theta_k$ over horizon time $T$ from the feedback of the algorithm's decision $S\\_{k,t}$ at each time $t$. Also, note that the existence of assortments $S_k$ in Assumption 3 is *regardless of* our scheduler $S\\_{k,t}$.  We highlight that the nature of it is not different from the stability assumptions in [15,46,32,52], in which they assume the existence of allocations such that arrival rates are less than service rates with $\\epsilon$.\n\n**Need of well-defined posterior distributions for their algorithm:** We respectfully disagree with your comment. In this comment, you may be referring to our Thompson sampling algorithm (Algorithm 2). We also clarify that we do not impose any specific distribution on the true parameter $\\theta_k$. Our analysis in this work is in the frequentist regret where $\\theta_k$'s are fixed, which holds for the worst-case scenario under Assumptions 1–3. *Hence, there are no prior or posterior assumptions.* Our TS-based algorithm uses a Gaussian distribution sampling, but this does not imply that the true parameter must follow a particular distribution.", "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": "", "extra_scores": {}}]

Author rebuttal:
Thank you for taking the time to review our paper. We are encouraged by your feedback, noting that our problem is both novel and interesting, inspired by real-world challenges. We have attached a PDF that includes additional experimental results and a notation table, addressing the reviewers' comments. Below, we provide detailed responses to each of the reviewers' comments.

Meta-review: The paper proposes a queueing matching bandits framework using UCB and Thompson sampling algorithms to stabilize multi-class, multi-server systems and achieve sublinear regret. Reviewers acknowledged the framework's novelty, emphasizing its structured feature-based model and practical applications. However, concerns included computational complexity, presentation clarity, limited empirical data, and reliance on synthetic experiments. Despite these issues, most reviewers supported acceptance, highlighting the theoretical contribution and potential impact, while one reviewer recommended rejection due to confusion over notation and assumptions. The authors addressed these concerns, suggesting improvements and clarifying their model’s practical relevance.  Overall, the paper is sufficiently novel, makes interesting contributions and is acceptable to NeurIPS.
Decision: Accept (poster)