Finite-Memory Control of POMDPs: Fundamental Limits and Efficient Design
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.
Related
- Simple homotopy types of smooth four-manifolds with finite fundamental group
- Finite Cyclic Fundamental Groups and Exotic Universal Covers from the Cartwright--Steger Surface
- Data-Driven Control in Infinite-Dimensional Spaces: Fundamental Lemma and Applications
- The Complexity of Approximating the Value in Revealing POMDPs with Long-Run Average Objectives
- Jacobian-Free Unrolling: memory efficient unrolled network for 3D SPECT Reconstruction
BibTeX
@misc{kutay2026finitememory,
title = {{Finite-Memory Control of POMDPs: Fundamental Limits and Efficient Design}},
author = {Emrecan Kutay and Atilla Eryilmaz and Ness Shroff},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.03414},
eprint = {2611.03414},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.03414},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Finite-Memory Control of POMDPs: Fundamental Limits and Efficient Design
AU - Emrecan Kutay
AU - Atilla Eryilmaz
AU - Ness Shroff
PY - 2026
DA - 2026/11/02
PB - arXiv
DO - 10.48550/arxiv.2611.03414
UR - https://arxiv.org/abs/2611.03414
AB - 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.
ER -