Abstract
In this work, we propose marginalized operators, a new class of off-policy evaluation operators for reinforcement learning. Marginalized operators strictly generalize generic multi-step operators, such as Retrace, as special cases. Marginalized operators also suggest a form of sample-based estimates with potential variance reduction, compared to sample-based estimates of the original multi-step operators. We show that the estimates for marginalized operators can be computed in a scalable way, which also generalizes prior results on marginalized importance sampling as special cases. Finally, we empirically demonstrate that marginalized operators provide performance gains to off-policy evaluation problems and downstream policy optimization algorithms.
Introduction
Off-policy learning—the ability to learn a target policy from data generated by a different behavior policy—is a cornerstone of modern reinforcement learning (RL). However, a significant gap exists between the two primary approaches to this problem. Online RL typically relies on multi-step operators (e.g., Retrace, $n$-step TD) that utilize iterative bootstrapping. While efficient, these methods suffer from high variance due to the multiplication of importance sampling ratios along trajectories. Conversely, offline RL often employs marginalized importance sampling (IS), which focuses on state-action stationary distributions to avoid exploding variance but lacks the iterative efficiency of bootstrapping.
This paper introduces marginalized operators, a framework that bridges this gap by incorporating the stability of marginalized IS into the iterative structure of multi-step bootstrapping.
Marginalized Off-Policy Evaluation Operators
The core innovation is the replacement of multiplicative trace coefficients with learned TD weights ($w$). These weights represent the expected cumulative trace at a specific state-action pair, effectively "marginalizing" the importance ratios over the state distribution.
Key Theoretical Properties
- Strict Generalization: The authors prove that marginalized operators ($M^w$) are a strict generalization of standard multi-step operators. While any contractive multi-step operator has an equivalent marginalized counterpart, the marginalized framework can represent a broader range of learning dynamics.
- Scalable Estimation: Since ideal TD weights are typically unknown, the authors propose a scalable saddle-point (min-max) optimization objective to estimate them, making the approach compatible with deep neural networks.
- LP Duality: The framework reveals a theoretical connection to the dual Linear Programming (LP) formulation of MDPs, where iterative operator application corresponds to solving a sequence of relaxed LPs.
Experimental Evaluation
The proposed methods were tested across three distinct environments:
- Chain MDP: A tabular environment for precise measurement of evaluation error under varying noise and off-policy levels.
- Open World: A $10 \times 10$ deterministic maze used to visualize value function propagation.
- Deep RL Benchmarks: Continuous control tasks from the DeepMind Control Suite and Bullet physics, using the TD3 algorithm to evaluate performance in high-dimensional settings.
Key Results
Tabular Stability and Convergence
In the Chain MDP experiments, marginalized operators demonstrated significantly faster convergence and lower error compared to Retrace and one-step methods.
As shown in the figure above, marginalized operators (red) maintain stability even as parameters like horizon or off-policy levels increase, whereas traditional multi-step methods like Retrace (blue) can become unstable, particularly when truncation parameters are large.
Information Propagation
The "Open World" maze visualization highlights how marginalized operators efficiently propagate reward information.
While one-step methods are slow to propagate information and Retrace becomes noisy at higher truncation levels ($c=2$), marginalized operators provide a smooth and rapid propagation of the value function from the goal back to the starting state. This "trace regeneration" allows the agent to extract more information from behavior data, even when specific trajectories might be "cut off" by zero importance ratios in standard methods.
Deep RL Performance
When integrated into the TD3 algorithm, marginalized multi-step updates yielded consistent performance improvements across several continuous control tasks. While the authors noted higher variance across random seeds—likely due to the added complexity of learning TD weights online—the overall performance gains suggest that the variance reduction benefits of marginalization translate to complex, non-linear function approximation.
Limitations and Future Directions
The primary trade-off for the improved stability of marginalized operators is computational overhead. Estimating the density ratios requires an additional neural network and a min-max optimization step. Furthermore, the online estimation of these weights can introduce new sources of instability. Future research will focus on more robust ways to combine marginalized and traditional multi-step operators and scaling these techniques to large-scale distributed RL systems.
Summary updated