2.4-贝尔曼方程

2.4 贝尔曼方程

现在我们来介绍贝尔曼方程，这是一种分析状态值的数学工具。简而言之，贝尔曼方程是一组线性方程，描述了所有状态值之间的关系。

首先，注意到\(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)\)中的两个项进行分析。

1. 第一项\(\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)\)。为简单起见，我们放弃对\(s\)或\((s, a)\)的依赖。不过，在存在依赖关系的情况下，结论仍然有效。

2. 第二项\(\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)\)感到困惑，因为它依赖于另一个未知的\(v_\pi(s')\). 必须注意的是，贝尔曼方程指的是所有状态下的一组线性方程，而不是单一方程。如果我们把这些方程放在一起，就会发现如何计算所有状态值就很清楚了。详情将在第\(2.7\)节中介绍。

• \(\pi(a|s)\)是给定的政策。由于状态值可用于评价策略，因此从贝尔曼方程中求解状态值是一个策略评价过程，这也是许多强化学习算法中的一个重要过程，本书稍后会介绍。

• \(p(r|s,a)\)和\(p(s'|s,a)\)代表系统模型。在\(2.7\)节中，我们将首先展示如何利用模型计算状态值，本书将在后面介绍如何通过使用无模型算法(free model )，在不使用模型的情况下做到这一点。

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

首先，从总概率理论中可以得出:

\[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).\]

因此，公式\((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]中使用的表达式

其次，在某些问题中，奖励\(r\)可能只取决于下一个状态\(s'\)。因此，我们可以将奖励写成\(r(s')\)，因此\(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)\left[r(s^{\prime})+\gamma v_{\pi}(s^{\prime})\right].\]