## 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.

Original language | English |
---|---|

Journal | Theory of Computing Systems |

Volume | 55 |

Issue | 2 |

Pages (from-to) | 380-403 |

Number of pages | 24 |

ISSN | 1432-4350 |

DOIs | |

Publication status | Published - 1 Jan 2014 |

## Keywords

- Analysis of algorithms
- Concurrent reachability games
- Strategy iteration
- Value iteration