When does rationality-as-search have nontrivial implications?

post by nostalgebraist · 2018-11-04T22:42:01.452Z · LW · GW · 12 comments

Contents

12 comments

(This originated as a comment [LW(p) · GW(p)] on the post "Embedded World-Models," [? · GW] but it makes a broadly applicable point and is substantial enough to be a post, so I thought I'd make it a post as well.)

This post [? · GW] feels quite similar to things I have written in the past to justify my lack of enthusiasm about idealizations like AIXI and logically-omniscient Bayes. But I would go further: I think that grappling with embeddedness properly will inevitably make theories of this general type irrelevant or useless, so that "a theory like this, except for embedded agents" is not a thing that we can reasonably want. To specify what I mean, I'll use this paragraph as a jumping-off point:

Embedded agents don’t have the luxury of stepping outside of the universe to think about how to think. What we would like would be a theory of rational belief for situated agents which provides foundations that are similarly as strong as the foundations Bayesianism provides for dualistic agents.

Most "theories of rational belief" I have encountered -- including Bayesianism in the sense I think is meant here -- are framed at the level of an evaluator outside the universe, and have essentially no content when we try to transfer them to individual embedded agents. This is because these theories tend to be derived in the following way:

For example, in Solomonoff, is defined by computability while is allowed to be uncomputable. In the LIA construction, is defined by polytime complexity while is allowed to run slower than polytime. In logically-omniscient Bayes, finite sets of hypotheses can be manipulated in a finite universe but the full Boolean algebra over hypotheses generally cannot (N.B. I don't think this last case fits my schema quite as well as the other two).

I hope the framework I've just introduced helps clarify what I find unpromising about these theories. By construction, any agent you can actually design and run is a single element of (a "practical strategy"), so every fact about rationality that can be incorporated into agent design gets "hidden inside" the individual , and the only things you can learn from the "ideal theory" are things which can't fit into a practical strategy.

For example, suppose (reasonably) that model averaging and complexity penalties are broadly good ideas that lead to good results. But all of the model averaging and complexity penalization that can be done computably happens inside some Turing machine or other, at the level "below" Solomonoff. Thus Solomonoff only tells you about the extra advantage you can get by doing these things uncomputably. Any kind of nice Bayesian average over Turing machines that can happen computably is (of course) just another Turing machine.

This also explains why I find it misleading to say that good practical strategies constitute "approximations to" an ideal theory of this type. Of course, since just says to follow the best strategies in , if you are following a very good strategy in your behavior will tend to be close to that of . But this cannot be attributed to any of the searching over that does, since you are not doing a search over ; you are executing a single member of and ignoring the others. Any searching that can be done practically collapses down to a single practical strategy, and any that doesn't is not practical.

Concretely, this talk of approximations is like saying that a very successful chess player "approximates" the rule "consult all possible chess players, then weight their moves by past performance." Yes, the skilled player will play similarly to this rule, but they are not following it, not even approximately! They are only themselves, not any other player.

Any theory of ideal rationality that wants to be a guide for embedded agents will have to be constrained in the same ways the agents are. But theories of ideal rationality usually get all of their content by going to a level above the agents they judge. So this new theory would have to be a very different sort of thing.

To state all this more pithily: if we design the search space to contains everything feasible, then rationality-as-search has no feasible implications. If rationality-as-search is to have feasible implications, then the search space must be weak enough for there to be something feasible that is not a point in the search space.

12 comments

Comments sorted by top scores.

comment by Vaniver · 2018-11-06T17:51:01.204Z · LW(p) · GW(p)

This seems broadly right to me, but it seems to me like metaheuristics (in the numerical optimization sense) are practical and have a structure like the one that you're describing. Neural architecture search is the name people are using for this sort of thing in contemporary ML.

What's different between them and the sort of thing you describe? Well, for one the softening is even stronger; rather than a performance-weighted average across all strategies, it's a performance-weighted sampling strategy that has access to all strategies (but will only actually evaluate a small subset of them). But it seems like the core strategy--be both doing object-level cognition and meta-level cognition about how you're doing object-level cognitive--is basically the same.

It remains unclear to me whether the right way to find these meta-strategies is something like "start at the impractical ideal and rescue what you can" or "start with something that works and build new features"; it seems like modern computational Bayesian methods look more like the former than the latter. When I think about how to describe human epistemology, it seems like computationally bounded Bayes is a promising approach (where probabilities change both by the standard updates among hypotheses that already exist, and new operations to be formalized to add or remove hypotheses; you want to be able to capture "Why didn't you assign high probability to X?" "Because I didn't think of it; now that I have, I do."). But of course I'm using my judgment that already works to consider adding new features here, rather than having built how to think out of rescuing what I can from the impractical ideal of how to think.

Replies from: nostalgebraist
↑ comment by nostalgebraist · 2018-11-09T05:33:35.367Z · LW(p) · GW(p)
But it seems like the core strategy--be both doing object-level cognition and meta-level cognition about how you're doing object-level cognitive--is basically the same.
It remains unclear to me whether the right way to find these meta-strategies is something like "start at the impractical ideal and rescue what you can" or "start with something that works and build new features"; it seems like modern computational Bayesian methods look more like the former than the latter.

I'd argue that there's usually a causal arrow from practical lore to impractical ideals first, even if the ideals also influence practice at a later stage. Occam's Razor came before Solomonoff; "change your mind when you see surprising new evidence" came before formal Bayes. The "core strategy" you refer to sounds like "do both exploration and exploitation," which is the sort of idea I'd imagine goes back millennia (albeit not in those exact terms).

One of my goals in writing this post was to formalize the feeling I get, when I think about an idealized theory of this kind, that it's a "redundant step" added on top of something that already does all the work by itself -- like taking a decision theory and appending the rule "take the actions this theory says to take." But rather than being transparently vacuous, like that example, they are vacuous in a more hidden way, and the redundant steps they add tend to resemble legitimately good ideas familiar from practical experience.

Consider the following (ridiculous) theory of rationality: "do the most rational thing, and also, remember to stay hydrated :)". In a certain inane sense, most rational behavior "conforms to" this theory, since the theory parasitizes on whatever existing notion of rationality you had, and staying hydrated is generally a good idea and thus does not tend to conflict with rationality. And whenever staying hydrated is a good idea, one could imagine pointing to this theory and saying "see, there's the hydration theory of rationality at work again." But, of course, none of this should actually count in the "hydration theory's" favor: all the real work is hidden in the first step ("do the most rational thing"), and insofar as hydration is rational, there's no need to specify it explicitly. This doesn't quite map onto the schema, but captures the way in which I think these theories tend to confuse people.

If the more serious ideals we're talking about are like the "hydration theory," we'd expect them to have the appearance of explaining existing practical methods, and of retrospectively explaining the success of new methods, while not being very useful for generating any new methods. And this seems generally true to me: there's a lot of ensemble-like or regularization-like stuff in ML that can be interpreted as Bayesian averaging/updating over some base space of models, but most of the excitement in ML is in these base spaces. We didn't get neural networks from Bayesian first principles.

comment by Richard_Ngo (ricraz) · 2018-11-05T15:15:03.799Z · LW(p) · GW(p)

This was a very useful and well-explained idea. Strongly upvoted.

comment by DanielFilan · 2018-11-08T19:42:58.317Z · LW(p) · GW(p)

I think that this is a slightly wrong account of the case for Solomonoff induction. The claim is not just that Solomonoff induction predicts computable environments better than computable predictors, but rather that the Solomonoff prior is an enumerable semimeasure that is also a mixture over every enumerable semimeasure, and therefore predicts computable environments at least as well as any other enumerable semimeasure. So, using your notation, . It still fails as a theory of embedded agency, since it only predicts computable environments, but it's not true that we must only compare it to prediction strategies strictly weaker than itself. The paper (Non-)Equivalence of Universal Priors has a decent discussion of this.

Replies from: DanielFilan
↑ comment by DanielFilan · 2018-11-09T06:13:32.700Z · LW(p) · GW(p)

Although it's also worth noting that as per Theorem 16 of the above paper, not all universally dominant enumerable semimeasures are versions of the Solomonoff prior, so there's the possibility that the Solomonoff prior only does well by finding a good non-Solomonoff distribution and mimicking that.

Replies from: cousin_it
↑ comment by cousin_it · 2018-11-09T10:45:33.515Z · LW(p) · GW(p)

Not sure that theorem gives us very much. Yeah, a mixture of all programs must include some programs that stop without outputting anything, so M(empty string) must be strictly greater than M(0)+M(1). But we can also make a semimeasure where M(empty string)=1, M(0)=M(1)=1/2 by fiat, and otherwise defer to a mixture. So it can't itself be a mixture of all programs, but will be just as good for sequence prediction. That's all the theorem says. Basically, if a Swiss army knife solves all problems, we shouldn't be surprised by the existence of other tools (like a Swiss army knife with added fishing hook) that also solve all problems.

Replies from: DanielFilan
↑ comment by DanielFilan · 2018-11-09T22:07:46.198Z · LW(p) · GW(p)

Yes, it's true that the theorem doesn't show that there's anything exciting that's interestingly different from a universal mixture, just that AFAIK we can't disprove that, and the theorem forces us to come up with a non-trivial notion of 'interestingly different' if we want to.

comment by cousin_it · 2018-11-05T19:44:30.491Z · LW(p) · GW(p)

AIXI-like agents can be embedded in uncomputable worlds. So I'm not sure your post has much to do with embeddedness. You're just pointing out that AIXI is a poor metaphor when there are resource constraints, no matter if the agent is embedded or not. Sure, I agree with that.

Replies from: nostalgebraist
↑ comment by nostalgebraist · 2018-11-05T20:44:08.796Z · LW(p) · GW(p)

My argument isn’t specialized to AIXI — note that I also used LIA as an example, which has a weaker R along with a weaker S.

Likewise, if you put AIXI in a world whose parts can do uncomputable things (like AIXI), you have the same pattern one level up. Your S is stronger, with uncomptable strategies, but by the same token, you lose AIXI’s optimality. It’s only searching over computable strategies, and you have to look at all strategies (including the uncomputable ones) to make sure you’re optimal. This leads to a rule R distinct from AIXI, just as AIXI is distinct from a Turing machine.

I guess it’s conceivable that this hits a fixed point at this level or some higher level? That would be abstractly interesting but not very relevant to embeddedness in the kind of world I think I inhabit.

Replies from: cousin_it
↑ comment by cousin_it · 2018-11-05T21:28:15.025Z · LW(p) · GW(p)

Have you seen papers like this one? Embedded AIXIs converge on Nash equilibrium against each other, that's optimal enough, you don't need to go up another level. I agree it's not very relevant to our world, but there's no difference in terms of embeddedness, the only difference is resource constraints.

Replies from: nostalgebraist
↑ comment by nostalgebraist · 2018-11-06T02:02:20.647Z · LW(p) · GW(p)

I was not aware of these results -- thanks. I'd glanced at the papers on reflective oracles but mentally filed them as just about game theory, when of course they are really very relevant to the sort of thing I am concerned with here.

We have a remaining semantic disagreement. I think you're using "embeddedness" quite differently than it's used in the "Embedded World-Models" post. For example, in that post (text version):

In a traditional Bayesian framework, “learning” means Bayesian updating. But as we noted, Bayesian updating requires that the agent start out large enough to consider a bunch of ways the world can be, and learn by ruling some of these out.

Embedded agents need resource-limited, logically uncertain updates, which don’t work like this.

Unfortunately, Bayesian updating is the main way we know how to think about an agent progressing through time as one unified agent. The Dutch book justification for Bayesian reasoning is basically saying this kind of updating is the only way to not have the agent’s actions on Monday work at cross purposes, at least a little, to the agent’s actions on Tuesday.

Embedded agents are non-Bayesian. And non-Bayesian agents tend to get into wars with their future selves.

The 2nd and 4th paragraphs here are clearly false for reflective AIXI. And the 2nd paragraph implies that embedded agents are definitionally resource-limited. There is a true and important sense in which reflective AIXI can be "embedded" -- that was the point of coming up with it! -- but the Embedded Agency sequence seems to be excluding this kind of case when it talks about embedded agents. This strikes me as something I'd like to see clarified by the authors of the sequence, actually.

I think the difference may be that we talk about "a theory of rationality for embedded agents," we could mean "a theory that has consequences for agents equally powerful to it," or we could mean something more like "a theory that has consequences for agents of arbitrarily low power." Reflective AIXI (as a theory of rationality) explains why reflective AIXI (as an agent) is optimally designed, but it can't explain why a real-world robot might or might not be optimally designed.

comment by Logan Zoellner (logan-zoellner) · 2024-08-30T14:45:37.093Z · LW(p) · GW(p)

It seems fair to worry about smuggling hypercomputation into optimal agents via assuming global optimization (due to the intractability of the halting problem).  But there are plenty of domains where the global optima is just the asymptotic limit of local search.

For example suppose I have to predict the outcome of a biased coin flip, observing a bunch of actual coin flips and then computing p(heads) based off of that converges just fine to the right answer.

Even in Turing-complete domains, search sort of just works even though the Halting problem tells us proving we've found an optimal solution may be impossible.