The paper Optimal Policies Tend to Seek Power tries to justify the claim in the title with a mathematical argument, using a clever formal definition of "power". I like the general approach, but I think that parts of the formalisation do not correspond well to the intuitive understanding of the concepts involved. This wouldn't be an issue if the goal of the paper was to prove a mathematical theorem. Here, however, the goal is to be able to deduce something about the behaviour of future AI systems. Therefore, the interface between "math" and "the world" is much more important. This post attempts to take another route to formalisation, which I think is closer to the intuition, albeit more difficult to work with mathematically.

Intro

The power of a state $s$, written $POWE{R}_{\mu }\left(s\right)$, is defined as (roughly) the average optimal value of that state, over some chosen distribution of rewards $\mu$. The paper quite convincingly argues for it:

Power is the ability to achieve a range of goals. In an MDP, the optimal value function $V_R^{\ast }(s,\gamma )$ captures the agent’s ability to “achieve the goal” $R$. Therefore, average optimal value captures the agent’s ability to achieve a range of goals.

The problem with this approach is that it's very sensitive to the choice of the distribution of rewards $\mu$. In particular, one might take a Dirac delta on a reward giving 1 in any chosen state, and 0 everywhere else, which would trivially assign maximal power to that particular state. To combat this difficulty, authors introduce some technical devices allowing them to say "for most distributions, the power of (one, obviously better, state) is greater than the power of (another, obviously worse, state)".

To me, "$X$ happens for most distributions of rewards" should mean that there is some reasonable, uninformative, broad prior $D$ over distributions of rewards, and that $P_D\left(X\right)>\frac{1}{2}$. The approach chosen in the paper not only doesn't correspond to this intuitive understanding, but seems to me to be (in certain sense) proving the thesis by assuming the conclusion.

More concretely, the approach taken in the paper is as follows. Given a reward $R$ and a permutation $\sigma$ over states of the MDP, one can obtain another reward $\left(\sigma R\right)\left(s\right)=R\left(\sigma \right(s\left)\right)$ by permuting the states' rewards. This also works if we have not one reward $R$, but a distribution over rewards, by pushing it forward by $\sigma$. Therefore, each such permutation $\sigma$ induces an orbit $S_{\sigma }$ in the space of (distributions of) rewards. The authors then say that the power of one state $s_1$ is greater than power of another state $s_2$ for most distributions, if, for each permutation $\sigma$, for the majority of distributions of rewards $\mu$ in the orbit $S_{\sigma }$, we have the inequality $POWE{R}_{\mu }\left(s_1\right)>POWE{R}_{\mu }\left(s_2\right)$.

This is arguably quite far from how anyone would interpret the phrase "for most distributions" in real life. What we care about is the global behaviour in the whole space, not the the local behaviour in orbits. (Moreover, the permutations considered here are arbitrary in a sense of not respecting the structure of the MDP - but that is another issue).

The main problem of making the probabilistic meaning of "most" proposed above work here is that it is mathematically difficult to work in the infinite-dimensional space of distributions over rewards. There are many pathologies, such as the fact that there is no counterpart to the (Lebesgue-) uniform measure (after scouring the internet, I found that authors make this argument in a response to the review of the paper).

I still think it is possible to make progress on this. It should be possible to use something like Dirichlet/Pitman-Yor/Gaussian processes, or even something more geometric such as Wasserstein distance, based on the metric structure of the rewards in an MDP. However, regardless of the concrete distribution, the first step is to prove that the event $POWE{R}_{\mu }\left(s_1\right)\le POWE{R}_{\mu }\left(s_2\right)$ is measurable in the space of distributions of rewards (that is, in $\mu$).

Thus, this post contains:

• the proof of this fact, and
• some (unfruitful) exploration of two simple cases of concrete distributions over distributions of rewards

The main technical device I use is the Giry monad, which gives a characterisation of the canonical $\sigma$-algebra on the space of probability distributions. I include the basic definition below, but those unfamiliar with the topic might enjoy this tutorial - which assumes only basic familiarity with measure theory and category theory.

Technical content

What the original paper did

