An Exponential Lower Bound for the Latest Deterministic Strategy Iteration Algorithms

摘要

This paper presents a new exponential lower bound for the two most populardeterministic variants of the strategy improvement algorithms for solvingparity, mean payoff, discounted payoff and simple stochastic games. The firstvariant improves every node in each step maximizing the current valuationlocally, whereas the second variant computes the globally optimal improvementin each step. We outline families of games on which both variants requireexponentially many strategy iterations.