Recently, model-free reinforcement learning has attracted research attention
due to its simplicity, memory and computation efficiency, and the flexibility
to combine with function approximation. In this paper, we propose Exploration
Enhanced Q-learning (EE-QL), a model-free algorithm for infinite-horizon
average-reward Markov Decision Processes (MDPs) that achieves regret bound of
$O(\sqrt{T})$ for the general class of weakly communicating MDPs, where $T$ is
the number of interactions. EE-QL assumes that an online concentrating
approximation of the optimal average reward is available. This is the first
model-free learning algorithm that achieves $O(\sqrt T)$ regret without the
ergodic assumption, and matches the lower bound in terms of $T$ except for
logarithmic factors. Experiments show that the proposed algorithm performs as
well as the best known model-based algorithms.

提出了一种基于 EE-QL，结合浓度逼近和无模型弱交流 MDPs 的无模型学习算法，实现了与最佳已知基于模型算法相似的学习速度。