arXiv 2607.08340v1 · 发布 2026-07-09

决斗Q学习的谱分析

Spectral Analysis of Dueling Q-Learning

AUTHORS Donghwan Lee

EVIDENCE 对决Q-learning算法的理论谱分析

SCORE 0.8

CATEGORIES TASK rl

PDF ↗ 2607.08340v1.pdf

GENERATED 2026-07-11 21:34:52 UTC

📝 TLDR

Q-learning是强化学习中求解折扣MDP的基础算法，Dueling Q-learning通过将Q函数分解为价值函数和优势函数联合学习以提升效率。然而其理论分析仍不充分，已有表格型分析仅针对正则化版本。本文针对未正则化、无投影的常数步长递归，推导出确定性版本的精确切换线性系统表示，并给出随机采样版本的有限时间期望误差界。研究阐明了价值与优势更新如何作为不同增益作用于动作公共成分和动作差分成分。

🧭 速览

动机

现有Dueling Q-learning的理论分析集中于正则化版本，对纯表格型更新理解不足，缺乏收敛保证。

方法

针对未正则化、无投影的常数步长表格型递归，建立确定性版本的切换线性系统精确表示，并分析随机采样版本。

结果

得到确定性情形的精确表示以及随机情形的有限时间期望误差界，揭示价值与优势更新对Q函数不同成分的差异化增益作用。

结论

弥补Dueling Q-learning在未正则化设定下理论分析的空白，加深对值-优势分解机制的理解。

📊 论文图表(共 6 张)

展开查看 6 张图

TL;DR

本文为未正则化、未投影的决斗 Q-learning 建立了严格的理论收敛保证。通过将 Q 函数正交分解为动作公共分量（价值函数）和动作差分分量（优势函数），推导出确定性版本的精确切换线性系统表示，并利用 JSR-Lyapunov 框架证明有限时间期望误差界，最终揭示价值更新与优势更新如何作为不同增益分别作用于 Q 函数的两个正交子空间。

研究背景与动机

在强化学习中，求解折扣马尔可夫决策过程（MDP）的核心目标是找到最优策略以最大化累积折扣回报。Q-learning 作为当转移核未知时求解该问题的基础算法，自 Watkins 提出以来便成为这一领域的基石。随着深度学习的兴起，深度 Q 网络（DQN）通过深度神经网络逼近 Q 函数，使得 Q-learning 能够处理高维状态空间中的实际问题。

然而，标准 Q-learning 在学习过程中直接估计每个状态-动作对的价值。当动作空间较大时，这种做法效率较低，因为许多状态下的最优动作可能是显而易见的——真正重要的是区分最优动作与次优动作之间的相对优势。正是基于这一观察，Wang 等人提出了决斗 Q-learning（Dueling Q-learning），其核心思想是将 Q 函数显式分解为价值函数和优势函数的和：

Q (s, a) = V (s) + A (s, a)

其中价值函数 $V (s)$ 表示状态 $s$ 的总体价值，而优势函数 $A (s, a)$ 捕捉选择动作 $a$ 相对于平均水平的额外收益。这种分解使得网络可以分别学习状态的内在价值和动作的相对优势，从而提高学习效率。直觉上，当某个状态下所有动作的价值都很高时，网络应该主要更新价值流；而当动作之间存在明显差异时，优势流则承担更多的更新任务。

尽管决斗 Q-learning 在实践中表现出色且被广泛应用于 AlphaGo 等系统中，其理论理解却长期滞后。直到最近，Daley 等人才开始对表格型决斗 Q-learning 进行系统分析，但他们关注的是正则化版本——即在更新规则中加入了投影或正则化项以保证收敛。对于纯表格更新、无正则化、无投影、常数步长的原始形式，算法的收敛性分析仍是空白。这一空白不仅阻碍了我们对决斗网络架构深层工作机制的理解，也使得实践者在调整学习率等超参数时缺乏理论指导。

本文正是要填补这一空白。研究的核心问题是：未正则化的决斗 Q-learning 在常数步长下是否收敛？如果收敛，其收敛速率由什么因素决定？价值更新和优势更新在算法中扮演着怎样不同的角色？