To refresh the memory, the original paper proceeds as follows. We assign "power" to each state of a MDP (under a fixed distribution $\mu$ over reward functions), to be: $$POWE{R}_{\mu }\left(s\right)=\frac{1-\gamma }{\gamma }\cdot E_{R\sim \mu }\left[V_R^{\ast }\right(s)-R(s\left)\right]$$ For a set $D$ of distributions over rewards, we define the inequality between powers of states $s_1,s_2$ to be: $$POWE{R}_{\mu }\left(s_1\right){\ge }_{most\left(D\right)}POWE{R}_{\mu }\left(s_2\right)$$ if and only if, for all $B_{\mu }=orb(\mu ,{\Sigma }_S)=\{\sigma \cdot \mu :\sigma \in {\Sigma }_S\}$, for the majority of $\nu \in B$ (which is a finite set) we have: $$POWE{R}_{\nu }\left(s_1\right)\ge POWE{R}_{\nu }\left(s_2\right)$$

(The paper considers only rewards of a form $R:S\to R$ and only deterministic policies $\pi \in S\to A$.)

Giry monad

First, we note that if $S$ and $A$ are finite (countable case is the same), then the space of reward functions $S\to R$ (in general, $S\times A\times S\to R$) is equal to $R^n$ for some $n\in N$ - therefore, it is a standard Borel space.

On the category of Borel spaces, we have the Giry monad $G$, which assigns, to each measurable space $X$, the space of the probability measures on $GX$. Therefore, $G$ points out a canonical $\sigma$-algebra on the $\Delta \left(R^n\right)$, which we denote by $\Sigma$.

We wiil describe $\Sigma$. First, we say that for a fixed $U\in {\Sigma }_{R^n}$, the evaluation function is given by: $$\begin{array}{cc}e{v}_U& :\Delta \left(R^n\right)\to R\\ e{v}_U\left(\mu \right)& =\mu \left(U\right)\end{array}$$ Then, $\Sigma$ It is generated by all $e{v}_U$, that is, by sets all sets of the form $e{v}_U^{-1}\left(V\right)$, for any measuable set $V\in {\Sigma }_R$.

Lemma 1: For any measurable function $f:R^n\to R$, we can take the evaluation with respect to this function: $$e{v}_f\left(\mu \right)=\int f\left(x\right)d\mu \left(x\right)$$ and then $\Sigma$ is equivalently generated by all $e{v}_f^{-1}\left(V\right)$.

Measurability of the $POWER$ inequality

