Adaptive trade-offs in off-policy learning

Mark Rowland, Will Dabney, Remi Munos

Abstract

A great variety of off-policy learning algorithms exist in the literature, and new breakthroughs in this area continue to be made, improving theoretical understanding and yielding state-of-the-art reinforcement learning algorithms. In this paper, we take a unifying view of this space of algorithms, and consider their trade-offs of three fundamental quantities: update variance, fixed-point bias, and contraction rate. This leads to new perspectives of existing methods, and also naturally yields novel algorithms for off-policy evaluation and control. We develop one such algorithm, C-trace, demonstrating that it is able to more efficiently make these trade-offs than existing methods in use, and that it can be scaled to yield state-of-the-art performance in large-scale environments.

Introduction

In reinforcement learning (RL), off-policy learning allows an agent to learn a target policy using data generated by a different, exploratory "behavior" policy. While theoretically sound methods like Retrace exist, many state-of-the-art deep RL agents (e.g., Rainbow, R2D2) often rely on "uncorrected" $n$-step returns. These heuristics ignore off-policy discrepancies but perform remarkably well in practice. This paper investigates this phenomenon, proving that off-policy learning is fundamentally a three-way tug-of-war between variance, contraction rate (learning speed), and fixed-point bias.

The Fundamental Trade-off

The authors introduce a theoretical framework decomposing the error of off-policy algorithms into three components:

  1. Variance: Sensitivity to random data perturbations.
  2. Contraction Rate: The speed at which the algorithm converges.
  3. Fixed-point Bias: The inherent error in the final converged values due to ignored corrections.

A key insight is that uncorrected $n$-step returns are not merely a "hack"; they are highly efficient at trading fixed-point bias for a massive boost in contraction rate and reduced variance. The authors prove a fundamental lower bound: no algorithm based on limited data can simultaneously minimize all three properties.

The fundamental three-way trade-off between fixed-point bias, contraction rate, and empirical variance.

Proposed Algorithms: alpha-Retrace and C-trace

To exploit these trade-offs, the paper introduces two novel methods:

  • alpha-Retrace: This algorithm evaluates a mixture of the target and behavior policies, controlled by a parameter alpha. By intentionally injecting a controlled amount of bias, it significantly improves the contraction rate compared to standard unbiased Retrace.
  • C-trace: Recognizing that the optimal alpha is hard to pre-determine, C-trace dynamically adapts alpha online. It lowers alpha (leaning toward the behavior policy) to maintain a user-defined target contraction rate, ensuring learning speed matches that of uncorrected methods while maintaining better theoretical grounding.

Empirical Results

The proposed methods were evaluated on both small-scale Markov Decision Processes (MDPs) and the Atari-57 benchmark. On tabular MDPs, alpha-Retrace is shown to be Pareto-efficient; for any given learning speed, it can achieve lower bias than uncorrected methods.

Performance comparison of alpha-Retrace variants against uncorrected and importance-weighted baselines.

In large-scale experiments, C-trace-R2D2 matched or slightly outperformed the standard R2D2 baseline (which uses uncorrected returns) across human-normalized scores. Furthermore, C-trace-DQN significantly outperformed Double DQN and Retrace-DQN, demonstrating the algorithm's robustness across different architectures. Empirical density plots confirmed that C-trace successfully maintains its target contraction rate throughout training, unlike standard Retrace which varies wildly by environment.

Conclusion

This work provides a unifying perspective on off-policy learning, highlighting the necessity of balancing bias, variance, and speed. By introducing C-trace, the authors demonstrate that principled off-policy corrections can be made as efficient as popular heuristics, bridging the gap between theoretical RL and large-scale practical applications.

Summary updated

Abstract

A great variety of off-policy learning algorithms exist in the literature, and new breakthroughs in this area continue to be made, improving theoretical understanding and yielding state-of-the-art reinforcement learning algorithms. In this paper, we take a unifying view of this space of algorithms, and consider their trade-offs of three fundamental quantities: update variance, fixed-point bias, and contraction rate. This leads to new perspectives on existing methods, and also naturally yields novel algorithms for off-policy evaluation and control. We develop one such algorithm, C-trace, demonstrating that it is able to more efficiently make these trade-offs than existing methods in use, and that it can be scaled to yield state-of-the-art performance in large-scale environments.
BibTeX
@inproceedings{rowland2020adaptive,
  author = {Mark Rowland and Will Dabney and Remi Munos},
  title = {{Adaptive trade-offs in off-policy learning}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2020},
  url = {https://openreview.net/forum?id=GOTu7az3io3},
}
Figure