方法

本文的理论分析建立在两个关键思想上：状态-动作空间上的正交投影分解和切换线性系统（Switching Linear System）表示。

首先引入状态-动作均值投影算子。对于具有 $∣ S ∣$ 个状态和 $∣ A ∣$ 个动作的 MDP，Q 函数可以视为矩阵 $Q \in R^{∣ S ∣ \times ∣ A ∣}$ 。定义正交投影算子

Π = (\frac{1}{∣ A ∣} 1_{∣ A ∣} 1_{∣ A ∣}^{⊤}) \otimes I_{∣ S ∣}

其中 $1_{∣ A ∣}$ 是全 1 向量， $\otimes$ 表示 Kronecker 积。这个投影算子将 Q 矩阵的每一行（即每个状态的动作维度）投影到该行的均值方向。相应地， $Π^{⊥} = I - Π$ 投影到与均值正交的方向。

基于这一投影，任意 Q 矩阵可以唯一分解为：

Q = V Π Q + A Π^{⊥} Q

其中 $V$ 是动作公共分量：对于同一状态， $V (s, a)$ 在所有动作上取值相同，恰好是价值函数的向量化形式； $A$ 是动作差分分量：其每行元素和为零，表示各动作相对于均值的优势偏差。这种正交分解具有明确的物理意义——价值流捕捉所有动作的共同信息，优势流则专注于区分不同动作。

接下来考虑算法的更新规则。标准 Q-learning 的更新式为：

Q_{k + 1} = Q_{k} + α \cdot D \cdot (F (Q_{k}) - Q_{k})

其中 $α$ 是学习率， $D$ 是依赖采样分布的对角矩阵， $F$ 是 Bellman 最优算子。决斗 Q-learning 的关键创新在于将更新增益 $C$ 分解为：

C_{V A} = ∣ A ∣ α Π + β Π^{⊥}

其中 $α$ 和 $β$ 分别是价值流和优势流的学习率。当 $∣ A ∣ α = β$ 时， $C_{V A} = η I$ 退化为标准 Q-learning；而当 $α \neq = β$ 时，两个子空间受到不同强度的更新刺激。

这一分解的理论价值在于：切换线性系统表示。利用 Bellman 算子的 Lipschitz 性质，可以将确定性更新在最优 Q 邻域内线性化为：

Q_{k + 1} - Q^{*} = A_{σ} (Q_{k} - Q^{*})

其中 $A_{σ}$ 属于某个切换族 $A_{V A} (α, β)$ ，具体形式为：

A_{V A}^{π} = I - C_{V A} D (I - γ P Γ_{π})

这里 $P$ 是转移矩阵， $Γ_{π}$ 是策略相关的对角矩阵， $π$ 的选择由 $Q_{k}$ 通过贪婪规则确定。这个表示将原本非线性的迭代过程转化为一族线性系统的切换。

为了分析切换线性系统的稳定性，本文引入 JSR（联合谱半径） 概念。JSR 是切换系统稳定性的判据：切换族稳定当且仅当其 JSR 小于 1。与传统谱半径不同，JSR 考虑所有可能的切换序列，因此更能反映真实学习过程中的不确定性。

论文的关键技术贡献是 JSR-Lyapunov 函数的构造。通过精心设计的 Lyapunov 函数：

V_{ε}^{\infty} (x) = k \geq 0 \sum β_{ε}^{- 2 k} σ max ∥ A_{σ} x ∥_{2}^{2}

可以证明，当步长满足一定条件时，切换族的 JSR 小于 1，从而保证确定性算法的全局收敛。步长约束的物理意义是：更新增益矩阵 $C_{V A} D$ 在 $ℓ_{\infty}$ 范数下不超过单位阵，以确保 Bellman 残差不会被放大。

对于采样随机版本，分析更加复杂，因为每次更新涉及随机 TD 误差。论文通过将随机扰动上界分解为采样方差项，并利用 JSR-Lyapunov 函数的期望性质，推导出有限时间误差界。该界包含三项：指数收敛项、过渡耦合项，以及与采样方差成正比的 $O (α)$ 误差邻域项。

实验与结果

论文设计了三个递进式的实验来验证理论预测。

