Q学习的符号分离有限时间误差分析

# 符号分离的 Q-learning 有限时间误差分析  
来源：https://arxiv.org/html/2605.16103  
作者：Donghwan Lee  
所属机构：韩国科学技术院 (KAIST) 电气工程系  
Email：donghwan@kaist\.ac\.kr  

###### 摘要  
本文针对常步长 Q-learning 提出了一种符号分离的有限时间误差分析方法。从切换系统表示出发，将误差分解为其分量上的负部和正部。负部由一个与固定最优策略相关的下界比较线性时不变 (LTI) 系统控制，而正部则由一个线性切换系统控制。得到的界表明，负侧 LTI 认证速度不会慢于正侧切换认证速度，并可能产生更快的指数包络。该分析揭示了 Q-learning 误差动态中由最大值算子引发的非对称性。这种非对称性与过估计有关：正的动作方向误差可能因 Bellman 最大值而被选中并传播，而负误差则享有最优策略下界比较。本文为确定性及随机常步长递归都提供了有限时间界。  

## 1 引言  
Q-learning [30 (https://arxiv.org/html/2605.16103#bib.bib22)] 是强化学习 (RL) [23 (https://arxiv.org/html/2605.16103#bib.bib2)] 中用于解决转移核未知的马尔可夫决策过程 (MDP) 的基础算法。几十年来，其收敛性已得到广泛研究。经典分析主要建立渐近收敛性 [27 (https://arxiv.org/html/2605.16103#bib.bib24), 7 (https://arxiv.org/html/2605.16103#bib.bib25), 4 (https://arxiv.org/html/2605.16103#bib.bib26), 11 (https://arxiv.org/html/2605.16103#bib.bib37)]。这些结果具有基础性，但仅凭渐近收敛性无法量化迭代向解逼近的有限时间进程。这一局限促使了有限时间收敛性分析的发展，这类分析提供了迭代向最优 Q 函数逼近的显式界。有限时间分析的最新进展包括 [24 (https://arxiv.org/html/2605.16103#bib.bib29), 9 (https://arxiv.org/html/2605.16103#bib.bib27), 6 (https://arxiv.org/html/2605.16103#bib.bib28), 1 (https://arxiv.org/html/2605.16103#bib.bib30), 29 (https://arxiv.org/html/2605.16103#bib.bib31), 20 (https://arxiv.org/html/2605.16103#bib.bib32), 15 (https://arxiv.org/html/2605.16103#bib.bib33), 5 (https://arxiv.org/html/2605.16103#bib.bib34)]。大多数现有结果将 Q-learning 视为一种非线性随机逼近方案 [10 (https://arxiv.org/html/2605.16103#bib.bib8)]，并依赖于 Bellman 最优性算子的压缩性质。另一种观点将 Q-learning 视为一个离散时间随机切换系统 [18 (https://arxiv.org/html/2605.16103#bib.bib11), 16 (https://arxiv.org/html/2605.16103#bib.bib13)]。这一视角在 [11 (https://arxiv.org/html/2605.16103#bib.bib37), 12 (https://arxiv.org/html/2605.16103#bib.bib38), 13 (https://arxiv.org/html/2605.16103#bib.bib39), 17 (https://arxiv.org/html/2605.16103#bib.bib41)] 中提出，并用于证明常步长 Q-learning 的有限时间界。在这种形式中，误差动态是仿射而非线性的，因为当前迭代所选择的贪心策略可能不同于最优策略。仿射项通过上、下比较系统进行控制。上比较系统仍为切换系统，而下比较系统可限制为最优策略模式。尽管这种比较系统方法给出了有效的有限时间界，但它通过辅助系统控制 Q-learning 误差，而非直接利用原始误差递归的切换结构。因此，像联合谱半径 (JSR) [26 (https://arxiv.org/html/2605.16103#bib.bib18), 21 (https://arxiv.org/html/2605.16103#bib.bib17), 3 (https://arxiv.org/html/2605.16103#bib.bib19), 8 (https://arxiv.org/html/2605.16103#bib.bib16)] 这样的内在切换系统量难以直接应用于原始 Q-learning 动态。精确的切换系统表示消除了这一障碍，它将 Bellman 最大化误差精确表示为在合适选择的随机策略下动作方向 Q 误差的平均值 [14 (https://arxiv.org/html/2605.16103#bib.bib52)]。相应的确定性收敛率可由所得直接切换族的 JSR 刻画。由于 JSR 是切换线性族的最坏情况指数率，直接切换观点为理解 Q-learning 瞬态行为提供了精密的基于漂移的框架。本文在 [14 (https://arxiv.org/html/2605.16103#bib.bib52)] 的基础上，通过将 Q-learning 误差分解为分量上的负部和正部来精炼该观点。符号分离揭示了由 Bellman 最大值算子引发的非对称性。这种非对称性与基于值的 RL 中的过估计机制密切相关 [25 (https://arxiv.org/html/2605.16103#bib.bib55), 28 (https://arxiv.org/html/2605.16103#bib.bib56)]：最大值算子可以选择带有正估计误差的动作，而负误差则可以与最优策略下界系统进行比较。负侧与一个与最优策略相关的固定 LTI 系统比较，得到一个速率为 $\rho_{-}^{\star}$ 的认证。正侧由一组确定性策略上的线性切换系统控制，因为带有较大正误差的次优动作可能通过最大化算子进入。其认证速率为 $\rho_{+} = \rho_{\alpha}^{\mathrm{dir}}$。由于 $\rho_{-}^{\star} \leq \rho_{+}$ 且该不等式可以严格成立，有限时间界提供了一种认证层面的意义，即负误差可能比正误差衰减更快。得到的包络如图 1 所示。  

k k  
Error 0  
$e_k^+$  
$-e_k^-$  
图 1：符号分离包络示意图。正分量由全切换族速率认证，而负分量由优化的固定模式 LTI 速率认证。  

我们首先针对确定性的条件均值递归开发符号分离比较系统，其中最大值导致的残差以及下、上比较机制最为清晰。然后我们将相同的符号分离结构扩展到独立同分布观测模型下的常步长随机 Q-learning。有限时间速率认证使用两种 Lyapunov 构造：针对负侧 LTI 比较系统的固定模式 Lyapunov 函数，以及针对正侧直接切换族的基于乘积的 JSR Lyapunov 函数。目的是提供一个从切换系统角度看待 Q-learning 收敛行为的框架。该框架并非要取代基于 Bellman 压缩或随机逼近的分析，也不声称在所有问题实例上都有统一的样本复杂度改进。相反，符号分离的直接切换观点通过识别切换漂移并展示最优负侧速率何时比正侧直接切换速率更锐利，来补充现有分析。本文专注于 i.i.d. 观测模型。可以使用 [14 (https://arxiv.org/html/2605.16103#bib.bib52)] 中的方法将分析扩展到马尔可夫观测，但 i.i.d. 设置使得符号分离的切换系统论证更为清晰。  

## 2 预备知识  

### 2.1 符号说明  
我们使用以下符号。$\mathbb{R}$、$\mathbb{R}^n$ 和 $\mathbb{R}^{n \times m}$ 分别表示实数集、$n$ 维欧氏空间和 $n \times m$ 实矩阵集。对于矩阵 $A$，$A^\top$ 表示其转置。$I$ 表示具有适当维数的单位矩阵。对于有限集 $\mathcal{S}$，其基数用 $|\mathcal{S}|$ 表示。$A$ 与 $B$ 的 Kronecker 积记为 $A \otimes B$。对于方阵 $A$，$\rho(A)$ 表示其谱半径。对于集合 $\mathcal{Y} \subset \mathbb{R}^n$ 和向量 $x \in \mathbb{R}^n$，$\operatorname{dist}_{\infty}(x, \mathcal{Y})$ 表示从 $x$ 到 $\mathcal{Y}$ 的无穷范数距离：$\operatorname{dist}_{\infty}(x, \mathcal{Y}) := \inf_{y \in \mathcal{Y}} \|x - y\|_{\infty}$。我们用 $\Delta_{|\mathcal{A}|}$ 表示有限动作集 $\mathcal{A}$ 上的概率单纯形：$\Delta_{|\mathcal{A}|} := \{ p \in \mathbb{R}^{|\mathcal{A}|} : p_i \geq 0, \sum_{i=1}^{|\mathcal{A}|} p_i = 1 \}$。在整个论文中，除非另有说明，所有向量不等式都理解为分量上的。对于标量 $x$，定义 $x^+ := \max\{x, 0\}$, $x^- := \max\{-x, 0\}$。因此，$x^+$ 是 $x$ 的正部，$x^-$ 是 $x$ 的负部的幅度。对于向量 $x$，$x^+$ 和 $x^-$ 按分量定义，因此  
$$ x = x^+ - x^-, \quad |x| = x^+ + x^-, \quad x^+ \geq 0, \quad x^- \geq 0. $$  
对于有限矩阵族 $\mathcal{H} = \{ A_1, \ldots, A_N \}$，记 $\operatorname{co}(\mathcal{H})$ 为其凸包：$\operatorname{co}(\mathcal{H}) := \{ \sum_{i=1}^N \lambda_i A_i : \lambda_i \geq 0, \sum_{i=1}^N \lambda_i = 1 \}$。  

### 2.2 切换系统  
考虑离散时间切换线性系统 [16 (https://arxiv.org/html/2605.16103#bib.bib13), 18 (https://arxiv.org/html/2605.16103#bib.bib11), 22 (https://arxiv.org/html/2605.16103#bib.bib12)]  
$$ z_{k+1} = A_{\sigma_k} z_k + \xi_k, \quad k \in \{0,1,2,\ldots\}, $$  
其中每个索引 $i \in \{1,2,\ldots,M\}$ 称为一个模式，对应一个矩阵 $A_i$。序列 $\sigma_k \in \{1,2,\ldots,M\}$ 是切换信号，指定时刻 $k$ 激活哪个模式。等价地，说模式 $\sigma_k = i$ 激活意味着从 $z_k$ 到 $z_{k+1}$ 的更新使用动态矩阵 $A_i$。所有可能的模式矩阵组成的给定集合 $\mathcal{H} := \{A_1, A_2, \ldots, A_M\}$ 称为切换族，而 $\xi_k$ 是加性干扰。在本文中，一个模式表示当前应用的动态矩阵；在下面的 Q-learning 应用中，模式由策略选择器诱导。当 $\xi_k = 0$ 时，确定性部分简化为  
$$ z_{k+1} = A_{\sigma_k} z_k, \quad k \in \{0,1,2,\ldots\}. $$  
如果切换族只有一个元素，比如 $\mathcal{H} = \{H\}$，那么就没有真正的模式变化，切换系统退化为通常的线性时不变 (LTI) 递归 $z_{k+1} = H z_k + \xi_k$，或者在无干扰情况下 $z_{k+1} = H z_k$。因此，LTI 系统作为单元素族的特例包含在切换系统中。切换线性族的最坏情况指数率由联合谱半径 (JSR) [26 (https://arxiv.org/html/2605.16103#bib.bib18), 21 (https://arxiv.org/html/2605.16103#bib.bib17), 3 (https://arxiv.org/html/2605.16103#bib.bib19), 8 (https://arxiv.org/html/2605.16103#bib.bib16)] 刻画，定义如下。  

###### 定义 1. 对于有界矩阵集 $\mathcal{H} \subset \mathbb{R}^{m \times m}$，其 JSR 定义为  
$$ \rho(\mathcal{H}) := \lim_{k \to \infty} \sup_{A_1, \ldots, A_k \in \mathcal{H}} \| A_k \cdots A_1 \|^{1/k}, $$  
其中该值与所选的次乘性范数无关。当 $\mathcal{H}$ 有限时，每个固定乘积长度上的上确界是 $\mathcal{H}$ 中矩阵生成的所有乘积的最大值。如果 $\mathcal{H} = \{H\}$ 只包含一个矩阵，那么该定义退化为通常的谱半径：  
$$ \rho(\{H\}) = \lim_{k \to \infty} \| H^k \|^{1/k} = \rho(H). $$  

### 2.3 马尔可夫决策过程  
我们考虑一个无限时域折扣马尔可夫决策过程 (MDP) [19 (https://arxiv.org/html/2605.16103#bib.bib1)]，其中智能体依次选择动作以最大化累积折扣奖励。状态空间和动作空间是有限的，分别记为 $\mathcal{S} := \{1,2,\ldots,|\mathcal{S}|\}$ 和 $\mathcal{A} := \{1,2,\ldots,|\mathcal{A}|\}$。在状态 $s \in \mathcal{S}$ 时，决策者选择动作 $a \in \mathcal{A}$。下一个状态 $s'$ 根据 $P(s'|s,a)$ 抽取，转移产生奖励 $r(s,a,s')$，其中 $r: \mathcal{S} \times \mathcal{A} \times \mathcal{S} \to \mathbb{R}$。记 $r(s_k, a_k, s_{k+1}) =: r_{k+1}$ 对于 $k \geq 0$。期望单步奖励为  
$$ R(s,a) := \mathbb{E}[r_{k+1} \mid s_k = s, a_k = a] = \sum_{s' \in \mathcal{S}} P(s'|s,a) r(s,a,s'). $$  
一个确定性策略 $\pi: \mathcal{S} \to \mathcal{A}$ 将每个状态 $s$ 映射到一个动作 $\pi(s)$。在整个论文中，折扣因子 $\gamma \in (0,1)$。令 $\Theta$ 表示所有可容许确定性策略的集合。对于策略 $\pi$，其 Q 函数定义为  
$$ Q^\pi(s,a) = \mathbb{E} \left[ \left. \sum_{k=0}^\infty \gamma^k r_{k+1} \right| s_0 = s, a_0 = a, \pi \right], $$  
对所有 $s \in \mathcal{S}$ 和 $a \in \mathcal{A}$。相应的价值函数为 $V^\pi(s) := Q^\pi(s, \pi(s))$。最优 Q 函数为  
$$ Q^*(s,a) := \sup_{\pi \in \Theta} Q^\pi(s,a), \quad s \in \mathcal{S}, a \in \mathcal{A}. $$  
一个确定性策略 $\pi^*$ 是最优的，如果对所有的 $(s,a) \in \mathcal{S} \times \mathcal{A}$ 都有 $Q^{\pi^*}(s,a) = Q^*(s,a)$。一旦 $Q^*$ 已知，就可以恢复出一个最优的平局打破贪心策略：$\pi^*(s) = \arg\max_{a \in \mathcal{A}} Q^*(s,a)$。相应的最优价值函数为 $V^*(s) := \max_{a \in \mathcal{A}} Q^*(s,a)$。  

对于每个状态 $s \in \mathcal{S}$，定义最优贪心动作集为 $\Phi^*(s) := \operatorname{Arg}\max_{a \in \mathcal{A}} Q^*(s,a)$。所有最优确定性策略的集合为  
$$ \Theta^* := \{ \pi \in \Theta : \pi(s) \in \Phi^*(s), \; \forall s \in \mathcal{S} \}. $$  
上述定义在有限折扣 MDP 中等价于通常的最优确定性策略集。