algorithm - Q 学习的收敛标准

Question

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

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

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

问候。

Answer 1

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

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

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