Policy Gradient Methods Converge Globally in Imperfect-Information Extensive-Form Games

🕒 Published (v1): 2025-01-01 · Source: NeurIPS · Venue: NeurIPS 2025 · link

Ask a follow-up

Open an assistant pre-loaded with this paper's context.

💬 Ask ChatGPT✦ Ask Claude

TL;DR

This paper proves, for the first time, that regularized alternating policy gradient methods (with direct, softmax, and natural policy gradient parametrizations) converge globally to an ε-approximate Nash equilibrium in imperfect-information extensive-form games (IIEFGs), with iteration and sample complexity polynomial in 1/ε and game parameters. The key insight is that despite the nonconvexity of the policy optimization landscape, the utility satisfies a proximal Polyak-Łojasiewicz (pPŁ) condition via hidden concavity inherited from the sequence-form representation.

Problem

Prior MARL theory focused on Markov games, yet practical MARL successes (Poker, Stratego, Hanabi) occur in imperfect-information EFGs. Counterfactual regret minimization (CFR) algorithms fail to scale to neural-network policies due to high-variance importance sampling and average-iterate convergence. No prior work established polynomial-time convergence guarantees for policy gradient methods in IIEFGs—the nonconvexity of behavioral strategy space and failure of value iteration were the main obstacles.

Method

The approach exploits hidden concavity: utilities are concave in sequence-form strategies; composing with the bijection from behavioral policies to sequence-form strategies and applying bidilated regularization yields a function satisfying the proximal Polyak-Łojasiewicz (pPŁ) condition. A novel decentralized exploration scheme (each player independently flips a biased coin and with probability γ executes a uniformly-random sequence) guarantees sufficient infoset visitation and directly controls the pPŁ modulus. Three alternating (not simultaneous) update algorithms are analyzed: 1. Alt-RegPG: direct parametrization, Euclidean projection onto truncated simplices, L2 bidilated regularizer. 2. Alt-EntRegPG: softmax parametrization projected onto bounded polytope XR/ΘR, entropic bidilated regularizer. 3. Alt-RegNPG: natural policy gradient via Fisher-information preconditioning, equivalent to mirror descent with Mahalanobis norm; in policy space reduces to multiplicative-weight updates proportional to exp(ηQ).

Gradient estimation uses REINFORCE without importance sampling, possible because the bidilated regularizer's gradient can be estimated from trajectory rollouts directly. Convergence is proved via a Lyapunov function argument (not regret minimization), yielding last-iterate guarantees.

Key Contributions

• First polynomial-time last-iterate convergence guarantees for policy gradient in zero-sum IIEFGs (answering an open question).
• Proof that regularized IIEFG utilities satisfy the pPŁ condition via hidden concavity of sequence-form utilities.
• Novel decentralized exploration scheme (Assumption 2) that gives explicit, controllable gradient domination modulus—replacing distribution-mismatch coefficient assumptions common in MDP PG theory.
• Three convergent algorithms: Alt-RegPG (direct), Alt-EntRegPG (softmax), Alt-RegNPG (natural PG).
• Sharper dependence of the pPŁ modulus on the hidden convexity modulus than Karimi et al. (2016) for constrained optimization.
• Comparative analysis bridging IIEFG and Markov game theory structures.

Results

• All three algorithms attain ε-approximate NE in the last iterate in T = poly(1/ε, 1/ε, 1/γ, |H|, |S₁|, |S₂|, A, B, 2^{D(T)}) iterations (exponential in depth D(T) is polynomial in game size since D(T) is logarithmic in game size).
• Sample complexity per step: poly(1/ε, 1/ε, 1/γ, |H|, |S₁|, |S₂|, A, B, 2^{D(T)}) trajectories.
• Empirical validation on Kuhn Poker, Leduc Poker, 2×2 Abrupt Dark Hex, and Liar's Dice: exploitability diminishes over time for Alt-RegNPG variants; performance is competitive with CFR and magnetic mirror descent (MMD).
• Prior best (Liu et al., 2024): best-iterate convergence only, pseudo-polynomial in game size; Sokota et al. (2022): no convergence guarantee, empirical only.

Limitations

• Convergence rates are acknowledged to be loose; constants and dependence on game parameters likely improvable.
• Requires mini-batching (multiple trajectory samples per iteration); no single-sample or variance-reduction guarantees.
• The ε-truncation assumption (Assumption 1) must be enforced explicitly, adding algorithmic overhead.
• Exploration parameter γ introduces a polynomial blowup in iteration complexity; optimal γ tuning is not fully characterized.
• Analysis limited to two-player zero-sum perfect-recall IIEFGs; extension to general-sum or imperfect-recall games is open.
• Limit-point behavior of (unregularized) policy gradient in IIEFGs remains open.

Relevance to Agentic AI / LLM Agents

Policy gradient methods—especially NPG/PPO/TRPO—are the backbone of RLHF and multi-agent LLM training, yet their theoretical properties in partially-observable, multi-agent settings (which mirror IIEFGs more than Markov games) have been poorly understood. This paper's proof that alternating policy gradient converges polynomially in IIEFGs directly strengthens the theoretical foundation for training competitive or cooperative LLM agents in strategic, partially-observable environments. The connection between the bidilated entropic regularizer and MDP discounted entropy regularization (used in soft-actor-critic, RLHF KL penalties) suggests these convergence results may transfer to LLM fine-tuning regimes. For researchers building multi-agent LLM systems that interact strategically (negotiation, debate, game-playing), this establishes that vanilla gradient-based self-play has provable equilibrium-finding guarantees without requiring CFR-style value iteration.