Formal Open Problem in Decision Theory

(This post was origi­nally pub­lished on March 31st 2017, and has been brought for­warded as part of the AI Align­ment Fo­rum launch se­quence on fixed points.)

In this post, I pre­sent a new for­mal open prob­lem. A pos­i­tive an­swer would be valuable for de­ci­sion the­ory re­search. A nega­tive an­swer would be helpful, mostly for figur­ing out what is the clos­est we can get to a pos­i­tive an­swer. I also give some mo­ti­va­tion for the prob­lem, and some par­tial progress.

Open Prob­lem: Does there ex­ist a topolog­i­cal space (in some con­ve­nient cat­e­gory of topolog­i­cal spaces) such that there ex­ists a con­tin­u­ous sur­jec­tion from to the space (of con­tin­u­ous func­tions from to )?


Mo­ti­va­tion:

Topolog­i­cal Nat­u­ral­ized Agents: Con­sider an agent who makes some ob­ser­va­tions and then takes an ac­tion. For sim­plic­ity, we as­sume there are only two pos­si­ble ac­tions, and . We also as­sume that the agent can ran­dom­ize, so we can think of this agent as out­putting a real num­ber in , rep­re­sent­ing its prob­a­bil­ity of tak­ing ac­tion .

Thus, we can think of an agent as hav­ing a policy which is a func­tion from the space of pos­si­ble ob­ser­va­tions to . We will re­quire that our agent be­haves con­tin­u­ously as a func­tion of its ob­ser­va­tions, so we will think of the space of all pos­si­ble poli­cies as the space of con­tin­u­ous func­tions from to , de­noted .

We will let de­note the space of all pos­si­ble agents, and we will have a func­tion which takes in an agent, and out­puts that agent’s policy.

Now, con­sider what hap­pens when there are other agents in the en­vi­ron­ment. For sim­plic­ity, we will as­sume that our agent ob­serves one other agent, and makes no other ob­ser­va­tions. Thus, we want to con­sider the case where , so .

We want to be con­tin­u­ous, be­cause we want a small change in an agent to cor­re­spond to a small change in the agent’s policy. This is par­tic­u­larly im­por­tant since other agents will be im­ple­ment­ing con­tin­u­ous func­tions on agents, and we would like any con­tin­u­ous func­tion on poli­cies to be able to be con­sid­ered valid con­tin­u­ous func­tion on agents.

We also want to be sur­jec­tive. This means that our space of agents is suffi­ciently rich that for any pos­si­ble con­tin­u­ous policy, there is an agent in our space that im­ple­ments that policy.

In or­der to meet all these crite­ria si­mul­ta­neously, we need a space of agents, and a con­tin­u­ous sur­jec­tion .

Unify­ing Fixed Point The­o­rems: While we are pri­mar­ily in­ter­ested in the above mo­ti­va­tion, there is an­other sec­ondary mo­ti­va­tion, which may be more com­pel­ling for those less in­ter­ested in agent foun­da­tions.

There are (at least) two main clusters of fixed point the­o­rems that have come up many times in de­ci­sion the­ory, and math­e­mat­ics in gen­eral.

First, there is the Law­vere cluster of the­o­rems. This in­cludes the Law­vere fixed point the­o­rem, the di­ag­o­nal lemma, and the ex­is­tence of Quines and fixed point com­bi­na­tors. Th­ese are used to prove Gödel’s in­com­plete­ness The­o­rem, Can­tor’s The­o­rem, Löb’s The­o­rem, and achieve ro­bust co­op­er­a­tion in the Pri­soner’s Dilemma in modal frame­work and bounded var­i­ants. All of these can be seen as corol­laries of Law­vere’s fixed point the­o­rem, which states that in a carte­sian closed cat­e­gory, if there is a point-sur­jec­tive map , then ev­ery mor­phism has a fixed point.

