Convergence and Numerical Complexity of Policy and Value Iterations in Linear-Quadratic Discrete-Time Reinforcement Learning
Lingyi Xu, Zoran Gajić · IFAC-PapersOnLine · 2024
This paper demonstrates that the value iteration (VI) algorithm of reinforcement learning of discrete-time (DT) linear-quadratic (LQ) optimal control problem converges very slowly mostly linearly, compared to the quadratic rate of convergence of the corresponding policy iteration (PI) algorithm. The VI algorithm produces non-monotonically decreasing or increasing sequences that converge to the optimal value either from below or from above depending on the choice of initial conditions. It is remarkable that the VI algorithm converges even in the case when the initial condition is very far from the optimal value by several orders of magnitude, and when the initial condition is not stabilizing. The PI algorithm generates a non-increasing sequence that monotonically converges from above to the optimal value assuming the initial condition (feedback gain) is stabilizing. The convergence rate for the PI algorithm is quadratic, which assures its fast convergence. It is shown in this paper that the convergence of the VI algorithm can be made quadratic by using the doubling algorithm. We precisely state a condition needed for convergence of the VI algorithm, which is milder than the corresponding convergence condition for the PI algorithm. We have also shown that the newly proposed VI algorithm requires less computational effort than the PI algorithm. Several numerical examples are solved to document the presented results.