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

Abstract

We consider the numerical solution of discrete-time stationary infinite-horizon discounted stochastic control problems, 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, we 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. We also study the effects of a certain mixing (ergodicity) condition on the algorithm's performance. We show that the one-way multigrid algorithm improves upon the complexity of its single-grid variant and is, in a certain sense, optimal.