PILOT: An $\mathcal{O}(1/K)$-Convergent Approach for Policy Evaluation with Nonlinear Function Approximation

Learning an accurate value function for a given policy is a critical step in solving reinforcement learning (RL) problems. So far, however, the convergence speed and sample complexity performances of most existing policy evaluation algorithms remain unsatisfactory, particularly with non-linear function approximation. This challenge motivates us to develop a new path-integrated primal-dual stochastic gradient (PILOT) method, that is able to achieve a fast convergence speed for RL policy evaluation with nonlinear function approximation. To further alleviate the periodic full gradient evaluation requirement, we further propose an enhanced method with an adaptive-batch adjustment called PILOT + . The main advantages of our methods include: i) PILOT allows the use of constant step sizes and achieves the O(1/K) convergence rate to first-order stationary points of non-convex policy evaluation problems; ii) PILOT is a generic single-timescale algorithm that is also applicable for solving a large class of non-convex strongly-concave minimax optimization problems; iii) By adaptively adjusting the batch size via historical stochastic gradient information, PILOT + is more sample-efficient empirically without loss of theoretical convergence rate. Our extensive numerical experiments verify our theoretical findings and showcase the high efficiency of the proposed PILOT and PILOT + algorithms compared with the state-of-the-art methods.

Published as a conference paper at ICLR 2024 Among various algorithms for PE, one of the simplest and most effective methods is the temporal difference (TD) learning approach (Sutton, 1988). In TD learning, instead of focusing on the predicted and actual outcomes, the key idea is to make the difference between temporally successive predictions small. Specifically, the TD learning approach learns the value function using the Bellman equation to bootstrap from the currently estimated value function. To date, there have been many algorithms proposed within the family of TD learning (Dann et al., 2014). However, most of these methods suffer from either unstable convergence performance, (e.g., TD(λ) (Sutton, 1988) for off-policy training) or high computational complexity (e.g., the least-squares temporal difference (LSTD) (Boyan, 2002)) in training with massive features. One reason of the unstable convergence performance of these early attempts is that they do not leverage the gradient-oracle in PE. Thus, in recent years, gradient-based PE algorithms have attracted increasing attention.