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

Optimal control of partially observable Markov decision processes (POMDPs), in general, requires a complete history. Traditionally, a belief state is used as a sufficient statistic to control POMDPs. However, being defined over a continuous space, its full representation is impossible with a finite-memory controller. 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 to design representative memory states. We prove upper bounds on the optimality gap of any RECAP codebook, and use the resulting components together with the converse to define the codebook objective. Experiments on 11 POMDP benchmarks demonstrate that RECAP improves over finite-memory representation baselines under the same memory budget.