辅助博弈中可证明最优的学习算法

# 辅助博弈的最优可证明学习算法 来源: https://arxiv.org/html/2607.08012 Mark Bedaywi · Michael I. Jordan · Stuart Russell · Nika Haghtalab ###### 摘要 本文研究*辅助博弈*框架的一种在线变体，其中，知情智能体与不知情智能体在 \(T\) 个时间步上重复交互，以优化一个共同的奖励函数。知情智能体（人类）观测世界的潜在状态，而不知情智能体（助手）仅观测人类的行动。我们首次为重复辅助博弈提供了可证明高效的学习算法。我们引入了*辅助遗憾*的概念：即交互累积效用与事后最优联合策略（将潜在状态映射到行动对）的累积效用之间的差距。我们为人类和助手分别提出了去中心化算法，这些算法实现了 \( (1-1/e) \) 近似辅助遗憾率 \(\tilde{\mathcal{O}}\left(T^{3/4}\right)\)，其运行时间与行动和状态空间的大小成多项式关系。这些算法具有通用性；特别地，它们能够容纳任何无遗憾算法作为助手。我们证明，实现优于 \( (1-1/e) \) 的遗憾近似因子在计算上是难处理的。此外，我们展示了如何将这些通用无遗憾算法调整到伪去中心化设置中——使用共享的随机串——以实现 \(\tilde{\mathcal{O}}\left(T^{1/2}\right)\) 的速率，该速率在忽略对数因子时是渐进最优的。 ## 1 引言 考虑两个合作智能体之间的重复交互，它们具有共同的目标，但信息访问不对称。一个智能体观测变化的潜在状态——例如偏好、类型或目标——而另一个必须仅基于第一个智能体产生的间接信号采取行动。这种场景自然地出现在人类-助手交互、合作多智能体系统、辅助 AI 训练以及涌现通信的抽象中，其中前者代表具有私有偏好的人类主体，后者代表试图代表人类行事的 AI 助手。尽管效用上不存在策略性偏离，但这些环境中的协调构成了根本性挑战。一方面，缺乏共享的参照系或通用语言意味着智能体必须通过随时间观察彼此的行动来学习如何通信。另一方面，行动同时产生效用，导致它们扮演双重角色：既是实现奖励的工具，也是传递潜在状态的信号。这种信息性与效用性之间的张力是问题的核心。 捕捉这些挑战的一个理论视角是*辅助博弈*框架，也称为*合作逆强化学习*（Hadfield-Menell 等，2016 (https://arxiv.org/html/2607.08012#bib.bib24)）。该框架将人类与辅助 AI 系统之间的交互建模为具有部分可观测性的合作博弈。先前的工作研究了最优辅助策略的均衡和结构性质——例如，行动信息性与效用性之间的权衡——但计算和学习此类策略的算法问题尚未被探索过。在本文中，我们引入了辅助博弈的*在线*变体，并给出了计算高效、去中心化的算法，用于学习人类和助手双方的近优策略。 我们的模型捕捉了知情智能体（人类）与不知情智能体（助手）之间的重复交互。在每一轮 \(t\) 中，一个潜在状态 \(\theta^{(t)}\in\Theta\)——可能来自非平稳过程——实现并仅被人类观测到。这个状态代表关于人类偏好或目标的私有信息。人类从有限行动空间 \(\mathcal{A}_H\)（大小为 \(M_H\)）中选择一个行动 \(a_H^{(t)}\)。助手观测到 \(a_H^{(t)}\)，但看不到 \(\theta^{(t)}\)，并从有限行动空间 \(\mathcal{A}_A\)（大小为 \(M_A\)）中选择一个行动 \(a_A^{(t)}\) 作为响应。随后，两个智能体共同获得一个奖励 \(r\!\left(a_H^{(t)}, a_A^{(t)}; \theta^{(t)}\right)\)，该奖励依赖于联合行动和人类的私有状态。 为了衡量性能，我们考虑*联合*人类-助手策略空间：即策略对 \((\pi_H, \pi_A)\)，其中人类策略 \(\pi_H: \Theta \to \mathcal{A}_H\) 将潜在状态映射到人类行动，助手策略 \(\pi_A: \mathcal{A}_H \to \mathcal{A}_A\) 将人类行动映射到助手行动。我们通过 \(\alpha\) 近似辅助遗憾（定义 3.1 (https://arxiv.org/html/2607.08012#S3.Thmtheorem1)）来衡量成功：即智能体的累积奖励与事后最优联合策略累积奖励的 \(\alpha\) 倍之间的差距。 我们的主要结果为人类和助手提供了一对去中心化学习算法，这些算法实现了 \( (1-1/e) \) 近似辅助遗憾，其速率为 \(\tilde{\mathcal{O}}\left(T^{3/4}\right)\)，运行时间为 \(\mathrm{poly}(N, M_H, M_A)\)（定理 4.1 (https://arxiv.org/html/2607.08012#S4.Thmtheorem1)）；在轻微的初始协调下——一个从人类行动序列到助手策略的共享编码——该速率提升至 \(\tilde{\mathcal{O}}\left(\sqrt{T}\right)\)，在 \(T\) 上忽略对数因子时是渐进最优的（定理 4.2 (https://arxiv.org/html/2607.08012#S4.Thmtheorem2)）。 这一结果依赖于两个技术要素。首先是一个归约，将辅助博弈中的联合策略优化转化为带有拟阵约束的在线子模最大化问题（引理 D.1 (https://arxiv.org/html/2607.08012#A4.Thmtheorem1) 和 5.4 (https://arxiv.org/html/2607.08012#S5.Thmtheorem4)）。该归约利用子模函数的结构，使得尽管联合策略空间是指数大小的，但计算上仍是可处理的。其次是一个遗憾分解引理（引理 4.4 (https://arxiv.org/html/2607.08012#S4.Thmtheorem4)），它将辅助遗憾边界约束为集中式算法的外部遗憾、其策略切换次数以及助手针对移动目标的追踪遗憾之和。这一分解指导我们的设计实现两个结构性属性：人类的*稳定性*（少量策略切换）和助手的*自适应性*（低追踪遗憾）。近似因子 \(1-1/e\) 是紧的：除非 \(\mathsf{RP} = \mathsf{NP}\)，否则任何高效算法都无法实现对于 \(\alpha > 1-1/e\) 的次线性 \(\alpha\) 近似辅助遗憾（定理 4.3 (https://arxiv.org/html/2607.08012#S4.Thmtheorem3)）。 ## 2 相关工作 用数学建模 AI 辅助问题的想法最早在大约十年前由 Fern 等人 (2014 (https://arxiv.org/html/2607.08012#bib.bib17)) 和 Hadfield-Menell 等人 (2016 (https://arxiv.org/html/2607.08012#bib.bib24)) 的工作中提出。Shah 等人 (2020 (https://arxiv.org/html/2607.08012#bib.bib52)) 证明，这样的助手比传统的奖励学习算法更能满足人类偏好；Hadfield-Menell 等人 (2016 (https://arxiv.org/html/2607.08012#bib.bib24), 2017 (https://arxiv.org/html/2607.08012#bib.bib25)) 证明，最优助手可以避免与人类价值观不一致的问题。Malik 等人 (2018 (https://arxiv.org/html/2607.08012#bib.bib44)) 和 Laidlaw 等人 (2025 (https://arxiv.org/html/2607.08012#bib.bib37)) 提出了经验上表现良好的求解辅助博弈的算法，但设计可证明最优地玩此类博弈的学习算法仍然是一个开放问题。与我们类似，先前的工作也采用了将辅助博弈问题归约为其他问题类别的方法——特别是归约为部分可观测马尔可夫决策过程（POMDP）的类别。我们引入了一种具有数学结构的新归约，从而可以证明最优性保证。 辅助博弈的一个特定子类是*通信博弈*。我们在附录 F (https://arxiv.org/html/2607.08012#A6) 中更详细地描述了这方面的相关工作。 我们的工作与均衡计算方面的文献相关。我们可以将目标表述为在辅助博弈中去中心化地学习最优均衡。计算最优均衡在一般情况下是计算上难处理的（Gilboa 和 Zemel, 1989 (https://arxiv.org/html/2607.08012#bib.bib21)），包括在共同利益博弈中也是如此（Chu 和 Halpern, 2001 (https://arxiv.org/html/2607.08012#bib.bib11); Conitzer 和 Sandholm, 2006 (https://arxiv.org/html/2607.08012#bib.bib13)）。在共同利益博弈中，最优均衡同时也是每个玩家的 Stackelberg 均衡。计算 Stackelberg 均衡的计算可处理性已被证明依赖于博弈的几何结构，并且可能在一般情况下是难处理的（Letchford 等, 2009 (https://arxiv.org/html/2607.08012#bib.bib40); Peng 等, 2019 (https://arxiv.org/html/2607.08012#bib.bib47)）。对于可以高效计算 Stackelberg 均衡的博弈，可以通过一个玩家的学习动态比另一个更稳定的动力学来实现向 Stackelberg 均衡的收敛（Brown 等, 2024 (https://arxiv.org/html/2607.08012#bib.bib7); Zrnic 等, 2021 (https://arxiv.org/html/2607.08012#bib.bib58)）。我们为通信博弈提出的学习动态也满足这一性质。 研究智能体之间合作交互的其他领域包括团队决策理论的工作（例如，Radner (1962 (https://arxiv.org/html/2607.08012#bib.bib48))；Ho 等人 (1972 (https://arxiv.org/html/2607.08012#bib.bib29))；Nayyar 等人 (2013 (https://arxiv.org/html/2607.08012#bib.bib46))；Mahajan 和 Mannan (2016 (https://arxiv.org/html/2607.08012#bib.bib43))；Malikopoulos (2022 (https://arxiv.org/html/2607.08012#bib.bib45))），这些工作采用控制论方法研究最优合作；以及人-AI 协作方面的工作，研究人-AI 系统何时实现互补性，即优于各个组件之和的性能（例如，Green 和 Chen (2019 (https://arxiv.org/html/2607.08012#bib.bib22))；Bansal 等人 (2021 (https://arxiv.org/html/2607.08012#bib.bib6))；Wilder 等人 (2020 (https://arxiv.org/html/2607.08012#bib.bib57))；Steyvers 等人 (2022 (https://arxiv.org/html/2607.08012#bib.bib55))；Donahue 等人 (2022 (https://arxiv.org/html/2607.08012#bib.bib15))；Athey 等人 (2020 (https://arxiv.org/html/2607.08012#bib.bib5))；Alur 等人 (2024 (https://arxiv.org/html/2607.08012#bib.bib3))；Greenwood 等人 (2025 (https://arxiv.org/html/2607.08012#bib.bib23))；Collina 等人 (2026 (https://arxiv.org/html/2607.08012#bib.bib12))）。 ## 3 模型与预备知识 在线辅助博弈由一个偏好空间 \(\Theta\)（大小为 \(N\)）、两个行动集 \(\mathcal{A}_H\) 和 \(\mathcal{A}_A\)（大小分别为 \(M_H\) 和 \(M_A\)）以及一个有界奖励函数 \(r: \mathcal{A}_H \times \mathcal{A}_A \times \Theta \to [0,1]\) 定义。两个智能体，一个助手和一个人类，在 \(T\) 轮中重复进行该博弈。首先，自然在开始之前固定偏好 \(\theta^{(1)}, \dots, \theta^{(T)} \in \Theta\)。然后，辅助博弈的每一轮 \(t \in [T]\) 包含以下步骤： 1. 人类观测到 \(\theta^{(t)}\) 并采取行动 \(a_H^{(t)} \in \mathcal{A}_H\)。 2. 助手仅看到人类采取的行动 \(a_H^{(t)}\)，而看不到偏好 \(\theta^{(t)}\)。然后，助手采取行动 \(a_A^{(t)} \in \mathcal{A}_A\) 作为响应。 3. 助手和人类都获得奖励 \(r\left(a_H^{(t)}, a_A^{(t)}; \theta^{(t)}\right)\)。 参数 \(\theta^{(t)}\) 捕获了第 \(t\) 轮时人类的偏好。我们允许偏好 \(\theta^{(t)}\) 随时间变化，从而允许对人类偏好的变化具有鲁棒性。然而，我们施加了一个限制：偏好序列在博弈开始之前是固定的。也就是说，每一轮的偏好不能根据之前的交互轮次自适应地选择。我们称之为*不知情*设置。更强的模型是，对手可以根据之前的交互轮次对抗性地选择偏好 \(\theta^{(t)}\)，这被称为*自适应*设置。我们在附录 B (https://arxiv.org/html/2607.08012#A2) 中证明，在自适应设置中学习最优辅助存在根本性的限制。 助手接收赌臂反馈：它观测到行动对 \(a_H^{(t)}, a_A^{(t)}\) 和相应的奖励 \(r\left(a_H^{(t)}, a_A^{(t)}; \theta^{(t)}\right)\)，但由于它无法访问 \(\theta^{(t)}\)，因此无法重建反事实奖励。相比之下，人类由于也能观测到 \(\theta^{(t)}\)，因此接收全信息反馈。 在辅助博弈的标准形式表示中，人类的策略空间是映射的集合 \(\Pi_H\)，映射从人类的私有偏好到人类行动：\(\pi_H: \Theta \to \mathcal{A}_H\)；助手的策略空间是映射的集合 \(\Pi_A\)，映射从观测到的人类行动到助手行动：\(\pi_A: \mathcal{A}_H \to \mathcal{A}_A\)。为方便表示，我们用 \(r(\pi_H, \pi_A; \theta)\) 表示当人类和助手分别采取策略 \(\pi_H\) 和 \(\pi_A\) 且人类偏好为 \(\theta\) 时，人类和助手获得的奖励，数学上即 \(r(\pi_H(\theta), ~\pi_A(\pi_H(\theta)); ~\theta)\)。 我们引入一个（近似）遗憾的概念来衡量在线辅助博弈中人类和助手的联合成功。我们称之为*辅助遗憾*，在本文剩余部分中简称为遗憾。辅助遗憾定义如下。 ###### 定义 3.1 (\(\alpha\) 辅助遗憾)。对于固定的 \(\alpha \in [0,1]\)，序列 \(\chi = \left(\theta^{(t)}, \pi_H^{(t)}, \pi_A^{(t)}\right)_{t=1}^T\) 的 \(\alpha\) 辅助遗憾，记作 \(R_T^\alpha(\chi)\)，为： \[ \alpha\left( \max_{\pi_H^* \in \Pi_H, \pi_A^* \in \Pi_A} \sum_{t=1}^T r\left(\pi_H^*, \pi_A^*; \theta^{(t)}\right) \right) - \sum_{t=1}^T r\left(\pi_H^{(t)}, \pi_A^{(t)}; \theta^{(t)}\right). \] 当上下文清楚时，我们在遗憾概念中省略 \(\theta^{(t)}\)，并记 \(r_t(\pi_H, \pi_A) = r(\pi_H, \pi_A; \theta^{(t)})\)。我们也用 \(R_T(\mathrm{Alg})\) 表示算法 \(\mathrm{Alg}\) 的最小最大 \(\alpha\) 辅助遗憾。 ### 3.1 带有拟阵约束的子模最大化 我们的结果将依赖于子模最大化和拟阵理论中的工具。本节我们将描述必要的工具。给定一个任意集合 \(\mathcal{U}\)，定义在 \(\mathcal{U}\) 上的集合函数是从子集到实数