PaperlayerView exact revision on arXiv

Source-linked AI summary

Towards Optimal Off-Policy Evaluation for Reinforcement Learning with Marginalized Importance Sampling

Tengyang Xie, Yifei Ma, Yu-Xiang Wang

arXiv:1906.03393v4cs.LGcs.AIstat.ML

TL;DR

The paper addresses off-policy evaluation when long horizons and large action spaces make standard importance sampling highly variable. It proposes recursively estimating target-policy marginal state distributions, obtaining polynomial horizon dependence and strong empirical performance across varied environments. The paper also identifies an unresolved factor-of-H gap relative to a Cramer-Rao lower bound in the relevant setting.

  • Problem

    Off-policy evaluation must estimate a target policy’s performance from behavior-policy data, while standard importance sampling can have variance that depends exponentially on horizon H.

  • Method

    The paper proposes marginalized importance sampling, which estimates the target policy’s marginal state distribution recursively at every step instead of using cumulative trajectory weights.

  • Results

    MIS achieves substantially better performance than existing approaches across a number of benchmarks and has a finite-sample error bound with polynomial dependence on H.

  • Takeaways & Limitations

    MIS provides a practical and theoretically analyzed alternative to trajectory-wide importance sampling for finite-state episodic settings with potentially infinite action spaces.

  • Takeaways & Limitations

    The paper conjectures that the additional factor of H relative to the Cramer-Rao lower bound is required in infinite-action settings, while recursive error propagation can otherwise cause exponential blow-up.

Abstract

from arXiv · show

Motivated by the many real-world applications of reinforcement learning (RL) that require safe-policy iterations, we consider the problem of off-policy evaluation (OPE) -- the problem of evaluating a new policy using the historical data obtained by different behavior policies -- under the model of nonstationary episodic Markov Decision Processes (MDP) with a long horizon and a large action space. Existing importance sampling (IS) methods often suffer from large variance that depends exponentially on the RL horizon $H$. To solve this problem, we consider a marginalized importance sampling (MIS) estimator that recursively estimates the state marginal distribution for the target policy at every step. MIS achieves a mean-squared error of $$ \frac{1}{n} \sum\nolimits_{t=1}^H\mathbb{E}_μ\left[\frac{d_t^π(s_t)^2}{d_t^μ(s_t)^2} \mathrm{Var}_μ\left[\frac{π_t(a_t|s_t)}{μ_t(a_t|s_t)}\big( V_{t+1}^π(s_{t+1}) + r_t\big) \middle| s_t\right]\right] + \tilde{O}(n^{-1.5}) $$ where $μ$ and $π$ are the logging and target policies, $d_t^μ(s_t)$ and $d_t^π(s_t)$ are the marginal distribution of the state at $t$th step, $H$ is the horizon, $n$ is the sample size and $V_{t+1}^π$ is the value function of the MDP under $π$. The result matches the Cramer-Rao lower bound in \citet{jiang2016doubly} up to a multiplicative factor of $H$. To the best of our knowledge, this is the first OPE estimation error bound with a polynomial dependence on $H$. Besides theory, we show empirical superiority of our method in time-varying, partially observable, and long-horizon RL environments.

1 Introduction

The paper studies off-policy evaluation for safer reinforcement-learning policy use, focusing on high variance from trajectory-wide importance weights. It proposes marginalized importance sampling and analyzes its theory and empirical performance across varied environments.

  • Motivation: Off-policy evaluation estimates a target policy’s performance using data collected by a different behavior policy.It matters in applications where online evaluation is expensive, risky, or potentially unethical.
  • Motivation: Importance sampling corrects behavior-target policy mismatch but can have variance that grows exponentially with the horizon.This creates severe sample-complexity problems for long-horizon episodic MDPs.
  • Approach: Marginalized importance sampling estimates state-distribution shifts at each step instead of reweighting entire trajectories.The approach aggregates trajectories sharing state-transition patterns under Markov independence assumptions.
  • Theory: The paper provides a finite-sample MSE bound for MIS in episodic tabular MDPs, including settings with potentially continuous action spaces.The bound is compared with a Cramer-Rao lower bound and is larger by at most a factor of H.
  • Experiments: Experiments compare MIS with strong prior baselines across time-invariant, time-varying, fully observable, partially observable, and long-horizon environments.The approach can also be incorporated into several importance-sampling-based estimators under Markov assumptions.

