Optimal approximation schedules for a class of iterative algorithms, with an application to multigrid value iteration

Many iterative algorithms employ operators which are difficult to evaluate exactly, but for which a graduated range of approximations exist. In such cases, coarse-to-fine algorithms are often used, in which a crude initial operator approximation is gradually refined with new iterations. In such algorithms, because the computational complexity increases over iterations, the algorithm's convergence rate is properly calculated with respect to cumulative computation time. This suggests the problem of determining an optimal rate of refinement for the operator approximation. This paper shows that, for linearly convergent algorithm, the optimal rate of refinement approaches the rate of convergence of the exact algorithm itself, regardless of the tolerance-complexity relationship. We illustrate this result with an analysis of coarse-to-fine grid algorithms for Markov decision processes with continuous state spaces. Using the methods proposed here we deduce an algorithm that presents optimal complexity results and consists solely of a non-adaptive schedule for the gradual decrease of grid size.