What are marginalized operators for off-policy reinforcement learning evaluation?

Estimating a target policy from another policy's data

Off-policy evaluation asks how well a target policy would perform, using data collected by a different behavior policy. The gap between the two policies is the central difficulty: the data are distributed according to the behavior policy, while the value being estimated belongs to the target policy.

The paper situates its contribution inside the online setting, where agents keep collecting new data, and where much prior work builds on multi-step operator-based methods. A multi-step operator updates a value estimate by combining Bellman errors over several steps, weighted by step-wise trace coefficients that control how much each step contributes. Retrace is the named example of such an operator in the paper.

TD weights replace step-wise traces

A marginalized operator is defined through a set of TD weights, written w, that assign a weight to each pair of state-action transitions. Instead of applying trace coefficients step by step along a trajectory, the operator aggregates the behavior policy's transition structure into these weights and then applies them to Bellman errors.

The key theoretical result is an equivalence: for any multi-step operator with step-wise trace coefficients c, there is a corresponding choice of TD weights w such that the marginalized operator equals the original multi-step operator. The paper states this as Proposition 3.2 and gives the explicit construction of w in terms of an expectation over trajectories started from each state-action pair. This is what makes the claim of strict generalization concrete rather than rhetorical: Retrace and similar operators are recovered as special cases by choosing the matching weights.

A wider contractive family than trace-based operators

Generalization alone would be a modest claim if the new class contained nothing beyond the old one. The paper addresses this directly. Corollary 3.3 states that the set of contractive multi-step operators is contained in the set of contractive marginalized operators for the same tuple of dynamics, reward, policies, and discount factor.

Proposition 3.4 then shows that the containment can be strict for some such tuples, and can also be an equality for others. In other words, whether marginalized operators add genuinely new contractive operators depends on the specific problem setting, not on a universal claim. The paper's counterexample for the strict case uses a deterministic chain MDP, and a separate lemma shows that restricting to Markovian traces leaves the mapping non-surjective even where non-Markovian traces can reach positive weights.

Contraction depends on a residual error term

For a marginalized operator to be useful in iterative value estimation, it must be a contraction. The paper characterizes this through a residual error vector built from the one-hot encoding of the starting state-action pair, the target policy's transition matrix, and the TD weights. The local contraction rate at a state-action pair is the 1-norm of that residual divided by one minus the discount factor.

This yields a checkable condition: the operator is contractive when the maximum of that residual norm over state-action pairs is below one minus the discount factor. The condition is stated per state-action pair, so contraction is a property the weights must earn locally rather than a blanket guarantee that comes with the operator class.

Why sample estimates may have lower variance

The abstract claims that marginalized operators suggest a form of sample-based estimate with potential variance reduction relative to sample-based estimates of the original multi-step operators. The mechanism the paper points to is the aggregation step: the weights are defined as expectations over the behavior policy's dynamics, so a sample-based estimate can target those aggregated weights rather than accumulating noisy per-step trace products along each trajectory.

The word potential matters here. The variance-reduction claim is presented as a property of the suggested estimator form, not as a theorem with a stated variance ratio in the abstract. Readers comparing this to importance-sampling estimators should treat the variance benefit as a motivation the paper develops and tests, not as a guaranteed magnitude.

Scalable estimation and the connection to marginalized importance sampling

A class of operators is only practical if its weights can be estimated without enumerating the full state-action space. The paper shows that estimates for marginalized operators can be computed in a scalable way, and that this computation generalizes prior results on marginalized importance sampling as special cases.

The appendix makes the connection explicit. The saddle-point objective used to estimate the weights differs from the earlier dualdice-style objective only in the target policy, and can be read as running that algorithm with a sub-probability behavior policy. For tabular settings, the paper also gives a direct Monte-Carlo procedure that accumulates cumulative step-wise traces per state-action pair and updates the weight table with a step size of 0.1, without solving a saddle-point problem.

What the empirical gains do and do not show

The paper reports empirically that marginalized operators provide performance gains to off-policy evaluation and to downstream policy optimization algorithms. That is the extent of the quantitative claim available in the evidence: the abstract states gains in both settings without reporting effect sizes, baselines, or the environments used for the headline comparison.

The scope is therefore the paper's own experimental settings, and the claim should be read as evidence that the operator class is usable end to end, not as a calibrated estimate of how much any particular algorithm improves. The theoretical results, by contrast, are stated for general tuples of dynamics, reward, target policy, behavior policy, and discount factor, subject to the contraction condition above.

Where the framework changes the comparison

The paper's own framing of its value is a bridge: marginalized operators connect multi-step operators and marginalized importance sampling, which had been treated as two separate frameworks for off-policy evaluation. The practical consequence is that a reader choosing between them no longer faces an either-or decision at the level of operator design, because a multi-step operator is a marginalized operator with a particular weight choice.

The judgment this paper supports is therefore conditional on the problem tuple. If the trace-based operator you want is already contractive, the marginalized form reproduces it; the added room matters when the weight-based family is strictly larger for your dynamics, policies, and discount factor, which Proposition 3.4 shows happens for some tuples and not others. The paper's suggested next step is to combine marginalized operators with traditional multi-step operators, in the same spirit as prior combinations of marginalized and step-wise importance sampling.

Sources used in this answer