Corrupted Learning Dynamics In Games

Abstract

Learning in games refers to scenarios where multiple players interact in a shared environment, each aiming to minimize their regret. An equilibrium can be computed at a fast rate of \(O(1/T)\) when all players follow the optimistic follow-the-regularized-leader (OFTRL). However, this acceleration is limited to the honest regime, in which all players adhere to a prescribed algorithm -- a situation that may not be realistic in practice. To address this issue, we present corrupted learning dynamics that adaptively find an equilibrium at a rate that depends on the extent to which each player deviates from the strategy suggested by the prescribed algorithm. First, in two-player zero-sum corrupted games, we provide learning dynamics for which the external regret of \(x\)-player (and similarly for \(y\)-player) is roughly bounded by \(O(log (m_x m_y) + \sqrt\{\hat\{C\}_y\} + \hat\{C\}_x)\), where \(m_x\) and \(m_y\) denote the number of actions of \(x\)- and \(y\)-players, respectively, and \

Stats

• citations0
• S2 citations—
• github stars0
• HF likes0
• heat score0.00
• arxiv keytsuchiya2024corrupted

Related papers

• Uncoupled Learning Dynamics With \(o(\log T)\) Swap Regret In Multiplayer Games (2022)0.00
• Corruption-robust Offline Two-player Zero-sum Markov Games (2024)0.00
• On The Complexity Of Computing Sparse Equilibria And Lower Bounds For No-regret Learning In Games (2023)0.00
• Simple Uncoupled No-regret Learning Dynamics For Extensive-form Correlated Equilibrium (2021)6.34
• Near Optimal Convergence To Coarse Correlated Equilibrium In General-sum Markov Games (2025)0.00
• Learning In Multi-memory Games Triggers Complex Dynamics Diverging From Nash Equilibrium (2023)0.00
• Adversarial Learning In Games With Bandit Feedback: Logarithmic Pure-strategy Maximin Regret (2026)0.00
• Impact Of Decentralized Learning On Player Utilities In Stackelberg Games (2024)0.00