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

Philip Jordan; Maryam Kamgarpour

cs.LGApr 1, 2026

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

Authors: Philip Jordan, Maryam Kamgarpour

Organizations: SYCAMORE group, Institute of Mechanical Engineering, EPFL Switzerland.

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.

Figures & tables

Fig. 1: Empirical convergence of

V^{m}(\pi^{m})

towards

V^{m}_{\star}

for

m\in\left\{1,\dots,5\right\}

when running Algorithm 1 in the Probe environment.

Explore similar work

Multi-Environment POMDPs with Finite-Horizon Objectives
May 8, 2026Léonard Brice, Filip Cano, Krishnendu Chatterjee +2Belief-Space Planning Markov Models
Institute of Science and Technology Austria
Robustness Analysis of POMDP Policies to Observation Perturbations
Apr 23, 2026Benjamin Kraske, Qi Heng Ho, Federico Rossi +2Partially Observable Markov Decision Processes
University of Colorado Boulder, Boulder, Colorado, USA · Virginia Tech, Blacksburg, Virginia, USA · Jet Propulsion Laboratory, California Institute of Technology, Pasadena, California, USA
Learning Policy from a Single Trajectory in Average-Reward Markov Decision Process
Jun 15, 2026Jongmin Lee, Ernest K. Ryu, Vaneet AggarwalMarkov Decision Processes Reinforcement Learning
Seoul National University · UCLA · Purdue University

May 8, 2026J/K move · Enter open · S save

Multi-Environment POMDPs with Finite-Horizon Objectives

Léonard Brice, Filip Cano, Krishnendu Chatterjee, Thomas A. Henzinger+1

Institute of Science and Technology Austria

Belief-Space Planning Markov Models Partially Observable Markov Decision Processes

Open paper AskPDF arXiv

Partially Observable Markov Decision Processes (POMDPs) are systems in which one agent interacts with a stochastic environment, and receives only partial information about the current state. In a multi-environment POMDP (MEPOMDP), the initial state is unknown, and assumed to be adversarially chosen. In this work we focus on computing the optimal value and policy in MEPOMDPs with finite-horizon objectives. That problem is known to be PSPACE-complete in POMDPs. Our main results are as follows: (1) we establish that it is also PSPACE-complete in the more general setting of MEPOMDPs; (2) we present a practical algorithm and evaluate it on classical benchmarks, significantly outperforming the only previously known algorithm.

Abstract

Explore similar work

Multi-Environment POMDPs with Finite-Horizon Objectives

Robustness Analysis of POMDP Policies to Observation Perturbations

Learning Policy from a Single Trajectory in Average-Reward Markov Decision Process