PaperlayerView exact revision on arXiv

Source-linked AI summary

DualDICE: Behavior-Agnostic Estimation of Discounted Stationary Distribution Corrections

Ofir Nachum, Yinlam Chow, Bo Dai, Lihong Li

arXiv:1906.04733v2cs.LGcs.AIstat.ML

TL;DR

DualDICE addresses discounted stationary distribution estimation from fixed off-policy data, where existing methods require behavior-policy knowledge and per-step importance ratios. It estimates the corrections without those requirements, provides convergence guarantees, and consistently—and often significantly—improves performance over previous algorithms.

  • Problem

    Fixed off-policy datasets require accurate discounted stationary distribution corrections, but prior estimators assume known behavior policies and use per-step importance ratios.

  • Method

    DualDICE estimates discounted stationary distribution ratios agnostically to the number or type of behavior policies and without per-step importance ratios.

  • Results

    DualDICE consistently, and often significantly, improves performance compared to previous algorithms for estimating stationary distribution ratios.

  • Takeaways & Limitations

    DualDICE provides a way to estimate off-policy stationary distribution corrections when the behavior policy is unknown or multiple behavior policies generated the data.

  • Takeaways & Limitations

    The method assumes support coverage: whenever dπ(s, a) > 0, the dataset distribution dD(s, a) must also be positive, and correction terms must be bounded.

Abstract

from arXiv · show

In many real-world reinforcement learning applications, access to the environment is limited to a fixed dataset, instead of direct (online) interaction with the environment. When using this data for either evaluation or training of a new policy, accurate estimates of discounted stationary distribution ratios -- correction terms which quantify the likelihood that the new policy will experience a certain state-action pair normalized by the probability with which the state-action pair appears in the dataset -- can improve accuracy and performance. In this work, we propose an algorithm, DualDICE, for estimating these quantities. In contrast to previous approaches, our algorithm is agnostic to knowledge of the behavior policy (or policies) used to generate the dataset. Furthermore, it eschews any direct use of importance weights, thus avoiding potential optimization instabilities endemic of previous methods. In addition to providing theoretical guarantees, we present an empirical study of our algorithm applied to off-policy policy evaluation and find that our algorithm significantly improves accuracy compared to existing techniques.

1 Introduction

Fixed datasets are important for reinforcement learning when environment interaction is unavailable or costly, motivating stationary-distribution corrections for accurate evaluation and learning. DualDICE estimates these corrections without knowing the behavior policies and avoids direct per-step importance ratios.

  • Motivation: Real-world applications such as medicine, recommendation, and education may make deploying a new policy expensive or risky.These settings limit direct environment access for evaluation or training.
  • Motivation: Discounted stationary distribution ratios measure target-policy state-action likelihood normalized by its probability in off-policy data.Accurate ratios can improve policy-evaluation accuracy and policy-learning stability.
  • Prior limitations: Existing ratio estimators require behavior-policy probabilities and use per-step importance ratios that can have high variance when behavior and target policies differ.These requirements are especially problematic for multiple, non-Markovian behavior policies.
  • Contribution: DualDICE estimates discounted stationary distribution ratios while remaining agnostic to the number or type of behavior policies used to collect data.The method also provides theoretical convergence guarantees and is evaluated on off-policy policy-evaluation benchmarks.
  • Contribution: DualDICE consistently, and often significantly, improves performance over previous stationary-distribution-ratio estimators.The reported empirical study applies the method to off-policy policy evaluation.

2 Background

