Queue Length Regret Bounds for Contextual Queueing Bandits
Authors: Seoungbin Bae
Garyeong Kang
Dabeen Lee
Venue: ICLR 2026 Poster (2026)
Keywords: Queueing bandits
contextual bandits
logistic bandits
Primary area: reinforcement learning

Abstract: We introduce contextual queueing bandits, a new context-aware framework for scheduling while simultaneously learning unknown service rates. Individual jobs carry heterogeneous contextual features, based on which the agent chooses a job and matches it with a server to maximize the departure rate. The service/departure rate is governed by a logistic model of the contextual feature with an unknown server-specific parameter. To evaluate the performance of a policy, we consider queue length regret, defined as the difference in queue length between the policy and the optimal policy. The main challenge in the analysis is that the lists of remaining job features in the queue may differ under our policy versus the optimal policy for a given time step, since they may process jobs in different orders. To address this, we propose the idea of policy-switching queues equipped with a sophisticated coupling argument. This leads to a novel queue length regret decomposition framework, allowing us to understand the short-term effect of choosing a suboptimal job-server pair and its long-term effect on queue state differences. We show that our algorithm, CQB-$\varepsilon$, achieves a regret upper bound of $\widetilde{\mathcal{O}}(T^{-1/4})$. We also consider the setting of adversarially chosen contexts, for which our second algorithm, CQB-Opt, achieves a regret upper bound of $\mathcal{O}(\log^2 T)$. Lastly, we provide experimental results that validate our theoretical findings.

Published as a conference paper at ICLR 2026
QUEUE LENGTH REGRET BOUNDS FOR CONTEXTUAL QUEUEING BANDITS
Scoungbin Bac', Garyeong Kang', Dabeen Lee
1 DDppartment of Industrial & Systems Engineering, KAIST *Department of Mathematical Sciences, Scoul National University sbbae31 @kat st.ac..ck river Beckaist.ac.kie dabeen @snu aesnu.ac... ac.kr
ABSTRACT
We introduce contextual queueing bandits, new context-aware framework for scheduling while simultancously learning unknown service rates. Individual jobs carry heterogeneous contextual features, based on which the agent chooses a job and matches it with server to maximize the departure rate. The service/departure rate is governed by a logistic model of the contextual feature with an unknown server-specific parameter. To evaluate the performance of policy, we consider queue length regret, defined as the difference in queue length between the pol- icy and the optimal policy. The main challenge in the analysis is that the lists of remaining job features in the queue may differ under our policy versus the opti- mal policy for given time step, since they may process jobs in different orders. To address this, we propose the idea of policy-switching queues equipped with a sophisticated coupling argument. This leads to novel queue length regret decom- position framework, allowing us to understand the short-term effect of choosing suboptimal job-server pair and its long-term effect on queue state differences. We show that our algorithm, CQB-e, achieves regret upper bound O(T-1/4). We also consider the setting of adversarially chosen contexts, for which our sec- ond algorithm, CQB-Op achieves a regret upper bound of Ologg T). Lastly, we provide experimental results that validate our theoretical findings.
INTRODUCTION
Queueing systems play an important role in modern service platforms such as cloud job sched- ulers, personalized recommendation systems, ride-hailing, delivery marketplaces, call centers, and large-scale LLM inference (Neely, 2010; Aksin et al., 2007; Yang al., 2024; Fu al., 2024; Mitzenmacher Shahout, 2025; Lee et al., 2024a). A central difficulty in these platforms is the necessity to account for individual jobs with diverse features and contexts, such job sizes, power usage, user profiles, and compatible devices, when assigning them to processors. Providing such context-aware service is crucial to improving overall service quality. However, once heterogeneous contextual features are allowed for different assuming a priori knowledge of service (departure) rates for all job-server pairs is unrealistie. This motivates real-time scheduling algorithms that si- multaneously learn unknown context-dependent service rates from observed queue dynamics while making job-server assignments real time.
There has been a substantial body of work on scheduling in uncertain environments, where the scheduler must simultaneously learn unknown system parameters while making job ser-eerver alloca- tion decisions. Among these efforts, approaches that model the problem of learning unknown service rates using multi-armed bandit formulations have received significant attention (Krishnasamy al., 2016; Gaitonde & Tardos, 2020; Choudhury et al., 2021; Stahlbuhk et al., 2021; Sentenac et al., 2021; Hsu et al., 2022; Freund et al., 2022; Yang et al., 2023; Huang et al., 2024; Krishnakumar & Sinha, 2025). In particular, frameworks that minimize the notion of queue length regret (Krish- nasamy et al., 2016; Stahlbuhk et al., 2021; Krishnakumar & Sinha, 2025), defined as the difference
Also affiliated with Research Institute of Mathematics, Seoul National University, Korea Institute for Ad- vanced Study, and the Interdisciplinary Program in Artificial Intelligence, Scoul National University.

---

Published as a conference paper at ICLR 2026
c++1
I+2
Queue x²
R2
X2
X4
X2
Server
Fal
Supcsss
Queue
%
%
12 %
Figure 1: Illustration of the queueing processes under our policy and the optimal policy x² in contextual queueing bandits with three servers. Due to a suboptimal choice by our policy a in round 1+ 1, the queue states diverge in round + 2, where we call this queue state misalignment.
in queue length under a given policy versus the optimal policy, provide useful lens for developing and analyzing algorithms that ensure stability even when service rates are unknown. However, these existing works on queue length regret do not take into account individual job contexts.
Recently, Kim & Oh (2024) consider context-aware approach in which each queue is assigned a fixed contextual vector, and all jobs within the same queue share the same context. Then a job in queue is allocated to server whose service rate is determined by the contextual vector and the unknown parameter of the server. However, since it is required for their model to fix the number of distinct queues, it does not fully support heterogeneous contexts for different jobs. Another issue is that they define regret to maximize the cumulative weight sum for the Max Weight algorithm, which is far from capturing queue length regret.
Motivated by these limitations, we propose contextual queueing bandits, a new context-aware frame- work to learn unknown service rates where jobs arrive with heterogeneous contextual features, the agent selects a job-server pair for assignment in each time step, and the service/departure rate is de- termined by logistic model with the contextual feature and the unknown server-specific parameter. We present two algorithms, CQB-E and CQB-Opt, and evaluate the policies via the notion of queue length regret. Unlike previous work that assumes a fixed context for each queue, allowing heteroge- neous contexts brings about a specific challenge. That is, the context features of the remaining jobs in a queue under our policy may differ from those under the optimal policy, since the two distinct policies may take different job processing orders. We call this phenomenon queue state misalign- ment, illustrated in Figure 1. Addressing this issue is the main challenge in analyzing algorithms designed to minimize queue length regret. Our contributions are summarized below in detail.
We introduce contextual queueing bandits, a novel context-aware framework for schedul- ing and queueing system control while simultaneously learning unknown service rates. Jobs carry heterogeneous context information, based on which the agent selects a job and assigns it to a server so that the departure rate maximized. The departure rate given by a feature-based logistic model, whose parameter is unknown to the agent. To evaluate policies, we take queue length regret, which is defined as the difference in queue length under given policy versus the optimal policy. This is the first work to establish provable decay rate for queue length regret under contextual queueing bandit settings.
The main challenge in analyzing queue length regret that, for given time step, the list of remaining job features in the queue under our policy may differ from the remaining feature list under the optimal policy. This happens because our policy may process jobs in a different order from the optimal policy. We refer to this as queue state misalignment, which makes difficult to compare the queue states under two distinct policies for a given time step. To address this, we take policy-switching queues which follow our policy up to certain round and then switch to the optimal policy thereafter. This lets us decompose queue length regret into telescoping sum, each of whose terms is the difference in queue length between two policy-switching queues whose moments of switching differ by exactly one round. Under this alignment technique, equipped with a sophisticated coupling argument, we can provide an upper bound on each term given by the product of (i) the difference in departure rates for the round when two consecutive policy-switching queues apply different policies and (ii) the long-term impact of queue state differences at the end of time horizon.
We show that our algorithm, CQB-s, achieves a queue length regret bound of O(T-1/4), which vanishes for large T. To achieve the decaying bound, our algorithm proceeds with two phases; it goes through a pure-exploration phase first and switches to e-greedy
2

---

Published as a conference paper at ICLR 2026
policy, We argue that the gap between service rates for the job-server pairs under the algorithm and the optimal policy is nonincreasing. Furthermore, we show that the impact of policy switching in one round on queue state differences at the end of time horizon is nondecreasing. Combining these two via Chebyshev's sum inequality, we provide the desired queue length regret upper bound.
We also consider the setting where job contexts are chosen by the adversary. For the ad- versarial setting, our second algorithm, CQB-Opt, achieves queue length regret upper bound of Olog" T). The main difficulty for the analysis is that it is hard to uniformly con- trol the uncertainty lerm, which is defined to capture the magnitude of the selected feature vector relative to the previously chosen ones and its directional deviation from them. In contrast, for the stochastic setting, we observe a smooth transition from a phase where the uncertainty term large another phase where it is small, based on which we develop the two phase structure of CQB-s. However, for the adversarial setting, the uncertainty term can still be large even towards the end of time horizon. To get around this issue, we instead count the total number of such rounds and analyze the underlying randomness in their occurrence. This lets us apply the coupling-base queue length regret decomposition technique, subject to incurring poly-logarithmic term in the regret upper bound.
We again emphasize that our analysis and proof techniques are novel, developed to characterize queue length regret under queue state misalignment. In particular, our queue length regret decom- position approach lets us understand the short-term effect of choosing a suboptimal job-server pair and long-term effect on queue state differences, which is of independent interest.
2 RELATED WORK
Queueing Bandits. Krishnasamy et al. (2016) introduce the framework of queueing bandits for modeling queueing system control problems where learning unknown service rates is required while scheduling jobs. By leveraging connections with multi-armed bandits and, at the same time, discov- ering queueing-specifte dynamics, they establish a decaying upper bound on queue length regret. This work has motivated significant body of follow-up work designing algorithms for schedul- ing while learning unknown service rates based on bandit learning, such as learning with dispatching and Max Weight-based algorithms (Krishnasamy et al., 2016; Gaitonde & Tardos, 2020; Choudhury et al., 2021; Stahlbuhk et al., 2021; Sentenac et al., 2021; Hsu et al., 2022; Freund et al., 2022; Yang al., 2023; Huang et al.. 2024: Krishnakumar & Sinha, 2025). However, these do not consider het- erogeneous contexts for individual jobs, limiting their applications in modern personalized service platforms. Recently, Kim & Oh (2024) consider context-aware qucueing bandit problem based on the multinomial logit model. However, their setting still limits the number of distinct contextual feature vectors, and they study proxy notion of regret, missing queue length regret analysis.
Logistic Bandits. We assume that the service rate of server allocated to job follows logistic model of the job's contextual feature vector and the server-specific unknown parameter. Hence, the problem of learning unknown server parameters relates to logistic bandits. Starting from the seminal work of Filippi et al. (2010), there has been flurry of activities to characterize and improve regret bounds for logistic bandits (Faury et al., 2020; Li et al., 2017: Jun et al., 2021; Abeille et al., 2021; Lee et al., 2024b; Bae & Lee, 2025). However, there are fundamental differences between logistic bandits and our contextual queueing bandits framework, which makes it difficult to directly apply the regret analyses for logistic bandits to our setting. First, logistic bandits consider exogenous action sets shared by all policies, but action sets in our setting are endogenous and policy-dependent. To be more precise, actions taken in previous rounds affect the queue state in the current and future rounds. This leads to the phenomenon of queue state misalignment under our policy versus the optimal policy. Moreover, we investigate queue length regret instead of cumulative reward regret, reflecting the objective tailored to achieve queueing system control. These differences in the dynamics of action sets and the regret definition require new techniques.
3

---

