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 $\mathcal{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 algorithms for adversarial multi-armed bandits and improves the regret to $\mathcal{O}(\sqrt{T})$, albeit with a stronger ergodic assumption. To the best of our knowledge, these are the first model-free algorithms with sub-linear regret (that is polynomial in all parameters) in the infinite-horizon average-reward setting.

本文提出两种基于无模型的强化学习算法，用于学习无限时间持续的平均回报MDP问题，第一种算法在弱相互通信的MDPs中，将问题简化为折扣回报问题，在T步之后的遗憾为O(T^(2/3)),该算法是解决该问题的第一种无模型的算法；第二种算法利用了对抗多臂老虎机自适应算法的最新进展，将遗憾进一步改进至O(sqrt(T))，但需要更强的符合人类定义的遍历条件。这个结果取代了Abbasi-Yadkori等人2019年只有在符合人类定义的遍历条件下的ergodic MDP才能达到O(T^(3/4))的遗憾。

无模型强化学习中的无限时域平均奖赏马尔可夫决策过程