Stochastic Shortest Path Games
Authors:
- Stephen D. PatekSPStephen D. Patek
- Dimitri P. BertsekasDBDimitri P. Bertsekas
- 1 January 1999
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Control and Optimization
- Vol. 37 (3) , 804-824
Abstract
We consider dynamic, two-player, zero-sum games where the "minimizing" player seeks to drive an underlying finite-state dynamic system to a special terminal state along a least expected cost path. The "maximizer" seeks to interfere with the minimizer's progress so as to maximize the expected total cost. We consider, for the first time, undiscounted finite-state problems, with compact action spaces, and transition costs that are not strictly positive. We admit that there are policies for the minimizer which permit the maximizer to prolong the game indefinitely. Under assumptions which generalize deterministic shortest path problems, we establish (i) the existence of a real-valued equilibrium cost vector achievable with stationary policies for the opposing players and (ii) the convergence of value iteration and policy iteration to the unique solution of Bellmans equation.Keywords
This publication has 7 references indexed in Scilit:
- An Analysis of Stochastic Shortest Path ProblemsMathematics of Operations Research, 1991
- Solving H-horizon, stationary Markov decision problems in time proportional to log(H)Operations Research Letters, 1990
- Stochastic gamesInternational Journal of Game Theory, 1981
- Zero-Sum Dynamic Games1981
- Convexity and Optimization in Finite Dimensions I1970
- Finite state stochastic games: Existence theorems and computational proceduresIEEE Transactions on Automatic Control, 1969
- Stochastic GamesProceedings of the National Academy of Sciences, 1953