Smoothed analysis of policy iteration and value iteration for deterministic discounted and mean-payoff games played on any graph

Bruno Loff, Mateusz Skomra

Our understanding of turn-based stochastic games is reminiscent of our understanding of linear programming in the 1970s. Instead of the simplex method, we have two families of algo…