# Post-Hoc Interpretation of POMDP Policies (extended version)

Geoffrey Laforest, Olivier Buffet, Alexandre Niveau, Bruno Zanuttini

<figure><img src="image_1.png" /></figure>

## To cite this version:

Geoffrey Laforest, Olivier Buffet, Alexandre Niveau, Bruno Zanuttini. Post-Hoc Interpretation of POMDP Policies (extended version). Université de Caen Normandie. 2025. hal-05180842

HAL Id: hal-05180842

https://hal.science/hal-05180842v1

Submitted on 4 Aug 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.
# Post-Hoc Interpretation of POMDP Policies
(extended version)*

Geoffrey Laforest

Olivier Buffet

Alexandre Niveau

Bruno Zanuttini

August 4, 2025

## Abstract

Policies for partially observable Markov decision processes are rich objects, prescribing actions to take depending on the whole history of observations and actions. Typical representations of such policies are by hyperplanes in the space of belief states, or by finite-state controllers, which are arguably not easy to interpret.

We propose to redescribe policies into mappings defined on features of the current belief state, built in a systematic manner from state features. Such a mapping can in turn be represented by an intelligible object, like a decision tree, thereby providing an interpretable representation of the policy as a whole. We moreover show how our approach allows to explain the decision taken by an agent at each step of an interaction with the environment. This provides an end-to-end process, starting from a policy computed by any solver, and ending with an explanation of each decision made at execution time. We formally define our approach, investigate related computational problems, and report on experiments on several families of problems.

## 1 Introduction

We are interested in the representation of policies of actions for partially observable Markov decision processes (POMDPs), which are stochastic decision processes with partially observable states. At execution time, a policy prescribes actions to take depending on the whole history of actions and observations. Standard representations of such policies are by finite-state controllers (with states/nodes labelled with actions to take, and transitions fired by observations), and by sets of α-vectors, which are hyperplanes in the belief space, that

<footnote>*This paper is an extended version of a paper published at ECAI 2025 (Laforest et al., 2025). The extension consists of the appendix, providing formal proofs of claims, details about the benchmarks used in the experiments, and additional experimental results.</footnote>
is, the space of probability distributions over the state space (which represent
possible beliefs of the agent over the current state).

Arguably, such representations lack interpretability: states/nodes in finite-
state controllers are simply atoms, and α-vectors are high-dimensional vectors
of real values. Hence we propose a new representation of policies for POMDPs,
in which a set of epistemic features is built in a systematic manner from a given
set of state features, and policies are represented by interpretable objects (e.g.,
matrices of weights, decision trees) defined on the embedding of the belief space
onto these epistemic features.

In a nutshell, an epistemic feature is a propositional formula over the state
features (e.g., a small disjunction or conjunction), and its value in a belief state
is the probability that it is satisfied by a state drawn from it. This allows us
to propose representations of policies over features like “The degree of belief
that the goal is at (0,0)” which, we think, makes them more interpretable. Our
approach is post-hoc, that is, it starts from any (non-interpretable) policy and
redescribes it into a more interpretable one.

After some related work and background (§2-3), we present our approach in
details (§4-6). Then we experimentally compare our representations to finite-
state controllers in terms of size and computational time (§7). Finally, we
illustrate how these representations help provide interpretations of the behavior
of the policy (§8) and conclude (§9).

## 2 Related work

There is a growing interest in explainable and interpretable machine learning,
which is motivated by ethical and legal concerns, and the need to understand al-
gorithmic predictions to ensure decisions based on machine learning are safe and
reliable (Gilpin et al., 2018; Doshi-Velez and Kim, 2018; Linardatos et al., 2021).
In this work, we focus on interpretability, i.e., the degree to which a human can
understand the model’s results and the causes of its decisions. This often im-
plies that a user can grasp how inputs are processed and mapped to the outputs
in a human-comprehensible format (Gao and Guan, 2023). Closely related no-
tions often involve deriving agent behaviors that are more easily interpretable
by external observers. For instance, behaviors may be considered legible if they
facilitate guessing the agent’s true objective, explainable if the agent’s actions
clearly align with some objective, or predictable if future actions can be easily
anticipated (Chakraborti et al., 2019). Observer-aware MDPs provide a formal
framework to address these challenges within stochastic environments (Miura
and Zilberstein, 2021).

Interpretability usually takes two roads (Du et al., 2020). Interpretability
*by design* means that the models learnt or computed are taken from a language
deemed interpretable *per se*. In planning, examples are representations by easy-
to-understand trees (Topin et al., 2021) or expressed with symbolic features
(Huang et al., 2020; Grandien et al., 2024), sometimes both (Costa et al., 2024;
Kohler et al., 2024). In (Huang et al., 2020), a continuous state-action space is
discretized, and the policy is represented with if-else fuzzy rules.

Now *post-hoc* interpretability, which is the setting of our work, means a model is redescribed, after learning or computation, into an interpretable language. In the setting of MDPs and reinforcement learning, examples build on measuring the importance of reachable states (Huber et al., 2021; Gajcin et al., 2021) or actions taken under the given policy. For instance, in (Saulières et al., 2024), the importance of actions is assessed regarding their role in satisfying a predicate of interest at each time-step until the end of the episode. Another approach consists in targeting a simpler language (Bewley et al., 2021). As in our framework, the authors of (Wang et al., 2016) use explainable features of the belief state, but their goal is to communicate a robot's beliefs rather than to explain its policy; moreover, their framework requires handcrafted features to be provided. Finally, in (Russell and Santos, 2019), a decision tree is used to assess feature importance, but the focus is primarily on explaining the reward, with policy explanation being only a byproduct. In contrast, our objective is to directly explain the policy.

In (Nashed et al., 2023), the authors propose to represent an MDP as a layered causal graph, which allows identifying the variables responsible for an action or decision. Our work is complementary to theirs, since we focus more on making a policy interpretable while they try to justify the decisions.

In the POMDP setting, one can use symbolic features based on a logical language (Meli et al., 2024). The authors use handcrafted features to describe interesting traces of a given policy, then use these descriptions as heuristics for solvers. Hence, despite many similarities with our work, the focus there is on computing interpretable heuristics.

Different from, but related to, the degree of interpretability of a (representation of a) policy is its size. Policies computed by search, as with SARSOP, are in practice represented by high-dimensional vectors with many nonzero coefficients. For this reason, symbolic solvers, such as Symbolic Perseus (Poupart, 2005), have been developed to exploit factored representations. Another representation of policies is by a finite-state controller (FSC). In (Grześ et al., 2015), the authors propose algorithms for computing such FSCs from policies given by oracles. Their focus is on (post-hoc) compression of policies, which can be seen as a manner of enhancing interpretability. We experimentally compare our approach with theirs in §7. Another work (Azeem et al., 2024) represents transitions between FSC nodes with decision trees, but without questioning the FSC representation itself, contrary to us.

Another line of work leverages recurrent neural networks for their ability to encode the history (Bakker, 2001). They are often integrated in another architecture to make predictions, such as Deep Q-Networks (Mnih et al., 2015). Carefully designed and tuned, they can be a strong baseline for many POMDPs (Ni et al., 2022). A somewhat compact representation of a policy can also be obtained by embedding it into an RKHS and truncating the embedding basis up to a certain number (Mazoure et al., 2022). This results in a more compact but approximated policy.
Finally, close to our work is the work on knowledge-based programs (Lang and Zanuttini, 2015; Zanuttini et al., 2020), which are representations of policies as programs branching on epistemic features (similar to ours), possibly yielding very compact representations. Our work can indeed be seen as using specific forms of KBPs as a target language for redescribing policies.

## 3 Background

Given a finite set $S$, we write $\mathcal{P}(S)$ for the set of all subsets of $S$, and $\Delta(S)$ for the probability simplex over $S$. Given a distribution $\delta$, we write $\mathbf{x} \sim \delta$ to denote random variable $\mathbf{x}$ being sampled from $\delta$, and $x \in \delta$ to mean that value $x$ is in the support of $\delta$.

A Partially Observable Markov Decision Process (POMDP) (Kaelbling et al., 1998) is a tuple $(S, \mathcal{A}, \mathcal{O}, T, Z, R, b_0, \gamma)$, where $S, \mathcal{A}, \mathcal{O}$ are finite sets of states, actions, and observations, resp.; for all $s \in S$ and $a \in \mathcal{A}$, $T_{s,a} \in \Delta(S)$ is the distribution of next states when action $a$ is taken in state $s$; for all $s \in S$, $a \in \mathcal{A}$ and $s' \in T_{s,a}$, $Z_{s,a,s'} \in \Delta(\mathcal{O})$ is the distribution of observations upon transition $(s, a, s')$, and $R_{s,a,s'} \in \mathbb{R}$ the reward received for this transition; $b_0 \in \Delta(S)$ is an initial belief state; and $\gamma \in [0, 1)$ is a discount factor.

