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

HAL
open science

# Observer-Aware Probabilistic Planning Under Partial Observability

Salomé Lepers, Vincent Thomas, Olivier Buffet

► To cite this version:

Salomé Lepers, Vincent Thomas, Olivier Buffet. Observer-Aware Probabilistic Planning Under Partial Observability. 2025. hal-05380088

HAL Id: hal-05380088

https://inria.hal.science/hal-05380088v1

Preprint submitted on 24 Nov 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.

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

Distributed under a Creative Commons Attribution 4.0 International License
OBSERVER-AWARE PROBABILISTIC PLANNING
UNDER PARTIAL OBSERVABILITY

A PREPRINT

Salomé Lepers¹

Vincent Thomas¹

Olivier Buffet¹

(1)Université de Lorraine, CNRS, Inria, LORIA, F-54000 Nancy, France

November 24, 2025

ABSTRACT

In this article, we are interested in planning problems where the agent is aware of the presence of an observer, and where this observer is in a partial observability situation. The agent has to choose its strategy so as to optimize the information transmitted by observations. Building on observer-aware Markov decision processes (OAMDPs), we propose a framework to handle this type of problems and thus formalize properties such as legibility, explicability and predictability. This extension of OAMDPs to partial observability can not only handle more realistic problems, but also permits considering dynamic hidden variables of interest. These dynamic target variables allow, for instance, working with predictability, or with legibility problems where the goal might change during execution. We discuss theoretical properties of PO-OAMDPs and, experimenting with benchmark problems, we analyze HSVI's convergence behavior with dedicated initializations and study the resulting strategies.

# 1 Introduction

As explained by Klein et al. [2004], efficient and safe human-agent collaboration requires behaviors that carry information such as intentions, abilities, current status or upcoming actions (see also [Schadenberg et al., 2021, Singamaneni et al., 2024]). Various works in manipulation or mobile robotics try to derive behaviors with such properties [Dragan and Srinivasa, 2013, Dragan et al., 2013, Fisac et al., 2020, Beetz et al., 2010, Angelopoulos et al., 2022]. An alternative is to explicitly communicate through language with the human [Gong and Zhang, 2018].

Here we consider an agent (robot or otherwise) observed by a passive human, as in Figure 1 (left). In this setting, Chakraborti et al. [2019, 2018] build on previous work to derive a taxonomy of the concepts behind such information communication through the behavior. In particular, they distinguish between

1. transmitting information, with properties such as *legibility* (legible behaviors convey intentions, i.e., actual task at hand, via action choices), *explicability* (explicable behaviors conform to observers’ expectations, i.e., they appear to have some purpose), and *predictability* (a behavior is predictable if it is easy to guess the end of an on-going trajectory); or

2. hiding information, as through *obfuscation*, when the agent tries to hide its actual goal.

They propose a general framework for such problems while assuming deterministic dynamics, and work mostly with plans (a sequence of actions, which induces a sequence of states). In their approach, the human is modeled by the robot as having a model of the robot+environment system (including the robot’s possible tasks), and is thus able to predict the robot’s behavior.

Miura and Zilberstein [2021] build a unifying framework while assuming stochastic transitions, namely *observer-aware Markov decision processes* (OAMDPs), adopting a similar approach as Chakraborti et al. [2019], as illustrated in Figure 1. Among other things, their work also covers legibility, explicability, and predictability. To better handle predictability, Lepers et al. [2024] have recently proposed an approach that does not reason with complete trajectories, but with actions or states at each time step, thus being better suited to stochastic dynamics. This implies reasoning on dynamic target variables, which requires introducing a variant of the OAMDP formalism, namely the pOAMDP (predictable OAMDP).
<figure><img src="image_3.png" /><figcaption>Figure 1: An OAMDP agent (3) assumes that the observer expects (2) the agent to behave so as to achieve some task (1).</figcaption></figure>

This paper proposes a formalism that can handle both 1. problems with a static type (e.g., legibility, explicability as with OAMDPs) or a dynamic one (predictability as with pOAMDPs), and 2. problems with partial observability. In this last situation, the observer may not have access to the state and the action of the agent but to an observation that depends on the transition, but the agent has access to all information, including the observer's observation. Introducing partial observability allows considering more diverse and more realistic scenarios. For example, one can consider settings where the PO-OAMDP agent is not always visible and needs to choose between several paths to be seen by the observer and allow her to better infer the current situation.

Section 2 provides background on Markov decision processes and observer-aware MDPs. The PO-OAMDP formalism is introduced in Sec. 3, before discussing theoretical properties of PO-OAMDPs and an example solving algorithm in Sec. 4, presenting illustrative experiments in Sec. 5, and concluding in Sec. 6.

# 2 Background

## 2.1 Markov Decision Processes

A Markov decision process (MDP) [Bellman, 1957, Bertsekas, 2005] is specified through a tuple $\langle S, A, T, R, \gamma, S_f \rangle$ where: $S$ is a finite set of states; $A$ is a finite set of actions; $T: S \times A \times S \to [0; 1]$, the transition function, gives the probability $T(s, a, s')$ that action $a$ performed in state $s$ will lead to state $s'$; $R: S \times A \times S \to \mathbb{R}$, the reward function, gives the immediate reward $R(s, a, s')$ received upon transition $(s, a, s')$; $\gamma \in [0, 1]$ is a discount factor; and $S_f \subset S$ is a set of terminal states: for all $s, a \in S_f \times A$, $T(s, a, s) = 1$ and $R(s, a, s) = 0$.

Then, a (stochastic) policy $\pi: S \to \Delta(\mathcal{A})$ maps states to distributions over actions, $\pi(a|s)$ denoting the probability to perform $a$ when in $s$. When a policy is deterministic, $\pi$ denotes the only possible action in $s$. Assuming $\gamma < 1$, the value of a policy $\pi$ is the sum of discounted rewards over an infinite horizon:

$$V^{\pi}(s) \triangleq \mathbb{E}_{\pi} \left[ \sum_{t=0}^{\infty} \gamma^t r(S_t, A_t) | S_0 = s \right],$$

and an optimal policy $\pi^*$ is such that, for all $s$, $V^{\pi^*}(s) = \max_{\pi} V^{\pi}(s)$.

The value iteration (VI) algorithm approximates $V^*$, the value function common to all optimal policies, by iterating the following computation (where $k$ is the current iteration):

$$V_{k+1}(s) \leftarrow \max_a \sum_{s'} T(s, a, s') \cdot (R(s, a, s') + \gamma V_k(s')).$$
Calculations stop when the *Bellman residual* is below a threshold: $\max_s |V_{k+1}(s) - V_k(s)| \le \frac{1-\gamma}{\gamma} \epsilon$, an $\epsilon$-optimal deterministic policy being then obtained by acting greedily with respect to the solution value function $V_k$, i.e., using

$$ \pi^*(s) \leftarrow \arg\max_a \sum_{s'} T(s, a, s') \cdot (R(s, a, s') + \gamma V^*(s')). $$

These properties remain valid with $\gamma = 1$ if

1. $S_f$ is not empty; and

2. $R$ is such that there exists at least one policy that reaches $S_f$ with probability 1 from any state $s$, and that the value of other policies diverge towards $-\infty$ in states from which $S_f$ is reachable with probability $< 1$.

Such problems are called *Stochastic Shortest Path problems* (SSPs). In particular, we have an SSP if, for all $(s, a, s') \in (S \setminus S_f) \times A \times S$, we have $r(s, a, s') < 0$, meaning that we are trying to reach a terminal state at “minimum cost” (on average).

Note: SSPs are more general than MDPs because any MDP can be turned into an SSP with, at any time step, a $1 - \gamma$ probability to transition to a terminal state.

## 2.2 Observer-Aware Markov Decision Processes

An *Observer-Aware MDP* (OAMDP) [Miura and Zilberstein, 2021] models a situation wherein an agent is aware of the presence of an external observer, and interacts with its environment while attempting to maximize a performance criterion linked to the observer’s belief about the agent’s “type”, the *belief* about some variable being the probability distribution over this variable’s possible values.

An OAMDP is formalized by a tuple $\langle S, s_0, A, T, \gamma, S_f, \Theta, B, R_{AG} \rangle$ where:

* $\langle S, s_0, A, T, \gamma, S_f \rangle$ is an MDP with an initial state $s_0$ but no reward function;

* $\Theta$ is a finite set of types representing a characteristic of the agent such as possible goals, intentions or capabilities;

* $B: H^* \to \Delta(\Theta)$ gives the assumed belief of the observer (about the agent’s type) given a state-action history;

* $R_{AG}: S \times A \times \Delta(\Theta) \to \mathbb{R}$ is the agent’s reward function.

In most of the cases they consider, Miura and Zilberstein derive $B$ by relying on Baker et al.’s “BST” Bayesian belief update rule [Baker et al., 2009], i.e., considering that, again from the agent’s viewpoint, the observer models the agent’s behavior for a given type $\theta$ through an MDP by:

1. using a corresponding reward function $R_{\text{OBS}}^{\theta}$;

2. solving MDP $\langle S, s_0, A, T^\theta, R_{\text{OBS}}^\theta, \gamma, S_f^\theta \rangle$ (where $S, A$ and $\gamma$ are as in the OAMDP definition) to obtain $V_{\text{OBS}}^{*,\theta}$ for states reachable from $s_0$; and

3. building a stochastic “softmax” policy $\pi_{\text{OBS}}^\theta$ such that, $\forall (s, a)$,

$$ \pi_{\text{OBS}}^{\theta}(a|s) \triangleq \frac{e^{\frac{1}{\tau} Q_{\text{OBS}}^{*,\theta}(s,a)}}{\sum_{a'} e^{\frac{1}{\tau} Q_{\text{OBS}}^{*,\theta}(s,a')}}, $$

