3 基于模型的动态规划方法

3.1 基于模型的动态规划方法理论

上一章我们将强化学习的问题纳入到马尔科夫决策过程的框架下解决。一个完整的已知模型的马尔科夫决策过程可以利用元组（S，A，P，r，γ）来表示。其中S为状态集，A为动作集，P为转移概率，也就是对应着环境和智能体的模型，r为回报函数，γ为折扣因子用来计算累积回报R。累积回报公式为 ，其中0≤γ≤1，当T为有限值时，强化学习过程称为有限范围强化学习，当T=∞时，称为无穷范围强化学习。我们以有限范围强化学习为例进行讲解。

强化学习的目标是找到最优策略π使得累积回报的期望最大。所谓策略是指状态到动作的映射π：s→a，用τ表示从状态s到最终状态的一个序列τ：s t ，s t+1 …，s T ，则累积回报R （τ）是个随机变量，随机变量无法进行优化，无法作为目标函数，我们采用随机变量的期望作为目标函数，即∫R （τ）p π （τ） dτ作为目标函数。用公式来表示强化学习的目标： 。强化学习的最终目标是找到最优策略为π * ：s→u * ，我们看一下这个表达式的直观含义。

如图3.1所示，最优策略的目标是找到决策序列 ，因此从广义上来讲，强化学习可以归结为序贯决策问题。即找到一个决策序列，使得目标函数最优。这里的目标函数∫R （τ）p π （τ） dτ是累积回报的期望值，累积回报的含义是评价策略完成任务的总回报，所以目标函数等价于任务。强化学习的直观目标是找到最优策略，目的是更好地完成任务。回报函数对应着具体的任务，所以强化学习所学到的最优策略是与具体的任务相对应的。从这个意义上来说，强化学习并不是万能的，它无法利用一个算法实现所有的任务。

从广义上讲，强化学习是序贯决策问题。但序贯决策问题包含的内容更丰富。它不仅包含马尔科夫过程的决策，而且包括非马尔科夫过程的决策。在上一节，我们已经将强化学习纳入到马尔科夫决策过程MDP的框架之内。马尔科夫决策过程可以利用元组（S，A，P，r，γ）来描述，根据转移概率P是否已知，可以分为基于模型的动态规划方法和基于无模型的强化学习方法，如图3.2所示。两种类别都包括策略迭代算法，值迭代算法和策略搜索算法。不同的是，在无模型的强化学习方法中，每类算法又分为online和offline两种。online和offline的具体含义，我们会在下一章中详细介绍。

基于模型的强化学习可以利用动态规划的思想来解决。顾名思义，动态规划中的“动态”蕴含着序列和状态的变化；“规划”蕴含着优化，如线性优化，二次优化或者非线性优化。利用动态规划可以解决的问题需要满足两个条件：一是整个优化问题可以分解为多个子优化问题；二是子优化问题的解可以被存储和重复利用。前面已经讲过，强化学习可以利用马尔科夫决策过程来描述，利用贝尔曼最优性原理得到贝尔曼最优化方程：

从方程（3.1）中可以看到，马尔科夫决策问题符合使用动态规划的两个条件，因此可以利用动态规划解决马尔科夫决策过程的问题。

贝尔曼方程（3.1）指出，动态规划的核心是找到最优值函数。那么，第一个问题是：给定一个策略π，如何计算在策略π下的值函数？其实上章已经讲过，此处再重复一遍，如图3.3所示：

图中上部大方框内的计算公式为

该方程表示，在状态s处的值函数等于采用策略π时，所有状态-行为值函数的总和。下面小方框的计算公式为状态-行为值函数的计算：

该方程表示，在状态s采用动作a的状态值函数等于回报加上后续状态值函数。

将方程（3.3）代入方程（3.2）便得到状态值函数的计算公式：