Off-policy evaluation estimates a target policy’s value from fixed transition data, often through discounted occupancy corrections. The background highlights trajectory-importance-sampling variance and the assumptions and importance ratios required by prior correction methods.

  • Off-Policy Policy Evaluation: Off-policy policy evaluation estimates a target policy’s value using a fixed dataset of transitions sampled in some manner.The dataset may come from one behavior policy, multiple behavior policies, or an oracle sampler.
  • Off-Policy Policy Evaluation: Trajectory-wide importance weighting can suffer from exponentially high variance as trajectory length increases.This problem is known as the curse of horizon.
  • Off-Policy Policy Evaluation: Weighting states by their long-term occupancy measure avoids exponential dependence on trajectory length.The policy value can be re-expressed using discounted state-action occupancy probabilities.
  • Stationary Distribution Corrections: The correction term wπ/µ(s,a) is the target policy’s discounted stationary state-action distribution divided by the behavior distribution, and it must be estimated from behavior-distributed data.The correction connects target-policy value estimation to occupancy estimation.
  • Prior Methods and Limitations: Prior correction methods use stationary-flow identities and temporal-difference objectives, but require a known single Markovian behavior policy and per-step importance ratios.The ratios can have high variance and harm stochastic-optimization convergence.
  • Multiple Unknown Behavior Policies: DualDICE instead handles transitions sampled in an unknown fashion, requiring only support coverage and bounded correction terms.Its correction is defined as wπ/D(s,a) := dπ(s,a) / dD(s,a), with dπ(s,a)>0 implying dD(s,a)>0 and a finite bound C.

3 DualDICE

DualDICE estimates discounted stationary distribution corrections from fixed-data samples without requiring the behavior distribution. Its Bellman-residual and Fenchel-dual formulations support practical optimization, direct correction recovery, and theoretical error guarantees.

  • 3.1 The Key Idea: DualDICE estimates wπ/D(s, a) using only off-policy transition samples, initial-state samples, and target-policy actions, without explicit knowledge of dD.The method begins with wπ/D(s, a) = dπ(s,a) / dD(s,a) and assumes access to samples rather than the dataset distribution itself.
  • 3.1 The Key Idea: The original objective combines squared zero-reward Bellman error under dD with an initial-state-policy term that prevents the trivial ν∗≡0 solution.Together, the terms produce a non-zero Bellman residual at state-action pairs sampled from dD.
  • 3.1 The Key Idea: The optimal Bellman residual satisfies (ν∗−Bπν∗)(s, a) = wπ/D(s, a), making the residual the desired correction.This identity is the foundation for obtaining corrections from an optimized value function.
  • 3.2 Exploiting Fenchel Duality: Fenchel duality converts the objective into a saddle-point problem whose unbiased stochastic gradients are linear in ν and concave in ζ.The optimizer ζ∗ directly equals the distribution correction, eliminating additional computation after optimization.
  • 3.3 Extension to General Convex Functions: A general convex penalty preserves the method’s computational benefits, including unbiased estimates, well-behaved optimization, and direct recovery through ζ∗(s, a).The quadratic penalty is a special case of this broader convex-penalty formulation.
  • 3.4 Theoretical Guarantees: Theorem 2 decomposes OPE error into statistical, optimization, and approximation terms, while linear parameterizations can achieve O(exp(−T)) optimization rates with SVRG.The statistical term decreases as N increases, whereas more flexible function spaces reduce approximation error but complicate optimization.

4 Related Work

The related work covers direct density-ratio estimators and off-policy policy-evaluation methods, highlighting DualDICE’s applicability when stationary-distribution samples and behavior-policy densities are unavailable.

  • Density Ratio Estimation: Density-ratio estimation methods include moment matching, probabilistic classification, and ratio matching alongside naive separate density estimation.Direct estimators avoid potentially magnifying error by estimating numerator and denominator densities separately.
  • Density Ratio Estimation: Existing direct ratio estimators require samples from both the dataset and target stationary distributions, which is impractical for off-policy learning.DualDICE is presented as applicable without samples from the target stationary distribution.
  • Off-policy Policy Evaluation: Off-policy evaluation methods trade off model bias, importance-sampling variance, and behavior-policy knowledge requirements.Direct Method has low variance but model-class-dependent bias; importance sampling can have unbounded, horizon-dependent variance; Doubly Robust combines both approaches.
  • Off-policy Policy Evaluation: Unlike methods other than Direct Method, DualDICE avoids requiring knowledge of the behavior policy’s density ratio.This distinguishes it from the listed importance-weight-based evaluation approaches.

