Model-Based Learning of Near-Optimal Finite-Window Policies in POMDPs
Philip Jordan, Maryam Kamgarpour · 2026
Read Model-Based Learning of Near-Optimal Finite-Window Policies in POMDPs by Philip Jordan, Maryam Kamgarpour (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-01024.txt.
Introduction
Jordan and Kamgarpour study model learning of finite-window policies in POMDPs. Finite windows stand in for endless past links, a finite process from pasts, the superstate MDP. With a superstate model, methods can compute optimal policies, but gauging is hard because runs come from the first process, not the target model. They propose a gauging method for tabular POMDPs and study its sample needs via filter stability and concentration inequalities. From a single run, they get tight bounds, yielding near-optimal finite-window policies with value iteration.
Catalog record
| CREATOR | Philip Jordan, Maryam Kamgarpour |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 44716 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2604.01024
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Model-Based Learning of Near-Optimal Finite-Window Policies in POMDPs Philip Jordan, Maryam Kamgarpour 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. I Introduction Partially observable Markov decision processes (POMDPs) are a fundamental framework for modeling sequential decision-making under uncertainty. While Markov decision processes (MDPs) have become the standard model in reinforcement learning, they rely on the agent having full knowledge of the environment’s state – an idealization that is often unrealistic in practice. POMDPs relax this requirement by allowing the agent to receive only partial or noisy observations of an underlying state, making them applicable to a broader class of problems, such as robotic control [ 13 ] and autonomous driving [ 3 ] under sensor noise, or strategic interaction in games of imperfect information [ 21 ] . Developing principled methods for learning in POMDPs is therefore a problem of fundamental importance. However, it has long been recognized that the greater generality of POMDPs comes with inherent hardness barriers, arising from the fact that optimal policies may depend on the full history of observations. Apart from very specific settings such as linear quadratic Gaussian problems, even the planning task of identifying a near-optimal policy under full knowledge of the model is computationally intractable [ 18 ] . Similar obstacles arise in the learning problem: even ignoring computational constraints, finding a near-optimal policy in a POMDP requires an exponential number of samples [ 12 ] . As a result, a large body of work has explored approximate solution methods that trade optimality for computational tractability or sample-efficiency. In this work, we focus on approximate approaches that are implementable in a computationally efficient manner. One such approach is the use of finite-window techniques, where policies depend only on a fixed-length history window of recent actions and observations [ 15 , 14 , 16 ] . Recently, several works have sought to provide a theoretical explanation for the empirical success of finite-window policies [ 8 , 5 , 6 , 1 ] . A standard approach in these works is to approximate the underlying POMDP by an MDP, referred to as a superstate MDP , whose states correspond to windows of recent history. This reduction from POMDP to superstate MDP provides a principled framework for designing provable algorithms for POMDPs. Under appropriate structural assumptions, one can show that optimal finite-window policies for the superstate MDP are also near-optimal for the respective POMDP [ 9 ] . A central challenge in theoretical analysis of the superstate MDP approach is that, although we can define Markovian transition dynamics over superstates, trajectories can only be sampled from the underlying POMDP, whose dynamics depend on the full history of actions and observations. In this work, we consider a model-based approach for tabular POMDPs, aiming to estimate the reward function and transition kernel of the superstate MDP from trajectories generated by the POMDP. The key difficulty is to learn an optimal policy despite this mismatch between the Markovian structure of the target model and the history-dependent nature of the data-generating process. To the best of our knowledge, how to accomplish this in a sample-efficient manner has not been addressed in prior work. Prior work [ 8 ] analyzes Q-learning in the superstate MDP and derives approximation guarantees based on filter stability; however, the resulting convergence guarantees are only asymptotic. A quasi-polynomial finite-time complexity guarantee for a finite-window approach is established in [ 6 ] , but no explicit sample complexity bound for a fixed window size is provided. More recently, [ 5 , 1 ] study the finite-time convergence of temporal-difference-learning-based policy evaluation in the superstate MDP under linear function approximation. Applied to the tabular setting, the resulting guarantees imply sample complexity bounds for learning an \epsilon -optimal policy on the order of \mathcal{O}(\epsilon^{-4}) , leaving a substantial gap to the tight \mathcal{O}(\epsilon^{-2}) rates known for fully observable MDPs [ 2 ] . Even in the basic tabular case, it is thus not well-understood whether this sample complexity gap is avoidable or the fundamental price of partial observability. Contributions. Motivated by the above, we consider tabular POMDPs, and our contributions are summarized as follows. 1. We propose a method for estimating the model of a superstate MDP based on a trajectory sampled from the underlying POMDP. Transition probabilities and rewards are estimated from the empirical frequencies of the observed finite action-observation windows. 2. Under regularity assumptions on the transition and observation kernels, see Assumptions 1 and 2 , we provide tight sample complexity guarantees for the proposed superstate model estimation, see Proposition 2 . 3. Through value iteration on the estimated model, we derive an efficient algorithm for learning policies with m -step history dependence. In particular, for a trajectory of length \mathcal{O}(\epsilon^{-2}) , the obtained policy is \epsilon -optimal for the POMDP up to an additional error due to finite-window approximation, see Theorem 1 . II Preliminaries Notation. Let \mathbb{N}\coloneqq\left\{1,2,\dots\right\} and \mathbb{N}_{0}\coloneqq\mathbb{N}\cup\left\{0\right\} . For n\in\mathbb{N} , let [n]\coloneqq\left\{1,2,\dots,n\right\} and [n]_{0}\coloneqq[n]\cup\left\{0\right\} . For a,b\in\mathbb{N} with a\leq b , let [a,b]\coloneqq\left\{a,a+1,\dots,b-1,b\right\} . II-A Problem formulation POMDP. We consider tabular infinite-horizon discounted POMDPs defined as a tuple \mathcal{P}=(\mathcal{S},\mathcal{A},\mathcal{O},r,\mathbb{P},\mathbb{O},\mu,\gamma) with finite state space \mathcal{S} of size S\coloneqq|\mathcal{S}| , finite action space \mathcal{A} of size A\coloneqq|\mathcal{A}| , and finite observation space \mathcal{O} of size O\coloneqq|\mathcal{O}| . The reward function is defined as r:\mathcal{O}\times\mathcal{A}\to[-1,1] , and transition probabilities are given by \mathbb{P}(\cdot\mid s,a)\in\Delta(\mathcal{S}) for each s\in\mathcal{S} and a\in\mathcal{A} , where \Delta(\mathcal{S}) denotes the probability simplex over \mathcal{S} . For each s\in\mathcal{S} , observation probabilities are given by \mathbb{O}(\cdot\mid s)\in\Delta(\mathcal{O}) . At time t\in\mathbb{N} , the agent chooses an action a_{t}\in\mathcal{A} . Then, the agent receives a noisy observation o_{t}\sim\mathbb{O}(\cdot\mid s_{t}) , obtains reward r(o_{t},a_{t}) , and the unobserved state transitions to s_{t+1}\sim\mathbb{P}(\cdot\mid s_{t},a_{t}) . The initial state s_{1} is drawn from the distribution \mu\in\Delta(\mathcal{S}) . We consider infinite interactions with rewards discounted by \gamma\in(0,1) . Histories and policies. For n\in\mathbb{N}_{0} , let \mathcal{H}^{n}\coloneqq(\mathcal{A}\times\mathcal{O})^{n} be the set of n -step action-observation histories, where \mathcal{H}^{0} denotes the empty history. Let \mathcal{H}^{\leq m}\coloneqq\bigcup_{n\in[m]_{0}}\mathcal{H}^{n} and \mathcal{H}^{\infty}\coloneqq\bigcup_{m\in\mathbb{N}_{0}}\mathcal{H}^{\leq m} . For t\in\mathbb{N} , let h\in\mathcal{H}^{t} be a history written as h=(a_{i},o_{i})_{i=1}^{t}\in\mathcal{H}^{t} . For k,l\in\mathbb{N} with k\leq l , we define the sub-history h_{k:l}=(a_{i},o_{i})_{i\in[k,l]\cap[1,t]} . In particular, h_{1:t}=h . We denote by |h|=t the length of h . We distinguish between the class