Skip to Main content Skip to Navigation
Conference papers

Solving multichain stochastic games with mean payoff by policy iteration

Abstract : Zero-sum stochastic games with finite state and action spaces, perfect information, and mean payoff criteria arise in particular from the monotone discretization of mean-payoff pursuit-evasion deterministic differential games. In that case no irreducibility assumption on the Markov chains associated to strategies are satisfied (multichain games). The value of such a game can be characterized by a system of nonlinear equations, involving the mean payoff vector and an auxiliary vector (relative value or bias). Cochet-Terrasson and Gaubert proposed in (C. R. Math. Acad. Sci. Paris, 2006) a policy iteration algorithm relying on a notion of nonlinear spectral projection (Akian and Gaubert, Nonlinear Analysis TMA, 2003), which allows one to avoid cycling in degenerate iterations. We give here a complete presentation of the algorithm, with details of implementation in particular of the nonlinear projection. This has led to the software PIGAMES and allowed us to present numerical results on pursuit-evasion games.
Document type :
Conference papers
Complete list of metadata

https://hal.inria.fr/hal-00933689
Contributor : Marianne Akian <>
Submitted on : Monday, January 20, 2014 - 9:41:54 PM
Last modification on : Thursday, March 5, 2020 - 6:23:37 PM

Identifiers

Collections

Citation

Marianne Akian, Jean Cochet-Terrasson, Sylvie Detournay, Stéphane Gaubert. Solving multichain stochastic games with mean payoff by policy iteration. CDC 2013 - 52nd IEEE Conference on Decision and Control, Dec 2013, Florence, Italy. pp.1834-1841, ⟨10.1109/CDC.2013.6760149⟩. ⟨hal-00933689⟩

Share

Metrics

Record views

1869