Policy Abstraction and Nash Refinement in Tree-Exploiting PSRO

📄 arXiv: 2502.02901v2 📥 PDF

作者: Christine Konicki, Mithun Chakraborty, Michael P. Wellman

分类: cs.GT, cs.AI

发布日期: 2025-02-05 (更新: 2025-02-15)

💡 一句话要点

提出基于策略抽象和纳什精炼的树搜索PSRO算法，加速不完美信息博弈的求解。

🎯 匹配领域: 支柱二：RL算法与架构 (RL & Architecture)

关键词: 策略空间响应预言机 经验博弈论 深度强化学习 不完美信息博弈 子博弈完美均衡

📋 核心要点

  1. 现有PSRO方法在复杂博弈中面临策略空间爆炸和探索效率低下的问题，限制了其应用。
  2. 论文提出基于策略抽象的经验博弈树表示，并利用子博弈完美均衡指导策略探索，提升效率。
  3. 实验表明，基于SPE的策略生成相比纳什均衡能更快收敛到均衡，且资源消耗可控。

📝 摘要（中文）

策略空间响应预言机(PSRO)将经验博弈论分析与深度强化学习(DRL)相结合，以解决传统分析方法难以处理的复杂博弈问题。树搜索PSRO(TE-PSRO)是该方法的一种变体，它通过查询模拟器获得的数据，迭代地构建一个在扩展形式上的粗化经验博弈模型，该模拟器代表了博弈的详细描述。我们对TE-PSRO进行了两项主要的方法改进，增强了其在复杂不完美信息博弈中的适用性。首先，我们为经验博弈树引入了一种可扩展的表示，其中边对应于通过DRL学习的隐式策略。这些策略覆盖了博弈模型中抽象的底层博弈中的条件，支持树在各个epoch上的可持续增长。其次，我们通过利用精炼的纳什均衡来指导策略探索，从而利用经验模型中的扩展形式。为此，我们提出了一种基于广义逆向归纳的模块化和可扩展算法，用于计算不完美信息博弈中的子博弈完美均衡(SPE)。我们在包括具有外部报价的交替报价议价博弈在内的一系列博弈中对我们的方法进行了实验评估；我们的结果表明，当基于SPE而不是纳什均衡生成新策略时，TE-PSRO收敛到均衡的速度更快，并且对于不断增长的经验模型，时间/内存需求合理。

🔬 方法详解

问题定义：论文旨在解决复杂不完美信息博弈中，传统PSRO方法因策略空间巨大和探索效率低下而难以有效求解的问题。现有方法难以在合理的时间和资源内找到博弈的均衡策略。

核心思路：论文的核心思路是构建一个粗化的经验博弈模型，并通过策略抽象来控制模型的大小。同时，利用子博弈完美均衡（SPE）而非传统的纳什均衡来指导策略探索，从而更有效地找到博弈的均衡解。SPE考虑了博弈的动态结构，能够避免一些次优的策略选择。

技术框架：TE-PSRO的整体框架包括以下几个主要阶段：1) 使用深度强化学习训练策略；2) 基于训练好的策略构建经验博弈树，其中树的边对应于抽象策略；3) 在经验博弈树上计算子博弈完美均衡（SPE）；4) 基于SPE指导新的策略生成，并重复以上步骤。该框架迭代地构建和优化经验博弈模型，最终收敛到博弈的均衡解。

关键创新：论文的关键创新在于两个方面：一是提出了基于策略抽象的经验博弈树表示，能够有效地控制模型的大小，并支持树的持续增长。二是利用子博弈完美均衡（SPE）来指导策略探索，相比于传统的纳什均衡，SPE能够更好地利用博弈的结构信息，从而提高探索效率。

关键设计：论文的关键设计包括：1) 策略抽象的具体方法，如何将底层博弈中的状态映射到经验博弈树的节点；2) 计算SPE的算法，论文提出了一种基于广义逆向归纳的模块化和可扩展算法；3) 如何利用SPE来指导策略生成，例如，可以根据SPE选择在哪些状态下进行策略探索。

🖼️ 关键图片

fig_0
fig_1
fig_2

📊 实验亮点

实验结果表明，在包括具有外部报价的交替报价议价博弈在内的一系列博弈中，基于SPE生成新策略的TE-PSRO比基于纳什均衡的TE-PSRO收敛速度更快。同时，该方法在不断增长的经验模型中，保持了合理的时间和内存需求。

🎯 应用场景

该研究成果可应用于各种复杂的不完美信息博弈场景，例如谈判、拍卖、安全博弈、以及多智能体系统中的资源分配等。通过更有效地求解这些博弈，可以提升决策效率和优化资源利用，具有重要的实际应用价值和潜力。

📄 摘要（原文）

Policy Space Response Oracles (PSRO) interleaves empirical game-theoretic analysis with deep reinforcement learning (DRL) to solve games too complex for traditional analytic methods. Tree-exploiting PSRO (TE-PSRO) is a variant of this approach that iteratively builds a coarsened empirical game model in extensive form using data obtained from querying a simulator that represents a detailed description of the game. We make two main methodological advances to TE-PSRO that enhance its applicability to complex games of imperfect information. First, we introduce a scalable representation for the empirical game tree where edges correspond to implicit policies learned through DRL. These policies cover conditions in the underlying game abstracted in the game model, supporting sustainable growth of the tree over epochs. Second, we leverage extensive form in the empirical model by employing refined Nash equilibria to direct strategy exploration. To enable this, we give a modular and scalable algorithm based on generalized backward induction for computing a subgame perfect equilibrium (SPE) in an imperfect-information game. We experimentally evaluate our approach on a suite of games including an alternating-offer bargaining game with outside offers; our results demonstrate that TE-PSRO converges toward equilibrium faster when new strategies are generated based on SPE rather than Nash equilibrium, and with reasonable time/memory requirements for the growing empirical model.