Regret Minimization Against Adaptive Opponents in Repeated Games

Forum topic · 小凯 · 2026-06-06

Summary

This arXiv paper (2506.08285) by Mingyang Liu, Asuman Ozdaglar, and Tiancheng Yu, published on June 11, 2025, studies regret minimization in repeated games where opponents are adaptive and can respond to the history of play. Standard external regret fails to capture such adaptability. The authors introduce Repeated Policy Regret (RP-Regret), a game-theoretic metric measuring the gap between realized accumulated utility and the best-in-hindsight accumulated utility when all players can respond to history. They propose three algorithms to minimize RP-Regret under different conditions: an algorithm based on an optimization oracle, a convex linearization surrogate approach, and a direct minimization method for opponents whose strategies change slowly. The work extends classical regret analysis to settings where strategic adaptation matters, providing both theoretical metrics and practical algorithmic tools for learning in repeated games with responsive participants.

Paper Overview

Field: Machine Learning Authors: Mingyang Liu, Asuman Ozdaglar, Tiancheng Yu Published: 2025-06-11 arXiv: 2506.08285

Abstract

We study regret minimization in repeated games with adaptive opponents who can respond based on histories of play. Standard external regret measures fail to capture this adaptability. To address this, we introduce Repeated Policy Regret (RP-Regret), a game-theoretic metric measuring the difference between realized accumulated utility and the best-in-hindsight accumulated utility when all players can respond to the history of play.

Algorithms Proposed

The paper presents three algorithms to minimize RP-Regret under different conditions:

1. Optimization-oracle-based algorithm — leveraging an optimization oracle for the minimization task. 2. Convex linearization surrogate algorithm — using convex surrogate objectives. 3. Direct minimization algorithm — designed for opponents whose strategies change slowly over time.

Significance

By introducing RP-Regret, the authors extend regret analysis beyond external regret to settings where strategic adaptation by all players is possible, offering a more faithful benchmark for performance in repeated games with responsive opponents.

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