5 Experiments

Experiments evaluate DualDICE for off-policy policy evaluation from controlled tabular settings through difficult control tasks and convex-function choices. DualDICE is competitive with TD when optimization is solved exactly and remains accurate and stable where TD degrades, with f(x) = 2|x|^3/2 performing best empirically.

  • Experimental Setup: The experiments estimate stationary-distribution corrections from behavior-policy trajectories and use them to estimate target-policy average step reward.Comparisons include a TD-based approach and weighted step-wise importance sampling.
  • Choice of Convex Function f: f(x) = 2|x|^3/2 is empirically the best-performing convex penalty choice, despite f(x) = 1/2x^2 being the most natural choice.This form is used in the Figure 2 experiments.
  • Taxi: In Taxi, exact matrix-operation optimization shows DualDICE and TD methods are competitive.The controlled setting removes optimization difficulties from the comparison.
  • Control Tasks: On control tasks, DualDICE approximates desired values more accurately as α increases, whereas TD performs poorly, particularly with unknown behavior policies.On Cartpole TD can approach the desired value at large α; on Reacher its learning is too unstable to learn effectively.
  • Control Tasks: In Cartpole and Reacher, DualDICE provides good, stable performance while TD suffers high variance, worsened when the behavior policy is estimated.Reacher’s continuous actions make the instability especially severe for TD.

6 Conclusions

DualDICE avoids behavior-policy knowledge and importance weights, yielding better estimates than TD methods, especially with function approximation and stochastic optimization. The section also identifies open directions for extending and understanding the method.

  • DualDICE is agnostic to the behavior policy and avoids importance weights in its losses.
  • DualDICE provides significantly better estimates than TD methods in settings requiring function approximation and stochastic optimization.
  • Future work includes applying DualDICE to off-policy training, studying how f affects distribution-correction approximation error, and evaluating real-world OPE tasks.
  • The optimization procedure takes a convex function f, off-policy transition data, a target policy, two networks, learning rates, iterations, and batch size as inputs.

B Additional Results

Additional control-task experiments compare DualDICE with doubly robust, direct-model, and Qπ baselines, showing continued performance across discrete and continuous settings. Baseline performance is described as more robust on Acrobot than on Pendulum.

  • Figure 4 compares DualDICE with doubly robust, direct method, and Qπ baselines on control-task OPE across training steps.DR reduces importance-sampling variance with a learned value function; DM uses a learned dynamics-and-reward model for Monte Carlo rollouts; Qπ learns values by Bellman-error minimization.
  • DualDICE continues to perform well against previous OPE methods on Acrobot and Pendulum.
  • Baselines perform reasonably well on discrete Acrobot, whereas their performance degrades in continuous Pendulum.

C Experimental Details

The Taxi experiment uses a tabular exact-solve protocol aligned with prior work, including a fixed discount and specified behavior and target policies. The corresponding comparison solves DualDICE over state variables.

  • The Taxi experiment follows the protocol of prior work in a tabular, exact-solve setting.The TD methods are equivalent to their kernel-based TD method in this setting.
  • The experiment fixes γ to 0.995 and uses the behavior and target policies from prior work.
  • DualDICE is solved exactly with matrix operations over |S| variables ν(s) for comparison with prior exact solves over state variables.
  • The alternative objective based on w^π/μ requires knowledge of the importance weights π(a|s)/μ(a|s).

C.2 Control Tasks

