技术摘要：合作多智能体无奖励探索中的视界阈值

问题陈述

本工作研究了表格型有限视界马尔可夫决策过程（MDP）框架下的合作多智能体无奖励探索。在此设定中，$m$ 个智能体在 $\rho$ 个学习阶段内与未知环境 $M = (S, s_0, A, H, P, r)$ 并行交互。关键在于，在探索阶段，智能体无法观测到奖励函数 $r$；其目标是以足够的精度学习转移动力学 $P$，以便在探索结束后，针对任何被揭示的奖励函数计算出 $\epsilon$-最优策略。

核心研究问题探讨两种资源之间的权衡：

1. 并行时间：学习阶段的数量 $\rho$。
2. 智能体复杂度：每阶段部署的智能体数量 $m$。

本文旨在刻画视界 $H$ 如何支配学习效率，特别是确定当阶段数量受限时，多项式数量的智能体是否足以完成任务。

方法论

上界：H-MARFE 算法

作者提出了 H-MARFE（H-Phase Multi-Agent Reward-Free Exploration，H-阶段多智能体无奖励探索），这是一种设计为在恰好 $\rho = H$ 个阶段内运行并使用多项式数量智能体的算法。

核心机制：
与顺序式的后悔最小化方法不同，H-MARFE 利用分层探索策略，使估计精度随状态可达性进行缩放。

1. 分阶段动力学估计：在第 $i$ 阶段（其中 $i \in \{0, \dots, H-1\}$），算法仅专注于估计时间步 $i$ 处的转移动力学 $P_i$。
2. 可达性过滤：算法在每个时间步定义一组“活跃”状态 $\hat{S}^\beta_i$，由在当前估计动力学下可达概率至少为 $\beta$ 的状态组成。可达性低的状态通过确定性转移到吸收态 $s_{sink}$ 而被有效剪枝。
3. 策略构建：对于每个活跃的状态 - 动作对 $(s, a)$，算法基于先前阶段学习到的动力学，计算一个策略 $\hat{\pi}_{i,s,a}$，以最大化在时间步 $i$ 到达状态 $s$ 并执行动作 $a$ 的概率。
4. 并行执行：在每个阶段，$m$ 个智能体被分配来自活跃集的随机状态 - 动作对。它们执行其分配的策略以收集轨迹，这些轨迹被聚合以形成当前层的经验转移估计。

技术革新：
分析引入了一种中间动力学模型 $P^1$，它在活跃集上与真实动力学 $P$ 一致，否则转移到 $s_{sink}$。证明依赖于对估计动力学 $\hat{P}$ 与 $P^1$ 之间的策略加权误差进行界定。通过控制相对于可达性的占据测度中的加性误差，该算法确保了针对任何奖励函数的价值估计误差保持有界，从而避免了朴素并行化中典型的指数级误差累积。

下界构造

为了确立视界规模阶段数量的必要性，作者构造了一个“关键动力学”MDP。

• 结构：该 MDP 的状态空间大小为 2（$s^\star$ 和 $s_{sink}$）。存在一个隐藏的“密钥”动作序列 $a^\star_0, \dots, a^\star_{H-1}$。在状态 $s^\star$ 采取正确的动作 $a^\star_h$ 会使智能体保持在 $s^\star$；任何其它动作都会转移到吸收态 $s_{sink}$。
• 奖励：特定的奖励函数 $r_{key}$ 仅在智能体在最终时间步处于状态 $s^\star$ 且执行了正确的最终动作时，才分配 1 的奖励。
• 推论：为了学习动力学（从而学习最优策略），算法必须发现整个密钥序列。在单个阶段中，$m$ 个智能体最多能揭示密钥的 $\log_A(m)$ 位信息。如果阶段数量 $\rho$ 显著小于 $H$，除非智能体数量 $m$ 随 $H/\rho$ 呈指数增长，否则发现完整密钥的概率将呈指数级下降。

主要结果

1. 上界（定理 3.1）

H-MARFE 算法以高概率为任何奖励函数实现 $\epsilon$-最优策略，所需资源为：

• 阶段数：$\rho = H$。
• 智能体数：$m = \tilde{O}\left(\frac{S^6 H^6 A}{\epsilon^2}\right)$。

这表明，当学习阶段数量与视界呈线性缩放时，可实现高效学习（关于 $S, A, H, \epsilon^{-1}$ 的多项式复杂度）。

2. 下界（定理 4.1）

对于任何限制在 $\rho < H$ 个学习阶段内的合作多智能体算法，要实现常数精度（例如 $\epsilon = 0.1$），需要：

• 智能体数：$m = \Omega\left(\frac{A^{(H-1)/\rho}}{\rho}\right)$。

该下界证明，将阶段数量减少到视界以下，需要智能体数量呈指数级增加。

3. 视界阈值

综合结果揭示了一个由视界 $H$ 控制的急剧机制转变：

• 多项式区域：当 $\rho \approx H$ 时，智能体复杂度为多项式级。
• 指数区域：当 $\rho \ll H$ 时，智能体复杂度随 $H/\rho$ 呈指数级增长。

意义与主张

本文声称确立了表格型 MDP 中无奖励探索并行效率的基本极限。主要贡献在于识别出视界 $H$ 是并行时间的关键阈值。

• 视界规模阶段的必要性：该工作表明，为了避免智能体复杂度的指数级增长，不能简单地将探索压缩为常数或次线性数量的阶段。阶段数量必须与视界成比例缩放。
• 算法效率：H-MARFE 提供了一种计算高效的方法来实现这种最优权衡，这与先前的无奖励文献形成对比，后者本质上是顺序的，或者需要随回合数线性增长的切换成本。
• 理论差距：作者指出，虽然其上界实现了多项式复杂度，但对 $S$ 和 $H$ 的依赖（$S^6 H^6$）高于最先进的单智能体界限（$S^2 H^3$）。他们明确表示，这种差距是并行化的固有成本，还是其分析的人为产物，仍然是一个未解决的问题。

本文得出结论：合作多智能体无奖励探索仅在允许并行时间（阶段）随问题视界缩放时，才可能以多项式资源实现，这从根本上将该设定与那些并行性可以任意降低时间复杂度而无需付出指数级资源代价的场景区分开来。