为了评估马尔可夫决策过程(MDP)框架内不同策略的有效性或“优劣”,并最终找到最优策略,一个数学基础不可或缺。这种评估是强化学习 (reinforcement learning)的核心。贝尔曼方程提供了将状态(或状态-动作对)的值与后续状态的值关联起来的数学依据,许多强化学习算法都以此为构建依据。
贝尔曼期望方程:评估给定策略
假设我们有一个固定的策略 π,它将状态映射到采取每个可能动作的概率 π(a∣s)。在遵循此策略的情况下,处于特定状态 s 有多大价值?我们使用状态值函数 Vπ(s) 来量化 (quantization)这一点,它定义为从状态 s 开始并随后遵循策略 π 所获得的期望总折扣回报:
Vπ(s)=Eπ[∑k=0∞γkRt+k+1∣St=s]
这里,Eπ[⋅] 表示在智能体遵循策略 π 的情况下的期望值,Rt+k+1 是在时间步 t+k+1 收到的奖励,且 γ∈[0,1] 是用于权衡即时奖励与未来奖励的折扣因子。
贝尔曼期望方程为 Vπ(s) 提供了递归定义。它将状态的值分解为期望的即时奖励和下一个状态的期望折扣值:
Vπ(s)=∑aπ(a∣s)∑s′,rp(s′,r∣s,a)[r+γVπ(s′)]
让我们分析此方程:
- ∑aπ(a∣s):我们对智能体在状态 s 中可能采取的所有动作 a 进行求和,并按策略 π 下采取该动作的概率进行加权。
- ∑s′,rp(s′,r∣s,a):对于选定的动作 a,我们对所有可能的下一个状态 s′ 和奖励 r 进行求和,并按环境的转移动态 p(s′,r∣s,a) 进行加权。这给出了在状态 s 中采取动作 a 的期望结果。
- [r+γVπ(s′)]:这是递归的核心。它是即时奖励 r 加上下一个状态 s′ 的折扣值 Vπ(s′),假设我们从 s′ 开始继续遵循策略 π。
类似地,我们可以定义动作值函数 Qπ(s,a),它表示从状态 s 开始,采取动作 a,然后遵循策略 π 的期望回报:
Qπ(s,a)=Eπ[∑k=0∞γkRt+k+1∣St=s,At=a]
Qπ(s,a) 的贝尔曼期望方程是:
Qπ(s,a)=∑s′,rp(s′,r∣s,a)[r+γ∑a′π(a′∣s′)Qπ(s′,a′)]
该方程表明,在状态 s 中采取动作 a 的值是期望的即时奖励加上下一个状态-动作对的期望折扣值,在下一个状态 s′ 中,对所有根据策略 π 选择的可能的下一个动作 a′ 进行平均。
注意 Vπ 和 Qπ 之间的直接关系:
- 状态的值是根据策略,该状态中可用动作值的期望值:
Vπ(s)=∑aπ(a∣s)Qπ(s,a)
- 状态-动作对的值是期望的即时奖励加上下一个状态的期望折扣值:
Qπ(s,a)=∑s′,rp(s′,r∣s,a)[r+γVπ(s′)]
对于给定的策略 π 和已知的动态 p(s′,r∣s,a),贝尔曼期望方程定义了一个线性方程组。如果状态空间足够小,我们可以直接求解此系统以找到与策略 π 对应的 Vπ 或 Qπ 值函数。
Qπ(s,a) 的递归计算。该值取决于期望的即时奖励 r 和下一个状态-动作对 Qπ(s′,a′) 的折扣期望值,这些值根据环境动态和策略在下一个状态中的选择进行平均。
贝尔曼最优性方程:寻找最佳策略
评估给定策略虽然有用,但许多强化学习 (reinforcement learning)设置中的最终目标是找到一个最优策略,记为 π∗,该策略能从任何起始状态获得尽可能高的期望回报。我们将最优状态值函数 V∗(s) 和最优动作值函数 Q∗(s,a) 定义为:
V∗(s)=maxπVπ(s)
Q∗(s,a)=maxπQπ(s,a)
贝尔曼最优性方程定义了最优策略的值。与期望方程不同,它们包含一个最大化步骤,反映了最优策略必须在每个状态中选择最佳动作这一事实。
V∗(s) 的贝尔曼最优性方程是:
V∗(s)=maxa∑s′,rp(s′,r∣s,a)[r+γV∗(s′)]
该方程表明,状态 s 的最优值是通过选择动作 a 来获得的,该动作最大化了即时奖励 r 和所得下一个状态 s′ 的折扣最优值 γV∗(s′) 的期望和。
Q∗(s,a) 的贝尔曼最优性方程通常更便于决策:
Q∗(s,a)=∑s′,rp(s′,r∣s,a)[r+γmaxa′Q∗(s′,a′)]
在这里,在状态 s 中采取动作 a 的最优值是期望的即时奖励加上在下一个状态 s′ 中可用的最佳可能动作 a′ 的期望折扣值。术语 maxa′Q∗(s′,a′) 等同于 V∗(s′),突出了这种联系:
V∗(s)=maxaQ∗(s,a)
重要地,贝尔曼最优性方程由于 max 运算符的存在而形成一个非线性方程组。求解此系统会得到最优值函数 V∗ 和 Q∗。一旦我们有了 Q∗,寻找最优策略 π∗ 就很简单了:在任何状态 s 中,根据 Q∗ 采取贪婪行动。也就是说,选择使 Q∗(s,a) 最大化的动作 a:
π∗(s)=argmaxaQ∗(s,a)
(如果多个动作具有相同的最大值,则可以选择其中任何一个。)
这些最优性方程并没有直接告诉我们如何找到 V∗ 或 Q∗,但它们定义了最优值必须满足的条件。值迭代和策略迭代(将在下文讨论)等算法运用这些方程来计算模型 p(s′,r∣s,a) 已知情况下的最优策略。对于免模型设置,Q学习等方法根据经验迭代地逼近 Q∗。因此,理解贝尔曼方程对于掌握几乎所有基本的强化学习算法都非常必要。