基于线性函数逼近的Q学习切换系统理论

# 具有线性函数近似的 Q-学习切换系统理论

来源: https://arxiv.org/html/2605.11021
Donghwan Lee 和 Han-Dong Lim
韩国科学技术院（KAIST）电气工程系
韩国大田 34141
[email protected]

###### 摘要

本文基于联合谱半径（JSR）开发了具有线性函数近似（LFA）的 Q-学习的切换系统解释。我们推导了均值动态的精确线性切换模型，并将收敛性与相应切换系统的稳定性联系起来。相同的构造随后用于独立同分布（i.i.d.）观测和马尔可夫观测下的随机线性 Q-学习。尽管精确计算 JSR 通常很困难，但该证书捕捉了切换模式的乘积，且可能比单步范数界限保守性更低。该框架还提供了正则化 Q-学习（带有 LFA）的基于 JSR 的观点。由此产生的分析在单一参数空间公式中联系了投影贝尔曼方程、有限差分随机策略切换和切换系统稳定性。

## 1 引言

Q-学习\[34\] 是折扣马尔可夫决策过程（MDPs）\[30,27,2\] 中强化学习的基础算法。在大规模状态-动作空间中，线性函数近似（LFA）通过低维参数表示动作价值函数。在使用 LFA 时，贝尔曼最优算子被投影到特征子空间上，且贪婪动作可能随参数变化而变化。由此产生的均值递归不是一个单一的线性系统；它是一种依赖于策略的线性切换动态。为了保持主要发展的重点，本文将所有新命题的证明推迟到附录中。

我们通过切换系统理论\[19,23\] 研究带有 LFA 的 Q-学习，称为线性 Q-学习。贝尔曼最优误差诱发了一个基于随机策略的切换系统，稳定性对象是相关切换矩阵族的联合谱半径（JSR）\[29,32,12\]。基本恒等式是贝尔曼最大值的随机策略线性化：两个价值最大向量之间的差异可以精确地表示为参数差的策略加权线性函数。

该表示为线性 Q-学习的确定性递归提供了一个切换线性模型。当相应的 JSR 小于 1 时，分段二次 Lyapunov 范数\[11\] 证明了均值线性 Q-学习映射的收缩性、投影贝尔曼不动点的唯一性以及指数收敛性。JSR 分析允许任意切换，而确定性线性 Q-学习仅实现其轨迹上生成的随机策略模式。因此，所提出的 JSR 条件是实际递归的鲁棒充分证书。

随后，所提出的 Lyapunov 证书被用于随机线性 Q-学习。在 i.i.d. 观测下，采样递归是切换均值动态加上鞅差噪声。在马尔可夫观测下，加入并减去平稳平均漂移，并将坐标采样差异视为有界误差。这在确定性、i.i.d. 和马尔可夫分析中保持了相同的 JSR 诱导范数。

我们还应用切换观点来处理带有 LFA 的正则化 Q-学习\[21\]。正则化平移每个直接切换模式，从而导致取决于正则化参数的正则化 JSR 和稳定性条件。该分析提供了一种统一的方法，通过由贝尔曼最优误差经由随机策略线性化诱导的切换矩阵族来比较未正则化和正则化线性 Q-学习。

## 2 相关工作

Q-学习的经典收敛分析依赖于随机逼近、ODE 方法、贝尔曼收缩性、单调性和有限时间误差估计\[33,31,13,3,9,1,28,18,7\]。这些结果构成了表式 Q-学习的标准基础。本文在线性 Q-学习上采取了不同的路线：它将线性 Q-学习视为一个切换系统，并通过矩阵族及其 JSR 研究诱导的切换动态。

线性 Q-学习的收敛理论也在表式设置之外得到了发展。早期关于 LFA 收敛的充分条件由\[25\] 给出。后续工作引入了收敛变体和平稳机制，包括双时间尺度变体\[4\]、目标网络\[35\]、带有截断的目标网络\[6\] 以及带有过参数化的目标网络\[5\]。非线性随机逼近的有限样本分析也已被用于研究具有马尔可夫噪声的强化学习算法\[8\]。最近关于投影贝尔曼方程和线性 Q-学习的研究在适当条件下建立了存在性、稳定性和有界集收敛结果\[26,24\]。这些结果通过随机逼近、算法修改、目标网络结构或投影方程分析来解决相关的稳定性问题。这里的方法是互补的：它提取确定性线性 Q-学习递归的切换矩阵族，并将其 JSR 用作稳定性证书。

