This post seeks to clarify the question of what utility functions should be defined over, in the situation where an agent has uncertainty over their own utility function.

---

Outcomes or worlds

The most intuitively natural thing to define utility functions over is outcomes or worlds. The problem with this approach is that it results in an excessive amount of utility functions.

For instance, imagine the agent has two actions $a_1$ and $a_2$. The action $a_1$ will map straight to world $w_1$, while $a_2$ will map to a complicated probability distribution over a large set of worlds $W_2$. The agent gets no further action.

If we see the set of worlds as $W=\left\{w_1\right\}\cup W_2$, then we have a vast amount of possible utility functions. Whereas in practice only two parts of the utility function matters: its value on $w_1$, and its expected value on $W_2$.

An agent that knows those values (technically, that knows the ordering of those values) for a single utility function, can reach a decision. Therefore it would seem perverse to have things change when the agent starts to have uncertainty over its utility.

What would make sense is to have utilities defined over expected outcomes -- ie over $\left\{w_1\right\}$ and $W_2$ -- but that definition doesn't seem to work in more general situations.

Histories

Model the agent as interacting $n$ times with the world. It gets an observation, then follows that by an action until it takes its last action $a_n$. Call the set of $n$ alternating observations and actions a history, and let $H$ be the set of histories. We can also define partial histories, sequences $h=o_1{a}_1{o}_2{a}_2\dots o_m$ of length $m<n$.

Note this inverts the usual order, by starting with observations and following with actions. This is because the history ends with an action: since the agent can't affect anything more after than, subsequent observations are meaningless. Partial histories, though, end with observations, not actions (this is for subsequent ease of use).

Any utility function $u$ can be seen as function from $H$ to $R$, by mapping the history $h_n\in H$ to $u\left(h_n\right)$, the expected utility of the history.

So a more natural class would be to define utilities as being over $H$, the set of possible histories. Note that actions are included in histories, and histories with the same observations but different actions can have different utility values. This is because, eg, the observation of someone saying 'You succeed in your task!' will have different implications depending on the action just prior.

So define $U$ as the set of utility functions (not equivalence classes of utility functions) over $H$.

This is better that defining $U$ over outcomes, but still somewhat unsatisfactory, as we can have a large number of incredibly unlikely histories, and these should not affect the normalisation procedure much.

So what is really wanted is a distribution over $H$. But that makes no sense, as we don't know what the actions will be. So we need to look at how the agent choose its actions: at its set of strategies.

Strategies

The set of deterministic strategies $S$ is the set of ways an agent can pick its actions, given its past history. It would be tempting to define utilities as taking values over $S$, but there a subtleties to deal with first.

Isomorphic strategies

Suppose the agent can choose action $a_1$ or $b_1$ at the first step, then $a_2$ or $b_2$ at the second step. The observations are $o_1$ and $o_2$, independently of actions chosen.

Then consider the following strategies:

• $s\left(o_1\right)=a_1$, $s\left(o_1{a}_1{o}_2\right)=a_2$, $s\left(o_1{a}_2{o}_2\right)=a_2$.
• $s^{\prime }\left(o_1\right)=a_1$, $s^{\prime }\left(o_1{a}_1{o}_2\right)=a_2$, $s^{\prime }\left(o_1{a}_2{o}_2\right)=b_2$.

These strategies seem to differ: they give different behaviours on the partial history $h=o_1{a}_2{o}_2$. However, because both will choose $a_1$ after $o_1$, the history $h$ will never come up. Thus we will define $S$ as consisting of equivalent classes of strategies that will always choose the same action in any situation that actually arises.

Stochastic strategies

We should briefly note that we can form stochastic strategies by setting a probability distribution over $S$ (this defines a simplex with 'pure' elements of $S$ as the vertexes). This set includes all possible stochastic strategies.

Utilities and strategies

This section presents a ways of connecting strategies and utilities. Starting with embedding utilities over histories into utilities over strategies:

Theorem 1: There is a linear map $k$ from $U$ to $R^S$. This $k$ need not be either injective nor surjective.

Proof: The set $R^S$ is naturally identified with the set of functions $S\to R$.

Each element of $s\in S$ defines a probability distribution on $H$, and hence an expectation for any utility function $u$. Write this expectation as $u\left(s\right)$. Then the values of $u\left(s\right)$ for different $s$ defines the element $k\left(u\right)\in R^S$.

The linearity of $k$ comes from the fact that utility functions are additive: $(u+v)\left(s\right)=u\left(s\right)+v\left(s\right)$.

To show that $k$ need not be injective, consider the following situation, where the initial observation is $o$ or $o^{\prime }$ with equal probability, leading to a choice of actions $\{a,b\}$ and $\left\{a^{\prime }\right\}$:

Then there are two strategies -- the ones that pick $a$ and $b$ -- but three worlds -- those ending in $a$, $b$, and $a^{\prime }$ -- so $k$ maps a three dimensional space into a two dimensional one, and cannot be injective.

