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 $\Omega \left(\sqrt{DXAT}\right)$ for undiscounted returns, where $D$ is the diameter of the Markov decisi…