Marginalized Operators for Off-policy Reinforcement Learning

Yunhao Tang, Mark Rowland, Rémi Munos, Michal Valko

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 and downstream policy optimization algorithms.

Introduction

Off-policy learning—the ability to learn a target policy using data generated by a different behavior policy—is a cornerstone of modern Reinforcement Learning (RL). Historically, the field has approached this challenge through two distinct lenses. Online RL typically utilizes multi-step operators like $n$-step TD or Retrace, which rely on bootstrapping along specific trajectories. While effective for iterative improvement, these methods often suffer from high variance due to the compounding product of importance sampling ratios. Conversely, Offline RL frequently employs marginalized importance sampling (MIS), which focuses on the stationary state-visitation distribution. While MIS reduces variance, it does not naturally integrate into the iterative bootstrapping loops required for many online algorithms.

This paper introduces marginalized operators, a unified framework that bridges the gap between these two paradigms. By averaging multi-step corrections over state-action visitations rather than individual trajectories, these operators achieve significant variance reduction and enable more robust learning from off-policy data.

The Marginalized Operator Framework

The authors propose Marginalized Off-Policy Evaluation Operators ($M^w$). Standard multi-step operators compute a weighted sum of Bellman errors along a specific trajectory. If an action in that trajectory is highly unlikely under the target policy, the "trace" is cut, and the algorithm effectively stops learning from the remainder of that path.

In contrast, marginalized operators utilize TD weights ($w$) to weight Bellman errors based on the discounted visitation distribution. This approach offers several theoretical and practical advantages:

  1. Generality: The authors prove that every contractive multi-step operator (including Retrace and Tree Backup) is a special case of a marginalized operator.
  2. Trace Regeneration: Unlike trajectory-based methods, marginalized operators can "skip" a low-probability action and continue learning from subsequent states. This is possible because they evaluate the probability of reaching a state through any possible path, rather than being restricted to the single path observed in the data.
  3. Saddle-Point Optimization: Because true TD weights are typically unknown, the authors derive a saddle-point (min-max) optimization objective to estimate them. This connects modern deep RL to Fenchel duality and classical Linear Programming (LP) formulations.

Theoretical Insights

A key contribution of this work is the formal proof of variance reduction. The paper demonstrates that in deterministic environments, the marginalized operator always exhibits lower variance than its multi-step counterpart. By smoothing out the noise inherent in individual trajectories through state-visitation averaging, the operator provides a more stable learning signal.

Furthermore, the authors show that the space of contractive marginalized operators is strictly larger than that of traditional multi-step operators. This suggests that there are valid ways to learn from off-policy data that were previously inaccessible to standard trace-based methods.

Empirical Evaluation

The researchers evaluated marginalized operators across three distinct environments to measure estimation error, stability, and performance:

  • Tabular Chain MDP: Used to precisely measure the impact of hyperparameters like noise and horizon length. Marginalized operators consistently reached lower relative error faster than one-step or Retrace baselines.
  • Open World Maze: A 10x10 deterministic maze used to visualize value function propagation. In scenarios where high truncation levels caused standard Retrace to become unstable and diverge, the marginalized operator remained stable and converged to the correct value.
  • Deep RL Benchmarks: The operators were integrated into the TD3 algorithm and tested on continuous control tasks from the MuJoCo and Bullet physics engines (e.g., Cheetah, Walker, and Ant). The results showed performance gains in average return, though the authors noted increased sensitivity to random seeds compared to simpler methods.

Discussion and Limitations

While marginalized operators offer a powerful theoretical bridge and clear variance benefits, they introduce computational overhead. Implementing these operators requires training an additional neural network to estimate the TD weights ($w$) and a discriminator ($q$). This nested min-max optimization can be difficult to tune and may introduce instability into the training loop.

Future research is needed to make weight estimation more robust and scalable for large-scale distributed systems. However, by providing a unified view of bootstrapping and marginalization, this work establishes a new foundation for developing more data-efficient off-policy RL algorithms.

Summary updated

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 and downstream policy optimization algorithms.
BibTeX
@inproceedings{tang2022marginalized,
  author = {Yunhao Tang and Mark Rowland and Rémi Munos and Michal Valko},
  title = {{Marginalized Operators for Off-policy Reinforcement Learning}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2022},
  url = {https://openreview.net/forum?id=JT73IlHcdb},
}
Figure