arXiv:2504.18868cs.GTcs.LG2025-04被引 1

用元学习改进后悔最小化,更逼近博弈论中的纳什均衡。

Approximating Nash Equilibria in General-Sum Games via Meta-Learning

  • 通过元学习优化后悔最小化器的策略相关性
  • 在不完美信息博弈中显著提升纳什均衡近似精度
  • 适合研究博弈算法或强化学习的学者参考

纳什均衡是博弈论中最著名的解概念,为每个玩家分配一个策略,使其无单方面偏离动机。尽管纳什均衡始终存在,但在一般和博弈中寻找其解属于PPAD完全问题,通常被认为难以求解。后悔最小化是近似二人零和博弈纳什均衡的有效框架,但在一般和博弈中,此类算法仅保证收敛至粗相关均衡(CCE),即玩家可关联策略的解。本文利用元学习降低后悔最小化器产生的策略相关性,促使算法趋向纳什均衡。元学习后的后悔最小化器仍保证收敛至CCE,但本文给出了其与纳什均衡距离的元损失上界。我们在一般和不完美信息博弈中评估该方法,结果表明,相比现有后悔最小化技术,本方法能显著更好逼近纳什均衡。

原文摘要 · Abstract (English)

Nash equilibrium is perhaps the best-known solution concept in game theory. Such a solution assigns a strategy to each player which offers no incentive to unilaterally deviate. While a Nash equilibrium is guaranteed to always exist, the problem of finding one in general-sum games is PPAD-complete, generally considered intractable. Regret minimization is an efficient framework for approximating Nash equilibria in two-player zero-sum games. However, in general-sum games, such algorithms are only guaranteed to converge to a coarse-correlated equilibrium (CCE), a solution concept where players can correlate their strategies. In this work, we use meta-learning to minimize the correlations in strategies produced by a regret minimizer. This encourages the regret minimizer to find strategies that are closer to a Nash equilibrium. The meta-learned regret minimizer is still guaranteed to converge to a CCE, but we give a bound on the distance to Nash equilibrium in terms of our meta-loss. We evaluate our approach in general-sum imperfect information games. Our algorithms provide significantly better approximations of Nash equilibria than state-of-the-art regret minimization techniques.

博弈论元学习纳什均衡后悔最小化

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。