强化学习 3:基于模型——动态规划(Dynamic Programming)

基于动态规划的强化学习是一种【基于模型的强化学习方法】,也就是在已知模型的基础上判断一个策略的价值函数,并在此基础上寻找到最优的策略和最优价值函数,或者直接寻找最优策略和最优价值函数。

当问题具有下列特性时,通常可以考虑使用动态规划来求解:

 最优子结构性质:一个复杂问题的最优解由数个小问题的最优解构成,可以通过寻找子问题的最优解来得到复杂问题的最优解;

重叠子问题性质:子问题在复杂问题内重复出现,使得子问题的解可以被存储起来重复利用。所以动态规划经分解得到的子问题往往不是相互独立的。

马尔科夫决策过程(MDP)具有上述两个属性:Bellman方程把问题递归为求解子问题,价值函数就相当于存储了一些子问题的解,可以复用。因此可以使用动态规划来求解MDP。

DP方法和强化学习的核心思想是通过价值函数来搜索最优策略,一旦我们通过迭代更新价值函数找到了最佳价值函数,那么我们将很容易得到最优策略。

参考资料

[1] 叶强:《强化学习》第三讲 动态规划寻找最优策略

[2] 华师数据学院·王嘉宁:强化学习(四):基于表格型动态规划算法的强化学习

[3] 时雨:强化学习4:动态规划

目录

  • 预测与控制
  • 策略评估(Policy Evaluation)——估计状态价值
  • 策略提升(Policy Improvement)——估计动作价值
  • 策略迭代(Policy Iteration)
  • 价值迭代(Value Iteration)
  • 策略迭代和价值迭代的区别
  • 广义策略迭代(Generalized Policy Iteration, GPI)

1 预测与控制

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

1.1 预测问题

在给定策略下迭代计算价值函数。

给定一个MDP[公式]和策略[公式],或者给定一个MRP[公式],要求输出基于当前策略[公式]的状态价值[公式]

1.2 控制问题

给定一个MDP[公式],要求确定最优价值函数[公式]和最优策略[公式]

2 策略评估(Policy Evaluation)——估计状态价值

策略评估是指根据后续的状态价值来更新当前时刻的状态价值,是对状态价值的一种估计,也就是解决“预测”问题。

动态规划是一种有模型的算法,已经保存当前时刻所有状态以及所有可能采取的动作,因此需要通过当前已知的这些信息来预估每个状态最终的价值,也就是说,这些状态价值是一个唯一的值,只是我们并不知道具体是多少,而动态规划的目的就是去找到这个值。

那么,如何评估智能体Agent不同的状态价值呢?采用的方法就是反向迭代应用贝尔曼方程

状态价值函数的贝尔曼方程:(上一章笔记)

[公式]

其中状态[公式]是状态[公式]的下一个状态。

如果根据策略[公式],则可以用贝尔曼方程不断地对每一个状态的价值函数进行迭代:

[公式]

其中,

[公式] —— [公式]时刻状态[公式]的价值函数的第[公式]次迭代值;

[公式] —— [公式]时刻状态[公式]的价值函数的第[公式]次迭代值。

在这个迭代式中我们假定了一个近似值函数序列[公式],它们是处于收敛前的各个阶段的价值函数,这里是按照迭代顺序排列(迭代是由后往前反向迭代),和状态顺序是刚好相反的。

在这其中,我们对[公式]进行随机初始化,然后开始进行迭代更新,当[公式]时,[公式]将逐渐收敛于[公式],我们就称这个过程为【迭代策略评估】。

3 策略提升(Policy Improvement)——估计动作价值

策略提升又叫做策略控制、策略更新、策略改进。

在上面,我们用策略评估来估计状态价值,当前的值函数已经是在当前策略[公式]下的最优值函数,能够准确指示在策略[公式]下的不同状态能够获得的期望收益。

但是,当前状态未必是最佳状态,所以这就要求我们进一步进行策略提升

我们假设在状态[公式]时,我们执行一个新动作[公式](并不是在策略[公式]指导下进行),并在此后一直运行原来的策略[公式],计算其动作价值为:

[公式][公式]

我们把这个新动作 [公式] 构成的行为模式称为新策略 [公式],对比 [公式]  [公式] 的好坏就是比较[公式][公式],有可能后者就优于前者了。

实现策略提升的方法就是贪心算法(greedy algorithm):

[公式][公式]

4 策略迭代(Policy Iteration)

策略迭代就是策略评估与策略控制相互交替的过程。在这个过程中,不断更新值函数与策略,最终收敛到最优策略与最优值函数,如下:

E表示策略评估,I表示策略提升。

首先进行的是策略评估,当前仅当策略评估收敛时,才进行策略控制。

有时候不需要持续迭代至最有价值函数,可以设置一些条件提前终止迭代,比如设定一个Ɛ,比较两次迭代的价值函数平方差;直接设置迭代次数;以及每迭代一次更新一次策略等。

5 价值迭代(Value Iteration)

价值迭代是将策略评估与策略控制相结合,即在每一次迭代中直接选择最优的动作来更新当前的状态价值,这样就能保证每个状态都能够保存最好的策略。

价值迭代是由贝尔曼最优方程得到的,贝尔曼最优方程为:

[公式]

价值迭代的迭代形式为:

[公式]

与策略迭代不同,价值迭代在每一次策略评估迭代之后就紧接着进行策略提升,将两者结合地更加紧密。

6 策略迭代和价值迭代的区别

策略迭代的策略评估过程中其收敛方向是当前策略下的价值函数,然后进行策略提升来优化策略。

而价值迭代的目的更加直接,是当前状态下的最优值函数,当最优值函数得到之后,只要在其基础上采用贪心算法就可以得到最优策略。

策略迭代的收敛速度更快一些,在状态空间较小时,最好选用策略迭代方法。当状态空间较大时,价值迭代的计算量更小一些,节约内存。

7 广义策略迭代(Generalized Policy Iteration, GPI)

无论是策略迭代还是价值迭代都是融合了【策略评估】与【策略提升】两个过程的产物,我们将这种搜索智能体Agent最优策略的方法统称为广义策略迭代

几乎所有的强化学习问题都可以描述为GPI过程,因为它们都有着策略和价值函数这两个重要元素,两者相辅相成,策略的更新往往来源于价值函数,而价值函数的更新方向又是向着策略的,而当两者都处于稳定状态之后,那么值函数与策略一定已经收敛到了最优状态,它们之间的关系可以通过下图表示:

因为要遍历状态空间,DP方法往往在大规模的状态空间上不太适用,这被称之为“维度灾难”。

但是,相比于其他解决MDPs问题的方法,它又是最有效的,理论上可以搜索到最优策略。还有很多改进方法,例如异步动态规划(Asynchronous Dynamic Programming)、近似动态规划(Approximate Dynamic Programming)等等。

(待完善)