Statistical Tractability of Off-policy Evaluation of History-dependent Policies in POMDPs
Partially Observable Markov Decision Process; Offline Policy Evaluation; Reinforcement Learning Theory
Yes
No ethics review needed.
See weaknesses
It seems interesting to me that the model-based methods, which use synthetic data from learned models, bypass the limitations of model-free algorithms, especially in history-dependent scenarios.
This paper explores the off-policy evaluation (OPE) of history-dependent policies within partially observable Markov decision processes (POMDPs) using large observation spaces. Traditional methods for OPE in POMDPs have relied on model-free approaches and simplified memoryless policies due to computational complexity. This paper address this by examining the statistical challenges of evaluating more complex, history-dependent policies and by proposing a model-based method to circumvent limitations in model-free approaches. Key theoretical contributions include identifying scenarios where model-free methods are insufficient, as well as demonstrating how a simple model-based approach can achieve polynomial sample complexity.
1. What is the practical meaning of assumption D (multi-step outcome revealing) and how is it related to other revealing conditions in offline and online partially observable reinforcement learning, as well as the corresponding results?

2. Although it is said that $M^*$ does not necessarily satisfy the realizability, would the observable-equivalent realizability actually similar to it, and the resulting dependency on the realizability error seems actually trivial? Since the only difference is the additional gap due to the error in estimation likelihood from the misspecification of $M$.
Yes
No ethics review needed.
I have a concern regarding the MLE part. From my understanding, it seems that $\epsilon_{MLE}$ may implicitly depend on the horizon length $H$. Could you please clarify and elaborate on this point? If so, how would this dependence impact the main results in the paper?
The findings in this paper are interesting. It demonstrates that no sample-efficient model-free OPE algorithm exists for POMDPs when evaluating history-dependent policies, whereas a model-based approach can achieve polynomial sample complexity. This highlights the effectiveness of model-based methods in POMDPs, and perhaps inspires future research on model-based RL for POMDPs. The theoretical analysis is solid and strong, and the writing is logically structured.
This paper explores the statistical tractability of off-policy evaluation (OPE) for history-dependent policies in unconfounded partially observable Markov decision processes (POMDPs) with large observation spaces. The authors first establish information-theoretic hardness results for model-free algorithms when evaluating history-dependent policies, highlighting the increased complexity compared to memoryless policies. To address these challenges, they then propose a model-based approach that enables efficient OPE for history-dependent policies.
1. The writing could be improved to be more accessible to readers who may not be deeply familiar with this topic. For example, in the introduction, the authors could provide additional insights into belief and outcome coverage when these concepts are first introduced.

2. Another area for improvement in the writing would be providing a broader perspective on the paper’s contributions. Since the main contribution is extending existing results from memoryless policies to history-dependent policies, it would be helpful to include a high-level discussion in the introduction on (1) why history-dependent policies are particularly important in POMDP settings, and (2) what major challenges arise when attempting to apply existing analysis techniques for memoryless policies to history-dependent policies.
Yes
No ethics review needed.
1. Can authors provide any empirical or simulation results by the proposed algorithm on the setting described in the paper?
2. Are there any possibilities that can handle the state-space mismatch problem specified in Theorem 7?
1. The paper addresses an important gap in the literature by extending OPE to history-dependent target policies in POMDPs.
2. The authors provide solid theoretical results, including both hardness proofs and positive guarantees for model-based algorithm.
3. The paper is well-organized, with clear definitions, assumptions, and theorem statements that make the paper accessible.
This paper focus on OPE problems in unconfounded POMDPs with large observation spaces and history-dependent target policies. While previous work addressed the problem for memoryless target policies under certain coverage assumptions, the authors extended these results to history-dependent target policies and prove polynomial complexity.
1. The paper does not include experimental results to validate the theoretical findings or to demonstrate the practical effectiveness of the MLE-based algorithm.
2. The model-based algorithm is not robust to state-space mismatch or model misspecification.
Yes
No ethics review needed.
Should the policy $\pi$ in Eq. (1) be behavior policy $\pi_b$?

 I wonder if assumption A can be relaxed, for example, estimated via the offline data set? And how would this relax affect the MLE in Algorithm?
(1) The paper provides hardness results for model-free methods, which motivates the authors to adopt the model-based methods.

(2) This paper weakens several previous assumptions on target policies and POMDPs, and proves the polynomial sample complexity upper bound for model-based methods.

(3) The paper is well-organized and easy to follow.
This paper investigates off-policy evaluation in POMDPs. Compared to previous work, this paper considers more general target policies that depend on the entire observable history. The authors first provide hardness results showing that a model-free algorithm can not output a near-optimal evaluation with polynomial sample complexity. To handle this challenge, the authors adopt a model-based method based on MLE. The authors further prove that under certain assumptions, even considering more general target policies, the proposed model-based method can output near-optimal evaluation with polynomial sample complexity. Finally, the authors weaken the realization assumption under misspecification cases.
It seems that the **Pre-filtering** and **MLE** parts of algorithms are not computationally efficient. **Pre-filtering** requires to verify each of the models in set $\mathcal{M}$. Is there any efficient way to implement these two steps?
@inproceedings{
anonymous2024statistical,
title={Statistical Tractability of Off-policy Evaluation of History-dependent Policies in {POMDP}s},
author={Anonymous},
booktitle={Submitted to The Thirteenth International Conference on Learning Representations},
year={2024},
url={https://openreview.net/forum?id=Qja5s0K3VX},
note={under review}
}
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.
I certify that there is no URL (e.g., github page) that could be used to find authors’ identity.
I acknowledge that I and all co-authors of this work have read and commit to adhering to the ICLR Code of Ethics.
Partially Observable Markov Decision Process; Offline Policy Evaluation; Reinforcement Learning Theory
I certify that there is no acknowledgement section in this submission for double blind review.
/pdf/c085b93ed60aa54119af628afca267ec34298e69.pdf
learning theory
I understand the reciprocal reviewing requirement as described on https://iclr.cc/Conferences/2025/CallForPapers. If none of the authors are registered as a reviewer, it may result in a desk rejection at the discretion of the program chairs. To request an exception, please complete this form at https://forms.gle/Huojr6VjkFxiQsUp6.
I certify that this submission complies with the submission instructions as described on https://iclr.cc/Conferences/2025/AuthorGuide.
Statistical Tractability of Off-policy Evaluation of History-dependent Policies in POMDPs
ICLR 2025 Conference Submission
ICLR.cc/2025/Conference/Submission