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

• URL: http://arxiv.org/abs/2606.09668v1
• Date: Mon, 08 Jun 2026 15:51:25 GMT
• Title: Algorithm for Contextual Queueing Bandits with Rate-Optimal Queue Length Regret
• Abstract summary: Queue length regret is defined as the expected difference between the learner's and oracle's queue lengths at horizon $T$.<n>In this paper, we improve this rate to $widetildemathcalO(T-1/2)$.
• Score: 1.0098114696565863
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• Constrained Online Learning with Noisy Constraint Values [55.29259818039367]
  Under common feasibility, our LEDGER algorithm attains $O(sqrt T)$ expected regret and $O(sqrtTlog(eT))$ expected budget violation.<n>Neither a Slater condition, independence between feedback channels, nor an absolute constraint-value bound is needed.
  arXiv  Detail & Related papers  (2026-09-07T01:38:41Z)
• Asymptotically Optimal Regret for Reinforcement Learning without Horizon Dependence [54.59847568544922]
  We study horizon-free regret for finite-horizon time-homogeneous Markov decision processes with $A$ states, $A$ actions, horizon $H$, and per-trajectory total reward bounded by $1$.<n>We prove a regret upper bound [tilde O(sqrtSAK+S8A3)] with failure probability $$, where $K$ is the number of episodes and $tilde O(sqrtSAK+S3K)$ hides $mathsfpoly
  arXiv  Detail & Related papers  (2026-07-22T07:42:19Z)
• Price of Fairness in Bandits: A Tight Minimax Characterization [9.360852329235477]
  In bandit problems, standard regret-minimizing algorithms treat exploration as an amortized cost, exposing early participants to unfair ex-ante losses.<n>Recent work addresses this by evaluating the sequence of per-round expected rewards through the generalized $p$-mean.<n>We prove an algorithm-independent lower bound $(sqrtkmax(1,q)/T)$; for $q>1$, this shows that the penalty $kq/2$ is information-theoretically unavoidable.
  arXiv  Detail & Related papers  (2026-07-15T02:58:57Z)
• Queue Length Regret Bounds for Contextual Queueing Bandits [0.8984888893275712]
  We introduce contextual queueing bandits, a new context-aware framework for scheduling while simultaneously learning unknown service rates.<n>We show that our algorithm, CQB-$varepsilon$, achieves a regret upper bound of $widetildemathcalO(T-1/4)$.<n>We also consider the setting of adversarially chosen contexts, for which our second algorithm, CQB-Opt, achieves a regret upper bound of $mathcalO(log2 T)$.
  arXiv  Detail & Related papers  (2026-01-27T07:40:23Z)
• Tail Distribution of Regret in Optimistic Reinforcement Learning [3.9962751777898955]
  We characterize the tail distribution of the cumulative regret $R_K$ over $K$ episodes, rather than only its expectation or a single high-probability quantile.<n>A proposed algorithm depends on a tuning parameter $$, which balances the expected regret and the range over which the regret exhibits a sub-Gaussian tail.
  arXiv  Detail & Related papers  (2025-11-23T02:23:09Z)
• Lateral Tree-of-Thoughts Surpasses ToT by Incorporating Logically-Consistent, Low-Utility Candidates [0.0]
  Lateral Tree-of-Thoughts (LToT) is a drop-in controller that separates utility from logical consistency and treats low-utility but consistent candidates as assets rather than waste.<n>LToT explores laterals via Lateral Racing with Short-Circuit (LR--SC), a capped successive-halving race that spreads tiny probes across a very wide lateral set.
  arXiv  Detail & Related papers  (2025-10-01T22:23:58Z)
• From Continual Learning to SGD and Back: Better Rates for Continual Linear Models [50.11453013647086]
  We analyze the forgetting, i.e., loss on previously seen tasks, after $k$ iterations.<n>We develop novel last-iterate upper bounds in the realizable least squares setup.<n>We prove for the first time that randomization alone, with no task repetition, can prevent catastrophic in sufficiently long task sequences.
  arXiv  Detail & Related papers  (2025-04-06T18:39:45Z)
• p-Mean Regret for Stochastic Bandits [52.828710025519996]
  We introduce a simple, unified UCB-based algorithm that achieves novel $p$-mean regret bounds.<n>Our framework encompasses both average cumulative regret and Nash regret as special cases.
  arXiv  Detail & Related papers  (2024-12-14T08:38:26Z)
• Contextual Bandits for Unbounded Context Distributions [20.923880900127774]
  Nonparametric contextual bandit is an important model of sequential decision making problems.<n>We propose two nearest neighbor methods combined with UCB exploration.<n>Our analysis shows that this method achieves minimax optimal regret under a weak margin condition.<n>The second method achieves an expected regret of $tildeOleft(T1-frac(alpha+1)betaalpha+(d+2)beta+T1-betaright)$, in which $beta$ is a parameter describing the tail strength.
  arXiv  Detail & Related papers  (2024-08-19T02:30:37Z)
• Communication-Constrained Bandits under Additive Gaussian Noise [111.06688156723018]
  We study a distributed multi-armed bandit where a client supplies the learner with communication-constrained feedback. We propose a multi-phase bandit algorithm, $mathttUEtext-UCB++$, which matches this lower bound to a minor additive factor.
  arXiv  Detail & Related papers  (2023-04-25T09:31:20Z)
• Fast Rates for the Regret of Offline Reinforcement Learning [69.23654172273085]
  We study the regret of reinforcement learning from offline data generated by a fixed behavior policy in an infinitehorizon discounted decision process (MDP) We show that given any estimate for the optimal quality function $Q*$, the regret of the policy it defines converges at a rate given by the exponentiation of the $Q*$-estimate's pointwise convergence rate.
  arXiv  Detail & Related papers  (2021-01-31T16:17:56Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.