When does rationality-as-search have nontrivial implications?

(This origi­nated as a com­ment on the post “Embed­ded World-Models,” but it makes a broadly ap­pli­ca­ble point and is sub­stan­tial enough to be a post, so I thought I’d make it a post as well.)


This post feels quite similar to things I have writ­ten in the past to jus­tify my lack of en­thu­si­asm about ideal­iza­tions like AIXI and log­i­cally-om­ni­scient Bayes. But I would go fur­ther: I think that grap­pling with em­bed­ded­ness prop­erly will in­evitably make the­o­ries of this gen­eral type ir­rele­vant or use­less, so that “a the­ory like this, ex­cept for em­bed­ded agents” is not a thing that we can rea­son­ably want. To spec­ify what I mean, I’ll use this para­graph as a jump­ing-off point:

Embed­ded agents don’t have the lux­ury of step­ping out­side of the uni­verse to think about how to think. What we would like would be a the­ory of ra­tio­nal be­lief for situ­ated agents which pro­vides foun­da­tions that are similarly as strong as the foun­da­tions Bayesi­anism pro­vides for du­al­is­tic agents.

Most “the­o­ries of ra­tio­nal be­lief” I have en­coun­tered—in­clud­ing Bayesi­anism in the sense I think is meant here—are framed at the level of an eval­u­a­tor out­side the uni­verse, and have es­sen­tially no con­tent when we try to trans­fer them to in­di­vi­d­ual em­bed­ded agents. This is be­cause these the­o­ries tend to be de­rived in the fol­low­ing way:

  • We want a the­ory of the best pos­si­ble be­hav­ior for agents.

  • We have some class of “prac­ti­cally achiev­able” strate­gies , which can ac­tu­ally be im­ple­mented by agents. We note that an agent’s ob­ser­va­tions provide some in­for­ma­tion about the qual­ity of differ­ent strate­gies . So if it were pos­si­ble to fol­low a rule like “find the best given your ob­ser­va­tions, and then fol­low that ,” this rule would spit out very good agent be­hav­ior.

  • Usu­ally we soften this to a perfor­mance-weighted av­er­age rather than a hard argmax, but the prin­ci­ple is the same: if we could search over all of , the rule that says “do the search and then fol­low what it says” can be com­pet­i­tive with the very best . (Triv­ially so, since it has ac­cess to the best strate­gies, along with all the oth­ers.)

  • But usu­ally . That is, the strat­egy “search over all prac­ti­cal strate­gies and fol­low the best ones” is not a prac­ti­cal strat­egy. But we ar­gue that this is fine, since we are con­struct­ing a the­ory of ideal be­hav­ior. It doesn’t have to be prac­ti­cally im­ple­mentable.

For ex­am­ple, in Solomonoff, is defined by com­putabil­ity while is al­lowed to be un­com­putable. In the LIA con­struc­tion, is defined by poly­time com­plex­ity while is al­lowed to run slower than poly­time. In log­i­cally-om­ni­scient Bayes, finite sets of hy­pothe­ses can be ma­nipu­lated in a finite uni­verse but the full Boolean alge­bra over hy­pothe­ses gen­er­ally can­not (N.B. I don’t think this last case fits my schema quite as well as the other two).

I hope the frame­work I’ve just in­tro­duced helps clar­ify what I find un­promis­ing about these the­o­ries. By con­struc­tion, any agent you can ac­tu­ally de­sign and run is a sin­gle el­e­ment of (a “prac­ti­cal strat­egy”), so ev­ery fact about ra­tio­nal­ity that can be in­cor­po­rated into agent de­sign gets “hid­den in­side” the in­di­vi­d­ual , and the only things you can learn from the “ideal the­ory” are things which can’t fit into a prac­ti­cal strat­egy.

For ex­am­ple, sup­pose (rea­son­ably) that model av­er­ag­ing and com­plex­ity penalties are broadly good ideas that lead to good re­sults. But all of the model av­er­ag­ing and com­plex­ity pe­nal­iza­tion that can be done com­putably hap­pens in­side some Tur­ing ma­chine or other, at the level “be­low” Solomonoff. Thus Solomonoff only tells you about the ex­tra ad­van­tage you can get by do­ing these things un­com­putably. Any kind of nice Bayesian av­er­age over Tur­ing ma­chines that can hap­pen com­putably is (of course) just an­other Tur­ing ma­chine.

This also ex­plains why I find it mis­lead­ing to say that good prac­ti­cal strate­gies con­sti­tute “ap­prox­i­ma­tions to” an ideal the­ory of this type. Of course, since just says to fol­low the best strate­gies in , if you are fol­low­ing a very good strat­egy in your be­hav­ior will tend to be close to that of . But this can­not be at­tributed to any of the search­ing over that does, since you are not do­ing a search over ; you are ex­e­cut­ing a sin­gle mem­ber of and ig­nor­ing the oth­ers. Any search­ing that can be done prac­ti­cally col­lapses down to a sin­gle prac­ti­cal strat­egy, and any that doesn’t is not prac­ti­cal.

Con­cretely, this talk of ap­prox­i­ma­tions is like say­ing that a very suc­cess­ful chess player “ap­prox­i­mates” the rule “con­sult all pos­si­ble chess play­ers, then weight their moves by past perfor­mance.” Yes, the skil­led player will play similarly to this rule, but they are not fol­low­ing it, not even ap­prox­i­mately! They are only them­selves, not any other player.

Any the­ory of ideal ra­tio­nal­ity that wants to be a guide for em­bed­ded agents will have to be con­strained in the same ways the agents are. But the­o­ries of ideal ra­tio­nal­ity usu­ally get all of their con­tent by go­ing to a level above the agents they judge. So this new the­ory would have to be a very differ­ent sort of thing.


To state all this more pithily: if we de­sign the search space to con­tains ev­ery­thing fea­si­ble, then ra­tio­nal­ity-as-search has no fea­si­ble im­pli­ca­tions. If ra­tio­nal­ity-as-search is to have fea­si­ble im­pli­ca­tions, then the search space must be weak enough for there to be some­thing fea­si­ble that is not a point in the search space.