Multigrid methods for zero-sum two player stochastic games

摘要: In this thesis, we present some algorithms and numerical results for the solution of large scale zero-sum two player repeated stochastic games. particular, consider class games with perfect information infinite horizon. class, discounted payoff mean payoff. Our are mainly based on policy iteration type multigrid methods, implemented in C. These applied either to dynamic programming equation a true finite state space game or discretization an Isaacs PDE differential game. first part, propose algorithm which combines iterations algebraic methods solve linear systems involved iterations. We tests discretizations equations variational inequalities. also full multilevel iteration, similar FMG, allows one improve substantially computation time solving For payoff, develop action spaces, general multichain case (i.e. without irreducibility assumption Markov chains determined by strategies players), following idea Cochet-Terrasson Gaubert (2006). This relies notion nonlinear spectral projection operators (which monotone convex). show that sequence values relative satisfies lexicographical monotonicity property, implies does terminate. variant Richman pursuit-evasion new particular singular arise instance above Furthermore, introduce method find stationary probability irreducible chain using control approach Howard systems.