PaperlayerView exact revision on arXiv

Source-linked AI summary

Marginalized Operators for Off-policy Reinforcement Learning

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

arXiv:2203.16177v1cs.LGstat.ML

TL;DR

Off-policy evaluation asks how to estimate a target policy’s value from data generated by another policy, while online bootstrapping and offline importance-sampling approaches are difficult to combine. The paper proposes marginalized operators that generalize multi-step operators and connect to marginalized importance sampling, and reports performance gains in evaluation and downstream optimization.

  • Problem

    Off-policy evaluation must estimate a target policy’s value from data collected under a different policy, while offline importance-sampling methods generally do not naturally incorporate bootstrapping for online learning.

    Source: §1 · p. 1

  • Method

    The paper proposes marginalized off-policy evaluation operators that generalize multi-step operators and support scalable estimates connected to marginalized importance sampling.

    Source: §1 · p. 1

  • Results

    Marginalized operators provide performance gains in off-policy evaluation and downstream policy optimization.

    Source: §1 · pp. 1–2

  • Takeaways & Limitations

    Marginalized operators bridge multi-step operators and marginalized importance sampling in a unified framework for off-policy evaluation.

    Source: §7 · p. 9

    The analysis covers multi-step operators formed as weighted mixtures of Bellman errors, excluding operators that bias the fixed point for faster contraction.

    Source: §1 · p. 2

Abstract

from arXiv · show

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.

1 Introduction

Off-policy evaluation estimates a target policy’s value from data collected under another policy, but online bootstrapping methods and offline importance-sampling methods are difficult to bring together. The paper proposes marginalized operators to bridge these approaches and reports gains in evaluation and downstream optimization.

1 Introduction

  • Online multi-step methods use bootstrapping to improve estimates iteratively, which is useful when the target policy changes slowly.New-policy predictions can draw on predictions for old policies.Source: §1 · p. 1
  • Offline methods often use marginalized importance sampling for variance reduction, but generally lack bootstrapping and are challenging to apply directly to online learning.The offline setting does not permit further data collection.Source: §1 · p. 1
  • Marginalized operators generalize multi-step operators as special cases and connect their stochastic estimates to marginalized importance sampling.The paper also proposes a scalable way to compute estimated marginalized operators.Source: §1 · p. 1
  • The paper reports performance gains from marginalized operators in off-policy evaluation and downstream policy optimization.Source: §1 · pp. 1–2
  • The analysis is limited to multi-step operators formed as weighted mixtures of Bellman errors, excluding operators that bias the fixed point for faster contraction.The uncorrected n-step operator is given as an example of an excluded operator.Source: §1 · p. 2

2 Background

The background sets up discounted Markov decision processes, then introduces multi-step off-policy operators and marginalized importance sampling. It describes how the latter expresses policy values using visitation ratios that must be estimated from off-policy data.

2.1 Markov decision processes

  • The setup is an infinite-horizon discounted MDP with state-action rewards, transitions, and policies; rewards are assumed deterministic, though most results extend to stochastic rewards.Source: §2.1 · p. 2

2.2 Multi-step off-policy evaluation

  • Multi-step operators estimate Q at a starting state-action pair by accumulating TD errors weighted by trace coefficients that may depend on trajectory history.Source: §2.2 · p. 2
  • When 0 ≤ c_t ≤ π(a_t|x_t)/μ(a_t|x_t), Qπ is the unique fixed point; cutting traces after one step recovers the one-step Bellman operator.Source: §2.2 · p. 2

2.3 Off-policy evaluation via marginalized importance sampling

  • Marginalized importance sampling expresses Qπ using discounted visitation ratios and rewards.Source: §2.3 · p. 2
  • Because the marginalized ratios are generally unknown, off-policy data require ratio estimates, for which scalable algorithms are described.Source: §2.3 · p. 2

3 Marginalized Off-Policy Evaluation Operators

Marginalized operators apply TD weights to Bellman errors and encompass contractive multi-step operators. Their broader contractive class includes operators with no multi-step equivalent.

