# Reasoning about Emergence of Collective Memory

R. Ramanujam Institute of Mathematical SciencesHomi Bhabha National Institute
Chennai, India<EMAIL_ADDRESS>
###### Abstract

We offer a very simple model of how collective memory may form. Agents keep
signalling within neighbourhoods, and depending on how many support each
signal, some signals “win” in that neighbourhood. By agents interacting
between different neighbourhoods, ‘influence’ spreads and sometimes, a
collective signal emerges. We propose a logic in which we can reason about
such emergence of memory and present preliminary technical results on the
logic.

##  1 Introduction

> Strictly speaking, there is no such thing as collective memory – part of the
> same family of spurious notions as collective guilt. But there is collective
> instruction $\ldots$ All memory is individual, unreproducible; it dies with
> each person. What is called collective memory is not a remembering but a
> stipulating: that this is important, and this is the story about how it
> happened, with the pictures that lock the story in our minds.
>
> Susan Sontag ([25])

Any discussion on individual values and social values visits the question, How
are we to act? at some point. The question, of course, is, who is this we
referred to here ? Clearly this we is a social construction, one that depends
on the very social norms and social values that we wish to reason about
([28]). Integral to such social construction of a collective is the memory
ascribed to that collective. Group identity is constructed structurally by
ascribing memory to the group, and in turn, such identity shapes its memory.
Remembrance has a crucial impact on preferences and values, influences action.

It is here that Susan Sontag’s quote above assumes significance. Sontag calls
collective memory a process of stipulation. Somehow the collective ascribes
importance to an item of memory, authenticates it and symbolizes it; then on,
the symbolism “locks” the memory item, in Sontag’s account.

Note that this is a significant departure from the structural conception of
memory, that visualises memory as a notebook, and remembering as looking it
up. Wittgenstein ([29]) strongly attacked such a conception of memory.

> I saw this man years ago: now I have seen him again, I recognize him, I
> remember his name. And why does there have to be a cause of this remembering
> in my nervous system? Why must something or other, whatever it may be, be
> stored up there in any form? Why must a trace have been left behind? Why
> should there not be a psychological regularity to which no physiological
> regularity corresponds?
>
> If this upsets our concept of causality then it is high time it was upset.

Scholars like Sutton ([26]) have discussed this issue at length. For
Wittgenstein, social acts were important in shaping memory, and based on this,
scholars like Rusu ([24]) even talk of social time, and modern theories of
connectionism and distributed memory build on many such notions.

For us, these remarks are relevant from two viewpoints. The 1950’s saw the
development of automata theory as a study of memory structures, and in theory
of computation, automata provide a model of memory that Wittgenstein might
have approved of. In this view, memory is not a table to be looked up, but is
constituted by states of being of the automaton. Observations cause changes in
state, some states remember (some of the past) and some forget. Thus,
remembering and forgetting are built into system structure. Such a view is
important for seeing memory and reasoning as interdependent rather than as
separate (as psychologists used to consider). Logicians are used to equating
automata and logics, as in the case of monadic second order logics of order or
in the case of Pressburger arithmetic. (Wittgenstein would have approved.)

The other viewpoint relates to distributed memory, where interacting agents
rely on memory external to them. Computer science has evolved impressive
models of highly flexible interaction and memory that has literally changed
the everyday life of much of humanity in the last few decades. Today, memory
storage on the “cloud” has become indispensable for many, and people
voluntarily ‘post’ personal information to make it socially available in an
attempt to write personal information into social memory.

In social theory, the notion of collective memory is influential. Maurice
Halbwachs ([15]) talked of how an individual’s understanding of the past is
strongly linked to a group consciousness, which in turn is a form of group
memory that lives beyond the memories of individuals that form the group.

For the logician, these notions pose an interesting challenge: what are the
logical properties of collective remembering? What is the rationale followed
by a group in ascribing / stipulating collective importance to events and
their remembering? Why is a particular idealisation chosen? These are
difficult questions to answer, but a more modest reformulation of such
questions offers an approach to solutions. If the memory of an automaton is
describable via logic, we can perhaps build a model of group and individual
memory based on automata whose interactions lead to collective memory, which
in turn influences behaviour of individual automata.

Why should one bother? In ([20]) Rohit Parikh speaks of cultural structures
providing an infrastructure to social algorithms (much as data structures do
for computational algorithms). Epistemic reasoning is an essential component
of social algorithms, as persuasively argued by Parikh. We can then see
collective memory as an essential gradient of its infrastructure creating the
‘common ground’ in which social objectives and communications are interpreted
([11]). Moreover, social algorithms such as elections need social memory if
they are to achieve their democratic purpose.

Moreover, there has been extensive research in recent years on notions of
collective agency ([27]), collective action ([23]), collective belief ([14])
and many more. However, the memory required for collective action, belief and
agency is largely assumed rather than explicitly discussed. While social
theorists extensively discuss the role of society’s needs for remembrance (as
a way of acknowledging the past and taking responsibility for it) the notion
of memory as an infrastructural need for such functions is often glossed over.
Moreover, the notions of memory that inform these discussions are embodied in
text, icons and physical tokens, much like the notebook that Wittgenstein
refers to (and objects to). Contemporary reality, with the extension of human
memory using technology, suggests that more dynamic, behavioural models of
memory, and the re-inforcing behaviour that leads to stipulation as referred
to by Sontag, may be relevant.

What follows is a very simple, perhaps very simplistic, attempt at
formalization of this notion, inspired by the study of population protocols in
distributed computing ([5]) and large anonymous games [12]. We offer this
formal model tentatively, as an initial step of a (hopefully) detailed
research programme. As it stands, the model has no agency or epistemic
attitudes or social aggregation. Instead it focusses only on how local
attempts at signalling “importance” of an observation can spread and lead to
some stable phenomenon that can be meaningfully construed as collective
memory.

The crucial element here is that individuals perceive events differently,
based on social and cultural background. The word partition would evoke the
image of equivalence classes to a combinatorist in general, but very likely,
that of a terrible tragedy first to an Indian combinatorist.

###  1.1 Related work

The literature on memory studies principally consists of two strands, one on
individual memory, substantially incorporated into psychology, and the other
on group memory, primarily on social representations of history ([8]. A major
question of interest is whether such groups manifest emergent, robustly
collective forms of memory. In general, while social context is seen to
influence remembering, the act of remembering is held to be individual.
However the literature on collective intentionality ([28]) considers
collective memory as a form of collective attention to the past. The concepts
underlying the model we discuss below are greatly inspired by the “we-mode”,
discussed by the philosopher Raimo Tuomela, though we place an additional
emphasis on patterns of social interaction (rather than the interactions
themselves).

If we admit the existence of emergent collective memory, the major question is
whether the processes of social collective memory resemble in any way the
processes of individual memory or that of small groups (like families) studied
extensively by psychologists. In an astonishing thesis from an
interdisciplinary collaboration of neurobiology, medicine, cognitive science
and anthropolgy, Anastasio at al ([3]) assert that these two processes are in
fact the same. The model we present below, taking automata as memory
representations, attempts to build a ‘social automaton’ (roughly speaking) in
this spirit, showing a correspondence of processes.

The mechanism that we use in the model is closely related to that of majority
dynamics ([16]) and spread of influence ([19]) studied in the analysis of
social networks. There are also influential logical studies of diffusion in
social networks ([6]). In other papers, we have studied similar phenomena in
the context of large games ([21], [22]). While there is a correspondence at an
intuitive level between memory systems and large games, a formal
correspondence would lead to many potential applications.

The logic we propose here is a simple linear time temporal logic (with past)
with variables and bounded quantification. There is extensive logical
literature on the role of memory in multi-agent epistemic reasoning. For
instance, the notion of bounded-recall plans has been studied in ([13], [9],
[2]), to mention some recent works. However, this literature is principally on
the interactions between individual memories; our point of departure is in
studying emergent collective memory as an entity in itself. Moreover, the
logic we discuss here is extremely poor in logical machinery, in comparison:
there is no agency and no ascription of epistemic attitudes. Rather, we
discuss only the temporal evolution of signalling interaction and the stablity
of signals. On the other hand, logical studies of social networks such as
([6]) and [18]) are closer in spirit to the automaton model we present, though
the logics themselves are different.

##  2 A model

Let $N$ denote a fixed finite set of agent names. Let ${\cal C}\subseteq
2^{N}$ be a nonempty set of nonempty subsets of $N$, referred to as
neighbourhoods over $N$. We assume $|N|>2$.

For presenting the model we will make some simplifying assumptions. We fix a
finite signal alphabet $\Gamma$ common to all agents. Let
$\Gamma=\\{\gamma_{\\_}1,\ldots,\gamma_{\\_}m\\}$.

Let $I\in{\cal C}$ and $|I|=k$. A distribution over $I$ is an $m$ tuple of
integers $\mathbf{y}=(y_{\\_}1,\ldots,y_{\\_}m)$ such that $y_{\\_}j\geq 0$
and $\Sigma_{\\_}{j=1}^{m}y_{\\_}j=k,\ \ 1\leq j\leq m$. That is, the $j$th
component of $\mathbf{y}$ gives the number of agents in the neighbourhood $I$
who give signal $\gamma_{\\_}j$. Let $\mathbf{Y}[I]$ denote the set of all
signal distributions of a neighbourhood $I$ and let
$\mathbf{Y}=\bigcup_{\\_}{I\in{\cal C}}\mathbf{Y}[I]$.

The main idea is this. All agents initially receive an external input and
assume some state. At each state, an agent produces a signal. Interactions
occur in neighbourhoods nondeterministically, and an agent who is a member of
many, could be interacting in different neighbourhoods (though every
interaction at any instant is confined to one neighbourhood). Each interaction
induces a state transition that is determined only by the distribution of
signals: it does not depend on who is signalling what, but how many are
producing each signal. Such interactions keep occurring repeatedly until a
stable configuration is reached.

Below, for $I\in{\cal C}$, we use the notation $\Gamma^{I}$ for a vector of
signals, one signal for each of the agents in $I$. Note that every such vector
induces a distribution over $\Gamma$ in $\mathbf{Y}[I]$.

We will consider systems of agents below where the set of possible states $Q$
is uniform for all agents. Thus a state transition in $Q\times Q$ is also
possible uniformly for all agents. By a triple $(\gamma,q,q^{\prime})$ we mean
that an agent who is signalling $\gamma$ changes state from $q$ to
$q^{\prime}$. $\sigma:\Gamma\to(Q\times Q)$ specifies such a signal based
change of state. Let $\Sigma$ denote the collection of such maps.

###### Definition 1

A memory system over ${\cal C}$ is a tuple $M=(Q,\delta,\iota,\omega)$, where

  * •

$Q$ is a finite set of memory states,

  * •

$\iota:N\to Q$ is the initial state,

  * •

$\omega:Q\to\Gamma$ is the signalling function, and

  * •

$\delta$ is a finite family of transition relations
$\delta_{\\_}I\subseteq(\mathbf{Y}[I]\times\Sigma)$, where $I\in{\cal C}$.

###  2.1 Dynamics

A configuration $\chi$ is an element of $Q^{N}$. Let $\omega(\chi)$ denote the
vector in $\Gamma^{N}$ induced by $\omega$. For $I\in{\cal C}$ and let
$\mathbf{y}_{\\_}I$ be a distribution of signals induced by the vector
$\omega(\chi)$ restricted to $I$.

