Research map / Learning theory and algorithms / Submodular and game algorithms

Rapid Learning in Constrained Minimax Games with Negative Momentum

AAAI 2025 · Learning theory and algorithms › Submodular and game algorithms · approach: Zero-sum game learning dynamics · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Extends negative momentum from unconstrained GDA to constrained minimax games via a restarting aggregated momentum buffer applied to mirror descent, FTRL, RM+ and CFR+ (MoCFR+, DMoGDA), with convergence theory for entropy regularization and strong empirical gains on NFGs and EFGs.

Problem

Negative momentum has been studied only for unconstrained minimax games with GDA; its use in constrained games and with game-solver algorithms (RM+, CFR+) for solving NFGs and EFGs is unexplored, and existing last-iterate methods are costly or slow in large games.

Approach

Keep a momentum buffer in the dual space with negative coefficient, aggregate snapshots of the buffer over a restart window k, and use it as an attachment point (spring-like restoring force) inside mirror descent, FTRL, RM+ and CFR+ updates, giving momentum-augmented versions of classic game solvers.

Key results

• MoRM+ and MoCFR+ consistently reach about 10^9 times lower exploitability than RM+ and CFR+ respectively, according to the paper's claim.
• MoCFR+ outperforms PCFR+ and CFR+ across the tested EFGs, and DMoGDA outperforms all baselines by a considerable margin in larger games.
• MoRM+ overcomes the slow ergodic convergence of RM+ on the 3x3 matrix game with unique NE.

Measured effects reported in the paper

Surprising findings

• GDA-type algorithms (DMoGDA) outperform state-of-the-art CFR variants in larger games, which the authors describe as a first.

Limitations

• Theoretical guarantees are proven for entropy-regularized variants and a restricted setting; the trade-off between the bias of the modified equilibrium and convergence speed is governed by beta.
• Hyperparameters (eta, beta, k) are tuned by grid search per game, and the optimal restart interval depends on learning rate and beta.

Experimental setup

Datasets: randomly generated normal-form games (sizes 25, 50, 75) Kuhn Poker Leduc Poker Goofspiel-4 Goofspiel-5 Liar's dice-4 Liar's dice-5

Benchmarks: 3x3 bias matrix game random normal-form games (25, 50, 75) Kuhn Poker Leduc Poker Goofspiel-4 Goofspiel-5 Liar's dice-4 Liar's dice-5

Metrics: exploitability (duality gap)

Baselines: RM RM+ OMWU OGDA MMD-A MMD-M CFR CFR+ PCFR+ Reg-CFR Reg-DOGDA

Builds on: negative momentum regret matching+ counterfactual regret minimization magnetic mirror descent optimistic gradient descent ascent

Closest papers by meaning

• Continuous-Time Analysis of Heavy Ball Momentum in Min-Max Games (ICML 2025 · similarity 0.89)
• Accelerated Regularized Learning in Finite N-Person Games (NeurIPS 2024 · similarity 0.87)
• Learning Equilibria in Adversarial Team Markov Games: A Nonconvex-Hidden-Concave Min-Max Optimization Problem (NeurIPS 2024 · similarity 0.87)
• Solving Neural Min-Max Games: The Role of Architecture, Initialization & Dynamics (NeurIPS 2025 · similarity 0.86)
• Boosting Perturbed Gradient Ascent for Last-Iterate Convergence in Games (ICLR 2025 · similarity 0.86)
• Efficient Learning in Polyhedral Games via Best-Response Oracles (AAAI 2024 · similarity 0.86)