3.1 Properties of the marginalized operator

  • The marginalized operator combines TD weights with Bellman errors, and Qπ is a fixed point for any choice of weights.Contraction depends on the weights’ balance-equation residual being sufficiently small; exact balance is not required.Source: §3 · p. 2, §3.1 · p. 3

3 Marginalized Off-Policy Evaluation Operators

  • Marginalized operators can recover contractive multi-step operators as special cases.This follows by choosing weights appropriately; the family is not limited to multi-step operators.Source: §3.1 · p. 3, §3.2 · p. 3

3.2 Multi-step off-policy evaluation operators as special cases

  • Choosing equivalent TD weights makes a marginalized operator identical to any given multi-step operator, so the contractive marginalized class contains the contractive multi-step class.Retrace imposes a nonnegative-residual constraint, stronger than the condition that the marginalized operator be contractive.Source: §3.2 · p. 3, A Proof of theoretical results · p. 12

3.3 Further characterizations of contractive marginalized operators

  • Some contractive marginalized operators have no multi-step equivalent because marginalized weights can regenerate traces after a zero, unlike multiplicative cumulative traces.Parameterized TD weights can therefore directly represent contractive operators outside the multi-step family.Source: §3.3 · p. 4

4 Understanding Marginalized Off-Policy Evaluation Operators

The section examines unbiased stochastic estimates, their variance properties, and an LP interpretation linking relaxed policy-evaluation problems to contractive operators.

4.1 Stochastic estimates of evaluation operators

  • Unbiased stochastic estimates can be constructed for marginalized operators, with expectations equal to the operators’ outputs.The section considers both trajectory-based and random-time estimates.Source: §4.1 · p. 4

4.2 Connections to conditional importance sampling

  • Conditioning cumulative traces on a state-action pair connects marginalized operators to conditional importance sampling and can reduce estimator variance.The random-time variance guarantee requires deterministic transitions and rewards; it is not established for stochastic rewards.Source: §4.2 · p. 4
  • Using estimated TD weights trades the variance reduction of marginalized importance sampling for potential bias when the weights are imperfect.The quality of the estimated weights affects downstream updates.Source: §4.2 · p. 5
  • The TD-weight interpretation also extends the approach from Q-function evaluation to value-function operators such as V-trace.The passage points to Appendix C for detailed results.Source: §4.2 · p. 5

4.3 Policy evaluation via linear programs and its connections to contractions

  • Relaxed dual LPs permit balance-equation violations controlled by η, and their feasible region characterizes TD weights with contraction rate at most η.The resulting sequence of LP values converges to Qπ through repeated application of a marginalized operator.Source: §4.3 · pp. 5–6

5 Estimating TD Weights

The section develops methods to estimate marginalized TD weights and to optimize contraction directly, including when the weights do not exactly match a multi-step operator.

5 Estimating TD Weights

  • The proposed TD-learning approach estimates equivalent TD weights using a scoring function or critic and an optimization objective.The estimated weights can then approximate those corresponding to a chosen step-wise trace.Source: §5 · p. 6
  • A richer scoring-function class yields an estimate closer to the equivalent TD weights under the stated approximation result.The section relates the result to marginalized importance sampling as a special case.Source: §5 · p. 6

5.1 Optimizing for the contraction rate

  • The objective can be used to minimize the local contraction rate directly, without choosing a particular step-wise trace.For the stated scoring-function class, the contraction rate is bounded by the objective’s maximum loss.Source: §5.1 · pp. 6–7
  • Imperfectly estimated weights can still define a contractive marginalized operator whose repeated application converges to the correct value.The weights need not exactly match those for any particular trace coefficient.Source: §5.1 · p. 7

6 Experiments

Experiments compare marginalized operators with one-step and multi-step baselines in tabular MDPs and deep reinforcement learning. The results show faster convergence or greater stability in several settings, with noisy rewards and deep-estimator variability qualifying the gains.

