PaperlayerView exact revision on arXiv

Source-linked AI summary

GenDICE: Generalized Offline Estimation of Stationary Values

Ruiyi Zhang, Bo Dai, Lihong Li, Dale Schuurmans

arXiv:2002.09072v1stat.MLcs.LG

TL;DR

The paper studies stationary-value estimation when only fixed offline transition data are available and no transition operator or environment interaction can be accessed. GenDICE estimates a stationary-to-empirical correction ratio through divergence-minimization constraints, proves consistency under general conditions, and performs strongly on offline PageRank and off-policy evaluation benchmarks.

  • Problem

    Estimating stationary-distribution quantities is difficult with fixed offline data, especially in behavior-agnostic OPE where unknown behavior distributions make standard importance sampling unsuitable.

  • Method

    GenDICE estimates a stationary-distribution correction ratio using a dual embedding formulation for divergence minimization and constraints that eliminate degenerate solutions.

  • Results

    GenDICE is theoretically consistent and achieves significant improvements on behavior-agnostic off-policy evaluation benchmarks and offline PageRank.

  • Takeaways & Limitations

    The method provides a general stationary-distribution correction estimator for discounted and average settings using multiple behavior-agnostic samples.

  • Takeaways & Limitations

    Behavior-agnostic OPE involves unknown behavior distributions, while alternative divergences may require additional constraints on dual functions.

Abstract

from arXiv · show

An important problem that arises in reinforcement learning and Monte Carlo methods is estimating quantities defined by the stationary distribution of a Markov chain. In many real-world applications, access to the underlying transition operator is limited to a fixed set of data that has already been collected, without additional interaction with the environment being available. We show that consistent estimation remains possible in this challenging scenario, and that effective estimation can still be achieved in important applications. Our approach is based on estimating a ratio that corrects for the discrepancy between the stationary and empirical distributions, derived from fundamental properties of the stationary distribution, and exploiting constraint reformulations based on variational divergence minimization. The resulting algorithm, GenDICE, is straightforward and effective. We prove its consistency under general conditions, provide an error analysis, and demonstrate strong empirical performance on benchmark problems, including off-line PageRank and off-policy policy evaluation.

1 INTRODUCTION

Stationary-distribution quantities matter across applications, but classical estimators require environment interaction or an explicit transition model. GenDICE addresses offline estimation from fixed transition data with a stationary-distribution corrector and establishes consistency alongside empirical gains.

  • Stationary-distribution quantities underpin PageRank, MCMC-based Bayesian inference, queueing analysis, and reinforcement learning.
  • Classical estimators require next-state sampling through environment interaction or an explicitly known transition distribution, excluding fixed offline datasets.
  • GenDICE estimates stationary quantities from fixed state-transition samples by correcting the discrepancy between sampled and stationary distributions.
  • The offline setting requires inferring an asymptotic quantity from finite data, yet the proposed techniques support consistent estimation under general conditions.
  • GenDICE combines a dual embedding formulation for divergence minimization with a mechanism that explicitly eliminates degenerate solutions.
  • Consistency and statistical properties are established theoretically, while experiments report significant improvements on behavior-agnostic OPE benchmarks and offline PageRank.

2 BACKGROUND

Offline PageRank and policy evaluation estimate stationary values from sampled transitions rather than direct model access. In behavior-agnostic OPE, unknown behavior distributions make standard importance sampling unsuitable, motivating stationary correction ratios.

  • Off-line PageRank: Offline PageRank estimates a web page’s asymptotic visitation probability from sampled graph transitions without an explicitly given transition model.
  • Off-line PageRank: The offline PageRank estimate can be recovered from the empirical page probability and a stationary-to-data correction ratio.
  • Policy Evaluation: Policy evaluation estimates discounted or average reward for a target policy from trajectories generated by a Markov decision process.
  • Behavior-agnostic OPE: Behavior-agnostic OPE uses fixed transitions from multiple unknown behavior policies, unlike classical OPE with a known behavior policy.
  • Behavior-agnostic OPE: Typical importance-sampling estimators do not apply when the behavior distribution is unknown, and trajectory-based estimators can suffer variance exponential in horizon length.
  • Behavior-agnostic OPE: Stationary correction reduces behavior-agnostic OPE to estimating a correction ratio function, which can then reweight empirical rewards.

