Finite State Controllers for Bounded Memory Policies

194 concepts125 papers1 proposal

When an agent operates in the real world, it rarely has a perfect view of its environment. In these Partially Observable Markov Decision Processes (POMDPs), a robot or autonomous system faces a fundamental challenge: immediate observations are often ambiguous. Two completely different rooms might look identical to a vacuum robot's sensors, a phenomenon known as perceptual aliasing. To make the correct decision, the agent must rely on memory.

The naive approach to memory is to track the entire history of actions and observations. However, this history grows linearly with time, causing the space of possible policies to explode exponentially as a massive decision tree. An alternative is to maintain a "belief state"—a continuous probability distribution over all possible world states. While mathematically elegant, tracking and optimizing over an uncountable set of probabilities quickly becomes computationally intractable, particularly in multi-agent systems or resource-constrained hardware.

Finite-State Controllers (FSCs) offer a powerful escape route from this complexity. Instead of tracking an infinite history or a continuous belief space, an FSC restricts the agent's memory to a compact, fixed-size automaton. By structuring memory as a discrete directed graph, FSCs allow agents to achieve near-optimal performance with strict, predictable memory bounds.


The Anatomy of a Finite-State Controller Policy

An FSC represents an agent's policy as a small mental state machine. It consists of a predefined number of internal memory nodes (control states). At any given moment, the agent resides in one of these internal states.

The decision-making loop operates through two simple mappings:

  1. Action Selection: The agent selects an action based on its current internal state. In more expressive formulations known as Mealy machines, the action is determined by a combination of both the current internal state and the most recent external observation, as utilized by Miao Liu et al. and Christopher Amato.
  2. Internal State Transition: When the agent receives a new observation from the environment, it transitions to a new internal memory state.
    [ Observation ] ───┐
                       ▼
  ┌────────────────────────────────────────┐
  │        Finite-State Controller         │
  │                                        │
  │   Current Internal State (Node)        │
  │               │                        │
  │               ▼                        │
  │       Next Internal State              │
  └────────────────────────────────────────┘
                       │
                       ▼
                   [ Action ]

By replacing full history tracking with a fixed-size automaton, the agent compresses its entire past into a single discrete variable. As shown by Andrew Clark et al., this structural constraint transforms computationally undecidable or intractable history-dependent planning problems into manageable optimization tasks.


Why it Works: Collapsing Redundant Histories

The core intuition behind the success of FSCs is that an agent does not need to remember everything to act optimally. Many distinct sequences of historical events lead to the exact same future action.

Consider a robot navigating a maze to find an exit. It does not need to remember the precise sequence of every turn it took over the last hour. It only needs to know a high-level abstract state, such as "I am currently searching for the first red door" or "I have already passed the red door and am looking for the exit."

FSCs exploit this redundancy by collapsing long, distinct observation histories into shared internal nodes. As demonstrated by Alex Schutz et al. in A Finite-State Controller Based Offline Solver for Deterministic POMDPs, collapsing redundant paths into shared nodes can compress the policy representation by over 300 times compared to standard decision trees.

Remarkably, these controllers do not need to be large to be effective. Work by Roman Andriushchenko et al. shows that deterministic FSCs can achieve near-optimal performance using extremely small structures—often requiring fewer than five nodes. By allocating memory states locally only where observations are inconsistent or ambiguous, the agent avoids a global state-space explosion.


Synthesizing and Optimizing Bounded Policies

How do we find the optimal transitions and actions for a fixed-size controller? Because the transitions depend on discrete internal states, the optimization landscape is non-convex and filled with local optima. Researchers have developed several distinct paradigms to solve this:

Nonlinear and Global Optimization

In Solving POMDPs Using Quadratically Constrained Linear Programs, Christopher Amato et al. formulated the policy search as a Quadratically Constrained Linear Program (QCLP). This approach treats the action and transition probabilities as continuous variables within a fixed-size controller, allowing global optimization techniques to find high-quality policies that operate within a constant, minimal memory footprint.

Bounded Policy Iteration

Instead of fixing the size of the controller permanently, algorithms like Bounded Policy Iteration, introduced by Pascal Poupart et al., start with a small controller and expand it incrementally. The policy grows in complexity only when the algorithm detects that adding a new memory state will strictly improve the agent's expected reward, keeping the search space tightly bounded.

Symbolic and SAT-Based Synthesis

When an agent must satisfy strict safety or reachability guarantees (e.g., reaching a goal with 100% certainty), exact verification is required. Krishnendu Chatterjee et al. developed a symbolic SAT-based algorithm for almost-sure reachability. By parameterizing the memory size, their solver systematically searches for the minimal number of internal states an agent must retain to guarantee success, treating internal memory and external sensor precision as interchangeable resources (Krishnendu Chatterjee et al.).


Scaling to Multi-Agent Coordination and Generalized Planning

The compact nature of FSCs makes them uniquely suited for two of the most difficult domains in artificial intelligence: decentralized multi-agent systems and generalized planning.

Multi-Agent Coordination (Dec-POMDPs)

In decentralized environments, multiple agents must coordinate to achieve a shared goal without real-time communication. Exact dynamic programming in this setting suffers from a catastrophic double-exponential memory growth.

To bypass this barrier, Daniel S. Bernstein et al. introduced a framework where each agent represents its local policy as a stochastic FSC. By pairing these individual controllers with a shared "correlation device" (a source of shared randomness), the authors proved that teams of agents could achieve monotonic value improvement while keeping memory usage strictly bounded. Similarly, Feng Wu et al. demonstrated that reusing a fixed set of sub-policies as building blocks prevents exponential expansion over long planning horizons.

Generalized Planning

Generalized planning aims to discover a single policy that can solve an entire class of problems, regardless of their size or specific objects—such as a robot learning a rule to clean a room whether it is 5 meters or 50 meters wide.

Blai Bonet et al. demonstrated that generalized planning logic can be formally extended using finite-state controllers. By representing the policy as a graph where edges correspond to qualitative features and actions (Blai Bonet et al.), the agent executes complex control flows, including loops and conditional branching, with constant memory overhead.


Conclusion

Finite-state controllers bridge the gap between the theoretical necessity of memory in uncertain environments and the practical constraints of physical hardware. By shifting the planning paradigm from expanding infinite history trees to optimizing compact, recurrent state graphs, FSCs provide an interpretable, verifiable, and highly scalable framework for intelligent decision-making.

Key Foundational Work

Acting Optimally in Partially Observable Stochastic Domains (1994) — contributed 2 concept elements to this direction.
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 2, frozen text):

@misc{lacuna_finite_state_controller_policy_represent_38525af9_v2,
  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/v/2},
  note = {Version 2, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake