Categorical-measure-theoretic approach to optimal policies tending to seek power

[jacek]

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.

[Algon]

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.

I want to know what spark of intuition led to your optimism. The technical details didn’t feel like they contributed to conveying this intuition of yours. It would help if you gave some examples of using the metric structure of the some functions in a space to pin down some sort of probability distribution.

[jacek]

Hm, so one comment is that the proof in the post was not meant to convey the intuition for the existence of the concrete probability distribution—the measurability of the POWER inequality is a necessary first step, but not really technically related to the (potential) rest of the proof (although I had initially hoped that lifting some distribution on rewards by the Giry monad might produce something interesting).

As for why the additional structure might be helpful: the issue with there being no Lebesgue-like uniform measure is that in the infinite-dimensional space like $[0,1{]}^N$, one cannot assign any positive measure to any subset. For example, in $[0,1]$, each of the halves have to have equal measures, because the measure has to be shift-invariant. In $[0,1{]}^2$, we can do this with each of the four squares like $[0,1/2]\times [0,1/2]$. Repeating this process, in the limit, there is no measure we can assign to those intervals, because they can be divide into countably-many non-negligible sets (c.f. https://​​en.wikipedia.org/​​wiki/​​Infinite-dimensional_Lebesgue_measure).

So the problem is that first, the space is too big, and second, there is too much freedom of cutting the space into pieces and shifting them. The EPIC metric paper I linked to in the post (or some related research) might be helpful in solving both of these issues.

First, we can make the space smaller by dividing it by some equivalence relation—reward shaping properties in MDPs provide such relation (although EPIC considers the relation from the original paper by Ng et al which is too weak—something stronger is needed). To give a concrete (although a bit silly) example: there is no uniform measure on the space of real-valued functions on $[0,1]$. But suppose we have a (very strong) equivalence relation $f\sim g$ iff $f\left(0\right)=g\left(0\right)$. Then, the space collapses to just $R$, which has a normal $\lambda$ measure.

The second problem is that we had too much freedom in shifting the subsets (or, the shift-invariance was too strong). In our case, “shifting” is applied to the sets of probability distributions of rewards. But individual rewards cannot always be shifted, since this operation doesn’t preserve optimal policies. So maybe this puts some restrictions on the transformations we can apply to the space, and the measures don’t blow up.

So, briefly, I don’t understand those behaviours very well yet, but my intuitive optimism comes from:

• first, the fact that of rewards seems to be rich, so if the space of distributions of rewards inherits some of the properties, the induced symmetries would limit the allowed transformations

• second, there is another approach I which forgot to write about in the post, which is to consider non-shift-invariant uninformative priors—for example, Jeffrey prior on $[0,1]$ is not the uniform distribution. It seems that the problem we are dealing with here is quite common in math, and people have invented workarounds (like the abstract Wiener spaces mentioned in the wikipedia article) - the issue is checking whether any of those workaround applies here

[Algon]

Thank you for writing this, I feel like it makes the core idea you’re expressing at much clearer.

My intuition is that abstract Wiener spaces won’t get you the sort of measure you’re looking for alone, based off my experience with measures over big spaces in physics. But, that said, I feel like there should be some such measure over large physical spaces, as presumably power has a definition in terms of physical concepts, or else how the heck can we recover our intuition of power in our world? It should all add up to normality, after all. It seems to me that looking over those physics papers which descibed single particles as agentic because our distributions over them tend towards max entropy, which we can view as the particle seeking the greatest “option value” it can, would be a good place to build up the latter intuition.

I think I am undecided as to whether you can use the rich structre of reward functions to limit the allowed transormations in a useful way. Partly because I suspect that this rich structure reflects a physical structure (something like the natural abstractions thesis + selection pressure from reality for the sorts of rewards we typically see) or perhaps a simplicity prior of some sort. But maybe it will work out. I don’t know.

My lack of optimism as to the possibility of your agenda is basically why I was willing to accept the strange probability distribution TurnTrout went with, I guess. But on reflection, perhaps I should have used that as an existence proof of distribution over reward which allows something like our intuitive picture of power seeking. And tried to see if I could interpret it to be something less weird, use it to find something less weird, or just go look for less weird things because maybe they’d work.

Sorry for the long post, but I just realized I didn’t update based off Turntrout’s results. It seems more likely to me now that your agenda might work. Though I’d be more optimistic if you were using Turntrout’s distribution as inspiration for what to look for in some way.