> 文档中心 > 贝尔曼期望方程(Bellman Expectation Equation)

贝尔曼期望方程(Bellman Expectation Equation)

马尔可夫决策过程之贝尔曼期望方程

  • 价值函数与贝尔曼期望方程
    • 回顾
    • 策略的重要性
      • 策略的具体表现形式
      • 如何判断一个策略 π \pi π的优劣性
    • 价值函数(Value Function)
      • 状态价值函数(state-value function)
      • 状态-动作价值函数(action-value function)
    • 贝尔曼期望方程(Behrman Expectation Equation)
      • V π ( s ) V_\pi(s) Vπ(s) q π ( s , a ) q_\pi(s,a) qπ(s,a)之间的关系
      • 贝尔曼期望方程

上一节介绍了马尔可夫奖励过程中(Markov Reward Process,MRP) 出现的概念,本节引入贝尔曼期望方程,讲述马尔可夫决策过程(Markov Decision Process, MDP)的逻辑具体是如何实现的。

价值函数与贝尔曼期望方程

回顾

在介绍马尔可夫奖励过程(MRP)内容中,讲述了马尔可夫决策过程(MDP)的逻辑场景及相关概念,在这里做一个简单回顾:

  • 在某时刻t t t的状态 St S_t St的情况下,在该时刻选择 At A_t At并执行,系统必然将当前状态 St → S_t \to St下一个时刻状态 S t + 1S_{t+1} St+1,状态转移的同时返回奖励结果 R t + 1R_{t+1} Rt+1

在本节中,重新对各概念和条件进行设定;

  • 状态(State) 设置为离散型随机变量,由 n nn种状态构成, S \mathcal SS表示状态集合, S ( k ) S^{(k)}S(k)表示状态集合 S \mathcal SS中编号为 k kk的状态, s, s ′ s,s's,s均表示某种具体状态;
    S = { S ( 1 ) , S ( 2 ) , . . . , S ( n ) } , s , s ′∈ S \mathcal S=\{S^{(1)},S^{(2)},...,S^{(n)}\},s,s' \in \mathcal S S={S(1),S(2),...,S(n)},s,sS

  • 动作(Action) 设置为离散型随机变量,由 m mm种动作构成, A \mathcal AA表示动作集合, A ( k ) A^{(k)}A(k)表示动作集合 A \mathcal AA中编号为 k kk的动作, a, a ′ a,a'a,a表示某种具体动作;
    A = { A ( 1 ) , A ( 2 ) , . . . , A ( m ) } , a , a ′∈ A \mathcal A=\{A^{(1)},A^{(2)},...,A^{(m)}\},a,a' \in \mathcal A A={A(1),A(2),...,A(m)},a,aA

  • 奖励(Reward) 设置为离散型随机变量,由 s ss种奖励构成, R \mathcal RR表示奖励集合, R ( k ) R^{(k)}R(k)表示奖励集合 R \mathcal RR中编号为 k kk的奖励, r rr表示某种具体奖励;
    R = { R ( 1 ) , R ( 2 ) , . . . , R ( s ) } , r ∈ R \mathcal R=\{R^{(1)},R^{(2)},...,R^{(s)}\},r \in \mathcal R R={R(1),R(2),...,R(s)},rR