where $Q_{\text{OBS}}^{*,\theta}(s, a) \triangleq \sum_{s'} T^\theta(s, a, s') \cdot (R_{\text{OBS}}^\theta(s, a, s') + \gamma V_{\text{OBS}}^{*,\theta}(s'))$, and temperature $\tau > 0$ allows tuning the policy’s optimality (thus the agent’s assumed rationality for the observer).

The observer belief about the type can thus be obtained by Bayesian inference using $\pi_{\text{OBS}}^\theta$. Note that, unless, for some $\theta$, we have $T = T^\theta$, $R_{AG} = R_{\text{OBS}}^\theta$, and $S_f = S_f^\theta$, then there will likely be no perfect match between the agent’s behavior and any of the types. Miura and Zilberstein used this framework to formalize various observer-aware problems including legibility, explicability and predictability.

Note: As done previously, “OBS” is used to denote quantities associated to the observer viewpoint (as perceived by the agent), such as probabilities, denoted $P_{\text{OBS}}$. Also, we will sometimes write a function $f(X, Y)$ describing a conditional probability distribution under the form $f(Y|X)$ to exhibit the dependence between variables.

## 3 OAMDPs with Partial Observability

This section introduces the PO-OAMDP formalism, shows how the observer’s belief about the target variable is maintained, and looks at some typical use cases.
## 3.1 Formalism

We describe the key ingredients of the PO-OAMDP framework before providing a formal definition. 1. Within the PO-OAMDP framework, the agent has access to the complete state of the system, while the observer now only has a partial perception. A set of observations and an observation function are thus added to the OAMDP formalism. 2. In this context, the type is replaced by a target variable which can change over time, contrary to OAMDP's static types. For the definition of the target variable to be as generic as possible, its value at each time step is a function of the transition followed by the system. The target variable can thus be a part of the system state (e.g., a non-observable variable for the observer), but it can also be linked to the action performed by the agent (for predictability), or to the state transition rather than to the state itself. This variable can also gather several different variables. But considering a single variable is without loss of generality. 3. Additionally, we assume that the agent has access not only to the complete state of the system, but also to the observations received by the observer (this is realistic in particular if the observation process is deterministic: in that case the observations received by the observer are easy to predict). The agent can thus build the mental state of the observer during the execution of its behavior. By having access to all of the problem's information (the system state, the chosen action and the observations perceived by the observer), the agent can make decisions to control the observer's inference about the target variable.

Formally, a PO-OAMDP is defined by a tuple $\langle S, s_0, A, T, \gamma, S_f, \Psi, \Omega, O, B, R_{AG}, \phi \rangle$, where:

* $\langle S, s_0, A, T, \gamma, S_f \rangle$ is an MDP with an initial state $s_0$ but no reward function;

* $\Psi$ denotes both the (dynamic) target variable and the finite set of values it can take;

* $\phi: S \times A \times S \to \Psi$ is a function that gives the value of the target variable given the transition: $\psi_t = \phi(s_t, a_t, s_{t+1})$;

* $\Omega$ is the finite set of observations;

