mlsanityData to 14 Oct 2026

On the Curses of Future and History in Future-dependent Value Functions for Off-policy Evaluation

arXiv 2402.14703 ↗First posted 22 Feb 2024cs.LG cs.AI stat.MLcited by 10

Not on the map. Why?

Abstract (arXiv)

We study off-policy evaluation (OPE) in partially observable environments with complex observations, with the goal of developing estimators whose guarantee avoids exponential dependence on the horizon. While such estimators exist for MDPs and POMDPs can be converted to history-based MDPs, their estimation errors depend on the state-density ratio for MDPs which becomes history ratios after conversion, an exponential object. Recently, Uehara et al. [2022a] proposed future-dependent value functions as a promising framework to address this issue, where the guarantee for memoryless policies depends on the density ratio over the latent state space. However, it also depends on the boundedness of the future-dependent value function and other related quantities, which we show could be exponential-in-length and thus erasing the advantage of the method. In this paper, we discover novel coverage assumptions tailored to the structure of POMDPs, such as outcome coverage and belief coverage, which enable polynomial bounds on the aforementioned quantities. As a side product, our analyses also lead to the discovery of new algorithms with complementary properties.

Key facts. Cited by 10 papers in the map (data through 14 Oct 2026). Builds on 46 of its 73 references that are in the map. First posted on arXiv 22 Feb 2024.

Builds on

46 of 73 references.

References · 46

  1. 2015Doubly Robust Off-policy Value Evaluation for Reinforcement Learningcited by 339
  2. 2016Contextual Decision Processes with Low Bellman Rank are PAC-Learnablecited by 292
  3. 2019Information-Theoretic Considerations in Batch Reinforcement Learningcited by 287
  4. 2016Data-Efficient Off-Policy Policy Evaluation for Reinforcement Learningcited by 286
  5. 2021Bellman-consistent Pessimism for Offline Reinforcement Learningcited by 269
  6. 2019DualDICE: Behavior-Agnostic Estimation of Discounted Stationary Distribution Correctionscited by 254
  7. 2019Batch Policy Learning under Constraintscited by 244
  8. 2018Breaking the Curse of Horizon: Infinite-Horizon Off-Policy Estimationcited by 227
  9. 2019Provably efficient RL with Rich Observations via Latent State Decodingcited by 169
  10. 2022Hybrid RL: Using Both Offline and Online Data Can Make RL Efficientcited by 161
  11. 2019Minimax Weight and Q-Function Learning for Off-Policy Evaluationcited by 150
  12. 2018More Robust Doubly Robust Off-policy Evaluationcited by 141
34 more
  1. 2022Offline Reinforcement Learning with Realizability and Single-policy Concentrabilitycited by 123
  2. 2020Minimax-Optimal Off-Policy Evaluation with Linear Function Approximationcited by 120
  3. 2019Towards Optimal Off-Policy Evaluation for Reinforcement Learning with Marginalized Importance Samplingcited by 119
  4. 2019Double Reinforcement Learning for Efficient Off-Policy Evaluation in Markov Decision Processescited by 119
  5. 2021Provable Benefits of Actor-Critic Methods for Offline Reinforcement Learningcited by 110
  6. 2020Batch Value-function Approximation with Only Realizabilitycited by 104
  7. 2022When Is Partially Observable Reinforcement Learning Not Scary?cited by 100
  8. 2020Off-Dynamics Reinforcement Learning: Training for Transfer with Domain Classifierscited by 97
  9. 2020Improper Learning for Non-Stochastic Controlcited by 83
  10. 2021Towards Instance-Optimal Offline Reinforcement Learning with Pessimismcited by 78
  11. 2021RL for Latent MDPs: Regret Guarantees and a Lower Boundcited by 70
  12. 2019Off-Policy Evaluation in Partially Observable Environmentscited by 66
  13. 2020Sample-Efficient Reinforcement Learning of Undercomplete POMDPscited by 66
  14. 2022Near-optimal Offline Reinforcement Learning with Linear Representation: Leveraging Variance Information with Pessimismcited by 65
  15. 2020Off-policy Policy Evaluation For Sequential Decisions Under Unobserved Confoundingcited by 61
  16. 2016Reinforcement Learning of POMDPs using Spectral Methodscited by 52
  17. 2022PAC Reinforcement Learning for Predictive State Representationscited by 43
  18. 2022Provable Reinforcement Learning with a Short-Term Memorycited by 40
  19. 2016A PAC RL Algorithm for Episodic POMDPscited by 37
  20. 2021A Minimax Learning Approach to Off-Policy Evaluation in Confounded Partially Observable Markov Decision Processescited by 36
  21. 2022Provably Efficient Reinforcement Learning in Partially Observable Dynamical Systemscited by 35
  22. 2022Pessimism in the Face of Confounders: Provably Efficient Offline Reinforcement Learning in Partially Observable Markov Decision Processescited by 26
  23. 2021Off-Policy Evaluation in Partially Observed Markov Decision Processes under Sequential Ignorabilitycited by 24
  24. 2022Partially Observable RL with B-Stability: Unified Structural Condition and Sharp Sample-Efficient Algorithmscited by 24
  25. 2021A Spectral Approach to Off-Policy Evaluation for POMDPscited by 21
  26. 2022Future-Dependent Value-Based Off-Policy Evaluation in POMDPscited by 21
  27. 2023Augmented balancing weights as linear regressioncited by 21
  28. 2019Lecture Notes: Selected topics on robust statistical learning theorycited by 17
  29. 2021Minimax Model Learningcited by 16
  30. 2023Lower Bounds for Learning in Revealing POMDPscited by 15
  31. 2023Learning Hidden Markov Models Using Conditional Samplescited by 12
  32. 2022A Complete Characterization of Linear Estimators for Offline Policy Evaluationcited by 7
  33. 2023A Policy Gradient Method for Confounded POMDPscited by 6
  34. 2023Provably Efficient UCB-type Algorithms For Learning Predictive State Representationscited by 6

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2024: 1; 2025: 4; 2026: 5.

10 papers.

  1. 2025Offline Reinforcement Learning in Large State Spaces: Algorithms and Guaranteescited by 10
  2. 2025Statistical Tractability of Off-policy Evaluation of History-dependent Policies in POMDPscited by 8
  3. 2024RL in Latent MDPs is Tractable: Online Guarantees via Off-Policy Evaluationcited by 6
  4. 2025Reinforcement Learning with Continuous Actions Under Unmeasured Confoundingcited by 3
  5. 2026A Unifying View of Coverage in Linear Off-Policy Evaluationcited by 1
  6. 2026A Covering Framework for Offline POMDPs Learning using Belief Space Metriccited by 1
  7. 2026Exponential Hardness of Off-Policy Evaluation under History-Dependent Loggingcited by 1
  8. 2025Selecting Belief-State Approximations in Simulators with Latent Statescited by 0
  9. 2026Off-Policy Evaluation for Missingness-Aware Policies in MDPs with Rewards Missing Not at Randomcited by 0
  10. 2026Revealing After Overwriting: An Exponential POMDP OPE Lower Bound under History-Dependent Loggingcited by 0