3 GENDICE

GenDICE estimates stationary-distribution correction ratios from fixed transition samples, without direct access to transition probabilities or a next-state sampler. It reformulates the problem as a constrained variational divergence optimization that is practical to solve.

  • 3.1 ESTIMATING STATIONARY DISTRIBUTION CORRECTION: GenDICE estimates a stationary correction ratio from fixed samples of transitions under an unknown sampling distribution.The method targets the ratio between the stationary distribution and the empirical distribution, using only offline data.
  • 3.1 ESTIMATING STATIONARY DISTRIBUTION CORRECTION: The stationary condition is expressed through a distribution operator that can be sampled by mixing initial-state-policy samples with observed transitions.This avoids requiring element-wise access to the transition operator or arbitrary evaluation of its induced integral.
  • 3.2 ELIMINATING DEGENERATE SOLUTIONS: When γ = 1, imposing τ ≥ 0 and E_p[τ] = 1 removes the zero solution and rescaled correction ratios from the optimization.The normalization constraint makes the correction ratio a proper density ratio.
  • 3.2 ELIMINATING DEGENERATE SOLUTIONS: For any γ ∈ (0, 1] and λ > 0, the penalized optimization has the desired correction-ratio solution, so λ need not increase toward infinity.Theorem 1 permits estimation by solving a single optimization with an arbitrary positive penalty weight.
  • 3.3 EXPLOITING DUAL EMBEDDING: Dual embedding converts the divergence objective into a min-max formulation that avoids intractable integrals and the need for double sampling.For f-divergences, Fenchel duality and function-valued dual variables yield an optimization suitable for practical estimation.
  • 3.3 EXPLOITING DUAL EMBEDDING: The estimator is compatible with integral probability metrics while retaining consistency, although some alternatives impose additional dual-function constraints or computation.Wasserstein and Dudley variants may require extra gradient penalties, while MMD admits a closed-form dual solution.

4 THEORETICAL ANALYSIS

The theoretical analysis bounds GenDICE’s objective suboptimality under mild conditions by approximation, sample-estimation, and optimization errors. The analysis also identifies a trade-off between function-class flexibility and the latter two errors.

  • 4 THEORETICAL ANALYSIS: Under mild conditions, the expected objective error between GenDICE’s estimate and the target correction ratio is bounded by approximation, sampling, and optimization terms.The result applies when the function classes F and H are learnable.
  • 4 THEORETICAL ANALYSIS: The sample-estimation contribution decreases at order 1/√N, while approximation error depends on the representation flexibility of F and H.Optimization error reflects the suboptimality of the solution returned by the optimization algorithm.
  • 4 THEORETICAL ANALYSIS: In special cases, objective suboptimality can be lower-bounded by a divergence between the estimated and target ratios, directly bounding error in the estimated policy value.This connects the theoretical objective guarantee to policy-evaluation accuracy.
  • 4 THEORETICAL ANALYSIS: More flexible function classes can reduce approximation error but increase estimation and optimization errors, whereas linear parameterizations tend to have the opposite trade-off.For linear parameterizations, estimation and optimization errors can often be upper-bounded explicitly, but approximation error is larger.

5 RELATED WORK