* $O: A \times S \times \Omega \to \mathbb{R}$ is the observation function; $O(a, s', o)$ is the probability of emitting observation $o$ if state $s'$ is reached while performing $a$;

* $B: \Omega^* \to \Delta(S)$ gives the observer's belief on the state given an observation history; the belief on the target variable can be deduced from that state belief (see Sec. 3.2), denoted $b$;

* $R_{AG}: S \times \Delta(\Psi) \times A \times S \times \Delta(\Psi) \to \mathbb{R}$ is the agent's reward function under its most general form: $R_{AG}(s_t, \beta_t, a_t, s_{t+1}, \beta_{t+1})$, where $\beta$ denotes a target belief.

Here, we assume that, through her observations, the observer knows at each time step whether a terminal state has been reached or not, without necessarily indicating which terminal state is concerned.

Unlike the OAMDP model, which needs an MDP for each possible type, the PO-OAMDP model is based on a single MDP. However, within our framework with partial observability, using only one MDP is not restrictive, and, as discussed in Sec. 3.4, any OAMDP can provably be turned into an equivalent PO-OAMDP.

The next subsection describes how the observer's belief (on the state) can be updated and how the belief on the target variable is deduced, which is used to evaluate the agent's reward attached to a transition. Then, it illustrates the use of the PO-OAMDP formalism to model different scenarios.

## 3.2 State- and Target-Belief Computation

**BST belief state update** Following Miura and Zilberstein, we employ the BST Bayesian belief update rule [Baker et al., 2009], thus introduce a reward function $R_{OBS}: S \times A \times S \to \mathbb{R}$ assumed to be the agent's reward function according to the observer. Then, the observer models the agent's behavior for a given task through an MDP by: 1. solving the MDP with reward $R_{OBS}$; and 2. deriving a softmax policy $\pi_{OBS}$.

Note that, given the dynamics (transition + observation) of the PO-OAMDP and the presumed policy $\pi_{OBS}$ of the agent, the observer faces a hidden Markov model (HMM) [Rabiner, 1989]: she solves a filtering problem, using the observation's history $o_{1:t}$ to estimate her belief on the state $s_t$. The observer belief can thus be computed with:

$$ 
\begin{aligned}
B(s_{t+1}|o_{1:t+1}) &= P(s_{t+1}|o_{1:t+1}) = \frac{P(s_{t+1}, o_{1:t+1})}{\sum_{s_{t+1}} P(s_{t+1}, o_{1:t+1})} \\
&= \frac{K(s_{t+1}, o_{1:t+1})P(o_{1:t})}{\sum_{s_{t+1}} K(s_{t+1}, o_{1:t+1})P(o_{1:t})}, \text{ where} \\
K(s_{t+1}, o_{1:t+1}) &\triangleq \sum_{a_t} O(o_{t+1}|a_t, s_{t+1}) \sum_{s_t} T(s_{t+1}|s_t, a_t) \cdot \\
& \qquad \pi_{OBS}(a_t|s_t) \cdot B(s_t|o_{1:t}).
\end{aligned}
$$
**Belief on the target variable** To evaluate the reward received during a transition, we need to evaluate the belief $\beta$ on the value that will be taken by the target value: $\Psi_t = \phi(S_t, A_t, S_{t+1})$. This can be done by starting with the observer's belief $b$ on the current state, $S_t$:

$$ 
\begin{aligned}
\beta(\psi) &= \sum_{s,a,s'} \mathbb{1}_{\psi=\phi(s,a,s')} \cdot P_{\text{OBS}}(s, a, s'|b) \\
&= \sum_{s,a,s'} \mathbb{1}_{\psi=\phi(s,a,s')} \cdot P_{\text{OBS}}(s'|s, a) \cdot P_{\text{OBS}}(a|s) \cdot P_{\text{OBS}}(s|b) \\
&= \sum_{s,a,s'} \mathbb{1}_{\psi=\phi(s,a,s')} \cdot T(s, a, s') \cdot \pi_{\text{OBS}}(a|s) \cdot b(s),
\end{aligned}
\quad (1) $$

where $\mathbb{1}_*$ is the indicator function.

### 3.3 Relationship with POMDPs

Despite similarities between POMDP and PO-OAMDP there are some key differences:

1. in PO-OAMDPs, the reward function is typically not linear in belief space,

2. in PO-OAMDPs, the agent reasons about the observer's belief rather than its own belief, so that POMDPs are not a subclass of PO-OAMDPs. Also, the Bellman optimality operator for PO-OAMDPs does not preserve piecewise linearity and convexity as in POMDPs. The optimal value function may even exhibit local discontinuities (a property inherited from OAMDPs).

### 3.4 Implementation on Various Scenarios

The PO-OAMDP model allows us to generate different behaviors by changing $\Psi$ and $R$, and to work with different types of problems. An important property, formally demonstrated in Section A, shows that PO-OAMDPs are at least as expressive as OAMDPs.

**Proposition 1.** Any OAMDP $\mathcal{M}$ with BST belief update can be turned into an equivalent PO-OAMDP $\mathcal{M}'$, i.e., such that an optimal solution to one problem is optimal for the other problem.

A starting point of the proof is to turn the static type of an OAMDP into a (hidden) target state variable. The following shows how to formulate legibility, explicability, and (state/action) predictability while assuming (for the sake of clarity) that the transition and observation functions do not depend on the type.

**Legibility** Assuming several possible objectives for the agent, legibility aims at reducing the observer's uncertainty about the agent's actual objective.

The target variable is thus part of the state, indicating the objective among a finite set of possible objectives, and the *observer* reward function $R_{\text{OBS}}$ depends on the target. For the *agent* reward function, Miura and Zilberstein use the opposite of the Euclidean distance to the “ideal belief”. The ideal belief being defined by: $\beta^*(s) = (0, \dots, 0, 1, 0, \dots, 0)$ (with a 1 for component $\psi = \phi(s)$), we thus have, for $R_{\text{AG}}$:

$$ R_{\text{leg}}(s, \beta, a, s', \beta') \triangleq -\|\beta - \beta^*(s)\|_2. $$

**Explicability** Assuming one or several possible objectives, an explicable behavior is a behavior coherent with the observer's expectations.

To express this idea, Miura and Zilberstein (following Sreedharan et al. [2020]) propose minimizing the probability that the observed behavior corresponds to a random behavior, even if multiple behaviors are still likely. As they do, we thus introduce a “virtual” target value $\psi_0$ (in addition to the ones used for legibility) that corresponds to a random behavior (policy) in addition to the other (real) target values. Then, the explicability criterion described above is obtained using

$$ R_{\text{exp}}(s, \beta, a, s', \beta') \triangleq -\beta(\psi_0). $$

**Predictability** A predictable behavior is typically a behavior whose end of trajectory is easy for the observer to guess. Miura and Zilberstein's discussion on predictability, which relies on work for deterministic settings and thus reasons on complete trajectories, does not provide a very convenient way of formalizing predictability under stochastic dynamics. We rely instead on Lepers et al.'s work [Lepers et al., 2024], as they propose a more satisfying approach relying on step-by-step predictions.

The starting point is that the observer tries, at each time step, to predict either the next action, or the next state, hence two different types of predictability. For action predictability, we set $\Psi = A$ and $\phi(s, a, s') = a$. For state
predictability, we set $\Psi = S$ and $\phi(s, a, s') = s'$. In both cases, to act optimally, the observer has to bet on the most probable next target values, and thus pick a value in the set of candidate values

$$C_{\Psi}(\beta_t) \triangleq \arg\max_{\psi} \beta_t(\psi).$$

Considering that the observer samples her prediction uniformly at random in the set $C_{\Psi}(\beta_t)$, the probability that $\psi$ is predicted is:

$$\mathrm{pred}(\psi|\beta_t) \triangleq \frac{1}{|C_{\Psi}(\beta_t)|} \cdot \mathbb{1}_{\psi \in C_{\Psi}(\beta_t)}.$$

Then, defining

$$R_{a-\mathrm{pred}}(s, \beta, a, s', \beta') \triangleq \mathrm{pred}(a|\beta) - 1, \text{ or}$$

$$R_{s-\mathrm{pred}}(s, \beta, a, s', \beta') \triangleq \mathrm{pred}(s'|\beta) - 1,$$

the immediate reward is the opposite of the probability that, under the current transition, the bet of a rational observer will fail: $R_{a-\mathrm{pred}}(s, \beta, a, s', \beta') = -P(\text{failed rational bet})$.

Note: Other example scenarios formalized as PO-OAMDPs are presented in supplementary material, Section C. They illustrate, among other things, the similarities with $\rho$-POMDPs [Araya-López et al., 2010], a variant of the POMDP formalism where an agent's reward function depends on its own belief, which permits modeling active information-gathering problems. Yet, the same differences between OAMDPs and $\rho$-POMDPs pointed out by Miura and Zilberstein [Miura and Zilberstein, 2021] still hold between PO-OAMDPs and $\rho$-POMDPs.

# 4 Resolution

## 4.1 Sequential Decision-Making Problem

An OAMDP can be turned into an equivalent MDP using the state-action history $\langle s_{0:t}, a_{1:t} \rangle$ (i.e., all the raw information available to the agent at $t$) as information state, or the state-belief (over type) pair $\langle s, \beta \rangle$ when using the BST update [Miura and Zilberstein, 2021, Miura et al., 2024].

Similarly, in a PO-OAMDP, the raw information available at $t$ is the state-action-observation history $\langle s_{0:t}, a_{1:t}, o_{1:t} \rangle$. Yet, note that:

(1) the pair $\langle s_t, o_{1:t} \rangle$ induces a Markov process; and

(2) the observer's beliefs ($b_t$, thus also $\beta_t$) depend on the observation history $o_{1:t} \equiv \langle o_1, \dots, o_t \rangle$;

(3) the reward is a function of the state and the target belief, thus of the observation history, not of the past states and actions.

From (1) and (3), the state and observation history pair $\langle s_t, o_{1:t} \rangle$ is a sufficient statistic for optimal decision-making. What is more, when using the BST update, the state belief is Markovian (though not the target belief in general), so that $\langle s_t, b_t \rangle$ can be used instead.

Formally, we obtain an MDP $\langle \mathcal{I}, i_0, \mathcal{A}, T', R', \gamma, \mathcal{I}_f \rangle$, where:

* $\mathcal{I} \triangleq S \times B$ is the (infinite) set of states, with $i_0 = \langle s_0, b_0 \rangle$ the initial state;

* $\mathcal{A}$ is the PO-OAMDP's set of actions;

* $T' : \mathcal{I} \times \mathcal{A} \times \mathcal{I} \to [0; 1]$ is the transition function defined by:

$$T'(i'|i, a) \triangleq \mathrm{Pr}(s', b'|s, b, a) \\ = \sum_o \mathbb{1}_{b'=B(b,o)} \mathrm{O}(o|s', a) \mathrm{P}(s'|a, s);$$

* $R' : \mathcal{I} \times \mathcal{A} \times \mathcal{I} \to \mathbb{R}$ is the reward function defined by:

$$R'(s, b, a, s', b') \triangleq R_{\mathrm{AG}}(s, \beta(b), a, s', \beta(b')),$$

where $\beta(b)$ is the target belief that can be derived from $b$ as seen in Equation (1);

* $\gamma \in [0, 1]$ is the discount factor; and

* $\mathcal{I}_f \subset \mathcal{I}$ is the set of elements $\langle s, b \rangle$ in $\mathcal{I}$ such that $s \in S_f$.
We assume that $R_{AG}(s, \beta(b), a, s', \beta(b')) = 0$ whenever $s \in S_f$. As a consequence, when $i \equiv \langle s, b \rangle \in I_f$ is reached, since the state $s$ does not change anymore, and even if the state belief may still evolve, all future rewards will be null, so that we are in a “terminal sub-set of states”.

In this setting, Bellman’s optimality operator is thus written

$$V^*(i) = \max_a \sum_{i' \in \text{nxt}(i, a)} T'(i, a, i') \cdot [R'(i, a, i') + \gamma V^*(i')],$$

where nxt(i, a) is the (finite) set of possible next state-belief pairs when performing a in i.

## 4.2 SSPs

Setting $\gamma = 1$ raises the question whether the resulting problem is a valid SSP. The following proposition answers positively while considering problems with a possibly infinite set of states reachable from initial state $\langle s_0, - \rangle$, where $-$ denotes the empty history.

**Proposition 2.** *Assuming that $R_{AG}$ is bounded from above by $R_{AG}^{\max} < 0$ (in non-terminal states), the PO-OASSP is a valid SSP.*

*Proof.* First, any reachable pair $\langle s, o_{1:t} \rangle$ with $s \in S_f$ is a terminal state of the PO-OASSP.

Then, let $\hat{\pi}$ be a proper policy of the observer SSP. When in $\langle s, o_{1:t} \rangle$, one can apply $\hat{\pi}$ (thus ignoring observation histories), thus ensuring that a terminal state of the SSP is reached, which corresponds to a terminal state of the PO-OASSP.

In the contrary, if, from $\langle s, o_{1:t} \rangle$, one applies a policy $\pi$ that reaches a terminal state only with probability $p < 1$, then there is a probability $1-p$ to follow an infinite trajectory with a per-step cost $R_{AG}^{\max} < 0$, so that the value at $\langle s, o_{1:t} \rangle$ diverges to $-\infty$. □

Note that ensuring that $R_{AG}$ only takes negative values is not sufficient to prove the above lemma, as not all infinite sums of negative values diverge. For the $R_{AG}$ functions described in Sec. 3 for legibility, explicability and predictability, the least upper-bound is 0, so that it is unclear whether all improper policies have diverging values. In particular, Lepers et al.’s Proposition 2 in [Lepers et al., 2024], which applies in our setting, states that state predictability can lead to an improper policy. A simple trick to come back to a valid SSP is to linearly combine the invalid $R_{AG}$ with a valid $R: S \times A \times S \to \mathbb{R}^-$ using $R'_{AG} = R_{AG} + \lambda \cdot R$ for some small $\lambda > 0$.

## 4.3 Complexity

Proposition 1 tells us that PO-OAMDPs cover a larger class of problems than OAMDPs. Below we establish that PO-OAMDPs inherit the same main complexity results as OAMDPs, results which require assuming *Bayesian updates* for the observer’s belief, what we denote by PO-OAMDP$_{BU}$. Such results are obtained considering the *value problem*, i.e., determining whether a policy exists that can achieve some pre-defined value.

**Theorem 3.** *The finite-horizon value problem for PO-OAMDP$_{BU}$ is PSPACE as long as R can be evaluated using polynomial space.*

*Proof.* As for OAMDP$_{BU}$, a policy’s possible outcomes can be expressed as a tree whose depth corresponds to the finite horizon, and the policy’s value can be computed in polynomial space through a tree traversal (provided R can be evaluated in polynomial space as well). PO-OAMDP$_{BU}$ are thus in PSPACE. □

**Theorem 4.** *The finite-horizon value problem for PO-OAMDP$_{BU}$ is PSPACE-hard.*

*Proof.* The proof of Prop. 1 shows that any OAMDP$_{BU}$ can be turned into a PO-OAMDP$_{BU}$ through a polynomial reduction. Then, as OAMDP$_{BU}$ is PSPACE-hard [Miura and Zilberstein, 2021], so is PO-OAMDP$_{BU}$. □

**Corollary 5.** *The finite-horizon value problem for PO-OAMDP$_{BU}$ is PSPACE-complete when R can be evaluated using polynomial space.*

This is a direct consequence of Theorems 3 and 4.
## 4.4 HSVI

This section proposes solving discounted PO-OAMDPs ($\gamma < 1$) using a variant of Smith and Simmons's heuristic search value iteration (HSVI) algorithm [Smith and Simmons, 2004, 2005, Smith, 2007]. HSVI is generally used to solve POMDPs through equivalent belief MDPs, maintaining an upper and a lower bound of $V^*$, respectively denoted $\bar{V}$ and $\underline{V}$, and whose representations exploit $V^*$'s convexity in belief space. As illustrated in Algorithm 1 (where it is presented for MDPs, thus reasoning on states), these bounds are updated (Algorithm 1) while simulating trajectories in a recursive manner (Algorithm 1), making decisions optimistically (i.e., acting greedily with respect to $\bar{V}$, cf. Algorithm 1) and picking the next transition so as to provably reduce uncertainty about the value (Algorithm 1). It stops when $\bar{V}(b_0) - \underline{V}(b_0) \le \epsilon$ for some positive $\epsilon$ (Algorithm 1).

<caption>**Algorithm 1:** HSVI for (infinite-horizon) MDPs</caption>

**Input** : $s_0$ a state
**Fct Solve**
1. Initialize $\bar{V}: S \to \mathbb{R}$ with optimistic value
2. Initialize $\underline{V}: S \to \mathbb{R}$ with pessimistic value
3. **while** $\bar{V}(s_0) - \underline{V}(s_0) \ge \epsilon$ **do**
4. &nbsp;&nbsp;&nbsp;&nbsp;**Explore**($s_0, 0$)
5. &nbsp;&nbsp;&nbsp;&nbsp;**return** $\underline{V}$
6.
7. **Fct Explore**($s, t$)
8. &nbsp;&nbsp;&nbsp;&nbsp;**if** $\bar{V}(s) - \underline{V}(s) \ge \epsilon\gamma^{-t}$ **then**
9. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**Update**($s, t$)
10. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$a^* \leftarrow \arg\max_a r(s, a) + \gamma \sum_{s'} T(s, a, s')\bar{V}(s')$
11. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$s^* \leftarrow \arg\max_{s'} T(s, a^*, s') [\bar{V}(s') - \underline{V}(s') - \epsilon \cdot \gamma^{-(t+1)}]$
12. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**Explore**($s^*, t+1$)
13. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**Update**($s, t$)
14. &nbsp;&nbsp;&nbsp;&nbsp;**return**
15. **Fct Update**($s, t$)
16. &nbsp;&nbsp;&nbsp;&nbsp;**if** $\bar{V}(s) - \max_a r(s, a) + \gamma \sum_{s'} T(s, a, s')\bar{V}(s') > \underline{V}(s)$
17. &nbsp;&nbsp;&nbsp;&nbsp;**Explore**($s, t$)
18. &nbsp;&nbsp;&nbsp;&nbsp;**Update**($s, t$)
19. &nbsp;&nbsp;&nbsp;&nbsp;**return** $\underline{V}(s')$

Differences between POMDPs and PO-OAMDPs lead to several differences in HSVI. 1. Our setting allows for observable terminal states, so that trajectories can be terminated when one is encountered, and $V^*(i) = 0$ for $i \in S_f$. 2. $\underline{V}$ and $\bar{V}$ are expressed in information space $\mathcal{I} \equiv S \times \Delta(S)$, not in $\Delta(S)$ alone. 3. PO-OAMDPs inherit local discontinuities in $\Delta(S)$ from OAMDPs [Miura et al., 2024, Sec. 3.2], so that we do not attempt to use generalizing representations (which typically rely on continuity properties), but only rely on pointwise representations. 4. Usual bound initializations do not apply, and others need to be introduced, as discussed next.

**Initializing Bounds** As in a standard discounted MDP, a first way to initialize the bounds is simply with, $\forall i, \underline{V}(i) = R'^{\min}/(1-\gamma)$ and $\bar{V}(i) = R'^{\max}/(1-\gamma)$, where $R'^{\min} \triangleq \min_{i,a,i'} R'(i, a, i')$ and $R'^{\max} \triangleq \max_{i,a,i'} R'(i, a, i')$. These naive initializations are very loose, thus far from informative. Usual POMDP bounds rely on properties that do not hold in our setting (in particular the linearity of the reward function in belief space), and thus do not apply here. In the following, we consider that a term that is not belief-dependent (noted $R_s$ and possibly equal to $R_{\text{OBS}}$) can be isolated in the reward function, the other term being denoted $R_b: R'(s, b, a, s', b') = R_s(s, a, s') + R_b(s, b, a, s, b')$, and introduce so-called *combined initializations*.

Our decomposition $R' = R_s + R_b$ allows lower-bounding $R'(i, a, i')$ with $R_s(s, a, s') + R_b^{\min}$, where $R_b^{\min} \triangleq \min_{i,a,i'} R_b(i, a, i')$, so that $V^*(s, b)$ could be lower-bounded by $V_s^{\pi}(s) + R_b^{\min}/(1-\gamma)$, with $\pi$ some policy, for instance the solution $\pi_s^*$ of the MDP equipped with $R_s$. But this lower bound can again be very loose when $\gamma$ is close to 1. To avoid the $\frac{1}{1-\gamma}$ term, we can work with some predefined policy $\pi$ and lower-bound its PO-OAMDP value as

$$V^{\pi}(s, b) \geq V_{s}^{\pi}(s) + R_{b}^{\min} \cdot V_{costToGo}^{\pi}(s), \qquad (2)$$

where $V_s^\pi$ evaluates $\pi$ with $R_s$, and $V_{costToGo}^\pi$ evaluates $\pi$ with $R_{costToGo}(s, a, s') \triangleq \mathbb{1}_{s' \notin S_f}$, i.e., $V_{costToGo}^\pi(s)$ is the average time before reaching a terminal state under $\pi$ if interpreting $1 - \gamma$ as a termination probability at each time step. Two possible choices for $\pi$, the best one depending on the situation at hand, are $\pi_{\text{OBS}}$, so that $V_s^\pi = V_{\text{OBS}}$, and $\pi_s^*$.
To upper-bound $V^*$, a simple approach is to compute $V_s^*$, the optimal value function for the MDP with $R_s$, and then write:

$$V^*(s, b) \leq V_s^*(s) + \frac{R_b^{\max}}{1 - \gamma}, \qquad (3)$$

where $R_b^{\max} \triangleq \max_{i,a,i'} r_b(i, a, i') (= 0$ for all the criteria we presented).

Using $\gamma = 1$, thus for PO-OASSPs, the lower bound (Eq. (2)) requires the initializing policy $\pi$ to be proper, which is true when using $\pi_{OBS}$, $\pi_s^*$, or a uniformly random policy, and the upper bound (Eq. (3)) requires replacing the belief-dependent term with 0.

# 5 Experiments

The conducted experiments will first allow looking at some resulting behaviors, thus demonstrating its possible benefits, and illustrating some encountered phenomena. Then, they will show the influence of problem types and bound initializations on HSVI's runtime. The source code is available at https://gitlab.inria.fr/po-oamdp/po-oamdp_aamas25.

**Baseline Policies** In any given problem instance, we first compute the softmax policy $\pi_{OBS}$ obtained using value iteration and a softmax with a low temperature ($\tau = 0.01$), so that sub-optimal actions are picked with low probability.

Then, this policy not only serves 1. to model the observer's belief update, but also 2. as a baseline, and 3. to compute HSVI's initial bounds as described in Sec. 4.4.

**Algorithm Settings** Our experiments focus on goal-oriented problems. However we stick to using a (large) discount factor $\gamma = 0.99$, 1. to illustrate some pathological behaviors, and 2. to allow sticking to the standard HSVI algorithm.<fnref n="1" />

Any instance of value iteration or policy evaluation [Bertsekas, 2005] stops when the Bellman residual is below $\epsilon_{VI} = 0.0001$. Also, in all experiments, HSVI stops when the root gap $\epsilon_{HSVI} = 0.001$ or with a 1 h timeout.

## 5.1 Benchmark Problems

We now describe the underlying MDP, named *Maze*.

### 5.1.1 Maze problems

As illustrated in Figs. 2 to 5, a maze is defined by a 4-connected grid world that contains walls (in dark grey), normal cells (in white), hidden cells (in cyan), and goal cells: the current *actual* goal (green disk) and *alternate* goals (pink diamonds).

More formally, in this SSP:

1. each state $s$ in $S$ indicates (a) the $(x, y)$ coordinates of the agent, which can be in a normal, hidden, or goal cell, and (b) which goal cell is the actual goal $(x_g, y_g)$;

2. the only terminal states ($S_f$) are states $s$ such that the agent is in the actual goal $((x, y) = (x_g, y_g))$;

3. $A = \{\text{up, down, left, right}\}$;

4. $T(s, a, s')$ encodes the agent's moves: an agent in a normal, hidden or alternate-goal cell moves in the direction indicated by its chosen action if no wall prevents it; an agent in an actual-goal cell, being in a terminal state, does not move;

5. $R_{OBS}$, the observer reward function, returns a default penalty of $-0.01$ for each move, $-1$ when the agent hits a wall, and $0$ when in a terminal state.

To this SSP we add:

6. a set of observations $\Omega = \{(x, y)|(x, y)$ is a visible or actual-goal cell$\} \cup \{\text{none}\}$; and

7. an observation function $O$ which returns the agent's location (with probability $p_{OBS}$, set by default to 1) when it is in a visible cell or in a goal cell, and the "none" observation otherwise; and

8. the belief $b_0$ uniform over states $s = (x_0, y_0, x_{g_i}, y_{g_i})$, $(x_0, y_0)$ being the initial cell (known by the observer, but hidden) and $i$ indexing possible goals.

<footnote n="1">¹Adapting Horák et al.'s Goal-HSVI [Horák et al., 2018] would allow solving such problems.</footnote>
Note that, as required, 1. the observer knows when a terminal state is reached, i.e., when the agent has reached the actual goal; and 2. there are several possible goals in legibility and explicability scenarios, but a single one for predictability.

The observer policy $\pi_{\text{OBS}}$ just quickly reaches the actual goal, and can thus follow any of possibly many shortest paths (with deviations due to the softmax), ignoring the observer's viewpoint.

### 5.1.2 Grids used

**Legibility and Explicability** The maze (Fig. 2) consists of an open space with 3 possible goal states and a single row (#5) of visible cells which the agent may want to exploit. We will consider the actual goal being either the left one or the middle one.

**Legibility with Stochastic Observations** We examine stochastic observations ($p_{\text{OBS}} = 0.5$) only in a legibility problem (Fig. 3) with two paths for the left goal, the longest one (right) having more visible cells.

**Predictability** For action- and state-predictability, the maze (Fig. 5) consists of mostly hidden corridors, only three cells being visible for the observer: ($D, 10$), ($D, 2$) and ($B, 2$), the actual-goal cell.

## 5.2 Solution Evaluation

Table 1 provides 1. the reward functions in use in each setting, the choice of a combination with $R_{\text{OBS}}$ being discussed below, and 2. the value at $i_0$ in each case for the PO-OAMDP policy vs the baseline $\pi_{\text{OBS}}$ vs the underlying MDP optimal policy (estimated through 1 000 simulated trajectories). The main observation is that the PO-OAMDP agent consistently and significantly outperforms the baseline.

<table><caption>Table 1: $V^{\pi}(i_0)$ for various problems</caption><thead><tr><th rowspan="2">criterion</th><th rowspan="2">Policies</th><th colspan="3">Legibility</th><th rowspan="2">Action pred.<br/>R<sub>OBS</sub> + R<sub>a-pred</sub></th><th rowspan="2">State pred.<br/>R<sub>s-pred</sub></th></tr><tr><th>left goal</th><th>middle goal</th><th>p<sub>OBS</sub> = 0.5</th></tr></thead><tbody><tr><td rowspan="3">V<sub>PO-OAMDP</sub></td><td>PO-OAMDP</td><td>-3.59</td><td>-3.10</td><td>-3.02</td><td>-1.05</td><td>-1.61</td><td>-2.46</td></tr><tr><td>MDP (π<sub>OBS</sub>)</td><td>-6.76</td><td>-7.59</td><td>-4.32</td><td>-3.09</td><td>-6.30</td><td>-10.99</td></tr><tr><td>MDP</td><td>-4.12</td><td>-3.56</td><td>-3.26</td><td>-1.51</td><td>-3.41</td><td>-8.40</td></tr><tr><td rowspan="3">V<sub>OBS</sub></td><td>PO-OAMDP</td><td>-0.15</td><td>-0.18</td><td>-0.10</td><td>-0.13</td><td>-0.13</td><td>-0.17</td></tr><tr><td>MDP (π<sub>OBS</sub>)</td><td>-0.20</td><td>-0.20</td><td>-0.10</td><td>-0.20</td><td>-0.16</td><td>-0.17</td></tr><tr><td>MDP</td><td>-0.13</td><td>-0.11</td><td>-0.08</td><td>-0.13</td><td>-0.13</td><td>-0.13</td></tr></tbody></table>

In the following, we mainly look at example trajectories obtained using a PO-OAMDP agent, along with the evolution of the belief about the target variable. Corresponding observer MDP policies $\pi_{\text{OBS}}$ are provided in Section B. White stripes appearing on belief evolutions (Figs. 2 to 5) correspond to time steps where the agent has been observed.

**Legibility** In the grid Figure 2a, if row 5 is crossed on the left, the observer strongly believes in the left goal, and rewards become small, which makes it harder for HSVI to converge to a proper policy. We thus combined $R_{\text{OBS}}$ with the legibility reward.

For the left actual goal Fig. 2a, the agent does not go directly up to visible cell ($D, 5$), what would slightly increase the probability of the middle goal. It goes to the left-most visible cell ($B, 5$), and goes back to it multiple times to increase the belief in the left goal before actually reaching that actual goal. Disappearing from ($B, 5$) (rather than appearing in ($C, 5$)) also increases the belief in the actual goal. As illustrated in Section B.2, Fig. 9, there are no such “oscillations” when the remaining path to the goal is short.

For the middle actual goal Fig. 2b, the agent has a similar behavior, but going up to visible cell ($D, 5$) instead of ($B, 5$).

As can be observed in Table 1, those PO-OAMDP policies have significantly better values than the default MDP policies, which do not attempt to increase the observer's certainty before traversing to the goal.

**Legibility with Stochastic Observability** As shown in Fig. 2, with the actual goal on the left, the PO-OAMDP policy depends on $p_{\text{OBS}} = 1$ (left), the agent prefers the left (and shortest) path to the goal, where it is easily seen in ($B, 4$). When $p_{\text{OBS}} = 0.5$ (right), the agent prefers the less likely right path, where it is more likely to be seen without having to wait. The belief evolution is less sudden with the right path, which is less likely for the observer.
<figure><img src="image_4.png" /><figcaption>Figure 2: PO-OAMDP trajectories and corresponding belief evolutions for the *legibility* task with $p_{\text{OBS}} = 1$ (so that the evolution is deterministic) for two different goal cells</figcaption></figure>

**Explicability** Here, the explicability reward function $R_{\text{exp}}$ alone was sufficient to obtain proper policies. This is because a behavior is explicable if it appears to be normal, thus, here, to reach a terminal state as fast as $\pi_{\text{OBS}}$ would do.

As shown in Fig. 4, the agent goes directly to visible cell (D, 5), which is consistent with all three possible goals, thus quickly and significantly decreasing the probability of a random behavior (target value $\psi_0$), and not trying to bring information about the actual goal (which is then reached as fast as possible).
<figure><img src="image_5.png" /><figcaption>Figure 3: PO-OAMDP trajectories and corresponding belief evolutions for the *legibility* task with $p_{\text{OBS}} = 1$ and $p_{\text{OBS}} = 0.5$ (in this last case, only a sampled belief evolution—in which the agent has been observed in $(D, 5)$—is shown).</figcaption></figure>

**Action Predictability** As shown in Figs. 5a and 5b, action predictability here requires combining $R_{\text{a-pred}}$ with $R_{\text{OBS}}$ to obtain a proper policy. Indeed, without $R_{\text{OBS}}$, the observer can keep on correctly predicting action *down*, believing it is most probably in cell (B, 2), while it is actually in (F, 1) (Fig. 5a, truncated trajectory). This rightmost trajectory if preferred over going through the empty room, where the action sequence is less predictable. Adding $R_{\text{OBS}}$ fixes this issue by making sure that an infinite trajectory induces an infinite cost. Then, the best option is to go through (D, 10) so as to reduce the uncertainty about the trajectory early on, despite the traversal of the empty room afterwards. Note: In a smaller version of this environment, with no empty room, adding $R_{\text{OBS}}$ is not required, cf. Sec. B.4, Fig. 11.

**State Predictability** Fig. 5c shows a behavior very similar to Fig. 5b, but for coming back once in (B, 5) after reaching (B, 6) for the first time (see also (B, 2)). This is because $\pi_{\text{OBS}}$ makes it likely enough that the agent randomly moved backward at some point.

## 5.3 Computation Time

Fig. 6 shows the evolution of the upper and lower bound during HSVI's convergence on the legibility task, with typical monotonic step-wise behaviors on both sides. Fig. 7 shows the evolution of the error gap in the four problems involving deterministic observations for the two proposed bound initializations.
<figure><img src="image_6.png" /><figcaption>Figure 4: PO-OAMDP trajectory and corresponding belief evolution for the *explicability* task with $p_{OBS} = 1$ (so that the evolution is deterministic) for the left goal cell</figcaption></figure>

**Criteria and Grid** A first comment is that the convergence is much faster for the predictability criteria. This is likely due 1. to the lack of open spaces in the corresponding grid (so that less trajectories need to be considered) and 2. to the reward functions possibly better guiding the decisions.

**Initializations** Overall, the combined initialization has a better anytime behavior than the naive one. This is true in particular in the most complex problems (legibility and explicability), even if the curves sometimes cross each other.

# 6 Conclusion

We have introduced the novel framework of observer-aware MDPs under partial observability (PO-OAMDPs), which allows addressing (among other things) legibility, explicability and predictability problems when the observer has only a limited perception of the agent and its environment. This framework more than just generalizes Miura and Zilberstein's OAMDPs (with similar complexity results) as the target variable is now transition-dependent, and can thus be dynamic, contrary to the original agent type. This enables formalizing a wider range of problems (e.g., action and state predictability as defined by Lepers et al. [2024], but see also Sec. C).

Assuming a BST model of the observer, we show how to update her state belief (known to the agent), and derive her belief over the target variable. This leads to turning a PO-OAMDP into an equivalent state+belief MDP whose virtual state is a (state, state-belief) pair, allowing to adapt Smith and Simmons's HSVI algorithm [Smith and Simmons, 2004] with dedicated upper- and lower-bound initializations.

Experiments show the benefits of these initializations and illustrate the PO-OAMDP framework by demonstrating resulting non-trivial behaviors with several criteria (legibility, explicability and predictability), with a significant
<figure><img src="image_7.png" /><figcaption>Figure 5: PO-OAMDP trajectories and corresponding belief evolutions for predictability tasks</figcaption></figure>

benefit compared to default policies. Among other things, they show that these criteria do not necessarily induce valid SSPs, an issue that can be provably be alleviated by simply adding another cost function.

Future work includes further exploring the possibilities offered by PO-OAMDPs, and improving solution techniques. In particular, we aim at exploiting the continuity of $V^*$ in belief space, even if it may not be convex and may exhibit local discontinuities [Miura et al., 2024].

References

Georgios Angelopoulos, Alessandra Rossi, Claudia Di Napoli, and Silvia Rossi. You are in my way: Non-verbal social cues for legible robot navigation behaviors. In *IEEE/RSJ International Conference on Intelligent Robots and Systems, IROS 2022, Kyoto, Japan, October 23-27, 2022*, pages 657–662. IEEE, 2022. doi: 10.1109/IROS47612.2022.9981754. URL https://doi.org/10.1109/IROS47612.2022.9981754.

Mauricio Araya-López, Olivier Buffet, Vincent Thomas, and François Charpillet. A POMDP extension with belief-dependent rewards. In *Advances in Neural Information Processing Systems 23*, 2010.

Chris L. Baker, Rebecca Saxe, and Joshua B. Tenenbaum. Action understanding as inverse planning. *Cognition*, 113 (3):329–349, 12 2009. doi: 10.1016/j.cognition.2009.07.005.

Michael Beetz, Freek Stulp, Piotr Esden-Tempski, Andreas Fedrizzi, Ulrich Klank, Ingo Kresse, Alexis Maldonado, and Federico Ruiz-Ugalde. Generality and legibility in mobile manipulation. *Auton. Robots*, 28(1):21–44, 2010. doi: 10.1007/S10514-009-9152-9. URL https://doi.org/10.1007/s10514-009-9152-9.

Richard Bellman. A Markovian decision process. *Journal of Mathematics and Mechanics*, 6(5):679–684, 1957.

Dimitri P. Bertsekas. *Dynamic Programming and Optimal Control*. Athena Scientific, 2005.
<figure><img src="image_8.png" /><figcaption>Figure 6: Evolution of the upper and lower bounds for legibility on the first maze using the combined initialization</figcaption></figure>

<figure><img src="image_9.png" /><figcaption>Figure 7: Evolution of the error gap as a function of time (in seconds) for different initializations (log scales)</figcaption></figure>

Tathagata Chakraborti, Anagha Kulkarni, Sarath Sreedharan, David E. Smith, and Subbarao Kambhampati. Explicability? legibility? predictability? transparency? privacy? security? the emerging landscape of interpretable agent behavior. CoRR, abs/1811.09722, 2018. URL http://arxiv.org/abs/1811.09722.

Tathagata Chakraborti, Anagha Kulkarni, Sarath Sreedharan, David E. Smith, and Subbarao Kambhampati. Explicability? legibility? predictability? transparency? privacy? security? the emerging landscape of interpretable agent behavior. In Proceedings of the Twenty-Ninth International Conference on Automated Planning and Scheduling (ICAPS), 2019. URL https://ojs.aaai.org/index.php/ICAPS/article/view/3463.
Anca D. Dragan and Siddhartha S. Srinivasa. Generating legible motion. In *Paul Newman, Dieter Fox, and David Hsu, editors, Robotics: Science and Systems IX, Technische Universität Berlin, Berlin, Germany, June 24 - June 28, 2013*, 2013. doi: 10.15607/RSS.2013.IX.024. URL http://www.roboticsproceedings.org/rss09/p24.html.

Anca D. Dragan, Kenton C. T. Lee, and Siddhartha S. Srinivasa. Legibility and predictability of robot motion. pages 301–308, 2013.

Jaime F. Fisac, Chang Liu, Jessica B. Hamrick, Shankar Sastry, J. Karl Hedrick, Thomas L. Griffiths, and Anca D. Dragan. Generating plans that predict themselves. In *Algorithmic Foundations of Robotics XII: Proceedings of the Twelfth Workshop on the Algorithmic Foundations of Robotics*, 2020.

Ze Gong and Yu Zhang. Behavior explanation as intention signaling in human-robot teaming. In *27th IEEE International Symposium on Robot and Human Interactive Communication, RO-MAN 2018, Nanjing, China, August 27-31, 2018*, pages 1005–1011. IEEE, 2018. doi: 10.1109/ROMAN.2018.8525675. URL https://doi.org/10.1109/ROMAN.2018.8525675.

Karel Horák, Branislav Bošanský, and Krishnendu Chatterjee. Goal-HSVI: Heuristic search value iteration for goal-POMDPs. In *Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence*, pages 4764–4770, 2018.

Gary Klein, David D. Woods, Jeffrey M. Bradshaw, Robert R. Hoffman, and Paul J. Feltovich. Ten challenges for making automation a "team player" in joint human-agent activity. *IEEE Intell. Syst.*, 19(6):91–95, 2004. doi: 10.1109/MIS.2004.74. URL https://doi.org/10.1109/MIS.2004.74.

Salomé Lepers, Sophie Lemonnier, Vincent Thomas, and Olivier Buffet. How to exhibit more predictable behaviors. *CoRR*, abs/2404.11296, 2024. URL https://arxiv.org/abs/2404.11296.

Shuwa Miura and Shlomo Zilberstein. A unifying framework for observer-aware planning and its complexity. In *Proceedings of the Thirty-Seventh Conference on Uncertainty in Artificial Intelligence*, volume 161, pages 610–620, 7 2021. URL https://proceedings.mlr.press/v161/miura21a.html.

Shuwa Miura, Olivier Buffet, and Shlomo Zilberstein. Approximation algorithms for observer aware MDPs. In *The 40th Conference on Uncertainty in Artificial Intelligence*, 2024. URL https://openreview.net/forum?id=UXsERjAZy8.

L.R. Rabiner. A tutorial on hidden Markov models and selected applications in speech recognition. *Proceedings of the IEEE*, 77(2):257–286, February 1989.

Bob R. Schadenberg, Dennis Reidsma, Dirk K. J. Heylen, and Vanessa Evers. "i see what you did there": Understanding people's social perception of a robot and its predictability. *J. Hum.-Robot Interact.*, 10(3), jul 2021. doi: 10.1145/3461534. URL https://doi.org/10.1145/3461534.

Phani-Teja Singamaneni, Pilar Bachiller-Burgos, Luis J. Manso, Anaís Garrell, Alberto Sanfeliu, Anne Spalanzani, and Rachid Alami. A survey on socially aware robot navigation: Taxonomy and future challenges. *Int. J. Robotics Res.*, 43(10):1533–1572, 2024. doi: 10.1177/02783649241230562. URL https://doi.org/10.1177/02783649241230562.

Trey Smith. *Probabilistic Planning for Robotic Exploration*. PhD thesis, The Robotics Institute, Carnegie Mellon University, 2007.

Trey Smith and Reid G. Simmons. Point-based POMDP algorithms: Improved analysis and implementation. In *Proceedings of the Twenty-First Conference on Uncertainty in Artificial Intelligence*, pages 542–549, 2005.

Trey Smith and R.G. Simmons. Heuristic search value iteration for POMDPs. In *Proceedings of the Annual Conference on Uncertainty in Artificial Intelligence (UAI)*, 2004.

Sarath Sreedharan, Anagha Kulkarni, Tathagata Chakraborti, David E. Smith, and Subbarao Kambhampati. A Bayesian account of measures of interpretability in human-AI interaction, 2020.

## A OAMDPs expressed as PO-OAMDPs

This appendix demonstrates that, assuming the BST belief update is used, any OAMDP can be turned into an equivalent PO-OAMDP (cf. Section 3).

**Proposition 6.** Any OAMDP $\mathcal{M}$ with BST belief update can be turned into an equivalent PO-OAMDP $\mathcal{M}'$, i.e., such that an optimal solution to one problem is optimal for the other problem.

*Proof.* Let $\mathcal{M} \equiv \langle S, s_0, A, T, \gamma, S_f, \Theta, B, R_{AG} \rangle$ be an OAMDP and, for each $\theta$ in the set of possible types $\Theta$, let $\mathcal{M}^{\theta} \equiv \langle S, s_0, A, T^{\theta}, \gamma, S_f^{\theta}, R_{\text{OBS}}^{\theta} \rangle$ be the corresponding MDP.

Let us now introduce a new type $\tilde{\theta}$ and the MDP $\tilde{\mathcal{M}} \equiv \langle S, s_0, A, T^{\tilde{\theta}} \triangleq T, \gamma, S_f^{\tilde{\theta}} \triangleq S_f, R_{\text{OBS}}^{\tilde{\theta}} \rangle$, where $R_{\text{OBS}}^{\tilde{\theta}}$ is the reward function that returns $-1$ at each time step until a terminal state is reached (to ensure that we have a valid SSP
if needed). We can now define the PO-OAMDP $\mathcal{M}' \equiv \langle S', s'_0, A', T', \gamma, S'_f, R'_{\text{OBS}}, (\Psi \equiv) \Theta', \Omega, O', B', R'_{\text{AG}}, \phi \rangle$ where:

$$
\begin{align*}
\Theta' &\triangleq \Theta \cup \{\tilde{\theta}\}, \\
S' &\triangleq S \times \Theta', \\
s'_0 &\triangleq (s_0, \tilde{\theta}), \\
A' &\triangleq A, \\
T'((s, \theta), a, (s', \theta')) &\triangleq 1_{\theta=\theta'} \cdot T^{\theta}(s, a, s'), \\
S'_f &\triangleq \{(s, \theta)|s \in S_f^{\theta}\}, \\
R'_{\text{OBS}}((s, \theta), a, (s', \theta')) &\triangleq 1_{\theta=\theta'} \cdot R^{\theta}_{\text{OBS}}(s, a, s'), \\
\Omega &\triangleq S, \\
O'(a, s', o) &\triangleq 1_{o=s'}, \\
B'((s, \theta)|-) &\triangleq \begin{cases} B((s, \theta)|-) \cdot 1_{s=s_0} & \text{if } \theta \in \Theta, \text{ and} \\ 0 & \text{if } \theta = \tilde{\theta}, \end{cases}
\end{align*}
$$

(with beliefs at time steps beyond $t = 0$ computed by Bayesian belief updates),

$$R'_{\text{AG}}(s, \beta, a, s', \beta') \triangleq R_{\text{AG}}(s, a, \beta_{-\tilde{\theta}}),$$

where $\beta_{-\tilde{\theta}}$ is the belief vector $\beta$ deprived of the $\tilde{\theta}$ component, and

$$\phi((s, \theta), a, (s', \theta')) \triangleq \theta.$$

Note that the “fake type” $\tilde{\theta}$ only serves to ensure that the actual dynamics (transition function and set of terminal states) exist, as it could be that none of the “true types” is attached to them.

Then, solving the underlying MDP with reward $R'_{\text{OBS}}$ (either for all states, or for all states reachable from the states in $b_0$) is equivalent to solving each MDP $\mathcal{M}^{\theta}$, and the softmax policy $\pi'_{\text{OBS}}$ is equivalent to the softmax policies $\pi^{\theta}_{\text{OBS}}$. Thus, the BST update is the same in both cases.

As can be noted, the belief over targets/types will always have value 0 for $\tilde{\theta}$, so that $\beta_{-\tilde{\theta}}$ will correspond to the belief over types for the OAMDP, and, as a consequence, the agent reward is equivalent in both settings. Then because the initial state of the PO-OAMDP is $(s_0, \tilde{\theta})$, and because the belief updates are equivalent, the dynamics of the PO-OAMDP are equivalent to those of the original OAMDP, so that solving the one is equivalent to solving the other. $\square$

Note that the fake type $\tilde{\theta}$ is, in a sense, the actual type of the (observer-aware) agent, which is ignored by the observer because the observer does not model the agent as optimizing $R'_{\text{AG}}$.

# B Complementary Experimental Results

The following sections present some complementary experimental results. Section B.1 shows an illustration of the observer's softmax MDP policies $\pi_{\text{OBS}}$ used in legibility and explicability tasks. The following subsections present the results obtained with smaller versions of the grids used in the main experiments (Section 5). These subsections illustrate that back and forth movements observed in previous tasks (Fig. 2) are not always necessary and are the consequences of uncertainties on the target variable and induced costs.

## B.1 Observer's Softmax MDP Policies

Figs. 8a and 8b illustrate the $\pi_{\text{OBS}}$ policies that are used for both legibility and explicability tasks (because the task considered by the observer is the same in both scenarios). In these figures, the higher the probability to select an action, the darker the corresponding arrow, and, when the probability is below a threshold of 0.1, the corresponding arrow is not shown.

This highlights that the observer models the agent as following a stochastic policy, and it must be noted that, due to negative rewards when hitting a wall, probabilities to go away from the wall are larger than the aforementioned probability threshold.
<figure><img src="image_10.png" /><figcaption>Figure 8: Observer's Softmax MDP policies of the legibility and explicability task for different actual goals</figcaption></figure>

## B.2 Legibility

When addressing legibility task in a smaller grid (Fig. 9), the PO-OAMDP agent simply reaches cell (C, 3), stays visible by moving left to (B, 3), then goes to the actual-goal cell. It must be noted that at time step 2, the agent decides not to appear in cell (D, 3). Since the observer would have expected the agent to go in cell (D, 3) if its actual goal had been $\psi_2$, her belief in the middle goal $\psi_2$ decreases just by not observing the agent in that cell. When the agent appears in cell (C, 3), the observer belief in goal $\psi_1$ increases but, since $\pi_{\text{OBS}}$ is stochastic, she cannot be sure of the actual goal of the agent.

Then, the agent prefers to quickly reach its actual goal and a terminal state (with future cumulated rewards of 0) than take time to reduce uncertainties as seen in previous experiment (Fig. 2a). This is because, in this new maze, the goal is easily reached and the agent is only penalized one time step by the remaining uncertainty. This is not the case when the goal is far from the visible cells, which explains back and forth movements observed in Fig. 2 to reduce uncertainties regarding the actual goal before following a hidden path to reach that goal.

It must also be noted that, even in this simple problem, the PO-OAMDP policy performs better than the naive $\pi_{\text{OBS}}$ policy.

## B.3 Explicability

When addressing explicability in a smaller grid, the PO-OAMDP agent directly crosses the visible line and reaches its actual goal as fast as possible (Fig. 10).

By appearing in cell (D, 3), it maintains an ambiguity regarding its actual goal, but reduces the probability of the random policy $\psi_0$ since the probability to reach that cell when acting randomly is lower than when trying to reach one of the goals. Being not observed at the next time step reduces the probability of acting randomly (when acting
<figure><img src="image_11.png" /><figcaption>a) Softmax policy $\pi_{\text{OBS}}$</figcaption></figure>

$V = -3.5$

<figure><img src="image_12.png" /><figcaption>b) PO-OASSP policy $\pi$</figcaption></figure>

$V = -2.1$

<figure><img src="image_13.png" /><figcaption>c) Belief evolution</figcaption></figure>

<caption>Figure 9: Results for legibility</caption>

randomly, the agent would have a 0.5 probability to appear in a visible cell), and also increases the belief in the middle goal (because left- and right-goal policies have a non-negligible probability to maintain in the visible row 3).

The uncertainty regarding the actual goal is maintained until the actual goal of the agent is reached and the agent is observed in a terminal state. The fact that the agent is not observed at time step 4 also reduces the probability of the middle goal ($\psi_2$) to be the actual goal.

## B.4 Predictability

The predictability task described in this section (Fig. 11) is simpler than the one in the body of the article depicted in Fig. 5.

In the maze presented in Section 5.1.1, the agent had to cross an empty area, which induces a lot of uncertainties regarding its next action (as many trajectories cross that area) or its actual state (which depends on how he decided to cross the area). It required essentially adding a small negative reward $\delta$ (through $R_{\text{OBS}}$) to ensure that the problem corresponds to a valid SSP and the agent reaches its actual goal (otherwise, the agent might get stuck in a situation where its next action is the most probable one for the observer, but its state does not change, having a cumulated 0 value).

In the setting of Fig. 11, once the agent has appeared in (D, 6), the remainder of its trajectory (as modeled by the observer through $\pi_{\text{OBS}}$) is much less ambiguous, except for randomly sampled sub-optimal moves. There is thus no need for an additional negative reward.
<figure><img src="image_14.png" /><figcaption>A B C D E F G
a) Softmax policy $\pi_{\text{OBS}}$</figcaption></figure>

$V = -1.96$

<figure><img src="image_15.png" /><figcaption>b) PO-OASSP policy $\pi$</figcaption></figure>

$V = -0.75$

<figure><img src="image_16.png" /><figcaption>c) Belief evolution</figcaption></figure>

