Reanalysis of Variance Reduced Temporal Difference Learning
This work addresses incremental improvements in reinforcement learning policy evaluation by correcting and solidifying the theoretical understanding of variance reduction techniques for researchers and practitioners.
The authors identified technical errors in the prior analysis of the variance reduced temporal difference (VRTD) algorithm and provided a corrected non-asymptotic convergence analysis, showing that VRTD converges linearly to a neighborhood of the fixed-point solution and reduces variance and bias errors compared to vanilla TD, with improved computational complexity under Markov sampling.
Temporal difference (TD) learning is a popular algorithm for policy evaluation in reinforcement learning, but the vanilla TD can substantially suffer from the inherent optimization variance. A variance reduced TD (VRTD) algorithm was proposed by Korda and La (2015), which applies the variance reduction technique directly to the online TD learning with Markovian samples. In this work, we first point out the technical errors in the analysis of VRTD in Korda and La (2015), and then provide a mathematically solid analysis of the non-asymptotic convergence of VRTD and its variance reduction performance. We show that VRTD is guaranteed to converge to a neighborhood of the fixed-point solution of TD at a linear convergence rate. Furthermore, the variance error (for both i.i.d.\ and Markovian sampling) and the bias error (for Markovian sampling) of VRTD are significantly reduced by the batch size of variance reduction in comparison to those of vanilla TD. As a result, the overall computational complexity of VRTD to attain a given accurate solution outperforms that of TD under Markov sampling and outperforms that of TD under i.i.d.\ sampling for a sufficiently small conditional number.