  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.
