Previously: Towards Measures of Optimisation

When thinking about optimisation processes it is seductive to think in information-theoretic terms.

Is there some useful measure^[1] of 'optimisation' we can derive from utility functions or preference orderings, just as Shannon derived 'information' from probability distributions? Could there be a 'mathematical theory of optimisation' that is analogous to Shannon's theory of information? In this post we exhibit negative evidence that this point of view is a fertile direction of inquiry.

In the last post we reviewed proposals in that direction, most notably Yudkowsky's original idea using preference orderings, and suggested some informal desiderata. In this post we state our desiderata formally, and show that they can't all be satisfied at once. We exhibit a new proposal from Scott Garrabrant which relaxes one desideratum, and revisit the previous proposals to see which desiderata they satisfy.

Setup

Recall our setup: we're choosing an action from a set to achieve an outcome in a set $Ω$ . For simplicity, we assume that $Ω$ is finite. Denote the set of probability distributions on $Ω$ by $Δ Ω .$ We have a default distribution $p \in Δ Ω$ , which describes the state of affairs before we optimise, or in a counterfactual world where we don't optimise, and action distributions $p_{a} \in Δ Ω$ for each $a \in A$ , which describe the state of affairs if we do. Our preferences are described by a utility function $u : Ω \to R$ . Let $U$ denote the set of utility functions.

In the previous post we considered random variables $O P (p, u) (x),$ which measure the optimisation entailed by achieving some outcome $x$ , given a utility function $u$ and base distribution $p$ . We then took an expectation over $p_{a}$ to measure the optimisation entailed by achieving some distribution over outcomes, i.e. we defined $O P (p, p_{a}, u) = E_{p_{a}} O P (p, u) (x)$ .

In this post we state our desiderata directly over $O P (p, p_{a}, u)$ instead. For more on this point see the discussion of the convex-linearity desideratum below.

Desiderata

Here are the desiderata we originally came up with for $O P : Δ Ω \times Δ Ω \times U \to R \cup {- \infty, \infty}$ . They should hold for all $p, p_{a}, p_{b} \in Δ Ω$ and for all $u \in U$ . Explanations below.

(Continuity)
$O P$ is continuous^[2] in all its arguments.
(Invariance under positive scaling).
$O P (p, p_{a}, α u) = O P (p, p_{a}, u)$ for all $α \in R_{> 0} .$
(Invariance under translation).
$O P (p, p_{a}, u) = O P (p, p_{a}, u + β)$ for all $β \in R .$
(Zero for unchanged expected utility).
$O P (p, p_{a}, u) = 0$ whenever $E_{p} (u) = E_{p_{a}} (u)$ .
(Strict monotonicity).
$O P (p, p_{a}, u) > O P (p, p_{b}, u)$ whenever $E_{p_{a}} (u) > E_{p_{b}} (u)$ .
(Convex-linearity).
$O P (p, λ p_{a} + (1 - λ) p_{b}, u) = λ O P (p, p_{a}, u) + (1 - λ) O P (p, p_{b}, u)$ for all $λ \in [0, 1] .$
(Interesting and not weird).
See below.

Continuity just seems reasonable.

We want invariance under positive scaling and invariance under translation because a von Neumann-Morgernstern utility function is only defined up to an equivalence class $[u] = [α u + β]$ for $α \in R_{> 0}$ and $β \in R$ (we denote this equivalence relation by $\sim$ in the remainder of the post). One of our motivations for this whole endeavour is to be able to talk about how much a utility function is being optimised without having to choose a specific $α$ and $β$ .

The combination of zero for unchanged expected utility and strict mononicity means that $O P (p, p_{a}, u)$ follows the sign of $E_{p_{a}} (u) - E_{p} (u) .$ Increases in expected utility count as positive optimisation, decreases count as negative optimisation, and when expected utility is unchanged no optimisation has taken place.

Convex-linearity holds if and only if $O P (p, p_{a}, u)$ can be rewritten as the expectation under $p_{a}$ of an underyling measure of the optimisation of outcomes $x$ rather than distributions $p_{a} .$ This is intuitively desirable since we're pursuing an analogy with information theory, where $O P (p, p_{a}, u)$ corresponds to the entropy of a random variable, and $O P (p, u) (x)$ corresponds to the information content of its outcomes. This is the desideratum that Scott's proposal violates in order to satisfy the rest.

