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

Learning Equilibria in Adversarial Team Markov Games: A Nonconvex-Hidden-Concave Min-Max Optimization Problem

NeurIPS 2024 · Learning theory and algorithms › Submodular and game algorithms · approach: Zero-sum game learning dynamics · 1 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.

Proposes ISPNG, an independent bandit-feedback policy-gradient algorithm that learns epsilon-Nash equilibria in infinite-horizon adversarial team Markov games via a nonconvex-hidden-concave min-max reformulation and new weakly-smooth nonconvex SGD results.

Problem

Learning Nash equilibria in infinite-horizon adversarial team Markov games (ATMGs) with only bandit feedback and independent learning, where the min-max objective is nonconvex-nonconcave and the feasible set has coupled constraints.

Approach

Regularize the adversary's value with a quadratic penalty on its state-action visitation measure so the max over the adversary's occupancy measure is differentiable with Hölder-continuous gradient; then run inexact stochastic projected gradient descent on this weakly-smooth nonconvex function, with the adversary best-responding via visitation-regularized policy gradient.

Key results

• Provides the first learning algorithm (ISPNG) that computes an epsilon-Nash equilibrium in ATMGs with iteration and sample complexity polynomial in 1/epsilon and game parameters, avoiding exponential dependence on the number of agents.
• Shows the gradient of the regularized max function is (1/2)-Hölder continuous with constant O(1/nu), enabling convergence of inexact stochastic PGD for weakly-smooth nonconvex functions.
• Establishes convergence to an epsilon-saddle point for nonconvex-hidden-strongly-concave functions with T = O(1/(nu^2 eps^3)) maximization oracle calls.

Limitations

• Convergence relies on batch sampling of gradients; sample complexity not improved by variance reduction.
• Requires a regularization coefficient nu that must be carefully tuned, and the learning dynamics use turn-taking rather than fully simultaneous updates.
• Analysis is theoretical; no empirical experiments reported.

Experimental setup

Metrics: epsilon-Nash equilibrium gap iteration complexity sample complexity

Baselines: Kalogiannis et al. (2023) equilibrium computation for ATMGs

Builds on: Markov potential games policy gradient Danskin's theorem REINFORCE convex RL visitation measure estimator

Closest papers by meaning

• Efficiently Computing Nash Equilibria in Adversarial Team Markov Games (ICLR 2023 · similarity 0.94)
• Solving Zero-Sum Convex Markov Games (ICML 2025 · similarity 0.92)
• Optimistic Policy Gradient in Multi-Player Markov Games with a Single Controller: Convergence beyond the Minty Property (AAAI 2024 · similarity 0.90)
• Constrained Exploitability Descent: An Offline Reinforcement Learning Method for Finding Mixed-Strategy Nash Equilibrium (ICML 2025 · similarity 0.90)
• Learning Nash Equilibrium of Markov Potential Games with a Shared Constraint via Primal-Dual Optimization (AAAI 2025 · similarity 0.90)
• Solving Neural Min-Max Games: The Role of Architecture, Initialization & Dynamics (NeurIPS 2025 · similarity 0.90)