David Silver 强化学习 第三讲

动态规划寻找最优策略

Posted by Pelhans on January 10, 2018

本部分我们采用动态规划在已知模型的基础上判断一个策略的价值函数,并在此基础上寻找到最优的策略和最优价值函数,或直接寻找最优策略和最优价值函数,即预测和控制问题.再通俗来讲就是一个对策略进行评估,一个是确定最优的价值函数和策略.

简介

总结自叶强的David Silver强化学习公开课中文讲解及实践专栏

什么是动态规划算法

动态算法即把一个复杂问题分解为子问题,并通过解决一个一个的子问题来求解整个问题的方法.当问题满足如下两个特性时可以采用动态规划来求解:

1:一个复杂问题的最优解由数个小问题的最优解构成,可以通过寻找子问题的最优解来得到复杂问题的最优解;
2:子问题在复杂问题内重复出现,使得子问题的解可以被存储起来重复利用;

MDP具有上述两个属性:Bellman方程把问题递归为求解子问题,价值函数就相当于存储了一些子问题的解,可以复用.因此可以采用动态规划算法来求解一类成为”规划”的问题.“规划”指的是在了解整个MDP的基础上也就是清楚模型结构的基础上来求解最优策略.

我们可以用规划来进行预测控制.

预测指的是在给定一个MDP 和策略 ,或者给定一个MRP ,要求输出基于当前策略的价值函数

控制指的是在给定一个MDP ,要求确定最优价值函数 和最优策略 .

迭代法策略评估

理论

迭代法策略评估用来评估一个给定的策略,也就是解决预测问题.可采用反向迭代应用Bellman期望方程.具体实现上可分为同步反向迭代和异步反向迭代.

同步反向迭代是在每次迭代过程中,对于第k+1次迭代,所有的状态s的价值用计算病更新该状态第k+1次迭代中使用的价值,其中是s的后继状态.该方法通过反复迭代最终将收敛至.

即在一次迭代内,状态s的价值等于前一次迭代该状态的即时奖励与所有s的下一个可能状态s’ 的价值与其概率乘积的和.

异步反向迭代是在第k次迭代使用档次迭代的状态价值来更新状态价值.

例子:方格世界

已知:

状态空间S:如图。S1 - S14非终止状态,ST终止状态,下图灰色方格所示两个位置;

行为空间A:{n, e, s, w} 对于任何非终止状态可以有东南西北移动四个行为;

转移概率P:任何试图离开方格世界的动作其位置将不会发生改变,其余条件下将100%地转移到动作指向的状态;

即时奖励R:任何在非终止状态间的转移得到的即时奖励均为-1,进入终止状态即时奖励为0;

衰减系数:1;

当前策略π:Agent采用随机行动策略,在任何一个非终止状态下有均等的几率采取任一移动方向这个行为.

问题:评估在这个方格世界里给定的策略。

该问题等同于:求解该方格世界在给定策略下的(状态)价值函数,也就是求解在给定策略下,该方格世界里每一个状态的价值。

求解:

状态价值在第153次迭代后收敛.

附加简单表述k=3时红字是如何计算的.

策略为东南西北四个方向的概率均为0.25.方式为随机行动.

向上的奖励为0,向右的奖励为-2.0,向下的奖励为-2.0,向左则原地不动,奖励-1.7.衰减系数=1.状态奖励为-1.带入公式就得右侧公式.

策略迭代

在上面的例子中,基于给定策略的价值迭代最终收敛得到的策略就是最优策略.通常情况下还需要在改善的策略上继续评估,反复多次.不过这种方法总能收敛至最优策略.

策略的优化方法为:

1) 首先在一个给定的策略下迭代更新价值函数:

2) 随后,在当前策略基础上,贪婪地选取行为,使得后继状态价值增加最多:

策略改善的理论证明

大体上来讲,就是在更新新的策略后,在当前策略下,状态s在动作下得到的q值等于当前策略下状态s所有可能动作得到的q值中的最大值。这个值一般不小于使用当前策略得到的行为所的得出的q值,因而也就是该状态的状态价值。若q值不再改善,那我们就找到了最优策略下的最大q值,此时的策略就是最优策略.

证明图:

价值迭代

优化原则

一个最优策略可以被分解为两部分:从状态s到下一个状态s’采取了最优行为 ;在状态s’时遵循一个最优策略。

定理:一个策略能够使得状态s获得最优价值,当且仅当:对于从状态s可以到达的任何状态s’,该策略能够使得状态s’的价值是最优价值:

确定性的价值迭代

在前一个定理的基础上,如果我们清楚地知道我们期望的最终(goal)状态的位置以及反推需要明确的状态间关系,那么可以认为是一个确定性的价值迭代。此时,我们可以把问题分解成一些列的子问题,从最终目标状态开始分析,逐渐往回推,直至推至所有状态。

价值迭代

用来寻找最优策略,它从初始状态价值开始同步迭代计算,最终收敛,整个过程中没有遵循任何策略,但需要知道状态间的转移概率,也就是需要知道模型.需要注意的是,与策略迭代不同,在值迭代过程中,算法不会给出明确的策略,迭代过程其间得到的价值函数,不对应任何策略。

价值迭代的优点是就算不知道目标状态在哪里,这套系统同样可以工作。它根据每一个状态的最优后续状态价值来更新该状态的最佳状态价值,这里强调的是每一个。

小结

使用状态价值函数或行为价值函数两种价值迭代的算法时间复杂度都较大,为 。一种改进方案是使用异步动态规划,其他的方法即放弃使用动态规划,随后的几讲中将详细讲解其他方法。