The Complexity of Solving Reachability Games Using Value and Strategy Iteration

Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaperJournal articleResearchpeer-review

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.

Original languageEnglish
JournalTheory of Computing Systems
Volume55
Issue2
Pages (from-to)380-403
Number of pages24
ISSN1432-4350
DOIs
Publication statusPublished - 1 Jan 2014

    Research areas

  • Analysis of algorithms, Concurrent reachability games, Strategy iteration, Value iteration

See relations at Aarhus University Citationformats

ID: 81805188