# Bandit-Based Rate Adaptation for a Single-Server Queue

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 Dec 2025.

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

- [Algorithm for Contextual Queueing Bandits with Rate-Optimal Queue Length Regret](https://mlsanity.com/paper/2606.09668/) (2026)
- [Learning While Scheduling Jobs under Context-Dependent Service Rates: An Anytime Rate-Optimal Algorithm](https://mlsanity.com/paper/2610.06006/) (2026)

## Abstract (arXiv)

This paper considers the problem of obtaining bounded time-average expected queue sizes in a single-queue system with a partial-feedback structure. Time is slotted; in slot t the transmitter chooses a rate V(t) from a continuous interval. Transmission succeeds if and only if V(t)≤ C(t), where channel capacities C(t) and arrivals are i.i.d. draws from fixed but unknown distributions. The transmitter observes only binary acknowledgments (ACK/NACK) indicating success or failure. Let varepsilon>0 denote a sufficiently small lower bound on the slack between the arrival rate and the capacity region. We propose a phased algorithm that progressively refines a discretization of the uncountable infinite rate space and, without knowledge of varepsilon, achieves a O!big(log3.5(1/varepsilon)/varepsilon3big) time-average expected queue size uniformly over the horizon. We also prove a converse result showing that for any rate-selection algorithm, regardless of whether varepsilon is known, there exists an environment in which the worst-case time-average expected queue size is Omega(1/varepsilon2). Thus, while a gap remains in the setting without knowledge of varepsilon, we show that if varepsilon is known, a simple single-stage UCB type policy with a fixed discretization of the rate space achieves O!big(log(1/varepsilon)/varepsilon2big), matching the converse up to logarithmic factors.