arXiv:2606.06486cs.LGcs.AI2026-06

提出新方法让博弈中应对对手变化的策略更优,提升合作效率。

Regret Minimization with Adaptive Opponents in Repeated Games

  • 引入可适应对手的重复博弈后悔度度量RP-Regret
  • 设计三类算法实现非凸空间下的后悔最小化
  • 在猎鹿等博弈中能达成更高收益的合作解

本文研究重复博弈中面对自适应对手时的后悔最小化问题。传统外部后悔度无法捕捉对手基于历史行为的响应。为此,我们提出重复策略后悔度(RP-Regret),衡量玩家在可响应历史的前提下,实际累积收益与事后最优策略之差。该度量天然适用于重复博弈,支持更强比较器和更宽松对手约束,并在所有玩家最小化时可导向更优均衡。我们识别出实现次线性RP-Regret所需的必要条件,包括比较策略变化率及对手记忆长度。进一步提出三种算法:(i) 基于优化查询的算法;(ii) 每轮最小化凸线性近似后悔度;(iii) 对手策略缓慢变化时直接最小化。当所有玩家采用此类算法时,可学习到某些子博弈完美均衡。实验表明,在猎鹿博弈等场景中,最小化该后悔度能获得更高收益的合作解。

原文摘要 · Abstract (English)

In this paper, we study regret minimization in repeated games with \emph{adaptive} opponents who can respond based on histories of play. The standard metric of \emph{external regret} in online learning is known to fail to capture such adaptivity. To account for players' counterfactual reasoning, we introduce {\tt Repeated Policy Regret (RP-Regret)}, a game-theoretic metric that measures the difference between the \emph{realized} and the \emph{best-in-hindsight} accumulated utility when all players can \emph{respond} to the history of play. Compared to existing regret notions in this setting, ours is native to repeated game playing, enabling stronger comparators and opponents with fewer constraints, while maintaining the possibility of finding better equilibria when all players minimize it. We first identify necessary conditions for obtaining {\tt RP-Regret} sublinear in time, on the variation of the player's comparator strategies in the regret definition and on the memories of both the comparator and opponents' strategies. We then study additional conditions and provable algorithms to minimize {\tt RP-Regret}, which is by definition \emph{non-convex} in the strategy space. To address this challenge, we propose three algorithms: (i) one based on an optimization oracle, as assumed in some prior work in online non-convex learning; (ii) one that minimizes a convex and \emph{linearized} surrogate of {\tt RP-Regret} at each iteration; (iii) one that directly minimizes {\tt RP-Regret} when opponents change strategies slowly. Furthermore, when all players can run algorithms to minimize the {\tt RP-Regret} (or its linearized variant), certain subgame perfect equilibria of the repeated game can be learned. We also provide experiments showing that minimizing our regret notions can lead to more cooperative solutions with higher utility in games such as Stag-Hunt.

博弈论在线学习后悔最小化重复博弈

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