# 贝尔曼方程

贝尔曼方程(Bellman Equation)把值函数分解为了当前奖励(immediate reward)+ 未来奖励的折扣总和(discounted sum of future rewards)。

贝尔曼方程是一个递归的形式。

# 动作值函数的贝尔曼方程

动作值函数的贝尔曼方程

Qπ(st,at)=ESt+1,At+1[Rt+γQπ(St+1,At+1)St=st,At=at]Q_{\pi}(s_t, a_t) = \mathbb{E}_{S_{t+1}, A_{t+1}} \Big [ R_t + \gamma \cdot Q_{\pi}(S_{t+1}, A_{t+1}) \mid S_t = s_t, A_t = a_t \Big ]

证明过程

易证:

Gt=k=0γkRt+k=Rt+γGt+1G_t = \sum_{k=0} \gamma^k R_{t+k} = R_t + \gamma \cdot G_{t+1}

那么有:

Qπ(st,at)=ESt+1,At+1,[GtSt=st,At=at]=ESt+1,At+1,[Rt+γGt+1St=st,At=at]=ESt+1,At+1,[Rt+γQπ(St+1,At+1)St=st,At=at]\begin{aligned} Q_{\pi}(s_t, a_t) &= \mathbb{E}_{S_{t+1}, A_{t+1}, \cdots} \Big [ G_t \mid S_t = s_t, A_t = a_t \Big ] \\ &= \mathbb{E}_{S_{t+1}, A_{t+1}, \cdots} \Big [ R_t + \gamma \cdot G_{t+1} \mid S_t = s_t, A_t = a_t \Big ] \\ &= \mathbb{E}_{S_{t+1}, A_{t+1}, \cdots} \Big [ R_t + \gamma \cdot Q_{\pi}(S_{t+1}, A_{t+1}) \mid S_t = s_t, A_t = a_t \Big ] \end{aligned}

最后一步是因为动作值函数 Qπ(St+1,At+1)Q_{\pi}(S_{t+1}, A_{t+1}) 求的就是 Gt+1G_{t+1} 的期望。

# 状态值函数的贝尔曼方程

状态值函数的贝尔曼方程

Vπ(st)=EAt,St+1[Rt+γVπ(St+1)St=st]V_{\pi}(s_t) = \mathbb{E}_{A_t, S_{t+1}} \Big [ R_t + \gamma \cdot V_{\pi}(S_{t+1}) \mid S_t = s_t \Big ]

证明过程

状态值函数的定义Vπ(St)=EAt[Qπ(St,At)]V_{\pi}(S_t) = \mathbb{E}_{A_t} \Big [ Q_{\pi}(S_t, A_t) \Big ] 得到:

Qπ(St,At)=ESt+1,At+1[Rt+γQπ(St+1,At+1)St=st,At=at]=ESt+1[Rt+γVπ(St+1)St=st,At=at]\begin{aligned} Q_{\pi}(S_t, A_t) &= \mathbb{E}_{S_{t+1}, A_{t+1}} \Big [ R_t + \gamma \cdot Q_{\pi}(S_{t+1}, A_{t+1}) \mid S_t = s_t, A_t = a_t \Big ] \\ &= \mathbb{E}_{S_{t+1}} \Big [ R_t + \gamma \cdot V_{\pi}(S_{t+1}) \mid S_t = s_t, A_t = a_t \Big ] \end{aligned}

Vπ(St)=EAt[Qπ(St,At)]=EAt,St+1[Rt+γVπ(St+1)St=st]\begin{aligned} V_{\pi}(S_t) &= \mathbb{E}_{A_t} \Big [ Q_{\pi}(S_t, A_t) \Big ] \\ &= \mathbb{E}_{A_t, S_{t+1}} \Big [ R_t + \gamma \cdot V_{\pi}(S_{t+1}) \mid S_t = s_t \Big ] \end{aligned}

# 另一种形式

贝尔曼方程可以表达为另一种形式。

bellman equation 1

Vπ(s)=aAπ(as)Qπ(s,a)(1)V_{\pi}(s) = \sum_{a \in \mathcal{A}} \pi(a \mid s) Q_{\pi}(s, a) \tag{1}


bellman equation 2

Qπ(s,a)=R(s,a)+γsSPssaVπ(s)(2)Q_{\pi}(s, a) = R(s, a) + \gamma \sum_{s' \in \mathcal{S}} P_{ss'}^a V_{\pi}(s') \tag{2}


bellman equation 3

把式 (2) 代入式 (1):

Vπ(s)=aAπ(as)(R(s,a)+γsSPssaVπ(s))(3)V_{\pi}(s) = \sum_{a \in \mathcal{A}} \pi(a \mid s) \Big( R(s, a) + \gamma \sum_{s' \in \mathcal{S}} P_{ss'}^a V_{\pi}(s') \Big) \tag{3}


bellman equation 4

把式 (1) 代入式 (2):

Qπ(s,a)=R(s,a)+γsSPssaaAπ(as)Qπ(s,a)(4)Q_{\pi}(s, a) = R(s, a) + \gamma \sum_{s' \in \mathcal{S}} P_{ss'}^a \sum_{a \in \mathcal{A}} \pi(a' \mid s') Q_{\pi}(s', a') \tag{4}


式 (3) 和式 (4) 就是贝尔曼方程的另一种形式。

# 贝尔曼最优方程

之前定义了最优状态值函数 V(s)V_*(s) 和最优动作值函数 Q(s,a)Q_*(s, a),如果只关注最优值:

V(s)=aAπ(as)Q(s,a)V_*(s) = \sum_{a \in \mathcal{A}} \pi(a \mid s) Q_*(s, a)

Q(s,a)=R(s,a)+γsSPssaV(s)Q_*(s, a) = R(s, a) + \gamma \sum_{s' \in \mathcal{S}} P_{ss'}^a V_*(s')

V(s)=aAπ(as)(R(s,a)+γsSPssaV(s))(5)V_*(s) = \sum_{a \in \mathcal{A}} \pi(a \mid s) \Big( R(s, a) + \gamma \sum_{s' \in \mathcal{S}} P_{ss'}^a V_*(s') \Big) \tag{5}

Q(s,a)=R(s,a)+γsSPssaaAπ(as)Q(s,a)(6)Q_*(s, a) = R(s, a) + \gamma \sum_{s' \in \mathcal{S}} P_{ss'}^a \sum_{a \in \mathcal{A}} \pi(a' \mid s') Q_*(s', a') \tag{6}

式 (5) 和式 (6) 就是贝尔曼最优方程(Bellman Optimality Equation)。

# 总结

贝尔曼方程是大多数强化学习算法的理论基础。

可以看到,如果环境是已知的,即 R(s,a)R(s, a)PssaP_{ss'}^a 已知,这就变成了一个动态规划问题。但在很多问题中,我们并不知道这两个函数,所以不能直接通过贝尔曼方程来求解。