Given a POMDP, a history is a finite sequence of actions and observations of the form $h := \langle a_0, o_0, \dots, a_t, o_t \rangle$. We write $\mathcal{H}$ for the set of all histories. A (nondeterministic) policy $\text{pol}: \mathcal{H} \to \mathcal{P}(\mathcal{A})$ maps histories to sets of actions. An interaction of (an agent executing) a policy $\text{pol}$ with a POMDP $(S, \mathcal{A}, \mathcal{O}, T, Z, R, b_0, \gamma)$ proceeds as follows: a state $s_0$ is sampled from $b_0$ and the initial history is $h_0 := \langle \rangle$; then at each time-step $t$, the agent nondeterministically chooses an action $a_t$ from $\text{pol}(h_t)$, state $s_{t+1}$ is sampled from $T_{s_t, a_t}$, observation $o_t$ is sampled from $Z_{s_t, a_t, s_{t+1}}$, reward $r_t$ is given by $R_{s_t, a_t, s_{t+1}}$, and the new history is $h_{t+1} = h_t \cdot \langle a_t, o_t \rangle$

A history $h = \langle a_0, o_0, \dots, a_t, o_t \rangle$ therefore induces a probability distribution $\text{bs}(h)$ over $S$, called a belief state: $\text{bs}(h)(s)$ is the probability that $s_{t+1}$ is $s$ over all interactions with history $h_t = h$. We write $\mathcal{B}$ for the set of all belief states ($\mathcal{B} := \Delta(S)$). The belief state $\text{bs}(h)$ for $h := \langle a_0, o_0, \dots, a_t, o_t \rangle$ can be computed through Bayesian update: $\text{bs}(\langle \rangle) = b_0$, and for $u \le t$, writing $b_u$ for $\text{bs}(\langle a_0, o_0, \dots, a_{u-1}, o_{u-1} \rangle)$,

$$b_{u+1}(s_{u+1}) := \eta \sum_{s_u \in S} Z_{s_u, a_u, s_{u+1}}(o_u) T_{s_u, a_u}(s_{u+1}) b_u(s_u),$$

where $\eta$ is a normalizing constant. We also write $b_{u+1}$ as $b_u \oplus \langle a_u, o_u \rangle$, the update of belief state $b_u$ after executing $a_u$ and observing $o_u$. The set $\text{Reach}(\text{pol}, b_0)$ of belief states reachable by $\text{pol}$ is the set of all belief states $b$ such that there is an interaction of $\text{pol}$ with the POMDP satisfying $b = \text{bs}(h_t)$ for some $t$.

A (nondeterministic, partial) belief-based policy $p: B \to \mathcal{P}(\mathcal{A})$ maps a set $B \subseteq \mathcal{B}$ to sets of actions, and induces the policy $\text{pol}(p): \mathcal{H} \to \mathcal{P}(\mathcal{A})$ via $\text{pol}(p)(h) := p(\text{bs}(h))$. In this paper we will only consider belief-based policies. This is however without a great loss of generality, since it is well-known
that belief states are a *sufficient statistic* for acting optimally: there is always at least one optimal policy which is (induced by) a belief-based one (Kaelbling et al., 1998, §3).<fnref n="1" />

**Example 1.** As a running example, we use a POMDP containing 4 states, written $s_{00}, s_{01}, s_{10}, s_{11}$ (read intuitively as $s_{xy}$). There are three actions: $check_=$ does not change the state but (deterministically) produces observation **true** (resp. **false**) when taken in state $s_{xy}$ with $x = y$ (resp. $x \neq y$); $switch_x$ deterministically maps each $s_{xy}$ to $s_{(1-x)y}$, yielding observation **void**; $noop$ does not change the state and yields observation **void**. Finally, $b_0$ is the uniform distribution $b^{\text{unif}}$ over $S$, and $R_{:,s'}$ is 1 for $s' \in \{s_{00}, s_{11}\}$, 0 otherwise.

Then $h^= := \langle check_=, false, switch_x, void \rangle$ is a history, inducing the belief state $b^= := bs(h^=)$, which assigns probability $\frac{1}{2}$ to $s_{00}, s_{11}$. Let moreover $b^\neq$ be the belief state assigning $\frac{1}{2}$ to $s_{01}, s_{10}$, and $p$ be defined by $p(b^{\text{unif}}) := \{check_=, noop\}, p(b^\neq) := \{switch_x\}$, and $p(b^=) = \{check_=, noop\}$.<fnref n="2" /> Then $p$ is a (nonoptimal) belief-based policy, inducing, for example, $\text{pol}(p)(h^=) := p(b^=) = \{check_=, noop\}$. $\square$

Policies can be naturally represented as trees, a node being a history or a belief state, branching on actions that can be taken at this node and subsequent possible observations. This representation however grows exponentially with the number of time-steps.

Manipulating graphs rather than trees yields more compact *finite state controllers* (FSCs) (Meuleau et al., 1999; Hansen, 1998; Grześ et al., 2015). A (nondeterministic) FSC consists of a set of nodes $N$ among which a distinguished set of initial nodes $N_0$, an action mapping $act: N \to \mathcal{A}$ assigning an action to each node, and a partial transition function $\delta: N \times \mathcal{O} \to \mathcal{P}(N)$.<fnref n="3" /> An FSC induces a policy in the obvious way: given a history $h$, choose an action nondeterministically among all those nodes which are reachable via the history from any initial node.

An $\epsilon$-optimal (infinite-horizon) belief-based policy can also be obtained by approximating the optimal value function for a long horizon. Such approximation is typically expressed as a set $\Gamma_a$ of $\alpha$-vectors per action $a$, inducing the nondeterministic policy $p(b) := \underset{\alpha \in \mathcal{A}}{\operatorname{argmax}} (\underset{\alpha \in \Gamma_a}{\operatorname{max}} b \cdot \alpha)$. However, as the dimension of the vectors grows linearly with the number of states and as the sets of alpha vectors $\Gamma_a$ can become very large, in practice this representation is neither more compact nor more readable than tree policies.

# 4 Epistemic features

We now come to the heart of our proposal: redescribing policies over *epistemic features*, which are features defined on the belief space. Formally, given a

<footnote n="1">¹Optimality is measured with respect to the expectation of cumulated, discounted reward. But our work handles any policy, whether optimal or not, so this is of little importance for this paper.</footnote>

<footnote n="2">²The definition over other belief states is irrelevant to our examples.</footnote>

<footnote n="3">³Partial because not all observations may be received at each node.</footnote>
POMDP, we define an epistemic feature to be a function $\varphi: \mathcal{B} \to \mathbb{R}$. Epistemic features may take many different forms, for instance, entropy; but we focus on epistemic features built in a systematic manner from a set of state features, that is, Boolean features of the form $f: S \to \mathcal{B}$, where $\mathcal{B} := \{0,1\}$ (false and true). Such state features are typically readily available (e.g., from a factored representation of the POMDP) or easily defined by an expert.

**Example 2** (continued). The state space of our running example can be described with two state features, x and y, with $x(s_{xy}) := x$ and $y(s_{xy}) := y$; for instance, $x(s_{00}) = x(s_{01}) = 0$. $\square$

Given a set $F$ of state features, any propositional formula $g$ over $F$ induces an epistemic feature $Bg$, whose value in belief state $b$ is the probability that a state sampled from $b$ satisfies $g$. To make this formal, write $s_F$ for the assignment to $F$ induced by $s \in S$ ($\forall f \in F: s_F(f) := f(s)$), and define $\text{sat}(s,g) := 1$ (resp. 0) if $s_F$ satisfies $g$ under the standard semantics of propositional logic.

**Definition 1** (epistemic feature). Let $F \subseteq \mathbb{B}^S$ be a set of state features. An epistemic feature over $F$ is an atom $\varphi$ of the form $Bg$, where $g$ is a propositional formula over $F$.<fnref n="4" /> As a function, $\varphi$ is defined for all belief states $b$ by $\varphi(b) := \mathbb{E}_{s \sim b} \text{sat}(s,g)$.

To keep the epistemic features easy to interpret, in practice we use simple logical combinations. A (propositional) literal over state features $F$ is a formula of the form $f$ or $\neg f$ for some $f \in F$. An epistemic clause $\kappa$ (resp. epistemic term $\tau$) of width $w$ is an epistemic feature $Bg$ where $g$ is a disjunction (resp. conjunction) of at most $w$ literals (over different state features) over $F$. Such epistemic clause or term is positive if all literals in $g$ are of the form $f$ (as opposed to $\neg f$). The set of all epistemic clauses (resp. terms, positive clauses, positive terms) of width $w$ over $F$ is written $\Phi_F^{\vee,w}$ (resp. $\Phi_F^{\wedge,w}$, $\Phi_F^{\vee,+,w}$, $\Phi_F^{\wedge,+,w}$).

**Example 3** (continued). The epistemic clauses of width $w = 1$ are Bx, By, B(¬x), B(¬y); the first two are positive, the last two are not. For $w = 2$, the epistemic clauses are B(x ∨ y), B(¬x ∨ ¬y), B(x ∨ ¬y), and B(¬x ∨ y); only the first one is positive.

Consider $b$ defined by $b(s_{00}) := \frac{1}{2}$, $b(s_{01}) := \frac{1}{4}$, and $b(s_{10}) := \frac{1}{4}$. For $\kappa := B(x \lor y)$, we have $\kappa(b) = \frac{1}{2} \times 0 + \frac{1}{4} \times 1 + \frac{1}{4} \times 1 = \frac{3}{4}$, and for $\kappa := B(\neg y)$, we have $\kappa(b) = \frac{1}{2} \times 1 + \frac{1}{4} \times 0 + \frac{1}{4} \times 1 = \frac{3}{4}$. $\square$

# 5 Embeddings and projections

Given a set of epistemic features $\Phi$ and a belief-based policy $p$, we propose to redescribe $p$ as a mapping defined over embeddings of belief states onto $F$. Importantly, we only consider policies restricted to a finite set of belief states (e.g., all those reachable by $p$ in a certain number of time-steps), and leave the general case to future work.

<footnote n="4">⁴Latin (resp. Greek) letters are for state (resp. epistemic) features/formulas.</footnote>
**Definition 2 (embedding).** Let $\Phi$ be an ordered tuple of $N$ epistemic features. The embedding of belief state $b$ (onto $\Phi$) is defined to be the vector $\Phi(b) := (\varphi(b) | \varphi \in \Phi) \in \mathbb{R}^N$.

The embedding of a belief state onto a set of epistemic features is often
lossy. However, as our experiments show (§7), epistemic clauses or terms of
small width will in general be enough for unambiguously representing optimal
policies over a finite subset of the belief space, for natural sets of state features
on natural problems.

If this is not the case, it might be that restricting the nondeterministic
choices of the policy makes it representable again. Given a finite set of belief
states $B$, an initial belief state $b_0 \in B$, and a policy $p: B \to \mathcal{P}(A)$, call $p'$ a
specialization of $p$ relative to $B$ and $b_0$ if (i) for all belief states $b \in B$ on which
$p'$ is defined, $\emptyset \subset p'(b) \subseteq p(b)$ holds, (ii) $p'$ is defined on $b_0$, and (iii) for all
belief states $b \in B$ such that $p'$ is defined on $b$, for all actions $a \in p'(b)$ and
observations $o$, if $b \oplus ao \in B$ holds, then $p'$ is defined on $b \oplus ao$. In words, a
specialization chooses a subset of the actions at each belief state, and its domain
must be closed under reachability from $b_0$.

**Example 4 (continued from Example 1).** Observe that $B := \{\mathbf{b}^{\text{unif}}, \mathbf{b}^{\neq}, \mathbf{b}^{=}\}$ is the set of belief states reachable by policy $p$. The policy $p_1$ defined by $p_1(\mathbf{b}^{\text{unif}}) := \{\text{check}_=\}, p_1(\mathbf{b}^{\neq}) := \{\text{switch}_x\}, \text{ and } p_1(\mathbf{b}^{=} := \{\text{check}_=, \text{noop}\}$ is a specialization of $p$ (relative to $B$ and $\mathbf{b}^{\text{unif}}$). The policy $p_2$ defined by $p_2(\mathbf{b}^{\text{unif}}) := \{\text{noop}\}$ (and undefined on other belief states) is also a (nonoptimal) specialization of $p$, as only $\mathbf{b}^{\text{unif}}$ is reachable from $\mathbf{b}^{\text{unif}}$ by $p_2$ (and $\emptyset \subset p_2(\mathbf{b}^{\text{unif}}) \subseteq p(\mathbf{b}^{\text{unif}})$ holds). $\square$

By the properties of the belief space (Kaelbling et al., 1998), any special-
ization of an optimal belief-based policy is also optimal. More generally, re-
describing a specialization of a policy amounts to restricting the actions which
the agent can take, but consistently with the initial policy.

With this in hand, we can define when a policy can be represented over a
set of epistemic features.

**Definition 3 (projectable, projection).** Let $B$ be a finite set of belief states, $p: B \to \mathcal{P}(A)$ be a belief-based policy defined on $B$, and $\Phi$ be a set of epistemic features. Then $p$ is said to be exactly projectable onto $\Phi$ over $B$ if there is a projection $\pi: \{\Phi(b) | b \in B\} \to \mathcal{P}(A)$ such that for all $b \in B$, $\pi(\Phi(b)) = p(b)$ holds. It is said to be projectable onto $\Phi$ relative to $B$ and $b_0$ if there is a specialization $p'$ of $p$ which is exactly projectable onto $\Phi$ over $B \cap \text{Reach}(\text{pol}(p'), b_0)$.

