2025-11-18T08:49:13.884110

Perturbing Best Responses in Zero-Sum Games

Dziwoki, Horcik
This paper investigates the impact of perturbations on the best-response-based algorithms approximating Nash equilibria in zero-sum games, namely Double Oracle and Fictitious Play. More precisely, we assume that the oracle computing the best responses perturbs the utilities before selecting the best response. We show that using such an oracle reduces the number of iterations for both algorithms. For some cases, suitable perturbations ensure the expected number of iterations is logarithmic. Although the utility perturbation is computationally demanding as it requires iterating through all pure strategies, we demonstrate that one can efficiently perturb the utilities in games where pure strategies have further inner structure.
academic

Perturbing Best Responses in Zero-Sum Games

基本信息

摘要

本文研究了扰动对基于最佳响应算法的影响,这些算法用于近似零和博弈中的纳什均衡,特别关注Double Oracle和Fictitious Play算法。研究假设计算最佳响应的预言机在选择最佳响应前对效用进行扰动。研究表明,使用这种扰动预言机可以减少两种算法的迭代次数。在某些情况下,合适的扰动可以确保期望迭代次数为对数级别。虽然效用扰动需要遍历所有纯策略,计算代价较高,但研究证明对于纯策略具有内部结构的博弈(如部分可观察随机博弈),可以高效地实现扰动。

研究背景与动机

核心问题

在大规模策略空间的双人零和博弈中计算纳什均衡是一个计算密集型问题。虽然理论上已知存在大小为O(log n)的ε-纳什均衡(其中n为纯策略数量),但传统的基于最佳响应预言机(BRO)的算法如Fictitious Play(FP)和Double Oracle(DO)在最坏情况下需要Ω(n)次迭代。

重要性

  1. 理论-实践差距: Althöfer和Lipton等人证明存在对数大小的ε-NE,但实际算法无法达到这一复杂度
  2. 下界限制: Hazan和Koren证明任何基于BRO的算法至少需要Ω(√n/log³n)次迭代
  3. 实际应用需求: 深度强化学习算法(如Policy Space Response Oracles)依赖于这些基础算法

现有方法局限

  1. FP和DO: 最坏情况下需要O(n)次迭代
  2. Hazan-Koren算法: 虽然提供了O(√n/ε²)的复杂度,但算法复杂且仅为平方根级改进
  3. 正则化方法: 如PU和OMWU虽然达到O(log n)迭代,但需要维护所有纯策略的概率分布,不适用于大规模博弈

研究动机

通过在最佳响应预言机中引入扰动,使其更强大,从而突破理论下界的限制,实现对数级别的收敛速度。

核心贡献

  1. 引入扰动最佳响应预言机(PBRO): 提出在计算最佳响应前对效用进行随机扰动的机制
  2. 理论结果:
    • 证明Stochastic Fictitious Play (SFP)在期望上达到O(log n/ε²)次迭代复杂度
    • 证明Stochastic Double Oracle (SDO)对特定困难实例(Zhang和Sandholm的例子)达到O(log n)期望迭代
  3. 高效实现方案: 提出针对具有内部结构的博弈(如POSG、路径规划博弈)的高效扰动方法,无需遍历所有纯策略
  4. 实验验证: 在多种博弈类型上验证了扰动方法的有效性,包括矩阵博弈、随机博弈和路径规划博弈
  5. 理论工具: 利用Gumbel-max技巧建立SFP与随机指数加权预测器(REWF)的联系

方法详解

任务定义

输入: 矩阵博弈M ∈ ℝ^(m×n),精度参数ε > 0 输出: ε-纳什均衡策略对⟨p*, q*⟩ 约束: 最小化迭代次数(预言机调用次数)

扰动最佳响应的数学定义

对于行玩家,给定列玩家混合策略q ∈ Δ_n:

B̃R_r(q) ∈ argmin_{i∈[m]} π_i(Mq - u)

其中u是随机向量,其分量为i.i.d.随机变量。

对于列玩家,给定行玩家混合策略p ∈ Δ_m:

