arXiv CSopen access

Algorithm for Contextual Queueing Bandits with Rate-Optimal Queue Length Regret

Algorithm for Contextual Queueing Bandits with Rate-Optimal Queue Length Regret

arXiv:2606.09668v1 [cs.LG] 8 Jun 2026

Seoungbin Bae1 Dabeen Lee2 1 Department of Industrial & Systems Engineering, KAIST 2 Department of Mathematical Sciences, Seoul National University [email protected], [email protected]

Abstract Contextual queueing bandits provide a framework for learning to schedule heterogeneous jobs under unknown context-dependent service rates. Under stochastic contexts, existing algorithms e −1/4 ) queue length regret, defined as the expected difference between the learner’s achieve O(T e −1/2 ). The and oracle’s queue lengths at horizon T . In this paper, we improve this rate to O(T key observation is that random exploration is needed only up to a carefully chosen cutoff round, rather than throughout the entire horizon. We propose CQB-η-2, a three-phase algorithm: (i) pure random exploration to construct an initial estimator, (ii) η-random exploration combined with a UCB rule to continue learning while maintaining negative drift, and (iii) pure UCB after the exploration cutoff. Our proof decomposes the queue length regret at the cutoff round. Before the cutoff, negative drift suppresses queue length differences caused by suboptimal choices. After the cutoff, the first two phases provide sufficient random exploration samples, ensuring that UCB decisions incur small departure-rate gaps. Combining these two bounds yields queue length e −1/2 ). We further prove a minimax lower bound of order Ω(T −1/2 ). The regret of order O(T proof constructs two hard instances that are statistically indistinguishable up to the final service decision, and uses a queue-specific coupling argument to convert the resulting testing error into queue length regret. Together, our upper and lower bounds characterize the minimax dependence on the horizon T up to logarithmic factors.

1

Introduction

Queueing systems play an important role in modern service platforms, including cloud computing (Vilaplana et al., 2014), online service systems (Andrews et al., 2004), call centers (Koole and Mandelbaum, 2002), and multi-LLM services (Mitzenmacher and Shahout, 2025). In these systems, jobs arrive over time, service capacity is limited, and scheduling decisions must be made online. A central challenge is that jobs are heterogeneous and carry contexts, while the corresponding contextdependent service rates are often unknown in advance. This motivates learning-while-scheduling policies that infer unknown service rates from observed departures while keeping the queue stable (Krishnasamy et al., 2016; Kim and Oh, 2024). Queueing bandits formalize learning-while-scheduling when service rates are unknown (Krishnasamy et al., 2016, 2021). In a discrete-time queueing bandit problem, the learner selects which server or job-server pair to use, observes binary departure feedback, and uses this feedback to improve future scheduling decisions. The objective is not only to identify choices with large departure 1

probabilities, but also to control the queue length, because each suboptimal decision can affect future queue states. However, classical queueing bandits typically do not account for job contexts: each action has a fixed unknown departure probability, independent of the features of the jobs currently in the queue. Contextual queueing bandits address this limitation by combining queueing bandits with contextual bandit models. In this framework, the departure probability of a job-server pair is modeled as a logistic function of its feature vector and an unknown parameter (Bae et al., 2026a,b), as in logistic and generalized linear bandits (Filippi et al., 2010; Li et al., 2017; Faury et al., 2020). In this paper, we study contextual queueing bandits under stochastic contexts in a discrete-time system with a single queue and K servers. In each round, the learner observes the contexts of jobs in the queue, selects a job-server pair to process, observes whether the selected job departs, and a new job may arrive. The performance measure is queue length regret, defined as the expected difference between the learner’s and oracle’s queue lengths at horizon T , where the oracle policy knows the true departure probabilities. Unlike standard bandit regret, which accumulates reward losses over time, queue length regret compares the queue states at horizon T . The closest prior works on e −1/4 ) queue length regret under contextual queueing bandits (Bae et al., 2026a,b) establish O(T −1/4 stochastic contexts. This leaves open whether the T rate is intrinsic to contextual queueing bandits or a consequence of the existing algorithmic design and analysis. e −1/2 ). We answer this question by showing that the queue length regret can be improved to O(T Our algorithm, CQB-η-2, is based on the principle that random exploration should be used to learn the unknown service model, but need not be maintained until the end of the horizon. This differs from previous algorithms, which maintain random exploration throughout the entire horizon. We also prove a minimax lower bound of order Ω(T −1/2 ), showing that the dependence on T is tight up to logarithmic factors. Our contributions are summarized as follows: • We propose CQB-η-2, a three-phase contextual queueing bandit algorithm motivated by the idea of cutting off random exploration after sufficient samples are collected. The algorithm first performs pure random exploration to construct an initial estimator, then uses a mixture of η-random exploration and a UCB rule to continue learning while maintaining negative drift, and finally cuts off random exploration and uses only the UCB rule. e −1/2 ) under stochastic • We prove that CQB-η-2 achieves queue length regret of order O(T e −1/4 ) rate. This shows that random exploration until contexts, improving the previous O(T the end of the horizon is not necessary for achieving the T −1/2 order.

• The improvement in queue length regret is due to the clever design of phase transitions. In particular, we stop pure exploration at some cutoff point. First, although the learner may still make suboptimal decisions before the cutoff point due to random exploration, we observe that a negative drift makes the resulting effect on queue length small towards the end of horizon T . After the cutoff point, we would collect Θ(T ) random exploration samples, in which case pure UCB decisions have departure-rate gaps of order T −1/2 . This separation explains why stopping random exploration can improve the queue length regret rate. • We establish a minimax lower bound of order Ω(T −1/2 ). The proof constructs two hard instances that are statistically indistinguishable up to the final service decision and uses a

2

queue-specific coupling argument to convert the resulting testing error into queue length regret. This shows that the dependence on T is tight up to logarithmic factors. • We provide simulations demonstrating that CQB-η-2 achieves lower empirical queue lengths than baseline algorithms.

2

Preliminaries

This section reviews the contextual queueing bandit model, the definition of queue length regret, and the policy-switching queue/coupling framework, following Bae et al. (2026a,b).

2.1

Model

We consider a discrete-time contextual queueing system with a single queue and K servers, where in each round the agent selects a job-server pair to process and a new job may arrive. At the beginning of round t, the queue state Xt is the collection of contexts of all remaining jobs. The queue length is Q(t) = |Xt |. If Xt ̸= ∅, the agent chooses a job-server pair (xt , at ) ∈ Xt × [K]. If Xt = ∅, the agent selects a fixed dummy pair (x0 , a0 ), and the resulting observation is not used for learning. Let A(t) ∈ {0, 1} be the arrival random variable in round t, with P(A(t) = 1) = λ, and let x(t) be the newly arriving job context when A(t) = 1. Let D(t) ∈ {0, 1} be the departure random variable in round t. We will specify its conditional distribution below. Then the queue state and queue length evolve according to Xt+1 = Xt \ {xt : D(t) = 1} ∪ {x(t) : A(t) = 1},

Q(t + 1) = [Q(t) + A(t) − D(t)]+ .

e(t) ), where x e(t) = x(t) if A(t) = 1 and x e(t) = x e otherHere, [z]+ = max{0, z}. We use A(t) = (A(t), x e. We also write D(t) = (D(t), (xt , at )). Let E(t) ∈ {0, 1} be the exwise for a fixed no-arrival symbol x ploration random variable used in round t+1. The filtration is Ft = σ(X1 , A(1), D(1), E(1), . . . , A(t− 1), D(t − 1)). We assume that arrivals are exogenous with conditional arrival probability P(A(t) = 1 | Ft ) = λ. For a filtration G and a random variable Z, we write E[· | G, Z] for conditioning on G ∨ σ(Z). For each job-server pair (x, a), let ϕ(x, a) ∈ Rd be its feature vector, and let θ ∗ ∈ Rd be the unknown parameter. Then, the departure probability follows

D(t) | Ft , xt , at ∼ Bern(µ(⟨ϕ(xt , at ), θ ∗ ⟩)),

2.2

µ(z) = (1 + exp(−z))−1 .

Oracle policy and queue length regret

Let π denote our policy, and let π ∗ be the oracle policy that knows θ ∗ . Given a nonempty queue state Y, π ∗ chooses a job-server pair that maximizes µ(⟨ϕ(x, a), θ ∗ ⟩) over (x, a) ∈ Y × [K]. The queue length regret at horizon T is RT = E[Q(T ) − Q∗ (T )], where Q∗ (T ) is the queue length under π∗.

2.3

Policy-switching queues and coupling

Let π be a given policy. For t ∈ [0, T − 1], let πt be the policy that follows π for rounds 1, . . . , t and then follows π ∗ for rounds t + 1, . . . , T − 1. We construct a coupling of the policy-switching queueing processes as follows. All processes use the same arrival random variables A(i) and the same 3

exploration random variables E(i); these exploration random variables affect only rounds in which the process follows π. Let Qt (i) be the queue length at the beginning of round i in the coupled process governed by πt , and let (xt,i , at,i ) be the job-server pair selected in round i by this process. In each round i, draw a shared random variable Ui ∼ Unif(0, 1). Let Dt (i) = 1 {Ui ≤ µ(⟨ϕ(xt,i , at,i ), θ ∗ ⟩)} and write Dt (i) = (Dt (i), (xt,i , at,i )). For notational convenience, we use Dt (i) = 0 and Dt (i) = 1 as shorthand for the events Dt (i) = 0 and Dt (i) = 1, respectively, together with the selected job-server pair (xt,i , at,i ). This construction gives E[Q(T )] = E[QT −1 (T )] and E[Q∗ (T )] = E[Q0 (T )], while consecutive processes governed by πt and πt−1 have the same queue state at the beginning of round t. Define ψt (T ) = Qt (T ) − Qt−1 (T ) for t ∈ [T − 1]. Then, we can decompose the queue length regret as RT = E[QT −1 (T ) − Q0 (T )] =

TX −1

E[ψt (T )].

t=1

2.4

Assumptions

Throughout the paper, we impose the following standard conditions. Assumption 1. For all x ∈ X and a ∈ [K], ∥ϕ(x, a)∥2 ≤ 1. Also, for a known S > 0, θ ∗ ∈ Θ = {θ ∈ Rd : ∥θ∥2 ≤ S}. Assumption 2. There exist κ, R > 0 such that 1/κ ≤ µ̇(⟨ϕ(x, a), θ⟩) ≤ R for all x ∈ X , a ∈ [K], and θ ∈ Θ. Assumption 3. Newly arriving contexts are i.i.d. from an unknown distribution D. Moreover, for P some σ02 > 0, λmin (Ex∼D [ K1 a∈[K] ϕ(x, a)ϕ(x, a)T ]) ≥ σ02 . Assumption 4. There exists a traffic slackness parameter ϵ > 0 such that for every x ∈ X , there exists a∗ (x) ∈ [K] satisfying µ(⟨ϕ(x, a∗ (x)), θ ∗ ⟩) − λ ≥ ϵ. Assumptions 1 and 2 are standard in logistic bandits (Filippi et al., 2010). Assumption 3 guarantees sufficient feature diversity, which is also standard in finite-armed logistic bandits (Li et al., 2017). Assumption 4 imposes a traffic slackness condition that guarantees negative drift under the oracle policy, and similar conditions can be found in Krishnasamy et al. (2016); Kim and Oh (2024); Bae et al. (2026a).

3

Improved queue length regret via random exploration cutoff

3.1

Motivation and comparison with previous works

e −1/4 ) The closest prior works on contextual queueing bandits, due to Bae et al. (2026a,b), obtain O(T queue length regret. There are two reasons to expect that this rate can be improved. First, since queue √ length regret is evaluated at a terminal horizon rather than accumulated over all rounds, the T cumulative-regret scale in logistic bandits suggests the possibility of a T −1/2 rate for this terminal-horizon performance measure. Second, the algorithms of Bae et al. (2026a,b) both have to maintain random exploration until the end of the horizon. This requirement comes from the proof technique. To elaborate, by the decomposition result in Lemma 6, previous proofs control the departure-rate gap in the first square-root factor by a monotone upper bound, and

4

Algorithm 1 CQB-η-2 input d, T , K, S, κ, λ0 , λ, δ, ϵ, σ0 initialize τ1 , τ2 as in (4), V0 ← λ0 I, θb0 ← 0 1: for t = 1, . . . , T do 2: if t ≤ τ1 then ▷ Phase 1: pure random exploration 3: η←1 4: else if τ1 < t ≤ τ2 then ▷ Phase 2: random exploration with probability η and UCB 5: η ← ϵ/4 6: else ▷ Phase 3: pure UCB 7: η←0 8: end if 9: Sample E(t − 1) ∼ Bern(η) 10: if A(t − 1) = 1 and E(t − 1) = 1 then 11: xt ← x(t−1) , at ∼ Unif([K]) 12: else 13: (xt , at ) ← arg maxx∈Xt , a∈[K] UCBt (x, a) (UCBt (x, a) as in (1)) 14: end if 15: Choose (xt , at ) and observe D(t) 16: Vt ← Vt−1 + ϕ(xt , at )ϕ(xt , at )T 17: Update θbt as in (2), βt as in (3) 18: end for maintaining random exploration until the end of the horizon preserves this monotone control. From an algorithmic perspective, however, after sufficiently accurate estimation is achieved through early random exploration, it is natural to terminate random exploration and use only the UCB rule. Motivated by these two observations, we propose a three-phase algorithm that cuts off random exploration in the final phase.

3.2

Proposed algorithm

Algorithm 1 presents our CQB-η-2 algorithm. We use the term random exploration for the rule that, when a new job arrives (A(t − 1) = 1) and the exploration flag is set (E(t − 1) = 1), selects the newly arrived job and chooses a server uniformly at random. The algorithm has three phases. In Phase 1, it performs random exploration with probability one on arrivals. In Phase 2, it combines random exploration with probability η and a UCB rule, where we set η = ϵ/4. In Phase 3, it cuts off random exploration and uses only the UCB rule. The phase transition points τ1 and τ2 are defined in the regret analysis in Section 3.3. At a high level, τ1 ensures that pure random exploration in Phase 1 provides enough information for the rule that combines random exploration with probability η and UCB in Phase 2 to guarantee a negative drift. The transition point τ2 ensures that the same Phase 2 rule achieves sufficient estimation accuracy, so that the pure UCB rule is sufficient in Phase 3. For any job-server pair (x, a), the UCB is calculated as UCBt (x, a) = µ(⟨ϕ(x, a), θbt−1 ⟩) + βt−1 ∥ϕ(x, a)∥V−1 . t−1

5

(1)

We use the regularized logistic maximum likelihood estimator θbt ← arg min θ∈Θ

t X

[−D(i) log µ(⟨ϕi , θ⟩) − (1 − D(i)) log(1 − µ(⟨ϕi , θ⟩))] +

i=1

λ0 ∥θ∥22 . 2

(2)

and the confidence radius given by q

βt ← κ 0.5d log(1 + t/(κλ0 d)) + 0.5 log(1/δ) + S κλ0 .

(3)

p

We adopt this simple form of the estimator and confidence radius because they are not the main focus of our contribution. Finally, we provide the main theorem of Algorithm 1. Theorem 5. Suppose that Assumptions 1 to 4 hold. Set δ = T −4 . For every T satisfying τ2 − τ1 ≥ T /2, the queue length regret of Algorithm 1 satisfies RT = O

3.3

d + log(T ) κ2 d log(T ) log(T ) log(T ) κ d log(T ) √ √ + + . + λϵ ϵ2 λϵσ04 λϵ3 σ02 λϵ σ0 T ! p

!

Proof of theorem 5

The improved queue length regret comes from how the policy-switching decomposition is used. The decomposition itself is from Bae et al. (2026a), but previous analyses use it with a monotone departure-rate gap bound over the entire horizon. This requires random exploration until round T . We instead split the regret at the exploration cutoff. For rounds before the cutoff, we control the effect at horizon T of a queue length difference by negative drift. For rounds after the cutoff, we control the departure-rate gap by the estimation accuracy obtained from the Θ(T ) random exploration samples collected before the cutoff. We now recall the decomposition and then make this split explicit. For the queue state Xt under π, define (x∗t , a∗t ) ∈ arg maxx∈Xt ,a∈[K] µ(⟨ϕ(x, a), θ ∗ ⟩). Let ϕ∗t = ϕ(x∗t , a∗t ) and ϕt = ϕ(xt , at ). Also define Ft+ = Ft ∨ σ(E(t − 1), A(t)) and ψet (T ) = E[ψt (T ) | Ft+ , Dt (t) = 0, Dt−1 (t) = 1]. The following decomposition corresponds to Lemma 4.2 of Bae et al. (2026a). It separates the effect of the decision in round t into the departure-rate gap in that round and the effect at horizon T of the queue-length difference created in that round. Lemma 6. For each t ∈ [T − 1], we have E[ψt (T )] ≤

r h

E (µ(⟨ϕ∗t , θ ∗ ⟩) − µ(⟨ϕt , θ ∗ ⟩))2

i r h

·

i

E ψet (T ) .

In Lemma 6, the first square-root factor is the departure-rate gap, and the second square-root factor is the effect at horizon T of the queue length difference created in round t. The key point is that these two factors do not have to be controlled by the same type of bound in all rounds. Before the cutoff, we use a naive upper bound on the departure-rate gap, but the second factor is small by negative drift. After the cutoff, we use a naive upper bound on the second factor, but the departure-rate gap is small because the first two phases have already collected Θ(T ) random exploration samples. This is the step that leads to the T −1/2 rate. We also introduce a lemma showing that, under our coupling construction, the two consecutive policy-switching processes governed by πt and πt−1 differ in their policy only at round t, and hence their queue states can differ by at most one in all subsequent rounds. 6

Lemma 7. For each t ∈ [T − 1], we have ψt (T ) ∈ {−1, 0, 1}. Next, define the phase transition points τ1 , τ2 as follows: For sufficiently large constants c1 , c2 > 0, " √ # p  2 c1 d + c2 log(1/δ) 2 128βT2 8 log(1/δ) 4τ1 128 log(T ) τ1 = + 2 2 + , τ2 = T − − − 1. (4) λ λ ϵ ϵ2 σ02 ϵ σ0 For the upper-bound proof, we set δ = T −4 in βt and τ1 . We now bound the two terms in Lemma 6. We first show that the first term, the departure-rate gap term, is upper bounded at order T −1/2 after τ2 , that is, after Phase 2 has collected enough samples of order Θ(T ). Lemma 8. If τ2 − τ1 ≥ T /2, then for every t ∈ [τ2 + 1, T − 1], we have q

s

E[(µ(⟨ϕ∗t , θ ∗ ⟩) − µ(⟨ϕt , θ ∗ ⟩))2 ] ≤

2 −τ1 ) ) + d exp(− where νph2 = exp(− λϵ(τ32

T −4 + νph2 +

128βT2 . λϵσ02 T

λϵ(τ2 −τ1 )σ02 ). 64

Next, we show that the second term in the decomposition in Lemma 6, the effect of a queue length difference created in round t, is upper bounded by an exponentially increasing sequence clipped at one by Lemma 7. Lemma 9. For t > T − 4τ1 /ϵ − 1, we have r h

i

 

q

E[ψet (T )] ≤ 1. For t ≤ T − 4τ1 /ϵ − 1, we have

s

E ψet (T ) ≤ min 1,



3T −4 + 19ϵ−2 exp −



ϵ2 32

 

(T − t − 1 − 4τ1 /ϵ)

.



The number of rounds with positive drift up to round t affects the threshold value 4τ1 /ϵ that separates the two cases in Lemma 9. Notice that this threshold value does not depend on τ2 . This is because our choice of τ1 and the exploration rule in Phase 2 allow the algorithm to collect sufficiently many samples of order Θ(T ) through random exploration while maintaining negative drift during Phase 2. This is the key reason why, unlike previous works, our algorithm can cut off random exploration in the final phase. Now, we are ready to start the proof of Theorem 5. −1 Proof of Theorem 5. Recall the queue length regret decomposition of RT = Tt=1 E[ψt (T )]. We analyze the queue length regret before and after τ2 by writing RT = A1 + A2 , where A1 = Pτ2 PT −1 t=1 E[ψt (T )] and A2 = t=τ2 +1 E[ψt (T )]. This split follows the two different uses of Lemma 6. In A1 , we control the effect of a queue-length difference by negative drift. In A2 , we control the departure-rate gap by the estimation accuracy obtained before the cutoff. For A1 , we use the decomposition in Lemma 6 and consider the departure-rate gap term and the effect of a queue length difference term for t ∈ [1, τ2 ]. For the departure-rate gap term, we use a naive upper bound p of one as E[(µ(⟨ϕ∗t , θ ∗ ⟩) − µ(⟨ϕt , θ ∗ ⟩))2 ] ≤ 1. For the effect of a queue length difference term,

P

T − t − 1 − 4ϵ−1 τ1 ≥ T − τ2 − 1 − 4ϵ−1 τ1 = 128ϵ−2 log(T ) q

for every t ≤ τ2 . Thus Lemma 9 gives A1 ≤

E[ψet (T )] ≤

τ2 p X

√

3 + 19ϵ−2 T −2 . Therefore,

3 + 19ϵ−2 T −2 ≤

t=1

7

p

3 + 19ϵ−2 T −1 .

(5)

Next, consider A2 . We again apply Lemma 6 for t ∈ [τ2 + 1, T − 1]. For the departure-rate gap term, we use Lemma 8 to upper bound it by q

s

E[(µ(⟨ϕ∗t , θ ∗ ⟩) − µ(⟨ϕt , θ ∗ ⟩))2 ] ≤

T −4 + νph2 +

128βT2 . λϵσ02 T

For the effect of a queue length difference term, we use the naive bound from Lemma 9 to upper q bound it by one as A2 ≤

TX −1 t=τ2 +1

E[ψet (T )] ≤ 1. Therefore,

s

128βT2 ·1 T −4 + νph2 + λϵσ02 T

!

=



4τ1 128 log(T ) + ϵ ϵ2

s

T −4 + νph2 +

128βT2 . λϵσ02 T

(6)

For νph2 , by the assumption of Theorem 5, τ2 −τ1 ≥ T /2, so νph2 ≤ exp(−λϵT /64)+d exp(−λϵσ02 T /128). Moreover, the definition of τ2 and τ2 − τ1 ≥ T /2 imply T ≥ 2(1 + 4/ϵ)τ1 . Since τ1 ≥ 8 log(1/δ)/λ and δ = T −4 , we have λϵT /64 ≥ λτ1 /8 ≥ 4 log T . Also, using σ02 ≤ 1 and taking c1 , c2 suf−4 ficiently large, λϵσ02 T√/128 ≥ λσ02 τ1 /16 √ ≥ log d + 4 log T . Hence 2νph2 ≤ 2T . Substituting √ this into a + b and 4τ1 /ϵ + 128 log(T )/ϵ = T − τ2 − 1 ≤ T , gives  (6), using  a√+ b ≤ 128 log(T ) √ 128β√T 4τ1 + O(T −1 ), which completes the proof. A2 ≤ ϵ + ϵ2 λϵσ T 0

4

Queue length regret lower bound analysis

We now prove that the T −1/2 dependence in Theorem 5 is tight in terms of the horizon T . The proof uses a two-instance testing argument. The two instances have the same arrival process and context distribution, but their optimal server sets are complementary. They are statistically difficult to distinguish from the observed history before round T − 1, while the service decision in round T − 1 can still change the terminal queue length. We compare an arbitrary policy with a comparison policy that changes only the server chosen in round T − 1, and then use a testing argument conditioned on the event that a job arrives in round T − 2 to convert the testing error into queue length regret. For an instance ν and a policy π, let Qπ (T ) be the queue length at horizon T under π, and let Q∗ (T ) be the queue length at horizon T under the oracle policy. Write RT (π; ν) = Eν [Qπ (T )−Q∗ (T )]. For fixed d, K, S, σ02 , λ, and ϵ, let C(d, K, S, σ02 , λ, ϵ) be the class of contextual queueing bandit instances satisfying Assumptions 1 to 4 with dimension d, K servers, parameter radius S, feature diversity parameter σ02 , arrival rate λ, and traffic slackness parameter ϵ. Theorem 10. Fix d ≥ 2, K ≥ 2, ϵ ∈ (0, 1), and λ ∈ (0, 1 √ − ϵ). Let 0 < σ02 ≤ 1/d, and let Bλ,ϵ = log((8 − 3(1 − λ − ϵ))/(3(1 − λ − ϵ))). Assume S ≥ Bλ,ϵ d. Then, for every T ≥ 3, inf π

sup

ν∈C(d,K,S,σ02 ,λ,ϵ)

RT (π; ν) ≥

λ(1 − λ − ϵ)e−1/6 √ . 16 T

√ Remark 11. The condition S ≥ Bλ,ϵ d is used to cover the full range λ + ϵ < 1. When λ + ϵ is close to one, the hard instances require service probabilities close to one, which correspond to large logistic logits and therefore require a large parameter radius S.

8

4.1

Proof of theorem 10

We first introduce an explicit hard instance construction. Lemma 12. Under the conditions of Theorem 10, fix T ≥ 3 and set √ γ = 1 − λ − ϵ, ∆T = γ/(8 T ), pT = 1 − γ/2 + ∆T , qT = 1 − γ/2 − ∆T . Let zp = log(pT /(1 − pT )) and zq = log(qT /(1 − qT )). Let the context set be Xlb = {x(σ) = d−1/2 (1, σ2 , . . . , σd )T : σj ∈ {−1, +1}, j = 2, . . . , d}, and let the context distribution be uniform on Xlb . Let M = diag(1, −1, 1, 1, . . . , 1), and define ϕ(x, 1) = x and ϕ(x, a) = Mx for a = 2, . . . , K. Let ej be the j-th unit vector, and define √ √ ∗ ∗ θ+ = 0.5 d((zp + zq )e1 + (zp − zq )e2 ), θ− = 0.5 d((zp + zq )e1 − (zp − zq )e2 ). Let νT+ and νT− be the two instances with arrival rate λ, this context distribution and feature map, ∗ and θ ∗ , respectively. Then ν + , ν − ∈ C(d, K, S, σ 2 , λ, ϵ). and unknown parameters θ+ − 0 T T The next proposition characterizes the optimal server sets and departure-probability properties of the hard instances. √ Proposition 13. For the hard instances in Lemma 12, define, for each x ∈ Xlb , ξ(x) = d x2 ∈ {−1, +1} and (

S+ (x) =

{1}, {2, . . . , K},

ξ(x) = +1, ξ(x) = −1,

S− (x) = [K] \ S+ (x).

For every x ∈ Xlb and s ∈ {+, −}, servers in Ss (x) have departure probability pT under νTs , s and servers outside Ss (x) √ have departure probability qT under νT . Moreover, pT > qT > λ + ϵ, pT − qT = (1 − λ − ϵ)/(4 T ), and u(1 − u) ≥ 3(1 − λ − ϵ)/16 for all u ∈ [qT , pT ]. Next, we state a pathwise comparison lemma for the hard instances. Lemma 14. Fix s ∈ {+, −} and consider the hard instance νTs in Lemma 12. For any deterministic policy, there exists a coupling under which the oracle queue is pathwise no larger than the queue generated by that policy at every round. Finally, let F = {A(T − 2) = 1}. The following proposition is a conditional consequence of the KL chain rule and the Bretagnolle–Huber inequality (Lemma 26). Proposition 15. Fix a deterministic policy π and two instances ν + , ν − with the same arrival process and context distribution. Let HT −1 = σ(A(1), D(1), . . . , A(T − 2), D(T − 2)). Write P+ and P− for probabilities under ν + and ν − , respectively. Suppose that, up to round T − 2, the conditional departure distributions under the two instances are either identical or equal to Bern(p) and Bern(q) in some order. If it holds that (T − 2) max {DKL (Bern(p)∥ Bern(q)), DKL (Bern(q)∥ Bern(p))} ≤ 1/6 , then for every event G ∈ HT −1 , we have P+ (Gc | F ) + P− (G | F ) ≥ 0.5e−1/6 . 9

Now, we are ready to start the proof of Theorem 10. Proof of Theorem 10. Fix a deterministic policy π. Let νT+ , νT− , pT , and qT be as in Lemma 12, and let S+ (·) and S− (·) be as in Proposition 13. For s ∈ {+, −}, write Ps and Es for probability and expectation under νTs . For each s ∈ {+, −}, define a comparison policy π s that agrees with π in rounds 1, . . . , T − 2 and, in round T − 1, selects the same job as π but chooses the smallest server in Ss (x) for that job context x. Let Qs (T ) and Ds (T − 1) be the queue length and departure random variable under π s . By Lemma 14, under νTs , Q∗ (T ) ≤ Qs (T ), and hence RT (π; νTs ) ≥ Es [Qπ (T ) − Qs (T )]. Recall that F = {A(T − 2) = 1}. On F , the queue under π is nonempty at the beginning of round T − 1. Since π and π s have the same queue state at the beginning of round T − 1 and the same arrival in round T − 1, RT (π; νTs ) ≥ Es [1 {F }(Ds (T − 1) − Dπ (T − 1))]. Let (xT −1 , aT −1 ) be the job-server pair selected by π in round T − 1, with an arbitrary fixed value if the queue is empty, and set G = {aT −1 ∈ S+ (xT −1 )}. On F ∩ Gc , π chooses a suboptimal server under νT+ . On F ∩ G, it chooses a suboptimal server under νT− . Since F depends only on the arrival process, P+ (F ) = P− (F ) = λ. By Proposition 13, under νT+ , the conditional expectation of D+ (T − 1) − Dπ (T − 1) is pT − qT on F ∩ Gc and zero on F ∩ G. Under νT− , the same conditional expectation is pT − qT on F ∩ G and zero on F ∩ Gc . Thus we have RT (π; νT− ) ≥ λ(pT − qT ) P− (G | F ).

RT (π; νT+ ) ≥ λ(pT − qT ) P+ (Gc | F ),

(7)

Let HT −1 = σ(A(1), D(1), . . . , A(T − 2), D(T − 2)). Since π is deterministic, G ∈ HT −1 . For each round up to T − 2, if the queue is empty, the departure random variable is deterministically zero under both instances. Otherwise, by Proposition 13, the conditional departure distributions under νT+ and νT− are either identical or equal to Bern(pT ) and Bern(qT ) in some order. By the Bernoulli KL bound (Lemma 25) and Proposition 13, max{DKL (Bern(pT )∥ Bern(qT )), DKL (Bern(qT )∥ Bern(pT ))} ≤

1−λ−ϵ 1 (pT − qT )2 = ≤ . 2(3(1 − λ − ϵ)/16) 6T 6T

Thus the KL condition of Proposition 15 holds. Applying Proposition 15 gives P+ (Gc | F ) + P− (G | F ) ≥ e−1/6 /2. Substituting this bound into (7) gives RT (π; νT+ ) + RT (π; νT− ) ≥ λ(pT − qT )(P+ (Gc | F ) + P− (G | F )) λ(pT − qT )e−1/6 λ(1 − λ − ϵ)e−1/6 √ = , 2 8 T √ Therefore, max{RT (π; νT+ ), RT (π; νT− )} ≥ λ(1 − λ − ϵ)e−1/6 /(16 T ), which completes the proof. For a randomized policy, conditioning on its internal random seed and averaging gives the same sum lower bound, and hence the same maximum lower bound. ≥

10

Figure 1: Queue length regret in synthetic experiments. Left: comparison with baselines. Middle: CQB-η-2 with ϵ ∈ {0.05, 0.1, 0.15}. Right: CQB-η-2 with K ∈ {3, 5, 10}.

5

Experiments

We compare the empirical queue length regret of CQB-η-2 with standard baselines. We use T = 2000, d = 10, K = 5, λ = 0.7, ϵ = 0.1, and κ = 50. The feature vectors and the unknown parameter are sampled coordinate-wise from Unif[−1, 1], and instances that do not satisfy the slackness and κ assumptions are rejected. All curves are averaged over 10 independent runs, and the error bands indicate ±1 standard deviation. For the practical implementation, we use δ = T −1 and scale the confidence radius by 0.1. For CQB-η-2, we set the phase transition points to τ1 = 0.2T and τ2 = 0.3T . For CQB-ε, we set the initial random-exploration length to τ = 0.2T , which plays the√same role as τ1 in CQB-η-2. For ACQB, the random-exploration probability is η(t) = min{1, c1 / t + 1}, and we set c1 = 20. The random policy selects both the job and the server uniformly at random, and FIFO+random selects the oldest job in the queue and a server uniformly at random. Figure 1 shows that CQB-η-2 and CQB-ε have the smallest final regret in the baseline comparison. The middle panel shows that larger slackness improves performance, and the right panel shows that CQB-η-2 remains stable across the tested values of K. All experiments were conducted on a server equipped with an AMD EPYC 9354 32-Core Processor, 251 GiB of RAM, and one NVIDIA RTX A6000 GPU.

6

Conclusion

We studied contextual queueing bandits under stochastic contexts and showed that the queue length e −1/4 ) rate to O(T e −1/2 ). The main algorithmic idea is regret can be improved from the previous O(T to stop random exploration after enough samples have been collected and use a pure UCB rule in the final phase. We also proved an Ω(T −1/2 ) lower bound, showing that the dependence on T is tight up to logarithmic factors. An important direction for future work is to obtain lower bounds that also match the upper bound in the dependence on d and κ.

References Yasin Abbasi-Yadkori, Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. Advances in neural information processing systems, 24, 2011. Marc Abeille, Louis Faury, and Clément Calauzènes. Instance-wise minimax-optimal algorithms

11

for logistic bandits. In International Conference on Artificial Intelligence and Statistics, pages 3691–3699. PMLR, 2021. Shipra Agrawal, Vashist Avadhanula, Vineet Goyal, and Assaf Zeevi. Mnl-bandit: A dynamic learning approach to assortment selection. Operations Research, 67(5):1453–1485, 2019. Zeynep Aksin, Mor Armony, and Vijay Mehrotra. The modern call center: A multi-disciplinary perspective on operations management research. Production and operations management, 16(6): 665–688, 2007. Matthew Andrews, Krishnan Kumaran, Kavita Ramanan, Alexander Stolyar, Rajiv Vijayakumar, and Phil Whiting. Scheduling in a queuing system with asynchronously varying service rates. Probability in the Engineering and Informational Sciences, 18(2):191–217, 2004. Seoungbin Bae and Dabeen Lee. Neural logistic bandits. arXiv preprint arXiv:2505.02069, 2025. √ Seoungbin Bae and Dabeen Lee. Logistic Bandits with Õ( dT ) Regret without Context Diversity Assumptions. arXiv preprint arXiv:2604.22161, 2026. Seoungbin Bae, Garyeong Kang, and Dabeen Lee. Queue length regret bounds for contextual queueing bandits. arXiv preprint arXiv:2601.19300, 2026a. Seoungbin Bae, Junyoung Son, and Dabeen Lee. Learning to route and schedule llms from user retrials via contextual queueing bandits. arXiv preprint arXiv:2602.02061, 2026b. Agrim Bari, Parikshit Hegde, and Gustavo de Veciana. Optimal scheduling algorithms for llm inference: Theory and practice. Proceedings of the ACM on Measurement and Analysis of Computing Systems, 9(3):1–43, 2025. Shuhao Chen, Weisen Jiang, Baijiong Lin, James Kwok, and Yu Zhang. Routerdc: Query-based router by dual contrastive learning for assembling large language models. Advances in Neural Information Processing Systems, 37:66305–66328, 2024. Chao-Kai Chiang, Takashi Ishida, and Masashi Sugiyama. Llm routing with dueling feedback. arXiv preprint arXiv:2510.00841, 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 International Symposium on Theory, Algorithmic Foundations, and Protocol Design for Mobile Networks and Mobile Computing, pages 181–190, 2021. Louis Faury, Marc Abeille, Clément Calauzènes, and Olivier Fercoq. Improved optimistic algorithms for logistic bandits. In International Conference on Machine Learning, pages 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 multi-agent learning in asymmetric queuing systems. In Conference on Learning Theory, pages 4080–4084. PMLR, 2022. 12

Yichao Fu, Siqi Zhu, Runlong Su, Aurick Qiao, Ion Stoica, and Hao Zhang. Efficient llm scheduling by learning to rank. Advances in Neural Information Processing Systems, 37:59006–59029, 2024. Jason Gaitonde and Éva Tardos. Stability and learning in strategic queuing systems. In Proceedings of the 21st ACM Conference on Economics and Computation, pages 319–347, 2020. Wei-Kang Hsu, Jiaming Xu, Xiaojun Lin, and Mark R Bell. Integrated online learning and adaptive control in queueing systems with uncertain payoffs. Operations Research, 70(2):1166–1181, 2022. Jiatai Huang, Leana Golubchik, and Longbo Huang. When lyapunov drift based queue scheduling meets adversarial bandit learning. IEEE/ACM Transactions on Networking, 32(4):3034–3044, 2024. Neharika Jali, Guannan Qu, Weina Wang, and Gauri Joshi. Efficient reinforcement learning for routing jobs in heterogeneous queueing systems. In International Conference on Artificial Intelligence and Statistics, pages 4177–4185. PMLR, 2024. Kwang-Sung Jun, Lalit Jain, Blake Mason, and Houssam Nassif. Improved confidence bounds for the linear logistic model and applications to bandits. In International Conference on Machine Learning, pages 5148–5157. PMLR, 2021. Jung-hun Kim and Min-hwan Oh. Queueing matching bandits with preference feedback. Advances in Neural Information Processing Systems, 37:64649–64702, 2024. Ger Koole and Avishai Mandelbaum. Queueing models of call centers: An introduction. Annals of Operations Research, 113(1):41–59, 2002. G Krishnakumar and Abhishek Sinha. Minimizing queue length regret for arbitrarily varying channels. In 2025 IEEE International Symposium on Information Theory (ISIT), pages 1–6. IEEE, 2025. 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: A 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.06855, 2024a. Joongkyu Lee and Min-hwan Oh. Improved online confidence bounds for multinomial logistic bandits. arXiv preprint arXiv:2502.10020, 2025. Junghyun Lee, Se-Young Yun, and Kwang-Sung Jun. A unified confidence sequence for generalized linear models, with applications to bandits. arXiv preprint arXiv:2407.13977, 2024b. Lihong Li, Yu Lu, and Dengyong Zhou. Provably optimal algorithms for generalized linear contextual bandits. In International Conference on Machine Learning, pages 2071–2080. PMLR, 2017. Qingkai Liang and Eytan Modiano. Minimizing queue length regret under adversarial network models. Proceedings of the ACM on Measurement and Analysis of Computing Systems, 2(1):1–32, 2018. 13

Woei Lin and P Kumar. Optimal control of a queueing system with two heterogeneous servers. IEEE Transactions on Automatic control, 29(8):696–703, 1984. Michael Mitzenmacher and Rana Shahout. Queueing, predictions, and large language models: Challenges and open problems. Stochastic Systems, 15(3):195–219, 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. Min-hwan Oh and Garud Iyengar. Thompson sampling for multinomial logit contextual bandits. Advances in Neural Information Processing Systems, 32, 2019. Isaac Ong, Amjad Almahairi, Vincent Wu, Wei-Lin Chiang, Tianhao Wu, Joseph E Gonzalez, M Waleed Kadous, and Ion Stoica. Routellm: Learning to route llms with preference data. arXiv preprint arXiv:2406.18665, 2024. Flore Sentenac, Etienne Boursier, and Vianney Perchet. Decentralized learning in online queuing systems. Advances in Neural Information Processing Systems, 34:18501–18512, 2021. Reza Shirkavand, Shangqian Gao, Peiran Yu, and Heng Huang. Cost-aware contrastive routing for llms. arXiv preprint arXiv:2508.12491, 2025. Thomas Stahlbuhk, Brooke Shrader, and Eytan Modiano. Learning algorithms for minimizing queue length regret. IEEE Transactions on Information Theory, 67(3):1759–1781, 2021. Jordi Vilaplana, Francesc Solsona, Ivan Teixidó, Jordi Mateo, Francesc Abella, and Josep Rius. A queuing theory model for cloud computing. The Journal of Supercomputing, 69(1):492–507, 2014. Xinyuan Wang, Yanchi Liu, Wei Cheng, Xujiang Zhao, Zhengzhang Chen, Wenchao Yu, Yanjie Fu, and Haifeng Chen. Mixllm: Dynamic routing in mixed large language models. In Proceedings of the 2025 Conference of the Nations of the Americas Chapter of the Association for Computational Linguistics: Human Language Technologies (Volume 1: Long Papers), pages 10912–10922, 2025. Mevan Wijewardena, Kamiar Asgari, and Michael J Neely. Bandit-based rate adaptation for a single-server queue. arXiv preprint arXiv:2512.12016, 2025. Yuqing Yang, Yuedong Xu, and Lei Jiao. A queueing theoretic perspective on low-latency llm inference with variable token length, 2025. URL https://arxiv.org/abs/2407.05347. Zixian Yang, R Srikant, and Lei Ying. Learning while scheduling in multi-server systems with unknown statistics: Maxweight with discounted ucb. In International Conference on Artificial Intelligence and Statistics, pages 4275–4312. PMLR, 2023. Yu-Jie Zhang, Sheng-An Xu, Peng Zhao, and Masashi Sugiyama. Generalized linear bandits: Almost optimal regret with one-pass update. arXiv preprint arXiv:2507.11847, 2025. Richard Zhuang, Tianhao Wu, Zhaojin Wen, Andrew Li, Jiantao Jiao, and Kannan Ramchandran. Embedllm: Learning compact representations of large language models. arXiv preprint arXiv:2410.02223, 2024. 14

A

Related work

Queueing and contextual queueing bandits. Queueing bandits study learning-while-scheduling problems in which unknown service rates must be learned while queue lengths are controlled (Krishnasamy et al., 2016, 2021). This line of work includes queue length regret, dispatching under unknown service rates, decentralized queueing systems, MaxWeight-type learning algorithms, adversarial or nonstationary queueing models, and related queue-aware learning problems (Stahlbuhk et al., 2021; Choudhury et al., 2021; Sentenac et al., 2021; Freund et al., 2022; Yang et al., 2023; Liang and Modiano, 2018; Huang et al., 2024; Krishnakumar and Sinha, 2025; Wijewardena et al., 2025; Gaitonde and Tardos, 2020; Hsu et al., 2022). Classical queueing-control and scheduling works provide stability, drift, and routing tools that underlie these models (Lin and Kumar, 1984; Neely, 2010; Koole and Mandelbaum, 2002; Andrews et al., 2004; Aksin et al., 2007; Vilaplana et al., 2014). Recent queueing and scheduling studies also consider modern service systems, including LLM inference and multi-LLM routing (Mitzenmacher and Shahout, 2025; Yang et al., 2025; Fu et al., 2024; Lee et al., 2024a; Jali et al., 2024; Bari et al., 2025; Murthy et al., 2024). Contextual queueing bandit variants incorporate job-specific features into departure models (Kim and Oh, 2024; e −1/4 ) queue length Bae et al., 2026a,b). The closest prior works Bae et al. (2026a,b) obtain O(T −1/2 e regret under stochastic contexts, whereas we prove a O(T ) upper bound and an Ω(T −1/2 ) lower bound that match in T up to logarithmic factors. Logistic bandits. Our logistic departure model is related to generalized linear bandits, logistic bandits, and multinomial-logit bandits (Filippi et al., 2010; Abbasi-Yadkori et al., 2011; Li et al., 2017; Faury et al., 2020; Jun et al., 2021; Abeille et al., 2021; Lee et al., 2024b; Bae and Lee, 2025; Lee and Oh, 2025; Zhang et al., 2025; Agrawal et al., 2019; Oh and Iyengar, 2019; Bae and Lee, 2026). Related choice-model and routing bandits also study categorical feedback under logistic-type models (Chiang et al., 2025; Wang et al., 2025; Ong et al., 2024; Shirkavand et al., 2025; Chen et al., 2024; Zhuang et al., 2024). Unlike these works, contextual queueing bandits measure queue length regret, and the available job-server pairs depend on the queue state; this requires queue-specific arguments rather than a direct application of standard logistic-bandit regret analyses.

B

Deferred proofs for section 3.3

B.1

Good events

Throughout this appendix, set δ = T −4 in the confidence radius. For t ∈ [T ], define Epred (t) = {∀s ≤ t, (x, a) ∈ X × [K], |µ(⟨ϕ(x, a), θbs−1 ⟩) − µ(⟨ϕ(x, a), θ ∗ ⟩)| ≤ βs−1 ∥ϕ(x, a)∥V−1 }. s−1

Also define Eburn (t) = {∀s ∈ {τ1 + 1, . . . , t}, (x, a) ∈ Xs × [K], βs−1 ∥ϕ(x, a)∥V−1 ≤ ϵ/8}. s−1

Let Edrift (t) = Epred (t) ∩ Eburn (t). We write Epred = Epred (T ), Eburn = Eburn (T ), and Edrift = Edrift (T ). Then Epred (t), Eburn (t), and Edrift (t) are Ft -measurable. If t1 ≤ t2 , then Edrift (t2 ) ⊆ Edrift (t1 ).

15

Let τ2 X

Nph2 =

1 {A(s − 1) = 1, E(s − 1) = 1}

s=τ1 +1

and Sph2 =

τ2 X

1 {A(s − 1) = 1, E(s − 1) = 1}ϕs ϕT s.

s=τ1 +1

Define λϵ(τ2 − τ1 )σ02 λmin (Sph2 ) ≥ . 16

(

Eph2 =

)

Finally, let λϵ(τ2 − τ1 ) νph2 = exp − 32 



λϵ(τ2 − τ1 )σ02 + d exp − . 64 !

Lemma 16. With the confidence radius in (3) and the phase transition points in (4), for sufficiently large absolute constants c1 , c2 > 0, we have 



c P Epred ≤ T −4 ,

c P(Edrift ) ≤ 3T −4 ,





c P Eph2 ≤ νph2 .

Proof. The first bound follows from Lemma 18 with confidence level δ = T −4 . Lemma 20, with the c same confidence level, gives P(Eburn ) ≤ 2T −4 . Therefore, by the union bound, 



c c c P(Edrift ) ≤ P Epred + P(Eburn ) ≤ 3T −4 .

For s ∈ {τ1 + 1, . . . , τ2 }, set Zs = 1 {A(s − 1) = 1, E(s − 1) = 1}. Let Gs be the sigma-field generated before A(s − 1) and E(s − 1) are drawn. Since the Phase 2 random exploration probability is ϵ/4, we have E[Zs | Gs ] = λϵ/4. We apply Lemma 23 with n = τ2 − τ1 and p = λϵ/4. This gives 

P Nph2 <

λϵ(τ2 − τ1 ) 8





≤ exp −

λϵ(τ2 − τ1 ) . 32 

(8)

Conditional on the random exploration times, the corresponding feature vectors are i.i.d. with the same distribution as ϕ(X, J), where X ∼ D and J ∼ Unif([K]). By Assumption 3, P E[ϕ(X, J)ϕ(X, J)T ] = EX∼D [K −1 a∈[K] ϕ(X, a)ϕ(X, a)T ] ⪰ σ02 I. Also, Assumption 1 gives ∥ϕ(X, J)∥2 ≤ 1. On the event Nph2 ≥ λϵ(τ2 − τ1 )/8, there are at least ⌈λϵ(τ2 − τ1 )/8⌉ Phase 2 random exploration samples. We apply Lemma 24 to the first ⌈λϵ(τ2 − τ1 )/8⌉ such samples in chronological order. Adding positive semidefinite matrices cannot decrease the minimum eigenvalue, so λmin (Sph2 ) ≥ λϵ(τ2 − τ1 )σ02 /16 with conditional probability at least 1 − d exp(−λϵ(τ2 − τ1 )σ02 /64). c )≤ν Combining this bound with (8) gives P(Eph2 ph2 . Lemma 17. Fix t > τ1 and suppose that the queue is nonempty at the beginning of round t. Let (x̄t , āt ) be a job-server pair selected by the UCB rule, that is, (x̄t , āt ) ∈ arg max

n

x∈Xt , a∈[K]

o

µ(⟨ϕ(x, a), θbt−1 ⟩) + βt−1 ∥ϕ(x, a)∥V−1 , t−1

On Edrift (t), ϵ µ(⟨ϕ∗t , θ ∗ ⟩) − µ(⟨ϕ̄t , θ ∗ ⟩) ≤ . 4 16

ϕ̄t = ϕ(x̄t , āt ).

Proof. On Epred (t), µ(⟨ϕ∗t , θ ∗ ⟩) ≤ µ(⟨ϕ∗t , θbt−1 ⟩) + βt−1 ∥ϕ∗t ∥V−1

t−1

≤ µ(⟨ϕ̄t , θbt−1 ⟩) + βt−1 ϕ̄t

V−1 t−1

≤ µ(⟨ϕ̄t , θ ∗ ⟩) + 2βt−1 ϕ̄t V−1 . t−1

The second inequality follows from the definition of the UCB rule. On Eburn (t), the last term is at most ϵ/4.

B.2

Proof of lemma 8

Proof of Lemma 8. Let gt = µ(⟨ϕ∗t , θ ∗ ⟩) − µ(⟨ϕt , θ ∗ ⟩). If the queue is empty in round t, we set gt = 0. Hence it suffices to consider the case where the queue is nonempty. On Eph2 , the matrix Vτ2 dominates the Phase 2 random-exploration design matrix, and therefore λϵ(τ2 − τ1 )σ02 . 16

λmin (Vτ2 ) ≥

For every t ≥ τ2 + 1, we have Vt−1 ⪰ Vτ2 , and hence, using ∥ϕt ∥2 ≤ 1, 16 . λϵ(τ2 − τ1 )σ02

∥ϕt ∥2V−1 ≤ t−1

Since τ2 − τ1 ≥ T /2, we have ∥ϕt ∥2V−1 ≤ t−1

32 . λϵσ02 T

(9)

Now consider a Phase 3 round t ∈ {τ2 + 1, . . . , T − 1}. By construction, Phase 3 uses the pure UCB rule. On Epred , for the optimal pair (x∗t , a∗t ) in the current queue and the pair (xt , at ) selected by the algorithm, µ(⟨ϕ∗t , θ ∗ ⟩) ≤ µ(⟨ϕ∗t , θbt−1 ⟩) + βt−1 ∥ϕ∗t ∥V−1

t−1

≤ µ(⟨ϕt , θbt−1 ⟩) + βt−1 ∥ϕt ∥

V−1 t−1

≤ µ(⟨ϕt , θ ∗ ⟩) + 2βt−1 ∥ϕt ∥V−1 . t−1

The second inequality follows from the definition of the UCB rule. Therefore, on Epred ∩ Eph2 , gt ≤ 2βt−1 ∥ϕt ∥V−1 ≤ 2βT ∥ϕt ∥V−1 . t−1

Using (9), on Epred ∩ Eph2 , gt2 ≤

128βT2 . λϵσ02 T 17

t−1

Finally, since 0 ≤ gt ≤ 1, Lemma 16 gives h

i

h

i







c c E gt2 ≤ E gt2 1 {Epred ∩ Eph2 } + P Epred + P Eph2

≤



128βT2 + T −4 + νph2 . λϵσ02 T

Taking square roots gives the desired result.

B.3

Proof of lemma 9

Proof of Lemma 9. We first record the negative drift property after Phase 1 for the coupled process governed by πT −1 . This process has the same marginal law as the original queue governed by the learning policy. Fix t > τ1 and suppose that QT −1 (t) > 0. Let ηt be an upper bound on the conditional probability that the random exploration rule is used in round t; in Phase 2, ηt = ϵ/4, and in Phase 3, ηt = 0. Let (x∗t , a∗t ) be an optimal job-server pair in the queue of this process at the beginning of round t. By Assumption 4, µ(⟨ϕ∗t , θ ∗ ⟩) ≥ λ + ϵ. If the algorithm uses random exploration, the departure-rate loss relative to the optimal pair is at most one. If it uses the UCB rule, the loss is at most ϵ/4 on Edrift (t) by Lemma 17. Therefore, on Edrift (t) ∩ {QT −1 (t) > 0}, ϵ E[DT −1 (t) | Ft ] ≥ µ(⟨ϕ∗t , θ ∗ ⟩) − ηt − 4 ϵ ϵ ϵ ≥λ+ϵ− − =λ+ . 4 4 2 Hence, whenever QT −1 (t) > 0 and t > τ1 , on Edrift (t), ϵ E[A(t) − DT −1 (t) | Ft ] ≤ − . 2

(10)

We use this drift condition to obtain a tail bound for QT −1 (t). Let ζ = ϵ/2, ρ = exp(−ϵ2 /8), and b = exp(ζ). Define the deterministic bad-round count B(t) = min{t, τ1 }. Thus rounds 1, . . . , τ1 are treated as bad rounds, and all later rounds have negative drift on Edrift (t). Define V (t) =

b ρ

 

−B(t−1)

exp(ζQT −1 (t)).

We claim that, for every t ∈ [T − 1], E[1 {Edrift (t + 1)}V (t + 1)] ≤ ρE[1 {Edrift (t)}V (t)] + 1.

(11)

To prove this, first consider a round t > τ1 . If QT −1 (t) > 0, then, on Edrift (t), (10) and Lemma 22 give 



E[exp(ζ(A(t) − DT −1 (t))) | Ft ] ≤ exp −ζϵ/2 + ζ 2 /2 = exp(−ϵ2 /8) = ρ. If QT −1 (t) = 0, then the actual departure from the queue is zero and QT −1 (t + 1) = A(t), so E[exp(ζQT −1 (t + 1)) | Ft ] ≤ exp(ζ) ≤ 1 + ρ, 18

where the last inequality holds for ϵ ∈ (0, 1). Combining the two cases, for every t > τ1 , on Edrift (t), E[exp(ζQT −1 (t + 1)) | Ft ] ≤ 1 + ρ exp(ζQT −1 (t)).

(12)

For t ≤ τ1 , we use the crude bound E[exp(ζQT −1 (t + 1)) | Ft ] ≤ 1 + b exp(ζQT −1 (t)).

(13)

Since Edrift (t + 1) ⊆ Edrift (t) and Edrift (t) ∈ Ft , (12) and (13) and the definition of V (t) give (11). Solving the recursion and using QT −1 (1) = 0, E[1 {Edrift (t)}V (t)] ≤ 1 +

1 ≤ 17ϵ−2 , 1−ρ

(14)

where we used 1 − e−x ≥ x/2 for x ∈ [0, 1]. Let a = 1 + ϵ/4. Since a = ζ −1 log(b/ρ), Edrift ⊆ Edrift (t), and B(t − 1) ≤ τ1 , Markov’s inequality and (14) imply that, for every t and every y ≥ 0, P(QT −1 (t) ≥ aτ1 + y, Edrift ) ≤ 17ϵ−2 exp(−ζy).

(15)

We next bound the probability that a one-job discrepancy created in a fixed round i survives until round T . Let n = T − i − 1. If n < 4τ1 /ϵ, then the trivial bound ψei (T ) ≤ 1 gives the first part of the lemma. Thus assume n ≥ 4τ1 /ϵ. Condition on Fi+ and on the disagreement event Di (i) = 0, Di−1 (i) = 1. Let Q̄i (i + 1) be the queue length of the process governed by πi at the beginning of round i + 1 under this disagreement event. After round i, the process governed by πi follows the oracle policy. Let H be the first time after round i at which this process hits queue length zero. By Lemma 21, under the disagreement event, ψi (T ) ∈ {0, 1}, and ψi (T ) = 1 implies H > T . Therefore, 



ψei (T ) ≤ P H > T | Fi+ , Di (i) = 0, Di−1 (i) = 1 . We now bound this survival probability. Suppose that Q̄i (i+1) = q. For rounds t = i+1, . . . , T −1, as long as the queue is nonempty, the oracle policy has departure probability at least λ + ϵ. Thus, for such rounds, E[A(t) − Di (t) | Gt ] ≤ −ϵ, where Gt is the history of the process governed by πi up to the beginning of round t. By Lemma 22 with ζ = ϵ/2, 



E[exp(ζ(A(t) − Di (t))) | Gt ] ≤ exp −ζϵ + ζ 2 /2 ≤ exp(−ϵ2 /4). We apply this bound only before the hitting time. In the next display, all probabilities and expectations are conditional on Q̄i (i+1) = q, Fi+ , and the disagreement event Di (i) = 0, Di−1 (i) = 1.

19

For m ∈ {i + 1, . . . , T }, let Hm = {H > m}. For m ∈ {i + 1, . . . , T − 1}, on Hm , the queue is nonempty at the beginning of round m, and hence the following one-step stopped inequality holds: 



m X

E1 {Hm+1 } expζ





(A(s) − Di (s)) | Gm 

s=i+1



≤ 1 {Hm } expζ



m−1 X

(A(s) − Di (s))E[exp(ζ(A(m) − Di (m))) | Gm ]

s=i+1



≤ exp(−ϵ2 /4)1 {Hm } expζ

m−1 X



(A(s) − Di (s)).

s=i+1

Iterating the last display gives 





TX −1

!

ϵ2 E1 {HT } expζ (A(s) − Di (s)) ≤ exp − n . 4 s=i+1 On HT , we have TX −1

q+

(A(s) − Di (s)) ≥ 1.

s=i+1

Therefore, 

P



H > T | Q̄i (i + 1) = q, Fi+ , Di (i) = 0, Di−1 (i) = 1

(

ϵ2 ≤ min 1, exp ζ(q − 1) − n 4

!)

.

(16)

This stopped estimate handles the empty-queue case: no negative drift is asserted after the queue becomes empty. It remains to average (16) over Fi+ . Set ω=

4τ1 , ϵ

ϵ yi = (n − ω). 4

Since n ≥ ω, we have yi ≥ 0. Also, under the disagreement event, Q̄i (i + 1) ≤ QT −1 (i) + 1. Hence (15) gives 



P Q̄i (i + 1) ≥ aτ1 + 1 + yi , Edrift ≤ 17ϵ−2 exp(−ζyi ).

(17)

On the complementary event Q̄i (i + 1) < aτ1 + 1 + yi , (16) yields 

P



H > T | Fi+ , Di (i) = 0, Di−1 (i) = 1

ϵ2 ≤ exp ζ(aτ1 + yi ) − n 4

!

!

ϵ2 ≤ exp − (n − ω) . 32 The last inequality follows from ζ = ϵ/2, a = 1 + ϵ/4, yi = ϵ(n − ω)/4, ω = 4τ1 /ϵ, and ϵ ∈ (0, 1). 20

Combining the bound on the event Q̄i (i + 1) < aτ1 + 1 + yi with (17) and Lemma 16, h

i

E ψei (T )

!

c ≤ P(Edrift ) + exp

ϵ2 − (n − ω) + 17ϵ−2 exp(−ζyi ) 32

ϵ2 4τ1 ≤ 3T −4 + 19ϵ−2 exp − T −i−1− 32 ϵ 

!

,

where we used ζyi = ϵ2 (n − ω)/8 and ϵ−2 ≥ 1. Taking square roots, using the trivial bound ψei (T ) ≤ 1, and relabeling i as t complete the proof.

C

Deferred proofs for section 4

C.1

Proof of lemma 12

√ Proof of Lemma 12. Let γ = 1 − λ − ϵ, ∆T = γ/(8 T ), pT = 1 − γ/2 + ∆T , and qT = 1 − γ/2 − ∆T . Since T ≥ 3, we have pT ≤ 1 − 3γ/8 < 1, qT ≥ 1 − 5γ/8 ≥ 3/8, and qT − (λ + ϵ) ≥ 3γ/8 > 0. Thus zp and zq are well-defined, and pT > λ + ϵ. It remains to verify that νT+ , νT− ∈ C(d, K, S, σ02 , λ, ϵ). Since ∥x∥2 = 1 and M is orthogonal, ∥ϕ(x, a)∥2 = 1. Also, if X is uniform on Xlb , then E[XX T ] = d−1 I and 



1 X 1 E ϕ(X, a)ϕ(X, a)T  = I. K a∈[K] d Thus Assumption 3 holds for every σ02 ≤ 1/d. For every x ∈ Xlb and each sign s ∈ {+, −}, the logits ⟨ϕ(x, a), θs∗ ⟩ over a ∈ [K] take values in {zp , zq } and include zp . Therefore maxa∈[K] µ(⟨ϕ(x, a), θs∗ ⟩) = pT > λ + ϵ, and the traffic slackness condition holds. For the parameter radius, let Lγ = log((8 − 3γ)/(3γ)). The bounds qT ≥ 3/8 and pT ≤ 1 − 3γ/8 imply |zp |, |zq | ≤ Lγ . Therefore s ∗ θ± 2 =

 √ √ d 2 zp + zq2 ≤ Lγ d = Bλ,ϵ d ≤ S. 2

Finally, Assumption 2 holds for finite constants because all logits over Θ lie in [−S, S] and µ̇ is positive and continuous on this interval. Hence νT+ , νT− ∈ C(d, K, S, σ02 , λ, ϵ).

C.2

Proof of proposition 13

Proof of Proposition 13. Let γ = 1 − λ − ϵ. For x ∈ Xlb , let ξ(x) = then ∗ ⟨ϕ(x, 1), θ+ ⟩ = zp ,

∗ ⟨ϕ(x, a), θ+ ⟩ = zq

√

d x2 ∈ {−1, +1}. If ξ(x) = +1,

for all a ∈ {2, . . . , K}.

If ξ(x) = −1, then these two logits are reversed. Thus, under νT+ , servers in S+ (x) have departure probability pT , and servers outside S+ (x) have departure probability qT . The same calculation with ∗ gives the corresponding statement under ν − . θ− T

21

It remains to verify the numerical bounds. Since T ≥ 3, we have pT ≤ 1 − 3γ/8 √ < 1, qT ≥ 1 − 5γ/8 ≥ 3/8, and qT − (λ + ϵ) ≥ 3γ/8 > 0. Thus pT > qT > λ + ϵ and pT − qT = γ/(4 T ). Also, pT ≥ 1/2, 1 − pT ≥ 3γ/8, qT ≥ 3/8, and 1 − qT ≥ γ/2. Thus pT (1 − pT ) ≥

3γ , 16

qT (1 − qT ) ≥

3γ . 16

For every u ∈ [qT , pT ], the concavity of u(1 − u) gives u(1 − u) ≥ min{pT (1 − pT ), qT (1 − qT )} ≥

3γ . 16

Substituting γ = 1 − λ − ϵ completes the proof.

C.3

Proof of lemma 14

Proof of Lemma 14. Fix s ∈ {+, −} and a deterministic policy ρ. Let Q∗ (t) be the oracle queue under νTs , and let Qρ (t) be the queue generated by ρ under the same instance. Couple the two processes by using the same arrival random variables and the same uniform random variables to generate departures. We prove the claim by induction. At t = 1, both queues are empty. Assume Q∗ (t) ≤ Qρ (t). If Q∗ (t) = 0, then Q∗ (t + 1) = A(t), while Dρ (t) ≤ Qρ (t) implies Qρ (t + 1) = Qρ (t) + A(t) − Dρ (t) ≥ A(t). If Q∗ (t) > 0, then Qρ (t) > 0 as well. By Proposition 13, the oracle can choose a job-server pair with departure probability pT , and every feasible job-server pair has departure probability at most pT . Let rtρ ≤ pT be the departure probability of the job-server pair selected by ρ. Using the same uniform random variable Ut for the departures, D∗ (t) = 1 {Ut ≤ pT } and Dρ (t) = 1 {Ut ≤ rtρ }, so D∗ (t) ≥ Dρ (t). Thus Q∗ (t + 1) = Q∗ (t) + A(t) − D∗ (t) ≤ Qρ (t) + A(t) − Dρ (t) = Qρ (t + 1).

C.4

Proof of proposition 15

Proof of Proposition 15. Let P+F and P−F be the conditional laws on HT −1 under ν + and ν − given F . Since the initial queue is empty, the observations generating HT −1 determine the queue state before each round up to T −1. For a deterministic policy, the selected job-server pair is therefore determined by the past history. The two instances have the same arrival process and context distribution, and conditioning on F = {A(T − 2) = 1} fixes only the shared arrival random variable A(T − 2). Thus, in each round, only the conditional distribution of the departure random variable can differ between the two instances. If the queue is empty, the departure random variable is deterministically zero under both instances. Otherwise, by assumption, the two conditional distributions of the departure random variable are either identical or are Bern(p) and Bern(q) in some order. Therefore, the KL chain rule bounds DKL (P+F ∥P−F ) by the sum of the one-round conditional KL divergences. The arrival and context terms contribute zero, and each departure term is at most the larger KL divergence between Bern(p) and Bern(q). Thus, 



DKL P+F ∥P−F ≤ (T − 2) max{DKL (Bern(p)∥ Bern(q)), DKL (Bern(q)∥ Bern(p))}. 22

By assumption, the right-hand side is at most 1/6. By the Bretagnolle–Huber inequality (Lemma 26) applied to P+F , P−F , and G, 1 P+ (Gc | F ) + P− (G | F ) = P+F (Gc ) + P−F (G) ≥ e−1/6 . 2

D

Auxiliary lemmas

This section collects auxiliary results used in the appendix. The following prediction-error bound is Lemma 28 of Bae and Lee (2026), stated in the notation of this paper. Lemma 18. With the confidence radius defined by (3), it holds with probability at least 1 − δ that µ(⟨ϕ(x, a), θbs−1 ⟩) − µ(⟨ϕ(x, a), θ ∗ ⟩) ≤ βs−1 ∥ϕ(x, a)∥V−1

s−1

for all s ∈ [T ] and all (x, a) ∈ X × [K]. The following design-matrix lower bound is Proposition 1 of Li et al. (2017). Lemma 19. Let Y1 , . . . , Yn be i.i.d. random vectors drawn from a distribution supported on the unit ball in Rd . Let Σ = E[Y1 Y1T ]. For any B > 0 and δ > 0, there exist absolute constants C1 , C2 > 0 such that λmin

n X

!

Ys YsT

≥B

s=1

with probability at least 1 − δ, provided that ! √ p C1 d + C2 log(1/δ) 2 2B n≥ + . λmin (Σ) λmin (Σ) The following burn-in uncertainty bound is adapted from Lemma 5.2 of Bae et al. (2026a). Lemma 20. Suppose that τ1 is chosen according to (4) with sufficiently large absolute constants c1 , c2 > 0. Then, with probability at least 1 − 2δ, βt−1 ∥ϕ(x, a)∥V−1 ≤ ϵ/8 t−1

for all t ∈ {τ1 + 1, . . . , T } and all (x, a) ∈ Xt × [K]. 1 Proof of Lemma 20. Let B1 = 64βT2 /ϵ2 , and let Nph1 = τs=1 1 {A(s − 1) = 1} be the number of Phase 1 random exploration samples. During Phase 1, every arrival is used for random exploration, and the server is selected uniformly at random. Conditional on the random exploration times, the corresponding feature vectors are i.i.d. with the same distribution as ϕ(X, J), where X ∼ D and J ∼ Unif([K]). By Assumption 3, E[ϕ(X, J)ϕ(X, J)T ] ⪰ σ02 I. Set ! √ p C1 d + C2 log(1/δ) 2 2B1 nph1 = + 2 . σ02 σ0

P

23

By taking the absolute constants c1 , c2 in the definition of τ1 sufficiently large, λτ1 ≥ nph1 , 2



exp −

λτ1 8



≤ δ.

For each s ∈ [τ1 ], let Gs be the sigma-field generated by the history before A(s − 1) is drawn. Then 1 {A(s − 1) = 1} is {0, 1}-valued and has conditional mean λ given Gs . We apply Lemma 23 with n = τ1 and p = λ to get λτ1 P(Nph1 < nph1 ) ≤ P Nph1 < 2 



≤ δ.

On the event Nph1 ≥ nph1 , we apply Lemma 19 to the first ⌈nph1 ⌉ Phase 1 random exploration samples in chronological order, with n = ⌈nph1 ⌉, B = B1 , and λmin (Σ) = σ02 . Adding positive semidefinite matrices cannot decrease the minimum eigenvalue, so λmin (Sph1 ) ≥ B1 with conditional probability at least 1 − δ, where Sph1 =

τ1 X

1 {A(s − 1) = 1}ϕs ϕT s

s=1

is the design matrix formed by the Phase 1 random exploration samples. By the union bound, this design lower bound holds with probability at least 1 − 2δ. On this event, for every t ∈ {τ1 + 1, . . . , T }, Vt−1 ⪰ Vτ1 ⪰ Sph1 . Using ∥ϕ(x, a)∥2 ≤ 1 and βt−1 ≤ βT , ϵ βT = βt−1 ∥ϕ(x, a)∥V−1 ≤ √ t−1 8 B1 for all (x, a) ∈ Xt × [K]. The following coupling property follows from Lemmas B.1 and C.5 of Bae et al. (2026a) and Lemma E.1 of Bae et al. (2026b), stated in the notation of this paper. Lemma 21. Consider the coupled consecutive policy-switching queues governed by πt and πt−1 . If Dt (t) = Dt−1 (t), then ψt (T ) ∈ {−1, 0}. If Dt (t) = 0 and Dt−1 (t) = 1, then ψt (T ) ∈ {0, 1}. Moreover, under the event Dt (t) = 0 and Dt−1 (t) = 1, if the process governed by πt hits queue length zero in a round after t and no later than T , then ψt (T ) = 0. Equivalently, ψt (T ) = 1 implies that this process does not hit queue length zero before round T . We also use the following standard inequalities. Lemma 22 (Conditional Hoeffding lemma). Let X be a random variable satisfying X ∈ [−1, 1] almost surely. If E[X | G] ≤ −a for some a ≥ 0, then for every ζ ≥ 0, !

ζ2 E[exp(ζX) | G] ≤ exp −ζa + . 2

24

Lemma 23 (Multiplicative Chernoff bound). Let Z1 , . . . , Zn be {0, 1}-valued random variables adapted to a filtration {Gi }ni=0 . If E[Zi | Gi−1 ] ≥ p for every i, then n X

pn P Zi < 2 i=1

!

pn . ≤ exp − 8 



Lemma 24 (Matrix Chernoff bound). Let Y1 , . . . , Yn ∈ Rd be i.i.d. random vectors satisfying ∥Yi ∥2 ≤ 1 almost surely and E[Yi YiT ] ⪰ σ02 I. Then P λmin

n X i=1

!

Yi YiT

nσ02 < 2

!

!

nσ 2 ≤ d exp − 0 . 8

Lemma 25. Let u, v ∈ (0, 1). If w(1 − w) ≥ m for every w ∈ [min{u, v}, max{u, v}], then DKL (Bern(u)∥ Bern(v)) ≤

(u − v)2 . 2m

Proof of Lemma 25. Fix v ∈ (0, 1) and define f (r) = DKL (Bern(r)∥ Bern(v)) for r ∈ (0, 1). Then f (v) = 0, f ′ (v) = 0, and f ′′ (r) = 1/(r(1 − r)). By Taylor’s theorem, for some point r̄ between u and v, DKL (Bern(u)∥ Bern(v)) = f (u) =

(u − v)2 . 2r̄(1 − r̄)

The point r̄ lies between u and v. Thus r̄(1 − r̄) ≥ m by assumption, and the desired bound follows. Lemma 26 (Bretagnolle–Huber inequality). For any probability measures P, Q and event G, P (Gc ) + Q(G) ≥

1 exp{−DKL (P ∥Q)}. 2

25