Interesting and not weird is an informal catch-all desideratum.

Not weird is inspired by the problem we ran across in the previous post when trying to redefine Yudkowsky's proposed optimisation measure for utility functions instead of preference orderings: you could make $O P$ arbitrarily low by adding some $x$ to $Ω$ with zero probability under both $p$ and $p_{a}$ and large negative utility. This kind of brittleness counts against a proposed $O P$ .

Interesting is the most important desideratum and the hardest to formalise. $O P$ should be a derivative of utility functions that might plausibly lead us to new insights that are much harder to access by thinking about utility functions directly. If we compare to derivatives of probability, it should be more like information than like odds ratios. $O P$ definitely shouldn't just recapitulate expected utility.

Impossibility

It turns out our first 6 desiderata sort of just recapitulate expected utility.

In particular, they're equivalent to saying that $O P (p, p_{a}, u)$ just picks out some representative $v$ of each equivalence class of utility functions and reports its expectation under $p_{a}$ . The zero point of the representative must be set so that $E_{p} (v) = 0$ (and so we'll get different representatives for different $p$ ), but other than that, any representative defined continuously in terms of $p$ and $u$ will do.

Proposition 1: Desiderata 1-6 are satisfied if and only if $O P (p, p_{a}, u) = E_{p_{a}} rep (p, [u]),$ for some continuous function $rep : Δ Ω \times U / \sim\to U$ with $rep (p, [u]) \sim u$ and $E_{p} rep (p, [u]) = 0$ for all $p \in Δ Ω$ and $u \in U$ .

Proof: See Appendix.

For example, we can translate $u$ by $- E_{p} (u)$ and rescale by the utility difference between any two points, i.e. set $rep (p, [u]) = \frac{u (x) - E_{p} (u)}{u (x_{1}) - u (x_{2})}$ for some fixed $x_{1}, x_{2} \in Ω$ ^[3]. The translation gets us the right zero point, and the scaling ensures the function is well defined, i.e. it sends all equivalent $u$ to the same representative.

$O P (p, p_{a}, u) = E_{p_{a}} (\frac{u (x) - E_{p} (u)}{u (x_{1}) - u (x_{2})}) = \frac{E_{p_{a}} (u) - E_{p} (u)}{u (x_{1}) - u (x_{2})}$ satisfies desiderata 1-6. But it's not very interesting! It's just the expectation of a utility function.

Not all possibilities for $rep (p, [u])$ are of this simple form, and as stated it remains possible that a well-chosen $rep (p, [u])$ , with a scaling factor that depends more subtly on $p$ and $u$ , could lead to an interesting and well-behaved optimisation measure. But proposition 1 contrains the search space, and can be seen as moderately strong evidence that any optimisation measure satisfying desiderata 1-6 must violate desideratum 7.

If we take this perspective, perhaps we should think of dropping one of the desiderata. Which one should it be?

New Proposal: Garrabrant

Convex-linearity, according to the following idea, suggested by Scott Garrabrant.

Intuitively, we start with some notion of 'disturbance' - a goal-neutral measure of how much an action affects the world. Then we say that the amount of optimisation that has taken place is the least amount of disturbance necessary to achieve a result at least this good.

