The Complexity of All-switches Strategy Improvement

John Fearnley, Rahul Savani

TL;DR

This paper investigates the computational complexity of a specific strategy improvement algorithm, "all-switches," used for solving various types of games. The authors prove that determining whether a particular edge is ever switched or used in the final optimal strategy is PSPACE-complete for parity games, mean-payoff games, discounted games, and simple stochastic games. This finding highlights a fundamental limitation in the efficiency of these common game-solving algorithms.

What Problem Does This Paper Address?

Solving complex games like parity games, mean-payoff games, and discounted games is a long-standing challenge in computer science. These games have important applications in areas like formal verification and AI. While strategy improvement algorithms are a well-established method for tackling these problems, their theoretical performance has been a puzzle. Specifically, the "all-switches" variant, which aims to make the most progress in each step by switching as many edges as possible, was once thought to be a candidate for a polynomial-time solution. However, this paper addresses the question of the computational complexity of this "all-switches" strategy improvement algorithm, aiming to understand why it might not be as efficient as initially hoped. The authors focus on two specific decision problems: whether a given edge is ever switched during the algorithm's execution, and whether a given edge is part of the final optimal strategy.

Methods

The core of this paper's contribution lies in a sophisticated reduction from the PSPACE-complete problem of "BITSWITCH" (related to iterated boolean circuit evaluation) to the "EDGESWITCH" and "OPTIMALSTRATEGY" problems for strategy improvement algorithms. The authors construct complex parity games that are specifically designed to mimic the behavior of boolean circuits and their iterative evaluation.

Key techniques include:

  • Gadget Construction: The paper details the construction of intricate game structures (gadgets) that simulate boolean circuit gates (OR, NOT) and control flow mechanisms (clocks, deceleration lanes). These gadgets are carefully designed to ensure that the strategy improvement algorithm's steps correspond to the circuit's computations.
  • Priority Engineering: The assignment of priorities to game vertices is crucial. The authors use a complex, injective priority assignment function to ensure that game-theoretic outcomes precisely mirror boolean logic operations and that the strategy improvement algorithm makes specific, predictable moves.
  • One-Sink Games: The construction often results in "one-sink" parity games, a simplified variant that helps in analyzing the algorithm's behavior and proving its properties.
  • Reduction Strategy: The paper systematically reduces the complexity of BITSWITCH to the complexity of EDGESWITCH and OPTIMALSTRATEGY for various game types (parity, mean-payoff, discounted, simple stochastic) by showing that if the circuit evaluation problem can be solved, then the corresponding strategy improvement problem can also be solved.

Datasets

Not discussed in the paper. The paper focuses on theoretical complexity and uses constructed games as its "instances" rather than real-world datasets.

Key Insights and Ideas

  • PSPACE-Completeness of "All-Switches": The most significant insight is the proof that even the seemingly aggressive "all-switches" strategy improvement algorithm, when applied to common game types, leads to PSPACE-complete decision problems. This suggests that the inherent complexity lies not just in the switching rule but in the underlying game structures and the iterative nature of the improvement process.
  • Simulating Computation with Games: The paper demonstrates a powerful technique for encoding computational processes (like iterated circuit evaluation) into game-theoretic settings. This allows for the transfer of complexity results from computation to game theory.
  • The Power of "All Switches": The "all-switches" rule, which aims to make maximal progress, paradoxically leads to PSPACE-completeness. This implies that the ability to switch multiple edges simultaneously doesn't necessarily simplify the problem from a complexity standpoint; instead, it allows the algorithm to simulate more complex computations.
  • Universality of the Construction: The authors show how their construction for parity games can be adapted to prove similar PSPACE-completeness results for mean-payoff, discounted, and simple stochastic games, highlighting a common underlying complexity across these related game classes.

Key Results

  • Theorem 1.2: The EDGESWITCH problem for the Vöge and Jurdziński's algorithm (for parity games) is PSPACE-complete.
  • Corollary 1.3: EDGESWITCH is PSPACE-complete for gain-bias algorithms (mean-payoff games) and standard strategy improvement algorithms for discounted and simple stochastic games.
  • Theorem 1.5: The OPTIMALSTRATEGY problem for Vöge and Jurdziński's algorithm is PSPACE-complete.
  • Corollary 1.6: OPTIMALSTRATEGY is PSPACE-complete for the gain-bias algorithm and standard strategy improvement algorithms for discounted and simple stochastic games.
  • Corollary 1.7: A PSPACE-hardness result is shown for the BOTTOMANTIPODAL algorithm on unique sink orientations of hypercubes.

Limitations and Future Work

  • One-Sink Game Assumption: For some proofs, the authors rely on constructing "one-sink" games. While this simplifies analysis, it's a specific type of game, and the results for general games are derived through reductions.
  • Complexity of Other Algorithms: The paper focuses on "all-switches" strategy improvement. It acknowledges that other pivoting algorithms for parity games (like Lemke's algorithm) exist and suggests that similar PSPACE-completeness results might be achievable for them, extending to linear complementarity problems.
  • MDPs: The paper poses the question of whether PSPACE-hardness can be extended to all-switches strategy improvement for Markov Decision Processes (MDPs), noting that their current construction has limitations for direct application.
  • Practical Implications: While the theoretical complexity is established, the practical implications for solving these games in real-world scenarios remain an open area. The PSPACE-completeness suggests that no polynomial-time algorithm is likely to exist, but subexponential or quasi-polynomial algorithms might still be feasible for certain game classes.

Summary updated

Abstract

Strategy improvement is a widely-used and well-studied class of algorithms for solving graph-based infinite games. These algorithms are parameterized by a switching rule, and one of the most natural rules is "all switches" which switches as many edges as possible in each iteration. Continuing a recent line of work, we study all-switches strategy improvement from the perspective of computational complexity. We consider two natural decision problems, both of which have as input a game $G$, a starting strategy $s$, and an edge $e$. The problems are: 1.) The edge switch problem, namely, is the edge $e$ ever switched by all-switches strategy improvement when it is started from $s$ on game $G$? 2.) The optimal strategy problem, namely, is the edge $e$ used in the final strategy that is found by strategy improvement when it is started from $s$ on game $G$? We show $\mathtt{PSPACE}$-completeness of the edge switch problem and optimal strategy problem for the following settings: Parity games with the discrete strategy improvement algorithm of V\"oge and Jurdzi\'nski; mean-payoff games with the gain-bias algorithm [14,37]; and discounted-payoff games and simple stochastic games with their standard strategy improvement algorithms. We also show $\mathtt{PSPACE}$-completeness of an analogous problem to edge switch for the bottom-antipodal algorithm for finding the sink of an Acyclic Unique Sink Orientation on a cube.
BibTeX
@inproceedings{fearnley2015complexity,
  author = {John Fearnley and Rahul Savani},
  title = {{The Complexity of All-switches Strategy Improvement}},
  booktitle = {SODA},
  year = {2015},
  url = {https://openreview.net/forum?id=3vKdJLBM7m},
}
Figure