Per-decision Multi-step Temporal Difference Learning with Control Variates

Kristopher De Asis, Richard S. SuttonUAI 2018

TL;DR

This paper introduces per-decision control variates to multi-step Temporal Difference (TD) learning, a technique that significantly reduces the variance typically associated with off-policy reinforcement learning. By applying a correction at every step of a multi-step trajectory—rather than just at the end—the authors create a more stable and efficient bridge between one-step TD and Monte Carlo methods, outperforming standard algorithms like $n$-step Expected Sarsa.

Introduction

In Reinforcement Learning (RL), agents often face a fundamental bias-variance tradeoff. One-step TD methods (like Sarsa) have low variance but high bias because they rely heavily on current, potentially inaccurate estimates. Conversely, Monte Carlo methods have zero bias but high variance because they rely on long, noisy sequences of actual rewards. Multi-step TD methods ($n$-step) attempt to find the "sweet spot" between these extremes.

The challenge is amplified in off-policy learning, where an agent learns about a "target policy" while following a different "behavior policy." Importance sampling corrections used in these scenarios can compound over multiple steps, leading to massive variance that makes learning unstable. The authors propose a way to maintain the benefits of multi-step learning without this crippling variance.

Methodology: $n$-step CV Sarsa

The authors introduce $n$-step CV Sarsa (Control Variate Sarsa). The core idea is to use a control variate—a classic statistical tool for variance reduction—at each step of the multi-step return.

Specifically, they use the difference between the sampled action-value and the expected action-value under the target policy as a correction term. Unlike standard $n$-step Expected Sarsa, which only takes an expectation at the final step ($n$), CV Sarsa applies this correction at every step along the trajectory. This approach effectively implements a "doubly robust" estimator in an online, model-free RL setting, combining importance sampling with value function estimates to achieve superior stability.

Experimental Setup

The researchers evaluated their approach on two classic RL benchmarks:

  1. 5x5 Grid World: Used for both on-policy and off-policy prediction tasks. This tabular environment allows for precise error measurement against a known ground truth.
  2. Mountain Car: Used for an on-policy control task. This environment uses tile coding, testing if the method scales to linear function approximation in continuous state spaces.

Key Results and Insights

Stability and Accuracy

In the Grid World off-policy task, $n$-step CV Sarsa remained stable and achieved low RMS error for values of $n$ (like $n=4$) where standard $n$-step Expected Sarsa completely diverged. Across almost all parameter settings, CV Sarsa achieved lower error than its non-CV counterparts.

Comparison of RMS Error between n-step Expected Sarsa (left) and n-step CV Sarsa (right) across different step sizes (α) and n values.

The control variate acts like an implicit adaptive learning mechanism. If value estimates are accurate, the algorithm relies more on expectations (behaving like one-step TD). If estimates are poor, it incorporates more of the actual sampled rewards. This allows the agent to benefit from multi-step trajectories without being overwhelmed by noise.

Performance in Control Tasks

In the Mountain Car task, CV Sarsa achieved higher average returns and learned faster than Expected Sarsa, proving the method's utility in continuous state spaces with function approximation.

Learning curves showing average return per episode for CV Sarsa vs Expected Sarsa in the Mountain Car task.

Conclusion and Future Work

While $n$-step CV Sarsa significantly improves stability, it can still diverge if the step size ($\alpha$) and the number of steps ($n$) are both very large. The authors used a fixed coefficient ($c = -1$) for their control variate, which assumes value estimates are perfectly correlated with returns. Future work could investigate adaptive control variate parameters that change online based on the current accuracy of the value function, potentially making the algorithm even more robust for complex, high-dimensional tasks.

Summary updated

BibTeX
@inproceedings{asis2018per,
  author = {Kristopher De Asis and Richard S. Sutton},
  title = {{Per-decision Multi-step Temporal Difference Learning with Control Variates}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2018},
}
Figure