Bandit-Based Rate Adaptation for a Single-Server Queue

Technical Summary: Bandit-Based Rate Adaptation for a Single-Server Queue

Problem Formulation
This paper addresses the problem of rate adaptation in a single-server queueing system operating in discrete time slots with partial feedback. In each slot $t$, a transmitter selects a transmission rate $V(t)$ from a continuous interval $[0, 1]$. The channel capacity $C(t)$ and the arrival process $A(t)$ are independent and identically distributed (i.i.d.) draws from fixed but unknown distributions. Transmission succeeds if and only if $V(t) \leq C(t)$; otherwise, it fails. The transmitter receives only binary feedback (ACK/NACK) indicating success or failure. The objective is to design a rate-selection algorithm that ensures a uniformly bounded time-average expected queue size, provided the arrival rate $\lambda$ lies strictly within the system's capacity region. The "slack" between the arrival rate and the maximum achievable service rate is denoted by $\varepsilon > 0$.

The authors distinguish between two scenarios:

1. Known $\varepsilon$: The transmitter has prior knowledge of the lower bound on the gap between the arrival rate and the capacity region.
2. Unknown $\varepsilon$: The transmitter does not know $\varepsilon$ and must learn the system dynamics without this parameter.

Methodology
The paper integrates queueing theory with continuum-armed bandit learning. Unlike standard queueing bandits that operate on finite action spaces, this work handles an uncountable infinite rate space.

• For Known $\varepsilon$: The authors propose a discretization strategy where the continuous rate space $[0, 1]$ is mapped to a finite grid of size $d = \lceil \gamma/\varepsilon \rceil$. This transforms the problem into a finite-armed bandit problem. The authors apply the classical Upper Confidence Bound (UCB1) algorithm to this discretized set. They perform a rigorous two-stage analysis: a learning stage to identify the optimal discretized rate and a control stage using Lyapunov drift analysis to bound the queue size once the rate is sufficiently close to optimal.

• For Unknown $\varepsilon$: The authors propose a phased algorithm that iteratively refines the discretization of the rate space. The algorithm operates in phases $\ell = 1, 2, \dots$. In each phase $\ell$, the rate space is discretized into $d_\ell$ levels, where $d_\ell$ grows as a function of the phase length $T_\ell$. Within each phase, a UCB1 adaptation runs on the current discretization. The sequences $\{T_\ell\}$ and $\{d_\ell\}$ are carefully chosen (specifically, $T_\ell = 2^{\ell+2}$ and $d_\ell \propto T_\ell^{1/2-\delta}$) to balance the exploration burden against the need for finer discretization to ensure stability.

Key Contributions

1. Novel Formulation: The paper introduces the first integration of queueing stability with continuum-armed bandits, addressing the challenge that no fixed finite set of arms can guarantee stability without knowledge of the unknown arrival and service distributions.
2. Algorithm Design for Unknown $\varepsilon$: A phased UCB algorithm is designed that adaptively refines the rate discretization without prior knowledge of $\varepsilon$.
3. Converse Result: The authors establish a lower bound (converse) showing that for any rate-selection algorithm (whether $\varepsilon$ is known or unknown), there exists an environment where the worst-case time-average expected queue size is $\Omega(1/\varepsilon^2)$.
4. Optimality for Known $\varepsilon$: The paper proves that when $\varepsilon$ is known, the proposed UCB-based algorithm on a fixed discretization achieves a time-average expected queue size of $O(\log(1/\varepsilon)/\varepsilon^2)$. This matches the converse lower bound up to logarithmic factors, establishing optimality in this setting.

Results

• Unknown $\varepsilon$: The proposed phased algorithm achieves a time-average expected queue size of order $O(\log^{3.5}(1/\varepsilon)/\varepsilon^3)$ uniformly over the time horizon.
• Known $\varepsilon$: The algorithm achieves a time-average expected queue size of order $O(\log(1/\varepsilon)/\varepsilon^2)$.
• Lower Bound: The converse result demonstrates that the queue size cannot be better than $\Omega(1/\varepsilon^2)$ in the worst case, regardless of the algorithm's knowledge of $\varepsilon$.

Significance and Claims
The paper claims to be the first to integrate queueing stability with continuum-armed bandits, motivated by practical applications like rate selection in IEEE 802.11 systems where the action space is too large for finite-armed formulations.

The authors highlight a gap between the upper bound ($O(\varepsilon^{-3})$) and the lower bound ($O(\varepsilon^{-2})$) in the unknown $\varepsilon$ setting. They conjecture that an algorithm achieving $O(\log^\alpha(1/\varepsilon)/\varepsilon^2)$ is possible when $\varepsilon$ is unknown, which would close this gap. The paper explicitly states that designing such an algorithm is left as future work. Additionally, the authors suggest extending the continuum-armed queueing framework to multi-queue or networked settings as another future direction.

The work provides a theoretical foundation for rate adaptation under partial feedback, demonstrating that while knowledge of the system slack $\varepsilon$ allows for near-optimal performance, learning without this knowledge incurs a polynomial penalty in the queue size bound.