**Example 5 (continued).** For $w = 1$, we have $(\mathbf{B}x)(b) = (\mathbf{By})(b) = (\mathbf{B}(-x))(b) = (\mathbf{B}(-y))(b) = \frac{1}{2}$ for $b \in \{\mathbf{b}^{\text{unif}}, \mathbf{b}^{=}, \mathbf{b}^{\neq}\}$, hence

$$
\Phi_F^{\vee, 1}(\mathbf{b}^{\text{unif}}) = \Phi_F^{\vee, 1}(\mathbf{b}^{=}) = \Phi_F^{\vee, 1}(\mathbf{b}^{\neq}) = \left(\frac{1}{2}, \frac{1}{2}, \frac{1}{2}, \frac{1}{2}\right).
$$

Hence $p$ is not exactly projectable onto $\Phi_F^{\vee, 1}$, since it prescribes different sets of
actions for $\mathbf{b}^{\text{unif}}$ and $\mathbf{b}^{\neq}$, which have the same projection onto $\Phi_F^{\vee, 1}$. It is however
projectable, since its specialization $p_2$ is (obviously) exactly projectable.
On the other hand, $p$ is exactly projectable onto the set $\Phi_F^{\wedge,+1} \cup \Phi_F^{\wedge,+2} = \{\text{Bx}, \text{By}, \mathbf{B}(\mathbf{x} \wedge \mathbf{y})\}$, since the value $v_3$ of the third feature is already different on all three belief states (it is $\frac{1}{4}$ on $\mathbf{b}^{\text{unif}}$, $\frac{1}{2}$ on $\mathbf{b}^=$, and 0 on $\mathbf{b}^{\ne}$). Hence we can define (for instance) $\pi((v_1, v_2, v_3)) = \{\text{switch}_x\}$ for $v_3 < \frac{1}{8}$, and $\pi((v_1, v_2, v_3)) = \{\text{check=}, \text{noop}\}$ for $\frac{1}{8} \le v_3$. For a nonexact projection, we can define for instance $\pi'((v_1, v_2, v_3)) = \{\text{switch}_x\}$ for $v_3 < \frac{1}{8}$, $\pi'((v_1, v_2, v_3)) = \{\text{check=}\}$ for $\frac{1}{8} \le v_3 < \frac{3}{8}$, and $\pi'((v_1, v_2, v_3)) = \{\text{noop}\}$ for $\frac{3}{8} \le v_3$.

Observe that these definitions use only the value of the third feature, and hence $p$ is also projectable onto $\Phi_F^{\wedge,+2}$ alone. $\square$

Obviously, projectability depends on the set of epistemic features. The following results explore this dependency.<fnref n="5" />

**Proposition 1.** Let $B$ be a finite set of belief states, $p: B \to \mathcal{P}(A)$ a policy defined on $B$, and $F$ a set of state features. Let $w$ be an integer with $0 \le w < |F|$. If $p$ is (exactly) projectable onto $\Phi_F^{\vee,w}$ (resp. $\Phi_F^{\wedge,w}$), then it is (exactly) projectable onto $\Phi_F^{\vee,w+1}$ (resp. $\Phi_F^{\wedge,w+1}$).

**Proposition 2.** Let $F$ be an ordered tuple of $n$ state features, and assume that the function $F: S \to \mathbb{B}^n$ defined by $F(s) := (f(s) \mid f \in F)$ is injective. Then any policy over a finite set $B$ of belief states is projectable onto $\Phi_F^{\vee,n}$ and onto $\Phi_F^{\wedge,n}$.

These results justify our approach in the sense that provided the set of state features is rich enough, we can always project a policy onto a set of epistemic features containing only clauses or terms (of small width in practice — see §7).

