# Post-Hoc Interpretation of POMDP Policies

Geoffrey Laforest, Olivier Buffet, Alexandre Niveau, Bruno Zanuttini

► To cite this version:

Geoffrey Laforest, Olivier Buffet, Alexandre Niveau, Bruno Zanuttini. Post-Hoc Interpretation of POMDP Policies. 28th European Conference on Artificial Intelligence (ECAI 2025), Oct 2025, Bologna (ITALY), Italy. hal-05197856

HAL Id: hal-05197856

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

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

Geoffrey Laforest<sup>a,∗</sup>, Olivier Buffet<sup>b</sup>, Alexandre Niveau<sup>a</sup> and Bruno Zanuttini<sup>a</sup>

**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 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 describes 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 algorithmic predictions to ensure decisions based on machine learning are safe and reliable [11, 7, 22]. 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 implies that a user can grasp how inputs are processed and mapped to the outputs in a human-comprehensible format [10]. Closely related notions 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 [5]. Observer-aware MDPs provide a formal framework to address these challenges within stochastic environments [26].

Interpretability usually takes two roads [8]. 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 [33] or expressed with symbolic features [15, 12], sometimes both [6, 18]. In [15], 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 [16, 9] or actions taken under the given policy. For instance, in [32], 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 [3]. As in our framework, the authors of [34] 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 [31], 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.

<footnote><sup>a</sup>Université Caen Normandie, ENSICAEN, CNRS, Normandie Univ; GREYC UMR6072, F-14000 Caen, France</footnote>

<footnote><sup>b</sup>Université de Lorraine, CNRS, Inria; LORIA, F-54000 Nancy, France</footnote>

<footnote>* Corresponding Author. Email: geoffrey.laforest@unicaen.fr.</footnote>
In [28], 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 [24]. 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 [30], have been developed to exploit factored representations. Another representation of policies is by a finite-state controller (FSC). In [13], 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 [1] 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 [2]. They are often integrated in another architecture to make predictions, such as Deep Q-Networks [27]. Carefully designed and tuned, they can be a strong baseline for many POMDPs [29]. 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 [23]. This results in a more compact but approximated policy.

