Is Temporal Difference Learning Optimal? An Instance-Dependent Analysis
This work addresses the suboptimality of TD learning for policy evaluation in reinforcement learning, offering improved algorithms with theoretical guarantees, though it is incremental in refining existing methods.
The paper tackles the problem of policy evaluation in discounted Markov decision processes by providing instance-dependent guarantees on the error, showing that the widely-used temporal difference (TD) algorithm is strictly suboptimal in non-asymptotic settings, and introducing variance-reduced stochastic approximation methods that achieve near-optimal performance up to logarithmic factors.
We address the problem of policy evaluation in discounted Markov decision processes, and provide instance-dependent guarantees on the $\ell_\infty$-error under a generative model. We establish both asymptotic and non-asymptotic versions of local minimax lower bounds for policy evaluation, thereby providing an instance-dependent baseline by which to compare algorithms. Theory-inspired simulations show that the widely-used temporal difference (TD) algorithm is strictly suboptimal when evaluated in a non-asymptotic setting, even when combined with Polyak-Ruppert iterate averaging. We remedy this issue by introducing and analyzing variance-reduced forms of stochastic approximation, showing that they achieve non-asymptotic, instance-dependent optimality up to logarithmic factors.