Research map / Reinforcement learning / Policy gradient and actor-critic

Demystifying the Paradox of Importance Sampling with an Estimated History-Dependent Behavior Policy in Off-Policy Evaluation

ICML 2025 · Reinforcement learning › Policy gradient and actor-critic · approach: Importance-weighted OPE estimators · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Theoretically explains why estimating a history-dependent behavior policy lowers MSE of importance sampling OPE estimators (via a bias-variance decomposition and projection onto tangent-space constraints), extending the analysis to SIS, DR and MIS with parametric and nonparametric behavior policy estimation.

Problem

Prior work showed empirically that estimating a history-dependent behavior policy can lower the MSE of importance sampling OPE even when the true behavior policy is Markovian, but the reason was unexplained and limited to OIS.

Approach

Replacing the true behavior policy with a history-conditioned MLE acts as a projection of the IS estimator onto a constrained tangent space (similar to adding an augmentation term making it DR-like), which reduces asymptotic variance at the cost of finite-sample bias that grows with horizon and history length.

Key results

• Theory shows history-dependent behavior policy estimation reduces asymptotic variance of OIS and SIS and that longer history further reduces variance, while MIS variance increases with history length.
• Finite-sample bias of history-dependent estimators grows with horizon (factor C^{2T}) and history length, so they are biased relative to oracle estimators in small samples.
• Numerical experiments on CartPole (averaged over 50 simulations) show SIS and DR with misspecified Q achieve lower MSE with longer history at large sample sizes, while MIS MSE worsens with history length.

Measured effects reported in the paper

Surprising findings

• Estimating the behavior policy can lower MSE of IS estimators even when the behavior policy is known, because plugging in an estimate acts like adding an augmentation term.
• History-dependent MIS ratio estimation increases asymptotic variance, contrary to SIS/OIS/DR.

Limitations

• Finite-sample bias increases with horizon and history length, making history-dependent estimators risky in small samples.
• Heuristic history-length selection rule is not validated in the paper (simulations not reported).

Experimental setup

Datasets: CartPole simulator (gym) MuJoCo Inverted Pendulum MuJoCo Double Inverted Pendulum MuJoCo Swimmer

Benchmarks: CartPole Inverted Pendulum Double Inverted Pendulum Swimmer

Metrics: absolute bias log MSE log variance

Baselines: oracle importance sampling SIS with oracle ratio DR with oracle ratio MIS with oracle ratio

Builds on: doubly robust estimation marginalized importance sampling conditional importance sampling incremental importance sampling

Closest papers by meaning

• Towards Optimal Off-Policy Evaluation for Reinforcement Learning with Marginalized Importance Sampling (NeurIPS 2019 · similarity 0.94)
• Importance Sampling Policy Evaluation with an Estimated Behavior Policy (ICML 2019 · similarity 0.93)
• Scaling Marginalized Importance Sampling to High-Dimensional State-Spaces via State Abstraction (AAAI 2023 · similarity 0.92)
• Statistical Tractability of Off-policy Evaluation of History-dependent Policies in POMDPs (ICLR 2025 · similarity 0.90)
• Efficient Policy Evaluation with Offline Data Informed Behavior Policy Design (ICML 2024 · similarity 0.90)
• Kernel Metric Learning for In-Sample Off-Policy Evaluation of Deterministic RL Policies (ICLR 2024 · similarity 0.89)