Finally, close to our work is the work on knowledge-based programs [21, 35], 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 $\mathcal{S}$, we write $\mathcal{P}(\mathcal{S})$ for the set of all subsets of $\mathcal{S}$, and $\Delta(\mathcal{S})$ for the probability simplex over $\mathcal{S}$. Given a distribution $\delta$, we write $x \sim \delta$ to denote random variable $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) [17] is a tuple $(\mathcal{S}, \mathcal{A}, \mathcal{O}, T, Z, R, b_0, \gamma)$, where $\mathcal{S}, \mathcal{A}, \mathcal{O}$ are finite sets of states, actions, and observations, resp.; for all $s \in \mathcal{S}$ and $a \in \mathcal{A}$, $T_{s,a} \in \Delta(\mathcal{S})$ is the distribution of next states when action $a$ is taken in state $s$; for all $s \in \mathcal{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(\mathcal{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 := (a_0, o_0, \dots, a_t, o_t)$. 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 $(\mathcal{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 = (a_0, o_0, \dots, a_t, o_t)$ therefore induces a probability distribution $\text{bs}(h)$ over $\mathcal{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(\mathcal{S}))$. The belief state $\text{bs}(h)$ for $h := (a_0, o_0, \dots, a_t, o_t)$ can be computed through Bayesian update: $\text{bs}(\langle \rangle) = b_0$, and for $u \le t$, writing $b_u$ for $\text{bs}((a_0, o_0, \dots, a_{u-1}, o_{u-1}))$,

$$b_{u+1}(s_{u+1}) := \eta \sum_{s_u \in \mathcal{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: \mathcal{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 [17, §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: $\text{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$); $\text{switch}_-$ deterministically maps each $s_{xy}$ to $s_{(1-x)y}$, yielding observation void; $\text{noop}$ does not change the state and yields observation void. Finally, $b_0$ is the uniform distribution $b^{\text{unif}}$ over $\mathcal{S}$, and $R_{\cdot, \cdot, s'}$ is 1 for $s' \in \{s_{00}, s_{11}\}$, 0 otherwise.

Then $b^- := \langle \text{check}_-, \text{false}, \text{switch}_-, \text{void} \rangle$ is a history, inducing the belief state $b^- := \text{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}}) := \{\text{check}_-, \text{noop}\}$, $p(b^\neq) := \{\text{switch}_-, \text{noop}\}$, and $p(b^-) = \{\text{check}_-, \text{noop}\}$.<fnref n="2" /> Then $p$ is a (nonoptimal) belief-based policy, inducing, for example, $\text{pol}(p)(h^-) := p(b^-) = \{\text{check}_-, \text{noop}\}$. □

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) [25, 14, 13]. A (nondeterministic) FSC consists of a set of nodes $N$ among which a distinguished set of initial nodes $N_0$, an action mapping $\text{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)^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) :=$

<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>
$\text{argmax}_{a \in A}(\max_{\alpha \in \Gamma_a} 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 POMDP, we define an epistemic feature to be a function $\varphi: 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 \mathbb{B}$, where $\mathbb{B} := \{0, 1\}$ (false and true). Such state features are typically readily available (e.g., from a fac- tored 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($\neg x$), B($\neg y$); the first two are positive, the last two are not. For $w = 2$, the epistemic clauses are B($x \lor y$), B($\neg x \lor \neg y$), B($x \lor \neg y$), and B($\neg x \lor 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{1}{2}$, 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.

**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 un-ambiguously 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 := \{\text{b}^{\text{unif}}, \text{b}^{\neq}, \text{b}^{=}\}$ is the set of belief states reachable by policy $p$. The policy $p_1$ defined by $p_1(\text{b}^{\text{unif}}) := \{\text{check}_=\}$, $p_1(\text{b}^{\neq}) := \{\text{switch}_x\}$, and $p_1(\text{b}^{=}) := \{\text{check}=, \text{noop}\}$ is a specialization of $p$ (relative to $B$ and $\text{b}^{\text{unif}}$). The policy $p_2$ defined by $p_2(\text{b}^{\text{unif}}) := \{\text{noop}\}$ (and undefined on other belief states) is also a (nonoptimal) specialization of $p$, as only $\text{b}^{\text{unif}}$ is reachable from $\text{b}^{\text{unif}}$ by $p_2$ (and $\emptyset \subset p_2(\text{b}^{\text{unif}}) \subseteq p(\text{b}^{\text{unif}})$ holds). $\square$

By the properties of the belief space [17], any specialization of an optimal belief-based policy is also optimal. More generally, 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 $(\text{Bx})(b) = (\text{By})(b) = (\text{B}(\neg x))(b) = (\text{B}(\neg y))(b) = \frac{1}{2}$ for $b \in \{\text{b}^{\text{unif}}, \text{b}^{=}, \text{b}^{\neq}\}$, hence

$$ \Phi_F^{\vee,1}(\text{b}^{\text{unif}}) = \Phi_F^{\vee,1}(\text{b}^{=}) = \Phi_F^{\vee,1}(\text{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 $\text{b}^{\text{unif}}$ and $\text{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}, \text{B}(x \land y)\}$, since the value $v_3$ of the third feature is already different on all three belief states (it is $\frac{1}{4}$ on $\text{b}^{\text{unif}}$, $\frac{1}{2}$ on $\text{b}^{=}$, and $0$ on $\text{b}^{\neq}$). 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" />

<footnote n="4">⁴ Latin (resp. Greek) letters are for state (resp. epistemic) features/formulas.</footnote>

<footnote n="5">⁵ Proofs of all claims are given in the extended version [20] (Appendix A).</footnote>
**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 to $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 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 pre dicting any of the given labels is correct (nonexact projectability); it is however free to generalize to belief states outside of $B$.

**Example 6 (continued).** Consider again $B = \{b^{\text{unif}}, b^{=}, b^{\neq}\}$, $\Phi = \Phi_F^{\wedge^{+,1}} \cup \Phi_F^{\wedge^{+,2}}$ ordered as $(\text{Bx}, \text{By}, \text{B}(\times \wedge 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 in- terpretability in mind, we focus on decision tree classifiers, branch- ing 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: B \to \mathcal{P}(A)$, we first sample a deterministic policy $\tilde{p}: B \to A$ by choosing an action independently and uniformly at random from $p(b)$, for each $b \in 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$

<figure><img src="image_1.png" /><figcaption>**Figure 1.** Decision tree representation of the specialization $\pi'$ of $p$.</figcaption></figure>

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 B$. We then restrict $p$ to a 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 $\{(\Phi(b), \tilde{\pi}(\Phi(b))) \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 [4]. Still, this is of course more costly than, for instance, following an arc in a finite-state controller. Hence epistemic representations come with a trade-off between efficiency at execution time and interpretability. This is reminiscent of other epistemic approaches to representing policies, like (probabilistic) knowledge-based programs [21, 35].

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.

<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>
# 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 [19],<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 Φ of epistemic features, we decide whether *p* is projectable, and if yes, redescribe it into a decision tree *ρ* over Φ.

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 [13] 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 $Bf$ (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 the extended version [20] (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. 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 the extended version [20] (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).

<figure><img src="image_2.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>

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).

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

<footnote n="8">⁸ https://github.com/AdaCompNUS/sarsop</footnote>
<figure><img src="image_3.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>

<figure><img src="image_4.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>

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) $\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 conclusions (see §9).

<figure><img src="image_5.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>

## 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$.

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 = 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(x \land 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 $x \land y$ is true, than the test $B(x \land 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 *s* promoting (resp. demoting) for a test $B_g \ge \theta$ ($\theta > 0$) if it satisfies (resp. does not satisfy) *g*, and similarly for
<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=.</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>

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, B_{a12} \ge .10, B_{g20} \le .12, B_{g22} \le .11, B_{w10} \in [.10, .25], B_{w21} \le .10, B_{w00} \in [.12, .25]$

* promoting states:

<table><tr><td>a</td><td>w</td><td>g</td><td>w</td><td>w</td><td>g</td><td>w</td></tr><tr><td>g</td><td>w</td><td></td><td></td><td>a</td><td>a</td><td></td></tr><tr><td></td><td></td><td>a</td><td></td><td></td><td></td><td></td></tr></table>

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, Bg_{00} \uparrow .01, Bg_{01} \uparrow .01, Bg_{02} \uparrow .01, Bg_{20} \downarrow .11, Bg_{21} \uparrow .03, Bg_{22} \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:

<table><tr><td>w</td><td>g</td><td></td><td>g</td><td></td><td>w</td><td></td><td></td><td></td></tr><tr><td>a</td><td></td><td></td><td>a</td><td>w</td><td></td><td></td><td></td><td></td></tr><tr><td></td><td></td><td></td><td>a</td><td>g</td><td></td><td></td><td></td><td></td></tr><tr><td></td><td></td><td></td><td>a</td><td>g</td><td></td><td>w</td><td></td><td></td></tr><tr><td></td><td></td><td></td><td>a</td><td></td><td></td><td>a</td><td>w</td><td></td></tr><tr><td></td><td></td><td></td><td>a</td><td></td><td></td><td></td><td>a</td><td>w</td></tr></table>

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 epistemic features, with the goal of improving interpretability. For this we take a classifier (here, a decision tree) as a representation of the policy. Our experiments show that our approach has the potential to yield representations on par with finite-state controllers in terms of size and computation time, while hopefully 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 [30] and factored belief tracking [4]. 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 [28].

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
Reasearch (ANR) through grant ANR-22-CE23-0029.

## References

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

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

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

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

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

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

[7] F. Doshi-Velez and B. Kim. Considerations for evaluation and generalization in interpretable machine learning. In H. J. Escalante, S. Escalera, I. Guyon, X. Baró, Y. Güçlütürk, U. Güçlü, and M. van Gerven, editors, Explainable and Explainable Models in Computer Vision and Machine Learning, pages 3–17. Springer International Publishing, Cham, 2018.

[8] M. Du, N. Liu, and X. Hu. Techniques for interpretable machine learning. Communications of the ACM, 63(1):68–77, 2020.

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

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

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

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

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

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

[15] J. Huang, P. P. Angelov, and C. Yin. Interpretable policies for reinforcement learning with empirical fuzzy sets. Engineering Applications of Artificial Intelligence, 91, 2020.

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

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

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

[19] H. Kurniawati, D. Hsu, and W. S. Lee. SARSOP: Efficient point-based POMDP planning by approximating optimally reachable belief spaces. In Proc. Robotics: Science and Systems IV. MIT Press, 2008.

[20] G. Laforest, O. Buffet, A. Niveau, and B. Zanuttini. Post-hoc interpretation of POMDP policies (extended version). Technical report, Université de Caen Normandie, 2025. URL https://hal.science/hal-05180842.

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

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

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

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

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

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

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

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

[29] T. Ni, B. Eysenbach, and R. Salakhutdinov. Recurrent model-free RL can be a strong baseline for many POMDPs. In K. Chaudhuri, S. Jegelka, L. Song, C. Szepesvári, G. Niu, and S. Sabato, editors, Proc. 39th International Conference on Machine Learning (ICML 2022), volume 162 of Proceedings of Machine Learning Research, pages 16691–16723, 2022.

[30] P. Poupart. Exploiting Structure to Efficiently Solve Large Scale Partially Observable Markov Decision Processes. PhD thesis, University of Toronto, 2005.

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

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

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

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

[35] B. Zanuttini, J. Lang, A. Saffidine, and F. Schwarzentruber. Knowledge-based programs as succinct policies for partially observable domains. Artificial Intelligence, 288, 2020.