技术摘要：基于切换系统理论的 Q-learning 分析

1. 问题陈述

Q-learning 是折扣马尔可夫决策过程（MDP）中一种基础的强化学习算法。虽然表格型 Q-learning 已得到充分理解，但对于大规模状态-动作空间，其计算成本过高。标准的补救措施是线性函数逼近（LFA），其中 Q 函数表示为特征的线性组合（$Q_\theta = \Phi\theta$）。

尽管已有广泛研究，但线性 Q-learning（使用 LFA 的 Q-learning）的收敛性和稳定性仍然是一个复杂问题。现有的分析依赖于随机逼近、常微分方程（ODE）方法或贝尔曼收缩性质。由于线性 Q-learning 的确定性递归由于贝尔曼更新中的 $\max$ 算子而具有非线性特征，因此存在一个关键的研究空白，即如何理解有限时间误差行为和精确的稳定性条件。此外，已知投影贝尔曼方程（通常通过投影 Q 值迭代求解）的收敛性与实际线性 Q-learning 更新之间存在差异；前者并不保证后者的收敛。

本文通过开发一种基于**切换线性系统（SLS）**理论的新框架来解决这些问题。核心问题在于表征线性 Q-learning 误差动力学的稳定性，其误差动力学会根据当前的参数估计值和由此导出的贪婪策略在不同的线性模式之间进行切换。

2. 方法论

作者提出了一个将线性 Q-learning 误差动力学建模为**切换线性系统（SLS）**的框架。

2.1 切换系统表示

核心见解在于，两个 Q 值估计之间的非线性差异 $V_\theta - V_{\bar{\theta}}$ 可以表示为一个由随机策略索引的线性算子。具体而言，对于任何 $\theta, \bar{\theta}$，存在一个随机策略 $\mu_{\theta, \bar{\theta}}$ 使得：
$$V_\theta - V_{\bar{\theta}} = \Pi_{\mu_{\theta, \bar{\theta}}} \Phi (\theta - \bar{\theta})$$
其中 $\Pi_\mu$ 是由策略 $\mu$ 诱导的状态-动作转移矩阵。

因此，确定性线性 Q-learning 更新映射 $T_\alpha(\theta) = \theta + \alpha g(\theta)$（其中 $g$ 是投影贝尔曼残差）满足：
$$T_\alpha(\theta) - T_\alpha(\bar{\theta}) = A_{\mu_{\theta, \bar{\theta}}} (\theta - \bar{\theta})$$
其中 $A_\mu = I - \alpha \Phi^\top D \Phi + \alpha \gamma \Phi^\top D P \Pi_\mu \Phi$。

这通过将非线性递归转化为一个切换线性误差递归：
$$x_{k+1} = A_{\mu_k} x_k$$
其中 $x_k = \theta_k - \theta^*$ 是相对于投影贝尔曼不动点的误差，且切换信号 $\mu_k$ 由轨迹决定。

2.2 联合谱半径（JSR）作为稳定性证书

该切换系统的稳定性通过相关矩阵族的**联合谱半径（JSR）**进行分析。

• 令 $\mathcal{A}_\alpha$ 为对应于所有确定性策略的有限矩阵族。
• JSR（记作 $\rho(\mathcal{A}_\alpha)$）定义为该族矩阵乘积的精确最坏情况指数增长率。
• 作者证明了随机策略矩阵凸包的 JSR 等于确定性策略族族的 JSR（$\rho(\text{co}(\mathcal{A}_\alpha)) = \rho(\mathcal{A}_\alpha)$）。

条件 $\rho(\mathcal{A}_\alpha) < 1$ 作为稳定性的鲁棒充分证书。与单步范数界限不同，JSR 捕捉了任意切换序列下的最坏情况行为，从而提供了对系统稳定性更紧密且本质的表征。

2.3 李雅普诺夫构造

当 $\rho(\mathcal{A}_\alpha) < 1$ 时，本文直接从切换矩阵的乘积构造了一个分段二次李雅普诺夫函数（即范数 $p_\epsilon$）。该函数证明了映射 $T_\alpha$ 在 $p_\epsilon$-范数下是全局收缩的，从而确保了确定性递归存在唯一的固定点并实现指数收敛。

