# Learning Explainable and Better Performing Representations of POMDP Strategies

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 36 references that are in the map.
- First posted on arXiv 15 Jan 2024.

## Builds on (most cited first, 15 of 15)

- [The Probabilistic Model Checker Storm](https://mlsanity.com/paper/2002.07080/) (2020)
- [Solving POMDPs by Searching the Space of Finite Policies](https://mlsanity.com/paper/1301.6720/) (2013)
- [Robust Finite-State Controllers for Uncertain POMDPs](https://mlsanity.com/paper/2009.11459/) (2020)
- [What is Decidable about Partially Observable Markov Decision Processes with ω-Regular Objectives](https://mlsanity.com/paper/1309.2802/) (2013)
- [dtControl 2.0: Explainable Strategy Representation via Decision Tree Learning Steered by Experts](https://mlsanity.com/paper/2101.07202/) (2021)
- [Solving POMDPs by Searching in Policy Space](https://mlsanity.com/paper/1301.7380/) (2013)
- [dtControl: Decision Tree Learning Algorithms for Controller Representation](https://mlsanity.com/paper/2002.04991/) (2020)
- [Safe Policy Improvement for POMDPs via Finite-State Controllers](https://mlsanity.com/paper/2301.04939/) (2023)
- [Inductive Synthesis of Finite-State Controllers for POMDPs](https://mlsanity.com/paper/2203.10803/) (2022)
- [Verification of indefinite-horizon POMDPs](https://mlsanity.com/paper/2007.00102/) (2020)
- [Counterexample-Guided Strategy Improvement for POMDPs Using Recurrent Neural Networks](https://mlsanity.com/paper/1903.08428/) (2019)
- [Gradient-Descent for Randomized Controllers under Partial Observability](https://mlsanity.com/paper/2111.04407/) (2021)
- [Under-Approximating Expected Total Rewards in POMDPs](https://mlsanity.com/paper/2201.08772/) (2022)
- [Search and Explore: Symbiotic Policy Synthesis in POMDPs](https://mlsanity.com/paper/2305.14149/) (2023)
- [An Automaton Learning Approach to Solving Safety Games over Infinite Graphs](https://mlsanity.com/paper/1601.01660/) (2016)

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

- [Finite-State Controllers for (Hidden-Model) POMDPs using Deep Reinforcement Learning](https://mlsanity.com/paper/2602.08734/) (2026)
- [Explainable Representation of Finite-Memory Policies for POMDPs using Decision Trees](https://mlsanity.com/paper/2411.13365/) (2024)
- [Error-awareness Accelerates Active Automata Learning](https://mlsanity.com/paper/2602.21674/) (2026)
- [Synthesizing POMDP Policies: Sampling Meets Model-checking via Learning](https://mlsanity.com/paper/2605.14440/) (2026)

## Abstract (arXiv)

Strategies for partially observable Markov decision processes (POMDP) typically require memory. One way to represent this memory is via automata. We present a method to learn an automaton representation of a strategy using a modification of the L*-algorithm. Compared to the tabular representation of a strategy, the resulting automaton is dramatically smaller and thus also more explainable. Moreover, in the learning process, our heuristics may even improve the strategy's performance. In contrast to approaches that synthesize an automaton directly from the POMDP thereby solving it, our approach is incomparably more scalable.