Published as a conference paper at ICLR 2026
3 PROBLEM SETTING
We consider a discrete-time contextual queueing system with a single queue and K servers, given as follows. In each round t [T', the agent observes a queue state X; E X C IR given by the set of contextual feature vectors of remaining jobs, chooses a job (with feature) 2ς E 24, and matches it with a server k2 E [K]. Let Q(t) be the queue length at the beginning of round t, i.e. Q(t) [x]-- Let A(t) E {0. 1} indicate the random arrival of job at time t with mean X, and let D(t) E {0.1] denote the random departure at time with mean Ju(ar} (T,) where juz) = (1+e-))
the logistic
function and 8% E IRd is the unknown parameter of server kt- When A(t) = 1, we denote by 2x() the feature of the job arriving at time Then
Xe+1= = X, fa, ((t) = 13 U f2 A(t) = 1}, (Q(1))(Q()) + A(1) - D(t))*
where [g]+ max (0, q)+ For technical convenience, we assume that dummy job xo E Rd is chosen when the queue is empty, while ignoring the feedback of the queueing process to avoid unfair advantage. We denote by E(t) E {0, 1} the random variable that indicates whether
random exploration in round / 1+1 used in Algorithm 1. We define the arrival tuple and the departure tuple as
A(t) = (A(t), F()) (tt) := (Dt (Iz, k2)). where (0)) is a masked feature defined as 2(() =
if A(t) = 0 where ã E d is a fixed symbol for the sign of no arrival, and ((() = (1)) if A(t) =1.
Then define the filtration F. == (X,, A(1) (1), E(1), ..... A(t - 1), D(t 1)) for t [7]. For notational convenience, when we write A(t) = 0 (or ((t) = 1), it means the observation
includes A(I) = 0 (or A(t) 1) and (7(1) Similarly, ( = 0 (or D(L) = 1) denotes observing
D(t)_ 0 (or (() = 1) together with (Izz, ke). For the augmented o-algebra & generated by filtration F and a random variable X, i.e., 9 == F V oXX), we use the shorthand notation "F, X
For example, E F denotes the conditional expectation of Z with respect F V (X). and E|Z| F = 1] denotes the conditional expectation given F and the event X = 1.
Our goal in this paper is to characterize how large the queue length can be under our policy x at the end of the horizon, compared to the queue length under the optimal policy x¹ that runs with prior knowledge of 0% for all i E [K]. Here, given a set of remaining feature vectors y C X, n chooses job-server pair that maximizes the departure rate given by max p(x 02). If there is tie. we assume that the job entering first is taken. Then queue length regret is defined as RT = ET) - Q" (T)), where (t(() is the queue length at the beginning of time step t under the optimal policy. Lastly, we state some standard assumptions for logistic and queueing bandits:
Assumption 3.1. || < 1 for all x E X, and for some known constant S, 0z e = {0 1101la S for all [K].
Assumption 3.2. There exist K. R R> 0 such that 1/x S (0= S for all x E X and 9 E O.
Assumption 3.3. The features of newly arriving jobs are assumed to be independently and identi- cally distributed (i.i.d) from an unknown distribution 'D. Moreover, there exists E > O such that Ez<D(xx 2 E with of := Amin (E)= > O.
Assumption 3.4. There exists some traffic slack > 0 such that for each E X, there exists server K* E [K] with puxx 0%-) X2
Assumptions 3.1 and 3.2 are standard in the logistic bandit literature. Here, Assumption 3.2 provides parameters to control the local behavior of ji(-). Assumption 3.3 is also standard in sampling-basel approaches for logistic bandits. Algorithm 1 works under Assumption 3.3. but for the adversarial setting and Algorithm 2, we lift the assumption. Assumption 3.4 applies traffic slack to guarantee stability, which can also be found in Kim Oh (2024).
4 CHALLENGES AND NEW TECHNIQUES
Queue State Misalignment. To describe the challenge of the problem and motivate our approach, we start with the simplest case where all new jobs share a single fixed context I1, which can be viewed as the setting of previous work due to Krishnasamy et al. (2016); Kim & Oh (2024). Note that in such case, the queue state X; under our policy and the optimal queue state X; have no difference in the types of features. Now, a key measure for assessing the performance of a policy is (the conditional expectation of) the gap between the departure rates D* (*) for the optimal queue and
4

---

Published as a conference paper at ICLR 2026
ours (t), given by E (t)
D(t Fil c (e(K] μl (I - (x An optimistic algorithm for the logistic bandit would choose Fe, ks maximizing the upper confidence bound (UCB) based on computing arg max u( ((x,0)-1,x)) )= + (x k) where 0,-1,8 is the estimated pa- rameter of server k. and by k) is a bonus term. Choosing the bonus term as an upper bound on the prediction error |p(x (u(xT0.-1,4) 0(-1,k)
p (x)6t) for all X' and &s [K]. the gap can be bounded
from above as
max 11 02) (axx00%. S =E NE[K]
(1(2 UM(=T0--,A + ba, k)) - ulx
max x x.(K)
(11(2 10.T00-10 1,)) + by (x. k:) u(x; 0%.)
max (K
=m(x, (1 k:)) u(x (z.00) S (Zx ki)
where the first and last inequalities are due to the definition of by (z. k),, and the first equality holds because X;- = X. Then we may apply results on choosing (z, k) which leads to a sublinear upper bound on the cumulative sum of gap terms. However, the result is viable only when X X, or X²" C Xz The condition does not necessarily hold as soon as we allow two distinct features.
Aligning Queue States via Policy-Switching Queues. Taking detour from the issue of queue state misalignment, we introduce our new approach to analyze queue length regret. It is two-fold; we consider policy-switchine queues, and to compare their queue length at the end of horizon, we develop a coupling argument.
We define Q(1,, 12) as the length of the queue the beginning of time step t2 under our policy applied from time steps t = to i and the optimal policy applied from t 11 + 1 to t2 1. In other words, for (+,, 12), we switch from our policy to the optimal policy at time & + 1. By definition, Q122 - 22) = (12)) and Q00, t2) (12). Moreover, we may decompose queue length regret as RT (t) - (t) = Σi= E[Q(t, Q(t 1( T)). Here, Qtt, - Q(t T) the length difference between two consecutive policy-switching queues whose moments of switching differ by exactly one round.
To bound the gap Qtt. T) - (t- 100t-1.7 1) for two consecutive policy-switching queues, we construct
a coupling process for Qtt. T) and Q T) to align them. We denote by Q + (t) and Q-(t)
(t) the
coupled queue lengths of (tt, T) and Q(t 1,.). We use notations A A+ (t), A (t) for their job
arrivals and (1), D=(1) (1) for job departures. For job arrival in each round i E [T]. we draw a shared random variable U01
(n, 1). The two queues receive the same new job if Us,1 S X, i... (i) = A Ai(i) = 1, and if U1 > X, they receive no job, i.c., A+ = A A-ii) = 0. Similarly, for job departure in each round E [T], we draw shared random variable U4.2 Unif(O, 1). The server ks-"" assigned to the first queue succeeds, i.e., D D*(t) (t)
and D (+) 0 if U122 )((x;)TT0> Likewise, we have D (t) 1 if U22 S m((x7) Tep and D- (L) = 0 otherwise, where kj- is the server assigned to the second queue. This coupling process preserves the marginals EtQ(t, T)] TE[Q+ (t) and EEQ(( 1, T)] EIQ (t)], implying in
1, if U12 s (((x)t
turn that Rt = Σi E[Q (1) - Q (1)
Therefore, to establish an upper bound on Rr, it suffices to consider
(t,,T) Q* (t) (t)..
As the two coupled queues follow the same policy up round - 1, their queue states at time step i are identical. With this alignment, we can characterize (t, T) as follows. Lemma 4.1. We have (1, T) {-1,0, for all I 11.
Moreover, the expected value of ('(1, can be bounded from above as follows.
Lemma 4.2. Let (2z, kt)) E arg max, Ex. uxxT (2). let Fi = F, V (E(( - 1), A(t), and
let (1, T) == E[v((,,) Ft. D + (1) = 0, D (1) = 1). Then all E [T- - 1].
B(N(L, T)) <
E
11 (cF))TOZ)) - (x) (xTT%)))
E (((,T)
=66
=:01
5

---

Published as a conference paper at ICLR 2026
Algorithm CQB-E
Initialize: E = T 1/2 0, Vo,k = KAOL, I.....K
I: for tort= 1, ,...., do
2: i [1, and A(t - 1) then
> Pure-exploration
3:
21 f- (/xx(-11 x(--1), ky + -p+1
4:
p p p+p (mod K)
5:
else / E ( 1, and E(L B) == =1
and A(l - = then 3t + x((-11) ke Unif([K])
D e-exploration
6:
7:
else
UCB-based rule
8:
(Iz, ks) f arg max SEM, KE[K] u(x SauTO,_1,
1,, .b) + Bc- ||
9:
end if
10:
Match (Iz, ka) and receive r
11:
for I....,K K do
12:
if k ki then
13:
Update Or, as in Section 5, and 3r, as in Equation (1)
14:
V +- Vi-1,k + 2422
15:
else
16:
0., 11 Br, + 31- Ve, t- Ve-1,
17:
end
18:
end for
19:
Sample FE(L) ~ Bern(e)
20:
end for
We prove these lemmas in Appendix B. From the bound in Lemma 4.2, represents the immediate error incurred when choosing suboptimal job-server pair, and 8, captures the long-term effect of the difference in the queue states at time step / + 1 of the two consecutive policy-switching queues. Note that Rr S Ei= m4dt, and we may deduce upper bound the right-hand side by taking inequality, applying the elliptical potential lemma (Abbasi- Yadkori et al., 201 1, Lemma 10) on T-1 mj, and using Lemma 4.1 to get ΣT= 8, < T. This approach would give us an upper bound of (VTT) on Rr, which matches typical regret upper bounds for contextual bandits. However, such a bound is not sufficient, as we hope for a decaying bound.
the
In the following section, we take more refined analysis and characterize of the sequences of my and & based on which we prove a decaying upper bound of (TT-1/4) on queue length regret. This establishes that the queue length difference vanishes as T gets large.
monotonic behaviors
5 DECAYING REGRET FOR CONTEXTUAL. QUEUEING BANDITS
Idea and Outline. Recall that mi represents instantaneous regret, so as we keep updating our es- timators close the true parameters, expect reduce it increases. ô, captures the long-term effect of the disagreement between two consecutive policy-switching queues, so one can anticipate that 6, will increase t since an early disagreement (a small will wear off as they follow the same optimal policy for the remaining T (-1 rounds. In fact, we will show that our algorithm, described in Algorithm 1, guarantees that m. < M, where (M,) [M.herr)
nonincreasing sequence and that S A, where (Athe a nondecreasing sequence. Then we apply Chebyshev's sum inequality to deduce Rr < (Σr-) M.) A.)/(T 1). Lastly, we show that Σt- Mr ((T3/4)
and ET-1 A, (l)g(T))) which leads a decaying upper bound on queue length regret.
Algorithm. Algorithm 1 consists of two phases. It starts with a pure-exploration phase where, a new job arrives, we select while choosing server in a round-robin man- ner. After the pure-exploration phase, we apply the e-exploration policy which, if new job arrives, explores imizing the UCB term in Line 8. For both phases, when a new job arrives, in which case the new job has to be chosen for exploration. Af- ter job-server matching, receive binary feedhack rt whether the server completed the
with probability & and chooses job-server pair optimistically by max-
take an exploration step only

---

Published as a conference paper at ICLR 2026
job. Then update the estimator 0,, by maximizing the regularized cross-entropy loss as 0.10 = arg max, (Ei=1 1(;; = k} [r; log [ 0) + (1 - -r;) log(1 p2x (A/2) and
then projecting it onto the parameter set as 0.. = arg mingee Ei= 1 = 1e) (((x)0 uxxx (212) Jallva. Lastly, update the confidence radius Be,
11kk=1 -k] k1) log(K/0) KS =0 (Vilog(T)). (1) 2
Br, 2\ 2d
1+
Kdgd Σ
We note that the choice of estimators for the logistic model parameters and the confidence radius is due to Faury et al. (2020), thus we may obtain the following prediction error bound.
Lemma 5.1. It holds with probability at least 1 that 00-11)) 1((x" [(x00)) S 1 , for all t E (7). x E X, and l E [K].
In fact, may take recent parameter estimation frameworks developed for logistic bandits, such as those that avoid a projection step and guarantee tighter confidence bounds. Nevertheless, we take the basic estimation method for simpler presentation, letting us focus on the queueing part.
Regret Analysis. Let B. == (x//2) ( 2dloog(1 + 1/ (niAd)) - log( (og(K/o) v.8/ and let the length of pure-exploration r be given by
2C3K
d + loggog(//)) ( o
1687
l (dlog(T)
log(1/0) o 21a
(
ofee (
o - 2e)²
for some absolute constant C3 Then we can argue that after the pure- explooralootioon phase, the uncertainty term, defined as || can be uniformly bounded.
Lemma 5.2. It holds with probability at least 1 1-28 that || | E X. and k E [K].
S
c- for all [ 48
Next, we argue that random exploration steps by the e-exploration policy reduce the uncertainty term while its optimistic exploitation rounds successfully control instantaneous regret with the uncertainty term. Combining these, we show that (conditional) expected instantaneous regrel can be upper bounded by a nonincreasing function in t. We define the good event &g as the event that both Lemmas 5.1 and 5.2 hold for all t [T]. We also define the truncated good event ES$ by restricting Ey up round I, i.e., the event that Lemmas 5.1 and 5.2 hold for all rounds [t]. By construction, EST is F:mmauuuraae..
Lemma 5.3. Under the e-exploration policy, and on the good event Eg. the expected instantaneous regret is bounded from above
[l(u((=;)T u(xx (1 1) min {1, XE + 437 - 1)}
Vt E [T + 1,2), where v(t) = (No + Ae(t-T)aá + */2 exp (0p0--1---0 (- + to exp(- (t- (t-r) 16K
d
4k
Lastly, the following lemma shows that the expected difference between Q+ and Q is upper- bounded by a clipped exponential ramp, exhibiting an exponential growth until a certain round (the threshold round) and then clipped to 1, which is nondecreasing in t. We carefully choose the threshold round based on the length 7 of the pure-exploration phase, where the uncertainty term can be large. Consequently, if the number of remaining rounds T - f 1 is large compared to r, the impact of disagreement in D* and D will disappear with high probability. When - is small, we still have that (11, T) < by Lemma 4.1.
Lemma 5.4. Let w = 47/e, and let C, := 1 1+ 16/e2. On the good event Eg. we have min (1, 20, exp (-e² (T t 1-w)) w) /32)}
E (T
ift < T w -
ift> w w-1
Here, T - w 1 corresponds to the threshold round. Now we are ready to show an upper bound on queue length regret under Algorithm 1.
7

---

Published as a conference paper at ICLR 2026
Algorithm 2 CQB-Opt
Initialize: Vo,+ kdpl, K I,..., K
1: for ( 1,..., do
2: Tt, hig < arg max u(x 12-1,)) + B 1,-1,811=1l1
3: Match (Ix, ki)) and receive r
4:
for k .....KK do
5:
if = ke then
6:
Update 0r,8 as in Section and 3r, as in Equation (1)
7:
V + V1-1, + sts!
8:
else
0, t 01 Bc, + B1-1 VL f- Ve-1
9:
10: end if
11: end for
end for
Theorem 5.5. Let 5 (0,T-2), let be given in Equation (2). For T 2 max max(r,4/ce the queue length regret of Algorithm is bounded from above as
R₁ -0
(PTT-11B"" log ( dT dT-1//1ogl (T)
83/2T log
3/2 dT 1/2 log 3/2 3
l0g (T)
oge0
off
oee
ofea
Proof sketch. Starting with m we split the analysis into two cases depending on whether the good event &, holds. By Lemmas 5.1 and 5.2, we have (P(E)) S 35. On the event Eg, for all t E 11
can apply Lemma 5.3. Moreover, we have the trivial bound m for all f []. Combining these bounds across the two cases yields
i
m S M1 min (1, v + VAE + 1t)
ift
Next, for 67, we follow a similar procedure by splitting into the two cases &g and &g. On the event Eg. we apply Lemma 5.4 obtain
min {1, 3 22C, exp -T-
if T - w-1
6e A.
ift
follows from Cheby- shev's sum inequality that R, < "TT1 m, >TT1 T-1 M, < (EiT)) Mc) T- AT) 1). For the summation of M, ss we split into two parts. Regret incurred from the first rounds is at most r = (d ( For > т, we have M, = ( + ve + 1/vet). Hence, the sum is bounded from above by Ö(T VT/E), and taking = T-122 yields Ö(T3/4). For the summation of A, 's the first T terms give rise to geometric sum, which we show bounded by )) and for the rest of w rounds, A, < 1. Hence, in total, the sum is bounded above by (d log(TT)) (aage))) Combining these, we obtain the desired bound on queue length regret, while the full proof is presented in Appendix E.
Since (M, hre is nonincreasing in f and {A, (T is nondecreasing
POLYLOGARITHMEL REGRET ADVERSARIAL CONTEXTS
In this section, present Algorithm 2 for the setting of adversarial contexts, without Assump- tion 3.3, and show that achieves polylogarithmic regret bound.
Bad Rounds. We say that [T' is bad round if || c/(48)-1.N,) and take B' as the collection of bad rounds. We call [T] E' good rounds. Hence, in bad round, the uncertainty term is large. Under Assumption 3.3, Lemma 5.2 shows that the uncertainty term can be uniformly bounded after rounds of pure exploration. However, without the assumption, bad rounds can arise
8

---

Published as a conference paper at ICLR 2026
toward the end of horizon. As result, for the adversarial context setting, have count the number of bad rounds. For this, we use the counting version of the elliptical potential lemma.
Proposition 6.1. We have [B' - 32 Kd T/(ddKno)))// = O(d log (T)/e*
Another issue to deal with the underlying randomness of whether or not a given round is a bad round. Under Assumption 3.3, we designed the pure- pure-exploration phase that after rounds, each time slot is a good round deterministically. The randomness complicates the derivation of tail bound for (t),, while such bound is crucial to determine how many jobs the round of policy-switching for Qtt, l". To handle the randomness, we define a G-measurable weighted process, given by V(t) = (t-1))(()))) for some constant a > 1, > 0, where G. == (XY, A(1, D(1), A - 1), D(1 1)) and (t) = [[[ |-
backlogged in
Regret Analysis. As in the stochastic setting, take w' to define the threshold round for studying the expected difference in the queue lengths of two consecutive saiicy--witching queues, based on the number of bad rounds in Proposition 6.1:
w Kd +T/(dK>>))f/ (d (T)
Let us define the good event E for the adversarial setting as the event when Lemma 5.1 holds.
Lemma 6.2. Let g = G. (A()), and (1, T) == ()) g (I) = D D (L) = 1]. Then on the good event Eyg we have
min {1, 20, exp (T-
ift w' -11 ift> T w/ -
E
(t, T)
Now state polylogarithmic upper bound on queue length regret under Algorithm 2. Theorem 6.3. Set 8 E (., The queue length regret of Algorithm 2 is bounded from above as
RT O cP log (o) dlog(T)
c1.
Proof sketch. The adversarial nature of the incoming contexts makes it difficult to endow me with monotonic behavior, which in turn makes it hard to apply Chebyshev's inequality as in the regret analysis of Algorithm 1. Instead, apply the Cauchy-Schwarz inequality Lemma 4.2, which -T- yields RT S V m2 // oF. For m, since we always choose the job-server pair fol- lowing the optimistic rule, the difference departure rates can be bounded from above by 2 times the bonus term. Applying the elliptical potential lemma yields ΣT= m (od To bound ΣT-1 63 with (t(t, T',, we apply Lemma 6.2 before. The full proof can be found in Appendix E.2.
7 EXPERIMENTS
In this section, we empirically evaluate the performance of our algorithms.
We generate random instances with À 0.7, 0.1. K 5, d 5, and к 10. Feature vec- tors x E IRd and server-specific parameters 0z E Rd for E [K] are sampled from Uni For each algorithm, we evaluate N 10 instances over T 5000 rounds and report the av- erage queue length at time T with +1 standard deviation across runs. For Algorithm 1, we set Cd log(T) K>- 2e)-2 with constant factor C' 3e 4. The first plot of Figure 4 com- pares our algorithms (Algorithms 1 and 2) against (i) random policy and (ii) the optimal policy (iii) four additional baseline algorithms; further details are provided in Appendix A. The random policy chooses job-server pair uniformly round, the job-server pair with the maximum departure rate. We observe a linear increase in queue length under the random policy, whereas both of our algorithms decrease toward the optimal level after a certain time. The second and third plots show how the performance of Algorithm and Al- gorithm 2, respectively, varies with (0.05, 0.1, 0.15). In the second plot, Algorithm exhibits
random, while the optimal policy selects, in every

---

Published as a conference paper at ICLR 2026
CoD- COD-Cpt
0:2331
000.0a (e-3.00)
028-4 11m0..
200
C0N Opr (ned
Optimal Pailiy
0110.11
0OO Qp. (o-0.13)
coslrr
200
1000
3200
1000
7700
Time Step
Time Step
Time Step
Figure 2: Average queue length across algorithms and settings. (Left) CQB-e and CQB-Opt versus a random policy, the optimal policy, and additional baselines. (Middle) and (right) performance of CQB-E and CQB-Opt, respectively, for E {0.05, 0.1,0.155
longer pure-exploration rounds for small e, as dictated by followed by a sharp decrease in queue length. Our results in Figure 4 demonstrate that increases (i.e., under lower load), our algorithms converge faster toward the optimal queue length, consistent with our theoretical results. Additional experiments varying K and are provided in Appendix A due to space constraints.
8 CONCLUSION
We introduced contextual queueing bandits, a new context-aware framework for learning- while-- scheduling with logistic service models. Using policy-switching queues and coupling argument, we decompose queue length regret into the short-term effect of choosing a suboptimal job-server pair and its long-term effect queue state differences. We proved that CQB-e attains ((T-1/4) regret under stochastic contexts and CQB-Opt achieves Ologg T) regret against adversarially cho- sen contexts, corroborated by experiments. Future directions include (i) establishing lower bounds for queue length regret, (ii) extending the framework to multiple queues, and (iii) incorporating operational constraints such as a maximum waiting time (time in queue) constraint.
ACKNOWLEDGEMENT
We would like to thank the review team for their careful review and valuable feedback. This work was supported by the National Research Foundation Korea (NRF) grant (No. ASS-2024-00350733 and the Institute of Information & communications Technology Planning & evaluation (ITPP) grants (No. ITTP2026-RS- RRS-2024-00437266 and (No. RS-2021-1221 1343, Artificial Intelligence Graduate School Program (Seoul National University)) funded by the Korea government (MSIT).
REFERENCES
Yasin Abbasi-Yadkorf Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. Advances in neural information processing systems, 24, 2011.
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, pp. 3691- 3699. PMLR. 2021.
Zeynep Aksin, Mor Armony, and Vijay Mehrotra. The modern call center: A multi-disciplinary perspective operations management research. Production and operations management, 16(6): 665-688, 2007.
Seoungbin Bae and Dabeen Lee. Neural logistic bandits. arXiv preprint arXiv:2505.0200 2025.
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 Interna- tional Symposium on Theory, Algorithmic Foundations, and Protocol Design Mobile Nenworks and Mobile Computing, pp. 181-190, 2021.
10

---

Published as a conference paper at ICLR 2026
Louis Faury, Mare Abeille, Clément Calauzènes, and Olivier Fercoq. Improved optimistic algo- rithms for logistic bandits. In International Conference on Machine Learning, pp. 3052-3060. PMLR. 2020.
Sarah Filippi, Olivier Cappe. Aurélien Garivier, and Csaba Szepesvári. Parametric bandits: The generalized linear case. Advances in neural information processing systems, 23, 2010.
Daniel Freund, Thodoris Lykouris, and Wentao Weng. Efficient decentralized aglti learning in asymmetric queuing systems. In Conference on Learning Theory, pp. 4080-4084, PMLR, 2022.
Yichao Fu, Siqi Zhu, Runlong Su, Aurick Qiao, Ion Stoica, and Hao Zhang. Efficient Ilm scheduling by learning to rank. Advances in Neural Information Processing Systems, 37:59006-59022 2024.
Jason Gaitonde and Êvva Tardos. Stability and learning in strategic queuing systems. Proceedings of the st ACM Conference on Economics and Computation, EC '20, pp. 319-347, New York, NY, USA, 2020. Association for Computing Machinery. ISBN 9781495379755. 2391403.3399499 URL htwps::tps/.om o org/ 10. 1ee..145550
doi: 10.1145/ 1145/ 1145/3391403.... 99959333911133399999. 3399491.
Wei-Kang Hsu, Jiaming Xu, Xiaojun Lin, and Mark R. Bell. Integrated online learning and adaptive control in queueing systems with uncertain payoffs. Operations Research, 70(2): 166- 181, 2022. doi: 10.1287/0pr:22221.2100 URL httpss//ddo..og/oo.ooo 1ttp:///01...////.e.eee opree...ee....... 202p.....2...................111 2021. 2100.
Jiatai Huang, Leana Golubchik, and Longbo Huang. When Yуарunоv drift based queue scheduling meets adversarial bandit learning. IEEE/ACM Transactions Networking, 32(4):3034-30 2024. doi: 10. 00.109/TNET.202433377555.
Neharika Jali, Guannan Qu, Weina Wang, and Gauri Joshi. Efficient reinforcement learning for rout- ing jobs in heterogeneous queueing systems. In International Conference on Artificial Intelligence and Statistics, pp. 4177-4185. PMLR, 2024.
Kwang-Sune Jun, Lalit Jain, Blake Mason, and Houssam Nassif. Improved confidence bounds for the linear logistic model and applications bandits. In International Conference Machine Learning, pp. 5148-5157. PMLR, 2021.
Jung-hun hun Kim and Min-hwan Oh. Queueing matching bandits with preference feedback. Advances in Neural Information Processing Systems, 37:64649-64702 2024.
G Krishnakumar and Abhishek Sinha. Minimizing queue length regret for arbitrarily varying chan- nels, 2025. URL
25011 13551.
Subhashini Krishnasamy, Rajat Sen, Ramesh Johari, and Sanjay Shakkottai. Regret of queueing bandits. Advances in Neural Information Processing Systems, 29, 2016.
Subhashini Krishnasamy, Rajat Sen, Ramesh Johari, and Sanjay Shakkottai. Learning unknown
service rates in queues: multiarmed bandit approach. Operations research, 69(1):315-330,
2021.
Jiung Lee, Hongseok Namkoong, and Yibo Zeng. Design and scheduling of an ai-based queueing system. arXiv preprint arXiv:2406.0688. 2024a.
Junghyun Lee, Se-Young Young Yun, and Kwang- Sung Jun. A unified confidence sequence for generalized linear models, with applications to bandits. In The Thirhy- Annual Conference Neural Information Processing Systems, 2024b. URL. https: /oopneevieiieeeeee ew. net. forum? ? id= MDdOQa A.TA.
Lihong Li, Yu Lu, and Dengyong Zhou. Provably optimal algorithms for generalized linear contex- tual bandits. In International Conference on Machine Learning, pp. 2071-2080. PMLR, 2017.
Woei Lin and P Kumar. Optimal control of a queueing system with two heterogeneous servers. IEEE Transactions Automatic control, 2966)66677733 1984.

---

Published as a conference paper at ICLR 2026
Michael Mitzenmacher and Rana Shahout. Queueing, predictions, and large language models: Chal- lenges and open problems. Stochastic Systems, 2025.
Yashaswini Murthy, Isaac Grosof, Siva Theja Maguluri, and R Srikant. Performance of npg in countable state-space average-cost rl. arXiv preprint arXiv:2405. 20467, 2024.
Michael Neely. Stochastic network optimization with application to communication and queueing systems. Morgan & Claypool Publishers, 2010.
Flore Sentenac, Etienne Boursier, and Vianney Perchet. Decentralized learning in online queuing systems, Advances in Neural Information Processing Systems, 34:18501-18512, 2021.
Thomas Stahlbuhk, Brooke Shrader, and Eytan Modiano. Learning algorithms for minimizing queue length regret. IEEE Transactions Information Theory, 67(3):1759-113 2021.
Yuqing Yang, Lei Jiao, and Yuedong Xu. A queueing theoretic perspective on low-latency Ilm inference with variable token length. In 2024 22nd International Symposium on Modeling and Optimization Mobile, Ad Hoc, and Wireless Networks (WiOpt), pp. 273-280. IEEE, 2024.
Zixian Yang, R Srikant, and Lei Ying. Learning while scheduling in multi-server systems with unknown statisties: Maxweight with discounted ucb. In International Conference Artificial Intelligence and Statistics, pp. 4275 4312. PMLR, 2023.
12

---

Published as a conference paper at ICLR 2026
A
ADDITIONAL EXPERIMENTS
130
000g X--1
MK-3
638 X--31
C38 0zt 00-50
008 X0e11
CGP Out
X-11
120
Time Stop
Time Stop
co0ir (d-3)
Co3-0pt (d+3)
300
000 (d-3)
300
(e-5)
220
250
220
130
130
50
1000
2033
1000
0033
5000
1000
2033
3000
0033
5000
Figure 3: Average queue length across varying and d. (Top-left/rihh) CQB-e/CQB-Opt for
K {3, 5, 7,9). (Bottom-lefttrighht)) CQB-e/CQB-Opt for d E {3, 10, 10,
500
CDBc CDB
CO0 Con Dx
CDE TMA
Random
Tollcy
Pollyy
303
COB---ts
103
COD O
0-715
0-1bs
Thee Step
Time Step
Time Step
Figure 4: Average queue length across algorithms and settings. (Left) shows the average queue length for MNIST. (Middle) and (Right) show the performance for Heart Disease and In- Vehicle Coupon Recommendation, respectively.
Baseline algorithms. We introduce four additional baselines as follows:
CQB-c-Opt: We follow the same algorithm as Algorithm 2, while performing random exploration in every round with probability æ T-12
CQB-TS: We follow the same algorithm as Algorithm 2, except that we replace the decision rule by sampling rewards for all x E XG, [K] as
k)) N (x 0 11-IA R B ==1.))
and then choosing the job-server pair as (æt, k.) arg max Fz(x, k).
Q-UCB (Algorithm of Krishnasamy al. (2021)): every round t, we explore with probability Bern(min 3K (log" t)/1)). We choose i, the first-in job, and then choose
log²
arg max PD (t) + kE[K]
2Tx -0-1] 1)'
where (1)(1) Ei-1 1(k k)r:/Tt(t 1) and Tk(l: -1) E'= 1(k: k).
13

---

Published as a conference paper at ICLR 2026
Q-ThS (Algorithm of Krishnasamy al. (2021)): In every round explore with probability (ern(min(11)) (1,3K(log") f)/t)). We choose as the in job. For every & E [K], we sample
Fr(z, k)) Beta( +1, (1 - -1) +1),
and choose k2 arg ke[k] Fe(ar,)), where the same definitions of (t) and (t 1) as above.
Notice that Q-UCB and Q-ThS the algorithms proposed by Krishnasamy al. (2021), which is the first work to study the queueing bandit problem and queue length regret in a multi-armed bandit framework without contextual information.
Varying K and d. Figure 3 illustrates how varying values of K and d affect the performance of Algorithms and 2. In Figure 3 (top-left) and (top-right), we vary E {3,5,, 5, 7, } for CQB-e and CQB-Opt, respectively holding all other parameters fixed. In Figure 3 (bottom-left) and (bottom- right), we vary d (3,5, 10, 20), for CQB-e and CQB-Opt, holding other parameters fixed. Consistent with theoretical expectations, performance deteriorates K and d increase.
Real-world dataset. For MNIST, we normalize each 28 x 28 image by dividing pixel values by 255, downsample by averaging over non-overlapping 4 blocks to obtain a and flatten this map into a 49-dimensional feature vector used as the context X. We set the average arrival rate to À 0.15. For the Heart Disease dataset (UCI), we start from 297 records, remove rows with missing values, apply one-hot encoding to categorical features, and standardize numerical features. The class labels are imbalanced (from 160 samples in Class 0 13 Class 4), so we apply the synthetic minority oversampling technique (SMOTE) to obtain approximately balanced K = classes and then sample 4000 instances with replacement for our simulations. We set À = 0.2. For the In- Vehicle Coupon Recommendation dataset (UCI), remove rows with missing values, one-hot encode all categorical features (120 features in total), standardize numerical features, and convert the target into binary label (accepted
feature map,
1, rejected 0). We randomly sample 4000 instances from the processed data and set À = 0.5. We comfortably used = =T/10 for Algorithm because real-world datasets typically have high dimensionality, which would cause unnecessarily large exploration. The results in Figure 4 show that Algorithm achieves the best performance on all three datasets (MNIST, Heart Disease, and In- Vehicle Coupon Recommendation)
B PROOFS FOR SECTION
In this section, we prove Lemmas 4.1 and 4.2.
B. PROOF OF LEMMA 4.1
In fact, we prove the following lemma, which is a refined version of Lemma 4.1. Note that D (t) < D-(t) (t) holds for each E [2]] by definition of the coupling process, so Lemma 4.1 is a direct consequence of Lemma B.
Lemma B.1. 1f D D (t) 0 or D
(t) = D+(() = 0, D- (1) 1, we have (t,, E (0,1) for all E [T 1].
have (t, T) 0), and if
Proof. For jobs Iı, x2, we say that æ1 has higher priority than 22, denoted as dy > 32, if
maxxeik] p (xx
max (xx or
max u |ax u(IT0t) but job iı enters the queue earlier than job 222-
In particular, the optimal policy chooses the job with the highest priority with respect to the binary order >
Recall that Q+ (t) and Q (t) are what are obtained after coupling the two consecutive policy- switching queues defined for Q(t, T) and Q(t 1,T). To characterize (tt T), we understand
14

---

Published as a conference paper at ICLR 2026
the dynamics of the coupled queues for time steps i [t + 1.T). Note that X2= XT- For i E [++ 1, 7), let X and X denote the queue states of the two coupled policy-switching queues for round i. For i [ + 1,7], , let us consider the following five states.
$ = { = }, } 1 = { = (z7))
5T & = 00171)
2 - { X { - (-))))
11 {x 1x = { - 2 <
Then we show that for X2* and X, ,i sufficient to consider transitions between these five states.
For round t, note that X = X, As D (t) < (t). we consider two cases: (i) D (t) (t) and (ii) (+) 0, D (1) =1 If (+) (t) 0, then 2+ X = X = X in the policy-switching queues have the same number of jobs at time 1+1, and moreover, X44 is obtained from X after D (t)
which case we observe S2+1.0 time + 1. If Dt)
the optimal policy processing a job in X, Therefore, when D (t) = D D=( = 1, the two possible states for round 1 are S1+,0 and St 11122 If (t) 0 and (t) 1, then round + would be in state 11+1.1'
Next, we consider round E + 1, for which X and X are given. Assume that round i in one of the above five states. Then we will argue that is round i + 1. As 1, both X;* and X take the optimal policy.
(C1) If round is in state St,,, then X, X, the optimal policy would choose the same job. As a result, round i + would be in state S
(C2) If round i is in state St, it falls into the following two cases, based whether the optimal policy chooses ot for X²-.
(C2-1) If the optimal policy selects x for X this mcans that D+ > D (i). Therefore, there are three possibilities. When (i) -i)()))() (i) = 0, as the queues keep the same sets jobs for round + 1, we have St+1.1 for round + 1. D+ = D (i) 1. as the optimal policy would choose another job in X, we still have state S for round + 1. When (+) 1 and D (i) = 0, round i would be in state S (C2-2) the optimal policy does not choose x, from X then it chooses the same job for X and X which means that round + would in state S S411.1
To summarize, for case (C2), we have S,+1,0 or St.11 round +
(C3) If round is in state S by the symmetry between St and S we may argue that have 1,410 or ST+,1 in round i + 1 with a similar argument as in case (C2).
(C4) If round is in state S it falls into the following two cases, based on whether the optimal policy chooses of for x
(C4-1) the optimal policy selects x for X this means that D+) > (i).. Therefore, there are three possibilities. When D+(1)= D-(()) (i) = 0, the queues keep the same sets of jobs for round +1, 1, we have St.12 for round i + 1. If D (i) D (i) the optimal policy would choose another job in X the optimal policy chooses x; from X we have state S++,0 round + If not, round
would be in state Si+ When D+) and D (i) O. round i would be state S (C4-2) If the optimal policy does not choose 2,5t from 2,, then it would not choose x; from x either. Hence, the optimal policy chooses the same job for X and X round
i ++1 would be in state S 5,+1,2-
15

---

Published as a conference paper at ICLR 2026
In summary, for case (C4), we have S,-1,0 St1,1 S1+,22 1,2 in round i+ 1.
(C5) If round i is in state S2 by the symmetry between ST,2 and S7,2 we may argue that we have S1+100 or 11,1 or $41,2 in round with similar argument as in case (C4).
Recall that if (t) 0 and (1) = 1, then round / + 1 would be in state St+,1 Due to our case analysis above, we have S4+2,0 or 2,2,, for round + 2. If the state of round + is S1+200- then we have Sa,0 for each round i 2 + 2, in which case (b1,, 7) = 0. If we have S for round t repeat the same argument as for state t + If observe ST for round T, then have (), Otherwise, round T would be in state ST,0, in which case (b(1, 0.
(t), then round t would be in state 1141.0 St.,2 By analysis above, we have S1+2,0 or S(42,1 or Si+2,2 for round + 2. If the state round t + is S,+200 then we have Si for each round i 2 1 2, in which case (b T) 0. If we have S142,1 for round f + 2, we have S1+3,0 or 3 for round t 3. S1+3,0 the state of round +, then as before, we deduce (/(4, 7) = 0. It the state is 51+,,1 we repeat the same argument as for state t 2. If we observe T for round T, then we have (tt, T) -1. Otherwise, round T would be in state Sr,6, in which case (t, 7) = 0. If we observe 2, for round + 2, then we again repeat the argument as for round t + to argue that (t, E {0, -1}.
Moreover, if D+
This finishes the proof of Lemma B.I.
B.2 PROOF OF LEMMA 4.2
Recall the definition of filtration given by Ftt = ViVo 1); A()) for / E [T], and notice that Fz, ky are F measurable.
By the regret decomposition Ry = Σ
T-1 E (t, T)], we deduce that
Rr
E E (vb,,)) Fi]]
F
(D 0, D ()
= 1|
(1, (ott ( D (t) D (1) 1]]
where the first equality holds due to the tower rule and the second equality holds since D (t) <
DT(() (t) by our coupling process, which prevents the case where D (t) 1 and D (t) 0. For the
first part of the right-hand side, it follows from Lemma B. that
E (t, Ft D+
D (t) 0 0
E (L, (T,
5.
Next, for the second part, notice that the departure disagreement event with D+((1= = 0, D- 11 occurs when
(ax) I S S (1T7) U2.2 ~ 10..
Moreover, as ++(1) Q(t) and (a k2) E arg magmaxxxx,.een u(xT we know that ot Zt.
kt hy and It = Iú kn = kj Therefore, we have
P P + (t) 0. D (t) = Ft) = (lx;) -x(T
16

---

Published as a conference paper at ICLR 2026
Plugging in these observations to the above decomposition of Rr, obtain
T-1
RT
E
(a;)) - (z) E
[ttt, T)
F D (t) (t) (t) =1]
T
1A
E
(x (M ((z)) - (xT ((TT0))
D+. B B ( | (*) = 0 (t)
where the second inequality follows from the Cauchy-Schwarz inequality. For the second square root term,
E
E
(t,
T)
Fi.t D (t) = (t)
SE
E
(Rb T))² 0,
E
[T
F. (t) 0, D (t) = =1]]
(Lemma B.1)
T))
This finishes the proof.
Remark B.2. Notice that the same proof can be applied for the adversarial setting by replacing the filtration F with G, To be more precise, we may prove that
(I, V T
(x:00,
E (1,
= E()(t,T) where Gt C.Vo((A(t))) =( g. D = D (t) 11. and (et,k]
arg max ME((K) 11xx 0%)
C PROOFS FOR THE LEMMAS IN SECTION
In this section, we provide our proofs of Lemmas 5.1 5.4. The proof of Theorem 5.5 is deferred to Appendix 1.
C.1 PROOF OF LEMMA 5.1
Recall the definition of 0.-1. which is the projection of the maximum likelihood estimator 0 1 following
δ_11.1 arg min DE
Σ a (x.0)
(x)0(_1.e)
V
Set As E [K]. For all x X, E [2]] with probability least 1 8/K, have
" r T 1-. ) - (z))
$ R T (0-11, - 87)
(R-Lipschitz)
|| ||o - Oz -
R
(Cauchy-Schwarz)
(1+
2dlog
(1+ kdnd
Ei(k: [(]]==}}]
k1) log(K/))+ /vo
|
2
\
(Lemma F.3, R S 1/4) where for the last inequality, we replaced with the actual number of the update for server k. which D{= 1 = k3 and with 8/K. Finally, taking the union bound for all servers ls E [K] finishes
the proof.
17

---

Published as a conference paper at ICLR 2026
C.2 PROOF OF LEMMA 5.2 For all E [T + 1,7 we have
||0||
|
| |0l|vz
(4)
1/2 (V(-1,x)
min (V+,k)
Let N > be the number of jobs matched to server k E [K] during the pure-exploration period [1, r]. We first show that if N is large enough, the minimum eigenvalue of V is reduced enough to show the proof.
Recall that in the pure-exploration phase, immediately choose the newly arriving job with the server in a round-robin manner. Then, we can see that N features inside Vr, are i.i.d. samples from the unknown distribution D. Here, if
(Civa+ C24 log( [o)(K/6)
2 +
2B ob
(5)
o
for some B 0, it follows from Proposition F.5 that
Amin (Vr,) 2 B
holds with probability at least 8/K. Based on this, set B 16,3/ 26)². Then, if
N C3 + log(K/))
1633 of(c 22)²
0 [dlog(T)
(6)
of
off²
for some absolute constant C3 O, we have
Amin (Vr,) 2 (E 22)²
Then, considering Equation (4), with probability at least - 5/ K/KKa and for all & E [r + 1,7].
|
6 26
S 6 2
5
1/2 (Vr,k)
4,3
4,3-11As
and the desired result is achieved.
Now, we show that by our definition of r, each of the K servers is guaranteed to get at least F >>> i..dd features (KT in total) up to round with probability least 1 8, where
d log( log(K) K/0)
16,9%
7: C3
T (c 22)2
Since in pure exploration round, we always choose the newly arriving job for the random explo- ration. Therefore, the total number of arrivals until round becomes the number of the i.i.d. features inside Vy, Now, consider the sum of A(t). Since E A(t) are the summation of i.i.d. Bernoulli random variables with mean År, applying Hoeffding's 's incquality
-2 (AT K7)²
Σ A(t) Xr S KT XT
& exx
if KF S Ar holds. To represent the probability in 8, setting B < log(8), we have
X272
2AK + 1og((/0)
k2 2 0,
Solving the quadratic inequality for т, and choosing r as
A
A
A
4A2 A2
(dlog(T) ofe²
0
2
2X2
18

---

Published as a conference paper at ICLR 2026
where
A = 2XK + log(1/0),
A2 = =K?7
We also that satisfies the condition since Ar by our choice of 7 and F
A1t V A9 -2
2AK KF. Therefore
A(t) 2 KT 21-6.
(8)
Finally, we gather the results. By Equation (8) we get at least KF iidd. features during the initial rounds with probability at least 1 6. By round-robin assignment during the pure-exploration, each server receives at least i.i.d. features. Since F satisfies the condition in Equation (6), for each
server & E [K], with probability lest 8/ K, Equation (7) holds. Lastly, taking the union bound for all servers and for Equation (8) finishes the proof.
C.3 PROOF OF LEMMA 5.3
Before we prove Lemma 5.3, we need to establish several technical results first. By our e-exploration policy and Assumption 3.3, deduce following proposition. Proposition C.1. Under the e-exploration policy
Ae E. 2
[ E AEE,
E [1(ke= = k]]aa]]
K
E-exploration occurs with probability of when the new job (t- arrives and A(t 1) 1. Therefore, by Assumption 3.3,
Proof.
E [ T = P(A(1 1) 1, E( 1) 1) [ IP(A(L - 1, =)]
P(A(t 1) = 1, E(t 1) 1} (((-1) (x((-1))
T P(A(t- - 1) 1, 1) =1)
>eΣ.
Also, since we choose the server uniformly,
E [1t = k) ł (Ne/KYE,
as required.
Now we provide high probability lower bound on the minimum eigenvalue of the design matrix. Lemma C.2. For E [T + 1,7],k k. e [K]. with probability at least
exp (- xe((-r)
3K
d dexp
Xe(t-r)añ 16K
Ae(t T)o
Amin (Ve,)) 2
4K
Proof. Consider V. We will first show a high probability bound that for some N O, the number of ii.d. sampled features inside Ve, from r + to T is larger than N > O. Then we will show that if there are N (or more) i.i.d. sampled features {x; J.r: then Amin (2 xyae] ) is larger than M for some M > 0 with high probability. Lastly, considering the probability that both events hold, we obtain the desired result of Amin (V,,,) M with high probability.
First, define the total number of random explorations for server k from T + 1 up to round / inside as
E
Σ 1=
1[A(i 1) = 1, Eli 1) = 1, k =k k}
19

---

Published as a conference paper at ICLR 2026
Since E[E, λe(t /) K, set
1
1 E[E de(t
(e(t-T) -T)
8 2'
N 8p
K
and apply the Chernoff bound (Lemma F.6), we have
Xe(l Ae(l -T)
P(EL 2 N) = (ELN & 2 exp
8K
Next, consider the case where Eg 2 N. Choose those i.d. sampled features and define a new design matrix Ve, which consists of them
VE,K 1)
1, = k)
Now we apply the Matrix Chernoff bound (Lemmaa F.7), on Ve, with
8' 8 2' n' NN,,, M 8'n'o
Then
P (Amin((e,s)) (Vr,)) 2 M Eidt 2 N) 2 PP
Amin (Vex)) 2 M Ei -N)
= 1 PP (Amin (Pr,)) S M E = N)
2 1 - dexp (-
>xE(t (-eett-Tpe -)
(10)
16K
Now we consider the case when both Equations (9) and (10) hold. By Equation (9) we have E,,- 2 Ae(t-r) which means that there least Ae(t-7) i.i.d. features inside Ve, with high probability. Next, by Equation (10), if the number of i.i.d. features inside Ve, is larger than xe(t-r) we have
2K
Amin Ci 1= [k; = k))a..) 2 Ae(t-r)oß with high probability. Then 4k
Amin (V2,s) Amin Aoll + Σ 1(k =k]k=)))xx))) 2 No + de(t T)og
4K
Next, considering the probability of both cases holds together,
P Fr,k 2 N, Amia Amin(Ve.)) M)
IP (EE, 2 N)P Amin((e.p M
E 2 N)
(- Ae(t (-Ae(t- (e((t-T) dexp
de(t T)o
2 exp
8K
16K
where the last inequality follows from Equations (9) and (10), finishing the proof.
Proof of Lemma 5.3. Now ready to the proof. Define the good event &,, when Lemma C.2 holds in round I. Then on the event Et, for any x E X, 1 E [r + 1,7],
Ao de(l - - 1)o -1
|
Amin (V)-1A)))
4K
E does not hold, we use the naive bound
||0||
1
$ 1/20-
1-1
20

---

Published as a conference paper at ICLR 2026
Taking expectation,
E
12
Fr, Btt -1)
E
118,,1
Fr, E(I 1)
+E [ ||a 1
Fr. E(l -1)
1L
||00112 V.
Fi, - 1)
+ IPE,)) )1
Ft,
de(t - 1)02
-1
1o +
4K
(x (-(--T-1))
(- (-(t-T-l 1e
exp
+ dexp
(11)
8K
16K
where the inequality follows from Lemma C.2. Recall the definition of v(t 1) which is the right- hand side of Equation (11).
Now we consider the expected value of instantaneous regret on the good event Eg. We define new event ε, which holds when A(t- -) = and E(t- where E-exploration is applied in round t. Notice that if e- e-exploration is not applied, we choose the job and matching server optimistically by choosing the maximum UCB value. Therrforee
u (xt) (at)) - (x: (x.T62))
- E (N (x;)T((z) - (z) (zT
Fi, E( 1(1- ]1]
E
(tower rule)
P(E22) + PPE (# (a:))
- (x.
Fi. E( - m)
Ft. 1)] E(t
$ d x E
46% 438-1,e11z
11 -
where the last inequality, on the good event Eg. we can use Equation (18). Now, for the second term,
4,3 1. 1.
12 V
Fr, -1)
< 1 || |loaale==1
Fr, - 11)
S <4.3.u(l. 1)
where the first inequality holds since 37 2 B 2 11- and the last inequality follows from
Equation (11). Substituting the result and taking min[11-} on both sides finishes the proof.
C.4 PROOF OF LEMMA 5.4
For simplicity, in this section, we assume Lemmas 5.1 and 5.2 always hold (E, always holds) and skip the conditional notation for it.
Recall the definition of the filtration
F= (x A(1,, E(I),
A(t 1), D(t 1))
Note that F, shorts of Ett 1) therefore Q(t) still Fe-meauurable, while xa not.
Bad rounds.
Now we define F, F--meauurable bad rounds. Let notations
UCB(x, k) = 14 T0001.1.) + Br 11 i.
and
(+) ((()) = arg max UCB(x, k). 4 kE[K]
21

---

Published as a conference paper at ICLR 2026
Then
B = (E ((t) a 1
(t)
(+)
6 c 22
v-
4/3 (,o(1
Under Fe, note that ke can be different from 2!") A(th since the unseen E(t 1) could choose random exploration. However, since Q(t) is F F--easuurble, M, and nt 1((t), kg a(+ also Fr- F-meesurable. We also introduce notation
(tt)=
n
Next, we establish that for good rounds, there a negative drift as described in the following propo- sition.
Proposition C.3. On the good event for all & & B. [[A(t) (() Fi) -1/2 -112
Proof. Consider Q 1) which corresponds to the policy-switching queue of following our policy up to round t 1 and switching to the optimal policy at round t. As explained in Section 4, we may applying the coupling argument on Q(1) and Q( - 1,7). As they follow the same policy up to time step
two coupled queues for ((t) and Q(t T, have the same queue state in Let D(t) and ( - 1, denote the random job departures of the two coupled queues at round for Q()) and Q( 1, T).. Note that
round L.
EB (A(() D(L) [F]]
D(t) Fil S - (E(t- - 1) Fi) E 1(t- D(t)
EE A(t) D(t 1, F E
Fr. E(t 1)
-P(E(L 1) = =0 (11-1,1)- ((1)
Fr, F((1 - 1) =0]
- + u (ox))
((xf+)) T 0240)
- + 23 1,, |24 (x((t/
t-1,(()
<c/²
where the first inequality holds because D(t 1, is due the optimal policy and Assumption 3.4 holds, the second inequality holds because our algorithm takes (+) k{{t) under E(t - 1) = 0, the third inequality follows from Equation (18) on the good even Eg. and the inequality follows from definition of B.
Proposition C.4. On the good event Eg. we have
B(T) = (lgg(T)) oge2
(dloog(T)
Proof.
The result is direct consequence of Lemma 5.2 and the definition of B.
Queue length difference under disagreement. In this paragraph, we give the upper bound for the expected queue length difference between two consecutive policy-switching queues. For notational convenience, we assume that Qt.. 7) for & E [T] are coupled based on our discussion in Section 4. Then we study the expected queue length difference Q(t, T) Q(t 1, T)) given the disagreement event where Qt T) fails and Qt T') succeeds in round Recall the definition of Fit.
プ = F, V (E (),
and we define new event of
E₂(1) = (((+)))(--))-(
22

---

Published as a conference paper at ICLR 2026
Lemma C.5. For all t [T - 1). the event (t), we have
8(T (110(+))-1-(--I-II
0, 1 =1] 1] 2exp
D
Proof. We start with the left-hand side of the desired inequality which is
E [t) | F.. D* (1) = 0, D (()) =]
the value of (1, 7) is in 10. We can ignore the D* (t) case when (t, 0 considering the value of E (t, T) ,
By Lemma B.I, if (1) = 0, (()
= 0, D- (t) = =]]. Now we only consider the case for (t, = 1. (t, = 1 means there is a disagreement event in and (1) = 1, and the difference of queue length is preserved until round T. Notice that if the queue with an extra job Q hits O queue length before round T. the queue length difference between Q+ and Q will always become 0 thereafter by our coupling process. This implies that the probability of (t) ((t,)) never hitting length for all j + 1, 7] larger than the probability that the queue length difference is preserved until round 7. Then, we have,
round as D+ (4)
P S (Q(L,) >..,)>>,V, 0,V E (. [t Fr. D* -,
FT.
(t) 1)
Next, consider the event on the right-hand side, where Q(t,5) > 0 for all j E It This means that by the queue dynamics, Qtt, 1 ((t,)) D (Aj) for all j. Therefore the event on the right-hand side implies that the cumulative net service at round T does not exceed Q(t+ which is
+ 1) - 1,
P (Q(t. > 0, (ejeEtt,TT F... D+ = D (t) 11
(A0 21 Ft. -0) -1)
SP Q((+1)++
i=t+1
Furthermore, to upper bound the right-hame side, we prepare to apply Azuma Hooff--ig inequality (Lemma F.8). Define a sequence for i E [, 1, - 1] as X; == E[D (i) - A(i)
(i)
A(i) and Y == Ei=++, X,. We have E[X, [F]] = 0, and IY: Y = |xxl S 2, which means, by applying Azuma-Hoeffding inequality with a < (T - 1 1)e 1) Q(1 + 1) (and the condition of a > 0 holds since we consider on the event Eg()) we have
P Σ (EID+ (1)+))-((111))) -1) A(i)))
(T 1)e + 1- Q(+++((++())
+ 1) (+) -,
((t- 1)c
Q(1, -1-Q(1,i+1)) 1))2
$ 2cxp
8(t-i-1)
Notice that for i E + 1]. D+ is follows by the optimal policy, which means E(D+(1) A(i)
Fij 2 by Assumption 3.4, which implies that
T-1 1
- (P) A(1))
P
Σ (0000-10)21-(((11) =1,
NitH1
T-1
=P Q(++1)++
Σ
- - -, =,
1=++1
23

---

Published as a conference paper at ICLR 2026
Combining results, we have
= =1] s 2exp (- (-(((+1)-11) - 11 -1- 8(T -t-- 1)
E Ft.
finishing the proof.
Tail bound for Q(t). The result of Lemma C.5 shows that the queue length difference under the disagreement event can be bounded by the exponential term of remaining rounds (T - t 1) (which suits our goal upper bound the queue length difference with the exponential ramp) and the queue length Q(++ 1). Therefore, in this paragraph, we control the value of Q(L + 1) by giving the exponential tail bound for it.
Lemma C.6. Set (0,c/2), p e c-ne/4, c". For some 3j
log ( P
and 2 we have
IP (Q(()) 2 aB(1 1) + b, Eg) s p en
1
Remark C.7. For simplicity, assume the queue starts with an empty state Q(1) Set 1) c/2, e 2 2 for x E [0, 1). then we can simplify Cp = 1
p= e -- 218, Since
Proof. Recall the definition of Eg. where we cut Ey to round such that Lemmas 5.1 and 5.2 holds for all E [T'] round to make J--measurable.
Now, we start with the one-step bound for the moment generating function (mgf) of Q(t). For some r E (0, c/2),
E en((+)))
Fi =E (0IR10++(-DD00 D(O)+
Fi
< 1 R ( (((e) Fi
where the incquality follows by considering both cases, where Q(t) + A(t) - D(t) < 0 gives A(t)
1 and Q + Aaat(((ff)())))) 2 0 gives e A(0)) -01)()++()))D0))) We split into cases for E ((t(A(()-Dis)) Fi..
(CI): If & B, by Proposition C.3, the good event EY we have
E [[A(t) D(t)FE) -E/2,
Therefore
E (((A()())D()))))
F.] = e n [ Fi
S e ne/2 2/122
(IA(t) - S Hoeffding lemma)
c 1//4
(n E c/2)
p
(C2): If E B, we give naive bound of
E (enlA(t)-DD ((O)
Fi S 6d = =B.
(A(()) - D())) s 1)
Substituting results for both cases yields
E
(
F. 11 Q000 (pI(t +
(12)
Remark C.S. By the initial pure- eure-exploration round in Algorithm 1, rounds T + 1 to are good (Proposition C.4). However, for rounds 1 to T, whether round is good or bad is not deterministic, which means 1(t E B3 is Fe-masurrble. This makes it hard to find a relation between ((++1) and 20 from Equation (12), because e(())) and (p1 {t & B) + 31 e B}} on the right-hann side are dependent.
24

---

Published as a conference paper at ICLR 2026
Readers might think of a simple workaround: treat all rounds up as bad. This is viable since (pl(t & B3} B1 E B1) S B and the number of bad rounds is upper bounded by Proposition C.4. Doing yields deterministic set of bad rounds. Thus 1 [3) is not random variable. Taking expectations on both sides of Equation (12),
E (e
[ = IE [e S1+ (p1(t & BJ + 81(1 E BB)) E [0R(0]
resulting in simple relation between L [e and E [enQ(t]
However, we do not take this detour. Instead, we provide the proof assuming 1 E BJ is an Fi- measurable random variable. The reason to align with the proof of Algorithm where, in an adversarial context setting, 1 E B'} is G.mmesurable random variable that cannot be known beforehand.
Assume that 1 E B} is a random variable which is F, measurable. Therefore, directly applying expectation on both sides of Equation (12) will not separate enQ(t) and (pl(t & B) + B1 E B}) on the right-hand side, making it hard to apply the recursive relation between E [e*Q(++1] on the left side and E [enQ(t)] on the right side. Therefore, design new weighted process V(t) to avoid such problems. Define the weighted process as
((t)= = (a)
8 B(t-1) e0(())
Lemma C.9. We have
E [[))) S p' 'EE
+ 1
1- p
Proof. Recall that s. ax(t), k(t), and 1(t E B) are Fe-maauurable. Therefore,
E [1{ 9 (t + 1) Fi]
$ E [1 V V( Fi]
((t)
(t++1
Fg
B
B(t-1)
11|EB)
E
Fi]
P
<1(Eg)
1)
19
-1(EB)
1 (R00
(plit & B} + B1ft B)))
p
p
(Equation (12))
Since
(((EB)
1
(pl B} + 31(1 E B)) = P.
p
have
8 (
B(t-1)
(0 (( (2)
-B(()
E [1 1) A. S ((E)
S
(3/p 2 1)
Taking the expectation on both sides and applying the tower rule on the left-hand side gives
E [1(t)tt) (( 1)] < pE [1{g]] +1
Solving a linear recursion, we have
1-2
E [[( < P'-'BIV(1)+
Σ
p² < p 1 I1 [QR((]] +
S p
1 E
1
1 - p
finishing the proof.
25

---

Published as a conference paper at ICLR 2026
Based on the results, we have
P (Q(1)= 2 aB(t 1) + 6, Eg) = PP (Q((t) 2 aB(t 1) + b, (g)
P (P(1 2 e E -B(1-1)
1
IP v(1)
en Eg
P (V
2 cnh Eg
where the last inequality follows from by choosing 1 log applying Markov inequality to the right-hand side yields 1)
@
Under the condition of b 2 0,
P (v((t) 2 nb
(0 E
e
1
7b
(Lemma C.9)
enb
p
Substituting the result back finishes the proof.
Proof Lemma 5.4. Now we are ready to start the proof. Recall the definition of Ftt, (1,,, T) and the result of Lemma C.5, which is, on the event &g (4)
E (t. Ft. D (1) 0, (1) = < exxp
8(T -T-
Our goal is get an exponential decay of this value in terms of the number of remaining rounds (T - 1-1) 1) and avoid the dependence of Q(++1). Therefore, we split into 2 cases where Q(+++) 1) s
[T-r-1) and Q(I ((1+1)) 1)) <T--t112 which gives
((,,E((,,T) 1B (x(,,T)) D 0, D 1]
1) (T (T-1--1 E (tt 7) 0, < $1(010- Q(t +)(++1)+++++
2
B.
+1 +1(((++)>> -T-t-1) 1)
Eg (1)
2
For term B1,
E (t,
(0)
(1110(++1) 1) (4
+ (
-t 1) (t, -
Multiplying 1)) ( } on both sides yields
I(((+1)) (1T-1-1)
2 E (bttt, -))
6(T <T--1-1) {1(0(+1)+
Q(++1)
Tbb(t
= ())
2
We can see that the right-hand side implies Et), which means 1(Q(t + 1) (T 1)e 13.
Therefore we can directly apply the result of Lemma C.5, which yields
B1 1((0( Q(t 11) <TT
(Q(t 1) (T -- 1)c)2
2exp
2
8 --1)
(T - 1)c + 1)2
< exp
8(T - 1)
( 1)
2xxp
26

---

Published as a conference paper at ICLR 2026
Substituting term B₁ back, taking the expectation both sides, and applying the tower rule yields
( -1
32 (
P Q(t - (T - -t -) Eg
E 1 [(E & 2exp
(13)
B
Next, we going to apply the exponential tail bound of Lemma C.6 to term B2. Recall the lemma IP (Q(1)=
aB(1 + b, Eg) S Cpe
and the condition of a, b which are
1 2 log
b20 0
1
p
Set a = 2 then
1 (n (-mcc4)) a>1 a>1+</4=
1 (10g (c") - loo (e-x))
log (
8
1)
7)
7
We need the condition of b 2 0. In order to control this, set threshold value of the remaining rounds as
2aT
2aB(T)
W ==
and split into 2 cases.
(CI): -T--1 w, we do not apply Lemma C.6, since it means that there are not many rounds remaining to reduce the queue length difference by emptying the queue with an extra job. Therefore, we give a naive bound of
E [1EE))((T,)) sT.
(C2): (T (T- 2 w, means that -T- (2aB(B)) then
<(T ct aB(t)
B2 = [(( 11) aB(1) + P Q(t ((++1)) aB(t) +
Eg
2
(c 1)
aB(T))
Eg
2
(eT - 1. 1 w)
S Q(++1)2 aB(1)
Eg
20
< C,e x ((TT-1111-
(Lemma C.6, 62.6200 0)
Substituting this Equation (13) and taking min 1} on both sides (by Lemma 4.1) gives
(T--T -t -t-1)) + Cpexp
(-Me( 2
w) }}
E ((1EE))(t,T) < min
1, 2 2exp
32
min 1, 2C, exp
(-32 (T - (T-1-1-w)
(C, 2 2, = c/2)
32
Combining the results of both cases yields the desired result.
D PROOFS FOR THE LEMMAS IN SECTION 6
In this section, we provide our proofs of Proposition 6.1 and lemma 6.2. The proof of Theorem 6.3 deferred to Appendix E.2.
27

---

Published as a conference paper at ICLR 2026
For the adversarial setting, switch the definition of the filtration exclude E(t)
G. = o A(1), D(1), D(2).... , D(t - 1))
Note that (t)) and Ge-measurable. Now we define G fe-measurable bad rounds and the notation
as
B' = I E [T] | Iloellyy
(0(1) = KM4 n B'H.
1-1
43 43,-1,8
We first introduce the negative drift for the good rounds Proposition D.1. On the good event Eg, for all & B',
[[A(() D(1) Ge] S -e/2
Proof. We show there is a negative drift in good rounds t & B': Recall the definition of D(t) and Dtt 1, in the proof of Proposition C.3, which coupled each other. Then we have
E [A(t) ((t) Gr] E A(t) D(t 1, Go +E [D 1,t) D(t) Go
I - + I (x;)
o%.) < - + 23 1,k, [|| [.ll=elllv
(Assumption 3.4, coupling process)
(E), Equation (18))
S c/22
(t $ B')
as desired.
D. PROOF OF PROPOSITION 6.
We show the upper bound of the number of bad rounds B' follows:
min { 1, 48
IB'
4,T
KEB'
(Be 2 Be,ks (Bi)s increasing in 1, 43, 21,1> 0)
min { 1, || 1 1.k1 }
(1 E B')
$ 2Kdlog(1 T/(dKkda)).
(Lemma F.1)
Moving the term
on the left-hand side to the right gives the desired result.
4/f
D.2
PROOF OF LEMMA 6.2
The proof follows the same argument as Lemma 5.4. First, define a filtration as
g G. v (A(t))
Now, consider the queue length difference under the disagreement on the event (t) where (t) = (Q(++1) < (T - 1)e + 1), defined as
E [ttt, T) gt (D)(D(t)-- =
Recall the previous definition of the filtration and the corresponding queue length difference under the disagreement for Algorithm 1, which are
F :F (E(F A(t)))
E (bt( D+ ()) (
The expected value is conditioned on F.t, D (t) = 0, D (t) = 1. which means the value of the conditional expectation only affected by the situation up to round which is represented by
28

---

Published as a conference paper at ICLR 2026
Q( 1). Also, from round + 1 to T, Tt) follows the optimal policy and this is irrelevant to whether we followed Algorithm or Algorithm 2 until round t. Thereby, we can simply follow the same proof procedure and reuse the result of Lemma C.5, which gives, on the event Eyy
E (1, (", D (1) 1] S 2 (- (-(Q(t=1) 1) 1- -T 1 (14)
8(T (1-1)
Next, we consider the tail bound for Q(t). Recall that Q(t) and (t) are G.-measurable random variables. As noted in Remark C.8, although in Algorithm 1, 1tt E B) is deterministic by the pure- exploration round, we develop the proof if is Fi-measurable random variable. Algorithm 2, we can that 1 }"} is Ge-measurable. Also in Proposition D.I, we show the negative drift in good rounds conditioned on G. which is the same as Proposition C.3 of Algorithm 1. Therefore, we can exactly follow the proof of Lemma C.6, simply replacing B with B', Fi with Gi, and &g with Eg. and get the same result of
PP (Q(()) aB' - 1)) + b, Eg) Cpe 7/
(15)
Now we are ready to start the proof. For the queue length Q + 1), we split into 2 cases where Q(I + 1) v -'---1) and Q(L + 1) > <(T-t-1) and proceed as
1f { (T, gt. D = D (t) 1]
- 1)t RT -t & E [t(t.T)
- (t)) -t) -] g (+) = D ( (t) = 1]
2
=1(0(t+))
<(T <(T-1-1)
{ E ((t,
E
52exp (- ( +[(O++)>> c(T -t-1) {
32
where for the inequality, for the first term, the indicator function {(((t +1 - <(T-t-1) E/
2 implies that (1) holds, therefore we can apply Equation (14). After that, replacing Q(t + 1) with =(T-)-1) gives the desired inequality.
Taking the expectation on both sides
(T ((T---11)
<(T - -1-1) +P (((++))>
E (t.)) S 2 exp
Eg (16)
32
2
Set 2 and threshold value w of
w' = 2a 2Kdlog(1 + T/(KKnA)))
4Bz 2)
2a 2aBB(T) (T)
(Proposition 6.1)
Now for the second term of Equation (16), we split into 2 cases.
If If -- 1) < w', we give a naive bound as
E [1, 1
(C2): If (T --11 2 w/, then
Q(t + 1) <TT -1-1-11 1)
2 Eg 5 =P [((++)) 2 aB'(t)+ +
(cTT-1-1) aB((t) Eg
((T 11 1-1) 1) al'' (T)
< P Q(++1) aB'(t)
Eg
[e(T - l-w")
SP Q((+1) aB((1)
Eg
20
-n (eT 1 11
-n(s
$ C,e
(Equation (15), 2, 0)
29

---

Published as a conference paper at ICLR 2026
Substituting the result to Equation (16) and taking min(', 1) both sides yields
E
(1,))
-
(T
[TEETT 1 w }
S min
1, 2exp
Cp exp exp
32
2
2²
(T 1 w') ('))}
S <min
1, 20pexp exp
((C, 2 1, = =/2)
32
finishing the proof.
E REGRET ANALYSES
E. PROOF OF THEOREM 5.5
Recall the definition of the good event Ey where both Lemmas 5.1 and 5.2 hold. Then, by the union bound, P(EE) 2 1 36. By the regret decomposition result given in Lemma 4.2,
T-1
RT
16
(c;)) (x. (xT
2
1t, T)
=16.
=:
Let us consider my Fort E [L, we give naive bound of 1. For E [T + 1,7
m < P(E)) E ((g) (n (att) 06: 1 (x. (x.To%)) 2
s 36 + min 4.7 1)},
where for the last inequality, can apply Lemma 5.3 the good event Eg. Applying square root and min(1, on both sides
m. S min
1, v35 + ViE + 437ult -1)
1)
Combining these, we obtain
ift ST T ift
S Mr
min 1, 35 + Ae + 18z
where (Me gives rise to nonincreasing sequence.
Next we consider term 6, For T - - we give a naive bound 1. For t I T w 1, we have
8 PPE)) + P(E,)) (tt,
36 + min (1, 2C, exp
(--
2
where the first inequality follows from Lemma 4.1, and the last inequality follows form Lemma 5.4 on the good event Eg. Applying square root and min(1, both sides
& s min {1, v35 + 22C, exp (-64 64 (T 1- - -11-11
Then we deduce that
min 1, 38 + 22C, exp
(T (T 1--11-w)) w))}
ift - w ift> T -
d, < A. =
30

---

Published as a conference paper at ICLR 2026
where (Ar)e(T) gives rise to nondecreasing sequence. Consequently, obtain
PT
M,
Since tefry is nonincreasing and (Ather is nondecreasing t, applying Chebyshev's sum inequality (Lemma F.4) gives
RT S T-1
Σ M,
Σ A
(17)
For the summation of M''s,
Mr Mc Σ Mr
1=T+1
T-1
S + (1-) --= + 23T
Σ Vu(t-1)
1=
< 0 dllo((T)
dE(t - -1100
-1/2
01) TVVie 23T Σ
oft2
4K
Bi
T
(t - T 1)AE
(t [ 1)AE
+ 2,8
exp
+ Vdexp
16K
32K
1
B:
For term Bi,
T-1
(>o+
- 1)08
Xe(t
-1/2
1
4K
Bi B VAo +
dt
S
VT.
|
4K
Voo
oovie
For term B2, by applying the geometrio-series formula, obtain
B2 S 1
d
1
16K
32
( e /
VTo
λ
where the second inequality holds because e= 2 x/2 for x E (0, 1]. Using the bouns on B₁ and B2 with ε = T 1/2 yields
T-1 1
(llog(T)
Σ
M 0
+ (1011)+TVV
off2
4K
23T
16K
32VdK +
+ 2,T
+
T
Vxn
σoVi
de
Xoog
(llo(T))
1/223/44 ///2 1/2
dT 1Tg222102/220 2/2 o
=0
73/11 +
offe
do
Next, for the summation of A.'s,
T-w-1
2
Σ
110110002 (T-
+
Σ
v 20, exp
TT - t- - 1 - w)
64
1=1
t=1
2ar
2Cp
+ +1(1)
e- c2/64
dlog(T) (T)
0
(1 (1-e 2 x/2, E (0,1))
ofee
(log(T))
o
of
31

---

Published as a conference paper at ICLR 2026
Finally, plugging in the bounds on the summation terms Equation (17), we have
d log
(T)
d/ log(T)
d8/278/4 log 3/2
d log 8/2
log (T)
RT S T --1
0
ogr3
+
oico
ofce
PT- (PT-1110' log2(T)
dT dT log(T)
d3/2 - 1/4 104 3/2 (T)
log
d 1/2 log 3/2 (())
=0
+
oges
oge
oge
ofe
as required.
E.2 PROOF OF THEOREM 6.3
Recall the definition of the good event E where Lemma 5.1 holds. We have P(E)) 1 8. By modification of Lemma 4.2 for the adversarial setting explained in Remark B.2, we deduce that
RT
E
n (oz))o2=) (c.To%)))
TE (t,
T
E
(x;)Tozz)
(xz)
27 (xT
Σ (t,,
(Cauchy-Schward
B.
Ba
For term Bi.
E n1 (zz) -1 (xr) 0% )9
1 <P(E)) E [( (n (1xt) (x. )
x (T + 1 (8) (1 (c(tt) (x) (rf(%) 27
as P(E))) < 5 and d E (0, T-). For the second term on the right-hand side, on the event E/
# ((t)) 0%:)) - (2) s 1 (xtt 0011.111)))) + 10-1. || anilly; r (z. 0%,
s (2x) (o.)Too-1.1)) 1 ) + 1 /selly, (x]
< 2 | voellv=1. v=l.
where the second inequality holds due to our optimistic choice. As the left-hand side is at most 1 as well, follows that
11 (o=))oR=) - (x. I min (1,280-1.1111 1,8 1/ ine
(18)
Gathering the results,
T-1 B S O11+
Σ
|| vill min 1, 1,488
T
$ 23T
( +
1, 111lzo112 min
< 20
0 (1) + 2od +T/(KK>o))
O (dl)))
where the second inequality follows from the fact that B, 2 BB and (Be herr is monotonically increasing t, while the third inequality is due Lemma F.1. Moreover, we have
43r 2 64R2x² log(1/5) 2 32 log(T) 2 1,
32

---

Published as a conference paper at ICLR 2026
for all 8 (0, 1/v] and T 2 2. Therefore min(1, - ammin1 a 2 to pull out By out of min(1,
Next, for term B2.
T-1 Σ 1=1
(B2)²
E (t
T-1 = P(())) Σ
(1,)
T-w-1
T-1
B(EE)) (t,
+ Σ [1(E3)0(T.1)
(=T--
T-w-1
(- (T 11-1--
00
Σ
2C, exp
32
d log 2 (T)
1 - e
(T-(T-u-1))32
2C
-
de log (T)
128C e²
0
(1-e e1-e"22/0
2/2, E (0,1))
d log (T) 1
0
+
3
where the first inequality follows from Lemmas 4.1 and 6.2 on the good event Ey, while the third
inequality holds since 0 < e² 22/32 < 1. Substituting term B, and term Bg back gives
Rr = O (
d2 logg((T)
cl. + dloo(T))
2
F AUXILIARY LEMMAS
Lemma F.1. We have
Σ min { 1, 11
< 2Kdlog (1 + ([+K/(dk)a)).
Proof. Recall the definition of Ve, = RdOI + Ei 1fk; = k] Then,
1 1sk: = k) min {1, 1|::
min 1, ||
A=
K
log det Vi
2
det xdA
k=1
< 2
K log det
1
Σ
Vix
K log det (et
K
km
2K log det
KinD 2. +1
2Kdlog t/ddk>))),
where the first inequality follows from the elliptical potential lemma (Lemma F.2), the second inequality follows from the concavity of log det(-), and the last inequality follows from the determinant--rra inequality (Lemma 10 of Abbasi- Yadkori et al. (2011)).
n
33

---

Published as a conference paper at ICLR 2026
Lemma F.2 (Elliptical potential lemma, Lemma 11 of Abbasi- Yadkori et al. (2011)). For any À and sequence { TRd, define Z AI Ei= xTo.. Then, provided that ||22|12 S I. holds for all t E [T', we have
Σ min (1, || S 2lo
det Zr det AI S 2d (1
TL2
dA
Lemma F.3 (Lemma 12 of Faury et al. (2020)). Let the maximum likelihood estimator of the regu- larized cross-entropy loss as 0,") and define its projection as
0, arg min
Σ 1 (x:[)) -x (x:
V.
where AoI E Iaa. Define confidence and Be as
C. G- -==: 100 s 22
Br --=1 2dlog 1
[+
modd) 1og((18))
SS SVA0
Then, with probability at least 1 5,
V1 1, 0" C
Lemma F.4 (Chebyshev sum inequality). If (a:)i=m is nondecreasing and (b:) is nonincreasing, and ag. 2 0, we have
agb <
Σ as
bi
Proposition F.5 (Proposition 1 Li et al. (2017)). Define V = E/= N.ae, where x; is drawn i.i.d. from some unknown distribution v with support in the unit ball, IR Furthermore, let :: E[r be the second moment matrix, and B and 6 0 be two positive constants. Then, there exists absolute constants C1, C2 >
such that Amin (V)) 2 B with probability at least - 6, as long as
t2 Civd+ C2 C2.log(1/5)
2B
( (2)
Amin (Σ)
Lemma F.6 (Multiplicative Chernoff bound). Suppose X1...., X,, (0.1) dom variables. Let X denote their sum and μ = [[[x]. Then for any 0 - 8 < 1,
independent
P(X S -1-68 (1-8))) S exp (-82p/2)
Also, for any O,
P(X 2 (1+ (1p) I exp (-82p/((2 5))
Lemma F.7 (Matrix Chernoff bound). Let X Rd be random vector with || S and T 2 I for some > 0. Suppose XI...., Xn be i.i.d. sampled vectors and define V, En X.X. Then for any 0 < 1,
-
na
62noo
(Amin (V.) S (1-
S dexp
(1-5)1-3
2
Lemma F.8 (Azuma-Hoeffinn Hoeffddigg inequality). If supermartingale (Yi)ı20 corresponding to filtration 9, satisfies IY, Y-- S 6; for all [t], then for any 2 we have
a²
P(Y: Yo 2 a) < 2exp
!
34

---

Published as a conference paper at ICLR 2026
G DISCUSSIONS
Algorithm design and regret bounds. We clarity the design of CQB-E and its relation to classical explore saare-then-caee then-commit (ETC) strategies. At first glance, CQB-E resembles ETC, which known to be suboptimal in instance-independent regret compared to UCB- or Thompson sampling-bas based approaches, but its structure different.
CQB-s has two phases: phase is pure exploration and phase 2 is mainly exploitation, yet still enforces exploration via uniform exploration steps and UCB-based job-server selection. Unlike classical ETC, we do not assume large gap A between the best and second-bes, arms, and phase is tuned to create a negative drift rather than to shrink uncertainty below A/2. Without a large-gap assumption, pure exploitation in phase 2 is impossible, which motivates the JCBB-ased rule.
Now for the regret, our analysis relies on the bound R S EL= V Elu (l, T)), where
MA,r is the instantancous service-rate gap and (tt, 7)) measures how decision at time t propagates through the queue up to horizon T. The E- e-exploration in phase 2 is specifically designed to enforce opposite monotonic behavior in [| . and (1, 7)), which allows us to minimize this weighted sum and apply Chebyshev's sum inequality, yielding the decaying queue length regret of order O(T-1/4).
If one were to apply a vanilla ETC or UCB algorithm directly to the queueing bandit problem, this monotonicity structure would not hold and the above decomposition would not give decaying queue length regret; for UCB, one instead obtains non-decaying bound of order Olog² T), in Algorithm 2. This explains why our regret rates are neither O(T-1/3) (classical ETC) nor O (standard contextual bandits), but rather 1/4) for CQB-s and Oloog T) for CQB-Opt.
RL with queueing states. We briefly relate our framework to the recent work of Murthy et al. (2024), which studies RL with queueing states in a countable state-space average- setting. While their problem is close in spirit to queueing bandits, their formulation does not directly encompass ours for the following reasons.
First, Murthy et al. (2024) assumes countable state space, whereas contextual queueing bandits naturally lead to an uncountable state space: our framework allows arbitrary context vectors from continuous domain, and each state is represented by the list of remaining job context features. Second, their regret bound contains an approximation term arising from Q-function estimation via neural networks, of the form T where c" upper-bounds the approximation error. If this black- box error is non-negligible, the resulting regret bound can be large and even grow linearly in T. In contrast, our analysis does not rely on a generic function approximator. Third, their regret notion is defined via the cumulative average queue length, whereas our queue length regret is the instanta- neous gap between the queue length under our policy and that under an optimal policy in expectation. It is not clear whether a sublinear bound under their metric would translate into a decaying bound under ours.
Coupling argument in multi-queue setting. This suggests an interesting direction for future work. At a high level, defining coupling argument for the multi-queue setting is straightforward. However, the real difficulty arises when checking whether the good structural properties for the single-queue case would still continue to hold. Lemma 4.1 states that (tt T) E 0,10, i.e. the difference between the queue lengths under two consecutive policy policy-switching queues is always in {-1,0,1) 1}. However, when we allow multiple queues, it is not as straightforward to control (t,,T)) making it difficult to directly extend our analysis to the multi-queue setting.
To illustrate this difficulty, let consider discrete-time time system with two queues and server. In each time slot, the server can serve one job from a chosen nonempty queue, and service is de- terministic. The two coupled systems see identical arrivals. Define the policy "r" as follows: in state (Q1 (t), Q2(t)), if (t) < Q2(t) serve queue 1, if Q2(t) < (t( serve queue 2, and (t) = Q2(t) > 0 serve queue 1. Initially, Q (0) = Qi (0) = 2 and Q; (0) = Q7 (0) = 2. In time slot t 1, n" serves queue 1, while our policy makes mistake and serves queue 2, and there is no job arrival. Thus (1), (,(12((1)))) (1)) = (1,2) and (Q (1)(Q((1)) = (2. For t 2 both systems use x². The arrivals are (2), A2(2)) (0,0) and (Ai(1), A2(() (1,1) for
35

---

Published as a conference paper at ICLR 2026
all 2 3. One checks by induction that for all 2 2 we have (QT (t). (t)) (0,t) and (Qf (t( (t)) (t. 0), hence Qi (t) Qi (t) t.
Define == Q (T)) for i E (1.2). Then for all T 2 2 we get 1/1 () T, so the per-queue difference grows linearly
even though the two systems differ only at a single time slot. In this example, we know that t (1, 7) ()) O, but the individual terms 1/ (1, and (2, 7) are not necessarily bounded. This suggests that we need a more sophisticated analysis for the multi-queue setting. Therefore, it seems difficult to directly carry our single-queu analysis to the multi-queue setting and still obtain meaningful bounds. Handling such multi-queue systems non-trivial but important problem, and we leave it as future work.
Dependence on the slackness parameter: We briefly comment on the role of the slackness pa- rameter our pure-exploration phase. In our analysis is sufficient to know a lower bound on in order to relax the corresponding condition. We also view it as an interesting direction for future work to design algorithms that achieve decaying queue length regret even when no such lower bound is available. Possible approaches include shifting the dependence on to an external parameter (e.g., designing algorithms guaranteed work when T is chosen as a function of 1/s), or developing procedures that adaptively estimate over time.
Preemptive policy class and work conservation. We clarify here which policy class we study and how it relates to the non-work-conserving routing policies in Jali al. (2024); Lin & Kumar (1984). Our model follows the queueing bandit framework of Krishnasamy et al. (2016), where in each time slot single job is selected from the central queue and assigned to server. This is directly analogous to a multi-armed bandit problem, and our contribution is to enrich this framework with contextual information for individual jobs. In this baseline formulation, one can view the system as having single active server per time slot, so our analysis indeed focuses on work-conserving policies that always serve a job whenever the queue is nonempty.
The framework can be extended to multiple servers by selecting, in each time slot, maximum- weight matching between jobs and servers based on their contextual service rates. Since our model permits preemption, idling available server while jobs are waiting does not improve performance, so it suffices to focus on work-conserving policies in this preemptive setting.
By contrast, Jali et al. (2024); Lin & Kumar (1984) study non-preemptive scheduling, where once job is assigned to a server it cannot be interrupted. In that setting, non-work conseriing policies can indeed be beneficial for queue length and latency: a job may prefer to wait in the central queue for better-matched server rather than being routed immediately to a sub-par one. Thus, the main distinc- tion is that our preemptive queueing bandit model justifies focusing on work-conserving policies, whereas the non-pre con-preemptive models in Jali et al. (2024); Lin & Kumar (1984) naturally motivate non-work-conserving routing rules.
H USE OF LARGE LANGUAGE MODELS
This manuscript is reviewed and edited for grammar and clarity using ChatGPT-5.
36


Reviews:
[{"review_id": "jn3phzMV9A", "reviewer": "Reviewer_LS7k", "summary": "The paper studies a contextual queueing bandit problem, where each job is associated with distinct contextual features. In each round, the decision maker selects a job based on its context and assigns it to a server, aiming to maximize the overall job departure rate. A key challenge arises from queue state misalignment, as different policies lead to different queueing states over time. To address this, the authors propose the CQB-$\\epsilon$ algorithm, which alternates between a pure exploration phase and an $\\epsilon$-greedy phase. Using a telescoping-based analysis technique, they establish a regret bound of $\\tilde{O}(T^{-1/4})$. Furthermore, the paper extends the framework to an adversarial context setting, where the CQB-Opt algorithm achieves sublinear regret under the assumption of the existence of at least one good server.", "questions": "What are the insights provided by the regret analysis which show the new challenges comparing to the existing queueing bandits?", "limitations": "", "rating": 4, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "The strengths of the paper are summarized below.\n\n- The paper introduces a novel contextual queueing bandit framework in which arriving jobs have distinct contextual features. The problem is well-motivated by practical applications such as personalized recommendation systems and LLM inference workloads.\n\n-The paper addresses the analytical challenges arising from queue state mismatch, which complicates the regret analysis in queueing-based decision processes.\n\n- The work extends beyond the stochastic setting by developing and theoretically analyzing an algorithm for the adversarial context setting, providing provable sublinear regret guarantees.", "weaknesses": "The weaknesses of the paper are given below. \n\n- The main contribution lies in extending existing queueing bandit frameworks to the heterogeneous contextual setting, but many of the key algorithmic and analytical techniques are adapted from prior work rather than fundamentally novel.\n\n- The algorithmic design of the proposed methods follows standard extensions of existing bandit algorithms. While the regret analysis is mathematically interesting, it does not lead to new insights in algorithmic design for queueing bandits.\n\n- The experimental evaluation is limited to synthetic datasets, which restricts the demonstration of practical effectiveness. Incorporating real-world datasets or additional application scenarios would strengthen the empirical validation.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "yjzw4ndAjE", "reviewer": "Reviewer_4hBS", "summary": "This paper studies contextual queueing bandits, a new context-aware framework for scheduling while simultaneously learning unknown service rates. Individual jobs carry heterogeneous contextual features, based on which the agent chooses a job and matches it with a server to maximize the departure rate. The service/departure rate is governed by a logistic model of the contextual feature with an unknown server-specific parameter. To evaluate the performance of a policy, the authors consider queue length regret, defined as the difference in queue length between the taken policy and the optimal policy. The main challenge in the analysis is that the lists of remaining job features in the queue may differ under the taken policy compared to the optimal policy for a given time step, since these two policies may process jobs in different orders. To handle this challenge, the authors propose the idea of policy-switching queues equipped with a sophisticated coupling argument. This leads to a novel queue length regret decomposition framework, which exhibits the short-term effect of choosing a suboptimal job-server pair and its long-term effect on queue state differences. The authors show that the proposed algorithm, CQB-$\\varepsilon$, achieves a regret upper bound of $O(T^{ −1/4})$. The authors also study the setting of adversarially chosen contexts, for which the proposed second algorithm, CQB-Opt, achieves a regret upper bound of $O(\\log^2 T)$. Lastly, the authors provide experimental results to validate their theoretical findings.", "questions": "Please see the weaknesses above.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The studied problem, contextual queueing bandits, is interesting and novel, which can be applied to various scenarios such as job scheduling and wireless networks. This problem may attract attention in both online learning and queueing theory communities.\n2. The authors design two algorithms, i.e., CQB-$\\varepsilon$, which achieves a regret upper bound of $O(T^{ −1/4})$ for the regular contextual setting, and CQB-Opt for the adversarially chosen context setting, which achieves a regret upper bound of $O(\\log^2 T)$.\n3. The challenges and developed techniques are clearly explained.", "weaknesses": "1. This paper should discuss and compare with the following work, which studies RL with queueing states, in formulation and results. For example, can the formulation of the following work encompass the formulation of this paper?\n\nYashaswini Murthy, Isaac Grosof, Siva Theja Maguluri, and R. Srikant. Performance of NPG in countable state-space average-cost RL. arXiv preprint arXiv:2405.20467 (2024).\n\n2. The proposed algorithm, CQB-$\\varepsilon$, uses the explore-then-exploit (ETE) strategy, which is known to be suboptimal regarding the instance-independent regret bound compared to the UCB and Thompson sampling based strategies. The authors should discuss more on why they use the ETE strategy?\n3. Discussions and comments are lacking following the main theoretical results, e.g., Theorems 5.5 and 6.3. For example, the authors should discuss more on the intuition behind the $O(T^{ −1/4})$ and $O(\\log^2 T)$ regret bounds. Why are the regret bounds neither $O(T^{ −1/3})$ as the traditional ETE regret bound, nor $O(T^{ −1/2})$ as the traditional contextual bandit regret bound?\n4. The current baseline in empirical evaluations is the random sampling policy, which is too simple. It would enhance this paper if the authors can compare with more baselines which are from (or the adaptations of) existing queueing bandit works.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "mF41Bu1IQN", "reviewer": "Reviewer_4uwX", "summary": "This paper introduces a new framework called contextual queueing bandits, which extends classical queueing bandit models by incorporating heterogeneous job contexts and learning unknown service rates governed by a logistic model. The authors use a non-trivial performance metric queue length regret to measure the gap between the learning policy and the optimal policy. To analyze this, the paper develops a policy-switching queue coupling technique that decomposes queue length regret into short-term (instantaneous) and long-term (state-misalignment) effects. Then building on this, two algorithms are proposed: one for the stochastic context setting (i.i.d. job features) and achieving a vanishing regret bound of $O(T^{-1/4})$; another for the adversarial context setting (arbitrary features) an achieving a polylogarithmic regret bound of $O(\\log^2 T)$. The authors also conduct simulation experiments to demonstrate queue length convergence.", "questions": "1. How sensitive are the results to the logistic model assumption? Could the framework handle other contextual service model?\n\n2. Is the coupling argument extendable to multi-queue settings (each queue associated with a server)?\n\n3. Is it possible to remove the dependence on slackness parameter in the pure exploration phase to develop a more adaptive policy?\n\n4. As mentioned in the weakness part, the operational meaning of the vanishing queue length could be clarified.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper extends classical queueing bandits to a contextual setting, where job features directly affect service rates.  The metric of queue length regret is a non-trivial and operationally meaningful objective compared to standard cumulative reward regret.\n\n2. The writing is good. The queue dynamics, logistic service model, and filtration definitions are clearly presented. The results for both stochastic and adversarial contexts are also clearly separated.\n\n3. The policy-switching queue construction and coupling argument are technically elegant and could inspire future queue length regret analysis in other dynamic systems.\n\n4. The paper establishes the first provable decaying queue-length regret bound in the stochastic contextual setting by exploiting Chebyshev’s sum inequality for oppositely ordered sequences. This result is both elegant and novel, and I appreciate this contribution.", "weaknesses": "1. The logistic service rate model needs to be further examined and discussed.\n\n2. Although the coupling-based decomposition is theoretically interesting, the operational meaning of the $O(T^{-1/4})$ scaling could be clarified. For example, what does vanishing queue length difference imply in real scheduling terms?\n\n3.  The length setup for the pure exploration phase requires prior knowledge of the traffic slackness parameter. It would be valuable to discuss whether this dependence can be relaxed.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Mod2u4UE9L", "reviewer": "Reviewer_p2QT", "summary": "This paper introduces a new framework called contextual queueing bandits (CQB). The problem involves a single queue and multiple servers. Jobs arrive with diverse \"contextual features\" (e.g., job size, user profile). The system's agent must decide which job to assign to which server in real-time to maximize the service (departure) rate. The key challenge is that these service rates, which are modeled by a logistic function of the job's context and an unknown server-specific parameter, are not known in advance and must be learned simultaneously. The paper presents an algorithm that achieves an $\\tilde{\\mathcal{O}}(T^{-1/4})$ regret in the stochastic setting, and a $\\mathcal{O}(\\log^{2}T) regret in the adversarial setting.", "questions": "1. Are you considering only work-conserving policies where all the servers are kept busy whenever there is a job in the central queue? For the context-based service rate setting, I believe that a non-work-conserving policy can be better in terms of queue length and latency -- a job might benefit from waiting in the central queue while its matching server is unavailable rather than being routing to a sub-par server. Routing policies of this nature have been considered in https://arxiv.org/pdf/2402.01147 and https://ieeexplore.ieee.org/document/1103637. Could you please cite these works and clarify how the setting of this work differs from those in the previous papers? If I understand correctly, you are assuming that only one server is active at any given time.\n\n2. In Figure 1, what do you mean by 'success' or 'failure'? Once a job is assigned to a server, the time taken to serve it will be determined by the logistic service rate model. So won't that server remain occupied for the next few time slots until the job finishes? The authors seem to be using a one-shot service success/failure model where a job is served with probability $\\sigma(\\mu)$, that is, success, and otherwise it is dropped.\n\nI believe that the practicality and impact of this work can be improved significantly by enhancing the service model to consider multiple servers being used simultaneously for different jobs, and moving away from this sucess/failure type service model.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. New problem setting: The paper considers a formulation of queueing bandits where an incoming job is associated with a context vector $x$, which is matched with a corresponding feature vector $\\theta$ of a server. The service rate of the server is the logistic function of the inner product of $x$ and $\\theta$. The key challenge is that $\\theta$ is unknown and needs to be estimated by balancing exploration of more servers and exploitation of the currently estimated best-matching server of a job in the queue.\n\n2. Analysis Technique: The paper clearly identifies and names the \"queue state misalignment\" phenomenon, arising due to the mismatch between the context vector set in the queue of a candidate policy and that of the optimal policy. The paper presents a new analytical technique that uses queue length regret decomposition based on policy-switching queues and a novel coupling argument. This technique cleverly isolates the short-term impact of a suboptimal choice from its long-term effect on the queue state.\n\n3. Regret Guarantees: The paper provides the first provable decaying queue length regret bound $\\tilde{\\mathcal{O}}(T^{-1/4})$ for this setting. This is a strong result, as it shows the queue length under the learning policy converges to that of the optimal policy. The $\\mathcal{O}(\\log^{2}T)$ regret for the adversarial setting is also a solid finding.", "weaknesses": "1. Simplistic Service Model: I believe that the service model considered by the paper is too simplistic and detached from practice. See my questions below for more details.\n\n2. Regret Lower Bound: The main regret bound for the stochastic setting is $\\tilde{\\mathcal{O}}(T^{-1/4})$. The paper does not provide a lower bound to show if this rate is optimal.\n\n3. Traffic assumptions: Assumption 3.4 is somewhat strong. It requires that for every job context $x$, there exists a server $k^*$ that can process it with a service rate greater than the arrival rate $\\lambda$ by at least $\\epsilon$. This guarantees system stability if the optimal policy is followed. Also, the paper assumes a uniform rate of arrivals, and it is unclear how the policy and regret analysis can be extended to bursty arrivals, which are common in practice.\n\n4. The two-phase policy with a pure exploration phase followed by $\\epsilon$-greedy is not very practical, but it seems to be the tractable algorithm for which the authors can give guarantees.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)