强化学习基础

强化学习概述

强化学习（reinforcement learning，RL） 讨论的问题是智能体（agent）怎么在复杂、不确定的环境（environment）中最大化它能获得的奖励。如图 1.1 所示，强化学习由两部分组成：智能体和环境。在强化学习过程中，智能体与环境一直在交互。智能体在环境中获取某个状态后，它会利用该状态输出一个动作 （action），这个动作也称为决策（decision）。然后这个动作会在环境中被执行，环境会根据智能体采取的动作，输出下一个状态以及当前这个动作带来的奖励。智能体的目的就是尽可能多地从环境中获取奖励。

图 1.1 强化学习示意

强化学习与监督学习

我们可以把强化学习与监督学习做一个对比。以图片分类为例，如图 1.2 所示，监督学习（supervised learning）假设我们有大量被标注的数据，比如汽车、飞机、椅子这些被标注的图片，这些图片都要满足独立同分布，即它们之间是没有关联关系的。假设我们训练一个分类器，比如神经网络。为了分辨输入的图片中是汽车还是飞机，在训练过程中，需要把正确的标签信息传递给神经网络。当神经网络做出错误的预测时，比如输入汽车的图片，它预测出来是飞机，我们就会直接告诉它，该预测是错误的，正确的标签应该是汽车。最后我们根据类似错误写出一个损失函数（loss function），通过反向传播（back propagation）来训练神经网络。

图 1.2 监督学习

所以在监督学习过程中，有两个假设：

  • 输入的数据（标注的数据）都应是没有关联的。因为如果输入的数据有关联，学习器（learner）是不好学习的。
  • 需要告诉学习器正确的标签是什么，这样它可以通过正确的标签来修正自己的预测。

通常假设样本空间中全体样本服从一个未知分布，我们获得的每个样本都是独立地从这个分布上采样获得的，即独立同分布(independent and identically distributed，简称 i.i.d.)。

在强化学习中，监督学习的两个假设其实都不能得到满足。以雅达利（Atari） 游戏 Breakout 为例，如图 1.3 所示，这是一个打砖块的游戏，控制木板左右移 动从而把球反弹到上面来消除砖块。在玩游戏的过程中，我们可以发现智能体得到的观测（observation）不是独立同分布的，上一帧与下一帧间其实有非常强的 连续性。我们得到的数据是相关的时间序列数据，不满足独立同分布。另外，我 们并没有立刻获得反馈，游戏没有告诉我们哪个动作是正确动作。比如现在把木板往右移，这只会使得球往上或者往左一点儿，我们并不会得到即时的反馈。因 此，强化学习之所以困难，是因为智能体不能得到即时的反馈，然而我们依然希望智能体在这个环境中学习。

图 1.3 雅达利游戏Breakout

如图 1.4 所示，强化学习的训练数据就是一个玩游戏的过程。我们从第 1 步开始，采取一个动作，比如我们把木板往右移，接到球。第 2 步我们又做出动作，得到的训练数据是一个玩游戏的序列。比如现在是在第 3 步，我们把这个序列放进网络，希望网络可以输出一个动作，即在当前的状态应该输出往右移或 者往左移。这里有个问题，我们没有标签来说明现在这个动作是正确还是错误的，必须等到游戏结束才可能知道，这个游戏可能 10s 后才结束。现在这个动作到底对最后游戏是否能赢有无帮助，我们其实是不清楚的。这里我们就面临延迟奖励（delayed reward） 的问题，延迟奖励使得训练网络非常困难。

图 1.4 强化学习：玩Breakout

强化学习和监督学习的区别如下。

  1. 强化学习输入的样本是序列数据，而不像监督学习里面样本都是独立的。

  2. 学习器并没有告诉我们每一步正确的动作应该是什么，学习器需要自己去发现哪些动作可以带来 最多的奖励，只能通过不停地尝试来发现最有利的动作。

  3. 智能体获得自己能力的过程，其实是不断地试错探索（trial-and-error exploration）的过程。探索 （exploration）和利用（exploitation）是强化学习里面非常核心的问题。其中，探索指尝试一些新的动作， 这些新的动作有可能会使我们得到更多的奖励，也有可能使我们“一无所有”；利用指采取已知的可以获 得最多奖励的动作，重复执行这个动作，因为我们知道这样做可以获得一定的奖励。因此，我们需要在探 索和利用之间进行权衡，这也是在监督学习里面没有的情况。

  4. 在强化学习过程中，没有非常强的监督者（supervisor），只有奖励信号（reward signal），并且奖励信号是延迟的，即环境会在很久以后告诉我们之前我们采取的动作到底是不是有效的。因为我们没有得到即时反馈，所以智能体使用强化学习来学习就非常困难。当我们采取一个动作后，如果我们使用监督学习，我们就可以立刻获得一个指导，比如，我们现在采取了一个错误的动作，正确的动作应该是什么。而在强化学习里面，环境可能会告诉我们这个动作是错误的，但是它并没有告诉我们正确的动作是什么。而且更困难的是，它可能是在一两分钟过后告诉我们这个动作是错误的。所以这也是强化学习和监督学习不同的地方。

通过与监督学习的比较，我们可以总结出强化学习的一些特征。

  1. 强化学习会试错探索，它通过探索环境来获取对环境的理解。

  2. 强化学习智能体会从环境里面获得延迟的奖励。

  3. 在强化学习的训练过程中，时间非常重要。因为我们得到的是有时间关联的数据（sequential data）， 而不是独立同分布的数据。在机器学习中，如果观测数据有非常强的关联，会使得训练非常不稳定。这也 是为什么在监督学习中，我们希望数据尽量满足独立同分布，这样就可以消除数据之间的相关性。

  4. 智能体的动作会影响它随后得到的数据，这一点是非常重要的。在训练智能体的过程中，很多时 候我们也是通过正在学习的智能体与环境交互来得到数据的。所以如果在训练过程中，智能体不能保持稳 定，就会使我们采集到的数据非常糟糕。我们通过数据来训练智能体，如果数据有问题，整个训练过程就 会失败。所以在强化学习里面一个非常重要的问题就是，怎么让智能体的动作一直稳定地提升。

强化学习的例子

为什么我们关注强化学习，其中非常重要的一个原因就是强化学习得到的模型可以有超人类的表现。 监督学习获取的监督数据，其实是人来标注的，比如 ImageNet 的图片的标签都是人类标注的。因此我们 可以确定监督学习算法的上限（upper bound）就是人类的表现，标注结果决定了它的表现永远不可能超 越人类。但是对于强化学习，它在环境里面自己探索，有非常大的潜力，它可以获得超越人类的能力的表 现，比如 DeepMind 的 AlphaGo 这样一个强化学习的算法可以把人类顶尖的棋手打败。

这里给大家举一些在现实生活中强化学习的例子。

  1. 在自然界中，羚羊其实也在做强化学习。它刚刚出生的时候，可能都不知道怎么站立，然后它通过试错，一段时间后就可以跑得很快，可以适应环境。

  2. 我们也可以把股票交易看成强化学习的过程。我们可以不断地买卖股票，然后根据市场给出的反馈来学会怎么去买卖可以让我们的奖励最大化。

  3. 玩雅达利游戏或者其他电脑游戏，也是一个强化学习的过程，我们可以通过不断试错来知道怎么 玩才可以通关。

图 1.5 所示为强化学习的一个经典例子，即雅达利的 Pong 游戏。游戏中右边的选手把球拍到左边， 然后左边的选手需要把球拍到右边。训练好的强化学习智能体和正常的选手有区别：强化学习的智能体会一直做无意义的振动，而正常的选手不会做出这样的动作。

图 1.5 Pong游戏

在 Pong 游戏里面，其实只有两个动作：往上或者往下。如图 1.6 所示，如果强化学习通过学习一个策略网络来进行分类，那么策略网络会输入当前帧的图片，输出所有决策的可能性，比如往上移动的概率。

图 1.6 强化学习玩 Pong

如图 1.7 所示，对于监督学习，我们可以直接告诉智能体正确动作的标签是什么。但在 Pong 游戏中， 我们并不知道它的正确动作的标签是什么。

基于策略的智能体（policy-based agent）

图 1.7 监督学习玩 Pong

在强化学习里面，我们让智能体尝试玩 Pong 游戏，对动作进行采样，直到游戏结束，然后对每个动作进行惩罚。图 1.8 所示为预演（rollout）的一个过程。预演是指我们从当前帧对动作进行采样，生成很多局游戏。我们将当前的智能体与环境交互，会得到一系列观测。每一个观测可看成一个轨迹（trajectory）。 轨迹就是当前帧以及它采取的策略，即状态和动作的序列：

\[ \tau=\left(s_{0}, a_{0}, s_{1}, a_{1}, \ldots\right) \]

最后结束时，我们会知道到底有没有把这个球拍到对方区域，对方有没有接住，我们是赢了还是输了。我们可以通过观测序列以及最终奖励（eventual reward）来训练智能体，使它尽可能地采取可以获得最终奖励的动作。一场游戏称为一个回合（episode） 或者试验（trial）。

图 1.8 可能的预演序列

强化学习的历史

强化学习是有一定的历史的，早期的强化学习，我们称其为标准强化学习。最近业界把强化学习与深度学习结合起来，就形成了深度强化学习（deep reinforcement learning），因此，深度强化学习 = 深度学习 + 强化学习。我们可将标准强化学习和深度强化学习类比于传统的计算机视觉和深度计算机视觉。

如图 1.9a 所示，传统的计算机视觉由两个过程组成。

  1. 给定一张图片，我们先要提取它的特征，使用一些设计好的特征，比如方向梯度直方图（histogram of oriental gradient，HOG）、可变现的组件模型（deformable part model，DPM）。
  2. 提取这些特征后，我们再单独训练一个分类器。这个分类器可以是支持向量机（support vector machine，SVM）或 Boosting，然后就可以辨别这张图片是狗还是猫。

（a）传统的计算机视觉

（b）深度计算机视觉

图 1.9 传统的计算机视觉与深度计算机视觉的区别

2012年，Krizhevsky等人提出了AlexNet，AlexNet在ImageNet分类比赛中取得冠军，迅速引起了人们对于卷积神经网络的广泛关注。

大家就把特征提取以及分类两者合到一块儿去了，就是训练一个神经网络。这个神经网络既可以做特征提取，也可以做分类，它可以实现端到端训练，如图 1.9b 所示，它的参数可以在每一个阶段都得到极大的优化，这是一个非常重要的突破。

我们可以把神经网络放到强化学习里面。

  • 标准强化学习：比如 TD-Gammon 玩 Backgammon 游戏的过程，其实就是设计特征，然后训练价值函数的过程，如图 1.10a 所示。标准强化学习先设计很多特征，这些特征可以描述现在整个状态。得到这些特征后，我们就可以通过训练一个分类网络或者分别训练一个价值估计函数来采取动作。
  • 深度强化学习：自从我们有了深度学习，有了神经网络，就可以把智能体玩游戏的过程改进成一个端到端训练（end-to-end training）的过程，如图 1.10b 所示。我们不需要设计特征，直接输入状态就可以输出动作。我们可以用一个神经网络来拟合价值函数或策略网络，省去特征工程（feature engineering）的过程。

（a）标准强化学习

（b）深度强化学习

图 1.10 标准强化学习与深度强化学习的区别

序列决策

智能体与环境

接下来我们介绍序列决策（sequential decision making） 过程。强化学习研究的问题是智能体与环 境交互的问题，图 1.12 左边的智能体一直在与图 1.12 右边的
环境进行交互。智能体把它的动作输出给环境，环境取得这个动作后会进行下一步，把下一步的观测与这个动作带来的奖励返还给智能体。这样的交 互会产生很多观测，智能体的目的是从这些观测之中学到能最大化奖励的策略。

图 1.12 智能体与环境

奖励

奖励是由环境给的一种标量的反馈信号（scalar feedback signal），这种信号可显示智能体在某一步采取某个策略的表现如何。强化学习的目的就是最大化智能体可以获得的奖励，智能体在环境里面存在的目的就是最大化它的期望的累积奖励（expected cumulative reward）。不同的环境中，奖励也是不同的。这里给大家举一些奖励的例子。

  1. 比如一个象棋选手，他的目的是赢棋，在最后棋局结束的时候，他就会得到一个正奖励（赢）或 者负奖励（输）。
  2. 在股票管理里面，奖励由股票获取的奖励与损失决定。
  3. 在玩雅达利游戏的时候，奖励就是增加或减少的游戏的分数，奖励本身的稀疏程度决定了游戏的难度。

序列决策

在一个强化学习环境里面，智能体的目的就是选取一系列的动作来最大化奖励，所以这些选取的动作 必须有长期的影响。但在这个过程里面，智能体的奖励其实是被延迟了的，就是我们现在选取的某一步动作，可能要等到很久后才知道这一步到底产生了什么样的影响。如图 1.13 所示，在玩雅达利的 Pong 游戏 时，我们可能只有到最后游戏结束时，才知道球到底有没有被击打过去。过程中我们采取的上升（up）或 下降（down）动作，并不会直接产生奖励。强化学习里面一个重要的课题就是近期奖励和远期奖励的权衡 （trade-off），研究怎么让智能体取得更多的远期奖励。

在与环境的交互过程中，智能体会获得很多观测。针对每一个观测，智能体会采取一个动作，也会得到一个奖励。所以历史是观测、动作、奖励的序列：

\[ H_{t}=o_{1}, a_{1}, r_{1}, \ldots, o_{t}, a_{t}, r_{t} \]

智能体在采取当前动作的时候会依赖于它之前得到的历史，所以我们可以把整个游戏的状态看成关于这个历史的函数：

\[ s_{t}=f\left(H_{t}\right) \]

图 1.13 Pong游戏

状态和观测有什么关系？

状态是对世界的完整描述，不会隐藏世界的信息。观测是对状态的部分描述，可能会遗漏一些信息。在深度强化学习中，我们几乎总是用实值的向量、矩阵或者更高阶的张量来表示状态和观测。例如， 我们可以用 RGB 像素值的矩阵来表示一个视觉的观测，可以用机器人关节的角度和速度来表示一个机器人的状态。

