Reinforcement Learning in a Birth and Death Process: Breaking the Dependence on the State Space
This work addresses inefficiency in reinforcement learning for queueing systems by providing a state-space-independent regret bound, which is incremental as it builds on existing algorithms but offers a novel theoretical improvement.
The paper tackles the problem of reinforcement learning in MDPs with a birth and death structure, such as a controlled queue with impatient jobs, by showing that a tweaked version of Ucrl2 achieves a regret upper bound of ˜O(√(E_2AT)), where E_2 is independent of the state space size S, breaking the dependence on the diameter which scales as Ω(S^S).
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 \emph{diameter} $D$ of the MDP is $Ω(S^S)$, where $S$ is the number of states. Therefore, the existing lower and upper bounds on the regret at time$T$, of order $O(\sqrt{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 $\tilde{\mathcal{O}}(\sqrt{E_2AT})$ where $E_2$ is related to the weighted second moment of the stationary measure of a reference policy. Importantly, $E_2$ 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.