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:
- 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.
- 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.
- 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