Statistical Tractability of Off-policy Evaluation of History-dependent Policies in POMDPs
Yuheng Zhang Nan Jiang
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.
Partially Observable Markov Decision Process; Offline Policy Evaluation; Reinforcement Learning Theory