Learning to Admit Optimally in an $M/M/k/k+N$ Queueing System with Unknown Service Rate
This work addresses admission control for queueing systems in applications like production and messaging, but it is incremental as it adapts existing self-tuning control methods to a specific model with unknown service rate.
The paper tackles the problem of admission control in an M/M/k/k+N queueing system with unknown service rate, aiming to maximize long-term average reward by observing only arrival times and system state. The proposed learning-based dispatch scheme asymptotically converges to the optimal policy, with finite-time regret guarantees that vary from constant to logarithmic depending on parameter regimes.
Motivated by applications of the Erlang-B blocking model and the extended $M/M/k/k+N$ model that allows for some queueing, beyond communication networks to sizing and pricing in production, messaging, and app-based parking systems, we study admission control for such systems with unknown service rate. In our model, a dispatcher either admits every arrival into the system (when there is room) or blocks it. Every served job yields a fixed reward but incurs a per unit time holding cost which includes the waiting time in the queue to get service if there is any. We aim to design a dispatching policy that maximizes the long-term average reward by observing arrival times and system state at arrivals, a realistic decision-event driven sampling of such systems. The dispatcher observes neither service times nor departure epochs, which excludes the use of reward-based reinforcement learning approaches. We develop our learning-based dispatch scheme as a parametric learning problem a'la self-tuning adaptive control. In our problem, certainty equivalent control switches between always admit if room (explore infinitely often), and never admit (terminate learning), so at judiciously chosen times we avoid the never admit recommendation. We prove that our proposed policy asymptotically converges to the optimal policy and present finite-time regret guarantees. The extreme contrast in the control policies shows up in our regret bounds for different parameter regimes: constant in one versus logarithmic in another.