Reinforcement Learning and Regret Bounds for Admission Control
Not on the map. Why?
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.
Key facts. No citing papers in the map yet (data through 7 Oct 2026). Builds on 8 of its 30 references that are in the map. First posted on arXiv 7 Jun 2024.
Builds on
8 of 30 references.
References · 8
- 2013(More) Efficient Reinforcement Learning via Posterior Samplingcited by 233
- 2019Regret Minimization for Reinforcement Learning by Evaluating the Optimal Bias Functioncited by 43
- 2018Variance-Aware Regret Bounds for Undiscounted Reinforcement Learning in MDPscited by 41
- 2020Tightening Exploration in Upper Confidence Reinforcement Learningcited by 24
- 2022Logarithmic regret bounds for continuous-time average-reward Markov decision processescited by 7
- 2016Posterior Sampling for Reinforcement Learning Without Episodescited by 6
- 2022Learning-based Optimal Admission Control in a Single Server Queuing Systemcited by 3
- 2023Reinforcement Learning in a Birth and Death Process: Breaking the Dependence on the State Spacecited by 2
Built on by
Not cited yet.