An Optimal Strategy Improvement Algorithm for Solving Parity and Payoff Games

This paper presents a novel strategy improvement algorithm for parity and payoff games, which is guaranteed to select, in each improvement step, an optimal combination of local strategy modifications. Current strategy improvement methods stepwise improve the strategy of one player with respect to some ranking function, using an algorithm with two distinct phases: They first choose a modification to the strategy of one player from a list of

locally

profitable changes, and subsequently evaluate the modified strategy. This separation is unfortunate, because current strategy improvement algorithms have no effective means to predict the

global effect

of the individual local modifications beyond classifying them as profitable, adversarial, or stale. Furthermore, they are completely blind towards the

cross effect

of different modifications: Applying one profitable modification may render all other profitable modifications adversarial. Our new construction overcomes the traditional separation between choosing and evaluating the modification to the strategy. It thus improves over current strategy improvement algorithms by providing the

optimal improvement

in every step, selecting the best combination of local updates from a superset of all profitable and stale changes.