贝尔曼方程

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

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

动作值函数的贝尔曼方程

动作值函数的贝尔曼方程

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

证明过程

易证：

$$G_t=\sum _{k=0}{\gamma }^k{R}_{t+k}=R_t+\gamma \cdot G_{t+1}$$

那么有：

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

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

状态值函数的贝尔曼方程

状态值函数的贝尔曼方程

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

证明过程

由状态值函数的定义：$V_{\pi }(S_t)={\mathbb{E}}_{A_t}[Q_{\pi }(S_t,A_t)]$ 得到：

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

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

另一种形式

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

$$V_{\pi }(s)=\sum _{a\in \mathcal{A}}\pi (a\mid s)Q_{\pi }(s,a)\text{\hspace{1em}(1)}$$

---

$$Q_{\pi }(s,a)=R(s,a)+\gamma \sum _{s^{\prime }\in \mathcal{S}}{P}_{s{s}^{\prime }}^a{V}_{\pi }(s^{\prime })\text{\hspace{1em}(2)}$$

---

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

$$V_{\pi }(s)=\sum _{a\in \mathcal{A}}\pi (a\mid s)(R(s,a)+\gamma \sum _{s^{\prime }\in \mathcal{S}}{P}_{s{s}^{\prime }}^a{V}_{\pi }(s^{\prime }))\text{\hspace{1em}(3)}$$

---

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

$$Q_{\pi }(s,a)=R(s,a)+\gamma \sum _{s^{\prime }\in \mathcal{S}}{P}_{s{s}^{\prime }}^a\sum _{a\in \mathcal{A}}\pi (a^{\prime }\mid s^{\prime })Q_{\pi }(s^{\prime },a^{\prime })\text{\hspace{1em}(4)}$$

---

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

贝尔曼最优方程

之前定义了最优状态值函数 $V_{\ast }(s)$ 和最优动作值函数 $Q_{\ast }(s,a)$，如果只关注最优值：

$$V_{\ast }(s)=\sum _{a\in \mathcal{A}}\pi (a\mid s)Q_{\ast }(s,a)$$

$$Q_{\ast }(s,a)=R(s,a)+\gamma \sum _{s^{\prime }\in \mathcal{S}}{P}_{s{s}^{\prime }}^a{V}_{\ast }(s^{\prime })$$

$$V_{\ast }(s)=\sum _{a\in \mathcal{A}}\pi (a\mid s)(R(s,a)+\gamma \sum _{s^{\prime }\in \mathcal{S}}{P}_{s{s}^{\prime }}^a{V}_{\ast }(s^{\prime }))\text{\hspace{1em}(5)}$$

$$Q_{\ast }(s,a)=R(s,a)+\gamma \sum _{s^{\prime }\in \mathcal{S}}{P}_{s{s}^{\prime }}^a\sum _{a\in \mathcal{A}}\pi (a^{\prime }\mid s^{\prime })Q_{\ast }(s^{\prime },a^{\prime })\text{\hspace{1em}(6)}$$

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

总结

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

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