There are utilities in $U$ that are independent of any strategy; the kernel of $k$ is the subspace of these that happen to always map to utility $0$.

To show that $k$ need not be surjective, add actions $c$ and $b^{\prime }$ after $o$ and $o^{\prime }$ above:

Then the set of strategies has six elements (each strategy choose one element from among $3$ elements, then another from among $2$ elements), while the set of histories has five elements, corresponding to each of the five final actions. Hence $k$ cannot be surjective from the five dimensional $U$ to the six dimensional $R^S$. $\square$

Given this $k$, we can consider the true space of utility functions that we're interested in: the image of $k$, divided out by equivalence relations (translations and positive scalings). Thus the space of relevant utility classes is:

• $U=k\left(U\right)/\sim$.

Note that can translate any element of $R^S$ to have all its coordinates sum to zero, and then divide by positive scalings. This means that $U=S\cup \left\{0\right\}$ where $S$ is a sphere and $\left\{0\right\}$ corresponds to the utilities constant on all strategies. The topology of $U$ is the natural topology on $S$, combined with the fact that the only open set containing $\left\{0\right\}$ is $U$ itself.

Stable permutations

We want to be able to interchange strategies, and still get the same result: have some sort of symmetry on the normalisation process. However, since $k\left(U\right)$ can be a strict subset of $R^S$, we can't just take arbitrary permutations of $S$. This section will instead define the subset of stable permutations. Note that any permutation of $S$ extends to an invertable linear transformation of $R^S$ by permutation of the basis elements.

Definition: Stable permutations. A stable permutation is a permutation of $S$ that extends to a linear map on $R^S$ that preserves $k\left(U\right)\subset R^S$.

Since $U=k\left(U\right)/\sim$, we can call the set of stable permutations $S_U$.

How common are stable permutations? In general, not too uncommon and not too common, as the following two theorems will show:

Proposition 2: If $S$ is non-trivial, then so is $S_U$.

Proof: Consider the set of actions and possible observations as a tree. If $S$ contains more than one element, then there is a branching point where the agent can choose between more than one action. Since the length of the branches is $n$ and hence finite, there exists at least one branching point with no subsequent branching point: the agent has no further decisions to make.

Let $h$ be the partial history that corresponds to that final branching point, and let $a$ and $b$ be possible actions at $h$. Then a transposition of $a$ and $b$ will also permute any strategies $S$ for which $h$ is a possible history.

But because $h$ is a finale branching point, the expected utilities $u\left(ha\right)$ and $u\left(hb\right)$ are defined for any $u\in U$, independently of any strategy. Thus transposing $a$ and $b$ defines a map $\sigma$ on $U$, with $\sigma \left(u\right)\left(ha\right)=u\left(hb\right)$, $\sigma \left(u\right)\left(hb\right)=u\left(ha\right)$, and $u\left(h^{\prime }\right)$ otherwise unchanged for any history $h$ that doesn't start with $ha$ or $hb$.

Hence the permutation of $S$ corresponds to a linear automorphism of $U$, which preserves the image of $U$ under $k$, which means that that permutation is in $S_U$.$\square$

In general, any tree isomorphism will correspond to an element of $S_U$, and one can delete -- or add -- nodes with a single action before doing such an isomorphism. However, in the general case, the space of stable permutations is not that large:

Proposition 3: The set $S_U$ can be a strict subset of the set of permutations of $S$. And $S_U$ need not be transitive and may even have fixed points: there may exist an $s\in S$ which is mapped to itself for all $\rho \in S_U$.

Proof: consider the situation below, where there are no choices after $o_{1}b$:

Let $s$ be the strategy that chooses $b$ at $o_1$, and let $u$ be the utility function that maps $o_{1}b$ to $1$ and everything else to $0$. Then assume that $\rho$ exchanges $s$ with any $s^{\prime }$. This means that $\rho \left(k\right(u\left)\right)$ is a function in $R^S$ that takes value $1$ on a single policy $s^{\prime }$ that choose $a$ after $o_1$ (as all policies but $s$ do that), and $0$ everywhere else.

Without loss of generality, let $s^{\prime }$ choose $a$ and $a^{\prime }$ after $o_2$ and $o_2^{\prime }$, respectively. Then changing $a$ to $b$ must reduce the expectation of $s^{\prime }$ by $1$, and similarly changing $a^{\prime }$ to $b^{\prime }$. Thus changing $a$ to $b$ and changing $a^{\prime }$ to $b^{\prime }$ simultaneously must, by linearity, set the expected utility of that policy to $-1$. Consequently, $\rho \left(k\right(u\left)\right)$ cannot be an element of $k\left(U\right)$, and hence $\rho \notin S_U$.

Thus every element of $S_U$ must map $s$ to itself.$\square$

Extra results and concepts

This section presents some miscellaneous extra results and concepts within this formalism.

Utilities and strategies

Each $s\in S$ generates $H_s\subset H$ which is the set of histories which have non-zero probability given $s$.

Lemma 4: If $s\ne s^{\prime }$, then $H_s\ne H_{s^{\prime }}$.

