Near-optimal Regret Bounds for Reinforcement Learning

For undiscounted reinforcement learning in Markov decision processes (MDPs) we consider the total regret of a learning algorithm with respect to an optimal policy. In order to describe the transiti...