###### Definition 2

We say that an $I$-interaction is enabled at $\chi$ if there is a transition
$(\mathbf{y},\sigma)$ in $\delta_{\\_}I$ where $\mathbf{y}$ is the
distribution induced by $\omega(\chi)$ and $\sigma\in\Sigma$ is a signal-based
change of state.

The effect of the transition is determined by $\sigma$ and the new
configuration $\chi^{\prime}$ is given by:

$\chi^{\prime}(j)=q^{\prime},{\rm~{}where~{}}j\in
I,\sigma(\omega(\chi(j))=(\chi(j),q^{\prime})$

and $\chi^{\prime}(j)=\chi(j)$, otherwise. Thus, we have a transition
$(\chi,I,\chi^{\prime})$ on configurations labelled by neighbourhoods.

The dynamics of $M$ is then given by a configuration graph $G_{\\_}M$ whose
vertices are configurations and edges are labelled by neighbourhoods: an edge
$(\chi,I,\chi^{\prime})$ is present if an $I$-interaction is enabled at $\chi$
by a transition in $\delta$ with resulting configuration $\chi^{\prime}$ as
above. Note that $\iota$ specifies an initial configuration $\chi_{\\_}0$. A
history $\rho$ is any finite or infinite path in $G_{\\_}M$ starting from
$\chi_{\\_}0$. When $\rho$ is finite, $|\rho|$ denotes its length. Let ${\cal
H}_{\\_}M$ denote the set of all maximal histories of $M$.

###  2.2 Collective memory in $M$

Consider a history $\rho=\chi_{\\_}0\chi_{\\_}1\ldots$ of system $M$. We say
that signal $\gamma$ is eventually stable for neighbourhood $I$ in $\rho$ if
there exists $k$ such that for all $\ell\geq k$, (when $\rho$ is finite, for
all $\ell$ such that $k\leq\ell\leq|\rho|$), and for all $j\in I$,
$\omega(\chi_{\\_}\ell(j))=\gamma$.

We say that $\gamma$ is in collective memory in $\rho$ if it is eventually
stable for $N$ in $\rho$: that is, no matter what interactions take place, all
agents remain in states that emit signal $\gamma$.

When we have stable configurations, we see them as formation of collective
memory. For this it is of course essential that a history allows for
signalling to spread across neighbourhoods; if some neighbourhoods never
interact, then signalling can remain confined within pockets. So we consider
spanning histories where we impose the condition that every interaction that
is infinitely often enabled (according to the transition rule) in an infinite
history takes place infinitely often. This is a typical fairness condition
used in the theory of computation, but weaker, or different, conditions may be
sufficient for many systems. For instance, we might ask that the union of
neighbourhoods in a history span all of $N$; this merely says that all the
agents have interacted at least once. Note that this depends on $\delta$: the
distributions specified may already disable some agents or neighbourhoods from
ever interacting.

###### Definition 3

We say that the system $M$ supports emergence of collective memory if, for
every spanning history $\rho$ of $M$, there exists a signal $\gamma_{\\_}\rho$
that is in collective memory in $\rho$.

###  2.3 An example

Consider a system with two signals $\\{g,b\\}$, standing for “good” and “bad”.
There are only two states: $G$ and $B$, signalling $g$ and $b$ respectively.
Initially every agent perceives some global event as good or bad. Thus $\iota$
is an arbitrary distribution of signals in the system.

The transition rule is simple: for any neighbourhood $I$, if more than half in
$I$ signal $x$, then all agents in $I$ signal $x$ in the new state. If they
are exactly even, they continue evenly matched. Let $I$ be a neighbourhood
with $k$ agents.
$\delta_{\\_}I=\\{(m,n),(g,q,G),(b,q,G)|m>n,m+n=k\\}\cup\\{(m,n),(g,q,B),(b,q,B)|m<n,m+n=k\\}\cup\\{(m,m),(s,q,q)|k=2m,s\in\\{g,b\\}\\}$.

Now we can see that whether either of the signals becomes stable in a history
depends on both the initial perception as well as which $I$-interactions are
enabled. If odd-sized neighbourhoods can interact, a signal will begin to
dominate. When the initial distribution is exactly even, and the interacting
neighbourhoods are always split evenly, neither signal dominates the other.

On the other hand, suppose that a large fraction of the population receives
the signal $g$, but $\delta$ only enables neighbourhoods with the majority
signalling $b$ and a minority signalling $g$ to interact. Then the signal $b$
emerges as a stable signal, despite the initial distribution. This can be seen
as the influence of social structures on collective memory.

Such behavioural analysis is common in the study of runaway phenomena ([7])
and so-called informational cascades ([10]).

###  2.4 Some subclasses

Consider a memory system in which all interactions are constrained to be
pairwise. In such a system, the distribution profiles are entirely irrelevant,
since given a pair of agents, there are four possible pairs of signals,
determined by their states, and we only need to specify the resulting pair of
states. Thus $\delta\subseteq Q^{4}$. Such systems have been studied as
population protocols ([5]), for which a number of technical results are known.

We also have other interesting subclasses of systems: for instance, those
where the transition relation is presented as $\delta_{\\_}k$ where $1<k\leq
N$. That is, only the size of a neighbourhood determines whether it can
interact and not the identities of agents in it. (Note that even this
restriction does not rule out the predatory dominance of a signal, as
illustrated in the example above.)

Of great interest to social systems is where ${\cal C}$ represents a
hierarchy: we have an ordering $<$ on $N$ and impose the condition that all
$I\in{\cal C}$ are downward-closed with respect to the ordering relation.

However, note that these subclasses only constrain interaction structure and
not the memory updates. This may be consonant with the discussion on
collective memory in social theory, whereby social structures (and belief
systems) constrain opportunity and influence, but what persists in social
memory may well be impervious to social structures.

###  2.5 Computational power

Note that when $|\Gamma|=d$, every distribution over $\Gamma$ is a
$d$-dimensional vector in ${\rm Nature}^{d}$. The initial state $\iota$
specifies such a distribution. Now consider a spanning history that is stably
signalling $\gamma$; we can consider this the output of the memory system for
that history. Viewed thus, every system that supports emergence of collective
memory can be said to compute a function from $\mathbf{Y}\to\Gamma$.
Alternatively, we can consider such a function to be a predicate over ${\rm
Nature}^{d}\times\\{1,\dots,d\\}$. Thus we can speak of arithmetical
predicates computable by memory systems.

An important theorem in the study of population protocols guides us to the
study of what memory systems can compute. In the study of population
protocols, systems come with an output function, mapping to the two element
output alphabet $\\{0,1\\}$ (without loss of generality). In this case we can
consider the population protocol to be computing a predicate over ${\rm
Nature}^{d}$.

Recall that a semi-linear set is a subset of ${\rm Nature}^{d}$ that is a
finite union of linear sets of the form $\\{{\bf b}+k_{\\_}1{\bf
a_{\\_}1}+\ldots+k_{\\_}m{\bf a_{\\_}m}\mid k_{\\_}1,\ldots,k_{\\_}m\in{\rm
Nature}\\}$, where ${\bf b}\in{\rm Nature}^{d}$ and ${\bf a_{\\_}1}\ldots{\bf
a_{\\_}m}$ are $d$-dimensional basis vectors.

###### Theorem 1

[4]: A predicate is computable by a population protocol iff it is semi-linear.

An alternative characterization of these predicates is that they can be
expressed in first-order Presburger arithmetic, which is first order
arithmetic on the natural numbers with addition but not multiplication.

###### Theorem 2

Given a memory system $M$, checking whether $M$ supports emergence of
collective memory is decidable. Moreover the class of predicates computable by
memory systems is exactly that of population protocols.

There are two parts to the proof. We construct a Parikh automaton ([17] that
represents the configuration space of the memory system and reduce the check
for stability of signals in the system to the nonemptiness problem for the
associated Parikh automaton. This gives us the required decision procedure.

In the process we show that every predicate computed by a memory system is
semi-linear. By the earlier theorem, such a predicate can be computed by a
population protocol. Conversely, since population protocols are a subclass of
memory systems, the predicates computed by the former are computable by memory
systems as well. (There are some details related to the output function, and
the restriction to spanning histories, which complicate the construction a
little.)

To get an intuitive idea of the construction, we define Parikh automaton
below, which in turn needs the definition of Presburger arithmetic.

Firstly, let $\Delta=\\{a_{\\_}1,\ldots a_{\\_}m\\}$ be any finite alphabet,
and $w\in\Delta^{*}$. The Parikh image of $w$ counts the number of occurrences
of each letter of the alphabet in $w$. Formally, we have the map
$\pi:\Delta^{*}\to{\rm Nature}^{m}$ given by: $\pi(a_{\\_}i)=e_{\\_}i$ and
$\pi(uv)=\pi(u)+\pi(v)$, where $e_{\\_}i$ is the unit vector of length $m$
where the $i^{th}$ coordinate is $1$.

Clearly the map $\pi$ can be lifted to alphabets of the form $\Delta\times D$
where $D\subseteq{\rm Nature}^{d}$: $\pi(a_{\\_}i,\hat{k})=\hat{k}$ and
$\pi(uv)=\pi(u)+\pi(v)$. We can also consider the alphabetic projection into
$D^{*}$: $\lambda(a_{\\_}i,\hat{k})=a_{\\_}i$ and
$\lambda(uv)=\lambda(u)\lambda(v)$.

Presburger arithmetic is first order logic with the only atomic formulas of
the form $t~{}rel~{}t^{\prime}$ where $t$ and $t^{\prime}$ are terms, and
$rel\in\\{>,<,\geq,\leq\\}$. Terms are built from two constants $0$ and $1$,
and variables, using addition and $n\cdot t$ where $n\in{\rm Nature}$.
Formulas are interpreted over the structure ${\cal N}=({\rm
Nature},+,\cdot,0,1)$. When $\phi(\hat{x})$ is a formula with free variables
$\hat{x}$ the notion ${\cal N},\hat{k}\models\phi(\hat{x})$ is defined in the
standard fashion.

Given $D\subseteq{\rm Nature}^{d}$ and $L\subseteq(\Delta\times D)^{*}$, and a
formula $\phi$ of Presburger arithmetic, we define
$L\lceil_{\\_}\phi=\\{\lambda(w)\mid{\cal N},\pi(w)\models\phi(\hat{x})\\}$.

###### Definition 4

A Parikh automaton of dimension $d>0$ is a pair $(A,\phi)$ where
$\phi(x_{\\_}1,\ldots,x_{\\_}d)$ is a formula of Presburger arithmetic over
$d$ variables, and $A$ is a finite word automaton with the finite alphabet
$\Delta\times D$ where $D\subseteq{\rm Nature}^{d}$. We say that $(A,\phi)$
recognizes $L(A,\phi)=L(A)\lceil_{\\_}\phi$, where $L(A)$ is the language
recognized by the automaton $A$.

For the construction we need, there are some points to note. Configurations of
memory systems carry states, from which we compute signal distributions which
cause state changes. For the Parikh automaton, transitions are labelled by
distributions. More importantly we need to carry the neighbourhood based
signalling in the transitions of the Parikh automaton. While these are matters
of detail, the harder part of the proof is the definition of the formula of
Presburger arithmetic, for which we closely follow the proof method for
population protocols ([4]).

##  3 A logic for the rationale

We now turn our attention to our principal logical interest, namely, the
rationale by which agents decide what signals are chosen. This is surely
complex, depending on the systems being modelled. Here we propose a minimal
logic, in which agents evaluate signals based on their own evaluation of the
current state and their evaluation of signals from the neighbourhood,
depending on the signal distributions.

Let $V$ be a countable set of variables. Let the terms of the logic be defined
as

$\mathbf{\tau}::=i\ |\ x,\ i\in N,\ x\in V$

That is, a term is either an agent name or a variable (which takes agents as
its values). Let $\mathcal{P}$ denote a countable set of atomic propositional
symbols.

The formulas of the logic are built using the following syntax:

$\begin{split}\Phi::=&\tau_{\\_}1=\tau_{\\_}2\ |\ \tau\in I\ |\
p@\tau,p\in\mathcal{P}\ |\ \gamma@\tau,\gamma\in\Gamma\ |\ \neg\varphi\ |\\\
&\varphi_{\\_}1\lor\varphi_{\\_}2\ |\ \ominus\varphi\ |\ \bigcirc\varphi\ |\
\Diamond\kern-5.39993pt{\raisebox{1.07639pt}{\rm-}}\kern 1.75003pt\varphi\ |\
\Diamond\varphi\ |\ \sharp x\cdot\varphi(x)~{}op~{}k\end{split}$

where $\tau_{\\_}1$ and $\tau_{\\_}2$ are terms, $I\in{\cal C}$,
$op\in\\{=,\neq,<,\leq,>,\geq\\}$ and $k\in\\{0,\ldots,|N|\\}$.

The formula $\tau\in I$ asserts that the agent denoted by the term $\tau$ is a
member of the neigbourhood $I$. $p@\tau$ asserts that the condition $p$ holds
for agent $\tau$, and $\gamma@\tau$ specifies that $\tau$ is signalling
$\gamma$ at that instant. $\sharp$ is a counting quantifier, and $\sharp
x\cdot\varphi(x)\geq k$ (for example) says that at least $k$ agents support
the assertion $\phi$ at the instant. The modalities $\ominus$ and $\bigcirc$
denote the predecessor and successor instants, whereas
$\Diamond\kern-5.39993pt{\raisebox{1.07639pt}{\rm-}}\kern 1.75003pt$ and
$\Diamond$ denote some time in the past and some time in the future,
respectively. Their dual modalities are denoted
$\Box\kern-5.39993pt{\raisebox{1.07639pt}{\rm-}}\kern 1.75003pt$ and $\Box$
respectively. We talk of free and bound occurrences of variable $x$ in formula
$\varphi$ in the standard manner. $\varphi$ is said to be a sentence if it has
no free occurrences of variables.

The existential and universal quantifiers are defined easily: $\exists
x\cdot\phi(x)=\sharp x\cdot\varphi(x)>0$ and $\forall
x\cdot\phi(x)=\neg\exists x\neg\phi(x)$. We use the abbreviation
$\gamma@I=\forall x\cdot(x\in I\supset\gamma@x)$ to denote that all agents in
the neighbourhood signal $\gamma$.

The formula $\Box\forall x\cdot\gamma@x$ is denoted $stable(\gamma)$. The
formula $\displaystyle\bigvee_{\\_}{\gamma\in\Gamma}stable(\gamma)$ is special
and is called emergence.

The semantics is defined on histories. A model is a tuple
$(M,\mathit{val},\eta)$, where $M$ is a memory system, $\eta:V\to N$ denote an
assignment of agent variables to agent names and $\mathit{val}:Q\to
2^{\mathcal{P}}$ is the propositional valuation map. $\mathit{val}$ is lifted
to configurations by the map $\hat{\mathit{val}}:Q^{N}\to(N\to
2^{\mathcal{P}})$ by: $\hat{\mathit{val}}(\chi)(i)=\mathit{val}(\chi(i))$.

Let $\rho\in{\cal H}_{\\_}M$ be a finite or infinite history
$\rho=\chi_{\\_}0\chi_{\\_}1\ldots$. The notion that $\rho,k\models\phi$ is
defined in the standard fashion, for $k\geq 0$.

  * •

$\rho,k\models\tau_{\\_}1=\tau_{\\_}2$ iff
$\eta(\tau_{\\_}1)=\eta(\tau_{\\_}2)$.

  * •

$\rho,k\models\tau\in I$ iff $\eta(\tau)\in I$.

  * •

$\rho,k\models p@\tau$ iff $p\in\hat{val}(\rho_{\\_}k)(\eta(\tau))$.

  * •

$\rho,k\models\gamma@\tau$ iff $\omega(\rho_{\\_}k(\tau))=\gamma$.

  * •

$\rho,k\models\neg\varphi$ iff $\rho,k\not\models\varphi$.

  * •

$\rho,k\models\varphi_{\\_}1\lor\varphi_{\\_}2$ iff
$\rho,k\models\varphi_{\\_}1$ or $\rho,k\models\varphi_{\\_}2$.

  * •

$\rho,k\models\ominus\varphi$ iff $k>0$ and $\rho,k-1\models\varphi$.

  * •

$\rho,k\models\bigcirc\varphi$ iff there exists a successor instant in the
history and $\rho,k+1\models\varphi$.

  * •

$\rho,k\models\Diamond\kern-5.39993pt{\raisebox{1.07639pt}{\rm-}}\kern
1.75003pt\varphi$ iff there exists $\ell\leq k$ such that
$\rho,\ell\models\varphi$.

  * •

$\rho,k\models\Diamond\varphi$ iff there exists $\ell\geq k$ such that
$\rho,\ell\models\varphi$.

  * •

$\rho,k\models\sharp x\cdot\varphi(x)~{}op~{}k$ iff
$\mid\\{j\mid\rho,k\models\varphi[j/x]\\}\mid~{}op~{}k$.

The notions of satisfiability and validity are standard. Given a model
$(M,\mathit{val})$ and a sentence $\phi$ by $M\models\varphi$ we denote that
for all histories $\rho$ in ${\cal H}_{\\_}M$, $\rho,0\models\varphi$.

###  3.1 Examples

It is easily seen that specific distributions can be described in the logic.
For instance consider the distribution where there are 100 agents, 30 of whom
signal $a$ and the rest signal $b$. We can specify this as:

$\sharp x\cdot\gamma_{\\_}a@x=30\land\sharp x\cdot\gamma_{\\_}b@x=70$

With inequalities, classes of distributions that lead to the same signalling’
behaviour can be specified.

Further the structure of interaction in histories can be constrained in the
logic:

$\exists x\cdot(x\in I\supset\Box(x\in I))$

This asserts that once an agent participates in an interaction in the history,
it continues to participate in every interaction in the history. (In social
theory, such persistent actors in the structure are associated with memorials
that keep reminding everyone of a memory token.)

The state transition structure of memory systems can be described only to a
limited extent since the logic is first order and the state information which
may include modular counting of signals cannot be expressed in it. However,
propositional updates based on signal distributions can be specified.

The logic can describe various kinds of signalling schemes by agents.

  * •

Signal $a$ and $b$ alternatively:

$\Box[(\ominus\gamma_{\\_}a@i\supset\gamma_{\\_}b@i)\land(\ominus\gamma_{\\_}b@i\supset\gamma_{\\_}a@i)]$

  * •

If more than 5 agents in my neighbourhood previously signalled $a$ then I
signal $a$:

$(i\in I\land\sharp x.(x\in
I\land\ominus\gamma_{\\_}a@x)>5)\supset\gamma_{\\_}a@i$

  * •

$\gamma$ is collective memory:

$\Diamond\Box(\forall x.\gamma@x)$

  * •

$\gamma$ is collective amnesia:

$\Diamond\Box(\forall x.\neg\gamma@x)$

However, in terms of validities, the logic has little structure to force
validities beyond that of linear time temporal logic. The interest of the
logic is mainly in its role as a specification language for requirements on
memory systems, and hence we are more interested in checking whether a
specific memory system satisfies such a specification.

###  3.2 Model checking

In general, first order temporal logics are highly undecidable and non-
axiomatizable. However, what we have here is bounded quantification, since the
set of agents over which we quantify, is fixed and finite. So we can
effectively eliminate quantifiers and translate formulas into propositional
linear time temporal logic. Thus satisfiability is decidable via automaton
construction, but yet, extracting a memory system from the formula automaton
has some interesting details.

The model checking problem for the logic asks, given a model
$(M,\mathit{val})$ and a sentence $\varphi$, whether $M\models\varphi$.

###### Theorem 3

The model checking problem for the logic is decidable in time linear in $M$
and singly exponential in $\varphi$.

In this case, we construct a Parikh automaton that represents the
configuration space of the memory system, and take its product with the
formula automaton associated with the given sentence $\varphi$. The
construction is straightforward, though not entirely trivial.

##  4 Discussion

We began with the intention of reasoning about collective memory. How do
systems of signalling in neighbourhoods embody reasoning?

Firstly, it should be clear that the history model and the logical language
are rich enough to talk about the “remembrance of things past”. However, the
model assumes perfect observability for agents within neighbourhoods within a
fixed interaction structure. Both of these assumptions need to be relaxed,
leading to epistemic logics.

Such a logical exercise is not sufficient in itself to uncover the process of
stipulation mentioned by Sontag, or the interdependence between memory and
reasoning demanded by Wittgenstein. However, in our opinion, the model holds
considerable promise. For achieving the richness required, we hold two
features to be essential: reinforcement of memory that comes through repeated
interactions inside local neighbourhoods, but not confined to those
neighbourhoods; complex social rules that determine influence in signalling.
Elements of both are present in this model.

Further, while we have presented simple stability as the basic notion of
collective memory which is persistent, we can symmterically study notions like
collective amnesia in the model whereby signals predominant in the system lose
out in interactions and ultimately vanish. Incorporating both, to study
collective memory of some events while at the same time forgetting others
presents no logical difficulties but makes the model considerably complex to
reason about, requiring a structural insight for simplification.

Moreover, we have taken collective memory to mean the entire system. We can
instead parameterize such memory by a subset of agents to get group notions of
memory; this is relavant in the study of notions such as common ground for
communication ([11]).

It is interesting to consider dynamic memory systems, whereby endogenous
changes in signalling behaviour can lead to altering interaction structures
leading to new update rules. In particular, neighbourhoods need not be static,
but may expand and contract. This is analogous to dynamic form games as we
have studied elsewhere ([21]).

Social choice theory offers a variety of methods for aggregation of
information from individuals for collectives, but these are static rules.
Automata models such as the ones studied here can offer dynamic methods of
aggregation whereby we formulate ‘local’ aggregation rules which are applied
repeatedly. Whether this can lead to meaningful insight for social theories
remains to be seen, offering interesting technical questions for study in the
meanwhile.

Interactions in the model are nondeterministic. Stochastic models of
interactions may be more appropriate for social behaviour, relevant to social
network studies such as ([16], [19]). However, logicising the rationale of
such interaction would perhaps need a different approach.

##  5 Acknowledgement

We thank Oliver Roy and Wang Yi for discussions on the theme, and the TARK
reviewers for thoughtful remarks and helpful comments.

## References

  * [1]
  * [2] Natasha Alechina & Brian Logan (2010): _Belief ascription under bounded resources_.  Synth. 173(2), pp. 179–197, 10.1007/s11229-009-9706-6.
  * [3] Thomas J Anastasio, Kristen Ann Ehrenberger, Patrick Watson & Wenyi Zhang (2012): _Individual and collective memory consolidation: Analogous processes on different levels_.  MIT Press, 10.7551/mitpress/9173.001.0001.
  * [4] Dana Angluin, James Aspnes, David Eisenstat & Erik Ruppert (2007): _The computational power of population protocols_.  Distributed Computing 20(4), pp. 279–304, 10.1007/s00446-007-0040-2.
  * [5] James Aspnes & Eric Ruppert (2009): _An Introduction to Population Protocols_ , pp. 97–120.  Springer Berlin Heidelberg, Berlin, Heidelberg, 10.1007/978-3-540-89707-15.
  * [6] Alexandru Baltag, Zoé Christoff, Rasmus K. Rendsvig & Sonja Smets (2019): _Dynamic Epistemic Logics of Diffusion and Prediction in Social Networks_.  Studia Logica 107(3), pp. 489–531, 10.1007/s11225-018-9804-x.
  * [7] Abhijit V. Banerjee (1992): _A Simple Model of Herd Behaviour_.  The Quarterly Journal of Economics 107(3), pp. 797–817, 10.2307/2118364.
  * [8] Jeffrey Andrew Barash (2016): University of Chicago Press, 10.7208/9780226399294-toc.
  * [9] Francesco Belardinelli, Alessio Lomuscio & Emily Yu (2020): _Model Checking Temporal Epistemic Logic under Bounded Recall_.  In: Proceedings AAAI 2020, AAAI Press, pp. 7071–7078, 10.1609/aaai.v34i05.6193.
  * [10] Zoé Christoff & Jens Ulrik Hansen (2015): _A logic for diffusion in social networks_.  J. Appl. Log. 13(1), pp. 48–77, 10.1016/j.jal.2014.11.011.
  * [11] Herbert H Clark & Susan E Brennan (1991): _Grounding in communication_.  American Psychology Association, 10.1037/10096-006.
  * [12] C. Daskalakis & C. H. Papadimitriou (2007): _Computing equilibria in anonymous games_.  In: Proceedings of the 48th symposium on Foundations of Computer Science (FOCS), IEEE Computer Society Press, pp. 83–93, 10.1109/FOCS.2007.24.
  * [13] Kaya Deuser & Pavel Naumov (2020): _On composition of bounded-recall plans_.  Artif. Intell. 289, p. 103399, 10.1016/j.artint.2020.103399.
  * [14] Margaret Gilbert (1987): _Modelling Collective Belief_.  Synthese 73(1), pp. 185–204, 10.1007/BF00485446.
  * [15] Maurice Halbwachs (1950): _The Collective Memory_.  Harper and Row, New York.
  * [16] David Kempe, Jon Kleinberg & Éva Tardos (2015): _Maximizing the Spread of Influence through a Social Network_.  Theory of Computing 11(4), pp. 105–147, 10.4086/toc.2015.v011a004.
  * [17] Felix Klaedtke & Harald Rueß (2003): _Monadic Second-Order Logics with Cardinalities_.  In Jos C. M. Baeten, Jan Karel Lenstra, Joachim Parrow & Gerhard J. Woeginger, editors: Automata, Languages and Programming, Springer Berlin Heidelberg, pp. 681–696, 10.1007/3-540-45061-054.
  * [18] Fenrong Liu, Jeremy Seligman & Patrick Girard (2014): _Logical dynamics of belief change in the community_.  Synthese 191(11), pp. 2403–2431, 10.1007/s11229-014-0432-3.
  * [19] Elchanan Mossel, Joe Neeman & Omer Tamuz (2013): _Majority dynamics and aggregation of information in social networks_.  Autonomous Agents and Multi-Agent Systems 28(3), p. 408–429, 10.1007/s10458-013-9230-4.
  * [20] Rohit Parikh (2012): _What Is Social Software?_ , pp. 3–13.  LNCS 7010, Springer, 10.4204/EPTCS.
  * [21] Soumya Paul & R. Ramanujam (2013): _Dynamics of Choice restriction in Large Games_.  IGTR 15(4), 10.1142/S0219198913400318.
  * [22] Soumya Paul & R. Ramanujam (2014): _Subgames within Large Games and the Heuristic of Imitation_.  Stud Logica 102(2), pp. 361–388, 10.1007/s11225-014-9549-0.
  * [23] William G. Roy & Rachel Parker-Gwin (1999): _How Many Logics of Collective Action?_ Theory and Society 28(2), pp. 203–237, 10.1023/A:1006946310119.
  * [24] Mihai Rusu (2017): _Transitional Politics of Memory: Political Strategies of Managing the Past in Post-communist Romania_.  Europe-Asia Studies, pp. 260–282, 10.1080/09668136.2017.1380783.
  * [25] Susan Sontag (2003): _Regarding the pain of others_.  Picador, 10.3917/dio.201.0127.
  * [26] John Sutton (2014): _Remembering as Public Practice: Wittgenstein, memory, and distributed cognitive ecologies_.  10.1515/9783110378795.409.
  * [27] Allard Tamminga, Hein Duijf & Frederik Van De Putte (2020): _Expressivity results for deontic logics of collective agency_.  Synthese, pp. 260–282, 10.1007/s11229-020-02597-0.  Forthcoming.
  * [28] Raimo Tuomela (2013): _Social Ontology: Collective Intentionality and Group Agents_.  OUP USA, 10.1515/jso-2014-0040.
  * [29] Ludwig Wittgenstein (1967): _Zettel_.  Univ of California Press.


# Utility Theory for Sequential Decision Making

Mehran Shakerinava  Siamak Ravanbakhsh

###### Abstract

The von Neumann-Morgenstern (VNM) utility theorem shows that under certain
axioms of rationality, decision-making is reduced to maximizing the
expectation of some utility function. We extend these axioms to increasingly
structured sequential decision making settings and identify the structure of
the corresponding utility functions. In particular, we show that memoryless
preferences lead to a utility in the form of a per transition reward and
multiplicative factor on the future return. This result motivates a
generalization of Markov Decision Processes (MDPs) with this structure on the
agent’s returns, which we call Affine-Reward MDPs. A stronger constraint on
preferences is needed to recover the commonly used cumulative sum of scalar
rewards in MDPs. A yet stronger constraint simplifies the utility function for
goal-seeking agents in the form of a difference in some function of states
that we call potential functions. Our necessary and sufficient conditions
demystify the reward hypothesis that underlies the design of rational agents
in reinforcement learning by adding an axiom to the VNM rationality axioms and
motivates new directions for AI research involving sequential decision making.

Machine Learning, ICML

##  1 Introduction

Utility theory is a proposal for rational behavior when faced with risky
outcomes. Maximization of expected utility was originally hypothesized by
Bernoulli (Bernoulli, 1738, 1954) as a solution to the St. Petersburg paradox,
in which diminishing marginal utility explains human risk aversion in a game
of chance. This hypothesis was later grounded by von Neumann and Morgenstern
(VNM), such that as long as one’s preferences satisfied certain rationality
axioms, one’s behavior could be explained as maximization of some utility
function in expectation (von Neumann & Morgenstern, 1947). This paper aims to
extend utility theory to sequential decision making. Our primary motivation is
to ground what is known as the _reward hypothesis_ in reinforcement learning
(RL): “That all of what we mean by goals and purposes can be well thought of
as maximization of the expected value of the cumulative sum of a received
scalar signal (called reward).” (Sutton & Barto, 2018). While the connection
between the reward in RL and the concept of utility in game theory has not
gone unnoticed (_e.g._ , Jaquette (1976)), the adequacy of cumulative sum of
scalar rewards still remains a hypothesis (Sutton & Barto, 2018).

Sequential Decision MakingMemoryless (AR-MDP)Additive (MDP)Path-Oblivious
Figure 1:  We axiomatize preference relations in sequential decision making
and identify the corresponding structure for the utility function. The
memorylessness, additivity, and path-obliviousness axioms impose successively
stronger constraints on preferences over trajectories in sequential decision
making. As a result, the corresponding utility functions become more
structured. In particular, the additivity axiom leads to the additive reward
structure of the MDP. Memoryless preferences lead to a more general AR-MDP,
while path-oblivious preferences that only consider start and end states lead
to a utility that is expressed as change in a potential function of states.

We identify necessary and sufficient conditions in sequential decision making
that guarantee the existence of scalar reward signals, whose cumulative sum
can represent any set of preferences over trajectories. This condition is
presented as a single additional axiom to those of VNM, which itself justifies
maximization of expected utility. Moreover, we place this particular structure
of the utility function, _i.e._ , cumulative sum of scalar rewards, among
several other possibilities that are based on more or less stringent
assumptions. In particular, we show that applying a memorylessness property to
preference relations leads to a more general setup than Markov Decision
Processes (MDPs) in which the utility is not the cumulative sum of rewards,
but rather each step in addition to its additive contribution to the reward
has a multiplicative effect on future rewards. We call this generalization of
an MDP, an _Affine-Reward MDP (AR-MDP)_.

In the following, first, we review the foundations of utility theory in
Section 2. Then, in Section 3 through Section 6, we consider a successively
more structured setting for sequential decision making through additional
axioms that constrain preferences over trajectories. We identify a one-to-one
correspondence with an increasingly structured utility function in each case.
These utility functions include a utility in which each state-transition has
an associated additive reward and a multiplicative factor on future rewards as
a result of a Markovian assumption (Section 4), commonly used cumulative
rewards (Section 5), and utilities that are expressed as a difference of
potentials in the case of goal-seeking agents (Section 6). In Appendix B we
consider preference relations that have not been fully specified and how, in
some cases, it is possible to uniquely complete them. Section 7 briefly
reviews some of the relevant literature on utility theory. Finally, Section 8
discusses some implications of our results and considers possible extensions
and exciting future directions that are motivated by these findings.

##  2 Background

We are interested in studying “rational” decision-making. A pre-requisite to
decision-making is the ability to compare outcomes through a _preference
relation_. But what does it mean for a preference relation to be rational? We
will specify the meaning of rationality by introducing _axioms_ that agree
with our intuitive understanding of rationality.

Let $\mathcal{O}$ denote the set of possible outcomes111We will assume that
$\mathcal{O}$ is countable.. We write $x\succsim y$ if we prefer outcome $x$
to outcome $y$ (denoted as $x\succ y$) or if we are indifferent between the
two outcomes (denoted as $x\approx y$). When $x\approx y$ we say that $x$ and
$y$ are equivalent.

######  Axiom 2.1 (Completeness).

For all $x,y\in\mathcal{O}$, $x\succsim y$ or $y\succsim x$, _i.e._ , any pair
of outcomes are comparable.

######  Axiom 2.2 (Transitivity).

For all $x,y,z\in\mathcal{O}$, if $x\succsim y$ and $y\succsim z$, then
$x\succsim z$.

Note that completeness implies reflexivity (_i.e._ , for all
$x\in\mathcal{O}$, $x\succsim x$). Such preference relations are also
sometimes known as a _total preorder_.

Let us now consider uncertain outcomes. When a choice has an uncertain
outcome, there will be a probability $p(x)$ of obtaining each outcome $x$. We
will refer to such a choice as a lottery222A lottery is identified by a
probability distribution $p$ over the outcome space $\mathcal{O}$, so in this
sense, lotteries can be thought of as probability distributions.. We may also
consider compound lotteries, _i.e._ , lotteries of lotteries. Such lotteries
can always be simplified into a single non-compound lottery. We will denote a
general lottery of $n$ items as $\sum_{i=1}^{n}p(x_{i})x_{i}$, where each
$x_{i}$ is an outcome or a lottery. You can avoid confusing this notation with
an expectation by noting that outcomes can’t be multiplied and added.

######  Example 2.1.

The lottery

$L=\frac{1}{2}x+\frac{1}{3}y+\frac{1}{6}M$

means there is a $\frac{1}{2}$ chance of obtaining outcome $x$, a
$\frac{1}{3}$ chance of obtaining outcome $y$, and a $\frac{1}{6}$ chance of
obtaining an outcome according to another lottery $M$.

The framework introduced thus far does not allow us to make optimal decisions
when faced with _uncertain outcomes_. Suppose, for example, that there are
three outcomes: $x\succ y\succ z$. When faced with a choice between $y$ and
$\frac{1}{2}x+\frac{1}{2}z$ we are not able to say which choice is better. The
reason is that there is a fundamental issue with a preference over outcomes:
It does not specify how much we _value_ each outcome. For example, in this
case, we know that $x$ is preferred to $y$, but how much more is it preferred?
To solve this issue, we must move to _preferences over lotteries_. We will
restate our current axioms to apply to lotteries and add two more axioms. Let
$\mathcal{L}$ be the set of all lotteries of outcomes.

######  Axiom 2.3 (Completeness).

For all $L,M\in\mathcal{L}$, $L\succsim M$ or $M\succsim L$, _i.e._ , any pair
of lotteries are comparable.

######  Axiom 2.4 (Transitivity).

For all $L,M,N\in\mathcal{L}$, if $L\succsim M$ and $M\succsim N$, then
$L\succsim N$.

######  Axiom 2.5 (Continuity).

For all lotteries $L\succsim M\succsim N$, there exists $p\in[0,1]$ such that
$pL+(1-p)N\approx M$.

######  Axiom 2.6 (Independence).

For all $L,M,N\in\mathcal{L}$ and for all $p\in[0,1]$, $L\succsim
M\iff(1-p)L+pN\succsim(1-p)M+pN.$ (1)

The continuity axiom essentially states that, as the probabilities of a
lottery vary, our valuation of the lottery changes smoothly.

The independence axiom can be understood by considering each compound lottery
as a two-stage process. In the first stage, a coin with a probability $p$ of
landing heads is tossed for picking a lottery, and in the second stage, an
outcome is sampled from that lottery. If the coin lands heads, we get $N$ in
both cases, but if it lands tails, we can get either $L$ or $M$. We may
imagine that the coin has already been tossed, but the result has not yet been
revealed to us. If the coin landed heads, our decision will not matter, but if
it landed tails, we prefer to choose $L$. It seems reasonable, therefore, that
$(1-p)L+pN$ should be preferred to $(1-p)M+pN$. The same reasoning also
applies in the opposite direction. A corollary of independence is that, in a
compound lottery, we can replace one lottery with another equivalent lottery,
and the compound lotteries will be equivalent.

These four axioms are known as the von Neumann-Morgenstern (VNM) axioms and a
preference relation over lotteries that satisfies these axioms is called VNM-
rational.

It would be convenient if we could assign a value to each lottery such that
comparing these values produces the same result as the preference relation.
Such a function, if it exists, can be thought of as an _encoding_ of its
corresponding preference relation. This concept is captured by utility
functions.

######  Definition 2.2 (Utility function).

A utility function is a function $u:\mathcal{L}\to\mathbb{R}$, such that for
all $L,M\in\mathcal{L}$,

$L\succsim M\iff u(L)\geq u(M).$ (2)

Interestingly, VNM-rationality induces a utility function that is _unique_ up
to positive affine transformation such that the utility of any lottery is
equal to the _expected_ utility of its outcomes. This fact is formalized
below.

######  Theorem 2.3 (Von Neumann-Morgenstern utility theorem).

A preference relation satisfies the VNM axioms, if and only if it can be
represented by a utility function such that for all lotteries with probability
$p$,
$u\left(\sum_{x\in\mathcal{O}}p(x)x\right)=\sum_{x\in\mathcal{O}}p(x)u(x).$
(3) Furthermore, this utility function is unique up to positive affine
transformation.

###### Proof.

See the appendix of von Neumann & Morgenstern (1953) for the original proof or
Maschler et al. (2013) for a simplified proof. ∎

Utility functions that satisfy Equation 3 are called linear utility functions.
A utility function that represents a VNM-rational preference relation is
called a VNM-utility. The VNM utility theorem justifies the objective of
maximizing expected utility. However, one must make sure that the utility that
is being maximized is indeed a VNM-utility.

######  Example 2.4.

Consider the set of outcomes $\mathcal{O}=\\{\square,\circ,\triangle,\star\\}$
along with a VNM-rational preference relation $\succsim$ on its set of
lotteries $\mathcal{L}$. Suppose that
$\square\succ\circ\succ\triangle\succ\star$.

We aim to construct a linear utility function $u$ on $\mathcal{L}$. We start
by setting $u(\square)=1$ and $u(\star)=0$. By continuity, there exists some
$p$ such that $p\ \square+(1-p)\ \star\approx\circ$, so we set $u(\circ)=p$.
There also exists some $q<p$ such that $q\ \square+(1-q)\
\star\approx\triangle$, so we set $u(\triangle)=q$. Finally, we set the
utility of any lottery to the expected utility of its outcomes. The
constructed utility function is thus linear and one can show that it matches
our preferences. Freedom in picking $u(\square)$ and $u(\star)$, as long as
$u(\square)>u(\star)$, is what makes the utility function free up to positive
affine transformation.

Proofs of the VNM utility theorem show the existence of a linear utility
function by constructing it in the same way as this example.

##  3 Extension to Sequential Decision Making

We will now extend classical utility theory to sequential decision making. In
this setting, an outcome will no longer depend on a single decision but on a
sequence of decisions. Our model of sequential decision making consists of an
agent that is interacting with a world. The world is modeled as a (countable)
set of states $\mathcal{S}$. At each time-step $t\in\mathbb{N}$ the agent
finds itself in state $s_{t}\in\mathcal{S}$ and must choose an action $a_{t}$
from a set $\mathcal{A}$ of actions; some of these actions may be illegal in
state $s_{t}$.

We will assume that the result of an action depends only on the action and the
current state (_i.e._ , Markov property). The result of an action, if legal,
is to stochastically transition to a state and possibly terminate the
interaction. The transition probabilities are given by
$\mathbb{P}:\mathcal{S}\times\mathcal{A}\to\mathcal{D}(\mathcal{S})\cup\\{0\\}$,
where $\mathcal{D}(\mathcal{S})$ is the space of probability distributions
over $\mathcal{S}$ and $0$ indicates that the state-action pair is illegal.
The termination probabilities are given by
$\mathbb{T}:\mathcal{S}\times\mathcal{A}\times\mathcal{S}\to[0,1]$. The tuple
$(\mathcal{S},\mathcal{A},\mathbb{P},\mathbb{T})$ will be called a Controlled
Markov Process (CMP).

We define a transition to be a triplet
$(s,a,s^{\prime})\in\mathcal{S}\times\mathcal{A}\times\mathcal{S}$, with the
interpretation that the agent chooses action $a$ in state $s$ and transitions
to state $s^{\prime}$. A trajectory of length $n$ is a sequence of transitions
$\langle(s_{i},a_{i},s^{\prime}_{i})\rangle_{i\in\\{1,...,n\\}}$ where
$s^{\prime}_{i}=s_{i+1}$ for all $i\in\\{1,...,n-1\\}$. For each state $s$,
there is an empty trajectory $\epsilon_{s}$ that starts and ends in state $s$.
We will refer to all of these empty trajectories collectively as the empty
trajectory and denote it with $\epsilon$. The start and end state of
$\epsilon$ will be clear from context. We will use $\mathcal{T}$ as a short-
hand for the set of transitions
$\mathcal{S}\times\mathcal{A}\times\mathcal{S}$ and we will let
$\mathcal{T}^{*}$ denote the set of finite trajectories.

In sequential decision making, the set of outcomes will be the set of finite
trajectories of a CMP333The only role of a CMP in the case of utility theory
is to specify which trajectories have a non-zero probability and get included
in the set of outcomes. The probabilities themselves and the termination
probabilities don’t matter., _i.e._ , $\mathcal{O}=\mathcal{T}^{*}$, and
preferences will be defined over _lotteries of trajectories_.

The VNM utility theorem may be applied in this setting, without any additional
assumptions, to assign utilities to all finite trajectories of a CMP. However,
each trajectory would then be considered as an entirely independent entity,
and none of the structure of the CMP would be incorporated into the utility
function. Furthermore, an optimal decision-making function would, generally,
have to be a function of the agent’s entire past trajectory. We will refer to
a decision-making function of this general form as a policy. More
specifically, a policy is a function
$\pi:\mathcal{T}^{*}\to\mathcal{D}(\mathcal{A})$.

######  Example 3.1.

We will use the CMP seen in Figure 2 as our running example. For simplicity,
we will assume that preferences do not depend on the actions in a trajectory,
and thus, trajectories can be written as a sequence of visited states. We also
assume that $\langle s_{0},\hat{s}_{1},s_{2}\rangle\succsim\langle
s_{0},s_{1},s_{2}\rangle$ and $\langle s_{2},\hat{s}_{3}\rangle\succsim\langle
s_{2},s_{3}\rangle$.

With only the VNM axioms, all orderings of the trajectories are possible. For
example, we could have

$\displaystyle\langle s_{0},\hat{s}_{1},s_{2},\hat{s}_{3}\rangle$
$\displaystyle\succsim\langle s_{0},\hat{s}_{1},s_{2},s_{3}\rangle,\
\text{and}$ $\displaystyle\langle s_{0},s_{1},s_{2},s_{3}\rangle$
$\displaystyle\succsim\langle s_{0},s_{1},s_{2},\hat{s}_{3}\rangle.$

Then, an agent that started from state $s_{0}$ and is now in state $s_{2}$
will have to consider its past trajectory to decide if it prefers to go to
state $\hat{s}_{3}$ or state $s_{3}$.

$s_{0}$$\hat{s}_{1}$$s_{1}$$s_{2}$$\hat{s}_{3}$$s_{3}$ Figure 2: The CMP that
we use as our running example. We ignore actions and write trajectories as a
sequence of visited states. We also assume $\langle
s_{0},\hat{s}_{1},s_{2}\rangle\succsim\langle s_{0},s_{1},s_{2}\rangle$ and
$\langle s_{2},\hat{s}_{3}\rangle\succsim\langle s_{2},s_{3}\rangle$.

It seems reasonable to assume that in a Markovian world (_e.g._ , a CMP),
where all the information relevant for predicting the future is contained in
the present state, all the information necessary to _compare_ future events
should also be contained in the present state. To incorporate such a Markovian
assumption, we will need to constrain preference relations through an
additional axiom, introduced in the next section.

##  4 Memoryless Sequential Decision Making

Before introducing the axiom, we need to define a concatenation operator
“$\cdot$” for trajectories. It has the property that it distributes over the
addition operation used to create lotteries, that is, for all states $s$,
trajectories $\tau$ and $\tau^{\prime}$ that end in state $s$, and
lotteries444By a lottery that starts from state $s$, we mean a lottery of
trajectories that start from state $s$. $L$ that start from state $s$,

$(p\tau+(1-p)\tau^{\prime})\cdot L=p(\tau\cdot L)+(1-p)(\tau^{\prime}\cdot
L).$ (4)

We are now ready to augment the VNM axioms with the following axiom which
asserts that one should be able to ignore the past trajectory when comparing
future lotteries.

######  Axiom 4.1 (Memorylessness).

For all states $s$, trajectories $\tau$ that end in state $s$, and lotteries
$L$ and $M$ that start from state $s$, $\tau\cdot L\succsim\tau\cdot M\iff
L\succsim M.$ (5)

We will use the shorthand, VNM$\star$ axioms, for the VNM axioms along with
the memorylessness axiom, and similarly for other terms that include VNM.

######  Example 4.1.

Consider the running example of Figure 2 and the recall our preferences:
$\langle s_{0},\hat{s}_{1},s_{2}\rangle\succsim\langle
s_{0},s_{1},s_{2}\rangle$ and $\langle s_{2},\hat{s}_{3}\rangle\succsim\langle
s_{2},s_{3}\rangle$. Then, memorylessness implies

$\displaystyle\langle s_{0},\hat{s}_{1},s_{2},\hat{s}_{3}\rangle$
$\displaystyle\succsim\langle s_{0},\hat{s}_{1},s_{2},s_{3}\rangle,\
\text{and}$ $\displaystyle\langle s_{0},s_{1},s_{2},\hat{s}_{3}\rangle$
$\displaystyle\succsim\langle s_{0},s_{1},s_{2},s_{3}\rangle,$

however, it does not specify how $\langle
s_{0},\hat{s}_{1},s_{2},\hat{s}_{3}\rangle$ compares to $\langle
s_{0},s_{1},s_{2},s_{3}\rangle$. Under the VNM$\star$ axioms, any preference
is possible for these two trajectories.

As a result of the preferences implied by memorylessness, an agent that
started from state $s_{0}$ and is now in state $s_{2}$, does not need to
consider its past trajectory to make an optimal decision.

With the addition of the memorylessness axiom, the utility function is more
structured, and we can encode the preferences much more succinctly by
specifying only _two numbers per transition_ , instead of one number per
trajectory. These two numbers are the reward and reward multiplier. This fact
is formalized and proven below.

######  Theorem 4.2 (VNM$\star$ utility theorem).

A preference relation over lotteries of finite trajectories of a CMP satisfies
the VNM$\star$ axioms, if and only if there exists rewards
$r:\mathcal{T}\to\mathbb{R}$ and reward multipliers
$m:\mathcal{T}\to\mathbb{R}^{+}$, such that for all transitions $t$ and
follow-up trajectories $\tau$, $\displaystyle u(\epsilon)$
$\displaystyle\stackrel{{\scriptstyle\mathrm{def}}}{{=}}0$ (6) $\displaystyle
u(t\cdot\tau)$
$\displaystyle\stackrel{{\scriptstyle\mathrm{def}}}{{=}}r(t)+m(t)u(\tau),$ (7)
is a linear utility function representing the given preference relation.
Moreover, $r$ is unique up to positive scaling and $m$ is unique, except for
transitions that can only be followed by trajectories that are equivalent to
$\epsilon$. For such transitions, $m$ can be chosen arbitrarily.

###### Proof.

We first assume that the VNM$\star$ axioms hold and show how to construct $r$
and $m$. The VNM axioms tell us that there exists a linear utility function
that is unique up to positive affine transformation. We pick one such utility
function $u$ such that $u(\epsilon)=0$, where $\epsilon$ is the empty
trajectory. This $u$ is unique up to positive scaling.

Let $t=(s,a,s^{\prime})$ be an arbitrary transition and Let $L$ and $M$ be any
two lotteries that start from state $s^{\prime}$. The memorylessness axiom
tells us that preferences over lotteries that start from state $s^{\prime}$
are the same as preferences over lotteries of trajectories that start with
transition $t$.

We may conclude, by the VNM utility theorem, that for all lotteries $L$ that
start from state $s^{\prime}$, $u(t\cdot L)$ must be a positive affine
transformation of $u(L)$. The parameters of this positive affine
transformation give us $r(t)$ and $m(t)$. If $s^{\prime}$ can only be followed
by trajectories that are equivalent to $\epsilon$, then $u(L)=0$ and $m(t)$
can be chosen arbitrarily, otherwise, $m(t)$ is unique because scaling $u$
does not change $m$. Scaling $u$, scales $r$ correspondingly.

We now show that $u$ satisfies the VNM$\star$ axioms. Because $u$ is a linear
utility function, the VNM utility theorem tells us that it satisfies the VNM
axioms. The memorylessness axiom is also satisfied because prepending a
trajectory to a lottery results in a positive affine transformation of its
utility according to repeated application of Equation 7 and this
transformation preserves ordering. ∎

Theorem 4.2 motivates the definition of what we call Affine-Reward MDP (AR-
MDP). An AR-MDP is a CMP combined with a reward function
$r:\mathcal{T}\to\mathbb{R}$ that assigns a scalar to each transition and a
reward multiplier function $m:\mathcal{T}\to\mathbb{R}^{+}$. The _return_ or
utility associated with a trajectory $t\cdot\tau$ is recursively defined as

$\displaystyle u(t\cdot\tau)=r(t)+m(t)u(\tau),$ (8)

where $u(\epsilon)=0$.

When given a CMP and a preference relation $\succsim$, our ultimate goal is to
find an optimal policy, _i.e._ , a policy that achieves maximum expected
utility. The memorylessness axiom, along with the Markov property, guarantee
that there exists an optimal policy that depends only on the current state. We
will refer to such a policy as a memoryless policy. More specifically, a
memoryless policy is a function $\pi:\mathcal{S}\to\mathcal{D}(\mathcal{A})$.
Before formalizing this statement, we will need to briefly discuss how to
compare policies.

We first define the utility of an _infinite_ trajectory $\tau$ to be
$\lim_{T\to\infty}u(\tau_{:T})$, where $\tau_{:T}$ is the trajectory
consisting of the first $T$ transitions of $\tau$. The value of a (general)
policy $\pi$ in state $s$ is then defined as
$v^{\pi}(s)\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\mathbb{E}_{\pi}[u(\boldsymbol{\tau})\;|\;s]$,
where $\boldsymbol{\tau}$ is a random variable denoting the infinite
trajectory taken by an agent starting from state $s$ and following policy
$\pi$. Policy $\pi_{1}$ is preferred to policy $\pi_{2}$ in state $s$ if
$v^{\pi_{1}}(s)>v^{\pi_{2}}(s)$. A complication is that the limit might not
exist and so, we may not be able to compare some policies. To avoid this
problem, we assume in the following proposition that the limit exists.

######  Proposition 4.3.

Given a CMP $\mathcal{W}$ and a VNM$\star$ preference relation over lotteries
of all finite trajectories of $\mathcal{W}$ such that $v^{\pi}(s)$ exists for
all policies $\pi$ and all states $s$, there exists an optimal policy that is
memoryless.

###### Proof.

Let $\pi^{\star}_{s}$ be an optimal policy starting from state $s$. Consider
an agent that has arrived in state $s$ via trajectory $\tau$. The goal of the
agent is to find
$\arg\max_{\pi}\mathbb{E}_{\pi}[u(\tau\cdot\boldsymbol{\tau^{\prime}})\;|\;\tau]$
where $\boldsymbol{\tau^{\prime}}$ is a random variable representing the
future trajectory. Using the VNM$\star$ Theorem one can see that the objective
is equivalent to

$\displaystyle\arg\max_{\pi}\mathbb{E}_{\pi}[u(\tau)+m(\tau)u(\boldsymbol{\tau^{\prime}})\;|\;\tau]$
$\displaystyle=$
$\displaystyle\arg\max_{\pi}\mathbb{E}_{\pi}[u(\boldsymbol{\tau^{\prime}})\;|\;\tau]$
$\displaystyle(m(\tau)>0)$ $\displaystyle=$
$\displaystyle\arg\max_{\pi}\mathbb{E}_{\pi}[u(\boldsymbol{\tau^{\prime}})\;|\;s]$
$\displaystyle(\mathrm{Markov\ property})$ $\displaystyle=$
$\displaystyle\arg\max_{\pi}v^{\pi}(s)$ $\displaystyle=$
$\displaystyle\pi^{\star}_{s},$

where $m(\tau)=\prod_{t\in\tau}m(t)$. Therefore, the optimal action for the
agent is given by $\pi^{\star}_{s}(\epsilon_{s})$. This observation is true
for all states, therefore,
$\pi^{\star}(s)\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\pi^{\star}_{s}(\epsilon_{s})$
is a memoryless policy that is simultaneously optimal for all states. ∎

##  5 An Axiom for Markov Decision Processes

An MDP is a CMP combined with a reward function $r:\mathcal{T}\to\mathbb{R}$
that assigns a scalar to each transition. In an MDP, the utility of a
trajectory $\tau$ is evaluated as $u(\tau)=\sum_{t\in\tau}r(t)$.555This
definition of MDPs slightly differs from the usual definition which does not
include termination probabilities $\mathbb{T}$. We also do not include a
discount factor $\gamma$, but it is easy to simulate one by modifying the
termination probabilities as
$\mathbb{T}_{\mathrm{new}}=1-\gamma(1-\mathbb{T}_{\mathrm{old}})$.

Since the VNM$\star$ axioms incorporate a Markovian property, one might expect
them to correspond to MDPs, but as we saw, this is not the case, and instead,
we arrived at AR-MDPs which are more general than MDPs: If we set $m(t)=1$ for
all transitions $t$, then we arrive at MDPs. An important question, therefore,
arises: _What additional assumptions do MDPs make about preferences?_ The
additional axiom corresponding to an MDP is what we call additivity.

######  Axiom 5.1 (Additivity).

For all states $s$, trajectories $\tau_{1}$ and $\tau_{2}$ that end in state
$s$, lotteries $L$ and $M$ that start from state $s$, lotteries $N$ and $K$,
and $p\in[0,1]$, $\displaystyle p(\tau_{1}\cdot L)+(1-p)N\succsim
p(\tau_{1}\cdot M)+(1-p)K$ $\displaystyle\iff$ $\displaystyle p(\tau_{2}\cdot
L)+(1-p)N\succsim p(\tau_{2}\cdot M)+(1-p)K.$ (9)

This axiom is similar to memorylessness in the sense that it requires that
changing the initial trajectory of two lotteries should maintain preference
relations. The difference with memorylessness is that, here, we are allowed to
change the initial trajectory of equal-probability sub-lotteries, which makes
this axiom _stronger than memorylessness_. To arrive at memorylessness, let
$\tau_{2}=\epsilon_{s}$ and $N=K$, and use independence (2.6) to remove $N$
and $K$ from the comparison.

The additivity axiom is somewhat difficult to interpret. One of the ways to
better understand it is through its implications: if parts of a trajectory are
known and fixed and some parts are unknown and must be optimized, then
additivity says that each part can be optimized independently and the known
parts of the trajectory can be entirely ignored. It might be easy to check if
such an assumption holds for a given task.666Note that this implication is not
a sufficient condition for additivity to hold.

We will use the shorthand, VNM+ axioms, for the VNM axioms along with the
additivity axiom, and similarly for other terms that include VNM.

######  Theorem 5.1 (VNM+ utility theorem).

A preference relation over lotteries of finite trajectories of a CMP satisfies
the VNM+ axioms, if and only if there exists a reward function
$r:\mathcal{T}\to\mathbb{R}$, such that for all transitions $t$ and follow-up
trajectories $\tau$, $\displaystyle u(\epsilon)$
$\displaystyle\stackrel{{\scriptstyle\mathrm{def}}}{{=}}0$ (10) $\displaystyle
u(t\cdot\tau)$
$\displaystyle\stackrel{{\scriptstyle\mathrm{def}}}{{=}}r(t)+u(\tau),$ (11) is
a linear utility function representing the given preference relation.
Moreover, $r$ is unique up to positive scaling.

###### Proof.

We first assume that the VNM+ axioms hold and we show that it is possible to
obtain utilities as in Equation 11. Since the VNM+ axioms imply the VNM$\star$
axioms, the VNM$\star$ utility theorem lets us specify utilities as in
Equation 7 via functions $r$ and $m$. We will show that when the additivity
axiom holds, we can set $m(t)=1$ for all transitions $t$.

For transitions $t$ that can only be followed by trajectories that are
equivalent to $\epsilon$, $m(t)$ can be chosen arbitrarily, so we can set it
to $1$. Let $t=(s,a,s^{\prime})$ be an arbitrary transition among the
remaining transitions. We will show that $m(t)=1$. Let $\tau$ be a trajectory
following $t$ which is not equivalent to $\epsilon$.

$\displaystyle\frac{1}{2}\tau+\frac{1}{2}\epsilon_{s^{\prime}}\approx\frac{1}{2}\epsilon_{s^{\prime}}+\frac{1}{2}\tau$
$\displaystyle\implies$
$\displaystyle\frac{1}{2}(t\cdot\tau)+\frac{1}{2}\epsilon_{s^{\prime}}\approx\frac{1}{2}t+\frac{1}{2}\tau$
(additivity) $\displaystyle\implies$
$\displaystyle\frac{1}{2}(r(t)+m(t)u(\tau))=\frac{1}{2}u(\tau)+\frac{1}{2}r(t)$
$\displaystyle\implies$ $\displaystyle m(t)u(\tau)=u(\tau)$
$\displaystyle\implies$ $\displaystyle m(t)=1$ $\displaystyle(u(\tau)\neq 0)$

We now show that $u$ satisfies the VNM+ axioms. If we let $m(t)=1$ for all
transitions $t$, we see that by the VNM$\star$ utility theorem, $u$ satisfies
the VNM axioms. It remains to show that $u$ satisfies the additivity axiom.
Because utilities are additive (Equation 11), changing an initial trajectory
adds the utility difference of the old and new trajectories to the utility of
the lottery, thus, ordering is preserved. ∎

######  Example 5.2.

Consider the running example of Figure 2 and recall our partial preference
assumptions: $\langle s_{0},\hat{s}_{1},s_{2}\rangle\succsim\langle
s_{0},s_{1},s_{2}\rangle$ and $\langle s_{2},\hat{s}_{3}\rangle\succsim\langle
s_{2},s_{3}\rangle$. With additivity axioms our preference between $\langle
s_{0},\hat{s}_{1},s_{2},\hat{s}_{3}\rangle$ and $\langle
s_{0},s_{1},s_{2},s_{3}\rangle$ is now constrained. In contrast,
memorylessness does not constrain this preference.

To see this, note that one of the implications of Theorem 5.1 is that, for all
trajectories $\tau_{1},\tau_{2},\hat{\tau}_{1}$, and $\hat{\tau}_{2}$, such
that $\tau_{2}$ follows $\tau_{1}$ and $\hat{\tau}_{2}$ follows
$\hat{\tau}_{1}$,

$\hat{\tau}_{1}\succsim\tau_{1}\ \text{and}\
\hat{\tau}_{2}\succsim\tau_{2}\implies\hat{\tau}_{1}\cdot\hat{\tau_{2}}\succsim\tau_{1}\cdot\tau_{2}.$
(12)

Now, our preference assumptions along with Equation 12 imply that $\langle
s_{0},\hat{s}_{1},s_{2},\hat{s}_{3}\rangle\succsim\langle
s_{0},s_{1},s_{2},s_{3}\rangle$.

##  6 Goal-Seeking Sequential Decision Making

In many settings the objective is to reach the best possible state, _i.e._ ,
the means of achieving something do not matter, all that matters is the final
result. Some examples are chess, freestyle swimming, and tennis. Not all
sports fall into this category. In sports such as gymnastics, figure skating,
and diving, _how_ the task is performed (_i.e._ , the entire trajectory)
matters. We will introduce an axiom to account for such settings.

######  Axiom 6.1 (Path-obliviousness).

For all $p\in[0,1]$, states $s$ and $\tilde{s}$, lotteries
$L,M,\tilde{L},\tilde{M},N$ and $K$, such that $L$ and $M$ start from state
$s$, $\tilde{L}$ and $\tilde{M}$ start from state $\tilde{s}$, and the final-
state distribution of $\tilde{L}$ and $\tilde{M}$ is the same as that of $L$
and $M$, respectively, $\displaystyle pL+(1-p)N$ $\displaystyle\succsim
pM+(1-p)K$ $\displaystyle\iff p\tilde{L}+(1-p)N$ $\displaystyle\succsim
p\tilde{M}+(1-p)K.$ (13)

This axiom resembles additivity in the sense that changing the initial
trajectory of equal-probability sub-lotteries preserves ordering. Here,
however, we are allowed to change the starting state and entire trajectories
as long as the final-state distribution stays the same. _Path-obliviousness is
stronger than additivity_. To see this, note that letting
$L=\tau_{1}\cdot\hat{L}$, $\tilde{L}=\tau_{2}\cdot\hat{L}$,
$M=\tau_{1}\cdot\hat{M}$, and $\tilde{M}=\tau_{2}\cdot\hat{M}$ recovers
additivity.

Additionally, path-obliviousness implies that two trajectories that start from
the same state and end in the same state are equivalent. Let $\tau_{1}$ and
$\tau_{2}$ be two such trajectories. Then let $L=\tilde{M}=\tau_{1}$,
$M=\tilde{L}=\tau_{2}$, and $N=K$, and use independence to remove $N$ and $K$
to obtain $\tau_{1}\succsim\tau_{2}\iff\tau_{2}\succsim\tau_{1}$, which
implies $\tau_{1}\approx\tau_{2}$.

We will use the shorthand, VNM${\dagger}$ axioms, for the VNM axioms along
with the path-obliviousness axiom, and similarly for other terms that include
VNM.

######  Example 6.1.

Consider the running example of Figure 2. The inclusion of the path-
obliviousness axiom will constrain the preferences even further, _e.g._ ,
$\langle s_{0},\hat{s}_{1},s_{2}\rangle\approx\langle
s_{0},s_{1},s_{2}\rangle$ and $\langle
s_{0},\hat{s}_{1},s_{2},s_{3}\rangle\approx\langle
s_{0},s_{1},s_{2},s_{3}\rangle$. As a result, assuming that the CMP does not
terminate after one step, the action of the agent in state $s_{0}$ does not
matter because the agent will eventually end up in $s_{2}$ and all
trajectories that go from $s_{0}$ to $s_{2}$ have the same utilities and
utilities are additive.

For the theorem that we are about to introduce, we will make the simplifying
assumption that there exists a state $s_{0}$ from which all of the states of
the CMP are reachable.

######  Theorem 6.2 (VNM${\dagger}$ utility theorem).

A preference relations over lotteries of finite trajectories of a CMP
$\mathcal{W}$, in which all states are reachable from some state $s_{0}$,
satisfies the VNM${\dagger}$ axioms, if and only if there exists a function
$\phi:\mathcal{S}\to\mathbb{R}$ such that for all states $s$ and $s^{\prime}$,
and trajectories $\tau$ starting from state $s$ and ending in state
$s^{\prime}$, $\displaystyle u(\epsilon)$
$\displaystyle\stackrel{{\scriptstyle\mathrm{def}}}{{=}}0$ (14) $\displaystyle
u(\tau)$
$\displaystyle\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\phi(s^{\prime})-\phi(s),$
(15) is a linear utility function representing the given preference relation.
Moreover, $\phi$, called the _potential_ function, is unique up to positive
affine transformation.

###### Proof.

We first assume that the VNM${\dagger}$ axioms hold. Since path-obliviousness
implies additivity, we may invoke the VNM+ utility theorem to obtain additive
utilities that are unique up to positive scaling. We will now construct the
function $\phi$. We set $\phi(s_{0})$ to an arbitrary value and for any other
state $s$, we pick an arbitrary trajectory $\tau$ that goes from state $s_{0}$
to state $s$ and set $\phi(s)=\phi(s_{0})+u(\tau)$. The choice of trajectory
does not matter because of the path-obliviousness axiom; thus, $\phi(s)$ is
well-defined. In this way, we have constructed the potential function $\phi$.
Because we are free in choosing $\phi(s_{0})$ and the positive scaling of the
utilities, $\phi$ is unique up to positive affine transformation.

Next, we show that utilities can be obtained from this potential function
$\phi$. Let $\tau$ be an arbitrary trajectory starting from state $s$ and
ending in state $s^{\prime}$ and let $\tau_{0}$ be any trajectory that goes
from state $s_{0}$ to state $s$.

$\displaystyle\phi(s)-\phi(s_{0})+u(\tau)$ $\displaystyle=u(\tau_{0})+u(\tau)$
$\displaystyle=u(\tau_{0}\cdot\tau)$
$\displaystyle=\phi(s^{\prime})-\phi(s_{0})$ $\displaystyle\implies
u(\tau)=\phi(s^{\prime})-\phi(s)$

We now assume that utilities can be obtained from a potential function $\phi$.
It is easy to see that utilities are additive in this case. Therefore, the
VNM+ axioms must hold. Also, path-obliviousness holds, since changing the
starting state of a trajectory from state $s$ to state $s^{\prime}$ changes
the utility by $\phi(s^{\prime})-\phi(s)$ which preserves ordering. ∎

##  7 Related Works

Until the mid-twentieth century, utility theory relied on preference
structures that did not explicitly incorporate uncertainty or probability.
Specifying assumptions for characterizing rational behavior under uncertainty
began, in a sense, with the classical paper of Bernoulli (1738) and was later
developed and formalized in large part due to Ramsey (1926), De Finetti
(1937), von Neumann & Morgenstern (1947) and Savage (1954). These works
sparked renewed interest in the role of uncertainty in preference structures.

We have focused on the utility theory developed in (von Neumann & Morgenstern,
1947) as the basis for our work. Their work focuses mainly on a game-
theoretical setting, as opposed to a general sequential decision making
setting, and preferences were applied to entire plays of a game to show that
it is possible to assign utilities such that optimal behavior corresponds to
maximizing expected utility. Such an approach has become standard in game
theory; see, for example (Maschler et al., 2013). In games that have a
sequential nature, it is common to assume that the game eventually terminates
and that the final state determines the outcome of the game. In such cases,
preferences are applied to the terminal states. Expected utility theory would
then, for example, justify the use of an algorithm such as Expectiminimax
(Michie, 1966; Russell & Norvig, 1995)

in a non-deterministic two-player zero-sum game. Such an approach does not
apply to a general sequential decision making setting because, in many
scenarios, the entire trajectory should be evaluated, not only the final
state, and in some scenarios, the interaction might never terminate.

There are many works that have considered extensions of utility theory to the
setting where the set of outcomes has the structure of a product space
(Debreu, 1959; Fishburn, 1970; Keeney & Raiffa, 1976). They show that under
certain conditions, there exists an additive utility function. Note that the
set of trajectories is not a product space because many combinations of
transitions are invalid. That is why we needed stronger axioms than those
introduced in these earlier works.

Also, a condition called stationarity has been proposed, which is somewhat
similar to our memorylessness axiom (Koopmans, 1960). In the product space
setting, one can view the product space as a time series, then stationarity
states that changing the initial segment of two outcomes should not affect
their comparison.

To our knowledge, there is only one work that focuses on extending utility
theory to a general sequential decision making setting, namely (Pitis, 2019).
They add two axioms and one assumption to the VNM axioms to obtain the
equivalent of our VNM$\star$ Theorem, whereas we only add a single axiom. They
also consider the outcome space to be the set of state and policy pairs which
is a large continuous high-dimensional space whereas we use the set of finite
trajectories which is a countable space. In these regards, we believe that our
approach is simpler. We also go beyond Affine-Reward MDPs and provide theorems
for (additive) MDPs and goal-directed agents.

Another relevant attempt at a generalization of MDPs is through Constrained
MDPs, which maximize a certain utility while satisfying constraints on other
utilities (Altman, 1999). See Szepesvári (2020) for implications for the
reward hypothesis.

##  8 Discussion

The reward hypothesis refers to “goals and purposes”, but what exactly does
that mean? If the goal is to achieve some desired behavior, specifically, a
desired deterministic memoryless policy $\pi^{\star}$, then the hypothesis is
true, because we can define the reward function as $r(s,a,s^{\prime})=+1$ if
$a=\pi^{\star}(s)$ and $-1$ otherwise.

In this work, we view rational preferences as a very precise specification of
goals and purposes. Not only do they specify what behavior is optimal and what
behavior is sub-optimal (in a 0-1 fashion), but they also allow us to compare
any two behaviors, _i.e._ , we can say _how good_ a behavior is.

We have shown that, in this interpretation of the reward hypothesis, in the
case of Markovian preferences, expected cumulative reward may not be enough to
encode preferences and that an additional reward multiplier signal is also
required. Only when our preferences satisfy the additivity axiom, in addition
to being VNM-rational, does the additive reward suffice. This result can also
be of importance to practitioners of inverse reinforcement learning as
capturing an agent’s preferences by a reward function may not produce adequate
results unless we are sure that the agent’s preferences adhere to the VNM+
axioms.

We may also think of alternative ways of defining goals and purposes; see, for
example, Abel et al. (2021). These alternatives can usually be converted into
preferences in a non-unique way because they are, essentially, incomplete
preference specifications. If we can convert a set of goals into preference
relations that satisfy the VNM+ axioms, then we can successfully express those
goals via reward functions. Sometimes, a goal might not even be convertible to
a Markovian preference relation. In this case, rewards and reward multipliers
are not enough, and a memoryless policy may not be able to produce optimal
behavior. One solution to consider, in this case, is modifying the state-space
to include more information from the past.

We will now briefly mention some exciting avenues for future work. It would be
interesting to study the possibility of extending these theorems to the
setting of continuous state/action-space or continuous time (see Appendix A
for a proposal).

Another implication of our findings is the potential importance of AR-MDPs.
Identification of important real-world scenarios where the VNM$\star$ axioms
hold but VNM+ may not hold, and the design of efficient learning algorithms
for AR-MDPs merits investigation.

## Acknowledgements

We thank the anonymous reviewers for their valuable comments. This project is
in part supported by the CIFAR AI chairs program and NSERC Discovery Grant.

## References

  * Abel et al. (2021) Abel, D., Dabney, W., Harutyunyan, A., Ho, M. K., Littman, M., Precup, D., and Singh, S.  On the expressivity of markov reward.  _Advances in Neural Information Processing Systems_ , 34, 2021.
  * Altman (1999) Altman, E.  _Constrained Markov decision processes_ , volume 7.  CRC Press, 1999.
  * Bernoulli (1738) Bernoulli, D.  Specimen theoriae novae de mensura sortis.  _Commentarii Academiae Scientarum Imperialis Petropolitanae_ , (5):175–192, 1738.
  * Bernoulli (1954) Bernoulli, D.  Exposition of a new theory on the measurement of risk.  _Econometrica_ , 22:23–36, 1954.
  * De Finetti (1937) De Finetti, B.  La prévision: ses lois logiques, ses sources subjectives.  In _Annales de l’institut Henri Poincaré_ , volume 7, pp. 1–68, 1937.
  * Debreu (1959) Debreu, G.  Topological methods in cardinal utility theory.  Technical report, Cowles Foundation for Research in Economics, Yale University, 1959.
  * Fishburn (1970) Fishburn, P. C.  _Utility theory for decision making_.  Operations Research Society of America. Publications in operations research. Wiley, New York, 1970.
  * Jaquette (1976) Jaquette, S. C.  A utility criterion for markov decision processes.  _Management Science_ , 23(1):43–49, 1976.
  * Keeney & Raiffa (1976) Keeney, R. L. and Raiffa, H.  _Decisions with multiple objectives: preferences and value tradeoffs_.  Wiley series in probability and mathematical statistics. Wiley, New York, 1976.
  * Koopmans (1960) Koopmans, T. C.  Stationary ordinal utility and impatience.  _Econometrica: Journal of the Econometric Society_ , pp. 287–309, 1960.
  * Maschler et al. (2013) Maschler, M., Solan, E., and Zamir, S.  _Game Theory_.  Cambridge University Press, 2013.
  * Meyer (1976) Meyer, R. F.  Preferences over time.  _Decisions with multiple objectives_ , pp. 473–497, 1976.
  * Michie (1966) Michie, D.  Game-playing and game-learning automata.  In _Advances in programming and non-numerical computation_ , pp. 183–200. Elsevier, 1966.
  * Pitis (2019) Pitis, S.  Rethinking the discount factor in reinforcement learning: A decision theoretic approach.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 33, pp. 7949–7956, 2019.
  * Ramsey (1926) Ramsey, F. P.  Truth and probability.  In _The Foundations of Mathematics and other Logical Essays_ , pp. 156–198, 1926.
  * Russell & Norvig (1995) Russell, S. and Norvig, P.  _Artificial Intelligence: A Modern Approach_.  Prentice Hall, 1995.
  * Savage (1954) Savage, L. J.  The foundations of statistics.  _John Wiley and Sons, New York, and Chapman and Hall, London_ , 1954\.
  * Sutton & Barto (2018) Sutton, R. S. and Barto, A. G.  _Reinforcement learning: An introduction_.  MIT press, 2018.
  * Szepesvári (2020) Szepesvári, C.  Constrained mdps and the reward hypothesis.  https://readingsml.blogspot.com/2020/03/constrained-mdps-and-reward-hypothesis.html, 2020\.  Accessed: 2022-01-27.
  * von Neumann & Morgenstern (1947) von Neumann, J. and Morgenstern, O.  _Theory of Games and Economic Behavior_.  Princeton University Press, 2nd edition, 1947.
  * von Neumann & Morgenstern (1953) von Neumann, J. and Morgenstern, O.  _Theory of Games and Economic Behavior_.  Princeton University Press, 3rd edition, 1953.

##  Appendix A Countability of the Set of Outcomes

The VNM utility theorem, in its original form, is only applicable when the set
of outcomes is countable. We explain here why the set of finite trajectories
is countable.

######  Proposition A.1.

The set of finite trajectories of a CMP, whose states and actions are
countable, is countable.

###### Proof.

Because the set of states and actions of the CMP are countable, they are
isomorphic to $\mathbb{Z}_{\geq 1}$. Consequently, there is a one-to-one
mapping of non-empty finite trajectories to non-empty finite sequences of
positive integers. If we consider the _continued fraction representation_ of
real numbers, there is a bijection between $\mathbb{Q}_{\geq 1}$ and non-empty
finite sequences of positive integers. Therefore, the set of finite
trajectories fits inside $\mathbb{Q}_{\geq 1}$, which is a countable set. ∎

To apply the VNM utility theorem to uncountable sets of outcomes, an
additional axiom, known as the sure-thing principle (Savage, 1954, p. 77), is
required.

######  Axiom A.1 (Sure-thing principle).

For all lotteries $L$ with probability measure $p$, lotteries $M$, and sets
$\mathcal{X}$ such that $p(\mathcal{X})=1$,

$\forall x\in\mathcal{X}:x\succsim M\implies L\succsim
M\qquad\mathrm{and}\qquad\forall x\in\mathcal{X}:x\precsim M\implies L\precsim
M.$ (16)

Incorporating this axiom is one way that would allow us to include infinite
trajectories as part of the set of outcomes or consider an uncountable set of
states/actions or continuous time.

##  Appendix B Partially Specified Preferences

Since preference relations are constrained, a subset of them may be enough to
recover all preference relations. We identify one such interesting subset in
this section. In particular, we will assume that only preferences over
lotteries that start from a fixed initial state $s_{0}$ are known. Note that
we are not assuming that the preference relation is incomplete, only that some
of the preferences are not revealed to us.

######  Proposition B.1.

If a preference relation over lotteries of finite trajectories of a CMP
satisfies the VNM+ axioms, knowing only preferences over lotteries that start
from a fixed initial state $s_{0}$ uniquely determines all preferences over
lotteries of trajectories reachable from state $s_{0}$.

###### Proof.

From the known preferences, we can construct a utility function for
trajectories starting from state $s_{0}$. Now, consider an arbitrary
trajectory $\tau$ that starts in state $s$ (which is reachable from $s_{0}$)
and ends in state $s^{\prime}$. Let $\tau^{\prime}$ be a trajectory starting
from state $s_{0}$ and ending in state $s$. Then, because VNM+-utilities are
additive, the utility of trajectory $\tau$ can be obtained as
$u(\tau^{\prime}\cdot\tau)-u(\tau^{\prime})$. These utilities let us compare
all lotteries of trajectories that are reachable from state $s_{0}$, and thus,
all preferences are now determined. ∎

##  Appendix C Alternative Axioms

In this section, we will explore a few alternative axioms.

Instead of the additivity axiom, one may employ memorylessness along with the
following axiom.

######  Axiom C.1.

For all $\tau_{1}$, $\tau_{2}$ that end in state $s$, and all $\tau_{3}$,
$\tau_{4}$ that start from state $s$,

$\frac{1}{2}\tau_{1}\cdot\tau_{3}+\frac{1}{2}\tau_{2}\cdot\tau_{4}\approx\frac{1}{2}\tau_{1}\cdot\tau_{4}+\frac{1}{2}\tau_{2}\cdot\tau_{3}.$

It is easy to see that this axiom can replace additivity in the proof of the
VNM+ theorem. This axiom has been mentioned in Meyer (1976) in the context of
extending utility theory to real-valued time series.

It is possible to replace the path-obliviousness axiom with the additivity
axiom and an axiom that says any two trajectories with the same start and end
states are equivalent.