线性近似和投影贝尔曼方程已在近似动态规划、投影值迭代、线性 Q-学习和正则化 Q-学习中得到研究\[22,21,10\]。这些工作阐明了投影结构、近似误差、算法差异以及正则化的作用。我们专注于由贝尔曼最大值诱导的有限差分随机策略切换结构，并以此在公共 Lyapunov 范数中推导确定性和随机界限。

切换系统理论研究动力学在多种模式之间变化的系统\[19,23\]。JSR 给出了由矩阵族生成的所有乘积的最坏情况指数增长率\[29,32,12\]。先前对 Q-学习的切换系统分析主要集中在表式算法、仿射切换模型、比较系统或 JSR Lyapunov 构造上\[14,15,16,20,17\]。本文开发了线性 Q-学习的相应切换和 JSR 理论，其中模式在特征参数空间中起作用。

随机分析与常数步长随机逼近有关。在 i.i.d. 采样下，递归分解为切换均值动态加上鞅噪声；在马尔可夫观测下，出现额外的坐标采样误差。本文没有用标量收缩论证替换动力学，而是保留 JSR Lyapunov 范数作为确定性、i.i.d.、马尔可夫和正则化线性 Q-学习的公共证书。

## 3 预备知识

### 3.1 符号

实数集记为 $\mathbb{R}$；$\mathbb{R}^m$ 是 $m$ 维欧几里得空间；$\mathbb{R}^{m \times r}$ 是所有 $m \times r$ 实矩阵的集合。对于矩阵 $A$，$A^\top$ 表示其转置。单位矩阵记为 $I$。对于向量，$e_i$ 是第 $i$ 个标准基向量，维度由上下文确定，$\otimes$ 表示克罗内克积。对于有限集 $\mathcal{S}$，$|\mathcal{S}|$ 表示其基数。我们将 $\mathbb{R}^m$ 中的概率单纯形写为 $\Delta_m := \{q \in \mathbb{R}^m : q_i \ge 0, \sum_{i=1}^m q_i = 1\}$。对于有限矩阵族 $\mathcal{H} = \{\mathbf{A}_1, \dots, \mathbf{A}_N\}$，其凸包记为 $\operatorname{co}(\mathcal{H}) := \{\sum_{i=1}^N \lambda_i \mathbf{A}_i : \lambda_i \ge 0, \sum_{i=1}^N \lambda_i = 1\}$。

### 3.2 切换系统

离散时间切换线性系统是一个动态系统，其状态在每个时间点根据从预定族中选择的一个矩阵演化\[19,23,12\]。对于矩阵族 $\mathcal{H} = \{\mathbf{A}_1, \dots, \mathbf{A}_M\} \subset \mathbb{R}^{m \times m}$，任意切换系统为

$$x_{k+1} = \mathbf{A}_{\sigma_k} x_k, \quad \sigma_k \in \{1, \dots, M\}, \quad k \in \{0, 1, \dots\}.$$

切换信号 $\{\sigma_k\}_{k \ge 0}$ 可以是确定性的、状态相关的或由外部过程生成。如果存在常数 $C \ge 1$ 和 $\eta \in (0, 1)$ 使得

$$\|\mathbf{A}_{\sigma_{k-1}} \cdots \mathbf{A}_{\sigma_0} x\|_2 \le C \eta^k \|x\|_2$$

对于每个视界 $k \ge 0$、每个初始状态 $x \in \mathbb{R}^n$ 和每个切换序列成立，则该系统在任意切换下是均匀指数稳定的。$\mathcal{H}$ 的公共 Lyapunov 函数是一个正定函数，它在族中的每种模式下都递减。在下面的分析中，线性 Q-学习中的贝尔曼最大值诱导有限差分随机策略切换，相关的 Lyapunov 函数直接由诱导模式矩阵的乘积构建。

### 3.3 联合谱半径

