Q-learning with Uniformly Bounded Variance: Large Discounting is Not a Barrier to Fast Learning

Adithya M. Devraj, Sean P. Meyn

Sample complexity bounds are a common performance metric in the Reinforcement Learning literature. In the discounted cost, infinite horizon setting, all of the known bounds have a…