Source-linked AI summary
Off-Policy Evaluation via the Regularized Lagrangian
Mengjiao Yang, Ofir Nachum, Bo Dai, Lihong Li, Dale Schuurmans
TL;DR
Off-policy evaluation estimates a target policy's value from data collected by other, often unknown, behavior policies, while DICE estimators have distinct derivations despite similar minimax forms. This paper unifies those formulations as regularized Lagrangians of one linear program and analyzes alternatives. It finds that dual estimates offer more flexibility for stabilizing optimization while preserving asymptotic unbiasedness, and that novel configurations improve observed performance.
Problem
Behavior-agnostic off-policy evaluation seeks target-policy value from data gathered by other policies, while existing DICE methods have distinct derivations despite similar minimax forms.
Source: §1 · p. 1Method
The paper represents existing DICE formulations as regularized Lagrangians of a shared linear program and analyzes choices of constraints, regularization, and value estimation.
Source: §1 · p. 2Results
Dual estimates offer greater flexibility than primal estimates for incorporating optimization stabilizers while preserving asymptotic unbiasedness, and alternative estimators exhibit improved performance.
Source: §6 · p. 11Takeaways & Limitations
The findings suggest exploring OPE configurations beyond existing DICE algorithms, particularly dual estimates for offline OPE.
Source: §6 · p. 11Conditional expectation operators inside nonlinear functions create a biased gradient estimator, so vanilla stochastic gradient descent is not applicable.
Source: §3.2 · p. 5
Abstract
from arXiv · showhide
The recently proposed distribution correction estimation (DICE) family of estimators has advanced the state of the art in off-policy evaluation from behavior-agnostic data. While these estimators all perform some form of stationary distribution correction, they arise from different derivations and objective functions. In this paper, we unify these estimators as regularized Lagrangians of the same linear program. The unification allows us to expand the space of DICE estimators to new alternatives that demonstrate improved performance. More importantly, by analyzing the expanded space of estimators both mathematically and empirically we find that dual solutions offer greater flexibility in navigating the tradeoff between optimization stability and estimation bias, and generally provide superior estimates in practice.
1 Introduction
The paper unifies behavior-agnostic DICE estimators through a shared linear program and studies a broader set of estimator choices. Its analysis finds that dual solutions offer greater flexibility in balancing optimization stability and estimation bias, while new configurations improve observed outcomes.
1 Introduction
- Off-policy evaluation estimates a target policy's value from experience gathered by other policies, which may be unknown when deployment is costly or risky.This setting motivates behavior-agnostic OPE methods.Source: §1 · p. 1
- DICE estimators share a similar minimax optimization form despite deriving from apparently distinct approaches.The introduction contrasts DualDICE, GenDICE, and GradientDICE derivations.Source: §1 · p. 1
- Existing DICE formulations are regularized Lagrangians of the same linear program, whose dual form provides a succinct framework for off-policy evaluation.The paper uses this view to identify choices involving constraints, regularization, and how optimized solutions are converted to policy values.Source: §1 · p. 2
- Dual solutions offer greater flexibility than primal solutions for stabilizing optimization while preserving asymptotic unbiasedness, and novel configurations improve observed outcomes.The study examines these choices theoretically and empirically across domains and function approximators.Source: §1 · p. 2
2 Background
The background defines the MDP and policy-value setting, then introduces off-policy evaluation from a fixed dataset and the distribution correction used by DICE methods.
2 Background
- An infinite-horizon MDP is specified by state and action spaces, rewards, transitions, an initial-state distribution, and a discount factor; policies generate actions and state transitions.The paper focuses on the discounted case unless otherwise specified, and states that the same conclusions generally hold for the undiscounted case.Source: §2 · p. 2, §2.1 · p. 2
2.1 Policy Evaluation
- Policy value is the normalized expected per-step reward, expressible through policy Q-values or state-action visitations under an ergodicity assumption.For γ < 1 the cited equation has a unique solution; for γ = 1 the assumption reduces to ergodicity under a restriction on d.Source: §2.1 · pp. 2–3
2.2 Off-policy Evaluation via the DICE Family
- OPE estimates target-policy value from a finite dataset of unknown distribution; DICE methods approximate the stationary correction ratio dπ/dD and use it to estimate value.DualDICE and GenDICE use different objectives, while GradientDICE extends GenDICE with linear parametrization for convex-concave optimization with convergence guarantees.Source: §2.2 · p. 3
3 A Unified Framework of DICE Estimators
The section unifies DICE estimators through a linear program for policy evaluation and its regularized Lagrangian. It studies how optimization choices affect bias and stability, and shows how existing estimators fit within the framework alongside a new high-performing variant.
3 A Unified Framework of DICE Estimators
- The framework treats existing DICE formulations as regularized Lagrangians of one LP and identifies additional configurations for off-policy evaluation.Its d-LP formulation represents the target policy's state-action stationary distribution.Source: §3 · p. 3
3.1 Linear Programming Representation for the dπ-distribution
- The d-LP expresses policy value through the stationary state-action distribution, while its primal LP has solution Qπ; strong duality gives both the same value ρ(π).Directly solving the LPs is difficult with large or uncountable state-action spaces and off-policy samples, motivating a Lagrangian approach.Source: §3.1 · pp. 3–4
3.2 Regularizations and Redundant Constraints
- Direct ALM regularization faces a double-sample difficulty: nonlinear Bellman-residual terms make vanilla stochastic gradient estimates biased.The paper explores other regularizations and redundant constraints to add structure without changing optimal solutions, while analyzing when they bias value estimates.Source: §3.2 · pp. 4–5
- Regularizations and redundant constraints can improve optimization structure, but some choices shift solutions; dual estimates remain unbiased under more configurations than primal estimates.Without function approximation, dual solutions are unbiased in 6 of 8 configurations, versus 1 for primal solutions; the primal case also requires excluding positivity.Source: §3.2 · pp. 5–6
3.3 Recovering Existing OPE Estimators
- The unified configuration space recovers existing OPE estimators and includes a newly identified variant that achieves the best performance.Examples include DualDICE, GenDICE, GradientDICE, DR-MWQL, MWL, LSTDQ, and Algae Q-LP.Source: §3.3 · pp. 6–7
4 Experiments
Across Grid, Reacher, and Cartpole, the dual estimator with regularized dual variables performs best overall, and the experiments identify a configuration that generally works well. The results also show how regularization, constraints, and optimization form affect stability and estimation bias.
4 Experiments
- The dual estimator with regularized dual variables yields the best performance across the evaluated tasks, and the paper recommends it with α_R = 1, redundant constraints, and Lagrangian optimization.The evaluation spans tabular, discrete-control, and continuous-control tasks, with linear and neural-network parametrizations and behavior policies of different noise levels.Source: §4 · p. 7
- Dual regularization yields better estimates than primal regularization, and α_R = 1 has a slight advantage over α_R = 0 in the empirical summary.The summary also reports that including the redundant constraints improves stability and estimation performance, while the unconstrained primal form is more stable but more biased than the minimax regularized Lagrangian.Source: §4 · p. 7
4.1 Choice of Estimator (ˆρQ, ˆρζ, or ˆρQ,ζ)
- The dual estimator consistently gives the best estimates across tasks and behavior policies; primal estimates are significantly worse, while Lagrangian estimates generally have higher variance than dual estimates.The Lagrangian can improve on the primal, but the authors suggest it may not benefit from the doubly robust property in this practical setting because both solutions are biased.Source: §4.1 · p. 7, Figure 1 · p. 8
- Dual estimates remain roughly unchanged after reward scaling or shifting when transformed back to the original scale, whereas primal estimates are sensitive to reward transformations.With linear parametrization, primal estimates can fail to converge within the same number of gradient updates after scaling or shifting; the figure also compares neural-network parametrization.Source: §4.1 · p. 8, Figure 2 · p. 9
4.2 Choice of Regularization (αζ, αR, and αQ)
- Dual regularization avoids the bias seen with primal regularization when α_R = 1, and changing α_R between 0 and 1 has little effect on dual-regularized estimates in these experiments.The authors caution that this invariance may not generalize to other tasks; dual regularization permits choosing α_R based on the reward function.Source: §4.2 · p. 8
4.3 Choice of Redundant Constraints (λ and ζ ≥0)
- Removing the normalization constraint increases training instability and approximation error even when γ < 1, while removing the positivity constraint harms optimization stability and estimator accuracy.The supplied Figure 2 caption also reports that dual estimates are robust to reward transformations, whereas primal and Lagrangian estimates are sensitive to reward values.Source: §4.3 · pp. 8–9, Figure 2 · p. 9
4.4 Choice of Optimization (Lagrangian or Unconstrained Primal Form)
- The unconstrained primal form reduces variance on Grid and improves estimates on Cartpole, but creates bias on continuous-action Reacher; the authors generally favor the Lagrangian unless actions are discrete and dynamics stochasticity is low.Grid and Cartpole have discrete action spaces; the authors attribute Reacher's bias to difficulty taking the expectation over next-step samples.Source: §4.4 · p. 9
5 Related work
Off-policy evaluation methods often rely on importance reweighting, which can require knowledge or estimation of the behavior policy and can have variance exponential in the horizon. The DICE family and related convex-duality approaches offer alternative formulations, while the paper situates its approach among prior work.
5 Related work
- Many off-policy evaluation approaches use importance reweighting, often require knowing or estimating the behavior policy, and can suffer variance exponential in the horizon.The passage identifies these requirements and variance as limitations on their applications.Source: §5 · p. 9
- Figure 4 reports that positivity constraints improve training stability, normalization is essential at γ = 1 and helpful below 1, and the unconstrained primal form can help with discrete actions.These are outcomes stated in the supplied figure caption.Source: Figure 4 · p. 10
- DICE methods perform stationary distribution estimation, and the paper develops a convex-duality framework that unifies many such algorithms.The passage also relates DICE dual methods to FQI-style primal estimators and identifies prior Lagrangian-type estimators.Source: §5 · p. 10
- Prior Lagrangian methods for linear programs that characterize value functions typically do not incorporate off-policy correction and assume on-policy samples.The cited work contrasts with this paper's off-policy setting.Source: §5 · p. 11
6 Conclusion
The paper presents off-policy evaluation through regularized Lagrangians of the d-LP and studies how estimator and optimization choices affect bias and performance. Its conclusion favors dual estimates for their flexibility and reports alternative estimators with improved performance.
6 Conclusion
- The paper proposes a unified view of off-policy evaluation through the regularized Lagrangian of the d-LP.Existing DICE algorithms are recovered through particular choices of regularizers, redundant constraints, and methods for converting optimized solutions to policy values.Source: §6 · p. 11
- Dual estimates offer greater flexibility than primal estimates for incorporating optimization stabilizers while preserving asymptotic unbiasedness.The conclusion identifies dual estimates with policy values in terms of the state-action distribution and primal estimates with estimated Q-values.Source: §6 · p. 11
- The study identifies alternative estimators not previously identified in the literature that exhibit improved performance.The authors describe these findings as suggesting new directions for offline OPE research.Source: §6 · p. 11
A Robustness Justification
The section interprets regularization as perturbations to the optimization conditions and distinguishes effects on the dual and primal solutions. In particular, relaxing the dual variable's constraint preserves the stationary state-action distribution solution, whereas relaxing the primal variable changes the optimal primal solution.
A Robustness Justification
- Dual regularization can be interpreted as robustness through perturbations to Bellman differences, while primal regularization introduces L2-ball perturbations to the stationary state-action distribution condition.With entropy regularization, the perturbation lies in the simplex.Source: A Robustness Justification · p. 14
- The displayed optimization is described as a Lagrangian, with the dual regularization term penalizing f2(ζ) and the objective including a reward-weighted dual variable.The supplied passage defines the relevant objective terms but does not state a further result for this expression.Source: A Robustness Justification · p. 14
- Relaxing dual ζ does not change the optimal solution, which remains the stationary state-action distribution; relaxing primal Q instead changes the optimal primal solution.The passage presents this contrast as one justification for advantages of dual OPE estimation.Source: A Robustness Justification · p. 14
B Proof for Theorem 2
The appendix characterizes estimator bias across regularization configurations, connects the framework to existing OPE estimators, and develops alternative forms and an undiscounted LP.
B Proof for Theorem 2
- The Lagrangian estimator is unbiased when either Q* = Qπ or ζ* = dπ/dD, while normalization can bias solutions that do not satisfy that constraint.The proof also identifies configurations that are always unbiased and configurations that are generally biased.Source: B Proof for Theorem 2 · pp. 14, 15, 17
C Recovering Existing OPE estimators
- The framework recovers LSTDQ as a special case under linear primal and dual parametrizations, and one listed configuration yields a similar result.The stated setup excludes positivity and normalization constraints and assumes a solution exists.Source: C Recovering Existing OPE estimators · pp. 18–19
D Alternative Biased Form
- The unconstrained primal form optimizes only over Q, but its practical approximation is generally biased because next-step samples are averaged inside a square.The form also faces an inaccessible transition operator; the bias may be an acceptable trade-off in simple, discrete environments.Source: D Alternative Biased Form · p. 19
E Undiscounted MDP
- For γ = 1, the d-LP represents policy value with a unique stationary distribution, while the primal LP's optimal Q is independent of Q up to a constant offset.The argument relies on adding the constraint that the distribution sums to 1 and on ergodicity of the policy-induced Markov chain.Source: E Undiscounted MDP · p. 20
F.1 OPE tasks
The experiments use Grid, Reacher, and Cartpole tasks, with specified target and behavior policies, trajectory collection, and function-approximation setups.
F.1 OPE tasks
- Experiments use γ = 0.99 and 400 trajectories per task, with trajectory lengths of 100 for Grid, 200 for Reacher, and 250 for Cartpole.For γ = 1, the trajectory length is 1000; the normalization ablation also evaluates γ = 0.995 and γ = 1.Source: §F.1 · p. 21
F.2 Linear Parametrization Details
- The linear-parametrization study uses one-hot state-action inputs for upper and lower bounds, then checks that estimates with both variables linear fall between them.Feed-forward networks have two fixed 64-neuron hidden layers without nonlinear activations; only the output layer is trained.Source: §F.2 · p. 21
F.3 Neural Network Details
- Neural-network experiments use two 64-neuron ReLU hidden layers and Adam, with task- and configuration-specific learning rates selected by hyperparameter search.Batch size is 2048; the selected rates vary across tasks and, for Cartpole, between primal and dual regularization.Source: §F.3 · p. 21
G Additional Results
Additional experiments compare the best DICE estimator with unregularized alternatives, examine target networks, and test regularization under a third behavior policy.
G.1 Comparison to unregularized Lagrangian
- The best DICE estimator outperforms the unregularized primal, dual, and Lagrangian estimates in training stability and final estimation.The comparison is against the original Lagrangian without regularization or redundant constraints.Source: §G.1 · pp. 21–22, Figure 5 · p. 22
G.2 Primal Estimates with Target Networks
- Target networks with double Q-learning improve primal-estimate performance on Reacher, but estimates remain sensitive to reward scaling and shifting.Figure 6 shows primal and Lagrangian estimates after transformed rewards are mapped back to the original scale.Source: §G.2 · p. 22, Figure 6 · p. 22
G.3 Additional Regularization Comparison
- With data from a third behavior policy, regularizing the dual variable is generally better than regularizing the primal variable, while primal regularization with reward produces biased estimates.The figure reports dual estimates with αR = 0 and αR = 1.Source: §G.3 · p. 22, Figure 7 · p. 23
G.4 Additional Ablation Study
The ablation compares a positivity-constrained primal form with an unconstrained primal form.
G.4 Additional Ablation Study
- The positivity constraint improves training stability, while the unconstrained primal problem is more stable but produces biased estimates.The comparison uses data collected from a third behavior policy.Source: Figure 8 · p. 23