引言与背景

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

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

价值表示：从表格到函数

表格与函数表示的对比

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

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

\[ \hat{v}(s, w) = as + b = [s, 1] \begin{bmatrix} a \\ b \end{bmatrix} = \phi^T(s)w \]

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

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

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

函数复杂度与近似能力

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

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

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

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

\[ J_1 = \sum_{i=1}^n(\hat{v}(s_i, w) - v_\pi(s_i))^2 = \sum_{i=1}^n(\phi^T(s_i)w - v_\pi(s_i))^2 \]

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

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

\[ J_1 = \left\| \begin{bmatrix} \phi^T(s_1) \\ \vdots \\ \phi^T(s_n) \end{bmatrix} w - \begin{bmatrix} v_\pi(s_1) \\ \vdots \\ v_\pi(s_n) \end{bmatrix} \right\|^2 = \|\Phi w - v_\pi\|^2 \]

其中：

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

\[ w^* = (\Phi^T\Phi)^{-1}\Phi^Tv_\pi \]

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

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

目标函数

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

\[ \begin{equation}J(w) = \mathbb{E}[(v_\pi(S) - \hat{v}(S, w))^2]\end{equation} \]

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

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

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

优化算法

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

\[ \begin{equation}w_{k+1} = w_k - \alpha_k \nabla_w J(w_k) = w_k + 2\alpha_k\mathbb{E}[(v_\pi(S) - \hat{v}(S, w_k))\nabla_w\hat{v}(S, w_k)]\end{equation} \]

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

\[ \begin{equation}w_{t+1} = w_t + \alpha_t [v_\pi(s_t) - \hat{v}(s_t, w_t)] \nabla_w\hat{v}(s_t, w_t)\end{equation} \]

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

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

\[ \begin{equation}w_{t+1} = w_t + \alpha_t [r_{t+1} + \gamma\hat{v}(s_{t+1}, w_t) - \hat{v}(s_t, w_t)] \nabla_w\hat{v}(s_t, w_t)\end{equation} \]

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

\[ \begin{equation}w_{t+1} = w_t + \alpha_t [r_{t+1} + \gamma\phi^T(s_{t+1})w_t - \phi^T(s_t)w_t] \phi(s_t)\end{equation} \]

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

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

理论分析

收敛性分析

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

\[ \begin{equation}w_{t+1} = w_t + \alpha_t\mathbb{E}[r_{t+1} + \gamma\phi^T(s_{t+1})w_t - \phi^T(s_t)w_t\phi(s_t)]\end{equation} \]

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

\[ \begin{equation}\Phi = \left\lbrack \begin{matrix} \vdots \\ {\phi }^{T}\left( s\right) \\ \vdots \end{matrix}\right\rbrack \in {\mathbb{R}}^{n \times m},\;D = \left\lbrack \begin{matrix} \ddots & & \\ & {d}_{\pi }\left( s\right) & \\ & & \ddots \end{matrix}\right\rbrack\in {\mathbb{R}}^{n \times n}\end{equation} \]

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

(11)式可以重写为：

\[ \mathbb{E}[r_{t+1} + \gamma\phi^T(s_{t+1})w_t - \phi^T(s_t)w_t\phi(s_t)]= b - Aw_t \]

其中：

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

此时，(11)式可以写为

\[ \begin{equation}w_{t+1} = w_t+ \alpha_t(b - Aw_t)\end{equation} \]

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

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

\[ w^* = w^* + \alpha_\infty(b - Aw^*) \]

这表明 \(b - Aw^* = 0\)，因此：

\[ w^* = A^{-1}b \]

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

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

🧾 ****

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

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

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

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

\[ \begin{equation}\|\hat{v}(w^*) - v_\pi\|_D = \|\Phi w^* - v_\pi\|_D \leq \frac{1}{1-\gamma} \min_w \|\hat{v}(w) - v_\pi\|_D = \frac{1}{1-\gamma} \min_w \sqrt{J_E(w)}\end{equation} \]

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

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

最小二乘时序差分(LSTD)

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

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

\[ \begin{aligned}A &= \mathbb{E}[\phi(s_t)(\phi(s_t) - \gamma\phi(s_{t+1}))^T]\\ b &= \mathbb{E}[r_{t+1}\phi(s_t)]\end{aligned} \]

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

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

\[ \begin{equation}\begin{aligned}\hat{A}t &= \sum_{k=0}^{t-1}\phi(s_k)(\phi(s_k) - \gamma\phi(s_{k+1}))^T\\ \hat{b}t &= \sum_{k=0}^{t-1}r_{k+1}\phi(s_k)\end{aligned}\end{equation} \]