<caption>Figure 10: Results for explicability</caption>

# C More Example Scenarios

## C.1 Obfuscation

Opposite problems can also be considered. The agent then attempts to hide information. It may, for instance, have multiple possible goals, and try to not reveal its actual goal to the observer. Obfuscation in the PO-OAMDP setting presents the same difficulties as in the OAMDP setting:

* if the objective is only about obfuscating information, but not on achieving a task, then the agent may simply not do anything to hide its goal, and

* to derive the observer's belief over the goals, one assumes that the observer does not know that the agent may be trying to trick her.

Relaxing the last assumption would typically require considering a game-theoretic setting, which is out of scope of this paper.

## C.2 Broadening to Other Types of Problems

For now we have discussed problems already modeled in the OAMDP and p-OAMDP frameworks by considering the observer's partial observability. Yet, PO-OAMDPs allow modeling other problems in which the agent will not try to
<figure><img src="image_17.png" /><figcaption>a) Softmax policy $\pi_{\text{OBS}}$</figcaption></figure>

$V = -5.01$

<figure><img src="image_18.png" /><figcaption>b) PO-OASSP policy $\pi$</figcaption></figure>

$V = -1.1$

<figure><img src="image_19.png" /><figcaption>c) Belief evolution</figcaption></figure>

<caption>Figure 11: Results for action predictability</caption>

