Research map / Bandits and online learning / Contextual bandits and Thompson sampling

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

NeurIPS 2026 · Bandits and online learning › Contextual bandits and Thompson sampling · approach: Oracle-efficient contextual bandits · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Proposes CQB-η-2, a three-phase contextual queueing bandit algorithm that stops random exploration before the horizon, improving queue length regret from Õ(T^{-1/4}) to Õ(T^{-1/2}) and proving a matching Ω(T^{-1/2}) minimax lower bound.

Problem

Queue length regret in contextual queueing bandits with logistic departure rates under stochastic contexts; prior best rate was Õ(T^{-1/4}).

Approach

Random exploration is only needed up to a cutoff round: pure random exploration builds an initial estimator, a mixed eta-random exploration plus UCB phase keeps negative drift while collecting Θ(T) samples, and pure UCB after the cutoff yields small departure-rate gaps, with the regret split at the cutoff.</ruple>

Key results

• Proves queue length regret of Õ(T^{-1/2}) for CQB-η-2 under stochastic contexts, improving prior Õ(T^{-1/4}).
• Proves minimax lower bound Ω(T^{-1/2}) via two hard instances and queue-specific coupling, matching the upper bound in T up to logs.
• Simulations (T=2000, d=10, K=5) show CQB-η-2 achieves lower empirical queue length than baselines such as CQB-ε and ACQB.

Limitations

• Lower bound does not match the upper bound in dependence on d and kappa.
• Simulations are synthetic with practical deviations (scaled confidence radius, delta=1/T, fixed phase points).

Experimental setup

Datasets: synthetic instances

Benchmarks: synthetic contextual queueing simulation

Metrics: queue length regret

Baselines: CQB-epsilon ACQB random policy FIFO+random

Builds on: queueing bandits logistic bandits policy-switching coupling

Closest papers by meaning

• Queueing Matching Bandits with Preference Feedback (NeurIPS 2024 · similarity 0.89)
• Near-Optimal Regret-Queue Length Tradeoff in Online Learning for Two-Sided Markets (NeurIPS 2025 · similarity 0.87)
• Active Context Selection Improves Simple Regret in Contextual Bandits (NeurIPS 2026 · similarity 0.87)
• Reinforcement Learning and Regret Bounds for Admission Control (ICML 2024 · similarity 0.86)
• Contextual Bandits for Unbounded Context Distributions (ICML 2025 · similarity 0.86)
• Local Anti-Concentration Class: Logarithmic Regret for Greedy Linear Contextual Bandit (NeurIPS 2024 · similarity 0.85)