状态s 处的值函数υ π （s），可以利用后继状态的值函数υ π （s′）来表示。可是有人会说，后继状态的值函数υ π （s′）也是未知的，那么怎么计算当前状态的值函数，这不是自己抬自己吗？如图3.4所示。没错，这正是bootstrapping算法（自举算法）！

如何求解（3.4）的方程？首先，我们从数学的角度去解释方程（3.4）。对于模型已知的强化学习算法，方程（3.4）中的 ，γ和 都是已知数，π（a|s）为要评估的策略是指定的，也是已知值。方程（3.4）中唯一的未知数是值函数，从这个角度理解方程（3.4）可知，方程（3.4）是关于值函数的线性方程组，其未知数的个数为状态的总数，用 来表示。

此处，我们使用高斯-赛德尔迭代算法进行求解。即：

高斯-赛德尔迭代法的讲解请参看 3.2 节。建议读者先去学习和了解高斯-赛德尔迭代法再回来继续学习。下面我们给出策略评估算法的伪代码，如图3.5所示：

需要注意的是，每次迭代都需要对状态集进行一次遍历（扫描）以便评估每个状态的值函数。

接下来，我们举个策略评估的例子。

如图3.6所示为网格世界，其状态空间为S={1，2，…，14}，动作空间为A={东，南，西，北}，回报函数为r≡-1，需要评估的策略为均匀随机策略：

图3.7为值函数迭代过程中值函数的变化。为了进一步说明，我们举个具体的例子，如从K=1到K=2时，状态1处的值函数计算过程。

由公式（3.5）得到：

保留两位有效数字便是-1.7。

计算值函数的目的是利用值函数找到最优策略。第二个要解决的问题是：如何利用值函数进行策略改善，从而得到最优策略？

一个很自然的方法是当已知当前策略的值函数时，在每个状态采用贪婪策略对当前策略进行改善，即

如图3.8给出了贪婪策略示意图。图中虚线为最优策略选择。

如图3.9所示为方格世界贪婪策略的示意图。我们仍然以状态1为例得到改善的贪婪策略：

至此，我们已经给出了策略评估算法和策略改善算法。万事已具备，将策略评估算法和策略改善算法合起来便组成了策略迭代算法，如图3.10所示。

策略迭代算法包括策略评估和策略改善两个步骤。在策略评估中，给定策略，通过数值迭代算法不断计算该策略下每个状态的值函数，利用该值函数和贪婪策略得到新的策略。如此循环下去，最终得到最优策略。这是一个策略收敛的过程。

如图3.11所示为值函数收敛过程，通过策略评估和策略改善得到最优值函数。从策略迭代的伪代码我们看到，进行策略改善之前需要得到收敛的值函数。值函数的收敛往往需要很多次迭代，现在的问题是进行策略改善之前一定要等到策略值函数收敛吗？

对于这个问题，我们还是先看一个例子。如图3.12所示，策略评估迭代10次和迭代无穷次所得到的贪婪策略是一样的。因此，对于上面的问题，我们的回答是不一定等到策略评估算法完全收敛。如果我们在评估一次之后就进行策略改善，则称为值函数迭代算法。

值函数迭代算法（如图3.13所示）的伪代码为

需要注意的是在每次迭代过程中，需要对状态空间进行一次扫描，同时在每个状态对动作空间进行扫描以便得到贪婪的策略。

值函数迭代是动态规划算法最一般的计算框架，我们接下来阐述最优控制理论与值函数迭代之间的联系。解决最优控制的问题往往有三种思路：变分法原理、庞特里亚金最大值原理和动态规划的方法。三种方法各有优缺点。

基于变分法的方法是最早的方法，其局限性是无法求解带有约束的优化问题。基于庞特里亚金最大值原理的方法在变分法基础上进行发展，可以解决带约束的优化问题。相比于这两种经典的方法，动态规划的方法相对独立，主要是利用贝尔曼最优性原理。

对于一个连续系统，往往有一组状态方程来描述：

性能指标往往由积分给出：

最优控制的问题是

