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

arXiv: https://arxiv.org/abs/2606.09668 · HTML: https://mlsanity.com/paper/2606.09668/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 29 of its 48 references that are in the map.
- First posted on arXiv 8 Jun 2026.

## Builds on (most cited first, 29 of 29)

- [RouteLLM: Learning to Route LLMs with Preference Data](https://mlsanity.com/paper/2406.18665/) (2024)
- [Improved Optimistic Algorithms for Logistic Bandits](https://mlsanity.com/paper/2002.07530/) (2020)
- [RouterDC: Query-Based Router by Dual Contrastive Learning for Assembling Large Language Models](https://mlsanity.com/paper/2409.19886/) (2024)
- [Efficient LLM Scheduling by Learning to Rank](https://mlsanity.com/paper/2408.15792/) (2024)
- [MixLLM: Dynamic Routing in Mixed Large Language Models](https://mlsanity.com/paper/2502.18482/) (2025)
- [MNL-Bandit: A Dynamic Learning Approach to Assortment Selection](https://mlsanity.com/paper/1706.03880/) (2017)
- [EmbedLLM: Learning Compact Representations of Large Language Models](https://mlsanity.com/paper/2410.02223/) (2024)
- [Improved Confidence Bounds for the Linear Logistic Model and Applications to Linear Bandits](https://mlsanity.com/paper/2011.11222/) (2020)
- [A Unified Confidence Sequence for Generalized Linear Models, with Applications to Bandits](https://mlsanity.com/paper/2407.13977/) (2024)
- [Learning Unknown Service Rates in Queues: A Multi-Armed Bandit Approach](https://mlsanity.com/paper/1604.06377/) (2016)
- [A Queueing Theoretic Perspective on Low-Latency LLM Inference with Variable Token Length](https://mlsanity.com/paper/2407.05347/) (2024)
- [Generalized Linear Bandits: Almost Optimal Regret with One-Pass Update](https://mlsanity.com/paper/2507.11847/) (2025)
- [Cost-Aware Contrastive Routing for LLMs](https://mlsanity.com/paper/2508.12491/) (2025)
- [Improved Online Confidence Bounds for Multinomial Logistic Bandits](https://mlsanity.com/paper/2502.10020/) (2025)
- [Job Dispatching Policies for Queueing Systems with Unknown Service Rates](https://mlsanity.com/paper/2106.04707/) (2021)
- [Stability and Learning in Strategic Queuing Systems](https://mlsanity.com/paper/2003.07009/) (2020)
- [Decentralized Learning in Online Queuing Systems](https://mlsanity.com/paper/2106.04228/) (2021)
- [Learning While Scheduling in Multi-Server Systems with Unknown Statistics: MaxWeight with Discounted UCB](https://mlsanity.com/paper/2209.01126/) (2022)
- [Efficient Reinforcement Learning for Routing Jobs in Heterogeneous Queueing Systems](https://mlsanity.com/paper/2402.01147/) (2024)
- [LLM Routing with Dueling Feedback](https://mlsanity.com/paper/2510.00841/) (2025)
- [Queueing Matching Bandits with Preference Feedback](https://mlsanity.com/paper/2410.10098/) (2024)
- [Neural Logistic Bandits](https://mlsanity.com/paper/2505.02069/) (2025)
- [Optimal Scheduling Algorithms for LLM Inference: Theory and Practice](https://mlsanity.com/paper/2508.01002/) (2025)
- [Performance of NPG in Countable State-Space Average-Cost RL](https://mlsanity.com/paper/2405.20467/) (2024)
- [Design and Scheduling of an AI-based Queueing System](https://mlsanity.com/paper/2406.06855/) (2024)
- [Queue Length Regret Bounds for Contextual Queueing Bandits](https://mlsanity.com/paper/2601.19300/) (2026)
- [Learning to Route and Schedule LLMs from User Retrials via Contextual Queueing Bandits](https://mlsanity.com/paper/2602.02061/) (2026)
- [Minimizing Queue Length Regret for Arbitrarily Varying Channels](https://mlsanity.com/paper/2501.13551/) (2025)
- [Bandit-Based Rate Adaptation for a Single-Server Queue](https://mlsanity.com/paper/2512.12016/) (2025)

## Built on by (most cited first, 2 of 2)

- [Nonpreemptive Scheduling While Learning Context-Dependent Service Rates](https://mlsanity.com/paper/2609.37660/) (2026)
- [Learning While Scheduling Jobs under Context-Dependent Service Rates: An Anytime Rate-Optimal Algorithm](https://mlsanity.com/paper/2610.06006/) (2026)

## Abstract (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 widetildeO(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 widetildeO(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 widetildeO(T-1/2). We further prove a minimax lower bound of order Omega(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.