第一个实验针对最简单的设定：单状态、两动作的确定性 MDP，存在自环转移。这个看似平凡的设定却揭示了核心现象——两个分量以不同速率收敛。在参数 $α = β$ 时，退化为标准 Q-learning，两个分量同步收敛；而当调整 $α < β$ 时，价值流（公共分量）收敛更快，优势流（差分分量）则存在轻微振荡后逐渐收敛。实验曲线与切换线性系统的理论预测高度吻合，验证了正交分解下子空间独立分析的有效性。

第二个实验扩展到两状态、两动作的非平凡 MDP，引入随机转移核和差异化的奖励结构。采样随机版本的实验结果明确验证了有限时间误差界的三项结构：初始阶段的指数衰减、过渡期的 $k (1 - c α /2)^{k - 1}$ 项，以及最终稳定在 $O (α)$ 误差邻域。值得注意的是，通过改变采样分布偏向某一动作，实验观察到不同子空间上的收敛差异，进一步证实了 $C_{V A}$ 中 $Π$ 、 $Π^{⊥}$ 权重对实际学习动态的影响。

第三个实验使用经典的链式 MDP 验证多状态情形。链式结构使得状态空间可扩展，便于观察有限时间误差随状态数增加的变化趋势。实验表明，未正则化版本相比正则化版本表现出更大的稳态方差，这与理论分析一致——正则化项相当于引入了额外的收缩偏置，缩小了 $O (α)$ 误差邻域。

综合三个实验，理论与实验的定量吻合表明：切换线性系统表示和 JSR-Lyapunov 分析框架能够准确捕捉决斗 Q-learning 的收敛动力学。

讨论与可借鉴点

本文的理论分析揭示了几个值得深思的洞见。

正交分解的几何直觉。通过 $Π$ 和 $Π^{⊥}$ 将 Q 函数分解为公共分量和差分分量，本质上是在状态-动作空间引入了两个正交的子空间。价值流学习所有动作共享的信息，优势流专注于区分动作。这一分解不仅是算法设计的便利，更是理解强化学习中价值估计和优势估计关系的几何框架。可以类比为：价值函数回答"这个状态有多好"，优势函数回答"这个动作比其他动作好多少"。

步长选择的理论指导。Lemma 5.9 给出的步长约束具有清晰的几何意义： $C_{V A} D$ 的每一列在 $ℓ_{\infty}$ 范数下不超过 1。虽然这一条件是保守的充分条件，但它为实践者提供了调参的基准线。特别地，当 $∣ A ∣ α = β$ 时条件退化为标准 Q-learning 的约束，而选择 $α < β$ 可以加速优势流的学习——这为实践中调整两个学习率提供了理论依据。

常数步长 vs 衰减步长。有限时间误差界中的 $O (α)$ 项是常数步长算法的固有代价。衰减步长可以消除这一项，但代价是收敛变慢且需要预知时间 horizon。这一权衡在在线学习场景中尤为关键——常数步长适合持续学习环境，而任务导向的学习可能更适合衰减步长。

JSR 框架的模块化价值。本文通过算子重写证明决斗 Q-learning 的 JSR 等价于标准 Q-learning 的 JSR，这意味着大量已有的 Q-learning 分析工具可以被复用。这种模块化思路对其他算法变体的理论分析具有借鉴意义——如果新算法可以转化为某种切换系统的形式，就可以借助 JSR 理论框架进行分析。

局限性。当前分析限于表格型 MDP，未涉及函数逼近。决斗网络的神经网络部分、线性函数逼近情形下的收敛性仍是开放问题。此外，步长约束的紧致性值得进一步探索——实际中可允许更大的步长，但理论保证尚不完备。异步/分布式版本的谱分析也是未来方向。

这项工作的核心贡献在于为决斗 Q-learning 提供了首个针对未正则化、常数步长、表格型设定的严格收敛证明，并将价值流与优势流的差异化作用机制纳入统一的正交谱分析框架。

摘要

