Interpreting Systems as Solving POMDPs: A Step Towards a Formal Understanding of Agency

Under what circumstances can a system be said to have beliefs and goals, and how do such agency-related features relate to its physical state? Recent work has proposed a notion of interpretation map, a function that maps the state of a system to a probability distribution representing its beliefs about an external world. Such a map is not completely arbitrary, as the beliefs it attributes to the system must evolve over time in a manner that is consistent with Bayes’ theorem, and consequently the dynamics of a system constrain its possible interpretations. Here we build on this approach, proposing a notion of interpretation not just in terms of beliefs but in terms of goals and actions. To do this we make use of the existing theory of partially observable Markov decision processes (POMDPs): we say that a system can be interpreted as a solution to a POMDP if it not only admits an interpretation map describing its beliefs about the hidden state of a POMDP but also takes actions that are optimal according to its belief state. An agent is then a system together with an interpretation of this system as a POMDP solution. Although POMDPs are not the only possible formulation of what it means to have a goal, this nevertheless represents a step towards a more general formal definition of what it means for a system to be an agent.

1. 1.

   These machines are probably equivalent to the sufficient information state processes in [9, definition 2] but establishing this is beyond the scope of this work.

2. 2.

   The FEP literature includes both publications on how to construct agents that solve problems (e.g. [8]) and publications on when a system of stochastic differential equations contain an agent performing approximate Bayesian inference. Only the latter literature addresses a question comparable to the one addressed in the present manuscript.

3. 3.

   We choose actions to be deterministic functions of the machine state because the stochastic Moore machines considered here also have deterministic outputs. Other choices may be more suitable in other cases.

4. 4.

   If the denominator in Eq. (3) is zero for some value \(s \,{\in }\, {\mathcal {S}}\) then define e.g. \(f_{\pi ^*}(b,s)=b\).

Authors and Affiliations

1. Cross Labs, Cross Compass, Tokyo, 104-0045, Japan

   Martin Biehl

2. Earth-Life Science Institute, Tokyo Institute of Technology, Tokyo, 152-8550, Japan

   Nathaniel Virgo

Corresponding author

Correspondence to Martin Biehl .

Editors and Affiliations

1. University of Sussex, Brighton, UK

   Christopher L. Buckley

2. University of Chieti-Pescara, Pescara, Italy

   Daniela Cialfi

3. Donders Institute for Brain, Cognition and Behaviour, Nijmegen, The Netherlands

   Pablo Lanillos

4. Wellcome Centre for Human Neuroimaging, London, UK

   Maxwell Ramstead

5. Wellcome Centre for Human Neuroimaging, London, UK

   Noor Sajid

6. Kyoto University, Kyoto, Japan

   Hideaki Shimazaki

7. Ghent University, Ghent, Belgium

   Tim Verbelen

A Consistency in More Familiar Form

One way to turn Eq. (2) into a probably more familiar form is to introduce some abbreviations and look at some special cases. We follow a similar strategy to [16]. Let

and

Then consider the case of a deterministic machine and choose the \(m' \in {\mathcal {M}}\) that actually occurs for a given input \(i \in {\mathcal {I}}\) such that \({\mu }(m'|i,m)=1\) or abusing notation \(m' = m'(i,m)\). Then we get from Eq. (2):

If we then also consider an input \(i \in {\mathcal {I}}\) that is subjectively possible as defined in [16] which here means that \(\psi _{{\mathcal {I}}}(i|m)>0\) we get