由贝尔曼最优性原理得到哈密尔顿-雅克比-贝尔曼方程：

方程（3.9）是一个偏微分方程，一般不存在解析解。对于偏微分方程（3.9），有三种解决思路：第一种思路是将值函数进行离散，求解方程（3.9）的数值解，然后利用贪婪策略得到最优控制。这对应于求解微分方程的数值求解方法；第二种思路是利用变分法，将微分方程转化成变分代数方程，在标称轨迹展开，得到微分动态规划DDP；第三种思路是利用函数逼近理论，对方程中的回报函数和控制函数进行函数逼近，利用优化方法得到逼近系数，这类方法称为伪谱的方法。

前两种方法都是以值函数为中心，其思路与值函数迭代类似，我们在此介绍前两种方法。

第一个思路：将函数进行数值离散化，也就是HJB方程的数值算法。

如图3.14所示为平面移动机器人的移动规划部分的代码，从代码中我们看到，图3.14框线内节点处的值在计算时选取的也是最小值函数。

第二个思路是采用变分法。下面我们给出DDP方法的具体推导公式和伪代码。

由贝尔曼最优性原理得

假设

令Q（δx，δu）=V （x+δx）-V （x），则Q在标称轨迹（x k ，u k ）展开：

又x k+1 =f （x k ，u k ），得到：

将（3.12）代入（3.11）可以得到：

其中：

将（3.13）视为δu的函数，则Q （δx，δu）是δu的二次函数。

如图3.15所示， 。

我们令

微分动态规划的伪代码为

●前向迭代：给定初始控制序列 ，正向迭代计算标称轨迹。

●反向迭代：由代价函数边界条件V xN ，V xxN 反向迭代计算（3.14），（3.15）和（3.16）得到贪婪策略δu * 。

●正向迭代新的控制序列：

从第二步反向迭代计算贪婪策略δu * 的过程我们可以看到，贪婪策略通过最小化值函数得到。

3.2 动态规划中的数学基础讲解

3.2.1 线性方程组的迭代解法

利用（3.4）计算策略已知的状态值函数时，方程（3.4）为一个线性方程组。因此策略的评估就变成了线性方程组的求解。线性方程组的数值求解包括直接法（如高斯消元法，矩阵三角分解法，平方根法、追赶法等）和迭代解法。策略评估中采用线性方程组的迭代解法。

1.何为迭代解法

不失一般性，用方程（3.17）表示一般的线性方程组。

所谓迭代解法是根据（3.17）式设计一个迭代公式，任取初试值 ，将其代入到设计的迭代公式中，得到 ，再将 代入迭代公式中得到 ，如此循环最终得到收敛的 。

那么，根据（3.17）式如何设计迭代公式？

（1）方法一：雅克比（Jacobi）迭代法。 [1]

雅克比迭代法假设系数矩阵的对角元素 。从（3.17）的第i个方程分离出 ，以此构造迭代方程：

方程（3.18）写成矩阵的形式为

其中：

若记 ，则迭代公式为

在进行迭代计算时，（3.18）式变为

利用迭代公式（3.20）求解线性方程组（3.17）的方法称为雅克比迭代法。矩阵B称为迭代矩阵。

雅克比迭代法解线性方程很快，还能不能更快？答案是肯定的。我们可以观察（3.21），不难发现第 次迭代计算分量 时，分量 都已经求出来了，但是在计算 时，雅克比迭代方法没有利用这些新计算出来的值。如果这些新计算出来的值能够被利用，计算速度肯定会提高，这就是高斯-赛德尔迭代法。

2.高斯-赛德尔迭代法

当求得新的分量之后，马上用来计算的迭代算法称为高斯-赛德尔迭代法。对于线性方程组，对应于雅克比迭代过程（3.21）的高斯-赛德尔迭代过程为

用矩阵的形式可表示为

写成迭代方程为

3.2.2 压缩映射证明策略评估的收敛性