Finally, observe that exact projectability of $p$ can be straightforwardly decided in polynomial time, by checking that for all belief states $b, b'$ in $B$, if $\Phi(b) = \Phi(b')$ holds, then $p(b) = p(b')$ holds. On the other hand, (non exact) projectability is hard to decide.

**Proposition 3.** The following problem is NP-complete:

* Input: A belief-based policy $p: B \to \mathcal{P}(A)$ defined on a finite set of belief states $B$; $b_0 \in B$; and a set of epistemic features $\Phi$.

* Question: Is $p$ projectable onto $\Phi$ relative to $B, b_0$?

Hardness holds even if the underlying POMDP is fully observable and has only 3 actions.

# 6 Epistemic representations

We can finally define epistemic representations of policies. Given a set of epistemic features $\Phi$ and a belief-based policy $p$ (defined over a finite set of belief states $B$ with an initial belief state $b_0$) which is projectable onto $\Phi$ relative

<footnote n="5">⁵Proofs of all claims are given in Appendix A.</footnote>
<figure><img src="image_2.png" /><figcaption>Figure 1: Decision tree representation of the specialization $\pi'$ of p.</figcaption></figure>

to $\mathcal{B}$ and $b_0$, our aim is to compute an interpretable representation of $p$, as a representation of a projection of $p$ onto $\Phi$.

We view this problem as that of computing a classifier for a set of labelled examples, where, for each belief state $b \in \mathcal{B}$, the vector $\Phi(b)$ is an example, and $p(b)$ is the set of labels for $\Phi(b)$. The classifier must classify all examples correctly, with the semantics that predicting any of the given labels is correct (nonexact projectability); it is however free to generalize to belief states outside of $\mathcal{B}$.

**Example 6 (continued).** Consider again $\mathcal{B} = \{\mathbf{b}^{\text{unif}}, \mathbf{b}^{=}, \mathbf{b}^{\neq}\}$, $\Phi = \Phi_F^{\wedge,+,1} \cup \Phi_F^{\wedge,+,2}$ ordered as $(\mathbf{Bx}, \mathbf{By}, \mathbf{B}(\mathbf{x} \wedge \mathbf{y}))$, and $p$. Then the examples are $(\frac{1}{2}, \frac{1}{2}, \frac{1}{4})$, $(\frac{1}{2}, \frac{1}{2}, \frac{1}{2})$, and $(\frac{1}{2}, \frac{1}{2}, 0)$, with sets of labels $\{\text{check}_=, \text{noop}\}$, $\{\text{check}_=, \text{noop}\}$, and $\{\text{switch}_x\}$, respectively. $\square$

In principle, any class of classifiers can be used. However, with interpretability in mind, we focus on *decision tree* classifiers, branching on tests $B_g \ge \theta$, and with one action at each leaf.<fnref n="6" /> Due to the NP-hardness of deciding projectability, and to keep the approach simple, given a policy $p: \mathcal{B} \to \mathcal{P}(\mathcal{A})$, we first sample a deterministic policy $\dot{p}: \mathcal{B} \to \mathcal{A}$ by choosing an action independently and uniformly at random from $p(b)$, for each $b \in \mathcal{B}$. Then the problem becomes a single-label classification problem.<fnref n="7" />

Another advantage of decision trees is that, if we bound neither the depth of the trees nor the number of occurrences of an epistemic feature along a branch, a representation always exists (provided the policy is projectable).

**Example 7 (continued).** Figure 1 depicts a decision tree representation of $p$ (assuming the deterministic specialization $\pi'$ of Example 5 has been sampled from $p$). $\square$

Summarizing, we start from a given POMDP and a given belief-based policy $p$. The policy $p$ can be obtained in any manner, and represented in any form, provided we can compute $p(b)$ efficiently given $b \in \mathcal{B}$. We then restrict $p$ to a

<footnote n="6">⁶We also tested linear classifiers, but they turned out to yield larger representations and to require much more computation time than decision trees.</footnote>

<footnote n="7">⁷The use of multi-label classification approaches is left to future work. In practice, policies output by the solvers in our experiments were typically deterministic.</footnote>
finite set of relevant belief states $B$, typically those reachable by $p$ from $b_0$ in a
given number of time-steps.

Our aim is to compute an epistemic representation $\rho$ of $p$, or of a specialization of it. For this, we start from a set $F$ of state features, given by a factored description of the POMDP or by an expert. We then choose an epistemic width $w$, whether we want to use epistemic clauses and/or terms, and whether we want to restrict to positive clauses/terms (§7 discusses how to make such choices). This defines a set of epistemic features $\Phi$.

We then test whether $p$ is projectable onto $\Phi$ relative to $B$ and $b_0$. If this is not the case, then we extend the set $\Phi$, typically by increasing $w$. If the set of state features is rich enough, then Proposition 2 guarantees that this process ends with $p$ being projectable.

When $p$ is projectable, we retain a projection $\pi$ of it. If this projection is nondeterministic, then we choose an arbitrary deterministic policy $\pi$ from it, otherwise we set $\pi := \pi$.

With this in hand, we then compute the set of ordered pairs $\{\langle\Phi(b), \dot{\pi}(\Phi(b))\rangle \mid b \in B\}$. We feed a classification algorithm with this set, requiring it to compute a classifier which is exact on the given pairs. The classification process is unconstrained on belief states outside of $B$, but of course we can use any kind of regularization to obtain more meaningful representations.

Finally, we see the classifier so obtained (if possible, which is always the case with unconstrained decision trees) as our epistemic representation $\rho$, a belief-based policy defined to map each $b \in B$ to the label output by the classifier on $\Phi(b)$.

The representation $\rho$ is intended to be shown to the user, as an interpretable version of $p$. Of course, it can also be used by an agent to choose actions during an interaction with the POMDP, provided the agent maintains the current belief state $b_t$ at each time-step $t$. Note that this requires the agent to know the POMDP model (transition and observation function). However, the full belief state needs not be computed in general: computing $\Phi(\text{bs}(h_t))$ is a *belief tracking* task, which can be performed implicitly from $b_0$ and $h_t$, for instance using operations over dynamic Bayesian networks representing the POMDP action and observation models (Bonet and Geffner, 2016). Still, this is of course more costly than, for instance, following an arc in a finite-state controller. Hence epistemic representations come with a tradeoff between efficiency at execution time and interpretability. This is reminiscent of other epistemic approaches to representing policies, like (probabilistic) knowledge-based programs (Lang and Zanuttini, 2015; Zanuttini et al., 2020).

Also, as explored in §8, the epistemic representation $\rho$ can be used to make the decisions of an agent more interpretable at execution time, as a complement to presenting the policy as a whole.
# 7 Experiments

We ran experiments on several standard problems from the POMDP literature. Our goals were to explore various properties of our representations, with different sets of epistemic features, and to investigate which epistemic width is enough for projectability in practice.

## 7.1 Protocol

Each experiment consists first in choosing a POMDP and computing a near-optimal policy *p* for it, using the off-the-shelf solver SARSOP (Kurniawati et al., 2008),<fnref n="8" /> which outputs *p* in the form of a set of α-vectors. We restrict *p* to the sets *B* of all belief states reachable by *p* in at most 100 steps, which in our benchmarks is enough for reaching a terminal state on all branches. Then (i) we redescribe *p* into FSCs and (ii) using the natural set of state features for the POMDP, and for several sets $\Phi$ of epistemic features, we decide whether *p* is projectable, and if yes, redescribe it into a decision tree $\rho$ over $\Phi$.

For each method, we record the redescription's computation time (excluding the computation of *p*) and its size, here the number of nodes for both FSCs and decision trees, as well as the depth of trees.

For computing FSCs, we generalized in a straightforward manner Grześ et al.'s *policy2fsc* algorithm (Grześ et al., 2015) to nondeterministic policies and to histories after which not all observations can occur.

For each benchmark, given the set of state features *F*, we consider the following sets of epistemic features: $\Phi_i := \bigcup_{j=1}^i (\Phi_F^{\vee,j} \cup \Phi_F^{\wedge,j})$ and $\Phi_i^+ := \bigcup_{j=1}^i (\Phi_F^{\vee,+,j} \cup \Phi_F^{\wedge,+,j})$, for $i = 1, 2, 3$. So, the richest set of epistemic features includes all epistemic clauses and terms of width 1, 2, or 3, and the poorest, only features $\mathbf{B}f$ (for all $f \in F$).

Apart from SARSOP, all methods were run with our own implementation in Python, using *sklearn* for computing decision trees. We used servers with Intel Xeon processors, between 2.0 and 2.8 GHz and between 128 and 512 GB of RAM. Experiments for a given benchmark were all run on the same server, with one core dedicated to each computation. All computations were given a timeout of 1 h CPU time; SARSOP was run with target precision $10^{-2}$.

## 7.2 Benchmarks

We tested our approach on four different families of POMDPs, with different characteristics (in particular, reliable or noisy observations, fixed or combinatorial set of actions). The complete descriptions can be found in Appendix B.

In *Wumpus*, an agent on a 2D grid must reach a goal (at an unknown location) while avoiding monsters (*Wumpuses*). The agent starts at (0, 0) and moves deterministically. *Wumpuses* never move but are hidden; however, the agent can “smell” so as to detect whether there is a *Wumpus* around its position.

<footnote n="8">⁸https://github.com/AdaCompNUS/sarsop</footnote>
In the *Localize* variant, the agent starts at a random position, but it has an action to localize itself. Finally, in the *safe* versions, there is no wumpus around the agent in the initial state, and the agent knows that.

In *Rock-Sample*, an agent on a 2D grid must sample rocks and reach an exit. Sampling a good (resp. bad) rock is rewarding (resp. costly). A noisy sensor (the further the sensed rock, the noisier) allows the agent to test the quality of a rock.

*Mastermind* is the famous code-breaking game. The agent must guess a hidden combination of colours in a given number of steps. Actions are combinatorial (testing a combination) and so are observations (numbers of good and misplaced colours).

Finally, we use the *Minesweeper* game. A 2D grid contains hidden mines. The agent can click cells, revealing either a mine (then the game is lost) or the number of mines around the clicked cell.

## 7.3 Results

For lack of space, we do not give the plots for all settings nor benchmarks, but only representative ones. The other plots can be found in Appendix C.

We start with results about computational time. Figure 2 shows the comparison between the time for computing an FSC (y-axis) versus the time for computing a decision tree (x-axis).

As expected, when using a larger set of epistemic features, our method requires more computational time (bottom plot). It is however very competitive with FSCs when using a restricted set (top plot; also middle plots in the appendix).

Concerning the size of the representations, Fig. 3 and 4 show the comparison between FSCs and decision trees with $\Phi_1^+$ and $\Phi_3$, and between decision trees with all 6 sets of epistemic features, respectively. The figures clearly show that the richer the set of features, the smaller the decision trees, which is natural given that what can be represented with small features can also be represented with larger features (Proposition 1). Compared with FSCs, decision trees are usually larger, but this is not so clear-cut for Minesweeper. Anyway, our experiments remain restricted to instances with a moderate number of belief states, which does not allow to draw a definite conclusion (in particular, there always exists a tree or an FSC with at most as many leaves/nodes as belief states, so it is expected that the size is at most linear in the number of belief states).

Fig. 5 shows the depth of the trees for all 6 settings on the same 2 benchmarks. The plots suggest that the depth evolves sublinearly, and hence remains reasonable. This is even more so that we measured the raw depth, without taking into account the fact that the same feature may occur several times (and hence, that the branch can be presented more succinctly to the user, as discussed in §8).

Finally, we measured the percentage of instances which were not projectable, for each setting. It turns out that the only settings in which there were nonprojectable instances are Mastermind with epistemic features $\Phi_1^+$ or (equivalently)
<figure><img src="image_3.png" /><figcaption>Figure 2: Computational time (in seconds) for computing a decision tree (x-axis) versus an FSC (y-axis). Top: epistemic features $\Phi_1^+$, bottom: $\Phi_3$.</figcaption></figure>

$\Phi_1$ (1.38% of the instances were not projectable), and Wumpus with localization action and the same sets of features (0.29%). In addition to be very low, in both cases these figures dropped to 0 already with $\Phi_2^+$.

We experimented only on moderate-size instances, yet we find these results encouraging. First, natural benchmarks turn out to be projectable (with straightforward sets of state features) for very low epistemic width (almost always 1, and always 2, even with only positive literals). Second, for such width (1 or 2), the approach is competitive with FSCs in terms of computation time and size; overall, width 2 seems to be a good tradeoff. Third, the tree representations have a reasonable depth, which is a good point towards interpretability.

Of course, more intensive experiments should be run before drawing definite
<figure><img src="image_4.png" /><figcaption>Figure 3: Size of representations (number of nodes in the decision tree or FSC) as a function of the number of belief states, for Wumpus with localization action (left) and Minesweeper (right).</figcaption></figure>

conclusions (see §9).

# 8 Explanations of decisions at execution time

Arguably, it is difficult for a human user to apprehend the representation of a complete policy, even as a reasonably compact decision tree. We now present how our epistemic representations can be used to present the decisions made by an agent at execution time. Precisely, when the agent is executing a policy, we explain each decision in turn, leveraging the epistemic representation of the policy.

This section is meant to illustrate the potential of our approach to representing policies. We leave it to future work to investigate approaches from the literature to presenting the classifications made using a decision tree. Let us also emphasize that a similar approach could be applied to other classifiers.

Let $p$ be a policy and $\rho$ an epistemic representation of it as a decision tree, over a set of epistemic features $\Phi$. We consider an episode of interaction of the agent with the environment, where the agent starts with the initial belief state $b_0$ and then follows $\rho$.
<figure><img src="image_5.png" /><figcaption>Figure 4: Size of representations (number of nodes in the decision tree or FSC) as a function of the number of belief states, for Wumpus with localization action (left) and Minesweeper (right).</figcaption></figure>

For each time-step $t$, let $b_t$ be the current belief state, and $a_t := \rho(b_t)$ the next action, based on the branch $\beta_t$ of the decision tree activated by $b_t$. We essentially present the user five elements: the observation received, the evolution of epistemic features from $b_{t-1}$ to $b_t$, the action $a_t$, the branch $\beta_t$, and representative states of $\beta_t$ in $b_t$. An example is given on Fig. 6 (for the decision tree of Fig. 1, and starting from $b_0 = \text{b}^{\text{unif}}$), and we now present the details.

First, since our approach considers a finite set $B$ of belief states, we restrict the tests in branch $\beta_t$ to the actual values occurring in $B$. This makes clearer the real scope of each test; for instance, in Fig. 6, at time-step 0, the actual branch of the decision tree is $B(\times \wedge y) \in [\frac{1}{8}, \frac{3}{8})$, but only belief states with value $\frac{1}{4}$ satisfy this branch, so we present the latter interval. As another example, $\beta_2$ as presented makes it clearer that the action is motivated by the maximum possible belief that $\times \wedge y$ is true, than the test $B(\times \wedge y) \ge \frac{3}{8}$ of the decision tree.

Concerning the evolution of epistemic features, to keep the number of values manageable, we only present the features appearing in $\beta_{t-1}$ or $\beta_t$ with the evolution of their value (if nonzero). This is meant to restrict this part of the presentation to what pertains to the last and next decisions seen by the user.

Now in addition to presenting $\beta_t$, so as to give a more intuitive view of it, we present a restricted number of states of the current belief state. Call a state
<figure><img src="image_6.png" /><figcaption>Figure 5: Depth of decision trees as a function of the number of belief states, for Wumpus with localization action (left) and Minesweeper (right).</figcaption></figure>

<table><caption>Figure 6: Explanations for an interaction with our running example.</caption><tr><td>Beginning of interaction.</td></tr><tr><td>Action taken: a<sub>0</sub> = check<sub>+</sub>.</td></tr><tr><td>Justified by branch: β<sub>0</sub> = B(x ∧ y) ∈ [<sup>1</sup>&frasl;<sub>4</sub>, <sup>1</sup>&frasl;<sub>4</sub>].</td></tr><tr><td>Promoting states: s<sub>00</sub>, s<sub>01</sub>.</td></tr><tr><td>Observation received: o<sub>0</sub> = false.</td></tr><tr><td>Evolution of knowledge: B(x ∧ y) ↓ <sup>1</sup>&frasl;<sub>4</sub>.</td></tr><tr><td>Action taken: a<sub>1</sub> = switch<sub>x</sub>.</td></tr><tr><td>Justified by branch: β<sub>1</sub> = B(x ∧ y) = 0.</td></tr><tr><td>Promoting states: s<sub>01</sub>, s<sub>10</sub>.</td></tr><tr><td>Observation received: o<sub>1</sub> = void.</td></tr><tr><td>Evolution of knowledge: B(x ∧ y) ↑ <sup>1</sup>&frasl;<sub>2</sub>.</td></tr><tr><td>Action taken: a<sub>2</sub> = noop.</td></tr><tr><td>Justified by branch: β<sub>2</sub> = B(x ∧ y) ∈ [<sup>1</sup>&frasl;<sub>2</sub>, <sup>1</sup>&frasl;<sub>2</sub>].</td></tr><tr><td>Promoting states: s<sub>00</sub>, s<sub>11</sub>.</td></tr><tr><td>Observation received: o<sub>2</sub> = void.</td></tr><tr><td>End of interaction.</td></tr></table>

s promoting (resp. demoting) for a test $B_g \ge \theta$ ($\theta > 0$) if it satisfies (resp. does not satisfy) $g$, and similarly for tests $B_g \le \theta$ ($\theta < 1$). If $b_t$ contains states which
promote all tests in $\beta_t$, then we present the user a sample of a fixed size of the most probable of them according to $b_t$. In Fig. 6, at $t = 1$, we present $s_{01}$ and $s_{10}$, which both promote $B(x \land y) \le 0$ (that is, do not satisfy $x \land y$). If no state promotes all tests (for instance, no state can promote both $B(x \land y) \ge \frac{1}{4}$ and $B(x \land y) \le \frac{1}{4}$ in $\beta_0$), then we consider each subbranch $\beta'_t$ which is the set of demoted tests of at least one state, and for each $\beta'_t$ with a minimum number of demotions, we present a sample of the most probable states demoting exactly $\beta'_t$. This is meant to present a diverse set of states to the user. In Fig. 6, state $s_{00}$ demotes $B(x \land y) \ge \frac{1}{4}$, and $s_{11}$ demotes $B(x \land y) \le \frac{1}{4}$. As can be seen, by ensuring diversity, this also makes clear why sensing actions are taken, as these are typically justified by uncertainty.

We now give the first two time-steps of an interaction in the Wumpus example (safe version, with unknown starting position). For compactness, we abbreviate the features: $a_{rc}$ (resp. $w_{rc}$, $g_{rc}$) for “the agent (resp. Wumpus, goal)” is at row $r$, column $c$ (the top row is 0).

The first step is as follows:

* action taken: localize

* justified by branch:
  $B_{g00} \le .12$, $B_{g01} \le .12$, $Ba_{12} \ge .10$, $B_{g20} \le .12$, $B_{g22} \le .11$, $Bw_{10} \in [.10, .25]$, $Bw_{21} \le .10$, $Bw_{00} \in [.12, .25]$

* promoting states:

<figure><img src="image_7.png" /></figure>

As can be seen, the branch expresses that there are a number of positions of which the agent is unsure. The promoting states explain quite well why localize is taken, by showing diverse plausible positions for the agent.

The interaction proceeds as follows:

* observation received: 2-0

* evolution of knowledge:
  $Ba_{12} \downarrow .10$, $Ba_{20} \uparrow .87$, $Ba_{21} \downarrow .10$, $Bw_{00} \uparrow .04$, $Bw_{02} \uparrow .04$, $Bw_{10} \downarrow .10$, $Bw_{21} \downarrow .10$, $B_{g00} \uparrow .01$, $B_{g01} \uparrow .01$, $B_{g02} \uparrow .01$, $B_{g20} \downarrow .11$, $B_{g21} \uparrow .03$, $B_{g22} \uparrow .01$

For instance, $Ba_{12} \downarrow .10$ pertains to the decision at $t = 0$ (test $Ba_{12} \ge .10$), while $Ba_{20} \uparrow .87$ pertains to $t = 1$, getting the user ready to better read the next branch. The latter evolution is clearly informative: the agent is now (at least) almost sure of its location.

The explanation for the next decision goes as follows:

* action taken: up
* justified by branch:
  $B_{g00} = .12$, $B_{g01} \le .11$, $B_{g02} = .12$, $B_{a20} = 1$, $B_{a21} = 0$, $B_{w02} = .17$, $B_{g21} = .14$

* promoting states:

<figure><img src="image_8.png" /></figure>

As it turns out, the branch seems to explain less directly why the agent chooses to move up. This comes from coincidences in the (small) space of reachable belief states; We come back to this issue in the discussion. However, again the promoting states explain the choice quite well: the Wumpus is never just above the agent, and the goal has a good chance to be above it.

# 9 Conclusion

We proposed an approach for redescribing POMDP policies onto sets of epis-
temic features, with the goal of improving interpretability. For this we take a
classifier (here, a decision tree) as a representation of the policy. Our experi-
ments show that our approach has the potential to yield representations on par
with finite-state controllers in terms of size and computation time, while hope-
fully more readable. Interestingly, they also show that for natural benchmarks,
simple (small) epistemic features are enough for indeed representing the policy.
Finally, we show how to use our approach to explain decisions at execution time.

On the experimental side, one next step is to run more experiments, with
larger instances of POMDPs. For this we plan to use factored POMDP solvers
(Poupart, 2005) and factored belief tracking (Bonet and Geffner, 2016). Another
step to take is to study to what extent human users find the redescriptions and
interactions interpretable, so as to go beyond the raw measures which we studied
in this paper.

Our goal was to give first results about our approach, but there are many
limitations. One limitation is in the interactions: when presenting a branch to
the user, it may turn out that the tests make sense only due to (i) unnatural
correlations between belief states in the restricted set, and/or (ii) the fact that
the decision tree “knows” that is has been executed since the beginning of the
interaction. As an example, assume the policy moves along the grid first on
the top row, from left to right. Then there can never be a belief state where
the agent is on the second row but the goal is on the top row (it would have
reached it earlier). Hence a branch in an optimal policy may make a decision
(say, to move down), after testing the position of the agent while one would
naturally test the position of the goal. In future work, we would like to handle
such unnatural correlations so as to present the user the root causes; for this we
plan to use approaches from the literature, for instance, causal graphs (Nashed et al., 2023).

Finally, our long-term objective is to perform planning and reinforcement learning directly on the epistemic embeddings of the belief states. The goal here would be to get interpretability by design, and hopefully to exploit the existence of compact epistemic representations of (optimal) policies for faster convergence.

**Acknowledgements** This work has been funded by the French National Agency for Research (ANR) through grant ANR-22-CE23-0029.

## References

Azeem, M., Chakraborty, D., Kanav, S., and Kretinsky, J. (2024). Explainable finite-memory policies for partially observable Markov decision processes. arXiv:2411.13365 [cs.AI].

Bakker, B. (2001). Reinforcement learning with long short-term memory. In Dietterich, T., Becker, S., and Ghahramani, Z., editors, *Proc. Advances in Neural Information Processing Systems 14 (NIPS 2001)*, pages 1475–1482. MIT Press.

Bewley, T., Lawry, J., and Richards, A. (2021). Modelling agent policies with interpretable imitation learning. In Heintz, F., Milano, M., and O'Sullivan, B., editors, *Proc. International Workshop on the Foundations of Trustworthy AI - Integrating Learning, Optimization and Reasoning (TAILOR 2020)*, pages 180–186. Springer.

Bonet, B. and Geffner, H. (2016). Factored probabilistic belief tracking. In Kambhampati, S., editor, *Proc. 25th International Joint Conference on Artificial Intelligence (IJCAI 2016)*, pages 3045–3052. IJCAI/AAAI Press.

Chakraborti, T., Kulkarni, A., Sreedharan, S., Smith, D. E., and Kambhampati, S. (2019). Explicability? Legibility? Predictability? Transparency? Privacy? Security? The emerging landscape of interpretable agent behavior. In Benton, J., Lipovetzky, N., Onaindia, E., Smith, D. E., and Srivastava, S., editors, *Proc. 29th International Conference on Automated Planning and Scheduling (ICAPS 2019)*, pages 86–96. AAAI Press.

Costa, V. G., Pérez-Aracil, J., Salcedo-Sanz, S., and Pedreira, C. E. (2024). Evolving interpretable decision trees for reinforcement learning. *Artificial Intelligence*, 327.

Doshi-Velez, F. and Kim, B. (2018). Considerations for evaluation and generalization in interpretable machine learning. In Escalante, H. J., Escalera, S., Guyon, I., Baró, X., Güçlüürk, Y., Güçlü, U., and van Gerven, M., editors, *Explainable and Interpretable Models in Computer Vision and Machine Learning*, pages 3–17. Springer International Publishing, Cham.
Du, M., Liu, N., and Hu, X. (2020). Techniques for interpretable machine learning. *Communications of the ACM*, 63(1):68–77.

Gajcin, J., Nair, R., Pedapati, T., Marinescu, R., Daly, E., and Dusparic, I. (2021). Contrastive explanations for comparing preferences of reinforcement learning agents. arXiv:2112.09462 [cs.AI].

Gao, L. and Guan, L. (2023). Interpretability of machine learning: Recent advances and future prospects. *IEEE Multimedia*, 30(4):105–118.

Gilpin, L. H., Bau, D., Yuan, B. Z., Bajwa, A., Specter, M. A., and Kagal, L. (2018). Explaining explanations: An overview of interpretability of machine learning. In Bonchi, F., Provost, F. J., Eliassi-Rad, T., Wang, W., Cattuto, C., and Ghani, R., editors, *Proc. 5th IEEE International Conference on Data Science and Advanced Analytics (DSAA 2018)*, pages 80–89. IEEE.

Grandien, N., Delfosse, Q., and Kersting, K. (2024). Interpretable end-to-end neurosymbolic reinforcement learning agents. arXiv:2410.14371 [cs.AI].

Grześ, M., Poupart, P., Yang, X., and Hoey, J. (2015). Energy efficient execution of POMDP policies. *IEEE Transactions on Cybernetics*, 45(11):2484–2497.

Hansen, E. (1998). An improved policy iteration algorithm for partially observable MDPs. In Jordan, M. I., Kearns, M. J., and Solla, S. A., editors, *Proc. Advances in Neural Information Processing Systems 10 (NIPS 1997)*, pages 1015–1021. MIT Press.

Huang, J., Angelov, P. P., and Yin, C. (2020). Interpretable policies for reinforcement learning by empirical fuzzy sets. *Engineering Applications of Artificial Intelligence*, 91.

Huber, T., Weitz, K., André, E., and Amir, O. (2021). Local and global explanations of agent behavior: Integrating strategy summaries with saliency maps. *Artificial Intelligence*, 301.

Kaelbling, L. P., Littman, M. L., and Cassandra, A. R. (1998). Planning and acting in partially observable stochastic domains. *Artificial Intelligence*, 101(1-2):99–134.

Knuth, D. E. (1976). The computer as master mind. *Journal of Recreational Mathematics*, 9(1):1–6.

Kohler, H., Delfosse, Q., Akrour, R., Kersting, K., and Preux, P. (2024). Interpretable and editable programmatic tree policies for reinforcement learning. In Rachelson, E., Claeys, E., Bertoin, D., and Drougard, N., editors, *Proc. 17th European Workshop on Reinforcement Learning (EWRL 2024)*.

Kurniawati, H., Hsu, D., and Lee, W. S. (2008). SARSOP: Efficient point-based POMDP planning by approximating optimally reachable belief spaces. In *Proc. Robotics: Science and Systems IV*. MIT Press.
Laforest, G., Buffet, O., Niveau, A., and Zanuttini, B. (2025). Post-hoc interpretation of POMDP policies. In Lynce, I. and Murano, A., editors, *Proc. 28th European Conference on Artificial Intelligence (ECAI 2025)*. IOS Press.

Lang, J. and Zanuttini, B. (2015). Probabilistic knowledge-based programs. In Yang, Q. and Wooldridge, M. J., editors, *Proc. 24th International Joint Conference on Artificial Intelligence (IJCAI 2015)*, pages 1594–1600. AAAI Press.

Linardatos, P., Papastefanopoulos, V., and Kotsiantis, S. (2021). Explainable AI: A review of machine learning interpretability methods. *Entropy*, 23(1).

Mazoure, B., Doan, T., Li, T., Makarenkov, V., Pineau, J., Precup, D., and Rabusseau, G. (2022). Low-rank representation of reinforcement learning policies. *Journal of Artificial Intelligence Research*, 75:597–636.

Meli, D., Castellini, A., and Farinelli, A. (2024). Learning logic specifications for policy guidance in POMDPs: An inductive logic programming approach. *Journal of Artificial Intelligence Research*, 79:725–776.

Meuleau, N., Peshkin, L., Kim, K.-E., and Kaelbling, L. (1999). Learning finite-state controllers for partially observable environments. In Kathryn B. Laskey, H. P., editor, *Proc. 15th Conference on Uncertainty in Artificial Intelligence (UAI 1999)*, pages 427–436. Morgan Kaufmann.

Miura, S. and Zilberstein, S. (2021). A unifying framework for observer-aware planning and its complexity. In de Campos, C. P., Maathuis, M. H., and Quaeghebeur, E., editors, *Proc. 37th Conference on Uncertainty in Artificial Intelligence (UAI 2021)*, volume 161 of *Proceedings of Machine Learning Research*, pages 610–620.

Mnih, V., Kavukcuoglu, K., Silver, D., Rusu, A. A., Veness, J., Bellemare, M. G., Graves, A., Riedmiller, M. A., Fidjeland, A., Ostrovski, G., Petersen, S., Beattie, C., Sadik, A., Antonoglou, I., King, H., Kumaran, D., Wierstra, D., Legg, S., and Hassabis, D. (2015). Human-level control through deep reinforcement learning. *Nature*, 518(7540):529–533.

Nashed, S. B., Mahmud, S., Goldman, C. V., and Zilberstein, S. (2023). Causal explanations for sequential decision making under uncertainty. In Agmon, N., An, B., Ricci, A., and Yeoh, W., editors, *Proc. 22nd International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2023)*, pages 2307–2309. ACM.

Ni, T., Eysenbach, B., and Salakhutdinov, R. (2022). Recurrent model-free RL can be a strong baseline for many POMDPs. In Chaudhuri, K., Jegelka, S., Song, L., Szepesvári, C., Niu, G., and Sabato, S., editors, *Proc. 39th International Conference on Machine Learning (ICML 2022)*, volume 162 of *Proceedings of Machine Learning Research*, pages 16691–16723.
Poupart, P. (2005). *Exploiting Structure to Efficiently Solve Large Scale Partially Observable Markov Decision Processes*. PhD thesis, University of Toronto.

Russell, J. and Santos, E. (2019). Explaining reward functions in Markov decision processes. In Barták, R. and Brawner, K. W., editors, *Proc. 32nd International Florida Artificial Intelligence Research Society Conference (FLAIRS 2019)*, pages 56–61. AAAI Press.

Russell, S. and Norvig, P. (2020). *Artificial Intelligence: A Modern Approach*. Pearson, 4th edition.

Saulières, L., Cooper, M. C., and de Saint-Cyr, F. D. (2024). Backward explanations via redefinition of predicates. In Endriss, U., Melo, F. S., Bach, K., Diz, A. J. B., Alonso-Moral, J. M., Barro, S., and Heintz, F., editors, *Proc. 27th European Conference on Artificial Intelligence (ECAI 2024)*, volume 392 of *Frontiers in Artificial Intelligence and Applications*, pages 786–793. IOS Press.

Sebag, M. and Teytaud, O. (2012). Combining myopic optimization and tree search: Application to minesweeper. In Hamadi, Y. and Schoenauer, M., editors, *Proc. 6th International Conference on Learning and Intelligent Optimization (LION 6)*, volume 7219 of *Lecture Notes in Computer Science*, pages 222–236. Springer.

Smith, T. and Simmons, R. (2004). Heuristic search value iteration for POMDPs. In Chickering, D. M. and Halpern, J. Y., editors, *Proc. 20th Conference in Uncertainty in Artificial Intelligence (UAI 2004)*, pages 520–527. AUAI Press.

Topin, N., Milani, S., Fang, F., and Veloso, M. (2021). Iterative bounding MDPs: Learning interpretable policies via non-interpretable methods. In Leyton-Brown, K. and Mausam, editors, *Proc. 35th AAAI Conference on Artificial Intelligence (AAAI 2021)*, pages 9923–9931. AAAI Press.

Wang, N., Pynadath, D. V., and Hill, S. G. (2016). The impact of POMDP-generated explanations on trust and performance in human-robot teams. In Jonker, C. M., Marsella, S., Thangarajah, J., and Tuyls, K., editors, *Proc. 15th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2016)*, pages 997–1005. ACM.