2 Problem formulation

The paper formulates OPE in finite-horizon, nonstationary episodic MDPs, where state information is available but transition dynamics may be difficult to estimate in large action spaces. The estimator uses behavior-policy trajectories and known action probabilities to minimize target-policy value MSE.

  • MDP setting: The environment is a finite-horizon, nonstationary episodic MDP with states, actions, transitions, rewards, and horizon H.The transition function gives next-state probabilities, while the reward function gives expected immediate rewards.
  • Policies and data: The behavior policy μ collects n trajectories, while the target policy π is the policy whose value is evaluated.Historical data contains state, action, and reward triplets for every time step and episode.
  • OPE objective: The OPE objective is to construct an estimator of v^π that minimizes MSE using observed data and known action probabilities.The target-policy state distributions after policy change are not directly observed.
  • Large-action-space regime: The setting assumes relatively small state spaces but action-state transition models too large to estimate reliably from available data.States remain observable, enabling direct estimation of state distributions after changing policies.
  • Assumptions: The formulation includes technical reward, overlap, and moment assumptions needed for consistent off-policy evaluation.The provided passages explain that bounded reward variance is required even for on-policy evaluation and that overlap conditions support importance-weight moments.

3 Marginalized Importance Sampling Estimators for OPE

The MIS estimator replaces trajectory-wide importance weighting with recursively estimated marginal state distributions, targeting lower horizon dependence without explicitly modeling state-action dynamics. Its advantage is reduced potential horizon dependence, though it does not dominate naive importance sampling in every setting.

  • Estimator design: Model-based estimators can be inaccurate in large action spaces because rarely visited actions make transition and reward estimates unreliable.Function approximation may add bias under covariate shifts caused by changing policies.
  • Estimator design: Standard importance sampling avoids estimating transition dynamics by directly approximating expected rewards, but its importance-weight variance can grow exponentially in H.This can make its sample complexity worse than applicable model-based approaches.
  • MIS construction: MIS estimates importance weights through marginal state distributions at each time step rather than cumulative trajectory products.The estimator recursively estimates the target-policy state distribution and combines it with reward estimates.
  • MIS construction: MIS uses empirical state visitation frequencies and standard bandit-style importance sampling for its reward estimator.The bandit estimator is described as optimal up to a universal constant when the action space is large.
  • Scope and trade-offs: MIS avoids a variance dependence that need not be exponential in H, but it does not dominate the naive IS estimator in general settings.The paper notes that history-based state representations can impose broader limits on achievable performance.

4 Theoretical Analysis of the MIS Estimator

The MIS estimator achieves polynomial horizon dependence and approaches information-theoretic optimality, while its analysis addresses bias, dependence, and recursive error propagation.

  • Theoretical guarantees: O(H^3) sample complexity is obtained for MIS, matching the Cramer–Rao lower bound for DAG-MDPs up to a factor of H.The guarantee is described as the first sample-complexity result under this setting.
  • Theoretical guarantees: MIS recursively estimates target-policy state distributions, yielding variance polynomial rather than exponential in the horizon.This contrasts with naive IS, whose trajectory-weight variance can grow exponentially in H.
  • Theoretical guarantees: The leading variance term depends on policy similarity and importance-weight second moments rather than explicitly on the state or action-space sizes.The bound can therefore accommodate continuous actions, while τ_a and τ_s appear only in lower-order terms.
  • Theoretical guarantees: The general upper bound scales as H^3, but smaller horizon exponents are possible for favorable policy–MDP configurations.When V_max is independent of H, the sample complexity can be O(H).
  • Optimality and limitations: Removing the remaining factor-H gap to the Cramer–Rao lower bound is left as an open question, especially for large or continuous action spaces.The paper conjectures that this factor may reflect an information-theoretic limit in those settings.
  • Proof sketch: The proof handles dependent within-episode data, unvisited states that induce bias, and recursive error propagation that can otherwise cause exponential blow-up.The analysis uses cumulative data representations, a fictitious unbiased estimator, and bounds showing state-distribution variance grows at most linearly in time.

