1.4　强化学习的理论基础

本节将介绍前面讨论的概念（奖励、智能体、动作、观察和环境）以及它们的数据表示和符号。然后，将这些作为知识基础，探索RL更高阶的概念，包括状态、片段、历史、价值和收益，这些概念会在本书后面反复提到，用于描述不同的方法。

1.4.1　马尔可夫决策过程

在此之前，我们将介绍马尔可夫决策过程（Markov Decision Process，MDP），用俄罗斯套娃的方式来描述它：从最简单的马尔可夫过程（Markov Process，MP）开始，然后将其扩展成马尔可夫奖励过程（Markov reward process），最后加入动作的概念，得到MDP。

MP和MDP被广泛地应用于计算机科学和其他工程领域。因此，阅读本章除了让你对RL的上下文更熟悉外，对理解其他领域也有用。如果你已经很熟悉MDP了，那么可以快速浏览本章，只关注术语的定义即可。

马尔可夫过程

我们从马尔可夫家族最简单的MP（也称为马尔可夫链）开始。想象一下你面前有一个只能被观察的系统。能观察到的被称为状态，系统可以根据动力学定律在状态间进行切换。再强调一次，你不能影响系统，只能观察到状态的变化。

系统中所有可能的状态形成了一个集合，称为状态空间。对MP而言，状态集应该是有限的（虽然有限制，但是它可以非常大）。观察结果形成了一个状态序列或状态链（这就是MP也称为马尔可夫链的原因）。例如，看一下最简单的模型——城市的天气模型，我们可以观察到今天是晴天还是雨天，这就是状态空间。随着时间的推移，一系列观察结果形成了一条状态链，例如[晴天，晴天，雨天，晴天，……]，这称为历史。

要将这样的系统称为MP，它需要满足马尔可夫性质，这意味着系统未来的任何状态变化都仅依赖于当前状态。马尔可夫性质的重点就是让每一个可观察的状态是自包含的，都能描述系统的未来状态。换句话说，马尔可夫性质要求系统的状态彼此可区分且唯一。在这种情况下，只需要一个状态就可以对系统的未来动态进行建模，而不需要整个历史或最后N个状态。

在天气的例子中，马尔可夫性质将模型限制在这样的情况下：不管之前看到了多少个晴天，晴天之后是雨天的概率都是相同的。这个模型不太现实，因为根据常识，我们知道明天会下雨的概率不仅取决于当前的状况，还取决于许多其他因素，例如季节、纬度以及附近是否有山和海。最近有研究表明，甚至连太阳的活动都会对天气造成重大影响。所以，这个例子的假设有点太天真了，但是有助于理解限制条件并做出清醒的决定。

当然，如果想让模型变得更复杂，只需要扩展状态空间就可以了，以更大的状态空间为代价，我们可以捕获模型更多的依赖项。例如，如果要分别捕获夏天和冬天雨天的概率，将季节包含在状态中即可。

在这种情况下，状态空间将是[晴天+夏天，晴天+冬天，雨天+夏天，雨天+冬天]。

只要系统模型符合马尔可夫性质，就可以用转移矩阵来描述状态转移的概率，它是一个大小为N×N的方阵，N是模型中状态的数量。矩阵中的单元（第i行，第j列）表示系统从状态i转移到状态j的概率。

例如，在晴天/雨天的例子中，转移矩阵如下所示：

在这种情况下，如果某天是晴天，那么第二天是晴天的概率为80%，是雨天的概率为20%。如果观察到某天是雨天，那么第二天是晴天的概率是10%，第二天还是雨天的概率是90%。

MP的正式定义如下：

• 一组状态（S），系统可以处于任一状态。
• 一个转移矩阵（T），通过转移概率定义了系统的动态。

图1.4是可视化MP的有效工具，其中节点代表系统的状态，边上的标记表示状态转移的概率。如果转移的概率为0，那么我们不会画出这条边（即无法从一个状态转移到另一个状态）。这种表示法通常也用来表示有限状态机，这是自动机理论的研究范围。

再强调一次，我们仅在讨论观察。我们无法影响天气，只做观察和记录。

