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

We thank the reviewer for their valuable comments and respond to the weaknesses and questions below.

---

Pre-filtering is computationally inefficient

You are right. However, we focus on the statistical tractability in this work, and the same pre-filtering step has also appeared in MLE algorithms for online learning of POMDPs (Liu et al. 2022a). In fact, even without pre-filtering, MLE itself is generally computationally inefficient for latent-variable models like POMDPs, and standard approximations such as Expectation-Maximization (EM) do not have strong theoretical guarantees. That said, the pre-filtering step may inspire practical regularization methods (e.g., using $C\_\mathcal{F, h}$ as a regularizer to bias learning towards models with smaller $C\_\mathcal{F, h}$) to improve the performance of heuristic approximations of MLE, but that is beyond the scope of this paper as our focus is on the fundamental theoretical understanding.

---

$\pi$ in Eq.(1)

You are right that it should be $\pi\_b$; we will correct. In fact the policy does not matter here: $\log P\_{M}^{\pi}(\tau)$ can be broken into log of transition probabilities and log of action probabilities (under $\pi$), and the latter has no dependence on the model $M$ and thus has 0 gradient. We wrote in this form because it makes the application of MLE guarantees obvious, but we will add additional details to clarify.

---

Relaxing Assumption A & whether it can be estimated

We guess you mean whether we can handle unknown $\pi\_b$ and estimate it from data; we believe so. Note that MLE itself does not require knowledge of $\pi\_b$ (as explained above). The only step in the algorithm that requires $\pi\_b$ is actually pre-filtering in the multi-step revealing setting: to compute $\Sigma\_{\mathcal{F}, h}$ we need to know $U\_{\mathcal{F}, h}$, which is the probability of future sequences given different hidden state (under a candidate model dynamics). The probability of actions need to be given by $\pi\_b$. When $\pi\_b$ is unknown, the standard treatment is to assume a realizable policy class and learn it from data using behavior cloning. It remains to show that the calculation of $\Sigma\_{\mathcal{F}, h}$ is robust to the estimation error of $\pi\_b$ through behavior cloning, which we believe is possible.

Also, a main message of our work is to compare model-free and model-based algorithms, and the model-free algorithms of Uehara et al. (2023a) and Zhang & Jiang (2024) also require knowledge of $\pi\_b$, so simply assuming a known $\pi\_b$ allows for the cleanest comparison.

We thank the reviewer for their valuable comments and respond to the weaknesses and questions below.

---

Empirical results

Our work aims to provide theoretical understanding of fundamental limits of OPE in POMDPs. A major bottleneck in experiments is that the MLE model-based algorithm is known to be computationally inefficient in latent-variable models such as POMDPs, and popular approximations based on Expectation-Maximization (EM) do not have strong theoretical guarantees. Nevertheless, we believe that the theoretical separation between model-free and model-based methods in this setting is interesting in its own right. Note that similar separation results in other areas of the RL literature are mostly pure theory, too (see e.g., Sun et al. 2019).

---

State-space mismatch

Contrary to what the reviewer wrote, state-space mismatch is actually handled in Theorem 8, which is a positive result that complements the negative result in Theorem 7. The problem is not about the algorithm, but how the assumptions are stated and extended (from the realizable case to the state-space mismatch case). If we take the earlier assumptions (especially Assumption D) at face value, Theorem 7 tells us that the MLE algorithm fails, but that is due to us misunderstanding what Assumption D really means and which models it is really imposed on ($M^*$ vs. models in $\mathcal{M}$). Theorem 8 shows that once we impose Assumption D on models in $\mathcal{M}$, which is an alternative interpretation of imposing it on $M^*$ + pre-filtering in the realizable setting, the polynomial guarantee can be recovered. The contrast between Theorems 7 and 8 teach us something interesting about the fundamental nature of the revealing assumptions, which is only exposed under state-space mismatch and rarely touched by prior works.

We thank the reviewer for their valuable comments and will improve the writing accordingly. Below we respond to the weaknesses and questions.

---

Importance of history-dependent policies

