离策略方法中的近似与稳定性挑战

# 离策略方法中的近似与稳定性挑战 ## 1. 离策略发散的示例 ### 1.1 简单示例 在离策略学习中，更新分布与在线策略分布不匹配会带来挑战。为了建立直观理解，先考虑一个简单示例。假设在一个更大的马尔可夫决策过程（MDP）中有两个状态，其估计值分别为 $w$ 和 $2w$，这里参数向量 $w$ 只有一个分量 $w$。在线性函数近似下，如果这两个状态的特征向量分别为简单数字（单分量向量），即 1 和 2 时，就会出现这种情况。 在第一个状态，只有一个动作可用，该动作会确定性地转移到第二个状态，且奖励为 0。假设初始时 $w = 10$，那么从估计值为 10 的状态转移到估计值为 20 的状态，看起来是个好的转移，$w$ 会被增加以提高第一个状态的估计值。如果 $\gamma$ 接近 1，TD 误差将近似为 10，若 $\alpha = 0.1$，为了减少 TD 误差，$w$ 会增加到近似 11。然而，第二个状态的估计值也会增加到近似 22。如果再次发生转移，从估计值约为 11 的状态转移到估计值约为 22 的状态，TD 误差约为 11，比之前更大。这会让人觉得第一个状态被低估，其值会再次增加，这次会增加到约 12.1。实际上，随着进一步更新，$w$ 会发散到无穷大。 更仔细地看更新序列，两个状态之间转移的 TD 误差为： $\delta_t = R_{t+1} + \gamma\hat{v}(S_{t+1}, w_t) - \hat{v}(S_t, w_t) = 0 + \gamma2w_t - w_t = (2\gamma - 1)w_t$ 离策略半梯度 TD(0) 更新公式为： $w_{t+1} = w_t + \alpha\rho_t\delta_t\nabla\hat{v}(S_t, w_t) = w_t + \alpha\cdot 1\cdot(2\gamma - 1)w_t\cdot 1 = [1 + \alpha(2\gamma - 1)]w_t$ 这里重要性采样比 $\rho_t$ 为 1，因为从第一个状态只有一个动作可用，所以目标策略和行为策略下该动作被采取的概率都为 1。如果 $1 + \alpha(2\gamma - 1) > 1$，即 $\gamma > 0.5$ 时，系统不稳定，$w$ 会根据其初始值趋向正无穷或负无穷。而且，稳定性不依赖于具体的步长，只要 $\alpha > 0$，不同的步长只会影响 $w$ 趋向无穷大的速率，而不影响是否会趋向无穷大。 这个示例的关键在于，这个转移会反复发生，而 $w$ 不会在其他转移上更新。在离策略训练中这是可能的，因为行为策略可能会选择目标策略永远不会选择的动作，对于这些转移，$\rho_t$ 为 0，不会进行更新。而在在线策略训练中，$\rho_t$ 始终为 1。每次从 $w$ 状态转移到 $2w$ 状态使 $w$ 增加时，也必须有从 $2w$ 状态的转移，这个转移会减少 $w$，除非转移到的值比 $2w$ 更高的状态，否则 $w$ 会被减少。 ### 1.2 Baird 反例 上述简单示例只是一个完整 MDP 的片段，缺乏说服力。Baird 反例给出了一个完整的发散示例。考虑一个具有七个状态、两个动作的阶段性 MDP。虚线动作会使系统以相等概率转移到六个上层状态之一，而实线动作会使系统转移到第七个状态。行为策略 $b$ 选择虚线和实线动作的概率分别为 $\frac{6}{7}$ 和 $\frac{1}{7}$，使得在该策略下的下一个状态分布是均匀的（所有非终止状态相同），这也是每个阶段的起始分布。目标策略 $\pi$ 总是选择实线动作，所以在线策略分布（对于 $\pi$）集中在第七个状态。所有转移的奖励都为 0，折扣率 $\gamma = 0.99$。 考虑根据每个状态圆圈中所示表达式进行线性参数化来估计状态值。例如，最左边状态的估计值为 $2w_1 + w_8$，这里下标对应于整体权重向量 $w \in R^8$ 的分量，这对应于第一个状态的特征向量为 $x(1) = (2, 0, 0, 0, 0, 0, 0, 1)^T$。由于所有转移的奖励都为 0，真实值函数 $v_{\pi}(s) = 0$，对于所有 $s$，当 $w = 0$ 时可以精确近似。实际上，由于权重向量的分量（8 个）比非终止状态（7 个）多，有很多解。而且，特征向量集 $\{x(s) : s \in S\}$ 是线性独立的。从这些方面看，这个任务似乎是线性函数近似的有利情况。 如果对这个问题应用半梯度 TD(0)，权重会发散到无穷大。即使使用动态规划（DP）进行期望更新，系统仍然不稳定。这表明，即使是最简单的自举和函数近似组合，如果更新不是根据在线策略分布进行，也可能不稳定。 ### 1.3 Q - learning 的反例 也有类似于 Baird 反例的情况表明 Q - learning 会发散。这令人担忧，因为在其他情况下，Q - learning 在所有控制方法中具有最好的收敛保证。人们付出了很多努力来寻找解决这个问题的方法或获得一些较弱但仍然可行的保证。例如，只要行为策略足够接近目标策略，如 $\epsilon$ - 贪心策略，可能可以保证 Q - learning 的收敛。但到目前为止，还没有理论分析。 ### 1.4 其他探索思路 #### 1.4.1 采用最小二乘法近似 有人想知道，如果在每次迭代中不是朝着期望的单步回报迈一步，而是将值函数完全改变为最佳的最小二乘法近似，是否能解决不稳定性问题。如果特征向量集 $\{x(s) : s \in S\}$ 是线性独立的，就像在 Baird 反例中那样，那么每次迭代都可以进行精确近似，方法会简化为标准的表格型 DP，问题可以解决。但关键是考虑无法得到精确解的情况，在这种情况下，即使每