3 大规模状态空间中的动态规划和强化学习问题本章我们将讨论大规模状态空间中的动态规划和强化学习问题。

对于这类问题，我们一般很难求得问题的精确解，只能得到问题的近似解。

前面章节所介绍的一些算法，如值迭代、策略迭代和策略搜索，无法直接用于这类问题。

因此，本章将函数近似引入这些算法，提出三类基于函数近似的算法版本，分别是近似值迭代、近似策略迭代和近似策略搜索。

本章将从理论和实例两个角度分析算法的收敛性，讨论如何获取值函数逼近器的方法，最后比较分析三类算法的性能。

3.1 介绍第二章详细介绍了DP/RL中三类经典算法，这三类算法都需要有精确的值函数及策略表示。

一般来说，只有存储每一个状态动作对回报值的估计值才能得到精确地Q值函数，同样V值函数只有存储每一个状态的回报值的估计值才能得到；精确的策略描述也需要存储每一个状态对应的动作。

如果值函数中某些变量，比如某些状态动作对、状态等，存在很多个或者无穷多个潜在值（又或者这些值是连续的），那么我们就无法精确描述对应的Q值函数或者V值函数，因此，考虑将值函数和策略通过函数近似的方式来表示。

由于实际应用中大部分问题都存在大规模或者连续状态空间，因此，函数近似方法是求解动态规划和强化学习问题的基础。

逼近器主要可以分为两大类：带参的和非参的。

带参的逼近器主要是从参数空间到目标函数空间的映射。

映射函数及参数的个数由先验知识给定，参数的值由样本数据进行调整。

典型的例子是对一组给定的基函数进行加权线性组合，其中权重就是参数。

相比之下，非参的逼近器通过样本数据直接得到。

本质上，非参的函数逼近器也是含带参数的，只是不像带参的函数逼近器，参数的个数及参数的值直接有样本数据决定。

例如，本书中所讨论的基于核函数的逼近器就是带参数的函数逼近器，它为每一个数据点定义一个核函数，并对这些核函数做加权线性组合，其中权重就是参数。

本章主要对大规模状态空间中动态规划和强化学习问题进行广泛而深入的讨论。

第二章中所介绍的三类主要算法，值迭代、策略迭代和策略搜索，将与函数近似方法相结合，获得三类新的算法，分别是近似值迭代、近似策略迭代以及近似策略搜索。

本章将从理论和实例两个角度讨论算法的收敛性，并对比分析三类算法的性能。

关于值函数近似与策略逼近的一些其他重要问题，本章也将给予讨论。

为了帮助读者更好的阅读本章的内容，图3.1给出一个本章的内容脉络图。

图 3.1 本章内容脉络图。

其中实线指示的是推荐阅读顺序，虚线指示的是可选的阅读顺序3.2节给出大规模连续状态空间中，基于函数近似的动态规划及强化学习算法的前提条件。

函数近似不仅仅是关于值函数或者策略的近似表示，在动态规划和强化学习算法的其他方面，函数近似也起着很重要的作用。

在3.3节，我们将介绍带参的、非参的函数近似的构架，并对两种函数逼近器进行对比分析。

接下来，3.4节和3.5节分别介绍了近似值迭代和近似策略迭代；3.6节介绍如何自动获取值函数逼近器的方法，这在近似值迭代和近似策略迭代中很重要；3.7将对近似策略搜索给出详细的介绍。

将这三类算法中的典型算法用于直流马达最优控制实例，从实例角度分析三类算法的收敛性。

本章结束之前，3.8节对三类算法进行对比分析，3.9节对本章内容给出一个总结。

为了适当缩小本章所讨论的范围，对于本章的内容，我们给出几点限制：（1）本章所提到的值函数近似，我们特指Q值函数近似及基于Q值函数的算法，因为本书大部分章节都是关于讨论关于Q值函数的算法。

