# Learning-based Optimal Admission Control in a Single Server Queuing System

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 38 references that are in the map.
- First posted on arXiv 21 Dec 2022.

## Builds on (most cited first, 10 of 10)

- [Learning in structured MDPs with convex cost functions: Improved regret bounds for inventory management](https://mlsanity.com/paper/1905.04337/) (2019)
- [Learning Unknown Service Rates in Queues: A Multi-Armed Bandit Approach](https://mlsanity.com/paper/1604.06377/) (2016)
- [Job Dispatching Policies for Queueing Systems with Unknown Service Rates](https://mlsanity.com/paper/2106.04707/) (2021)
- [On Learning the cμ Rule in Single and Parallel Server Networks](https://mlsanity.com/paper/1802.06723/) (2018)
- [Augmenting Max-Weight with Explicit Learning for Wireless Scheduling with Switching Costs](https://mlsanity.com/paper/1808.01618/) (2018)
- [Learning and Information in Stochastic Networks and Queues](https://mlsanity.com/paper/2105.08769/) (2021)
- [Learning While Scheduling in Multi-Server Systems with Unknown Statistics: MaxWeight with Discounted UCB](https://mlsanity.com/paper/2209.01126/) (2022)
- [An online learning approach to dynamic pricing and capacity sizing in service systems](https://mlsanity.com/paper/2009.02911/) (2020)
- [Brownian control problems for a multiclass M/M/1 queueing problem with model uncertainty](https://mlsanity.com/paper/1702.06479/) (2017)
- [Asymptotic optimality of the generalized cμ rule under model uncertainty](https://mlsanity.com/paper/2004.01232/) (2020)

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

- [Bayesian Learning of Optimal Policies in Markov Decision Processes with Countably Infinite State-Space](https://mlsanity.com/paper/2306.02574/) (2023)
- [Reinforcement Learning and Regret Bounds for Admission Control](https://mlsanity.com/paper/2406.04766/) (2024)
- [Learning Adaptive SED for heterogeneous load balancing](https://mlsanity.com/paper/2609.06881/) (2026)

## Abstract (arXiv)

We consider a long-term average profit maximizing admission control problem in an M/M/1 queuing system with unknown service and arrival rates. With a fixed reward collected upon service completion and a cost per unit of time enforced on customers waiting in the queue, a dispatcher decides upon arrivals whether to admit the arriving customer or not based on the full history of observations of the queue-length of the system. (Naor 1969, Econometrica) showed that if all the parameters of the model are known, then it is optimal to use a static threshold policy -- admit if the queue-length is less than a predetermined threshold and otherwise not. We propose a learning-based dispatching algorithm and characterize its regret with respect to optimal dispatch policies for the full information model of Naor (1969). We show that the algorithm achieves an O(1) regret when all optimal thresholds with full information are non-zero, and achieves an O(ln1+ε(N)) regret for any specified ε>0, in the case that an optimal threshold with full information is 0 (i.e., an optimal policy is to reject all arrivals), where N is the number of arrivals.