Abstract
Admission control is a fundamental problem in queuing systems, yet general-purpose reinforcement learning (RL) algorithms often struggle with regret bounds that scale exponentially with buffer size. This paper introduces UCRL-AC, an algorithm specifically designed for admission control that exploits the birth-and-death structure of these systems. By reformulating the relative bias function, UCRL-AC achieves regret bounds that are linear in, or even independent of, the buffer size. Empirical results demonstrate significant improvements in both learning efficiency and computational speed compared to state-of-the-art baselines.
Introduction
In modern infrastructure such as data centers, 5G networks, and electric vehicle charging stations, controllers must make real-time decisions to accept or reject incoming jobs. This process, known as Admission Control, aims to maximize rewards from accepted tasks while minimizing the costs associated with queue occupancy. While Reinforcement Learning (RL) offers a framework for solving such problems without prior knowledge of arrival rates, standard algorithms face a significant theoretical hurdle: the "Diameter Problem."
The Diameter Problem in Queuing Systems
The performance of RL algorithms is typically measured by "regret"—the difference between the reward of an optimal policy and the reward actually collected. Standard regret bounds for algorithms like UCRL2 depend on the diameter $D$ of the state space, which represents the maximum expected time to transition between any two states. In a queuing system with a finite buffer of size $S$, this diameter can grow exponentially with $S$. Consequently, general-purpose RL guarantees suggest that the time required to learn an optimal policy might be prohibitively long for large-scale systems.
UCRL-AC: Exploiting System Structure
To bypass the exponential complexity of general RL, the authors propose UCRL-AC (Upper Confidence Reinforcement Learning for Admission Control). The algorithm is built on several key innovations:
- Optimism under Uncertainty: UCRL-AC maintains confidence intervals for unknown arrival rates and selects an "optimistic" model within these bounds to guide exploration.
- Birth-and-Death Process Modeling: By treating the queue as a Continuous-Time Markov Decision Process (CTMDP) where states only change by increments of $\pm 1$, the authors leverage the specific mathematical properties of birth-and-death processes.
- Relative Bias Reformulation: Instead of the system diameter, the analysis focuses on the relative bias function—the long-term expected reward starting from a specific state. The authors derive closed-form expressions for this bias, proving that regret only grows linearly with $S$.
- Computational Optimization: Leveraging the tridiagonal structure of the transition matrices in queuing systems, the authors reduce the complexity of policy evaluation from $O(S^3)$ to $O(S)$, enabling much faster updates.
Experimental Results
The authors evaluated UCRL-AC against several baselines, including UCRL2, PSRL (Posterior Sampling for RL), KL-UCRL, and UCRL3, using $M/M/c/S$ queue simulations.
As shown in the figures above, UCRL-AC consistently achieves the lowest cumulative regret across various configurations of buffer size $S$ and service rate $\mu$. Notably, as $S$ increases from 20 to 50, the performance advantage of UCRL-AC becomes even more pronounced, validating the theoretical claim that it avoids the exponential regret scaling of general-purpose algorithms. Furthermore, the optimized Policy Iteration in UCRL-AC provided a 140x speedup in computation time compared to standard Value Iteration.
Conclusion
UCRL-AC demonstrates that the exponential dependence on buffer size in admission control is not an inherent limitation of RL, but rather a consequence of using overly general tools. By tailoring the algorithm to the specific structure of birth-and-death processes, the authors provide both stronger theoretical guarantees and superior empirical performance. Future work includes extending the model to scenarios with unknown service rates and non-constant arrival rates.
Summary updated