Search papers, labs, and topics across Lattice.
This paper analyzes model-based learning of finite-window policies in tabular POMDPs by constructing and learning a superstate MDP. They address the challenge of mismatch between the POMDP sampling process and the superstate MDP target model by leveraging connections between filter stability and concentration inequalities. The result is a tight sample complexity bound for estimating the superstate MDP model from a single trajectory, leading to near-optimal finite-window policies.
Tight sample complexity guarantees for learning near-optimal policies in POMDPs are now possible, even from a single trajectory.
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.
