Cover Image

Convergence of Regret Matching in Potential Games and Constrained Optimization

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Anagnostides, Ioannis, Tewolde, Emanuel, Zhang, Brian Hu, Panageas, Ioannis, Conitzer, Vincent, Sandholm, Tuomas
Format:	Preprint
Published:	2025
Subjects:	Computer Science and Game Theory Machine Learning Optimization and Control
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Expected Variational Inequalities
by: Zhang, Brian Hu, et al.
Published: (2025)

Scale-Invariant Regret Matching and Online Learning with Optimal Convergence: Bridging Theory and Practice in Zero-Sum Games
by: Zhang, Brian Hu, et al.
Published: (2025)

Last-Iterate Convergence: Zero-Sum Games and Constrained Min-Max Optimization
by: Daskalakis, Constantinos, et al.
Published: (2018)

A Polynomial-Time Algorithm for Variational Inequalities under the Minty Condition
by: Anagnostides, Ioannis, et al.
Published: (2025)

(Doubly) Exponential Lower Bounds for Follow the Regularized Leader in Potential Games
by: Anagnostides, Ioannis, et al.
Published: (2026)

Computational Lower Bounds for Regret Minimization in Normal-Form Games
by: Anagnostides, Ioannis, et al.
Published: (2024)

The Complexity of Symmetric Equilibria in Min-Max Optimization and Team Zero-Sum Games
by: Anagnostides, Ioannis, et al.
Published: (2025)

Learning and Computation of $Φ$-Equilibria at the Frontier of Tractability
by: Zhang, Brian Hu, et al.
Published: (2025)

The Complexity of Equilibrium Refinements in Potential Games
by: Anagnostides, Ioannis, et al.
Published: (2025)

Convergence of $\text{log}(1/ε)$ for Gradient-Based Algorithms in Zero-Sum Games without the Condition Number: A Smoothed Analysis
by: Anagnostides, Ioannis, et al.
Published: (2024)

Barriers to Welfare Maximization with No-Regret Learning
by: Anagnostides, Ioannis, et al.
Published: (2024)

Efficient $Φ$-Regret Minimization with Low-Degree Swap Deviations in Extensive-Form Games
by: Zhang, Brian Hu, et al.
Published: (2024)

On the Interplay between Social Welfare and Tractability of Equilibria
by: Anagnostides, Ioannis, et al.
Published: (2023)

Decision Making under Imperfect Recall: Algorithms and Benchmarks
by: Tewolde, Emanuel, et al.
Published: (2026)

The Value of Recall in Extensive-Form Games
by: Berker, Ratip Emin, et al.
Published: (2024)

The Complexity of Proper Equilibrium in Extensive-Form and Polytope Games
by: Zhang, Brian Hu, et al.
Published: (2026)

Steering No-Regret Learners to a Desired Equilibrium
by: Zhang, Brian Hu, et al.
Published: (2023)

On the Complexity of Correlated Equilibria Beyond Normal-Form Games
by: Anagnostides, Ioannis, et al.
Published: (2026)

Global Convergence of Multi-Agent Policy Gradient in Markov Potential Games
by: Leonardos, Stefanos, et al.
Published: (2021)

Position: Machine Learning for Heart Transplant Allocation Policy Optimization Should Account for Incentives
by: Anagnostides, Ioannis, et al.
Published: (2026)

Last-iterate Convergence Separation between Extra-gradient and Optimism in Constrained Periodic Games
by: Feng, Yi, et al.
Published: (2024)

Polynomial Convergence of Bandit No-Regret Dynamics in Congestion Games
by: Dadi, Leello, et al.
Published: (2024)

Doubly Optimal No-Regret Online Learning in Strongly Monotone Games with Bandit Feedback
by: Ba, Wenjia, et al.
Published: (2021)

On the tractability of Nash equilibrium
by: Avramopoulos, Ioannis
Published: (2023)

Computing Optimal Equilibria and Mechanisms via Learning in Zero-Sum Extensive-Form Games
by: Zhang, Brian Hu, et al.
Published: (2023)

Weakest Bidder Types and New Core-Selecting Combinatorial Auctions
by: Prasad, Siddharth, et al.
Published: (2025)

Faster Rates for No-Regret Learning in General Games via Cautious Optimism
by: Soleymani, Ashkan, et al.
Published: (2025)

Achieving Logarithmic Regret in KL-Regularized Zero-Sum Markov Games
by: Nayak, Anupam, et al.
Published: (2025)

Cautious Optimism: A Meta-Algorithm for Near-Constant Regret in General Games
by: Soleymani, Ashkan, et al.
Published: (2025)

Adaptive, Doubly Optimal No-Regret Learning in Strongly Monotone and Exp-Concave Games with Gradient Feedback
by: Jordan, Michael I., et al.
Published: (2023)

Team Belief DAG: Generalizing the Sequence Form to Team Games for Fast Computation of Correlated Team Max-Min Equilibria via Regret Minimization
by: Zhang, Brian Hu, et al.
Published: (2022)

Fast Last-Iterate Convergence of Learning in Games Requires Forgetful Algorithms
by: Cai, Yang, et al.
Published: (2024)

An Exponentially Converging Particle Method for the Mixed Nash Equilibrium of Continuous Games
by: Wang, Guillaume, et al.
Published: (2022)

Game Transformations That Preserve Nash Equilibria or Best-Response Sets
by: Tewolde, Emanuel, et al.
Published: (2021)

A Lower Bound on Swap Regret in Extensive-Form Games
by: Daskalakis, Constantinos, et al.
Published: (2024)

On Characterizations of Potential and Ordinal Potential Games
by: Arefizadeh, Sina, et al.
Published: (2024)

On Separation Between Best-Iterate, Random-Iterate, and Last-Iterate Convergence of Learning in Games
by: Cai, Yang, et al.
Published: (2025)

From Average-Iterate to Last-Iterate Convergence in Games: A Reduction and Its Applications
by: Cai, Yang, et al.
Published: (2025)

Exponential Lower Bounds on the Double Oracle Algorithm in Zero-Sum Games
by: Zhang, Brian Hu, et al.
Published: (2024)

Constrained Policy Optimization for Provably Fair Order Matching
by: Cheng, Zehua, et al.
Published: (2026)