# Explainable Representation of Finite-Memory Policies for POMDPs using Decision Trees

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 14 of its 43 references that are in the map.
- First posted on arXiv 20 Nov 2024.

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

- [Explanation in Artificial Intelligence: Insights from the Social Sciences](https://mlsanity.com/paper/1706.07269/) (2017)
- [A Survey Of Methods For Explaining Black Box Models](https://mlsanity.com/paper/1802.01933/) (2018)
- [Explainable Reinforcement Learning Through a Causal Lens](https://mlsanity.com/paper/1905.10958/) (2019)
- [Learning Finite State Representations of Recurrent Policy Networks](https://mlsanity.com/paper/1811.12530/) (2018)
- [Enforcing Almost-Sure Reachability in POMDPs](https://mlsanity.com/paper/2007.00085/) (2020)
- [dtControl 2.0: Explainable Strategy Representation via Decision Tree Learning Steered by Experts](https://mlsanity.com/paper/2101.07202/) (2021)
- [Optimal Cost Almost-sure Reachability in POMDPs](https://mlsanity.com/paper/1411.3880/) (2014)
- [dtControl: Decision Tree Learning Algorithms for Controller Representation](https://mlsanity.com/paper/2002.04991/) (2020)
- [Counterexample Explanation by Learning Small Strategies in Markov Decision Processes](https://mlsanity.com/paper/1502.02834/) (2015)
- [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)
- [A Symbolic SAT-based Algorithm for Almost-sure Reachability with Small Strategies in POMDPs](https://mlsanity.com/paper/1511.08456/) (2015)
- [Learning Explainable and Better Performing Representations of POMDP Strategies](https://mlsanity.com/paper/2401.07656/) (2024)
- [Learning-Based Synthesis of Safety Controllers](https://mlsanity.com/paper/1901.06801/) (2019)

## Abstract (arXiv)

Partially Observable Markov Decision Processes (POMDPs) are a fundamental framework for decision-making under uncertainty and partial observability. Since in general optimal policies may require infinite memory, they are hard to implement and often render most problems undecidable. Consequently, finite-memory policies are mostly considered instead. However, the algorithms for computing them are typically very complex, and so are the resulting policies. Facing the need for their explainability, we provide a representation of such policies, both (i) in an interpretable formalism and (ii) typically of smaller size, together yielding higher explainability. To that end, we combine models of Mealy machines and decision trees; the latter describing simple, stationary parts of the policies and the former describing how to switch among them. We design a translation for policies of the finite-state-controller (FSC) form from standard literature and show how our method smoothly generalizes to other variants of finite-memory policies. Further, we identify specific properties of recently used "attractor-based" policies, which allow us to construct yet simpler and smaller representations. Finally, we illustrate the higher explainability in a few case studies.