Infrafunctions and Robust Optimization
This will be a fairly important post. Not one of those obscure result-packed posts, but something a bit more fundamental that I hope to refer back to many times in the future. It’s at least worth your time to read this first section up to its last paragraph.
There are quite a few places where randomization would help in designing an agent. Maybe we want to find an interpolation between an agent picking the best result, and an agent mimicking the distribution over what a human would do. Maybe we want the agent to do some random exploration in an environment. Maybe we want an agent to randomize amongst promising plans instead of committing fully to the plan it thinks is the best.
However, all of these run into the standard objection that any behavior like this, where a randomized action is the best thing to do, is unstable as the agent gets smarter and has the ability to rewrite itself. If an agent is randomizing to sometimes take actions that aren’ t optimal according to its utility function, then there will be an incentive for the agent to self-modify to eliminate its randomization into those suboptimal actions.
The formalization of this is the following proposition.
Proposition 1: Given some compact metric space of options , if is a bounded function,
Intuitively, what this is saying is that the only possible way for a mixture of options to be an optimal move is if each component option is an optimal move. So, utility functions can only give you randomization behavior if the randomization is between optimal actions. The set of such will typically only contain a single point. And so, in general, for any utility function at all, an agent using it will experience a convergent pressure towards deterministic decision-making.
Every single clever alignment trick involving an agent behaving randomly or sampling from a distribution is thereby guaranteed to fail, as it’s not stable under reflection as the agent gets smarter, for anything worthy of being called an agent (in the sense that it has an implicit utility function and acts to achieve it).
The rest of this post will be about how the above sentence is false. There’s a mathematically principled, reflectively stable, way an agent can be, where randomization behavior persists. No matter how smart it gets, it won’t want to remove its randomization behavior. Reflectively stable quantilizers are back on the menu, as are reflectively stable human-imitators, reflectively stable Thompson samplers, and more.
What’s an Infrafunction?
Intuitively, just as infradistributions are a generalization of probability distributions, infrafunctions are a generalization of functions/random variables in the same direction. The next paragraph will be informal (and somewhat wrong) to not clog it with caveats.
The Fundamental Theorem of Inframeasures says that there are two ways of viewing inframeasures. The first way is to view an inframeasure as a closed convex set of measures, where the worst-case measure is picked. You don’t know what distribution in the set will be picked by reality, and so you model it as an adversarial process and plan for the worst-case. As for the second way to view an inframeasure, the thing you do with probability distributions is to take expectations of functions with them. For instance, the probability of an event is just the expected value of the function that’s 1 if the event happens, and 0 otherwise. So an inframeasure may also be viewed as a functional that takes a function as an input, and outputs the expectation value, and which must fulfill some weak additional properties like concavity. Measures fulfill the much stronger property of inducing a linear function .
Moving away from that, it’s important to note that the vector space of continuous functions , and the vector space of (finite signed) measures on (denoted ), are dual to each other. A function and a measure are combined to get an expectation value. (ie, taking the expectation) is the special function of type . Every continuous linear function corresponds to taking expectations with respect to some finite signed measure, and every continuous linear function corresponds to taking expectations with respect to some continuous function .
Since the situation is so symmetric, what happens if we just take all the mathematical machinery of the Fundamental Theorem of Inframeasures, but swap measures and functions around? Well… compare the next paragraph against the earlier paragraph about the Fundamental Theorem of Inframeasures.
The Fundamental Theorem of Infrafunctions says that there are two ways of viewing infrafunctions. The first way is to view an infrafunction as a closed convex set of functions , where the worst-case function is picked. You don’t know what function in the set will be picked by reality, and so you model it as an adversarial process and plan for the worst-case. As for the second way to view an infrafunction, a thing you do with functions to is you combine them with a probability distribution to get an expectation value. So an infrafunction may also be viewed as a function that takes a probability distribution as an input, and outputs the expectation value, and which must fulfill some weak additional properties like concavity. Functions fulfill the much stronger property of inducing a linear function .
For the following theorem, a set of functions is called upper-complete if, whenever and , as well. And a function will be called minimal in if and implies that .
Theorem 1: Fundamental Theorem of Infrafunctions If is a compact metric space, there is a bijection between concave upper-semicontinuous functions of type , and closed convex upper-complete sets of continuous functions .
Conjecture 1: Continuity=Compactness If is a compact metric space, there is a bijection between concave continuous functions of type , and closed convex upper-complete sets of continuous functions where the subset of minimal functions has compact closure.
Ok, so, infrafunctions can alternately be viewed as concave (hill-like) functions , or closed convex upwards-complete sets of continuous functions.
Effectively, this is saying that any concave scoring function on the space of probability distributions (like the negative KL-divergence) can equivalently be viewed as a worst-case process that adversarially selects functions. For any way of scoring distributions over “what to do” where randomization ends up being the highest-scoring option, the scoring function on is probably going to curve down (be concave), and so it’ll implicitly be optimizing for the worst-case score amongst a set of functions .
Now, going from a desired randomization behavior, to a concave scoring function with that desired behavior as the optimum, to the set of functions the scoring function is implicitly worst-casing over, takes nontrivial mathematical effort. There’s a whole bunch of possible randomization behaviors for which I don’t know what sort of worst-case beliefs induce that sort of randomization.
For instance, what sort of uncertainty around a utility function makes an agent softmax over it? I don’t know. Although, to be fair, I haven’t tried particularly hard.
Generalization of Quantilization
However, one example that can be worked out (and has already been worked out by Jessica Taylor and Vanessa Kosoy) is quantilization.
If you haven’t seen quantilization before, it’s where you take a reference distribution over actions, , and instead of picking the best action to optimize the function , you condition on the event “the action I picked is in the top 1 percent of actions sampled from , in terms of how much likes it” and sample from that distribution.
I mean, it doesn’t have to be 1 percent specifically, but this general process of “take a reference distribution, plot out how good it is w.r.t. some function , condition on the score being beyond some threshold, and sample from that updated distribution” is referred to as quantilization.
Well, if that’s the sort of optimization behavior we’re looking for, we might ask “what sort of concave scoring function on probability distributions has quantilization as the optimum?”, or “what sort of utility function uncertainty produces that scoring function?”
As it turns out, quantilization w.r.t. a reference distribution , where your utility function is , corresponds to worst-casing amongst the following set of functions for some . The epistemic state that leads to quantilization is therefore one where you think that your utility function is unfixably corrupted, but that its deviation from the true utility function is low relative to a given reference distribution . Specifically, if is your utility function you see, and is the true utility function which is a corruption of, you believe that and have no other beliefs about the true utility function .
You’d be very wary about going off-distribution because you’d think “the corruption can be arbitrarily bad off-distribution because all I believe is that is low, so in a region where is low-probability, it’s possible that is super-low there”. You’d also be very wary about deterministically picking a single spot where is high, because maybe the corruption is concentrated on those sparse few spots where is the highest.
However, if you randomize uniformly amongst the top quantile of where is high, this is actually the optimal response to this sort of utility function corruption. No matter how the corruption is set up (as long as it’s small relative to ), the quantilizing policy is unlikely to do poorly w.r.t (the agent’s irreducibly uncertain beliefs about) the true utility function.
These are some rather big claims. Exactly as stated above, they’ve already been proven a long time ago by people who aren’t me. However, there’s a further-reaching generalization that the above results are a special case of, which allows interpolating between quantilization and maximization, which is novel.
Introduction to Lp Spaces (skippable)
If you already know what spaces are, you can skip straight to the general theorem, but if you don’t, time to take a detour and explain them.
Given some nice space and probability distribution , we can make the vector space of “measurable functions which are equivalent w.r.t. ”. After all, you can add functions together, and multiply by constants, so it makes a vector space. However, the elements of this vector space aren’t quite functions, they’re equivalence classes of functions that are equivalent w.r.t. . Ie, if and are two different functions, but has zero probability of selecting a point where , then and will be the same point in the vector space we’re constructing.
This vector space can be equipped with a norm. Actually, it can be equipped with a lot of norms. One for each real number in . The norm on the space of “functions that are equivalent w.r.t. ” is: For the norm, it’d be Compare this to euclidean distance! So, our set-of-functions which induces quantilization behavior, Can also be expressed as “an -sized ball around w.r.t. the norm and ”, and this is the core of how to generalize further, for we may ask, what’s so special about the norm? What about the norm for all the ? What do those do?
Theorem 2: Ball Theorem
For any , , , and , the infrafunction corresponding to (Knightian uncertainty over the ball of size centered at , w.r.t ), is where . Further, given a function , the optimal to pick is the distribution , for some constants and .
Some special cases of this are as follows. For , you get quantilization. Worst-casing over little balls means that your task is to pick the probability distribution which maximizes , and this maximizing probability distribution is rescaled by the function that’s 1 when exceeds the threshold value and 0 otherwise (as this is the limit of as ) This can be restated as conditioning on the event that exceeds a certain threshold, and so we get quantilizers.
For , you get a more aggressive sort of optimization. Worst-casing over little balls means that your task is to pick the probability distribution which maximizes , and this maximizing probability distribution is but rescaled linearly with how much exceeds the threshold value . So, for example, given two points and , if , the probability density at is enhanced by a factor of 3 over what it’d be at .
For , you basically just get argmax over the support of the distribution . Worst-casing over little balls means that your task is to pick the probability distribution which maximizes , and this maximizing probability distribution is but rescaled according to for arbitrarily large . Ie, incredibly large at the highest value of , which dominates the other values. So pretty much, a dirac-delta distribution at the best point in the support of .
There’s a massive amount of work to be done on how various sorts of randomization behavior from agents relate to various sorts of concave scoring rules for distributions, and how those relate with various sorts of (restricted) worst-case assumptions about how the utility function got corrupted.
But what’s this about agents with infrafunctions as their utility functions being stable under reflection? Well, we’d want an agent to be incentivized to keep its utility function the same (or at least not change it in unpredictable ways) no matter what it sees. Making this more precise, if an agent has a utility (infra)function , then it should believe that optimizing for the infrafunction ( but modified in a predictable way to account for having seen history ) after seeing history , will produce equal or better results (according to ) than optimizing for any competitor (infra)function after seeing . This is a necessary condition to give the starting agent no incentive to alter the utility function of its future self in an unpredictable way (ie, alter it in a way that differs from ).
For example, if an agent with an infrafunction ever ends up thinking “If I was an optimizer for the utility function (not infrafunction!) , I’d do better, hang on, lemme just rewrite myself to optimize that instead”, that would be instability under reflection. That just should not ever happen. Infrafunctions shouldn’t collapse into utility functions.
And, as it turns out, if you’ve got an agent operating an an environment with a utility infrafunction, there is a way to update the infrafunction over time which makes this happen. The agent won’t want to change its infrafunction in any way other than by updating it. However, the update shares an undesirable property with the dynamically consistent way of updating infradistributions, though. Specifically, the way to update a utility infrafunction (after you’ve seen a history) depends on what the agent’s policy would do in other branches.
If you’re wondering why the heck we need to update our utility infrafunction over time, and why updating would require knowing what happens in alternate timelines, here’s why. The agent is optimizing worst-case expected value of the functions within its set-of-functions. Thus, the agent will tend to focus its marginal efforts on optimizing for the utility functions in its set which have the lowest expected value, in ways that don’t destroy too much value for the utility functions which are already doing well in expectation. And so, for a given function (the set induced by the infrafunction ), it matters very much whether the agent is doing quite well according to in alternate branches (it’s doing well in expectation so it’s safe to mostly ignore it in this branch), or whether the agent is scoring horribly according to in the alternate branches (which means that it needs to be optimized in this branch).
Time to introduce the notation to express how the update works. If is a finite history, and is a stochastic partial policy that tells the agent what to do in all situations except where the history has as a prefix, and is a stochastic partial policy that tells the agent what to do in all situations where the history has as a prefix, then is the overall policy made by gluing together those two partial policies.
Also, if is an environment, and is a stochastic policy, refers to the distribution over infinite histories produced by the policy interacting with the environment. By abuse of notation, can be interpreted as a probability distribution on This is because, obeying , everything either works just fine and keeps telling you what your next action is and you build some infinite history , or the partial history happens and stops telling you what to do.
The notation is the indicator function that’s 1 when the full history lacks as a prefix, and 0 on the partial history . is the function , but with a restricted domain so it’s only defined on infinite bitstrings with as a prefix.
With those notations out of the way, given an infrafunction (and using for the utility functions in the corresponding set ), we can finally say how to define the updated form of , where we’re updating on some arbitrary history , environment , and off-history partial stochastic policy which tells us how we act for all histories that lack as a prefix.
Definition 1: Infrafunction Update For an infrafunction of type , history , environment , and partial stochastic policy which specifies all aspects of how the agent behaves except after history , , the update of the infrafunction, is the infrafunction corresponding to the set of functions Or, restated,
So, basically, what this is doing is it’s taking all the component functions, restricting them to just be about what happens beyond the partial history , scaling them down, and taking the behavior of those functions off-h to determine what constant to add to the new function. So, functions which do well off-h get a larger constant added to them than functions which do poorly off-h.
And now we get to our theorem, that if you update infrafunctions in this way, it’s always better (from the perspective of the start of time) to optimize for the updated infrafunction than to go off and rewrite yourself to optimize for something else.
Theorem 3: Dynamic Consistency For any environment , finite history , off-history policy , and infrafunctions and , we have that Or, restating in words, selecting the after-h policy by argmaxing for makes an overall policy that outscores the policy you get by selecting the after-h policy to argmax for .
Ok, but what does this sort of update mean in practice? Well, intuitively, if you’re optimizing according to an infrafunction, and some of the component functions you’re worst-casing over are sufficiently well-satisfied in other branches, they kind of “drop out”. We’re optimizing the worst-case, so the functions that are doing pretty well elsewhere can be ignored as long as you’re not acting disastrously with respect to them. You’re willing to take a hit according to those functions, in order to do well according to the functions that aren’t being well-satisfied in other branches.
Why Worst Case?
Worst case seems a bit sketchy. Aren’t there more sane things to do like, have a probability distribution on utility functions, and combine them according to geometric average? That’s what Nash Bargaining does to aggregate a bunch of utility functions into one! Scott Garrabrant wrote an entire sequence about that sort of stuff!
Well, guess what, it fits in the infrafunction framework. Geometric averaging of utility functions ends up being writeable as an infrafunction! (But I don’t know what it corresponds to worst-casing over). First up, a handy little result.
Proposition 2: Double Integral Inequality If , let be an abbreviation for . Then for all , and and and , we have that
Corollary 1: -Averaging is Well-Defined Given any distribution over a family of functions or infrafunctions , define the -average of this family (for ) as the function -averaging always produces an infrafunction.
Corollary 2: Geometric Mean Makes Infrafunctions The geometric mean of a distribution over utility functions is an infrafunction.
Proof: The geometric mean of a distribution over utility functions is the function However, the geometric mean is the same as the integral. So we get that it’s actually writeable as And we can apply Corollary 2 to get that it’s an infrafunction.
So, this -mixing, for is… well, for 1, it’s just usual mixing. For 0, it’s taking the geometric average of the functions. For , it’s taking the minimum of all the functions. So, it provides a nice way to interpolate between minimization, geometric averaging, and arithmetic averaging, and all these ways of aggregating functions produce infrafunctions.
Just don’t ask me what utility functions are actually in the infrafunction corresponding to a geometric mixture.
The Crappy Optimizer Theorem
Technically this theorem doesn’t actually belong in this post. But it’s close enough to the subject matter of this post to throw it in anyways. It turns out that “every” (not really) vaguely optimizer-ish process can be reexpressed as some sort of ultradistribution. An ultradistribution is basically an infradistribution (a closed convex set of probability distributions), except it maximizes functions instead of minimizing them.
And so, “every” (not really) optimizer-y process can be thought of as just argmax operating over a more restricted set of probability distributions.
Try not to read too much into the Crappy Optimizer Theorem, I’d very strongly advise that you take your favorite non-argmax process and work out how it violates the assumptions of the theorem. Hopefully that’ll stop you from thinking this theorem is the final word on optimization processes.
Anyways, let’s discuss this. The type signature of argmax is . Let’s say we’re looking for some new sort of optimizer that isn’t argmax. We want a function of the same type signature, that “doesn’t try as hard”.
We don’t actually know what is! It could be anything. However, there’s a function , which I’ll call the “score-shift” function, and it’s defined as follows. Basically, given an optimizer and a function, you run the optimizer on the function to get a good input, and shove that input through the function to get a score. As a concrete example, . If you have a function , argmax over it, and plug the result of argmax back into , that’s the same as taking the function and producing a score of .
So, instead of studying the magical optimizer black box , we’ll be studying instead, and characterizing the optimization process by what scores it attains on various functions. There are four properties in particular, which it seems like any good optimizer should fulfill.
1: -additivity For any constant function and function , .
2: Homogenity For any and function , .
3: Subadditivity For any functions , .
4: Zero bound For any function , .
Rephrasing this, though we don’t know what the optimization-y process is, it’s quite plausible that it’ll fulfill the following four properties.
1: If you add a constant to the input function, you’ll get that constant added to your score.
2: If you rescale the input function, it rescales the score the optimization process attains.
3: Optimizing the sum of two functions does worse than optimizing them separately and adding your best scores together.
4: Optimizing a function that’s never positive can’t produce a positive score.
Exercise: Which of these properties does softmax break? Which of these properties does gradient ascent with infinitesimal step-size break?
Also, notice that the first two properties combined are effectively saying “if you try to optimize a utility function, the optimization process will ignore scales and shifts in that utility function”.
Theorem 4: Crappy Optimizer Theorem For any selection process where fulfills the four properties above, will hold for some closed convex set of probability distributions . Conversely, the function for any closed convex set will fulfill the four properties of an optimization process.
Informal Corollary 3: Any selection process where fulfills the four properties is effectively just argmax but using a restricted set of probability distributions.
Other Aspects of Infrafunctions
Infrafunctions are the analogue of random variables in inframeasure theory. Here are two useful properties of them.
First off, in the classical case of functions, we can average functions together. There’s a distinguished averaging function . Pretty obvious.
When we go to infrafunctions, this gets extended somewhat. There’s a distinguished function , where is the space of infradistributions, and is the space of infrafunctions. If you know enough category theory, we can say that the space of infrafunctions is a -algebra, where is the infradistribution monad. If you don’t know enough category theory, basically, there’s an infra-version of “averaging points together” and it makes all the diagrams commute really nicely.
Proposition 3: The space of infrafunctions is a -algebra, with the function being defined as .
Also, in the classical case, if you’ve got a function , that produces a function in a pretty obvious way. Just precompose. .
A similar thing holds here. Except, in this case, instead of a function, we can generalize further to a continuous infrakernel . Again, to get a function , you just precompose. . Take the distribution , shove it through the infrakernel to get an infradistribution on , and shove that through the infrafunction .
Proposition 4: All continuous infrakernels induce a function via
So, given an infrakernel (and functions are a special case of this) going one way, you can transfer infrafunctions backwards from one space to the other.
The restriction to continuous infrakernels, though, actually does matter here. A function induces two infrakernels, one of type (the image), and one of type (the preimage). So, theoretically we could get a function of type by routing through the preimage function. However, since it requires continuity of the function to make things work out, you can only reverse the direction if the function mapping a point to its preimage is Hausdorff-continuous. So, for functions with Hausdorff-continuous inverses, you can flip the usual direction and go . But this trick doesn’t work in general, only is valid in general.
There’s a bunch of other things you can do, like intersection of infrafunctions making a new infrafunction, and union making a new infrafunction. Really, most of the same stuff as works with infradistributions.
The field is wide-open. But it’s a single framework that can accomodate Scott’s generalized epistemic states, Scott’s geometric averaging, Knightian uncertainty, intersecting and unioning that uncertainty, averaging, quantilizers, dynamic consistency, worst-case reasoning, and approximate maximization. So it seems quite promising for future use.