B̃R_c(p) ∈ argmax_{j∈[n]} π_j(p^⊤M + v)

Stochastic Fictitious Play (SFP)

算法流程:

  1. 初始化: t←1, p←e_k, q←e_l (初始纯策略)
  2. 计算终止条件边界: lb←BRVal_r(q), ub←BRVal_c(p)
  3. 当ub - lb > tε时:
    • t←t+1
    • i←B̃R_r(q), j←B̃R_c(p) (扰动最佳响应)
    • p←p+e_i, q←q+e_j (累积策略)
    • 更新边界
  4. 返回平均策略: ⟨p*/t, q*/t⟩

关键创新:

  • 使用扰动预言机而非确定性预言机
  • 维护累积策略向量,最终返回平均策略
  • 终止条件使用未扰动的最佳响应值

Gumbel扰动的理论基础

Gumbel-max技巧 (Lemma 1): 对于向量x ∈ ℝ^n,如果z的分量独立同分布于Gumbel分布G(0,β):

P(argmax_i π_i(x+z) = i*) = π_i*(softmax(x/β))

这意味着使用Gumbel扰动的最佳响应等价于从softmax分布中采样。

与REWF的联系:

  • SFP中行玩家的策略选择等价于REWF策略
  • 在第t轮,采样自softmax(-η∑^{t-1} Me)
  • 参数η = 1/β控制探索-利用权衡

理论分析核心

定理3 (SFP复杂度): 对于归一化到0,1的矩阵博弈M ∈ ℝ^(m×n),m ≤ n,设β = (2+√(2ln n))/(ε√(8ln n)),则SFP在O(log n/ε²)期望迭代内找到ε-NE。

证明思路:

  1. 设定迭代次数T = ((2+√(2ln n))/ε)² ∈ O(log n/ε²)
  2. 利用Corollary 2(REWF的遗憾界),概率≥3/4: 
    ∑_{t=1}^T M(i_t,j_t) - min_i ∑_{t=1}^T M(i,j_t) ≤ √T(1 + √(ln n)/2)
  3. 对列玩家应用对偶结果(概率≥3/4)
  4. 两个事件同时发生概率≥1/2
  5. 结合两个不等式得到ub - lb ≤ ε
  6. 期望运行次数≤2次

Stochastic Double Oracle (SDO)

算法特点:

  • 维护策略子集R ⊆ m, C ⊆ n
  • 每轮计算子博弈MR,C的纳什均衡
  • 使用扰动预言机添加新策略

针对特定博弈的分析:

Example 1 (矩阵L):

L = [0   1   ...  1  ]
    [-1  0   ...  1  ]
    [⋮   ⋮   ⋱   ⋮  ]
    [-1  -1  ... 0  ]

Lemma 4 (均匀扰动的期望): 对于第k行x = ⟨1,...,1,0,-1,...,-1⟩,使用U(-1/2,1/2)扰动, 扰动最佳响应的期望索引EI = k/2

Theorem 6: SDO在O(log n)期望迭代内找到L的NE

证明技术:

  • 定义势函数X_t = max{r_t, c_t},其中r_t = min R_t, c_t = min C_t
  • 使用漂移理论(drift theory)证明X_t - EX_{t+2} ≥ X_t/2
  • 应用Corollary 17得到ET ≤ 2ln n

高效扰动实现

聚类方法: 对于具有内部结构的博弈(如随机博弈):

  1. 识别对应相同终端状态的矩阵元素
  2. 将矩阵元素聚类为K个簇
  3. 对每个簇应用相同的随机扰动值

扰动公式:

B̃R_r(q) = argmin_{i∈[m]} π_i((L + ∑_{k=1}^K z_k B_k)q)

其中B_k是掩码矩阵,标识第k个簇的元素

优势:

  • 只需生成K个随机数(K << mn)
  • 保持了博弈结构的语义
  • 适用于POSG、EFG等结构化博弈

实验设置

