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

• URL: http://arxiv.org/abs/2604.01024v1
• Date: Wed, 01 Apr 2026 15:32:47 GMT
• Title: Model-Based Learning of Near-Optimal Finite-Window Policies in POMDPs
• Abstract summary: We study model-based learning of finite-window policies in partially observable Markov decision processes (POMDPs)<n>A common approach to learning under partial observability is to approximate history dependencies using finite action-observation windows.<n>Once a model of this superstate MDP is available, standard MDP algorithms can be used to compute optimal policies.
• Score: 8.784438985280092
• License: http://creativecommons.org/licenses/by/4.0/
• 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 papers

• Learning Policy from a Single Trajectory in Average-Reward Markov Decision Process [66.74725576150941]
  We study the dynamics of a single trajectory in weakly communicating MDPs.<n>We introduce the first model-free method that requires no prior knowledge of problem-dependent quantities.
  arXiv  Detail & Related papers  (2026-06-15T13:53:19Z)
• Scalable Policy-Based RL Algorithms for POMDPs [6.2229686397601585]
  We consider an approach that solves a Partially Observable Reinforcement Learning (PORL) problem by approximating a POMDP model into a finite-state Markov Decision Process (MDP)<n>We show that the approximation error decreases exponentially with the length of this history.<n>To the best of our knowledge, our finite-time bounds are the first to explicitly quantify the error introduced when applying standard TD learning to a setting where the true dynamics are not Markovian.
  arXiv  Detail & Related papers  (2025-10-08T00:33:38Z)
• Efficient Learning of POMDPs with Known Observation Model in Average-Reward Setting [56.92178753201331]
  We propose the Observation-Aware Spectral (OAS) estimation technique, which enables the POMDP parameters to be learned from samples collected using a belief-based policy. We show the consistency of the OAS procedure, and we prove a regret guarantee of order $mathcalO(sqrtT log(T)$ for the proposed OAS-UCRL algorithm.
  arXiv  Detail & Related papers  (2024-10-02T08:46:34Z)
• Sample Complexity Characterization for Linear Contextual MDPs [67.79455646673762]
  Contextual decision processes (CMDPs) describe a class of reinforcement learning problems in which the transition kernels and reward functions can change over time with different MDPs indexed by a context variable. CMDPs serve as an important framework to model many real-world applications with time-varying environments. We study CMDPs under two linear function approximation models: Model I with context-varying representations and common linear weights for all contexts; and Model II with common representations for all contexts and context-varying linear weights.
  arXiv  Detail & Related papers  (2024-02-05T03:25:04Z)
• Predictable MDP Abstraction for Unsupervised Model-Based RL [93.91375268580806]
  We propose predictable MDP abstraction (PMA) Instead of training a predictive model on the original MDP, we train a model on a transformed MDP with a learned action space. We theoretically analyze PMA and empirically demonstrate that PMA leads to significant improvements over prior unsupervised model-based RL approaches.
  arXiv  Detail & Related papers  (2023-02-08T07:37:51Z)
• A multilevel reinforcement learning framework for PDE based control [0.2538209532048867]
  Reinforcement learning (RL) is a promising method to solve control problems. Model-free RL algorithms are sample inefficient and require thousands if not millions of samples to learn optimal control policies. We propose a multilevel RL framework in order to ease this cost by exploiting sublevel models that correspond to coarser scale discretization.
  arXiv  Detail & Related papers  (2022-10-15T23:52:48Z)
• Optimality Guarantees for Particle Belief Approximation of POMDPs [55.83001584645448]
  Partially observable Markov decision processes (POMDPs) provide a flexible representation for real-world decision and control problems. POMDPs are notoriously difficult to solve, especially when the state and observation spaces are continuous or hybrid. We propose a theory characterizing the approximation error of the particle filtering techniques that these algorithms use.
  arXiv  Detail & Related papers  (2022-10-10T21:11:55Z)
• Bayesian regularization of empirical MDPs [11.3458118258705]
  We take a Bayesian perspective and regularize the objective function of the Markov decision process with prior information. We evaluate our proposed algorithms on synthetic simulations and on real-world search logs of a large scale online shopping store.
  arXiv  Detail & Related papers  (2022-08-03T22:02:50Z)
• PAC Reinforcement Learning for Predictive State Representations [60.00237613646686]
  We study online Reinforcement Learning (RL) in partially observable dynamical systems. We focus on the Predictive State Representations (PSRs) model, which is an expressive model that captures other well-known models. We develop a novel model-based algorithm for PSRs that can learn a near optimal policy in sample complexity scalingly.
  arXiv  Detail & Related papers  (2022-07-12T17:57:17Z)
• Near Optimality of Finite Memory Feedback Policies in Partially Observed Markov Decision Processes [0.0]
  We study a planning problem for POMDPs where the system dynamics and measurement channel model is assumed to be known. We find optimal policies for the approximate belief model under mild non-linear filter stability conditions. We also establish a rate of convergence result which relates the finite window memory size and the approximation error bound.
  arXiv  Detail & Related papers  (2020-10-15T00:37:51Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.