exhibit a legible, explicable or predictable behavior (for instance), but could attempt to convey as much information as possible about the state of the world currently watched by the observer.

**Scenario #1:** Let us consider an office-like environment (see Figure 12) with doors that are either opened or locked up, and an agent trying to let an external observer know the state of the doors through its actions. This can of courses have achieved by opening the doors visible to the observer, but also by showing up in certain zones that can be reached only by opening certain doors. Thus, even if these doors are never seen by the observer, the agent's presence may allow inferring that some doors are open.

In the example of Figure 12, by choosing a longer path in the hidden zone and reappearing in C, it tells the observer that doors d1 and d2 are not locked. Becoming visible in B would allow achieving the objective, but without
<figure><img src="image_20.png" /><figcaption>Figure 12: A grid environment with doors that may be locked. Walls are represented by black cells, doors by brown rectangles. The grey zone correspond to a zone hidden to the observer. The agent starts in A and has to go to O.</figcaption></figure>

<figure><img src="image_21.png" /><figcaption>Figure 13: Grid environment with an intruder. Wall are represented by black cells. The grey area corresponds to a zone hidden to the observer. The intruder is represented by a red circle and the agent by a blue circle.</figcaption></figure>

providing information to the observer about the state of door d2. Solving this problem requires the agent to reason about

