Abstract
Off-policy reinforcement learning algorithms must navigate a fundamental trade-off between update variance, fixed-point bias, and contraction rate. This paper introduces a unifying framework to characterize these trade-offs and proposes C-trace, an adaptive algorithm that dynamically manages these quantities. C-trace bridges the gap between theoretically sound methods and high-performing empirical techniques, matching or exceeding state-of-the-art results in deep RL benchmarks like Atari-57.
Introduction: The Theory-Practice Gap
Off-policy learning—learning about a target policy using data from a different behavior policy—is critical for data efficiency in reinforcement learning. However, a significant gap exists between theory and practice. Theoretically sound algorithms like Importance Sampling or Retrace often suffer from high variance or slow convergence. In contrast, state-of-the-art deep RL agents often use "uncorrected" $n$-step returns, which lack theoretical guarantees but perform exceptionally well. This paper investigates why these uncorrected methods succeed and how to design principled algorithms that capture their benefits.
The Off-Policy Trilemma
The authors formalize the off-policy learning problem as a "trilemma" involving three fundamental axes:
- Update Variance: The noise introduced by stochastic data samples.
- Fixed-Point Bias: The error in the value function the algorithm converges to in the limit of infinite data.
- Contraction Rate: The speed at which the algorithm converges toward its fixed point.
Mathematically, it is impossible for an update based on limited data to simultaneously achieve low variance, a fast contraction rate, and zero fixed-point bias across all environments. Uncorrected returns succeed by accepting high bias in exchange for drastically lower variance and faster contraction, which is often more valuable early in training than asymptotic perfection.
Methods: $\alpha$-Retrace and C-trace
To exploit these trade-offs, the authors introduce two novel methods:
- $\alpha$-Retrace: A modification of the standard Retrace algorithm that evaluates a mixture of the target and behavior policies, controlled by a parameter $\alpha$. By shifting the target closer to the behavior policy, $\alpha$-Retrace reduces "trace cutting," trading a small amount of bias for a significantly faster contraction rate.
- C-trace: An adaptive version of $\alpha$-Retrace that dynamically adjusts $\alpha$ online using a stochastic approximation (Robbins-Monro). C-trace is designed to hit a user-defined target contraction rate, effectively matching the speed of uncorrected methods while maintaining a principled, bounded bias.
Key Results
Evaluations on tabular MDPs and the Atari-57 suite demonstrate the effectiveness of this approach. In tabular settings, $\alpha$-Retrace successfully interpolates between the high-bias/fast-contraction of uncorrected returns and the zero-bias/slow-contraction of standard Retrace.
When integrated into deep RL architectures, C-trace-DQN significantly outperformed both Double DQN and Retrace-DQN. Furthermore, replacing uncorrected returns with C-trace in the massive-scale R2D2 agent resulted in performance that matched or slightly exceeded the original state-of-the-art across mean, median, and human-gap metrics on Atari-57.
Conclusion
By providing a rigorous framework for the trade-offs inherent in off-policy learning, this work explains the empirical success of biased methods and provides a principled path forward. C-trace offers a robust mechanism for balancing convergence speed and accuracy, successfully bridging the gap between reinforcement learning theory and large-scale practice.
Summary updated