成都p2p网站建设广州网站维护

本章是整个课程中，算法与方法的第一章，应该是最简单的入门方法。

上一章讲到了贝尔曼最优方程，其目的是计算出最优状态值，从而确定对应的最优策略。

而压缩映射理论推出了迭代算法

对初始值V0赋一个随机的初始值，算法最终总会找到这个最优状态值与最优策略，就是上一章讲到的稳定点，这个方法就叫做值迭代法（value  iteration）。

那么如何实现这个值迭代算法呢？首先选择贝尔曼最优方程的矩阵-向量形式。

接着算法进行迭代，每个迭代周期内进行两步操作。第一步叫做策略升级，利用现有策略对应参数，计算出其中的最优策略记作下个时间点的策略Pi_k+1。

第二步叫做值的升级，利用第一步新得到的最优策略，对现有的值进行升级。

这里的Vk不是状态值，因为它不一定满足贝尔曼方程（原文这样写，我也没明白为啥不一定满足）

这里是采用矩阵-向量的形式进行值迭代的理论分析，具体的算法实现，还是用基于元素的方式来完成。在基于元素的方式下，第一步策略升级的公式，可以写成如下这样，向下的大括号整体上是行为值（Action Value，第二章的内容）

策略更新的本质就是将每个状态下的行为，都修改成行为值最大的那个，可以看出这是个基于贪心思路的策略。

第二步的值升级公式，在基于元素的形式下，可以写成如下形式

因为采用贪心的思路，这个新的值V_k+1等价于最优的行为值（行为值最大的行为，采用的概率为100%，其余的为0%，就能得到最大值）。

整个计算的流程如下所示，依次计算各对应的变量

值迭代算法的伪代码（没仔细看）

第二种算法叫做策略迭代法（Policy iteration algorithm），该算法也是分为两步。初始情况下，给一个随机的策略Pi_0。第一步是对这个策略进行性能的量化，计算出状态值。

第二步叫做策略改进，逐状态更新对应的行为。

整个策略迭代法的计算顺序如下所示，其中PE为策略估计，PI是策略提升。策略迭代算法本质上是在策略估计中，嵌入了另一个迭代算法。

策略迭代算法的实现与值迭代算法类似，都是采用基于元素的方式。策略迭代算法的策略评估，其基于元素的方法如下所示：

迭代的终止条件为j的值足够大（即迭代足够多的次数），或者迭代的过程中，前后两次计算得到的状态值差异足够小。

第二步策略改进的基于元素的方法如下所示

当然需要的操作跟矩阵-向量形式一样，都是先找寻最大行为值，再更新策略里的相关行为。

策略迭代的伪代码如下（也没仔细看）

下面讨论的是值迭代法和策略迭代法之间的关系。下面是两个算法的整体情况，都是分两步进行。策略迭代的初始是一个随机的策略，值迭代的初始是一个随机的状态值。

两个算法本质上很相似，用；流水线的形式表示可以看出，两个算法的开头相差一步，后面都是一样的。

用表格的形式展示，可以看到算法的细节，后面的每一步虽然名字不同，但是计算的内容大部分是一样的。

第四步的计算是有差异的，策略迭代这里是要用一个无穷步迭代算法计算这个策略值，而值迭代这里只是一个一步的迭代运算。

所以在做策略迭代的时候，这里要设置一个阈值j，迭代次数大于J的迭代操作予以舍弃，这叫做截断的策略迭代算法（truncated policy iteration algorithm）。

这个是截断的策略迭代算法的伪代码

下面是几个算法测试的性能

既然有三种算法，那么在使用中又是如何取舍的？我问了豆包，结果贴在了下面。总的来说就是，简单问题选值迭代，复杂问题下资源（时间资源、计算资源）充足选策略迭代，资源不充足选基于截断的策略迭代。