Fast Dynamic Programming

Abstract

A well-established method for finding the optimal control policy for a given dynamical system is to solve the problem iteratively going from its terminal state "backwards" in time, known as Dynamic Programming Algorithm. For a generic problem with discrete state/action space, the algorithm has computational complexity of O(NM) for N states and M actions. In this thesis, we propose a novel numerical algorithm that approaches this problem in the conjugate domain, using the so-called Legendre-Fenchel Transform. In essence, the proposed approach is analogous to, and was inspired by Fast Fourier Transform, and how it can be beneficial to do computations/analysis in the frequency domain. In particular, this approach allows us to exploit the structure of the problem (e.g., in LQ control) to drastically reduce the computational complexity to O(N+M). Of course, this computational gain comes with a cost of introducing error.