Surrogate Loss Gradient Descent in Variational Inequalities with Linear Approximation

The use of surrogate losses to approximate principled updates in prediction space has been instrumental in the success of scaling function approximation in reinforcement learning. These methods are motivated by approximating an update in prediction space with an optimization inner-loop that takes a fixed number of gradient steps on a surrogate loss. Despite its prevalence, there is a disconnect between existing theory and algorithms used in practice with respect to the number of gradient steps. In this paper, we focus on the linear approximation case to derive sharp guarantees when parameters are updated by a fixed number of gradient steps on a surrogate loss. It provides a unified approach that naturally connects the mean-path analysis of TD and LSPE, which correspond to both extremes from one step to an infinite number of inner-steps, and have been previously analysed with different techniques. Our analysis, however, gives a precise insight into the compute-optimal number of gradient steps $k^\star$, which in practice is often taken to be larger than 1 but far from $k=+\infty$. We show formally how $k^\star$ depends on problem-specific parameters such as condition numbers in prediction space and feature space, as well as the constant cost of setting up the surrogate loss and show that choosing such $k^\star$ improves overall complexity by a significant factor.