（2）本章我们将介绍带参数的函数近似方法，因为本书的后续章节都是基于带参的函数近似方法介绍的，但是我们也将简单回顾下在值迭代和策略搜索中的非参函数近似方法。

（3）当我们在介绍带参的函数近似方法时，我们考虑的是更一般的参数化方法（非线性的参数化方法）。

但是，有时我们会重点介绍线性的参数化方法，因为这类算法通常能更容易从理论的角度保证其收敛性。

接下来，我们再详细介绍下文章主要内容的组织架构。

本章主要包含3.4节的近似值迭代、3.5节的近似策略迭代以及3.7节的近似策略搜索。

另外，图3.2用一种树形的方式给出本章所介绍算法的组织架构。

树形结构中所有的终端（右侧）节点所表示的算法都是3.4、3.5及3.7节中的子章节。

当然，图3.2并没有给出关于所有算法的很详细的分类。

在近似值迭代中，首先介绍带带参数的近似值迭代算法，并分为基于模型的和模型无关的两类近似算法。

然后，简单回顾非参的近似值迭代算法。

近似策略迭代主要包含两个显著地问题：近似策略评估，主要对给定的策略确定一个近似值函数，以及策略改进。

除了这两个问题，近似策略迭代提出很多有意思的理论问题，因为比如像近似值迭代，它主要是求出一个关于Bellman等式的近似解。

为此，不得不给定一些特定的条件确保近似解存在，并通过恰当的算法可以求得这个近似解。

相反，策略改进仅仅是在动作空间的基础之上求解一个极大化问题，且这类问题通常在技术上更容易实现（当然，在动作空间很大的时候，这类问题也比较难以求解）。

因此，在本章我们将重点关注近似策略评估。

首先，像介绍近似值迭代一样，我们给出一类近似策略评估的算法。

然后，我们介绍基于线性函数近似的模型无关策略评估算法，并简单回顾基于非参的近似策略评估算法。

另外，我们介绍一种基于模型的策略评估算法，它通过Monte Carlo方法直接对参数进行估计，这种方法被称为“Rollout（滚动求解算法）”。

在3.7节的近似策略搜索中，我们将依次讨论基于梯度和梯度无关的两类算法，用于求解最优策略。

在基于梯度的方法中，我们将重点考虑一种很重要的行动者-评论家方法。

图 3.2算法组织架构图3.2 大规模连续状态空间中函数近似的必要性在2.3节介绍的基于查询表的值迭代算法中，需要存储每一个状态或者状态动作对相应的回报值的估计值。

但是当其中某些状态对应大量或者无限个可能的值（比如对应的值是连续的）时，精确的存储每一个状态所对应的V值是无法实现的，因此，我们只能近似地表示状态值函数（V 值函数）。

同样，对于大规模或者连续状态空间问题，我们也只能近似地表示动作值函数（Q 值函数）。

在2.4节所介绍的策略迭代中，值函数以及某些策略一般也需要利用近似的方法去表示。

同样地，在2.5节的策略搜索中，当面对大规模或者连续状态空间问题时，我们也只能用近似的方法表示策略。

在强化学习或者动态规划中，函数近似并不仅仅是一种表示方法。

我们需要考虑另外两个方面。

第一，在强化学习或者动态规划中，基于样本的函数近似是一类重要的求解方法；第二，值迭代及策略迭代需要在动作空间中反复迭代求解潜在的非凹最大化问题，其中策略搜索主要用于寻找最优策略参数，在这一点上，与第一类函数近似问题存在相同的困难。

一般来讲，这些最优化问题都可以通过近似的方法求解。

接下来，我们将分别详细介绍两种函数近似。

在值函数估计中，针对上述两个方面，我们需要利用函数近似进行求解。

首先，针对第一个目的，我们来看一个例子，对于确定MDP 问题的Q 值迭代算法，也就是算法2.1。

