Cover Image

Computational Lower Bounds for Regret Minimization in Normal-Form Games

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Anagnostides, Ioannis, Kalavasis, Alkis, Sandholm, Tuomas
Format:	Preprint
Published:	2024
Subjects:	Computer Science and Game Theory Machine Learning
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

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

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)

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

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

Convergence of Regret Matching in Potential Games and Constrained Optimization
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)

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

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

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

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

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

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

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

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

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)

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

Parallelizing Counterfactual Regret Minimization
by: Kim, Juho, et al.
Published: (2026)

Swap Regret and Correlated Equilibria Beyond Normal-Form Games
by: Arunachaleswaran, Eshwar Ram, et al.
Published: (2025)

Optimal Correlated Equilibria in General-Sum Extensive-Form Games: Fixed-Parameter Algorithms, Hardness, and Two-Sided Column-Generation
by: Zhang, Brian, et al.
Published: (2022)

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

On the Power of Perturbation under Sampling in Solving Extensive-Form Games
by: Masaka, Wataru, et al.
Published: (2025)

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

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

Tight Regret Upper and Lower Bounds for Optimistic Hedge in Two-Player Zero-Sum Games
by: Tsuchiya, Taira
Published: (2025)

Regret Minimization in Stackelberg Games with Side Information
by: Harris, Keegan, et al.
Published: (2024)

On the Optimality of Dilated Entropy and Lower Bounds for Online Learning in Extensive-Form Games
by: Fan, Zhiyuan, et al.
Published: (2024)

On the Learning Curves of Revenue Maximization
by: Hanneke, Steve, et al.
Published: (2026)

Solving Infinite-Player Games with Player-to-Strategy Networks
by: Martin, Carlos, et al.
Published: (2025)

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

Mediator Interpretation and Faster Learning Algorithms for Linear Correlated Equilibria in General Extensive-Form Games
by: Zhang, Brian Hu, et al.
Published: (2023)

On the Outcome Equivalence of Extensive-Form and Behavioral Correlated Equilibria
by: Zhang, Brian Hu, et al.
Published: (2024)

ApproxED: Approximate exploitability descent via learned best responses
by: Martin, Carlos, et al.
Published: (2023)

Watermarking Game-Playing Agents in Perfect-Information Extensive-Form Games
by: Kim, Juho, et al.
Published: (2026)

On the Limitations and Possibilities of Nash Regret Minimization in Zero-Sum Matrix Games under Noisy Feedback
by: Maiti, Arnab, et al.
Published: (2023)

GPU-Accelerated Counterfactual Regret Minimization
by: Kim, Juho
Published: (2024)

Regret Minimization and Convergence to Equilibria in General-sum Markov Games
by: Erez, Liad, et al.
Published: (2022)

Equilibrium Refinements Improve Subgame Solving in Imperfect-Information Games
by: Kubicek, Ondrej, et al.
Published: (2026)

Meta-Learning in Self-Play Regret Minimization
by: Sychrovský, David, et al.
Published: (2025)

Regret Minimization in Bilateral Trade With Perturbed Markets
by: Lunghi, Anna, et al.
Published: (2026)

Domain-Independent Game Abstraction using Word Embedding Techniques
by: Kim, Juho, et al.
Published: (2026)