We'll use the KL-divergence as our notion of disturbance, but there are other options. Let $⪰_{u}$ order probability distributions by their expected utility, so $p^{'} ⪰ p_{a}$ if and only if $E_{p^{'}} u (x) \geq E_{p_{a}} u (x) .$ Then we define $O P_{S G}^{+} (p, p_{a}, u) = {min}_{p^{'} ⪰ p_{a}} D_{K L} (p ∣∣ p^{'}) .$

So if it didn't require much disturbance to transform the default distribution $p$ into $p_{a}$ , we won't get much credit for our optimisation. If it required lots of disturbance then we might get more credit - but only if there wasn't some $p^{'}$ much closer to $p$ which would've been just as good. In that case most of our disturbance was wasted motion.

Notice that Scott's idea only measures positive optimisation: if $E_{p_{a}} (u) < E_{p} (u)$ then we just get $O P_{S G}^{+} (p, p_{a}, u) = 0.$

To get something which does well on our desiderata, we need to combine it with some simliar way of measuring negative optimisation. One idea is to say that when expected utility goes down as a result of our action, the amount of de-optimisation that has taken place is the least amount of disturbance needed to get back to somewhere as good as you started^[4]. Using the KL-divergence as our notion of disturbance we get $O P_{S G}^{-} (p, p_{a}, u) = {min}_{p^{'} ⪰ p} D_{K L} (p_{a} ∣∣ p^{'}) .$

Then we can say $O P_{S G} = O P_{S G}^{+} - O P_{S G}^{-} = {min}_{p^{'} ⪰ p_{a}} D_{K L} (p ∣∣ p^{'}) - {min}_{p^{'} ⪰ p} D_{K L} (p_{a} ∣∣ p^{'}) .$

Note that one or both of the two terms will always be zero, depending on whether expected utility goes up or down.

Proposition 2: $O P_{S G}$ satisfies continuity, invariance under positive scaling, invariance under translation, zero for unchanged expected utility, and strict monotonicity; and does not satisfy convex-linearity.

Proof: See Appendix.

$O P_{S G}$ seems interesting, and not obviously weird, so whether or not you like it might come down the importance you assign to convex-linearity. Remember that in the information theory analogy, the lack of linearity makes $O P_{S G}$ like a notion of entropy without a notion of information. If you didn't like that analogy anyway, this is probably fine.

Previous Proposals

Let's quickly run through how some previously proposed definitions of $O P$ score according to our desiderata. We won't give much explanation of these proposals - see our previous post for that.

Yudkowsky

In our current setup and notation we can write Yudkowsky's original proposal^[5]as $O P_{E Y} (p, p_{a}, u) = - E_{x \sim p_{a}} (log \sum_{u (y) \geq u (x)} p (y))$ .

Since this proposal is about preference orderings rather than utility functions, it violates a few of our utility function-centric desiderata.

Proposition 3: $O P_{E Y}$ satisfies invariance under positive scaling, invariance under translation, and convex-linearity; it does not satisfy continuity, zero for unchanged expected utility, or strict monotonicity.

Proof: See Appendix.

$O P_{E Y}$ was interesting enough to kick off this whole investigation. How weird it is is open to interpretation.

Yudtility

In the previous post we tried to augment Yudkowsky's proposal to a version sensitive to the size of utility differences betweeen different outcomes, rather than just their order. We can write our idea as $O P_{U Y} (p, p_{a}, u) = - E_{x \sim p_{a}} (log \frac{\sum_{u (y) \geq u (x)} p (y) (u (y) - u (x_{w}))}{\sum p (y) (u (y) - u (x_{w}))})$ where $x_{w} = {argmin}_{x \in Ω} u (x) .$

Proposition 4: $O P_{U Y}$ satisfies invariance under positive scaling, invariance under translation, and convex-linearity; it does not satisfy continuity, zero for unchanged expected utility, or strict monotonicity.

Proof: See Appendix.

$O P_{U Y}$ also intuitively fails not weird, since as we noted in the previous post, it can be made arbitrarily small by making $u (x_{w})$ sufficiently low - the existence of a very bad outcome can kill your optimisation power, even if it has zero probability under either the default or achieved distribution.

Altair

In a post from 2012, Alex Altair identifies some desiderata for a measure of optimisation. His setup is slightly different to ours: instead of comparing two distinct distributions $p$ and $p_{a}$ , he imagines one distribution $p_{t}$ varying continously over time, and aims to define instantaneuous $O P$ in terms of the rate of change of $E_{p_{t}} (u) .$ He gives the following desiderata:

The sign of $O P$ should be the sign of $\frac{d}{d t} E_{p_{t}} (u) .$
Constant positive $O P$ should imply exponentially increasing $E_{p_{t}} (u) .$

The analogue of 1 in our setup is the requirement that the sign of $O P$ should be the sign of $E_{p_{a}} (u) - E_{p} (u)$ . As we mentioned, this is a consequence of zero for unchanged expected utility and strict mononicity. But importantly, strict monotonicity also rules out the degenerate solution of setting OP to $1$ if $E_{p_{a}} (u) - E_{p} (u)$ is positive and $- 1$ if it's negative.

2 seems like the sort of condition should fall out of desiderata along the lines of 'OP should be additive across a sequence of independent optimisation events'. We haven't thought much about the sequential case, but we think it's the most interesting direction to consider in the future.

Altair tentatively suggests defining $O P$ as $\frac{\frac{d}{d t} E_{p_{t}} (u) .}{∣ E_{p_{t}} (u) ∣} .$ An analogue in our setup would be $O P_{A A} (p, p_{a}, u) = \frac{E_{p_{a}} (u) - E_{p} (u)}{∣ E_{p} (u) ∣}$ .

Proposition 5: $O P_{A A}$ satifies continuity, invariance under positive scaling, zero for unchanged expected utility, strict monotonicity, and convex-linearity. It does not satisfy invariance under translation.

Proof: See Appendix.

But $O P_{A A}$ is not very interesting - it's similar to the $O P$ we got out of Proposition 5.

Future Directions

Comments suggesting new desiderata or proposals, rejecting existing ones, or pointing out mistakes are encouraged. We don't plan to work on this any more for now, so anyone who wants to to take up the baton is welcome to.

That said, there are a few reasons why the basic premise of this project, which is something like, "Let's look for a true name for optimisation defined in terms of utility functions, inspired by information theory," might be misguided:

Utility functions might already be the true name - after all, they do directly measure optimisation, while probability doesn't directly measure information.
The true name might have nothing to do with utility functions - Alex Altair has made the case that it should be defined in terms of preference orderings instead.
Following the information theory analogy might put form over substance - perhaps quests for the true name of a quantity need to be guided by clear cut use cases instead, so you get the meaningful feedback loops necessary to iterate to something interesting.

If you're not put off by these concerns, and want something concrete and mathematical to work on, then we think there's some low hanging fruit in formulating desiderata over a sequence of optimisation events, instead of just one. One of Shannon's desiderata for a measure of information was that the information content of two independent events should be the sum of the information content of the individual events. It seems natural to say something similar for optimisation, but we haven't thought much about how to formulate it.^[6]^[7]

Appendix: Proofs

Proposition 1

Proposition 1: Desiderata 1-6 are satisfied if and only if $O P (p, p_{a}, u) = E_{p_{a}} rep (p, [u]),$ for some continuous function $rep : Δ Ω \times U / \sim\to U$ with $rep (p, [u]) \sim u$ and $E_{p} rep (p, [u]) = 0$ for all $p \in Δ Ω$ and $u \in U$ .

Proof: Forwards direction:

By convex-linearity $O P (p, p_{a}, u) = E_{p_{a}} f (p, x, u)$ for some $f : Δ Ω \times Ω \times U$ . By the two invariance conditions we have that $E_{p_{a}} f (p, x, u_{1}) = E_{p_{a}} f (p, x, u_{2})$ for any $p_{a}, p \in Δ Ω and u_{1}, u_{2} \in U$ with $u_{1} \sim u_{2}$ . A consequence of this is that $f (p, x, u_{1}) = f (p, x, u_{2})$ for any $x \in Ω$ , $p \in Δ Ω$ and $u_{1}, u_{2} \in U$ with $u_{1} \sim u_{2}$ (to see this for a given $x$ , just set $p_{a} = δ_{x}$ , where $δ_{x}$ is the distribution which is $1$ at $x$ and $0$ elsewhere). That means we can well-define a function $g : Δ Ω \times Ω \times U / \sim\to R$ by $g (p, x, [u]) = f (p, x, u)$ . Since $U$ is the set of functions from $Ω$ to $R$ , we can reformulate $g$ as a function (whose name is not yet justified) $rep : Δ Ω \times U / \sim\to U$ , where $rep (p, [u])$ is defined by $rep (p, [u]) (x) = g (p, x, [u]) = f (p, x, u)$ . Then we get that $O P (p, p_{a}, u) = E_{p_{a}} rep (p, [u])$ , as in the statement of the proposition.

To show that $rep$ is continuous, note that by the continuity of $O P$ we have that ${lim}_{(p, [u]) \to (p^{*}, [u^{*}])} O P (p, δ_{x^{*}}, u) = {lim}_{(p, [u]) \to (p^{*}, [u^{*}])} rep (p, [u]) (x^{*})$ for any sequence $(p, [u]) \to (p^{*}, [u^{*}])$ . Since ${lim}_{(p, [u]) \to (p^{*}, [u^{*}])} O P (p, δ_{x^{*}}), u) = {lim}_{(p, [u]) \to (p^{*}, [u^{*}])} rep (p, [u]) (x^{*})$ and $O P (p^{*}, δ_{x^{*}}, u^{*}) = rep (p^{*}, [u^{*}]) (x^{*})$ , the continuity of $rep$ follows.

