Finite-Memory Control of POMDPs: Fundamental Limits and Efficient Design
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
| Benchmark | RECAP | Pred- c | Pred- m | Val- m | Rec- m | Dirichlet | Fin-win | Full bel. | |
|---|---|---|---|---|---|---|---|---|---|
| paint | 2 | ||||||||
| marking | 2 | ||||||||
| saci_s12 | 2 | ||||||||
| line4_2goals | 2 | ||||||||
| shuttle | 3 | ||||||||
| network | 3 |
Appendix figures & tables1 asset
Supplementary material from the paper’s appendix.
Appendix
| Benchmark | Brief description | ||||
|---|---|---|---|---|---|
| paint | 4 | 4 | 2 | 2 | Quality-control: Paint, inspect, ship, or reject a part under noisy blemish signal. |
| marking | 9 | 4 | 3 | 2 | Robot uses a movable token to mark its environment and reach a goal under partial observation. |
| saci_s12 | 12 | 6 | 5 | 2 | Aircraft identification: classify friend/enemy from noisy sensor passes. |
| line4_2goals | 4 | 2 | 1 | 2 | 1D two-goal navigation with no informative observations, agent acts from memory alone. |
| shuttle | 8 | 3 | 5 | 3 | Chrisman docking: shuttle navigation with aliased station/docking observations. |
| network | 7 | 4 | 2 | 3 | Littman network: regulate server load against crash risk with noisy up-down observations. |
Partially Observable Markov Decision Processes
Partially Observable Markov Decision Processes study sequential decisions when agents must act from incomplete, noisy observations of hidden states.
See all 97 papers