We would like a mathematical theory which characterises the intuitive notion of ‘optimisation’.

Before Shannon introduced his mathematical theory of communication, the concept of ‘information’ was vague and informal. Then Shannon devised several standardised measures of it, with useful properties and clear operational interpretations. It turned out the concept of information is universal, in that it can be quantified on a consistent scale (bits) across various contexts.

Could something similar be true for ‘optimisation’?

In this post we review a few proposed ways to measure optimisation power and play around with them a bit.

Our general setup will be that we’re choosing actions from a set $A$ to achieve an outcome in a set $\Omega$. We have some beliefs about how our actions will affect outcomes in the form of a probability distribution $p_a\in \Delta \Omega$ for each $a\in A$. We also have some preferences, either in the form of a preference ordering over outcomes, or a utility function over outcomes. We will also assume there is some default distribution $p\in \Delta \Omega$, which we can interpret either as our beliefs about $\Omega$ if we don’t act, or if we take some default action^[1].

Yudkowsky

Yudkowsky’s proposed definition just makes use of a preference ordering $⪰$ over $\Omega$. To measure the optimisation power of some outcome $x$, we count up all the outcomes which are at least as good as $x$, and divide that number by the total number of possible outcomes. It’s nice to take a negative log to turn this fraction into a number of bits: $$OP\left(x\right)=-\log \frac{|\{x^{\prime }\in \Omega \mid x^{\prime }⪰x\}|}{|\Omega |}.$$ If I achieve the second best outcome out of eight, that's $-\log \frac{2}{8}=2$ bits of optimisation power.

If the outcome space is infinite, then we can't count the number of outcomes at least as good as the one we got, so we need a measure to integrate over. If we make use of our default probability distribution here, the resulting quantity has a nice interpretation. $\frac{{\int }_{x^{\prime }⪰x}p\left(x^{\prime }\right)d{x}^{\prime }}{\int p\left(x^{\prime }\right)d{x}^{\prime }}$ is just ${\int }_{x^{\prime }⪰x}p\left(x^{\prime }\right)d{x}^{\prime }$: the default probability of doing as well as we did. Since we're always assuming we've got a default distribution, we might as well define OP like this even in the finite-domain case. Again we’ll take a log to get $$OP\left(x\right)=-\log {\int }_{x^{\prime }⪰x}p\left(x^{\prime }\right)d{x}^{\prime }.$$ Now 2 bits of optimisation power means the default probability of doing this well was $\frac{1}{4}$.

So far we’ve just been thinking about the optimisation power of achieving a specific outcome. We can define the optimisation power of an action as the expected optimisation power under the distribution it induces over outcomes: $$OP\left(a\right)=\int p_a\left(x\right)OP\left(x\right)dx.$$ The above definitions just make use of a preference ordering. If we do have a utility function $u:\Omega \to R$ then we’d like our definitions to make use of that too. Intuitively, achieving the second best outcome out of three should constitute more optimisation power in a case where it’s almost as good as the first and much better than the third, compared to a case where it’s only slightly better than the third and much less good than the first^[2].

Analogously to how we previously asked ‘what fraction of the default probability mass is on outcomes at least as good as this one?’ we could try to ask ‘what fraction of the default expected utility comes from outcomes at least as good as this one?’.

But making use of utility functions in the above definition is tricky. Recall that utility functions originate from the Von Neumann-Morgenstern theorem, which says that if an agent choosing between probabilistic mixtures of options satisfies some weak rationality criteria then it acts as if it maximises expected utility according to a utility function $u:\Omega \to R$. The utility function produced by the VNM-theorem is only defined up to positive affine transformations, meaning that the utility function $u^{\prime }=au+b$, for any $a\in R_{>0}$ and $b\in R$, equally well represents the tradeoffs between outcomes the agent is willing to take. Another way of looking at this is that only ratios of differences in utility are real. Therefore any definition of OP which changes when you multiply your utilities by a positive scalar or add a constant is very questionable. Alex Altair ran into this problem when trying to define OP in terms of the rate of change of utility.

One way we considered to get around this is to measure the utility of every outcome relative to the worst one. Let $x_w={\mathrm{argmin}}_{x\in \Omega }u\left(x\right)$ and define $$OP\left(x\right)=-\log \frac{{\int }_{x^{\prime }⪰x}p\left(x^{\prime }\right)\left(u\right(x^{\prime })-u(x_w\left)\right)d{x}^{\prime }}{\int p\left(x^{\prime }\right)\left(u\right(x^{\prime })-u(x_w\left)\right)d{x}^{\prime }}.$$

In words, this asks 'what fraction of the default extra expected utility on top of the minimum comes from outcomes at least this good?'.

This is invariant to translating and rescaling utility. Unfortunately it has a problem of its own - it’s sensitive to our choice of $x_w$. By adding some made up element to $\Omega$ with large negative utility and zero probability of occurring, we can make OP arbitrarily low. In that case basically all of the default relative expected utility comes from avoiding the worst outcome, which is guaranteed, so you don’t get any credit for optimising.

Wentworth

An alternative approach to measuring optimisation in bits comes from John’s Utility Maximisation = Description Length Minimisation. In the language of our setup, John shows that you can take any utility function $u:\Omega \to R$^[3], and map it to a probability distribution $q_u\in \Delta \Omega$, such that maximising expected utility with respect to $u$ is equivalent to minimising cross-entropy with respect to $q_u$.

At first we weren’t sure of the precise sense of equivalence John meant, but one way to state it is that the interval scale over actions $a\in A$ which you obtain by considering $E_{p_a}u\left(x\right)$ is precisely the same as the interval scale you get by considering $-H(p_a,q_u)$. This will become very explicit with a bit of rejigging.

John defines $q_u$ by taking a softmax: $q_u\left(x\right)=\frac{e^{u\left(x\right)}}{{\sum }_{x^{\prime }}{e}^{u\left(x^{\prime }\right)}}$. But we’ll keep working in base 2 and write $q_u\left(x\right)=\frac{2^{u\left(x\right)}}{{\sum }_{x^{\prime }}{2}^{u\left(x^{\prime }\right)}}$ instead^[4].

So we get that $$\begin{array}{cc}-H(p_a,q_u)& =--E_{p_a}\log q_u\left(x\right)\\ & =E_{p_a}\log \frac{2^{u\left(x\right)}}{{\sum }_{x^{\prime }}{2}^{u\left(x^{\prime }\right)}}\\ & =E_{p_a}\log 2^{u\left(x\right)}-E_{p_a}\log \sum _{x^{\prime }}{2}^{u\left(x^{\prime }\right)}\\ & =E_{p_a}u\left(x\right)-\log \sum _{x^{\prime }}{2}^{u\left(x^{\prime }\right)}\end{array}$$

The term on the right doesn't depend on $p_a$ or $x$, so what this means is that $$-H(p_a,q_u)=E_{p_a}u\left(x\right)+C_u$$ for some constant $C_u$. In other words, this switch from maximising expected utility to minimising cross-entropy is just like translating your utility function by a constant and carrying on as you were.

Since utility functions are only defined up to translation anyway, this means the sense of equivalence is as strong as can be, but it does dispel the impression that this is a useful way to measure optimisation power in bits. The number of extra 'bits' of optimisation power that some action $a_1$ has compared to $a_2$ is precisely the number of extra expected utilons - and that means that scaling your utility function scales your optimisation power by the same amount.

Takeaways

We would like a measure of the amount of optimisation taking place which makes use of utility functions, which is invariant under postive affine transformations of those utility functions, and which isn't too sensitive to strange things like the utility of the worst outcome. The search continues.