RL Practice1 | XiangSiqi’s Blog

Bellman Equation

贝尔曼公式的出发点考虑环境为：

考虑的策略为，这是一个马尔可夫链，考虑return为：

取平均得到价值函数：

第一项为：

第二项考虑为：

考虑马尔可夫链的无记忆性：

从而得到：

写为：

考虑矩阵形式，为一个向量，定义，是一个矢量，定义，是一个矩阵，得到：

这就是Bellman公式，利用不动点收缩方法：

这个迭代将收敛到满足Bellman公式的，即：

现在考虑action value函数：

显然第一项为：

第二项为：

得到：

第一项完全由环境决定，第二项由策略和环境决定。可以看到满足：

我们的优化目标是得到一个正确的策略，在贪婪算法下，对于状态，定义为使得取得最大值的，即得到，或者说，只需要让每一行最大的数变成1，其他变成0，转置后就自然得到。将这个策略代入价值函数中，即得到新一轮的价值函数，再计算，反复循环，即可收敛到最好的策略。

例如初始化为一个全是0.2的矩阵，即均等采样，利用贝尔曼公式迭代得到，利用这个策略进行探索获得的，进一步计算，得到这个策略探索所获得的关于每一步行为的价值。此时贪婪搜索修正，取得，迭代即可。这种方法称为策略迭代。

或者初始化，这是一个向量，均等初始化意味着任何态的优势都是相通的，代入得到，意味着所有状态均等的行为价值，贪婪算法得到，意味着任何态均等下的策略，同时由于贪心算法，不再需要代入Bellman公式试探，而是直接从中提取，本质是根据定义：

从而进一步迭代。这种方法称为值迭代。

对比一下发现，策略迭代需要多重迭代以收敛到，然后再计算出，而值迭代不收敛到，选择直接把初始化的用于计算。

你可能会问，为什么在策略迭代计算出后，为什么不直接利用计算出下一次的呢，其实，考虑，带入计算之后发现得到的还是。这就是策略迭代的特征，它是充分收敛的。而值迭代则根本没有这一步，因此需要很多步骤。

因此还有一种方法是在中收敛一部分，通过设定一个截断循环。完整方法是初始化一个策略，再初始化价值函数，利用Bellman公式迭代，但是只迭代次，得到，计算得到，从中利用贪婪算法得到，循环即可，直到收敛。显然，策略迭代则得到，而值迭代则则不利用Bellman公式，直接用计算。

Bellman公式的问题是它是一个Model Based算法，这就是说，我们必须知道全部的环境量：

在采样角度体现为，每一次都要完成从任意出发，执行动作后无穷次采样：

，意味着从出发一步得到的奖励和末态的价值函数的第个采样，或者就是从出发沿第个路径走无穷多步得到的采样，因为：

这就是MC Basic的方法，考虑从每个出发，做次探索，并将Return求平均，当足够大时，根据MC，则可以取得在下的，再利用此更新策略。

但是这种方法的问题是，信息利用不全，考虑从出发的路径：

从中间任意节点切入也可以当作一个trajectory，得到。而在计算时，我们不从左到右计算，这样每一个时间步需要做次运算，个时间步的计算复杂度是，考虑从倒回来，则，，即：

其实这就是Bellman公式的一种形式。一个更为值得注意的关键点是，使用MC的前提是i.i.d，如果一个trajectory中包含多个同样的态，对这些态的的重复计入会破坏相关性，因此在迭代时，我们只记录最后面那个态的。

更进一步的改进是不是跑完搜索之后再做更新，而是跑一个trajectory就做一次更新，从而加速收敛。

还有改进是利用替代原始贪婪搜索：

这里是能够执行的action的数量。