1. the consequences of its actions,

2. its visibility, which depends on its location,

3. the observer's possible inferences, and

4. in particular the doors whose state the agent wants the observer to know.

**Scenario #2:** In a second scenario, let us consider an agent responsible for tracking intruders in an environment an observer cannot perceive (see Figure 13). By modeling the observer's reasoning process, the agent can leverage the observer's expectations to act, appearing in certain places and let the observer know about the presence and location of an intruder.
In the example illustrated by Figure 13, the observer expects the agent to try getting close to the intruder. The agent can thus inform the observer about the intruder's location by choosing among the possible trajectories bringing as close as possible to the intruder, a path that is often visible to the observer.

**Scenario #3:** Finally, in complex tasks that require achieving several intermediate sub-tasks (/objectives), the agent may try to convey information about the progress of the ongoing sub-task by following longer paths but

1. which are partially visible to the observer, and

2. which leave less ambiguity about its intermediate objective.

By trying to make it easier to infer the intermediate objectives it attempts to achieve, the agent can thus transmit the status of the current sub-task, what can be crucial in a collaborative scenario (that would require in return a particular action from the human).

These various situations show that the PO-OAMDP formalism allows broadening the family of problems covered by conveying information not only about the agent's behavior. This framework allows modeling problems close to active information gathering, as formalized by ρ-POMDPs [Araya-López et al., 2010]. In ρ-POMDPs, an agent partially observes its (own) environment, and has to act as well as possible to obtain relevant observations and maximize some information measure about its target variables (such as its location). The main difference with PO-OAMDPs is that, in the latter, the agent wants to control the information acquired by a third party (the observer), not its own information (which is complete). This requires in particular a model of the observer that the agent will take advantage of to indirectly control the observer's belief.