mlsanityData to 7 Oct 2026

Statistical Tractability of Off-policy Evaluation of History-dependent Policies in POMDPs

arXiv 2503.01134 ↗First posted 3 Mar 2025cs.LG cs.AIcited by 7

Not on the map. Why?

Abstract (arXiv)

We investigate off-policy evaluation (OPE), a central and fundamental problem in reinforcement learning (RL), in the challenging setting of Partially Observable Markov Decision Processes (POMDPs) with large observation spaces. Recent works of Uehara et al. (2023a); Zhang & Jiang (2024) developed a model-free framework and identified important coverage assumptions (called belief and outcome coverage) that enable accurate OPE of memoryless policies with polynomial sample complexities, but handling more general target policies that depend on the entire observable history remained an open problem. In this work, we prove information-theoretic hardness for model-free OPE of history-dependent policies in several settings, characterized by additional assumptions imposed on the behavior policy (memoryless vs. history-dependent) and/or the state-revealing property of the POMDP (single-step vs. multi-step revealing). We further show that some hardness can be circumvented by a natural model-based algorithm -- whose analysis has surprisingly eluded the literature despite the algorithm's simplicity -- demonstrating provable separation between model-free and model-based OPE in POMDPs.

Key facts. Cited by 7 papers in the map (data through 7 Oct 2026). Builds on 47 of its 69 references that are in the map. First posted on arXiv 3 Mar 2025.

Builds on

47 of 69 references.

References · 47

  1. 2020Is Pessimism Provably Efficient for Offline RL?cited by 362
  2. 2015Doubly Robust Off-policy Value Evaluation for Reinforcement Learningcited by 337
  3. 2016Contextual Decision Processes with Low Bellman Rank are PAC-Learnablecited by 290
  4. 2016Data-Efficient Off-Policy Policy Evaluation for Reinforcement Learningcited by 285
  5. 2019Information-Theoretic Considerations in Batch Reinforcement Learningcited by 285
  6. 2021Bellman-consistent Pessimism for Offline Reinforcement Learningcited by 267
  7. 2019Batch Policy Learning under Constraintscited by 242
  8. 2018Breaking the Curse of Horizon: Infinite-Horizon Off-Policy Estimationcited by 226
  9. 2019Provably efficient RL with Rich Observations via Latent State Decodingcited by 169
  10. 2019Minimax Weight and Q-Function Learning for Off-Policy Evaluationcited by 150
  11. 2018More Robust Doubly Robust Off-policy Evaluationcited by 141
  12. 2019Empirical Study of Off-Policy Policy Evaluation for Reinforcement Learningcited by 121
35 more
  1. 2019Towards Optimal Off-Policy Evaluation for Reinforcement Learning with Marginalized Importance Samplingcited by 118
  2. 2019Double Reinforcement Learning for Efficient Off-Policy Evaluation in Markov Decision Processescited by 118
  3. 2022When Is Partially Observable Reinforcement Learning Not Scary?cited by 100
  4. 2020Off-Dynamics Reinforcement Learning: Training for Transfer with Domain Classifierscited by 93
  5. 2022A Review of Off-Policy Evaluation in Reinforcement Learningcited by 92
  6. 2021RL for Latent MDPs: Regret Guarantees and a Lower Boundcited by 69
  7. 2020Sample-Efficient Reinforcement Learning of Undercomplete POMDPscited by 66
  8. 2019Off-Policy Evaluation in Partially Observable Environmentscited by 65
  9. 2020Off-policy Policy Evaluation For Sequential Decisions Under Unobserved Confoundingcited by 60
  10. 2022Nearly Minimax Optimal Offline Reinforcement Learning with Linear Function Approximation: Single-Agent MDP and Markov Gamecited by 53
  11. 2016Reinforcement Learning of POMDPs using Spectral Methodscited by 51
  12. 2021Proximal Reinforcement Learning: Efficient Off-Policy Evaluation in Partially Observed Markov Decision Processescited by 40
  13. 2022Provable Reinforcement Learning with a Short-Term Memorycited by 40
  14. 2016A PAC RL Algorithm for Episodic POMDPscited by 37
  15. 2022Provably Efficient Reinforcement Learning in Partially Observable Dynamical Systemscited by 35
  16. 2021A Minimax Learning Approach to Off-Policy Evaluation in Confounded Partially Observable Markov Decision Processescited by 34
  17. 2022Learning in Observable POMDPs, without Computationally Intractable Oraclescited by 30
  18. 2022Sample-Efficient Reinforcement Learning of Partially Observable Markov Gamescited by 26
  19. 2022Planning in Observable POMDPs in Quasipolynomial Timecited by 25
  20. 2021Off-Policy Evaluation in Partially Observed Markov Decision Processes under Sequential Ignorabilitycited by 24
  21. 2022Partially Observable RL with B-Stability: Unified Structural Condition and Sharp Sample-Efficient Algorithmscited by 24
  22. 2021Doubly Robust Off-Policy Actor-Critic: Convergence and Optimalitycited by 20
  23. 2021A Spectral Approach to Off-Policy Evaluation for POMDPscited by 20
  24. 2022Future-Dependent Value-Based Off-Policy Evaluation in POMDPscited by 20
  25. 2022An Instrumental Variable Approach to Confounded Off-Policy Evaluationcited by 20
  26. 2021Sublinear Regret for Learning POMDPscited by 19
  27. 2023Learning in POMDPs is Sample-Efficient with Hindsight Observabilitycited by 17
  28. 2021Minimax Model Learningcited by 16
  29. 2022Embed to Control Partially Observed Systems: Representation Learning with Provable Sample Efficiencycited by 16
  30. 2022Computationally Efficient PAC RL in POMDPs with Latent Determinism and Conditional Embeddingscited by 12
  31. 2024On the Curses of Future and History in Future-dependent Value Functions for Off-policy Evaluationcited by 9
  32. 2023Provably Efficient Representation Learning with Tractable Planning in Low-Rank POMDPcited by 8
  33. 2023Marginalized Importance Sampling for Off-Environment Policy Evaluationcited by 5
  34. 2024RL in Latent MDPs is Tractable: Online Guarantees via Off-Policy Evaluationcited by 5
  35. 2023Sample-Efficient Learning of POMDPs with Multiple Observations In Hindsightcited by 3

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2025: 2; 2026: 5.

7 papers.

  1. 2025To Distill or Decide? Understanding the Algorithmic Trade-off in Partially Observable Reinforcement Learningcited by 3
  2. 2026A Covering Framework for Offline POMDPs Learning using Belief Space Metriccited by 1
  3. 2026Design Experiments to Compare Multi-armed Bandit Algorithmscited by 1
  4. 2025Selecting Belief-State Approximations in Simulators with Latent Statescited by 0
  5. 2026Minimax Optimal Strategy for Delayed Observations in Online Reinforcement Learningcited by 0
  6. 2026Off-Policy Evaluation for Missingness-Aware Policies in MDPs with Rewards Missing Not at Randomcited by 0
  7. 2026Exponential Hardness of Off-Policy Evaluation under History-Dependent Loggingcited by 0