针对“状态转移过程中”转移到各状态的具体概率(当前状态转移到其他状态(含自身)的概率信息):

  • 若概率分布是离散的 → \to 称为状态转移矩阵(State Transition Matrix)。
  • 若概率分布是连续的 → \to 称为动态特性函数(Dynamic Characteristics Function)。
  • 综合上述设定,在本节使用p (s′ , r ∣ s , a ) p(s',r\mid s,a) p(s,rs,a)表示状态转移矩阵,即:
    p( s ′ ,r∣s,a)=P( S t + 1= s ′ , R t + 1=r∣ S t =s, A t =a) p(s',r\mid s,a) = P(S_{t+1}=s',R_{t+1}=r\mid S_t=s,A_t=a)p(s,rs,a)=P(St+1=s,Rt+1=rSt=s,At=a)

策略的重要性

策略的具体表现形式

马尔可夫决策过程(MDP)的核心在于执行过程中,找到最优的策略 π ( a ∣ s ) \pi(a \mid s) π(as);
策略是如何表示/描述的?
我们从动作(Action)的角度解释策略;
上一节中,我们介绍了两种策略:

  • 确定性策略(Deterministic Policy)
  • 随机性策略(Stochastic Policy)

通过对确定性策略/随机性策略的描述,我们发现任意动作 a a a都不是独立存在并发生的,而是伴随着状态 s s s而产生的;
换句话说,是在状态 s s s的条件下 → \to 选择某种动作 a a a作为当前时刻的待执行动作

示例
前提条件:某决策过程中,动作集合 A \mathcal A A中包含3种动作;状态集合 S \mathcal S S中包含2种状态;
A = {A ( 1 ) ,A ( 2 ) ,A ( 3 ) } , S = {S ( 1 ) ,S ( 2 ) } \mathcal A = \{A^{(1)},A^{(2)},A^{(3)}\},\mathcal S = \{S^{(1)},S^{(2)}\} A={A(1),A(2),A(3)},S={S(1),S(2)}
假设一:确定性策略
若当前状态是 S(1) S^{(1)} S(1),只能唯一确定地选择 A(3) A^{(3)} A(3);
基于上述假设,根据确定性策略, S(1) S^{(1)} S(1)状态下动作选择的概率分布如下表:

动作(Action) 概率(Probability)
A ( 1 ) A^{(1)} A(1) 0.0
A ( 2 ) A^{(2)} A(2) 0.0
A ( 3 ) A^{(3)} A(3) 1.0

表格中描述的概率分布就是一种确定性策略(Deterministic Policy)
假设二:随机性策略
若当前状态是 S(2) S^{(2)} S(2),动作集合 A \mathcal A A中存在2种动作可以选择 → A(1) , A(3) \to A^{(1)},A^{(3)} A(1),A(3),并且各动作被选择的概率分布如下:

动作(Action) 概率(Probability)
A ( 1 ) A^{(1)} A(1) 0.2
A ( 3 ) A^{(3)} A(3) 0.8

同假设一,上述表格描述的也是一种策略 → \to 随机性策略(Stochastic Policy)

如何判断一个策略 π \pi π的优劣性

在判定一个策略 π \pi π的优劣性时,假设状态转移矩阵 p ( s ′ , r ∣ s , a ) = 1 → p(s',r\mid s,a)=1 \to p(s,rs,a)=1此时是一种确定性环境(Deterministic Environment) → \to 只能唯一地选择下一个确定的状态;
基于上述条件下,可以直接使用回报(Return) G t G_t Gt直接作为评价标准 → \to 哪个状态的回报结果大,就选择该状态对应的策略;
但在实际情况中,由于状态转移概率的存在(下一时刻状态的选择存在概率分布),智能体从当前状态到最终状态可能存在多种状态序列 → \to 每个状态序列内有若干不同的回报 G t G_t Gt,因而没有办法直接用 G t G_t Gt比较的方式来确定策略。

换一种思路:
根据状态转移矩阵的定义 → \to 当前状态 S t S_t St到下一时刻状态 St+1 S_{t+1} St+1的可能性的分布;我们将这种可能性作为权重,使用回报的期望(回报可能性的加权和)作为策略的评价指标:
期望值越大 → \to 选择高回报状态的概率就越大 → \to 引入价值函数(Value Function) 来改进策略。

价值函数(Value Function)

价值函数表示当前时刻 t t t状态 S t S_t St确定的情况下,对策略 π ( a ∣ s ) \pi(a \mid s) π(as)的综合性考量。我们从2种角度对策略进行评判:

状态价值函数(state-value function)

状态价值函数表示当前时刻 t t t状态 S t = s S_t=s St=s开始,智能体采取策略 π ( a ∣ s ) \pi(a \mid s) π(as)得到的期望回报
Vπ ( s ) =Eπ [Gt ∣St = s ] V_\pi(s)=E_\pi[G_t \mid S_t=s] Vπ(s)=Eπ[GtSt=s]
我们称 V π ( s ) V_\pi(s) Vπ(s)是策略 π ( a ∣ s ) \pi(a \mid s) π(as)的状态价值函数。可以发现,状态价值函数只包含1个变量 s s s,因此状态价值函数是由状态s s s所具有的价值决定的

状态-动作价值函数(action-value function)

状态动作价值函数表示从当前时刻 t t t状态 S t = s S_t=s St=s开始,智能体遵循策略 π ( a ∣ s ) → \pi(a \mid s) \to π(as) 执行动作 a a a之后的期望回报
q π ( s , a ) = E π [ G t ∣ S t = s , A t = a ] = ∑ s ′ , r p ( s ′ , r ∣ s , a ) [ G t ∣ S t = s , A t = a ] \begin{aligned} q_\pi(s,a) & =E_\pi[G_t \mid S_t=s,A_t=a] \\ & = \sum_{s',r} p(s',r \mid s,a)[G_t \mid S_t=s,A_t=a] \\ \end{aligned} qπ(s,a)=Eπ[GtSt=s,At=a]=s,rp(s,rs,a)[GtSt=s,At=a]
我们称 q π ( s , a ) q_\pi(s,a) qπ(s,a)是策略 π \pi π的状态动作价值函数。可以发现该函数中包含两个变量 s s s a a a,因此状态动作价值函数是由当前状态s s s和动作a a a的共同价值决定的

贝尔曼期望方程(Behrman Expectation Equation)

V π ( s ) V_\pi(s) Vπ(s) q π ( s , a ) q_\pi(s,a) qπ(s,a)之间的关系

我们通过观察发现, q π ( s , a ) q_\pi(s,a) qπ(s,a)就是在 V π ( s ) V_\pi(s) Vπ(s)的基础上选择了某个具体动作 a a a产生的回报结果;换句话说, V π ( s ) V_\pi(s) Vπ(s) s s s状态下的策略中所有可能发生的动作 a a a对应的 q π ( s , a ) q_\pi(s,a) qπ(s,a)的加权平均。
通过上面的推演,我们获得 V π ( s ) V_\pi(s) Vπ(s) q π ( s , a ) q_\pi(s,a) qπ(s,a)之间的关系:
V π ( s ) = ∑ a ∈ A π ( a ∣ s ) [ G t ∣ S t = s , A t = a ] = ∑ a ∈ A π ( a ∣ s ) q π ( s , a ) \begin{aligned} V_\pi(s) & = \sum_{a \in \mathcal A} \pi(a \mid s) [G_t \mid S_t=s,A_t=a] \\ & = \sum_{a \in \mathcal A} \pi(a \mid s) q_\pi(s,a)\\ \end{aligned} Vπ(s)=aAπ(as)[GtSt=s,At=a]=aAπ(as)qπ(s,a)
此时, V π ( s ) V_\pi(s) Vπ(s)可以使用 q π ( s , a ) q_\pi(s,a) qπ(s,a)表示了,反过来, q π ( s , a ) q_\pi(s,a) qπ(s,a)是否可以用 V π ( s ) V_\pi(s) Vπ(s)表示呢?
继续观察:
按照逻辑场景,在执行 a a a之后,系统必然将当前状态 S t = s S_{t}=s St=s转移到下一时刻状态 St+1 S_{t+1} St+1,假设下一时刻状态转移到 s ′ s' s,我们观察 St+1 S_{t+1} St+1的状态价值函数是如何表示的?
Vπ (S t + 1 =s′ ) =Eπ [G t + 1 ∣S t + 1 =s′ ] V_\pi(S_{t+1}=s')=E_\pi[G_{t+1} \mid S_{t+1} =s'] Vπ(St+1=s)=Eπ[Gt+1St+1=s]
从公式组成上和 V π ( s ) V_\pi(s) Vπ(s)没什么区别,只是下标增加了1。我们将 Gt+1 G_{t+1} Gt+1进行展开:
G t + 1 =R t + 2 + γR t + 3 +γ2 R t + 4 + . . . G_{t+1} = R_{t+2} + \gamma R_{t+3} + \gamma^2 R_{t+4} + ... Gt+1=Rt+2+γRt+3+γ2Rt+4+...
再类比一下 G t G_{t} Gt的展开式:
Gt =R t + 1 + γR t + 2 +γ2 R t + 3 + . . . G_{t} = R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + ... Gt=Rt+1+γRt+2+γ2Rt+3+...
我们发现,实际上 G t G_t Gt Gt+1 G_{t+1} Gt+1之间存在如下关系:
Gt =R t + 1 + γG t + 1G_t = R_{t+1} + \gamma G_{t+1} Gt=Rt+1+γGt+1
得到如下关系,重新对 q π ( s , a ) q_\pi(s,a) qπ(s,a)进行展开:
q π ( s , a ) = E π [ G t ∣ S t = s , A t = a ] = ∑ s ′ , r p ( s ′ , r ∣ s , a ) [ G t ∣ S t = s , A t = a ] = ∑ s ′ , r p ( s ′ , r ∣ s , a ) [ r + γ G t + 1 ∣ S t + 1 = s ′ , A t + 1 = a ′ ] = ∑ s ′ , r p ( s ′ , r ∣ s , a ) ( r + γ V π ( s ′ ) ) \begin{aligned} q_\pi(s,a) & =E_\pi[G_t \mid S_t=s,A_t=a] \\ & = \sum_{s',r} p(s',r \mid s,a)[G_t \mid S_t=s,A_t=a] \\ & = \sum_{s',r} p(s',r \mid s,a)[r + \gamma G_{t+1} \mid S_{t+1}=s',A_{t+1}=a'] \\ & = \sum_{s',r} p(s',r \mid s,a)(r + \gamma V_\pi(s'))\\ \end{aligned} qπ(s,a)=Eπ[GtSt=s,At=a]=s,rp(s,rs,a)[GtSt=s,At=a]=s,rp(s,rs,a)[r+γGt+1St+1=s,At+1=a]=s,rp(s,rs,a)(r+γVπ(s))
其中 V π ( s ′ ) V_\pi(s') Vπ(s)表示下一时刻状态 St+1 = s ′ S_{t+1}=s' St+1=s的状态价值函数。
细心的朋友发现,

  • 期望中的条件怎么突然从 St = s ,At = a S_t=s,A_t=a St=s,At=a变成了 S t + 1 =s′ ,A t + 1 =a′ S_{t+1}=s',A_{t+1}=a' St+1=s,At+1=a;
  • Vπ (s′ ) V_\pi(s') Vπ(s) Vπ ( s ) V_\pi(s) Vπ(s)用的根本不是相同的策略,一个是π ( a ∣ s ) \pi(a\mid s) π(as),另一个是π (a′ ∣s′ ) \pi(a' \mid s') π(as)( a′ a' a表示下一时刻选择的某个动作,和当前时刻的a a a区分开)

首先解答第一个问题
G t → Gt+1 G_t \to G_{t+1} GtGt+1时,公式中函数的后验部分不包含任何关于 t t t时刻的信息 → \to 而是 t + 1 t+1 t+1时刻的信息;自然需要转换成 t + 1 t+1 t+1时刻的条件。
新的疑问 St+1 = s ′ , At+1 = a ′ S_{t+1}=s',A_{t+1}=a' St+1=s,At+1=a随便说换就换的吗?

该问题和第二个问题一同解答:
→ \to 我们需要回溯之前 Gt G_t Gt G t + 1G_{t+1} Gt+1之间关系的公式
看起来 G t G_t Gt Gt+1 G_{t+1} Gt+1之间关系是很容易能够归纳出来,但内部的条件是很苛刻的

我们知道, G t G_t Gt t t t时刻 S t = s S_t=s St=s状态下动作的回报;而 Gt+1 G_{t+1} Gt+1 t + 1 t+1 t+1时刻 St+1 = s ′ S_{t+1}=s' St+1=s状态下动作回报;
→ \to 如何使2种相邻时刻并且状态确定的回报产生必然的联系?

总结起来就一句话:我们如何能够在 St = s S_t=s St=s的情况下使得 S t + 1 =s′ S_{t+1}=s' St+1=s

  • 如果当前时刻状态 St = s S_t=s St=s顺利地转移到下一时刻状态 S t + 1 =s′ S_{t+1}=s' St+1=s,那么状态,动作可以变化的同时,还可以执行下一时刻的策略π (a′ ∣s′ ) \pi(a' \mid s') π(as)

至少需要4个条件

  • St = s S_t=s St=s是确定的(这个是必然的,因为它是前提条件);
  • At = a A_t=a At=a
  • R t + 1 = r R_{t+1}=r Rt+1=r
  • S t + 1 =s′ S_{t+1}=s' St+1=s

但凡这4个条件有1个不是确定的 → \to 必然不能满足 G t = Rt+1 + γ Gt+1 G_t = R_{t+1} + \gamma G_{t+1} Gt=Rt+1+γGt+1
换句话说,4个条件全部确定,才能保证 t → t + 1 t \to t+1 tt+1时刻路径的唯一性

回顾上式:
= ∑ s ′ , r p ( s ′ , r ∣ s , a ) [ G t ∣ S t = s , A t = a ] = ∑ s ′ , r p ( s ′ , r ∣ s , a ) [ r + γ G t + 1 ∣ S t + 1 = s ′ , A t + 1 = a ′ ] \begin{aligned} & = \sum_{s',r} p(s',r \mid s,a)[G_t \mid S_t=s,A_t=a] \\ & = \sum_{s',r} p(s',r \mid s,a)[r+ \gamma G_{t+1} \mid S_{t+1}=s',A_{t+1}=a'] \\ \end{aligned} =s,rp(s,rs,a)[GtSt=s,At=a]=s,rp(s,rs,a)[r+γGt+1St+1=s,At+1=a]
该式子中的 S t = s , A t = a , Rt+1 = r , St+1 = s ′ S_t=s,A_t=a,R_{t+1}=r,S_{t+1}=s' St=s,At=a,Rt+1=r,St+1=s都是确定的,该步骤才能成立。
最后一步,根据期望的性质( C C C表示常数):

  • E ( C ) = C E(C)=C E(C)=C
  • E ( C X ) = C E ( X ) E(CX)=CE(X) E(CX)=CE(X)

根据这2条性质,上式可以写成:
= ∑ s ′ , r p ( s ′ , r ∣ s , a ) [ G t ∣ S t = s , A t = a ] = ∑ s ′ , r p ( s ′ , r ∣ s , a ) [ r + γ G t + 1 ∣ S t + 1 = s ′ , A t + 1 = a ′ ] = ∑ s ′ , r p ( s ′ , r ∣ s , a ) ( r + γ [ G t + 1 ∣ S t + 1 = s ′ , A t + 1 = a ′ ] ) = ∑ s ′ , r p ( s ′ , r ∣ s , a ) ( r + γ V π ( s ′ ) ) \begin{aligned} & = \sum_{s',r} p(s',r \mid s,a)[G_t \mid S_t=s,A_t=a] \\ & = \sum_{s',r} p(s',r \mid s,a)[r + \gamma G_{t+1} \mid S_{t+1}=s',A_{t+1}=a'] \\ & = \sum_{s',r} p(s',r \mid s,a)(r + \gamma[G_{t+1} \mid S_{t+1}=s',A_{t+1}=a']) \\ & = \sum_{s',r} p(s',r \mid s,a)(r + \gamma V_\pi(s'))\\ \end{aligned} =s,rp(s,rs,a)[GtSt=s,At=a]=s,rp(s,rs,a)[r+γGt+1St+1=s,At+1=a]=s,rp(s,rs,a)(r+γ[Gt+1St+1=s,At+1=a])=s,rp(s,rs,a)(r+γVπ(s))

贝尔曼期望方程

根据上一节,我们获取了 V π ( s ) V_\pi(s) Vπ(s) q π ( s , a ) q_\pi(s,a) qπ(s,a)之间的关联关系:
Vπ ( s ) =∑ a ∈ A π ( a ∣ s )qπ ( s , a ) V_\pi(s)= \sum_{a \in \mathcal A} \pi(a \mid s) q_\pi(s,a) Vπ(s)=aAπ(as)qπ(s,a)
qπ ( s , a ) =∑ s ′, r p (s′ , r ∣ s , a ) ( r + γVπ (s′ ) ) q_\pi(s,a) = \sum_{s',r} p(s',r \mid s,a)(r + \gamma V_\pi(s')) qπ(s,a)=s,rp(s,rs,a)(r+γVπ(s))
最终将上述2个关系式进行相互套娃,就得到了如下式子:
Vπ ( s ) =∑ a ∈ A π ( a ∣ s )∑ s ′, r p (s′ , r ∣ s , a ) ( r + γVπ (s′ ) ) V_\pi(s) = \sum_{a \in \mathcal A}\pi(a \mid s)\sum_{s',r}p(s',r \mid s,a)(r + \gamma V_\pi(s')) Vπ(s)=aAπ(as)s,rp(s,rs,a)(r+γVπ(s))
qπ ( s , a ) =∑ s ′, r p (s′ , r ∣ s , a ) ( r + γ (∑ a ′∈ A π (a′ ∣s′ )qπ (s′ ,a′ ) ) ) q_\pi(s,a)=\sum_{s',r} p(s',r \mid s,a)(r + \gamma (\sum_{a' \in \mathcal A}\pi(a' \mid s') q_\pi(s',a'))) qπ(s,a)=s,rp(s,rs,a)(r+γ(aAπ(as)qπ(s,a)))

这两个式子都是不动点方程,满足不动点定理,为后续的基于DP,MC的强化学习提供有效的理论支撑。

下一节继续介绍贝尔曼最优方程

相关参考:
【强化学习】马尔科夫决策过程【白板推导系列】
马尔科夫决策过程之Bellman Equation(贝尔曼方程)
深度强化学习原理、算法pytorch实战 - 刘全,黄志刚编著

全民K歌电脑版