6 Experiments

  • The experiments use tabular TD weights in tabular MDPs and function approximations for TD-weight estimates in deep RL.The deep experiments use continuous-control tasks and a neural-network estimator wψ to approximate wc.Source: §6 · p. 7, §6.3 · p. 9

6.1 Chain MDP

  • As final-reward noise increases, marginalized operators and Retrace converge to higher error than the one-step operator; short bootstrap horizons may be preferable.The authors speculate that multi-step methods bootstrap noise faster, while one-step backups dampen variance more.Source: §6.1 · pp. 7–8
  • Marginalized operators converge faster than Retrace, which outperforms the one-step operator; increasing action count or horizon makes evaluation harder.More actions increase estimation variance, while longer horizons require more iterations to propagate values.Source: §6.1 · p. 7, Figure 1 · p. 8
  • With larger Retrace truncation c̄, performance is less stable and asymptotic error increases, while the marginalized operator converges more stably.c̄=0 recovers the one-step operator, whereas c̄=∞ recovers full importance sampling.Source: §6.1 · p. 8

6.2 Open World

  • In the Open World MDP, one-step propagation is slow; at c̄=2 Retrace becomes unstable while its marginalized counterpart remains more stable.At c̄=1, Retrace and the marginalized operator perform similarly; the observations suggest potential variance reduction from marginalization.Source: Figure 2 · p. 8, §6.2 · p. 8

6.3 Deep RL experiments

  • Marginalized multi-step updates provide marginal average-performance gains over vanilla multi-step updates on continuous-control tasks, but seed variation is relatively large.The experiments use deep RL implementations with function-approximated TD weights.Source: Figure 3 · p. 9, §6.3 · p. 9

7 Conclusion

The conclusion presents marginalized operators as a general off-policy evaluation framework that connects multi-step operators with marginalized importance sampling. It identifies combining marginalized operators with traditional multi-step operators as a direction for future work.

7 Conclusion

  • Marginalized operators bridge multi-step operators and marginalized importance sampling within a unified off-policy evaluation framework.The framework treats operator-based approaches and marginalized estimation methods as compatible, and suggests combining techniques from both.Source: §7 · p. 9
  • Combining marginalized operators with traditional multi-step operators is identified as a future research direction.The proposed combination is analogous to marginalized importance sampling combined with step-wise importance sampling.Source: §7 · p. 9

A Proof of theoretical results

This section proves theoretical properties of marginalized operators, including fixed-point, contraction, and equivalence results, relationships between their weights and multi-step traces, and a random-time representation with a variance reduction result under deterministic transitions and rewards. It also establishes a Bellman equation for the marginalized visitation quantity and guarantees for objective-based error bounds and relaxed LP iterations, including contraction for arbitrary choices from the specified feasible sets.

Propositions 3.1–3.2

  • For any TD weights, Qπ solves the marginalized-operator fixed-point equation, whose contraction rate is derived from its residual weights.The proof also gives a condition under which the operator is contractive.Source: A Proof of theoretical results · p. 12

Proposition 3.2 and Corollary 3.3

  • For any multi-step operator with step-wise traces, corresponding marginalized weights can yield an equivalent operator; the corollary connects their contractive subclasses.The equivalence is stated as Mwc = Rc, and the corollary derives the relationship between the spaces of contractive operators.Source: A Proof of theoretical results · pp. 12–14

Proposition 3.4

  • A Markovian-trace mapping can fail to reach all contractive marginalized weights, and the broader mapping can also fail to be surjective for some MDP tuples.The Markovian counterexample uses a deterministic chain; the broader counterexample shows that even allowing non-Markovian traces need not make the mapping surjective.Source: A Proof of theoretical results · pp. 14–15
  • In a special two-state, one-action setting, every marginalized weight can be realized by non-Markovian step-wise traces.The constructed traces yield the required equality for either state-action pair.Source: A Proof of theoretical results · pp. 15–16

