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:
- Variance: Sensitivity to random data perturbations.
- Contraction Rate: The speed at which the algorithm converges.
- 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.
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.
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