The Complexity of Solving Reachability Games Using Value and Strategy Iteration

TY - JOUR

T1 - The Complexity of Solving Reachability Games Using Value and Strategy Iteration

AU - Hansen, Kristoffer Arnsfelt

AU - Ibsen-Jensen, Rasmus

AU - Miltersen, Peter Bro

PY - 2014/1/1

Y1 - 2014/1/1

N2 - 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 2m Θ(N) on the worst case number of iterations needed by both of these algorithms for providing non-trivial approximations to the value of a game with N non-terminal positions and m actions for each player in each position. In particular, both algorithms have doubly-exponential complexity. Even when the game given as input has only one non-terminal position, we prove an exponential lower bound on the worst case number of iterations needed to provide non-trivial approximations.

AB - 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 2m Θ(N) on the worst case number of iterations needed by both of these algorithms for providing non-trivial approximations to the value of a game with N non-terminal positions and m actions for each player in each position. In particular, both algorithms have doubly-exponential complexity. Even when the game given as input has only one non-terminal position, we prove an exponential lower bound on the worst case number of iterations needed to provide non-trivial approximations.

KW - Analysis of algorithms

KW - Concurrent reachability games

KW - Strategy iteration

KW - Value iteration

U2 - 10.1007/s00224-013-9524-6

DO - 10.1007/s00224-013-9524-6

M3 - Journal article

AN - SCOPUS:84903487299

SN - 1432-4350

VL - 55

SP - 380

EP - 403

JO - Theory of Computing Systems

JF - Theory of Computing Systems

IS - 2

ER -