贝尔曼方程

贝尔曼方程 (Bellman Equation) 描述了动作价值函数的递归关系。

贝尔曼方程

假设 $R_t$ 是 $S_t,A_t,S_{t+1}$ 的函数。那么

$$Q_{\pi }\left(s_t,a_t\right)={\mathbb{E}}_{S_{t+1},A_{t+1}}\left[R_t+\gamma \cdot Q_{\pi }\left(S_{t+1},A_{t+1}\right)\mid S_t=s_t,A_t=a_t\right]$$

通过 $Q,V$ 之间的关系，我们可以得到贝尔曼方差的其他两种形式：

$$\begin{array}{rl}{Q}_{\pi }\left(s_t,a_t\right)& ={\mathbb{E}}_{S_{t+1}}\left[R_t+\gamma \cdot V_{\pi }\left(S_{t+1}\right)\mid S_t=s_t,A_t=a_t\right]\\ V_{\pi }\left(s_t\right)& ={\mathbb{E}}_{A_t,S_{t+1}}\left[R_t+\gamma \cdot V_{\pi }\left(S_{t+1}\right)\mid S_t=s_t\right]\end{array}$$

贝尔曼方程的证明

$$\begin{array}{rl}{Q}_{\pi }\left(s_t,a_t\right)& ={\mathbb{E}}_{S_{t+1},A_{t+1}}\left[U_t\mid S_t=s_t,A_t=a_t\right]\\ & ={\mathbb{E}}_{S_{t+1},A_{t+1}}\left[R_t+\gamma \cdot U_{t+1}\mid S_t=s_t,A_t=a_t\right]\\ & ={\mathbb{E}}_{S_{t+1},A_{t+1}}\left[R_t\mid S_t=s_t,A_t=a_t\right]+\gamma \cdot {\mathbb{E}}_{S_{t+1},A_{t+1}}\left[U_{t+1}\mid S_t=s_t,A_t=a_t\right]\end{array}$$

分析第二项，$U_{t+1}$ 的期望可以写成

$$\begin{array}{rl}& {\mathbb{E}}_{{\mathcal{S}}_{t+1},{\mathcal{A}}_{t+1}}\left[U_{t+1}\mid S_t=s_t,A_t=a_t\right]\\ =& {\mathbb{E}}_{S_{t+1},A_{t+1}}\left[{\mathbb{E}}_{S_{t+2},A_{t+2}}\left[U_{t+1}\mid S_{t+1},A_{t+1}\right]\mid S_t=s_t,A_t=a_t\right]\\ =& {\mathbb{E}}_{S_{t+1},A_{t+1}}\left[Q_{\pi }\left(S_{t+1},A_{t+1}\right)\mid S_t=s_t,A_t=a_t\right]\end{array}$$

综上所述，我们得到

$$Q_{\pi }\left(s_t,a_t\right)={\mathbb{E}}_{S_{t+1},A_{t+1}}\left[R_t+\gamma \cdot Q_{\pi }\left(S_{t+1},A_{t+1}\right)\mid S_t=s_t,A_t=a_t\right]$$

最优贝尔曼方程

假设 $R_t$ 是 $S_t,A_t,S_{t+1}$ 的函数。那么

$$Q_{\ast }\left(s_t,a_t\right)={\mathbb{E}}_{S_{t+1}\sim p\left(\mid s_t,a_t\right)}\left[R_t+\gamma \cdot \underset{A\in \mathcal{A}}{\max }{Q}_{\ast }\left(S_{t+1},A\right)\mid S_t=s_t,A_t=a_t\right]$$

最优贝尔曼方程的证明

设最优策略函数为 ${\pi }^{\ast }=\arg {\max }_{\pi }{Q}_{\pi }(s,a),\forall s\in \mathcal{S},a\in \mathcal{A}$。由贝尔曼方程可得：

$$Q_{{\pi }^{\ast }}\left(s_t,a_t\right)={\mathbb{E}}_{S_{t+1},A_{t+1}}\left[R_t+\gamma \cdot Q_{{\pi }^{\ast }}\left(S_{t+1},A_{t+1}\right)\mid S_t=s_t,A_t=a_t\right]$$

根据定义，最优动作价值函数是

$$Q_{\ast }(s,a)\triangleq \underset{\pi }{\max }{Q}_{\pi }(s,a),\forall s\in \mathcal{S},a\in \mathcal{A}$$

所以 $Q_{{\pi }^{\ast }}(s,a)$ 就是 $Q_{\ast }(s,a)$。于是

$$Q_{\ast }\left(s_t,a_t\right)={\mathbb{E}}_{S_{t+1},A_{t+1}}\left[R_t+\gamma \cdot Q_{\ast }\left(S_{t+1},A_{t+1}\right)\mid S_t=s_t,A_t=a_t\right]$$

因为动作 $A_{t+1}=\arg {\max }_A{Q}_{\ast }\left(S_{t+1},A\right)$ 是状态 $S_{t+1}$ 的确定性函数，所以

$$Q_{\ast }\left(s_t,a_t\right)={\mathbb{E}}_{S_{t+1}}\left[R_t+\gamma \cdot \underset{A\in \mathcal{A}}{\max }{Q}_{\ast }\left(S_{t+1},A\right)\mid S_t=s_t,A_t=a_t\right]$$