2.4-贝尔曼方程

本节将来介绍大名鼎鼎的贝尔曼方程 (Bellman equation)。其是用于分析状态值的核心工具。一句话概述：贝尔曼方程描述了所有状态值之间的关系。

下面我们将要详细推导贝尔曼方程。首先，\(G_t\)可以重新写成:

\[\begin{aligned}G_{t}&=R_{t+1}+\gamma R_{t+2}+\gamma^{2}R_{t+3}+\ldots\\&=R_{t+1}+\gamma(R_{t+2}+\gamma R_{t+3}+\ldots)\\&=R_{t+1}+\gamma G_{t+1},\end{aligned}\]

其中\(G_{t+1}=R_{t+2}+\gamma R_{t+3}+\cdots\)。该方程建立了\(G_t\)和 \(G_{t+1}\)之间的关系。因此状态值可以写成:

\[\begin{aligned}v_{\pi}(s)&=\mathbb{E}[G_{t}|S_{t}=s]\\&=\mathbb{E}[R_{t+1}+\gamma G_{t+1}|S_{t}=s]\\&=\mathbb{E}[R_{t+1}|S_{t}=s]+\gamma\mathbb{E}[G_{t+1}|S_{t}=s].\end{aligned}.\tag{2.4}\]

下面对\((2.4)\)中的两项进行分析。

第一项\(\mathbb{E}[R_{t+1}|S_t=s]\)是即时奖励的期望值，通过使用附录\(A\)中的全期望的性质，这一项可以化为:

\[\begin{aligned}\mathbb{E}[R_{t+1}|S_{t}=s]&=\sum_{a\in\mathcal{A}}\pi(a|s)\mathbb{E}[R_{t+1}|S_{t}=s,A_{t}=a]\\&=\sum_{a\in\mathcal{A}}\pi(a|s)\sum_{r\in\mathcal{R}}p(r|s,a)r.\end{aligned}.\tag{2.5}\]

这里，\(\mathcal{A}\)和\(\mathcal{R}\)分别是可能的行动和奖励的集合。对于不同的状态，\(\mathcal{A}\)可能是不同的，此时\(\mathcal{A}\)可以表示为\(\mathcal{A}(s)\)。类似地，\(\mathcal{R}\)也可能依赖于\((s, a)\)。
第二项\(\mathbb{E}[G_{t+1}|S_t=s]\)是未来奖励的期望值，它可以计算为:

\[\begin{aligned}\mathbb{E}[G_{t+1}|S_{t}=s]&=\sum_{s^{\prime}\in\mathcal{S}}\mathbb{E}[G_{t+1}|S_{t}=s,S_{t+1}=s^{\prime}]p(s^{\prime}|s)\\&=\sum_{s^{\prime}\in\mathcal{S}}\mathbb{E}[G_{t+1}|S_{t+1}=s^{\prime}]p(s^{\prime}|s)\quad(\text{due to the Markov property})\\&=\sum_{s^{\prime}\in\mathcal{S}}v_{\pi}(s^{\prime})p(s^{\prime}|s)\\&=\sum_{s^{\prime}\in\mathcal{S}}v_{\pi}(s^{\prime})\sum_{a\in\mathcal{A}}p(s^{\prime}|s,a)\pi(a|s).&(2.6)\end{aligned}\]

Note

首先将条件期望分解为\(\mathbb{E}[G_{t+1}|S_{t}=s,S_{t+1}=s^{\prime}]p(s^{\prime}|s)\)

我们知道,MDP具有马尔可夫性,未来的奖励完全取决于现在的情况，而不是历史的情况。

\(\mathbb{E}[G_{t+1}|S_{t}=s,S_{t+1}=s^{\prime}]=\mathbb{E}[G_{t+1}|S_{t+1}=s^{\prime}],\)

替换价值函数,\(\mathbb{E}[G_{t+1}|S_{t+1}=s^{\prime}]\)正是状态\(s^\prime\)的价值函数\(v_\pi(s^\prime)\)

状态转移概率\(p(s^{\prime}|s)\)可进一步分解为：在策略\(\pi\)下选择行动\(a\)的概率\(\pi(s|a)\)，以及执行行动\(a\)后转移到\(s^\prime\)的概率\(p(s^\prime|s,a)\)。

将\((2.5)-(2.6)\)代入\((2.4)\)可得

