强化学习（Reinforcement Lrarning，RL）03：贝尔曼方程

强化学习（Reinforcement Lrarning，RL）03：贝尔曼方程

• 强化学习（Reinforcement Lrarning，RL）03：贝尔曼方程
• • 1. 状态价值
  • • 1.1状态价值函数（State Value Function）
    • 1.2 最优策略（Optimal Policy）
  • 2. 贝尔曼方程
  • • 2.1 贝尔曼方程（Bellman Equation）
    • 2.2 贝尔曼方程的推导
    • 2.3 贝尔曼方程矩阵形式（Matrix-vector form of Bellman Equation）
    • 2.4 求解贝尔曼方程
    • • 方法一：矩阵求解
      • 方法二：迭代算法（优先采用）
  • 3. 动作价值函数
  • • 3.1动作价值函数（Action Value Fuction）
    • 3.2 贝尔曼最优方程（Bellman Optimal Equation, BOE）

强化学习（Reinforcement Lrarning，RL）03：贝尔曼方程

1. 状态价值

1.1状态价值函数（State Value Function）

评估智能体从某特定状态开始，遵循某一策略进行决策时，所能获得的预期累计奖励的大小。具体来说，状态价值函数定义为智能体处于状态 s s s 时，按照某一策略 π \pi π 进行后续决策所能得到的未来奖励的期望值，用 V π ( s ) V_{\pi}(s) Vπ​(s) 表示。数学上，可以表示为：
V π ( s ) = E π [ G t ∣ S t = s ] = E π [ ∑ t = 0 ∞ γ t R t ∣ S t = s ] (1) V_\pi(s)=E_\pi[G_t|S_t=s]=E_\pi[\sum_{t=0}^\infty \gamma^tR_{t}|S_t=s] \tag{1} Vπ​(s)=Eπ​[Gt​∣St​=s]=Eπ​[t=0∑∞​γtRt​∣St​=s](1)

其中，

• V π ( s ) V_\pi(s) Vπ​(s) 表示在状态 s s s 下，遵循策略 π \pi π 的状态价值。
• E π E_\pi Eπ​ 表示对策略 π \pi π 下的未来期望求期望值。
• G t G_t Gt​ 表示当前时间步开始的折扣回报，前文：马尔科夫决策过程进行过详细介绍。

1.2 最优策略（Optimal Policy）

通过状态价值,定义最优策略，用 π ∗ \pi^* π∗ 表示。最优策略应该满足下式：
V π ∗ ( s ) ≥ V π ( s ) , ∀ s ∈ S (2) V_{\pi^*}(s) \geq V_{\pi}(s), \forall s \in S \tag{2} Vπ∗​(s)≥Vπ​(s),∀s∈S(2)

2. 贝尔曼方程

2.1 贝尔曼方程（Bellman Equation）