2.4 随机与正则化扩展

• 随机情况： 该框架被扩展到 i.i.d. 采样模型。随机递归被分解为确定性切换动力学加上一个鞅差噪声项。推导出了有限时间误差界限，表明误差收敛到不动点的邻域内，该邻域的大小取决于步长和噪声特性。
• 正则化情况： 分析被应用于 $\ell_2$-正则化 Q-learning。正则化通过 $-\alpha \eta I$ 偏移了切换矩阵。稳定性由该偏移后的族族的 JSR $\rho(\mathcal{A}_{\alpha, \eta})$ 决定。论文推导了关于正则化如何与步长及内在问题数据相互作用的界限。

3. 主要贡献与结果

3.1 有限时间误差分析

本文推导了线性 Q-learning 的显式有限时间误差界限。收敛速率与切换族的 JSR 挂钩。具体而言，如果 $\rho(\mathcal{A}_\alpha) < 1$，则误差以由 $\rho(\mathcal{A}_\alpha) + \epsilon$ 决定的速率呈指数衰减。界限包含了初始误差、步长和噪声底层的项。

3.2 迭代间的区别

本文严格证明了投影 Q 值迭代（PQVI）的收敛性并不意味着确定性线性 Q-learning 的收敛性，反之亦然。

• 示例 1 & 2： 作者提供了反例，在这些反例中，PQVI 发散而线性 Q-learning 收敛（以及反之亦然）。这强调了尽管两者共享相同的固定点，但它们的动态行为有着本质的区别。
• 示例 4： 展示了一个情况，其中切换族的 JSR 大于 1（意味着在任意切换下是不稳定的），然而实际的贝尔曼生成的非线性递归却全局收敛。这说明 JSR 条件是实际轨迹的一个保守的充分条件，因为实际轨迹并不会探索 JSR 定义下允许的所有切换序列。

3.3 正则化分析

本文提供了正则化 Q-learning 的统一视角。它表明正则化会偏移切换模式，从而导致一个新的 JSR 条件。

• 命题 4： 建立了一个将正则化 JSR 与重标度后的未正则化 JSR 联系起来的精确恒等式：$\rho(\mathcal{A}_{\alpha, \eta}) = |1 - \alpha \eta| \rho(\mathcal{B}_{\alpha/(1-\alpha \eta)})$。
• 洞察： 这揭示了在固定步长设置下，增加正则化参数 $\eta$ 并不一定会单调地改善稳定性。虽然它增加了“增量性”（稳定性裕度），但它同时也改变了有效步长的缩放，这可能会收紧稳定性约束。

3.4 李雅普诺夫证书

本文构造了一个公共分段二次李雅普诺夫函数（一种范数），用于证明非线性映射的收缩性。该证书比标准的单步范数界限更少保守，因为它考虑了切换动力学的乘积结构。

4. 意义与主张

本文声称通过切换系统的视角为线性 Q-learning 提供了一个统一框架。其主要意义在于：

1. 精确的最坏情况表征： 通过使用 JSR，分析捕捉了系统的精确最坏情况指数增长率，超越了保守的单步界限。
2. 正则化的统一视图： 它将正则化 Q-learning 连接到相同的切换系统理论中，展示了正则化如何修改切换族，并提供了明确的稳定性条件。
3. 澄清收敛机制： 它明确区分了线性 Q-learning 的动力学与投影贝尔曼迭代，解释了为什么尽管两者共享固定点，但可能表现出不同的收敛行为。
4. 鲁棒性： 基于 JSR 的条件是针对实际随机策略切换的鲁棒证书，因为它即使在任意切换（它是实际轨迹切换行为的超集）的情况下也能保证稳定性。

作者指出，为了清晰起见，其分析侧重于 i.i.d. 观测，尽管该切换分解可以扩展到马尔可夫噪声。这项工作并非提出新算法，而是为现有的线性 Q-learning 动力学及其稳定性属性提供了更深层的理论理解。