MDP中的动态规划
动态规划 (DP) 是一类优化方法，在给定一个 MDP 描述的完备环境模型的情况下，可以计算其最优策略。但它的作用有限，因为一般情况下我们无法准确的知道环境的动力学模型，此外计算量也是一个很大的问题。但 DP 提供了一个必要的基础，强化学习中很多方法都是对 DP 的一种近似，只不过降低了计算复杂度。
策略评估
首先我们考虑对于任意一个策略 $\pi$，如何计算它的状态价值函数 $V_\pi$，这一过程被称之为策略评估。考虑状态价值函数的贝尔曼方程，在环境模型已知的情况下，贝尔曼方程共有 $ |\mathcal{S}| $ 个。这些方程都是线性方程，联立解 $|\mathcal{S}|$ 个方程组就能得到 $V_\pi(s)$。
$$\begin{aligned} V_\pi(s) &= \mathbb{E}[G_t|s_t=s] \\ &= \mathbb{E}[r_{t+1}+\gamma G_{t+1} | s_t=s] \\ &=\sum_{a\in\mathcal{A}}\pi(a|s)\sum_{s’\in\mathcal{S}}p(s’|s,a)\left[r(s,a,s’)+\gamma\mathbb{E}[G_{t+1}|s_{t+1}=s’]\right] \\ &=\sum_{a\in\mathcal{A}}\pi(a|s)\sum_{s’\in\mathcal{S}}p(s’|s,a)\left[r(s,a,s’)+\gamma V_\pi(s’)\right] \end{aligned}$$
对于小规模的线性方程组，一般可以使用直接方法，例如高斯消去法和矩阵分解法。但是对于大规模的线性方程组，则会考虑迭代方法，例如雅可比迭代法、高斯-赛德尔迭代等。
不同的迭代方法只是构造了不同的迭代形式（$\boldsymbol{x}=\mathbf{B}\boldsymbol{x}+\boldsymbol{f}$），而贝尔曼方程已经是一种迭代形式了，因此可以直接进行迭代求解。现在的关键在于如何证明公式（1）所表示的迭代形式是收敛的。
此外，我们也可以使用状态-动作价值函数进行迭代计算，迭代公式就是状态-动作价值函数的贝尔曼方程：
$$\begin{aligned} Q_\pi(s,a) &= \sum_{s’\in\mathcal{S}} p(s’|s,a) \left[r(s,a,s’) + \gamma V_\pi(s’) \right] \\ &= \sum_{s’\in\mathcal{S}} p(s’|s,a) \left[r(s,a,s’) + \gamma \sum_{a’\in\mathcal{A}} \pi(a’|s’) Q_\pi(s’,a’) \right] \end{aligned}$$
一般来说，知道了 $V_\pi$，$Q_\pi$ 自然就知道了。
收敛性证明
我们定义关于策略 $\pi$ 的贝尔曼算子 $\mathcal{B}_\pi$ （Bellman Expectation Backup Operator）为
$$ \begin{aligned} {\mathcal{B}}_{\pi} U(s’)&=\sum_a \pi(a|s) \sum_{s} p(s’|s,a) \left[ r(s,a,s’)+\gamma U(s’) \right] ,\quad \forall s \in \mathcal{S} \end{aligned} $$
一个算子是一个操作，上式中贝尔曼算子是对 $U(s)$ 的操作。下面我们证明贝尔曼算子 $\mathcal{B}_\pi$ 是一个收缩映射。根据贝尔曼算子的定义，有：
$$ \begin{aligned} |\mathcal{B}_\pi U_1(s) - \mathcal{B}_\pi U_2(s)| &= \left|\sum_{a\in\mathcal{A}}\pi(a|s)\sum_{s’\in\mathcal{S}}p(s’|s,a)\left[\gamma \left(U_1(s’)-U_2(s’)\right)\right]\right|\\ &\le \gamma\sum_{a\in\mathcal{A}}\pi(a|s)\sum_{s’\in\mathcal{S}}p(s’|s,a)\left| \left(U_1(s’)-U_2(s’)\right)\right| \\ &\le \gamma\sum_{a\in\mathcal{A}}\pi(a|s)\sum_{s’\in\mathcal{S}}p(s’|s,a) \left(\max_{s^{\prime \prime}\in\mathcal{S}} |U_1(s^{\prime \prime})-U_2(s^{\prime \prime})|\right) \\ &= \gamma \max_{s^{\prime \prime}\in\mathcal{S}} |U_1(s^{\prime \prime})-U_2(s^{\prime \prime})| \\ &= \gamma ||U_1-U_2||_{\infty} \end{aligned} $$
因此，对于任意的 $s$ 都有（3）成立，（3）可以写为
$$ \lVert\mathcal{B}_\pi U_1 - \mathcal{B}_\pi U_2\rVert_{\infty} \le \gamma ||U_1-U_2||_{\infty} $$
当 $\gamma < 1$ 时贝尔曼算子是一个严格的收缩映射，下面证明序列 $\lbrace U,\mathcal{B}_\pi U,\mathcal{B}^2_\pi U,… \rbrace$ 是收敛的:
$$\begin{aligned} || \mathcal{B}^{m+1}_{\pi} U - \mathcal{B}^{m}_{\pi} U ||_{\infty} &\le \gamma \lVert \mathcal{B}^m_\pi U-\mathcal{B}^{m-1}_{\pi} U\rVert_{\infty} \\ &\le \gamma^2 ||\mathcal{B}^{m-1}_\pi U-\mathcal{B}^{m-2}_\pi U||_{\infty} \\ &\cdots\\ &\le \gamma^m ||\mathcal{B}_\pi U-U||_{\infty} \end{aligned}$$
根据（5）可得，当 $m$ 趋近于无穷时，$U_{m+1}$ 和 $U_{m}$ 的差值会趋近于 0。序列 $\lbrace U,\mathcal{B}_\pi U,\mathcal{B}^2_\pi U,…,\rbrace$ 会收敛到一个值，我们不断利用贝尔曼算子对 $V_\pi(s)$ 进行迭代，所得序列会收敛到一个不动点。
实际的策略评估算法
根据迭代法，我们一般会维护两个关于状态价值函数的数组，$V_\pi^{old},V_\pi^{new}$，然后利用贝尔曼算子交替更新两个数组。但在实际操作过程中，一般只需要维护一个数组 $V_\pi$，利用贝尔曼算子迭代时就地更新 $V_\pi$ 就行了，一般来说会收敛得更快。
那么策略评估算法如下：
策略改进
现在我们已经可以评估一个策略的好坏了，能得到一个策略的状态价值函数。现在我们考虑如何改进策略。一般来说，如果 $\pi$ 和 $\pi’$ 是任意的两个确定的策略，对任意 $s\in\mathcal{S}$，有
$$Q_\pi(s,\pi’(s))\ge V_\pi(s)$$
那么我们称 $\pi’$ 比 $\pi$ 更好或者一样好。公式（6）同时也意味着
$$V_{\pi’}(s) \ge V_{\pi}(s),\quad s\in \mathcal{S}$$
下面来进行简单的证明。
$$\begin{aligned} V_{\pi}(s) & \leq Q_{\pi}\left(s, \pi’(s)\right) \\ &=\mathbb{E}_\pi \left[r_{t+1}+\gamma V_{\pi}\left(s_{t+1}\right) \mid s_{t}=s, a_{t}=\pi’(s)\right] \\ &=\mathbb{E}_{\pi’}\left[r_{t+1}+\gamma V_{\pi}\left(s_{t+1}\right) \mid s_{t}=s\right] \\ & \leq \mathbb{E}_{\pi^\prime}\left[r_{t+1}+\gamma q_{\pi}\left(s_{t+1}, \pi^\prime\left(s_{t+1}\right)\right) \mid s_{t}=s\right] \\ &=\mathbb{E}_{\pi^\prime}\left[r_{t+1}+\gamma \mathbb{E}\left[r_{t+2}+\gamma V_{\pi}\left(s_{t+2}\right) \mid s_{t+1}, a_{t+1}=\pi^\prime\left(s_{t+1}\right)\right] \mid s_{t}=s\right] \\ &=\mathbb{E}_{\pi^\prime}\left[r_{t+1}+\gamma r_{t+2}+\gamma^{2} V_{\pi}\left(s_{t+2}\right) \mid s_{t}=s\right] \\ & \leq \mathbb{E}_{\pi^\prime}\left[r_{t+1}+\gamma r_{t+2}+\gamma^{2} r_{t+3}+\gamma^{3} V_{\pi}\left(s_{t+3}\right) \mid s_{t}=s\right] \\ & \vdots \\ & \leq \mathbb{E}_{\pi^\prime}\left[r_{t+1}+\gamma r_{t+2}+\gamma^{2} r_{t+3}+\gamma^{3} r_{t+4}+\cdots \mid s_{t}=s\right] \\ &=V_{\pi^\prime}(s) \end{aligned}$$
公式（8）告诉我们对于当前状态 $s$，只要根据 $Q_\pi(s,a)$，找到一个最优的动作，所得到的新策略的 $V_{\pi’}$ 一定会优于或者等于原始策略。注意到这里的策略是固定策略，是一张表，我们在这一步只是把表中当前状态对应的动作改了。如果对所有状态都这么操作，可以得到一个新的策略：
$$\begin{aligned} \pi’(s):&=\arg\max_{a\in\mathcal{A}} Q_\pi(s,a) \\ &=\arg\max_{a\in\mathcal{A}} \sum_{s’\in\mathcal{S}}p(s’|s,a)\left[r(s,a,s’)+\gamma V_\pi(s’)\right] \end{aligned}$$
这样构造出来的贪心策略（当前取最优）满足策略改进定理的条件——公式（8）。所以新的策略一定比原来的策略要好或者一样好。因此，公式（9）一般称之为策略改进。
证明一个迭代算法有效，一般先要证明算法能够逐渐变好，还要证明它一定会收敛到最优解。下面再来看策略改进方法是否能收敛到最优解。假设根据公式（9）得到的新策略为 $\pi’$，且假设 $\pi’$ 与 $\pi$ 一样好，即 $V_{\pi’}(s)=V_{\pi}(s),\forall s\in \mathcal{S}$，那么有：
$$\begin{aligned} V_{\pi’}(s)&= \max_{a\in\mathcal{A}} Q_\pi(s,a) \\ &=\max_{a\in\mathcal{A}} \sum_{s’\in\mathcal{S}}p(s’|s,a)\left[r(s,a,s’)+\gamma V_{\pi}(s’)\right] \\ &=\max_{a\in\mathcal{A}} \sum_{s’\in\mathcal{S}}p(s’|s,a)\left[r(s,a,s’)+\gamma V_{\pi’}(s’)\right] \end{aligned}$$
最后一个等式就是贝尔曼最优方程，因此策略改进方法能够收敛到最优策略。
目前来说我们考虑的都是确定性策略，对于随机策略来说本节说的方法也都成立。策略改进方法在随机策略的设置下也是成立的，在推导公式（8）的时候令非最优动作出现的概率为 0 即可。
策略迭代
一旦一个策略 $\pi$ 根据 $V_\pi$ 就能得到一个更好的策略。我们就可以通过计算 $V_{\pi’}$ 来得到一个更好的策略。不停的迭代就能得到最优策略。
$$\pi_0 \rightarrow V_{\pi_0} \rightarrow \pi_1 \rightarrow \cdots \rightarrow \pi_* \rightarrow V_{\star}$$
这种寻找最优策略的方法称之为策略迭代。算法流程图如下：
思考：如何使用状态-动作价值函数进行策略迭代？下面给出两个关键步骤：
- 对状态-动作价值函数进行评估：
$$Q_\pi(s,a) = \sum_{s’\in\mathcal{S}} p(s’|s,a) \left[r(s,a,s’) + \gamma \sum_{a’\in\mathcal{A}} \pi(a’|s’) Q_\pi(s’,a’) \right]$$
- 对当前策略进行改进：
$$\pi’(s) =\arg\max_{a\in\mathcal{A}} Q_\pi(s,a)$$
价值迭代
策略迭代算法的一个缺点是每一次迭代都涉及了策略评估，这本身就是一个需要多次遍历状态集合的迭代过程。
如果策略评估是迭代进行的，那么收敛到 $V_\pi$ 理论上在极限处才成立。我们是否必须等到其完全收敛，还是可以提早结束呢？其实，我们是可以提前截断策略评估的过程，提前截断策略评估过程并不影响策略迭代的收敛。一种特殊的情况就是策略评估只遍历一次，就立刻进行策略迭代，该算法被称之为价值迭代。更新公式就是把策略评估和策略迭代两个公式结合在一起：
$$V_{k+1}(s) := \max_{a\in\mathcal{A}}\sum_{s’\in\mathcal{S}} p(s’|s,a)\left[r(s,a,s’)+\gamma V_{k}(s’)\right] $$
价值迭代的算法流程如下所示：
对于状态-动作价值函数的价值迭代，可以写为：
$$Q_{k+1}(s,a) := \sum_{s’\in\mathcal{S}} p(s’|s,a) \left[r(s,a,s’) + \gamma \max_{a\in\mathcal{A}} Q_{k}(s’,a’) \right]$$
上式其实就是学习率 $\alpha=1$ 时的 Q-learning。值得注意的是，价值迭代仅仅是将贝尔曼最优方程变为一条更新规则。
收敛性证明
下面我们来证明，价值迭代也是收敛的。首先我们定义贝尔曼最优算子为 $\mathcal{B_\star}$ （Bellman optimality backup operator）：
$$\mathcal{B}_\star U(s) := \max_{a\in\mathcal{A}} \sum_{s’\in\mathcal{S}}p(s’|s,a)\left[r(s,a,s’)+\gamma U(s’)\right],\quad \forall s \in \mathcal{S}$$
那么有：
$$\begin{aligned} ||\mathcal{B}_\star U_1 - \mathcal{B}_\star U_2||_\infty &= \max_{s}\left\lbrace\left|\max_{a_1\in\mathcal{A}} \sum_{s’\in\mathcal{S}}p(s’|s,a_1)\left[r(s,a_1,s’)+\gamma U_1(s’)\right]-\max_{a_2\in\mathcal{A}} \sum_{s’\in\mathcal{S}}p(s’|s,a_2)\left[r(s,a_2,s’)+\gamma U_2(s’)\right]\right|\right\rbrace\\ &\le \max_{s}\left\lbrace\left|\max_{a_1\in\mathcal{A}} \left(\sum_{s’\in\mathcal{S}}p(s’|s,a_1)\left[r(s,a_1,s’)+\gamma U_1(s’)\right]\right)- \sum_{s’\in\mathcal{S}}p(s’|s,a_1)\left[r(s,a_1,s’)+\gamma U_2(s’)\right]\right|\right\rbrace \\ &\le \max_{s}\left\lbrace\max_{a_1\in\mathcal{A}} \left|\sum_{s’\in\mathcal{S}}p(s’|s,a_1)\left[r(s,a_1,s’)+\gamma U_1(s’)\right]- \sum_{s’\in\mathcal{S}}p(s’|s,a_1)\left[r(s,a_1,s’)+\gamma U_2(s’)\right]\right| \right\rbrace\\ &\le \gamma \max_{s}\left\lbrace \max_{a\in\mathcal{A}}\left| \sum_{s’\in\mathcal{S}}p(s’|s,a)\left[U_1(s’)-U_2(s’)\right]\right| \right\rbrace \\ &\le \gamma \max_{s}\left\lbrace\max_{a\in\mathcal{A}} \left[\sum_{s’\in\mathcal{S}}p(s’|s,a)\left|U_1(s’)-U_2(s’)\right| \right]\right\rbrace\\ &\le \gamma \max_{s}\left\lbrace \max_{a\in\mathcal{A},s’} \left\lbrace|U_1(s’)-U_2(s’)| \right\rbrace \right\rbrace\\ &= \gamma ||U_1-U_2||_{\infty} \end{aligned}$$
由此，可知 $\mathcal{B_\star}$ 是一个收缩映射。根据下式，当 $m$ 趋近于无穷时，$U_{m+1}$ 和 $U_{m}$ 的差值会趋近于 0。序列 $\lbrace U,\mathcal{B}_\star U,\mathcal{B}^2_\star U,…\rbrace$ 会收敛到一个值，我们不断利用贝尔曼算子对 $V_\star(s)$ 进行迭代，所得序列会收敛到一个不动点。
$$\begin{aligned} ||\mathcal{B}^{m+1}_\star U-\mathcal{B}^{m}_star U||_{\infty} &\le \gamma ||\mathcal{B}^{m}_\star U-\mathcal{B}^{m-1}_\star U||_{\infty} \\ &\le \gamma^2 ||\mathcal{B}^{m-1}_\star U-\mathcal{B}^{m-2}_star U||_{\infty}\\ &\cdots\\ &\le \gamma^m ||\mathcal{B}_\star U-U||_{\infty} \end{aligned}$$
唯一性证明
收敛性证明中已经表明一定存在一个不动点，下面再来证明这个不动点的唯一性。
首先，假设 $\mathcal{B}_\star$ 含有两个不动点 $U,V$，且 $U \neq V$。那么一定有 $||U-V||_{\infty}>0$。由于 $U,V$ 都是不动点，也有 $||\mathcal{B}_\star U-\mathcal{B}_\star V||_{\infty}=||U-V||_{\infty}$ 。但是，由于 $\mathcal{B}_\star$ 是一个收缩映射，根据上面的证明，有 $||\mathcal{B}_\star U-\mathcal{B}_\star V||_{\infty}\le \gamma||U-V||_{\infty} < ||U-V||_{\infty}$。因此，假设不成立。所以，不动点一定是唯一的。
唯一性表明了，满足贝尔曼最优方程的价值函数是唯一的，通过这个最优价值函数可以得到最优策略。
上面对价值迭代的收敛性和唯一性证明，也表明了贝尔曼最优方程的解是唯一的，根据价值迭代得到的价值函数一定是最优的价值函数，因此可以得到最优策略。
异步动态规划
异步动态规划是一类就地迭代的 DP 算法，这类算法使用任意可用的状态值，以任意顺序来更新状态值。在某些状态的值更新一次之前，某些状态值可能已经更新了好几次。但为了保证收敛，每个状态都必须被更新，不能忽略某些状态。这种就地迭代算法一般都是收敛的。
广义策略迭代
策略迭代包括两个同时进行的相互作用的流程：策略评估与策略改进，这两个过程交替进行。我们用广义策略迭代来表示策略评估与策略改进相互作用的思路。几乎所有强化学习方法都可以被表述位广义策略迭代（GPI）。几乎所有方法都包含明确定义的策略和价值函数，策略总是基于特定的价值函数进行改进，价值函数也始终会向对应特定策略的真实价值函数收敛。
动态规划的效率
动态规划方法对于一些大规模的问题并不是非常适用（维度灾难），但是和其他解决马尔可夫决策过程的方法相比，DP 的算法效率是相当高的。对于状态空间很大的问题，一般可以采用异步动态规划方法，问题中最优解可能只涉及状态空间中部分的状态。当前强化学习算法的大体思路本质上应该还是动态规划，只是进行了一些近似。