数据集和博弈类型

  1. 随机矩阵博弈: n×n矩阵,元素从0,1均匀采样,每个规模生成100个实例
  2. 矩阵L和U^⊤: 来自Example 1和2的困难实例
  3. f-finger Morra游戏: 经典博弈,矩阵大小f²×f²
  4. Colonel Blotto游戏: 5个战场,不同单位预算
  5. n-bit随机博弈: 对应2^n×2^n矩阵,具有树状结构
  6. 路径规划博弈: n×n网格,一方寻找最短路径,另一方选择边增加成本

评价指标

  • 迭代次数: 达到ε-NE所需的预言机调用次数
  • ε值: 设定为0.1
  • 统计量: 10次重复实验的均值和标准差

对比方法

  1. FP: 标准Fictitious Play
  2. AFP: Anticipatory Fictitious Play
  3. SAFP: AFP的扰动版本
  4. DO: 标准Double Oracle
  5. SDO: 扰动版本Double Oracle

实现细节

  • 编程语言: Python
  • 硬件: AMD Ryzen 7 PRO 7840U
  • 随机数生成: numpy库,初始种子为1
  • 初始化: 最坏情况索引(k=l=n)
  • Tie-breaking: 选择最小索引的最佳响应
  • SFP的β参数: 根据Theorem 3设定
  • SDO扰动分布:
    • 理论分析: U(-1,1)
    • 实际应用: U(-0.01,0.01)和U(-0.001,0.001)

实验结果

主要结果

SFP在不同博弈上的表现

随机0,1矩阵博弈:

  • AFP表现最优,显著优于其他方法
  • SFP和SAFP表现相似,略优于FP
  • 随机博弈中扰动优势不明显
  • 迭代次数随规模增长接近线性

矩阵U^⊤:

  • FP和AFP显示O(n)最坏情况复杂度
  • SFP和SAFP迭代次数显著减少
  • 对于n=1000,SFP约需10-15次迭代,而FP需1000次
  • 验证了理论O(log n)复杂度

f-finger Morra游戏:

  • SFP和SAFP快速收敛,即使对于大规模f
  • FP和AFP迭代次数随f²增长
  • f=10时,SFP约需50次迭代,FP需200+次

SDO在不同博弈上的表现

矩阵L和U^⊤ (理论扰动U(-1,1)):

  • SDO达到理论预测的对数复杂度
  • 对于n=2000,SDO约需10-15次迭代
  • DO需要n次迭代(未在图中显示因规模过大)
  • 完美验证Theorem 6和7

f-finger Morra游戏:

  • 扰动显著减少迭代次数
  • U(-0.01,0.01)和U(-0.001,0.001)都有效
  • 较小扰动(U(-0.001,0.001))在大规模时表现更稳定

Colonel Blotto游戏:

  • 5个战场,单位预算0-40
  • 扰动方法持续优于无扰动版本
  • U(-0.01,0.01)整体表现最优

高效扰动实验

n-bit随机博弈 (对应L和U^⊤):

  • 使用聚类扰动方法
  • 对于n=2000(2^11规模),约需100次迭代
  • 虽比理论扰动稍慢,但远优于DO的线性复杂度
  • 证明高效实现的可行性

路径规划博弈:

  • 在n×n网格上测试
  • 扰动显著减少迭代次数
  • 网格规模增大时,优势更明显
  • n=14时,扰动版本约需100次迭代,无扰动需200+次

消融实验观察

扰动强度影响:

  • 过大扰动可能损害收敛(在随机博弈中观察到)
  • U(-0.001,0.001)在多数情况下表现稳定
  • U(-0.01,0.01)在结构化博弈中更有效

扰动分布选择:

  • Gumbel分布: 理论最优,适合SFP
  • 均匀分布: 实践中更简单,SDO中有效
  • 两者在实验中表现相近

关键发现

  1. 博弈类型依赖性: 扰动在结构化/困难实例中效果显著,在随机博弈中优势不明显
  2. 理论-实践一致性: 实验结果与理论预测高度吻合
  3. 高效实现可行性: 聚类方法在保持效果的同时大幅降低计算成本
  4. 鲁棒性: 扰动方法在多种博弈类型上表现稳定