\[\begin{aligned}v_{\pi}(s)&=\mathbb{E}[R_{t+1}|S_{t}=s]+\gamma\mathbb{E}[G_{t+1}|S_{t}=s],\\&=\underbrace{\sum_{a\in\mathcal{A}}\pi(a|s)\sum_{r\in\mathcal{R}}p(r|s,a)r}_{\text{mean of immediate rewards}}+\underbrace{\gamma\sum_{a\in\mathcal{A}}\pi(a|s)\sum_{s^{\prime}\in\mathcal{S}}p(s^{\prime}|s,a)v_{\pi}(s^{\prime})}_{\text{mean of future rewards}}\\&=\sum_{a\in\mathcal{A}}\pi(a|s)\left[\sum_{r\in\mathcal{R}}p(r|s,a)r+\gamma\sum_{s^{\prime}\in\mathcal{S}}p(s^{\prime}|s,a)v_{\pi}(s^{\prime})\right],\quad\text{for all }s\in\mathcal{S}.\end{aligned}\tag{2.7}\]

这个方程就是大名鼎鼎的贝尔曼方程，它描述了不同状态值之间的关系。是设计和分析强化学习算法的基本工具。

贝尔曼方程乍看之下似乎很复杂，实际上，它的结构非常清晰。下面是对该方程的解释说明。

\(v_\pi(s)\)和\(v_\pi(s')\)是需要计算的未知状态值。初学者可能难以理解如何求解未知的\(v_\pi(s)\)，因为从式\((2.7)\)来看，状态值存在于等式的两边。必须要注意的是，每一个状态都有这样一个贝尔曼方程，如果我们把这些方程放在一起，如何计算所有状态值就变得很清晰了。详情将在第\(2.7\)节中介绍。
\(\pi(a|s)\)是给定的政策，是已知量。贝尔曼方程一定是对应一个特定的策略。求解贝尔曼方程从而得到状态值是一个策略评价 (policy evaluation)的过程，这是许多强化学习算法中的核心步骤。
\(p(r|s,a)\)和\(p(s'|s,a)\)代表系统模型。这是已知量还是未知量呢？在\(2.7\)节中，我们将首先展示如何利用已知模型计算状态值，在后面的章节中，将会慢慢推广到无模型算法(free model)，在不使用模型的情况下做到这一点。

除了\((2.7)\)中的表达式外，读者还可能在文献中遇到贝尔曼方程的其他表达式。接下来我们介绍三种常见的等价形式。

第一种等价形式是:

\[v_\pi(s)=\sum_{a\in\mathcal{A}}\pi(a|s)\sum_{s^{\prime}\in\mathcal{S}}\sum_{r\in\mathcal{R}}p(s^{\prime},r|s,a)\left[r+\gamma v_\pi(s^{\prime})\right].\]

这是[3]中使用的表达式。这个式子可以通过下面的全概率公式(详见附录A)代入式\((2.9)\)得到，

\[p(s^{\prime}|s,a)=\sum_{r\in\mathcal{R}}p(s^{\prime},r|s,a),\\ p(r|s,a)=\sum_{s^{\prime}\in\mathcal{S}}p(s^{\prime},r|s,a).\]
第二种常见的等价形式是贝尔曼期望方程 (Bellman expectation equation)：

\[v_\pi(s)=\mathbb{E}[R_{t+1}+\gamma v_\pi (S_{t+1})\mid S_t=s ],s\in\mathcal{S}.\]

这是因为\(\mathbb{E}[G_{t+1}\mid S_t=s]=\sum_a \pi(a\mid s) \sum_{a^\prime}p(s^\prime \mid s,a)v_\pi(s^\prime)=\mathbb{E}[{v_\pi(S_{t+1})\mid S_t=s}]\)，将其代入\((2.4)\)中即可得到贝尔曼期望方程。
第三种，在某些问题中，奖励\(r\)可能仅依赖于下一个状态\(s'\)，即奖励可以写成\(r(s^\prime)\)。此时我们有\(p(r(s')|s, a))=(s'|s, a)\)，将其代入\((2.7)\)可以得到另外一个表达式：

\[v_{\pi}(s)=\sum_{a\in\mathcal{A}}\pi(a|s)\sum_{s^{\prime}\in\mathcal{S}}p(s^{\prime}|s,a)[r(s^{\prime})+\gamma v_{\pi}(s^{\prime})].\]

2.4-贝尔曼方程

评论