GenDICE addresses offline stationary-value estimation without transition-operator access, extending stationary-distribution correction to behavior-agnostic settings and offline PageRank.

  • Off-policy Policy Evaluation: Importance-sampling OPE methods can suffer exponential variance in long-horizon problems, while prior stationary-correction methods require a single known behavior policy.These restrictions limit applicability to behavior-agnostic offline data.
  • Off-policy Policy Evaluation: Standard model-based methods apply to behavior-agnostic data but depend heavily on reward and transition-modeling assumptions that may make evaluation unreliable.
  • Markov Chain Monte Carlo: GenDICE differs from classical MCMC by using only an off-policy dataset rather than repeatedly interacting with the transition operator.It estimates stationary quantities through stationary density-ratio estimation.
  • Density Ratio Estimation: Unlike standard density-ratio methods using samples from both distributions, GenDICE estimates a stationary density ratio from its offline setting.
  • PageRank: Prior PageRank work uses an online reverse-time RL framework, whereas GenDICE studies an offline PageRank setting.

6 EXPERIMENTS

Experiments evaluate GenDICE on offline PageRank and off-policy policy evaluation across tabular and continuous-control settings. GenDICE generally outperforms model-based and importance-sampling baselines, including DualDICE in continuous control, while ablations examine optimization choices and constraints.

  • Experimental Setup: GenDICE is evaluated on OPE and OPR using fixed offline trajectories, with comparisons against model-based methods, weighted IS, IPS, and DualDICE.Results use 20 random seeds and report means and standard deviations.
  • Tabular Case: GenDICE outperforms model-based methods on offline PageRank because it directly estimates the stationary distribution vector or ratio instead of an entire transition matrix.
  • Continuous Case: In Reacher, GenDICE maintains good performance with continuous actions, function approximation, and stochastic optimization, where IS and model-based performance deteriorates.
  • Reacher: Longer trajectories or more trajectories improve all methods, and behavior policies closer to the target policy improve performance across Reacher settings.GenDICE performs well for both average and discounted reward; its optimization curves achieve the smallest loss and outperform DualDICE in discounted reward.
  • HalfCheetah: GenDICE performs better than all baselines in the more challenging HalfCheetah domain for discounted and average-reward cases.
  • Ablation Study: Ablations vary learning rates, activation functions, constraint penalties, discount factors, divergences, and penalty weights to assess robustness and implementation sensitivity.The constraint penalty is necessary to avoid a trivial solution, while χ2-divergence remains consistent across a large penalty-weight range; λ = 1 is suggested in practice.

7 CONCLUSION

GenDICE estimates stationary distribution correction ratios from multiple behavior-agnostic samples and supports both discounted and average stationary distributions. Experiments on off-policy evaluation and offline PageRank report superiority over existing state-of-the-art methods.

  • The method is evaluated on off-policy evaluation and offline PageRank.
  • The paper reports GenDICE’s superiority over existing state-of-the-art methods on these empirical tasks.
  • Assumptions: The analysis assumes the target-policy transition operator has a unique stationary distribution in the selected divergence.
  • Assumptions: With total variation divergence, the assumption requires the transition operator to be ergodic.

A.1 CONSISTENCY OF THE ESTIMATOR

The estimator’s optimization solution is the stationary density ratio, and GenDICE implements the resulting objective with function approximators and stochastic gradient updates.

  • The optimal nonnegative function τ is the stationary density ratio µ(x)/p(x).
  • The derivation uses Fenchel duality for an f-divergence and adds a convex normalization penalty.
  • Algorithm: GenDICE uses approximators for the correction ratio and dual function, a constraint scalar, learning rates, iterations, and minibatches.
  • Algorithm: Each iteration samples transition minibatches, samples target-policy actions, computes an empirical loss, and updates the parameters by stochastic gradients.
  • Algorithm: The procedure returns the learned correction-ratio approximator after the prescribed optimization iterations.

C PROOF OF THEOREM 3

The proof connects the optimization objective to stationary-distribution correction and decomposes estimation error into statistical, optimization, and approximation components.

  • The bounded divergence remains valid, so its optimal solution is still the stationary density ratio µ(x)/p(x).
  • Error decomposition: The proof separates estimation, optimization, and function-class approximation effects through an empirical surrogate objective.
  • The discrepancy d(τ,τ*) is zero exactly when p·τ is a stationary distribution in the weak divergence sense.
  • Under a spectral representation and identity divergence, suboptimality lower-bounds a metric measuring deviation between τ and τ*.

