美文网首页
强化学习基础篇(六)动态规划之策略迭代(2)

强化学习基础篇(六)动态规划之策略迭代(2)

作者: Jabes | 来源:发表于2020-10-15 16:29 被阅读0次

强化学习基础篇(六)动态规划之策略迭代(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. 策略迭代算法伪代码

image.png

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.

他们的交互过程如下所示:

image.png

如果评价过程和提升过程都稳定下来,即不再发生变化,那么值函数和策略必须都是最优的。这意味着贝尔曼最优方程成立。

还可以用两个目标来考虑GPI中评价和提升过程的相互作用,如上图所示,上面的线代代表目标 ​,下面的线代表目标​。目标会发生相互作用,因为两条线不是平行的。从一个策略​ 和一个价值函数​开始,每一次箭头向上代表着利用当前策略进行值函数的更新,每一次箭头向下代表着根据更新的值函数贪婪地选择新的策略,说它是贪婪的,是因为每次都采取转移到可能的、状态函数最高的新状态的行为。最终将收敛至最优策略和最优值函数。

相关文章

网友评论

      本文标题:强化学习基础篇(六)动态规划之策略迭代(2)

      本文链接:https://www.haomeiwen.com/subject/xnngpktx.html