# Inductive Synthesis of Finite-State Controllers for POMDPs

arXiv: https://arxiv.org/abs/2203.10803 · HTML: https://mlsanity.com/paper/2203.10803/

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 21 Mar 2022.

## Built on by (most cited first, 9 of 9)

- [Learning Logic Specifications for Policy Guidance in POMDPs: an Inductive Logic Programming Approach](https://mlsanity.com/paper/2402.19265/) (2024)
- [Learning Explainable and Better Performing Representations of POMDP Strategies](https://mlsanity.com/paper/2401.07656/) (2024)
- [Sound Heuristic Search Value Iteration for Undiscounted POMDPs with Reachability Objectives](https://mlsanity.com/paper/2406.02871/) (2024)
- [A Finite-State Controller Based Offline Solver for Deterministic POMDPs](https://mlsanity.com/paper/2505.00596/) (2025)
- [Deductive Controller Synthesis for Probabilistic Hyperproperties](https://mlsanity.com/paper/2307.04503/) (2023)
- [Explainable Representation of Finite-Memory Policies for POMDPs using Decision Trees](https://mlsanity.com/paper/2411.13365/) (2024)
- [Scaling Observation-aware Planning in Uncertain Domains](https://mlsanity.com/paper/2605.22364/) (2026)
- [dtControl2+varepsilon: Trading Optimality for Explainability in MDPs via Decision Trees](https://mlsanity.com/paper/2607.25925/) (2026)
- [Revealing After Overwriting: An Exponential POMDP OPE Lower Bound under History-Dependent Logging](https://mlsanity.com/paper/2610.05063/) (2026)

## Abstract (arXiv)

We present a novel learning framework to obtain finite-state controllers (FSCs) for partially observable Markov decision processes and illustrate its applicability for indefinite-horizon specifications. Our framework builds on oracle-guided inductive synthesis to explore a design space compactly representing available FSCs. The inductive synthesis approach consists of two stages: The outer stage determines the design space, i.e., the set of FSC candidates, while the inner stage efficiently explores the design space. This framework is easily generalisable and shows promising results when compared to existing approaches. Experiments indicate that our technique is (i) competitive to state-of-the-art belief-based approaches for indefinite-horizon properties, (ii) yields smaller FSCs than existing methods for several models, and (iii) naturally treats multi-objective specifications.