强化学习基础篇(六)动态规划之策略迭代(2)
1、策略改进(Policy improvement)的理论证明
考虑对一个确定性策略(Deterministic policy),我们可以通过执行贪婪计算不断优化改进策略,即:
在这个过程中每次只使用一次步骤改善状态的动作值函数。即:
如下将证明策略提升定理:
<svg xmlns:xlink="http://www.w3.org/1999/xlink" width="116.553ex" height="25.431ex" viewBox="0 -5708.1 50182.4 10949.4" role="img" focusable="false" style="vertical-align: -11.936ex; margin-bottom: -0.237ex;" class="in-text-selection"><g stroke="currentColor" fill="currentColor" stroke-width="0" transform="matrix(1 0 0 -1 0 0)"><g transform="translate(167,0)"><g transform="translate(26944,0)"><g transform="translate(19674,4830)"><text font-family="STIXGeneral, 'PingFang SC', serif" stroke="none" transform="scale(51.874) matrix(1 0 0 -1 0 0)">已</text><g transform="translate(807,0)"><text font-family="STIXGeneral, 'PingFang SC', serif" stroke="none" transform="scale(51.874) matrix(1 0 0 -1 0 0)">知</text></g><g transform="translate(1614,0)"><text font-family="STIXGeneral, 'PingFang SC', serif" stroke="none" transform="scale(51.874) matrix(1 0 0 -1 0 0)">条</text></g><g transform="translate(2421,0)"><text font-family="STIXGeneral, 'PingFang SC', serif" stroke="none" transform="scale(51.874) matrix(1 0 0 -1 0 0)">件</text></g></g><g transform="translate(0,3471)"><text font-family="STIXGeneral, 'PingFang SC', serif" stroke="none" transform="scale(51.874) matrix(1 0 0 -1 0 0)">在</text><g transform="translate(807,0)"><text font-family="STIXGeneral, 'PingFang SC', serif" stroke="none" transform="scale(51.874) matrix(1 0 0 -1 0 0)">当</text></g><g transform="translate(1614,0)"><text font-family="STIXGeneral, 'PingFang SC', serif" stroke="none" transform="scale(51.874) matrix(1 0 0 -1 0 0)">前</text></g><g transform="translate(2421,0)"><text font-family="STIXGeneral, 'PingFang SC', serif" stroke="none" transform="scale(51.874) matrix(1 0 0 -1 0 0)">状</text></g><g transform="translate(3229,0)"><text font-family="STIXGeneral, 'PingFang SC', serif" stroke="none" transform="scale(51.874) matrix(1 0 0 -1 0 0)">态</text></g><g transform="translate(6807,0)"><text font-family="STIXGeneral, 'PingFang SC', serif" stroke="none" transform="scale(51.874) matrix(1 0 0 -1 0 0)">时</text></g><g transform="translate(7614,0)"><text font-family="STIXGeneral, 'PingFang SC', serif" stroke="none" transform="scale(51.874) matrix(1 0 0 -1 0 0)">,</text></g><g transform="translate(8421,0)"><text font-family="STIXGeneral, 'PingFang SC', serif" stroke="none" transform="scale(51.874) matrix(1 0 0 -1 0 0)">采</text></g><g transform="translate(9229,0)"><text font-family="STIXGeneral, 'PingFang SC', serif" stroke="none" transform="scale(51.874) matrix(1 0 0 -1 0 0)">用</text></g><g transform="translate(10036,0)"><text font-family="STIXGeneral, 'PingFang SC', serif" stroke="none" transform="scale(51.874) matrix(1 0 0 -1 0 0)">动</text></g><g transform="translate(10843,0)"><text font-family="STIXGeneral, 'PingFang SC', serif" stroke="none" transform="scale(51.874) matrix(1 0 0 -1 0 0)">作</text></g><g transform="translate(13766,0)"><text font-family="STIXGeneral, 'PingFang SC', serif" stroke="none" transform="scale(51.874) matrix(1 0 0 -1 0 0)">并</text></g><g transform="translate(14573,0)"><text font-family="STIXGeneral, 'PingFang SC', serif" stroke="none" transform="scale(51.874) matrix(1 0 0 -1 0 0)">跳</text></g><g transform="translate(15380,0)"><text font-family="STIXGeneral, 'PingFang SC', serif" stroke="none" transform="scale(51.874) matrix(1 0 0 -1 0 0)">转</text></g><g transform="translate(16188,0)"><text font-family="STIXGeneral, 'PingFang SC', serif" stroke="none" transform="scale(51.874) matrix(1 0 0 -1 0 0)">到</text></g><g transform="translate(16995,0)"><text font-family="STIXGeneral, 'PingFang SC', serif" stroke="none" transform="scale(51.874) matrix(1 0 0 -1 0 0)">下</text></g><g transform="translate(17802,0)"><text font-family="STIXGeneral, 'PingFang SC', serif" stroke="none" transform="scale(51.874) matrix(1 0 0 -1 0 0)">一</text></g><g transform="translate(18610,0)"><text font-family="STIXGeneral, 'PingFang SC', serif" stroke="none" transform="scale(51.874) matrix(1 0 0 -1 0 0)">个</text></g><g transform="translate(19417,0)"><text font-family="STIXGeneral, 'PingFang SC', serif" stroke="none" transform="scale(51.874) matrix(1 0 0 -1 0 0)">状</text></g><g transform="translate(20224,0)"><text font-family="STIXGeneral, 'PingFang SC', serif" stroke="none" transform="scale(51.874) matrix(1 0 0 -1 0 0)">态</text></g></g><g transform="translate(8751,2112)"><text font-family="STIXGeneral, 'PingFang SC', serif" stroke="none" transform="scale(51.874) matrix(1 0 0 -1 0 0)">根</text><g transform="translate(807,0)"><text font-family="STIXGeneral, 'PingFang SC', serif" stroke="none" transform="scale(51.874) matrix(1 0 0 -1 0 0)">据</text></g></g><g transform="translate(19417,762)"><text font-family="STIXGeneral, 'PingFang SC', serif" stroke="none" transform="scale(51.874) matrix(1 0 0 -1 0 0)">跳</text><g transform="translate(807,0)"><text font-family="STIXGeneral, 'PingFang SC', serif" stroke="none" transform="scale(51.874) matrix(1 0 0 -1 0 0)">转</text></g></g><g transform="translate(9865,-672)"><text font-family="STIXGeneral, 'PingFang SC', serif" stroke="none" transform="scale(51.874) matrix(1 0 0 -1 0 0)">对</text><g transform="translate(1675,0)"><text font-family="STIXGeneral, 'PingFang SC', serif" stroke="none" transform="scale(51.874) matrix(1 0 0 -1 0 0)">求</text></g><g transform="translate(2482,0)"><text font-family="STIXGeneral, 'PingFang SC', serif" stroke="none" transform="scale(51.874) matrix(1 0 0 -1 0 0)">两</text></g><g transform="translate(3290,0)"><text font-family="STIXGeneral, 'PingFang SC', serif" stroke="none" transform="scale(51.874) matrix(1 0 0 -1 0 0)">次</text></g><g transform="translate(4097,0)"><text font-family="STIXGeneral, 'PingFang SC', serif" stroke="none" transform="scale(51.874) matrix(1 0 0 -1 0 0)">期</text></g><g transform="translate(4904,0)"><text font-family="STIXGeneral, 'PingFang SC', serif" stroke="none" transform="scale(51.874) matrix(1 0 0 -1 0 0)">望</text></g><g transform="translate(5712,0)"><text font-family="STIXGeneral, 'PingFang SC', serif" stroke="none" transform="scale(51.874) matrix(1 0 0 -1 0 0)">还</text></g><g transform="translate(6519,0)"><text font-family="STIXGeneral, 'PingFang SC', serif" stroke="none" transform="scale(51.874) matrix(1 0 0 -1 0 0)">是</text></g><g transform="translate(7326,0)"><text font-family="STIXGeneral, 'PingFang SC', serif" stroke="none" transform="scale(51.874) matrix(1 0 0 -1 0 0)">等</text></g><g transform="translate(8134,0)"><text font-family="STIXGeneral, 'PingFang SC', serif" stroke="none" transform="scale(51.874) matrix(1 0 0 -1 0 0)">于</text></g><g transform="translate(8941,0)"><text font-family="STIXGeneral, 'PingFang SC', serif" stroke="none" transform="scale(51.874) matrix(1 0 0 -1 0 0)">对</text></g><g transform="translate(10616,0)"><text font-family="STIXGeneral, 'PingFang SC', serif" stroke="none" transform="scale(51.874) matrix(1 0 0 -1 0 0)">求</text></g><g transform="translate(11424,0)"><text font-family="STIXGeneral, 'PingFang SC', serif" stroke="none" transform="scale(51.874) matrix(1 0 0 -1 0 0)">期</text></g><g transform="translate(12231,0)"><text font-family="STIXGeneral, 'PingFang SC', serif" stroke="none" transform="scale(51.874) matrix(1 0 0 -1 0 0)">望</text></g></g></g></g></g></svg>
如果值不再改善,则在某一状态下,遵循当前策略采取的行为得到的值将会是最优策略下所能得到的最大值。
上述表示就满足了Bellman最优方程,说明当前策略下的状态价值就是最优状态价值:
对于所有的,都满足,因此是最优策略。
2. 策略迭代算法伪代码