从状态 s s s 开始，按照某一策略 π \pi π 行动时，该状态的价值函数 V π ( s ) V_\pi(s) Vπ​(s) 可以表示为:
V π ( s ) = ∑ a π ( a ∣ s ) [ ∑ r p ( r ∣ s , a ) r + γ ∑ s ′ p ( s ′ ∣ s , a ) V π ( s ′ ) ] (3) V_\pi(s)=\sum_a{\pi(a|s)}[\sum_r{p(r|s,a)r}+\gamma \sum_{s'}{p(s'|s,a)V_\pi(s')}] \tag{3} Vπ​(s)=a∑​π(a∣s)[r∑​p(r∣s,a)r+γs′∑​p(s′∣s,a)Vπ​(s′)](3)

• V π ( s ) V_\pi(s) Vπ​(s) 是在状态 s s s 下遵循策略 π \pi π 的状态价值。
• π ( a ∣ s ) \pi(a|s) π(a∣s) 是在状态 s s s 下采取行动 a a a 的概率。
• p ( s ′ ∣ s , a ) p(s'|s,a) p(s′∣s,a) 是状态 s s s，采取行动 a a a 后转移到状态 s ′ s' s′ 的概率.
• r r r 是即时奖励。
• γ ∈ [ 0 , 1 ) \gamma \in [0, 1) γ∈[0,1) 是未来的折扣因子。

2.2 贝尔曼方程的推导

由于 V π ( s ) V_\pi(s) Vπ​(s) 是回报 G t G_t Gt​ 的期望，则有，
V π ( s ) = E π [ G t ∣ S t = s ] = E π [ R t + γ G t + 1 ∣ S t = s ] = E π [ R t ∣ S t = s ] + γ E π [ G t + 1 ∣ S t = s ] (4) \begin{aligned} V_\pi(s) &= E_\pi[G_t|S_t=s] \\ &= E_\pi[R_t+\gamma G_{t+1}|S_t=s] \\ &= E_\pi[R_t|S_t=s] + \gamma E_\pi[G_{t+1}|S_t=s] \tag{4} \end{aligned} Vπ​(s)​=Eπ​[Gt​∣St​=s]=Eπ​[Rt​+γGt+1​∣St​=s]=Eπ​[Rt​∣St​=s]+γEπ​[Gt+1​∣St​=s]​(4)

其中 E π [ R t ∣ S t = s ] E_\pi[R_t|S_t=s] Eπ​[Rt​∣St​=s] 为即时奖励，
E π [ R t ∣ S t = s ] = ∑ a { π ( a ∣ s ) E [ R t ∣ S t = s , A t = a ] } = ∑ a { π ( a ∣ s ) ∑ r p ( r ∣ s , a ) r } (5) \begin{aligned} E_\pi[R_t|S_t=s] &= \sum_a\{ {\pi(a|s)E[R_t|S_t=s,A_t=a]} \} \\ &= \sum_a\{{ \pi(a|s)\sum_r p(r|s,a)}r \} \tag{5} \end{aligned} Eπ​[Rt​∣St​=s]​=a∑​{π(a∣s)E[Rt​∣St​=s,At​=a]}=a∑​{π(a∣s)r∑​p(r∣s,a)r}​(5)

其中 E π [ G t + 1 ∣ S t = s ] E_\pi[G_{t+1}|S_t=s] Eπ​[Gt+1​∣St​=s] 为未来奖励，
E π [ G t + 1 ∣ S t = s ] = ∑ s ′ { E [ G t + 1 ∣ S t = s , S t + 1 = s ′ ] p ( s ′ ∣ s ) } = ∑ s ′ { E [ G t + 1 ∣ S t + 1 = s ′ ] p ( s ′ ∣ s ) } ( 马尔科夫的无记忆性 ) = ∑ s ′ { V π ( s ) p ( s ′ ∣ s ) } = ∑ s ′ { V π ( s ) ∑ a p ( s ′ ∣ s , a ) π ( a , s ) } (6) \begin{aligned} E_\pi[G_{t+1}|S_t=s] &= \sum_{s'}\{ E[G_{t+1}|S_t=s,S_{t+1}=s']p(s'|s) \} \\ &= \sum_{s'}\{ E[G_{t+1}|S_{t+1}=s']p(s'|s) \} (马尔科夫的无记忆性) \\ &= \sum_{s'}\{ V_{\pi}(s)p(s'|s) \} \\ &= \sum_{s'}\{ V_{\pi}(s) \sum_a p(s'|s,a)\pi(a,s) \} \\ \tag{6} \end{aligned} Eπ​[Gt+1​∣St​=s]​=s′∑​{E[Gt+1​∣St​=s,St+1​=s′]p(s′∣s)}=s′∑​{E[Gt+1​∣St+1​=s′]p(s′∣s)}(马尔科夫的无记忆性)=s′∑​{Vπ​(s)p(s′∣s)}=s′∑​{Vπ​(s)a∑​p(s′∣s,a)π(a,s)}​(6)

综上，由 ( 4 ) ( 5 ) ( 6 ) (4)(5)(6) (4)(5)(6)得出贝尔曼方程的数学表达，
V π ( s ) = E π [ R t ∣ S t = s ] + γ E π [ G t + 1 ∣ S t = s ] = ∑ a π ( a ∣ s ) ∑ r p ( r ∣ s , a ) r   + γ ∑ a π ( a ∣ s ) ∑ s ′ p ( s ′ ∣ s , a ) V π ( s ′ ) = ∑ a π ( a ∣ s ) [ ∑ r p ( r ∣ s , a ) r + γ ∑ s ′ p ( s ′ ∣ s , a ) V π ( s ′ ) ] (7) \begin{aligned} V_\pi(s) &= E_\pi[R_t|S_t=s] + \gamma E_\pi[G_{t+1}|S_t=s] \\ &= \sum_a { \pi(a|s)\sum_r p(r|s,a)r} \ +\gamma \sum_{a} \pi(a|s) \sum_{s'}p(s'|s,a)V_{\pi}(s') \\ &= \sum_a \pi(a|s)[\sum_r p(r|s,a)r + \gamma \sum_{s'}p(s'|s,a)V_{\pi}(s')] \tag{7} \end{aligned} Vπ​(s)​=Eπ​[Rt​∣St​=s]+γEπ​[Gt+1​∣St​=s]=a∑​π(a∣s)r∑​p(r∣s,a)r +γa∑​π(a∣s)s′∑​p(s′∣s,a)Vπ​(s′)=a∑​π(a∣s)[r∑​p(r∣s,a)r+γs′∑​p(s′∣s,a)Vπ​(s′)]​(7)

