这篇论文为多智能体博弈场景提供了更合理的遗憾度量，做强化学习、博弈论或多智能体系统的研究者值得关注，它可能改变你对自适应对手环境下算法设计的理解。
这篇论文针对重复博弈中自适应对手（能根据历史调整策略）的遗憾最小化问题，提出了一个新的博弈论指标——重复策略遗憾（RP-Regret）。该指标衡量所有玩家都能根据历史响应时，实际累积效用与事后最优效用之间的差距，比现有指标更贴合重复博弈场景，且约束更少。研究发现，要实现 RP-Regret 随时间次线性增长，需要满足玩家比较策略和对手策略记忆的特定条件。论文提出了三种算法来最小化非凸的 RP-Regret，包括基于优化 oracle、凸线性化代理以及直接最小化（当对手变化缓慢时）。当所有玩家都运行这些算法时，可以学习到重复博弈的某些子博弈完美均衡。实验表明，最小化 RP-Regret 能在 Stag-Hunt 等博弈中引导出更合作、效用更高的解。
Regret Minimization with Adaptive Opponents in Repeated Games
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.