PS. 算法中函数表示估计值,表示真实值。
3. 策略迭代的修改
策略迭代在每一个迭代步总是先对策略进行值函数估计,直至收敛,那我们能否在策略估计还未收敛时就进行策略改进呢?
可能有如下几种思路:
-
引入epsilon收敛
-
简单地在对策略估计迭代次之后就进行策略改进。
-
在迭代次就进行策略改进,迭代次就等同于值迭代(value iteration)。
4. 广义策略迭代(Generalized Policy Iteration)
策略迭代包括两个同时进行的交互过程,一个使得值函数(value function)与当前策略一致(策略评价 policy evaluation),另一个使得策略相对于当前值函数较贪婪(策略提升 policy improvement)。
在策略迭代中,这两个过程交替进行,每个过程在另一个过程开始之前完成,但这显然不是必需的。 例如,值迭代(value iteration)中,在每个策略提升(policy improvement)之间仅执行一次策略评估(policy evaluation)迭代。 在异步(asynchronous)动态规划时,评价和提升过程则以更精细的方式交错。 只要两个过程都持续更新所有的状态,那么最终结果通常是相同的,即收敛到最优值函数和最优策略。
使用术语——广义策略迭代(Generalized Policy iteration,GPI)来指代让策略评价和策略提升交互的一般概念,而不依赖于两个过程的粒度(granularity)和其他细节。
几乎所有强化学习方法都可以被很好地描述为GPI。也就是说,它们都具有可识别的策略 (identifiable policy)和值函数,策略 总是相对于值函数被改善,并且值函数总是趋向策略下的值函数 。
the policy always being improved with respect to the value function.
the value function always being driven toward the value function for the policy.
他们的交互过程如下所示:

如果评价过程和提升过程都稳定下来,即不再发生变化,那么值函数和策略必须都是最优的。这意味着贝尔曼最优方程成立。
还可以用两个目标来考虑GPI中评价和提升过程的相互作用,如上图所示,上面的线代代表目标 ,下面的线代表目标。目标会发生相互作用,因为两条线不是平行的。从一个策略 和一个价值函数开始,每一次箭头向上代表着利用当前策略进行值函数的更新,每一次箭头向下代表着根据更新的值函数贪婪地选择新的策略,说它是贪婪的,是因为每次都采取转移到可能的、状态函数最高的新状态的行为。最终将收敛至最优策略和最优值函数。
网友评论