自对弈强化学习中决策能力结构性阈值决定崩溃

# 决策容量中的结构性阈值主导自对弈强化学习的崩溃行为 来源：https://arxiv.org/html/2605.16315 ###### 摘要 我们证明，在自对弈强化学习智能体中，存在一个决策容量阈值，该阈值决定了当规则受到非对称扰动时智能体是否会崩溃。在多种扑克变体（Kuhn、Leduc、Leduc-4）、矩阵博弈（Matching Pennies）、掷骰子游戏（Liar's Dice；24,576个信息集）以及六种学习算法（Q-Learning、SARSA、REINFORCE、PPO、DQN、NFSP）中，消除所有具有正到达率的条件性决策会导致快速收敛到一个确定性利用吸引子（DEA）——一个接近最大损失值的固定点。即使保留一个具有正到达率的条件性决策点也能防止这种崩溃。冻结基线和固定对手的对照实验确认，其机制是约束下的共同适应，而非扰动本身。该现象与时机无关，在恢复行动后完全可逆，并在函数近似下加剧。这些结果确立了由CACw=0\\text\{CAC\}\_\{w\}=0处不连续性引发的实际上的陡峭阈值，其严重性通过所有测试领域中的到达加权容量连续缩放。 ## 1. 引言 通过自对弈训练的多智能体强化学习（MARL）智能体已在复杂博弈中达到超人类水平（Silver等人, 2018 (https://arxiv.org/html/2605.16315#bib.bib4); Brown和Sandholm, 2019 (https://arxiv.org/html/2605.16315#bib.bib8); Vinyals等人, 2019 (https://arxiv.org/html/2605.16315#bib.bib12)），但其对环境结构性变化的鲁棒性仍知之甚少。先前工作主要关注对观测或奖励的对抗性扰动（Gleave等人, 2020 (https://arxiv.org/html/2605.16315#bib.bib6)）、分布偏移下的对手建模（Foerster等人, 2018 (https://arxiv.org/html/2605.16315#bib.bib14)）或基于群体的方法的训练稳定性（Balduzzi等人, 2019 (https://arxiv.org/html/2605.16315#bib.bib15)）。对*行动空间*的结构性变化——智能体永久失去某些行动——的研究在很大程度上仍是空白。这种扰动在实践中自然出现。在机器人领域，硬件故障可能导致执行器失效，从而在部署中消除智能体可用的行动。在金融交易中，监管变化可能限制先前可用的策略。在多智能体软件系统中，API弃用可能移除行动端点。理解自对弈智能体如何应对这些非对称能力损失，对于在行动空间无法保证静态的环境中部署强化学习系统至关重要。我们通过在离散、不完美信息博弈中，确定性移除一个玩家在指定决策节点子集上下注或加注的能力来研究这一问题。我们发现了一个具有精确阈值的结构性失效模式：智能体的*条件性行动容量*（CAC）——即其保留多于一个合法行动的信息集数量——决定了自对弈动态是崩溃还是稳定。为了可解释性，我们报告未加权的CAC；到达加权变体CACw\\text\{CAC\}\_\{w\}对很少到达的决策点进行折扣，并且是与最佳响应不连续性一致的量。我们的核心发现是一个显著的门槛效应。当CACw\\text\{CAC\}\_\{w\}降至零（每个正到达决策都被强制）时，自适应自对弈智能体收敛到一个*确定性利用吸引子*（DEA）——由被强制玩家的策略σ0f\\sigma\_\{0\}^\{f\}所诱导的单智能体MDP的唯一最优策略。其稳定性源于在CACw=0\\text\{CAC\}\_\{w\}=0下反事实分支的缺失：对手面临一个静态、确定性的环境，具有唯一的最佳响应，而ε\\varepsilon\-贪婪扰动限制了与理论最小值的偏差。零偶然性将博弈简化为针对σ0f\\sigma\_\{0\}^\{f\}的最佳响应这一静态事实是预期的；贡献在于观察到的学习转变：从零容量时的崩溃到仅保留一个正到达决策点时的接近纳什稳定性。冻结基线和固定对手的对照实验将持续的共同适应分离为机制。 我们的贡献： - ·我们确定了一个支配自对弈RL中崩溃的显著到达加权CAC阈值，并提供了刻画零偶然性固定点的形式化命题。 - ·通过冻结基线和固定对手的比较，我们将约束下的共同适应隔离为机制。 - ·我们证明了在函数近似（DQN）下崩溃会持续并加剧。 - ·我们在八种博弈变体（1–24,576个信息集）、六种算法、多种扰动调度中进行了复现，并展示了完全可逆性。边界条件（IPD、Liar's Dice、合作博弈）使阈值定义更加清晰。 ## 2. 相关工作 #### 解决不完美信息博弈。 反事实遗憾最小化（CFR）（Zinkevich等人, 2007 (https://arxiv.org/html/2605.16315#bib.bib1)）及其变体已成功解决越来越大的扑克博弈，从一对一限注德州扑克（Bowling等人, 2015 (https://arxiv.org/html/2605.16315#bib.bib2)）到通过DeepStack（Moravčík等人, 2017 (https://arxiv.org/html/2605.16315#bib.bib7)）、Libratus（Brown和Sandholm, 2018 (https://arxiv.org/html/2605.16315#bib.bib9)）和Pluribus（Brown和Sandholm, 2019 (https://arxiv.org/html/2605.16315#bib.bib8)）实现的无限注变体。这些系统假设固定的博弈结构。我们研究的是博弈结构在训练后发生非对称变化时会发生什么。 #### 自对弈强化学习。 自对弈推动了从TD-Gammon（Tesauro, 1994 (https://arxiv.org/html/2605.16315#bib.bib3)）到AlphaZero（Silver等人, 2018 (https://arxiv.org/html/2605.16315#bib.bib4)）和AlphaStar（Vinyals等人, 2019 (https://arxiv.org/html/2605.16315#bib.bib12)）的进步。神经虚拟自对弈（NFSP）（Heinrich和Silver, 2016 (https://arxiv.org/html/2605.16315#bib.bib10)）将强化学习与平均策略跟踪相结合。策略空间响应Oracle（PSRO）（Lanctot等人, 2017 (https://arxiv.org/html/2605.16315#bib.bib11)）维护多样化的策略群体。然而，自对弈动态可能不稳定——智能体可能会循环、过拟合自身弱点或表现出非传递行为（Balduzzi等人, 2019 (https://arxiv.org/html/2605.16315#bib.bib15); Lanctot等人, 2019 (https://arxiv.org/html/2605.16315#bib.bib5)）。我们的工作确定了一种独特的失效模式：在非对称行动空间约束下的共同适应驱动崩溃。 #### 多智能体RL中的鲁棒性。 MARL鲁棒性文献涵盖对抗性策略（Gleave等人, 2020 (https://arxiv.org/html/2605.16315#bib.bib6)）、对手学习意识（Foerster等人, 2018 (https://arxiv.org/html/2605.16315#bib.bib14)）和分布鲁棒性（Zhang等人, 2021 (https://arxiv.org/html/2605.16315#bib.bib13)）。这些通常扰动观测、奖励或对手行为。我们扰动*行动空间*本身——这是一种消除决策点而非添加噪声的结构性变化。这揭示了连续扰动无法产生的定性阈值效应。 #### 行动屏蔽与约束RL。 无效行动屏蔽是博弈AI中的标准做法（Huang和Ontañón, 2022 (https://arxiv.org/html/2605.16315#bib.bib19)），而约束MDP形式化了行动限制（Altman, 1999 (https://arxiv.org/html/2605.16315#bib.bib20)）。鲁棒MDP处理不确定转移（Iyengar, 2005 (https://arxiv.org/html/2605.16315#bib.bib21); Nilim和El Ghaoui, 2005 (https://arxiv.org/html/2605.16315#bib.bib22)），而随机行动集MDP对可用行动变化的情况进行建模（Boutilier等人, 2018 (https://arxiv.org/html/2605.16315#bib.bib23)）。然而，*训练过程中*在自对弈下移除行动的动态后果尚未被研究。 #### 自对弈稳定化。 对手塑造方法如LOLA（Foerster等人, 2018 (https://arxiv.org/html/2605.16315#bib.bib14)）和SOS（Letcher等人, 2019 (https://arxiv.org/html/2605.16315#bib.bib24)）通过考虑对手的学习动态来稳定自对弈。基于群体的方法包括PSRO（Lanctot等人, 2017 (https://arxiv.org/html/2605.16315#bib.bib11)）和α\\alpha\-PSRO（Muller等人, 2020 (https://arxiv.org/html/2605.16315#bib.bib25)）维护多样化的策略群体以避免循环。我们实证测试了PSRO，发现它*缓解*但未消除崩溃（§6.3 (https://arxiv.org/html/2605.16315#S6.SS3)）。 #### 可被利用性与博弈论评估。 可被利用性——智能体价值与纳什均衡价值之间的差距——是计算博弈论中的标准评估指标（Johanson和Bowling, 2007 (https://arxiv.org/html/2605.16315#bib.bib16); Timbers等人, 2022 (https://arxiv.org/html/2605.16315#bib.bib17)）。我们通过形式化命题（第5节）将我们的阈值效应与缩减博弈的最佳响应结构联系起来。 ## 3. 背景 #### Kuhn扑克。 三张牌（J型被消除的扰动（例如，移除下注行动）。除非另有说明，扰动在训练期间保持有效；恢复实验在测试时恢复行动。所有CAC都是相对于初始完整博弈计算，并假设对手的博弈结构保持不变。 #### 条件性行动容量（CAC）。 给定博弈，CAC统计玩家在某个信息集处拥有多于一个合法行动的信息集数量。所有基于CAC的实验都使用未加权计数作为代理；CACw\\text\{CAC\}\_\{w\}（到达加权，第5节）是控制的理论量。所有观察到的CAC阈值对应于CACw>0\\text\{CAC\}\_\{w\}>0 vs. CACw=0\\text\{CAC\}\_\{w\}=0机制；未加权计数作为一个可解释的代理，与所有测试博弈中的到达加权区分相一致。 #### 自对弈设置。 单个智能体扮演两个角色，Q值按玩家特定的信息状态索引。这等价于我们零和设置中的独立自对弈，因为每个玩家的策略由分离的信息状态条目隐式确定。我们通过经验验证这一点：分离智能体实验产生相同结果（附录B (https://arxiv.org/html/2605.16315#A2)）。 #### 统计分析。 跨种子的配对tt检验，自助法95% CI（10,000次重采样），Cohen's dd。由于配对评估下跨种子方差低，效应量大，应解释为指示方向和可靠性。 #### 标准化。 跨博弈比较使用(r−rmin)/(rmax−rmin)∈[0,1](r - r_{\min})/(r_{\max} - r_{\min}) \in [0,1]。这种标准化有助于跨奖励尺度比较，但掩盖了绝对可被利用性；我们在可计算的地方（Kuhn, Leduc）报告精确可被利用性以补充标准化奖励。标准化比较与两种博弈中均可用的可被利用性趋势一致。 ## 5. 理论 我们在两人零和扩展式博弈中形式化阈值效应。以下命题适用于零和情况；第6.5节 (https://arxiv.org/html/2605.16315#S6.SS5)提供了经验证据表明合作和混合动机设置产生定性不同的（有界退化）响应。将形式化处理扩展到一般和博弈留待未来工作。 令G=(H,P,A,I,u)G = (H, P, \mathcal{A}, \mathcal{I}, u)为一个两人零和博弈，包含历史集HH、玩家函数PP、行动集AA、信息划分I\mathcal{I}和效用uu。 #### 条件性行动容量。 对于缩减博弈G′G'，玩家ii的未加权条件性行动容量为： CAC(Pi)=∑h∈Ii1[|A(h)|≥2]。\text{CAC}(P_{i}) = \sum_{h \in \mathcal{I}_{i}} \mathbf{1}[|A(h)| \geq 2]。 (1) 这统计了扰动后玩家仍有真正选择的信息集数量。 #### 到达加权条件性行动容量。 对于策略剖面σ\sigma，信息集hh的*到达概率*为ρσ(h)=∏h′⊏hσP(h′)(h′)\rho^{\sigma}(h) = \prod_{h' \sqsubset h} \sigma_{P(h')}(h')，即通往hh路径上行动概率的乘积。我们定义*到达加权CAC*： CACw(Pi)=∑h∈Iiρσ(h)⋅1[|A(h)|≥2]\text{CAC}_{w}(P_{i}) = \sum_{h \in \mathcal{I}_{i}} \rho^{\sigma}(h) \cdot \mathbf{1}[|A(h)| \geq 2] (2) 这通过折扣很少到达的信息集来细化未加权计数。实验中使用的未加权CAC是一个上界：CAC≥CACw\text{CAC} \geq \text{CAC}_{w}。 ###### 命题1（零偶然性利用）。 令G′G'为缩减博弈，其中CAC(P0)=0\text{CAC}(P_{0}) = 0（等价于CACw(P0)=0\text{CAC}_{w}(P_{0}) = 0）。则P0P_{0}在G′G'中的价值为： v0(G′)=−maxπ1∈Π1∑z∈Zu1(z)⋅ρσ0f,π1(z)v_{0}(G') = -\max_{\pi_{1} \in \Pi_{1}} \sum_{z \in Z} u_{1}(z) \cdot \rho^{\sigma_{0}^{f}, \pi_{1}}(z) 其中σ0f\sigma_{0}^{f}是P0P_{0}的强制（确定性）策略。此外，P1P_{1}的最佳响应是纯的，且可在O(|Z|)O(|Z|)时间内计算。 ###### 证明。 在零偶然性下，σ0f\sigma_{0}^{f}是P0P_{0}的唯一策略。博弈简化为P1P_{1}在确定性环境下的单智能体MDP。最优策略是一个纯最佳响应，可通过在P1P_{1}的决策节点上进行反向归纳计算，复杂度与在σ0f\sigma_{0}^{f}下可到达的终端历史数量成线性关系。 ∎ ###### 命题2（残余偶然性界）。 假设P0P_{0}至少保留一个信息集h∗∈I0h^{*} \in \mathcal{I}_{0}，满足|A(h∗)|≥2|A(h^{*})| \geq 2且到达概率ρσ(h∗)>0\rho^{\sigma}(h^{*}) > 0。令v0∗v_{0}^{*}为P0P_{0}在以h∗h^{*}为根的子博弈中的最小最大价值，令v0forcedv_{0}^{\text{forced}}为在其他所有节点上采用强制策略时的价值。则： v0(G′)≥ρσ(h∗)⋅v0∗+(1−ρσ(h∗))⋅v0forcedv_{0}(G') \geq \rho^{\sigma}(h^{*}) \cdot v_{0}^{*} + (1 - \rho^{\sigma}(h^{*})) \cdot v_{0}^{\text{forced}} 特别地，只要v0∗>v0forcedv_{0}^{*} > v_{0}^{\text{forced}}且ρσ(h∗)>0\rho^{\sigma}(h^{*}) > 0，就有v0(G′)>v0zero-contv_{0}(G') > v_{0}^{\text{zero-cont}}。改进量与保留节点的到达概率成正比： δ(h∗)=ρσ(h∗)⋅(v0∗−v0forced)\delta(h^{*}) = \rho^{\sigma}(h^{*}) \cdot (v_{0}^{*} - v_{0}^{\text{forced}}) ###### 证明。 根据到达概率的线性性质，P0P_{0}的价值可以分解为经过h∗h^{*}的历史（其中P0P_{0}最优行动）和不经过h∗h^{*}的历史（其中P0P_{0}被迫行动）的贡献。界直接由此得出。当h∗h^{*}以概率1到达时（如Kuhn根节点仅移除，所有博弈都经过"pb"节点），δ(h∗)=v0∗−v0forced\delta(h^{*}) = v_{0}^{*} - v_{0}^{\text{forced}}，且恢复完整的最小最大价值。 ∎ ###### 推论1。 从CACw>0\text{CAC}_{w} > 0到CACw=0\text{CAC}_{w} = 0的转变定性地改变了最佳响应结构：从一个需要混合或自适应响应（价值由δ(h∗)\delta(h^{*})界定）的博弈，转变为具有可简单计算的纯最佳响应的博弈。一个具有正到达概率的保留决策点足以防止崩溃；一个到达概率为零的保留决策点不提供任何保护。 ###### 命题3（DEA作为自对弈动态的固定点）。 考虑在零偶然性（CACw=0\text{CAC}_{w} = 0）下的表格Q学习自对弈。令Q1(s,a)Q_{1}(s, a)表示P1P_{1}的Q值。在标准假设（ε>0\varepsilon > 0, αt→0\alpha_{t} \to 0, ∑αt=∞\sum \alpha_{t} = \infty）下，P1P_{1}的Q值收敛