为了展示一个更复杂的例子，我们来考虑另外一个模型，上班族模型（迪尔伯特就是一个很好的例子，他是斯科特·亚当斯的著名漫画中的主角）。上班族的状态空间如下：

• 家：他不在办公室。
• 计算机：他在办公室用计算机工作。
• 咖啡：他在办公室喝咖啡。
• 聊天：他在办公室和同事聊天。

状态转移图如图1.5所示。

假设上班族的工作日通常从家的状态开始，并且每天到了办公室后，都毫无例外地从喝咖啡开始（没有家→计算机的边，也没有家→聊天的边）。图1.5也展示了工作日都结束（即转移到家的状态）自计算机状态。

其转移矩阵如下所示：

转移概率可以直接插入状态转移图中，如图1.6所示。

实际上，我们很少能知道确切的转移矩阵。真实世界中，一般只能得到系统状态的观察，这被称为片段：

• 家→咖啡→咖啡→聊天→聊天→咖啡→计算机→计算机→家
• 计算机→计算机→聊天→聊天→咖啡→计算机→计算机→计算机
• 家→家→咖啡→聊天→计算机→咖啡→咖啡

从观察中估算转移矩阵并不困难——将所有的状态转移计数，再将其归一化，这样总和就是1了。观察的数据越多，估算就越接近真正的模型。

还需要注意，马尔可夫性质暗示了稳定性（即所有状态的底层转移概率分布不会随着时间变化）。非稳定性意味着有一些隐藏的因素在影响系统的动态，而这些因素没有被包含在观察中。但是，这与马尔可夫性质相矛盾，后者要求同一状态的底层概率分布必须相同，和状态的转移历史无关。

注意，在片段中观察到的实际状态转移与转移矩阵中的底层概率分布是有区别的。观察的具体片段是从模型的分布中随机抽样得到的，因此片段不同，估算得到的转移分布也可能不同。而真正的状态转移概率是不变的。如果不能保证这个前提，那么马尔可夫链将不再适用。

现在我们来继续扩展MP模型，使其更接近RL问题。将奖励加入其中吧！

马尔可夫奖励过程

为了引入奖励，先对MP模型做一些扩展。首先，在状态转移之间引入价值的概念。概率已经有了，但是概率是用来捕获系统的动态的，所以现在在没有额外负担的情况下，添加一个额外的标量。

奖励能用各种形式来表示。最常用的方法是增加一个方阵，和转移矩阵相似，用i行j列来表示从状态i转移到状态j的奖励。

如前所述，奖励可正可负、可大可小。在某些情况下，这种表示方法是多余的，可以被简化。例如，如果不管起始状态是什么，奖励都是由到达状态给出的，那么可以只保留状态→奖励对，这样的表示更紧凑。但情况并不总是这样，它要求奖励必须只依赖于目标状态。

我们在模型中加入的第二个东西是折扣因子γ，它是从0到1（包含0和1）的某个数字。我们会在对马尔可夫奖励过程的其他特征都进行定义后解释它表示的意义。

你应该记得，我们会观察一个MP的状态转移链。在马尔可夫奖励过程中也是这样，但是每次转移，都加入一个新的量——奖励。现在，每次系统状态转移时，我们的观察都会加入一个奖励值。

对于每一个片段，t时刻的回报定义如下：

试着理解一下这个公式。对每个时间点来说，回报都是这个时间点后续得到的奖励总和，但是越远的奖励会乘越多的折扣因子，和t差的步数就是折扣因子的幂。折扣因子代表了智能体的远见性。如果γ是1，则回报Gt就是所有后续奖励的总和，对应的智能体会依赖后续所有的奖励来做出判断。如果γ等于0，则回报Gt就是立即奖励，不考虑后续任何状态，对应完全短视的智能体。

这些极端值只在极端情况下有用，而大多数时候，γ会设置为介于两者之间的某个值，例如0.9或0.99。这种情况下，我们会关注未来不久的奖励，但是不会考虑太遥远。在片段比较短并有限的情况下，γ=1可能会适用。

γ参数在RL中非常重要，在后续章节中会频繁出现。现在，把它想成在估算未来的回报时，要考虑多远的未来。越接近1，会考虑越多的未来。

