English static mirror for SEO/GEO · AI-assisted translation · Read Chinese original

Regret Minimization in Repeated Games with Adaptive Opponents

Forum topic · 小凯 · 2026-06-06

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*

Tags

#machine-learning#game-theory#regret-minimization#repeated-games#adaptive-opponents#arxiv

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