第04章:动态规划
- author: zhouyongsdzh@foxmail.com
- date: 2017-11-04
- weibo: @周永_52ML
目录
0.写在前面
上一节讲到马尔科夫决策过程,并把强化学习问题用MDP框架建模。并且介绍了强化学习的目标是寻找最优策略π∗使得累计回报Gt的期望最大,累计回报Gt是个随机变量,无法当成目标函数进行优化,因为把随机变量(Gt)的期望作为目标函数。
这一节介绍基于模型的强化学习问题求解的一种算法-动态规划算法。动态规划算法是解决复杂问题的一类方法,算法通过把复杂问题分解成若干个子问题,通过求解子问题进一步得到全局问题的解。
所谓基于模型的强化学习即马尔科夫决策过程已知(即状态转移概率已知)。如果MDP未知,称为无模型(model-free)的强化学习,仍有对应的求解算法(后面章节会详细介绍)。
使用动态规划求解问题 需要满足以下条件:
- 最优化原理:问题的最优解是由所包含的子问题的解组成,且子问题的解也是最优的;
- 子问题重叠:即子问题之间不是独立的,一个子问题在下一阶段决策中可能被重复用到。
马尔科夫决策过程满足上述两个条件,即贝尔曼方程把值函数的求解表示成递归地子问题求解过程,值函数相当于存储了一些子问题的解,可以复用。
在强化学习中,动态规划是基于模型的求解最优策略和最优值函数的算法,即在已知模型的基础上判断一个策略的价值函数(策略评估过程),并在此基础上寻求最优的策略和最优价值函数(策略改进过程)。或者直接寻求最优策略和最优价值函数(价值迭代算法)。
动态规划算法属于值表法(Tabular Methods)的一种(下一章的蒙特卡洛方法也属于这一类)。值表法即值函数用表格表示,值函数的参数为表格里的内容。
思考:如何用动态规划算法在MDP基础上求解最优策略?动态规划包括两个主要过程:预测(predict)和控制(control)。
- 预测:给定一个MDP和当前策略π,要求基于当前策略π计算价值函数Vπ;
- 控制:给定一个MDP,要 求计算最优价值函数V∗和最优策略π∗;
1. 策略评估
上一节提到,强化学习问题可以用MDP描述,并根据贝尔曼最优性原理得到贝尔曼最优化方程,即:
\begin{align} v_*(s) & = \max_{a \in \mathcal{A}} R(s,a) + \gamma \sum_{s’ \in \mathcal{S}} P(s’ |s,a) v__(s’) \\\ q__(s,a) & = R(s,a) + \sum_{s’ \in \mathcal{S}} P(s’|s,a) \max_{a’ \in \mathcal{A}} q_*(s’,a’) \end{align} \qquad (rl.4.1)
贝尔曼方程符合动态规划中的条件,在这里动态规划的核心是寻找最优值函数。一个关键的问题摆在面前:如何计算策略π下的值函数? 在第03章部分已经给出了计算公式:
vπ(s)=∑a∈Aπ(a|s)(R(s,a)+γ∑s′∈SP(s′|s,a)vπ(s′)) qπ(s,a)=R(s,a)+γ∑s′∈SP(s′|s,a)∑a′∈Aπ(a′|s′)⋅qπ(s′,a′)(rl.4.2)
可以看到状态s的值函数vπ(s)可以利用后继状态的值函数vπ(s′)来表示。后继状态值函数vπ(s′)又该如何求解呢?貌似是个没完没了的过程~~~
其实不然,对于模型已知的强化学习问题,公式(rl.4.2)中的P(s′|s,a),γ以及R(s,a)都是已知的,π(a|s)为要评估的策略是指定的,也是已知值。公式(rl.4.2)中唯一的未知数是值函数,那么可以把(rl.4.2)理解为关于值函数的线性方程组,未知数的个数为状态总数,用|S|表示。
考虑到状态值函数序列v0,v1,v2,⋯,初始到值函数v0可以是任意的(除非为最终状状态值函数,值为0)。接下来的值函数都是根据贝尔曼方程得到,更新逻辑为:
vk+1(s)=Eπ[R(s,t)+γvk(St+1)|St=s] =∑a∈A(R(s,a)+γ∑s′∈SP(s′|s,a)vk(s′))(rl.4.3)
这里vk=vπ,序列{vk}最终将会收敛到vπ对应的值函数(稳定状态),这个算法称为迭代策略评估算法(Iterative Policy Evaluation)。下面给出策略评估算法的伪代码:
这部分参考教材的伪代码
$
\{ \;//\; \color{red} {迭代策略评估算法} \\\
- 输入
\\\ \}
$
[optional] 补充Gridworld示例。
策略评估算法用于根据当前策略计算每个状态的值函数的,计算值函数的目的是为了寻求最优策略。那么,如何利用状态值函数改进策略,进而得到最优策略呢?
2. 策略改进
策略改进(policy improvement)采用了比较直接的做法:在已知当前策略的值函数时,在每个状态采用贪婪策略(greedy policy)对当前策略进行改进,形式化表示如下:
π′(s)=argmax
这里\pi为当前策略,\pi’为改进后的策略。
至此,我们介绍了策略评估(依据当前策略预测值函数)和策略改进(依据贪婪策略选择最大值函数对应的策略),将二者合起来即为策略迭代算法。
3. 策略迭代
策略迭代算法包括策略评估和策略改进两个步骤。
- 策略评估:给定策略,通过数值迭代算法不断计算该策略下的值函数,直至收敛。
- 策略改进:利用收敛的值函数和贪婪策略得到新的策略;
如此循环下去,最终得到最优策略和最优值函数,是一个策略收敛的过程。策略迭代算法伪代码如下:
这部分参考教材的伪代码
$
\{ \;//\; \color{red} {策略迭代算法} \\\
- 输入
\\\ \}
$
4. 值迭代
从策略迭代算法的伪代码可以看到,每一轮迭代中,在进行策略改进之前都要得到收敛的值函数,收敛的值函数需要很多次循环才能得到。问题:进行策略改进之前一定要得到当前策略对应的收敛值函数吗?
示例:网格,迭代10次。
我们发现,当前策略迭代10次与迭代无穷次所得到的贪婪策略都是一样的。因此,对于上面的问题,不一定非得等到策略评估算法完全收敛,才进行策略改进。如果在进行一次策略评估之后就进行策略改进,称之为值函数迭代算法。 值函数迭代算法的伪代码如下:
<伪代码>
可以看到,这里每次迭代过程在策略评估阶段只对状态空间扫描一次。