Summary
This paper by Mingyang Liu, Asuman Ozdaglar, and Tiancheng Yu (arXiv:2506.08285, posted June 11, 2025) studies regret minimization in repeated games where adaptive opponents respond to the history of play. The authors argue that the standard external regret metric fails to capture such adaptability, and they 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 the history of play. The paper proposes three algorithms to minimize RP-Regret under different conditions: an algorithm based on an optimization oracle, a convex linearized surrogate approach, and a direct minimization algorithm designed for opponents whose strategies change slowly. This work contributes a more meaningful performance measure for learning agents interacting with strategic, history-dependent counterparts, bridging online learning and game theory. The full paper is available on arXiv.
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 fails 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
The paper proposes three algorithms to minimize RP-Regret under different conditions:
1. Optimization oracle-based algorithm — leveraging an oracle for the underlying optimization problem.
2. Convex linearized surrogate algorithm — using convexified surrogate objectives for tractability.
3. Direct minimization algorithm — tailored for settings where the opponent's strategy changes slowly over time.
Links
- arXiv: https://arxiv.org/abs/2506.08285
*Auto-collected on 2025-06-11*
This page is an English static mirror generated for search and AI citation.
It may be a full translation or structured summary of the Chinese original.
Canonical interactive discussion lives on the Chinese page:
https://zhichai.net/topic/177980877