首先，我们先从数学上了解什么是压缩映射（Contraction Mapping）。Contraction Mapping 中文可以译为压缩映射或压缩映像。这个概念来自于数学中的泛函分析。内容涉及不动点理论。不动点和压缩映射常用来解决代数方程，微分方程，积分方程等，为方程解的存在性、唯一性和讨论迭代收敛性证明提供有力的工具。本文用来证明迭代的收敛性。

定义：设 是度量空间，其度量用 表示。映射 ，若存在a， 使得 ，则称 上的一个压缩映射；

若存在 ，则称 的不动点。

定理1完备度量空间上的压缩映射具有唯一的不动点。

定理1是说，从度量空间任何一点出发，只要满足压缩映射，压缩映射的序列必定会收敛到唯一的不动点。因此证明一个迭代序列是不是收敛，只要证明该序列所对应的映射是不是压缩映射。

我们已经知道了什么是压缩映射，那么策略评估是如何跟压缩映射扯上关系的呢？

回答这个问题，我们还要追根溯源，看看基于模型的策略评估到底是什么东西。前面已经提过，从数学的角度来看，若将值函数看成是未知数，值函数的求解其实是解一组线性方程。为讲述方便，我们在这里再次列一下：

对这个线性方程组，我们使用的方法是高斯-赛德尔迭代：

高斯-赛德尔解线性方程组迭代收敛条件是右面的未知数矩阵的谱半径小于1，这个条件也是由压缩映射定理得来的。在这里，我们不去求系数矩阵的谱，而是找一个特殊的度量 以便简化证明，这个度量我们选为无穷范数，即

从当前值函数到下一个迭代值函数的映射可表示为

下面，我们证明该映射是一个压缩映射。

证明

因为 ，所以 是一个压缩映射，该迭代序列最终收敛到相应于策略π的值函数。上面是利用向量形式进行的推导，可能不是很直观，下面我们从值函数的定义出发进行证明。

根据图3.16，值函数公式为：

如图 3.17 中的不等式证明所示：第一个不等号对应动作值函数差绝对值 最大的那个分支；第二个不等式对应着下一级值函数差绝对值最大的那个，第三个不等号则是将 推广到整个状态空间，即放大到整个状态空间中值函数差最大的那个。

如果将值函数看成是一个向量，无穷范数是该向量中绝对值最大的那个。

3.3 基于gym的编程实例

我们在本章的3.1节中已经介绍了基于策略迭代的方法和基于值函数的方法。在本节中，我们基于Python和gym实现策略迭代方法和值迭代方法。我们仍然以机器人找金币为例，其MDP模型在上一章已经给出了介绍。这一节我们先介绍策略迭代方法，再介绍值迭代方法。

1.策略迭代方法

如3.1节中，策略迭代方法包括策略评估和策略改善。在Python中代码定义如图3.18所示。

在图3.18中，Python代码包括策略评估和策略改善两个子程序。这两个子程序交替运行，使得策略逐渐优化收敛。下面我们需要分别实现策略评估和策略改善。

首先是策略评估。

策略评估算法的伪代码由图3.5给出。图3.19中，我们给出策略评估算法的伪代码及Pyhon实现。

需要注意的一点是策略评估包括两个循环，第一个循环为 1000 次，保证值函数收敛到该策略所对应的真实值函数。第二个循环为整个状态空间的扫描，这样保证状态空间每一点的值函数都得到估计。在第二个循环中，用到了系统的模型，即，由于模型已知，因此我们确切地知道采用相应的策略后下一个状态是什么。这个性质使得智能体无需实际采用这个动作然后看下一个状态是什么，而仅仅利用模型就能预测下个状态。这个良好的性质使得智能体能预测所有的动作，而无模型的方法则没有如此好的性质——这是基于模型方法和无模型方法的本质区别。无模型的方法只能利用各种方法来估计当前的行为好坏。