5 Experiments

Experiments compare MIS with classic and marginalized importance-sampling baselines across time-invariant, time-varying, partially observable, continuous-action, and long-horizon environments. MIS generally preserves consistency and avoids the rapid horizon-related degradation seen in trajectory-weighted methods.

  • Time-invariant MDPs: MIS matches DM on ModelWin and outperforms IS/WIS on ModelFail, the strongest existing methods in their respective domains.
  • Time-invariant MDPs: MIS maintains polynomial dependence on H in time-invariant ModelWin and ModelFail experiments.
  • Time-varying MDPs: As H increases, Relative RMSE scales as O(H) for MIS, whereas IS and WIS quickly deteriorate and SSD-IS remains roughly constant but biased.
  • Long-horizon benchmarks: MIS achieves substantially better performance than existing approaches across several benchmarks, including Mountain Car, where long-horizon evaluation is required.

6 Conclusions

The paper proposes marginalized importance sampling for OPE, replacing trajectory-wide cumulative weights with estimated target-policy state marginals at each step. It establishes polynomial finite-sample guarantees, near-optimality relative to the Cramer–Rao bound, and strong empirical performance.

  • MIS estimates the target policy’s marginal state distribution at every step instead of using cumulative trajectory importance weights.
  • The paper proves the first finite-sample MIS error bound in its finite-state episodic setting with potentially infinite action spaces and polynomial dependence on all parameters.
  • The bound matches an oracle estimator’s asymptotic variance up to a low-order additive factor and lies within O(H) of the Cramer–Rao lower bound.
  • MIS achieves substantially better performance than existing approaches across multiple benchmarks.

B Theoretical analysis of the marginalized IS estimator

The analysis develops a fictitious estimator to handle the recursive structure and bias issues of MIS, then establishes unbiasedness and a finite-sample MSE bound. The resulting error propagates only linearly with horizon under sufficient sample size and is near rate-optimal.

  • Estimator analysis: The proof introduces a fictitious estimator to analyze the actual MIS estimator's recursive structure and bias.The fictitious estimator is not implementable, but the paper states that it behaves essentially the same as the actual estimator.
  • Unbiasedness: The fictitious estimator is unbiased for every δ < 1.The proof uses backward recursive applications of the law of total expectation.
  • Variance analysis: The variance decomposes into initial-state estimation and conditional importance-sampling variance for estimating transition quantities.The decomposition is analyzed recursively using the law of total variance.
  • Finite-sample bound: The estimator's error increases only linearly in time horizon instead of exponentially, provided n is at least linear in h.The paper describes this bound as tight and says it implies moderate error propagation.
  • Optimality: H^3SA/ϵ^2 episodes suffice in the finite-action setting, compared with the H^2SA/ϵ^2 Cramer-Rao lower bound, leaving at most a factor-H gap.For unbounded actions, the paper conjectures that the additional H dependence in its H^3τ_aτ_s/ϵ^2 bound is required.

C.2 Marginalized IS-Based Estimators

This section gives a generic marginalized IS framework that recursively estimates state-marginal ratios and replaces trajectory-level importance weights. Under unbiased or consistent ratio estimates, the resulting estimators retain unbiasedness or consistency, with extensions for partial observability and reward estimation.

  • Framework: The marginalized framework recursively estimates the state-marginal ratio under the target policy and uses it in place of cumulative trajectory weights.The construction is justified through the Markov property and conditional independence.
  • Statistical guarantees: An unbiased ratio estimator preserves unbiasedness, while a consistent ratio estimator preserves consistency of the marginalized OPE estimator.These guarantees are stated for estimators falling within the corresponding generic IS frameworks.
  • Partial observability: Observable states in POMDPs can provide partial trajectories for representing the current state and reducing variance.The method uses the closest observable state to construct the relevant marginalized ratio.
  • Variance reduction: The proposed marginalized estimator can reduce variance from cumulative importance weights, complementing doubly robust methods that reduce action-stochasticity variance.The paper further motivates reducing variance from reward-function stochasticity.
  • Reward estimation: Replacing sampled rewards with an unbiased and consistent reward estimator preserves the estimator's unbiasedness or consistency.The paper uses this extension to obtain a better marginalized framework.

