Block-Coordinate Methods and Restarting for Solving Extensive-Form Games

Darshan Chakrabarti, Jelena Diakonikolas, Christian Kroer

Abstract

Extensive-form games (EFGs) provide a robust framework for modeling sequential interactions with imperfect information. Solving these games typically involves finding a Nash equilibrium, formulated as a bilinear saddle-point problem over a non-separable strategy space known as a treeplex. Traditional first-order methods require full game tree traversals for every update, while standard coordinate descent methods struggle with the hierarchical constraints of the treeplex. This paper introduces the Extrapolated Cyclic Primal-Dual Algorithm (ECyclicPDA), a cyclic coordinate-descent method tailored for EFGs. By integrating a novel adaptive restarting heuristic, the method achieves an $O(1/T)$ convergence rate and demonstrates superior performance over state-of-the-art solvers like CFR+ on several benchmarks.

Introduction

In the study of multi-agent systems, extensive-form games (EFGs) are the standard model for sequential competition involving private information, such as Poker or Battleship. Finding a Nash equilibrium in these games is computationally intensive because large games possess massive strategy trees. The optimization is typically framed as a bilinear saddle-point problem over the "sequence-form" strategy space.

A significant bottleneck in solving these problems is the scale of the strategy space. Standard first-order methods, such as Mirror Prox, require a full traversal of the entire game tree to perform a single gradient update. While coordinate descent methods—which update only a subset of variables at a time—have revolutionized large-scale machine learning, they are difficult to apply to EFGs. This is because EFG strategy spaces, or treeplexes, are non-separable: a decision made at the root of the tree fundamentally constrains all downstream actions. Consequently, local updates often violate global feasibility constraints, making efficient block-wise updates theoretically and practically challenging.

Methodology

The ECyclicPDA Algorithm

The authors propose the Extrapolated Cyclic Primal-Dual Algorithm (ECyclicPDA) to overcome the limitations of non-separability. The algorithm introduces several key innovations:

  1. Pseudo-Block Updates: Rather than attempting to maintain a feasible strategy at every micro-step, ECyclicPDA performs "pseudo-updates" in a bottom-up (postorder) fashion. The algorithm only ensures the strategy is valid and feasible once a full cycle through all blocks is completed.
  2. Dilated Regularizers: The method leverages the recursive mathematical structure of dilated regularizers. This allows the global update to be decomposed into local, block-wise proximal steps that respect the tree's hierarchy without requiring a global projection at every step.
  3. Bottom-Up Processing: By processing the tree from leaves to root, the algorithm accumulates gradient information and updates behavioral strategies locally. These are converted back to the global sequence-form only at the end of an iteration, significantly reducing the computational overhead per update.

Adaptive Restarting Heuristic

To further accelerate convergence, the authors introduce an adaptive restarting heuristic. The solver is "restarted" whenever the duality gap—a measure of the distance to equilibrium—drops by a fixed fraction. While restarting is theoretically well-understood for simpler Euclidean problems, this paper demonstrates its remarkable efficacy for the complex entropy-based dilated regularizers used in EFGs. This heuristic allows the solver to achieve higher numerical precision much faster than standard sublinear methods.

Experimental Evaluation

The algorithm was evaluated on four standard EFG benchmarks of varying complexity:

  • Goofspiel (4 ranks): A card-bidding game.
  • Liar’s Dice: A game involving bluffing and probability.
  • Leduc Poker (13 ranks): A simplified Texas Hold'em variant.
  • Battleship: A board game requiring spatial strategy and hidden information management.

These benchmarks range from approximately 6,000 to over 250,000 sequences, testing the scalability of the coordinate descent approach.

Key Results and Insights

Convergence and Efficiency

ECyclicPDA achieves an $O(1/T)$ convergence rate that is independent of the number of blocks. This is a significant theoretical breakthrough, as most cyclic coordinate methods suffer from performance penalties that scale polynomially with the number of blocks. In practice, ECyclicPDA consistently outperformed Mirror Prox (MP), particularly when utilizing "children" or "postorder" block construction strategies.

Comparison with State-of-the-Art

In the Liar’s Dice benchmark, ECyclicPDA surpassed CFR+, the long-standing gold standard for EFG solving, after $10^4$ gradient computations. On the Battleship benchmark, the restarted version of ECyclicPDA achieved a duality gap several orders of magnitude lower than Mirror Prox, demonstrating its ability to find highly accurate solutions where other methods plateau.

The Impact of Restarting

One of the most significant findings is that adaptive restarting acts as a universal speedup. It improved the performance of almost every solver tested, including existing ones like Mirror Prox and Predictive CFR+. With restarting, solvers were able to reach numerical precision in as few as 200 iterations on certain games.

Discussion and Future Work

Despite its success, the study highlights several open questions. First, the authors observed an "Infoset Mystery": the most granular block strategy (assigning every decision point to its own block) performed the worst, contrary to expectations. The reasons behind the failure of this fine-grained approach remain unclear.

Second, while the restarting heuristic is empirically powerful, a formal proof of linear convergence for dilated, non-Euclidean regularizers is still missing. Finally, the benefits of coordinate methods appear sensitive to game structure; the gains were more pronounced in Battleship and Liar's Dice than in Leduc Poker. Future research is required to determine which specific game properties, such as tree depth or branching factor, most influence the effectiveness of block-coordinate updates.

Summary updated

Abstract

Coordinate descent methods are popular in machine learning and optimization for their simple sparse updates and excellent practical performance. In the context of large-scale sequential game solving, these same properties would be attractive, but until now no such methods were known, because the strategy spaces do not satisfy the typical separable block structure exploited by such methods. We present the first cyclic coordinate-descent-like method for the polytope of sequence-form strategies, which form the strategy spaces for the players in an extensive-form game (EFG). Our method exploits the recursive structure of the proximal update induced by what are known as dilated regularizers, in order to allow for a pseudo block-wise update. We show that our method enjoys a O(1/T) convergence rate to a two-player zero-sum Nash equilibrium, while avoiding the worst-case polynomial scaling with the number of blocks common to cyclic methods. We empirically show that our algorithm usually performs better than other state-of-the-art first-order methods (i.e., mirror prox), and occasionally can even beat CFR$^+$, a state-of-the-art algorithm for numerical equilibrium computation in zero-sum EFGs. We then introduce a restarting heuristic for EFG solving. We show empirically that restarting can lead to speedups, sometimes huge, both for our cyclic method, as well as for existing methods such as mirror prox and predictive CFR$^+$.
BibTeX
@inproceedings{chakrabarti2023block,
  author = {Darshan Chakrabarti and Jelena Diakonikolas and Christian Kroer},
  title = {{Block-Coordinate Methods and Restarting for Solving Extensive-Form Games}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2023},
  url = {https://openreview.net/forum?id=4AmJVaJ78I},
}
Figure