cs.LGNov 2, 2026

Finite-Memory Control of POMDPs: Fundamental Limits and Efficient Design

Authors: Emrecan Kutay, Atilla Eryilmaz, Ness Shroff

Organizations: Department of Electrical and Computer Engineering The Ohio State University

Abstract

Optimal control of partially observable Markov decision processes (POMDPs), in general, requires a complete history. The belief state, a distribution over hidden states, summarizes this history and provides the classical sufficient statistic to control POMDPs. However, the continuous nature of the belief space generally prevents a finite-memory controller from maintaining it exactly. This raises the question we address in this work: what must the available finite memory preserve to achieve near-optimal control performance? We study this question through an information-theoretic converse that gives a fundamental lower bound on the loss of any finite-memory controller. The analysis introduces the concept of a decision witness that characterizes belief states whose confusion would lead to unavoidable loss. Motivated by this bound, we propose RECAP, a constructive quantization method for designing representative memory states. We prove an upper bound on the optimality gap of any RECAP codebook and use the components of this bound together with the converse analysis to define the codebook objective. Experiments on 11 POMDP benchmarks demonstrate that RECAP improves over finite-memory representation baselines under the same memory budget.

Figures & tables

Appendix figures & tables1 asset

Supplementary material from the paper’s appendix.

Appendix

Explore similar work

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

    Apr 1, 2026Philip Jordan, Maryam KamgarpourPartially Observable Markov Decision ProcessesPolicy Learning

  2. Finite-Time Guarantees for Constrained Reinforcement Learning under Partial Observability

    Oct 15, 2026Valentina Zaccaria, Philip Jordan, Tingting Ni +2Primal-Dual RLReinforcement Learning

  3. Multi-Environment POMDPs with Finite-Horizon Objectives

    May 8, 2026Léonard Brice, Filip Cano, Krishnendu Chatterjee +2Belief-Space PlanningMarkov Models