Wikipedia contributors (2025). Hunt the Wumpus. https://en.wikipedia.org/w/index.php?title=Hunt%20the%20Wumpus. Wikipedia, The Free Encyclopedia; accessed July 31, 2025.

Zanuttini, B., Lang, J., Saffidine, A., and Schwarzentruber, F. (2020). Knowledge-based programs as succinct policies for partially observable domains. *Artificial Intelligence*, 288.
# A Proofs

This appendix provides proofs that are not detailed in the body of the paper.

**Proposition 1.** Let $B$ be a finite set of belief states, $p: B \to \mathcal{P}(A)$ a policy defined on $B$, and $F$ a set of state features. Let $w$ be an integer with $0 \le w < |F|$. If $p$ is (exactly) projectable onto $\Phi_F^{\vee,w}$ (resp. $\Phi_F^{\wedge,w}$), then it is (exactly) projectable onto $\Phi_F^{\vee,w+1}$ (resp. $\Phi_F^{\wedge,w+1}$).

*Proof.* This comes from the ability to retrieve the value of an epistemic clause (resp. term) of width $w$ from the values of epistemic clauses (resp. terms) of width $w+1$. Indeed, for a propositional term $t$ and a belief state $b$, we have $\mathbf{B}(t)(b) = \mathbf{B}(t \land f)(b) + \mathbf{B}(t \land \neg f)(b)$, for an arbitrary state feature $f \in F$. For a propositional clause $c$, writing $t$ for a term equivalent to the negation of $c$, we have $\mathbf{B}(c)(b) = 1 - \mathbf{B}(t)(b) = 1 - (\mathbf{B}(t \land f)(b) + \mathbf{B}(t \land \neg f)(b))$ for an arbitrary state feature $f \in F$, and hence $\mathbf{B}(c)(b) = -1 + \mathbf{B}(c \lor \neg f)(b) + \mathbf{B}(c \lor f)(b)$. $\square$