有了策略评估，策略改善就比较简单了，即基于当前的值函数得到贪婪策略，将贪婪策略作为更新的策略，策略改善用公式表示为

图3.20为策略改善的Python代码，该代码包括两个循环，外循环对整个状态空间进行遍历，内循环对每个状态空间所对应的动作空间进行遍历，通过动作值函数得到贪婪策略。

整个策略改善的代码其实是为了实现公式（3.24）。

2.值迭代方法

基于策略迭代的方法是交替进行策略评估和策略改善。其中策略评估中需要迭代多次，以保证当前策略评估收敛。值迭代的方法则是在策略评估步只迭代一次。其伪代码和Python代码实现如图3.21所示。

值迭代需要三重循环，第一重大循环用来保证值函数收敛，第二重中间的循环用来遍历整个状态空间，对应着一次策略评估，第三重最里面的循环则是遍历动作空间，用来选最优动作。

3.4 最优控制与强化学习比较

当模型已知时，强化学习问题可转化为最优控制问题。本节我们给出最优控制的计算方法。一般而言，最优控制的数值计算方法分为间接法和直接法。其分类如图3.18所示。

最优控制问题的数学形式化，可由方程（3.6）和（3.8）给出。为了表述方便，我们在这里重复写下最优控制的数学形式化：

1.什么是间接法

所谓间接法，是指首先利用变分法、最大值原理或者动态规划方法得到求解最优问题的一组微分方程（如本章3.1节利用动态规划的方法得到了一组偏微分方程），之后，利用数值求解方法求出此微分方程组的解，此解即为原最优问题的解。如本文介绍的微分动态规划的方法就属于间接法。

2.什么是直接法

直接法与间接法不同，它不需要首先利用最优控制理论（如变分原理，最大值原理或动态规划方法）得到一组微分方程，而是直接在可行控制集中搜索，找到最优的解。直接方法也分为两类，一类是将状态变量和控制变量参数化，将最优控制问题转化为参数优化问题；第二类是引入函数空间中的内积与泛函的梯度，将静态的优化方法推广到函数空间中。

在直接法中，最常用的是伪谱的方法。伪谱的方法是指在正交配置点处将连续最优控制问题离散化，通过全局差值多项式逼近状态量和输入控制量，直接将最优控制问题转化为非线性规划问题，再利用非线性规划问题的各种优化方法求解。常用的伪谱方法有Gauss（高斯）伪谱法、Legendre（勒让德）伪谱法、Radau（拉道）伪谱法和Chebyshev（切比雪夫）伪谱法。

最优控制方法在那些模型已知的序贯决策问题中已经取得了很好的结果。若是你面对的问题可以用精确的模型来描述，便可直接采用最优控制的方法。至于采用最优控制的哪种方法，可根据具体问题选用。

可能有人疑惑，这本书讲的是强化学习，怎么又讲开了最优控制，是不是跑题了？

没有跑题。

最优控制经过几十年的发展，已有很多优秀的成果。在模型未知的强化学习算法中，这些优秀的成果可直接拿来应用。如何应用？在基于模型的强化学习算法中，智能体会先利用交互数据拟合一个模型，有了模型，我们就可以利用最优控制的计算方法计算当前最优解，产生当前的最优控制率。智能体会利用当前的最优控制率与环境交互，进一步优化行为。

结合最优控制的强化学习算法在机器人等领域取得了很多优秀的成果，最典型的是引导策略搜索的算法。本书第10章会详细介绍该方法。

3.5 习题

1.什么是策略迭代算法，什么是值迭代算法，两者的区别和联系是什么。

2.高斯赛德尔迭代算法和雅克比迭代算法的区别是什么。

3.利用动态规划的方法求解如下迷宫问题：

4.基于HJB方程分别用数值法和DDP的方法分别求解如下带有非完整约束使得机器人路径最优的规划问题： /uWPai8q5h8frHDaiN81ubP6Rr8MiwMjbFwOx12rEDjf8+6DklIyunWesFAlnxle