Regret Minimization with Adaptive Opponents in Repeated Games
Summary
This paper introduces Repeated Policy Regret (RP-Regret), a game-theoretic metric for regret minimization in repeated games with adaptive opponents, and proposes three algorithms to minimize it, showing that doing so can lead to cooperative equilibria like in Stag-Hunt.
View Cached Full Text
Cached at: 06/05/26, 10:10 PM
Paper page - Regret Minimization with Adaptive Opponents in Repeated Games
Source: https://huggingface.co/papers/2606.06486
Abstract
Repeated policy regret provides a game-theoretic framework for analyzing adaptive opponents in repeated games, offering stronger equilibrium guarantees than traditional external regret through novel non-convex optimization algorithms.
In this paper, we studyregret minimizationinrepeated gameswithadaptive opponentswho can respond based on histories of play. The standard metric ofexternal regretin online learning is known to fail to capture such adaptivity. To account for players’ counterfactual reasoning, we introduce {\ttRepeated Policy Regret(RP-Regret)}, a game-theoretic metric that measures the difference between the realized and the best-in-hindsight accumulated utility when all players can 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 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 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), certainsubgame perfect equilibriaof 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.
View arXiv pageView PDFAdd to collection
Get this paper in your agent:
hf papers read 2606\.06486
Don’t have the latest CLI?curl \-LsSf https://hf\.co/cli/install\.sh \| bash
Models citing this paper0
No model linking this paper
Cite arxiv.org/abs/2606.06486 in a model README.md to link it from this page.
Datasets citing this paper0
No dataset linking this paper
Cite arxiv.org/abs/2606.06486 in a dataset README.md to link it from this page.
Spaces citing this paper0
No Space linking this paper
Cite arxiv.org/abs/2606.06486 in a Space README.md to link it from this page.
Collections including this paper0
No Collection including this paper
Add this paper to acollectionto link it from this page.
Similar Articles
A3M: Adaptive, Adversarial and Multi-Objective Learning for Strategic Bidding in Repeated Auctions
Introduces A3M, a framework combining adaptive deep reinforcement learning, adversarial reasoning, and multi-objective reward design for strategic bidding in repeated auctions, achieving 30-40% regret reduction.
Provably Optimal Learning Algorithms for Assistance Games
This paper introduces an online variant of assistance games and provides the first provably efficient learning algorithms for both the human and assistant agents, achieving near-optimal regret bounds.
Toward Optimal Switching Regret for Multi-Armed Bandits with Oblivious Adversary
This paper resolves an open problem by showing that a single algorithm achieves optimal switching regret for every S against an oblivious adversary in multi-armed bandits.
Emergence of Exploration in Policy Gradient Reinforcement Learning via Retrying
This paper introduces ReMax, a new objective for reinforcement learning that induces exploration as an emergent property by evaluating policies based on expected maximum return over multiple samples, without explicit exploration bonuses. The authors derive a policy gradient formulation and propose RePPO, a PPO variant that achieves efficient exploration on MinAtar and Craftax benchmarks.
Dynamic Regret for Non-Stationary Linear Bandits via Misspecification Reductions
This paper proposes a unified misspecification-reduction viewpoint for non-stationary linear bandits with round-specific feasible decision sets, achieving optimal dynamic regret without the restrictive orthogonal-structure assumption.