algorithm - Q-learning 中的收敛标准

Question

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

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

如果有人能就此对我进行教育，我将不胜感激。我也将不胜感激任何有关此效果的文章。

问候。

标签： algorithmmachine-learningartificial-intelligencereinforcement-learningq-learning

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）可确保满足此条件。