a score of 40
EXTRACTIVE
KG-A2C, A2C, A2C-chained, A2C-Explore
EXTRACTIVE
BIBREF6 introduce the KG-A2C, which uses a knowledge graph based state-representation to aid in the section of actions in a combinatorially-sized action-space—specifically they use the knowledge graph to constrain the kinds of entities that can be filled in the blanks in the template action-space. They test their approach on Zork1, showing the combination of the knowledge graph and template action selection resulted in improvements over existing methods. They note that their approach reaches a score of 40 which corresponds to a bottleneck in Zork1 where the player is eaten by a “grue” (resulting in negative reward) if the player has not first lit a lamp. The lamp must be lit many steps after first being encountered, in a different section of the game; this action is necessary to continue exploring but doesn’t immediately produce any positive reward. That is, there is a long term dependency between actions that is not immediately rewarded, as seen in Figure FIGREF1. Others using artificially constrained action spaces also report an inability to pass through this bottleneck BIBREF7, BIBREF8. They pose a significant challenge for these methods because the agent does not see the correct action sequence to pass the bottleneck enough times. This is in part due to the fact that for that sequence to be reinforced, the agent needs to reach the next possible reward beyond the bottleneck.
We compare our two exploration strategies to the following baselines and ablations: KG-A2C This is the exact same method presented in BIBREF6 with no modifications. A2C Represents the same approach as KG-A2C but with all the knowledge graph components removed. The state representation is text only encoded using recurrent networks. A2C-chained Is a variation on KG-A2C-chained where we use our policy chaining approach with the A2C method to train the agent instead of KG-A2C. A2C-Explore Uses A2C in addition to the exploration strategy seen in KG-A2C-Explore. The cell representations here are defined in terms of the recurrent network based encoding of the textual observation.
2002.08795
Introduction Ġand ĠBackground </s> Many Ġreinforcement Ġlearning Ġalgorithms Ġare Ġdesigned Ġfor Ġrelatively Ġsmall Ġdiscrete Ġor Ġcontinuous Ġaction Ġspaces Ġand Ġso Ġhave Ġtrouble Ġscaling . ĠText - ad venture Ġgames âĢĶ or Ġinteraction Ġf ictions âĢĶ are Ġsimulations Ġin Ġwhich Ġboth Ġan Ġagents ' Ġstate Ġand Ġaction Ġspaces Ġare Ġin Ġtextual Ġnatural Ġlanguage . ĠAn Ġexample Ġof Ġa Ġone Ġturn Ġagent Ġinteraction Ġin Ġthe Ġpopular Ġtext - game ĠZ ork 1 Ġcan Ġbe Ġseen Ġin ĠFig . ĠFIG REF 1 . ĠText - ad venture Ġgames Ġprovide Ġus Ġwith Ġmultiple Ġchallenges Ġin Ġthe Ġform Ġof Ġpartial Ġobserv ability , Ġcommons ense Ġreasoning , Ġand Ġa Ġcomb inator ially - sized Ġstate - action Ġspace . ĠText - ad venture Ġgames Ġare Ġstructured Ġas Ġlong Ġpuzzles Ġor Ġquests , Ġinter sp ersed Ġwith Ġbott len ec ks . ĠThe Ġquests Ġcan Ġusually Ġbe Ġcompleted Ġthrough Ġmultiple Ġbranching Ġpaths . ĠHowever , Ġgames Ġcan Ġalso Ġfeature Ġone Ġor Ġmore Ġbott len ec ks . ĠBott len ec ks Ġare Ġareas Ġthat Ġan Ġagent Ġmust Ġpass Ġthrough Ġin Ġorder Ġto Ġprogress Ġto Ġthe Ġnext Ġsection Ġof Ġthe Ġgame Ġregardless Ġof Ġwhat Ġpath Ġthe Ġagent Ġhas Ġtaken Ġto Ġcomplete Ġthat Ġsection Ġof Ġthe Ġquest ĠB IB REF 0 . ĠIn Ġthis Ġwork , Ġwe Ġfocus Ġon Ġmore Ġeffectively Ġexploring Ġthis Ġspace Ġand Ġsurpass ing Ġthese Ġbott len ec ks âĢĶ building Ġon Ġprior Ġwork Ġthat Ġfocuses Ġon Ġtackling Ġthe Ġother Ġproblems . </s> Form ally , Ġwe Ġuse Ġthe Ġdefinition Ġof Ġtext - ad venture Ġgames Ġas Ġseen Ġin ĠB IB REF 1 Ġand ĠB IB REF 2 . ĠThese Ġgames Ġare Ġpartially Ġobservable ĠMark ov Ġdecision Ġprocesses Ġ( P OM DP s ), Ġrepresented Ġas Ġa Ġ7 - t uple Ġof Ġ$\ l angle ĠS , T , A , \ O mega Ġ, ĠO , R , Ġ\ gam ma Ġ\ r angle Ġ$ Ġrepresenting Ġthe Ġset Ġof Ġenvironment Ġstates , Ġmostly Ġdeter ministic Ġconditional Ġtransition Ġprobabilities Ġbetween Ġstates , Ġthe Ġvocabulary Ġor Ġwords Ġused Ġto Ġcompose Ġtext Ġcommands , Ġobservations Ġreturned Ġby Ġthe Ġgame , Ġobservation Ġconditional Ġprobabilities , Ġreward Ġfunction , Ġand Ġthe Ġdiscount Ġfactor Ġrespectively . ĠFor Ġour Ġpurposes , Ġunderstanding Ġthe Ġexact Ġstate Ġand Ġaction Ġspaces Ġwe Ġuse Ġin Ġthis Ġwork Ġis Ġcritical Ġand Ġso Ġwe Ġdefine Ġeach Ġof Ġthese Ġin Ġrelative Ġdepth . </s> Action - Space . ĠTo Ġsolve ĠZ ork 1 , Ġthe Ġcannon ical Ġtext - ad venture Ġgames , Ġrequires Ġthe Ġgeneration Ġof Ġactions Ġconsisting Ġof Ġup Ġto Ġfive - words Ġfrom Ġa Ġrelatively Ġmodest Ġvocabulary Ġof Ġ6 97 Ġwords Ġrecognized Ġby Ġthe Ġgame âĢ Ļ s Ġparser . ĠThis Ġresults Ġin Ġ$\ math cal Ġ{ O } ( 697 ^ 5 ) ={ 1 . 64 e 14 } $ Ġpossible Ġactions Ġat Ġevery Ġstep . ĠTo Ġfacilitate Ġtext - ad venture Ġgame Ġplaying , ĠB IB REF 2 Ġintroduce ĠJericho , Ġa Ġframework Ġfor Ġinteracting Ġwith Ġtext - games . ĠThey Ġpropose Ġa Ġtemplate - based Ġaction Ġspace Ġin Ġwhich Ġthe Ġagent Ġfirst Ġselects Ġa Ġtemplate , Ġconsisting Ġof Ġan Ġaction Ġverb Ġand Ġpre position , Ġand Ġthen Ġfilling Ġthat Ġin Ġwith Ġrelevant Ġentities Ġ$ ($ e . g . Ġ$ [ get ] $ Ġ$ Ġ[ from ] Ġ$ Ġ$ ) $. ĠZ ork 1 Ġhas Ġ237 Ġtemplates , Ġeach Ġwith Ġup Ġto Ġtwo Ġbl anks , Ġyielding Ġa Ġtemplate - action Ġspace Ġof Ġsize Ġ$\ math cal Ġ{ O } ( 237 Ġ\ times Ġ6 97 ^ 2 ) ={ 1 . 15 e 8 } $. ĠThis Ġspace Ġis Ġstill Ġfar Ġlarger Ġthan Ġmost Ġused Ġby Ġprevious Ġapproaches Ġapplying Ġreinforcement Ġlearning Ġto Ġtext - based Ġgames . </s> State - Represent ation . ĠPrior Ġwork Ġhas Ġshown Ġthat Ġknowledge Ġgraphs Ġare Ġeffective Ġin Ġterms Ġof Ġdealing Ġwith Ġthe Ġchallenges Ġof Ġpartial Ġobserv ability Ġ$ ($ BI B REF 3 ĠB IB REF 3 ; ĠB IB REF 4 $ ) $. ĠA Ġknowledge Ġgraph Ġis Ġa Ġset Ġof Ġ3 - tu ples Ġof Ġthe Ġform Ġ$\ l angle Ġsubject , Ġrelation , Ġobject Ġ\ r angle Ġ$ . ĠThese Ġtri ples Ġare Ġextracted Ġfrom Ġthe Ġobservations Ġusing ĠStanford 's ĠOpen ĠInformation ĠExt raction Ġ( Open IE ) ĠB IB REF 5 . ĠHuman - made Ġtext - ad venture Ġgames Ġoften Ġcontain Ġrelatively Ġcomplex Ġsemi - struct ured Ġinformation Ġthat ĠOpen IE Ġis Ġnot Ġdesigned Ġto Ġparse Ġand Ġso Ġthey Ġadd Ġadditional Ġrules Ġto Ġensure Ġthat Ġthe Ġcorrect Ġinformation Ġis Ġparsed . ĠThe Ġgraph Ġitself Ġis Ġmore Ġor Ġless Ġa Ġmap Ġof Ġthe Ġworld , Ġwith Ġinformation Ġabout Ġobjects ' Ġafford ances Ġand Ġattributes Ġlinked Ġto Ġthe Ġrooms Ġthat Ġthey Ġare Ġplace Ġin Ġa Ġmap . ĠThe Ġgraph Ġalso Ġmakes Ġa Ġdistinction Ġwith Ġrespect Ġto Ġitems Ġthat Ġare Ġin Ġthe Ġagent 's Ġpossession Ġor Ġin Ġtheir Ġimmediate Ġsurrounding Ġenvironment . ĠAn Ġexample Ġof Ġwhat Ġthe Ġknowledge Ġgraph Ġlooks Ġlike Ġand Ġspecific Ġimplementation Ġdetails Ġcan Ġbe Ġfound Ġin ĠAppendix ĠSEC REF 14 . </s> BI B REF 6 Ġintroduce Ġthe ĠK G - A 2 C , Ġwhich Ġuses Ġa Ġknowledge Ġgraph Ġbased Ġstate - represent ation Ġto Ġaid Ġin Ġthe Ġsection Ġof Ġactions Ġin Ġa Ġcomb inator ially - sized Ġaction - space âĢĶ specific ally Ġthey Ġuse Ġthe Ġknowledge Ġgraph Ġto Ġconst rain Ġthe Ġkinds Ġof Ġentities Ġthat Ġcan Ġbe Ġfilled Ġin Ġthe Ġbl anks Ġin Ġthe Ġtemplate Ġaction - space . ĠThey Ġtest Ġtheir Ġapproach Ġon ĠZ ork 1 , Ġshowing Ġthe Ġcombination Ġof Ġthe Ġknowledge Ġgraph Ġand Ġtemplate Ġaction Ġselection Ġresulted Ġin Ġimprovements Ġover Ġexisting Ġmethods . ĠThey Ġnote Ġthat Ġtheir Ġapproach Ġreaches Ġa Ġscore Ġof Ġ40 Ġwhich Ġcorresponds Ġto Ġa Ġbottleneck Ġin ĠZ ork 1 Ġwhere Ġthe Ġplayer Ġis Ġeaten Ġby Ġa ĠâĢ ľ gr ue âĢ Ŀ Ġ( result ing Ġin Ġnegative Ġreward ) Ġif Ġthe Ġplayer Ġhas Ġnot Ġfirst Ġlit Ġa Ġlamp . ĠThe Ġlamp Ġmust Ġbe Ġlit Ġmany Ġsteps Ġafter Ġfirst Ġbeing Ġencountered , Ġin Ġa Ġdifferent Ġsection Ġof Ġthe Ġgame ; Ġthis Ġaction Ġis Ġnecessary Ġto Ġcontinue Ġexploring Ġbut Ġdoesn âĢ Ļ t Ġimmediately Ġproduce Ġany Ġpositive Ġreward . ĠThat Ġis , Ġthere Ġis Ġa Ġlong Ġterm Ġdependency Ġbetween Ġactions Ġthat Ġis Ġnot Ġimmediately Ġrewarded , Ġas Ġseen Ġin ĠFigure ĠFIG REF 1 . ĠOthers Ġusing Ġartificially Ġconstrained Ġaction Ġspaces Ġalso Ġreport Ġan Ġinability Ġto Ġpass Ġthrough Ġthis Ġbottleneck ĠB IB REF 7 , ĠB IB REF 8 . ĠThey Ġpose Ġa Ġsignificant Ġchallenge Ġfor Ġthese Ġmethods Ġbecause Ġthe Ġagent Ġdoes Ġnot Ġsee Ġthe Ġcorrect Ġaction Ġsequence Ġto Ġpass Ġthe Ġbottleneck Ġenough Ġtimes . ĠThis Ġis Ġin Ġpart Ġdue Ġto Ġthe Ġfact Ġthat Ġfor Ġthat Ġsequence Ġto Ġbe Ġreinforced , Ġthe Ġagent Ġneeds Ġto Ġreach Ġthe Ġnext Ġpossible Ġreward Ġbeyond Ġthe Ġbottleneck . </s> More Ġefficient Ġexploration Ġstrategies Ġare Ġrequired Ġto Ġpass Ġbott len ec ks . ĠOur Ġcontributions Ġare Ġtwo - fold . ĠWe Ġfirst Ġintroduce Ġa Ġmethod Ġthat Ġdetects Ġbott len ec ks Ġin Ġtext - games Ġusing Ġthe Ġoverall Ġreward Ġgained Ġand Ġthe Ġknowledge Ġgraph Ġstate . ĠThis Ġmethod Ġfreezes Ġthe Ġpolicy Ġused Ġto Ġreach Ġthe Ġbottleneck Ġand Ġrest arts Ġthe Ġtraining Ġfrom Ġthere Ġon Ġout , Ġadditionally Ġconducting Ġa Ġback tracking Ġsearch Ġto Ġensure Ġthat Ġa Ġsub - opt imal Ġpolicy Ġhas Ġnot Ġbeen Ġfrozen . ĠThe Ġsecond Ġcontribution Ġexplore Ġhow Ġto Ġleverage Ġknowledge Ġgraphs Ġto Ġimprove Ġexisting Ġexploration Ġalgorithms Ġfor Ġdealing Ġwith Ġcomb inator ial Ġaction - sp aces Ġsuch Ġas ĠGo - Explore ĠB IB REF 9 . ĠWe Ġadditionally Ġpresent Ġa Ġcomparative Ġab lation Ġstudy Ġanalyzing Ġthe Ġperformance Ġof Ġthese Ġmethods Ġon Ġthe Ġpopular Ġtext - game ĠZ ork 1 . </s> Expl oration ĠMethods </s> In Ġthis Ġsection , Ġwe Ġdescribe Ġmethods Ġto Ġexplore Ġcomb inator ially Ġsized Ġaction Ġspaces Ġsuch Ġas Ġtext - games âĢĶ f ocusing Ġespecially Ġon Ġmethods Ġthat Ġcan Ġdeal Ġwith Ġtheir Ġinherent Ġbottleneck Ġstructure . ĠWe Ġfirst Ġdescribe Ġour Ġmethod Ġthat Ġexplicitly Ġattempts Ġto Ġdetect Ġbott len ec ks Ġand Ġthen Ġdescribe Ġhow Ġan Ġexploration Ġalgorithm Ġsuch Ġas ĠGo ĠExplore ĠB IB REF 9 Ġcan Ġleverage Ġknowledge Ġgraphs . </s> K G - A 2 C - ch ained ĠAn Ġexample Ġof Ġa Ġbottleneck Ġcan Ġbe Ġseen Ġin ĠFigure ĠFIG REF 1 . ĠWe Ġextend Ġthe ĠK G - A 2 C Ġalgorithm Ġas Ġfollows . ĠFirst , Ġwe Ġdetect Ġbott len ec ks Ġas Ġstates Ġwhere Ġthe Ġagent Ġis Ġunable Ġto Ġprogress Ġany Ġfurther . ĠWe Ġset Ġa Ġpatience Ġparameter Ġand Ġif Ġthe Ġagent Ġhas Ġnot Ġseen Ġa Ġhigher Ġscore Ġin Ġpatience Ġsteps , Ġthe Ġagent Ġassumes Ġit Ġhas Ġbeen Ġlimited Ġby Ġa Ġbottleneck . ĠSecond , Ġwhen Ġa Ġbottleneck Ġis Ġfound , Ġwe Ġfreeze Ġthe Ġpolicy Ġthat Ġgets Ġthe Ġagent Ġto Ġthe Ġstate Ġwith Ġthe Ġhighest Ġscore . ĠThe Ġagent Ġthen Ġbegins Ġtraining Ġa Ġnew Ġpolicy Ġfrom Ġthat Ġparticular Ġstate . </s> Simply Ġfreezing Ġthe Ġpolicy Ġthat Ġled Ġto Ġthe Ġbottleneck , Ġhowever , Ġcan Ġpotentially Ġresult Ġin Ġa Ġpolicy Ġone Ġthat Ġis Ġglobally Ġsub - opt imal . ĠWe Ġtherefore Ġemploy Ġa Ġback tracking Ġstrategy Ġthat Ġrest arts Ġexploration Ġfrom Ġeach Ġof Ġthe Ġ$ n $ Ġprevious Ġsteps âĢĶ search ing Ġfor Ġa Ġmore Ġoptimal Ġpolicy Ġthat Ġreaches Ġthat Ġbottleneck . ĠAt Ġeach Ġstep , Ġwe Ġkeep Ġtrack Ġof Ġa Ġbuffer Ġof Ġ$ n $ Ġstates Ġand Ġad missible Ġactions Ġthat Ġled Ġup Ġto Ġthat Ġlocally Ġoptimal Ġstate . ĠWe Ġforce Ġthe Ġagent Ġto Ġexplore Ġfrom Ġthis Ġstate Ġto Ġattempt Ġto Ġdrive Ġit Ġout Ġof Ġthe Ġlocal Ġoptim a . ĠIf Ġit Ġis Ġfurther Ġunable Ġto Ġfind Ġitself Ġout Ġof Ġthis Ġlocal Ġoptim a , Ġwe Ġrefresh Ġthe Ġtraining Ġprocess Ġagain , Ġbut Ġstarting Ġat Ġthe Ġstate Ġimmediately Ġbefore Ġthe Ġagent Ġreaches Ġthe Ġlocal Ġoptim a . ĠIf Ġthis Ġcontinues Ġto Ġfail , Ġwe Ġcontinue Ġto Ġiter ate Ġthrough Ġthis Ġbuffer Ġof Ġseen Ġstates Ġstates Ġup Ġto Ġthat Ġlocal Ġoptim a Ġuntil Ġwe Ġeither Ġfind Ġa Ġmore Ġoptimal Ġstate Ġor Ġwe Ġrun Ġout Ġof Ġstates Ġto Ġrefresh Ġfrom , Ġin Ġwhich Ġwe Ġterminate Ġthe Ġtraining Ġalgorithm . </s> K G - A 2 C - Explore ĠGo - Explore ĠB IB REF 9 Ġis Ġan Ġalgorithm Ġthat Ġis Ġdesigned Ġto Ġkeep Ġtrack Ġof Ġsub - opt imal Ġand Ġunder - expl ored Ġstates Ġin Ġorder Ġto Ġallow Ġthe Ġagent Ġto Ġexplore Ġupon Ġmore Ġoptimal Ġstates Ġthat Ġmay Ġbe Ġa Ġresult Ġof Ġsparse Ġrewards . ĠThe ĠGo - Explore Ġalgorithm Ġconsists Ġof Ġtwo Ġphases , Ġthe Ġfirst Ġto Ġcontinuously Ġexplore Ġuntil Ġa Ġset Ġof Ġpromising Ġstates Ġand Ġcorresponding Ġtraject ories Ġare Ġfound Ġon Ġthe Ġbasis Ġof Ġtotal Ġscore , Ġand Ġthe Ġsecond Ġto Ġrobust ify Ġthis Ġfound Ġpolicy Ġagainst Ġpotential Ġsto ch astic ity Ġin Ġthe Ġgame . ĠProm ising Ġstates Ġare Ġdefined Ġas Ġthose Ġstates Ġwhen Ġexplored Ġfrom Ġwill Ġlikely Ġresult Ġin Ġhigher Ġreward Ġtraject ories . ĠSince Ġthe Ġtext Ġgames Ġwe Ġare Ġdealing Ġwith Ġare Ġmostly Ġdeter ministic , Ġwith Ġthe Ġexception Ġof ĠZ ork Ġin Ġlater Ġstages , Ġwe Ġonly Ġfocus Ġon Ġusing ĠPhase Ġ1 Ġof Ġthe ĠGo - Explore Ġalgorithm Ġto Ġfind Ġan Ġoptimal Ġpolicy . ĠB IB REF 10 Ġlook Ġat Ġapplying ĠGo - Explore Ġto Ġtext - games Ġon Ġa Ġset Ġof Ġsimpler Ġgames Ġgenerated Ġusing Ġthe Ġgame Ġgeneration Ġframework ĠText World ĠB IB REF 1 . ĠInstead Ġof Ġtraining Ġa Ġpolicy Ġnetwork Ġin Ġparallel Ġto Ġgenerate Ġactions Ġused Ġfor Ġexploration , Ġthey Ġuse Ġa Ġsmall Ġset Ġof ĠâĢ ľ ad missible Ġactions âĢ Ŀ âĢĶ actions Ġguaranteed Ġto Ġchange Ġthe Ġworld Ġstate Ġat Ġany Ġgiven Ġstep Ġduring ĠPhase Ġ1 âĢĶ to Ġexplore Ġand Ġfind Ġhigh Ġreward Ġtraject ories . ĠThis Ġspace Ġof Ġactions Ġis Ġrelatively Ġsmall Ġ( of Ġthe Ġorder Ġof Ġ$ 10 ^ 2 $ Ġper Ġstep ) Ġand Ġso Ġfinding Ġhigh Ġreward Ġtraject ories Ġin Ġlarger Ġaction - sp aces Ġsuch Ġas Ġin ĠZ ork Ġwould Ġbe Ġinf eas ible </s> Go - Explore Ġmaintains Ġan Ġarchive Ġof Ġcells âĢĶ defined Ġas Ġa Ġset Ġof Ġstates Ġthat Ġmap Ġto Ġa Ġsingle Ġrepresentation âĢĶ to Ġkeep Ġtrack Ġof Ġpromising Ġstates . ĠB IB REF 9 Ġsimply Ġenc odes Ġeach Ġcell Ġby Ġkeeping Ġtrack Ġof Ġthe Ġagent 's Ġposition Ġand ĠB IB REF 10 Ġuse Ġthe Ġtextual Ġobservations Ġencoded Ġby Ġrecurrent Ġneural Ġnetwork Ġas Ġa Ġcell Ġrepresentation . ĠWe Ġimprove Ġon Ġthis Ġimplementation Ġby Ġtraining Ġthe ĠK G - A 2 C Ġnetwork Ġin Ġparallel , Ġusing Ġthe Ġsnapshot Ġof Ġthe Ġknowledge Ġgraph Ġin Ġconjunction Ġwith Ġthe Ġgame Ġstate Ġto Ġfurther Ġencode Ġthe Ġcurrent Ġstate Ġand Ġuse Ġthis Ġas Ġa Ġcell Ġrepresentation . ĠAt Ġeach Ġstep , ĠGo - Explore Ġchooses Ġa Ġcell Ġto Ġexplore Ġat Ġrandom Ġ( weight ed Ġby Ġscore Ġto Ġprefer Ġmore Ġadvanced Ġcells ). ĠThe ĠK G - A 2 C Ġwill Ġrun Ġfor Ġa Ġnumber Ġof Ġsteps , Ġstarting Ġwith Ġthe Ġknowledge Ġgraph Ġstate Ġand Ġthe Ġlast Ġseen Ġstate Ġof Ġthe Ġgame Ġfrom Ġthe Ġcell . ĠThis Ġwill Ġgenerate Ġa Ġtrajectory Ġfor Ġthe Ġagent Ġwhile Ġfurther Ġtraining Ġthe ĠK G - A 2 C Ġat Ġeach Ġiteration , Ġcreating Ġa Ġnew Ġrepresentation Ġfor Ġthe Ġknowledge Ġgraph Ġas Ġwell Ġas Ġa Ġnew Ġgame Ġstate Ġfor Ġthe Ġcell . ĠAfter Ġexpanding Ġa Ġcell , ĠGo - Explore Ġwill Ġcontinue Ġto Ġsample Ġcells Ġby Ġweight Ġto Ġcontinue Ġexpanding Ġits Ġknown Ġstates . ĠAt Ġthe Ġsame Ġtime , ĠK G - A 2 C Ġwill Ġbenefit Ġfrom Ġthe Ġhe ur istics Ġof Ġselecting Ġpreferred Ġcells Ġand Ġbe Ġtrained Ġon Ġpromising Ġstates Ġmore Ġoften . </s> E val uation </s> We Ġcompare Ġour Ġtwo Ġexploration Ġstrategies Ġto Ġthe Ġfollowing Ġbas elines Ġand Ġabl ations : </s> K G - A 2 C ĠThis Ġis Ġthe Ġexact Ġsame Ġmethod Ġpresented Ġin ĠB IB REF 6 Ġwith Ġno Ġmodifications . </s> A 2 C ĠRep resents Ġthe Ġsame Ġapproach Ġas ĠK G - A 2 C Ġbut Ġwith Ġall Ġthe Ġknowledge Ġgraph Ġcomponents Ġremoved . ĠThe Ġstate Ġrepresentation Ġis Ġtext Ġonly Ġencoded Ġusing Ġrecurrent Ġnetworks . </s> A 2 C - ch ained ĠIs Ġa Ġvariation Ġon ĠK G - A 2 C - ch ained Ġwhere Ġwe Ġuse Ġour Ġpolicy Ġch aining Ġapproach Ġwith Ġthe ĠA 2 C Ġmethod Ġto Ġtrain Ġthe Ġagent Ġinstead Ġof ĠK G - A 2 C . </s> A 2 C - Explore ĠUses ĠA 2 C Ġin Ġaddition Ġto Ġthe Ġexploration Ġstrategy Ġseen Ġin ĠK G - A 2 C - Explore . ĠThe Ġcell Ġrepresentations Ġhere Ġare Ġdefined Ġin Ġterms Ġof Ġthe Ġrecurrent Ġnetwork Ġbased Ġencoding Ġof Ġthe Ġtextual Ġobservation . </s> Figure ĠFIG REF 10 Ġshows Ġthat Ġagents Ġutilizing Ġknowledge - graph s Ġin Ġaddition Ġto Ġeither Ġenhanced Ġexploration Ġmethod Ġfar Ġoutper form Ġthe Ġbaseline ĠA 2 C Ġand ĠK G - A 2 C . ĠK G - A 2 C - ch ained Ġand ĠK G - A 2 C - Explore Ġboth Ġpass Ġthe Ġbottleneck Ġof Ġa Ġscore Ġof Ġ40 , Ġwhereas ĠA 2 C - Explore Ġgets Ġto Ġthe Ġbottleneck Ġbut Ġcannot Ġsurpass Ġit . </s> There Ġare Ġa Ġcouple Ġof Ġkey Ġinsights Ġthat Ġcan Ġbe Ġdrawn Ġfrom Ġthese Ġresults ĠThe Ġfirst Ġis Ġthat Ġthe Ġknowledge Ġgraph Ġappears Ġto Ġbe Ġcritical ; Ġit Ġis Ġtheor ized Ġto Ġhelp Ġwith Ġpartial Ġobserv ability . ĠHowever Ġthe Ġknowledge Ġgraph Ġrepresentation Ġisn 't Ġsufficient Ġin Ġthat Ġthe Ġknowledge Ġgraph Ġrepresentation Ġwithout Ġenhanced Ġexploration Ġmethods Ġcannot Ġsurpass Ġthe Ġbottleneck . ĠA 2 C - ch ained âĢĶ which Ġexplores Ġwithout Ġa Ġknowledge Ġgraph âĢĶ f ails Ġto Ġeven Ġoutper form Ġthe Ġbaseline ĠA 2 C . ĠWe Ġhypothes ize Ġthat Ġthis Ġis Ġdue Ġto Ġthe Ġknowledge Ġgraph Ġaiding Ġimplicitly Ġin Ġthe Ġsample Ġefficiency Ġof Ġbottleneck Ġdetection Ġand Ġsubsequent Ġexploration . ĠThat Ġis , Ġexploring Ġafter Ġback tracking Ġfrom Ġa Ġpotentially Ġdetected Ġbottleneck Ġis Ġmuch Ġmore Ġefficient Ġin Ġthe Ġknowledge Ġgraph Ġbased Ġagent . </s> The ĠGo - Explore Ġbased Ġexploration Ġalgorithm Ġsees Ġless Ġof Ġa Ġdifference Ġbetween Ġagents . ĠA 2 C - Explore Ġconver ges Ġmore Ġquickly , Ġbut Ġto Ġa Ġlower Ġreward Ġtrajectory Ġthat Ġfails Ġto Ġpass Ġthe Ġbottleneck , Ġwhereas ĠK G - A 2 C - Explore Ġtakes Ġlonger Ġto Ġreach Ġa Ġsimilar Ġreward Ġbut Ġconsistently Ġmakes Ġit Ġthrough Ġthe Ġbottleneck . ĠThe Ġknowledge Ġgraph Ġcell Ġrepresentation Ġappears Ġto Ġthus Ġbe Ġa Ġbetter Ġindication Ġof Ġwhat Ġa Ġpromising Ġstate Ġis Ġas Ġopposed Ġto Ġjust Ġthe Ġtextual Ġobservation . </s> Comp aring Ġthe Ġadvanced Ġexploration Ġmethods Ġwhen Ġusing Ġthe Ġknowledge Ġgraph , Ġwe Ġsee Ġthat Ġboth Ġagents Ġsuccessfully Ġpass Ġthe Ġbottleneck Ġcorresponding Ġto Ġentering Ġthe Ġcellar Ġand Ġlighting Ġthe Ġlamp Ġand Ġreach Ġcomparable Ġscores Ġwithin Ġa Ġmargin Ġof Ġerror . ĠK G - A 2 C - ch ained Ġis Ġsignificantly Ġmore Ġsample Ġefficient Ġand Ġconver ges Ġfaster . ĠWe Ġcan Ġinfer Ġthat Ġch aining Ġpolicies Ġby Ġexplicitly Ġdetecting Ġbott len ec ks Ġlets Ġus Ġpass Ġit Ġmore Ġquickly Ġthan Ġattempting Ġto Ġfind Ġpromising Ġcell Ġrepresentations Ġwith ĠGo - Explore . ĠThis Ġform Ġof Ġchained Ġexploration Ġwith Ġback tracking Ġis Ġparticularly Ġsuited Ġto Ġsequential Ġdecision Ġmaking Ġproblems Ġthat Ġcan Ġbe Ġrepresented Ġas Ġac y cl ic Ġdirected Ġgraphs Ġas Ġin ĠFigure ĠFIG REF 1 . </s> App endix Ġ: :: ĠZ ork 1 </s> Z ork 1 Ġis Ġone Ġof Ġthe Ġfirst Ġtext - ad venture Ġgames Ġand Ġheavily Ġinfluences Ġgames Ġreleased Ġlater Ġin Ġterms Ġof Ġnarrative Ġstyle Ġand Ġgame Ġstructure . ĠIt Ġis Ġa Ġdungeon Ġcraw ler Ġwhere Ġthe Ġplayer Ġmust Ġexplore Ġa Ġvast Ġworld Ġand Ġcollect Ġa Ġseries Ġof Ġtreasures . ĠIt Ġwas Ġidentified Ġby ĠB IB REF 2 Ġas Ġa Ġmoons hot Ġgame Ġand Ġhas Ġbeen Ġthe Ġsubject Ġof Ġmuch Ġwork Ġin Ġleaning Ġagents ĠB IB REF 12 , ĠB IB REF 7 , ĠB IB REF 11 , ĠB IB REF 8 . ĠRewards Ġare Ġgiven Ġto Ġthe Ġplayer Ġwhen Ġthey Ġcollect Ġtreasures Ġas Ġwell Ġas Ġwhen Ġimportant Ġintermediate Ġmilestones Ġneeded Ġto Ġfurther Ġexplore Ġthe Ġworld Ġare Ġpassed . ĠFigure ĠFIG REF 15 Ġand ĠFigure ĠFIG REF 1 Ġshow Ġus Ġa Ġmap Ġof Ġthe Ġworld Ġof ĠZ ork 1 Ġand Ġthe Ġcorresponding Ġquest Ġstructure . </s> The Ġbottleneck Ġseen Ġat Ġa Ġscore Ġof Ġaround Ġ40 Ġis Ġwhen Ġthe Ġplayer Ġfirst Ġenters Ġthe Ġcellar Ġon Ġthe Ġright Ġside Ġof Ġthe Ġmap . ĠThe Ġcellar Ġis Ġdark Ġand Ġyou Ġneed Ġto Ġimmediately Ġlight Ġthe Ġlamp Ġto Ġsee Ġanything . ĠAttempt ing Ġto Ġexplore Ġthe Ġcellar Ġin Ġthe Ġdark Ġresults Ġin Ġyou Ġbeing Ġinstantly Ġkilled Ġby Ġa Ġmonster Ġknown Ġas Ġa ĠâĢ ľ gr ue âĢ Ŀ . </s> App endix Ġ: :: ĠKnowledge ĠGraph ĠRules </s> We Ġmake Ġno Ġchanges Ġfrom Ġthe Ġgraph Ġupdate Ġrules Ġused Ġby ĠB IB REF 6 . ĠCandidate Ġinteractive Ġobjects Ġare Ġidentified Ġby Ġperforming Ġpart - of - speech Ġtagging Ġon Ġthe Ġcurrent Ġobservation , Ġidentifying Ġsingular Ġand Ġproper Ġnoun s Ġas Ġwell Ġas Ġadject ives , Ġand Ġare Ġthen Ġfiltered Ġby Ġchecking Ġif Ġthey Ġcan Ġbe Ġexamined Ġusing Ġthe Ġcommand Ġ$ ex amine $ Ġ$ OB J $. ĠOnly Ġthe Ġinteractive Ġobjects Ġnot Ġfound Ġin Ġthe Ġinventory Ġare Ġlinked Ġto Ġthe Ġnode Ġcorresponding Ġto Ġthe Ġcurrent Ġroom Ġand Ġthe Ġinventory Ġitems Ġare Ġlinked Ġto Ġthe ĠâĢ ľ you âĢ Ŀ Ġnode . ĠThe Ġonly Ġother Ġrule Ġapplied Ġuses Ġthe Ġnavig ational Ġactions Ġperformed Ġby Ġthe Ġagent Ġto Ġinfer Ġthe Ġrelative Ġpositions Ġof Ġrooms , Ġe . g . Ġ$\ l angle Ġkitchen , down , cell ar Ġ\ r angle Ġ$ Ġwhen Ġthe Ġagent Ġperforms Ġ$ go $ Ġ$ down $ Ġwhen Ġin Ġthe Ġkitchen Ġto Ġmove Ġto Ġthe Ġcellar . </s> App endix Ġ: :: ĠHyper param eters </s> Hyper param eters Ġused Ġfor Ġour Ġagents Ġare Ġgiven Ġbelow . ĠPat ience Ġand Ġbuffer Ġsize Ġare Ġused Ġfor Ġthe Ġpolicy Ġch aining Ġmethod Ġas Ġdescribed Ġin ĠSection ĠSEC REF 2 . ĠCell Ġstep Ġsize Ġis Ġa Ġparameter Ġused Ġfor ĠGo - Explore Ġand Ġdescribes Ġhow Ġmany Ġsteps Ġare Ġtaken Ġwhen Ġexploring Ġin Ġa Ġgiven Ġcell Ġstate . ĠBase Ġhyper param eters Ġfor ĠK G - A 2 C Ġare Ġtaken Ġfrom ĠB IB REF 6 Ġand Ġthe Ġsame Ġparameters Ġare Ġused Ġfor ĠA 2 C .
Introduction and Background Many reinforcement learning algorithms are designed for relatively small discrete or continuous action spaces and so have trouble scaling. Text-adventure games—or interaction fictions—are simulations in which both an agents' state and action spaces are in textual natural language. An example of a one turn agent interaction in the popular text-game Zork1 can be seen in Fig. FIGREF1. Text-adventure games provide us with multiple challenges in the form of partial observability, commonsense reasoning, and a combinatorially-sized state-action space. Text-adventure games are structured as long puzzles or quests, interspersed with bottlenecks. The quests can usually be completed through multiple branching paths. However, games can also feature one or more bottlenecks. Bottlenecks are areas that an agent must pass through in order to progress to the next section of the game regardless of what path the agent has taken to complete that section of the quest BIBREF0. In this work, we focus on more effectively exploring this space and surpassing these bottlenecks—building on prior work that focuses on tackling the other problems. Formally, we use the definition of text-adventure games as seen in BIBREF1 and BIBREF2. These games are partially observable Markov decision processes (POMDPs), represented as a 7-tuple of $\langle S,T,A,\Omega , O,R, \gamma \rangle $ representing the set of environment states, mostly deterministic conditional transition probabilities between states, the vocabulary or words used to compose text commands, observations returned by the game, observation conditional probabilities, reward function, and the discount factor respectively. For our purposes, understanding the exact state and action spaces we use in this work is critical and so we define each of these in relative depth. Action-Space. To solve Zork1, the cannonical text-adventure games, requires the generation of actions consisting of up to five-words from a relatively modest vocabulary of 697 words recognized by the game’s parser. This results in $\mathcal {O}(697^5)={1.64e14}$ possible actions at every step. To facilitate text-adventure game playing, BIBREF2 introduce Jericho, a framework for interacting with text-games. They propose a template-based action space in which the agent first selects a template, consisting of an action verb and preposition, and then filling that in with relevant entities $($e.g. $[get]$ $ [from] $ $)$. Zork1 has 237 templates, each with up to two blanks, yielding a template-action space of size $\mathcal {O}(237 \times 697^2)={1.15e8}$. This space is still far larger than most used by previous approaches applying reinforcement learning to text-based games. State-Representation. Prior work has shown that knowledge graphs are effective in terms of dealing with the challenges of partial observability $($BIBREF3 BIBREF3; BIBREF4$)$. A knowledge graph is a set of 3-tuples of the form $\langle subject, relation, object \rangle $. These triples are extracted from the observations using Stanford's Open Information Extraction (OpenIE) BIBREF5. Human-made text-adventure games often contain relatively complex semi-structured information that OpenIE is not designed to parse and so they add additional rules to ensure that the correct information is parsed. The graph itself is more or less a map of the world, with information about objects' affordances and attributes linked to the rooms that they are place in a map. The graph also makes a distinction with respect to items that are in the agent's possession or in their immediate surrounding environment. An example of what the knowledge graph looks like and specific implementation details can be found in Appendix SECREF14. BIBREF6 introduce the KG-A2C, which uses a knowledge graph based state-representation to aid in the section of actions in a combinatorially-sized action-space—specifically they use the knowledge graph to constrain the kinds of entities that can be filled in the blanks in the template action-space. They test their approach on Zork1, showing the combination of the knowledge graph and template action selection resulted in improvements over existing methods. They note that their approach reaches a score of 40 which corresponds to a bottleneck in Zork1 where the player is eaten by a “grue” (resulting in negative reward) if the player has not first lit a lamp. The lamp must be lit many steps after first being encountered, in a different section of the game; this action is necessary to continue exploring but doesn’t immediately produce any positive reward. That is, there is a long term dependency between actions that is not immediately rewarded, as seen in Figure FIGREF1. Others using artificially constrained action spaces also report an inability to pass through this bottleneck BIBREF7, BIBREF8. They pose a significant challenge for these methods because the agent does not see the correct action sequence to pass the bottleneck enough times. This is in part due to the fact that for that sequence to be reinforced, the agent needs to reach the next possible reward beyond the bottleneck. More efficient exploration strategies are required to pass bottlenecks. Our contributions are two-fold. We first introduce a method that detects bottlenecks in text-games using the overall reward gained and the knowledge graph state. This method freezes the policy used to reach the bottleneck and restarts the training from there on out, additionally conducting a backtracking search to ensure that a sub-optimal policy has not been frozen. The second contribution explore how to leverage knowledge graphs to improve existing exploration algorithms for dealing with combinatorial action-spaces such as Go-Explore BIBREF9. We additionally present a comparative ablation study analyzing the performance of these methods on the popular text-game Zork1. Exploration Methods In this section, we describe methods to explore combinatorially sized action spaces such as text-games—focusing especially on methods that can deal with their inherent bottleneck structure. We first describe our method that explicitly attempts to detect bottlenecks and then describe how an exploration algorithm such as Go Explore BIBREF9 can leverage knowledge graphs. KG-A2C-chained An example of a bottleneck can be seen in Figure FIGREF1. We extend the KG-A2C algorithm as follows. First, we detect bottlenecks as states where the agent is unable to progress any further. We set a patience parameter and if the agent has not seen a higher score in patience steps, the agent assumes it has been limited by a bottleneck. Second, when a bottleneck is found, we freeze the policy that gets the agent to the state with the highest score. The agent then begins training a new policy from that particular state. Simply freezing the policy that led to the bottleneck, however, can potentially result in a policy one that is globally sub-optimal. We therefore employ a backtracking strategy that restarts exploration from each of the $n$ previous steps—searching for a more optimal policy that reaches that bottleneck. At each step, we keep track of a buffer of $n$ states and admissible actions that led up to that locally optimal state. We force the agent to explore from this state to attempt to drive it out of the local optima. If it is further unable to find itself out of this local optima, we refresh the training process again, but starting at the state immediately before the agent reaches the local optima. If this continues to fail, we continue to iterate through this buffer of seen states states up to that local optima until we either find a more optimal state or we run out of states to refresh from, in which we terminate the training algorithm. KG-A2C-Explore Go-Explore BIBREF9 is an algorithm that is designed to keep track of sub-optimal and under-explored states in order to allow the agent to explore upon more optimal states that may be a result of sparse rewards. The Go-Explore algorithm consists of two phases, the first to continuously explore until a set of promising states and corresponding trajectories are found on the basis of total score, and the second to robustify this found policy against potential stochasticity in the game. Promising states are defined as those states when explored from will likely result in higher reward trajectories. Since the text games we are dealing with are mostly deterministic, with the exception of Zork in later stages, we only focus on using Phase 1 of the Go-Explore algorithm to find an optimal policy. BIBREF10 look at applying Go-Explore to text-games on a set of simpler games generated using the game generation framework TextWorld BIBREF1. Instead of training a policy network in parallel to generate actions used for exploration, they use a small set of “admissible actions”—actions guaranteed to change the world state at any given step during Phase 1—to explore and find high reward trajectories. This space of actions is relatively small (of the order of $10^2$ per step) and so finding high reward trajectories in larger action-spaces such as in Zork would be infeasible Go-Explore maintains an archive of cells—defined as a set of states that map to a single representation—to keep track of promising states. BIBREF9 simply encodes each cell by keeping track of the agent's position and BIBREF10 use the textual observations encoded by recurrent neural network as a cell representation. We improve on this implementation by training the KG-A2C network in parallel, using the snapshot of the knowledge graph in conjunction with the game state to further encode the current state and use this as a cell representation. At each step, Go-Explore chooses a cell to explore at random (weighted by score to prefer more advanced cells). The KG-A2C will run for a number of steps, starting with the knowledge graph state and the last seen state of the game from the cell. This will generate a trajectory for the agent while further training the KG-A2C at each iteration, creating a new representation for the knowledge graph as well as a new game state for the cell. After expanding a cell, Go-Explore will continue to sample cells by weight to continue expanding its known states. At the same time, KG-A2C will benefit from the heuristics of selecting preferred cells and be trained on promising states more often. Evaluation We compare our two exploration strategies to the following baselines and ablations: KG-A2C This is the exact same method presented in BIBREF6 with no modifications. A2C Represents the same approach as KG-A2C but with all the knowledge graph components removed. The state representation is text only encoded using recurrent networks. A2C-chained Is a variation on KG-A2C-chained where we use our policy chaining approach with the A2C method to train the agent instead of KG-A2C. A2C-Explore Uses A2C in addition to the exploration strategy seen in KG-A2C-Explore. The cell representations here are defined in terms of the recurrent network based encoding of the textual observation. Figure FIGREF10 shows that agents utilizing knowledge-graphs in addition to either enhanced exploration method far outperform the baseline A2C and KG-A2C. KG-A2C-chained and KG-A2C-Explore both pass the bottleneck of a score of 40, whereas A2C-Explore gets to the bottleneck but cannot surpass it. There are a couple of key insights that can be drawn from these results The first is that the knowledge graph appears to be critical; it is theorized to help with partial observability. However the knowledge graph representation isn't sufficient in that the knowledge graph representation without enhanced exploration methods cannot surpass the bottleneck. A2C-chained—which explores without a knowledge graph—fails to even outperform the baseline A2C. We hypothesize that this is due to the knowledge graph aiding implicitly in the sample efficiency of bottleneck detection and subsequent exploration. That is, exploring after backtracking from a potentially detected bottleneck is much more efficient in the knowledge graph based agent. The Go-Explore based exploration algorithm sees less of a difference between agents. A2C-Explore converges more quickly, but to a lower reward trajectory that fails to pass the bottleneck, whereas KG-A2C-Explore takes longer to reach a similar reward but consistently makes it through the bottleneck. The knowledge graph cell representation appears to thus be a better indication of what a promising state is as opposed to just the textual observation. Comparing the advanced exploration methods when using the knowledge graph, we see that both agents successfully pass the bottleneck corresponding to entering the cellar and lighting the lamp and reach comparable scores within a margin of error. KG-A2C-chained is significantly more sample efficient and converges faster. We can infer that chaining policies by explicitly detecting bottlenecks lets us pass it more quickly than attempting to find promising cell representations with Go-Explore. This form of chained exploration with backtracking is particularly suited to sequential decision making problems that can be represented as acyclic directed graphs as in Figure FIGREF1. Appendix ::: Zork1 Zork1 is one of the first text-adventure games and heavily influences games released later in terms of narrative style and game structure. It is a dungeon crawler where the player must explore a vast world and collect a series of treasures. It was identified by BIBREF2 as a moonshot game and has been the subject of much work in leaning agents BIBREF12, BIBREF7, BIBREF11, BIBREF8. Rewards are given to the player when they collect treasures as well as when important intermediate milestones needed to further explore the world are passed. Figure FIGREF15 and Figure FIGREF1 show us a map of the world of Zork1 and the corresponding quest structure. The bottleneck seen at a score of around 40 is when the player first enters the cellar on the right side of the map. The cellar is dark and you need to immediately light the lamp to see anything. Attempting to explore the cellar in the dark results in you being instantly killed by a monster known as a “grue”. Appendix ::: Knowledge Graph Rules We make no changes from the graph update rules used by BIBREF6. Candidate interactive objects are identified by performing part-of-speech tagging on the current observation, identifying singular and proper nouns as well as adjectives, and are then filtered by checking if they can be examined using the command $examine$ $OBJ$. Only the interactive objects not found in the inventory are linked to the node corresponding to the current room and the inventory items are linked to the “you” node. The only other rule applied uses the navigational actions performed by the agent to infer the relative positions of rooms, e.g. $\langle kitchen,down,cellar \rangle $ when the agent performs $go$ $down$ when in the kitchen to move to the cellar. Appendix ::: Hyperparameters Hyperparameters used for our agents are given below. Patience and buffer size are used for the policy chaining method as described in Section SECREF2. Cell step size is a parameter used for Go-Explore and describes how many steps are taken when exploring in a given cell state. Base hyperparameters for KG-A2C are taken from BIBREF6 and the same parameters are used for A2C.
What are the baselines?
eb2d5edcdfe18bd708348283f92a32294bb193a5
What Ġare Ġthe Ġbas elines ?
a Ġscore Ġof Ġ40
<s> What Ġare Ġthe Ġbas elines ? </s> Introduction Ġand ĠBackground </s> Many Ġreinforcement Ġlearning Ġalgorithms Ġare Ġdesigned Ġfor Ġrelatively Ġsmall Ġdiscrete Ġor Ġcontinuous Ġaction Ġspaces Ġand Ġso Ġhave Ġtrouble Ġscaling . ĠText - ad venture Ġgames âĢĶ or Ġinteraction Ġf ictions âĢĶ are Ġsimulations Ġin Ġwhich Ġboth Ġan Ġagents ' Ġstate Ġand Ġaction Ġspaces Ġare Ġin Ġtextual Ġnatural Ġlanguage . ĠAn Ġexample Ġof Ġa Ġone Ġturn Ġagent Ġinteraction Ġin Ġthe Ġpopular Ġtext - game ĠZ ork 1 Ġcan Ġbe Ġseen Ġin ĠFig . ĠFIG REF 1 . ĠText - ad venture Ġgames Ġprovide Ġus Ġwith Ġmultiple Ġchallenges Ġin Ġthe Ġform Ġof Ġpartial Ġobserv ability , Ġcommons ense Ġreasoning , Ġand Ġa Ġcomb inator ially - sized Ġstate - action Ġspace . ĠText - ad venture Ġgames Ġare Ġstructured Ġas Ġlong Ġpuzzles Ġor Ġquests , Ġinter sp ersed Ġwith Ġbott len ec ks . ĠThe Ġquests Ġcan Ġusually Ġbe Ġcompleted Ġthrough Ġmultiple Ġbranching Ġpaths . ĠHowever , Ġgames Ġcan Ġalso Ġfeature Ġone Ġor Ġmore Ġbott len ec ks . ĠBott len ec ks Ġare Ġareas Ġthat Ġan Ġagent Ġmust Ġpass Ġthrough Ġin Ġorder Ġto Ġprogress Ġto Ġthe Ġnext Ġsection Ġof Ġthe Ġgame Ġregardless Ġof Ġwhat Ġpath Ġthe Ġagent Ġhas Ġtaken Ġto Ġcomplete Ġthat Ġsection Ġof Ġthe Ġquest ĠB IB REF 0 . ĠIn Ġthis Ġwork , Ġwe Ġfocus Ġon Ġmore Ġeffectively Ġexploring Ġthis Ġspace Ġand Ġsurpass ing Ġthese Ġbott len ec ks âĢĶ building Ġon Ġprior Ġwork Ġthat Ġfocuses Ġon Ġtackling Ġthe Ġother Ġproblems . </s> Form ally , Ġwe Ġuse Ġthe Ġdefinition Ġof Ġtext - ad venture Ġgames Ġas Ġseen Ġin ĠB IB REF 1 Ġand ĠB IB REF 2 . ĠThese Ġgames Ġare Ġpartially Ġobservable ĠMark ov Ġdecision Ġprocesses Ġ( P OM DP s ), Ġrepresented Ġas Ġa Ġ7 - t uple Ġof Ġ$\ l angle ĠS , T , A , \ O mega Ġ, ĠO , R , Ġ\ gam ma Ġ\ r angle Ġ$ Ġrepresenting Ġthe Ġset Ġof Ġenvironment Ġstates , Ġmostly Ġdeter ministic Ġconditional Ġtransition Ġprobabilities Ġbetween Ġstates , Ġthe Ġvocabulary Ġor Ġwords Ġused Ġto Ġcompose Ġtext Ġcommands , Ġobservations Ġreturned Ġby Ġthe Ġgame , Ġobservation Ġconditional Ġprobabilities , Ġreward Ġfunction , Ġand Ġthe Ġdiscount Ġfactor Ġrespectively . ĠFor Ġour Ġpurposes , Ġunderstanding Ġthe Ġexact Ġstate Ġand Ġaction Ġspaces Ġwe Ġuse Ġin Ġthis Ġwork Ġis Ġcritical Ġand Ġso Ġwe Ġdefine Ġeach Ġof Ġthese Ġin Ġrelative Ġdepth . </s> Action - Space . ĠTo Ġsolve ĠZ ork 1 , Ġthe Ġcannon ical Ġtext - ad venture Ġgames , Ġrequires Ġthe Ġgeneration Ġof Ġactions Ġconsisting Ġof Ġup Ġto Ġfive - words Ġfrom Ġa Ġrelatively Ġmodest Ġvocabulary Ġof Ġ6 97 Ġwords Ġrecognized Ġby Ġthe Ġgame âĢ Ļ s Ġparser . ĠThis Ġresults Ġin Ġ$\ math cal Ġ{ O } ( 697 ^ 5 ) ={ 1 . 64 e 14 } $ Ġpossible Ġactions Ġat Ġevery Ġstep . ĠTo Ġfacilitate Ġtext - ad venture Ġgame Ġplaying , ĠB IB REF 2 Ġintroduce ĠJericho , Ġa Ġframework Ġfor Ġinteracting Ġwith Ġtext - games . ĠThey Ġpropose Ġa Ġtemplate - based Ġaction Ġspace Ġin Ġwhich Ġthe Ġagent Ġfirst Ġselects Ġa Ġtemplate , Ġconsisting Ġof Ġan Ġaction Ġverb Ġand Ġpre position , Ġand Ġthen Ġfilling Ġthat Ġin Ġwith Ġrelevant Ġentities Ġ$ ($ e . g . Ġ$ [ get ] $ Ġ$ Ġ[ from ] Ġ$ Ġ$ ) $. ĠZ ork 1 Ġhas Ġ237 Ġtemplates , Ġeach Ġwith Ġup Ġto Ġtwo Ġbl anks , Ġyielding Ġa Ġtemplate - action Ġspace Ġof Ġsize Ġ$\ math cal Ġ{ O } ( 237 Ġ\ times Ġ6 97 ^ 2 ) ={ 1 . 15 e 8 } $. ĠThis Ġspace Ġis Ġstill Ġfar Ġlarger Ġthan Ġmost Ġused Ġby Ġprevious Ġapproaches Ġapplying Ġreinforcement Ġlearning Ġto Ġtext - based Ġgames . </s> State - Represent ation . ĠPrior Ġwork Ġhas Ġshown Ġthat Ġknowledge Ġgraphs Ġare Ġeffective Ġin Ġterms Ġof Ġdealing Ġwith Ġthe Ġchallenges Ġof Ġpartial Ġobserv ability Ġ$ ($ BI B REF 3 ĠB IB REF 3 ; ĠB IB REF 4 $ ) $. ĠA Ġknowledge Ġgraph Ġis Ġa Ġset Ġof Ġ3 - tu ples Ġof Ġthe Ġform Ġ$\ l angle Ġsubject , Ġrelation , Ġobject Ġ\ r angle Ġ$ . ĠThese Ġtri ples Ġare Ġextracted Ġfrom Ġthe Ġobservations Ġusing ĠStanford 's ĠOpen ĠInformation ĠExt raction Ġ( Open IE ) ĠB IB REF 5 . ĠHuman - made Ġtext - ad venture Ġgames Ġoften Ġcontain Ġrelatively Ġcomplex Ġsemi - struct ured Ġinformation Ġthat ĠOpen IE Ġis Ġnot Ġdesigned Ġto Ġparse Ġand Ġso Ġthey Ġadd Ġadditional Ġrules Ġto Ġensure Ġthat Ġthe Ġcorrect Ġinformation Ġis Ġparsed . ĠThe Ġgraph Ġitself Ġis Ġmore Ġor Ġless Ġa Ġmap Ġof Ġthe Ġworld , Ġwith Ġinformation Ġabout Ġobjects ' Ġafford ances Ġand Ġattributes Ġlinked Ġto Ġthe Ġrooms Ġthat Ġthey Ġare Ġplace Ġin Ġa Ġmap . ĠThe Ġgraph Ġalso Ġmakes Ġa Ġdistinction Ġwith Ġrespect Ġto Ġitems Ġthat Ġare Ġin Ġthe Ġagent 's Ġpossession Ġor Ġin Ġtheir Ġimmediate Ġsurrounding Ġenvironment . ĠAn Ġexample Ġof Ġwhat Ġthe Ġknowledge Ġgraph Ġlooks Ġlike Ġand Ġspecific Ġimplementation Ġdetails Ġcan Ġbe Ġfound Ġin ĠAppendix ĠSEC REF 14 . </s> BI B REF 6 Ġintroduce Ġthe ĠK G - A 2 C , Ġwhich Ġuses Ġa Ġknowledge Ġgraph Ġbased Ġstate - represent ation Ġto Ġaid Ġin Ġthe Ġsection Ġof Ġactions Ġin Ġa Ġcomb inator ially - sized Ġaction - space âĢĶ specific ally Ġthey Ġuse Ġthe Ġknowledge Ġgraph Ġto Ġconst rain Ġthe Ġkinds Ġof Ġentities Ġthat Ġcan Ġbe Ġfilled Ġin Ġthe Ġbl anks Ġin Ġthe Ġtemplate Ġaction - space . ĠThey Ġtest Ġtheir Ġapproach Ġon ĠZ ork 1 , Ġshowing Ġthe Ġcombination Ġof Ġthe Ġknowledge Ġgraph Ġand Ġtemplate Ġaction Ġselection Ġresulted Ġin Ġimprovements Ġover Ġexisting Ġmethods . ĠThey Ġnote Ġthat Ġtheir Ġapproach Ġreaches Ġa Ġscore Ġof Ġ40 Ġwhich Ġcorresponds Ġto Ġa Ġbottleneck Ġin ĠZ ork 1 Ġwhere Ġthe Ġplayer Ġis Ġeaten Ġby Ġa ĠâĢ ľ gr ue âĢ Ŀ Ġ( result ing Ġin Ġnegative Ġreward ) Ġif Ġthe Ġplayer Ġhas Ġnot Ġfirst Ġlit Ġa Ġlamp . ĠThe Ġlamp Ġmust Ġbe Ġlit Ġmany Ġsteps Ġafter Ġfirst Ġbeing Ġencountered , Ġin Ġa Ġdifferent Ġsection Ġof Ġthe Ġgame ; Ġthis Ġaction Ġis Ġnecessary Ġto Ġcontinue Ġexploring Ġbut Ġdoesn âĢ Ļ t Ġimmediately Ġproduce Ġany Ġpositive Ġreward . ĠThat Ġis , Ġthere Ġis Ġa Ġlong Ġterm Ġdependency Ġbetween Ġactions Ġthat Ġis Ġnot Ġimmediately Ġrewarded , Ġas Ġseen Ġin ĠFigure ĠFIG REF 1 . ĠOthers Ġusing Ġartificially Ġconstrained Ġaction Ġspaces Ġalso Ġreport Ġan Ġinability Ġto Ġpass Ġthrough Ġthis Ġbottleneck ĠB IB REF 7 , ĠB IB REF 8 . ĠThey Ġpose Ġa Ġsignificant Ġchallenge Ġfor Ġthese Ġmethods Ġbecause Ġthe Ġagent Ġdoes Ġnot Ġsee Ġthe Ġcorrect Ġaction Ġsequence Ġto Ġpass Ġthe Ġbottleneck Ġenough Ġtimes . ĠThis Ġis Ġin Ġpart Ġdue Ġto Ġthe Ġfact Ġthat Ġfor Ġthat Ġsequence Ġto Ġbe Ġreinforced , Ġthe Ġagent Ġneeds Ġto Ġreach Ġthe Ġnext Ġpossible Ġreward Ġbeyond Ġthe Ġbottleneck . </s> More Ġefficient Ġexploration Ġstrategies Ġare Ġrequired Ġto Ġpass Ġbott len ec ks . ĠOur Ġcontributions Ġare Ġtwo - fold . ĠWe Ġfirst Ġintroduce Ġa Ġmethod Ġthat Ġdetects Ġbott len ec ks Ġin Ġtext - games Ġusing Ġthe Ġoverall Ġreward Ġgained Ġand Ġthe Ġknowledge Ġgraph Ġstate . ĠThis Ġmethod Ġfreezes Ġthe Ġpolicy Ġused Ġto Ġreach Ġthe Ġbottleneck Ġand Ġrest arts Ġthe Ġtraining Ġfrom Ġthere Ġon Ġout , Ġadditionally Ġconducting Ġa Ġback tracking Ġsearch Ġto Ġensure Ġthat Ġa Ġsub - opt imal Ġpolicy Ġhas Ġnot Ġbeen Ġfrozen . ĠThe Ġsecond Ġcontribution Ġexplore Ġhow Ġto Ġleverage Ġknowledge Ġgraphs Ġto Ġimprove Ġexisting Ġexploration Ġalgorithms Ġfor Ġdealing Ġwith Ġcomb inator ial Ġaction - sp aces Ġsuch Ġas ĠGo - Explore ĠB IB REF 9 . ĠWe Ġadditionally Ġpresent Ġa Ġcomparative Ġab lation Ġstudy Ġanalyzing Ġthe Ġperformance Ġof Ġthese Ġmethods Ġon Ġthe Ġpopular Ġtext - game ĠZ ork 1 . </s> Expl oration ĠMethods </s> In Ġthis Ġsection , Ġwe Ġdescribe Ġmethods Ġto Ġexplore Ġcomb inator ially Ġsized Ġaction Ġspaces Ġsuch Ġas Ġtext - games âĢĶ f ocusing Ġespecially Ġon Ġmethods Ġthat Ġcan Ġdeal Ġwith Ġtheir Ġinherent Ġbottleneck Ġstructure . ĠWe Ġfirst Ġdescribe Ġour Ġmethod Ġthat Ġexplicitly Ġattempts Ġto Ġdetect Ġbott len ec ks Ġand Ġthen Ġdescribe Ġhow Ġan Ġexploration Ġalgorithm Ġsuch Ġas ĠGo ĠExplore ĠB IB REF 9 Ġcan Ġleverage Ġknowledge Ġgraphs . </s> K G - A 2 C - ch ained ĠAn Ġexample Ġof Ġa Ġbottleneck Ġcan Ġbe Ġseen Ġin ĠFigure ĠFIG REF 1 . ĠWe Ġextend Ġthe ĠK G - A 2 C Ġalgorithm Ġas Ġfollows . ĠFirst , Ġwe Ġdetect Ġbott len ec ks Ġas Ġstates Ġwhere Ġthe Ġagent Ġis Ġunable Ġto Ġprogress Ġany Ġfurther . ĠWe Ġset Ġa Ġpatience Ġparameter Ġand Ġif Ġthe Ġagent Ġhas Ġnot Ġseen Ġa Ġhigher Ġscore Ġin Ġpatience Ġsteps , Ġthe Ġagent Ġassumes Ġit Ġhas Ġbeen Ġlimited Ġby Ġa Ġbottleneck . ĠSecond , Ġwhen Ġa Ġbottleneck Ġis Ġfound , Ġwe Ġfreeze Ġthe Ġpolicy Ġthat Ġgets Ġthe Ġagent Ġto Ġthe Ġstate Ġwith Ġthe Ġhighest Ġscore . ĠThe Ġagent Ġthen Ġbegins Ġtraining Ġa Ġnew Ġpolicy Ġfrom Ġthat Ġparticular Ġstate . </s> Simply Ġfreezing Ġthe Ġpolicy Ġthat Ġled Ġto Ġthe Ġbottleneck , Ġhowever , Ġcan Ġpotentially Ġresult Ġin Ġa Ġpolicy Ġone Ġthat Ġis Ġglobally Ġsub - opt imal . ĠWe Ġtherefore Ġemploy Ġa Ġback tracking Ġstrategy Ġthat Ġrest arts Ġexploration Ġfrom Ġeach Ġof Ġthe Ġ$ n $ Ġprevious Ġsteps âĢĶ search ing Ġfor Ġa Ġmore Ġoptimal Ġpolicy Ġthat Ġreaches Ġthat Ġbottleneck . ĠAt Ġeach Ġstep , Ġwe Ġkeep Ġtrack Ġof Ġa Ġbuffer Ġof Ġ$ n $ Ġstates Ġand Ġad missible Ġactions Ġthat Ġled Ġup Ġto Ġthat Ġlocally Ġoptimal Ġstate . ĠWe Ġforce Ġthe Ġagent Ġto Ġexplore Ġfrom Ġthis Ġstate Ġto Ġattempt Ġto Ġdrive Ġit Ġout Ġof Ġthe Ġlocal Ġoptim a . ĠIf Ġit Ġis Ġfurther Ġunable Ġto Ġfind Ġitself Ġout Ġof Ġthis Ġlocal Ġoptim a , Ġwe Ġrefresh Ġthe Ġtraining Ġprocess Ġagain , Ġbut Ġstarting Ġat Ġthe Ġstate Ġimmediately Ġbefore Ġthe Ġagent Ġreaches Ġthe Ġlocal Ġoptim a . ĠIf Ġthis Ġcontinues Ġto Ġfail , Ġwe Ġcontinue Ġto Ġiter ate Ġthrough Ġthis Ġbuffer Ġof Ġseen Ġstates Ġstates Ġup Ġto Ġthat Ġlocal Ġoptim a Ġuntil Ġwe Ġeither Ġfind Ġa Ġmore Ġoptimal Ġstate Ġor Ġwe Ġrun Ġout Ġof Ġstates Ġto Ġrefresh Ġfrom , Ġin Ġwhich Ġwe Ġterminate Ġthe Ġtraining Ġalgorithm . </s> K G - A 2 C - Explore ĠGo - Explore ĠB IB REF 9 Ġis Ġan Ġalgorithm Ġthat Ġis Ġdesigned Ġto Ġkeep Ġtrack Ġof Ġsub - opt imal Ġand Ġunder - expl ored Ġstates Ġin Ġorder Ġto Ġallow Ġthe Ġagent Ġto Ġexplore Ġupon Ġmore Ġoptimal Ġstates Ġthat Ġmay Ġbe Ġa Ġresult Ġof Ġsparse Ġrewards . ĠThe ĠGo - Explore Ġalgorithm Ġconsists Ġof Ġtwo Ġphases , Ġthe Ġfirst Ġto Ġcontinuously Ġexplore Ġuntil Ġa Ġset Ġof Ġpromising Ġstates Ġand Ġcorresponding Ġtraject ories Ġare Ġfound Ġon Ġthe Ġbasis Ġof Ġtotal Ġscore , Ġand Ġthe Ġsecond Ġto Ġrobust ify Ġthis Ġfound Ġpolicy Ġagainst Ġpotential Ġsto ch astic ity Ġin Ġthe Ġgame . ĠProm ising Ġstates Ġare Ġdefined Ġas Ġthose Ġstates Ġwhen Ġexplored Ġfrom Ġwill Ġlikely Ġresult Ġin Ġhigher Ġreward Ġtraject ories . ĠSince Ġthe Ġtext Ġgames Ġwe Ġare Ġdealing Ġwith Ġare Ġmostly Ġdeter ministic , Ġwith Ġthe Ġexception Ġof ĠZ ork Ġin Ġlater Ġstages , Ġwe Ġonly Ġfocus Ġon Ġusing ĠPhase Ġ1 Ġof Ġthe ĠGo - Explore Ġalgorithm Ġto Ġfind Ġan Ġoptimal Ġpolicy . ĠB IB REF 10 Ġlook Ġat Ġapplying ĠGo - Explore Ġto Ġtext - games Ġon Ġa Ġset Ġof Ġsimpler Ġgames Ġgenerated Ġusing Ġthe Ġgame Ġgeneration Ġframework ĠText World ĠB IB REF 1 . ĠInstead Ġof Ġtraining Ġa Ġpolicy Ġnetwork Ġin Ġparallel Ġto Ġgenerate Ġactions Ġused Ġfor Ġexploration , Ġthey Ġuse Ġa Ġsmall Ġset Ġof ĠâĢ ľ ad missible Ġactions âĢ Ŀ âĢĶ actions Ġguaranteed Ġto Ġchange Ġthe Ġworld Ġstate Ġat Ġany Ġgiven Ġstep Ġduring ĠPhase Ġ1 âĢĶ to Ġexplore Ġand Ġfind Ġhigh Ġreward Ġtraject ories . ĠThis Ġspace Ġof Ġactions Ġis Ġrelatively Ġsmall Ġ( of Ġthe Ġorder Ġof Ġ$ 10 ^ 2 $ Ġper Ġstep ) Ġand Ġso Ġfinding Ġhigh Ġreward Ġtraject ories Ġin Ġlarger Ġaction - sp aces Ġsuch Ġas Ġin ĠZ ork Ġwould Ġbe Ġinf eas ible </s> Go - Explore Ġmaintains Ġan Ġarchive Ġof Ġcells âĢĶ defined Ġas Ġa Ġset Ġof Ġstates Ġthat Ġmap Ġto Ġa Ġsingle Ġrepresentation âĢĶ to Ġkeep Ġtrack Ġof Ġpromising Ġstates . ĠB IB REF 9 Ġsimply Ġenc odes Ġeach Ġcell Ġby Ġkeeping Ġtrack Ġof Ġthe Ġagent 's Ġposition Ġand ĠB IB REF 10 Ġuse Ġthe Ġtextual Ġobservations Ġencoded Ġby Ġrecurrent Ġneural Ġnetwork Ġas Ġa Ġcell Ġrepresentation . ĠWe Ġimprove Ġon Ġthis Ġimplementation Ġby Ġtraining Ġthe ĠK G - A 2 C Ġnetwork Ġin Ġparallel , Ġusing Ġthe Ġsnapshot Ġof Ġthe Ġknowledge Ġgraph Ġin Ġconjunction Ġwith Ġthe Ġgame Ġstate Ġto Ġfurther Ġencode Ġthe Ġcurrent Ġstate Ġand Ġuse Ġthis Ġas Ġa Ġcell Ġrepresentation . ĠAt Ġeach Ġstep , ĠGo - Explore Ġchooses Ġa Ġcell Ġto Ġexplore Ġat Ġrandom Ġ( weight ed Ġby Ġscore Ġto Ġprefer Ġmore Ġadvanced Ġcells ). ĠThe ĠK G - A 2 C Ġwill Ġrun Ġfor Ġa Ġnumber Ġof Ġsteps , Ġstarting Ġwith Ġthe Ġknowledge Ġgraph Ġstate Ġand Ġthe Ġlast Ġseen Ġstate Ġof Ġthe Ġgame Ġfrom Ġthe Ġcell . ĠThis Ġwill Ġgenerate Ġa Ġtrajectory Ġfor Ġthe Ġagent Ġwhile Ġfurther Ġtraining Ġthe ĠK G - A 2 C Ġat Ġeach Ġiteration , Ġcreating Ġa Ġnew Ġrepresentation Ġfor Ġthe Ġknowledge Ġgraph Ġas Ġwell Ġas Ġa Ġnew Ġgame Ġstate Ġfor Ġthe Ġcell . ĠAfter Ġexpanding Ġa Ġcell , ĠGo - Explore Ġwill Ġcontinue Ġto Ġsample Ġcells Ġby Ġweight Ġto Ġcontinue Ġexpanding Ġits Ġknown Ġstates . ĠAt Ġthe Ġsame Ġtime , ĠK G - A 2 C Ġwill Ġbenefit Ġfrom Ġthe Ġhe ur istics Ġof Ġselecting Ġpreferred Ġcells Ġand Ġbe Ġtrained Ġon Ġpromising Ġstates Ġmore Ġoften . </s> E val uation </s> We Ġcompare Ġour Ġtwo Ġexploration Ġstrategies Ġto Ġthe Ġfollowing Ġbas elines Ġand Ġabl ations : </s> K G - A 2 C ĠThis Ġis Ġthe Ġexact Ġsame Ġmethod Ġpresented Ġin ĠB IB REF 6 Ġwith Ġno Ġmodifications . </s> A 2 C ĠRep resents Ġthe Ġsame Ġapproach Ġas ĠK G - A 2 C Ġbut Ġwith Ġall Ġthe Ġknowledge Ġgraph Ġcomponents Ġremoved . ĠThe Ġstate Ġrepresentation Ġis Ġtext Ġonly Ġencoded Ġusing Ġrecurrent Ġnetworks . </s> A 2 C - ch ained ĠIs Ġa Ġvariation Ġon ĠK G - A 2 C - ch ained Ġwhere Ġwe Ġuse Ġour Ġpolicy Ġch aining Ġapproach Ġwith Ġthe ĠA 2 C Ġmethod Ġto Ġtrain Ġthe Ġagent Ġinstead Ġof ĠK G - A 2 C . </s> A 2 C - Explore ĠUses ĠA 2 C Ġin Ġaddition Ġto Ġthe Ġexploration Ġstrategy Ġseen Ġin ĠK G - A 2 C - Explore . ĠThe Ġcell Ġrepresentations Ġhere Ġare Ġdefined Ġin Ġterms Ġof Ġthe Ġrecurrent Ġnetwork Ġbased Ġencoding Ġof Ġthe Ġtextual Ġobservation . </s> Figure ĠFIG REF 10 Ġshows Ġthat Ġagents Ġutilizing Ġknowledge - graph s Ġin Ġaddition Ġto Ġeither Ġenhanced Ġexploration Ġmethod Ġfar Ġoutper form Ġthe Ġbaseline ĠA 2 C Ġand ĠK G - A 2 C . ĠK G - A 2 C - ch ained Ġand ĠK G - A 2 C - Explore Ġboth Ġpass Ġthe Ġbottleneck Ġof Ġa Ġscore Ġof Ġ40 , Ġwhereas ĠA 2 C - Explore Ġgets Ġto Ġthe Ġbottleneck Ġbut Ġcannot Ġsurpass Ġit . </s> There Ġare Ġa Ġcouple Ġof Ġkey Ġinsights Ġthat Ġcan Ġbe Ġdrawn Ġfrom Ġthese Ġresults ĠThe Ġfirst Ġis Ġthat Ġthe Ġknowledge Ġgraph Ġappears Ġto Ġbe Ġcritical ; Ġit Ġis Ġtheor ized Ġto Ġhelp Ġwith Ġpartial Ġobserv ability . ĠHowever Ġthe Ġknowledge Ġgraph Ġrepresentation Ġisn 't Ġsufficient Ġin Ġthat Ġthe Ġknowledge Ġgraph Ġrepresentation Ġwithout Ġenhanced Ġexploration Ġmethods Ġcannot Ġsurpass Ġthe Ġbottleneck . ĠA 2 C - ch ained âĢĶ which Ġexplores Ġwithout Ġa Ġknowledge Ġgraph âĢĶ f ails Ġto Ġeven Ġoutper form Ġthe Ġbaseline ĠA 2 C . ĠWe Ġhypothes ize Ġthat Ġthis Ġis Ġdue Ġto Ġthe Ġknowledge Ġgraph Ġaiding Ġimplicitly Ġin Ġthe Ġsample Ġefficiency Ġof Ġbottleneck Ġdetection Ġand Ġsubsequent Ġexploration . ĠThat Ġis , Ġexploring Ġafter Ġback tracking Ġfrom Ġa Ġpotentially Ġdetected Ġbottleneck Ġis Ġmuch Ġmore Ġefficient Ġin Ġthe Ġknowledge Ġgraph Ġbased Ġagent . </s> The ĠGo - Explore Ġbased Ġexploration Ġalgorithm Ġsees Ġless Ġof Ġa Ġdifference Ġbetween Ġagents . ĠA 2 C - Explore Ġconver ges Ġmore Ġquickly , Ġbut Ġto Ġa Ġlower Ġreward Ġtrajectory Ġthat Ġfails Ġto Ġpass Ġthe Ġbottleneck , Ġwhereas ĠK G - A 2 C - Explore Ġtakes Ġlonger Ġto Ġreach Ġa Ġsimilar Ġreward Ġbut Ġconsistently Ġmakes Ġit Ġthrough Ġthe Ġbottleneck . ĠThe Ġknowledge Ġgraph Ġcell Ġrepresentation Ġappears Ġto Ġthus Ġbe Ġa Ġbetter Ġindication Ġof Ġwhat Ġa Ġpromising Ġstate Ġis Ġas Ġopposed Ġto Ġjust Ġthe Ġtextual Ġobservation . </s> Comp aring Ġthe Ġadvanced Ġexploration Ġmethods Ġwhen Ġusing Ġthe Ġknowledge Ġgraph , Ġwe Ġsee Ġthat Ġboth Ġagents Ġsuccessfully Ġpass Ġthe Ġbottleneck Ġcorresponding Ġto Ġentering Ġthe Ġcellar Ġand Ġlighting Ġthe Ġlamp Ġand Ġreach Ġcomparable Ġscores Ġwithin Ġa Ġmargin Ġof Ġerror . ĠK G - A 2 C - ch ained Ġis Ġsignificantly Ġmore Ġsample Ġefficient Ġand Ġconver ges Ġfaster . ĠWe Ġcan Ġinfer Ġthat Ġch aining Ġpolicies Ġby Ġexplicitly Ġdetecting Ġbott len ec ks Ġlets Ġus Ġpass Ġit Ġmore Ġquickly Ġthan Ġattempting Ġto Ġfind Ġpromising Ġcell Ġrepresentations Ġwith ĠGo - Explore . ĠThis Ġform Ġof Ġchained Ġexploration Ġwith Ġback tracking Ġis Ġparticularly Ġsuited Ġto Ġsequential Ġdecision Ġmaking Ġproblems Ġthat Ġcan Ġbe Ġrepresented Ġas Ġac y cl ic Ġdirected Ġgraphs Ġas Ġin ĠFigure ĠFIG REF 1 . </s> App endix Ġ: :: ĠZ ork 1 </s> Z ork 1 Ġis Ġone Ġof Ġthe Ġfirst Ġtext - ad venture Ġgames Ġand Ġheavily Ġinfluences Ġgames Ġreleased Ġlater Ġin Ġterms Ġof Ġnarrative Ġstyle Ġand Ġgame Ġstructure . ĠIt Ġis Ġa Ġdungeon Ġcraw ler Ġwhere Ġthe Ġplayer Ġmust Ġexplore Ġa Ġvast Ġworld Ġand Ġcollect Ġa Ġseries Ġof Ġtreasures . ĠIt Ġwas Ġidentified Ġby ĠB IB REF 2 Ġas Ġa Ġmoons hot Ġgame Ġand Ġhas Ġbeen Ġthe Ġsubject Ġof Ġmuch Ġwork Ġin Ġleaning Ġagents ĠB IB REF 12 , ĠB IB REF 7 , ĠB IB REF 11 , ĠB IB REF 8 . ĠRewards Ġare Ġgiven Ġto Ġthe Ġplayer Ġwhen Ġthey Ġcollect Ġtreasures Ġas Ġwell Ġas Ġwhen Ġimportant Ġintermediate Ġmilestones Ġneeded Ġto Ġfurther Ġexplore Ġthe Ġworld Ġare Ġpassed . ĠFigure ĠFIG REF 15 Ġand ĠFigure ĠFIG REF 1 Ġshow Ġus Ġa Ġmap Ġof Ġthe Ġworld Ġof ĠZ ork 1 Ġand Ġthe Ġcorresponding Ġquest Ġstructure . </s> The Ġbottleneck Ġseen Ġat Ġa Ġscore Ġof Ġaround Ġ40 Ġis Ġwhen Ġthe Ġplayer Ġfirst Ġenters Ġthe Ġcellar Ġon Ġthe Ġright Ġside Ġof Ġthe Ġmap . ĠThe Ġcellar Ġis Ġdark Ġand Ġyou Ġneed Ġto Ġimmediately Ġlight Ġthe Ġlamp Ġto Ġsee Ġanything . ĠAttempt ing Ġto Ġexplore Ġthe Ġcellar Ġin Ġthe Ġdark Ġresults Ġin Ġyou Ġbeing Ġinstantly Ġkilled Ġby Ġa Ġmonster Ġknown Ġas Ġa ĠâĢ ľ gr ue âĢ Ŀ . </s> App endix Ġ: :: ĠKnowledge ĠGraph ĠRules </s> We Ġmake Ġno Ġchanges Ġfrom Ġthe Ġgraph Ġupdate Ġrules Ġused Ġby ĠB IB REF 6 . ĠCandidate Ġinteractive Ġobjects Ġare Ġidentified Ġby Ġperforming Ġpart - of - speech Ġtagging Ġon Ġthe Ġcurrent Ġobservation , Ġidentifying Ġsingular Ġand Ġproper Ġnoun s Ġas Ġwell Ġas Ġadject ives , Ġand Ġare Ġthen Ġfiltered Ġby Ġchecking Ġif Ġthey Ġcan Ġbe Ġexamined Ġusing Ġthe Ġcommand Ġ$ ex amine $ Ġ$ OB J $. ĠOnly Ġthe Ġinteractive Ġobjects Ġnot Ġfound Ġin Ġthe Ġinventory Ġare Ġlinked Ġto Ġthe Ġnode Ġcorresponding Ġto Ġthe Ġcurrent Ġroom Ġand Ġthe Ġinventory Ġitems Ġare Ġlinked Ġto Ġthe ĠâĢ ľ you âĢ Ŀ Ġnode . ĠThe Ġonly Ġother Ġrule Ġapplied Ġuses Ġthe Ġnavig ational Ġactions Ġperformed Ġby Ġthe Ġagent Ġto Ġinfer Ġthe Ġrelative Ġpositions Ġof Ġrooms , Ġe . g . Ġ$\ l angle Ġkitchen , down , cell ar Ġ\ r angle Ġ$ Ġwhen Ġthe Ġagent Ġperforms Ġ$ go $ Ġ$ down $ Ġwhen Ġin Ġthe Ġkitchen Ġto Ġmove Ġto Ġthe Ġcellar . </s> App endix Ġ: :: ĠHyper param eters </s> Hyper param eters Ġused Ġfor Ġour Ġagents Ġare Ġgiven Ġbelow . ĠPat ience Ġand Ġbuffer Ġsize Ġare Ġused Ġfor Ġthe Ġpolicy Ġch aining Ġmethod Ġas Ġdescribed Ġin ĠSection ĠSEC REF 2 . ĠCell Ġstep Ġsize Ġis Ġa Ġparameter Ġused Ġfor ĠGo - Explore Ġand Ġdescribes Ġhow Ġmany Ġsteps Ġare Ġtaken Ġwhen Ġexploring Ġin Ġa Ġgiven Ġcell Ġstate . ĠBase Ġhyper param eters Ġfor ĠK G - A 2 C Ġare Ġtaken Ġfrom ĠB IB REF 6 Ġand Ġthe Ġsame Ġparameters Ġare Ġused Ġfor ĠA 2 C .