MDP和强化学习 - VI，PI和Q学习算法的收敛性比较

Question

我已经使用python实现了VI（Value Iteration），PI（Policy Iteration）和QLearning算法。比较结果后，我发现了一些东西。 VI和PI算法汇聚于相同的实用程序和策略。使用相同的参数，QLearning算法会收敛到不同的实用程序，但使用VI和PI算法的策略相同。这是正常的吗？我阅读了很多关于MDP和RL的论文和书籍，但是找不到任何能说明VI-PI算法的实用程序是否应该与QLearning收敛到相同实用程序的东西。

以下信息是关于我的网格世界和结果。

我的网格世界

grid_world.png

• States => {s0，s1，...，s10}
• Actions => {a0，a1，a2，a3}其中：a0 = Up，a1 = Right，a2 = Down，a3 =所有状态的Left
• 有4种终端状态，具有+1，+ 1，-10，+ 10奖励。
• 初始状态是s6
• 动作的转换概率为P，并且（1-p）/ 2为该动作的左侧或右侧。 （例如：如果P = 0.8，当代理尝试上升时，80％的机会代理将上升，10％的机会代理将右移，10％左下。）

结果

• VI和PI算法结果，Reward = -0.02，Discount Factor = 0.8，Probability = 0.8
• VI在50次迭代后收敛，PI在3次迭代后收敛

vi_pi_results.png

• QLearning算法结果，奖励= -0.02，折扣因子= 0.8，学习率= 0.1，Epsilon（用于探索）= 0.1
• QLearning结果图像上的结果实用程序是每个状态的最大Q（s，a）对。

qLearning_1million_10million_iterations_results.png

此外，我还注意到，当QLearning进行100万次迭代时，距离+10奖励终端同样远的状态具有相同的效用。代理似乎并不关心它是否会从接近-10终端的路径获得奖励，而代理商则关注VI和PI算法。这是因为，在QLearning中，我们不知道环境的转移概率？

Answer 1

如果状态和动作空间是有限的，就像你的问题一样，当转换的数量接近无穷大并且在以下条件下时，Q-learning算法应该渐近地收敛到最优效用（也就是Q函数）：

，

其中n是过渡的数量，a是学习率。这种情况需要随着学习进展而更新学习率。一个典型的选择可能是使用a_n = 1/n。然而，在实践中，学习速率表可能需要根据问题进行一些调整。

另一方面，另一种收敛条件包括无限更新所有状态 - 动作对（在asymtotical意义上）。这可以通过保持大于零的勘探率来实现。

因此，在您的情况下，您需要降低学习率。