Finite State Controllers for Partially Observable Planning

You are reading version 1 of this direction, frozen 2026-10-04. The latest version is version 2.

Version 1 of 2135 papers178 conceptsfrozen 2026-10-04

In a perfect world, an agent knows exactly where it is. In the real world, sensors are noisy, and environments are hidden. To act optimally in these Partially Observable Markov Decision Processes (POMDPs), an agent technically needs to remember its entire history of actions and observations. This "belief state"—a probability distribution over all possible locations—is mathematically elegant but computationally ruinous. As the history grows, the complexity of tracking it explodes.

The research direction of Finite-State Controllers (FSCs) offers a way out. Instead of tracking a continuous, high-dimensional belief state, we represent the agent's policy as a small, discrete graph. This shift transforms the problem from "how do I calculate what I know?" to "how do I transition between a few useful internal states?"

The Automaton as Memory

The core intuition behind an FSC is that an agent doesn't need to remember everything; it only needs to remember what is relevant for its next decision. Eric A. Hansen pioneered this approach in An Improved Policy Iteration Algorithm for Partially Observable MDPs, demonstrating that representing policies as finite-state controllers makes them 40–50 times faster to execute than standard value iteration.

In this framework, a policy is a directed graph:

  • Nodes represent internal memory states, each associated with a specific action.
  • Edges represent transitions between these memory states, triggered by new observations.

By using these controllers, an agent avoids expensive Bayesian updates at runtime. It simply looks at its current node, takes the action, receives an observation, and follows the corresponding edge to the next node. This makes FSCs ideal for hardware with limited power, as noted by Murat Cubuktepe and Nils Jansen in their work on Robust Finite-State Controllers for Uncertain POMDPs.

Breaking the Complexity Barrier

Standard POMDP problems are notoriously difficult—often PSPACE-complete or even undecidable for certain infinite-horizon objectives. However, by restricting the search space to strategies with a fixed amount of memory, researchers like Laurent Doyen and Moshe Y. Vardi have shown that we can settle the complexity of these games, providing tight bounds for what is achievable with Finite-Memory Strategies.

This "memory-bounded" framing allows for the use of powerful symbolic tools. Krishnendu Chatterjee and Martin Chmelík developed Symbolic SAT-Based Algorithms that search for the smallest possible controller capable of reaching a goal. By parameterizing the memory size, these solvers can identify the minimal amount of information an agent must retain to guarantee success, turning an intractable search into a solvable Boolean satisfiability problem.

Coordination Without Communication

The power of FSCs is most evident in Decentralized POMDPs (Dec-POMDPs), where multiple agents must coordinate without knowing each other's observations. Exact solutions for Dec-POMDPs scale double-exponentially, making them practically impossible for large tasks.

Daniel S. Bernstein and Shlomo Zilberstein addressed this in Bounded Policy Iteration for Decentralized POMDPs by using stochastic FSCs. Because the controllers are fixed-size, the agents can improve their local strategies iteratively without the "policy tree" explosion that usually plagues multi-agent planning. This approach was further scaled by Christopher Amato and George Konidaris, who used FSCs to coordinate teams of robots performing complex macro-actions like navigating rooms or managing tasks.

Bounded Rationality and Interpretability

Beyond efficiency, FSCs offer a more realistic model of intelligence. Joseph Halpern and Rafael Pass argue in I'm Doing as Well as I Can that human "irrationality" is often just the optimal behavior for an agent with a limited number of internal states. By modeling agents as Rational Finite Automata, we can explain cognitive biases as necessary trade-offs for saving memory.

Finally, FSCs provide a level of transparency that neural networks lack. As Vincent Thomas and Francis Colas highlight in their work on Monte-Carlo Search for Dec-POMDPs, these graph-based structures allow practitioners to trace the specific reasoning behind an agent's actions. We can see exactly which observation triggered a state change, making the agent’s "thought process" human-interpretable and verifiable.

Papers in this version

Showing 60 of 135 papers.

History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 128 papers
  2. Version 1 · 2026-10-04 · 135 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_finite_state_controller_policy_represent_38525af9,
  title = {finite-state controller policy representation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/finite-state-controller-policy-representation/rdr_38525af97c314a39b7fb25e2b517062b},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_finite_state_controllers_for_partially_o_38525af9_v1,
  title = {Finite State Controllers for Partially Observable Planning},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/finite-state-controllers-for-partially-observable-planning/rdr_38525af97c314a39b7fb25e2b517062b/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}