[2604.01024] Model-Based Learning of Near-Optimal Finite-Window Policies in POMDPs

Computer Science > Machine Learning arXiv:2604.01024 (cs) [Submitted on 1 Apr 2026] Title:Model-Based Learning of Near-Optimal Finite-Window Policies in POMDPs Authors:Philip Jordan, Maryam Kamgarpour View a PDF of the paper titled Model-Based Learning of Near-Optimal Finite-Window Policies in POMDPs, by Philip Jordan and 1 other authors View PDF HTML (experimental) Abstract:We study model-based learning of finite-window policies in tabular partially observable Markov decision processes (POMDPs). A common approach to learning under partial observability is to approximate unbounded history dependencies using finite action-observation windows. This induces a finite-state Markov decision process (MDP) over histories, referred to as the superstate MDP. Once a model of this superstate MDP is available, standard MDP algorithms can be used to compute optimal policies, motivating the need for sample-efficient model estimation. Estimating the superstate MDP model is challenging because trajectories are generated by interaction with the original POMDP, creating a mismatch between the sampling process and target model. We propose a model estimation procedure for tabular POMDPs and analyze its sample complexity. Our analysis exploits a connection between filter stability and concentration inequalities for weakly dependent random variables. As a result, we obtain tight sample complexity guarantees for estimating the superstate MDP model from a single trajectory. Combined with value ite...