这是用户在 2025-7-16 21:37 为 https://app.immersivetranslate.com/pdf-pro/b47f92c4-4e5b-49ae-884c-24259d39157e/ 保存的双语快照页面，由 沉浸式翻译 提供双语支持。了解如何保存？

  4. MDP

  4. MDP

  作者：Nikhil Sharma
编辑：Saathvik Selvan 和 Wesley Zheng
致谢：部分章节改编自教材《人工智能：一种现代方法》。
上次更新：2024年10月

4.1 马尔可夫决策过程

4.1 马尔可夫决策过程

马尔可夫决策过程由以下几个属性定义：
  • 一个状态集合 S S SS 。MDP 中的状态与传统搜索问题中的状态表示方式相同。
  • 一个动作集合 A A AA 。MDP 中的动作也与传统搜索问题中的动作表示方式相同。
  •   一个起始状态。
  • 可能有一个或多个终止状态。
  • 可能有一个折扣因子 γ γ gamma\gamma 。我们稍后会介绍折扣因子。
  • 一个转移函数 T ( s , a , s ′ ) T s , a , s ′ T(s,a,s^('))T\left(s, a, s^{\prime}\right) 。由于我们引入了非确定性行为的可能性，我们需要一种方法来描述从任何给定状态采取任何给定行为后可能出现的结果的可能性。MDP 的转移函数正是这样做的——它是一个概率函数，表示智能体从状态 s ∈ S s ∈ S s in Ss \in S 采取行动 a ∈ A a ∈ A a in Aa \in A 最终到达状态 s ′ ∈ S s ′ ∈ S s^(')in Ss^{\prime} \in S 的概率。
  • 一个奖励函数 R ( s , a , s ′ ) R s , a , s ′ R(s,a,s^('))R\left(s, a, s^{\prime}\right) 。通常，MDP 会为每一步建模小的“生存”奖励，以奖励智能体的生存，以及到达终止状态的大额奖励。奖励可以是正的或负的，取决于它们是否有利于相关的智能体，智能体的目标自然是在到达某个终止状态之前获得尽可能多的奖励。
为一个情境构建一个 MDP 与为一个搜索问题构建一个状态空间图非常相似，但有一些额外的注意事项。考虑一下赛车的例子：
图1：赛车示例
有三种可能的状态， S = { S = { S={S=\{ 冷，暖，过热 } } }\} ，以及两种可能的动作 A = { A = { A={A=\{ 慢，快 } } }\} 。就像在状态空间图中一样，三种状态中的每一种都由一个节点表示，边表示动作。“过热”是一个终止状态，因为一旦赛车代理到达这个状态，它就不能再
执行任何动作以获得进一步的奖励（它是 MDP 中的一个汇聚状态，没有输出边）。值得注意的是，对于非确定性动作，有多条边表示来自同一状态的相同动作，但后继状态不同。每条边不仅用它所代表的动作来注释，还用转移概率和相应的奖励来注释。这些总结如下：
转移函数： T ( s , a , s ′ ) − T ( T s , a , s ′ − T ( T(s,a,s^('))-T(T\left(s, a, s^{\prime}\right)-T( 凉爽，慢速，凉爽 ) = 1 − T ( ) = 1 − T ( )=1-T()=1-T( 温暖，慢速，凉爽 ) = 0.5 − T ( ) = 0.5 − T ( )=0.5-T()=0.5-T( 温暖，慢速，温暖 ) = ) = )=)= 0.5 − T ( 0.5 − T ( 0.5-T(0.5-T( 凉爽，快速，凉爽 ) = 0.5 − T ( ) = 0.5 − T ( )=0.5-T()=0.5-T( 凉爽，快速，温暖 ) = 0.5 − T ( ) = 0.5 − T ( )=0.5-T()=0.5-T( 温暖，快速，过热 ) = 1 ) = 1 )=1)=1
奖励函数： R ( s , a , s ′ ) − R ( R s , a , s ′ − R ( R(s,a,s^('))-R(R\left(s, a, s^{\prime}\right)-R( 凉爽，慢速，凉爽 ) = 1 − R ( ) = 1 − R ( )=1-R()=1-R( 温暖，慢速，凉爽 ) = 1 − R ( ) = 1 − R ( )=1-R()=1-R( 温暖，慢速，温暖 ) = ) = )=)= 1 − R ( 1 − R ( 1-R(1-R( 凉爽，快速，凉爽 ) = 2 − R ( ) = 2 − R ( )=2-R()=2-R( 凉爽，快速，温暖 ) = 2 − R ( ) = 2 − R ( )=2-R()=2-R( 温暖，快速，过热 ) = − 10 ) = − 10 )=-10)=-10
我们用离散的时间步长来表示一个智能体在不同 MDP 状态下的移动，定义 s t ∈ S s t ∈ S s_(t)in Ss_{t} \in S 和 a t ∈ A a t ∈ A a_(t)in Aa_{t} \in A 分别为智能体在时间步 t t tt 时所处的状态和采取的动作。智能体从时间步 0 的状态 s 0 s 0 s_(0)s_{0} 开始，并在每个时间步采取一个动作。因此，智能体在 MDP 中的移动可以建模如下：
s 0 → a 0 s 1 → a 1 s 2 → a 2 s 3 → a 3 … s 0 → a 0 s 1 → a 1 s 2 → a 2 s 3 → a 3 … s_(0)rarr"a_(0)"s_(1)rarr"a_(1)"s_(2)rarr"a_(2)"s_(3)rarr"a_(3)"dotss_{0} \xrightarrow{a_{0}} s_{1} \xrightarrow{a_{1}} s_{2} \xrightarrow{a_{2}} s_{3} \xrightarrow{a_{3}} \ldots
此外，考虑到智能体的目标是最大化其在所有时间步中的奖励，我们可以相应地将其在数学上表达为以下效用函数的最大化：
U ( [ s 0 , a 0 , s 1 , a 1 , s 2 , … ] ) = R ( s 0 , a 0 , s 1 ) + R ( s 1 , a 1 , s 2 ) + R ( s 2 , a 2 , s 3 ) + … U s 0 , a 0 , s 1 , a 1 , s 2 , … = R s 0 , a 0 , s 1 + R s 1 , a 1 , s 2 + R s 2 , a 2 , s 3 + … U([s_(0),a_(0),s_(1),a_(1),s_(2),dots])=R(s_(0),a_(0),s_(1))+R(s_(1),a_(1),s_(2))+R(s_(2),a_(2),s_(3))+dotsU\left(\left[s_{0}, a_{0}, s_{1}, a_{1}, s_{2}, \ldots\right]\right)=R\left(s_{0}, a_{0}, s_{1}\right)+R\left(s_{1}, a_{1}, s_{2}\right)+R\left(s_{2}, a_{2}, s_{3}\right)+\ldots
马尔可夫决策过程，就像状态空间图一样，可以展开成搜索树。不确定性在这些搜索树中用 Q 状态建模，Q 状态也称为动作状态，本质上与期望最大化机会节点相同。这是一个合适的选择，因为 Q 状态使用概率来模拟环境将智能体置于给定状态的不确定性，正如期望最大化机会节点使用概率来模拟对抗智能体通过他们选择的移动将我们的智能体置于给定状态的不确定性。从状态 s s ss 采取动作 a a aa 所表示的 Q 状态表示为元组 ( s , a s , a s,as, a )。
观察我们赛车的展开搜索树，截断为深度 2：
图 2：赛车搜索树
绿色节点代表 Q 状态，即从一个状态采取了行动，但尚未解析为后继状态。重要的是要理解，智能体在 Q 状态中花费的时间步为零，它们只是为了便于表示和开发 MDP 算法而创建的结构。

4.1.1 有限范围和折扣

我们的赛车 MDP 存在一个固有的问题——我们没有对赛车可以采取行动并收集奖励的时间步数设置任何时间限制。按照我们目前的公式，它可能会
总是选择 a = a = a=a= ，在每个时间步都无限缓慢，安全有效地获得无限奖励，而没有任何过热的风险。有限视界和/或折扣因子的引入可以防止这种情况。强制执行有限视界的 MDP 很简单——它本质上定义了智能体的“生命周期”，这给了它们一定数量的时间步 n n nn ，以便在自动终止之前积累尽可能多的奖励。我们稍后会回到这个概念。
折扣因子稍微复杂一些，它的引入是为了模拟奖励价值随时间的指数衰减。具体来说，如果折扣因子为 γ γ gamma\gamma ，在时间步 t t tt 从状态 s t s t s_(t)s_{t} 采取行动 a t a t a_(t)a_{t} 并最终进入状态 s t + 1 s t + 1 s_(t+1)s_{t+1} ，则会产生 γ t R ( s t , a t , s t + 1 ) γ t R s t , a t , s t + 1 gamma^(t)R(s_(t),a_(t),s_(t+1))\gamma^{t} R\left(s_{t}, a_{t}, s_{t+1}\right) 的奖励，而不是仅仅 R ( s t , a t , s t + 1 ) R s t , a t , s t + 1 R(s_(t),a_(t),s_(t+1))R\left(s_{t}, a_{t}, s_{t+1}\right) 。现在，我们不再是最大化累加效用
U ( [ s 0 , a 0 , s 1 , a 1 , s 2 , … ] ) = R ( s 0 , a 0 , s 1 ) + R ( s 1 , a 1 , s 2 ) + R ( s 2 , a 2 , s 3 ) + … U s 0 , a 0 , s 1 , a 1 , s 2 , … = R s 0 , a 0 , s 1 + R s 1 , a 1 , s 2 + R s 2 , a 2 , s 3 + … U([s_(0),a_(0),s_(1),a_(1),s_(2),dots])=R(s_(0),a_(0),s_(1))+R(s_(1),a_(1),s_(2))+R(s_(2),a_(2),s_(3))+dotsU\left(\left[s_{0}, a_{0}, s_{1}, a_{1}, s_{2}, \ldots\right]\right)=R\left(s_{0}, a_{0}, s_{1}\right)+R\left(s_{1}, a_{1}, s_{2}\right)+R\left(s_{2}, a_{2}, s_{3}\right)+\ldots
而是尝试最大化折扣效用
U ( [ s 0 , a 0 , s 1 , a 1 , s 2 , … ] ) = R ( s 0 , a 0 , s 1 ) + γ R ( s 1 , a 1 , s 2 ) + γ 2 R ( s 2 , a 2 , s 3 ) + … U s 0 , a 0 , s 1 , a 1 , s 2 , … = R s 0 , a 0 , s 1 + γ R s 1 , a 1 , s 2 + γ 2 R s 2 , a 2 , s 3 + … U([s_(0),a_(0),s_(1),a_(1),s_(2),dots])=R(s_(0),a_(0),s_(1))+gamma R(s_(1),a_(1),s_(2))+gamma^(2)R(s_(2),a_(2),s_(3))+dotsU\left(\left[s_{0}, a_{0}, s_{1}, a_{1}, s_{2}, \ldots\right]\right)=R\left(s_{0}, a_{0}, s_{1}\right)+\gamma R\left(s_{1}, a_{1}, s_{2}\right)+\gamma^{2} R\left(s_{2}, a_{2}, s_{3}\right)+\ldots
注意到上述折扣效用函数的定义类似于比率为 γ γ gamma\gamma 的几何级数，我们可以证明，只要满足约束 | γ | < 1 | γ | < 1 |gamma| < 1|\gamma|<1 （其中 | n | | n | |n||n| 表示绝对值运算符），它就保证是有限值的，逻辑如下：
U ( [ s 0 , s 1 , s 2 , … ] ) = R ( s 0 , a 0 , s 1 ) + γ R ( s 1 , a 1 , s 2 ) + γ 2 R ( s 2 , a 2 , s 3 ) + … U s 0 , s 1 , s 2 , … = R s 0 , a 0 , s 1 + γ R s 1 , a 1 , s 2 + γ 2 R s 2 , a 2 , s 3 + … U([s_(0),s_(1),s_(2),dots])=R(s_(0),a_(0),s_(1))+gamma R(s_(1),a_(1),s_(2))+gamma^(2)R(s_(2),a_(2),s_(3))+dotsU\left(\left[s_{0}, s_{1}, s_{2}, \ldots\right]\right)=R\left(s_{0}, a_{0}, s_{1}\right)+\gamma R\left(s_{1}, a_{1}, s_{2}\right)+\gamma^{2} R\left(s_{2}, a_{2}, s_{3}\right)+\ldots
= ∑ t = 0 ∞ γ t R ( s t , a t , s t + 1 ) ≤ ∑ t = 0 ∞ γ t R max = R max 1 − γ = ∑ t = 0 ∞   γ t R s t , a t , s t + 1 ≤ ∑ t = 0 ∞   γ t R max  = R max  1 − γ =sum_(t=0)^(oo)gamma^(t)R(s_(t),a_(t),s_(t+1)) <= sum_(t=0)^(oo)gamma^(t)R_("max ")=(R_("max "))/(1-gamma)=\sum_{t=0}^{\infty} \gamma^{t} R\left(s_{t}, a_{t}, s_{t+1}\right) \leq \sum_{t=0}^{\infty} \gamma^{t} R_{\text {max }}=\frac{R_{\text {max }}}{1-\gamma}
其中 R max R max  R_("max ")R_{\text {max }} 是 MDP 中任何给定时间步可获得的最大可能奖励。通常， γ γ gamma\gamma 严格从范围 0 < γ < 1 0 < γ < 1 0 < gamma < 10<\gamma<1 中选择，因为范围 − 1 < γ ≤ 0 − 1 < γ ≤ 0 -1 < gamma <= 0-1<\gamma \leq 0 中的值在大多数现实情况下根本没有意义—— γ γ gamma\gamma 的负值意味着状态 s s ss 的奖励会在交替的时间步长在正值和负值之间来回切换。

  4.1.2 马尔可夫性

马尔可夫决策过程是“马尔可夫”的，因为它们满足马尔可夫性质，或无记忆性质，该性质指出，在给定当前状态的情况下，未来和过去是条件独立的。直观地说，这意味着，如果我们知道当前状态，那么了解过去并不能给我们提供关于未来的更多信息。为了用数学方式表达这一点，考虑一个智能体，它在某个 MDP 中采取行动 a 0 , a 1 , … , a t − 1 a 0 , a 1 , … , a t − 1 a_(0),a_(1),dots,a_(t-1)a_{0}, a_{1}, \ldots, a_{t-1} 后访问了状态 s 0 , s 1 , … , s t s 0 , s 1 , … , s t s_(0),s_(1),dots,s_(t)s_{0}, s_{1}, \ldots, s_{t} ，并且刚刚采取了行动 a t a t a_(t)a_{t} 。该智能体在给定其先前访问的状态和采取的行动的历史记录的情况下到达状态 s t + 1 s t + 1 s_(t+1)s_{t+1} 的概率可以写成如下形式： P ( S t + 1 = s t + 1 ∣ S t = s t , A t = a t , S t − 1 = s t − 1 , A t − 1 = a t − 1 , … , S 0 = s 0 ) P S t + 1 = s t + 1 ∣ S t = s t , A t = a t , S t − 1 = s t − 1 , A t − 1 = a t − 1 , … , S 0 = s 0 P(S_(t+1)=s_(t+1)∣S_(t)=s_(t),A_(t)=a_(t),S_(t-1)=s_(t-1),A_(t-1)=a_(t-1),dots,S_(0)=s_(0))P\left(S_{t+1}=s_{t+1} \mid S_{t}=s_{t}, A_{t}=a_{t}, S_{t-1}=s_{t-1}, A_{t-1}=a_{t-1}, \ldots, S_{0}=s_{0}\right)
其中每个 S t S t S_(t)S_{t} 表示代表我们智能体状态的随机变量， A t A t A_(t)A_{t} 表示代表我们智能体在时间 t t tt 采取的行动的随机变量。马尔可夫性质指出，上述概率可以简化如下： P ( S t + 1 = s t + 1 ∣ S t = s t , A t = a t , S t − 1 = s t − 1 , A t − 1 = a t − 1 , … , S 0 = s 0 ) = P ( S t + 1 = P S t + 1 = s t + 1 ∣ S t = s t , A t = a t , S t − 1 = s t − 1 , A t − 1 = a t − 1 , … , S 0 = s 0 = P S t + 1 = P(S_(t+1)=s_(t+1)∣S_(t)=s_(t),A_(t)=a_(t),S_(t-1)=s_(t-1),A_(t-1)=a_(t-1),dots,S_(0)=s_(0))=P(S_(t+1)=:}P\left(S_{t+1}=s_{t+1} \mid S_{t}=s_{t}, A_{t}=a_{t}, S_{t-1}=s_{t-1}, A_{t-1}=a_{t-1}, \ldots, S_{0}=s_{0}\right)=P\left(S_{t+1}=\right. s t + 1 ∣ S t = s t , A t = a t ) s t + 1 ∣ S t = s t , A t = a t {:s_(t+1)∣S_(t)=s_(t),A_(t)=a_(t))\left.s_{t+1} \mid S_{t}=s_{t}, A_{t}=a_{t}\right)
即“无记忆性”，意味着在时间 t t tt 到达状态 s ′ s ′ s^(')s^{\prime} 的概率仅取决于在时间 t t tt 的状态 s s ss 和采取的动作 a a aa ，而不取决于任何更早的状态或动作。 事实上，正是这些无记忆概率由转移函数 T ( s , a , s ′ ) = P ( s ′ ∣ s , a ) T s , a , s ′ = P s ′ ∣ s , a T(s,a,s^('))=P(s^(')∣s,a)T\left(s, a, s^{\prime}\right)=P\left(s^{\prime} \mid s, a\right) 编码。

4.2 求解马尔可夫决策过程

4.2 求解马尔可夫决策过程

回想一下，在确定性的、非对抗性的搜索中，解决搜索问题意味着找到一个到达目标状态的最优计划。另一方面，解决马尔可夫决策过程意味着找到一个最优策略 π ∗ : S → A π ∗ : S → A pi^(**):S rarr A\pi^{*}: S \rightarrow A ，一个将每个状态 s ∈ S s ∈ S s in Ss \in S 映射到一个动作 a ∈ A a ∈ A a in Aa \in A 的函数。一个显式策略 π π pi\pi 定义了一个反射智能体——给定一个状态 s s ss ，一个位于 s s ss 并执行 π π pi\pi 的智能体将选择 a = π ( s ) a = π ( s ) a=pi(s)a=\pi(s) 作为要采取的适当动作，而无需考虑其动作的未来后果。最优策略是指如果由执行智能体遵循，将产生最大预期总奖励或效用的策略。
考虑以下 MDP，其中 S = { a , b , c , d , e } , A = { S = { a , b , c , d , e } , A = { S={a,b,c,d,e},A={S=\{a, b, c, d, e\}, A=\{ 为东、西、退出 } } }\} （退出仅在状态 a a aa 和 e e ee 中是有效动作，并分别产生 10 和 1 的奖励），折扣因子为 γ = 0.1 γ = 0.1 gamma=0.1\gamma=0.1 ，并且具有确定性转换：
图 1：简单 MDP
这个 MDP 的两个潜在策略如下：
经过一些调查，不难确定策略2是最优的。遵循该策略直到采取 a = a = a=a= 退出行动，对于每个起始状态，会产生以下奖励：
  起始状态   奖励
a 10
b 1
Start State Reward a 10 b 1| Start State | Reward | | :--- | :--- | | a | 10 | | b | 1 |
  起始状态   奖励
c 0.1
d 0.1
e 1
Start State Reward c 0.1 d 0.1 e 1| Start State | Reward | | :--- | :--- | | c | 0.1 | | d | 0.1 | | e | 1 |
现在我们将学习如何使用马尔可夫决策过程的贝尔曼方程，通过算法来解决这些 MDP（以及更复杂的 MDP！）。

4.2.1 贝尔曼方程

为了讨论 MDP 的贝尔曼方程，我们必须首先引入两个新的数学量：
  • 一个状态 s , V ∗ ( s ) s , V ∗ ( s ) s,V^(**)(s)s, V^{*}(s) 的最优值 - s s ss 的最优值是指一个以最优方式行动的智能体从 s s ss 开始，在其剩余生命周期内所获得的期望效用值。请注意，在文献中，通常用 V ∗ ( s ) V ∗ ( s ) V^(**)(s)V^{*}(s) 表示相同的量。
  • 一个 Q 状态 ( s , a ) , Q ∗ ( s , a ) ( s , a ) , Q ∗ ( s , a ) (s,a),Q^(**)(s,a)(s, a), Q^{*}(s, a) 的最优值 - ( s , a ) ( s , a ) (s,a)(s, a) 的最优值是指一个智能体从 s s ss 开始，采取行动 a a aa ，并在此之后以最优方式行动所获得的期望效用值。
使用这两个新的量以及前面讨论过的其他 MDP 量，贝尔曼方程定义如下：
V ∗ ( s ) = max a ∑ s ′ T ( s , a , s ′ ) [ R ( s , a , s ′ ) + γ V ∗ ( s ′ ) ] V ∗ ( s ) = max a   ∑ s ′   T s , a , s ′ R s , a , s ′ + γ V ∗ s ′ V^(**)(s)=max_(a)sum_(s^('))T(s,a,s^('))[R(s,a,s^('))+gammaV^(**)(s^('))]V^{*}(s)=\max _{a} \sum_{s^{\prime}} T\left(s, a, s^{\prime}\right)\left[R\left(s, a, s^{\prime}\right)+\gamma V^{*}\left(s^{\prime}\right)\right]
在我们开始解释这意味着什么之前，让我们也定义一个 Q 状态的最优值方程（更常见的是最优 Q Q Q\mathbf{Q} 值）：
Q ∗ ( s , a ) = ∑ s ′ T ( s , a , s ′ ) [ R ( s , a , s ′ ) + γ V ∗ ( s ′ ) ] Q ∗ ( s , a ) = ∑ s ′   T s , a , s ′ R s , a , s ′ + γ V ∗ s ′ Q^(**)(s,a)=sum_(s^('))T(s,a,s^('))[R(s,a,s^('))+gammaV^(**)(s^('))]Q^{*}(s, a)=\sum_{s^{\prime}} T\left(s, a, s^{\prime}\right)\left[R\left(s, a, s^{\prime}\right)+\gamma V^{*}\left(s^{\prime}\right)\right]
请注意，第二个定义允许我们将贝尔曼方程重新表示为
V ∗ ( s ) = max a Q ∗ ( s , a ) V ∗ ( s ) = max a   Q ∗ ( s , a ) V^(**)(s)=max_(a)Q^(**)(s,a)V^{*}(s)=\max _{a} Q^{*}(s, a)
这是一个非常简单的量。贝尔曼方程是动态规划方程的一个例子，它通过固有的递归结构将问题分解为更小的子问题。我们可以在状态的 Q 值方程中看到这种固有的递归，在 [ R ( s , a , s ′ ) + γ V ∗ ( s ′ ) ] R s , a , s ′ + γ V ∗ s ′ [R(s,a,s^('))+gammaV^(**)(s^('))]\left[R\left(s, a, s^{\prime}\right)+\gamma V^{*}\left(s^{\prime}\right)\right] 项中。该项表示智能体通过首先从 s s ss 采取 a a aa 到达 s ′ s ′ s^(')s^{\prime} ，然后在此后以最佳方式行动所获得的总效用。采取的行动 a a aa 的直接奖励 R ( s , a , s ′ ) R s , a , s ′ R(s,a,s^('))R\left(s, a, s^{\prime}\right) ，被加到从 s ′ , V ∗ ( s ′ ) s ′ , V ∗ s ′ s^('),V^(**)(s^('))s^{\prime}, V^{*}\left(s^{\prime}\right) 可获得的最佳折扣奖励总和中，该总和被 γ γ gamma\gamma 折扣，以考虑采取行动 a a aa 时经过的一个时间步。虽然在大多数情况下，从 s ′ s ′ s^(')s^{\prime} 到某个终止状态存在大量可能的序列状态和动作，但所有这些细节都被抽象出来并封装在一个递归值 V ∗ ( s ′ ) V ∗ s ′ V^(**)(s^('))V^{*}\left(s^{\prime}\right) 中。
我们现在可以再向外迈一步，考虑 Q 值的完整方程。知道 [ R ( s , a , s ′ ) + R s , a , s ′ + [R(s,a,s^('))+:}\left[R\left(s, a, s^{\prime}\right)+\right. γ V ∗ ( s ′ ) ] γ V ∗ s ′ {: gammaV^(**)(s^('))]\left.\gamma V^{*}\left(s^{\prime}\right)\right] 表示从 Q 状态（ s , a s , a s,as, a ）到达状态 s ′ s ′ s^(')s^{\prime} 后以最佳方式行动所获得的效用，很明显，数量
∑ s ′ T ( s , a , s ′ ) [ R ( s , a , s ′ ) + γ V ∗ ( s ′ ) ] ∑ s ′   T s , a , s ′ R s , a , s ′ + γ V ∗ s ′ sum_(s^('))T(s,a,s^('))[R(s,a,s^('))+gammaV^(**)(s^('))]\sum_{s^{\prime}} T\left(s, a, s^{\prime}\right)\left[R\left(s, a, s^{\prime}\right)+\gamma V^{*}\left(s^{\prime}\right)\right]
仅仅是效用的加权和，每个效用都由其发生的概率加权。这根据定义是从 Q 状态（ s , a s , a s,as, a ）开始采取最优行动的预期效用！这完成了我们的分析，并为我们提供了足够的洞察力来解释完整的贝尔曼方程——一个状态的最优值， V ∗ ( s ) V ∗ ( s ) V^(**)(s)V^{*}(s) ，仅仅是从 s s ss 开始的所有可能行动中的最大预期效用。计算状态 s s ss 的最大预期效用本质上与运行期望最大化相同——我们首先计算每个 Q 状态（ s , a s , a s,as, a ）的预期效用（相当于计算机会节点的值），然后计算这些节点的最大值以计算最大预期效用（相当于计算最大化节点的值）。
关于贝尔曼方程的最后一点说明——它的用途是作为最优性的条件。换句话说，如果我们能以某种方式确定每个状态 s ∈ S s ∈ S s in Ss \in S 的值 V ( s ) V ( s ) V(s)V(s) ，使得贝尔曼方程对每个状态都成立
通过这些状态，我们可以得出结论，这些值是它们各自状态的最优值。实际上，满足这个条件意味着 ∀ s ∈ S , V ( s ) = V ∗ ( s ) ∀ s ∈ S , V ( s ) = V ∗ ( s ) AA s in S,V(s)=V^(**)(s)\forall s \in S, V(s)=V^{*}(s) 。

  4. 3 价值迭代

  5. 3 价值迭代

既然我们有了一个框架来测试 MDP 中状态值的最优性，那么自然而然的问题是如何实际计算这些最优值。为了回答这个问题，我们需要有时限的值（强制执行有限范围的自然结果）。状态 s s ss 在时间限制为 k k kk 步时的时限值表示为 V k ( s ) V k ( s ) V_(k)(s)V_{k}(s) ，表示从 s s ss 可获得的最大预期效用，前提是所考虑的马尔可夫决策过程在 k k kk 步内终止。等效地，这是在 MDP 的搜索树上运行深度为 k k kk 的期望最大化算法所返回的结果。
值迭代是一种动态规划算法，它使用迭代的更长时间限制来计算时间限制的值，直到收敛（也就是说，直到每个状态的 V V VV 值与过去迭代中的值相同： ∀ s , V k + 1 ( s ) = V k ( s ) ) ∀ s , V k + 1 ( s ) = V k ( s ) {: AA s,V_(k+1)(s)=V_(k)(s))\left.\forall s, V_{k+1}(s)=V_{k}(s)\right) ）。它的运作方式如下：
  1. ∀ s ∈ S ∀ s ∈ S AA s in S\forall s \in S ，初始化 V 0 ( s ) = 0 V 0 ( s ) = 0 V_(0)(s)=0V_{0}(s)=0 。这应该是直观的，因为设置0时间步的时间限制意味着在终止之前不能采取任何行动，因此无法获得任何奖励。
  2. 重复以下更新规则直到收敛：
    ∀ s ∈ S , V k + 1 ( s ) ← max a ∑ s ′ T ( s , a , s ′ ) [ R ( s , a , s ′ ) + γ V k ( s ′ ) ] ∀ s ∈ S , V k + 1 ( s ) ← max a   ∑ s ′   T s , a , s ′ R s , a , s ′ + γ V k s ′ AA s in S,quadV_(k+1)(s)larrmax_(a)sum_(s^('))T(s,a,s^('))[R(s,a,s^('))+gammaV_(k)(s^('))]\forall s \in S, \quad V_{k+1}(s) \leftarrow \max _{a} \sum_{s^{\prime}} T\left(s, a, s^{\prime}\right)\left[R\left(s, a, s^{\prime}\right)+\gamma V_{k}\left(s^{\prime}\right)\right]
    在值迭代的第 k k kk 次迭代中，我们使用每个状态的限制为 k k kk 的时间限制值来生成限制为（ k + 1 k + 1 k+1k+1 ）的时间限制值。本质上，我们使用计算出的子问题解决方案（所有 V k ( s ) V k ( s ) V_(k)(s)V_{k}(s) ）来迭代地构建更大的子问题解决方案（所有 V k + 1 ( s ) V k + 1 ( s ) V_(k+1)(s)V_{k+1}(s) ）；这就是使值迭代成为动态规划算法的原因。
注意，虽然贝尔曼方程看起来与上面的更新规则基本相同，但它们并不相同。贝尔曼方程给出了最优性的条件，而更新规则给出了一种迭代更新值直到收敛的方法。当达到收敛时，贝尔曼方程将对每个状态成立： ∀ s ∈ S , V k ( s ) = V k + 1 ( s ) = V ∗ ( s ) ∀ s ∈ S , V k ( s ) = V k + 1 ( s ) = V ∗ ( s ) AA s in S,V_(k)(s)=V_(k+1)(s)=V^(**)(s)\forall s \in S, V_{k}(s)=V_{k+1}(s)=V^{*}(s) 。
为了简洁起见，我们经常用简写 V k + 1 ← B U k V k + 1 ← B U k V_(k+1)larr BU_(k)V_{k+1} \leftarrow B U_{k} 表示 U k + 1 ( s ) ← max a ∑ s ′ T ( s , a , s ′ ) [ R ( s , a , s ′ ) + γ V k ( s ′ ) ] U k + 1 ( s ) ← max a   ∑ s ′   T s , a , s ′ R s , a , s ′ + γ V k s ′ U_(k+1)(s)larrmax_(a)sum_(s^('))T(s,a,s^('))[R(s,a,s^('))+gammaV_(k)(s^('))]U_{k+1}(s) \leftarrow \max _{a} \sum_{s^{\prime}} T\left(s, a, s^{\prime}\right)\left[R\left(s, a, s^{\prime}\right)+\gamma V_{k}\left(s^{\prime}\right)\right] ，其中 B B BB 称为贝尔曼算子。贝尔曼算子是一个 γ γ gamma\gamma 的收缩。为了证明这一点，我们需要以下一般不等式：
| max z f ( z ) − max z h ( z ) | ≤ max z | f ( z ) − h ( z ) | max z   f ( z ) − max z   h ( z ) ≤ max z   | f ( z ) − h ( z ) | |max_(z)f(z)-max_(z)h(z)| <= max_(z)|f(z)-h(z)|\left|\max _{z} f(z)-\max _{z} h(z)\right| \leq \max _{z}|f(z)-h(z)|.
现在考虑在同一状态 V ( s ) V ( s ) V(s)V(s) 和 V ′ ( s ) V ′ ( s ) V^(')(s)V^{\prime}(s) 评估的两个价值函数。我们证明贝尔曼更新 B B BB 是一个关于最大范数的 γ ∈ ( 0 , 1 ) γ ∈ ( 0 , 1 ) gamma in(0,1)\gamma \in(0,1) 的收缩，如下所示：
| B V ( s ) − B V ′ ( s ) | B V ( s ) − B V ′ ( s ) |BV(s)-BV^(')(s)|\left|B V(s)-B V^{\prime}(s)\right|
= | ( max a ∑ s ′ T ( s , a , s ′ ) [ R ( s , a , s ′ ) + γ V ( s ′ ) ] ) − ( max a ∑ s ′ T ( s , a , s ′ ) [ R ( s , a , s ′ ) + γ V ′ ( s ′ ) ] ) | = max a   ∑ s ′   T s , a , s ′ R s , a , s ′ + γ V s ′ − max a   ∑ s ′   T s , a , s ′ R s , a , s ′ + γ V ′ s ′ =|(max_(a)sum_(s^('))T(s,a,s^('))[R(s,a,s^('))+gamma V(s^('))])-(max_(a)sum_(s^('))T(s,a,s^('))[R(s,a,s^('))+gammaV^(')(s^('))])|=\left|\left(\max _{a} \sum_{s^{\prime}} T\left(s, a, s^{\prime}\right)\left[R\left(s, a, s^{\prime}\right)+\gamma V\left(s^{\prime}\right)\right]\right)-\left(\max _{a} \sum_{s^{\prime}} T\left(s, a, s^{\prime}\right)\left[R\left(s, a, s^{\prime}\right)+\gamma V^{\prime}\left(s^{\prime}\right)\right]\right)\right|
≤ max a | ∑ s ′ T ( s , a , s ′ ) [ R ( s , a , s ′ ) + γ V ( s ′ ) ] − ∑ s ′ T ( s , a , s ′ ) [ R ( s , a , s ′ ) + γ V ′ ( s ′ ) ] | ≤ max a   ∑ s ′   T s , a , s ′ R s , a , s ′ + γ V s ′ − ∑ s ′   T s , a , s ′ R s , a , s ′ + γ V ′ s ′ <= max_(a)|sum_(s^('))T(s,a,s^('))[R(s,a,s^('))+gamma V(s^('))]-sum_(s^('))T(s,a,s^('))[R(s,a,s^('))+gammaV^(')(s^('))]|\leq \max _{a}\left|\sum_{s^{\prime}} T\left(s, a, s^{\prime}\right)\left[R\left(s, a, s^{\prime}\right)+\gamma V\left(s^{\prime}\right)\right]-\sum_{s^{\prime}} T\left(s, a, s^{\prime}\right)\left[R\left(s, a, s^{\prime}\right)+\gamma V^{\prime}\left(s^{\prime}\right)\right]\right|
= max a | γ ∑ s ′ T ( s , a , s ′ ) V ( s ′ ) − γ ∑ s ′ T ( s , a , s ′ ) V ′ ( s ′ ) | = max a   γ ∑ s ′   T s , a , s ′ V s ′ − γ ∑ s ′   T s , a , s ′ V ′ s ′ =max_(a)|gammasum_(s^('))T(s,a,s^('))V(s^('))-gammasum_(s^('))T(s,a,s^('))V^(')(s^('))|=\max _{a}\left|\gamma \sum_{s^{\prime}} T\left(s, a, s^{\prime}\right) V\left(s^{\prime}\right)-\gamma \sum_{s^{\prime}} T\left(s, a, s^{\prime}\right) V^{\prime}\left(s^{\prime}\right)\right|
= γ max a | ∑ s ′ T ( s , a , s ′ ) ( V ( s ′ ) − V ′ ( s ′ ) ) | = γ max a   ∑ s ′   T s , a , s ′ V s ′ − V ′ s ′ =gammamax_(a)|sum_(s^('))T(s,a,s^('))(V(s^('))-V^(')(s^(')))|=\gamma \max _{a}\left|\sum_{s^{\prime}} T\left(s, a, s^{\prime}\right)\left(V\left(s^{\prime}\right)-V^{\prime}\left(s^{\prime}\right)\right)\right|
≤ γ max a | ∑ s ′ T ( s , a , s ′ ) max s ′ | V ( s ′ ) − V ′ ( s ′ ) | | ≤ γ max a   ∑ s ′   T s , a , s ′ max s ′   V s ′ − V ′ s ′ | | <= gammamax_(a)|sum_(s^('))T(s,a,s^('))max_(s^('))|V(s^('))-V^(')(s^('))||\leq \gamma \max _{a}\left|\sum_{s^{\prime}} T\left(s, a, s^{\prime}\right) \max _{s^{\prime}}\right| V\left(s^{\prime}\right)-V^{\prime}\left(s^{\prime}\right)| |
= γ max s ′ | V ( s ′ ) − V ′ ( s ′ ) | = γ max s ′   V s ′ − V ′ s ′ =gammamax_(s^('))|V(s^('))-V^(')(s^('))|=\gamma \max _{s^{\prime}}\left|V\left(s^{\prime}\right)-V^{\prime}\left(s^{\prime}\right)\right|
= γ ‖ V ( s ′ ) − V ′ ( s ′ ) ‖ ∞ = γ V s ′ − V ′ s ′ ∞ =gamma||V(s^('))-V^(')(s^('))||_(oo)=\gamma\left\|V\left(s^{\prime}\right)-V^{\prime}\left(s^{\prime}\right)\right\|_{\infty},
其中，第一个不等式来自上面介绍的一般不等式，第二个不等式来自取 V V VV 和 V ′ V ′ V^(')V^{\prime} 之间的差值的最大值，在倒数第二步中，我们使用了概率之和为 1 这一事实，无论 a a aa 的选择如何。最后一步使用了向量 x = ( x 1 , … , x n ) x = x 1 , … , x n x=(x_(1),dots,x_(n))x=\left(x_{1}, \ldots, x_{n}\right) 的最大范数的定义，即 ‖ x ‖ ∞ = max ( | x 1 | , … , | x n | ) ‖ x ‖ ∞ = max x 1 , … , x n ||x||_(oo)=max(|x_(1)|,dots,|x_(n)|)\|x\|_{\infty}=\max \left(\left|x_{1}\right|, \ldots,\left|x_{n}\right|\right) 。
因为我们刚刚证明了通过贝尔曼更新的值迭代在 γ γ gamma\gamma 中是一个收缩，所以我们知道值迭代会收敛，并且当达到满足 V ∗ = B U ∗ V ∗ = B U ∗ V^(**)=BU^(**)V^{*}=B U^{*} 的不动点时，收敛就会发生。
让我们通过回顾之前的赛车 MDP，并引入折扣因子 γ = 0.5 γ = 0.5 gamma=0.5\gamma=0.5 ，来看看值迭代在实践中的一些更新：
图 1：赛车 MDP
我们从初始化所有 V 0 ( s ) = 0 V 0 ( s ) = 0 V_(0)(s)=0V_{0}(s)=0 开始进行价值迭代：
  凉爽   温暖   过热
V 0 V 0 V_(0)V_{0} 0 0 0
cool warm overheated V_(0) 0 0 0| | cool | warm | overheated | | :--- | :--- | :--- | :--- | | $V_{0}$ | 0 | 0 | 0 |
在我们的第一轮更新中，我们可以如下计算 ∀ s ∈ S , V 1 ( s ) ∀ s ∈ S , V 1 ( s ) AA s in S,V_(1)(s)\forall s \in S, V_{1}(s) ：
V 1 ( cool ) = max { 1 ⋅ [ 1 + 0.5 ⋅ 0 ] , 0.5 ⋅ [ 2 + 0.5 ⋅ 0 ] + 0.5 ⋅ [ 2 + 0.5 ⋅ 0 ] } = max { 1 , 2 } = 2 V 1 ( warm ) = max { 0.5 ⋅ [ 1 + 0.5 ⋅ 0 ] + 0.5 ⋅ [ 1 + 0.5 ⋅ 0 ] , 1 ⋅ [ − 10 + 0.5 ⋅ 0 ] } = max { 1 , − 10 } = 1 V 1 ( overheated ) = max { } = 0 U 1 U 0 0 0 0 U 1 2 1 0 V 1 (  cool  ) = max { 1 ⋅ [ 1 + 0.5 ⋅ 0 ] , 0.5 ⋅ [ 2 + 0.5 ⋅ 0 ] + 0.5 ⋅ [ 2 + 0.5 ⋅ 0 ] } = max { 1 , 2 } = 2 V 1 (  warm  ) = max { 0.5 ⋅ [ 1 + 0.5 ⋅ 0 ] + 0.5 ⋅ [ 1 + 0.5 ⋅ 0 ] , 1 ⋅ [ − 10 + 0.5 ⋅ 0 ] } = max { 1 , − 10 } = 1 V 1 (  overheated  ) = max { } = 0 U 1 U 0 0 0 0 U 1 2 1 0 {:[V_(1)(" cool ")=max{1*[1+0.5*0]","0.5*[2+0.5*0]+0.5*[2+0.5*0]}],[=max{1","2}],[=2],[V_(1)(" warm ")=max{0.5*[1+0.5*0]+0.5*[1+0.5*0]","1*[-10+0.5*0]}],[=max{1","-10}],[=1],[V_(1)(" overheated ")=max{}],[=0],[{:[(U_(1))/(U_(0)),0,0,0],[U_(1),2,1,0]:}]:}\begin{aligned} V_{1}(\text { cool }) & =\max \{1 \cdot[1+0.5 \cdot 0], 0.5 \cdot[2+0.5 \cdot 0]+0.5 \cdot[2+0.5 \cdot 0]\} \\ & =\max \{1,2\} \\ & =2 \\ V_{1}(\text { warm }) & =\max \{0.5 \cdot[1+0.5 \cdot 0]+0.5 \cdot[1+0.5 \cdot 0], 1 \cdot[-10+0.5 \cdot 0]\} \\ & =\max \{1,-10\} \\ & =1 \\ V_{1}(\text { overheated }) & =\max \{ \} \\ & =0 \\ & \begin{array}{llll} \frac{U_{1}}{U_{0}} & 0 & 0 & 0 \\ U_{1} & 2 & 1 & 0 \end{array} \end{aligned}
类似地，我们可以重复这个过程，用我们新发现的 U 1 ( s ) U 1 ( s ) U_(1)(s)U_{1}(s) 值来计算第二轮更新，从而计算出 V 2 ( s ) V 2 ( s ) V_(2)(s)V_{2}(s) ：
V 2 ( cool ) = max { 1 ⋅ [ 1 + 0.5 ⋅ 2 ] , 0.5 ⋅ [ 2 + 0.5 ⋅ 2 ] + 0.5 ⋅ [ 2 + 0.5 ⋅ 1 ] } = max { 2 , 2.75 } = 2.75 V 2 ( warm ) = max { 0.5 ⋅ [ 1 + 0.5 ⋅ 2 ] + 0.5 ⋅ [ 1 + 0.5 ⋅ 1 ] , 1 ⋅ [ − 10 + 0.5 ⋅ 0 ] } = max { 1.75 , − 10 } = 1.75 V 2 ( overheated ) = max { } = 0 V 0 V 1 0 0 0 V 2 2.75 1.75 0 V 2 (  cool  ) = max { 1 ⋅ [ 1 + 0.5 ⋅ 2 ] , 0.5 ⋅ [ 2 + 0.5 ⋅ 2 ] + 0.5 ⋅ [ 2 + 0.5 ⋅ 1 ] } = max { 2 , 2.75 } = 2.75 V 2 (  warm  ) = max { 0.5 ⋅ [ 1 + 0.5 ⋅ 2 ] + 0.5 ⋅ [ 1 + 0.5 ⋅ 1 ] , 1 ⋅ [ − 10 + 0.5 ⋅ 0 ] } = max { 1.75 , − 10 } = 1.75 V 2 (  overheated  ) = max { } = 0 V 0 V 1 0 0 0 V 2 2.75 1.75 0 {:[V_(2)(" cool ")=max{1*[1+0.5*2]","0.5*[2+0.5*2]+0.5*[2+0.5*1]}],[=max{2","2.75}],[=2.75],[V_(2)(" warm ")=max{0.5*[1+0.5*2]+0.5*[1+0.5*1]","1*[-10+0.5*0]}],[=max{1.75","-10}],[=1.75],[V_(2)(" overheated ")=max{}],[=0],[{:[(V_(0))/(V_(1)),0,0,0],[V_(2),2.75,1.75,0]:}]:}\begin{aligned} V_{2}(\text { cool }) & =\max \{1 \cdot[1+0.5 \cdot 2], 0.5 \cdot[2+0.5 \cdot 2]+0.5 \cdot[2+0.5 \cdot 1]\} \\ & =\max \{2,2.75\} \\ & =2.75 \\ V_{2}(\text { warm }) & =\max \{0.5 \cdot[1+0.5 \cdot 2]+0.5 \cdot[1+0.5 \cdot 1], 1 \cdot[-10+0.5 \cdot 0]\} \\ & =\max \{1.75,-10\} \\ & =1.75 \\ V_{2}(\text { overheated }) & =\max \{ \} \\ & =0 \\ & \begin{array}{llll} \frac{V_{0}}{V_{1}} & 0 & 0 & 0 \\ V_{2} & 2.75 & 1.75 & 0 \end{array} \end{aligned}
值得注意的是，任何终点状态的 V ∗ ( s ) V ∗ ( s ) V^(**)(s)V^{*}(s) 必须为 0，因为从任何终点状态都无法采取任何行动来获得任何回报。

  4.3.1 策略提取

回想一下，我们在解决 MDP 中的最终目标是确定一个最优策略。这可以在确定所有状态的最优值后，使用一种称为策略提取的方法来完成。策略提取背后的直觉非常简单：如果你处于状态 s s ss ，你应该采取行动 a a aa ，这将产生最大的预期效用。毫不奇怪， a a aa 是将我们带到具有最大 Q 值的 Q 状态的行动，从而可以对最优策略进行正式定义：
∀ s ∈ S , π ∗ ( s ) = argmax a Q ∗ ( s , a ) = argmax a ∑ s ′ T ( s , a , s ′ ) [ R ( s , a , s ′ ) + γ V ∗ ( s ′ ) ] ∀ s ∈ S , π ∗ ( s ) = argmax a Q ∗ ( s , a ) = argmax a ∑ s ′   T s , a , s ′ R s , a , s ′ + γ V ∗ s ′ AA s in S,pi^(**)(s)=argmax _(a)Q^(**)(s,a)=argmax _(a)sum_(s^('))T(s,a,s^('))[R(s,a,s^('))+gammaV^(**)(s^('))]\forall s \in S, \pi^{*}(s)=\underset{a}{\operatorname{argmax}} Q^{*}(s, a)=\underset{a}{\operatorname{argmax}} \sum_{s^{\prime}} T\left(s, a, s^{\prime}\right)\left[R\left(s, a, s^{\prime}\right)+\gamma V^{*}\left(s^{\prime}\right)\right]
出于性能原因，记住策略提取最好具有状态的最优 Q 值，在这种情况下，只需要一个 argmax 操作即可确定状态的最优行动。仅存储每个 V ∗ ( s ) V ∗ ( s ) V^(**)(s)V^{*}(s) 意味着我们必须在使用 argmax 之前使用贝尔曼方程重新计算所有必要的 Q 值，这相当于执行深度为 1 的期望最大化。

  4.3.2 Q 值迭代

在使用值迭代求解最优策略时，我们首先找到所有最优值，然后使用策略提取来提取策略。但是，您可能已经注意到，我们还处理另一种编码有关最优策略信息的值：Q 值。
Q 值迭代是一种动态规划算法，用于计算有时限的 Q 值。它可以用以下公式描述：
Q k + 1 ( s , a ) ← ∑ s ′ T ( s , a , s ′ ) [ R ( s , a , s ′ ) + γ max a ′ Q k ( s ′ , a ′ ) ] Q k + 1 ( s , a ) ← ∑ s ′   T s , a , s ′ R s , a , s ′ + γ max a ′   Q k s ′ , a ′ Q_(k+1)(s,a)larrsum_(s^('))T(s,a,s^('))[R(s,a,s^('))+gammamax_(a^('))Q_(k)(s^('),a^('))]Q_{k+1}(s, a) \leftarrow \sum_{s^{\prime}} T\left(s, a, s^{\prime}\right)\left[R\left(s, a, s^{\prime}\right)+\gamma \max _{a^{\prime}} Q_{k}\left(s^{\prime}, a^{\prime}\right)\right]
注意，这个更新只是对值迭代的更新规则的一个小修改。实际上，唯一的真正区别是，由于我们在状态中时，是在转换之前选择一个动作，而当我们在 Q 状态中时，是在选择新动作之前进行转换，因此对动作的最大运算符的位置已经改变。一旦我们有了每个状态和动作的最佳 Q 值，我们就可以通过简单地选择具有最高 Q 值的动作来找到一个状态的策略。

  4.4 策略迭代

  4.4 策略迭代

价值迭代可能相当慢。在每次迭代中，我们必须更新所有 | S | | S | |S||S| 状态的值（其中 | n | | n | |n||n| 指的是基数运算符），每个状态都需要迭代所有 | A | | A | |A||A| 动作，因为我们要计算每个动作的 Q 值。反过来，计算每个 Q 值又需要再次迭代每个 | S | | S | |S||S| 状态，导致运行时间很差，为 O ( | S | 2 | A | ) O | S | 2 | A | O(|S|^(2)|A|)O\left(|S|^{2}|A|\right) 。此外，当我们只想确定 MDP 的最优策略时，价值迭代往往会进行大量的过度计算，因为策略提取计算出的策略通常比值本身收敛得快得多。解决这些缺陷的方法是使用策略迭代作为替代方案，该算法保持了价值迭代的最优性，同时提供了显著的性能提升。策略迭代的运作方式如下：
  1. 定义一个初始策略。这可以是任意的，但初始策略越接近最终的最优策略，策略迭代的收敛速度就越快。
  2. 重复以下步骤直到收敛：
  • 使用策略评估来评估当前策略。对于策略 π π pi\pi ，策略评估意味着计算所有状态 s s ss 的 V π ( s ) V π ( s ) V^(pi)(s)V^{\pi}(s) ，其中 V π ( s ) V π ( s ) V^(pi)(s)V^{\pi}(s) 是遵循 π π pi\pi 时从状态 s s ss 开始的预期效用： V π ( s ) = ∑ s ′ T ( s , π ( s ) , s ′ ) [ R ( s , π ( s ) , s ′ ) + γ V π ( s ′ ) ] V π ( s ) = ∑ s ′   T s , π ( s ) , s ′ R s , π ( s ) , s ′ + γ V π s ′ V^(pi)(s)=sum_(s^('))T(s,pi(s),s^('))[R(s,pi(s),s^('))+gammaV^(pi)(s^('))]V^{\pi}(s)=\sum_{s^{\prime}} T\left(s, \pi(s), s^{\prime}\right)\left[R\left(s, \pi(s), s^{\prime}\right)+\gamma V^{\pi}\left(s^{\prime}\right)\right] 。将策略迭代的第 i i ii 次迭代的策略定义为 π i π i pi_(i)\pi_{i} 。由于我们为每个状态固定了一个动作，因此我们不再需要 max 运算符，这实际上使我们得到了由上述规则生成的 | S | | S | |S||S| 个方程组。然后，可以通过简单地求解该系统来计算每个 V π i ( s ) V π i ( s ) V^(pi_(i))(s)V^{\pi_{i}}(s) 。或者，我们也可以使用以下更新规则计算 V π i ( s ) V π i ( s ) V^(pi_(i))(s)V^{\pi_{i}}(s) 直到收敛，就像在值迭代中一样： V k + 1 π i ( s ) ← ∑ s ′ T ( s , π i ( s ) , s ′ ) [ R ( s , π i ( s ) , s ′ ) + γ V k π i ( s ′ ) ] V k + 1 π i ( s ) ← ∑ s ′   T s , π i ( s ) , s ′ R s , π i ( s ) , s ′ + γ V k π i s ′ V_(k+1)^(pi_(i))(s)larrsum_(s^('))T(s,pi_(i)(s),s^('))[R(s,pi_(i)(s),s^('))+gammaV_(k)^(pi_(i))(s^('))]V_{k+1}^{\pi_{i}}(s) \leftarrow \sum_{s^{\prime}} T\left(s, \pi_{i}(s), s^{\prime}\right)\left[R\left(s, \pi_{i}(s), s^{\prime}\right)+\gamma V_{k}^{\pi_{i}}\left(s^{\prime}\right)\right] 。但是，第二种方法在实践中通常较慢。
  • 一旦我们评估了当前策略，就使用策略改进来生成更好的策略。策略改进在策略评估生成的状态值上使用策略提取来生成这种新的改进策略： π i + 1 ( s ) = argmax a ∑ s ′ T ( s , a , s ′ ) [ R ( s , a , s ′ ) + γ V π i ( s ′ ) ] π i + 1 ( s ) = argmax a ∑ s ′   T s , a , s ′ R s , a , s ′ + γ V π i s ′ pi_(i+1)(s)=argmax _(a)sum_(s^('))T(s,a,s^('))[R(s,a,s^('))+gammaV^(pi_(i))(s^('))]\pi_{i+1}(s)=\underset{a}{\operatorname{argmax}} \sum_{s^{\prime}} T\left(s, a, s^{\prime}\right)\left[R\left(s, a, s^{\prime}\right)+\gamma V^{\pi_{i}}\left(s^{\prime}\right)\right] 。如果 π i + 1 = π i π i + 1 = π i pi_(i+1)=pi_(i)\pi_{i+1}=\pi_{i} ，则算法已收敛，我们可以得出结论 π i + 1 = π i = π ∗ π i + 1 = π i = π ∗ pi_(i+1)=pi_(i)=pi^(**)\pi_{i+1}=\pi_{i}=\pi^{*} 。
让我们最后一次（已经厌倦了吗？）运行我们的赛车示例，看看我们是否使用策略迭代获得与使用值迭代相同的策略。回想一下，我们使用的折扣因子为 γ = 0.5 γ = 0.5 gamma=0.5\gamma=0.5 。
我们从一个总是慢行的初始策略开始：
  凉   暖   过热
π 0 π 0 pi_(0)\pi_{0}   慢   慢 -
cool warm overheated pi_(0) slow slow -| | cool | warm | overheated | | :--- | :--- | :--- | :--- | | $\pi_{0}$ | slow | slow | - |
因为终末状态没有向外的动作，所以没有策略可以给它赋值。因此，像我们所做的那样，忽略过热状态是合理的，并且简单地为任何终末状态 s s ss 分配 ∀ i , V π i ( s ) = 0 ∀ i , V π i ( s ) = 0 AA i,V^(pi_(i))(s)=0\forall i, V^{\pi_{i}}(s)=0 。下一步是在 π 0 π 0 pi_(0)\pi_{0} 上运行一轮策略评估：
V π 0 ( cool ) = 1 ⋅ [ 1 + 0.5 ⋅ V π 0 ( cool ) ] V π 0 ( warm ) = 0.5 ⋅ [ 1 + 0.5 ⋅ V π 0 ( cool ) ] + 0.5 ⋅ [ 1 + 0.5 ⋅ V π 0 ( warm ) ] V π 0 ( cool ) = 1 ⋅ 1 + 0.5 ⋅ V π 0 ( cool ) V π 0 ( warm ) = 0.5 ⋅ 1 + 0.5 ⋅ V π 0 ( cool ) + 0.5 ⋅ 1 + 0.5 ⋅ V π 0 ( warm ) {:[V^(pi_(0))(cool)=1*[1+0.5*V^(pi_(0))(cool)]],[V^(pi_(0))(warm)=0.5*[1+0.5*V^(pi_(0))(cool)]],[+0.5*[1+0.5*V^(pi_(0))(warm)]]:}\begin{aligned} V^{\pi_{0}}(\mathrm{cool}) & =1 \cdot\left[1+0.5 \cdot V^{\pi_{0}}(\mathrm{cool})\right] \\ V^{\pi_{0}}(\mathrm{warm}) & =0.5 \cdot\left[1+0.5 \cdot V^{\pi_{0}}(\mathrm{cool})\right] \\ & +0.5 \cdot\left[1+0.5 \cdot V^{\pi_{0}}(\mathrm{warm})\right] \end{aligned}
图1：赛车示例
求解关于 V π 0 ( cool ) V π 0 ( cool ) V^(pi_(0))(cool)V^{\pi_{0}}(\mathrm{cool}) 和 V π 0 ( warm ) V π 0 ( warm ) V^(pi_(0))(warm)V^{\pi_{0}}(\mathrm{warm}) 的方程组，得到：
  凉   暖   过热
V π 0 V π 0 V^(pi_(0))V^{\pi_{0}} 2 2 0
cool warm overheated V^(pi_(0)) 2 2 0| | cool | warm | overheated | | :--- | :--- | :--- | :--- | | $V^{\pi_{0}}$ | 2 | 2 | 0 |
现在我们可以用这些值来运行策略提取：
π 1 ( cool ) = argmax { slow : 1 ⋅ [ 1 + 0.5 ⋅ 2 ] , fast : 0.5 ⋅ [ 2 + 0.5 ⋅ 2 ] + 0.5 ⋅ [ 2 + 0.5 ⋅ 2 ] } = argmax { slow : 2 , fast : 3 } = fast π 1 ( warm ) = argmax { slow : 0.5 ⋅ [ 1 + 0.5 ⋅ 2 ] + 0.5 ⋅ [ 1 + 0.5 ⋅ 2 ] , fast : 1 ⋅ [ − 10 + 0.5 ⋅ 0 ] } = argmax { slow : 2 , fast : − 10 } = slow π 1 ( cool ) = argmax {  slow  : 1 ⋅ [ 1 + 0.5 ⋅ 2 ] ,  fast  : 0.5 ⋅ [ 2 + 0.5 ⋅ 2 ] + 0.5 ⋅ [ 2 + 0.5 ⋅ 2 ] } = argmax {  slow  : 2 ,  fast  : 3 } =  fast  π 1 (  warm  ) = argmax {  slow  : 0.5 ⋅ [ 1 + 0.5 ⋅ 2 ] + 0.5 ⋅ [ 1 + 0.5 ⋅ 2 ] ,  fast  : 1 ⋅ [ − 10 + 0.5 ⋅ 0 ] } = argmax {  slow  : 2 ,  fast  : − 10 } =  slow  {:[pi_(1)(cool)=argmax{" slow ":1*[1+0.5*2]","" fast ":0.5*[2+0.5*2]+0.5*[2+0.5*2]}],[=argmax{" slow ":2","" fast ":3}],[=" fast "],[pi_(1)(" warm ")=argmax{" slow ":0.5*[1+0.5*2]+0.5*[1+0.5*2]","" fast ":1*[-10+0.5*0]}],[=argmax{" slow ":2","" fast ":-10}],[=" slow "]:}\begin{aligned} \pi_{1}(\mathrm{cool}) & =\operatorname{argmax}\{\text { slow }: 1 \cdot[1+0.5 \cdot 2], \text { fast }: 0.5 \cdot[2+0.5 \cdot 2]+0.5 \cdot[2+0.5 \cdot 2]\} \\ & =\operatorname{argmax}\{\text { slow }: 2, \text { fast }: 3\} \\ & =\text { fast } \\ \pi_{1}(\text { warm }) & =\operatorname{argmax}\{\text { slow }: 0.5 \cdot[1+0.5 \cdot 2]+0.5 \cdot[1+0.5 \cdot 2], \text { fast }: 1 \cdot[-10+0.5 \cdot 0]\} \\ & =\operatorname{argmax}\{\text { slow }: 2, \text { fast }:-10\} \\ & =\text { slow } \end{aligned}
第二轮运行策略迭代会产生 π 2 ( cool ) = π 2 ( cool ) = pi_(2)(cool)=\pi_{2}(\mathrm{cool})= 快和 π 2 ( warm ) = π 2 ( warm ) = pi_(2)(warm)=\pi_{2}(\mathrm{warm})= 慢。由于这与 π 1 π 1 pi_(1)\pi_{1} 的策略相同，我们可以得出结论 π 1 = π 2 = π ∗ π 1 = π 2 = π ∗ pi_(1)=pi_(2)=pi^(**)\pi_{1}=\pi_{2}=\pi^{*} 。验证一下来练习！
  凉爽   温暖
π 0 π 0 pi_(0)\pi_{0}   慢   慢
π 1 π 1 pi_(1)\pi_{1}   快   慢
π 2 π 2 pi_(2)\pi_{2}   快   慢
cool warm pi_(0) slow slow pi_(1) fast slow pi_(2) fast slow| | cool | warm | | :--- | :--- | :--- | | $\pi_{0}$ | slow | slow | | $\pi_{1}$ | fast | slow | | $\pi_{2}$ | fast | slow |
这个例子展示了策略迭代的真正威力：仅需两次迭代，我们就已经得到了赛车 MDP 的最优策略！相比之下，我们在同一个 MDP 上运行价值迭代时，两次更新后距离收敛还有数次迭代，策略迭代的效率更高。

  4.5 总结

  4. 5 总结

上面介绍的材料很容易让人感到困惑。我们介绍了价值迭代、策略迭代、策略提取和策略评估，所有这些看起来都很相似，都使用了贝尔曼方程，但略有不同。
以下是每种算法的用途摘要：
  • 价值迭代：用于计算状态的最优价值，通过迭代更新直到收敛。
  • 策略评估：用于计算特定策略下状态的价值。
  • 策略提取：用于在给定某些状态价值函数的情况下确定策略。如果状态价值是最优的，那么这个策略也将是最优的。此方法在运行价值迭代后用于从最优状态价值计算最优策略，或者作为策略迭代中的一个子程序，用于计算当前估计的状态价值的最佳策略。
  • 策略迭代：一种封装了策略评估和策略提取的技术，用于迭代收敛到最优策略。由于策略通常比状态价值收敛得更快，因此它往往优于价值迭代。

  5. 强化学习

  5. 强化学习

  作者：Nikhil Sharma
编辑：Wesley Zheng
鸣谢：部分章节改编自教材《人工智能：一种现代方法》。
最后更新：2024年9月

5.1 强化学习

5.1 强化学习

在前一篇笔记中，我们讨论了马尔可夫决策过程，并使用诸如价值迭代和策略迭代等技术来解决它，以计算状态的最优值并提取最优策略。解决马尔可夫决策过程是离线规划的一个例子，在这种规划中，智能体完全了解转移函数和奖励函数，他们需要的所有信息都预先计算出 MDP 编码的世界中的最优动作，而无需实际采取任何动作。
在本节中，我们将讨论在线规划，在此期间，智能体对世界中的奖励或转移没有先验知识（仍然表示为 MDP）。在在线规划中，智能体必须尝试探索，在此期间，它执行动作并接收反馈，反馈的形式是它到达的后继状态以及它获得的相应奖励。智能体使用此反馈，通过一种称为强化学习的过程来估计最优策略，然后再使用此估计的策略进行利用或奖励最大化。
图 1：反馈循环
让我们从一些基本术语开始。在在线规划的每个时间步，智能体从状态 s s ss 开始，然后采取动作 a a aa ，最终到达后继状态 s ′ s ′ s^(')s^{\prime} ，获得一些奖励 r r rr 。每个 ( s , a , s ′ , r ) s , a , s ′ , r (s,a,s^('),r)\left(s, a, s^{\prime}, r\right) 元组被称为一个样本。通常，智能体会继续采取行动并连续收集样本，直到到达终止状态。这种样本的集合被称为一个回合。智能体通常会经历许多回合的探索，以便收集学习所需的足够数据。
强化学习有两种类型：基于模型的学习和无模型的学习。基于模型的学习试图在使用这些估计值通过价值或策略迭代正常解决 MDP 之前，利用探索过程中获得的样本来估计转移和奖励函数。另一方面，无模型的学习试图直接估计状态的价值或 Q 值，而从不使用
任何记忆来构建 MDP 中奖励和转移的模型。

5.2 基于模型的学习

5.2 基于模型的学习

在基于模型的学习中，智能体通过记录进入每个 Q 状态（ s , a s , a s,as, a ）后到达每个状态 s ′ s ′ s^(')s^{\prime} 的次数，来生成转移函数 T ^ ( s , a , s ′ ) T ^ s , a , s ′ hat(T)(s,a,s^('))\hat{T}\left(s, a, s^{\prime}\right) 的近似值。然后，智能体可以通过归一化其收集的计数来生成近似转移函数 T ^ T ^ hat(T)\hat{T} ——将每个观察到的元组（ s , a , s ′ s , a , s ′ s,a,s^(')s, a, s^{\prime} ）的计数除以智能体处于 Q 状态（ s , a s , a s,as, a ）的所有实例的计数之和。计数的归一化会缩放它们，使其总和为 1，从而允许将它们解释为概率。
考虑以下示例 MDP，其状态为 S = { A , B , C , D , E , x } S = { A , B , C , D , E , x } S={A,B,C,D,E,x}S=\{A, B, C, D, E, x\} ，其中 x x xx 表示终止状态，折扣因子为 γ = 1 γ = 1 gamma=1\gamma=1 ：
图 1：MDP 示例
假设我们允许我们的智能体在上述策略 π explore π explore  pi_("explore ")\pi_{\text {explore }} 下探索 MDP 四个回合（定向三角形表示沿三角形指向的方向移动，蓝色方块表示选择退出作为动作），从而产生以下结果：
现在我们总共有12个样本，每集3个，计数如下：
s s ss a a aa s ′ s ′ s^(')s^{\prime}   计数
A A AA   退出 x x xx 1
B B BB   东 C C CC 2
C C CC   东 A A AA 1
C C CC   东 D D DD 3
D D DD   退出 x x xx 3
E E EE   北 C C CC 2
s a s^(') count A exit x 1 B east C 2 C east A 1 C east D 3 D exit x 3 E north C 2| $s$ | $a$ | $s^{\prime}$ | count | | :--- | :--- | :--- | :--- | | $A$ | exit | $x$ | 1 | | $B$ | east | $C$ | 2 | | $C$ | east | $A$ | 1 | | $C$ | east | $D$ | 3 | | $D$ | exit | $x$ | 3 | | $E$ | north | $C$ | 2 |
  第 1 集
B , east, C , − 1 C , east, D , − 1 D , exit, x , + 10 B ,  east,  C , − 1 C ,  east,  D , − 1 D ,  exit,  x , + 10 {:[B","" east, "C","-1],[C","" east, "D","-1],[D","" exit, "x","+10]:}\begin{aligned} & B, \text { east, } C,-1 \\ & C, \text { east, } D,-1 \\ & D, \text { exit, } x,+10 \end{aligned}

  第 3 集

E , north, C , − 1 C , east, D , − 1 D , exit, x , + 10 E ,  north,  C , − 1 C ,  east,  D , − 1 D ,  exit,  x , + 10 {:[E","" north, "C","-1],[C","" east, ",D","-1],[D","" exit, ",x","+10]:}\begin{array}{ll} E, \text { north, } C,-1 \\ C, \text { east, } & D,-1 \\ D, \text { exit, } & x,+10 \end{array}

  第 2 集

  B，东，C，-1
C，东，D，-1
D，退出，x，+10

  第4集

E , north, C , − 1 C , east, A , − 1 A , exit, x , − 10 E ,  north,  C , − 1 C ,  east,  A , − 1 A ,  exit,  x , − 10 {:[E","" north, "C","-1],[C","" east, ",A","-1],[A","" exit, ",x","-10]:}\begin{array}{ll} E, \text { north, } C,-1 \\ C, \text { east, } & A,-1 \\ A, \text { exit, } & x,-10 \end{array}
图2：示例片段
回想一下 T ( s , a , s ′ ) = P ( s ′ ∣ a , s ) T s , a , s ′ = P s ′ ∣ a , s T(s,a,s^('))=P(s^(')∣a,s)T\left(s, a, s^{\prime}\right)=P\left(s^{\prime} \mid a, s\right) ，我们可以用这些计数来估计转移函数，方法是将每个元组 ( s , a , s ′ s , a , s ′ s,a,s^(')s, a, s^{\prime} ) 的计数除以我们处于 Q 状态的总次数 ( s , a s , a s,as, a )，并直接从我们在探索过程中获得的奖励中估计奖励函数：
  转移函数： T ^ ( s , a , s ′ ) T ^ s , a , s ′ hat(T)(s,a,s^('))\hat{T}\left(s, a, s^{\prime}\right)
   T ^ ( A T ^ ( A hat(T)(A\hat{T}(A ，出口， x ) = # ( A , exit , x ) # ( A , exit ) = 1 1 = 1 x ) = # ( A ,  exit  , x ) # ( A ,  exit  ) = 1 1 = 1 x)=(#(A," exit ",x))/(#(A," exit "))=(1)/(1)=1x)=\frac{\#(A, \text { exit }, x)}{\#(A, \text { exit })}=\frac{1}{1}=1
   T ^ ( B T ^ ( B hat(T)(B\hat{T}(B ，东， C ) = # ( B , east , C ) # ( B , east ) = 2 2 = 1 C ) = # ( B ,  east  , C ) # ( B ,  east  ) = 2 2 = 1 C)=(#(B," east ",C))/(#(B," east "))=(2)/(2)=1C)=\frac{\#(B, \text { east }, C)}{\#(B, \text { east })}=\frac{2}{2}=1
   T ^ ( C T ^ ( C hat(T)(C\hat{T}(C ，东， A ) = # ( C , east , A ) # ( C , east ) = 1 4 = 0.25 A ) = # ( C ,  east  , A ) # ( C ,  east  ) = 1 4 = 0.25 A)=(#(C," east ",A))/(#(C," east "))=(1)/(4)=0.25A)=\frac{\#(C, \text { east }, A)}{\#(C, \text { east })}=\frac{1}{4}=0.25
   T ^ ( C T ^ ( C hat(T)(C\hat{T}(C ，东， D ) = # ( C , east , D ) # ( C , east ) = 3 4 = 0.75 D ) = # ( C ,  east  , D ) # ( C ,  east  ) = 3 4 = 0.75 D)=(#(C," east ",D))/(#(C," east "))=(3)/(4)=0.75D)=\frac{\#(C, \text { east }, D)}{\#(C, \text { east })}=\frac{3}{4}=0.75
   T ^ ( D T ^ ( D hat(T)(D\hat{T}(D ，退出， x ) = # ( D , exit , x ) # ( D , exit ) = 3 3 = 1 x ) = # ( D ,  exit  , x ) # ( D ,  exit  ) = 3 3 = 1 x)=(#(D," exit ",x))/(#(D," exit "))=(3)/(3)=1x)=\frac{\#(D, \text { exit }, x)}{\#(D, \text { exit })}=\frac{3}{3}=1
   T ^ ( E T ^ ( E hat(T)(E\hat{T}(E ，北， C ) = # ( E , north , C ) # ( E , north ) = 2 2 = 1 C ) = # ( E ,  north  , C ) # ( E ,  north  ) = 2 2 = 1 C)=(#(E," north ",C))/(#(E," north "))=(2)/(2)=1C)=\frac{\#(E, \text { north }, C)}{\#(E, \text { north })}=\frac{2}{2}=1
  奖励函数： R ^ ( s , a , s ′ ) R ^ s , a , s ′ hat(R)(s,a,s^('))\hat{R}\left(s, a, s^{\prime}\right)
   R ^ ( A R ^ ( A hat(R)(A\hat{R}(A ，退出， x ) = − 10 x ) = − 10 x)=-10x)=-10
   R ^ ( B R ^ ( B hat(R)(B\hat{R}(B ，东， C ) = − 1 C ) = − 1 C)=-1C)=-1
   R ^ ( C R ^ ( C hat(R)(C\hat{R}(C ，东， A ) = − 1 A ) = − 1 A)=-1A)=-1
   R ^ ( C R ^ ( C hat(R)(C\hat{R}(C 东， D ) = − 1 D ) = − 1 D)=-1D)=-1
   R ^ ( D R ^ ( D hat(R)(D\hat{R}(D ，出口， x ) = + 10 x ) = + 10 x)=+10x)=+10
   R ^ ( E R ^ ( E hat(R)(E\hat{R}(E ，北， C ) = − 1 C ) = − 1 C)=-1C)=-1
根据大数定律，随着我们通过让智能体体验更多幕来收集越来越多的样本，我们对 T ^ T ^ hat(T)\hat{T} 和 R ^ R ^ hat(R)\hat{R} 的模型将得到改进，其中 T ^ T ^ hat(T)\hat{T} 收敛于 T T TT ，并且当我们发现新的（ s , a , s ′ s , a , s ′ s,a,s^(')s, a, s^{\prime} ）元组时， R ^ R ^ hat(R)\hat{R} 会获得先前未发现的奖励的知识。每当我们认为合适时，我们可以结束智能体的训练，通过使用我们当前的 T ^ T ^ hat(T)\hat{T} 和 R ^ R ^ hat(R)\hat{R} 模型运行价值或策略迭代来生成策略 π exploit π exploit  pi_("exploit ")\pi_{\text {exploit }} ，并使用 π exploit π exploit  pi_("exploit ")\pi_{\text {exploit }} 进行利用，让我们的智能体遍历 MDP，采取行动以寻求奖励最大化，而不是寻求学习。
我们很快将讨论如何在探索和利用之间有效分配时间的方法。基于模型的学习非常简单直观，但非常有效，仅通过计数和归一化即可生成 T ^ T ^ hat(T)\hat{T} 和 R ^ R ^ hat(R)\hat{R} 。但是，维护每个（ s , a , s ′ s , a , s ′ s,a,s^(')s, a, s^{\prime} ）元组的计数可能很昂贵，因此在下一节关于无模型学习的内容中，我们将开发绕过维护计数的方法，并避免基于模型的学习所需的内存开销。

5. 3. 无模型学习

  6. 3 无模型学习

接下来是无模型学习！有几种无模型学习算法，我们将介绍其中的三种：直接评估、时序差分学习和 Q 学习。直接评估和时序差分学习属于一类被称为被动强化学习的算法。在被动强化学习中，智能体被赋予一个策略来遵循，并在体验 episode 时学习该策略下状态的价值，这与 MDP 的策略评估在 T T TT 和 R R RR 已知时所做的事情完全相同。Q 学习属于第二类无模型学习算法，称为主动强化学习，在此期间，学习智能体可以使用它收到的反馈来迭代更新其策略，同时进行学习，直到最终在充分探索后确定最佳策略。

  7. 3. 1 直接评估

我们将介绍的第一种被动强化学习技术被称为直接评估，这种方法就像它的名字一样枯燥和简单。直接评估所做的就是确定一些策略 π π pi\pi ，并让智能体在遵循 π π pi\pi 的同时体验几个回合。当智能体通过这些回合收集样本时，它会维护从每个状态获得的总效用计数以及访问每个状态的次数。在任何时候，我们都可以通过将从 s s ss 获得的总效用除以访问 s s ss 的次数来计算任何状态 s s ss 的估计值。让我们对之前的示例运行直接评估，回想一下 γ = 1 γ = 1 gamma=1\gamma=1 。
  图 1：示例图像
通过第一个回合，我们可以看到从状态 D D DD 到终止，我们获得了 10 的总奖励，从状态 C C CC 我们获得了 ( − 1 ) + 10 = 9 ( − 1 ) + 10 = 9 (-1)+10=9(-1)+10=9 的总奖励，从状态 B B BB 我们获得了
( − 1 ) + ( − 1 ) + 10 = 8 ( − 1 ) + ( − 1 ) + 10 = 8 (-1)+(-1)+10=8(-1)+(-1)+10=8 。完成此过程将产生每个状态在各个回合中的总奖励，以及由此产生的估计值，如下所示：
s   总奖励   访问次数 V π ( s ) V π ( s ) V^(pi)(s)\mathrm{V}^{\pi}(\mathrm{s})
A -10 1 -10
B 16 2 8
C 16 4 4
D 30 3 10
E -4 2 -2
s Total Reward Times Visited V^(pi)(s) A -10 1 -10 B 16 2 8 C 16 4 4 D 30 3 10 E -4 2 -2| s | Total Reward | Times Visited | $\mathrm{V}^{\pi}(\mathrm{s})$ | | :--- | :--- | :--- | :--- | | A | -10 | 1 | -10 | | B | 16 | 2 | 8 | | C | 16 | 4 | 4 | | D | 30 | 3 | 10 | | E | -4 | 2 | -2 |
虽然直接评估最终会学习到每个状态的状态值，但由于它浪费了状态之间转换的信息，因此收敛速度通常不必要地慢。
图2：带注释的示例
在我们的例子中，我们计算了 V π ( E ) = − 2 V π ( E ) = − 2 V^(pi)(E)=-2V^{\pi}(E)=-2 和 V π ( B ) = 8 V π ( B ) = 8 V^(pi)(B)=8V^{\pi}(B)=8 ，但根据我们收到的反馈，这两个状态都只有 C C CC 作为后继状态，并且在转换到 C C CC 时会产生相同的 -1 奖励。根据贝尔曼方程，这意味着 B B BB 和 E E EE 在 π π pi\pi 下应该具有相同的值。然而，在我们的智能体处于状态 C C CC 的 4 次中，它有 3 次转换到 D D DD 并获得了 10 的奖励，还有 1 次转换到 A A AA 并获得了 -10 的奖励。纯粹是偶然，它获得 -10 奖励的唯一一次是从状态 E E EE 而不是 B B BB 开始的，但这严重扭曲了 E E EE 的估计值。通过足够的 episode， B B BB 和 E E EE 的值将收敛到它们的真实值，但像这样的情况会导致该过程比我们希望的要长。通过选择使用我们的第二个被动强化学习算法，即时序差分学习，可以缓解这个问题。

5.3.2 时序差分学习

时序差分学习（TD 学习）使用从每次经验中学习的想法，而不是简单地跟踪总奖励和状态被访问的次数，并在最后像直接评估那样进行学习。在策略评估中，我们使用了由我们的固定策略和贝尔曼方程生成的方程组来确定该策略下状态的值（或者使用像值迭代这样的迭代更新）。
V π ( s ) = ∑ s ′ T ( s , π ( s ) , s ′ ) [ R ( s , π ( s ) , s ′ ) + γ V π ( s ′ ) ] V π ( s ) = ∑ s ′   T s , π ( s ) , s ′ R s , π ( s ) , s ′ + γ V π s ′ V^(pi)(s)=sum_(s^('))T(s,pi(s),s^('))[R(s,pi(s),s^('))+gammaV^(pi)(s^('))]V^{\pi}(s)=\sum_{s^{\prime}} T\left(s, \pi(s), s^{\prime}\right)\left[R\left(s, \pi(s), s^{\prime}\right)+\gamma V^{\pi}\left(s^{\prime}\right)\right]
这些方程中的每一个都将一个状态的值等同于该状态的后继状态的折扣值的加权平均值，加上转换到这些后继状态时获得的奖励。TD 学习试图回答
问题在于如何在没有权重的情况下计算这个加权平均值，巧妙地使用指数移动平均法来实现。我们首先初始化 ∀ s , V π ( s ) = 0 ∀ s , V π ( s ) = 0 AA s,V^(pi)(s)=0\forall s, V^{\pi}(s)=0 。在每个时间步，智能体从状态 s s ss 采取行动 π ( s ) π ( s ) pi(s)\pi(s) ，转移到状态 s ′ s ′ s^(')s^{\prime} ，并获得奖励 R ( s , π ( s ) , s ′ ) R s , π ( s ) , s ′ R(s,pi(s),s^('))R\left(s, \pi(s), s^{\prime}\right) 。我们可以通过将收到的奖励与 π π pi\pi 下 s ′ s ′ s^(')s^{\prime} 的当前折扣值相加来获得样本值：
  样本 = R ( s , π ( s ) , s ′ ) + γ V π ( s ′ ) = R s , π ( s ) , s ′ + γ V π s ′ =R(s,pi(s),s^('))+gammaV^(pi)(s^('))=R\left(s, \pi(s), s^{\prime}\right)+\gamma V^{\pi}\left(s^{\prime}\right)
这个样本是 V π ( s ) V π ( s ) V^(pi)(s)V^{\pi}(s) 的新估计值。下一步是将这个抽样估计值通过指数移动平均法纳入我们现有的 V π ( s ) V π ( s ) V^(pi)(s)V^{\pi}(s) 模型中，该方法遵循以下更新规则：
   V π ( s ) ← ( 1 − α ) V π ( s ) + α ⋅ V π ( s ) ← ( 1 − α ) V π ( s ) + α ⋅ V^(pi)(s)larr(1-alpha)V^(pi)(s)+alpha*V^{\pi}(s) \leftarrow(1-\alpha) V^{\pi}(s)+\alpha \cdot 样本
上面， α α alpha\alpha 是一个受 0 ≤ α ≤ 1 0 ≤ α ≤ 1 0 <= alpha <= 10 \leq \alpha \leq 1 约束的参数，称为学习率，它指定了我们想要分配给现有 V π ( s ) , 1 − α V π ( s ) , 1 − α V^(pi)(s),1-alphaV^{\pi}(s), 1-\alpha 模型的权重，以及我们想要分配给新的抽样估计值 α α alpha\alpha 的权重。通常从 α = 1 α = 1 alpha=1\alpha=1 的学习率开始，相应地将 V π ( s ) V π ( s ) V^(pi)(s)V^{\pi}(s) 分配给第一个样本，然后慢慢地将其缩小到0，此时所有后续样本都将被清零，并停止影响我们的 V π ( s ) V π ( s ) V^(pi)(s)V^{\pi}(s) 模型。
让我们停下来分析一下更新规则。通过定义 V k π ( s ) V k π ( s ) V_(k)^(pi)(s)V_{k}^{\pi}(s) 和样本 k k _(k){ }_{k} 分别为在第 k th k th  k^("th ")k^{\text {th }} 次更新后状态 s s ss 的估计值和第 k th k th  k^("th ")k^{\text {th }} 个样本，来注释模型在不同时间点的状态，我们可以重新表达我们的更新规则：
   V k π ( s ) ← ( 1 − α ) V k − 1 π ( s ) + α ⋅ V k π ( s ) ← ( 1 − α ) V k − 1 π ( s ) + α ⋅ V_(k)^(pi)(s)larr(1-alpha)V_(k-1)^(pi)(s)+alpha*V_{k}^{\pi}(s) \leftarrow(1-\alpha) V_{k-1}^{\pi}(s)+\alpha \cdot 样本 k k _(k)_{k}
V k π ( s ) V k π ( s ) V_(k)^(pi)(s)V_{k}^{\pi}(s) 的这个递归定义恰好非常有趣，可以展开：
V k π ( s ) ← α ⋅ [ ( 1 − α ) k − 1 ⋅ V k π ( s ) ← α ⋅ ( 1 − α ) k − 1 ⋅ V_(k)^(pi)(s)larr alpha*[(1-alpha)^(k-1)*:}V_{k}^{\pi}(s) \leftarrow \alpha \cdot\left[(1-\alpha)^{k-1} \cdot\right. 样本 1 + … + ( 1 − α ) ⋅ 1 + … + ( 1 − α ) ⋅ _(1)+dots+(1-alpha)*_{1}+\ldots+(1-\alpha) \cdot 样本 k − 1 + k − 1 + _(k-1)+_{k-1}+ 样本 k ] k {:_(k)]\left._{k}\right]
因为 0 ≤ ( 1 − α ) ≤ 1 0 ≤ ( 1 − α ) ≤ 1 0 <= (1-alpha) <= 10 \leq(1-\alpha) \leq 1 ，当我们把数量 ( 1 − α 1 − α 1-alpha1-\alpha ) 提高到越来越大的幂时，它会越来越接近 0。通过我们推导出的更新规则扩展，这意味着旧样本的权重呈指数级下降，这正是我们想要的，因为这些旧样本是使用较旧（因此也较差）的 V π ( s ) ! V π ( s ) ! V^(pi)(s)!V^{\pi}(s)! 模型计算出来的。这就是时序差分学习的魅力——通过一个简单的更新规则，我们能够：
  • 在每个时间步都进行学习，因此可以利用我们获得的状态转移信息，因为我们在样本中使用的是 V π ( s ′ ) V π s ′ V^(pi)(s^('))V^{\pi}\left(s^{\prime}\right) 的迭代更新版本，而不是等到最后才进行任何计算。
  • 对较旧的、可能不太准确的样本给予指数级递减的权重。
  • 与直接评估相比，通过更少的 episode 就能更快地收敛到学习真实状态值。

  5.3.3 Q-学习

直接评估和时序差分学习最终都会学习到它们所遵循策略下所有状态的真实价值。然而，它们都有一个主要的固有问题——我们希望为我们的智能体找到一个最优策略，这需要知道状态的 Q 值。为了从我们拥有的价值中计算 Q 值，我们需要一个转移函数和奖励函数，正如贝尔曼方程所规定的。
Q ∗ ( s , a ) = ∑ s ′ T ( s , a , s ′ ) [ R ( s , a , s ′ ) + γ V ∗ ( s ′ ) ] Q ∗ ( s , a ) = ∑ s ′   T s , a , s ′ R s , a , s ′ + γ V ∗ s ′ Q^(**)(s,a)=sum_(s^('))T(s,a,s^('))[R(s,a,s^('))+gammaV^(**)(s^('))]Q^{*}(s, a)=\sum_{s^{\prime}} T\left(s, a, s^{\prime}\right)\left[R\left(s, a, s^{\prime}\right)+\gamma V^{*}\left(s^{\prime}\right)\right]
因此，时序差分学习或直接评估通常与一些基于模型的学习结合使用，以获取 T T TT 和 R R RR 的估计值，从而有效地更新学习智能体所遵循的策略。一种名为 Q 学习的革命性新思想避免了这种情况，它提出直接学习状态的 Q 值，从而绕过了对任何价值、转移函数或奖励函数的了解需求。因此，Q 学习是完全无模型的。Q 学习使用以下更新规则来执行所谓的 Q 值迭代：
Q k + 1 ( s , a ) ← ∑ s ′ T ( s , a , s ′ ) [ R ( s , a , s ′ ) + γ max a ′ Q k ( s ′ , a ′ ) ] Q k + 1 ( s , a ) ← ∑ s ′   T s , a , s ′ R s , a , s ′ + γ max a ′   Q k s ′ , a ′ Q_(k+1)(s,a)larrsum_(s^('))T(s,a,s^('))[R(s,a,s^('))+gammamax_(a^('))Q_(k)(s^('),a^('))]Q_{k+1}(s, a) \leftarrow \sum_{s^{\prime}} T\left(s, a, s^{\prime}\right)\left[R\left(s, a, s^{\prime}\right)+\gamma \max _{a^{\prime}} Q_{k}\left(s^{\prime}, a^{\prime}\right)\right]
请注意，此更新只是对价值迭代的更新规则的略微修改。实际上，唯一真正的区别是，由于我们在处于某个状态时选择一个动作，然后在处于 Q 状态时才选择一个新动作，因此对动作的最大运算符的位置已更改。
在转换之前选择一个动作，但我们在处于 Q 状态时才选择一个新动作。
有了这条新的更新规则，Q 学习的推导过程与 TD 学习基本相同，都是通过获取 Q Q Q\mathbf{Q} 值样本：
  样本 = R ( s , a , s ′ ) + γ max a ′ Q ( s ′ , a ′ ) = R s , a , s ′ + γ max a ′   Q s ′ , a ′ =R(s,a,s^('))+gammamax_(a^('))Q(s^('),a^('))=R\left(s, a, s^{\prime}\right)+\gamma \max _{a^{\prime}} Q\left(s^{\prime}, a^{\prime}\right)
并将它们纳入指数移动平均。
   Q ( s , a ) ← ( 1 − α ) Q ( s , a ) + α ⋅ Q ( s , a ) ← ( 1 − α ) Q ( s , a ) + α ⋅ Q(s,a)larr(1-alpha)Q(s,a)+alpha*Q(s, a) \leftarrow(1-\alpha) Q(s, a)+\alpha \cdot 样本
只要我们在探索上花费足够的时间，并以适当的速度降低学习率 α α alpha\alpha ，Q 学习就能学习到每个 Q 状态的最优 Q 值。这正是 Q 学习如此具有革命性的原因。TD 学习和直接评估通过遵循策略来学习策略下状态的值，然后再通过其他技术确定策略的最优性，而 Q 学习可以直接学习最优策略，即使采取次优或随机行动。这被称为离策略学习（与直接评估和 TD 学习相反，后者是同策略学习的例子）。

5.3.4 近似 Q 学习

Q 学习是一种令人难以置信的学习技术，它仍然是强化学习领域发展的核心。然而，它仍然有一些改进的空间。就目前而言，Q 学习只是以表格形式存储状态的所有 Q 值，考虑到强化学习的大多数应用都有成千上万甚至数百万个状态，这并不是特别有效。这意味着我们无法在训练期间访问所有状态，即使可以，也无法存储所有 Q 值，因为缺乏内存。
如上所述，如果吃豆人在运行普通的 Q 学习后发现图 1 不利，那么它仍然不知道图 2 甚至图 3 也是不利的。近似 Q 学习试图通过学习一些一般情况并推断到许多类似情况来解决这个问题。推广学习经验的关键是基于特征的状态表示，它将每个状态表示为一个称为特征向量的向量。例如，吃豆人的特征向量可以编码：
  • 到最近的幽灵的距离。
  • 到最近的食物颗粒的距离。
  • 幽灵的数量。
  • 吃豆人被困住了吗？0或1。
利用特征向量，我们可以将状态和 Q 状态的值视为线性价值函数：
V ( s ) = w 1 ⋅ f 1 ( s ) + w 2 ⋅ f 2 ( s ) + … + w n ⋅ f n ( s ) = w → ⋅ f → ( s ) V ( s ) = w 1 ⋅ f 1 ( s ) + w 2 ⋅ f 2 ( s ) + … + w n ⋅ f n ( s ) = w → ⋅ f → ( s ) V(s)=w_(1)*f_(1)(s)+w_(2)*f_(2)(s)+dots+w_(n)*f_(n)(s)= vec(w)* vec(f)(s)V(s)=w_{1} \cdot f_{1}(s)+w_{2} \cdot f_{2}(s)+\ldots+w_{n} \cdot f_{n}(s)=\vec{w} \cdot \vec{f}(s)
Q ( s , a ) = w 1 ⋅ f 1 ( s , a ) + w 2 ⋅ f 2 ( s , a ) + … + w n ⋅ f n ( s , a ) = w → ⋅ f → ( s , a ) Q ( s , a ) = w 1 ⋅ f 1 ( s , a ) + w 2 ⋅ f 2 ( s , a ) + … + w n ⋅ f n ( s , a ) = w → ⋅ f → ( s , a ) Q(s,a)=w_(1)*f_(1)(s,a)+w_(2)*f_(2)(s,a)+dots+w_(n)*f_(n)(s,a)= vec(w)* vec(f)(s,a)Q(s, a)=w_{1} \cdot f_{1}(s, a)+w_{2} \cdot f_{2}(s, a)+\ldots+w_{n} \cdot f_{n}(s, a)=\vec{w} \cdot \vec{f}(s, a)
  其中
f → ( s ) = [ f 1 ( s ) f 2 ( s ) … f n ( s ) ] T f → ( s ) = f 1 ( s ) f 2 ( s ) … f n ( s ) T vec(f)(s)=[[f_(1)(s),f_(2)(s),dots,f_(n)(s)]]^(T)\vec{f}(s)=\left[\begin{array}{llll}f_{1}(s) & f_{2}(s) & \ldots & f_{n}(s)\end{array}\right]^{T}
  并且
f → ( s , a ) = [ f 1 ( s , a ) f 2 ( s , a ) … f n ( s , a ) ] T f → ( s , a ) = f 1 ( s , a ) f 2 ( s , a ) … f n ( s , a ) T vec(f)(s,a)=[[f_(1)(s","a),f_(2)(s","a),dots,f_(n)(s","a)]]^(T)\vec{f}(s, a)=\left[\begin{array}{llll}f_{1}(s, a) & f_{2}(s, a) & \ldots & f_{n}(s, a)\end{array}\right]^{T}
分别表示状态 s s ss 和 Q 状态( s , a s , a s,as, a )的特征向量， w → = [ w 1 w 2 … w n ] w → = w 1 w 2 … w n vec(w)=[[w_(1),w_(2),dots,w_(n)]]\vec{w}=\left[\begin{array}{llll}w_{1} & w_{2} & \ldots & w_{n}\end{array}\right] 表示权重向量。将差定义为
  差值 = [ R ( s , a , s ′ ) + γ max a ′ Q ( s ′ , a ′ ) ] − Q ( s , a ) = R s , a , s ′ + γ max a ′   Q s ′ , a ′ − Q ( s , a ) =[R(s,a,s^('))+gammamax_(a^('))Q(s^('),a^('))]-Q(s,a)=\left[R\left(s, a, s^{\prime}\right)+\gamma \max _{a^{\prime}} Q\left(s^{\prime}, a^{\prime}\right)\right]-Q(s, a)
近似 Q 学习的工作方式与 Q 学习几乎相同，使用以下更新规则：
   w i ← w i + α ⋅ w i ← w i + α ⋅ w_(i)larrw_(i)+alpha*w_{i} \leftarrow w_{i}+\alpha \cdot 差值 ⋅ f i ( s , a ) ⋅ f i ( s , a ) *f_(i)(s,a)\cdot f_{i}(s, a)
与为每个状态存储 Q 值不同，通过近似 Q 学习，我们只需要存储一个权重向量，并且可以根据需要按需计算 Q 值。因此，这不仅为我们提供了一个更通用的 Q 学习版本，而且还提供了一个内存效率更高的版本。
关于 Q 学习的最后一点说明，我们可以使用差分重新表达精确 Q 学习的更新规则，如下所示：
   Q ( s , a ) ← Q ( s , a ) + α ⋅ Q ( s , a ) ← Q ( s , a ) + α ⋅ Q(s,a)larr Q(s,a)+alpha*Q(s, a) \leftarrow Q(s, a)+\alpha \cdot 差分
第二种表示法为我们提供了对更新的略有不同但同样有价值的解释：它计算的是抽样估计值与 Q ( s , a ) Q ( s , a ) Q(s,a)Q(s, a) 的当前模型之间的差值，并使模型朝着估计值的方向移动，移动的幅度与差值的幅度成正比。

5. 4 探索与利用

6. 4 探索与利用

我们现在已经介绍了若干种不同的方法，让智能体学习最优策略，并且强调了“充分探索”是必要的，但没有真正阐述“充分”意味着什么。在接下来的章节中，我们将讨论两种在探索和利用之间分配时间的方法： ϵ ϵ epsilon\epsilon -贪婪策略和探索函数。

7. 4. 1 ε ε epsi\varepsilon -贪婪策略

遵循 ϵ ϵ epsilon\epsilon -贪婪策略的智能体定义了一个概率 0 ≤ ϵ ≤ 1 0 ≤ ϵ ≤ 1 0 <= epsilon <= 10 \leq \epsilon \leq 1 ，并以概率 ϵ ϵ epsilon\epsilon 随机行动和探索。相应地，他们遵循当前已建立的策略，并以概率 ( 1 − ϵ 1 − ϵ 1-epsilon1-\epsilon ) 进行利用。这是一个非常容易实现的策略，但仍然可能很难处理。如果为 ϵ ϵ epsilon\epsilon 选择一个较大的值，那么即使在学习了最优策略之后，智能体仍然会主要表现出随机行为。类似地，选择一个较小的 ϵ ϵ epsilon\epsilon 值意味着智能体将不经常探索，导致 Q 学习（或任何其他选定的学习算法）非常缓慢地学习最优策略。为了解决这个问题，必须手动调整 ϵ ϵ epsilon\epsilon ，并随着时间的推移降低其值才能看到结果。

5.4.2 探索函数

通过探索函数可以避免手动调整 ϵ ϵ epsilon\epsilon 的问题，探索函数使用修改后的 Q 值迭代更新，从而优先访问较少访问的状态。修改后的更新如下：
Q ( s , a ) ← ( 1 − α ) Q ( s , a ) + α ⋅ [ R ( s , a , s ′ ) + γ max a ′ f ( s ′ , a ′ ) ] Q ( s , a ) ← ( 1 − α ) Q ( s , a ) + α ⋅ R s , a , s ′ + γ max a ′   f s ′ , a ′ Q(s,a)larr(1-alpha)Q(s,a)+alpha*[R(s,a,s^('))+gammamax_(a^('))f(s^('),a^('))]Q(s, a) \leftarrow(1-\alpha) Q(s, a)+\alpha \cdot\left[R\left(s, a, s^{\prime}\right)+\gamma \max _{a^{\prime}} f\left(s^{\prime}, a^{\prime}\right)\right]
其中 f f ff 表示一个探索函数。在设计探索函数时存在一定程度的灵活性，但一个常见的选择是使用：
f ( s , a ) = Q ( s , a ) + k N ( s , a ) f ( s , a ) = Q ( s , a ) + k N ( s , a ) f(s,a)=Q(s,a)+(k)/(N(s,a))f(s, a)=Q(s, a)+\frac{k}{N(s, a)}
其中 k k kk 是某个预先确定的值，而 N ( s , a ) N ( s , a ) N(s,a)N(s, a) 表示 Q 状态（ s , a s , a s,as, a ）被访问的次数。状态 s s ss 中的智能体总是选择每个状态中具有最高 f ( s , a ) f ( s , a ) f(s,a)f(s, a) 的动作，因此永远不必在探索和利用之间做出概率性决策。相反，探索由探索函数自动编码，因为项 k N ( s , a ) k N ( s , a ) (k)/(N(s,a))\frac{k}{N(s, a)} 可以给一些不常采取的动作足够的“奖励”，使其被选择而不是具有更高 Q 值的动作。随着时间的推移，状态被更频繁地访问，这种奖励对于每个状态都会减少到 0，并且 f ( s , a ) f ( s , a ) f(s,a)f(s, a) 向 Q ( s , a ) Q ( s , a ) Q(s,a)Q(s, a) 回归，使得利用变得越来越具有排他性。

  5.5 总结

  5.5 总结

非常重要的是要记住，强化学习有一个底层的 MDP，而强化学习的目标是通过推导出一个最优策略来解决这个 MDP。强化学习与价值迭代和策略迭代等方法的区别在于，它缺乏对底层 MDP 的转移函数 T T TT 和奖励函数 R R RR 的了解。因此，智能体必须通过在线试错而不是纯粹的离线计算来学习最优策略。有很多方法可以做到这一点：
  • 基于模型的学习：运行计算来估计转移函数 T T TT 和奖励函数 R R RR 的值，并使用 MDP 求解方法（如价值或策略迭代）以及这些估计值。
  • 无模型的学习：避免估计 T T TT 和 R R RR ，而是使用其他方法直接估计状态的值或 Q 值。
  • 直接评估：遵循策略 π π pi\pi ，简单地计算从每个状态获得的总奖励以及每个状态被访问的总次数。如果采集了足够的样本，这会收敛到 π π pi\pi 下状态的真实值，尽管速度很慢并且浪费了关于状态之间转换的信息。
  • 时序差分学习：遵循策略 π π pi\pi ，并使用指数移动平均与采样值，直到收敛到 π π pi\pi 下状态的真实值。时序差分学习和直接评估是在线策略学习的示例，它在决定策略是否为次优以及是否需要更新之前，学习特定策略的值。
  • Q-学习：通过试错和 Q 值迭代更新直接学习最优策略。这是离线策略学习的一个例子，即使在采取次优行动时也能学习到最优策略。
  • 近似 Q 学习：与 Q 学习做同样的事情，但使用基于特征的状态表示来泛化学习。
  • 为了量化不同强化学习算法的性能，我们使用后悔值的概念。后悔值体现了从一开始就在环境中采取最优行动所累积的总奖励，与通过运行学习算法所累积的总奖励之间的差异。