Proposition 4.1

  • Equivalent TD weights equal the conditional expected cumulative trace product at a geometrically sampled random time.The random time has distribution P(τ = n) = (1 − γ)γ^n for n ≥ 0.Source: A Proof of theoretical results · p. 16

Corollary 4.2

  • With deterministic transitions and rewards, the random-time marginalized estimate has the same expectation but smaller variance than the multi-step estimate.The proof obtains the variance comparison using the tower property of variance.Source: A Proof of theoretical results · p. 16

Proposition A.5

  • Proposition A.5 characterizes equivalent TD weights and associated nonnegative measures for trace coefficients bounded by the policy probabilities.The excerpt states the nonnegative-measure condition for 0 ≤ c(x, a) ≤ π(x, a).Source: A Proof of theoretical results · p. 16

Bellman equation proof

  • The proof derives a Bellman equation for d^w_c from its definition and also gives a matrix-notation derivation.The matrix proof expresses d^w_c using the visitation distribution matrix before obtaining the Bellman equations.Source: A Proof of theoretical results · p. 17

Proposition 5.2

  • With ±q in Q, the error |wψ(x∗, a∗) − w(x∗, a∗)| is bounded by maxq∈Q L(q, wψ), which also bounds the contraction rate when wc = wπ,µ.The scoring function q is defined from the multi-step transition probability, and the sub-probability measure ensures that T˜π converges.Source: A Proof of theoretical results · p. 18

Proposition 4.3 and more general results

  • The relaxed LP iteration is contractive with fixed point Qπ, and the contraction bound still holds when an arbitrary element of Dx,a is chosen.The generalization gives ∥Qt+1 − Qπ∥∞ ≤ η ∥Qt − Qπ∥∞.Source: A Proof of theoretical results · pp. 18–19

B Relations between different stochastic estimators

Marginalizing stochastic multi-step estimates can reduce variance under suitable conditions, though some variance orderings remain unclear. The sections extend this framework to V-trace and describe estimating TD weights for off-policy evaluation and actor-critic learning.

B Relations between different stochastic estimators

  • Under suitable conditions, marginalizing over random times or state-action pairs suggests potential variance reductions, but some operator variance orderings remain unclear.Figure 4 uses blue arrows for time marginalization and a red arrow for state-action marginalization.Source: B Relations between different… · p. 19, Figure 4 · p. 19

C Marginalized V-trace operator

  • Marginalized V-trace uses state-dependent weights and state-action-dependent ρ values to form an operator from V-trace TD errors.The section identifies the behavior policy’s discounted visitation distribution as part of this construction.Source: C Marginalized V-trace operator · p. 20

C.1 State-marginalized V-trace operator.

  • For V-trace, the multi-step and marginalized operators are equivalent in expectation, and equivalent TD weights can be obtained by conditional expectation.The passage also describes estimating weights through a saddle-point objective and bounding the contraction rate using its loss.Source: §C.1 · p. 20

D.1 Multi-step RL algorithms with TD weights

  • The actor-critic procedure estimates TD weights from behavior-policy trajectories, uses marginalized-operator targets to update its Q-function, then improves the policy.The policy can be updated by policy gradient or greedily with respect to the new Q-function.Source: §D.1 · p. 21

E Fenchel-duality based approach to estimating TD weights

  • The Dualdice saddle-point formulation is introduced to bypass double sampling, a problem that also arises when directly using the transition matrix to estimate TD weights.The extension estimates TD weights with an objective whose saddle point recovers those weights.Source: §E.1 · p. 22, §E.2 · p. 22

E.2 Fenchel duality-based estimation for TD weights

  • The TD-weight objective can be interpreted as Dualdice with a modified target policy, equivalently a sub-probability behavior policy formed using trace coefficients.The construction assumes the trace-weighted behavior policy is a sub-probability vector.Source: §E.2 · p. 22

F.1 Details on tabular estimations of TD weights

  • With tabular representations for both the critic and weight estimates, TD weights can be derived directly from off-policy samples without solving a saddle-point optimization.The procedure is described as a Monte Carlo estimate of the TD weights.Source: §F.1 · pp. 22–23

