# Reinforcement Learning and Regret Bounds for Admission Control

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods.
- Builds on 8 of its 30 references that are in the map.
- First posted on arXiv 7 Jun 2024.

## Placed in

- Deep reinforcement learning methods / [RL theory and sample complexity](https://mlsanity.com/deeprl/rl-theory-and-sample-complexity/)

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

- [(More) Efficient Reinforcement Learning via Posterior Sampling](https://mlsanity.com/paper/1306.0940/) (2013)
- [Regret Minimization for Reinforcement Learning by Evaluating the Optimal Bias Function](https://mlsanity.com/paper/1906.05110/) (2019)
- [Variance-Aware Regret Bounds for Undiscounted Reinforcement Learning in MDPs](https://mlsanity.com/paper/1803.01626/) (2018)
- [Tightening Exploration in Upper Confidence Reinforcement Learning](https://mlsanity.com/paper/2004.09656/) (2020)
- [Logarithmic regret bounds for continuous-time average-reward Markov decision processes](https://mlsanity.com/paper/2205.11168/) (2022)
- [Posterior Sampling for Reinforcement Learning Without Episodes](https://mlsanity.com/paper/1608.02731/) (2016)
- [Learning-based Optimal Admission Control in a Single Server Queuing System](https://mlsanity.com/paper/2212.11316/) (2022)
- [Reinforcement Learning in a Birth and Death Process: Breaking the Dependence on the State Space](https://mlsanity.com/paper/2302.10667/) (2023)

## Abstract (arXiv)

The expected regret of any reinforcement learning algorithm is lower bounded by Omegaleft(√DXATright) for undiscounted returns, where D is the diameter of the Markov decision process, X the size of the state space, A the size of the action space and T the number of time steps. However, this lower bound is general. A smaller regret can be obtained by taking into account some specific knowledge of the problem structure. In this article, we consider an admission control problem to an M/M/c/S queue with m job classes and class-dependent rewards and holding costs. Queuing systems often have a diameter that is exponential in the buffer size S, making the previous lower bound prohibitive for any practical use. We propose an algorithm inspired by UCRL2, and use the structure of the problem to upper bound the expected total regret by O(Slog T + √mT log T) in the finite server case. In the infinite server case, we prove that the dependence of the regret on S disappears.