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

arXiv: https://arxiv.org/abs/2604.01024 · HTML: https://mlsanity.com/paper/2604.01024/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 8 of its 21 references that are in the map.
- First posted on arXiv 1 Apr 2026.

## Builds on (most cited first, 8 of 8)

- [Partially Observable Markov Decision Processes in Robotics: A Survey](https://mlsanity.com/paper/2209.10342/) (2022)
- [Approximate information state for approximate planning and reinforcement learning in partially observed systems](https://mlsanity.com/paper/2010.08843/) (2020)
- [Learning in Observable POMDPs, without Computationally Intractable Oracles](https://mlsanity.com/paper/2206.03446/) (2022)
- [Solving POMDPs by Searching the Space of Finite Policies](https://mlsanity.com/paper/1301.6720/) (2013)
- [Near Optimality of Finite Memory Feedback Policies in Partially Observed Markov Decision Processes](https://mlsanity.com/paper/2010.07452/) (2020)
- [Convergence of Finite Memory Q-Learning for POMDPs and Near Optimality of Learned Policies under Filter Stability](https://mlsanity.com/paper/2103.12158/) (2021)
- [Finite-Time Analysis of Natural Actor-Critic for POMDPs](https://mlsanity.com/paper/2202.09753/) (2022)
- [Scalable Policy-Based RL Algorithms for POMDPs](https://mlsanity.com/paper/2510.06540/) (2025)

## Built on by (most cited first, 1 of 1)

- [Independent Learning of Nash Equilibria in Partially Observable Markov Potential Games with Decoupled Dynamics](https://mlsanity.com/paper/2605.06377/) (2026)

## Abstract (arXiv)

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.