Projected Exploitability Descent for Nash Equilibrium Computation in Multiplayer Imperfect-Information Games

• URL: http://arxiv.org/abs/2606.29169v1
• Date: Sun, 28 Jun 2026 03:25:15 GMT
• Title: Projected Exploitability Descent for Nash Equilibrium Computation in Multiplayer Imperfect-Information Games
• Abstract summary: We introduce a new algorithm called projected exploitability descent (PED)<n>PED works by running a subgradient descent minimizing a generalized exploitability function.<n>We find that PED obtains a consistent near-monotonic improvement throughout all runs.<n>This inspires a hybrid FP-PED that runs FP for an initial burn-in period before switching to PED for stable long-run refinement.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Many important games have more than two players and imperfect information. Existing approaches for computing Nash equilibrium, the central game-theoretic solution concept, in such games either lack scalability or obtain poor performance. In this paper we introduce a new algorithm called projected exploitability descent (PED) for approximating Nash equilibria in multiplayer games of imperfect information. The algorithm works by running projected subgradient descent minimizing a proxy for the multiplayer generalized exploitability function. The objective is nonconvex and nonsmooth, but can be represented as the sum of the maxima of linear functions, for which a subgradient can easily be computed and projected to the polytope of feasible sequence-form strategies. We explore performance of PED on a generalized version of the well-studied benchmark game three-player Kuhn poker. No prior exact algorithms scale to the version of the game with deck size larger than 4, and we compare performance to the popular algorithms of fictitious play (FP) and counterfactual regret minimization (CFR). We find that PED obtains a consistent near-monotonic improvement throughout all runs, though both FP and CFR perform significantly better in the initial iterations. This inspires a hybrid algorithm FP-PED that runs FP for an initial burn-in period before switching to PED for stable long-run refinement. We can alternatively view this as a multi-step algorithm that runs FP as a pre-processing step to obtain a strong initialization for PED.

Related papers

• Quadratic Programming Approach for Nash Equilibrium Computation in Multiplayer Imperfect-Information Games [0.0]
  We present an approach to approximation in multiplayer imperfectinformation games that solves a quadratically-constrained program based on a nonlinear approximation.<n>We also lead to a new approach for computing Nash equilibrium in multiplayer strategic-form games.
  arXiv  Detail & Related papers  (2025-09-30T00:28:21Z)
• Reevaluating Policy Gradient Methods for Imperfect-Information Games [94.45878689061335]
  We conduct the largest-ever exploitability comparison of DRL algorithms for imperfect-information games.<n>We find that FP-, DO-, and CFR-based approaches fail to outperform generic policy gradient methods.
  arXiv  Detail & Related papers  (2025-02-13T03:38:41Z)
• Efficiently Solving Turn-Taking Stochastic Games with Extensive-Form Correlation [52.16923999754027]
  We give an algorithm for computing a Stackelberg extensive-form correlated equilibrium.<n>We also give an efficient algorithm for approximately computing an optimal extensive-form correlated equilibrium.<n>Our algorithm for approximately optimal EFCE is, to our knowledge, the first that achieves 3 desiderata simultaneously.
  arXiv  Detail & Related papers  (2024-12-22T09:12:05Z)
• Planning and Learning with Adaptive Lookahead [74.39132848733847]
  Policy Iteration (PI) algorithm alternates between greedy one-step policy improvement and policy evaluation. Recent literature shows that multi-step lookahead policy improvement leads to a better convergence rate at the expense of increased complexity per iteration. We propose for the first time to dynamically adapt the multi-step lookahead horizon as a function of the state and of the value estimate.
  arXiv  Detail & Related papers  (2022-01-28T20:26:55Z)
• Anytime Optimal PSRO for Two-Player Zero-Sum Games [17.821479538423155]
  Policy Space Response Oracles (PSRO) is a reinforcement learning algorithm for games that can handle continuous actions. AODO is a double oracle algorithm for 2-player zero-sum games that converges to a Nash equilibrium. We show that our methods achieve far lower exploitability than DO and PSRO and never increase exploitability.
  arXiv  Detail & Related papers  (2022-01-19T16:34:11Z)
• Last-iterate Convergence in Extensive-Form Games [49.31256241275577]
  We study last-iterate convergence of optimistic algorithms in sequential games. We show that all of these algorithms enjoy last-iterate convergence, with some of them even converging exponentially fast.
  arXiv  Detail & Related papers  (2021-06-27T22:02:26Z)
• Minimax Optimization with Smooth Algorithmic Adversaries [59.47122537182611]
  We propose a new algorithm for the min-player against smooth algorithms deployed by an adversary. Our algorithm is guaranteed to make monotonic progress having no limit cycles, and to find an appropriate number of gradient ascents.
  arXiv  Detail & Related papers  (2021-06-02T22:03:36Z)
• Sparsified Linear Programming for Zero-Sum Equilibrium Finding [89.30539368124025]
  We present a totally different approach to the problem, which is competitive and often orders of magnitude better than the prior state of the art. With experiments on poker endgames, we demonstrate, for the first time, that modern linear program solvers are competitive against even game-specific modern variants of CFR.
  arXiv  Detail & Related papers  (2020-06-05T13:48:26Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.