Variance-Reduced Off-Policy TDC Learning: Non-Asymptotic Convergence Analysis

Shaocong Ma, Yi Zhou, Shaofeng Zou

TL;DR

This paper introduces VRTDC, the first variance-reduced, two-time-scale Temporal Difference with Gradient Correction (TDC) algorithm designed for off-policy reinforcement learning. By applying an SVRG-like variance reduction scheme simultaneously to both time-scales, the algorithm achieves state-of-the-art sample complexity for both i.i.d. and realistic Markovian data trajectories, significantly reducing convergence error compared to standard methods.

What Problem Does This Paper Address?

Policy evaluation is a cornerstone of reinforcement learning, often requiring "off-policy" learning where an agent evaluates a target policy using data generated by a different behavior policy. While standard Temporal Difference (TD) learning works well on-policy, it can diverge off-policy when combined with linear function approximation.

To fix this, algorithms like TDC use a two-time-scale gradient approach to ensure stability. However, these algorithms suffer from high variance due to the stochastic nature of environmental sampling, leading to slow convergence. While variance reduction techniques (like SVRG) have been applied to simpler, one-time-scale on-policy settings, extending them to the more complex, two-time-scale off-policy setting—especially with non-i.i.d. Markovian data trajectories—remained an open challenge until now.

Methods

The authors propose Variance-Reduced TDC (VRTDC). Unlike previous variance-reduced TD methods that only update a single parameter scale, VRTDC applies an SVRG-style variance reduction scheme simultaneously to both time-scales of the TDC algorithm: the primary policy parameter ($\theta$) and the secondary gradient correction parameter ($w$).

The paper develops two distinct variants:

  1. VRTDC for i.i.d. samples: Computes batch pseudo-gradients over independent samples in an outer loop to guide inner-loop stochastic updates.
  2. VRTDC for Markovian samples: Adapts the algorithm for a single continuous trajectory from a Markov Decision Process (MDP) by dividing the trajectory into sequential batches. This makes it practical for real-world RL where data is inherently correlated over time.

The theoretical analysis introduces a novel recursive refinement strategy to decouple and tightly bound the tracking errors of the two interdependent time-scales.

Datasets

The algorithm was evaluated using two simulated environments:

  1. The Garnet Problem: A standard abstract benchmark for reinforcement learning algorithms characterized by state space size, action space size, branching factor, and feature dimension. The authors configured it with 500 states, 20 actions, a branching factor of 50, and 15 features.
  2. Frozen Lake Game: A classic grid-world environment from OpenAI Gym, utilizing a 4-dimensional Gaussian feature matrix to approximate the value function.

Key Insights and Ideas

  • Two-Scale Variance Reduction: The core innovation is showing that variance reduction can be successfully synchronized across two different learning rates ($\alpha$ and $\beta$) moving at different speeds.
  • Markovian Adaptability: Real RL data isn't i.i.d.; it's Markovian (sequential and correlated). Proving that variance reduction still works under Markovian noise without losing sample efficiency is a major theoretical breakthrough.
  • Decoupling Interdependent Errors: Analyzing two-time-scale convergence usually results in loose bounds. The authors' recursive refinement strategy allows them to use preliminary bounds of one parameter to refine the bounds of the other, achieving a near-optimal sample complexity of $O(\epsilon^{-1} \log \epsilon^{-1})$ in the Markovian setting.

Key Results

  • Sample Complexity: In the i.i.d. setting, VRTDC matches the best-known lower bound of $\tilde{O}(\epsilon^{-1})$. In the Markovian setting, it achieves a near-optimal state-of-the-art complexity of $O(\epsilon^{-1} \log \epsilon^{-1})$.
  • Variance Reduction: Empirical results on the Garnet problem show that VRTDC drastically reduces the variance of the stochastic updates for both $\theta$ and $w$ compared to standard TDC.
Figure 2: Comparison of TDC, VRTDC in solving the Garnet problem.
  • Convergence Error: In both the Garnet and Frozen Lake tasks, VRTDC achieves a lower asymptotic convergence error than standard TD, TDC, and one-time-scale variance-reduced TD (VRTD).
Figure 1: Comparison of TD, TDC, VRTD, VRTDC in solving the Garnet problem.

Limitations and Future Work

  • Linear Function Approximation: The analysis is strictly limited to linear function approximation. Extending these non-asymptotic convergence guarantees to non-linear function approximators, such as deep neural networks, remains an open problem.
  • Hyperparameter Sensitivity: The two-time-scale architecture introduces multiple tightly coupled hyperparameters (two stepsizes $\alpha, \beta$ and the batch size $M$), which can be difficult to tune optimally in practice.

Summary updated

Abstract

Variance reduction techniques have been successfully applied to temporal-difference (TD) learning and help to improve the sample complexity in policy evaluation. However, the existing work applied variance reduction to either the less popular one time-scale TD algorithm or the two time-scale GTD algorithm but with a finite number of i.i.d.\ samples, and both algorithms apply to only the on-policy setting. In this work, we develop a variance reduction scheme for the two time-scale TDC algorithm in the off-policy setting and analyze its non-asymptotic convergence rate over both i.i.d.\ and Markovian samples. In the i.i.d.\ setting, our algorithm {matches the best-known lower bound $\tilde{O}(ε^{-1}$).} In the Markovian setting, our algorithm achieves the state-of-the-art sample complexity $O(ε^{-1} \log ε^{-1})$ that is near-optimal. Experiments demonstrate that the proposed variance-reduced TDC achieves a smaller asymptotic convergence error than both the conventional TDC and the variance-reduced TD.
BibTeX
@inproceedings{ma2020variance,
  author = {Shaocong Ma and Yi Zhou and Shaofeng Zou},
  title = {{Variance-Reduced Off-Policy TDC Learning: Non-Asymptotic Convergence Analysis}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2020},
  url = {https://openreview.net/forum?id=QNiREeGFLCW},
}
Figure