Poster
Reinforcement Learning in a Birth and Death Process: Breaking the Dependence on the State Space
Jonatha Anselmi · Bruno Gaujal · Louis-Sébastien Rebuffi
Hall J (level 1) #539
Keywords: [ queueing systems ] [ Markov Decision Processes ] [ Regret Analysis ] [ structured reinforcement learning ]
Abstract:
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 of the MDP is , where is the number of states. Therefore, the existing lower and upper bounds on the regret at time , of order for MDPs with states and 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 UCRL2 is in fact upper bounded by where is a weighted second moment of the stationary measure of a reference policy. Importantly, is bounded independently of . 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.
Chat is not available.