Research map / Reinforcement learning / Policy gradient and actor-critic
Optimistic Policy Gradient in Multi-Player Markov Games with a Single Controller: Convergence beyond the Minty Property
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.
Introduces a generalized Minty property and shows optimistic policy gradient converges to stationary epsilon-NE in multi-player Markov games with a single controller that exhibit equilibrium collapse, in O(1/eps^2) iterations.
Problem
Convergence of policy gradient methods to stationary Nash equilibria in multi-player Markov games, beyond two-player zero-sum and potential games, where the classical Minty property fails even for simple two-player single-controller Markov games (Von Neumann ratio game).
Approach
Generalizes the Minty property by distorting the operator with a componentwise weight function A and a weight W evaluated at the reference point, and relaxes pointwise guarantee to an average (sum over iterations) guarantee. Optimistic gradient descent with the weighted operator then converges to approximate strong solutions; for single-controller Markov games with equilibrium collapse, the condit
Key results
- OGD with weighted operator reaches an epsilon-approximate strong solution after T = O(1/epsilon^2) iterations under the average generalized Minty property.
- For multi-player Markov games with a single controller and equilibrium collapse, the method computes a stationary epsilon-NE in 1/epsilon^2 * poly(n, sum|A_i|, |S|, 1/zeta, C_G, 1/||rho||_inf) iterations.
- Polymatrix zero-sum Markov games with switching controllers satisfy the average generalized Minty-type condition (Assumption 2) and the ratio game satisfies the generalized Minty property despite violating the classical Minty property.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Assume both equilibrium collapse and a single controller | Optimistic policy gradient in multi-player Markov games · Multi-player Markov games | iterations to stationary ε-NE: 1/ε^2 · poly(n, ∑_{i=1}^n |A_i|, |S|, 1/ζ, C_G, 1/||ρ||_∞) | Helped |
| Use the average generalized Minty property with a weighted optimistic gradient update | Optimistic gradient descent · Variational inequality problems | iterations to an ε-approximate strong solution: O_ε(1/ε^2) | Helped |
Surprising findings
- Equilibrium collapse alone does not suffice for efficient computation of stationary NE; the single-controller structure is additionally needed.
Limitations
- Relies on product structure of joint strategy space and a single controller; hardness results suggest the assumption cannot be broadly relaxed.
- Requires access to the state visitation distribution (weights A) to run the update, estimated via the environment.
Experimental setup
Metrics: epsilon-Nash equilibrium gap equilibrium gap of iterates
Baselines: vanilla policy gradient with constant learning rate
Builds on: Minty property optimistic gradient descent optimistic mirror descent regret (RVU) Daskalakis et al. 2020 independent policy gradient in ratio game
Closest papers by meaning
- Independent Policy Gradient for Large-Scale Markov Potential Games: Sharper Rates, Function Approximation, and Game-Agnostic Convergence (ICML 2022 · similarity 0.93)
- Policy Optimization for Markov Games: Unified Framework and Faster Convergence (NeurIPS 2022 · similarity 0.93)
- Global Convergence of Multi-Agent Policy Gradient in Markov Potential Games (ICLR 2022 · similarity 0.93)
- Solving Zero-Sum Convex Markov Games (ICML 2025 · similarity 0.92)
- A Policy-Gradient Approach to Solving Imperfect-Information Games with Best-Iterate Convergence (ICLR 2025 · similarity 0.91)
- Learning Equilibria in Adversarial Team Markov Games: A Nonconvex-Hidden-Concave Min-Max Optimization Problem (NeurIPS 2024 · similarity 0.90)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.