The complexity of solving reachability games using value and strategy iteration

Details The complexity of solving reachability games using value and strategy iteration The complexity of solving reachability games using value and strategy iteration

2010-07-12

arxiv.org/abs/1007.1812v3

Computer Science

Computer Science and Game Theory

Scientific paper

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^(Theta(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.

Affiliated with

Also associated with

No associations

Rating

The complexity of solving reachability games using value and strategy iteration does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with The complexity of solving reachability games using value and strategy iteration, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The complexity of solving reachability games using value and strategy iteration will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-695447