环境有自己的函数\(s_{t}^{e}=f^{e}\left(H_{t}\right)\)来更新状态，在智能体的内部也有一个函数\(s_{t}^{a}=f^{a}\left(H_{t}\right)\)来更新状态。当智能体的状态与环境的状态等价的时候，即当智能体能够观察到环境的所有状态时，我们称这个环境是 完全可观测的（fully observed）。在这种情况下面，强化学习通常被建模成一个 马尔可夫决策过程（Markov decision process，MDP） 的问题(可以使用一个五元组表示\((S,A,T,R,\gamma)\))。在马尔可夫决策过程中，\(o_t = s_t^e = s_t^a\)。

但是有一种情况是智能体得到的观测并不能包含环境运作的所有状态，因为在强化学习的设定里面，环境的状态才是真正的所有状态。比如智能体在玩 black jack 游戏，它能看到的其实是牌面上的牌。或者在 玩雅达利游戏的时候，观测到的只是当前电视上面这一帧的信息，我们并没有得到游戏内部里面所有的运作状态。也就是当智能体只能看到部分的观测，我们就称这个环境是 部分可观测的（partially observed） 。 在这种情况下，强化学习通常被建模成 部分可观测马尔可夫决策过程（partially observable Markov decision process, POMDP） 的问题。部分可观测马尔可夫决策过程是马尔可夫决策过程的一种泛化。部分可观测马尔可夫决策过程依然具有马尔可夫性质，但是假设智能体无法感知环境的状态，只能知道部分观测值。比如在自动驾驶中，智能体只能感知传感器采集的有限的环境信息。部分可观测马尔可夫决策过程可以用一个七元组描述：\((S,A,T,R,\Omega,O,\gamma)\)。其中\(S\)表示状态空间，为隐变量，\(A\)为动作空间，\(T(s'|s,a)\)为状态转移概率，\(R\)为奖励函数，\(\Omega(o|s,a)\)为观测概率，\(O\)为观测空间，\(\gamma\)为折扣系数。

动作空间

不同的环境允许不同种类的动作。在给定的环境中，有效动作的集合经常被称为 动作空间（action space）。像雅达利游戏和围棋（Go）这样的环境有 离散动作空间（discrete action space），在这个动作空间里，智能体的动作数量是有限的。在其他环境，比如在物理世界中控制一个智能体，在这个环境中就有 连续动作空间（continuous action space）。在连续动作空间中，动作是实值的向量。

例如，走迷宫机器人如果只有往东、往南、往西、往北这 4 种移动方式，则其动作空间为离散动作空间；如果机器人可以向 360 。中的任意角度进行移动，则其动作空间为连续动作空间。

Agnet的组成成分和类型

部分可观测马尔可夫决策过程(Partially Observable Markov Decision Processes, POMDP) 是一个马尔可夫决策过程的泛化。POMDP依然具有一个强化学习 agent，它可能有一个或多个如下的组成成分。

  • 策略（policy）。智能体会用策略来选取下一步的动作。
  • 价值函数（value function）。我们用价值函数来对当前状态进行评估。价值函数用于评估智能体进入某个状态后，可以对后面的奖励带来多大的影响。价值函数值越大，说明智能体进入这个状态越有利。
  • 模型（model）。模型表示智能体对环境的状态进行理解，它决定了环境中世界的运行方式。下面我们深入了解这 3 个组成部分的细节。

策略

策略是智能体用来决定下一步动作的函数。策略可以是一个确定性的函数，也可以是一个随机的函数。确定性策略就是给定一个状态，智能体会输出一个动作；而随机策略则是给定一个状态，智能体会输出一个动作的概率分布。

随机策略（stochastic policy） 就是\(\pi\)函数, 即\(\pi(a \mid s) = p(a_t = a \mid s_t = s)\)。输入当前的状态，输出一个概率。
这个概率是智能体所有动作的概率，然后对这个概率分布进行采用，可得到智能体将采取的动作。比如在雅达利游戏里面，如往上移动的概率是 0.7，往下移动的概率是 0.3，就可以通过采样得到最终所要实施的动作。

确定性策略（deterministic policy） 就是智能体直接采用最优可能的动作，即\(a^{*}=\underset{a}{\arg \max} \pi(a \mid s)\)

价值函数

价值函数的值是对未来奖励的预测，我们用它来评估状态的好坏。
价值函数里面有一个折扣因子（discount factor），我们希望在尽可能短的时间里面得到尽可能多的奖励。比如现在给我们两个选择：10天后给我们100块钱或者现在给我们100块钱。我们肯定更希望现在就给我们 100 块钱，因为我们可以把这 100 块钱存在银行里面，这样就会有一些利息。因此，我们可以把折扣因子放到价值函数的定义里面，价值函数的定义为

\[ V_{\pi}(s) \doteq \mathbb{E}_{\pi}\left[G_{t} \mid s_{t}=s\right]=\mathbb{E}_{\pi}\left[\sum_{k=0}^{\infty} \gamma^{k} r_{t+k+1} \mid s_{t}=s\right], \text{对于所有的} s \in S \]

其中，价值函数的下标是\(\pi\)函数，因此价值函数其实反映了在\(\pi\)策略下，某一个状态平均可以得到多少奖励。期望\(E_{\pi}\)是指在策略 \(\pi\) 下的期望。\(G_t\) 是从时间 \(t\) 开始到结束的轨迹的 折扣化回报（Discounted Return） (由于从\(s\)状态开始，直到结束，轨迹有很多种，因此对其求均值)。\(\gamma\) 是折扣因子，\(\gamma \in [0,1]\)。如果 \(\gamma=0\)，那么我们只考虑当前的奖励；如果 \(\gamma=1\)，那么我们就考虑所有的奖励。

我们还有一种价值函数：Q 函数。Q 函数里面包含两个变量：状态和动作。其定义为

\[ Q_{\pi}(s, a) \doteq \mathbb{E}_{\pi}\left[G_{t} \mid s_{t}=s, a_{t}=a\right]=\mathbb{E}_{\pi}\left[\sum_{k=0}^{\infty} \gamma^{k} r_{t+k+1} \mid s_{t}=s, a_{t}=a\right] \]

所以我们未来可以获得奖励的期望取决于当前的状态和当前的动作。Q函数是强化学习算法里面要学习的一个函数。因为当我们得到 Q 函数后，进入某个状态要采取的最优动作可以通过 Q 函数得到。

模型

第3个组成部分是模型，模型决定了下一步的状态。下一步的状态取决于当前的状态以及当前采取的动作。它由状态转移概率和奖励函数两个部分组成。状态转移概率即

\[ p_{s s^{\prime}}^{a}=p\left(s_{t+1}=s^{\prime} \mid s_{t}=s, a_{t}=a\right) \]

奖励函数是指我们在当前状态采取了某个动作，可以得到多大的奖励，即

\[ R(s,a)=\mathbb{E}\left[r_{t+1} \mid s_{t}=s, a_{t}=a\right] \]

当我们有了策略、价值函数和模型3个组成部分后，就形成了一个马尔可夫决策过程（Markov decision process）。如图 1.15 所示，这个决策过程可视化了状态之间的转移以及采取的动作。

图 1.15 马尔可夫决策过程

我们来看一个走迷宫的例子。如图 1.16 所示，要求智能体从起点（start）开始，然后到达终点（goal）的位置。每走一步，我们就会得到 -1 的奖励。我们可以采取的动作是往上、下、左、右走。我们用现在智能体所在的位置来描述当前状态。

图 1.16 走迷宫的例子

我们可以用不同的强化学习方法来解这个环境。

如果我们采取 基于策略的强化学习（policy-based RL） 方法，当学习好了这个环境后，在每一个状态，我们都会得到一个最佳的动作。如图 1.17 所示，比如我们现在在起点位置，我们知道最佳动作是往右走；在第二格的时候，得到的最佳动作是往上走；第三格是往右走......通过最佳的策略，我们可以最快地到达终点。

图 1.17 使用基于策略的强化学习方法得到的结果

如果换成 基于价值的强化学习（value-based RL） 方法，利用价值函数作为导向，我们就会得到另外一种表征，每一个状态会返回一个价值。如图 1.18 所示，比如我们在起点位置的时候，价值是-16，因为我们最快可以 16 步到达终点。因为每走一步会减1，所以这里的价值是 -16。
当我们快接近终点的时候，这个数字变得越来越大。在拐角的时候，比如现在在第二格，价值是-15，智能体会看上、下两格，它看到上面格子的价值变大了，变成 -14 了，下面格子的价值是 -16，那么智能体就会采取一个往上走的动作。所以通过学习的价值的不同，我们可以抽取出现在最佳的策略。

图 1.18 使用基于价值的强化学习方法得到的结果

智能体类型

1.基于价值的智能体与基于策略的智能体：

根据智能体学习的事物不同，我们可以把智能体进行归类。基于价值的智能体（value-based agent） 显式地学习价值函数，隐式地学习它的策略。策略是其从学到的价值函数里面推算出来的。基于策略的智能体（policy-based agent） 直接学习策略，我们给它一个状态，它就会输出对应动作的概率。基于策略的智能体并没有学习价值函数。把基于价值的智能体和基于策略的智能体结合起来就有了 演员-评论员智能体（actor-critic agent） 。这一类智能体把策略和价值函数都学习了，然后通过两者的交互得到最佳的动作。

基于价值的智能体与基于策略的智能体有什么区别？

对于一个状态转移概率已知的马尔可夫决策过程，我们可以使用动态规划算法来求解。

从决策方式来看，强化学习又可以划分为基于策略的方法和基于价值的方法。决策方式是智能体在给定状态下从动作集合中选择一个动作的依据，它是静态的，不随状态变化而变化。

在 基于策略的强化学习 方法中，智能体会制定一套动作策略（确定在给定状态下需要采取何种动作），并根据这个策略进行操作。强化学习算法直接对策略进行优化，使制定的策略能够获得最大的奖励。

在 基于价值的强化学习 方法中，智能体不需要制定显式的策略，它维护一个价值表格或价值函数，并通过这个价值表格或价值函数来选取价值最大的动作。

基于价值迭代的方法只能应用在不连续的、离散的环境下（如围棋或某些游戏领域），对于动作集合规模庞大、动作连续的场景（如机器人控制领域），其很难学习到较好的结果（此时基于策略迭代的方法能够根据设定的策略来选择连续的动作）。

基于价值的强化学习算法有 Q学习（Q-learning） 、 Sarsa 等，而基于策略的强化学习算法有 策略梯度（Policy Gradient，PG） 算法等。此外，演员-评论员算法同时使用策略和价值评估来做出决策。其中，智能体会根据策略做出动作，而价值函数会对做出的动作给出价值，这样可以在原有的策略梯度算法的基础上加速学习过程，取得更好的效果。

2.基于模型的智能体与无模型的智能体：

在马尔可夫决策过程(MDP)中,有五个关键元素: \(S, A, P, R, \gamma\) 。\(S\) 和 \(A\) 表示环境的状态空间和动作空间; \(P\) 表示状态转移函数, \(p(s′|s, a)\) 给出了智能体在状态 \(s\) 下执行动作 \(a\) ,并转移到状态 \(s′\) 的概率; \(R\) 代表奖励函数, \(r(s, a)\) 给出了智能体在状态 \(s\) 执行动作 \(a\) 时环境返回的奖励值; \(\gamma\) 表示奖励的折扣因子,用来给不同时刻的奖励赋予权重。如果所有这些环境相关的元素都是已知的,那么模型就是已知的。此时可以在环境模型上进行计算,而无须再与真实环境进行交互。在通常情况下,智能体并不知道环境的奖励函数 \(R\) 和状态转移函数 \(p(s′|s, a)\) ,所以需要通过和环境交互,不断试错 (Trials and Errors),观察环境相关信息并利用反馈的奖励信号来不断学习。在这个不断试错和学习的过程中,可能有某些环境元素是未知的,如奖励函数 \(R\) 和状态转移函数 \(P\) 。此时,如果智能体尝试通过在环境中不断执行动作获取样本 \((s, a, s′, r)\) 来构建对 \(R\) 和 \(P\) 的估计,则 \(p(s′|s, a)\) 和 \(r\) 的值可以通过监督学习进行拟合。习得奖励函数 \(R\) 和状态转移函数 \(P\) 之后,所有的环境元素都已知,则规划方法可以直接用来求解该问题。这种方式即称 为 基于模型 的方法。

另一种称为无模型的方法则不尝试对环境建模,而是直接寻找最优策略。例 如,Q-learning 算法对状态-动作对 \((s, a)\) 的 Q 值进行估计,通常选择最大 Q 值对应的动作执行, 并利用环境反馈更新 Q 值函数,随着 Q 值收敛,策略随之逐渐收敛达到最优;策略梯度(Policy Gradient)算法不对值函数进行估计,而是将策略参数化,直接在策略空间中搜索最优策略,最大化累积奖励。这两种算法都不关注环境模型,而是直接搜索能最大化奖励的策略。这种不需要对环境建模的方式称为 无模型的方法 。可以看到,基于模型和无模型的区别在于,智能体是否利 用环境模型(或称为环境的动力学模型),例如状态转移函数和奖励函数。

学习与规划

学习（learning）和规划（planning）是序列决策的两个基本问题。

如图 1.21 所示，在强化学习中，环境初始时是未知的，智能体不知道环境如何工作，它通过不断地与环境交互，逐渐改进策略。

图 1.21 学习

如图 1.22 所示，在规划中，环境是已知的，智能体被告知了整个环境的运作规则的详细信息。智能体能够计算出一个完美的模型，并且在不需要与环境进行任何交互的时候进行计算。智能体不需要实时地与环境交互就能知道未来环境，只需要知道当前的状态，就能够开始思考，来寻找最优解。

在图 1.22 所示的游戏中，规则是确定的，我们知道选择左之后环境将会产生什么变化。我们完全可以通过已知的规则，来在内部模拟整个决策过程，无需与环境交互。

一个常用的强化学习问题解决思路是，先学习环境如何工作，也就是了解环境工作的方式，即学习得到一个模型，然后利用这个模型进行规划。

图 1.22 规划

探索和利用

在强化学习里面，探索和利用是两个很核心的问题。

探索 即我们去探索环境，通过尝试不同的动作来得到最佳的策略（带来最大奖励的策略）。
利用 即我们不去尝试新的动作，而是采取已知的可以带来很大奖励的动作。

在刚开始的时候，强化学习智能体不知道它采取了某个动作后会发生什么，所以它只能通过试错去探索，所以探索就是通过试错来理解采取的动作到底可不可以带来好的奖励。利用是指我们直接采取已知的可以带来很好奖励的动作。所以这里就面临一个权衡问题，即怎么通过牺牲一些短期的奖励来理解动作，从而学习到更好的策略。

下面举一些探索和利用的例子。

以选择餐馆为例，利用 是指我们直接去我们最喜欢的餐馆，因为我们去过这个餐馆很多次了，所以我们知道这里面的菜都非常可口。

探索 是指我们用手机搜索一个新的餐馆，然后去尝试它的菜到底好不好吃。我们有可能对这个新的餐馆感到非常不满意，这样钱就浪费了。

以做广告为例，利用 是指我们直接采取最优的广告策略。探索 是指我们换一种广告策略，看看这个新的广告策略可不可以得到更好的效果。

以挖油为例，利用 是指我们直接在已知的地方挖油，这样可以确保挖到油。
探索 是指我们在一个新的地方挖油，这样就有很大的概率可能不能发现油田，但也可能有比较小的概率可以发现一个非常大的油田。

以玩游戏为例，利用 是指我们总是采取某一种策略。比如，我们玩《街头霸王》游戏的时候，采取的策略可能是蹲在角落，然后一直出脚。这个策略很可能可以奏效，但可能遇到特定的对手就会失效。探索 是指我们可能尝试一些新的招式，有可能我们会放出“大招”来，这样就可能“一招毙命”。

与监督学习任务不同，强化学习任务的最终奖励在多步动作之后才能观察到，这里我们不妨先考虑比较简单的情形：最大化单步奖励，即仅考虑一步动作。需注意的是，即便在这样的简单情形下，强化学习仍与监督学习有显著不同，因为智能体需通过试错来发现各个动作产生的结果，而没有训练数据告诉智能体应当采取哪个动作。

想要最大化单步奖励需考虑两个方面：一是需知道每个动作带来的奖励，二是要执行奖励最大的动作。若每个动作对应的奖励是一个确定值，那么尝试遍所有的动作便能找出奖励最大的动作。然而，更一般的情形是，一个动作的奖励值是来自一个概率分布，仅通过一次尝试并不能确切地获得平均奖励值。

实际上，单步强化学习任务对应于一个理论模型，即\(K\)-臂赌博机（K-armed bandit）。 \(K\)-臂赌博机也被称为多臂赌博机（multi-armed bandit） 。如图 1.23 所示，\(K\)-臂赌博机有 \(K\)个摇臂，赌徒在投入一个硬币后可选择按下其中一个摇臂，每个摇臂以一定的概率吐出硬币，但这个概率赌徒并不知道。赌徒的目标是通过一定的策略最大化自己的奖励，即获得最多的硬币。

若仅为获知每个摇臂的期望奖励，则可采用仅探索（exploration-only）法：将所有的尝试机会平均分配给每个摇臂（即轮流按下每个摇臂），最后以每个摇臂各自的平均吐币概率作为其奖励期望的近似估计。若仅为执行奖励最大的动作，则可采用仅利用（exploitation-only）法：按下目前最优的（即到目前为止平均奖励最大的）摇臂，若有多个摇臂同为最优，则从中随机选取一个。

显然，仅探索法能很好地估计每个摇臂的奖励，却会失去很多选择最优摇臂的机会；仅利用法则相反，它没有很好地估计摇臂期望奖励，很可能经常选不到最优摇臂。因此，这两种方法都难以使最终的累积奖励最大化。

事实上，探索（估计摇臂的优劣）和利用（选择当前最优摇臂）这两者是矛盾的，因为尝试次数（总投币数）有限，加强了一方则自然会削弱另一方，这就是强化学习所面临的 探索-利用窘境（exploration-exploitation dilemma）。显然，想要累积奖励最大，则必须在探索与利用之间达成较好的折中。

图 1.23 K-臂赌博机图示

强化学习实验

Gymnasium

Gymnasium 是一个用于开发和比较强化学习算法的工具包。它提供了多种环境供我们使用。Gymnasium 的设计理念是简单易用，用户可以很方便地创建自己的环境。

Gymanasium主要针对于单agent的强化学习任务，如果想要开发多agent的强化学习任务，可以使用PettingZoo。

Gymnasium的安装可以通过pip命令进行安装：

1
pip install gymnasium

但是上面的命令不会安装其他的环境，所以我们需要安装一些额外的环境。Gymnasium提供了很多的环境供我们使用，比如经典控制、 Atari 游戏、机器人等。我们可以通过下面的命令安装一些常用的环境：

1
2
pip install gymnasium[atari]
pip install gymnasium[all] #install all dependencies.

gymnasium的使用非常简单，我们只需要创建一个环境，然后通过环境的step函数来进行交互。下面是一个简单的例子：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
import gymnasium as gym

# Initialise the environment
env = gym.make("LunarLander-v3", render_mode="human")

# Reset the environment to generate the first observation
observation, info = env.reset(seed=42)
for _ in range(1000):
    # this is where you would insert your policy
    action = env.action_space.sample()

    # step (transition) through the environment with the action
    # receiving the next observation, reward and if the episode has terminated or truncated
    observation, reward, terminated, truncated, info = env.step(action)

    # If the episode has ended then we can reset to start a new episode
    if terminated or truncated:
        observation, info = env.reset()

env.close()

如图 1.25 gymnasium 库里面有很多经典的控制类游戏。比如 Acrobot需要让一个双连杆机器人立起来；CartPole需要通过控制一辆小车，让杆立起来；MountainCar需要通过前后移动车，让它到达旗帜的位置。在刚开始测试强化学习的时候，我们可以选择这些简单环境，因为强化学习在这些环境中可以在一两分钟之内见到效果。

图 1.25 经典控制问题

如图 1.26 所示，CartPole-v0 环境有两个动作：将小车向左移动和将小车向右移动。我们还可以得到观测：小车当前的位置，小车当前往左、往右移的速度，杆的角度以及杆的最高点（顶端）的速度。

观测越详细，我们就可以更好地描述当前所有的状态。这里有奖励的定义，如果能多走一步，我们就会得到一个奖励（奖励值为1），所以我们需要存活尽可能多的时间来得到更多的奖励。当杆的角度大于某一个角度（没能保持平衡），或者小车的中心到达图形界面窗口的边缘，或者累积步数大于200，游戏就结束了，我们就输了。所以智能体的目的是控制杆，让它尽可能地保持平衡以及尽可能保持在环境的中央。

图 1.26 CartPole-v0的例子

1
2
3
4
5
6
7
8
9
import gymnasium as gym  # 导入 Gym 的 Python 接口环境包    
env = gym.make('CartPole-v1',render_mode="human")  # 构建实验环境    
observation, info = env.reset()  # 重置一个回合    
for _ in range(1000):    
    action = env.action_space.sample() # 从动作空间中随机选取一个动作    
    observation, reward, terminated, truncated, info = env.step(action) # 用于提交动作，括号内是具体的动作    
    if terminated or truncated:  # 检查是否结束
        break
env.close() # 关闭环境

注意：如果绘制了实验的图形界面窗口，那么关闭该窗口的最佳方式是调用 env.close()。试图直接关闭图形界面窗口可能会导致内存不能释放，甚至会导致死机。

当我们执行这段代码时，机器人会驾驶着小车朝某个方向一直跑，直到游戏失败，这是因为我们还没开始训练机器人。

我们想要查看当前 gymnasium 库已经注册了哪些环境，可以使用以下代码：

1
2
3
import gymnasium as gym  # 导入 Gym 的 Python 接口环境包    
for i in gym.registry:
    print(i)

每个环境都定义了自己的观测空间和动作空间。环境 env 的观测空间用 env.observation_space 表示，动作空间用 env.action_space 表示。观测空间和动作空间既可以是离散空间（取值是有限个离散的值），也可以是连续空间（取值是连续的值）。在 Gym 库中，一般离散空间用 gym.spaces.Discrete 类表示，连续空间用 gym.spaces.Box 类表示。

例如，环境MountainCar-v0的观测空间是Box(2,)，表示观测可以用 2 个 float 值表示；环境MountainCar-v0的动作空间是Discrete(3)，表示动作取值自{0,1,2}。对于离散空间，Discrete 类实例的成员 n 表示有几个可能的取值；对于连续空间，Box类实例的成员 low 和 high 表示每个浮点数的取值范围。

Blackjack-v1历程

接下来使用一个官方的Blackjack-v1的例程，来了解如何使用Gymnasium库。

构建agent

让我们构建一个Q-learning代理来解决Blackjack！我们需要一些函数来选择一个动作并更新代理的动作值。为了确保代理探索环境，一种可能的解决方案是epsilon贪婪策略，其中我们选择一个百分比为epsilon的随机动作，贪婪动作（当前值为最佳）的概率为1-epsilon。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
from collections import defaultdict
import gymnasium as gym
import numpy as np


class BlackjackAgent:
    def __init__(
        self,
        env: gym.Env,
        learning_rate: float,
        initial_epsilon: float,
        epsilon_decay: float,
        final_epsilon: float,
        discount_factor: float = 0.95,
    ):
        """Initialize a Reinforcement Learning agent with an empty dictionary
        of state-action values (q_values), a learning rate and an epsilon.

        Args:
            env: The training environment
            learning_rate: The learning rate
            initial_epsilon: The initial epsilon value
            epsilon_decay: The decay for epsilon
            final_epsilon: The final epsilon value
            discount_factor: The discount factor for computing the Q-value
        """
        self.env = env
        self.q_values = defaultdict(lambda: np.zeros(env.action_space.n))

        self.lr = learning_rate
        self.discount_factor = discount_factor

        self.epsilon = initial_epsilon
        self.epsilon_decay = epsilon_decay
        self.final_epsilon = final_epsilon

        self.training_error = []

    def get_action(self, obs: tuple[int, int, bool]) -> int:
        """
        Returns the best action with probability (1 - epsilon)
        otherwise a random action with probability epsilon to ensure exploration.
        """
        # with probability epsilon return a random action to explore the environment
        if np.random.random() < self.epsilon:
            return self.env.action_space.sample()
        # with probability (1 - epsilon) act greedily (exploit)
        else:
            return int(np.argmax(self.q_values[obs]))

    def update(
        self,
        obs: tuple[int, int, bool],
        action: int,
        reward: float,
        terminated: bool,
        next_obs: tuple[int, int, bool],
    ):
        """Updates the Q-value of an action."""
        future_q_value = (not terminated) * np.max(self.q_values[next_obs])
        temporal_difference = (
            reward + self.discount_factor * future_q_value - self.q_values[obs][action]
        )

        self.q_values[obs][action] = (
            self.q_values[obs][action] + self.lr * temporal_difference
        )
        self.training_error.append(temporal_difference)

    def decay_epsilon(self):
        self.epsilon = max(self.final_epsilon, self.epsilon - self.epsilon_decay)

训练agent

为了训练代理，我们将让agent运行一个episode（一个完整的游戏称为一个episode），并在采取的每个动作后更新其Q值。agent必须经历很多episode才能充分探索环境。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# hyperparameters
learning_rate = 0.01
n_episodes = 100_000
start_epsilon = 1.0
epsilon_decay = start_epsilon / (n_episodes / 2)  # reduce the exploration over time
final_epsilon = 0.1

env = gym.make("Blackjack-v1", sab=False)
env = gym.wrappers.RecordEpisodeStatistics(env, buffer_length=n_episodes)

agent = BlackjackAgent(
    env=env,
    learning_rate=learning_rate,
    initial_epsilon=start_epsilon,
    epsilon_decay=epsilon_decay,
    final_epsilon=final_epsilon,
)

Note

当前的超参数被设置为快速训练一个agent。如果你想收敛到最优策略，尝试将n_episodes增加10倍，并降低learning_rate（例如，降低到0.001）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
from tqdm import tqdm

for episode in tqdm(range(n_episodes)):
    obs, info = env.reset()
    done = False

    # play one episode
    while not done:
        action = agent.get_action(obs)
        next_obs, reward, terminated, truncated, info = env.step(action)

        # update the agent
        agent.update(obs, action, reward, terminated, next_obs)

        # update if the environment is done and the current obs
        done = terminated or truncated
        obs = next_obs

    agent.decay_epsilon()

使用matplotlib可视化训练过程：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
from matplotlib import pyplot as plt

def get_moving_avgs(arr, window, convolution_mode):
    return np.convolve(
        np.array(arr).flatten(),
        np.ones(window),
        mode=convolution_mode
    ) / window

# Smooth over a 500 episode window
rolling_length = 500
fig, axs = plt.subplots(ncols=3, figsize=(12, 5))

axs[0].set_title("Episode rewards")
reward_moving_average = get_moving_avgs(
    env.return_queue,
    rolling_length,
    "valid"
)
axs[0].plot(range(len(reward_moving_average)), reward_moving_average)

axs[1].set_title("Episode lengths")
length_moving_average = get_moving_avgs(
    env.length_queue,
    rolling_length,
    "valid"
)
axs[1].plot(range(len(length_moving_average)), length_moving_average)

axs[2].set_title("Training Error")
training_error_moving_average = get_moving_avgs(
    agent.training_error,
    rolling_length,
    "same"
)
axs[2].plot(range(len(training_error_moving_average)), training_error_moving_average)
plt.tight_layout()
plt.show()

Blackjack-v1训练过程

强化学习理论与建模

本章将介绍马尔可夫决策过程。在介绍马尔可夫决策过程之前，我们先介绍它的简化版本：马尔可夫过程（Markov process，MP） 以及 马尔可夫奖励过程（Markov reward process，MRP）。通过与这两种过程的比较，我们可以更容易理解马尔可夫决策过程。其次，我们会介绍 马尔可夫决策过程中的 策略评估（policy evaluation），就是当给定决策后，我们怎么去计算它的价值函数。最后，我们会介绍马尔可夫决策过程的控制，具体有 策略迭代（policy iteration） 和 价值迭代（value iteration） 两种算法。在马尔可夫决策过程中，它的环境是全部可观测的。但是很多时候环境里面有些量是不可观测的，但是这个部分观测的问题也可以转换成马尔可夫决策过程的问题。

马尔可夫过程

马尔可夫的性质

在随机过程中，马尔可夫性质（Markov property) 是指一个随机过程在给定现在状态及所有过去状态情况下，其未来状态的条件概率分布仅依赖于当前状态。以离散随机过程为例，假设随机变量 \(X_0,X_1,\cdots,X_T\) 构成一个随机过程。这些随机变量的所有可能取值的集合被称为状态空间（state space）。如果 \(X_{t+1}\) 对于过去状态的条件概率分布仅是 \(X_t\) 的一个函数，则

\[ p\left(X_{t+1}=x_{t+1} \mid X_{0:t}=x_{0: t}\right)=p\left(X_{t+1}=x_{t+1} \mid X_{t}=x_{t}\right) \]

其中 \(X_{0:t}\) 表示 \(X_0,X_1,\cdots,X_t\) 的联合分布，\(x_{0:t}\) 为在状态空间中的状态序列 \(x_0,x_1,\cdots,x_t\) 。马尔可夫性质也可以描述为给定当前状态时，将来的状态与过去状态是条件独立的。如果某一个过程满足马尔可夫性质，那么未来的转移与过去的是独立的，它只取决于现在。马尔可夫性质是所有马尔可夫过程的基础。

马尔可夫链

马尔可夫过程是一组具有马尔可夫性质的随机变量序列 \(s_1,\cdots,s_t\) ，其中下一个时刻的状态 \(s_{t+1}\) 只取决于当前状态 \(s_t\) ( 1-order markov chain )。我们设状态的历史为 \(h_{t}=\left\{s_{1}, s_{2}, s_{3}, \ldots, s_{t}\right\}\)（包含了之前的所有状态），则马尔可夫过程满足条件：

\[ p\left(s_{t+1} \mid s_{t}\right) =p\left(s_{t+1} \mid h_{t}\right) \]

从当前 \(s_t\) 转移到 \(s_{t+1}\) 就等价于从它之前是所有状态转移到 \(s_{t+1}\)。

离散时间的马尔可夫过程也称为 马尔可夫链（Markov chain） 。马尔可夫链是最简单的马尔可夫过程，其状态是有限的。例如，图 2.2 里面有4个状态，这4个状态在 \(s_1, s_2, s_3, s_4\) 之间互相转移。比如从\(s_1\)开始，\(s_1\) 有0.1的概率继续留存在 \(s_1\) 状态，有0.2的概率转移到 \(s_2\) ，有0.7的概率转移到 \(s_4\) 。如果 \(s_4\) 是我们的当前状态，它有0.3的概率转移到 \(s_2\) ，有0.2的概率转移到 \(s_3\) ，有0.5的概率留在当前状态。

图 2.2 马尔可夫链示例
我们可以用 状态转移矩阵（state transition matrix） \(\boldsymbol{P}\) 来描述状态转移 \(p\left(s_{t+1}=s^{\prime} \mid s_{t}=s\right)\)
\[ \boldsymbol{P}=\left(\begin{array}{cccc} p\left(s_{1} \mid s_{1}\right) & p\left(s_{2} \mid s_{1}\right) & \ldots & p\left(s_{N} \mid s_{1}\right) \\ p\left(s_{1} \mid s_{2}\right) & p\left(s_{2} \mid s_{2}\right) & \ldots & p\left(s_{N} \mid s_{2}\right) \\ \vdots & \vdots & \ddots & \vdots \\ p\left(s_{1} \mid s_{N}\right) & p\left(s_{2} \mid s_{N}\right) & \ldots & p\left(s_{N} \mid s_{N}\right) \end{array}\right) \]

状态转移矩阵类似于条件概率（conditional probability），它表示当我们知道当前我们在状态 \(s_t\)时，到达下面所有状态的概率。所以它的每一行描述的是从一个节点到达所有其他节点的概率。

隐马尔可夫模型

本小结关于隐马尔可夫模型的内容主要参考斯坦福的《Speech and Language Processing》的课件里面，关于HMM的附录部分和一个在线blog

当我们需要计算可观察事件序列的发生概率的时候，马尔可夫链是很有用的。但是，在很多情况下，我们所感兴趣的事件是隐藏的（我们没有办法直接观察到），例如，我们通常无法直接观察到一个句子当中各个词的词性（part-of-speech）标签，但是我们可以直接观察到单词，我们需要总单词序列中推导出词性标签，该标签就是隐藏的，因为我们无法直接观察到。

Part-of-Speech Tagging

词性标注是自然语言处理中的一个重要任务，它的目标是为句子中的每个单词分配一个词性标签。

词性标注的输入一个tokenized的单词序列\(x_1,x_2,\cdots,x_n\)，输出是一个标签序列\(y_1,y_2,\cdots,y_n\)。其中输出的每一个\(y_i\)都对应到一个输入的\(x_i\)。如下图所示

part-of-speech tagging

隐马尔可夫模型（Hidden Markov Model, HMM）使我们可以同时处理可观测事件（比如输入的单词）和隐藏事件（比如词性标签），其中隐藏事件我们虽然不能直接观察，但是在模型中，我们认为它们是造成观察结果的潜在因素（causal factors）

隐马尔可夫模型（如下图所示）通常由以下几个部分组成：

HMM示意图

\(Q = \{q_1,q_2,\cdots,q_N\}\)是所有可能的状态(隐藏状态)的集合，其中\(N\)是可能的状态数。

\(V = \{v_1,v_2,\cdots,v_M\}\)是所有可能的观测的集合，其中\(M\)是可能的观测数。

\(I = (i_1,i_2,\cdots,i_T)\)是长度为\(T\)的状态序列，而\(O = (o_1,o_2,\cdots,o_T)\)是对应的观测序列

\(A = [a_{ij}]_{N\times N}\)是状态转移矩阵，其中\(a_{ij} = P(i_{t+1} = q_j | i_t = q_i)\)表示在时刻\(t\)处于状态\(q_i\)的条件下，在时刻\(t+1\)处于状态\(q_j\)的概率。

\(B = [b_{jk}]_{N\times M}\)是观测概率矩阵，其中\(b_{jk} = P(o_t = v_k | i_t = q_j)\)表示在时刻\(t\)处于状态\(q_j\)的条件下，观测到\(v_k\)的概率。

\(\pi = (\pi_1,\pi_2,\cdots,\pi_N)\)是初始状态概率向量，其中\(\pi_i = P(i_1 = q_i)\)表示在时刻\(t=1\)处于状态\(q_i\)的概率。

隐马尔可夫模型由初始状态概率向量\(\pi\)、状态转移概率矩阵\(A\)和观测概率矩阵\(B\)决定。\(\pi\)和\(A\)决定状态序列，\(B\)决定观测序列。因此，隐马尔可夫模型\(\lambda\)可以用三元符号表示，即：

\[ \lambda = (A,B, \pi) \]

\(A,B,\pi\)称为隐马尔可夫模型的三要素。

从定义可知，隐马尔可夫模型做了两个基本假设：

  1. 齐次马尔可夫性假设，即假设隐藏的马尔可夫链在任意时刻\(t\)的状态只依赖于其前一时刻的状态，与其他时刻的状态及观测无关\(P(i_t\vert i_{t-1},o_{t-1},...,i_1,o_1)=P(i_t\vert i_{t-1})\)
  2. 观测独立性假设，即假设任意时刻的观测只依赖于该时刻的马尔可夫链的状态，与其他观测及状态无关：\(P(o_t\vert i_T,o_T,i_{T-1},o_{T-1},...,i_t,i_{t-1},o_{t-1},...,i_1,o_1)=P(o_t\vert i_t)\)

马尔可夫过程示例

图 2.2 所示为一个马尔可夫过程的例子，这里有七个状态。比如从 \(s_1\)开始，它有0.4的概率到 \(s_2\)，有 0.6 的概率留在当前的状态。 \(s_2\) 有 0.4 的概率到 \(s_1\)，有 0.4 的概率到 \(s_3\)，另外有 0.2 的概率留在当前状态。所以给定状态转移的马尔可夫链后，我们可以对这个链进行采样，这样就会得到一串轨迹。例如，假设我们从状态 \(s_3\)开始，可以得到3个轨迹：

  • \(s_3, s_4, s_5, s_6, s_6\)
  • \(s_3, s_2, s_3, s_2, s_1\)
  • \(s_3, s_4, s_4, s_5, s_5\)

通过对状态的采样，我们可以生成很多这样的轨迹。

图 2.3 马尔可夫过程的例子

马尔可夫奖励过程

马尔可夫奖励过程（Markov reward process, MRP） 是马尔可夫链加上奖励函数。在马尔可夫奖励过程中，状态转移矩阵和状态都与马尔可夫链一样，只是多了 奖励函数（reward function） 。奖励函数\(R\)是一个期望，表示当我们到达某一个状态的时候，可以获得多大的奖励。这里另外定义了折扣因子\(\gamma\)。如果状态数是有限的，那么\(R\)可以是一个向量。

回报与价值函数

这里我们进一步定义一些概念。范围（horizon） 是指一个回合的长度（每个回合最大的时间步数），它是由有限个步数决定的。
回报（return） 可以定义为奖励的逐步叠加，假设时刻\(t\)后的奖励序列为\(r_{t+1},r_{t+2},r_{t+3},\cdots,\) (其中关于为什么使用\(t+1\)而不是\(t\)，主要是为了体现\(r_{t+1}\)是进入\(s_t\)之后获得的瞬时奖励)，则回报为

\[ G_{t}=r_{t+1}+\gamma r_{t+2}+\gamma^{2} r_{t+3}+\gamma^{3} r_{t+4}+\ldots+\gamma^{T-t-1} r_{T} \]

其中，\(T\)是最终时刻，\(\gamma\)是折扣因子，越往后得到的奖励，折扣越多。这说明我们更希望得到现有的奖励，对未来的奖励要打折扣。当我们有了回报之后，就可以定义状态的价值了，就是 状态价值函数（state-value function）。对于马尔可夫奖励过程，状态价值函数被定义成回报的期望，即

\[ \begin{align*} V^{t}(s) &=\mathbb{E}\left[G_{t} \mid s_{t}=s\right] \\ &=\mathbb{E}\left[r_{t+1}+\gamma r_{t+2}+\gamma^{2} r_{t+3}+\ldots+\gamma^{T-t-1} r_{T} \mid s_{t}=s\right] \end{align*} \]

其中，\(G_t\)是之前定义的 折扣回报（discounted return）。我们对\(G_t\)取了一个期望，因为\(G_t\)表示的是一个特定的状态转移的回报，但是由于状态转移不是固定的，因此会有很多种状态转移，因此通过取期望来表示从该状态出发，能获得回报的期望，用于表示该状态的价值。

我们使用折扣因子的原因如下。第一，有些马尔可夫过程是带环的，它并不会终结，我们想避免无穷的奖励。第二，我们并不能建立完美的模拟环境的模型，我们对未来的评估不一定是准确的，我们不一定完全信任模型，因为这种不确定性，所以我们对未来的评估增加一个折扣。我们想把这个不确定性表示出来，希望尽可能快地得到奖励，而不是在未来某一个点得到奖励。第三，如果奖励是有实际价值的，我们可能更希望立刻就得到奖励，而不是后面再得到奖励（现在的钱比以后的钱更有价值）。最后，我们也更想得到即时奖励。有些时候可以把折扣因子设为 0（\(\gamma = 0\)），我们就只关注当前的奖励。我们也可以把折扣因子设为 1（\(\gamma = 1\)），对未来的奖励并没有打折扣，未来获得的奖励与当前获得的奖励是一样的权重。折扣因子可以作为强化学习智能体的一个 超参数（hyperparameter） 来进行调整，通过调整折扣因子，我们可以得到不同动作的智能体。

在马尔可夫奖励过程里面，我们如何计算价值呢？如图 2.4 所示，马尔可夫奖励过程依旧是状态转移，其奖励函数可以定义为：智能体进入第一个状态\(s_1\)的时候会得到\(5\)的奖励，进入第七个状态\(s_7\)的时候会得到\(10\)的奖励，进入其他状态都没有奖励。我们可以用向量来表示奖励函数，即

\[ \boldsymbol{R}=[5,0,0,0,0,0,10] \]

图 2.4 马尔可夫奖励过程的例子

我们对 4 步的回合（\(\gamma = 0.5\)）来采样回报\(G\)。

  1. \(s_{4}, s_{5}, s_{6}, s_{7} \text{的回报}: 0+0.5\times 0+0.25 \times 0+ 0.125\times 10=1.25\)
  2. \(s_{4}, s_{5}, s_{6}, s_{7} \text{的回报}: 0+0.5\times 0+0.25 \times 0+ 0.125\times 10=1.25\)
  3. \(s_{4}, s_{5}, s_{6}, s_{6} \text{的回报}: 0+0.5\times 0 +0.25 \times 0+0.125 \times 0=0\)

我们现在可以计算每一个轨迹得到的奖励，比如我们对轨迹\(s_4,s_5,s_6,s_7\)的奖励进行计算，这里折扣因子是\(0.5\)。在 \(s_4\)的时候，奖励为0。下一个状态\(s_5\)的时候，因为我们已经到了下一步，所以要把\(s_5\)进行折扣，\(s_5\)的奖励也是0。然后是\(s_6\)，奖励也是0，折扣因子应该是0.25。到达\(s_7\)后，我们获得了一个奖励，但是因为状态\(s_7\)的奖励是未来才获得的奖励，所以我们要对之进行3次折扣。最终这个轨迹的回报就是\(1.25\)。类似地，我们可以得到其他轨迹的回报。

这里就引出了一个问题，当我们有了一些轨迹的实际回报时，怎么计算它的价值函数呢？

比如我们想知道\(s_4\)的价值，即当我们进入\(s_4\)后，它的价值到底如何？一个可行的做法就是我们可以生成很多轨迹，然后把轨迹都叠加起来。比如我们可以从\(s_4\)开始，采样生成很多轨迹，把这些轨迹的回报都计算出来，然后将其取平均值作为我们进入\(s_4\)的价值。这其实是一种计算价值函数的办法，也就是通过 蒙特卡洛（Monte Carlo，MC）采样 的方法计算\(s_4\)的价值。

贝尔曼方程

但是这里我们采取了另外一种计算方法，从价值函数里面推导出 贝尔曼方程（Bellman equation） ：

\[ V(s)=\underbrace{R(s)}_{\text {即时奖励}}+\underbrace{\gamma \sum_{s^{\prime} \in S} p\left(s^{\prime} \mid s\right) V\left(s^{\prime}\right)}_{\text {未来奖励的折扣总和}} \]

其中，

  • \(V(s)\) 是状态 \(s\) 的价值函数
  • \(R(s)\) 是进入状态 \(s\) 后获得的即时奖励
  • \(s^{\prime}\) 是未来所有可能的状态
  • \(p\left(s^{\prime} \mid s\right)\) 是从状态 \(s\) 转移到状态 \(s^{\prime}\) 的概率
  • \(\gamma \sum_{s^{\prime} \in S} p\left(s^{\prime} \mid s\right) V\left(s^{\prime}\right)\) 是未来所有可能状态的平均的折扣价值

贝尔曼方程定义了当前状态与未来状态之间的关系。未来奖励的折扣总和加上即时奖励，就组成了贝尔曼方程。

全期望公式

在推到贝尔曼方程之间，我们先仿照 全期望公式（law of total ecpectation） 的证明过程来证明：

\[ \mathbb{E}[V(s_{t+1})|s_t]=\mathbb{E}[\mathbb{E}[G_{t+1}|s_{t+1}]|s_t]=\mathbb{E}[G_{t+1}|s_t] \]

Note

全期望公式也被称为叠期望公式（law of iterated expectation），它是指在给定一个随机变量的条件下，另一个随机变量的期望值等于在第一个随机变量的条件下的期望，然后第二个随机变量的期望值。全期望公式可以用来计算复杂的期望值，它可以将一个复杂的期望值分解成多个简单的期望值，从而简化计算。

如果\(A_i\)是样本空间的有限或可数的划分（partition），则全期望公式可以定义为

\[ \mathbb{E}[X]=\sum_{i} \mathbb{E}\left[X \mid A_{i}\right] p\left(A_{i}\right) \]

证明

为了符号简洁且易读，我们去掉了下标，令\(s = s_t, g^\prime = G_{t+1}, s^\prime = s_{t+1}\)。因此我们可以重写回报的期望为

\[ \begin{aligned} V(s_{t+1}) = \mathbb{E}\left[G_{t+1} \mid s_{t+1}\right] &=\mathbb{E}\left[g^{\prime} \mid s^{\prime}\right] \\ &=\sum_{g^{\prime}} g^{\prime}~p\left(g^{\prime} \mid s^{\prime}\right) \end{aligned} \]

Note

如果\(X\)和\(Y\)都是离散随机变量，则条件期望(conditional expectation) \(\mathbb{E}[X|Y=y]\)定义为

\[ \mathbb{E}[X \mid Y=y]=\sum_{x} x p(X=x \mid Y=y) \]

令\(s_t = s\)，我们对上式求期望(给定\(s\)下对\(s_{t+1}\))可得

\[ \begin{aligned} \mathbb{E}\left[\mathbb{E}\left[G_{t+1} \mid s_{t+1}\right] \mid s_{t}\right] &=\mathbb{E} \left[\mathbb{E}\left[g^{\prime} \mid s^{\prime}\right] \mid s\right] \\ &=\mathbb{E} \left[\sum_{g^{\prime}} g^{\prime}~p\left(g^{\prime} \mid s^{\prime}\right)\mid s\right]\\ &=\sum_{s^{\prime}} \sum_{g^{\prime}} g^{\prime} p\left(g^{\prime} \mid s^{\prime}, s\right) p\left(s^{\prime} \mid s\right) \\ &=\sum_{s^{\prime}} \sum_{g^{\prime}} \frac{g^{\prime} p\left(g^{\prime} \mid s^{\prime}, s\right) p\left(s^{\prime} \mid s\right) p(s)}{p(s)} \\ &=\sum_{s^{\prime}} \sum_{g^{\prime}} \frac{g^{\prime} p\left(g^{\prime} \mid s^{\prime}, s\right) p\left(s^{\prime}, s\right)}{p(s)} \\ &=\sum_{s^{\prime}} \sum_{g^{\prime}} \frac{g^{\prime} p\left(g^{\prime}, s^{\prime}, s\right)}{p(s)} \\ &=\sum_{s^{\prime}} \sum_{g^{\prime}} g^{\prime} p\left(g^{\prime}, s^{\prime} \mid s\right) \\ &=\sum_{g^{\prime}} \sum_{s^{\prime}} g^{\prime} p\left(g^{\prime}, s^{\prime} \mid s\right) \\ &=\sum_{g^{\prime}} g^{\prime} p\left(g^{\prime} \mid s\right) \\ &=\mathbb{E}\left[g^{\prime} \mid s\right]=\mathbb{E}\left[G_{t+1} \mid s_{t}\right] \end{aligned} \]

贝尔曼方程推导

贝尔曼方程的推导过程如下：

\[ \begin{aligned} V(s)&=\mathbb{E}\left[G_{t} \mid s_{t}=s\right]\\ &=\mathbb{E}\left[r_{t+1}+\gamma r_{t+2}+\gamma^{2} r_{t+3}+\ldots \mid s_{t}=s\right] \\ &=\mathbb{E}\left[r_{t+1}|s_t=s\right] +\gamma \mathbb{E}\left[r_{t+2}+\gamma r_{t+3}+\gamma^{2} r_{t+4}+\ldots \mid s_{t}=s\right]\\ &=R(s)+\gamma \mathbb{E}[G_{t+1}|s_t=s] \\ &=R(s)+\gamma \mathbb{E}[V(s_{t+1})|s_t=s]\\ &=R(s)+\gamma \sum_{s^{\prime} \in S} p\left(s^{\prime} \mid s\right) V\left(s^{\prime}\right) \end{aligned} \]

Note

贝尔曼方程就是当前状态与未来状态的迭代关系，表示当前状态的价值函数可以通过下个状态的价值函数来计算。贝尔曼方程因其提出者、动态规划创始人理查德·贝尔曼（Richard Bellman）而得名 ，也叫作“动态规划方程”。

贝尔曼方程定义了状态之间的迭代关系，即

\[ V(s)=R(s)+\gamma \sum_{s^{\prime} \in S} p\left(s^{\prime} \mid s\right) V\left(s^{\prime}\right) \]

假设有一个马尔可夫链如图 2.5a 所示，贝尔曼方程描述的就是当前状态到未来状态的一个转移。如图 2.5b 所示，假设我们当前在\(s_1\)
，那么它只可能去到3个未来的状态：有 0.1 的概率留在它当前位置，有 0.2 的概率去到\(s_2\)状态，有 0.7 的概率去到\(s_4\)状态。所以我们把状态转移概率乘它未来的状态的价值，再加上它的即时奖励（immediate reward），就会得到它当前状态的价值。贝尔曼方程定义的就是当前状态与未来状态的迭代关系。

图 2.5 状态转移

我们可以把贝尔曼方程写成矩阵的形式：

\[ \left(\begin{array}{c} V\left(s_{1}\right) \\ V\left(s_{2}\right) \\ \vdots \\ V\left(s_{N}\right) \end{array}\right)=\left(\begin{array}{c} R\left(s_{1}\right) \\ R\left(s_{2}\right) \\ \vdots \\ R\left(s_{N}\right) \end{array}\right)+\gamma\left(\begin{array}{cccc} p\left(s_{1} \mid s_{1}\right) & p\left(s_{2} \mid s_{1}\right) & \ldots & p\left(s_{N} \mid s_{1}\right) \\ p\left(s_{1} \mid s_{2}\right) & p\left(s_{2} \mid s_{2}\right) & \ldots & p\left(s_{N} \mid s_{2}\right) \\ \vdots & \vdots & \ddots & \vdots \\ p\left(s_{1} \mid s_{N}\right) & p\left(s_{2} \mid s_{N}\right) & \ldots & p\left(s_{N} \mid s_{N}\right) \end{array}\right)\left(\begin{array}{c} V\left(s_{1}\right) \\ V\left(s_{2}\right) \\ \vdots \\ V\left(s_{N}\right) \end{array}\right) \]

我们当前的状态是向量\([V(s_1),V(s_2),\cdots,V(s_N)]^\mathrm{T}\)。每一行来看，向量\(V\)乘状态转移矩阵里面的某一行，再加上它当前可以得到的奖励，就会得到它当前的价值。

当我们把贝尔曼方程写成矩阵形式后，可以直接求解：

\[ \begin{aligned} \boldsymbol{V} &= \boldsymbol{\boldsymbol{R}}+ \gamma \boldsymbol{P}\boldsymbol{V} \\ \boldsymbol{I}\boldsymbol{V} &= \boldsymbol{R}+ \gamma \boldsymbol{P}\boldsymbol{V} \\ (\boldsymbol{I}-\gamma \boldsymbol{P})\boldsymbol{V}&=\boldsymbol{R} \\ \boldsymbol{V}&=(\boldsymbol{I}-\gamma \boldsymbol{P})^{-1}\boldsymbol{R} \end{aligned} \]

我们可以直接得到 解析解（analytic solution）：

\[ \boldsymbol{V}=(\boldsymbol{I}-\gamma \boldsymbol{P})^{-1} \boldsymbol{R} \]

我们可以通过矩阵求逆把\(V\)的价值直接求出来。但是一个问题是这个矩阵求逆的过程的复杂度是\(O(N^3)\)。所以当状态非常多的时候，比如从10个状态到1000个状态，或者到100万个状态，当我们有100万个状态的时候，状态转移矩阵就会是一个100万乘100万的矩阵，对这样一个大矩阵求逆是非常困难的。所以这种通过解析解去求解的方法只适用于很小量的马尔可夫奖励过程。

计算马尔可夫奖励过程价值的迭代算法

我们可以将迭代的方法应用于状态非常多的马尔可夫奖励过程（large MRP），比如：动态规划的方法 ，蒙特卡洛的方法（通过采样的办法计算它），时序差分学习（temporal-difference learning，TD learning） 的方法（时序差分学习是动态规划和蒙特卡洛方法的一个结合）。

首先我们用蒙特卡洛方法来计算价值。如图 2.6 所示，蒙特卡洛方法就是当得到一个马尔可夫奖励过程后，我们可以从某个状态开始，把小船放到状态转移矩阵里面，让它“随波逐流”，这样就会产生一个轨迹。产生一个轨迹之后，就会得到一个奖励，那么直接把折扣的奖励即回报\(g\)算出来。算出来之后将它积累起来，得到回报\(G_t\)。当积累了一定数量的轨迹之后，我们直接用\(G_t\)除以轨迹数量，就会得到某个状态的价值。

图 2.6 计算马尔可夫奖励过程价值的蒙特卡洛方法

比如我们要计算\(s_4\)状态的价值，可以从\(s_4\)状态开始，随机产生很多轨迹。把小船放到状态转移矩阵里面，然后它就会“随波逐流”，产生轨迹。每个轨迹都会得到一个回报，我们得到大量的回报，比如100个、1000个回报，然后直接取平均值，就可以等价于现在\(s_4\)的价值，因为\(s_4\)的价值\(V(s_4)\)定义了我们未来可能得到多少的奖励。这就是蒙特卡洛采样的方法。

如图 2.7 所示，我们也可以用动态规划的方法，一直迭代贝尔曼方程，直到价值函数收敛，我们就可以得到某个状态的价值。我们通过自举（bootstrapping） 的方法不停地迭代贝尔曼方程，当最后更新的状态与我们上一个状态的区别并不大的时候，更新就可以停止，我们就可以输出最新的\(V^\prime(s)\)作为它当前的状态的价值。这里就是把贝尔曼方程变成一个贝尔曼更新（Bellman update），这样就可以得到状态的价值。

动态规划的方法基于后继状态价值的估计来更新现在状态价值的估计（如图 2.7 所示算法中的第 3 行用 \(V^\prime(s)\)来更新\(V\)）。根据其他估算值来更新估算值的思想，我们称其为自举。

图 2.7 计算马尔可夫奖励过程价值的动态规划算法

马尔可夫奖励过程的例子

如图 2.8 所示，如果我们在马尔可夫链上加上奖励，那么到达每个状态，我们都会获得一个奖励。我们可以设置对应的奖励，比如智能体到达状态 \(s_1\)时，可以获得 5 的奖励；到达\(s_7\) 的时候，可以得到 10 的奖励；到达其他状态没有任何奖励。
因为这里的状态是有限的，所以我们可以用向量\(\boldsymbol{R}=[5,0,0,0,0,0,10]\)来表示奖励函数，\(R\)表示每个状态的瞬时奖励大小。

我们通过一个形象的例子来理解马尔可夫奖励过程。我们把一艘纸船放到河流之中，它就会随着水流而流动，它自身是没有动力的。所以我们可以把马尔可夫奖励过程看成一个随波逐流的例子，当我们从某一个点开始的时候，纸船就会随着事先定义好的状态转移进行流动，它到达每个状态后，我们都有可能获得一些奖励。

图 2.8 马尔可夫奖励过程的例子

马尔可夫决策过程

相对于马尔可夫奖励过程，马尔可夫决策过程多了决策（决策是指动作），其他的定义与马尔可夫奖励过程的是类似的。此外，状态转移也多了一个条件，变成了\(p\left(s_{t+1}=s^{\prime} \mid s_{t}=s,a_{t}=a\right)\)。未来的状态不仅依赖于当前的状态，也依赖于在当前状态智能体采取的动作。马尔可夫决策过程满足条件：

\[ p\left(s_{t+1} \mid s_{t}, a_{t}\right) =p\left(s_{t+1} \mid h_{t}, a_{t}\right) \]

对于奖励函数，它也多了一个当前的动作，变成了\(R\left(s_{t}=s, a_{t}=a\right)=\mathbb{E}\left[r_{t} \mid s_{t}=s, a_{t}=a\right]\) 。当前的状态以及采取的动作会决定智能体在当前可能得到的奖励多少。

马尔可夫决策过程的策略

策略（policy） 定义了在某一状态下应该采取什么样的行动。直到状态之后，我们可以将当前的状态带入策略函数来得到一个概率，即：

\[ \pi(a \mid s)=p\left(a_{t}=a \mid s_{t}=s\right) \]

概率表示不同采取不同行动的可能性，比如可能有0.7的概率往左走，有0.3的概率往右走。除此之外，策略也可以是一个确定性的函数，即直接输出一个值（只有一个action的概率为1，其他的都为0），或者直接告诉我们接下来应该采取的动作，而不是动作概率。假设概率函数是平稳的（stationary）, 不同时间点，我们所采取的行动都是对策略函数的采样。

已知马尔可夫决策过程和策略\(\pi\)，我们可以把一个马尔可夫决策过程转换成马尔可夫奖励过程。在马尔可夫决策过程里面，状态转移函数\(P(s^\prime \mid s, a)\)是基于当前的状态以及当前的动作的，因为现在已知策略函数，也就是已知在每一个状态下，可能采取的动作的概率，所以我们就可以直接把动作进行求和，去掉\(a\)，这样我们就得到了马尔可夫奖励过程的状态转移，即：

\[ P_{\pi}\left(s^{\prime} \mid s\right)=\sum_{a \in A} \pi(a \mid s) p\left(s^{\prime} \mid s, a\right) \]

对于奖励函数，我们也可以把动作去掉，这样就可以得到类似于马尔可夫奖励过程的奖励函数，即：

\[ r_{\pi}(s)=\sum_{a \in A} \pi(a \mid s) R(s, a) \]

马尔可夫决策过程与马尔可夫奖励过程的区别

马尔可夫决策过程里面的状态转移与马尔可夫奖励过程以及马尔可夫过程的状态转移的差异如图 2.9 所示。马尔可夫过程/马尔可夫奖励过程的状态转移是直接决定的。比如当前状态是\(s\)，那么直接通过转移概率决定下一个状态是什么。但对于马尔可夫决策过程，它的中间多了一层动作\(a\)，即智能体在当前状态的时候，首先要决定采取某一种动作，这样我们会到达某一个黑色的节点。到达这个黑色的节点后，因为有一定的不确定性，所以当智能体当前状态以及智能体当前采取的动作决定过后，智能体进入未来的状态其实也是一个概率分布。在当前状态与未来状态转移过程中多了一层决策性，这是马尔可夫决策过程与之前的马尔可夫过程/马尔可夫奖励过程很不同的一点。在马尔可夫决策过程中，动作是由智能体决定的，智能体会采取动作来决定未来的状态转移。

图 2.9 马尔可夫决策过程与马尔可夫过程/马尔可夫奖励过程的状态转移的对比

马尔可夫决策过程中的价值函数

马尔可夫决策过程中的价值函数可以定义为：

\[ V_{\pi}(s)=\mathbb{E}_{\pi}\left[G_{t} \mid s_{t}=s\right]=\mathbb{E}_{\pi}\left[\sum_{k=0}^{\infty} \gamma^{k} r_{t+k+1} \mid s_{t}=s\right] \]

其中，期望是基于我们所采取的策略的。当策略古荡之后，我们通过对策略进行采样来得到一个期望，计算除它的价值函数。

这里我们引入了一个 Q函数（Q-function），Q函数也被称为 动作价值函数（action-value function），Q函数定义的是在某一状态下采取某一个动作，能够得到的汇报的期望，即

\[ Q_{\pi}(s, a)=\mathbb{E}_{\pi}\left[G_{t} \mid s_{t}=s, a_{t}=a\right]=\mathbb{E}_{\pi}\left[\sum_{k=0}^{\infty} \gamma^{k} r_{t+k+1} \mid s_{t}=s, a_{t}=a\right] \]

对Q函数中的动作进行求期望，就可以得到价值函数：

\[ V_{\pi}(s)=\sum_{a \in A} \pi(a \mid s) Q_{\pi}(s, a) \]

此处我们对Q函数的贝尔曼方程进行推导：

\[ \begin{aligned} Q(s,a)&=\mathbb{E}\left[G_{t} \mid s_{t}=s,a_{t}=a\right]\\ &=\mathbb{E}\left[r_{t+1}+\gamma r_{t+2}+\gamma^{2} r_{t+3}+\ldots \mid s_{t}=s,a_{t}=a\right] \\ &=\mathbb{E}\left[r_{t+1}|s_{t}=s,a_{t}=a\right] +\gamma \mathbb{E}\left[r_{t+2}+\gamma r_{t+3}+\gamma^{2} r_{t+4}+\ldots \mid s_{t}=s,a_{t}=a\right]\\ &=R(s,a)+\gamma \mathbb{E}[G_{t+1}|s_{t}=s,a_{t}=a] \\ &=R(s,a)+\gamma \mathbb{E}[V(s_{t+1})|s_{t}=s,a_{t}=a]\\ &=R(s,a)+\gamma \sum_{s^{\prime} \in S} p\left(s^{\prime} \mid s,a\right) V\left(s^{\prime}\right) \end{aligned} \]

贝尔曼期望方程

我们可以把状态价值函数和动作价值函数拆解成两个部分：即使奖励和后续状态的折扣价值(discounted valud of sucessor state)。

通过对状态价值函数的分解，我们就可以得到一个类似于之前马尔可夫奖励过程的贝尔曼方程——贝尔曼期望方程（Bellman expectation equation）：

\[ V_{\pi}(s)=\mathbb{E}_{\pi}\left[r_{t+1}+\gamma V_{\pi}\left(s_{t+1}\right) \mid s_{t}=s\right] \tag{2.6} \]

对于动作价值函数，我们也可以做类似的分解，得到动作价值函数的贝尔曼期望方程：

\[ Q_{\pi}(s, a)=\mathbb{E}_{\pi}\left[r_{t+1}+\gamma Q_{\pi}\left(s_{t+1}, a_{t+1}\right) \mid s_{t}=s, a_{t}=a\right] \tag{2.7} \]

贝尔曼期望方程定义了当前状态与未来状态之间的联系。

我们进一步进行简单的分解，先给出式（2.8）：

\[ V_{\pi}(s)=\sum_{a \in A} \pi(a \mid s) Q_{\pi}(s, a) \tag{2.8} \]

接着，我们再给出式（2.9）：

\[ Q_{\pi}(s, a)=R(s,a)+\gamma \sum_{s^{\prime} \in S} p\left(s^{\prime} \mid s, a\right) V_{\pi}\left(s^{\prime}\right) \tag{2.9} \]

式（2.8）和式（2.9）表示了状态价值函数与动作价值函数之间的关系。

我们把式（2.9）代入式（2.8），就可以得到：

\[ V_{\pi}(s)=\sum_{a \in A} \pi(a \mid s)\left(R(s, a)+\gamma \sum_{s^{\prime} \in S} p\left(s^{\prime} \mid s, a\right) V_{\pi}\left(s^{\prime}\right)\right) \tag{2.10} \]

其矩阵形式为：

\[ R \in \mathbb{R}^{NM \times 1} = \left( \begin{array}{c} R(s_1,a_1)\\ R(s_1,a_2)\\ \vdots\\ R(s_N,a_M)\\ \end{array}\right) \]

\[ Q \in \mathbb{R}^{NM \times 1} = \left( \begin{array}{c} Q(s_1,a_1)\\ Q(s_1,a_2)\\ \vdots\\ Q(s_N,a_M)\\ \end{array}\right) \]

\[ V \in \mathbb{R}^{N \times 1} = \left( \begin{array}{c} V(s_1)\\ V(s_2)\\ \vdots\\ V(s_N)\\ \end{array}\right) \]

\[ P \in \mathbb{R}^{NM \times N} = \left( \begin{array}{c} p(s_1 \mid s_1, a_1) & p(s_2 \mid s_1, a_1) & \cdots & p(s_N \mid s_1, a_1)\\ p(s_1 \mid s_1, a_2) & p(s_2 \mid s_1, a_2) & \cdots & p(s_N \mid s_1, a_2)\\ \vdots & \vdots & \ddots & \vdots\\ p(s_1 \mid s_N, a_M) & p(s_2 \mid s_N, a_M) & \cdots & p(s_N \mid s_N, a_M) \end{array}\right) \]

\[ \Pi \in \mathbb{R}^{N \times NM} = \left( \begin{array}{c} \pi(a_1 \mid s_1) & \pi(a_2 \mid s_1) & \cdots & \pi(a_M \mid s_1) & 0 & 0 & \cdots & 0 & 0 & 0 & \cdots & 0 & 0\\ 0 & 0 & 0 & 0 &\pi(a_1 \mid s_2) & \pi(a_2 \mid s_2) & \cdots & \pi(a_M \mid s_2) & 0 & 0 & \cdots & 0 & 0\\ \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \ddots & \vdots & \vdots & \vdots & \vdots\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & \cdots & \pi(a_1 \mid s_N) & \pi(a_2 \mid s_N) & \cdots & \pi(a_M \mid s_N)\\ \end{array}\right) \]

\[ Q = R + \gamma PV \]

\[ V = \Pi Q = \Pi(R + \gamma PV) = \Pi R + \gamma \Pi PV \]

若记\(R^\pi = \Pi R \in \mathbb{R}^{N \times 1}, P^\pi = \Pi P \in \mathbb{R}^{N \times N}\)，则：

\[ V = R^\pi + \gamma P^\pi V \]

其中\(R^\pi\)是给定策略\(\pi\)下的MDP的等效MRP的奖励函数，\(P^\pi\)是给定策略\(\pi\)下的MDP的等效MRP的状态转移概率矩阵。

式（2.10）表示了当前状态的价值与未来状态价值之间的关系。

我们把式（2.8）代入式（2.9），就可以得到：

\[ Q_{\pi}(s, a)=R(s, a)+\gamma \sum_{s^{\prime} \in S} p\left(s^{\prime} \mid s, a\right) \sum_{a^{\prime} \in A} \pi\left(a^{\prime} \mid s^{\prime}\right) Q_{\pi}\left(s^{\prime}, a^{\prime}\right) \tag{2.11} \]

式（2.11）表示了当前状态的动作价值与未来状态的动作价值之间的关系。

式(2.10)和式(2.11)是贝尔曼期望方程的另一种形式。

最优策略与最优价值函数

解决一个强化学习问题，就是找出一个策略，使得在该策略下，能够获得较多的长期回报。对于优先MDP，我们可以通过下面的方式来定义最优策略。首先，如果对于所有的状态\(s\)，都有\(\pi\)的期望奖励大于\(\pi^\prime\)的期望奖励，我们则称策略\(\pi\)比较策略\(\pi^\prime\)好（better than），即：

\[ \pi \geq \pi^\prime \Leftrightarrow V_{\pi}(s) \geq V_{\pi^\prime}(s), \forall s \in S \]

而实时上，MDP中存在一个策略好比其他策略都要好，我们称这个策略为最优策略（optimal policy）。尽管有可能存在多个最优策略，我们用\(\pi_*\)来表示最优策略，它们共享相同的状态价值函数，称作最优状态价值函数（optimal state-value function）\(V_*\)，其定义为：

\[ V_*(s) = \max_{\pi} V_{\pi}(s), \forall s \in S \]

最优策略也共享相同的动作价值函数，称作最优动作价值函数（optimal action-value function）\(Q_*\)，其定义为：

\[ Q_*(s, a) = \max_{\pi} Q_{\pi}(s, a), \forall s \in S, \forall a \in A \]

在动作价值函数中，对于给定的\((s,a)\)，Q函数的返回值表示在\(s\)状态下采取\(a\)行为，并且在后续过程中采用最优策略能够获得的期望回报。因为其可以写成如下等式：

\[ Q_*(s, a) = \mathbb{E}\left[{R_{t+1} + \gamma V_*(S_{t+1}) \mid S_t = s, A_t = a}\right] \]

因为\(V_*\)是某个策略的值函数，它必须满足状态值的自洽条件（贝尔曼方程）。然而，由于它是最优价值函数，\(V_*\)的自洽条件可以写成一种特殊形式，而不需要参考任何特定策略。这就是关于\(V_*\)的贝尔曼方程，或称 贝尔曼最优方程 。直观上，贝尔曼最优方程表达了这样一个事实：在最优策略下，一个状态的价值必须等于从该状态出发采取最佳动作的期望回报：

\[ \begin{align*} V_*(s) &= \max_{a \in A(s)} Q_{\pi_*}(s,a) \\ &= \max_{a \in A(s)} \mathbb{E}_{\pi_*}[G_t \mid S_t = s, A_t = a] \\ &= \max_{a \in A(s)} \mathbb{E}_{\pi_*}\left[R_{t+1} + \gamma G_{t+1} \mid S_t = s, A_t = a\right] \\ &= \max_{a \in A(s)} \mathbb{E}_{\pi_*}\left[R_{t+1} + \gamma V_*(S_{t+1}) \mid S_t = s, A_t = a\right] \\ &= \max_{a \in A(s)} \sum_{s',r} p(s',r|s,a) \left[ r + \gamma V_*(s') \right] \tag{3.19}\\ \end{align*} \]

同样，对于动作价值函数\(Q_*\)，我们也可以得到它的贝尔曼最优方程：

\[ \begin{align*} Q_*(s,a) &= \mathbb{E}\left[{R_{t+1} + \gamma V_*(S_{t+1}) \mid S_t = s, A_t = a}\right] \\ &= \mathbb{E}\left[R_{t+1} + \gamma \max_{a'} Q_*(S_{t+1},a') \mid S_t = s, A_t = a\right] \\ &=\sum_{s',r} p(s',r|s,a) \left[ r + \gamma \max_{a'} Q_*(s',a') \right] \\ \end{align*} \]

显式求解贝尔曼最优方程提供了一种寻找最优策略的途径，从而解决强化学习问题。然而，这种解法很少能直接有用。它类似于穷举搜索，需要遍历所有可能性，计算它们发生的概率及其期望回报。

这种解法依赖于三个在实践中很少成立的假设：

  1. 环境的动态特性被准确知晓；
  2. 计算资源足以完成计算；
  3. 状态具有马尔可夫性质。

在我们感兴趣的任务中，通常无法精确实现这个解法，因为这些假设中的某些往往会被违背。例如，在西洋双陆棋游戏中，虽然第一和第三条假设没有问题，但第二条假设是主要障碍。因为该游戏约有\(10^{20}\)个状态，即使用当今最快的计算机也需要数千年才能求解\(v_*\)的贝尔曼方程，寻找\(q_*\)也同样如此。因此在强化学习中，通常会求取近似解(后续介绍的策略迭代和价值迭代就是)，而非精确解。

预测与控制

预测（prediction）和控制（control）是马尔可夫决策过程里面的核心问题。

预测（评估一个给定的策略）的输入是马尔可夫决策过程 \(S,A,P,R,\gamma\)和策略\(\pi\)，输出是价值函数\(V_\pi\)。预测是指给定一个马尔可夫决策过程以及一个策略\(\pi\)，计算它的价值函数，也就是计算每个状态的价值。

控制（搜索最佳策略）的输入是马尔可夫决策过程\(S,A,P,R,\gamma\)，输出是最佳价值函数（optimal value function）\(V^*\)和最佳策略（optimal policy）\(\pi^*\)。控制就是我们去寻找一个最佳的策略，然后同时输出它的最佳价值函数以及最佳策略。

在马尔可夫决策过程里面，预测和控制都可以通过动态规划解决。要强调的是，这两者的区别就在于，预测问题是给定一个策略，我们要确定它的价值函数是多少。而控制问题是在没有策略的前提下，我们要确定最佳的价值函数以及对应的决策方案。实际上，这两者是递进的关系，在强化学习中，我们通过解决预测问题，进而解决控制问题。

举一个例子来说明预测与控制的区别。首先是预测问题。在图 2.16a 的方格中，我们规定从\(A \rightarrow A^\prime\)可以得到 +10 的奖励，从\(B \rightarrow B^\prime\)可以得到 +5 的奖励，其他步骤的奖励为 -1。如图 2.16b 所示，现在，我们给定一个策略：在任何状态中，智能体的动作模式都是随机的，也就是上、下、左、右的概率均为0.25。预测问题要做的就是，求出在这种决策模式下，价值函数是什么。图 2.16c 是对应的价值函数。

图 2.16 网格世界例子：预测

接着是控制问题。在控制问题中，问题背景与预测问题的相同，唯一的区别就是：不再限制策略。也就是动作模式是未知的，我们需要自己确定。 所以我们通过解决控制问题，求得每一个状态的最优的价值函数，如图 2.17b 所示；也得到了最优的策略，如图 2.17c 所示。

控制问题要做的就是，给定同样的条件，求出在所有可能的策略下最优的价值函数是什么，最优策略是什么。

图 2.17 网格世界例子：控制

马尔可夫决策过程控制

策略评估是指给定马尔可夫决策过程和策略，我们可以估算出价值函数的值。但是如果我们只有马尔可夫决策过程，那么应该如何找到最佳的策略，从而得到最佳价值函数（optimal value function）呢？

最佳价值函数的定义为：

\[ V^{*}(s)=\max_{\pi} V_{\pi}(s) \]

最佳价值函数是指，我们搜索一种策略\(\pi\)，让每个状态的价值最大。\(V^*(s)\)就是到达每一个状态，它的值的最大化情况。

使得每个状态的价值都最大化的策略称为 最优策略（optimal policy），记为\(\pi^*\)，即

\[ \pi^{*}(s)=\arg \max_{\pi} V_{\pi}(s) \]

最佳策略使得每个状态的价值函数都取得最大值。所以如果我们可以得到一个最佳价值函数，就可以认为某个马尔可夫决策过程的环境可解。在这种情况下，最佳价值函数是一致的，环境中可达到的上限的值是一致的，但这里可能有多个最佳策略，多个最佳策略可以取得相同的最佳价值。

当取得最佳价值函数后，我们可以通过对Q函数进行最大化来得到最佳策略：

\[ \pi^{*}(a\mid s)= \begin{cases} 1,\ a = \mathop{\arg\max}\limits_{a \in A} Q_{\pi^{*}}(s, a)\\ 0,\ \text{others} \end{cases} \]

当Q函数收敛后，因为 Q 函数是关于状态与动作的函数，所以如果在某个状态采取某个动作，可以使得 Q 函数最大化，那么这个动作就是最佳的动作。如果我们能优化出一个 Q 函数\(Q^*(s,a)\)，就可以直接在 Q 函数中取一个让 Q 函数值最大化的动作的值，就可以提取出最佳策略。

Q: 怎样进行策略搜索？

A: 最简单的策略搜索方法就是穷举。假设状态和动作都是有限的，那么每个状态我们可以采取\(A\)种动作的策略，总共就是\(|A|^{|S|}\)个可能的策略。我们可以把策略穷举一遍，算出每种策略的价值函数，对比一下就可以得到最佳策略。

但是穷举非常没有效率，所以我们要采取其他方法。搜索最佳策略有两种常用的方法：策略迭代和价值迭代。

寻找最佳策略的过程就是马尔可夫决策过程的控制过程。马尔可夫决策过程控制就是去寻找一个最佳策略使我们得到一个最大的价值函数值，即

\[ \pi^{*}(s)=\mathop{\arg\max}_{\pi} V_{\pi}(s) \]

对于一个事先定好的马尔可夫决策过程，当智能体采取最佳策略的时候，最佳策略一般都是确定的，而且是稳定的（它不会随着时间的变化而变化）。但最佳策略不一定是唯一的，多种动作可能会取得相同的价值。

我们可以通过策略迭代和价值迭代来解决马尔可夫决策过程的控制问题。

备份图

接下来我们介绍 备份（backup） 的概念。备份类似于自举之间的迭代关系，对于某一个状态，它的当前价值是与它的未来价值线性相关的。

我们将与图 2.10 类似的图称为 备份图（backup diagram） 或回溯图，因为它们所示的关系构成了更新或备份操作的基础，而这些操作是强化学习方法的核心。这些操作将价值信息从一个状态（或状态-动作对）的后继状态（或状态-动作对）转移回它。

每一个空心圆圈代表一个状态，每一个实心圆圈代表一个状态-动作对。

图 2.10 V_\pi 备份图

如式(2.12)所示，这里有两层加和。第一层加和是对叶子节点进行加和，往上备份一层，我们就可以把未来的价值（\(s^\prime\)的价值）备份到黑色的节点。

第二层加和是对动作进行加和，得到黑色节点的价值后，再往上备份一层，就会得到根节点的价值，即当前状态的价值。

\[ V_{\pi}(s)=\sum_{a \in A} \pi(a \mid s)\left(R(s, a)+\gamma \sum_{s^{\prime} \in S} p\left(s^{\prime} \mid s, a\right) V_{\pi}\left(s^{\prime}\right)\right) \tag{2.12} \]

图 2.11 所示为状态价值函数的计算分解，图 2.11b 的计算公式为

\[ V_{\pi}(s)=\sum_{a \in A} \pi(a \mid s) Q_{\pi}(s, a) \tag{2.13} \]

图 2.11b 给出了状态价值函数与 Q 函数之间的关系。图 2.11c 计算 Q 函数为

\[ Q_{\pi}(s,a)=R(s, a)+\gamma \sum_{s^{\prime} \in S} p\left(s^{\prime} \mid s, a\right) V_{\pi}\left(s^{\prime}\right) \tag{2.14} \]

我们将式(2.14)代入式(2.13)可得

\[ V_{\pi}(s)=\sum_{a \in A} \pi(a \mid s)\left(R(s, a)+\gamma \sum_{s^{\prime} \in S} p\left(s^{\prime} \mid s, a\right) V_{\pi}\left(s^{\prime}\right)\right) \]

所以备份图定义了未来下一时刻的状态价值函数与上一时刻的状态价值函数之间的关联。

图 2.11 状态价值函数的计算分解

对于 Q 函数，我们也可以进行这样的一个推导。如图 2.12 所示，现在的根节点是 Q 函数的一个节点。Q 函数对应于黑色的节点。下一时刻的 Q 函数对应于叶子节点，有4个黑色的叶子节点。

\[ Q_{\pi}(s, a)=R(s, a)+\gamma \sum_{s^{\prime} \in S} p\left(s^{\prime} \mid s, a\right) \sum_{a^{\prime} \in A} \pi\left(a^{\prime} \mid s^{\prime}\right) Q_{\pi}\left(s^{\prime}, a^{\prime}\right) \tag{2.15} \]

如式(2.15)所示，这里也有两层加和。第一层加和先把叶子节点从黑色节点推到空心圆圈节点，进入到空心圆圈结点的状态。

当我们到达某一个状态后，再对空心圆圈节点进行加和，这样就把空心圆圈节点重新推回到当前时刻的 Q 函数。

图 2.12 行为价值函数的备份图

图 2.13c 中，

\[ V_{\pi}\left(s^{\prime}\right)=\sum_{a^{\prime} \in A} \pi\left(a^{\prime} \mid s^{\prime}\right) Q_{\pi}\left(s^{\prime}, a^{\prime}\right) \tag{2.16} \]

我们将式(2.16)代入式(2.14)可得未来 Q 函数与当前 Q 函数之间的关联，即

\[ Q_{\pi}(s, a)=R(s, a)+\gamma \sum_{s^{\prime} \in S} p\left(s^{\prime} \mid s, a\right) \sum_{a^{\prime} \in A} \pi\left(a^{\prime} \mid s^{\prime}\right) Q_{\pi}\left(s^{\prime}, a^{\prime}\right) \]

图 2.13 Q函数的计算分解

动态规划

动态规划（Dynamic Programming，DP） 是指一类算法的集合，这些算法可以在已知环境完美模型（即马尔可夫决策过程，MDP）的前提下，用于计算最优策略。尽管经典的动态规划算法由于依赖完美模型的假设以及计算开销巨大，在强化学习中的实用性有限，但它们在理论上仍然具有重要意义。动态规划为理解其它RL方法奠定了基础。事实上，这些方法都可以看作是在试图实现与动态规划类似的效果，只是计算量更小，且不依赖于对环境的完美建模。

在动态规划中，我们通常会假设环境是有限MDP。也就是说，我们假设其状态空间\(S\)、动作空间\(A\)和奖励\(R\)都是有限的，并且环境的动力学性质被一组概率分布\(p(s^\prime,r \mid s,a)\)所表示。其中\(s \in S, a \in A, r \in R, s ^ \prime \in S ^+\)(\(S ^ +\)是 \(S\)加上结束状态)

虽然DP的想法也可以用于连续的状态空间和动作空间，但是只有在特殊的情况下，才有精确的解。而一种通常的做法是将连续的状态空间和动作空间量化成离散的，然后应用有限状态DP的方法来求取近似解。

DP和RL的的核心思想都是使用价值函数来寻找好的策略，因此这一章中，我们会介绍如何使用DP来计算价值函数。而只要我们找出了最优的价值函数 \(V_*\)或者最优的动作价值函数 \(Q_*\)，我们就可以很容易得使用贪心的策略获得最优的策略。其中\(V_*\)和\(Q_*\)满足如下的贝尔曼最优方程：

\[ \begin{align*} V_*(s) &= \max_{a \in A} Q_*(s,a) \\ &= \max_{a \in A} \mathbb{E} \left[R_{t+1} + \gamma V_*(S_{t+1}) \mid S_t = s, A_t = a\right] \\ &= \max_{a \in A} \sum_{s^\prime,r} p(s^\prime,r \mid s,a) \left[ r + \gamma V_*(s^\prime) \right] \\ \end{align*} \]

\[ \begin{align*} Q_*(s,a) &= \mathbb{E} \left[R_{t+1} + \gamma V_*(S_{t+1}) \mid S_t = s, A_t = a\right] \\ &= \mathbb{E} \left[R_{t+1} + \gamma \max_{a^\prime} Q_*(S_{t+1},a^\prime) \mid S_t = s, A_t = a\right] \\ &= \sum_{s^\prime,r} p(s^\prime,r \mid s,a) \left[ r + \gamma \max_{a^\prime} Q_*(s^\prime,a^\prime) \right] \\ \end{align*} \]

策略评估

已知马尔可夫决策过程以及要采取的策略\(\pi\)，计算价值函数\(V_\pi(s)\)的过程就是 策略评估。策略评估在有些地方也被称为 （价值）预测[（value）prediction）]，也就是预测我们当前采取的策略最终会产生多少价值。

考虑如下一个更通用版的贝尔曼方程（\(r\)不仅与\(s,a\)相关，而且还与\(s^\prime\)相关）：

\[ \begin{align*} V_{\pi}(s) =& \mathbb{E}_{\pi}\left[G_t \mid S_t = s \right] \\ =& \mathbb{E}_{\pi}\left[R_{t+1} + \gamma G_{t+1} \mid S_t = s \right] \\ =& \mathbb{E}_{\pi}\left[R_{t+1} + \gamma V_{\pi}(S_{t+1}) \mid S_t = s \right] \\ =& \sum_{a \in A} \pi(a|s) \sum_{s^\prime,r} p(s^\prime,r \mid s,a) \left[ r + \gamma V_{\pi}(s^\prime) \right] \end{align*} \]

虽然在策略已知，奖励函数以及状态转移函数已知的情况下，我们可以通过解析解的方式来求解价值函数，但是在实际中，由于运算量太大，因此采用迭代的方案更加合适。

假设有一系列的价值函数的近似\(V_0,V_1,\ldots\)，其中\(V_0\)是初始的近似值函数，可以任意选择（只要terminal state的价值是0就行），然后接下来的近似函数可以通过一下的迭代公式来计算：

\[ V_{k+1}(s) = \sum_{a \in A} \pi(a|s) \sum_{s^\prime,r} p(s^\prime,r \mid s,a) \left[ r + \gamma V_k(s^\prime) \right] \]

随着迭代的进行，\(V_k\)会逐渐收敛到真实的价值函数\(V_\pi\)。我们可以通过以下的公式来判断收敛：

\[ \max_{s \in S} |V_{k+1}(s) - V_k(s)| < \epsilon \]

除此之外，其实迭代的具体实现有多种方式，比如我们可以使用 全局迭代（global iteration） 的方式来进行迭代，也就是每次都对所有的状态进行更新。也可以使用 局部迭代（local iteration） 的方式来进行迭代(也称之为in-place方式)，也就是每次只对一个状态进行更新，而更新另一个状态的价值函数的时候，会使用到上次的更新后的价值函数。局部迭代的方式会更快一些。局部迭代的伪代码如下所示：

**Iterative Policy Evaluation**, for estimating $V \approx v_{\pi}$

  • Input: \(\pi\), the policy to be evaluated
  • Algorithm parameter: small threshold \(\theta > 0\) determining accuracy of estimation
  • Initialize: \(V(s)\) arbitrarily for \(s \in \mathcal{S}\), and \(V(\text{terminal}) \gets 0\)

Loop:
    \(\Delta \gets 0\)
    For each \(s \in \mathcal{S}\):
        \(v \gets V(s)\)
        \(V(s) \gets \sum\limits_a \pi(a|s) \sum\limits_{s', r} p(s', r \mid s, a)\left[r + \gamma V(s')\right]\)
        \(\Delta \gets \max(\Delta, |v - V(s)|)\)
Until \(\Delta < \theta\)

策略评估示例1

考虑一个4x4的网格世界，其状态空间\(S = \{1,2,\cdots,14\}\)，在每个状态下，都有四种可能的行为\(A = \{up, down, right, left\}\)，其奖励满足\(R(s^\prime,s,a) = 1 \; s \in S, s^\prime \in S^+, a \in A\)而且状态转移是确定的（deterministical），当采取动作会导致agent移出网格时，agent会停留在原地。例如，\(p(6,-1\mid 5, right) = 1\)，\(p(7,-1\mid 7,right) = 1\)，\(p(10,r \mid 5,right) = 0\)。假设agent采取随机策略，折扣因子\(\gamma = 1\)，其状态价值函数的计算过程如下图所示：

价值评估示例

策略评估示例2

另一个例子来源于斯坦福大学的一个在线示例，这个网页模拟了DP的价值评估和策略更新的过程。

如图 2.19a 所示，网格世界里面有很多格子，每个格子都代表一个状态。每个格子里面有一个初始值0（初始的状态价值）。每个格子里还有一个箭头，这个箭头是指智能体在当前状态应该采取什么策略。我们这里采取随机的策略，即朝着各个箭头方向运动的概率都是相同的。比如在某个状态，智能体都有上、下、左、右各 0.25 的概率采取某一个动作，所以它的动作是完全随机的。而奖励函数通过格子里面的R表示（需要注意的是，格子里面的R表示的是在该状态采取的任何行动的奖励都是R，而不是到达该状态所能获得的奖励）。我们可以看到有几个格子里面R的值是-1，只有一个格子的R为+1，那些没有写R的表示R为0。奖励的折扣因子\(\gamma = 0.9\)

在这样的环境里面，我们想计算每一个状态的价值。

如图 2.19b 所示，我们开始策略评估，策略评估是一个不停迭代的过程。当我们初始化的时候，所有的\(V(s)\)都是 0。我们现在迭代一次，迭代一次之后，有些状态的值已经产生了变化。

图 2.19 网格世界：动态规划示例

如图 2.20a 所示，我们再迭代一次，之前有值的状态的周围状态也开始有值。因为周围状态与之前有值的状态是临近的，所以这就相当于把周围的状态转移过来。如图 2.20b 所示，我们逐步迭代，值是一直在变换的。

图 2.20 网格世界：策略评估过程示例

当我们迭代了很多次之后，有些很远的状态的价值函数已经有值了，而且整个过程是一个呈逐渐扩散的过程，这其实也是策略评估的可视化。当我们每一步进行迭代的时候，远的状态就会得到一些值，值从已经有奖励的状态逐渐扩散。当我们执行很多次迭代之后，各个状态的值会逐渐稳定下来，最后值就会确定不变。收敛之后，每个状态的值就是它的状态价值。

策略提升

使用策略评估来计算给定策略的价值函数的目的是为了找出更好的策略。假设在一个确定策略（deterministic policy）\(\pi\)下，我们已经计算出了状态价值函数\(V_{\pi}(s)\)。对于某些状态\(s\)，我们想要知道的是，我们是否应该改变我们的策略，去选择action \(a \neq \pi(s)\)？首先，我们知道如果我们在状态\(s\)的时候，按照策略\(\pi\)来执行的话，能获得的好处——\(V_{\pi}(s)\)，但是我们并不知道，如果我们使用新的策略\(\pi^\prime\)，效果是否会变得更好。

为了解决这个问题，我们可以假设我们在\(s\)的第一步的时候，选择动作\(a\)，然后在\(s\)的后续步骤中，使用策略\(\pi\)。其行为价值函数为：

\[ \begin{align*} Q_{\pi}(s,a) &=\mathbb{E}\left[R_{t+1} + \gamma V_{\pi}(S_{t+1}) \mid S_t = s, A_t = a\right] \\ &=\sum_{s^\prime,r} p(s^\prime,r \mid s,a) \left[ r + \gamma V_{\pi}(s^\prime) \right] \end{align*} \]

假设现在有两个确定策略（deterministic policy）\(\pi\)和\(\pi^\prime\)，如果有(称之为策略提升定理)

\[ Q_{\pi}(s,\pi^\prime(s)) \geq V_{\pi}(s) \; for\ all\ s \in S \]

那么是可以证明

\[ V_{\pi^\prime}(s) \geq V_{\pi}(s) \]

证明

\[ \begin{align*} V_{\pi}(s) &\leq Q_{\pi}(s, \pi'(s)) \\ &= \mathbb{E} [ R_{t+1} + \gamma V_{\pi}(S_{t+1}) \mid S_t = s, A_t = \pi'(s) ] \\ &= \mathbb{E}_{\pi'} [ R_{t+1} + \gamma V_{\pi}(S_{t+1}) \mid S_t = s ] \\ &\leq \mathbb{E}_{\pi'} [ R_{t+1} + \gamma Q_{\pi}(S_{t+1}, \pi'(S_{t+1})) \mid S_t = s ] \\ &= \mathbb{E}_{\pi'} \left[ R_{t+1} + \gamma \mathbb{E} [ R_{t+2} + \gamma V_{\pi}(S_{t+2}) \mid S_{t+1}, A_{t+1} = \pi'(S_{t+1}) ] \mid S_t = s \right] \\ &= \mathbb{E}_{\pi'} [ R_{t+1} + \gamma R_{t+2} + \gamma^2 V_{\pi}(S_{t+2}) \mid S_t = s ] \\ &\leq \mathbb{E}_{\pi'} [ R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + \gamma^3 V_{\pi}(S_{t+3}) \mid S_t = s ] \\ &\quad \vdots \\ &\leq \mathbb{E'}_{\pi'} [ R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + \gamma^3 R_{t+4} + \cdots \mid S_t = s ] \\ &= V_{\pi'}(s) \end{align*} \]

因此如果我们根据\(q_{\pi}(s,a)\)的值，并且使用新的贪婪的策略\(\pi^\prime\)，其定义如下：

\[ \begin{align*} \pi'(s) &\doteq \mathop{\arg\max}_{a} Q_{\pi}(s, a) \\ &= \mathop{\arg\max}_{a} \mathbb{E} \left[ R_{t+1} + \gamma V_{\pi}(S_{t+1}) \mid S_t = s, A_t = a \right] \\ &= \mathop{\arg\max}_{a} \sum_{s', r} p(s', r \mid s, a) \left[ r + \gamma V_{\pi}(s') \right] \end{align*} \]

很明显，这个新的贪婪策略\(\pi^\prime\)满足上述的策略提升定理的条件，所以这个新的策略所产生的价值函数一定大于或者等于原来的策略所产生的价值函数。这种使用原先策略的动作价值函数，并使用贪婪的方案来选择动作来得到新的策略的方式称为 策略提升（policy improvement）。

如果新的贪婪策略\(\pi^\prime\)与原来的策略\(\pi\)的价值函数相同，即\(V_{\pi} = V_{\pi^\prime}\)，结合上述\(V_{\pi^\prime}\)的定义，可以得到如下等式：

\[ \begin{align*} V_{\pi^\prime}(s) &= \max_{a}\mathbb{E} \left[ R_{t+1} + \gamma V_{\pi^\prime}(S_{t+1}) \mid S_t = s, A_t = a \right] \\ &= \max_{a}\sum_{s', r} p(s', r \mid s, a) \left[ r + \gamma V_{\pi^\prime}(s') \right] \\ \end{align*} \]

该等是与贝尔曼最优方程是一样的，因此，\(V_{\pi^\prime}\)一定就是\(V_*\)，而且\(\pi\)与\(\pi^\prime\)都是最优策略。因此，策略提升一定会我们一个更好的策略，除非原始的策略就是最优策略。

到目前为止，上述关于策略提升的讨论主要是针对于特殊的情况，即确定策略(deterministic policy)。但是我们也可以将上述的讨论推广到随机策略（stochastic policy）上。上述的结论对于随机策略来说依然成立。

依据贪婪策略\(\pi^\prime\)的定义，我们选择使得\(Q_\pi(s,a)\)最大的动作，最为新策略\(\pi^\prime\)的动作。但是有可能存在多个动作\(a\)，都使得\(Q_\pi(s,a)\)最大。在确定策略的情况下，随便选一个就行了，但是对于随机策略，我们不需要只选取一个动作，而是可以为这些最大化\(Q_\pi(s,a)\)动作中的每一个分配一定的被选中概率，从而构成新的贪婪策略。只要所有非最大化\(Q_\pi(s,a)\)的动作被赋予零概率，任何这种分配方式都是允许的。

策略迭代

一旦一个策略\(\pi\)被使用\(V_\pi\)改进，生成了一个更优的策略\(\pi'\)，我们就可以计算\(V_{\pi'}\)，并再次进行改进，得到一个更优的策略\(\pi''\)。如此，我们可以得到一系列单调改进的策略和值函数：

\[ \pi_0 \xrightarrow{E} V_{\pi_0} \xrightarrow{I} \pi_1 \xrightarrow{E} V_{\pi_1} \xrightarrow{I} \pi_2 \xrightarrow{E} \cdots \xrightarrow{I} \pi_* \xrightarrow{E} V_*, \]

其中：

  • \(\xrightarrow{E}\)表示策略评估（Evaluation）；
  • \(\xrightarrow{I}\)表示策略改进（Improvement）。

每一步策略都会是对前一步的严格改进（除非策略已经是最优）。由于有限的马尔可夫决策过程（MDP）只拥有有限个确定性策略，因此这个过程必定在有限步内收敛到一个最优策略\(\pi_*\)和最优价值函数\(V_*\)。

这种寻找最优策略的方法被称为 策略迭代（Policy Iteration）。完整的算法在下方的框中给出。

Note

注意：每次策略评估本身是一个迭代计算，它从前一个策略对应的值函数作为初始值开始。这样可以极大地加快策略评估的收敛速度（因为值函数在两个策略之间变化通常较小）。

Policy Iteration（using iterative policy evaluation）for estimating $\pi \approx \pi_*$

  1. Initialization
     \(V(s) \in \mathbb{R}\) and \(\pi(s) \in \mathcal{A}(s)\) arbitrarily for all \(s \in \mathcal{S}\)；\(V(\text{terminal}) \doteq 0\)

  2. Policy Evaluation
     Loop:
      \(\Delta \leftarrow 0\)
      Loop for each \(s \in \mathcal{S}\):
       \(v \leftarrow V(s)\)
       \(V(s) \leftarrow \sum_{s', r} p(s', r \mid s, \pi(s)) \left[ r + \gamma V(s') \right]\)
       \(\Delta \leftarrow \max(\Delta, |v - V(s)|)\)
     until \(\Delta < \theta\)（其中 \(\theta\) 是一个决定估计精度的小正数）

  3. Policy Improvement
     \(\textit{policy-stable} \leftarrow \text{true}\)
     For each \(s \in \mathcal{S}\):
      \(\textit{old-action} \leftarrow \pi(s)\)
      \(\pi(s) \leftarrow \mathop{\arg\max}\limits_a \sum_{s', r} p(s', r \mid s, a) \left[ r + \gamma V(s') \right]\)
      If \(\textit{old-action} \ne \pi(s)\)，then \(\textit{policy-stable} \leftarrow \text{false}\)
     If \(\textit{policy-stable}\)，then：
      stop and return \(V \approx v_*\)，\(\pi \approx \pi_*\)
     else go to step 2

价值迭代

策略迭代的一个确定是，在每一次迭代过程中，都需要进行策略评估，而策略评估本身就是一个迭代过程（需要多次扫描整个状态空间，直到价值函数收敛到\(V_\pi\)）。

但是我们是否需要等到策略评估精确收敛之后，再进行策略提升？还是说我们可以在策略评估中只迭代几次就直接退出，然后直接进行策略提升呢？实施证明后者是可行的，即我们可以截断策略评估，其中一个比较特殊的截断方案是，我们在策略评估时，只扫描一次状态空间（每个状态只更新一次），这个算法就是价值迭代（Value Iteration）。

结合策略提升和截断的策略评估，我们可以得到如下的更新方程：

\[ \begin{align*} V_{k+1}(s) &= \max_{a} \mathbb{E} \left[ R_{t+1} + \gamma V_k(S_{t+1}) \mid S_t = s, A_t = a \right] \\ &= \max_{a} \sum_{s', r} p(s', r \mid s, a) \left[ r + \gamma V_k(s') \right] \end{align*} \]

另一个理解价值迭代的方法是通过贝尔曼最优方程。可以发现，价值迭代只是简单得将贝尔曼最优方程转换成了更新规则。

最后，让我们考虑价值迭代的终止条件。像策略评估一样，价值迭代通常需要无限次的迭代才能完全收敛到\(V_*\)。但是实际上，一旦在迭代过程中，价值函数的变化很小，我们就会停止。下面的框显示了具有这种终止条件的完整算法。

Value Iteration. for estimating $\pi \approx \pi_*$

Algorithm parameter: a small threshold \(\theta > 0\) determining accuracy of estimation
Initialize \(V(s)\), for all \(s \in \mathcal{S}^+\), arbitrarily except that \(V(\text{terminal}) = 0\)

Loop:
 \(\Delta \leftarrow 0\)
 Loop for each \(s \in \mathcal{S}\):
  \(v \leftarrow V(s)\)
  \(V(s) \leftarrow \max_a \sum_{s', r} p(s', r \mid s, a) \left[ r + \gamma V(s') \right]\)
  \(\Delta \leftarrow \max(\Delta, |v - V(s)|)\)
until \(\Delta < \theta\)

Output a deterministic policy, \(\pi \approx \pi_*\), such that
\(\pi(s) = \mathop{\arg\max}\limits_a \sum_{s', r} p(s', r \mid s, a) \left[ r + \gamma V(s') \right]\)