# Reinforcement Learning in a Birth and Death Process: Breaking the Dependence on the State Space

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 27 references that are in the map.
- First posted on arXiv 21 Feb 2023.

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

- [Provably Efficient Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/1907.05388/) (2019)
- [Minimax Regret Bounds for Reinforcement Learning](https://mlsanity.com/paper/1703.05449/) (2017)
- [Generalization and Exploration via Randomized Value Functions](https://mlsanity.com/paper/1402.0635/) (2014)
- [Provably Efficient Reinforcement Learning for Discounted MDPs with Feature Mapping](https://mlsanity.com/paper/2006.13165/) (2020)
- [Efficient Bias-Span-Constrained Exploration-Exploitation in Reinforcement Learning](https://mlsanity.com/paper/1802.04020/) (2018)
- [Regret Minimization for Reinforcement Learning by Evaluating the Optimal Bias Function](https://mlsanity.com/paper/1906.05110/) (2019)
- [Near-optimal Reinforcement Learning in Factored MDPs](https://mlsanity.com/paper/1403.3741/) (2014)
- [Tightening Exploration in Upper Confidence Reinforcement Learning](https://mlsanity.com/paper/2004.09656/) (2020)
- [Nearly Minimax Optimal Regret for Learning Infinite-horizon Average-reward MDPs with Linear Function Approximation](https://mlsanity.com/paper/2102.07301/) (2021)
- [Near-optimal Optimistic Reinforcement Learning using Empirical Bernstein Inequalities](https://mlsanity.com/paper/1905.12425/) (2019)
- [Towards Minimax Optimal Reinforcement Learning in Factored Markov Decision Processes](https://mlsanity.com/paper/2006.13405/) (2020)
- [Learning and Information in Stochastic Networks and Queues](https://mlsanity.com/paper/2105.08769/) (2021)
- [An Overview for Markov Decision Processes in Queues and Networks](https://mlsanity.com/paper/1907.10243/) (2019)

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

- [Learning Optimal Admission Control in Partially Observable Queueing Networks](https://mlsanity.com/paper/2308.02391/) (2023)
- [Reinforcement Learning and Regret Bounds for Admission Control](https://mlsanity.com/paper/2406.04766/) (2024)

## Abstract (arXiv)

In this paper, we revisit the regret of undiscounted reinforcement learning in MDPs with a birth and death structure. Specifically, we consider a controlled queue with impatient jobs and the main objective is to optimize a trade-off between energy consumption and user-perceived performance. Within this setting, the diameter D of the MDP is Omega(SS), where S is the number of states. Therefore, the existing lower and upper bounds on the regret at timeT, of order O(√DSAT) for MDPs with S states and A actions, may suggest that reinforcement learning is inefficient here. In our main result however, we exploit the structure of our MDPs to show that the regret of a slightly-tweaked version of the classical learning algorithm sc Ucrl2 is in fact upper bounded by tildeO(√E2AT) where E2 is related to the weighted second moment of the stationary measure of a reference policy. Importantly, E2 is bounded independently of S. Thus, our bound is asymptotically independent of the number of states and of the diameter. This result is based on a careful study of the number of visits performed by the learning algorithm to the states of the MDP, which is highly non-uniform.