A Covering Framework for Offline POMDPs Learning using Belief Space Metric
Organizations: Northwestern University
Abstract
In off policy evaluation (OPE) for partially observable Markov decision processes (POMDPs), an agent must infer hidden states from past observations, which exacerbates both the curse of horizon and the curse of memory in existing OPE methods. This paper introduces a novel covering analysis framework that exploits the intrinsic metric structure of the belief space (distributions over latent states) to relax traditional coverage assumptions. By assuming value relevant functions are Lipschitz continuous in the belief space, we derive error bounds that mitigate exponential blow ups in horizon and memory length. Our unified analysis technique applies to a broad class of OPE algorithms, yielding concrete error bounds and coverage requirements expressed in terms of belief space metrics rather than raw history coverage. We illustrate the improved sample efficiency of this framework via case studies: the double sampling Bellman error minimization algorithm, and the memory based future dependent value functions (FDVF). In both cases, our coverage definition based on the belief space metric yields tighter bounds.
Figures & tables
| Criteria | Existing Coverage With Curse of Horizon/Memory | Our Coverage using Belief Space Smoothness | ||
|---|---|---|---|---|
| Bellman Error Minimization ( e.g. Double Sampling ) | ||||
| Coverage Definition [ 14 ] | \displaystyle\bigg\|\frac{d^{\pi_{e}}({\color[rgb]{1,0,0}\tau_{h}},a)}{d^{D}({\color[rgb]{1,0,0}\tau_{h}},a)}\bigg\|_{\infty} | \displaystyle\bigg\|\frac{d^{\pi_{e}^{\phi}}({\color[rgb]{0,0.62,0}\phi(b)},a)}{d^{D}({\color[rgb]{0,0.62,0}\phi(b)},a)}\bigg\|_{\infty} | ||
| Coverage Worst Case 1 1 1 “Worst-case coverage” refers to the worst case for the most exploratory data-collection distribution. Scale | \color[rgb]{1,0,0}\displaystyle|\mathcal{B}|=\Theta((|\mathcal{O}||\mathcal{A}|)^{H}) | > | \color[rgb]{0,0.62,0}\displaystyle\mathrm{Covering}(\mathcal{B},\Theta(n^{-1/2})) 2 2 2 denotes the covering number of . | |
| Ability to handle | ✘ : Infinite | ✓ : Polynomial guarantee see example 1 | ||
| Future Dependent Value Function | ||||
| Coverage Definition [ 34 ] | {\sup_{h,V}\sqrt{\frac{\mathbb{E}_{\pi_{e}}[(\mathcal{B}^{(\mathcal{S},\mathcal{H}_{H})}V)(s_{h},{\color[rgb]{1,0,0}\tau_{h}})^{2}]}{\mathbb{E}_{\pi_{b}}[(\mathcal{B^{H}}V)(\tau_{h})^{2}]}}} | {\sup_{h,V}\sqrt{\frac{\mathbb{E}_{\pi_{e}^{\phi}}[(\mathcal{B}^{(\mathcal{S},\mathcal{H}_{T})}V)(s_{h},{\color[rgb]{0,0.62,0}\tau_{[h-T+1:h]}})^{2}]}{\mathbb{E}_{\pi_{b}^{\phi}}[(\mathcal{B^{H}}V)(\tau_{h})^{2}]}}} | ||
Appendix figures & tables1 asset
Supplementary material from the paper’s appendix.
Appendix
Off-Policy Evaluation
Off-policy evaluation estimates a policy’s value from data collected by another policy, using weighting, models, and uncertainty-aware methods.
See all 72 papers