在实践中，回报值不是非常有用，因为它是针对从马尔可夫奖励过程中观察到的一个特定状态链而定义的，所以即使是在同一个状态，这个值的变动范围也很大。但是，如果极端一点，计算出每一个状态的数学期望（对大量的状态链取平均值），就能得到一个更有用的值了，这个值被称为状态的价值：

解释起来很简单，对于每一个状态s，V(s)就是遵循马尔可夫奖励过程获得的平均（或称为期望）回报。

为了在实践中展示这些理论知识，在上班族（迪尔伯特）过程中加入奖励，将其变成迪尔伯特奖励过程（Dilbert Reward Process，DRP），奖励值如下：

• 家→家：1（回家是件好事）
• 家→咖啡：1
• 计算机→计算机：5（努力工作是件好事）
• 计算机→聊天：–3（分心不是件好事）
• 聊天→计算机：2
• 计算机→咖啡：1
• 咖啡→计算机：3
• 咖啡→咖啡：1
• 咖啡→聊天：2
• 聊天→咖啡：2
• 聊天→聊天：–1（长时间的对话变得无聊）

其状态转移图如图1.7所示。

让我们再把注意力放在γ参数上，考虑在γ不同的情况下，状态的价值会是多少。先从简单的情况开始：γ=0。要怎么计算状态的价值呢？要回答这个问题，需要先把聊天的状态固定住。随后的状态转移会是什么样的呢？答案是取决于概率。根据迪尔伯特奖过程的转移矩阵，下一个状态还是聊天的概率为50%，是咖啡的概率为20%，是计算机的概率为30%。当γ=0时，回报值就只等于下一个状态的奖励。所以，如果想计算聊天状态的价值，就只需要将所有的转移奖励乘上相应概率，并汇总起来。

V(chat) = –1×0.5 + 2×0.3 + 1×0.2 = 0.3

V(coffee) = 2×0.7 + 1×0.1 + 3×0.2 = 2.1

V(home) = 1×0.6 + 1×0.4 = 1.0

V(computer) = 5×0.5 + (–3)×0.1 + 1×0.2 + 2×0.2 = 2.8

所以，计算机是最有价值的状态（如果只考虑立即奖励的话），这并不奇怪，因为计算机→计算机的转移很频繁，而且有巨大的奖励，被打断的概率也不是很高。

还有个更棘手的问题，γ=1时价值怎么计算？仔细思考一下。答案是所有的状态的价值都是无穷大。图1.7并没有包含一个沉寂状态（不向其他状态转移的状态），而且折扣因子等于1时，未来无限次数的转移都将被考虑在内。你已经见过γ=0的情况了，所有的价值从短期来看都是正的，所以不管一开始状态的价值是多少，加上无限个正数就是一个无穷大值。

这个无穷大的结果告诉了我们为什么需要在马尔可夫奖励过程中引入γ，而不是直接将所有未来的奖励都加起来。很多情况下，转移的次数都是无限次的（或者很大的）。由于处理无穷大的值不切实际，因此需要限制计算的范围。小于1的γ就提供了这样的限制，本书后面的内容还会讨论它。如果你的环境范围有限（例如，井字棋，最多就只有9步），使用γ=1也能得到有限的价值。另外一个例子是多臂赌博机（Multi-Armed Bandit，MDP），这类环境很重要，它们只能进行一步操作。这意味着，你选择一个动作执行了一步，环境给你返回一些奖励，片段就结束了。

正如之前所提，马尔可夫奖励过程的γ通常被设置在0到1之间。但是，使用这样的值会让手工计算变得很困难，即使是迪尔伯特这样简单的马尔可夫奖励过程，因为这其中涉及成百上千个值。但计算机总是很擅长这类烦琐的任务，而且，给定转移矩阵和奖励矩阵后，有几个简单的方法能加速计算马尔可夫奖励过程的状态价值。在第5章研究Q-learning方法时，我们就能看到甚至实现一个这样的方法。

现在，我们为马尔可夫奖励过程再添加一点复杂性，是时候介绍最后一项内容了：动作。

加入动作

