Thursday, 14:15 - 14:40 h, Room: H 1012


Stephane Gaubert
Policy iteration algorithm for zero-sum stochastic games with mean payoff

Coauthors: Marianne Akian, Jean Cochet-Terrasson, Sylvie Detournay


We develop a policy iteration algorithm to solve zero-sum stochastic
games with finite state, perfect information and ergodic payoff (mean
payoff per turn). An initial version of this algorithm was introduced
by Cochet-Terrasson and Gaubert in 2006, who assumed an exact model of
the arithmetics and the finiteness of action spaces. This algorithm
does not require any irreducibility assumption on the Markov chains
determined by the strategies of the players. It is based on a discrete
nonlinear analogue of the notion of reduction of a super-harmonic
function, which ensures the convergence even in the case of degenerate
iterations, in which the mean payoff is not improved. Hence, it can
be applied to monotone discretizations of stationary Isaacs partial
differential equations without any strong ellipticity assumption. We
report examples on Isaacs equations, as well as on a discrete
combinatorial game (variant of the infinity Laplacian on a graph) in
which degenerate iterations do occur. We also discuss numerical
issues due to ill conditioned linear problems.


Talk 3 of the invited session Thu.2.H 1012
"Policy iteration algorithms and some applications" [...]
Cluster 17
"Nonsmooth optimization" [...]


  Today, Ohio Payday Loans are legitimate, but there are illegal transactions that are still on the rise. But at the same time, it acts only with sexual arousal. Viagra has a number of advantages in comparison with injections in the sexual organ or other procedures aimed at treatment of impotency.