跳转至

2.7-根据贝尔曼方程求解状态值

2.7根据贝尔曼方程求解状态值

计算给定策略的状态值是强化学习中的一个基本问题。这个问题通常被称为 "策略评估"(policy evaluation)。在本节中，我们将介绍从贝尔曼方程计算状态值的两种方法。

2.7.1 封闭式解决方案

由于\(v_{\pi}=r_{\pi}+\gamma P_{\pi}v_{\pi}\)是一个简单的线性方程，因此很容易求出其封闭方程的解，即

\[v_{\pi}=(I-\gamma P_{\pi})^{-1}r_{\pi}.\]

下面给出了\((I-\gamma P_{\pi})^{-1}\)的一些特性。

  • \(I-\gamma P_{\pi}\)是可逆的。证明如下，根据格什高林圆定理[4]，\(I-\gamma P_{\pi}\)的每个特征值都位于至少一个格什高林圆内。第\(i\)个格什高林圆的圆心位于\([I-\gamma P_{\pi}]_{ii}=1-\gamma p_{\pi}(s_{i}|s_{i})\)，半径等于\(\sum_{j\neq i}[I-\gamma P_{\pi}]_{ij}=-\sum_{j\neq i}\gamma p_{\pi}(s_{j}|s_{i}).\)。由于\(\gamma<1\)，我们知道半径小于中心大小: \(\sum_{j\neq i}\gamma p_{\pi}(s_{j}|s_{i})<1-\gamma p_{\pi}(s_{i}|s_{i}).\)。因此，所有格什高林圆都不环绕原点，因此\(I-\gamma P_{\pi}\)的任何特征值都不为零。

  • \((I-\gamma P_{\pi})^{-1} \geq I\)，这意味着\((I - \gamma P_\pi)\)的每个元素都是非负的，而且更具体地说，不小于单位矩阵的元素。这是因为\(P_\pi\)具有非负数项,因此\((I-\gamma P_{\pi})^{-1}=I+\gamma P_{\pi}+\gamma^{2}P_{\pi}^{2}+\cdots\geq I\geq0\)。

  • 对于任何矢量\(r\geq 0\)，都认为\((I-\gamma P_{\pi})^{-1}r\geq r \geq 0\)。这一性质源于因为\([(I-\gamma P_{\pi})^{-1}-I]r\geq0\)。因此，如果\(r_1\geq r_2\)，我们有\((I-\gamma P_\pi)^{-1}r_1\geq(I-\gamma P_\pi)^{-1}r_2\)。

Note

虽然这个公式非常优美，但是在实际求解中我们并不会使用，因为他涉及到一个对矩阵求逆的过程，而现实情况中状态空间是很大的。

2.7.2 迭代解

尽管封闭式解法有助于理论分析，但在实践中并不适用，因为它涉及逆矩阵的运算，而这一运算仍需要通过其他数值算法来计算。 计算。事实上，我们可以用下面的迭代算法直接求解贝尔曼方程

\[v_{k+1}=r_{\pi}+\gamma P_{\pi}v_{k},\quad k=0,1,2,\ldots,\tag{2.11}\]

该算法生成一串值\({v_0,v_1,v_2,\cdots}\)，其中\(v_0\in \mathbb{R}^n\)是对\(v_\pi\)的初始猜测。条件是

\[v_{k}\to v_{\pi}=(I-\gamma P_{\pi})^{-1}r_{\pi},\quad\mathrm{as}k\to\infty.\tag{2.12}\]

感兴趣的读者可以看下列证明

Note

将误差定义为\(\delta_k = v_k - v_\pi\)。我们只需证明\(\delta_k \rightarrow 0\)。\(v_{k+1} = \delta_{k+1} + v_\pi\) 和 \(v_k = \delta_k + v_\pi\) 代入 \(v_{k+1} = r_\pi + \gamma P_\pi v_k\) 可得

\[\delta_{k+1}+v_\pi=r_\pi+\gamma P_\pi(\delta_k+v_\pi),\]

可以被写为

\[\begin{aligned}\delta_{k+1}&=-v_{\pi}+r_{\pi}+\gamma P_{\pi}\delta_{k}+\gamma P_{\pi}v_{\pi},\\&=\gamma P_{\pi}\delta_{k}-v_{\pi}+(r_{\pi}+\gamma P_{\pi}v_{\pi}),\\&=\gamma P_{\pi}\delta_{k}.\end{aligned}\]

因此

\[\delta_{k+1}=\gamma P_{\pi}\delta_{k}=\gamma^{2}P_{\pi}^{2}\delta_{k-1}=\cdots=\gamma^{k+1}P_{\pi}^{k+1}\delta_{0}.\]

由于\(P_\pi\)的每个元素都是非负且不大于\(1\)，因此我们可以得出\(0\leq P_\pi^k \leq 1\)，对于任意\(k\)。也就是说，\(P_\pi^k\)的每个元素都不大于\(1\)，另一方面，由于\(\gamma< 1\)，我们知道\(\gamma^k\rightarrow 0\)，因此\(\delta_{k+1}=\gamma^{k+1}P_\pi^{k+1}\delta_0\rightarrow 0\)当\(k\rightarrow\infty\)时。

2.7.3 实例

下面应用\((2.11)\)中的算法求解一些示例的状态值。

图\(2.7\)中展示的例子如下。橘黄色的单元格代表禁区，蓝色的单元格代表目标区域，奖励设置为\(r_{boundary}=r_{forbidden}=-1,r_{target}=1\)。在这里，折现率设置为\(\gamma=0.9\)。

图2.7 (a)两种“好的”策略和其状态值。两种政策的状态值相同、但在第四列的前两个状态下，两种政策是不同的。

图2.7 (b)两种“坏的”策略和对应的状态值，状态值小于"好的"策略的状态值

图\(2.7(a)\)显示了两个"好的"策略及通过\((2.11)\)得出的相应状态值。两个政策的状态值相同，但在第四列的前两个状态不同。 不同。因此，我们知道不同的政策可能具有相同的状态值。

图\(2.7(b)\)显示了两种"坏的"政策及其对应的状态值。这两种政策之所以是坏的，是因为多状态的行动在直觉上是不合理的。所获得的状态值证明了这一推断，可以看出，设定的两种政策的状态值均为负值，且远小于图\(2.7(a)\)中的好政策的状态值。