引言与背景

价值函数方法是强化学习中的核心技术，它解决了传统表格方法在处理大型状态或动作空间时的效率问题。本文探讨了从表格表示向函数表示的转变，这是强化学习算法发展的重要里程碑。

在强化学习的发展路径中，价值函数方法位于从基于模型到无模型、从表格表示到函数表示的演进过程中。它结合了时序差分学习的思想，并通过函数近似技术来处理复杂环境。

价值表示：从表格到函数

表格与函数表示的对比

传统的表格方法将状态值存储在一个表格中：

而函数近似方法则使用参数化函数来表示这些值，例如：

其中 $\varphi (s)\in {\mathbb{R}}^2$ 称作是状态 $s$ 的特征向量，$w$ 是参数向量。

两种不同的表现形式的区别主要体现在以下几个方面：

• 值的检索方式
• 值的更新方式

函数复杂度与近似能力

函数的复杂度决定了其近似的能力：

• 一阶线性函数：$\hat{v}(s,w)=as+b=[s,1{]}^T[a,b{]}^T={\varphi }^T(s)w$
• 二阶多项式：$\hat{v}(s,w)=a{s}^2+bs+c=[s^2,s,1{]}^T[a,b,c{]}^T={\varphi }^T(s)w$
  随着函数阶数增加，近似精度提高，但参数向量维度也增加，需要更多存储和计算资源。

值得注意的是，上面两个例子中的 $\hat{v}(s,w)$ 对于 $w$ 来说是线性的（尽管对于 $s$ 可能是非线性的）。这种类型的方法称为线性函数逼近（linear function approximation），这是最简单的函数逼近方法。

那么还有一个问题是如何求解最优参数向量呢，当我们已知真实状态值 $\{v_{\pi }(s_i){\}}_{i=1}^n$，寻找最优参数向量 $w$ 就转化为一个标准的最小二乘问题。我们需要优化以下目标函数：

这个目标函数衡量的是函数近似值与真实值之间的平方误差总和。我们希望找到一个参数向量 $w$，使得这个误差最小化。

上述目标函数可以用矩阵形式更简洁地表示：

其中：

• $\Phi =\left[\begin{array}{c}{\varphi }^T(s_1)\\ ⋮\\ {\varphi }^T(s_n)\end{array}\right]\in {\mathbb{R}}^{n\times d}$ 是特征矩阵，每一行是一个状态的特征向量
• $v_{\pi }=\left[\begin{array}{c}{v}_{\pi }(s_1)\\ ⋮\\ v_{\pi }(s_n)\end{array}\right]\in {\mathbb{R}}^n$ 是真实状态值向量
• $d$ 是特征向量的维度（在例子中是2）
  这个最小二乘问题的最优解有一个闭式解：

在实际的强化学习算法中，我们通常无法直接计算这个闭式解，因为我们不知道真实值 $v_{\pi }$。相反，我们使用时序差分学习等方法来迭代地近似这个解，这将在后续中详细介绍。

基于函数近似的时序差分(TD)

目标函数

基于函数近似的TD learning旨在最小化以下目标函数：

其中期望是相对于随机变量 $S\in \mathcal{S}$ 计算的。

这个目标函数可以基于不同的状态分布来定义：

1. 均匀分布：
1. 稳态分布：$J(w)={\sum }_{s\in \mathcal{S}}{d}_{\pi }(s)(v_{\pi }(s)-\hat{v}(s,w){)}^2$
   🧾 **马尔可夫决策过程的稳态分布**

优化算法

为了最小化(1)式中的目标函数 $J(w)$，可以使用梯度下降算法：

使用随机梯度下降，得到：

由于真实值 $v_{\pi }(s_t)$ 未知，可以使用以下替代：

1. 蒙特卡洛方法：使用回报 $g_t$ 作为 $v_{\pi }(s_t)$ 的近似
1. 时序差分方法：使用 $r_{t+1}+\gamma \hat{v}(s_{t+1},w_t)$ ，即 TD target 作为 $v_{\pi }(s_t)$ 的近似
   因此，TD学习更新规则为：

在线性情况下（$\hat{v}(s,w)={\varphi }^T(s)w$），此时更新规则简化为：

函数近似下的TD learning 算法伪代码如下：

• 线性函数近似
• 特征向量类型

理论分析

收敛性分析

