静态与时变网络上的方差缩减Q-Learning

# 静态与时变网络下的方差缩减Q学习
来源：https://arxiv.org/html/2607.21876
Sreejeet Maity†,\*, Feng Zhu†,\*, Aritra Mitra\*, and Robert W. Heath Jr†\\dagger 平等贡献。\* 作者单位：北卡罗来纳州立大学电气与计算机工程系。邮箱：\{smaity2, fzhu5, amitra2\}@ncsu.edu。Robert W. Heath Jr. 单位：加州大学圣地亚哥分校电气与计算机工程系，美国圣地亚哥。邮箱：[email protected]。

###### 摘要

我们研究了一个去中心化强化学习问题，涉及多个智能体与同一个马尔可夫决策过程 (MDP) 进行交互。智能体可以通过网络交换信息，共同学习最优状态-动作值函数。针对此设定，我们提出了一种新颖的基于轮次的分布式 Q 学习算法，称为 VRDQ，其中在每个轮次内，智能体局部估计贝尔曼最优性算子，并使用基于共识的协议扩散信息。对于静态和时变网络，我们为 VRDQ 建立了高概率的有限时间收敛速率，该速率通过协作实现了线性加速。关键的是，我们证明实现样本复杂度上的这种加速仅需要 \~{O}(1) 次通信，这大幅改善了先前工作中的通信成本。

## I 引言

