Model-free reinforcement learning is known to be memory and computation efficient and more amendable to large scale problems. In this paper, two model-free algorithms are introduced for learning infinite-horizon average-reward Markov Decision Processes (MDPs). The first algorithm reduces the problem to the discounted-reward version and achieves O(T^2/3) regret after T steps, under the minimal assumption of weakly communicating MDPs. The second algorithm makes use of recent advances in adaptive a…