Stochastic shortest path games

Citation
Sd. Patek et Dp. Bertsekas, Stochastic shortest path games, SIAM J CON, 37(3), 1999, pp. 804-824
Citations number
13
Language
INGLESE
art.tipo
Article
Categorie Soggetti
Mathematics,"Engineering Mathematics
Journal title
SIAM JOURNAL ON CONTROL AND OPTIMIZATION
ISSN journal
0363-0129 → ACNP
Volume
37
Issue
3
Year of publication
1999
Pages
804 - 824
Database
ISI
SICI code
0363-0129(19990413)37:3<804:SSPG>2.0.ZU;2-J
Abstract
We consider dynamic, two-player, zero-sum games where the "minimizing" play er seeks to drive an underlying finite-state dynamic system to a special te rminal state along a least expected cost path. The "maximizer" seeks to int erfere with the minimizer's progress so as to maximize the expected total c ost. We consider, for the first time, undiscounted finite-state problems, w ith compact action spaces, and transition costs that are not strictly posit ive. We admit that there are policies for the minimizer which permit the ma ximizer to prolong the game indefinitely. Under assumptions which generaliz e deterministic shortest path problems, we establish (i) the existence of a real-valued equilibrium cost vector achievable with stationary policies fo r the opposing players and (ii) the convergence of value iteration and poli cy iteration to the unique solution of Bellman's equation.