鉴于合作式多智能体强化学习 (MARL) 在提升在线决策样本效率方面的潜力，我们考虑一个去中心化 RL 设定，涉及 N 个智能体，它们可以通过 (可能时变的) 网络交换信息。每个智能体与一个*共同环境*交互，该环境被建模为一个马尔可夫决策过程 (MDP)，目标是学习一个最大化长期累积回报的最优策略。在单智能体设定中，可以使用著名的 Q 学习算法 [17](https://arxiv.org/html/2607.21876#bib.bib45) 来学习这样的最优策略。考虑到我们设定中网络可用的集体信息，我们聚焦于回答两个基本问题：(i) *样本效率*：通过交换信息，每个智能体能否使用更少的样本 (相对于单智能体情况) 来学习最优策略？(ii) *通信效率*：如果可以，实现这种协作加速需要多少*通信开销*？也许令人惊讶的是，如下所述，即使在简单的表格 RL 问题中，这些问题也尚未解决，这促使了我们当前的研究。

相关工作。经典 Q 学习算法的去中心化变体的渐近收敛保证首次在 [4](https://arxiv.org/html/2607.21876#bib.bib109) 中给出；Actor-Critic 算法的类似结果后来在 [20](https://arxiv.org/html/2607.21876#bib.bib114), [21](https://arxiv.org/html/2607.21876#bib.bib115) 中得出。然而，为了刻画协作带来的明确统计增益，需要这些论文中尚未进行的更精细的非渐近分析。在一系列后续论文中，为去中心化时序差分学习 [1](https://arxiv.org/html/2607.21876#bib.bib113)、Q 学习 [3](https://arxiv.org/html/2607.21876#bib.bib110), [9](https://arxiv.org/html/2607.21876#bib.bib108) 以及一般随机逼近 [19](https://arxiv.org/html/2607.21876#bib.bib111) 推导了有限时间速率。然而，所有前述工作都存在两个关键局限性。首先，最终的性能界并未明确展示智能体间协作的任何益处。此外，每种方法的通信成本都与时间跨度 (即样本总数) 成线性关系。这产生了一个自然的张力：*使用现有的去中心化 RL 方法，通过收集更多样本来实现高精度，是以相应的高通信成本为代价的，阻碍了其在资源受限环境中的实际部署。*

在这项工作中，我们通过开发一种新型分布式 Q 学习算法来解决了上述张力，该算法 (i) 享有*接近最优*的协作统计益处，并且 (ii) 产生的通信成本仅与样本总数成*多对数*关系，这标志着相对于需要线性时间通信成本的现有方法有了显著改进。我们的结果适用于静态和时变网络，因此，相对于一些假设中央协调器的最新论文 [6](https://arxiv.org/html/2607.21876#bib.bib60), [18](https://arxiv.org/html/2607.21876#bib.bib59), [16](https://arxiv.org/html/2607.21876#bib.bib61)，我们的结果范围要广泛得多。重要的是，我们提出的算法具有与我们迄今为止查阅的所有论文根本不同的结构。

∙ \bullet 算法贡献。我们引入了一种新的去中心化 RL 算法，称为方差缩减扩散 Q 学习 (VRDQ)，它结合了两个关键要素：*局部算子估计*和*扩散*。与标准方法在*每个*时间步使用具有高方差的噪声更新方向来更新 Q 函数 (或其他相关参数) 不同，我们的方法依赖于通过局部估计贝尔曼最优性算子获得的低方差方向进行更少、*不频繁*的更新。更新的低频率直接转化为我们算法的低通信开销。我们方法的第二个关键要素是展示如何将局部算子估计阶段与旨在交换信息的平均共识扩散阶段并行运行。这些阶段的解耦特性使我们能够轻松地将统计误差与网络引起的误差分开，从而得到一个简单的整体分析。

∙ \bullet 理论贡献。我们的第一个主要结果，即定理 1 [https://arxiv.org/html/2607.21876#Thmtheorem1]，针对静态网络，并为我们的算法 VRDQ 建立了高概率有限样本收敛速率 \~{\mathcal{O}}(1/\sqrt{NT})，其中 T 是每个智能体的样本数，N 是智能体数量。这一结果揭示了相对于最近在 [15](https://arxiv.org/html/2607.21876#bib.bib12), [2](https://arxiv.org/html/2607.21876#bib.bib11), [8](https://arxiv.org/html/2607.21876#bib.bib20) 中建立的单智能体速率 \~{\mathcal{O}}(1/\sqrt{T}) 的明确协作优势。在定理 2 [https://arxiv.org/html/2607.21876#Thmtheorem2] 中，我们证明了 VRDQ 对于相当一般的时变网络类别继续享有相同的协作增益。关键的是，对于静态和时变网络，我们表明这种协作增益仅需 \mathcal{O}(\log^2(NT)) 次通信即可实现。

## II 符号与问题表述

图模型。我们首先介绍我们的网络模型。令 \mathcal{V} = \{1, 2, \ldots, N\} 为与同一环境 (建模为 MDP) 交互的 N 个智能体的集合。网络是无向图 \mathcal{G} = (\mathcal{V}, \mathcal{E})，其中 \mathcal{V} 是节点 (智能体) 集合，\mathcal{E} \subseteq \mathcal{V} \times \mathcal{V} 是表示智能体间通信链路的边集。由于图是无向的，当且仅当 (j,i) \in \mathcal{E} 时，(i,j) \in \mathcal{E}。如果 (i,j) \in \mathcal{E}，我们说智能体 j 是智能体 i 的邻居，并将智能体 i 的邻居集定义为其所有邻居 (包括其自身) 的集合：\mathcal{N}_i = \{j \mid (i,j) \in \mathcal{E}\}。我们为网络关联一个混合矩阵 W \in \mathbb{R}^{N \times N}，其中条目 (W)_{ij} 表示智能体 i 赋予智能体 j 信息的权重。如果 i \neq j，且 (i,j) \notin \mathcal{E}，则 (W)_{ij} = 0。混合矩阵 W 在分布式算法中起着核心作用，因为它决定了智能体如何组合来自邻居的信息。按照标准，我们假设 W 是对称且双随机的，即 W = W^\top，所有条目非负，且每行和每列之和为 1。稍后，在第六节 [https://arxiv.org/html/2607.21876#S6] 中，我们将看到我们的结果如何轻松推广到时变网络。

MDP 模型。我们现在介绍本文中使用的基本 MDP 符号。我们假设 \mathcal{V} 中的智能体与同一环境交互，该环境可建模为 MDP \mathcal{M} = \{\mathcal{S}, \mathcal{A}, \mathcal{R}, \mathcal{P}, \gamma\}，其中 \mathcal{S} 和 \mathcal{A} 是有限状态空间和动作空间，其基数分别记为 S 和 A，\mathcal{R}: \mathcal{S} \times \mathcal{A} \to \mathbb{R} 是奖励函数，\mathcal{R}(s,a) 表示在状态 s 执行动作 a 所获得的即时确定性奖励。在整篇论文中，我们假设有界奖励 |\mathcal{R}(s,a)| \leq \bar{R}，其中 \bar{R} > 0 是某个常数。对象 \mathcal{P}: \mathcal{S} \times \mathcal{A} \times \mathcal{S} \to [0,1] 是转移核，\mathcal{P}(s' \mid s,a) 表示在状态 s 执行动作 a 后转移到下一状态 s' 的概率。最后，\gamma \in (0,1) 是折扣因子。

智能体的行为由一个随机策略 \pi: \mathcal{S} \to \Delta(\mathcal{A}) 来刻画，该策略在给定状态 s \in \mathcal{S} 下输出动作空间 \mathcal{A} 上的概率分布。然后很自然地开发一个度量来衡量当智能体按照策略 \pi 与 MDP \mathcal{M} 交互时策略 \pi 的*优劣*。这就引出了值函数 V^\pi \in \mathbb{R}^S 的概念，定义为从状态 s \in \mathcal{S} 开始，遵循策略 \pi 的无限水平累积折扣回报的期望：

V^\pi(s) = \mathbb{E}\left[ \sum_{t=0}^{\infty} \gamma^t \mathcal{R}(s_t, a_t) \,\bigg|\, s_0 = s, \pi \right], \quad (1) 其中期望是关于状态转移和随机策略 \pi 的随机性；这里 s_t 和 a_t 分别表示时刻 t 的状态和动作。类似地，我们引入状态-动作值函数或 Q 函数 Q^\pi \in \mathbb{R}^{S \times A} 的概念，它评估从状态 s 和初始动作 a 开始的策略：

Q^\pi(s,a) = \mathcal{R}(s,a) + \mathbb{E}\left[ \sum_{t=1}^{\infty} \gamma^t \mathcal{R}(s_t, a_t) \,\bigg|\, \pi \right]. \quad (2)

Q 学习。智能体的总体目标是找到最大化所有状态 s \in \mathcal{S} 下的值函数 V^\pi 的最优策略 \pi^*。与动态规划问题不同，在我们的 RL 设定中，包含转移核和奖励函数的底层 MDP 模型对智能体是*未知*的。在这种设定下，著名的 Q 学习算法 [17](https://arxiv.org/html/2607.21876#bib.bib45) 首先迭代估计最优 Q 函数 Q^* \in \mathbb{R}^{S \times A}，然后通过贪婪动作选择提取关联的最优策略 \pi^*：在每个状态 s \in \mathcal{S} 下，\pi^*(s) = \arg\max_{a \in \mathcal{A}} Q^*(s,a)。Q 学习的核心思想是利用 Q^* 是下面定义的贝尔曼最优性算子 \mathcal{T}^* : \mathbb{R}^{S \times A} \to \mathbb{R}^{S \times A} [13](https://arxiv.org/html/2607.21876#bib.bib9) 的唯一不动点这一事实：

\mathcal{T}^* f(s,a) := \mathcal{R}(s,a) + \gamma \sum_{s' \in \mathcal{S}} \mathcal{P}(s' \mid s,a) \max_{a' \in \mathcal{A}} f(s',a'), \quad (3) \forall f \in \mathbb{R}^{S \times A}。为了运行 Q 学习，需要一个使用由合适采样模型生成的数据对 \mathcal{T}^* 的噪声经验估计序列。在这项工作中，我们将考虑流行的*生成式同步采样模型* [15](https://arxiv.org/html/2607.21876#bib.bib12), [8](https://arxiv.org/html/2607.21876#bib.bib20), [5](https://arxiv.org/html/2607.21876#bib.bib7), [12](https://arxiv.org/html/2607.21876#bib.bib8)，其中智能体进行如下形式的观测。在每个时间步 t=0,1,\ldots，对于*每个*状态-动作对 (s,a) \in \mathcal{S} \times \mathcal{A}，智能体独立地采样下一状态 s_t(s,a) \sim \mathcal{P}(\cdot \mid s,a)，并观察即时确定性奖励 \mathcal{R}(s,a)。然后，智能体构建贝尔曼最优性算子 \mathcal{T}^* 的一个*噪声经验*估计 \mathcal{T}_t : \mathbb{R}^{S \times A} \to \mathbb{R}^{S \times A}，定义如下：

\mathcal{T}_t f(s,a) = \mathcal{R}(s,a) + \gamma \max_{a' \in \mathcal{A}} f(s_t(s,a), a'), \quad (4) \forall f \in \mathbb{R}^{S \times A}。使用 \mathcal{T}_t，Q 学习算法更新 Q 估计如下，\forall (s,a) \in \mathcal{S} \times \mathcal{A}：

Q_{t+1}(s,a) = (1 - \alpha_t) Q_t(s,a) + \alpha_t \mathcal{T}_t Q_t(s,a), \quad (5) 其中 Q_t \in \mathbb{R}^{S \times A} 是时刻 t 的估计 Q 函数，\{\alpha_t\} 是合适的步长序列。经典渐近结果表明，由 (5) 生成的迭代序列 \{Q_t\} 几乎必然收敛到 Q^* [14](https://arxiv.org/html/2607.21876#bib.bib4)。更近期的研究 [15](https://arxiv.org/html/2607.21876#bib.bib12), [2](https://arxiv.org/html/2607.21876#bib.bib11), [8](https://arxiv.org/html/2607.21876#bib.bib20) 建立了非渐近保证，揭示出使用 T 个样本，估计误差 \|Q_T - Q^*\|_{\infty} 为 \~{\mathcal{O}}\left(1/\sqrt{T}\right)，具有高概率。

网络化 Q 学习问题。现在我们可以陈述我们感兴趣的问题。假设 \mathcal{V} 中的每个智能体被允许并行获取每个状态-动作对的 T 个*统计独立*样本，通过对生成式模型进行 T 次查询。