**Proposition 2.** Let $F$ be an ordered tuple of $n$ state features, and assume that the function $F: S \to \mathbb{B}^n$ defined by $F(s) := (f(s) \mid f \in F)$ is injective. Then any policy over a finite set $B$ of belief states is projectable onto $\Phi_F^{\vee,n}$ and onto $\Phi_F^{\wedge,n}$.

*Proof.* For epistemic terms, this follows directly from the fact that the function $b \mapsto \Phi_F^{\wedge,n}(b)$ is also injective. Indeed, the probability of each state $s$ in $b$ can be retrieved from the projection as the value of the unique epistemic term of width $n$ satisfied by $s$. The reasoning is similar for clauses: the probability of $s$ can be retrieved as $1 - \mathbf{B}(c)(b)$, with $c$ the unique epistemic clause of width $n$ not satisfied by $s$. $\square$

**Proposition 3.** The following problem is NP-complete:

* Input: A belief-based policy $p: B \to \mathcal{P}(A)$ defined on a finite set of belief states $B$; $b_0 \in B$; and a set of epistemic features $\Phi$.

* Question: Is $p$ projectable onto $\Phi$ relative to $B$, $b_0$?

*Hardness holds even if the underlying POMDP is fully observable and has only 3 actions.*

*Proof.* We give a reduction from the satisfiability problem for conjunctions of clauses of length 3. Given an instance, we build a fully observable MDP, epistemic features, an embedding of states, and a policy, such that the policy is projectable if and only if the conjunction of clauses is satisfiable.

