Reinforcement Learning and Regret Bounds for Admission Control

Lucas Weber, Ana Bušić, Jiamin Zhu

The expected regret of any reinforcement learning algorithm is lower bounded by $\hat{I}\text{c◯}\left(\sqrt{DXAT}\right)$ for undiscounted returns, where $D$ is the diameter of the Markov decis…