An optimal multigrid algorithm for continuous state discrete time stochastic control

The application of multigrid methods to a class of discrete-time, continuous-state, discounted, infinite-horizon dynamic programming problems is studied. The authors analyze the computational complexity of computing the optimal cost function to within a desired accuracy of ε, as a function of ε and the discount factor α. Using an adversary argument, they obtain lower bound results on the computational complexity for this class of problems. They also provide a multigrid version of the successive approximation algorithm whose requirements are (as a function of α and ε) within a constant factor from the lower bounds when a certain mixing condition is satisfied. Hence the algorithm is optimal