Accelerated Reinforcement Learning With Verifiable Excitation for Cubic Convergence

This article proposes and analyzes an accelerated reinforcement learning (RL) algorithm for discrete-time linear systems with unknown dynamics. The method achieves cubic convergence, improving upon the quadratic rates of existing policy iteration (PI)-based RL algorithms, and it does not rely on persistency of excitation (PE). The value function matrix is computed through a midpoint-centered Lyapunov equation, which provides a third-order Newton-type update and ensures fast convergence. To enable data-driven implementation without PE, we introduce a verifiable excitation condition based on filter outputs. This condition is easily testable online and guarantees that the collected data are sufficiently informative for solving the required least-squares equations. Within this framework, we further propose a data-driven procedure to compute an initial admissible control gain, where a bisection rule is used to determine the maximal feasible discount factor. Theoretical analysis establishes cubic convergence of the accelerated algorithm and proves the effectiveness of the designed excitation condition. Finally, we verify the proposed method through Monte Carlo experiments and comparative simulations with existing methods.