TD算法的收敛性可以通过分析以下确定性算法来研究：

(10)式可以看作是(11)式的 SGD实现，这个式子初看起来比较复杂，实际非常简单，我们可以做一些简化，

其中 $\Phi$ 是包含所有特征向量的矩阵，$D$ 是对角阵，其对角线是稳态分布。这两个矩阵将经常使用。

(11)式 可以重写为：

其中：

• $A={\Phi }^{T}D(I-\gamma P_{\pi })\Phi \in {\mathbb{R}}^{m\times m}$
• $b={\Phi }^{T}D{r}_{\pi }\in {\mathbb{R}}^m$
  证明可以参考Mathematical Foundations of Reinforcement Learning中的Box 8.3

此时，(11)式可以写为

这是一个简单的确定性过程，其收敛性分析如下。

首先，$w_t$ 的收敛值是什么？假设当 $t\to \infty$ 时，$w_t$ 收敛到一个常数值 $w^{\ast }$，那么根据 (12)式：

这表明 $b-A{w}^{\ast }=0$，因此：

关于这个收敛值，有几点重要的说明：

• 矩阵A的可逆性
• $w^{\ast }=A^{-1}b$ 的解释
• 表格方法是个特例
  其次，我们证明 (13)式 中的 $w_t$ 当 $t\to \infty$ 时收敛到 $w^{\ast }=A^{-1}b$。由于 (13)式 是一个简单的确定性过程，可以通过多种方式证明。我们提供两种证明：

🧾 ****

这种收敛性分析表明，TD-线性算法在适当条件下会收敛到最优参数值，这个参数值不仅能够最小化投影贝尔曼误差，而且在特殊情况下（表格表示）恰好等于真实状态值。

TD Learning与投影贝尔曼误差（projected Bellman error）

我们之前已经证明TD-线性算法收敛到 $w^{\ast }=A^{-1}b$，接下来我们将证明 $w^{\ast }$ 是最小化投影贝尔曼误差的最优解。为此，我们回顾三种目标函数。

1. 状态值误差
1. 贝尔曼误差
1. 投影贝尔曼误差
   由于TD算法旨在最小化 $J_{PBE}$ 而非 $J_E$，自然要问估计值 $\hat{v}(w)$ 与真实状态值 $v_{\pi }$ 的接近程度。在线性情况下，最小化投影贝尔曼误差的估计值是 $\hat{v}(w^{\ast })=\Phi w^{\ast }$。它与真实状态值 $v_{\pi }$ 的偏差满足：

这个不等式的证明在Mathematical Foundations of Reinforcement Learning中的Box 8.6中给出。

不等式(17)表明 $\Phi w^{\ast }$ 与 $v_{\pi }$ 之间的差距上界是 $J_E(w)$ 的最小值。然而，这个界限较松，特别是当 $\gamma$ 接近1时。因此，它主要具有理论价值。

最小二乘时序差分(LSTD)

接下来我们介绍一种称为最小二乘时序差分(LSTD)的算法。与TD-线性算法一样，LSTD旨在最小化投影贝尔曼误差。然而，它比TD-线性算法有一些优势。

回顾最小化投影贝尔曼误差的最优参数是 $w^{\ast }=A^{-1}b$，其中 $A={\Phi }^{T}D(I-\gamma P_{\pi })\Phi$ 和 $b={\Phi }^{T}D{r}_{\pi }$。实际上，$A$ 和 $b$ 也可以写为（参考Mathematical Foundations of Reinforcement LearningBox 8.1）：

上面两个等式表明 $A$ 和 $b$ 是 $s_t$, $s_{t+1}$, $r_{t+1}$ 的期望。LSTD的思想很简单：如果我们可以使用随机样本直接获得 $A$ 和 $b$ 的估计值（分别记为 $\hat{A}$ 和 $\hat{b}$），那么最优参数可以直接估计为 $w^{\ast }\approx {\hat{A}}^{-1}\hat{b}$。

具体来说，假设 $(s_0,r_1,s_1,\dots ,s_t,r_{t+1},s_{t+1},\dots )$ 是通过遵循给定策略 $\pi$ 获得的轨迹。设 ${\hat{A}}_t$ 和 ${\hat{b}}_t$ 分别是时间 $t$ 时 $A$ 和 $b$ 的估计值。它们计算为样本的平均值：