2.3 贝尔曼方程矩阵形式（Matrix-vector form of Bellman Equation）

重写贝尔曼方程：
V π ( s ) = R π ( s ) + γ ∑ s ′ p π ( s ′ ∣ s ) V π ( s ′ ) (8) V_{\pi}(s) = R_{\pi}(s) + \gamma \sum_{s'}p_{\pi}(s'|s)V_{\pi}(s') \tag{8} Vπ​(s)=Rπ​(s)+γs′∑​pπ​(s′∣s)Vπ​(s′)(8)

其中，
R π ( s ) = ∑ a π ( a ∣ s ) ∑ r p ( r ∣ s , a ) r R_{\pi}(s) = \sum_a \pi(a|s)\sum_r p(r|s,a)r Rπ​(s)=a∑​π(a∣s)r∑​p(r∣s,a)r

p π ( s ′ ∣ s ) = ∑ a π ( a ∣ s ) p ( s ′ ∣ s , a ) p_{\pi}(s'|s) = \sum_a \pi(a|s)p(s'|s,a) pπ​(s′∣s)=a∑​π(a∣s)p(s′∣s,a)

根据 ( 8 ) (8) (8) 式，有
V π ( s i ) = R π ( s i ) + γ ∑ s j p π ( s j ∣ s i ) V π ( s j ) (9) V_{\pi}(s_i) = R_{\pi}(s_i) + \gamma \sum_{s_j}p_{\pi}(s_j|s_i)V_{\pi}(s_j) \tag{9} Vπ​(si​)=Rπ​(si​)+γsj​∑​pπ​(sj​∣si​)Vπ​(sj​)(9)

其中 i i i 为当前时间步的状态个数， j j j 为下一时间步的状态个数，将 i × j i\times j i×j 个 ( 8 ) (8) (8) 式组合，得到贝尔曼方程的矩阵形式：
V π = R π + γ P π V π (10) V_{\pi} = R_{\pi} + \gamma P_{\pi}V_{\pi} \tag{10} Vπ​=Rπ​+γPπ​Vπ​(10)

其中，
V π = [ V π ( s 1 ) , V π ( s 2 ) , . . . , V π ( s n ) ] T ∈ R n R π = [ R π ( s 1 ) , R π ( s 2 ) , . . . , R π ( s n ) ] T ∈ R n P π ∈ R n × n \begin{aligned} V_{\pi} &= [V_{\pi}(s_1),V_{\pi}(s_2), ...,V_{\pi}(s_n)]^T \in R^n \\ R_{\pi} &= [R_{\pi}(s_1),R_{\pi}(s_2), ...,R_{\pi}(s_n)]^T \in R^n \\ P_{\pi} &\in R^{n \times n} \end{aligned} Vπ​Rπ​Pπ​​=[Vπ​(s1​),Vπ​(s2​),...,Vπ​(sn​)]T∈Rn=[Rπ​(s1​),Rπ​(s2​),...,Rπ​(sn​)]T∈Rn∈Rn×n​

[ P π ] i j = P π ( s j ∣ s i ) [P_{\pi}]_{ij}=P_{\pi}(s_j|s_i) [Pπ​]ij​=Pπ​(sj​∣si​) 是状态转移矩阵。

2.4 求解贝尔曼方程

方法一：矩阵求解

通过矩阵运算，得到贝尔曼方程的解：
V π = ( I − γ P π ) − 1 R π (11) V_{\pi} = (I - \gamma P_{\pi})^{-1}R_{\pi} \tag{11} Vπ​=(I−γPπ​)−1Rπ​(11)

缺点：运算量巨大，费时费力（通常不采用）。

方法二：迭代算法（优先采用）

V k + 1 = R π + γ P π V k (12) V_{k+1} = R_{\pi} + \gamma P_{\pi}V_k \tag{12} Vk+1​=Rπ​+γPπ​Vk​(12)

当 k → ∞ ， V k → ( I − γ P π ) − 1 R π k \to \infty，V_{k} \to (I - \gamma P_{\pi})^{-1}R_{\pi} k→∞，Vk​→(I−γPπ​)−1Rπ​

优点：通过迭代次数控制收敛精度（优先采用）。

3. 动作价值函数

3.1动作价值函数（Action Value Fuction）

用来评估在特定状态 s s s下采取某个动作 a a a 后，所能获得的预期回报的函数，用 Q π ( s , a ) Q_{\pi}(s,a) Qπ​(s,a) 表示。它比状态价值函数（State Value Function）提供了更细致的信息，因为它不仅考虑了状态本身的价值，还考虑了采取特定动作的重要性。 数学表达如下 ( 13 ) (13) (13) 式：
Q π ( s , a ) = E [ G t ∣ S t = s , A t = a ] (13) Q_{\pi}(s,a) = E[G_t|S_t=s, A_t=a] \tag{13} Qπ​(s,a)=E[Gt​∣St​=s,At​=a](13)

而
E [ G t ∣ S t = t ] = ∑ a E [ G t ∣ S t = s , A t = a ] π ( a ∣ s ) (14) E[G_t|S_t=t] = \sum_a E[G_t|S_t=s, A_t=a]\pi(a|s) \tag{14} E[Gt​∣St​=t]=a∑​E[Gt​∣St​=s,At​=a]π(a∣s)(14)

在 ( 14 ) (14) (14) 式中，
V π ( s ) = E [ G t ∣ S t = t ] Q π ( s , a ) = ∑ a E [ G t ∣ S t = s , A t = a ] π ( a ∣ s ) \begin{aligned} V_{\pi}(s) &= E[G_t|S_t =t] \\ Q_{\pi}(s,a) &= \sum_a E[G_t|S_t=s, A_t=a]\pi(a|s) \end{aligned} Vπ​(s)Qπ​(s,a)​=E[Gt​∣St​=t]=a∑​E[Gt​∣St​=s,At​=a]π(a∣s)​

因此，有
V π ( s ) = ∑ a π ( a ∣ s ) Q π ( s , a ) (15) V_{\pi}(s) = \sum_a \pi(a|s)Q_{\pi}(s,a) \tag{15} Vπ​(s)=a∑​π(a∣s)Qπ​(s,a)(15)

对比 ( 15 ) (15) (15) 式与 ( 7 ) (7) (7) 式贝尔曼方程，可以得出
Q π ( s , a ) = ∑ r p ( r ∣ s , a ) r + γ ∑ s ′ p ( s ′ ∣ s , a ) V π ( s ′ ) Q_{\pi}(s,a) = \sum_r p(r|s,a)r + \gamma \sum_{s'}p(s'|s,a)V_{\pi}(s') Qπ​(s,a)=r∑​p(r∣s,a)r+γs′∑​p(s′∣s,a)Vπ​(s′)

3.2 贝尔曼最优方程（Bellman Optimal Equation, BOE）

给出定义：
V π ( s ) = m a x π ∑ a π ( a ∣ s ) [ ∑ r p ( r ∣ s , a ) r + γ ∑ s ′ p ( s ′ ∣ s , a ) V π ( s ′ ) ] = m a x π ∑ a π ( a ∣ s ) Q π ( s , a ) \begin{aligned} V_{\pi}(s) &= max_{\pi}\sum_a \pi(a|s)[\sum_r p(r|s,a)r + \gamma \sum_{s'}p(s'|s,a)V_{\pi}(s')] \\ &= max_{\pi} \sum_a \pi(a|s)Q_{\pi}(s,a) \end{aligned} Vπ​(s)​=maxπ​a∑​π(a∣s)[r∑​p(r∣s,a)r+γs′∑​p(s′∣s,a)Vπ​(s′)]=maxπ​a∑​π(a∣s)Qπ​(s,a)​

若有不足之处，欢迎批评指正！