2.2 策略迭代和截断策略迭代

2.2.1 算法步骤

跟值迭代类似, 策略迭代也是一个迭代的方法, 主要分为策略计算(PE)和策略提升(PI)两步.

2.2.1.1 策略计算(PE)

首先在当前策略的基础上, 计算状态值, 实际就是求解贝尔曼公式:

在1.4.4 贝尔曼公式求解中, 我们介绍了有两种求解方式:解析解和迭代求解. 但是解析解需要求逆矩阵, 所以常采用迭代求解的方式:

它的展开形式为:

其中是上一轮迭代的状态值, 初值可以设置为任意值. 直到, 则认为已经收敛.

2.2.1.2 策略提升(PI)

有了状态值之后, 我们求解最优化问题, 得到新的最优策略:

一定优于, 详细证明可以前往书中查看. 展开形式写作:

之前我们介绍过, 最优策略一定是贪婪确定策略:

并且就是使得动作值最大的动作:

2.2.1.3 伪代码

完整的伪代码如图, 算法的策略迭代最终一定会收敛到最优解, 书中也给出了详细证明

2.2.2 例子1

仿真世界如图所示, 奖励设计如下:

抵达边界的奖励是-1:

抵达终点的奖励是1:

其他行为奖励是0

我们将初始策略随机设置为图示: 动作都是往左.

2.2.2.1 k=0

(1) 策略计算(PE)

首先求解贝尔曼公式, 因为这个式子非常简单, 我们可以直接求出解析解:

不过一般我们会用迭代方法计算, 过程如下:

最终的结果也是收敛到:

(2) 策略提升(PI)

这里我们需要计算最优动作值, 因此需要计算出所有的动作值. 这个仿真场景, 完整的计算公式如下:

我们将代入到式子中

可以看得出来, 最优动作是:

因为这个例子非常简单, 显然可以看出来这已经是最优解了.

2.2.3 例子2

这里我们给出了一个更复杂的例子:

仿真世界如图所示, 奖励设计如下:

抵达禁止格或边界的奖励是-1:

抵达终点的奖励是1:

其他行为奖励是0

这里我们将初始策略全部初始化为原地不动, 然后开始迭代. 迭代的过程不再详细描述, 用图片展示每一轮迭代的结果

2.2.4 截断策略迭代

2.2.4.1 值迭代和策略迭代对比

之前我们介绍了这两种迭代方式, 这里我们归纳一下它们的迭代过程:

(1) 策略迭代

PE(已知, 求解):

PI(已知, 求解):

(2) 值迭代

PU(已知, 求解):

VU(已知, 求解):

2.2.4.2 截断策略迭代

这里通过一个表格展现他们的迭代的过程区别, 可以看到一个比较明显的区别是

值迭代的是直接计算出来的; 但是策略迭代的是通过一个小迭代算法计算的:

截断策略迭代就是在策略迭代的基础上, 限制计算的最大迭代次数; 比如上式中, 迭代次之后直接结束迭代.

因为限制了小迭代的次数, 求得的可能并未完全收敛到附近; 因此阶段策略迭代整体收敛速度, 是慢于策略迭代的, 优于值迭代, 如上图所示.

但是每一次迭代的计算时间, 显然是值迭代<截断策略迭代<策略迭代. 所以算法的整体效率是由两方面决定的.