D Details of Experiments

The experiments clarify the settings, discuss the preference between MIS and SSD-IS, and extend evaluation to doubly robust combinations.

  • Experimental scope: The experimental section specifies the settings, compares MIS and SSD-IS, and reports extended results for MIS combined with doubly robust approaches.These components organize the empirical evaluation described for the paper.

D.1 Environment Settings

The experiments use specialized benchmark environments, including partially observable and non-stationary non-mixing settings, to test marginalized estimation under long horizons and large action spaces. The authors note that some simpler environments do not expose worst-case horizon dependence.

  • ModelWin: ModelWin uses two actions, stochastic transitions controlled by p = 0.4, and rewards determined by transitions into s2 or s3.The domain begins in s1 and assigns rewards of 1, −1, or 0 based on the resulting transition.
  • ModelFail: ModelFail delays rewards until the agent returns to s1 from an unobservable state, with π choosing a1 and a2 using probabilities 0.2 and 0.8.The behavior policy chooses actions uniformly at random.
  • Partial observability: ModelFail's partial observability includes full-state checkpoints every other step and logged action probabilities when the observation is “?”.The paper explicitly distinguishes this specialized setup from general POMDP partial observability.
  • Modeling comparison: Treating “?” as a state causes the model-based approach to fail, whereas a memory of size 2 resolves the issue.An alternative checkpoint-state MDP may also be considered, but policy actions need not generally depend only on the checkpoint state.
  • Environment limitations: ModelWin and ModelFail are highly specialized because deterministic returns to s1 allow every method to estimate that marginal state distribution from one data point.Consequently, the authors do not expect these environments to reveal worst-case dependence on parameters such as H.
  • Mountain Car: Mountain Car has a two-dimensional state, three discrete actions, deterministic dynamics, and horizon H = 100, with state aggregation used for MIS and SSD-IS.Position and velocity are discretized into tabular abstract states for comparison.

D.2 Detailed Discussions

The discussion highlights that ModelWin is a special episodic case, while SSD-IS can fail in general episodic settings because stationary distributions may misrepresent time-specific visitation. It also attributes MIS’s advantage over MDR to using all data for marginalized-state estimation.

  • ModelWin is only a special case of episodic fully observable MDPs, so its correctness does not generalize to all episodic problems.
  • SSD-IS can fail in Mountain Car because its stationary state distribution poorly approximates average visitation during the latter half of the finite horizon.
  • MIS may outperform MDR because MIS estimates the marginalized state distribution with the full dataset, whereas MDR uses only half.
  • The theoretical explanation for MIS outperforming MDR is left for future work.

D.3 SSD-IS with finite state space.

SSD-IS estimates stationary state-distribution ratios for infinite-horizon MDPs, whereas finite-horizon applications require marginalized, time-indexed state distributions. Its finite-sample trade-off can nevertheless be favorable in sufficiently mixing stationary MDPs.

  • SSD-IS estimates the ratio of stationary state distributions under the target and behavior policies for infinite-horizon MDPs.
  • The marginalized state distribution averages within-episode state visitation over observed transition triplets.
  • The paper presents spectral estimators as an explicit rewriting of prior SSD-IS equations, matching the discrete-state implementation modulo boundary conditions.
  • In sufficiently mixing stationary MDPs with large H, SSD-IS may offer a finite-sample bias-variance trade-off: variance is smaller by a factor of H, while ratio bias decays exponentially with t.

D.4 Extended Experimental Studies

The extended studies apply marginalized estimation within several IS-based estimators and report strong empirical benefits, including on Mountain Car and related experimental settings. The appendix also documents the algorithm’s stepwise estimation procedure and implementation details.

  • DR, WDR, MDR, and MIS are compared to test whether other IS-based estimators benefit from the marginalized approach.
  • Other IS-based methods can leverage the marginalized approach to improve performance substantially in the reported experiments.
  • Figure 6 evaluates Mountain Car across different numbers of episodes.
  • The MIS estimator normalizes estimated target-policy state distributions to the probability simplex for better performance.
Loading 1906.03393v4…