An optimal one-way multigrid algorithm for discrete-time stochastic control

The numerical solution of discrete-time stationary infinite-horizon discounted stochastic control problems is considered for the case where the state space is continuous and the problem is to be solved approximately, within a desired accuracy. After a discussion of problem discretization, the authors introduce a multigrid version of the successive approximation algorithm that proceeds `one way´ from coarse to fine grids, and analyze its computational requirements as a function of the desired accuracy and of the discount factor. They also study the effects of a certain mixing (ergodicity) condition on the algorithm´s performance. It is shown that the one-way multigrid algorithm improves upon the complexity of its single-grid variant and is, in a certain sense, optimal