你可能对如何将动作加入马尔可夫奖励过程已经有些想法了。首先，必须加入一组有限的动作（A）。这是智能体的动作空间。其次，用动作来约束转移矩阵，也就是转移矩阵需要增加一个动作的维度，这样转移矩阵就变成了转移立方体。

MP和马尔可夫奖励过程的转移矩阵是方阵，用行表示源状态，列表示目标状态。所以，每一行（i）都包含了转移到每个状态的概率（见图1.8）。

现在智能体不只是消极地观察状态转移了，它可以主动选择动作来决定状态的转移。所以，针对每个源状态，现在用一个矩阵来代替之前的一组数字，深度维度包含了智能体能采取的动作，另外一个维度就是智能体执行一个动作后能转移的目标状态。图1.9展示了新的状态转移表，它是一个立方体，源状态在高度维度（用i作索引），目标状态在宽度维度（j），智能体执行的动作在深度维度（k）。

所以，通过选择动作，智能体就能影响转移到目标状态的概率，这是非常有用的。

为了解释为什么我们需要这么多复杂的东西，我们来想象一下机器人生活在3×3的网格中，可以执行左转、右转和前进的动作。状态就是指机器人的位置和朝向（上、下、左、右），共包含3×3×4=36个状态（机器人可以处在任何位置，任何朝向）。

再想象一下发动机不太好的机器人（在现实生活中很常见），当它执行左转或右转时，有90%的概率成功转到指定的朝向，但有10%的概率轮子打滑了，机器人的朝向没变。对于前进也是一样的——90%可能成功，10%机器人会停留在原地。

图1.10展示了状态转移的一部分，显示了机器人处在网格的中心并朝向上，也就是从（1，1，朝上）状态开始的所有可能转移。如果机器人试着前进，则有90%的概率落到（0，1，朝上）状态，但是也有10%的概率轮子打滑，目标位置还是（1，1，朝上）。

为了完整地捕获所有细节，包括环境以及智能体动作可能产生的反应，MDP通常会是一个三维矩阵（3个维度分别为源状态、动作和目标状态）。

最后，为了将马尔可夫奖励过程转成MDP，需要像处理状态转移矩阵一样，将动作加入奖励矩阵中去。奖励矩阵将不止依赖于状态，还将依赖于动作。换句话说，智能体获得的奖励将不止依赖于最终转移到的状态，还将依赖于促使其转移到这个状态的动作。

这和你把精力投入到某件事中很像——即使努力的结果不是很好，但你仍将习得技能并获得知识。所以即使最终的结果是一样的，做一些事总比什么都不做获得的奖励要更多一些。

有了正式定义的MDP后，终于可以来介绍MDP和RL中最重要的概念：策略。

1.4.2　策略

策略最简单的定义是一组控制智能体行为的规则。即使是特别简单的环境，也能有多种多样的策略。在前面那个机器人网格世界的例子中，智能体就可能有多种策略，能导致被访问的状态不同。例如，机器人能执行下列动作：

• 不顾一切，盲目前进。
• 通过检查前一个前进的动作是否失败来试图绕过障碍。
• 通过有意思的旋转来逗乐其创造者。
• 通过随机地选择动作来模拟在网格世界中喝醉了的机器人。

你应该还记得RL中智能体的主要目的是获得尽可能多的回报。不同的策略能给予不同的回报，所以找到一个好的策略是很重要的。因此策略的概念很重要。

策略的正式定义就是每个可能状态下的动作概率分布：

π(a|s) = P[At = a|St = s]

定义中给出的是概率而不是具体的动作，是为了给智能体的行为引入随机性。我们将在本书的后面讨论为什么这是重要、有用的。确定性策略是概率性的一个特例，只需要将指定动作的概率设置成1就可以了。

另一个有用的概念是，如果策略是固定不变的，则MDP会变成马尔可夫奖励过程，因为我们可以用策略的概率来简化状态转移矩阵和奖励矩阵，以摆脱动作的维度。

恭喜你完成了这一阶段的学习！本章很具挑战性，但是对理解后续的实践内容很重要。在完成后续两章对OpenAI Gym和深度学习的介绍后，我们将开始解决这个问题——如何教智能体解决实际任务？