Research Article
How to solve large scale deterministic games with mean payoff by policy iteration
@INPROCEEDINGS{10.1145/1190095.1190110, author={Vishesh Dhingra and Stephane Gaubert}, title={How to solve large scale deterministic games with mean payoff by policy iteration}, proceedings={1st International ICST Conference on Performance Evaluation Methodologies and Tools}, publisher={ACM}, proceedings_a={VALUETOOLS}, year={2012}, month={4}, keywords={Policy iteration repeated games graph algorithms maxplus algebra nonlinear harmonic functions}, doi={10.1145/1190095.1190110} }- Vishesh Dhingra
Stephane Gaubert
Year: 2012
How to solve large scale deterministic games with mean payoff by policy iteration
VALUETOOLS
ACM
DOI: 10.1145/1190095.1190110
Abstract
Min-max functions are dynamic programming operators of zero-sum deterministic games with finite state and action spaces. The problem of computing the linear growth rate of the orbits (cycle-time) of a min-max function, which is equivalent to computing the value of a deterministic game with mean payoff, arises in the performance analysis of discrete event systems. We present here an improved version of the policy iteration algorithm given by Gaubert and Gunawardena in 1998 to compute the cycle-time of a min-max functions. The improvement consists of a fast evaluation of the spectral projector which is adapted to the case of large sparse graphs. We present detailed numerical experiments, both on randomly generated instances, and on concrete examples, indicating that the algorithm is experimentally fast.