Achieving ${\epsilon }^{-2}$ Dependence for Average-Reward Q-Learning with a New Contraction Principle

Zijun Chen, Zaiwei Chen, Nian Si +1

We present the convergence rates of synchronous and asynchronous Q-learning for average-reward Markov decision processes, where the absence of contraction poses a fundamental chall…