Reinforcement Learning in a Birth and Death Process: Breaking the Dependence on the State Space
Not on the map. Why?
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.
Key facts. Cited by 2 papers in the map (data through 7 Oct 2026). Builds on 13 of its 27 references that are in the map. First posted on arXiv 21 Feb 2023.
Builds on
13 of 27 references.
References · 13
- 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 514
- 2017Minimax Regret Bounds for Reinforcement Learningcited by 500
- 2014Generalization and Exploration via Randomized Value Functionscited by 112
- 2020Provably Efficient Reinforcement Learning for Discounted MDPs with Feature Mappingcited by 102
- 2018Efficient Bias-Span-Constrained Exploration-Exploitation in Reinforcement Learningcited by 65
- 2019Regret Minimization for Reinforcement Learning by Evaluating the Optimal Bias Functioncited by 43
- 2014Near-optimal Reinforcement Learning in Factored MDPscited by 41
- 2020Tightening Exploration in Upper Confidence Reinforcement Learningcited by 24
- 2021Nearly Minimax Optimal Regret for Learning Infinite-horizon Average-reward MDPs with Linear Function Approximationcited by 18
- 2019Near-optimal Optimistic Reinforcement Learning using Empirical Bernstein Inequalitiescited by 15
- 2020Towards Minimax Optimal Reinforcement Learning in Factored Markov Decision Processescited by 13
- 2021Learning and Information in Stochastic Networks and Queuescited by 8
1 more
Built on by
Citing papers per year: 2023: 1; 2024: 1.
2 papers.