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

Off-policy evaluation (OPE) is crucial in reinforcement learning, aiming to estimate a new policy’s performance using historical data from a different policy. In partially observable environments (POMDPs), however, existing OPE methods struggle due to the ‘curse of horizon’, leading to exponentially large errors as the time horizon increases. This is primarily because the methods rely on density ratios which are exponential. This paper highlights this challenge and the problem of existing solutions which can also have exponential dependency on the horizon.

To address this, the authors propose novel coverage assumptions, namely outcome and belief coverage, specifically tailored for POMDPs. These assumptions, unlike previous ones, leverage the inherent structure of POMDPs. By incorporating these assumptions into a refined version of the future-dependent value function framework, the researchers derive fully polynomial estimation error bounds, thus avoiding the curse of horizon. This involves constructing a novel minimum weighted 2-norm solution for future-dependent value functions and demonstrating its boundedness under the proposed coverage conditions. Furthermore, they develop a new algorithm analogous to marginalized importance sampling for MDPs and improved analyses that leverage the L1 normalization of vectors. These findings are significant as they provide a more efficient and accurate approach to OPE in complex, real-world scenarios.