Let us fix some states $s_1,s_2$. We can ask whether the set $$A=\{\mu \in D:POWE{R}_D(s_1)\ge POWE{R}_D(s_2\left)\right\}$$ is measurable in $\Sigma$ (since ultimately, we want to say something about it's measure).

Unrolling the definitions gives us $$\begin{array}{cc}POWE{R}_{\mu }\left(s_1\right)& \ge POWE{R}_{\mu }\left(s_2\right)⟺\\ \frac{1-\gamma }{\gamma }{E}_{R\sim \mu }\left[V_R^{\ast }\right(s_1)-R(s_1\left)\right]& \ge \frac{1-\gamma }{\gamma }{E}_{R\sim \mu }\left[V_R^{\ast }\right(s_1)-R(s_1\left)\right]⟺\\ E_{R\sim \mu }\left[\right(V_R^{\ast }\left(s_1\right)-V_R^{\ast }\left(s_2\right))-(R\left(s_1\right)-R\left(s_2\right)\left)\right]& \ge 0\end{array}$$ Let's now denote: $$\begin{array}{cc}f& :R^n\to R\\ f\left(R\right)& =V_R^{\ast }\left(s_1\right)-V_R^{\ast }\left(s_2\right)-\left(R\right(s_1)-R(s_2\left)\right)\\ & \\ F& :\Delta \left(R^n\right)\to R\\ F\left(\mu \right)& =E_{x\sim \mu }\left[f\right(x\left)\right]=\int f\left(x\right)d\mu \left(x\right)\end{array}$$ Rewriting the definition of $A$ gives us: $$A=\{\mu \in \Delta (R^n):E_{x\sim \mu }[f\left(x\right)]\ge 0\}=\{\mu \in \Delta (R^n):F(\mu )\ge 0\}=F^{-1}\left(\right[0,\infty \left)\right)$$ Now, we only have to argue that $f$ is measurable - then, by Lemma 1, we will know that $A$ is measurable. It is a sum of four terms - it is enough to show that $g\left(R\right)=R\left(s_i\right)$ and $h\left(R\right)=V_R^{\ast }\left(s_i\right)$ are measurable.

The first function $g\left(R\right)=R\left(s_1\right)$ is just a projection to the $s_i$-th coordinate, therefore measurable.

The second function $$h\left(R\right)=\underset{\pi \in \Pi }{max}{f}^{\pi ,s_i}\left(\gamma \right)\cdot R$$ is just a maximum over a finite set $\Pi =S\to A$ of linear functionals (on a finite-dimensional space), therefore measurable as well - where $f^{\pi ,s_i}\left(\gamma \right)$ is the visit distribution $$f^{\pi ,s_i}\left(\gamma \right)=E_{\left\{s_t\right\}\sim \pi }\left[\sum _{t=0}^{\infty }{\gamma }^t{e}_{s_t}\right]$$ (doesn't really matter what it is, the important point is that it is independent of $R$).

Probabilities on $D$

Ok, so now we can think about what is the probability mass of $A=A(s_1,s_2)$ under different probability distributions over $\Delta \left(R^n\right)$. To make our lives easier, we'll now switch to $\Delta \left(I^n\right)$, $I=[0,1]$. This doesn't change anything: we can rescale reward function by any factor and get an equivalent MDP (proof: just look at the Bellman equations).

Two (short) attempts I make below are unsuccessful. Both of them fail in a similar ways: by making the uniform distribution over rewards "too central", and by not having the full support over all probability distributions.

Lifting uniform distribution by Giry monad

We have one canonical distribution over distributions: take the uniform distribution $p$: $$1\stackrel{p}{\to }X$$ and apply the Giry monad: $$G\left(1\right)\simeq 1\stackrel{Gp}{\to }GX$$ But unfortunately, $Gp$ is just the uniform distribution over the Dirac deltas in ${\delta }_R\in GX$. Then, the situation is equivalent to calculating the measure of the set $POWE{R}_{\mu }\left(s_1\right)\ge POWE{R}_{\mu }\left(s_2\right)$ in one case of the uniform distribution over rewards (that is, a Diract delta on the uniform distribution of the rewards).

Dirichlet process

We can take Dirichlet process $D:=D\left(U\right[0,1{]}^n,\alpha )$ centered around the uniform distribution, for a fixed $\alpha$.

Definition: For a given distribution $H$ on $X$ and $\alpha \in (0,\infty )$, the Dirichlet process $D(H,\alpha )$ on the space $\Delta \left(X\right)$ is characterized by the following property: for any partition $A_1,A_2,\dots A_n$ of $X$, we have that if $\mu \sim D(H,\alpha )$, then: $$\left(\mu \right(A_1),\mu (A_2),\dots \mu (A_n\left)\right)\sim Dir\left(\alpha H\right(A_1),\alpha H(A_2),\dots \alpha H(A_n\left)\right)$$

Applying the definition to our $D\left(U\right[0,1{]}^n,\alpha )$ and the partition $\{A,A^c\}$, we get $$\left(\mu \right(A),\mu (A^c\left)\right)=\left(\mu \right(A),1-\mu (A\left)\right)\sim Dir\left(\alpha \lambda \right(A),\alpha (1-\lambda \left(A\right)\left)\right)=Beta\left(\alpha \lambda \right(A),\alpha (1-\lambda \left(A\right)\left)\right)$$

where $\lambda \left(A\right)$ the measure of $A$ under uniform distribution $U[0,1{]}^n$.

Therefore, we have the mean: $$E_{\mu \sim D}\left[\mu \right(A\left)\right]=\lambda \left(A\right)$$

Unfortunately, this is again quite uninteresting. All the choice was in centering the Dirichlet process at $H=U[0,1{]}^n$. (Another drawback is that Dirichlet process has support only on discrete distributions, which is at odds with our initial goal of having a broad prior over all distributions of rewards - in particular, continuous ones).

Conclusion

We proved that the event $POWE{R}_{\mu }\left(s_1\right)\ge POWE{R}_{\mu }\left(s_2\right)$ is measurable in the space of distibutions $\mu \sim D$. We failed to point out any interesting concrete priors over distributions of reward functions, but I am optimistic that it should be possible with better understanding of the metric (topological, linear, differential, ...?) structure of the reward functions on an MDP.