Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information
Date and Time: Thursday, September 22, 2011, 12:15 pm
Duration: 30 minutes
Location: OAT S15/S16/S17
Speaker: Thomas Dueholm Hansen (Aarhus University)
A fundamental model of operations research is the finite, but infinite-horizon, discounted Markov Decision Process. Ye showed recently that the simplex method with Dantzig pivoting rule, as well as Howard's policy iteration algorithm, solve discounted Markov decision processes, with a constant discount factor, in strongly polynomial time. More precisely, Ye showed that for both algorithms the number of iterations required to find the optimal policy is bounded by a polynomial in the number of states and actions. We improve Ye's analysis in two respects. First, we show a tighter bound for Howard's policy iteration algorithm. Second, we show that the same bound applies to the number of iterations performed by the strategy iteration (or strategy improvement) algorithm used for solving 2-player turn-based stochastic games with discounted zero-sum rewards. This provides the first strongly polynomial algorithm for solving these games.
Markov Decision Processes and 2-player turn-based stochastic games define Acyclic Unique Sink Orientations of cubes, and in this abstract framework the strategy iteration algorithm is sometimes referred to as the Bottom-Antipodal algorithm. We also present a conjecture by Hansen and Zwick, saying that the number of iterations for an n-dimensional cube is at most the (n+2)-th Fibonacci number.
Joint work with Peter Bro Miltersen and Uri Zwick.
Automatic MiSe System Software Version 1.4803M | admin login