相关工作

Fictitious Play收敛研究

  • Robinson (1951): 证明FP在零和博弈中收敛到NE
  • Karlin猜想: FP收敛速度的最古老开放问题
  • 部分结果: Abernethy等(2021)、Daskalakis和Pan(2014)针对特定矩阵类型的结果
  • AFP: Cloud等(2023)提出,仍需O(n)迭代但常数更小,每轮调用4次BRO

正则化方法

  • Hofbauer和Sandholm (2002): 证明扰动与正则化的联系
  • PU和OMWU: Cen等(2024)的正则化AFP变体,达到O(log n)但需维护所有策略概率分布
  • 本文区别: PBRO只需维护已选策略子集,适用于大规模博弈

Double Oracle研究

  • 基础复杂度: 已知DO需Θ(n)迭代,但缺乏深入理论研究
  • Zhang和Sandholm (2024): 证明DO在POSG上的指数下界
  • 变体研究: McAleer等(2022)的Self-Play PSRO等,但无收敛保证
  • 本文贡献: 首次系统研究SDO的收敛性质

BRO算法的理论界限

  • Althöfer (1994), Lipton和Young (1994): 存在O(log n)大小的ε-NE
  • Hazan和Koren (2016):
    • 下界: 任何BRO算法需Ω(√n/log³n)迭代
    • 上界: 提出O(√n/ε²)算法
  • 本文突破: 通过增强BRO(加入扰动)突破理论下界

深度强化学习应用

  • PSRO系列: Lanctot等(2017)、McAleer等(2022)、Bighashdel等(2024)
  • 联系: 这些方法依赖DO框架,本文的SDO可直接应用
  • 潜在影响: 扰动机制可能改进深度RL的探索策略

结论与讨论

主要结论

  1. 理论突破:
    • SFP达到O(log n/ε²)期望复杂度,首次证明PBRO算法的对数级收敛
    • SDO在特定困难实例上达到O(log n)期望复杂度
  2. 实践价值:
    • 扰动方法在结构化博弈中显著减少迭代次数
    • 高效实现方案使方法适用于大规模博弈
  3. 方法论贡献:
    • 建立了SFP与REWF的理论联系
    • 提供了使用漂移理论分析SDO的框架

局限性

  1. SDO一般复杂度未解决:
    • 仅证明了特定实例的对数复杂度
    • 一般情况下的复杂度仍是开放问题
  2. 随机博弈表现:
    • 扰动在随机生成的博弈中优势不明显
    • 可能因为随机博弈本身最佳响应就具有随机性
  3. 扰动参数选择:
    • 理论最优参数(β)在实践中可能过大
    • 需要根据具体博弈调整扰动强度
  4. 高效实现的近似性:
    • 聚类扰动不完全等价于完整扰动
    • 理论保证仅适用于完整扰动情况
  5. 计算成本:
    • 虽然减少迭代次数,但每次迭代需生成随机数
    • 对于某些博弈,收益可能不足以抵消额外开销

未来方向

  1. SDO的一般复杂度分析:
    • 证明或反驳SDO在一般情况下的对数复杂度
    • 识别SDO高效的博弈类别特征
  2. 自适应扰动策略:
    • 根据收敛情况动态调整扰动强度
    • 探索不同扰动分布的理论性质
  3. 深度强化学习集成:
    • 将PBRO集成到PSRO框架
    • 研究神经网络近似BRO时的扰动效果
  4. 更广泛的博弈类别:
    • 扩展到一般和博弈
    • 研究多人博弈中的扰动机制
  5. 实际应用验证:
    • 在真实博弈场景(如扑克、策略游戏)中测试
    • 评估实际计算资源约束下的性能

深度评价

