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

arXiv:2604.01024v2 Announce Type: replace 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 iteration, this yields approximately optimal finite-window policies for the POMDP.

Related

• Threshold Structure of Optimal Policies in Restart POMDPs
• Missingness-MDPs: Bridging the Theory of Missing Data and POMDPs
• Computing the Reachability Value of Posterior-Deterministic POMDPs
• Quantum Bayesian Networks Can Speed up Reinforcement Learning in Partially Observable Environments

Source: arXiv cs.LG | 2026-08-26