Q-learning收敛的标准

Question

我正在试验 Q-learning 算法。我已经从不同的来源阅读并理解了该算法，但是，似乎没有明确的数学支持的收敛标准。

大多数来源建议迭代多次（例如，N = 1000），而其他人则表示当所有状态和动作对 (s, a) 被无限频繁访问时实现收敛。但这里的问题是，多少是无限频繁。对于想要手动解决算法的人来说，最好的标准是什么？

如果有人能在这方面教育我，我将不胜感激。我也很感激任何有这种效果的文章。

问候。

Answer 1

Q-Learning 是强化学习的重大突破，正是因为它是第一个保证收敛到最优策略的算法。它最初是在(Watkins, 1989) 中提出的，其收敛性证明在(Watkins & Dayan, 1992) 中得到了完善。

简而言之，必须满足两个条件才能保证收敛于极限，这意味着在任意长的时间段后，策略将任意接近最优策略。请注意，这些条件并未说明策略接近最优策略的速度。

1. 学习率必须接近零，但不能太快。形式上，这要求学习率的总和必须发散，但它们的平方和必须收敛。具有这些属性的示例序列是1/1, 1/2, 1/3, 1/4, ...
2. 每个状态-动作对必须被无限频繁地访问。这有一个精确的数学定义：每个动作在每个状态下都必须有被策略选择的非零概率，即 ?(s, a) > 0对于所有(s, a)。在实践中，使用 ?-greedy 策略（其中? > 0）可确保满足此条件。