Finite-State Controllers of POMDPs using Parameter Synthesis

Sebastian Junges, Nils Jansen, Ralf Wimmer, Tim Quatmann, Leonore Winterer, Joost-Pieter Katoen, Bernd BeckerUAI 2018 · OpenReview

Abstract

Solving Partially Observable Markov Decision Processes (POMDPs) is a fundamental challenge in autonomous decision-making, often hindered by the uncountably infinite nature of belief states. This paper introduces a novel transformation that maps the search for a POMDP strategy onto a parameter synthesis problem for parametric Markov chains (pMCs). By leveraging mature formal verification tools like Storm, the authors demonstrate the ability to synthesize memory-efficient Finite-State Controllers (FSCs) that are provably correct and competitive with specialized POMDP solvers.

Introduction

In real-world scenarios such as robotics or network protocol design, agents must make decisions based on incomplete information. These scenarios are typically modeled as POMDPs. However, solving POMDPs is notoriously difficult because optimal decisions often depend on the entire history of observations. While standard approaches track a "belief state"—a probability distribution over all possible physical states—this space is uncountably infinite, making exact solutions undecidable for infinite-horizon goals.

A practical alternative is the use of Finite-State Controllers (FSCs), which utilize a small amount of internal memory to mimic history-dependence. Despite their utility, finding the optimal parameters for these controllers—such as which action to take or how to update memory—is an NP-hard problem. This research addresses the gap in efficiently synthesizing FSCs for complex specifications, such as reaching a goal while avoiding obstacles.

Methodology

The core contribution of this work is a formal bridge between POMDP planning and parametric model checking. This is achieved through a two-step process:

1. The Transformation

The authors prove that a POMDP combined with an FSC of size $k$ is structurally equivalent to a parametric Markov Chain (pMC). In this induced pMC, transitions are not fixed constants but variables (parameters) representing the agent's choices.

The transformation process from a POMDP and a Finite-State Controller (FSC) to an induced parametric Markov Chain.

2. Parameter Synthesis

Instead of traditional POMDP algorithms, the approach utilizes pMC tools to find parameter values that satisfy a given logical specification (e.g., the probability of success exceeding a threshold). The authors implemented this in the Storm model checker, employing several algorithmic techniques:

  • Particle Swarm Optimization (PSO): A heuristic search for rapid parameter discovery.
  • QCQP (Quadratically-Constrained Quadratic Programming): A mathematical optimization approach for rigorous synthesis.
  • Parameter Lifting & SMT: Techniques used to establish impossibility results, proving that no controller exists for a certain threshold.
Parametric transition structure in the synthesized model showing parameters p and q1.

Experimental Evaluation

The method was evaluated on a diverse set of POMDP benchmarks, including network routing protocols (NRP), gridworld navigation (Grid & Slippery), large-scale network models (Netw), and privacy protocols (Crypt). These benchmarks ranged from small models (16 states) to complex systems with nearly 5,000 states, testing the scalability and robustness of the parameter synthesis approach.

Key Insights and Results

The results demonstrate that the search for a randomized strategy in a POMDP is mathematically identical to finding a valid instantiation of a pMC. This allows the POMDP community to inherit decades of progress in formal verification. Key findings include:

  • Efficiency and Scalability: The tool synthesized nearly optimal controllers for benchmarks with thousands of states within seconds, handling pMCs with hundreds of parameters.
  • Memory vs. Randomization: Small FSCs (e.g., $k=2$ or $k=4$) are often sufficient for near-optimal performance. Furthermore, randomized controllers can often outperform larger deterministic ones, as the probability parameters can "smooth out" the lack of perfect information.
  • Provable Optimality: Unlike many solvers that only look for good strategies, this method can use SMT solvers to prove that specific performance thresholds are impossible for a given memory size, effectively closing the gap on several problems.

Conclusion and Future Work

While the approach is highly effective, it faces a "parameter explosion" as the memory bound $k$ increases, leading to a more complex optimization landscape. Additionally, the resulting rational functions can become extremely large for complex models. Future research will explore applying these techniques to permissive schedulers and real-world robotics scenarios where "correct-by-construction" guarantees are essential.

Summary updated

BibTeX
@inproceedings{junges2018finite,
  author = {Sebastian Junges and Nils Jansen and Ralf Wimmer and Tim Quatmann and Leonore Winterer and Joost-Pieter Katoen and Bernd Becker},
  title = {{Finite-State Controllers of POMDPs using Parameter Synthesis}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2018},
  url = {https://openreview.net/forum?id=rfVPAInnW5},
}
Figure