A Parameter-Free Best-of-Both-Worlds Policy for Queueing Bandits

Jongyeong Lee; Chansoo Kim

cs.LGNov 2, 2026

A Parameter-Free Best-of-Both-Worlds Policy for Queueing Bandits

Authors: Jongyeong Lee, Chansoo Kim

Organizations: Korea Institute of Science and Technology · University of Science and Technology

Abstract

We study online channel scheduling for a single queue served by $K$ channels under bandit feedback. We propose a simple best-of-both-worlds policy that explores when the queue is empty. During busy periods, it selects the empirical best channel while the prescribed conditions hold and, if any condition is violated, switches to a robust bandit policy to clear the queue. For arbitrary arrivals and services determined by an oblivious adversary, our policy achieves $\tilde{\mathcal{O}}(\sqrt{K L_T})$ worst-case queue length regret with high probability, where $L_T$ is the longest busy-period length. This result improves the previous $T^{3/4}$ dependence and matches the worst-case lower bound up to logarithmic factors. Under bounded i.i.d. stochastic models with a unique best stabilizing channel, we show that the cumulative queue length regret converges to a finite problem-dependent constant, and further establish the logarithmic expected worst-case queue length regret bound.

Figures & tables

Metric	Reference	Assumptions	Regret
$\max\limits_{t\in[T]}\max\limits_{i\in[K]}\quantity(Q_t^\pi- Q_t^i)$ (worst-case regret)	Krishnakumar and Sinha (2025)	oblivious $A_{t}\geq 0$ , $R_{t}\in[0,1]^{K}$	$\tilde{{\mathcal{O}}}(\sqrt{K}T^{3/4})$ (P)
	Algorithm 1 (Theorem 3 )	oblivious $A_{t}\geq 0$ , $R_{t}\in[0,1]^{K}$	$\tilde{{\mathcal{O}}}(\sqrt{KL_{T}})$ (P)
	Algorithm 1 (Corollary 5 )	i.i.d. bounded $A_{t},R_{t}$ , (S), ( 4 )	${\mathcal{O}}(\log(KT)/\Delta_{\min})$ (E)
$\sum_{t}\mathbb{E}[Q_{t}^{\pi}-Q_{t}^{i^{*}}]$ (cumulative regret)	Stahlbuhk et al. (2021)	i.i.d. Bernoulli $A_{t},R_{t}$ , (S)	${\mathcal{O}}(1)$
	Algorithm 1 (Theorem 4 )	i.i.d. bounded $A_{t},R_{t}$ , (S), ( 4 )	${\mathcal{O}}(1)$

Table 1: Comparison of queue length regret guarantees. Here, (S) indicates that the unique best arm is stabilizing, while (E) and (P) indicate guarantees in expectation and with high-probability, respectively. The quantity

L_{T}

denotes the length of the longest busy period and satisfies

L_{T}\leq T

. The queue dynamics considered in Stahlbuhk et al. (2021) , given in ( 8 ), differ from those considered in Krishnakumar and Sinha (2025) and ours, given in ( 1 ).

Panel of Figure 1 — Figure 1: Results in the adversarial regime.

Panel of Figure 2 — Figure 2: Results in the stochastic regime.

Panel of Figure 3 — Figure 3: The trajectories of queue lengths $Q_{t}^{\pi}$ .

Appendix figures & tables2 assets

Supplementary material from the paper’s appendix.

Appendix

Panel of Figure 4 — Figure 4: Results under arrival-first dynamics in ( 1 )

Panel of Figure 5 — Figure 5: Results under service-first dynamics in ( 8 )

Multi-Armed Bandits

Multi-Armed Bandits study how to choose among uncertain actions over time while balancing immediate rewards with learning.

See all 362 papers

Algorithm for Contextual Queueing Bandits with Rate-Optimal Queue Length Regret
Jun 8, 2026Seoungbin Bae, Dabeen LeeExploration-Exploitation Tradeoff Regret Minimization
Department of Industrial & Systems Engineering, KAIST · Department of Mathematical Sciences, Seoul National University
Learning While Scheduling Jobs under Context-Dependent Service Rates: An Anytime Rate-Optimal Algorithm
Oct 5, 2026Seoungbin Bae, Dabeen LeeMulti-Armed Bandits Contextual Bandits
Department of Industrial & Systems Engineering, KAIST · Department of Mathematical Sciences, Seoul National University
Nonpreemptive Scheduling While Learning Context-Dependent Service Rates
Sep 29, 2026Wansoo Choi, Seoungbin Bae, Dabeen LeeQueueing Theory Contextual Bandits
Department of Mathematical Sciences, Seoul National University · Department of Industrial & Systems Engineering, KAIST

Jun 8, 2026J/K move · Enter open · S save

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

Seoungbin Bae, Dabeen Lee

Department of Industrial & Systems Engineering, KAIST · Department of Mathematical Sciences, Seoul National University

Exploration-Exploitation Tradeoff Regret Minimization Contextual Bandits UCB Algorithms Queueing Theory

Open paper AskPDF arXiv

Contextual queueing bandits provide a framework for learning to schedule heterogeneous jobs under unknown context-dependent service rates. Under stochastic contexts, existing algorithms achieve

\widetilde{\mathcal{O}}(T^{-1/4})

queue length regret, defined as the expected difference between the learner's and oracle's queue lengths at horizon

T

. In this paper, we improve this rate to

\widetilde{\mathcal{O}}(T^{-1/2})

. The 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 regret of order

\widetilde{\mathcal{O}}(T^{-1/2})

. We further prove 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 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.

Abstract

Multi-Armed Bandits

Explore similar work

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

Learning While Scheduling Jobs under Context-Dependent Service Rates: An Anytime Rate-Optimal Algorithm

Nonpreemptive Scheduling While Learning Context-Dependent Service Rates