Research map / Reinforcement learning / MDPs and planning
On the Curses of Future and History in Future-dependent Value Functions for Off-policy Evaluation
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.
Analyzes off-policy evaluation in POMDPs with future-dependent value functions and proposes outcome and belief coverage assumptions that give polynomial (non-exponential in horizon) guarantees, plus a new MIS-style algorithm.
Problem
OPE in partially observable environments: existing FDVF-based guarantees depend on the boundedness of future-dependent value functions and related quantities, which can be exponential in horizon, and history-based MDP reductions suffer exponential cumulative importance weights.
Approach
Introduces outcome coverage (overlap from the current step onward) to bound FDVFs and belief coverage (overlap of belief states) to bound effective history weights, yielding fully polynomial guarantees; the belief-coverage weights enable an MIS-style estimator that avoids the double-sampling Bellman-completeness requirement.
Key results
- Shows FDVF boundedness can be exponential in horizon under a natural construction (importance-sampling and pseudo-inverse solutions), motivating new coverage assumptions.
- Outcome coverage yields a bound ||V_F||_inf <= H*C_{F,inf} (L_inf outcome coverage) and the FDVF-based estimator's error bound is polynomial in H with coverage parameters C_mu, C_{H,2}, C_{F,inf}.
- New MIS-style algorithm with error bound epsilon_V + epsilon_W + c H^2 C_{H,inf}(C_{F,inf}+1) sqrt(C_mu log(|V||W|/delta)/n) that avoids Bellman completeness.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use L∞ outcome coverage with the reward-weighted FDVF construction | FDVF-based OPE in POMDPs · Finite-horizon POMDPs | FDVF range bound | Helped |
| Use L2 belief coverage to construct effective history weights by belief matching | FDVF-based OPE in POMDPs · Finite-horizon POMDPs | effective history-weight second moment | Helped |
| Replace the helper class and Bellman-completeness requirement with a history-weight class and weight realizability | New effective-history-weight OPE algorithm · Finite-horizon POMDPs | Bellman-completeness requirement | Helped |
Surprising findings
- The natural FDVF constructions (importance sampling and pseudo-inverse) yield bounds exponential in horizon, so FDVF boundedness is not automatic.
Limitations
- Results hold for memoryless policies; extension to rich memories (e.g., belief-based) incurs exponential coverage dilution (curse of memory).
- Requires assumptions that the function class range is not much larger than the needed FDVF range and known behavior policy action probabilities.
- Purely theoretical; no empirical experiments reported in the main text.
Experimental setup
Baselines: importance sampling fitted-q evaluation pseudo-inverse FDVF construction
Builds on: future-dependent value functions marginalized importance sampling linear MDP coverage
Closest papers by meaning
- Future-Dependent Value-Based Off-Policy Evaluation in POMDPs (NeurIPS 2023 · similarity 0.95)
- Statistical Tractability of Off-policy Evaluation of History-dependent Policies in POMDPs (ICLR 2025 · similarity 0.90)
- Off-Policy Evaluation for Episodic Partially Observable Markov Decision Processes under Non-Parametric Models (NeurIPS 2022 · similarity 0.90)
- Breaking the Order Barrier: Off-Policy Evaluation for Confounded POMDPs (NeurIPS 2025 · similarity 0.90)
- Efficient and Sharp Off-Policy Evaluation in Robust Markov Decision Processes (NeurIPS 2024 · similarity 0.88)
- RL in Latent MDPs is Tractable: Online Guarantees via Off-Policy Evaluation (NeurIPS 2024 · similarity 0.86)
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.