对于有界矩阵集 $\mathcal{H} \subset \mathbb{R}^{m \times m}$，其联合谱半径（JSR）\[29,32,12\] 为

$$\rho(\mathcal{H}) := \lim_{k \to \infty} \sup_{\mathbf{A}_1, \dots, \mathbf{A}_k \in \mathcal{H}} \|\mathbf{A}_k \cdots \mathbf{A}_1\|^{1/k},$$

其中该值独立于所选的子乘性范数。当 $\mathcal{H}$ 有限时，每个固定乘积长度的上确界是 $\mathcal{H}$ 中矩阵生成的乘积上的最大值。JSR 是由 $\mathcal{H}$ 生成的切换乘积的确切最坏情况指数增长率。在本文中，JSR 小于 1 用于为任意切换稳定性和贝尔曼生成的非线性递归的收缩性构建公共分段二次 Lyapunov 证书。

以下分段二次 Lyapunov 构造是\[17,11\] 中引入的有限族公共 Lyapunov 引理。此处陈述它，因为它是确定性、随机和正则化分析中使用的 Lyapunov 证书。

###### 引理 1（公共 Lyapunov 构造\[17, Lemma 4\]）

设

$$\mathcal{H} = \{\mathbf{A}_1, \mathbf{A}_2, \dots, \mathbf{A}_M\} \subset \mathbb{R}^{m \times m}, \quad \rho := \rho(\mathcal{H}),$$

并固定 $\varepsilon > 0$ 使得 $\beta_\varepsilon := \rho + \varepsilon \in (0, 1)$。对于模式序列 $\sigma = (\sigma_1, \dots, \sigma_k) \in \{1, \dots, M\}^k$，记

$$\mathbf{A}_\sigma := \mathbf{A}_{\sigma_k} \cdots \mathbf{A}_{\sigma_1},$$

约定对于 $k=0$，空字给出 $\mathbf{A}_\sigma = I$。对于每个整数 $t \ge 0$，定义

$$V_\varepsilon^t(x) := \sum_{k=0}^t \beta_\varepsilon^{-2k} \max_{\sigma \in \{1, \dots, M\}^k} \|\mathbf{A}_\sigma x\|_2^2, \quad x \in \mathbb{R}^m.$$

则以下陈述成立。

1. (i) 对于每个 $t \ge 0$，$V_\varepsilon^{t+1}(x) \ge \|x\|_2^2 + \beta_\varepsilon^{-2} \max_{i \in \{1, \dots, M\}} V_\varepsilon^t(\mathbf{A}_i x), \quad \forall x \in \mathbb{R}^m$。
2. (ii) 对于每个 $t \ge 0$，函数 $V_\varepsilon^t$ 是二阶绝对齐次的，并且关于 $t$ 单调：$V_\varepsilon^t(\lambda x) = \|\lambda\|^2 V_\varepsilon^t(x), \quad V_\varepsilon^t(x) \le V_\varepsilon^{t+1}(x)$。
3. (iii) 存在 $C_\varepsilon > 0$ 使得 $\|x\|_2^2 \le V_\varepsilon^t(x) \le C_\varepsilon \|x\|_2^2, \quad \forall x \in \mathbb{R}^m, \quad \forall t \ge 0$。
4. (iv) 逐点极限 $V_\varepsilon^\infty(x) := \lim_{t \to \infty} V_\varepsilon^t(x)$ 存在且满足 $\|x\|_2^2 \le V_\varepsilon^\infty(x) \le C_\varepsilon \|x\|_2^2, \quad \forall x \in \mathbb{R}^m$。
5. (v) 函数 $p_\varepsilon(x) := \sqrt{V_\varepsilon^\infty(x)}$ 是 $\mathbb{R}^m$ 上的范数。
6. (vi) 对于每个 $i \in \{1, \dots, M\}$，$V_\varepsilon^\infty(\mathbf{A}_i x) \le \beta_\varepsilon^2 (V_\varepsilon^\infty(x) - \|x\|_2^2) \le \beta_\varepsilon^2 V_\varepsilon^\infty(x), \quad \forall x \in \mathbb{R}^m$。等价地，$p_\varepsilon(\mathbf{A}_i x) \le \beta_\varepsilon p_\varepsilon(x)$。