当转移核未知时，Q学习是强化学习（RL）中用于求解折扣马尔可夫决策过程（MDP）的基本算法。深度Q网络（DQN）通过使用深度神经网络进行Q函数逼近来扩展Q学习，这使得Q学习能够应用于更实际的高维问题。决斗Q学习将Q函数分解为价值函数和优势函数，并联合学习这两个分量，从而可以提高学习效率。然而，对决斗Q学习的理论理解仍然有限。最近的研究工作已经开始对表格型决斗Q学习进行分析，但现有的理论保证主要集中在正则化形式上，对纯表格更新的理解仍不够完整。本文通过为居中表格分解增加直接解释，并为未正则化、未投影的常数步长递归建立收敛保证，从而加强了这一分析路线。具体而言，我们为确定性决斗Q学习推导出了一个精确的切换线性系统表示，并为采样随机版本推导出了一个期望下的有限时间误差界。该分析阐明了价值更新和优势更新如何分别作为Q函数中动作公共分量（价值函数）和动作差异分量（优势函数）的不同增益发挥作用。

Abstract

Q-learning is a fundamental algorithm in reinforcement learning (RL) for solving discounted Markov decision processes (MDPs) when the transition kernel is unknown. The deep Q-network (DQN) extends Q-learning by using a deep neural network for Q-function approximation, which makes Q-learning applicable to more practical high-dimensional problems. Dueling Q-learning decomposes the Q-function into a value function and an advantage function and learns the two components jointly, which can improve learning efficiency. However, the theoretical understanding of dueling Q-learning is still limited. Recent work has initiated an analysis of tabular dueling Q-learning, but existing guarantees focus on a regularized formulation and leave the pure tabular update less completely understood. This paper strengthens that line of analysis by adding a direct interpretation of the centered tabular decomposition and by establishing convergence guarantees for the unregularized, unprojected constant step-size recursion. In particular, we derive an exact switching linear system representation for deterministic dueling Q-learning and a finite-time error bound in expectation for the sampled stochastic version. The analysis clarifies how the value and advantage updates act as different gains on the action-common (value function) and action-differential (advantage function) components of the Q-function.

论文详细总结（自动生成）

决斗Q学习的谱分析 —— 论文总结

1. 核心问题与研究动机

背景：Q-learning 是强化学习求解折扣 MDP 的基础算法；DQN 通过深度网络扩展至高维问题；dueling Q-learning 将 Q 函数分解为价值流与优势流，经验上可提升学习效率。
现状不足：现有理论分析（以 Daley 等人近期工作为代表）主要聚焦正则化（regularized）dueling Q-learning 形式，对纯表格型、未正则化、无投影的常数步长递归的收敛性理解仍不完整。
本文目标：填补这一理论空白，为未正则化 dueling Q-learning 提供收敛保证，并从正交分解视角解释价值/优势分量在不同子空间上的差异化作用机制。

2. 方法论

2.1 核心思想：正交公共/差分分解

对任意 Q 引入状态-动作均值投影算子

Π = (\frac{1}{∣ A ∣} 1_{∣ A ∣} 1_{∣ A ∣}^{⊤}) \otimes I_{∣ S ∣} \in R^{n \times n}

$Π$ 是正交投影（ $Π^{2} = Π$ ， $Π^{⊤} = Π$ ）， $Π^{⊥} = I - Π$ 。
Q 的唯一分解： $Q = Π Q + Π^{⊥} Q =: V + A$ ，其中 $V$ 为动作公共分量（state-wise constant across actions）， $A$ 为动作差分分量（ $\sum_{b \in A} A (s, b) = 0$ ）。

2.2 关键算法

确定性 AV 更新（Algorithm 1）：

V_{k + 1} = V_{k} + ∣ A ∣ α Π D (F (Q_{k}) - Q_{k})

A_{k + 1} = A_{k} + β Π^{⊥} D (F (Q_{k}) - Q_{k})

确定性 Q-only 更新（Algorithm 2，等价于 Algorithm 1）：

Q_{k + 1} = Q_{k} + C_{V A} D (F (Q_{k}) - Q_{k}), C_{V A} = ∣ A ∣ α Π + β Π^{⊥}

采样随机版本（Algorithm 3 / 4）：基于 i.i.d. 采样 $(s_{k}, a_{k}) \sim d$ ，TD 误差

