Rates of Convergence for Variable Resolution Schemes in Optimal Control

Abstract

This paper presents a general method to derive tight rates of convergence for numerical approximations in optimal control when we consider variable resolution grids. We study the continuous-space, discrete-time, and discrete-controls case. Previous work described methods to obtain rates of convergence using general approximators (Bertsekas, 1987), multi-grid (Chow & Tsitsiklis, 1991) or Random grids (Rust, 1996). These results provide bounds on the error of approximation of the value function as a function of the space discretization resolution (or the number of grid-points) which is assumed to be uniform. Consequently, they do not consider the benefit of using non-uniform resolutions. However, empirical results (Munos & Moore, 1999b) have shown the importance of using variable resolution discretizations, especially for problem of high-dimensional state-space (in order to attack the "curse of dimensionality"). This paper provides some bounds on the approximation error of the value func...