优点

  1. 理论严谨性:
    • 完整的数学证明,从Gumbel-max技巧到漂移理论
    • 清晰建立了SFP与经典在线学习算法(REWF)的联系
    • 理论结果与实验高度一致
  2. 问题选择重要:
    • 针对领域内长期存在的理论-实践差距
    • 突破了Hazan-Koren的下界限制(通过增强预言机)
    • 对深度强化学习有直接应用价值
  3. 方法创新性:
    • 简单而有效的扰动机制
    • 高效实现方案解决了计算瓶颈
    • 统一框架适用于FP和DO两类算法
  4. 实验全面性:
    • 涵盖理论实例、经典博弈、随机博弈、结构化博弈
    • 对比多种baseline方法
    • 诚实报告了随机博弈中的负面结果
  5. 写作清晰度:
    • 背景介绍充分,动机明确
    • 技术细节完整,可复现性强
    • 提供开源代码

不足

  1. 理论完备性:
    • SDO的一般复杂度未解决,仅有特例分析
    • 缺乏对扰动失效情况(如随机博弈)的理论解释
    • 高效扰动与完整扰动的理论差距未量化
  2. 实验设计:
    • 随机博弈实验规模相对较小(n≤1000)
    • 缺少与Hazan-Koren算法的直接比较
    • 未报告实际运行时间,只有迭代次数
  3. 实用性考虑:
    • 扰动参数选择缺乏通用指导
    • 对于何时使用扰动缺乏判断标准
    • 高效实现方案的适用范围不够明确
  4. 分析深度:
    • 对扰动机制为何有效的直观解释不足
    • 未深入分析不同博弈结构与扰动效果的关系
    • 消融实验相对简单
  5. 比较公平性:
    • AFP每轮调用4次BRO,而FP/SFP只调用2次
    • 应该也报告总BRO调用次数的比较

影响力

  1. 理论贡献:
    • 为BRO算法研究提供了新方向
    • 证明了增强预言机的潜力
    • 可能启发其他组合优化问题的研究
  2. 实践价值:
    • 直接适用于现有DO/FP框架
    • 对深度RL中的PSRO方法有改进潜力
    • 高效实现方案具有实际可操作性
  3. 局限性:
    • 需要进一步理论发展才能成为标准方法
    • 随机博弈中的表现限制了普适性
    • 计算开销需要在大规模应用中验证
  4. 可复现性:
    • 提供开源代码,复现性强
    • 算法描述清晰,易于实现
    • 实验设置详细

适用场景

强烈推荐:

  1. 具有明确结构的博弈(EFG, POSG)
  2. 存在多个等价最佳响应的博弈
  3. 传统DO/FP收敛慢的困难实例
  4. 策略空间巨大但有内部结构的博弈

谨慎使用:

  1. 完全随机的博弈
  2. 最佳响应唯一且明确的博弈
  3. 计算资源极度受限的场景
  4. 需要确定性保证的应用

不推荐:

  1. 小规模博弈(直接求解更快)
  2. 无结构的一般博弈(扰动优势不明显)
  3. 实时决策场景(随机性可能不可接受)

参考文献

关键理论基础:

  1. Althöfer (1994) - 对数大小ε-NE的存在性
  2. Hazan & Koren (2016) - BRO算法的理论界限
  3. Hofbauer & Sandholm (2002) - SFP收敛性证明
  4. Cesa-Bianchi & Lugosi (2006) - REWF算法

相关工作: 5. Zhang & Sandholm (2024) - DO的指数下界 6. Cloud et al. (2023) - Anticipatory Fictitious Play 7. Lanctot et al. (2017) - Policy Space Response Oracles 8. Cen et al. (2024) - 正则化博弈算法

总体评价: 这是一篇理论与实践结合良好的优秀论文。主要贡献是证明了扰动机制可以使BRO算法达到对数级复杂度,突破了已知的理论下界(通过增强预言机)。SFP的理论结果完整严谨,SDO的分析虽然不完全但提供了有价值的洞察。实验设计全面,诚实报告了方法的适用范围。主要不足是SDO的一般复杂度未解决,以及对随机博弈表现不佳缺乏理论解释。该工作为博弈论算法研究开辟了新方向,对深度强化学习也有潜在应用价值,值得进一步研究。