In POMDPs, optimal policies are generally history dependent. In particular, optimal policies can take the form of a mapping from belief states to actions, and the belief state itself is a function of history. Therefore, it is very natural to consider history-dependent policies in POMDPs, and the restriction to memoryless policies in prior works is due to technical difficulties. We can add more explanation on this point in revision.

---

Major challenges in applying existing analysis techniques for memoryless policies to history-dependent policies

The prior works of Uehara et al. (2023a) and Zhang & Jiang (2024) provide analyses of a model-free algorithm. As our Table 1 shows, model-free algorithms provably cannot handle general history-dependent policies under the assumptions of prior works (e.g., belief and outcome coverages). This is information-theoretic hardness (Theorem 3), so no amount of clever analyses can provide a rescue. Therefore, we need to consider stronger algorithms (model-based) to circumvent the hardness, which requires different analyses.

---

$H$-dependence on $\epsilon\_{MLE}$

$\epsilon\_{MLE}$ does not depend on $H$ in any way. Please refer to the equation above Eq.(3) on page 16, where an explicit expression for $\epsilon\_{MLE}$ is given and it does not depend on $H$. We are not sure why the reviewer makes this comment, but maybe you are worried that the $\epsilon\_{MLE}$ bounds the TV error of estimating the distribution of trajectories, which is supported on a very large space (the space of trajectories has a large cardinality that is exponential in horizon $H$). The key here is that the model class induces a hypothesis class of distributions over trajectories, and the learning algorithm is essentially performing density estimation using this hypothesis class. When the model class has limited capacity (this corresponds to the $\log|\mathcal{M}|$ term in $\epsilon\_{MLE}$), the TV error of density estimation will be bounded in a way that is independent of the size of the support. The size of the support is only incurred when you estimate without a hypothesis class (i.e., a "tabular" approach), using the empirical frequency that each trajectory appears in the data, but that is not the case here.

We thank the reviewer for their valuable comments and respond to the weaknesses below.

---

Assumption D

As mentioned on Line 195, multi-step outcome revealing essentially means that the future $f\_h$ can nontrivially predict the latent state $s\_h$. In particular, $C\_{\mathcal{F}} < \infty$ is equivalent to the outcome matrix $U\_{\mathcal{F},h}$ is full-rank. Roughly speaking, this means that starting from different latent states, the distribution of future observables is different under the behavior policy.

The more popular revealing condition is single-step outcome revealing (Assumption E) and its subtle variants, which come from the online POMDP literature, e.g., Liu et al. (2022a) that we cited. Since this condition requires that the immediate observation $o\_h$ nontrivially predicts $s\_h$ (Line 249), it is (generally speaking) stronger than multi-step outcome revealing, as the latter allows using the entire future---which includes $o\_h$ as part of it---to predict $s\_h$. In fact, one of contributions is exactly to study whether model-free and model-based algorithms can achieve polynomial guarantees under these assumptions (see columns of Table 1). For offline RL literature, the line of work by Uehara et al. (2023a) and Zhang & Jiang (2024) are the only one that we know who provide guarantees based on belief coverage (Assumption C) instead of exponential quantities (such as the boundedness of cumulative importance weight; see discussion in the introduction of Zhang & Jiang (2024)), and their assumption is essentially a version of multi-step outcome coverage.

---

Observable-equivalent Realizability

The reviewer wrote “would the observable-equivalent realizability actually [be] similar to it”. We guess you mean that the result and analysis in Theorem 8 is not technically that much different from the earlier analyses based on realizability, and incorporating the misspecification error is technically mundane. We agree, but incorporating misspecification is not the main message of this section. The main message is to consider state space mismatch, a practical scenario that is often overlooked by existing theoretical works on learning POMDPs. In particular, Theorem 7 may strike as a surprise since it is a natural extension of Theorem 4 to the state mismatch setting if one does not carefully think about what the assumptions really mean and which models they are really imposed on ($M^*$ vs. models in $\mathcal{M}$). Theorem 8 completes the message of Theorem 7 by showing that, polynomial guarantees can be recovered when we impose Assumption D on the models in $\mathcal{M}$ instead of $M^*$. Handling misspecification is just a nice little bonus orthogonal to the main point of the section, and you are right in pointing out that it is not technically significant.