Multigrid methods for two-player zero-sum stochastic games
For researchers working on numerical solutions of stochastic games or Isaacs equations, this work offers an efficient algorithm that significantly reduces computation time.
The paper presents a fast numerical algorithm combining policy iteration and algebraic multigrid methods for large-scale zero-sum stochastic games, demonstrating substantial improvements in computation time for solving variational inequalities.
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.