Approachability in infinite dimensional spaces

ApproachabilityinInfiniteDimensionalSpacesbyEhudLehrer1SchoolofMathematicalSciencesSacklerFacultyofExactSciencesTelAvivUniversity,RamatAvivTelAviv69978,Israele-mail:[e-mail]:April1997February27,2002Abstract.TheapproachabilitytheoremofBlackwell(1956b)isextendedtoinfinitedimensionalspaces.Twoplayersplayasequentialgamewhosepayoffsarerandomvariables.AsetCofrandomvariablesissaidtobeapproachablebyplayer1ifhehasastrategythatensuresthatthediffer-encebetweentheaveragepayoffanditsclosestpointinC,almostsurelyconvergestozero.Necessaryconditionsforasettobeapproachablearepresented.1IacknowledgeEilonSolanforhishelpfulcomments.1IntroductionBlackwell(1956b)consideredatwo-playersequentialgamewherethepayoffsateachroundarevectorsinafinitedimensionalspace,ratherthannumbers.Apre-specifiedsetinthe(vector)payoffspaceCissaidtobeapproachablebyplayer1ifhehasastrategythatensuresthatthedifferencebetweenthepartialaveragepayoffanditsclosestpointinC,almostsurelyconvergeswithtimetozero.Incontrastwiththefinitedimensionalpayoffspace,asinBlackwell(1956b),thepayoffspaceconsideredhereisinfinitedimensional.Wepresentsufficientconditionsthatensurealmostsurelyapproachability.Onemayconsideravector-payoffgameasfinitelymanygamesplayedsimultaneously.Ineachroundaplayertakesanactionwhichappliestoallgamesplayed.Iftherearenotransferablepayoffsfromonegametoanother,thepayoffsofthegamesareconsideredasonevector.Theobjectiveofplayer1thenistobringtheaveragevectorpayoffintoasetC.Blackwelltreatedthecasewhereineachroundallgamesareplayed.Herewealsoexaminethecasewherenotallgamesareplayedallthetime.Ineachround,dependingonthehistory,adifferentsetofgamesisplayed.Intermsofvector-payoffs,somecoordinatesmaybeinactiveinsomerounds.Therelevantaverageisthereforethesumofpastpayoffsdividedbythenumberoftimesacoordinatewaspreviouslyactive.Thus,thesumofpayoffsisdividedbyanumberthatmayvarywiththecoordinate.Thisfactimposesadifficultyinthatitdoesnotallowuseofthemulti-linearityoftheinnerproduct.Theapproachabilitytheoremhasbeenappliedextensivelysinceitsin-ception.Blackwell(1956a)himselfnotedthatHannan’s(1957)no-regrettheoremcanbeprovenbyusingtheapproachabilitytheorem.AumannandMaschler(1995)usedittoshowthattheuninformedplayerinare-1peatedgamewithincompleteinformationcanguaranteeatleastwhatisthenproventobethevalue.RecentlytheapproachabilitytheorygainedarevivalduetotheinfluentialworkofFosterandVohra(1997and1999)oncalibrationanditsrelationtocorrelatedequilibrium.HartandMas-Colell(2000)demonstratedaninteractivelearningprocessthatconvergestocorrelatedequilibrium.InHartandMas-Colell(2001)theyusedtheideabehindthegeometricprincipleofapproachabilitytointroducealargefam-ilyofadaptivelearningprocedures.Rustichini(1999)provedano-regrettheoremforacaseofimperfectmonitoring.Spinat(2000)showedthatanyminimalapproachablesetisaB-set,thatis,asetwhichsatisfiestheconditionofBlackwell’stheorem.InhisoriginalpaperBlackwell(1956b)alsointroducedthenotionofweakapproachability.Vieille(1992)useddifferentialgameswithafixeddurationtostudyweakapproachabilityinfinitedimensionalspaces.Asforapproachabilityinlargespaces,Lehrer(2001a)usedittoshowthatthereexistsapredictionschemethatpassesalargesetofcheckingrulesalaDavid(1982).Sandroniatal.(2000)extendedthisresulttothecasewherethecheckingrulesareprediction-based,thatis,whenaninspectorcanuserulesthatarebasedoncurrentforecastingratherthanonhistoricalonesonly.Lehrer(2001b)showedtheexistenceofaregret-freestrategyagainstinfinitelymanyperformancecriteria.Lehrer(2001c)introducedaninfinitegamewhereineachroundplayer1choosesadigitandplayer2adistributionoverdigits.Player1winsifthesequenceofdigitshechoseduringthegameisnormalwithrespecttothemeasureinducedbythesequenceofdistributionsplayer2chosethroughthegame.Lehrer(2001c)provedbytheapproachabilitytheoreminlargespacesthatplayer1hasapurewinningstrategyinthisgame.Thisstrategyisinparticularaprocedurebywhichonecanconstructanextendednormalnumberwithrespecttoanydistribution.Inthispaperweseparatethegeometricaspectsofapproachabilityfrom2thestrategicaspects.Thegeometricprinciplesbehindapproachabilityareintroducedfirst(Section3)andthenappliedtorandom-variable-payoffgames(inSection5).Section6isdevotedtodemonstratingtherelationbetweenthelawoflargenumbersandtheideaofapproachability.2ApproachabilityinanInfiniteDimensionalSpaceConsiderasequentialgamewhereateachstageplayerichoosesanac-tionfromameasurablesetSi,i=1;2:Let(sn1;sn2)2S1£S2denotethepairofactionstakenattimen.Ahistoryoflengthnisasequence(s11;s12;s21;s22;:::;sn1;sn2).Historiesoflengthnwilllaterbedenotedashn.ThesetofallfinitehistoriesisH=[n(S1£S2)n.Foranyhs;hn2Hwesaythathshnifhsisaprefixofhn.DenoteH=(S1£S2)1.Foragivenh12Hwedenotebyhnitsnthprefix.Let(Ω;¹;F)beaprobabilityspaceandÂbeafunctionfromHtothesetofrandomvariablesdefinedon(Ω;¹;F)thattakesonlyvaluesinf0;1g.Thus,foreveryh2H,Â(h)isarandomvariabledefinedover(Ω;¹;F)thatattainsonlytwovalues,0or1.WhenÂ(h)(!)=1,wesaythatafterthehistoryh,!isactiveandotherwise,that!isinactive.ThefunctionÂiscalledtheindicator.Thepayoffattimenafterthehistoryhn¡12Hoflengthn¡1,isdeterminedbyth