13 citations · 36 across the 15 of their papers we have counts for
Showing 2010Show all
2 papers · 1 filter
cs.GT2010★ 13 cited
Strategy iteration is strongly polynomial for 2-player turn-based stochastic games with a constant discount factor
Thomas Dueholm Hansen, Peter Bro Miltersen, Uri Zwick
Ye showed recently that the simplex method with Dantzig pivoting rule, as well as Howard's policy iteration algorithm, solve discounted Markov decision processes (MDPs), with a con…
cs.GT2010
The complexity of solving reachability games using value and strategy iteration
Kristoffer Arnsfelt Hansen, Rasmus Ibsen-Jensen, Peter Bro Miltersen
Two standard algorithms for approximately solving two-player zero-sum concurrent reachability games are value iteration and strategy iteration. We prove upper and lower bounds of 2…