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