The Complexity of Solving Reachability Games Using Value and Strategy Iteration

Kristoffer Arnsfelt Hansen; Rasmus Ibsen-Jensen; Peter Bro Miltersen

doi:10.1007/s00224-013-9524-6

The Complexity of Solving Reachability Games Using Value and Strategy Iteration

Kristoffer Arnsfelt Hansen, Rasmus Ibsen-Jensen, Peter Bro Miltersen

Publikation: Bidrag til tidsskrift/Konferencebidrag i tidsskrift /Bidrag til avis › Tidsskriftartikel › Forskning › peer review

Abstract

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^m _Θ(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.

Originalsprog	Engelsk
Tidsskrift	Theory of Computing Systems
Vol/bind	55
Nummer	2
Sider (fra-til)	380-403
Antal sider	24
ISSN	1432-4350
DOI	https://doi.org/10.1007/s00224-013-9524-6
Status	Udgivet - 1 jan. 2014

Adgang til dokumentet

10.1007/s00224-013-9524-6

http://www.scopus.com/inward/record.url?scp=84903487299&partnerID=8YFLogxK

Citationsformater

@article{0d76fc8329c44440ba6bebcd3aef358e,

title = "The Complexity of Solving Reachability Games Using Value and Strategy Iteration",

abstract = "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.",

keywords = "Analysis of algorithms, Concurrent reachability games, Strategy iteration, Value iteration",

author = "Hansen, {Kristoffer Arnsfelt} and Rasmus Ibsen-Jensen and Miltersen, {Peter Bro}",

year = "2014",

month = jan,

day = "1",

doi = "10.1007/s00224-013-9524-6",

language = "English",

volume = "55",

pages = "380--403",

journal = "Theory of Computing Systems",

issn = "1432-4350",

publisher = "Springer",

number = "2",

}

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 -

The Complexity of Solving Reachability Games Using Value and Strategy Iteration

Abstract

Adgang til dokumentet

Fingeraftryk

Citationsformater