Smoothed analysis of deterministic discounted and mean-payoff games (Mateusz Skomra, part 1)

tocsem #011, March 4, 2024 (https://brunoloff.wordpress.com/tocsem/)

link to part 2:    • Smoothed analysis of deterministic discoun...  

Deterministic turn-based discounted and mean-payoff games are fundamental classes of games with an unsettled complexity. They belong to the complexity classes NP and coNP, but are not known to be polynomial-time solvable. Furthermore, they are at the bottom of a hierarchy of complexity classes that stratifies the NP search problems. Despite these properties, the problem of solving turn-based games efficiently has been open for 35 years. Nevertheless, even though we do not know how to solve these games in polynomial time in the worst case, practical experiments suggest that solving random games is easy. More precisely, the policy iteration methods, which can take exponentially many steps in the worst case, converge quickly to the solution when the weights of the game are taken at random. The aim of my talk is to give an explanation of this phenomenon using the framework of "smoothed analysis" introduced by Spielman and Teng to explain the real-world efficiency of the simplex method. We prove that if the weights of a turn-based deterministic game are perturbed by a Gaussian noise, then the resulting randomized problem can be solved efficiently by a variant of a policy iteration method. In the talk, I will give an introduction to turn-based discounted and mean-payoff games, explain the basic algorithms that are used to solve them, and finish by discussing the smoothed analysis result. This talk is based on a joint work with Bruno Loff.