编者按：本文节选自《深度学习理论与实战：提高篇》一书，原文链接http://fancyerii.github.io/2019/03/14/dl-book/。作者李理，环信人工智能研发中心vp，有十多年自然语言处理和人工智能研发经验，主持研发过多款智能硬件的问答和对话系统，负责环信中文语义分析开放平台和环信智能机器人的设计与研发。

以下为正文。

目录

简介

策略评估(PolicyEvaluation)

策略评估代码示例

gridworld.py

PolicyEvaluation.ipynb

5.策略提升(PolicyImprovement)

策略提升定理

6.策略迭代(PolicyIteration)

7.策略迭代代码示例

8.价值迭代(ValueIteration)

9.价值迭代代码示例

10.通用策略迭代(GeneralizedPolicyIteration/GPI)

简介

动态规划是一种算法，对于简单的MDP问题可以用它来求解最优解。但是实际问题很少能用到这种算法，因为它的假设很难满足以及它计算复杂度太高了。不过学习这种算法依然很有用处，因为后面介绍的方法都想达到动态规划一样的效果，只不过它们能降低计算复杂度并且在非理想的环境下也可以使用。

这一节我们假设MDP是有限的，包括状态、行为和Reward，并且环境完全由(′,|,)确定。如果读者学习过计算机的算法课程，可能也会学到动态规划算法，它的基本思想是：一个"大"的问题的最优解，可以分解成一些小的问题，并且把小问题的的最优解的组合起来得到大问题的最优解。本书后文很多算法都是动态规划算法。

使用动态规划来解决强化学习问题的核心是使用价值函数来搜索好的策略。如果有了最优价值函数（不管是状态价值函数还是状态价值函数），我们就可以用它来计算最优的策略。最优价值函数满足如下的贝尔曼方程：

我们来理解一下这个公式，在状态s下最优的价值是什么呢？我们遍历所有可能的行为a，得到Reward值+1然后进入新的状态+1。这个过程由(′,|,)确定，所以加一个。当t+1时刻我们处于+1时，我们仍然要遵循最优的策略，所以第二项是∗(+1)。把根据期望的定义展开成求和就得到第二个等号。Q的贝尔曼方程也是类似的：

我们同样可以这样解读：在状态s采取a，Agent会得到+1和进入状态+1，在这个状态时我们有很多选择，但是我们要选择最大的那个a’。而动态规划就是根据上面的贝尔曼方程来得到迭代更新的算法。

策略评估(PolicyEvaluation)

首先我们来计算一个给定的策略的价值函数()，这叫策略评估(PolicyEvaltuion)，有时我们也把这个问题叫做预测(Prediction)问题。

其中(|)是给定策略时，在状态s下采取行为a的概率。公式的期望说明是在策略下变量+1和+1的概率。

如果环境的动力系统((′,|,))是完全已知的，而策略(|)也是已知的情况下，我们可以通过线性方程直接解出()。因为假设状态s有n种可能，那么就是n个变量，n个等式的线性方程，可以证明，如果<1，则方程有唯一解。这是一个线性代数的问题，但是这里我们会介绍一种迭代算法，这和梯度下降的思路有一些类似。因为迭代算法更容易推广到动态规划之外的算法，所以我们需要学习这种方法。下图是算法的伪代码：

图：策略评估算法伪代码

这个算法过程如下：首先把所有的0()都初始化成0，然后根据0计算1，…，一直继续下去直到收敛。根据()计算+1()的公式如下：

这个迭代算法的证明本书从略，有兴趣的读者可以参考这里。我们可以看一下收敛的时候，+1=，Δ=0，那么上面的迭代公式正好就是贝尔曼方程！有了上面的迭代算法，任何给定的策略，我们都可以计算出它的价值函数。

策略评估代码示例

接下来我们用代码来实现上面的算法，在介绍具体算法之前，先介绍GridWorld。

图：GridWorld

如上图所示，非终止状态共有14个S={1,2,…,14}，每个状态下都可以采取4个Action，A={up,down,left,right}，这些Action会确定(概率为1)的把Agent带到相应的位置，如果碰到墙了那就保持状态不变。因此(6,−1|5,ℎ)=1(7,−1|7,ℎ)=1，(10,|5,ℎ)=0。左上和右下是结束状态(迷宫出口)，如果没到结束状态，则reward是-1，因此这个任务期望Agent尽快找到出口。注意：(6,−1|5,ℎ)=1的意思是如果处于状态5并且Action是right，那么它一定会进入状态6并且reward是-1。因为概率和为1，因此(6,1.5|5,ℎ)=0，(4,−1|5,ℎ)=0。