To see that $rep (p, [u]) \sim u,$ note that by strict monotonicity $rep (p, [u]) and u$ induce the same ordering of probability distributions by expected utility, so by the von Neumann-Morgernstern utility theorem there exists a positive affine transformation between them. That $E_{p} rep (p, [u]) = 0$ follows directly from zero for unchanged expected utility.

Backwards direction:

Continuity follows from continuity of $rep$ . Invariance follows from the fact that $rep$ is defined on $U / \sim$ rather than $U$ . That $rep (p, [u]) \sim u$ gives us that if $E_{p_{a}} (u) < E_{p_{b}} (u)$ then $E_{p_{a}} rep (p, [u]) < E_{p_{b}} rep (p, [u])$ , i.e. strict monotonicity, and also that if $E_{p_{a}} (u) = E_{p} (u)$ then $E_{p_{a}} rep (p, [u]) = E_{p} rep (p, [u])$ , which since the latter is zero by assumption gives zero for unchanged expected utility. Linearity follows from linearity of expectation.

Proposition 2

$O P_{S G}$ satisfies continuity, invariance under positive scaling, invariance under translation, zero for unchanged expected utility, and strict monotonicity; and does not satisfy convex-linearity.

Proof: We have continuity since $O P_{S G}$ is the composition of continuous functions. Since we only use the ordering a utility function induces over distributions we get invariance for free. When $E_{p_{a}} (u) = E_{p} (u)$ both KL-divergences can be minimised to zero by $p^{'} = p$ , so we get zero for unchanged expected utility.

For strict monotonicity we can assume that $E_{p_{a}} (u) > E_{p_{b}} (u) \geq E_{p} (u)$ and show that $O P (p, p_{a}, u) > O P (p, p_{b}, u)$ (the case where both are $E_{p} (u) \geq E_{p_{a}} (u) > E_{p_{b}} (u)$ is similar, and the case where exactly one is $E_{p_{a}} (u) > E_{p} (u) > E_{p_{b}} (u)$ is easy). In particular we need to show that ${min}_{p^{'} ⪰ p_{a}} D_{K L} (p ∣∣ p^{'}) > {min}_{p^{'} ⪰ p_{b}} D_{K L} (p ∣∣ p^{'})$ , which we can do by taking some $q_{a} \in arg {min}_{p^{'} ⪰ p_{a}} D_{K L} (p ∣∣ p^{'})$ and constructing from it some $q_{b}$ with $D_{K L} (p ∣∣ q_{b}) < D_{K L} (p ∣∣ q_{a})$ and $q_{b} ≻ p_{b}$ . Take any $y, z \in Ω$ with $q_{a} (y) > p (y)$ and $q_{a} (z) > p (z)$ , and set $q_{b} (y) = q_{a} (y) - ε$ and $q_{b} (y) = q_{a} (y) + ε$ , with $q_{b} (x) = q_{a} (x)$ for all $x \in Ω ∖ {y, z}$ . For small $ε > 0$ , we get decreased KL-divergence without taking the expected utility below that of $p_{b} .$

To see that $O P_{S G}$ violates convex-linearity, consider the case where $Ω = {x_{1}, x_{2}}$ with $u (x_{1}) > u (x_{2})$ , and $E_{p} (u) < E_{p_{a}} (u)$ . In this case $O P_{S G} (p, p_{a}, u) = {min}_{p^{'} ⪰ p_{a}} D_{K L} (p ∣∣ p^{'}) = D_{K L} (p ∣∣ p_{a})$ . Since KL-divergence is not linear its easy to find a counterexample.

Proposition 3

$O P_{E Y}$ satisfies invariance under positive scaling, invariance under translation, and convex-linearity; it does not satisfy continuity, zero for unchanged expected utility, or strict monotonicity.

Proof: We get invariance by since $O P_{E Y}$ only uses the ordering over outcomes implied by a utility function, and convex-linearity since $O P_{E Y}$ is an expectation.

$O P_{E Y}$ is not continuous in $u$ : look at $O P (p, δ_{x}, u) = - log \sum_{u (y) \geq u (x)} p (y)$ for some $x$ , and consider what happens when we take some $z$ with $p (z) > 0$ and and $u (z) < u (x)$ , and increase $u (z)$ all the way to $u (x) .$ Zero for unchanged expected utility fails since $O P_{E Y}$ is only zero when $p_{a} = δ_{x_{w}}$ .

For a counterexample to strict monotonicity, let $Ω = {x_{1}, x_{2}, x_{3}}$ , $p (x_{1}) = p (x_{2}) = p (x_{3}) = \frac{1}{3}$ (which we will notate as $p = [\frac{1}{3} \frac{1}{3} \frac{1}{3}]$ ), $p_{a} = [010]$ , $p_{b} = [\frac{1}{2} 0 \frac{1}{2}]$ , and $u = [034] .$ Then $p_{a}$ wins on expected utility but loses on $O P_{E Y} .$

Proposition 4

$O P_{U Y}$ satisfies invariance under positive scaling, invariance under translation, and convex-linearity; it does not satisfy continuity, zero for unchanged expected utility, or strict monotonicity.

Proof: We get invariance by construction, and convex-linearity since $O P_{E Y}$ is an expectation.

Continuity fails for the same reason as before. We can reuse the same counterexample as before for strict monotonicity. For a counterexample to zero for unchanged expected utility let $Ω = {x_{1}, x_{2}, x_{3}}$ , $u = [048]$ , $p = [\frac{1}{2} \frac{1}{4} \frac{1}{4}]$ and $p_{a} = [\frac{3}{8} \frac{1}{2} \frac{1}{8}] .$

Proposition 5: $O P_{A A}$ satifies continuity, invariance under positive scaling, zero for unchanged expected utility, strict monotonicity, and convex-linearity. It does not satisfy invariance under translation.

Proof: Left as an exercise to the reader!

^{^}
By measure we mean a standard unit used to express the size, amount, or degree of something, not a probability measure. Alexander voted for yardstick to avoid confusion; Matt vetoed.
^{^}
Since we assume $Ω$ is finite, there is only one reasonable topology on $Δ Ω$ and $U$ , namely the Euclidean topology.
^{^}
When $u (x_{1}) = u (x_{2})$ we have to interpret $O P$ as negative infinity, zero, or positive infinity, depending on the sign of the numerator.
^{^}
Here we distinguish de-optimisation, by which we mean something like accidental or collateral damage, from disoptimisation - deliberate pessimisation of a utility function. If we are instead interested in interpreting expected utility decreases as disoptimisation, it would be natural to define $O P_{S G}^{-} = {min}_{p^{'} ⪯ p} D_{K L} (p ∣∣ p^{'})$ i.e. the amount of disoptimisation that has taken place is the least amount of disturbance needed to do even worse.
^{^}
Yudkowsky defined $O P$ as a function of default distribution, outcome, and preference ordering; we've made it a function of default distribution, achieved distribution, and utility function by taking an expectation under the achieved distribution and using the induced preference ordering of the utility function.
^{^}
Related ideas are to consider a sequence of distributions $p_{1}, p_{2}, p_{3}$ and require something like $O P (p_{1}, p_{3}, u) = O P (p_{1}, p_{2}, u) + O P (p_{2}, p_{3}, u)$ , or to get into more exotic operadic compositionality-style axioms like the one in Theorem 5.3 here.
^{^}
Another avenue is to replace convex-linearity with convexity, in which case $O P (p, p_{a}, u)$ might arrive as an infra-expectation of $O P (p, x, u)$ if not an expectation.

17

Optimisation Measures: Desiderata, Impossibility, Proposals

17