2.2 强化学习理论
1950年，阿兰·图灵提出了一个有趣的问题：“机器能思考吗？”，这一年，他发表了一篇划时代的论文Computing Machinery and Intelligence（计算机器与智能），首次提出了人工智能的概念，开启了人工智能的先河。智能体是人工智能中的重要概念，它泛指能够与环境进行交互并能独立思考的实体。在强化学习领域，智能体同样重要，事实上，强化学习的目的就是在智能体与环境的交互过程中训练智能体的判断执行能力。
除了智能体和环境两个组成部分，强化学习系统还必须具备四大核心要素：策略（Policy）、收益信号（Reward Signal）/奖励信号、价值函数（Value Function）及环境模型（Environment Model）。
策略：定义了学习智能体在给定时间内的行为方式。一般来讲，策略是一种从感知的环境状态到在这些状态中要采取的行动的映射，它可能是一个函数或一个查询表。策略是强化学习的核心主体，策略可以决定行为，而我们需要智能体具备的功能之一就是策略。在多数情况下，策略可能由一个或多个随机函数组成。
收益信号/奖励信号：定义了强化学习问题中的执行目标。在每个时间步长中，环境都会向智能体发送一个反馈信号，即收益值或奖励值。智能体执行动作的唯一目的是在长远的时间内最大化它所获得的总收益。因此，智能体在与环境的交互过程中，通过收益信号感知什么是好的事件、什么是坏的事件。收益信号可能是环境状态和所采取行动的随机函数。
价值函数：定义了一个状态的价值，即一个智能体从该状态开始，在未来期望积累的收益总量。如果说，收益信号告诉智能体在一次交互过程中什么是好的事件、什么是坏的事件，而价值函数则从更长远的角度评估某个状态下未来可能的收益情况，它使智能体能够更加关注未来的收益。收益与价值的关系是强化学习的重要内容，没有收益就没有价值，而价值评估是为了获得更多的价值。价值评估是强化学习算法的重要组成部分。
环境模型：定义了环境的行为模拟，或者是某种对环境的近似推断行为。在模型规划过程中，在实际经历可能的情况之前考虑未来的可能情况。使用模型和规划来解决强化学习问题的方法被称为基于模型的方法。必须说明，模型并不是强化学习的必备项，在无模型方法的过程中，强化学习可以采用试错和探索机制来训练智能体学习。
强化学习就是训练智能体“做什么才能获得最大收益”的过程，智能体不会被告知必须采取什么行为来应对某种环境状态，它必须在与环境的交互过程中通过尝试去发现哪些或者哪个动作能够产生最大的收益。智能体当前的某个动作可能会影响即时收益，而且还会影响环境的下一个状态出现，从而影响智能体之后的一系列收益。就像下象棋，每步棋都可能会让对手做出不同的反应。所以，试错和延迟收益是强化学习的两个显著特征。
强化学习对控制性任务的实现目标为：不断优化智能体在环境下采取的动作，并保证累积收益最大化。强化学习过程可以这样简单理解：智能体在某种状态下，通过策略选取执行动作，在与环境的交互过程中产生奖励和下一个状态，然后在新的状态下继续选择下一个执行动作，如此反复。然而，智能体对执行动作的选取是一个不断优化的过程，它采用持续的“交互—试错”机制来寻找最佳动作，并通过改进自身行为模式获取最大累积奖励回报。智能体与环境交互示意如图2.1所示。
图2.1 智能体与环境交互示意
2.2.1 马尔可夫决策过程
强化学习在实际中主要解决具有马尔可夫性的序贯决策问题，其中，马尔可夫性表示智能体在与环境交互过程中，下一个状态只取决于当前状态，与历史状态没有关系。设St为一个状态序列{S0，S1，S2，…，St，St+1，…}中的某个状态，我们说某个状态St是马尔可夫的（符合马尔可夫性，Markov Property），当且仅当P[St+1|St]=P[St+1|S1，S2，…，St]时成立。这就是说，下一个状态出现的概率只取决于当前状态，而与历史状态无关。如果一个强化学习任务满足马尔可夫性，我们则将其称为马尔可夫决策过程（MDP）。如果其状态空间和行为空间都是有限的，则称其为有限马尔可夫决策过程（Finite MDP）。一般我们讨论的MDP问题都是有限马尔可夫问题。
连续状态可以建模为具有马尔可夫决策过程的形式，在马尔可夫决策过程中，智能体通过执行动作改变自己和环境的状态，得到奖励或惩罚[96]。马尔可夫决策过程可以表示为四元组{S，A，P（s′|s，a），R}。
其中，S为有限状态集，S包括智能体的所有状态，即{s1，s2，s3，…，sn}∈S，智能体在通过策略π选择动作时需要考虑当前状态的情况，确保策略具有可行性和稳定性。A为动作集，A包括智能体采取的所有动作，即{a1，a2，a3，…，an}∈A。在马尔可夫决策过程中，状态之间的转移不涉及智能体的动作a，仅依赖于环境，智能体可以通过选择不同的动作a来引导状态之间的转移。P（s′|s，a）为状态转移函数，P（s′|s，a）表示在状态s时，智能体通过策略π采取动作a后，状态从s转移到s′的概率。状态转移概率包含环境中状态间固有的转移概率和动作带来的转移概率。R为奖励函数，R表示智能体在状态s时采取动作a，环境根据当前状态给出的奖励，可以表示为R（s，a）或R（s）。
在离散时间序列t=0，1，2，3，…中，智能体根据t时刻的状态s，通过策略π选择动作a，在与环境交互的过程中获得立即奖励R（s，a），并根据状态转移函数P（s′|s，a）得到下一时刻的环境状态s′。状态转移过程如图2.2所示。
图2.2 状态转移过程
在马尔可夫决策过程中，可通过设置奖励函数引导智能体选择“正确”的动作，强化学习目标，即在不同状态下，智能体根据策略π输出最优动作，使最终获得的累积回报最大。累积回报可用式（2.1）表示为
其中，Rt+1表示智能体在st时，通过策略π采取动作at，在与环境交互后获得的立即奖励。γ表示衰减因子，γ∈[0，1]，γ越小，表明智能体越依赖当前奖励；γ越大，表明智能体越关注未来状态获取的奖励。γ的值需要根据环境的变化情况来设定。
在马尔可夫决策过程中，价值函数是关于状态的函数，用来表示智能体对未来奖励的一个预测。未来奖励的多少取决于智能体所选择的动作，与价值函数相关的产生动作的方式称为策略，强化学习中策略的输出形式主要分为：确定性策略（Deterministic Policy）和随机性策略（Stochastic Policy）。确定性策略指输入状态s，策略给出一个确定动作a，确定性策略用式（2.2）表示为
随机性策略指输入状态s，输出动作分布，在状态s下，每个动作都以一定的概率被选取，随机性策略需要满足式（2.3），即
在有限马尔可夫决策过程中，将智能体在状态s和策略π下获得回报的期望值定义为状态价值函数Vπ（s）。同理，将智能体在状态s和策略π下采取动作a获得回报的期望值定义为动作状态价值函数Qπ（s，a）。状态价值函数和动作状态价值函数分别表示为式（2.4）、式（2.5）：
在Vπ（s）的基础上，Qπ（s，a）表示在状态s下选择动作a，然后遵循策略π后获得的值。因此，Vπ（s）和Qπ（s，a）之间的关系如式（2.6）和式（2.7）所示。
式（2.6）中，Vπ（s′）表示智能体在状态s′时的状态价值函数，p（s′，r|s，a）表示状态转移概率，对于任何策略π和任何状态s，s状态的价值与后续状态的价值存在递归关系。式（2.7）表示s状态下的Qπ（s，a）和s′状态下的Qπ（s′，a′）之间的关系。式（2.6）中Vπ（s）和Vπ（s′）之间的迭代关系称为基于Vπ（s）的贝尔曼方程（Bellman Equation），Vπ（s）是贝尔曼方程的唯一解。同理，式（2.7）中Qπ（s，a）和Qπ（s′，a′）之间的迭代关系称为基于Qπ（s，a）的贝尔曼方程，Qπ（s，a）是贝尔曼方程的唯一解。
强化学习的任务是通过贝尔曼方程寻找一个策略，使其能够在长期过程中获得最大的奖励收益。在有限马尔可夫决策过程中，对于所有的s∈S，π≥π1，满足
，此刻的策略为最优策略π*。因此，强化学习过程需要不断优化策略使贝尔曼方程的解达到最优。当贝尔曼方程解满足最优时，在最优策略π*下的状态价值函数和动作状态价值函数一定为最优函数，见式（2.8）：
最优确定性策略见式（2.9）：
同理，最优随机性策略见式（2.10）：
因为V*（s）是基于策略的状态价值函数，Q*（s，a）是基于策略的状态动作价值函数，它们必须满足贝尔曼方程中状态和价值的一致性；V*（s）和Q*（s，a）之间的关系定义为最优贝尔曼方程，即最优策略下各个状态的价值一定等于这个状态下最优动作的期望回报。基于V*（s）的最优贝尔曼方程和基于Q*（s，a）的最优贝尔曼方程分别用式（2.11）和式（2.12）表示：
2.2.2 动态规划
动态规划（Dynamic Programming）指的是一组算法，其在给定一个完备的具有马尔可夫决策过程的环境模型下，可用于计算最优策略。
在有限马尔可夫决策过程中，根据贝尔曼方程可以构造价值函数和状态之间的线性方程组，通过求解方程可以获得最优价值对应的策略，但是计算过程非常麻烦。动态规划是一种基于迭代思想的优化方法[97]，当环境模型的描述确定时（状态之间的转移概率已知），可以通过动态规划方法实现智能体最优策略的选择。在强化学习中动态规划的使用存在一定的局限性，主要包含两个原因：①动态规划要求对环境有一个确定的模型描述，这在实际过程中很难实现；②迭代过程计算复杂度较高。但是，动态规划方法的思想在其他强化学习方法中能够得到借鉴，通过降低计算复杂度和减弱环境模型的描述来实现最优策略选择。动态规划是利用迭代思想获取贝尔曼方程的近似解，并且实现对最优策略探索的递归过程。
1.策略评估（Policy Evaluation）
策略评估表示给定智能体的一个策略π，计算状态价值函数Vπ的过程。首先，对初始的价值函数进行随机赋值。其次，运用贝尔曼方程进行迭代，在贝尔曼方程中，γ∈[0，1]，根据压缩映射理论，贝尔曼方程最终将会收敛。基于贝尔曼方程的迭代过程如式（2.13）所示：
式（2.13）中，k=0，当k→∞时将会收敛到Vπ，这一过程称为迭代策略评估。
2.策略迭代（Policy Iteration）
策略在迭代过程中不断更新改善的过程称为策略迭代[98]。初始策略π0在贝尔曼方程迭代过程中计算出
，根据
对策略进行更新得到更优策略π1，继续通过π1计算出
，再根据
对策略进行更新得到更优的策略π2，如此往复，直到V值收敛，此时的策略必为最优策略，状态价值必为最优状态价值。在策略迭代过程中，策略更新方法通常采用贪婪策略（Greedy Policy），即选择状态价值最大时对应的动作。如果存在多个状态价值最大，采用随机方法选择其中一个策略，当状态价值收敛时，满足式（2.14）：
此时，策略π为最优策略。总的来说，策略迭代过程随机选择一个策略，计算在此策略下后续所有状态下的价值，然后采用贪婪算法更新策略，使用新的策略重复上面的过程，在不断进行策略评估和策略更新的过程中，获得最优状态价值和最优策略。
3.价值迭代（Value Iteration）
价值迭代是基于贝尔曼方程不断迭代计算状态价值的过程[99]。相比于策略迭代，价值迭代不需要等到状态价值收敛才调整策略，而是随着状态价值的迭代及时调整策略，每迭代一次，价值函数就更新一次策略，以此保证价值收敛得更快。价值函数的更新过程如式（2.15）所示：
由于策略的调整，价值每次更新都倾向于贪婪策略选择的最优策略对应的后续状态价值，故能更快收敛。
2.2.3 蒙特卡罗方法
蒙特卡罗方法（Monte Carlo Method）泛指对大量随机对象采用统计学方法估计未知特定量的计算方法。在强化学习中，蒙特卡罗方法通过平均样本收益值的方法来解决强化学习问题。具体可以采用分幕式（Episode）的方式，也就是把某段经验过程划分成多个幕，就像电影片段，不管智能体采用怎样的行为，最终一幕都会结束。价值评估和策略改进是在每一幕结束后进行的。
动态规划方法在求解强化学习中最优策略和最优价值时，需要对环境动态特性有完整的描述，包括状态之间的转移概率分布。另外，动态规划方法基于贝尔曼方程迭代，需要回溯到当前状态下所有可能的后续状态，导致对复杂问题的计算量很大。蒙特卡罗方法作为一种依靠“经验”来求解问题的算法，在强化学习中通过与环境交互得到一系列状态、动作、奖励样本序列[100]。通过对样本数据的评估，从真实经验中去学习，样本序列越多，学习效果则越好。与动态规划方法相比，其优点在于在不关注环境动态特性的情况下仍能够获得最优的策略和价值。蒙特卡罗方法在强化学习中主要解决预测问题和控制问题。预测表示通过给定策略π来求解状态价值函数V（π），控制则表示获取最优策略π*和最优价值V*。
1.蒙特卡罗预测
在有限马尔可夫决策过程中，将状态开始到结束称为一个完整的状态序列，状态的价值表示从该状态开始到结束的期望回报，即未来的折扣收益累计值的期望，如式（2.1）所示。使用蒙特卡罗方法求解在状态s的价值，是对特定状态的价值进行经验估计的过程，由于多次采集所有经过状态s所产生的回报值，并对其进行平均处理，所以随着越来越多的回报被收集，状态s的价值将收敛于平均值。蒙特卡罗求解强化学习预测问题如式（2.16）所示：
蒙特卡罗方法需要将状态产生的所有回报保存以后进行求平均值处理，在实际操作过程中会增加计算量。上述问题利用增量式更新平均值方法可以得到解决。增量式更新平均值方法指每次保存上一个样本序列中得到的均值和迭代次数，通过增量方式计算当前序列下的均值，增量式更新如式（2.17）所示：
根据式（2.17），价值函数V（St）更新如式（2.18）所示：
当采集的样本序列次数较多时，利用参数α代替T-1，α∈[0，1]，如式（2.19）所示：
同理，动作价值函数Q（St，At）的更新如式（2.20）所示：
2.蒙特卡罗控制
蒙特卡罗方法解决强化学习中的控制问题与动态规划中的价值迭代所用到的思路相似。在价值迭代中，首先给智能体一个初始的策略π0，计算出状态价值Vπ0，然后基于贪婪策略更新策略，不断重复更新策略和评估价值，最后得到最优价值函数V*和最优策略π*。蒙特卡罗方法和动态规划方法在解决强化学习控制问题时的主要区别在于：①在动态规划方法中进行策略评估时，需要根据状态转移概率和策略，通过贝尔曼方程进行计算，而在蒙特卡罗方法中则基于经验值计算；②蒙特卡罗方法一般优化最优动作价值函数Q*，而不是状态价值函数V*；③动态规划方法中价值迭代过程通常采用贪婪策略来选取最大状态价值所对应的动作；蒙特卡罗方法通常采用ε贪婪策略（ε-Greed Policy），ε为训练迭代过程中的探索率，在价值迭代过程中如果一直采用当前轮最大价值对应的动作，会导致一些较好的没有执行过的动作被忽略，故需要设置一定的概率ε选择其他动作。ε贪婪策略在强化学习算法中被广泛应用，相比于贪婪策略，ε贪婪策略能够增加动作的探索率，避免陷入局部最优。在使用ε贪婪策略选取动作时，设定ε为一个较小的值，使用
的概率选择目前认为是最大价值对应的动作，而用
的概率随机地从m个可选动作中选择非贪心动作，ε贪婪策略对选中贪心动作和非贪心动作的概率如式（2.21）所示：
2.2.4 时间差分学习
时间差分学习（Temporal-Difffference Learning）是强化学习理论中的重要思想，它是蒙特卡罗思想和动态规划思想的结合。与蒙特卡罗方法一样，时间差分学习方法可以直接从原始经验中学习，不需要建立环境的动态模型。
动态规划方法在强化学习中基于已得到的其他状态的价值估计值来更新当前状态的价值，但是需要依靠环境的概率转换模型来进行计算；蒙特卡罗方法不需要环境的状态转换概率模型，完全依靠经验值来学习更新价值，但是它需要从完整的采样序列中学习。以上两种方法在解决强化学习问题时都存在一定的弊端。时间差分学习结合动态规划和蒙特卡罗思想，采用样本经验进行学习，不基于环境的状态转移概率，利用经验中后一个价值来更新前一个价值。时间差分学习在解决预测问题时需要从给定的策略π映射出价值函数Vπ；在解决控制问题时需要对策略和价值不断更新并评估，确定最优策略π*和最优动作价值函数Q*。
1.时间差分学习预测
时间差分学习在处理预测问题时与蒙特卡罗方法相似，都是依据经验来实现对价值的评估的。时间差分学习在蒙特卡罗方法的基础上做了改进，将下一时刻的价值作为目标进行估计。时间差分学习在构造更新目标时与蒙特卡罗方法有一定的差异，蒙特卡罗方法中更新的目标Gt如式（2.1）所示，在时间差分学习中将Gt定义为式（2.22）。
其中，Rt+1表示从状态St转移到St+1获得的立即奖励，γ表示折扣因子，V（St+1）表示St+1时的状态价值，即使用状态转移后获得的立即奖励和下一状态的状态价值来实现状态价值的更新。因此，时间差分学习的价值函数更新如式（2.23）所示：
同理，利用时间差分学习更新动作价值函数Q（St，At）如式（2.24）所示：
在时间差分学习中，将Rt+1+γV（St+1）称为时间差分（Temporal-Difference，TD）目标值，将Rt+1+γV（St+1）-V（St）称为TD误差，用TD目标值代替Gt的过程为引导（Bootstrapping）。蒙特卡罗方法和时间差分学习在处理强化学习预测问题时有以下区别：①时间差分学习可以在一个不完整的状态序列下进行学习，即更新状态时可以通过后一个状态的预估价值和状态转移获得的立即奖励来对当前价值进行更新，不需要像蒙特卡罗方法一样必须完成一个完整的状态序列才可以进行价值更新；②时间差分学习中使用TD目标值代替Gt更新状态价值，属于对当前状态价值的有偏估计，方差小，而蒙特卡罗方法则使用实际的回报来更新状态价值，属于无偏估计，方差大。
2.时间差分学习控制
时间差分学习在解决强化学习中的控制问题时，根据Gt的获得方式主要分为两种情况。第一种情况是在线On-Policy控制，通过ε贪婪策略来选择新的动作，然后更新价值函数；第二种情况是离线Off-Policy控制，通过ε贪婪策略选择新的动作，通过贪婪策略更新价值函数。基于在线控制选择动作的策略与即将更新的策略一致，策略靠本身生成的数据进行更新。离线控制具备两个策略：行为策略（Behavior Policy）和目标策略（Target Policy），行为策略负责样本数据的获取，随机选取动作，有一定的概率选出最优动作；目标策略是在行为策略收集的样本基础上进行策略提升，并最终成为最优策略的。
2.2.5 强化学习算法概述
以时间差分学习理论为基础的强化学习算法包括具有在线控制特点的SARSA算法[101]、具有离线控制特点的Q-Learning算法等。在线控制一直使用一个策略（ε贪婪策略）来更新价值函数和选择新的动作。离线控制使用两个控制策略（ε贪婪策略和贪婪策略），其中，一个策略用于选择新的动作，另一个策略用于更新价值函数。
1.SARSA算法
SARSA算法是一种基于在线控制的经典强化学习算法，在当前状态下通过ε贪婪策略选择输出动作，智能体执行动作后与环境交互产生新的状态和即时奖励，同样采用ε贪婪策略更新上一个时刻的状态价值函数。SARSA算法的更新规则如式（2.25）所示：
式中，α为学习率；γ为折扣因子；Q（st，at）为智能体在st状态（st∈S），根据ε贪婪策略采取动作at（at∈A）获得收益的期望；Q（st+1，at+1）的获取方式同上；rt为智能体在与环境交互过程中获得当前时刻的立即奖励；rt+γQ（st+1，at+1）为TD目标；rt+γQ（st+1，at+1）-Q（st，at）为TD误差。该算法的原理是将智能体在st状态和采取的动作at构成Q表格，在迭代运算过程中选用下一个状态对应的状态—动作值函数来更新Q表格，最终在Q表格中选择状态价值对应的输出动作。SARSA算法流程如算法2.1所示。
2.Q-Learning算法
Q-Learning算法是一种使用时间差分求解强化学习控制问题的方法。相比于SARSA算法，Q-Learning算法采用ε贪婪策略来选择智能体的执行动作，采用贪婪策略来更新价值函数，算法在迭代更新时会考虑所有可能的动作，并利用贪婪策略选择最大的函数值进行更新计算。状态价值函数的更新过程为：智能体在当前状态执行动作后与环境交互产生新的状态和即时奖励，并利用贪婪策略更新上一时刻的状态价值函数。Q-Learning算法的更新规则如式（2.26）所示：
式中，α∈[0，1]为学习率；γ为折扣因子，
为在状态st+1下使用贪婪策略获取的最大的状态价值。Q-Learning算法和SARSA算法的优点在于不用考虑环境模型，可以直接比较所有可用动作带来的状态价值，并用迭代运算的方式更新状态价值，获得最优输出策略。Q-Learning算法流程如算法2.2所示。