F.2.1 Chain MDP

The chain-MDP section describes iterative Q-function estimation using operator-based targets and evaluates prediction error at the initial state. Figure 5 compares algorithm performance over iterations, averaged across 50 runs.

F.2.1 Chain MDP

  • At each iteration, the agent collects one trajectory and updates Q-values toward estimates generated by an operator baseline.The update uses step size α = 0.1.Source: §F.2.1 · p. 23
  • Relative error is measured as average prediction error at the initial state, using analytically computed Qπ values as the reference.The initial state is the chain’s leftmost state.Source: §F.2.1 · p. 23
  • Figure 5 plots algorithm performance against iterations, with each plot averaged over 50 runs.The caption identifies the axes but supplies no outcome comparison.Source: Figure 5 · p. 23

F.2.2 Open world

In the open-world visualization, TD weights vary across future state-action pairs according to the starting location. The paper also reports that marginalized operators’ one-shot evaluation gains carry over to policy optimization, unlike Retrace’s gains over one-step evaluation.

F.2.2 Open world

  • Each heat map fixes an initial state-action location and displays TD weights over typical future state-action pairs; the four starting locations are the square’s corners.The caption describes each state’s trace as the average TD weight across its actions.Source: §F.2.2 · p. 23, Figure 6 · p. 24
  • With a start near the bottom-right terminal state, TD weights are low for most pairs except nearby ones, consistent with the random behavior policy rarely visiting distant pairs.The authors interpret this pattern as assigning less influence to distant Bellman errors in the average estimate.Source: §F.2.2 · p. 23
  • For soft policy iteration, the behavior policy is uniformly random and each update mixes the current policy with a greedy target using α = 0.1; hard iteration uses α = 1.The target policy starts random, and returns are estimated by Monte Carlo from uniformly sampled states.Source: §F.2.2 · p. 24
  • Marginalized operators’ one-shot evaluation gains carry over to policy optimization, while Retrace performs similarly to the one-step operator under soft policy iteration and shows no advantage under hard iteration.Under hard iteration, the authors suggest greedy policies may cut Retrace traces quickly, slowing optimization.Source: §F.2.2 · p. 24

F.3 Further details on deep RL experiments

The deep RL experiments use continuous-control locomotion benchmarks across simulation engines and compare marginalized-operator targets with TD3 and a Retrace variant. The passage also specifies the networks and training setup used for these implementations.

Benchmarks

  • The experiments use continuous-control robotics locomotion tasks in the DeepMind control suite and Bullet physics, with sensory state inputs and position or torque controls.The passage also identifies MuJoCo as one of the simulation engines considered.Source: §F.3 · p. 24

Algorithms

  • TD3 is the baseline, using a deterministic policy and critic, with one-step targets of the form r(x, a) + γQφ(x′, πθ(x′)).The passage attributes double Q-learning and target networks to TD3’s stabilization techniques.Source: §F.3 · p. 24
  • Marginalized-operator targets are formed as MwψQ; the density estimator wψ and discriminator qη are trained using the objective in Eqn (10).The estimator and discriminator parameters are optimized with alternating gradient descents and ascents.Source: §F.3 · p. 24

Baseline multi-step algorithm

  • The multi-step baseline is a variant of Retrace (Munos et al., 2016), with targets computed recursively and coefficients c(x, a) based on λ and the policy-to-behavior ratio.The experiments use λ = 0.7; the stated Retrace Q-target variant was found not to work stably, so a delayed target-network estimate is used instead.Source: §F.3 · pp. 24–25

Architecture and hyper-parameters

  • Networks share two 256-unit hidden layers; mini-batches contain 100 replay-buffer samples, and Adam uses learning rates of 10^-3 except 10^-4 for the estimator.The estimator output is transformed to be strictly non-negative; implementations are built on SpinningUp, with remaining details referred to the code base.Source: §F.3 · p. 25
Loading 2203.16177v1…