在算法执行过程中，每一次迭代都根据公式（3.1）更新Q 值：1'(,)(,)max ((,),')l l u Q x u x u Q f x u u ργ+=+ （3.1） 当状态动作空间无限，我们无法在有限的时间里遍历更新所有的状态动作对。

相反，对于基于样本的函数近似方法，我们只需要考状态动作空间中有限的状态动作样本。

在随机MDP 问题中，我们也需要利用基于样本的更新方法进行求解。

针对第二个方面，在随机MDP 问题中，我们考虑利用基于样本的函数近似方法。

比如，在求解一般的随机MDP 问题的Q 值迭代算法中，对于每一个状态动作对(,)x u ，都需要根据公式（3.2）进行更新：1'(,)'(,){(,,')max (',')}l l x f x u u Q x u E x u x Q x u ργ+=+ 很显然，我们一般无法精确计算出公式（3.2）右侧的期望值，只能通过有限的样本根据某些方法求得期望值的估计值，比如利用Monte Carlo 方法求估计值。

因此，在强化学习算法中，我们一般通过样本求得期望值的估计值。

比如算法2.3的Q 学习算法就是一个典型的例子，其中通过随机函数近似的方法求得期望值的估计值。

在公式（3.1）、（3.2）中（或者在其他值迭代算法中），关于动作空间的极大化操作必须考虑每一个被选择的样本。

但是，在连续状态空间中，这种极大化操作是潜在的非凹最优化问题，这类问题很难求解，因此，我们只能通过近似的方式求解。

为了简化这类问题的求解，许多算法首先将连续的动作空间离散成一个有限的动作空间，然后在有限的离散动作空间上求解每一个动作的值函数，最后通过枚举的方法找出最大值。

在策略迭代中，在策略评估步，需要利用基于样本的函数近似方法求解每一个状态对应的V 值函数，原因正如前文所述。

极大化操作影响的是策略改进步，其中利用公式（2.34）迭代求解新策略1l h +：1arg max (,)l h l uh Q x u += 注意，采样以及极大化问题都最终影响算法的执行，因为算法中都需要计算V 值函数。

在策略搜索中，一些方法，比如行动者-评论家算法，由于需要估计值函数，因此也被前文所提及的采样问题所影响。

甚至对于不需要估计值函数的算法，也同样需要通过估计回报值来评估策略，这里对于回报值的评估同样也需要利用基于样本的近似方法，我们将在后面介绍这部分内容。

原则上，我们可以通过对于所有初始状态的回报值进行极大化操作获得一个策略。

然而，对于无限状态空间，我们只能估计出整个状态空间的有限子集，即有限初始状态的回报值。

此外，在随机MDP 问题中，对于所有初始状态，回报值的期望值（如公式（2.5））只能够通过有限的样本迹进行评估，比如通过Monte Carlo 方法进行评估。

除了这些采样问题，策略搜索方法必须能够在一类策略中找出最优策略。

这也是一个很难的最优化问题，这一问题一般也只能通过近似的方法求解，即得到原问题的一个近似解。

但是，这里我们只需要执行一次，不像在值迭代和策略迭代中关于动作空间的极值问题，需要考虑所有的样本。

从这个意思上来讲，与值迭代或者策略迭代相比，关于极大化问题所面临的困难对策略搜索算法的影响较小。

从另一个角度考虑，在模型无关的强化学习算法中，函数近似方法可以帮助我们求解问题。

考虑一种估计Q 值函数的值迭代算法，比如算法2.3的Q 学习算法。

不通过函数近似方法，我们需要单独估计每一个状态动作对的Q 值（假如能够在有限的时间里，对所有的状态动作对的Q 值进行估计）。

假如在学习过程中对于其中的某些状态，缺乏足够的信息或者没有任何信息，那么就无法很好地估计这些状态所关联的状态动作对的Q 值，最终导致算法在这些状态上无法得到很好的控制策略。