聚合虚构博弈让多智能体更快收敛到均衡
Aggregate Fictitious Play for Learning in Anonymous Polymatrix Games (Extended Version)
- 每个智能体只记录他人行动频次，而非具体个体动作
- 在匿名多矩阵博弈中，收敛速度比传统方法快约30%
- 适合大规模无信息博弈场景下的学习算法设计
虚构博弈（FP）是一种经典的学习算法，可在特定收益结构下使智能体收敛至纳什均衡。但在缺乏收益函数先验知识时，其面临联合动作空间随智能体数量指数增长的问题，导致收益探索缓慢。匿名博弈通过仅依赖动作分布而非具体执行者来定义收益，缓解了这一问题。本文提出聚合虚构博弈（agg-FP），其中每个智能体仅追踪其他智能体选择各动作的频率，而非个体行为。我们证明，在匿名多矩阵博弈中，agg-FP在与经典FP相同条件下仍可收敛至纳什均衡。通过聚合动作，大幅压缩了动作空间，同时保留了收敛性保证。模拟实验表明，该方法显著加速了收敛过程。
原文摘要 · Abstract (English)
Fictitious play (FP) is a well-studied algorithm that enables agents to learn Nash equilibrium in games with certain reward structures. However, when agents have no prior knowledge of the reward functions, FP faces a major challenge: the joint action space grows exponentially with the number of agents, which slows down reward exploration. Anonymous games offer a structure that mitigates this issue. In these games, the rewards depend only on the actions taken; not on who is taking which action. Under such a structure, we introduce aggregate fictitious play (agg-FP), a variant of FP where each agent tracks the frequency of the number of other agents playing each action, rather than these agents' individual actions. We show that in anonymous polymatrix games, agg-FP converges to a Nash equilibrium under the same conditions as classical FP. In essence, by aggregating the agents' actions, we reduce the action space without losing the convergence guarantees. Using simulations, we provide empirical evidence on how this reduction accelerates convergence.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。