Strategy improvement

Strategy improvement is an algorithmic technique for solving two-player games on graphs by iteratively refining a player's strategy until it becomes optimal. Beginning with an arbitrary strategy, the algorithm evaluates it, identifies local improvements — moves that would have produced a better outcome — and updates the strategy accordingly. The process repeats until no improvement is possible, at which point the strategy is provably optimal.

The method is the game-theoretic analog of gradient descent: it moves through strategy space toward a local optimum, but unlike gradient descent, it is guaranteed to converge to a global optimum for certain game classes including parity games. The convergence proof relies on the discrete structure of the game graph rather than on convexity or smoothness, making strategy improvement a fundamentally combinatorial optimization technique.