Regret Minimization Against Adaptive Opponents in Repeated Games

Forum topic · 小凯 · 2026-06-06

Summary

This paper studies regret minimization in repeated games where opponents are adaptive and can respond based on the history of play. Standard external regret fails to capture this adaptivity, so the authors introduce Repeated Policy Regret (RP-Regret), a game-theoretic metric that measures the gap between realized accumulated utility and the best-in-hindsight utility when all players are allowed to condition their actions on the full play history. They propose three algorithms to minimize RP-Regret under different conditions: one built on an optimization oracle, a convex linearization proxy approach, and a direct minimization method targeted at slowly varying opponent policies. The work connects equilibrium computation, online learning, and game-theoretic regret definitions, and is relevant to multi-agent learning, sequential decision-making, and mechanism design.

Paper Overview

Research Area: ML Authors: Mingyang Liu, Asuman Ozdaglar, Tiancheng Yu Release Date: 2025-06-11 arXiv: 2506.08285

Chinese Abstract

This paper studies regret minimization in repeated games with adaptive opponents. The standard external regret metric cannot capture this adaptivity. To address this, the authors introduce Repeated Policy Regret (RP-Regret), a game-theoretic metric that measures the difference between realized utility and the best-in-hindsight utility when all players can respond to the history of play. They propose three algorithms to minimize RP-Regret, including an algorithm based on an optimization oracle, a convex linearization proxy algorithm, and a direct minimization algorithm for opponents whose strategies change slowly.

Original Abstract

We study regret minimization in repeated games with adaptive opponents who can respond based on histories of play. We introduce Repeated Policy Regret (RP-Regret), a game-theoretic metric measuring the difference between realized and best-in-hindsight accumulated utility when all players can respond to the history of play. We propose three algorithms to minimize RP-Regret under different conditions.

--- *Auto-collected on 2025-06-11*

#paper #arXiv #ML