2.2 基于值函数的策略学习算法
强化学习任务的目标是使智能体能够通过不断调整当前策略，实现最大化长期累积奖励获得最优策略[3]。其中，用来不断调整策略的方法称为策略优化方法，也是解决强化学习任务、进行策略学习的关键步骤。本节将从定义、建模、经典算法方面详细阐述基于值函数的策略学习算法。
基于值函数的策略学习算法的优化对象是值函数，该方法早在20世纪80年代末就被提出且广泛应用于强化学习策略优化方面。在强化学习中，为了使智能体能够在当前状态下选择最佳动作执行并最终得到最优策略，具备一定的自主性，需要智能体能够评估并选择最佳动作，此时可用状态-动作值函数Q（s，a）对动作进行价值评估。具体地，在当前状态下首先计算每个状态-动作值函数 Q（s，a），然后根据计算的值函数贪婪地选择值函数最大的动作，不断迭代直至最终得到最优策略：
本节将首先介绍状态值函数Vπ（s）和状态-动作值函数Qπ（s， a）的定义，随后介绍策略迭代及值迭代框架，然后介绍一种传统的学习值函数的方法：Q-learning及 Sarsa算法，最后讲述基于最小二乘法的策略迭代算法（LSPI）。
2.2.1 值函数
值函数是学习强化学习中的最优策略的有效方法[3]。值函数可以分为两类：状态值函数Vπ（s）和状态-动作值函数Qπ（s， a）。状态值函数Vπ（s）可以用来衡量采用策略π时，状态s的价值。即状态值函数Vπ（s）是从状态 s出发，按照策略 π 采取行为得到的期望累积奖励，用公式表示为：
其中，
表示在初始状态为s1=s，策略为π（ at|st）和状态转移概率密度函数为 PT（ st+1| st， at）下的期望值。
另一类是状态-动作值函数Qπ（s， a），该值函数可以用来衡量在策略 π 下，智能体在给定状态下采取动作 a后的价值。即状态-动作值函数是从状态 s出发，采取行为 a后，根据策略 π 执行动作所得到的期望累积奖励：
其中，
是在初始状态为s1=s，采取动作a1后，按照策略π（at|st）和转移模型P T （s t+1|s t，a t）下所得到的条件期望累积奖励。可以看到状态-动作值函数与状态值函数唯一不同的是，状态-动作值函数不仅指定了初始状态，而且也指定了初始动作，而状态值函数的初始动作是根据策略产生的。值函数用来衡量某一状态或者状态-动作对的优劣，对于智能体来说，就是是否值得选择这一状态或者状态-动作对。因此，最优策略自然对应着最优值函数。
在实际算法实现时，不会按照上述定义进行计算，而是通过贝尔曼方程（Bellman Equation）进行迭代[4]。下面，我们将介绍状态值函数和状态-动作值函数的贝尔曼方程求解方法。对于任意策略 π 和任意状态 s，我们可以得到如下递归关系：
其中， s'为 s的下一状态。这就是贝尔曼方程的基本形态，它表明在策略π下，当前状态的值函数可以通过下一个状态的值函数来迭代求解。同样地，状态-动作值函数的贝尔曼方程可写成相似的形式：
其中，（s'，a'）为下一个状态-动作对。
计算值函数是为了找到更好的策略，最优状态值函数表示所有策略中值最大的值函数，即
同样地，最优状态-动作值函数可定义为在所有策略中最大的状态-动作值函数，即
。
状态值函数更新过程为：对每一个当前状态 s，执行其可能的动作 a，记录采取动作所到达的下一状态，并计算期望价值V （s），将其中最大的期望价值函数所对应的动作作为当前状态下的最优动作。最优状态值函数
刻画了在所有策略中值最大的值函数，即在状态 s下，每一步都选择最优动作所对应的值函数。
状态值函数考虑的是每个状态仅有一个动作可选（智能体认为该动作为最优动作），而状态-动作值函数是考虑每个状态下都有多个动作可以选择，选择的动作不同，转换的下一状态也不同，在当前状态下取最优动作时会使状态值函数与状态-动作值函数相等。最优状态值函数
的贝尔曼方程表明：最优策略下，状态 s的价值必须与当前状态下最优动作的状态-动作值相等，即
状态-动作值函数Q*（s， a）的最优方程为：
。
从最优值函数的角度寻找最优策略，可以通过最大化最优状态-动作值函数Q*（s， a）来获得：
2.2.2 策略迭代和值迭代
策略迭代是运用值函数来获取最优策略的方法[3]。策略迭代算法分为两个步骤：策略评估和策略改进。对一个具体的 MDP 问题，每次先初始化一个策略 π1，在每次迭代过程中，通过计算当前策略 πl下的贝尔曼方程得到状态-动作值函数
，该过程称为策略评估，具体流程如图2-2 所示。根据该值函数使用贪心策略来更新策略πl+1：
上述过程称为贪心策略改进。将上述过程不断迭代直至收敛，最终可得到最优策略：
|| πl+1 (a| s)-πl (a| s)||≤κ,∀s ∈ S,∀a ∈ A
其中 κ ＞ 0且一般取一个非常小的正数，||.||为 L2范数。
图2-2 策略迭代算法框架
以上即是强化学习中的 Actor-Critic 算法。策略改进为 Actor 部分，决定智能体的行为，而策略评估作为 Critic，用来评判智能体行为的优劣。贪心策略改进能确保策略的性能是提高的，这就是策略改进定理：
。
该定理表明，策略 πl+1的性能一定比策略 πl性能更好或等同。当且仅当
为最优状态-动作值函数，且 πl+1（a| s）与πl （ a|s）均为最优策略时等号成立。故在执行策略改进时除非当前策略已经是最优策略，否则要求将要更新的策略必须比原策略更好。
在策略迭代中，可以通过求解
的优化问题来进行策略改进，而关键部分是策略评估，即值函数的估计。在策略评估阶段，往往需要很多次迭代才能得到收敛的值函数。然而，在很多情况中，我们在值函数还没有完全收敛时得到的策略和值函数迭代无穷次所得到的策略是一样的。针对此问题，我们希望能够降低对策略评估的要求，从而提高策略迭代的收敛速度。
值迭代是求解最优策略的另一种有效方法[5]。在值迭代方法中，对于一个具体的 MDP 问题，首先初始化所有状态值函数 V（s），对每一个当前状态 s 及每个可能的动作 a，都计算采取这个动作后到达的下一个状态的期望值。取达到状态的期望值函数最大的动作 a 作为当前状态的值函数 V（s）的更新，即按照贝尔曼最优方程进行循环迭代：
直到值函数收敛，从而得到最优值函数V*（s）。最后，利用最优值函数进行一次策略更新，得到每个状态下确定性的最优策略，即
由此可见，策略迭代通常是策略评估与策略更新交替执行，直到两者均收敛，而值迭代是循环迭代寻找最优值函数，再进行一次策略提取即可，两者不需要交替执行。通常，策略迭代的收敛速度更快一些，当状态空间较小时，可选用策略迭代方法。当状态空间较大时，值迭代的计算量相对较小[5]。
综上，策略迭代和值迭代是用来解决动态规划问题的方法。动态规划就是通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。动态规划与强化学习的区别是，动态规划假设 MDP 是全知的，而强化学习中 MDP 可能是未知的。下一节，我们针对如何面对未知的 MDP求解最优策略。
2.2.3 Q-learning
本节我们从值迭代的角度，首先讲述一种学习值函数以及求解最优策略的传统方法：Q-learning[6]。值迭代是指首先学习值函数到收敛，然后利用最优值函数确定最优的贪婪策略。
根据状态-动作值函数的贝尔曼方程可以发现当前值函数的计算用到了后续状态的值函数，即用后续状态的值函数估计当前值函数，这就是bootstrapping 方法。然而，当没有环境的状态转移函数模型时，难以得到后续的全部状态，只能通过实验和采样的方法，每次实验一个后续状态 s'计算一个值函数，需要等到每次实验结束，所以学习速度慢，效率低下。因此，我们考虑在实验未结束时就估计当前值函数。时间差分法（Temporal Difference，TD）是根据贝尔曼方程求解值函数最核心的方法。根据状态-动作值函数的贝尔曼方程，Q-learning利用 TD偏差更新当前的值函数：
Q(st,at)= Q(st,at)+ α[r(st,at,st+1)+ γ maxaQ(st+1,a)-Q(st,at)]
令，δt= r（st，at，st+1）+ γmaxaQ（st+1，a）-Q（st，at）表示 TD偏差。Q-learning伪代码如图2-3所示。
图2-3 Q-learning伪代码
值得注意的是，Q-learning 采用的是异策略（off-policy）方法，即行动策略与目标策略所采用的策略不一致，其中行动策略采用 ε贪婪策略，而目标策略为贪婪策略。另外，Sarsa算法是一种与 Q-learning十分相似的算法，是基于时序差分的同策略（on-policy）方法[7]，即行动策略与目标策略所采用的策略一致，均为 ε贪婪策略。根据状态-动作值函数的贝尔曼方程，Sarsa 算法利用TD偏差采用同策略方式更新当前值函数：
Q ( st, at)=Q ( st, at)+α[ r( st, at, st+1)+ γQ(st+1,at+1)-Q(st,at)]
Sarsa算法伪代码如图2-4所示。
由此可见，Sarsa 算法先根据 ε贪婪策略采取动作 a，然后根据所采取的动作 a进行值函数的更新，即先做出动作后再更新值函数。而 Q-learning 先假设下一步采取达到状态的期望值函数最大的动作 a作为当前值函数的更新，然后再根据 ε贪婪策略采取动作，先更新值函数再采取动作。
图2-4 Sarsa算法伪代码
以上我们从值迭代的角度介绍了求解离散状态-动作问题的值函数方法，然而使用上述方法来计算每个状态-动作值函数的方法代价极大，特别是当状态-动作空间是连续的且规模很大时，会产生维度灾难，难以求解。为解决此问题，提出了值函数逼近方法[3]。接下来将介绍基于最小二乘法的策略迭代算法。
2.2.4 基于最小二乘法的策略迭代算法
基于动态规划的强化学习方法要求状态空间和动作空间不能太大且该空间是离散的。而当状态空间为连续的或维度较大时，无法直接利用上述方法解决问题，这时就需要考虑值函数逼近（Value Function Approximation）方法。值函数逼近方法更新的是值函数中的参数，因而，任意状态或状态-动作对的值都会被更新；对于上一节介绍的方法而言，值函数更新后改变的只有当前状态或状态-动作值函数。
基于最小二乘法的策略迭代算法（Least squares Policy Iteration，LSPI）是一种参数化策略迭代算法[8]，其利用线性模型估计状态-动作值函数来提高策略性能，令
是Qπ（s， a）的参数化逼近，可表示为
其中，φ（s， a）为 k维基函数，φ（s， a）=（φ1 （s， a），φ2 （s， a），…，φk （s， a）） T， ω是待估计参数。当值函数的模型确定时，适当调整参数 ω，使得值函数的估计值与真实值逼近。通过不断迭代更新参数，直到收敛。
通常在监督学习中，函数逼近使用样本的目标值作为训练集来估计函数。但是，强化学习中目标函数值不是直接可得的，必须由已收集到的路径样本计算后才能得到。此处样本是在策略 π 下，转移模型为 PT时得到的，可表示为 （s，a，r，s'）。假设在第 l次迭代中，收集 N 个样本的样本集表示为
。
现在，令
为第 l次迭代时，在策略 πl下得到的 N 个样本的值函数，将其向量化表示为：
。令
表示第 l次迭代时，其参数为 ωl，基函数为Φ的样本的值函数的估计值：
可表示为
，其中 ωl是长度为 k的列向量，基函数Φ是 N×k的矩阵：
Φ矩阵中每行代表某一样本 （s， a）基函数的值，每列表示的是所有样本对某一基函数的值。
状态-动作值函数的贝尔曼方程：
，其中
。将贝尔曼方程转化为基于 N 个样本的矩阵形式，方程变为：
其中，
和 R是 N 维向量。现在，
代替 Qπ l，使得估计值函数逼近贝尔曼方程，可得：
函数估计的目标是最小化贝尔曼残差的 L2范数，即
由于基函数的列是线性无关的，通过对上式求解，可得唯一的最优解为：
这就是目标函数的贝尔曼残差最小化逼近。得到值函数的估计后，便可根据估计的值函数进行策略的更新，这就是基于最小二乘法的策略迭代算法，算法框架如图2-5 所示。在任何给定状态 s下，使值函数的估计值在动作空间 A上最大化，可以得到该估计值函数上的贪婪策略 π。
图2-5 基于最小二乘法的策略迭代算法框架
截至目前，我们所使用到的策略更新方法都是确定性的贪心策略，但是在实际情况中，由于大规模的状态动作空间中需要探索新的状态-动作对以获得更好的策略，故随机策略相对于确定性策略更有优势。因此，在随机概率改进中考虑了所得到的策略的随机性。在这里，我们引入一个改进的随机策略技术：
其中，τ 是一个确定新策略 πl+1（a| s）随机性的参数，该策略称为吉布斯策略更新技术（Gibbs Policy Update）。
2.2.5 基于值函数的深度强化学习方法
深度强化学习以一种通用的形式将深度学习的智能感知与强化学习的决策能力相结合，直接通过高维感知输入的学习来控制智能体的行为。Minh 等人将卷积神经网络与传统 Q-learning 结合，提出新的值函数估计方法——深度 Q网络（Deep Q-learning Network，DQN）[9]。DQN 方法是深度强化学习领域的开创性工作，可以在许多 Atari 游戏中达到超乎常人的游戏水平，另外在处理基于视觉感知的控制任务方面也取得了显著成果。相比传统的 Q-learning，DQN方法新增经验回放机制和目标网络稳定训练过程。经验回放机制降低了数据间的相关性且使得样本可重用，从而提高了学习效率。该方法将连续动作空间离散化来解决连续状态空间问题，但是由于值函数的极度非凸性，智能体难以在每一个时间步都通过最大化值函数选择动作；另外，值函数由于需要对具体动作和状态评价，当动作空间连续或具有大规模动作空间时，如物理控制任务中的高维度连续动作空间，该方法往往不能有效求解。此外，动作空间的离散化会丢失关于动作空间结构的有用信息，且面临维度灾难的问题[10]。
近年，相关研究对 DQN 方法做了一系列改进，具体改进方向可分为训练算法的改进、具体网络结构的改进和引入新机制的改进等[10]。具体地，有解决Q-learning 中过高估计动作值函数的双 DQN（Double DQN，DDQN）方法[11]、减少和环境交互次数的示范深度 Q-learning[12]；解决实际应用中状态存在部分可观测性和噪声干扰的深度循环 Q 网络[13]、提高生成序列质量的增广对数先验深度 Q-learning[14]；降低深度强化学习抽样复杂度和提高算法效率的基于归一化优势函数的 DQN方法[15]等。
上述基于值函数的深度强化学习方法中的策略是通过策略迭代中的值函数间接学习得到的，然而，提高值函数逼近的质量不一定能产生更好的策略。值函数的微小变化可能会导致策略的极大变化，因此使用基于值函数的方法来控制昂贵的智能系统（如人形机器人）是不安全的。此外，基于值函数的策略学习方法难以处理连续动作空间问题，因为需要找到值函数的最大值来进行动作的选择。解决上述问题的一种方案是策略搜索算法，我们将在下一节中进行讲述。