Research map / Reinforcement learning / MDPs and planning
Statistical Tractability of Off-policy Evaluation of History-dependent Policies in POMDPs
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.
Proves information-theoretic hardness for model-free off-policy evaluation of history-dependent policies in POMDPs and shows a model-based MLE algorithm achieves polynomial sample complexity under single-step or memoryless-behavior multi-step revealing conditions.
Problem
Off-policy evaluation of history-dependent target policies in unconfounded POMDPs with large observation spaces, where prior model-free methods only handle memoryless targets with polynomial sample complexity.
Approach
Shows that any model-free OPE algorithm (one that queries the target policy only on offline-data histories) must suffer exponential sample complexity for history-dependent targets, while a simple MLE-based model-based algorithm with pre-filtering of models by revealing coefficients achieves polynomial bounds under single-step revealing, or under multi-step revealing with a memoryless behavior poli
Key results
- Theorem shows no model-free OPE algorithm can achieve polynomial sample complexity for history-dependent target policies even with memoryless behavior policy and single-step revealing, via a construction requiring Omega(2^H) samples.
- MLE-based model-based OPE attains error bound O(H^2 C_O^2 * ov * sqrt(log(|M|/delta)/n)) under single-step outcome revealing, with ov bounded by C_A C_H.
- Under multi-step revealing with memoryless behavior policy, the model-based MLE achieves a polynomial bound with C_F replacing C_O, showing memoryless behavior policies suffice to evaluate history-dependent targets.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Allow the target policy to depend on the full history rather than be memoryless | Model-free OPE in POMDPs · OPE in POMDPs with single-step revealing and memoryless behavior policy | sample complexity: poly(H) versus Ω(2^H) | Hurt |
| Use model-based MLE and evaluate the target policy in the fitted model | OPE of history-dependent target policies in POMDPs · Single-step outcome revealing | sample complexity: poly(H,\log (|\mathcal M|/\delta),\epsilon, C_{\mathcal{A}},C_{\mathcal F},C_{\mathcal H}) | Helped |
| Use a memoryless behavior policy with model-based MLE | OPE of history-dependent target policies in POMDPs · Multi-step outcome revealing | sample complexity: poly(H,\log (|\mathcal M|/\delta),\epsilon, C_{\mathcal{A}},C_{\mathcal F},C_{\mathcal H}) | Helped |
| Replace single-step revealing with multi-step revealing while requiring a memoryless behavior policy | MLE model-based OPE · OPE of history-dependent target policies in POMDPs | sample complexity | No clear effect |
| Replace model realizability with observable-equivalent realizability | MLE model-based OPE · OPE in POMDPs | sample complexity: poly(H) versus Ω(2^H) | Hurt |
| Require every model in the class to satisfy multi-step revealing and allow approximate observable-equivalent realizability | MLE model-based OPE · OPE in POMDPs with state-space mismatch | absolute return estimation error: \mathcal O \pa{H^2 C_{\mathcal F}^2 \offm \sqrt{\frac{\log \frac{|\mathcal M|}{\delta}}{n}+\epsapprox}} | Helped |
| Evaluate the same target policy with model-based rather than model-free OPE | OPE of history-dependent target policies in POMDPs · Single-step revealing, or multi-step revealing with memoryless behavior | sample complexity: model-free: Ω(2^H); model-based: polynomial | Helped |
Surprising findings
- Memoryless behavior policies can accurately evaluate history-dependent target policies under coverage conditions, counter to the intuition that history-dependent behavior is needed.
- Model-free OPE provably fails for history-dependent targets even when the model is fully known, while model-based rollouts succeed.
Limitations
- Model-based algorithm's guarantee with history-dependent behavior policy and multi-step revealing is left open.
- Requires knowledge of revealing coefficients C_O or C_F for pre-filtering.
- Results are theoretical with finite discrete state, action, and observation spaces.
Experimental setup
Baselines: model-free OPE of Uehara et al. 2023a importance sampling
Builds on: Uehara et al. 2023 future-dependent value functions for POMDP OPE Zhang & Jiang 2024 observable operator models weakly revealing POMDPs
Closest papers by meaning
- Off-Policy Evaluation in Partially Observable Environments (AAAI 2020 · similarity 0.94)
- Model-based Reinforcement Learning for Confounded POMDPs (ICML 2024 · similarity 0.92)
- Demystifying the Paradox of Importance Sampling with an Estimated History-Dependent Behavior Policy in Off-Policy Evaluation (ICML 2025 · similarity 0.90)
- On the Curses of Future and History in Future-dependent Value Functions for Off-policy Evaluation (NeurIPS 2024 · similarity 0.90)
- Model Selection for Off-policy Evaluation: New Algorithms and Experimental Protocol (NeurIPS 2025 · similarity 0.90)
- RL in Latent MDPs is Tractable: Online Guarantees via Off-Policy Evaluation (NeurIPS 2024 · similarity 0.89)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.