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

Abstract

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.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">&gt;</ETX>