Multigrid methods for two-player zero-sum stochastic games

Marianne Akian 1, 2 Sylvie Detournay 1, 2
1 MAXPLUS - Max-plus algebras and mathematics of decision
CMAP - Centre de Mathématiques Appliquées - Ecole Polytechnique, Inria Saclay - Ile de France, X - École polytechnique, CNRS - Centre National de la Recherche Scientifique : UMR
Abstract : We present a fast numerical algorithm for large scale zero-sum stochastic games with perfect information, which combines policy iteration and algebraic multigrid methods. This algorithm can be applied either to a true finite state space zero-sum two player game or to the discretization of an Isaacs equation. We present numerical tests on discretizations of Isaacs equations or variational inequalities. We also present a full multi-level policy iteration, similar to FMG, which allows to improve substantially the computation time for solving some variational inequalities.
Type de document :
Article dans une revue
Numerical Linear Algebra with Applications, Wiley, 2012, 19 (2), pp.313--342. 〈10.1002/nla.1815〉
Liste complète des métadonnées

https://hal.inria.fr/hal-00773036
Contributeur : Marianne Akian <>
Soumis le : vendredi 11 janvier 2013 - 14:52:24
Dernière modification le : jeudi 10 mai 2018 - 02:05:45

Lien texte intégral

Identifiants

Collections

Citation

Marianne Akian, Sylvie Detournay. Multigrid methods for two-player zero-sum stochastic games. Numerical Linear Algebra with Applications, Wiley, 2012, 19 (2), pp.313--342. 〈10.1002/nla.1815〉. 〈hal-00773036〉

Partager

Métriques

Consultations de la notice

251