C.2 STATISTICAL ERROR

The statistical analysis bounds GenDICE’s estimation error using concentration and covering-number arguments, while the main theorem combines statistical, optimization, and approximation errors.

  • The analysis focuses primarily on batch reinforcement learning with i.i.d. transition samples.
  • Statistical error: Pollard’s tail inequality bounds maximum deviations using a function class’s covering number.
  • Statistical error: The covering number is bounded using the pseudo-dimension of the function class.
  • Statistical error: With probability at least 1−δ, finite pseudo-dimensions and a Lipschitz conjugate yield a stochastic-error bound.
  • Limitations: For neural-network parameterizations, quantifying optimization error remains outside the paper’s scope.
  • Main theorem: The total expected error is bounded by 4E[ϵ_est] + E[ϵ_opt] + ϵ_approx(F,H).

D EXPERIMENTAL SETTINGS

Experiments evaluate GenDICE on tabular and control settings using offline data, varying graph structure, behavior-policy proximity, and task type. The control experiments compare stationary-distribution correction methods on discrete and continuous tasks.

  • Tabular case: The Taxi domain uses a 5×5 grid with 2000 states and policies constructed from Q-learning checkpoints.The target policy is obtained after 1000 Q-learning iterations, while a 950-iteration policy serves as the base policy.
  • Tabular case: Offline PageRank experiments use graph datasets whose degree statistics and visualizations are reported for different graph types.The Barabasi-Albert graph construction favors attaching new nodes to heavily linked existing nodes.
  • Control tasks: The control benchmarks include Cartpole, Reacher, and HalfCheetah, with feed-forward neural networks using two hidden layers of dimension 64 and tanh activations.Importance sampling uses behavior-cloned policy probabilities to compute π*(a|s)/π(a|s).
  • Control tasks: Cartpole is modified to an infinite-horizon task with reward −1 upon termination and 1 otherwise, and its target and behavior policies vary with α.The target combines a pretrained policy and a uniformly random policy, while the behavior mixture changes as α varies.
  • Control tasks: Reacher and HalfCheetah use Gaussian target and behavior policies whose standard deviations vary with α, with Adam training and batch size 2048.For Reacher, the learning-rate search selected 0.003.
  • Evaluation protocol: On Cartpole, GenDICE is competitive with importance sampling and model-based methods in average reward and outperforms them in log MSE loss.The passage attributes importance sampling’s poor performance to difficulty fitting a policy from data collected by multiple policies.

E.2 ADDITIONAL RESULTS ON CONTINUOUS CONTROL

Additional continuous-control experiments compare GenDICE with baselines across Reacher and HalfCheetah, including datasets collected from single or multiple behavior policies. Ablations examine learning rates, activation functions, and normalization alternatives.

  • Continuous-control results: GenDICE outperforms other baselines in log MSE across Reacher and HalfCheetah under different behavior policies.The experiments include single-policy datasets ranging from more difficult to easier settings and datasets collected by multiple behavior policies.
  • Continuous-control results: GenDICE more accurately estimates the target-policy reward than the baselines in the reported continuous-control figures.The cited results cover both Reacher and HalfCheetah.
  • Ablation study: When α = 0.0, only GenDICE with a larger learning rate obtains reasonable estimation in the more difficult OPE setting.At α = 0.33, GenDICE performs relatively well across all tested learning rates.
  • Ablation study: Square and softplus activations work well, whereas the exponential activation performs poorly under some settings.The authors use the square function in practice because of its low variance and better performance in most cases.
  • Normalization comparison: Self-normalization can be computationally prohibitive because estimating one stochastic gradient requires scanning all samples in the training set.The passage also states that self-normalization generally does not produce an unbiased solution.
  • Normalization comparison: Under a matched running-time budget on a BA graph, regularization performs better than self-normalization in the reported OPR comparison.The comparison uses 100 nodes, 10,000 offline samples, 20 trials, and χ2-divergence.
Loading 2002.09072v1…