Se­cond, there is the Brouwer cluster of the­o­rems. This in­cludes Brouwer’s fixed point the­o­rem, The Kaku­tani fixed point the­o­rem, Poin­caré–Miranda, and the in­ter­me­di­ate value the­o­rem. Th­ese are used to prove the ex­is­tence of Nash Equil­ibria, Log­i­cal In­duc­tors, and Reflec­tive Or­a­cles.

If we had a topolog­i­cal space and a con­tin­u­ous sur­jec­tion , this would al­low us to prove the one-di­men­sional Brouwer fixed point the­o­rem di­rectly us­ing the Law­vere fixed point the­o­rem, and thus unify these two im­por­tant clusters.

Thanks to Qiaochu Yuan for point­ing out the con­nec­tion to Law­vere’s fixed point the­o­rem (and ac­tu­ally ask­ing this ques­tion three years ago).


Par­tial Progress:

Most Di­ag­o­nal­iza­tion In­tu­itions Do Not Ap­ply: A com­mon ini­tial re­ac­tion to this ques­tion is to con­jec­ture that such an does not ex­ist, due to car­di­nal­ity or di­ag­o­nal­iza­tion in­tu­itions. How­ever, note that all of the di­ag­o­nal­iza­tion the­o­rems pass through (some mod­ifi­ca­tion of) the same lemma: Law­vere’s fixed point the­o­rem. How­ever, this lemma does not ap­ply here!

For ex­am­ple, in the cat­e­gory of sets, the rea­son that there is no sur­jec­tion from any set to the power set, , is be­cause if there were such a sur­jec­tion, Law­vere’s fixed point the­o­rem would im­ply that ev­ery func­tion from to it­self has a fixed point (which is clearly not the case, since there is a func­tion that swaps and ).

How­ever, we already know by Brouwer’s fixed point the­o­rem that ev­ery con­tin­u­ous func­tion from the in­ter­val to it­self has a fixed point, so the stan­dard di­ag­o­nal­iza­tion in­tu­itions do not work here.

Im­pos­si­ble if You Re­place with e.g. : This also pro­vides a quick san­ity check on at­tempts to con­struct an . Any con­struc­tion that would not be mean­ingfully differ­ent if the in­ter­val is re­placed with the cir­cle is doomed from the start. This is be­cause a con­tin­u­ous sur­jec­tion would vi­o­late Law­vere’s fixed point the­o­rem, since there is a con­tin­u­ous map from to it­self with­out fixed points.

Im­pos­si­ble if you Re­quire a Homeo­mor­phism: When I first asked this ques­tion I asked for a home­o­mor­phism be­tween and . Sam Eisen­stat has given a very clever ar­gu­ment why this is im­pos­si­ble. You can read it here. In short, us­ing a home­o­mor­phism, you would be able to use Law­vere to con­struct a con­tin­u­ous map that send a func­tion from to it­self to a fixed point of that func­tion. How­ever, no such con­tin­u­ous map ex­ists.


Notes:

If you pre­fer not to think about the topol­ogy of , you can in­stead find a space , and a con­tin­u­ous map , such that for ev­ery con­tin­u­ous func­tion , there ex­ists an , such that for all , .

Many of the de­tails in the mo­ti­va­tion could be differ­ent. I would like to see progress on similar ques­tions. For ex­am­ple, you could add some com­putabil­ity con­di­tion to the space of func­tions. How­ever, I am also very cu­ri­ous which way this spe­cific ques­tion will go.

This post came out of many con­ver­sa­tions, with many peo­ple, in­clud­ing: Sam, Qiaochu, Tsvi, Jes­sica, Pa­trick, Nate, Ryan, Mar­cello, Alex Men­nen, Jack Gal­lagher, and James Cook.


This post was origi­nally pub­lished on March 31st 2017, and has been brought for­warded as part of the AI Align­ment Fo­rum launch se­quences.

To­mor­row’s AIAF se­quences post will be ‘Iter­ated Am­plifi­ca­tion and Distil­la­tion’ by Ajeya Co­tra, in the se­quence on iter­ated am­plifi­ca­tion.