This makes it more apparent that in the interpretation the updated machine state \(m'=m'(i,m)\) parameterizes a belief \(\psi (h'|m'(i,m))\) which is equal to the posterior distribution over the hidden state given input i. In the non-deterministic case, note that when \({\mu }(m'|i,m)=0\) the consistency equation imposes no condition, which makes sense since that means the machine state \(m'\) can never occur. When \({\mu }(m'|i,m)>0\) we can divide Eq. (2) by this to also get Eq. (10). The subsequent argument for \(m'=m'(i,m)\) then must hold not only for this one possible next state but instead for every \(m'\) with \({\mu }(m'|i,m)\). So in this case (if s is subjectively possible) any of the possible next states will parameterize a belief \(\psi (h'|m')\) equal to the posterior.

B Proof of Proposition 1

For the readers’s convenience we recall the proposition:

Proposition 2

Consider a stochastic Moore machine \(({\mathcal {M}},{\mathcal {I}},{\mathcal {O}},{\mu },{\omega })\), together with a consistent interpretation as a solution to a POMDP, given by the POMDP \(({\mathcal {H}},{\mathcal {O}},{\mathcal {I}},\kappa ,{r})\) and Markov kernel \(\psi :{\mathcal {M}}\rightarrow P{\mathcal {H}}\). Suppose it is given an input \(i\in {\mathcal {I}}\), and that this input has a positive probability according to the interpretation. (That is, Eq. (14) is obeyed.) Then the parameterized distributions \(\psi (m)\) update as required by the belief state update equation (Eq. (3)) whenever \(a=\pi ^*(b)\) i.e. whenever the action is equal to the optimal action. More formally, for any \(m,m' \in {\mathcal {M}}\) with \({\mu }(m'|i,m)>0\) and \(i \in {\mathcal {I}}\) that can occur according to the POMDP transition and sensor kernels, we have for all \(h' \in {\mathcal {H}}\)

Proof

By assumption the machine part \(({\mathcal {M}},{\mathcal {I}},{\mu })\) of the stochastic Moore machine has a consistent Bayesian influenced filtering interpretation \(({\mathcal {H}},{\mathcal {O}},\psi ,{\omega },\kappa )\).

This means that the belief \(\psi (m)\) parameterized by the stochastic Moore machine obeys Eq. (2). This means that for every possible next state \(m'\) (i.e. \({\mu }(m'|s,m)>0\)) we have

and for every subjectively possible input, that is, for every input \(i \in {\mathcal {I}}\) with

(see below for a note on why this assumption is reasonable) we will have:

Now consider the update function for which the optimal policy is found Eq. (3):

and plug in the belief \(b=\psi (m)\) parameterized by the machine state, the optimal action \(\pi ^*(\psi (m))\) specified for that belief by the optimal policy \(\pi ^*\), and the \(s=i\):

Also introduce \(\kappa \) and write \(\psi (h|m)\) for \(\psi (m)(h)\) as usual

Which is what we wanted to prove.

Note that if Eq. (14) is not true and the probability of an input i is impossible according to the POMDP transition function, the kernel \(\psi \), and the optimal policy \(\omega \) then Eq. (13) puts no constraint on the machine kernel \({\mu }\) since both sides are zero. So the behavior of the stochastic Moore machine in this case is arbitrary. This makes sense since according to the POMDP that we use to interpret the machine this input is impossible, so our interpretation should tell us nothing about this situation.

C Sondik’s Example

We now consider the example from [15]. This has a known optimal solution. We constructed a stochastic Moore machine from this solution which has an interpretation as a solution to Sondik’s POMDP. This proves existence of stochastic Moore machines with such interpretations.

Consider the following stochastic Moore machine:

• State space \({\mathcal {M}}{:}{=}[0,1]\). (This state will be interpreted as the belief probability of the hidden state being equal to 1.)

• input space \({\mathcal {I}}=\{1,2\}\)

• machine kernel \({\mu }:{\mathcal {I}}\times {\mathcal {M}}\rightarrow P{\mathcal {M}}\) defined by deterministic function \(g:{\mathcal {I}}\times {\mathcal {M}}\rightarrow {\mathcal {M}}\):

  $$\begin{aligned} {\mu }(m'|s,m){:}{=}\delta _{g(s,m)}(m') \end{aligned}$$

  (21)

  where

  $$\begin{aligned} g(S=1,m){:}{=}{\left\{ \begin{array}{ll} \frac{15}{6m+20}-\frac{1}{2} &{}\text { if } 0 \le m \le 0.1188\\ \frac{9}{5} - \frac{72}{5m+60} &{}\text { if } 0.1188 \le m \le 1. \end{array}\right. } \end{aligned}$$

  (22)

  and

  $$\begin{aligned} g(S=2,m){:}{=}{\left\{ \begin{array}{ll} 2+\frac{20}{3m-15} &{}\text { if } 0 \le m \le 0.1188\\ - \frac{1}{5} - \frac{12}{5m-40} &{}\text { if } 0.1188 \le m \le 1. \end{array}\right. } \end{aligned}$$

  (23)

• output space \({\mathcal {O}}{:}{=}\{1,2\}\)

• expose kernel \(\omega :{\mathcal {M}}\rightarrow {\mathcal {O}}\) defined by

  $$\begin{aligned} \omega (m){:}{=}{\left\{ \begin{array}{ll} 1 \text { if } 0 \le m < 0.1188\\ 2 \text { if } 0.1188 \le m \le 1. \end{array}\right. } \end{aligned}$$

  (24)

A consistent interpretation as a solution to a POMDP for this stochastic Moore machine is given by

• The POMDP with

  • state space \({\mathcal {H}}{:}{=}\{1,2\}\)

  • action space equal to the output space \({\mathcal {O}}\) of the machine above

  • sensor space equal to the input space \({\mathcal {I}}\) of the machine above

  • model kernel \(\kappa :{\mathcal {H}}\times {\mathcal {O}}\rightarrow {\mathcal {H}}\times {\mathcal {I}}\) defined by

    $$\begin{aligned} \kappa (h',s|h,a){:}{=}\nu (h'|h,a)\phi (s|h',a) \end{aligned}$$

    (25)

    where \(\nu :{\mathcal {H}}\times {\mathcal {O}}\rightarrow P{\mathcal {H}}\) and \(\phi :{\mathcal {H}}\times {\mathcal {O}}\rightarrow P{\mathcal {I}}\) are shown in Table 1

    Full size table

  • reward function \(r:{\mathcal {H}}\times {\mathcal {O}}\rightarrow \mathbb {R}\) also shown in Table 1.

• Markov kernel \(\psi : {\mathcal {M}}\rightarrow P{\mathcal {H}}\) given by:

  $$\begin{aligned} \psi (h|m):=m^{\delta _1(h)}(1-m)^{\delta _2(h)}. \end{aligned}$$

  (26)

To verify this we have to check that \(({\mathcal {H}},{\mathcal {O}},\psi ,{\omega },\kappa )\) is a consistent Bayesian influenced filtering interpretation of the machine \(({\mathcal {M}},{\mathcal {I}},{\mu })\). For this we need to check Eq. (2) with \(\delta _{\alpha (m)}(a){:}{=}\delta _{\omega (m)}(a)\). So for each each \(m \in [0,1]\), \(h' \in \{1,2\}\), \(i \in \{1,2\}\), and \(m' \in [0,1]\) we need to check:

This is tedious to check but true. We would usually also have to show that \(\omega \) is indeed the optimal policy for Sondik’s POMDP but this is shown in [15].

D POMDPs and Belief State MDPs

Here we give some more details about belief state MDPs and the optimal value function and policy of Eqs. (4) and (5). There is no original content in this section and it follows closely the expositions in [9, 10].

We first define an MDP and its solution and then discuss then add some details about the belief state MDP associated to a POMDP.

Definition 6

A Markov decision process (MDP) can be defined as a tuple \(({\mathcal {X}},{\mathcal {A}},{\nu },{r})\) consisting of a set \({\mathcal {X}}\) called the state space, a set \({\mathcal {A}}\) called the action space, a Markov kernel \({\nu }:{\mathcal {X}}\times {\mathcal {A}}\rightarrow P({\mathcal {X}})\) called the transition kernel, and a reward function \({r}:{\mathcal {X}}\times {\mathcal {A}}\rightarrow \mathbb {R}\). Here, the transition kernel takes a state \(x \in {\mathcal {X}}\) and an action \(a \in {\mathcal {A}}\) to a probability distribution \({\nu }(x,a)\) over next states and the reward function returns a real-valued instantaneous reward r(x, a) depending on the hidden state and an action.

A solution to a given MDP is a control policy. As the goal of the MDP we here choose the maximization of expected cumulative discounted reward for an infinite time horizon (an alternative would be to consider finite time horizons). This means an optimal policy maximizes

where \(0<\gamma <1\) is a parameter called the discount factor. This specifies the goal.

To express the optimal policy explicitly we can use the optimal value function \(V^*:{\mathcal {X}}\rightarrow \mathbb {R}\). This is the solution to the Bellman equation [10]:

The optimal policy is then the function \(\pi ^*:{\mathcal {X}}\rightarrow {\mathcal {A}}\) that greedily maximizes the optimal value function [10]:

1.1 D.1 Belief State MDP

The belief state MDP for a POMDP (see Definition 4) is defined using the belief state update function of Eq. (3). We first define this function again here with an additional intermediate step:

The function f(b, a, s) returns the posterior belief over hidden states h given prior belief \(b \in P{\mathcal {H}}\), an action \(a \in {\mathcal {A}}\) and observation \(s \in {\mathcal {S}}\). The Markov kernel \(\delta _{f}:P{\mathcal {H}}\times {\mathcal {S}}\times {\mathcal {A}}\rightarrow PP{\mathcal {H}}\) associated to this function can be seen as a probability of the next belief state \(b'\) given current belief state b, action a and sensor value s:

Intuitively, the belief state MDP has as its transition kernel the probability \(Pr(b'|b,a)\) expected over all next sensor values of the next belief state \(b'\) given that the current belief state is b the action is a and beliefs get updated according to the rules of probability, so

This gives some intuition behind the definition of belief state MDPs.

Definition 7

Given a POMDP \(({\mathcal {H}},{\mathcal {A}},{\mathcal {S}},\kappa ,{r})\) the associated belief state Markov decision process (belief state MDP) is the MDP \((P{\mathcal {H}},{\mathcal {A}},{\beta },{\rho })\) where

• the state space \(P{\mathcal {H}}\) is the space of probability distributions beliefs over the hidden state of the POMDP. We write b(h) for the probability of a hidden state \(h \in {\mathcal {H}}\) according to belief \(b \in P{\mathcal {H}}\).

• the action space \(\mathcal {A}\) is the same as for the underlying POMDP

• the transition kernel \(\kappa : P{\mathcal {H}}\times A \rightarrow P{\mathcal {H}}\) is defined as [10, Section 3.4]

  $$\begin{aligned} {\beta }(b'|b,a){:}{=}&\sum _{s \in {\mathcal {S}}} \delta _{f(b,a,s)}(b') \sum _{h,h' \in {\mathcal {H}}} \kappa (h',s|h,a)b(h). \end{aligned}$$

  (37)

• the reward function \({\rho }:P{\mathcal {H}}\times {\mathcal {A}}\rightarrow \mathbb {R}\) is defined as

  $$\begin{aligned} {\rho }(b,a){:}{=}\sum _{h \in {\mathcal {H}}} b(h) {r}(h,a). \end{aligned}$$

  (38)

  So the reward for action a under belief b is equal to the expectation under belief b of the original POMDP reward of that action a.

1.2 D.2 Optimal Belief-MDP Policy

Using the belief MDP we can express the optimal policy for the POMDP.

The optimal policy can be expressed in terms of the optimal value function of the belief MDP. This is the solution to the equation [9]

This is the expression we used in Eq. (4). The optimal policy for the belief MDP is then [9]:

This is the expression we used in Eq. (5).

Reprints and permissions

© 2023 The Author(s), under exclusive license to Springer Nature Switzerland AG

Policies and ethics