The MDP has (among others) one state $s_c$ per clause $c$, and 3 actions $a_i$, $i = 1, 2, 3$, so that the built policy assigns $\{a_1, a_2, a_3\}$ to all of them. Those states are all reachable from $b_0$ via a single action available there.

Taking action $a_i$ in $s_c$ is interpreted as trying to satisfy $c$ with its $i$th literal, hence specializing the policy on these states chooses one or several literals per clause. So as to prevent a policy to choose the $i$th literal of clause $c$ and the
jth of clause $c'$ when these are opposite literals (say, $x$ and $
eg x$), we design the transition function so that taking $a_i$ in $s_c$ (resp. $a_j$ in $s_{c'}$) leads to a specific state $s_{i,c,j,c'}$ (resp. $s_{j,c',i,c}$). Now we build these two states, their embedding, and the policy so that the states have the same embedding, but disjoint sets of actions according to the underlying policy. This indeed prevents to make the two choices concurrently, since this would make two belief states reachable while they together prevent projectability.

Finally, the construction is finalized by making all actions but the one in the initial state lead to the state where they are taken, with the complement probability of the transitions already assigned by the above constructions (note that the choices of precise probability values is nonessential).

Clearly, the construction is polynomial time (each state can be identified by a unique state feature, except for the specific pairs of conflicting states for which we can use an additional, specific state feature), and the initial formula is satisfiable if and only if there is a specialization of the policy which cannot reach both $s_{i,c,j,c'}$ and $s_{j,c',i,c}$ (for all relevant $i, c, j, c'$). □

# B Benchmarks

This appendix provides a full description of each family of benchmarks.

## Wumpus (Wikipedia contributors, 2025; Russell and Norvig, 2020)
An agent must find a treasure as fast as possible on a 2D grid, while avoiding the monsters (Wumpuses). The agent always knows its own location and it has deterministic actions for moving by one square in the four cardinal directions. No location can be occupied by both the treasure and a Wumpus. The treasures and Wumpuses do not move and are initially at unknown locations, but the agent can “smell”, which reveals whether there is a Wumpus on one of the 4 neighboring cells. Therefore, the agent may infer the locations of the Wumpuses by moving around and smelling, and eventually reach a treasure.

Figure 7 illustrates a situation after the agent has smelled at and moved from the four locations marked by arrows (left), and additionally smelled at the middle location (right). Blue (resp. red) question marks indicate uncertainty about the presence of the goal (resp. Wumpus) at the corresponding location. The real location of the Wumpus is as on the rightmost figure, and the agent can deduce it only at that step.

A Wumpus POMDP is further specified by the size of the grid, the number of Wumpuses and treasures (both known to the agent), and whether there might be a Wumpus around the agent in the initial state (“unsafe” instances; the initial belief state is otherwise uniform).

In the Wumpus-Localized version of the problem, the agent starts at a random location on the map and initially does not know its position. It has an additional action, localize, which consists of observing its own position. Hence, after taking this action, it will know where it is exactly during the rest of the game.
<figure><img src="image_9.png" /><figcaption>Figure 7: Example (epistemic) situation for Wumpus. Figure (a) shows the belief state of the agent at time-step $t = 8$. The agent does not know the position of the Wumpus yet. Figure (b) shows the belief state at $t = 9$, after the agent took action $a_8 = $'smell' and received observation $o_8 = $'odor', hence being able to deduce the exact location of the Wumpus.</figcaption></figure>

The state features used to represent the states of the POMDP correspond to the presence of the agent, the Wumpus or the goal on each cell of the map.

**Rock-Sample (Smith and Simmons, 2004)** A rover navigates a 2D grid containing rocks (at known locations), each either good or bad, with equal probability. The rover can sample a rock at its current position, with a positive (resp. negative) reward if it was good (resp. bad); then the rock becomes bad. The rover can also check the status of a rock, with sensor accuracy decreasing exponentially with its distance to the rock. Reaching an exit (at one of known locations) yields a positive reward. Finally, the robot can move deterministically by one square in each cardinal direction, and always knows its position.

A Rock-Sample POMDP is further specified by the size of the grid and the positions of the rocks and exits. An interesting characteristic of this problem is noisy observations, which imply that a large number of belief states can be reached even on small grids.

We used two versions of this benchmark, the first one where the rocks are at the middle of the map, and another one, that we call *diagonal*, where the rocks span the antidiagonal line of the map.

The state features used correspond to the presence of the agent whether there is a good (resp. bad) rock on each cell of the map.

**Mastermind (Knuth, 1976)** Our third benchmark is Mastermind, the famous code-breaking game. A Mastermind POMDP is specified by the number of positions, colors, possible repetitions in the secret code, and the number of attempts allowed. An interesting characteristic of this benchmark is the combinatorial set of actions, which grows with the size of the instance.
At the beginning of each game, a secret combination is randomly generated given a combination length, a number of different colors and the number of possible repetitions of the same color in the code. The goal is to guess the code as fast as possible within a limited number of turns (the horizon). At each time-step, the action taken by the policy is to propose a combination. The observation received is a tuple consisting of the number of colors in the proposed combination matching those of the secret one at the exact same position, and the number of colors that are correct but misplaced. A positive reward is granted if the secret combination is found. A negative reward is given otherwise, the penalty being worse when nothing is found at all, that is, none of the colors of the secret code was correctly guessed (neither at a correct nor at an incorrect position).

The state features used to represent the problem correspond to the presence of each color at each position in the combination, and to the time-step.

**Minesweeper (Sebag and Teytaud, 2012)** Finally, we used the famous Minesweeper game. A Minesweeper POMDP is specified by the size of the grid and the number of mines.

The state corresponds to the (static and randomly generated) configuration of mines, plus the list of cells which have been probed. At each time-step, the action consists in picking a new cell to probe. If the selected cell contains a mine, the game is lost, resulting in a negative reward of -1. If it is empty, the number of mines in the 8 neighboring cells is revealed, and a reward of +0.1 is received. If all cells but the ones containing mines have been probed, the game is won, resulting in a positive reward of +1.

The state features used correspond to the presence of a mine, and to whether the cell has been probed, for each cell.

# C Additional experimental results

We present here all plots for the experiments reported on in §7. The results presented are the same as there, but for the complete set of epistemic settings and benchmarks.
<figure><img src="image_10.png" /><figcaption>Figure 8: Computational time (in seconds) for computing a decision tree (x-axis) versus an FSC (y-axis). Left column: clauses of width 1; middle: width 1 and 2; right: width 1, 2, and 3. Top row: only positive literals; bottom: positive and negative literals.</figcaption></figure>

<figure><img src="image_11.png" /><figcaption>Figure 9: Size of representations (number of nodes in the decision tree or FSC) as a function of the number of belief states, for all benchmarks, finite-state controllers, and our 2 extreme settings. From left to right: Wumpus, Wumpus-Localize, Rock-Sample, Rock-Sample with blocks on the antidiagonal, Minesweeper, Mastermind.</figcaption></figure>
<figure><img src="image_12.png" /><figcaption>Figure 10: Size of epistemic representations (number of nodes in the decision tree) as a function of the number of belief states, for all benchmarks and for our 6 settings. From left to right: Wumpus, Wumpus-Localize, Rock-Sample, Rock-Sample with blocks on the antidiagonal, Minesweeper, Mastermind.</figcaption></figure>

<figure><img src="image_13.png" /><figcaption>Figure 11: Depth of representations (depth of the decision tree) as a function of the number of belief states, for all benchmarks and for our 6 settings. From left to right: Wumpus, Wumpus-Localize, Rock-Sample, Rock-Sample with blocks on the antidiagonal, Minesweeper, Mastermind.</figcaption></figure>