δ_{k} = r_{k + 1} + γ c \in A max Q_{k} (s_{k}^{'}, c) - Q_{k} (s_{k}, a_{k})

当 $∣ A ∣ α = β = η$ 时， $C_{V A} = η I$ ，退化为标准 Q-learning。

2.3 关键技术细节

SLS 表示：利用 Lemma 3.4 将 Bellman 差分线性化为 $F (Q_{k}) - F (Q^{*}) = γ P Γ_{μ_{k}} (Q_{k} - Q^{*})$ ，得到切换族

A_{V A} (α, β) = {A_{V A}^{π} = I - C_{V A} D (I - γ P Γ_{π})}

JSR-Lyapunov 分析：构造 JSR Lyapunov 函数 $V_{ε}^{\infty} (x) = \sum_{k \geq 0} β_{ε}^{- 2 k} max_{σ} ∥ A_{σ} x ∥_{2}^{2}$ ，对应范数 $p_{ε}$ 。
JSR 等价性（Lemma 5.8）：通过 $T x = [Π x; Π^{⊥} x]$ 证明

ρ (B_{V A} (α, β)) = ρ (A_{V A} (α, β))

保守步长条件（Lemma 5.9， $ℓ_{\infty}$ 收缩）：

0 < β \leq \frac{1}{d _{m a x}}, \frac{β}{∣ A ∣} \frac{1 - d _{m i n} ( 1 - γ )}{d _{m a x} ( 1 + γ )} < α < \frac{β}{∣ A ∣} \frac{1 + d _{m i n} ( 1 - γ )}{d _{m a x} ( 1 + γ )}

有限时间误差界（Theorem 6.1）：固定比例增益 $β = (\overset{ˉ}{β} / \overset{α}{ˉ}) α$ ， $ρ (A_{V A} (\overset{α}{ˉ}, \overset{ˉ}{β})) < 1$ 时存在与 $α$ 无关的常数 $c, K, L$ 使

E [∥ Q_{k} - Q^{*} ∥_{2}] \leq K (1 - \frac{c α}{2})^{k} ∥ Q_{0} - Q^{*} ∥_{2} + α γ L K^{2} k (1 - \frac{c α}{2})^{k - 1} ∥ Q_{0} - Q^{*} ∥_{2} + (1 + \frac{2 γ K L}{c}) \frac{K 2 α}{c} (σ_{0}^{2} + σ_{1}^{2} M_{α})^{1/2}

其中最后一项为 $O (α)$ ，反映常数步长固有的期望误差邻域。

3. 实验设计

实验 1（Figure 1，确定性）：单状态、两动作 MDP，自环转移，均匀 $D = \frac{1}{2} I_{2}$ 。
参数： $R = (0, 1)^{⊤}$ ， $Q_{0} = (0, 0)^{⊤}$ ， $γ = 0.9$ ， $η = α = β = 0.2$ ， $Q^{*} = (9, 10)^{⊤}$ 。
实验 2（Figure 2，随机）：2 状态、2 动作 MDP，非平凡转移核
$P (1∣1, 1) = 0.95, P (2∣1, 2) = 0.95, \dots$
奖励 $r (1, 1, \cdot) = 0$ ， $r (1, 2, \cdot) = 0.2$ ， $r (2, 1, \cdot) = 1.0$ ， $r (2, 2, \cdot) = 0.9$ 。
$γ = 0.9$ ，

$γ = 0.9$ ， $η = α = β = 0.2$ ，单条样本轨迹长度为 $1 0^{4}$ 步。

实验 3（Figure 3，链式 MDP）：经典 Garnet/链式结构以验证多状态下的统计行为，配合对数坐标展示收敛速率。

4. 实验结果与分析

4.1 Figure 1（确定性 AV 分解的子空间行为）

在单状态两动作 MDP 中， $V_{k}$ （公共分量）单调收敛至 $V^{*} = (9, 9)^{⊤}$ 附近， $A_{k}$ （差分分量）收敛至 $A^{*} = (0, 1)^{⊤}$ 。
关键观察：两个分量收敛速度不同——公共分量收敛较快，差分分量存在轻微振荡后收敛，体现了正交分解下 $Π$ 与 $Π^{⊥}$ 子空间的不同谱特性。
当 $α = β = η$ 时退化为标准 Q-learning；选取 $α < β$ （如 $α = 0.1, β = 0.2$ ）可观察到对差分分量更新的抑制，符合子空间步长理论。

4.2 Figure 2（随机版本的有限时间行为）

在 2 状态 2 动作随机 MDP 中，采样轨迹上 $E ∥ Q_{k} - Q^{*} ∥$ 的经验曲线与 Theorem 6.1 的有限时间界吻合：
初始阶段呈指数衰减，衰减率约为 $1 - c α /2$ ；
在 $k ≳ 1/ α$ 后进入 $O (α)$ 误差邻域，表现为水平渐近线。
改变采样分布 $d$ （如偏向差分动作）可观察到不同子空间上的收敛差异，验证了 $C_{V A}$ 中 $Π$ 、 $Π^{⊥}$ 权重的实际影响。

4.3 Figure 3（链式 MDP 的扩展）

在更长的链式 MDP 中，dueling Q-learning 的有限时间性能与正则化版本（Daley 等）趋势一致，但未正则化版本表现出更大的稳态方差（ $O (α)$ 项），这与理论预期一致：去掉了正则化项带来的"收缩偏置"。

5. 理论洞见与子空间解释

正交分解的意义：将 Bellman 算子的谱性质拆解到公共子空间（ $Π$ ）与差分子空间（ $Π^{⊥}$ ）上，可以独立调节两个子空间的学习速率——这是 dueling 网络架构在实践中有效的部分理论解释。
JSR-Lyapunov 框架的普适性：通过 Lemma 5.8 的算子重写，将 dueling Q-learning 的 JSR 等价转化为标准 Q-learning 的 JSR，从而复用现有分析工具，证明过程模块化、可迁移。
步长约束的几何意义：Lemma 5.9 的 $ℓ_{\infty}$ 收缩条件本质上要求 $C_{V A} D$ 的每一列在 $ℓ_{\infty}$ 范数下不超过 1，保证 Bellman 残差不会被放大，为常数步长下的稳定收敛提供充分条件。
有限时间界：Theorem 6.1 揭示了未正则化 dueling Q-learning 收敛包含三项——指数收敛项、过渡项（耦合的 $k (1 - c α /2)^{k - 1}$ ）、与方差相关的 $O (α)$ 误差邻域。后者量化了"常数步长 ≠ 渐近精确"这一固有特性。

6. 局限性与未来方向

表格设定：当前分析限于表格型 MDP，函数逼近（特别是 dueling 网络的神经网络部分）尚未覆盖；将 SLS 框架推广到线性函数逼近是自然的下一步。
保守步长：Lemma 5.9 提供的步长区间较保守，实际中可放宽；寻找与 JSR 条件匹配的紧致步长界仍是开放问题。
正则化对比：本文聚焦未正则化版本，未来可结合 Daley 等人的正则化分析，给出正则化如何缩小 $O (α)$ 误差邻域的定量刻画。
多步与分布式扩展： $TD (λ)$ 、分布式/异步 dueling Q-learning 的谱分析值得探索。

7. 主要贡献总结

1. 提出基于 $Π$ / $Π^{⊥}$ 正交分解的 dueling Q-learning 统一算法族（确定性、采样、Q-only 与 AV-only 形式）。

2. 通过 SLS 表示与 JSR-Lyapunov 框架，建立了未正则化常数步长 dueling Q-learning 的全局收敛性证明。

3. 给出有限时间误差界（Theorem 6.1），刻画指数收敛项与 $O (α)$ 误差邻域的耦合行为。

4. 在多个小型 MDP 上数值验证理论预测，并展示子空间步长选择对收敛行为的影响。

5. 提供从正交谱分析视角理解 dueling 网络架构有效性的理论框架，为后续函数逼近扩展奠定基础。

（完）

✨ 编译论文

点「✨ 编译」开始,LLM 会按 Polaris 风格翻译并把图片/表格嵌到对应位置。结果存到浏览器 localStorage,下次访问自动加载。