The control-task experiments use Cartpole and Reacher with neural-network baselines and behavior-policy estimation, alongside modified task-specific target and behavior policies. The appendix also states the proof-error decomposition and a quadratic special case for f.

  • Control Tasks: Cartpole and Reacher use COP-TD as the TD baseline and feed-forward networks with two 64-unit tanh hidden layers.When μ is unknown, a behavior-cloned neural policy supplies probabilities for importance-weight calculations.
  • Control Tasks: Cartpole is modified to an infinite-horizon task with rewards of −1 at termination and 1 otherwise; its target policy mixes a trained policy with 0.3 uniform exploration.
  • Control Tasks: For Reacher, the target is a Gaussian around a trained deterministic policy with standard deviation 0.1, while the behavior standard deviation is 0.4 − 0.3α.The experiment uses γ = 0.99 and reports average step rewards of approximately −0.12 for π and −0.50 for μ at α = 0.
  • Theory: The proof decomposes total error into statistical and optimization components after first decomposing the estimator error.
  • Theory: The theoretical analysis specializes the general convex-function estimator to f(x) = 1/2x^2 under boundedness and reward-regularity assumptions.The analysis uses strong convexity, Lipschitz properties, bounded rewards, and bounded ν and w domains.
  • Theory: The appendix repeats the DualDICE objective and defines empirical, primal, and dual objectives used with an optimization algorithm.

D.1 Error Decomposition

The section decomposes DualDICE’s estimation and policy-value errors into optimization, approximation, statistical, reward, and estimator-related components. It also reconciles the theoretical density-ratio analysis with the implemented estimator ζ̂(s, a).

  • DualDICE initially analyzes ν̂ − B̂_πν̂ as an estimate of the discounted stationary distribution ratio w^π/D, then relates this analysis to the implemented ζ̂ estimator.
  • Reward randomness contributes a separate error term, while the estimator-based policy-value analysis decomposes the mean squared error for off-policy policy evaluation.
  • The policy-value error is decomposed by comparing J(ν̂*) with the objective and optimum, enabling term-by-term bounds.
  • The resulting error includes optimization error, approximation error from parametrizing ν and ζ, and statistical error from finite samples.
  • When the estimator residual vanishes for every state-action pair in the dataset, the additional term disappears and the error matches equation 19.

D.2 Statistical Error

The section bounds statistical errors arising from finite samples, reward observations, and function-class estimation under mixing and boundedness assumptions. The analysis uses concentration and covering-number arguments, with pseudo-dimension controlling complexity.

  • Statistical-error bounds are first developed for i.i.d. batch data and can be generalized to a single exponentially β-mixing sample path using a blocking technique.
  • Pollard’s tail inequality and pseudo-dimension-based covering-number bounds control maximum deviations over the relevant function classes.
  • The estimation-error bound assumes f* is L-Lipschitz continuous and holds with probability at least 1 − δ.
  • The statistical analysis bounds the function class through bounded ν and ζ, Lipschitz properties of f*, and pseudo-dimensions D_ν and D_ζ.
  • The finite-sample statistical error is obtained by combining the covering-number result with the preceding concentration analysis.
  • The theorem states that DualDICE’s mean squared error is bounded while accounting for sampling and algorithmic randomness and separately defined error terms.

D.4 Optimization Error

The section characterizes optimization error for the convex-concave DualDICE objective under different parametrizations and optimization algorithms. It gives convergence results for tabular, linear, and kernel settings while leaving neural-network analysis open.

  • For neural-network parametrizations, quantitatively analyzing optimization error remains an open problem outside the paper’s scope.
  • The optimization objective is generally convex-concave, and vanilla stochastic gradient descent has a convergence rate expressed in terms of the primal-dual gap.
  • The linear-model analysis assumes full-rank A, strictly positive-definite C, and uniformly bounded feature vectors.
  • The section studies optimization error for two algorithms applied to the objective: SVRG and stochastic gradient descent.
  • After T iterations with linear parametrization, SVRG achieves optimization error O(exp(−T)), while the stated SGD rate is also characterized in the corollary.
Loading 1906.04733v2…