Proof: since $s\ne s^{\prime }$, there must be some partial history $h$, of non-zero probability given $s$ or $s^{\prime }$, where $s$ will choose action $a$ while $s^{\prime }$ will choose action $a^{\prime }$ (in the extreme case, $h$ may be $\varnothing$). Thus $s$ must have at least one possible history starting with $ha$ while $s^{\prime }$ can have none (and vice versa for $h{a}^{\prime }$). $\square$

Proposition 5: Each $s$ has some $\left[u\right]\in U$ of which it is the unique maximising strategy for.

Proof: Define $u_s\in U$ as mapping $H_s$ to $1$ and the rest of $H$ to $0$. Thus the expectation $u_s\left(s\right)=1$, and $u_s\left(s^{\prime }\right)<1$ for $s\ne s^{\prime }$, since $s^{\prime }$ has a non-zero probability of reaching a history outside $H_s$, hence a history where $u_s$ has expected utility $0$. The argument extends to mixed strategies, and the relevant utility class is $\left[k\right(u_s\left)\right]$.$\square$

Partial histories

For any partial history $h$ (or $ha$, if we want it to end with an action), define $H_h$ ($H_{ha}$) as the set of histories that start with $h$ (or $ha$).

Let $S_h$ be the set of strategies on $H_h$, and $S\left(h\right)\subset S$ the set of strategies that allow the history $h$. Then there is a natural projection $q_h:S\left(h\right)\to S_h$ by mapping each strategy to its equivalence class of strategies on $H_h$. The same holds for $ha$.

Let $S_{-ha}$ be a set of partial strategies, defined as strategies defined on $H-H_{ha}$ that allow $ha$ to happen with non-zero probability. Then $S\left(ha\right)=S_{-ha}\times S_h$.

Let $U_{ha}$ be the set of utility functions on $H_{ha}$, and $k_{ha}$ the projection $U_{ha}\to S_{ha}$ from Theorem 1. We can define $U_{ha}$ as $k\left(U_{ha}\right)/\sim$, similarly to above.

Let $O_{ha}$ be the set of possible observations the agent can make just after $ha$. Then there is a decomposition $S_{ha}={\times }_{o\in O_{ha}}{S}_{hao}$.

Proposition 6: There is a natural map $r_{ha}$ from $U$ to $U_{ha}$.

Proof: for $u\in U$, $s\in S_{ha}$ and $s^{\prime }\in S_{-ha}$, define $r_{ha}\left(u\right)\left(s\right)$ as $u(s\times s^{\prime })$.

Now replace $s^{\prime }$ with $s^{\prime \prime }$, also in $S_{-ha}$, and compare, using standard conditional probability and conditional expected utility:

• $u(s\times s^{\prime })=P(ha|s\times s^{\prime })u(s\times s^{\prime }|ha)+(1-P(ha|s\times s^{\prime }\left)\right)u(s\times s^{\prime }|\neg ha))$.
• $u(s\times s^{\prime \prime })=P(ha|s\times s^{\prime \prime })u(s\times s^{\prime \prime }|ha)+(1-P(ha|s\times s^{\prime \prime }\left)\right)u(s\times s^{\prime \prime }|\neg ha))$.

Note that the probability of $ha$ is independent of $s$ (since $s\in S_{ha}$), and, since $s^{\prime }$ and $s^{\prime \prime }$ are deterministic, $P\left(ha|s^{\prime }\right)=P\left(ha|s^{\prime \prime }\right)$. Similarly $u(s\times s^{\prime }|ha)$ and $u(s\times s^{\prime }|\neg ha)$ are independent of $s^{\prime }$ and and $s$, respectively -- and the same goes for the $s^{\prime \prime }$ expression.

Putting this all together gives:

• $u(s\times s^{\prime })-u(s\times s^{\prime \prime })=P\left(ha|s^{\prime }\right)\left(u\right(s|ha)-u(s|ha\left)\right)+(1-P(ha|s^{\prime }\left)\right)\left(u\right(s^{\prime }|\neg ha)-u(s^{\prime }|\neg ha\left)\right)=C_{s^{\prime },s^{\prime \prime }}$,

where $C_{s^{\prime },s^{\prime \prime }}$ is a constant depending only on $s^{\prime }$ and $s^{\prime \prime }$.

Consequently, the map $r_{ha}$ defined above changes by a constant when $s^{\prime }$ changes. Similarly, if we change $u$ by changing its definition on $H-H_{ha}$ only, then $r_{ha}$ also changes by a constant, as $u\left(s^{\prime }|\neg ha\right)$ changes.

Thus, up to constants, $r_{ha}$ is a well defined map from $U$ to $k_{ha}\left(U_{ha}\right)$. Since it only uses the expectation of $u$ on $S$, this makes it a well defined map from $k\left(U\right)$ to $k_{ha}\left(U_{ha}\right)$.

Then if we divide by translations (and scalings), the constant factors drop out, so $r_{ha}$ is a well defined map from $U$ to $U_{ha}$.$\square$