 On the other hand, phase 1 of Go-Explore finds an optimal trajectory with approximately half the interactions with the environment, Moreover, the trajectory length found by Go-Explore is always optimal (i.e. 30 steps) whereas both DQN++ and DRQN++ have an average length of 38 and 42 respectively., Especially interesting is that the performance of DRRN is substantially lower than that of the Go-Explore Seq2Seq model
EXTRACTIVE
On Coin Collector, proposed model finds shorter path in fewer number of interactions with enironment.
On Cooking World, proposed model uses smallest amount of steps and on average has bigger score and number of wins by significant margin.
ABSTRACTIVE
Results ::: CoinCollector In this setting, we compare the number of actions played in the environment (frames) and the score achieved by the agent (i.e. +1 reward if the coin is collected). In Go-Explore we also count the actions used to restore the environment to a selected cell, i.e. to bring the agent to the state represented in the selected cell. This allows a one-to-one comparison of the exploration efficiency between Go-Explore and algorithms that use a count-based reward in text-based games. Importantly, BIBREF8 showed that DQN and DRQN, without such counting rewards, could never find a successful trajectory in hard games such as the ones used in our experiments. Figure FIGREF17 shows the number of interactions with the environment (frames) versus the maximum score obtained, averaged over 10 games of the same difficulty. As shown by BIBREF8, DRQN++ finds a trajectory with the maximum score faster than to DQN++. On the other hand, phase 1 of Go-Explore finds an optimal trajectory with approximately half the interactions with the environment. Moreover, the trajectory length found by Go-Explore is always optimal (i.e. 30 steps) whereas both DQN++ and DRQN++ have an average length of 38 and 42 respectively. In CookingWorld, we compared models in the three settings mentioned earlier, namely, single, joint, and zero-shot. In all experiments, we measured the sum of the final scores of all the games and their trajectory length (number of steps). Table TABREF26 summarizes the results in these three settings. Phase 1 of Go-Explore on single games achieves a total score of 19,530 (sum over all games), which is very close to the maximum possible points (i.e. 19,882), with 47,562 steps. A winning trajectory was found in 4,279 out of the total of 4,440 games. This result confirms again that the exploration strategy of Go-Explore is effective in text-based games. Next, we evaluate the effectiveness and the generalization ability of the simple imitation learning policy trained using the extracted trajectories in phase 1 of Go-Explore in the three settings mentioned above. In this setting, each model is trained from scratch in each of the 4,440 games based on the trajectory found in phase 1 of Go-Explore (previous step). As shown in Table TABREF26, the LSTM-DQN BIBREF7, BIBREF8 approach without the use of admissible actions performs poorly. One explanation for this could be that it is difficult for this model to explore both language and game strategy at the same time; it is hard for the model to find a reward signal before it has learned to model language, since almost none of its actions will be admissible, and those reward signals are what is necessary in order to learn the language model. As we see in Table TABREF26, however, by using the admissible actions in the $\epsilon $-greedy step the score achieved by the LSTM-DQN increases dramatically (+ADM row in Table TABREF26). DRRN BIBREF10 achieves a very high score, since it explicitly learns how to rank admissible actions (i.e. a much simpler task than generating text). Finally, our approach of using a Seq2Seq model trained on the single trajectory provided by phase 1 of Go-Explore achieves the highest score among all the methods, even though we do not use admissible actions in this phase. However, in this experiment the Seq2Seq model cannot perfectly replicate the provided trajectory and the total score that it achieves is in fact 9.4% lower compared to the total score achieved by phase 1 of Go-Explore. Figure FIGREF61 (in Appendix SECREF60) shows the score breakdown for each level and model, where we can see that the gap between our model and other methods increases as the games become harder in terms of skills needed. In this setting the 4,440 games are split into training, validation, and test games. The split is done randomly but in a way that different difficulty levels (recipes 1, 2 and 3), are represented with equal ratios in all the 3 splits, i.e. stratified by difficulty. As shown in Table TABREF26, the zero-shot performance of the RL baselines is poor, which could be attributed to the same reasons why RL baselines under-perform in the Joint case. Especially interesting is that the performance of DRRN is substantially lower than that of the Go-Explore Seq2Seq model, even though the DRRN model has access to the admissible actions at test time, while the Seq2Seq model (as well as the LSTM-DQN model) has to construct actions token-by-token from the entire vocabulary of 20,000 tokens. On the other hand, Go-Explore Seq2Seq shows promising results by solving almost half of the unseen games. Figure FIGREF62 (in Appendix SECREF60) shows that most of the lost games are in the hardest set, where a very long sequence of actions is required for winning the game. These results demonstrate both the relative effectiveness of training a Seq2Seq model on Go-Explore trajectories, but they also indicate that additional effort needed for designing reinforcement learning algorithms that effectively generalize to unseen games.
In this setting, we compare the number of actions played in the environment (frames) and the score achieved by the agent (i.e. +1 reward if the coin is collected). In Go-Explore we also count the actions used to restore the environment to a selected cell, i.e. to bring the agent to the state represented in the selected cell. This allows a one-to-one comparison of the exploration efficiency between Go-Explore and algorithms that use a count-based reward in text-based games. Importantly, BIBREF8 showed that DQN and DRQN, without such counting rewards, could never find a successful trajectory in hard games such as the ones used in our experiments. Figure FIGREF17 shows the number of interactions with the environment (frames) versus the maximum score obtained, averaged over 10 games of the same difficulty. As shown by BIBREF8, DRQN++ finds a trajectory with the maximum score faster than to DQN++. On the other hand, phase 1 of Go-Explore finds an optimal trajectory with approximately half the interactions with the environment. Moreover, the trajectory length found by Go-Explore is always optimal (i.e. 30 steps) whereas both DQN++ and DRQN++ have an average length of 38 and 42 respectively. FLOAT SELECTED: Table 3: CookingWorld results on the three evaluated settings single, joint and zero-shot.
2001.08868
Introduction </s> Text - based Ġgames Ġbecame Ġpopular Ġin Ġthe Ġmid Ġ80 s Ġwith Ġthe Ġgame Ġseries ĠZ ork ĠB IB REF 1 Ġresulting Ġin Ġmany Ġdifferent Ġtext - based Ġgames Ġbeing Ġproduced Ġand Ġpublished ĠB IB REF 2 . ĠThese Ġgames Ġuse Ġa Ġplain Ġtext Ġdescription Ġof Ġthe Ġenvironment Ġand Ġthe Ġplayer Ġhas Ġto Ġinteract Ġwith Ġthem Ġby Ġwriting Ġnatural - language Ġcommands . ĠRecently , Ġthere Ġhas Ġbeen Ġa Ġgrowing Ġinterest Ġin Ġdeveloping Ġagents Ġthat Ġcan Ġautomatically Ġsolve Ġtext - based Ġgames ĠB IB REF 3 Ġby Ġinteracting Ġwith Ġthem . ĠThese Ġsettings Ġchallenge Ġthe Ġability Ġof Ġan Ġartificial Ġagent Ġto Ġunderstand Ġnatural Ġlanguage , Ġcommon Ġsense Ġknowledge , Ġand Ġto Ġdevelop Ġthe Ġability Ġto Ġinteract Ġwith Ġenvironments Ġusing Ġlanguage ĠB IB REF 4 , ĠB IB REF 5 . </s> Since Ġthe Ġactions Ġin Ġthese Ġgames Ġare Ġcommands Ġthat Ġare Ġin Ġnatural Ġlanguage Ġform , Ġthe Ġmajor Ġobstacle Ġis Ġthe Ġextremely Ġlarge Ġaction Ġspace Ġof Ġthe Ġagent , Ġwhich Ġleads Ġto Ġa Ġcomb inator ially Ġlarge Ġexploration Ġproblem . ĠIn Ġfact , Ġwith Ġa Ġvocabulary Ġof Ġ$ N $ Ġwords Ġ( e . g . Ġ20 K ) Ġand Ġthe Ġpossibility Ġof Ġproducing Ġsentences Ġwith Ġat Ġmost Ġ$ m $ Ġwords Ġ( e . g . Ġ7 Ġwords ), Ġthe Ġtotal Ġnumber Ġof Ġactions Ġis Ġ$ O ( N ^ m ) $ Ġ( e . g . Ġ20 K $ ^ 7 Ġ\ app rox Ġ1 . 28 Ġe ^{ 30 } $ ). ĠTo Ġavoid Ġthis Ġlarge Ġaction Ġspace , Ġseveral Ġexisting Ġsolutions Ġfocus Ġon Ġsimpler Ġtext - based Ġgames Ġwith Ġvery Ġsmall Ġvoc ab ular ies Ġwhere Ġthe Ġaction Ġspace Ġis Ġconstrained Ġto Ġverb - object Ġpairs ĠB IB REF 6 , ĠB IB REF 7 , ĠB IB REF 8 , ĠB IB REF 9 . ĠMoreover , Ġmany Ġexisting Ġworks Ġrely Ġon Ġusing Ġpredetermined Ġsets Ġof Ġad missible Ġactions ĠB IB REF 10 , ĠB IB REF 11 , ĠB IB REF 12 . ĠHowever , Ġa Ġmore Ġideal , Ġand Ġstill Ġunder Ġexplored , Ġalternative Ġwould Ġbe Ġan Ġagent Ġthat Ġcan Ġoperate Ġin Ġthe Ġfull , Ġuncon str ained Ġaction Ġspace Ġof Ġnatural Ġlanguage Ġthat Ġcan Ġsystematically Ġgeneral ize Ġto Ġnew Ġtext - based Ġgames Ġwith Ġno Ġor Ġfew Ġinteractions Ġwith Ġthe Ġenvironment . </s> To Ġaddress Ġthis Ġchallenge , Ġwe Ġpropose Ġto Ġuse Ġthe Ġidea Ġbehind Ġthe Ġrecently Ġproposed ĠGo - Explore ĠB IB REF 0 Ġalgorithm . ĠSpecifically , Ġwe Ġpropose Ġto Ġfirst Ġextract Ġhigh Ġreward Ġtraject ories Ġof Ġstates Ġand Ġactions Ġin Ġthe Ġgame Ġusing Ġthe Ġexploration Ġmethodology Ġproposed Ġin ĠGo - Explore Ġand Ġthen Ġtrain Ġa Ġpolicy Ġusing Ġa ĠSe q 2 Se q ĠB IB REF 13 Ġmodel Ġthat Ġmaps Ġobservations Ġto Ġactions , Ġin Ġan Ġimitation Ġlearning Ġfashion . ĠTo Ġshow Ġthe Ġeffectiveness Ġof Ġour Ġproposed Ġmethodology , Ġwe Ġfirst Ġbenchmark Ġthe Ġexploration Ġability Ġof ĠGo - Explore Ġon Ġthe Ġfamily Ġof Ġtext - based Ġgames Ġcalled ĠCoin Collect or ĠB IB REF 8 . ĠThen Ġwe Ġuse Ġthe Ġ4 , 440 Ġgames Ġof ĠâĢ ľ First ĠText World ĠProblems âĢ Ŀ ĠB IB REF 14 , Ġwhich Ġare Ġgenerated Ġusing Ġthe Ġmachinery Ġintroduced Ġby ĠB IB REF 3 , Ġto Ġshow Ġthe Ġgeneral ization Ġability Ġof Ġour Ġproposed Ġmethodology . ĠIn Ġthe Ġformer Ġexperiment Ġwe Ġshow Ġthat ĠGo - Explore Ġfinds Ġwinning Ġtraject ories Ġfaster Ġthan Ġexisting Ġsolutions , Ġand Ġin Ġthe Ġlatter , Ġwe Ġshow Ġthat Ġtraining Ġa ĠSe q 2 Se q Ġmodel Ġon Ġthe Ġtraject ories Ġfound Ġby ĠGo - Explore Ġresults Ġin Ġstronger Ġgeneral ization , Ġas Ġsuggested Ġby Ġthe Ġstronger Ġperformance Ġon Ġunseen Ġgames , Ġcompared Ġto Ġexisting Ġcompetitive Ġbas elines ĠB IB REF 10 , ĠB IB REF 7 . </s> Introduction Ġ: :: ĠRein forcement ĠLearning ĠBased ĠAppro aches Ġfor ĠText - Based ĠGames </s> Among Ġreinforcement Ġlearning Ġbased Ġefforts Ġto Ġsolve Ġtext - based Ġgames Ġtwo Ġapproaches Ġare Ġprominent . ĠThe Ġfirst Ġapproach Ġassumes Ġan Ġaction Ġas Ġa Ġsentence Ġof Ġa Ġfixed Ġnumber Ġof Ġwords , Ġand Ġassociates Ġa Ġseparate Ġ$ Q $ - function ĠB IB REF 15 , ĠB IB REF 16 Ġwith Ġeach Ġword Ġposition Ġin Ġthis Ġsentence . ĠThis Ġmethod Ġwas Ġdemonstrated Ġwith Ġtwo - word Ġsentences Ġconsisting Ġof Ġa Ġverb - object Ġpair Ġ( e . g . Ġtake Ġapple ) ĠB IB REF 6 , ĠB IB REF 7 , ĠB IB REF 8 , ĠB IB REF 9 , ĠB IB REF 17 . ĠIn Ġthe Ġsecond Ġapproach , Ġone Ġ$ Q $ - function Ġthat Ġscores Ġall Ġpossible Ġactions Ġ( i . e . Ġsentences ) Ġis Ġlearned Ġand Ġused Ġto Ġplay Ġthe Ġgame ĠB IB REF 10 , ĠB IB REF 11 , ĠB IB REF 12 . ĠThe Ġfirst Ġapproach Ġis Ġquite Ġlimiting Ġsince Ġa Ġfixed Ġnumber Ġof Ġwords Ġmust Ġbe Ġselected Ġin Ġadvance Ġand Ġno Ġtemporal Ġdependency Ġis Ġenforced Ġbetween Ġwords Ġ( e . g . Ġlack Ġof Ġlanguage Ġmodelling ). ĠIn Ġthe Ġsecond Ġapproach , Ġon Ġthe Ġother Ġhand , Ġthe Ġnumber Ġof Ġpossible Ġactions Ġcan Ġbecome Ġexponentially Ġlarge Ġif Ġthe Ġad missible Ġactions Ġ( a Ġpredetermined Ġlow Ġcardinal ity Ġset Ġof Ġactions Ġthat Ġthe Ġagent Ġcan Ġtake ) Ġare Ġnot Ġprovided Ġto Ġthe Ġagent . ĠA Ġpossible Ġsolution Ġto Ġthis Ġissue Ġhas Ġbeen Ġproposed Ġby ĠB IB REF 18 , Ġwhere Ġa Ġhierarchical Ġpointer - gener ator Ġis Ġused Ġto Ġfirst Ġproduce Ġthe Ġset Ġof Ġad missible Ġactions Ġgiven Ġthe Ġobservation , Ġand Ġsubsequently Ġone Ġelement Ġof Ġthis Ġset Ġis Ġchosen Ġas Ġthe Ġaction Ġfor Ġthat Ġobservation . ĠHowever , Ġin Ġour Ġexperiments Ġwe Ġshow Ġthat Ġeven Ġin Ġsettings Ġwhere Ġthe Ġtrue Ġset Ġof Ġad missible Ġactions Ġis Ġprovided Ġby Ġthe Ġenvironment , Ġa Ġ$ Q $ - sc orer ĠB IB REF 10 Ġdoes Ġnot Ġgeneral ize Ġwell Ġin Ġour Ġsetting Ġ( Section Ġ5 . 2 ĠZero - Shot ) Ġand Ġwe Ġwould Ġexpect Ġperformance Ġto Ġdegrade Ġeven Ġfurther Ġif Ġthe Ġad missible Ġactions Ġwere Ġgenerated Ġby Ġa Ġseparate Ġmodel . ĠLess Ġcommon Ġare Ġmodels Ġthat Ġeither Ġlearn Ġto Ġreduce Ġa Ġlarge Ġset Ġof Ġactions Ġinto Ġa Ġsmaller Ġset Ġof Ġad missible Ġactions Ġby Ġeliminating Ġactions ĠB IB REF 12 Ġor Ġby Ġcomp ressing Ġthem Ġin Ġa Ġlatent Ġspace ĠB IB REF 11 . </s> Introduction Ġ: :: ĠExploration Ġin ĠRein forcement ĠLearning </s> In Ġmost Ġtext - based Ġgames Ġrewards Ġare Ġsparse , Ġsince Ġthe Ġsize Ġof Ġthe Ġaction Ġspace Ġmakes Ġthe Ġprobability Ġof Ġobserving Ġa Ġreward Ġextremely Ġlow Ġwhen Ġtaking Ġonly Ġrandom Ġactions . ĠSp arse Ġreward Ġenvironments Ġare Ġparticularly Ġchallenging Ġfor Ġreinforcement Ġlearning Ġas Ġthey Ġrequire Ġlonger Ġterm Ġplanning . ĠMany Ġexploration Ġbased Ġsolutions Ġhave Ġbeen Ġproposed Ġto Ġaddress Ġthe Ġchallenges Ġassociated Ġwith Ġreward Ġsp arsity . ĠAmong Ġthese Ġexploration Ġapproaches Ġare Ġnovelty Ġsearch ĠB IB REF 19 , ĠB IB REF 20 , ĠB IB REF 21 , ĠB IB REF 22 , ĠB IB REF 23 , Ġintrinsic Ġmotivation ĠB IB REF 24 , ĠB IB REF 25 , ĠB IB REF 26 , Ġand Ġcuriosity Ġbased Ġrewards ĠB IB REF 27 , ĠB IB REF 28 , ĠB IB REF 29 . ĠFor Ġtext Ġbased Ġgames Ġexploration Ġmethods Ġhave Ġbeen Ġstudied Ġby ĠB IB REF 8 , Ġwhere Ġthe Ġauthors Ġshowed Ġthe Ġeffectiveness Ġof Ġthe Ġepis odic Ġdiscovery Ġbonus ĠB IB REF 30 Ġin Ġenvironments Ġwith Ġsparse Ġrewards . ĠThis Ġexploration Ġmethod Ġcan Ġonly Ġbe Ġapplied Ġin Ġgames Ġwith Ġvery Ġsmall Ġaction Ġand Ġstate Ġspaces , Ġsince Ġtheir Ġcounting Ġmethods Ġrely Ġon Ġthe Ġstate Ġin Ġits Ġexplicit Ġraw Ġform . </s> Method ology </s> Go - Explore ĠB IB REF 0 Ġdiffers Ġfrom Ġthe Ġexploration - based Ġalgorithms Ġdiscussed Ġabove Ġin Ġthat Ġit Ġexplicitly Ġkeeps Ġtrack Ġof Ġunder - expl ored Ġareas Ġof Ġthe Ġstate Ġspace Ġand Ġin Ġthat Ġit Ġutilizes Ġthe Ġdetermin ism Ġof Ġthe Ġsimulator Ġin Ġorder Ġto Ġreturn Ġto Ġthose Ġstates , Ġallowing Ġit Ġto Ġexplore Ġsparse - re ward Ġenvironments Ġin Ġa Ġsample Ġefficient Ġway Ġ( see ĠB IB REF 0 Ġas Ġwell Ġas Ġsection ĠSEC REF 27 ). ĠFor Ġthe Ġexperiments Ġin Ġthis Ġpaper Ġwe Ġmainly Ġfocus Ġon Ġthe Ġfinal Ġperformance Ġof Ġour Ġpolicy , Ġnot Ġhow Ġthat Ġpolicy Ġis Ġtrained , Ġthus Ġmaking ĠGo - Explore Ġa Ġsuitable Ġalgorithm Ġfor Ġour Ġexperiments . ĠGo - Explore Ġis Ġcomposed Ġof Ġtwo Ġphases . ĠIn Ġphase Ġ1 Ġ( also Ġreferred Ġto Ġas Ġthe ĠâĢ ľ expl oration âĢ Ŀ Ġphase ) Ġthe Ġalgorithm Ġexplores Ġthe Ġstate Ġspace Ġthrough Ġkeeping Ġtrack Ġof Ġpreviously Ġvisited Ġstates Ġby Ġmaintaining Ġan Ġarchive . ĠDuring Ġthis Ġphase , Ġinstead Ġof Ġres uming Ġthe Ġexploration Ġfrom Ġscratch , Ġthe Ġalgorithm Ġstarts Ġexploring Ġfrom Ġpromising Ġstates Ġin Ġthe Ġarchive Ġto Ġfind Ġhigh Ġperforming Ġtraject ories . ĠIn Ġphase Ġ2 Ġ( also Ġreferred Ġto Ġas Ġthe ĠâĢ ľ rob ust ification âĢ Ŀ Ġphase , Ġwhile Ġin Ġour Ġvariant Ġwe Ġwill Ġcall Ġit ĠâĢ ľ general ization âĢ Ŀ ) Ġthe Ġalgorithm Ġtrains Ġa Ġpolicy Ġusing Ġthe Ġtraject ories Ġfound Ġin Ġphase Ġ1 . ĠFollowing Ġthis Ġframework , Ġwhich Ġis Ġalso Ġshown Ġin ĠFigure ĠFIG REF 56 Ġ( App endix ĠA . 2 ), Ġwe Ġdefine Ġthe ĠGo - Explore Ġphases Ġfor Ġtext - based Ġgames . </s> Let Ġus Ġfirst Ġdefine Ġtext - based Ġgames Ġusing Ġthe Ġsame Ġnotation Ġas ĠB IB REF 8 . ĠA Ġtext - based Ġgame Ġcan Ġbe Ġframed Ġas Ġa Ġdiscrete - time ĠPart ially ĠObserv able ĠMark ov ĠDecision ĠProcess Ġ( P OM DP ) ĠB IB REF 31 Ġdefined Ġby Ġ$( S , ĠT , ĠA , Ġ\ O mega Ġ, ĠO , ĠR ) $, Ġwhere : Ġ$ S $ Ġis Ġthe Ġset Ġof Ġthe Ġenvironment Ġstates , Ġ$ T $ Ġis Ġthe Ġstate Ġtransition Ġfunction Ġthat Ġdefines Ġthe Ġnext Ġstate Ġprobability , Ġi . e . Ġ$ T ( s _{ t + 1 } | a _ t ; s _ t ) Ġ\ for all Ġs _ t \ in ĠS $, Ġ$ A $ Ġis Ġthe Ġset Ġof Ġactions , Ġwhich Ġin Ġour Ġcase Ġis Ġall Ġthe Ġpossible Ġsequences Ġof Ġtokens , Ġ$\ O mega Ġ$ Ġis Ġthe Ġset Ġof Ġobservations , Ġi . e . Ġtext Ġobserved Ġby Ġthe Ġagent Ġevery Ġtime Ġhas Ġit Ġto Ġtake Ġan Ġaction Ġin Ġthe Ġgame Ġ( i . e . Ġdialogue Ġturn ) Ġwhich Ġis Ġcontrolled Ġby Ġthe Ġconditional Ġobservation Ġprobability Ġ$ O $, Ġi . e . Ġ$ O ( o _ t | s _ t , Ġa _{ t - 1 }) $, Ġand , Ġfinally , Ġ$ R $ Ġis Ġthe Ġreward Ġfunction Ġi . e . Ġ$ r = R ( s , a ) $. </s> Let Ġus Ġalso Ġdefine Ġthe Ġobservation Ġ$ o _ t Ġ\ in Ġ\ O mega Ġ$ Ġand Ġthe Ġaction Ġ$ a _ t Ġ\ in ĠA $. ĠText - based Ġgames Ġprovide Ġsome Ġinformation Ġin Ġplain Ġtext Ġat Ġeach Ġturn Ġand , Ġwithout Ġloss Ġof Ġgener ality , Ġwe Ġdefine Ġan Ġobservation Ġ$ o _ t $ Ġas Ġthe Ġsequence Ġof Ġtokens Ġ$\ l brace Ġo _ t ^ 0 , \ cd ots Ġ, o _ t ^ n \ r brace Ġ$ Ġthat Ġform Ġthat Ġtext . ĠSimilarly , Ġwe Ġdefine Ġthe Ġtokens Ġof Ġan Ġaction Ġ$ a _ t $ Ġas Ġthe Ġsequence Ġ$\ l brace Ġa _ t ^ 0 , \ cd ots Ġ, a _ t ^ m \ r brace Ġ$ . ĠFurthermore , Ġwe Ġdefine Ġthe Ġset Ġof Ġad missible Ġactions Ġ$\ math cal Ġ{ A } _ t Ġ\ in ĠA $ Ġas Ġ$\ math cal Ġ{ A } _ t = \ l brace Ġa _ 0 , \ cd ots Ġ, a _ z \ r brace Ġ$ , Ġwhere Ġeach Ġ$ a _ i $, Ġwhich Ġis Ġa Ġsequence Ġof Ġtokens , Ġis Ġgram matically Ġcorrect Ġand Ġad missible Ġwith Ġreference Ġto Ġthe Ġobservation Ġ$ o _ t $. </s> Method ology Ġ: :: ĠPhase Ġ1 : ĠExploration </s> In Ġphase Ġ1 , ĠGo - Explore Ġbuilds Ġan Ġarchive Ġof Ġcells , Ġwhere Ġa Ġcell Ġis Ġdefined Ġas Ġa Ġset Ġof Ġobservations Ġthat Ġare Ġmapped Ġto Ġthe Ġsame , Ġdiscrete Ġrepresentation Ġby Ġsome Ġmapping Ġfunction Ġ$ f ( x ) $. ĠEach Ġcell Ġis Ġassociated Ġwith Ġmeta - data Ġincluding Ġthe Ġtrajectory Ġtowards Ġthat Ġcell , Ġthe Ġlength Ġof Ġthat Ġtrajectory , Ġand Ġthe Ġcumulative Ġreward Ġof Ġthat Ġtrajectory . ĠNew Ġcells Ġare Ġadded Ġto Ġthe Ġarchive Ġwhen Ġthey Ġare Ġencountered Ġin Ġthe Ġenvironment , Ġand Ġexisting Ġcells Ġare Ġupdated Ġwith Ġnew Ġmeta - data Ġwhen Ġthe Ġtrajectory Ġtowards Ġthat Ġcells Ġis Ġhigher Ġscoring Ġor Ġequal Ġscoring Ġbut Ġshorter . </s> At Ġeach Ġiteration Ġthe Ġalgorithm Ġselects Ġa Ġcell Ġfrom Ġthis Ġarchive Ġbased Ġon Ġmeta - data Ġof Ġthe Ġcell Ġ( e . g . Ġthe Ġaccumulated Ġreward , Ġetc .) Ġand Ġstarts Ġto Ġrandomly Ġexplore Ġfrom Ġthe Ġend Ġof Ġthe Ġtrajectory Ġassociated Ġwith Ġthe Ġselected Ġcell . ĠPhase Ġ1 Ġrequires Ġthree Ġcomponents : Ġthe Ġway Ġthat Ġobservations Ġare Ġembedded Ġinto Ġcell Ġrepresentations , Ġthe Ġcell Ġselection , Ġand Ġthe Ġway Ġactions Ġare Ġrandomly Ġselected Ġwhen Ġexploring Ġfrom Ġa Ġselected Ġcell . ĠIn Ġour Ġvariant Ġof Ġthe Ġalgorithm , Ġ$ f ( x ) $ Ġis Ġdefined Ġas Ġfollows : Ġgiven Ġan Ġobservation , Ġwe Ġcompute Ġthe Ġword Ġembed ding Ġfor Ġeach Ġtoken Ġin Ġthis Ġobservation , Ġsum Ġthese Ġembed d ings , Ġand Ġthen Ġconc aten ate Ġthis Ġsum Ġwith Ġthe Ġcurrent Ġcumulative Ġreward Ġto Ġconstruct Ġthe Ġcell Ġrepresentation . ĠThe Ġresulting Ġvectors Ġare Ġsubsequently Ġcompressed Ġand Ġdisc ret ized Ġby Ġbin ning Ġthem Ġin Ġorder Ġto Ġmap Ġsimilar Ġobservations Ġto Ġthe Ġsame Ġcell . ĠThis Ġway , Ġthe Ġcell Ġrepresentation , Ġwhich Ġis Ġthe Ġkey Ġof Ġthe Ġarchive , Ġincorporates Ġinformation Ġabout Ġthe Ġcurrent Ġobservation Ġof Ġthe Ġgame . ĠAdding Ġthe Ġcurrent Ġcumulative Ġreward Ġto Ġthe Ġcell Ġrepresentation Ġis Ġnew Ġto Ġour ĠGo - Explore Ġvariant Ġas Ġin Ġthe Ġoriginal Ġalgorithm Ġonly Ġdown - sc aled Ġimage Ġpixels Ġwere Ġused . ĠIt Ġturned Ġout Ġto Ġbe Ġa Ġvery Ġvery Ġeffective Ġto Ġincrease Ġthe Ġspeed Ġat Ġwhich Ġhigh Ġreward Ġtraject ories Ġare Ġdiscovered . ĠIn Ġphase Ġ1 , Ġwe Ġrestrict Ġthe Ġaction Ġspace Ġto Ġthe Ġset Ġof Ġad missible Ġactions Ġ$\ math cal Ġ{ A } _ t $ Ġthat Ġare Ġprovided Ġby Ġthe Ġgame Ġat Ġevery Ġstep Ġof Ġthe Ġgame Ġ. ĠThis Ġtoo Ġis Ġparticularly Ġimportant Ġfor Ġthe Ġrandom Ġsearch Ġto Ġfind Ġa Ġhigh Ġreward Ġtrajectory Ġfaster . ĠFinally , Ġwe Ġdenote Ġthe Ġtrajectory Ġfound Ġin Ġphase Ġ1 Ġfor Ġgame Ġ$ g $ Ġas Ġ$\ math cal Ġ{ T } _ g = Ġ[( o _ 0 , Ġa _ 0 , Ġr _ 0 ), Ġ\ cd ots Ġ, Ġ( o _ t , a _ t , r _ t )] $. </s> Method ology Ġ: :: ĠPhase Ġ2 : ĠGeneral ization </s> Phase Ġ2 Ġof ĠGo - Explore Ġuses Ġthe Ġtraject ories Ġfound Ġin Ġphase Ġ1 Ġand Ġtrains Ġa Ġpolicy Ġbased Ġon Ġthose Ġtraject ories . ĠThe Ġgoal Ġof Ġthis Ġphase Ġin Ġthe Ġoriginal ĠGo - Explore Ġalgorithm Ġis Ġto Ġturn Ġthe Ġfragile Ġpolicy Ġof Ġplaying Ġa Ġtrajectory Ġof Ġactions Ġin Ġsequence Ġinto Ġa Ġmore Ġrobust , Ġstate - condition ed Ġpolicy Ġthat Ġcan Ġthus Ġdeal Ġwith Ġenvironmental Ġsto ch astic ity . ĠIn Ġour Ġvariant Ġof Ġthe Ġalgorithm Ġthe Ġpurpose Ġof Ġthe Ġsecond Ġphase Ġis Ġgeneral ization : Ġalthough Ġin Ġour Ġenvironment Ġthere Ġis Ġno Ġsto ch astic ity , Ġour Ġgoal Ġis Ġto Ġlearn Ġa Ġgeneral Ġpolicy Ġthat Ġcan Ġbe Ġapplied Ġacross Ġdifferent Ġgames Ġand Ġgeneral ize Ġto Ġunseen Ġgames . ĠIn Ġthe Ġoriginal ĠGo - Explore Ġimplementation , Ġthe Ġauthors Ġused Ġthe Ġbackward ĠPro x imal ĠPolicy ĠOptim ization Ġalgorithm Ġ( PP O ) ĠB IB REF 32 , ĠB IB REF 33 Ġto Ġtrain Ġthis Ġpolicy . ĠIn Ġthis Ġwork Ġwe Ġopt Ġfor Ġa Ġsimple Ġbut Ġeffective ĠSe q 2 Se q Ġimitation Ġlearning Ġapproach Ġthat Ġdoes Ġnot Ġuse Ġthe Ġreward Ġdirectly Ġin Ġthe Ġloss . ĠMore Ġspecifically , Ġgiven Ġthe Ġtrajectory Ġ$\ math cal Ġ{ T } _ g $, Ġwe Ġtrain Ġa ĠSe q 2 Se q Ġmodel Ġto Ġminimize Ġthe Ġnegative Ġlog - like lihood Ġof Ġthe Ġaction Ġ$ a _ t $ Ġgiven Ġthe Ġobservation Ġ$ o _ t $. ĠIn Ġother Ġwords , Ġconsider Ġa Ġword Ġembed ding Ġmatrix Ġ$ E Ġ\ in Ġ\ math bb Ġ{ R } ^{ d Ġ\ times Ġ| V | } $ Ġwhere Ġ$ d $ Ġis Ġthe Ġembed ding Ġsize Ġand Ġ$ | V | $ Ġis Ġthe Ġcardinal ity Ġof Ġthe Ġvocabulary , Ġwhich Ġmaps Ġthe Ġinput Ġtoken Ġto Ġan Ġembedded Ġvector . ĠThen , Ġwe Ġdefine Ġan Ġenc oder ĠL ST M $ _{ enc } $ Ġand Ġa Ġdec oder ĠL ST M $ _{ dec } $. ĠEvery Ġtoken Ġ$ o _ t $ Ġfrom Ġthe Ġtrajectory Ġ$\ math cal Ġ{ T } _ g $ Ġis Ġconverted Ġto Ġits Ġembedded Ġrepresentation Ġusing Ġthe Ġembed ding Ġmatrix Ġ$ E $ Ġand Ġthe Ġsequence Ġof Ġthese Ġembed ding Ġvectors Ġis Ġpassed Ġthrough ĠL ST M $ _{ enc } $ : </s> The Ġlast Ġhidden Ġstate Ġ$ h _{ | o _ t | } ^{ enc } $ Ġis Ġused Ġas Ġthe Ġinitial Ġhidden Ġstate Ġof Ġthe Ġdec oder Ġwhich Ġgenerates Ġthe Ġaction Ġ$ a _ t $ Ġtoken Ġby Ġtoken . ĠSpecifically , Ġgiven Ġthe Ġsequence Ġof Ġhidden Ġstates Ġ$ H Ġ\ in Ġ\ math bb Ġ{ R } ^{ d Ġ\ times Ġ| o _ t | } $ Ġof Ġthe Ġenc oder , Ġtokens Ġ$ a _ t ^ j $ Ġare Ġgenerated Ġas Ġfollows : </s> where Ġ$ W Ġ\ in Ġ\ math bb Ġ{ R } ^{ 2 d Ġ\ times Ġ| V | } $ Ġis Ġa Ġmatrix Ġthat Ġmaps Ġthe Ġdec oder Ġhidden Ġstate , Ġconc aten ated Ġwith Ġthe Ġcontext Ġvector , Ġinto Ġa Ġvocabulary Ġsize Ġvector . ĠDuring Ġtraining , Ġthe Ġparameters Ġof Ġthe Ġmodel Ġare Ġtrained Ġby Ġminimizing : </s> which Ġis Ġthe Ġsum Ġof Ġthe Ġnegative Ġlog Ġlikelihood Ġof Ġeach Ġtoken Ġin Ġ$ a _ t $ Ġ( using Ġteacher Ġforcing ĠB IB REF 34 ). ĠHowever , Ġat Ġtest Ġtime Ġthe Ġmodel Ġproduces Ġthe Ġsequence Ġin Ġan Ġauto - reg ressive Ġway ĠB IB REF 35 Ġusing Ġgreedy Ġsearch . </s> Exper iments Ġ: :: ĠGames Ġand Ġexperiments Ġsetup </s> A Ġset Ġof Ġcommonly Ġused Ġstandard Ġbenchmarks ĠB IB REF 8 , ĠB IB REF 3 , ĠB IB REF 7 Ġfor Ġagents Ġthat Ġplay Ġtext - based Ġgames Ġare Ġsimple Ġgames Ġwhich Ġrequire Ġno Ġmore Ġthan Ġtwo Ġwords Ġin Ġeach Ġstep Ġto Ġsolve Ġthe Ġgame , Ġand Ġhave Ġa Ġvery Ġlimited Ġnumber Ġof Ġad missible Ġactions Ġper Ġobservation . ĠWhile Ġsimpl ifying , Ġthis Ġsetting Ġlimits Ġthe Ġagent 's Ġability Ġto Ġfully Ġexpress Ġnatural Ġlanguage Ġand Ġlearn Ġmore Ġcomplex Ġways Ġto Ġspeak . ĠIn Ġthis Ġpaper , Ġwe Ġembrace Ġmore Ġchallenging Ġenvironments Ġwhere Ġmultiple Ġwords Ġare Ġneeded Ġat Ġeach Ġstep Ġto Ġsolve Ġthe Ġgames Ġand Ġthe Ġreward Ġis Ġparticularly Ġsparse . ĠHence , Ġwe Ġhave Ġselected Ġthe Ġfollowing Ġenvironments : </s> [ left margin = * ] </s> Coin Collect or ĠB IB REF 8 Ġis Ġa Ġclass Ġof Ġtext - based Ġgames Ġwhere Ġthe Ġobjective Ġis Ġto Ġfind Ġand Ġcollect Ġa Ġcoin Ġfrom Ġa Ġspecific Ġlocation Ġin Ġa Ġgiven Ġset Ġof Ġconnected Ġrooms Ġ. ĠThe Ġagent Ġwins Ġthe Ġgame Ġafter Ġit Ġcollects Ġthe Ġcoin , Ġat Ġwhich Ġpoint Ġ( for Ġthe Ġfirst Ġand Ġonly Ġtime ) Ġa Ġreward Ġof Ġ+ 1 Ġis Ġreceived Ġby Ġthe Ġagent . ĠThe Ġenvironment Ġpars es Ġonly Ġfive Ġad missible Ġcommands Ġ( go Ġnorth , Ġgo Ġeast , Ġgo Ġsouth , Ġgo Ġwest , Ġand Ġtake Ġcoin ) Ġmade Ġby Ġtwo Ġworlds ; </s> Cook ing World ĠB IB REF 14 Ġin Ġthis Ġchallenge , Ġthere Ġare Ġ4 , 440 Ġgames Ġwith Ġ222 Ġdifferent Ġlevels Ġof Ġdifficulty , Ġwith Ġ20 Ġgames Ġper Ġlevel Ġof Ġdifficulty , Ġeach Ġwith Ġdifferent Ġentities Ġand Ġmaps . ĠThe Ġgoal Ġof Ġeach Ġgame Ġis Ġto Ġcook Ġand Ġeat Ġfood Ġfrom Ġa Ġgiven Ġrecipe , Ġwhich Ġincludes Ġthe Ġtask Ġof Ġcollecting Ġingredients Ġ( e . g . Ġtomato , Ġpotato , Ġetc .), Ġobjects Ġ( e . g . Ġknife ), Ġand Ġprocessing Ġthem Ġaccording Ġto Ġthe Ġrecipe Ġ( e . g . Ġcook Ġpotato , Ġslice Ġtomato , Ġetc .). ĠThe Ġparser Ġof Ġeach Ġgame Ġaccepts Ġ18 Ġverbs Ġand Ġ51 Ġentities Ġwith Ġa Ġpred efined Ġgrammar , Ġbut Ġthe Ġoverall Ġsize Ġof Ġthe Ġvocabulary Ġof Ġthe Ġobservations Ġis Ġ20 , 000 . ĠIn ĠAppendix ĠSEC REF 36 Ġwe Ġprovide Ġmore Ġdetails Ġabout Ġthe Ġlevels Ġand Ġthe Ġgames ' Ġgrammar . </s> In Ġour Ġexperiments , Ġwe Ġtry Ġto Ġaddress Ġtwo Ġmajor Ġresearch Ġquestions . ĠFirst , Ġwe Ġwant Ġto Ġbenchmark Ġthe Ġexploration Ġpower Ġof Ġphase Ġ1 Ġof ĠGo - Explore Ġin Ġcomparison Ġto Ġexisting Ġexploration Ġapproaches Ġused Ġin Ġtext - based Ġgames . ĠFor Ġthis Ġpurpose , Ġwe Ġgenerate Ġ10 ĠCoin Collect or Ġgames Ġwith Ġthe Ġhardest Ġsetting Ġused Ġby ĠB IB REF 8 , Ġi . e . Ġhard - level Ġ30 Ġ( re fer Ġto Ġthe ĠAppendix ĠSEC REF 36 Ġfor Ġmore Ġinformation ) Ġand Ġuse Ġthem Ġas Ġa Ġbenchmark . ĠIn Ġfact , ĠCoin Collect or Ġrequires Ġmany Ġactions Ġ( at Ġleast Ġ30 Ġon Ġhard Ġgames ) Ġto Ġfind Ġa Ġreward , Ġwhich Ġmakes Ġit Ġsuitable Ġfor Ġtesting Ġthe Ġexploration Ġcapabilities Ġof Ġdifferent Ġalgorithms . ĠSecondly , Ġwe Ġwant Ġto Ġverify Ġthe Ġgeneral ization Ġability Ġof Ġour Ġmodel Ġin Ġcreating Ġcomplex Ġstrategies Ġusing Ġnatural Ġlanguage . ĠCoin Collect or Ġhas Ġa Ġvery Ġlimited Ġaction Ġspace , Ġand Ġis Ġmainly Ġdesigned Ġto Ġbenchmark Ġmodels Ġon Ġtheir Ġcapability Ġof Ġdealing Ġwith Ġsparse Ġrewards . ĠTherefore Ġwe Ġuse Ġthe Ġmore Ġcomplex ĠCooking World Ġgames Ġto Ġevaluate Ġthe Ġgeneral ization Ġcapabilities Ġof Ġour Ġproposed Ġapproach . ĠWe Ġdesign Ġthree Ġdifferent Ġsettings Ġfor ĠCooking World : Ġ1 ) ĠSingle : Ġtreat Ġeach Ġgame Ġindependently , Ġwhich Ġmeans Ġwe Ġtrain Ġand Ġtest Ġone Ġagent Ġfor Ġeach Ġgame Ġto Ġevaluate Ġhow Ġrobust Ġdifferent Ġmodels Ġare Ġacross Ġdifferent Ġgames .; Ġ2 ) ĠJoint : Ġtraining Ġand Ġtesting Ġa Ġsingle Ġpolicy Ġon Ġall Ġthe Ġ4 , 440 ĠCooking World Ġgames Ġat Ġthe Ġsame Ġtime Ġto Ġverify Ġthat Ġmodels Ġcan Ġlearn Ġto Ġplay Ġmultiple Ġgames Ġat Ġthe Ġsame Ġtime ; Ġ3 ) ĠZero - Shot : Ġsplit Ġthe Ġgames Ġinto Ġtraining , Ġvalidation , Ġand Ġtest Ġsets , Ġand Ġthen Ġtrain Ġour Ġpolicy Ġon Ġthe Ġtraining Ġgames Ġand Ġtest Ġit Ġon Ġthe Ġunseen Ġtest Ġgames . ĠThis Ġsetting Ġis Ġthe Ġhardest Ġamong Ġall , Ġsince Ġit Ġrequires Ġgeneral ization Ġto Ġunseen Ġgames . </s> In Ġboth ĠCoin Collect or Ġand ĠCooking World Ġgames Ġan Ġobservation Ġ$ o _ t $ Ġprovided Ġby Ġthe Ġenvironment Ġconsists Ġof Ġa Ġroom Ġdescription Ġ$ D $, Ġinventory Ġinformation Ġ$ I $, Ġquest Ġ$ Q $, Ġprevious Ġaction Ġ$ P $ Ġand Ġfeedback Ġ$ F $ Ġprovided Ġin Ġthe Ġprevious Ġturn . ĠTable ĠT AB REF 3 Ġshows Ġan Ġexample Ġfor Ġeach Ġof Ġthese Ġcomponents . ĠIn Ġour Ġexperiments Ġfor Ġphase Ġ1 Ġof ĠGo - Explore Ġwe Ġonly Ġuse Ġ$ D $ Ġas Ġthe Ġobservation . </s> Exper iments Ġ: :: ĠBas elines </s> For Ġthe ĠCoin Collect or Ġgames , Ġwe Ġcompared ĠGo - Explore Ġwith Ġthe Ġepis odic Ġdiscovery Ġbonus ĠB IB REF 30 Ġthat Ġwas Ġused Ġby ĠB IB REF 8 Ġto Ġimprove Ġtwo ĠQ - learning - based Ġbas elines : ĠD Q N ++ Ġand ĠDR Q N ++ . ĠWe Ġused Ġthe Ġcode Ġprovided Ġby Ġthe Ġauthors Ġand Ġthe Ġsame Ġhyper - param eters . </s> For Ġthe ĠCooking World Ġgames , Ġwe Ġimplemented Ġthree Ġdifferent Ġtreatments Ġbased Ġon Ġtwo Ġexisting Ġmethods : </s> [ left margin = * ] </s> L ST M - D Q N ĠB IB REF 7 , ĠB IB REF 8 : ĠAn ĠL ST M Ġbased Ġstate Ġenc oder Ġwith Ġa Ġseparate Ġ$ Q $ - fun ctions Ġfor Ġeach Ġcomponent Ġ( word ) Ġof Ġa Ġfixed Ġpattern Ġof ĠVerb , ĠAd ject ive 1 , ĠN oun 1 , ĠAd ject ive 2 , Ġand ĠN oun 2 . ĠIn Ġthis Ġapproach , Ġgiven Ġthe Ġobservation Ġ$ o _ t $, Ġthe Ġtokens Ġare Ġfirst Ġconverted Ġinto Ġembed d ings , Ġthen Ġan ĠL ST M Ġis Ġused Ġto Ġextract Ġa Ġsequence Ġof Ġhidden Ġstates Ġ$ H _{ dq n }\ in Ġ\ math bb Ġ{ R } ^{ d Ġ\ times Ġ| o _ t | } $. ĠA Ġmean - pool Ġlayer Ġis Ġapplied Ġto Ġ$ H _{ dq n } $ Ġto Ġproduce Ġa Ġsingle Ġvector Ġ$ h _{ o ^ t } $ Ġthat Ġrepresents Ġthe Ġwhole Ġsequence . ĠNext , Ġa Ġlinear Ġtransformation Ġ$ W _{ \ text { type }} \ in Ġ\ math bb Ġ{ R } ^{ d Ġ\ times Ġ| V _{ \ text { type }} | } $ Ġis Ġused Ġto Ġgenerate Ġeach Ġof Ġthe ĠQ Ġvalues , Ġwhere Ġ$ | V _{ \ text { type }} | Ġ\ ll Ġ| V | $ Ġis Ġthe Ġsubset Ġof Ġthe Ġoriginal Ġvocabulary Ġrestricted Ġto Ġthe Ġword Ġtype Ġof Ġa Ġparticular Ġgame Ġ( e . g Ġfor ĠVerb Ġtype : Ġtake , Ġdrop , Ġetc .). ĠForm ally , Ġwe Ġhave : </s> Next , Ġall Ġthe Ġ$ Q $ - fun ctions Ġare Ġjointly Ġtrained Ġusing Ġthe ĠD Q N Ġalgorithm Ġwith Ġ$\ ep sil on Ġ$ - gre edy Ġexploration ĠB IB REF 15 , ĠB IB REF 16 . ĠAt Ġevaluation Ġtime , Ġthe Ġarg max Ġof Ġeach Ġ$ Q $ - function Ġis Ġconc aten ated Ġto Ġproduce Ġ$ a _ t $. ĠImport antly , Ġin Ġ$ V _{ \ text { type }} $ Ġa Ġspecial Ġtoken Ġ$ < $ s $ > $ Ġis Ġused Ġto Ġdenote Ġthe Ġabsence Ġof Ġa Ġword , Ġso Ġthe Ġmodel Ġcan Ġproduce Ġactions Ġwith Ġdifferent Ġlengths . ĠFigure ĠFIG REF 57 Ġin ĠAppendix ĠSEC REF 55 Ġshows Ġa Ġdepiction Ġof Ġthis Ġmodel . </s> L ST M - D Q N + AD M : ĠIt Ġis Ġthe Ġsame Ġmodel Ġas ĠL ST M - D Q N , Ġexcept Ġthat Ġthe Ġrandom Ġactions Ġfor Ġ$\ ep sil on Ġ$ - gre edy Ġexploration Ġare Ġsampled Ġfrom Ġthe Ġset Ġof Ġad missible Ġactions Ġinstead Ġof Ġcreating Ġthem Ġby Ġsampling Ġeach Ġword Ġseparately . </s> DR RN ĠB IB REF 10 : ĠIn Ġthis Ġapproach Ġa Ġmodel Ġlearns Ġhow Ġto Ġscore Ġad missible Ġactions Ġinstead Ġof Ġdirectly Ġgenerating Ġthe Ġaction Ġtoken Ġby Ġtoken . ĠThe Ġpolicy Ġuses Ġan ĠL ST M Ġfor Ġencoding Ġthe Ġobservation Ġand Ġactions Ġare Ġrepresented Ġas Ġthe Ġsum Ġof Ġthe Ġembed ding Ġof Ġthe Ġword Ġtokens Ġthey Ġcontain . ĠThen , Ġthe Ġ$ Q $ Ġvalue Ġis Ġdefined Ġas Ġthe Ġdot Ġproduct Ġbetween Ġthe Ġembedded Ġrepresentations Ġof Ġthe Ġobservation Ġand Ġthe Ġaction . ĠFollowing Ġthe Ġaforementioned Ġnotation , Ġ$ h _{ o ^ t } $ Ġis Ġgenerated Ġas Ġin Ġthe ĠL ST M - D Q N Ġbaseline . ĠNext , Ġwe Ġdefine Ġits Ġembedded Ġrepresentation Ġas Ġ$ c _ i = \ sum Ġ_ k ^{ | a _ i | } ĠE ( a _ i ^ k ) $, Ġwhere Ġ$ E $ Ġis Ġan Ġembed ding Ġmatrix Ġas Ġin ĠEqu ation Ġ1 . ĠThus , Ġthe Ġ$ Q $ - function Ġis Ġdefined Ġas : </s> At Ġtesting Ġtime Ġthe Ġaction Ġwith Ġthe Ġhighest Ġ$ Q $ Ġvalue Ġis Ġchosen . ĠFigure ĠFIG REF 58 Ġin ĠAppendix ĠSEC REF 55 Ġshows Ġa Ġdepiction Ġof Ġthis Ġmodel . </s> Exper iments Ġ: :: ĠHyper - param eters </s> In Ġall Ġthe Ġgames Ġthe Ġmaximum Ġnumber Ġof Ġsteps Ġhas Ġbeen Ġset Ġto Ġ50 . ĠAs Ġmentioned Ġearlier , Ġthe Ġcell Ġrepresentation Ġused Ġin Ġthe ĠGo - Explore Ġarchive Ġis Ġcomputed Ġby Ġthe Ġsum Ġof Ġembed d ings Ġof Ġthe Ġroom Ġdescription Ġtokens Ġconc aten ated Ġwith Ġthe Ġcurrent Ġcumulative Ġreward . ĠThe Ġsum Ġof Ġembed d ings Ġis Ġcomputed Ġusing Ġ50 Ġdimensional Ġpre - trained ĠGl o Ve ĠB IB REF 36 Ġvectors . ĠIn Ġthe ĠCoin Collect or Ġbas elines Ġwe Ġuse Ġthe Ġsame Ġhyper - param eters Ġas Ġin Ġthe Ġoriginal Ġpaper . ĠIn ĠCooking World Ġall Ġthe Ġbas elines Ġuse Ġpre - trained ĠGl o Ve Ġof Ġdimension Ġ100 Ġfor Ġthe Ġsingle Ġsetting Ġand Ġ300 Ġfor Ġthe Ġjoint Ġone . ĠThe ĠL ST M Ġhidden Ġstate Ġhas Ġbeen Ġset Ġto Ġ300 Ġfor Ġall Ġthe Ġmodels . </s> Results Ġ: :: ĠCoin Collect or </s> In Ġthis Ġsetting , Ġwe Ġcompare Ġthe Ġnumber Ġof Ġactions Ġplayed Ġin Ġthe Ġenvironment Ġ( frames ) Ġand Ġthe Ġscore Ġachieved Ġby Ġthe Ġagent Ġ( i . e . Ġ+ 1 Ġreward Ġif Ġthe Ġcoin Ġis Ġcollected ). ĠIn ĠGo - Explore Ġwe Ġalso Ġcount Ġthe Ġactions Ġused Ġto Ġrestore Ġthe Ġenvironment Ġto Ġa Ġselected Ġcell , Ġi . e . Ġto Ġbring Ġthe Ġagent Ġto Ġthe Ġstate Ġrepresented Ġin Ġthe Ġselected Ġcell . ĠThis Ġallows Ġa Ġone - to - one Ġcomparison Ġof Ġthe Ġexploration Ġefficiency Ġbetween ĠGo - Explore Ġand Ġalgorithms Ġthat Ġuse Ġa Ġcount - based Ġreward Ġin Ġtext - based Ġgames . ĠImport antly , ĠB IB REF 8 Ġshowed Ġthat ĠD Q N Ġand ĠDR Q N , Ġwithout Ġsuch Ġcounting Ġrewards , Ġcould Ġnever Ġfind Ġa Ġsuccessful Ġtrajectory Ġin Ġhard Ġgames Ġsuch Ġas Ġthe Ġones Ġused Ġin Ġour Ġexperiments . ĠFigure ĠFIG REF 17 Ġshows Ġthe Ġnumber Ġof Ġinteractions Ġwith Ġthe Ġenvironment Ġ( frames ) Ġversus Ġthe Ġmaximum Ġscore Ġobtained , Ġaveraged Ġover Ġ10 Ġgames Ġof Ġthe Ġsame Ġdifficulty . ĠAs Ġshown Ġby ĠB IB REF 8 , ĠDR Q N ++ Ġfinds Ġa Ġtrajectory Ġwith Ġthe Ġmaximum Ġscore Ġfaster Ġthan Ġto ĠD Q N ++ . ĠOn Ġthe Ġother Ġhand , Ġphase Ġ1 Ġof ĠGo - Explore Ġfinds Ġan Ġoptimal Ġtrajectory Ġwith Ġapproximately Ġhalf Ġthe Ġinteractions Ġwith Ġthe Ġenvironment . ĠMoreover , Ġthe Ġtrajectory Ġlength Ġfound Ġby ĠGo - Explore Ġis Ġalways Ġoptimal Ġ( i . e . Ġ30 Ġsteps ) Ġwhereas Ġboth ĠD Q N ++ Ġand ĠDR Q N ++ Ġhave Ġan Ġaverage Ġlength Ġof Ġ38 Ġand Ġ42 Ġrespectively . </s> Results Ġ: :: ĠCooking World </s> In ĠCooking World , Ġwe Ġcompared Ġmodels Ġin Ġthe Ġthree Ġsettings Ġmentioned Ġearlier , Ġnamely , Ġsingle , Ġjoint , Ġand Ġzero - shot . ĠIn Ġall Ġexperiments , Ġwe Ġmeasured Ġthe Ġsum Ġof Ġthe Ġfinal Ġscores Ġof Ġall Ġthe Ġgames Ġand Ġtheir Ġtrajectory Ġlength Ġ( number Ġof Ġsteps ). ĠTable ĠT AB REF 26 Ġsummarizes Ġthe Ġresults Ġin Ġthese Ġthree Ġsettings . ĠPhase Ġ1 Ġof ĠGo - Explore Ġon Ġsingle Ġgames Ġachieves Ġa Ġtotal Ġscore Ġof Ġ19 , 530 Ġ( sum Ġover Ġall Ġgames ), Ġwhich Ġis Ġvery Ġclose Ġto Ġthe Ġmaximum Ġpossible Ġpoints Ġ( i . e . Ġ19 , 882 ), Ġwith Ġ47 , 562 Ġsteps . ĠA Ġwinning Ġtrajectory Ġwas Ġfound Ġin Ġ4 , 279 Ġout Ġof Ġthe Ġtotal Ġof Ġ4 , 440 Ġgames . ĠThis Ġresult Ġconfirms Ġagain Ġthat Ġthe Ġexploration Ġstrategy Ġof ĠGo - Explore Ġis Ġeffective Ġin Ġtext - based Ġgames . ĠNext , Ġwe Ġevaluate Ġthe Ġeffectiveness Ġand Ġthe Ġgeneral ization Ġability Ġof Ġthe Ġsimple Ġimitation Ġlearning Ġpolicy Ġtrained Ġusing Ġthe Ġextracted Ġtraject ories Ġin Ġphase Ġ1 Ġof ĠGo - Explore Ġin Ġthe Ġthree Ġsettings Ġmentioned Ġabove . </s> Results Ġ: :: ĠCooking World Ġ: :: ĠSingle </s> In Ġthis Ġsetting , Ġeach Ġmodel Ġis Ġtrained Ġfrom Ġscratch Ġin Ġeach Ġof Ġthe Ġ4 , 440 Ġgames Ġbased Ġon Ġthe Ġtrajectory Ġfound Ġin Ġphase Ġ1 Ġof ĠGo - Explore Ġ( pre vious Ġstep ). ĠAs Ġshown Ġin ĠTable ĠT AB REF 26 , Ġthe ĠL ST M - D Q N ĠB IB REF 7 , ĠB IB REF 8 Ġapproach Ġwithout Ġthe Ġuse Ġof Ġad missible Ġactions Ġperforms Ġpoorly . ĠOne Ġexplanation Ġfor Ġthis Ġcould Ġbe Ġthat Ġit Ġis Ġdifficult Ġfor Ġthis Ġmodel Ġto Ġexplore Ġboth Ġlanguage Ġand Ġgame Ġstrategy Ġat Ġthe Ġsame Ġtime ; Ġit Ġis Ġhard Ġfor Ġthe Ġmodel Ġto Ġfind Ġa Ġreward Ġsignal Ġbefore Ġit Ġhas Ġlearned Ġto Ġmodel Ġlanguage , Ġsince Ġalmost Ġnone Ġof Ġits Ġactions Ġwill Ġbe Ġad missible , Ġand Ġthose Ġreward Ġsignals Ġare Ġwhat Ġis Ġnecessary Ġin Ġorder Ġto Ġlearn Ġthe Ġlanguage Ġmodel . ĠAs Ġwe Ġsee Ġin ĠTable ĠT AB REF 26 , Ġhowever , Ġby Ġusing Ġthe Ġad missible Ġactions Ġin Ġthe Ġ$\ ep sil on Ġ$ - gre edy Ġstep Ġthe Ġscore Ġachieved Ġby Ġthe ĠL ST M - D Q N Ġincreases Ġdramatically Ġ(+ AD M Ġrow Ġin ĠTable ĠT AB REF 26 ). ĠDR RN ĠB IB REF 10 Ġachieves Ġa Ġvery Ġhigh Ġscore , Ġsince Ġit Ġexplicitly Ġlearns Ġhow Ġto Ġrank Ġad missible Ġactions Ġ( i . e . Ġa Ġmuch Ġsimpler Ġtask Ġthan Ġgenerating Ġtext ). ĠFinally , Ġour Ġapproach Ġof Ġusing Ġa ĠSe q 2 Se q Ġmodel Ġtrained Ġon Ġthe Ġsingle Ġtrajectory Ġprovided Ġby Ġphase Ġ1 Ġof ĠGo - Explore Ġachieves Ġthe Ġhighest Ġscore Ġamong Ġall Ġthe Ġmethods , Ġeven Ġthough Ġwe Ġdo Ġnot Ġuse Ġad missible Ġactions Ġin Ġthis Ġphase . ĠHowever , Ġin Ġthis Ġexperiment Ġthe ĠSe q 2 Se q Ġmodel Ġcannot Ġperfectly Ġreplicate Ġthe Ġprovided Ġtrajectory Ġand Ġthe Ġtotal Ġscore Ġthat Ġit Ġachieves Ġis Ġin Ġfact Ġ9 . 4 % Ġlower Ġcompared Ġto Ġthe Ġtotal Ġscore Ġachieved Ġby Ġphase Ġ1 Ġof ĠGo - Explore . ĠFigure ĠFIG REF 61 Ġ( in ĠAppendix ĠSEC REF 60 ) Ġshows Ġthe Ġscore Ġbreakdown Ġfor Ġeach Ġlevel Ġand Ġmodel , Ġwhere Ġwe Ġcan Ġsee Ġthat Ġthe Ġgap Ġbetween Ġour Ġmodel Ġand Ġother Ġmethods Ġincreases Ġas Ġthe Ġgames Ġbecome Ġharder Ġin Ġterms Ġof Ġskills Ġneeded . </s> Results Ġ: :: ĠCooking World Ġ: :: ĠJoint </s> In Ġthis Ġsetting , Ġa Ġsingle Ġmodel Ġis Ġtrained Ġon Ġall Ġthe Ġgames Ġat Ġthe Ġsame Ġtime , Ġto Ġtest Ġwhether Ġone Ġagent Ġcan Ġlearn Ġto Ġplay Ġmultiple Ġgames . ĠOverall , Ġas Ġexpected , Ġall Ġthe Ġevaluated Ġmodels Ġachieved Ġa Ġlower Ġperformance Ġcompared Ġto Ġthe Ġsingle Ġgame Ġsetting . ĠOne Ġreason Ġfor Ġthis Ġcould Ġbe Ġthat Ġlearning Ġmultiple Ġgames Ġat Ġthe Ġsame Ġtime Ġleads Ġto Ġa Ġsituation Ġwhere Ġthe Ġagent Ġencounters Ġsimilar Ġobservations Ġin Ġdifferent Ġgames , Ġand Ġthe Ġcorrect Ġaction Ġto Ġtake Ġin Ġdifferent Ġgames Ġmay Ġbe Ġdifferent . ĠFurthermore , Ġit Ġis Ġimportant Ġto Ġnote Ġthat Ġthe Ġorder Ġin Ġwhich Ġgames Ġare Ġpresented Ġgreatly Ġaffects Ġthe Ġperformance Ġof ĠL ST M - D Q N Ġand ĠDR RN . ĠIn Ġour Ġexperiments , Ġwe Ġtried Ġboth Ġan Ġeasy - to - hard Ġcurriculum Ġ( i . e . Ġsorting Ġthe Ġgames Ġby Ġincreasing Ġlevel Ġof Ġdifficulty ) Ġand Ġa Ġshuff led Ġcurriculum . ĠSh uff ling Ġthe Ġgames Ġat Ġeach Ġepoch Ġresulted Ġin Ġfar Ġbetter Ġperformance , Ġthus Ġwe Ġonly Ġreport Ġthe Ġlatter . ĠIn ĠFigure ĠFIG REF 28 Ġwe Ġshow Ġthe Ġscore Ġbreakdown , Ġand Ġwe Ġcan Ġsee Ġthat Ġall Ġthe Ġbas elines Ġquickly Ġfail , Ġeven Ġfor Ġeasier Ġgames . </s> Results Ġ: :: ĠCooking World Ġ: :: ĠZero - Shot </s> In Ġthis Ġsetting Ġthe Ġ4 , 440 Ġgames Ġare Ġsplit Ġinto Ġtraining , Ġvalidation , Ġand Ġtest Ġgames . ĠThe Ġsplit Ġis Ġdone Ġrandomly Ġbut Ġin Ġa Ġway Ġthat Ġdifferent Ġdifficulty Ġlevels Ġ( rec ipes Ġ1 , Ġ2 Ġand Ġ3 ), Ġare Ġrepresented Ġwith Ġequal Ġratios Ġin Ġall Ġthe Ġ3 Ġsplits , Ġi . e . Ġstrat ified Ġby Ġdifficulty . ĠAs Ġshown Ġin ĠTable ĠT AB REF 26 , Ġthe Ġzero - shot Ġperformance Ġof Ġthe ĠRL Ġbas elines Ġis Ġpoor , Ġwhich Ġcould Ġbe Ġattributed Ġto Ġthe Ġsame Ġreasons Ġwhy ĠRL Ġbas elines Ġunder - per form Ġin Ġthe ĠJoint Ġcase . ĠEspecially Ġinteresting Ġis Ġthat Ġthe Ġperformance Ġof ĠDR RN Ġis Ġsubstantially Ġlower Ġthan Ġthat Ġof Ġthe ĠGo - Explore ĠSe q 2 Se q Ġmodel , Ġeven Ġthough Ġthe ĠDR RN Ġmodel Ġhas Ġaccess Ġto Ġthe Ġad missible Ġactions Ġat Ġtest Ġtime , Ġwhile Ġthe ĠSe q 2 Se q Ġmodel Ġ( as Ġwell Ġas Ġthe ĠL ST M - D Q N Ġmodel ) Ġhas Ġto Ġconstruct Ġactions Ġtoken - by - token Ġfrom Ġthe Ġentire Ġvocabulary Ġof Ġ20 , 000 Ġtokens . ĠOn Ġthe Ġother Ġhand , ĠGo - Explore ĠSe q 2 Se q Ġshows Ġpromising Ġresults Ġby Ġsolving Ġalmost Ġhalf Ġof Ġthe Ġunseen Ġgames . ĠFigure ĠFIG REF 62 Ġ( in ĠAppendix ĠSEC REF 60 ) Ġshows Ġthat Ġmost Ġof Ġthe Ġlost Ġgames Ġare Ġin Ġthe Ġhardest Ġset , Ġwhere Ġa Ġvery Ġlong Ġsequence Ġof Ġactions Ġis Ġrequired Ġfor Ġwinning Ġthe Ġgame . ĠThese Ġresults Ġdemonstrate Ġboth Ġthe Ġrelative Ġeffectiveness Ġof Ġtraining Ġa ĠSe q 2 Se q Ġmodel Ġon ĠGo - Explore Ġtraject ories , Ġbut Ġthey Ġalso Ġindicate Ġthat Ġadditional Ġeffort Ġneeded Ġfor Ġdesigning Ġreinforcement Ġlearning Ġalgorithms Ġthat Ġeffectively Ġgeneral ize Ġto Ġunseen Ġgames . </s> Discussion </s> Exper imental Ġresults Ġshow Ġthat Ġour Ġproposed ĠGo - Explore Ġexploration Ġstrategy Ġis Ġa Ġviable Ġmethodology Ġfor Ġextracting Ġhigh - performing Ġtraject ories Ġin Ġtext - based Ġgames . ĠThis Ġmethod Ġallows Ġus Ġto Ġtrain Ġsupervised Ġmodels Ġthat Ġcan Ġoutper form Ġexisting Ġmodels Ġin Ġthe Ġexperimental Ġsettings Ġthat Ġwe Ġstudy . ĠFinally , Ġthere Ġare Ġstill Ġseveral Ġchallenges Ġand Ġlimitations Ġthat Ġboth Ġour Ġmethodology Ġand Ġprevious Ġsolutions Ġdo Ġnot Ġfully Ġaddress Ġyet . ĠFor Ġinstance : </s> Discussion Ġ: :: ĠState ĠRepresent ation </s> The Ġstate Ġrepresentation Ġis Ġthe Ġmain Ġlimitation Ġof Ġour Ġproposed Ġimitation Ġlearning Ġmodel . ĠIn Ġfact , Ġby Ġexamining Ġthe Ġobservations Ġprovided Ġin Ġdifferent Ġgames , Ġwe Ġnotice Ġa Ġlarge Ġoverlap Ġin Ġthe Ġdescriptions Ġ($ D $ ) Ġof Ġthe Ġgames . ĠThis Ġoverlap Ġleads Ġto Ġa Ġsituation Ġwhere Ġthe Ġpolicy Ġreceives Ġvery Ġsimilar Ġobservations , Ġbut Ġis Ġexpected Ġto Ġimitate Ġtwo Ġdifferent Ġactions . ĠThis Ġshow Ġespecially Ġin Ġthe Ġjoint Ġsetting Ġof ĠCooking World , Ġwhere Ġthe Ġ222 Ġgames Ġare Ġrepeated Ġ20 Ġtimes Ġwith Ġdifferent Ġentities Ġand Ġroom Ġmaps . ĠIn Ġthis Ġwork , Ġwe Ġopted Ġfor Ġa Ġsimple ĠSe q 2 Se q Ġmodel Ġfor Ġour Ġpolicy , Ġsince Ġour Ġgoal Ġis Ġto Ġshow Ġthe Ġeffectiveness Ġof Ġour Ġproposed Ġexploration Ġmethods . ĠHowever , Ġa Ġmore Ġcomplex ĠHier arch ical - Se q 2 Se q Ġmodel ĠB IB REF 37 Ġor Ġa Ġbetter Ġenc oder Ġrepresentation Ġbased Ġon Ġknowledge Ġgraphs ĠB IB REF 38 , ĠB IB REF 39 Ġwould Ġlikely Ġimprove Ġthe Ġof Ġperformance Ġthis Ġapproach . </s> Discussion Ġ: :: ĠLanguage ĠBased ĠExploration </s> In ĠGo - Explore , Ġthe Ġgiven Ġad missible Ġactions Ġare Ġused Ġduring Ġrandom Ġexploration . ĠHowever , Ġin Ġmore Ġcomplex Ġgames , Ġe . g . ĠZ ork ĠI Ġand Ġin Ġgeneral Ġthe ĠZ - Machine Ġgames , Ġthese Ġad missible Ġactions Ġare Ġnot Ġprovided . ĠIn Ġsuch Ġsettings , Ġthe Ġaction Ġspace Ġwould Ġexplode Ġin Ġsize , Ġand Ġthus ĠGo - Explore , Ġeven Ġwith Ġan Ġappropriate Ġcell Ġrepresentation , Ġwould Ġhave Ġa Ġhard Ġtime Ġfinding Ġgood Ġtraject ories . ĠTo Ġaddress Ġthis Ġissue Ġone Ġcould Ġleverage Ġgeneral Ġlanguage Ġmodels Ġto Ġproduce Ġa Ġset Ġof Ġgram matically Ġcorrect Ġactions . ĠAlternatively Ġone Ġcould Ġiter atively Ġlearn Ġa Ġpolicy Ġto Ġsample Ġactions , Ġwhile Ġexploring Ġwith ĠGo - Explore . ĠBoth Ġstrategies Ġare Ġviable , Ġand Ġa Ġcomparison Ġis Ġleft Ġto Ġfuture Ġwork . </s> It Ġis Ġworth Ġnoting Ġthat Ġa Ġhand - tail ored Ġsolution Ġfor Ġthe ĠCooking World Ġgames Ġhas Ġbeen Ġproposed Ġin Ġthe ĠâĢ ľ First ĠText World ĠProblems âĢ Ŀ Ġcompetition ĠB IB REF 3 . ĠThis Ġsolution Ġmanaged Ġto Ġobtain Ġup Ġto Ġ91 . 9 % Ġof Ġthe Ġmaximum Ġpossible Ġscore Ġacross Ġthe Ġ5 14 Ġtest Ġgames Ġon Ġan Ġunpublished Ġdataset . ĠHowever , Ġthis Ġsolution Ġrelies Ġon Ġentity Ġextraction Ġand Ġtemplate Ġfilling , Ġwhich Ġwe Ġbelieve Ġlimits Ġits Ġpotential Ġfor Ġgeneral ization . ĠTherefore , Ġthis Ġapproach Ġshould Ġbe Ġviewed Ġas Ġcomplementary Ġrather Ġthan Ġcompetitor Ġto Ġour Ġapproach Ġas Ġit Ġcould Ġpotentially Ġbe Ġused Ġas Ġan Ġalternative Ġway Ġof Ġgetting Ġpromising Ġtraject ories . </s> Conclusion </s> In Ġthis Ġpaper Ġwe Ġpresented Ġa Ġnovel Ġmethodology Ġfor Ġsolving Ġtext - based Ġgames Ġwhich Ġfirst Ġextracts Ġhigh - performing Ġtraject ories Ġusing Ġphase Ġ1 Ġof ĠGo - Explore Ġand Ġthen Ġtrains Ġa Ġsimple ĠSe q 2 Se q Ġmodel Ġthat Ġmaps Ġobservations Ġto Ġactions Ġusing Ġthe Ġextracted Ġtraject ories . ĠOur Ġexperiments Ġshow Ġpromising Ġresults Ġin Ġthree Ġsettings , Ġwith Ġimproved Ġgeneral ization Ġand Ġsample Ġefficiency Ġcompared Ġto Ġexisting Ġmethods . ĠFinally , Ġwe Ġdiscussed Ġthe Ġlimitations Ġand Ġpossible Ġimprovements Ġof Ġour Ġmethodology , Ġwhich Ġleads Ġto Ġnew Ġresearch Ġchallenges Ġin Ġtext - based Ġgames . </s> App endix Ġ: :: ĠText - Games Ġ: :: ĠCoin Collect or </s> In Ġthe Ġhard Ġsetting Ġ( mode Ġ2 ), Ġeach Ġroom Ġon Ġthe Ġpath Ġto Ġthe Ġcoin Ġhas Ġtwo Ġdistract or Ġrooms , Ġand Ġthe Ġlevel Ġ( e . g . Ġ30 ) Ġindicates Ġthe Ġshortest Ġpath Ġfrom Ġthe Ġstarting Ġpoint Ġto Ġthe Ġcoin Ġroom . </s> App endix Ġ: :: ĠText - Games Ġ: :: ĠCooking World </s> The Ġgame 's Ġcomplexity Ġis Ġdetermined Ġby Ġthe Ġnumber Ġof Ġskills Ġand Ġthe Ġtypes Ġof Ġskills Ġthat Ġan Ġagent Ġneeds Ġto Ġmaster . ĠThe Ġskills Ġare : </s> reci pe Ġ{ 1 , 2 , 3 }: Ġnumber Ġof Ġingredients Ġin Ġthe Ġrecipe </s> take Ġ{ 1 , 2 , 3 }: Ġnumber Ġof Ġingredients Ġto Ġfind Ġ( not Ġalready Ġin Ġthe Ġinventory ) </s> open : Ġwhether Ġcontainers / doors Ġneed Ġto Ġbe Ġopened </s> cook : Ġwhether Ġingredients Ġneed Ġto Ġbe Ġcooked </s> cut : Ġwhether Ġingredients Ġneed Ġto Ġbe Ġcut </s> drop : Ġwhether Ġthe Ġinventory Ġhas Ġlimited Ġcapacity </s> go Ġ{ 1 , 6 , 9 , 12 }: Ġnumber Ġof Ġlocations </s> Thus Ġthe Ġhardest Ġgame Ġwould Ġbe Ġa Ġrecipe Ġwith Ġ3 Ġingredients , Ġwhich Ġmust Ġall Ġbe Ġpicked Ġup Ġsomewhere Ġacross Ġ12 Ġlocations Ġand Ġthen Ġneed Ġto Ġbe Ġcut Ġand Ġcooked , Ġand Ġto Ġget Ġaccess Ġto Ġsome Ġlocations , Ġseveral Ġdoors Ġor Ġobjects Ġneed Ġto Ġbe Ġopened . ĠThe Ġhandic ap Ġof Ġa Ġlimited Ġcapacity Ġin Ġthe Ġinventory Ġmakes Ġthe Ġgame Ġmore Ġdifficult Ġby Ġrequiring Ġthe Ġagent Ġto Ġdrop Ġan Ġobject Ġand Ġlater Ġon Ġtake Ġit Ġagain Ġif Ġneeded . ĠThe Ġgrammar Ġused Ġfor Ġthe Ġtext - based Ġgames Ġis Ġthe Ġfollowing : </s> go , Ġlook , Ġexamine , Ġinventory , Ġeat , Ġopen / close , Ġtake / drop , Ġput / insert </s> cook ĠX Ġwith ĠY Ġ$\ long right arrow Ġ$ Ġgrilled ĠX Ġ( when ĠY Ġis Ġthe ĠBBQ ) </s> cook ĠX Ġwith ĠY Ġ$\ long right arrow Ġ$ Ġroasted ĠX Ġ( when ĠY Ġis Ġthe Ġoven ) </s> cook ĠX Ġwith ĠY Ġ$\ long right arrow Ġ$ Ġfried ĠX Ġ( when ĠY Ġis Ġthe Ġstove ) </s> slice ĠX Ġwith ĠY Ġ$\ long right arrow Ġ$ Ġsliced ĠX </s> ch op ĠX Ġwith ĠY Ġ$\ long right arrow Ġ$ Ġchopped ĠX </s> d ice ĠX Ġwith ĠY Ġ$\ long right arrow Ġ$ Ġdiced ĠX </s> prep are Ġmeal </s> Where ĠY Ġis Ġsomething Ġsharp Ġ( e . g . Ġknife ).
Introduction Text-based games became popular in the mid 80s with the game series Zork BIBREF1 resulting in many different text-based games being produced and published BIBREF2. These games use a plain text description of the environment and the player has to interact with them by writing natural-language commands. Recently, there has been a growing interest in developing agents that can automatically solve text-based games BIBREF3 by interacting with them. These settings challenge the ability of an artificial agent to understand natural language, common sense knowledge, and to develop the ability to interact with environments using language BIBREF4, BIBREF5. Since the actions in these games are commands that are in natural language form, the major obstacle is the extremely large action space of the agent, which leads to a combinatorially large exploration problem. In fact, with a vocabulary of $N$ words (e.g. 20K) and the possibility of producing sentences with at most $m$ words (e.g. 7 words), the total number of actions is $O(N^m)$ (e.g. 20K$^7 \approx 1.28 e^{30}$). To avoid this large action space, several existing solutions focus on simpler text-based games with very small vocabularies where the action space is constrained to verb-object pairs BIBREF6, BIBREF7, BIBREF8, BIBREF9. Moreover, many existing works rely on using predetermined sets of admissible actions BIBREF10, BIBREF11, BIBREF12. However, a more ideal, and still under explored, alternative would be an agent that can operate in the full, unconstrained action space of natural language that can systematically generalize to new text-based games with no or few interactions with the environment. To address this challenge, we propose to use the idea behind the recently proposed Go-Explore BIBREF0 algorithm. Specifically, we propose to first extract high reward trajectories of states and actions in the game using the exploration methodology proposed in Go-Explore and then train a policy using a Seq2Seq BIBREF13 model that maps observations to actions, in an imitation learning fashion. To show the effectiveness of our proposed methodology, we first benchmark the exploration ability of Go-Explore on the family of text-based games called CoinCollector BIBREF8. Then we use the 4,440 games of “First TextWorld Problems” BIBREF14, which are generated using the machinery introduced by BIBREF3, to show the generalization ability of our proposed methodology. In the former experiment we show that Go-Explore finds winning trajectories faster than existing solutions, and in the latter, we show that training a Seq2Seq model on the trajectories found by Go-Explore results in stronger generalization, as suggested by the stronger performance on unseen games, compared to existing competitive baselines BIBREF10, BIBREF7. Introduction ::: Reinforcement Learning Based Approaches for Text-Based Games Among reinforcement learning based efforts to solve text-based games two approaches are prominent. The first approach assumes an action as a sentence of a fixed number of words, and associates a separate $Q$-function BIBREF15, BIBREF16 with each word position in this sentence. This method was demonstrated with two-word sentences consisting of a verb-object pair (e.g. take apple) BIBREF6, BIBREF7, BIBREF8, BIBREF9, BIBREF17. In the second approach, one $Q$-function that scores all possible actions (i.e. sentences) is learned and used to play the game BIBREF10, BIBREF11, BIBREF12. The first approach is quite limiting since a fixed number of words must be selected in advance and no temporal dependency is enforced between words (e.g. lack of language modelling). In the second approach, on the other hand, the number of possible actions can become exponentially large if the admissible actions (a predetermined low cardinality set of actions that the agent can take) are not provided to the agent. A possible solution to this issue has been proposed by BIBREF18, where a hierarchical pointer-generator is used to first produce the set of admissible actions given the observation, and subsequently one element of this set is chosen as the action for that observation. However, in our experiments we show that even in settings where the true set of admissible actions is provided by the environment, a $Q$-scorer BIBREF10 does not generalize well in our setting (Section 5.2 Zero-Shot) and we would expect performance to degrade even further if the admissible actions were generated by a separate model. Less common are models that either learn to reduce a large set of actions into a smaller set of admissible actions by eliminating actions BIBREF12 or by compressing them in a latent space BIBREF11. Introduction ::: Exploration in Reinforcement Learning In most text-based games rewards are sparse, since the size of the action space makes the probability of observing a reward extremely low when taking only random actions. Sparse reward environments are particularly challenging for reinforcement learning as they require longer term planning. Many exploration based solutions have been proposed to address the challenges associated with reward sparsity. Among these exploration approaches are novelty search BIBREF19, BIBREF20, BIBREF21, BIBREF22, BIBREF23, intrinsic motivation BIBREF24, BIBREF25, BIBREF26, and curiosity based rewards BIBREF27, BIBREF28, BIBREF29. For text based games exploration methods have been studied by BIBREF8, where the authors showed the effectiveness of the episodic discovery bonus BIBREF30 in environments with sparse rewards. This exploration method can only be applied in games with very small action and state spaces, since their counting methods rely on the state in its explicit raw form. Methodology Go-Explore BIBREF0 differs from the exploration-based algorithms discussed above in that it explicitly keeps track of under-explored areas of the state space and in that it utilizes the determinism of the simulator in order to return to those states, allowing it to explore sparse-reward environments in a sample efficient way (see BIBREF0 as well as section SECREF27). For the experiments in this paper we mainly focus on the final performance of our policy, not how that policy is trained, thus making Go-Explore a suitable algorithm for our experiments. Go-Explore is composed of two phases. In phase 1 (also referred to as the “exploration” phase) the algorithm explores the state space through keeping track of previously visited states by maintaining an archive. During this phase, instead of resuming the exploration from scratch, the algorithm starts exploring from promising states in the archive to find high performing trajectories. In phase 2 (also referred to as the “robustification” phase, while in our variant we will call it “generalization”) the algorithm trains a policy using the trajectories found in phase 1. Following this framework, which is also shown in Figure FIGREF56 (Appendix A.2), we define the Go-Explore phases for text-based games. Let us first define text-based games using the same notation as BIBREF8. A text-based game can be framed as a discrete-time Partially Observable Markov Decision Process (POMDP) BIBREF31 defined by $(S, T, A, \Omega , O, R)$, where: $S$ is the set of the environment states, $T$ is the state transition function that defines the next state probability, i.e. $T(s_{t+1}|a_t;s_t) \forall s_t\in S$, $A$ is the set of actions, which in our case is all the possible sequences of tokens, $\Omega $ is the set of observations, i.e. text observed by the agent every time has it to take an action in the game (i.e. dialogue turn) which is controlled by the conditional observation probability $O$, i.e. $O(o_t|s_t, a_{t-1})$, and, finally, $R$ is the reward function i.e. $r=R(s,a)$. Let us also define the observation $o_t \in \Omega $ and the action $a_t \in A$. Text-based games provide some information in plain text at each turn and, without loss of generality, we define an observation $o_t$ as the sequence of tokens $\lbrace o_t^0,\cdots ,o_t^n\rbrace $ that form that text. Similarly, we define the tokens of an action $a_t$ as the sequence $\lbrace a_t^0,\cdots ,a_t^m\rbrace $. Furthermore, we define the set of admissible actions $\mathcal {A}_t \in A$ as $\mathcal {A}_t=\lbrace a_0,\cdots ,a_z\rbrace $, where each $a_i$, which is a sequence of tokens, is grammatically correct and admissible with reference to the observation $o_t$. Methodology ::: Phase 1: Exploration In phase 1, Go-Explore builds an archive of cells, where a cell is defined as a set of observations that are mapped to the same, discrete representation by some mapping function $f(x)$. Each cell is associated with meta-data including the trajectory towards that cell, the length of that trajectory, and the cumulative reward of that trajectory. New cells are added to the archive when they are encountered in the environment, and existing cells are updated with new meta-data when the trajectory towards that cells is higher scoring or equal scoring but shorter. At each iteration the algorithm selects a cell from this archive based on meta-data of the cell (e.g. the accumulated reward, etc.) and starts to randomly explore from the end of the trajectory associated with the selected cell. Phase 1 requires three components: the way that observations are embedded into cell representations, the cell selection, and the way actions are randomly selected when exploring from a selected cell. In our variant of the algorithm, $f(x)$ is defined as follows: given an observation, we compute the word embedding for each token in this observation, sum these embeddings, and then concatenate this sum with the current cumulative reward to construct the cell representation. The resulting vectors are subsequently compressed and discretized by binning them in order to map similar observations to the same cell. This way, the cell representation, which is the key of the archive, incorporates information about the current observation of the game. Adding the current cumulative reward to the cell representation is new to our Go-Explore variant as in the original algorithm only down-scaled image pixels were used. It turned out to be a very very effective to increase the speed at which high reward trajectories are discovered. In phase 1, we restrict the action space to the set of admissible actions $\mathcal {A}_t$ that are provided by the game at every step of the game . This too is particularly important for the random search to find a high reward trajectory faster. Finally, we denote the trajectory found in phase 1 for game $g$ as $\mathcal {T}_g= [(o_0, a_0, r_0), \cdots , (o_t,a_t,r_t)]$. Methodology ::: Phase 2: Generalization Phase 2 of Go-Explore uses the trajectories found in phase 1 and trains a policy based on those trajectories. The goal of this phase in the original Go-Explore algorithm is to turn the fragile policy of playing a trajectory of actions in sequence into a more robust, state-conditioned policy that can thus deal with environmental stochasticity. In our variant of the algorithm the purpose of the second phase is generalization: although in our environment there is no stochasticity, our goal is to learn a general policy that can be applied across different games and generalize to unseen games. In the original Go-Explore implementation, the authors used the backward Proximal Policy Optimization algorithm (PPO) BIBREF32, BIBREF33 to train this policy. In this work we opt for a simple but effective Seq2Seq imitation learning approach that does not use the reward directly in the loss. More specifically, given the trajectory $\mathcal {T}_g$, we train a Seq2Seq model to minimize the negative log-likelihood of the action $a_t$ given the observation $o_t$. In other words, consider a word embedding matrix $E \in \mathbb {R}^{d \times |V|}$ where $d$ is the embedding size and $|V|$ is the cardinality of the vocabulary, which maps the input token to an embedded vector. Then, we define an encoder LSTM$_{enc}$ and a decoder LSTM$_{dec}$. Every token $o_t$ from the trajectory $\mathcal {T}_g$ is converted to its embedded representation using the embedding matrix $E$ and the sequence of these embedding vectors is passed through LSTM$_{enc}$: The last hidden state $h_{|o_t|}^{enc}$ is used as the initial hidden state of the decoder which generates the action $a_t$ token by token. Specifically, given the sequence of hidden states $H \in \mathbb {R}^{d \times |o_t|}$ of the encoder, tokens $a_t^j$ are generated as follows: where $W \in \mathbb {R}^{2d \times |V|}$ is a matrix that maps the decoder hidden state, concatenated with the context vector, into a vocabulary size vector. During training, the parameters of the model are trained by minimizing: which is the sum of the negative log likelihood of each token in $a_t$ (using teacher forcing BIBREF34). However, at test time the model produces the sequence in an auto-regressive way BIBREF35 using greedy search. Experiments ::: Games and experiments setup A set of commonly used standard benchmarks BIBREF8, BIBREF3, BIBREF7 for agents that play text-based games are simple games which require no more than two words in each step to solve the game, and have a very limited number of admissible actions per observation. While simplifying, this setting limits the agent's ability to fully express natural language and learn more complex ways to speak. In this paper, we embrace more challenging environments where multiple words are needed at each step to solve the games and the reward is particularly sparse. Hence, we have selected the following environments: [leftmargin=*] CoinCollector BIBREF8 is a class of text-based games where the objective is to find and collect a coin from a specific location in a given set of connected rooms . The agent wins the game after it collects the coin, at which point (for the first and only time) a reward of +1 is received by the agent. The environment parses only five admissible commands (go north, go east, go south, go west, and take coin) made by two worlds; CookingWorld BIBREF14 in this challenge, there are 4,440 games with 222 different levels of difficulty, with 20 games per level of difficulty, each with different entities and maps. The goal of each game is to cook and eat food from a given recipe, which includes the task of collecting ingredients (e.g. tomato, potato, etc.), objects (e.g. knife), and processing them according to the recipe (e.g. cook potato, slice tomato, etc.). The parser of each game accepts 18 verbs and 51 entities with a predefined grammar, but the overall size of the vocabulary of the observations is 20,000. In Appendix SECREF36 we provide more details about the levels and the games' grammar. In our experiments, we try to address two major research questions. First, we want to benchmark the exploration power of phase 1 of Go-Explore in comparison to existing exploration approaches used in text-based games. For this purpose, we generate 10 CoinCollector games with the hardest setting used by BIBREF8, i.e. hard-level 30 (refer to the Appendix SECREF36 for more information) and use them as a benchmark. In fact, CoinCollector requires many actions (at least 30 on hard games) to find a reward, which makes it suitable for testing the exploration capabilities of different algorithms. Secondly, we want to verify the generalization ability of our model in creating complex strategies using natural language. CoinCollector has a very limited action space, and is mainly designed to benchmark models on their capability of dealing with sparse rewards. Therefore we use the more complex CookingWorld games to evaluate the generalization capabilities of our proposed approach. We design three different settings for CookingWorld: 1) Single: treat each game independently, which means we train and test one agent for each game to evaluate how robust different models are across different games.; 2) Joint: training and testing a single policy on all the 4,440 CookingWorld games at the same time to verify that models can learn to play multiple games at the same time; 3) Zero-Shot: split the games into training, validation, and test sets, and then train our policy on the training games and test it on the unseen test games. This setting is the hardest among all, since it requires generalization to unseen games. In both CoinCollector and CookingWorld games an observation $o_t$ provided by the environment consists of a room description $D$, inventory information $I$, quest $Q$, previous action $P$ and feedback $F$ provided in the previous turn. Table TABREF3 shows an example for each of these components. In our experiments for phase 1 of Go-Explore we only use $D$ as the observation. Experiments ::: Baselines For the CoinCollector games, we compared Go-Explore with the episodic discovery bonus BIBREF30 that was used by BIBREF8 to improve two Q-learning-based baselines: DQN++ and DRQN++. We used the code provided by the authors and the same hyper-parameters. For the CookingWorld games, we implemented three different treatments based on two existing methods: [leftmargin=*] LSTM-DQN BIBREF7, BIBREF8: An LSTM based state encoder with a separate $Q$-functions for each component (word) of a fixed pattern of Verb, Adjective1, Noun1, Adjective2, and Noun2. In this approach, given the observation $o_t$, the tokens are first converted into embeddings, then an LSTM is used to extract a sequence of hidden states $H_{dqn}\in \mathbb {R}^{d \times |o_t|}$. A mean-pool layer is applied to $H_{dqn}$ to produce a single vector $h_{o^t}$ that represents the whole sequence. Next, a linear transformation $W_{\text{type}}\in \mathbb {R}^{d \times |V_{\text{type}}|}$ is used to generate each of the Q values, where $|V_{\text{type}}| \ll |V|$ is the subset of the original vocabulary restricted to the word type of a particular game (e.g for Verb type: take, drop, etc.). Formally, we have: Next, all the $Q$-functions are jointly trained using the DQN algorithm with $\epsilon $-greedy exploration BIBREF15, BIBREF16. At evaluation time, the argmax of each $Q$-function is concatenated to produce $a_t$. Importantly, in $V_{\text{type}}$ a special token $<$s$>$ is used to denote the absence of a word, so the model can produce actions with different lengths. Figure FIGREF57 in Appendix SECREF55 shows a depiction of this model. LSTM-DQN+ADM: It is the same model as LSTM-DQN, except that the random actions for $\epsilon $-greedy exploration are sampled from the set of admissible actions instead of creating them by sampling each word separately. DRRN BIBREF10: In this approach a model learns how to score admissible actions instead of directly generating the action token by token. The policy uses an LSTM for encoding the observation and actions are represented as the sum of the embedding of the word tokens they contain. Then, the $Q$ value is defined as the dot product between the embedded representations of the observation and the action. Following the aforementioned notation, $h_{o^t}$ is generated as in the LSTM-DQN baseline. Next, we define its embedded representation as $c_i=\sum _k^{|a_i|} E(a_i^k)$, where $E$ is an embedding matrix as in Equation 1. Thus, the $Q$-function is defined as: At testing time the action with the highest $Q$ value is chosen. Figure FIGREF58 in Appendix SECREF55 shows a depiction of this model. Experiments ::: Hyper-parameters In all the games the maximum number of steps has been set to 50. As mentioned earlier, the cell representation used in the Go-Explore archive is computed by the sum of embeddings of the room description tokens concatenated with the current cumulative reward. The sum of embeddings is computed using 50 dimensional pre-trained GloVe BIBREF36 vectors. In the CoinCollector baselines we use the same hyper-parameters as in the original paper. In CookingWorld all the baselines use pre-trained GloVe of dimension 100 for the single setting and 300 for the joint one. The LSTM hidden state has been set to 300 for all the models. Results ::: CoinCollector In this setting, we compare the number of actions played in the environment (frames) and the score achieved by the agent (i.e. +1 reward if the coin is collected). In Go-Explore we also count the actions used to restore the environment to a selected cell, i.e. to bring the agent to the state represented in the selected cell. This allows a one-to-one comparison of the exploration efficiency between Go-Explore and algorithms that use a count-based reward in text-based games. Importantly, BIBREF8 showed that DQN and DRQN, without such counting rewards, could never find a successful trajectory in hard games such as the ones used in our experiments. Figure FIGREF17 shows the number of interactions with the environment (frames) versus the maximum score obtained, averaged over 10 games of the same difficulty. As shown by BIBREF8, DRQN++ finds a trajectory with the maximum score faster than to DQN++. On the other hand, phase 1 of Go-Explore finds an optimal trajectory with approximately half the interactions with the environment. Moreover, the trajectory length found by Go-Explore is always optimal (i.e. 30 steps) whereas both DQN++ and DRQN++ have an average length of 38 and 42 respectively. Results ::: CookingWorld In CookingWorld, we compared models in the three settings mentioned earlier, namely, single, joint, and zero-shot. In all experiments, we measured the sum of the final scores of all the games and their trajectory length (number of steps). Table TABREF26 summarizes the results in these three settings. Phase 1 of Go-Explore on single games achieves a total score of 19,530 (sum over all games), which is very close to the maximum possible points (i.e. 19,882), with 47,562 steps. A winning trajectory was found in 4,279 out of the total of 4,440 games. This result confirms again that the exploration strategy of Go-Explore is effective in text-based games. Next, we evaluate the effectiveness and the generalization ability of the simple imitation learning policy trained using the extracted trajectories in phase 1 of Go-Explore in the three settings mentioned above. Results ::: CookingWorld ::: Single In this setting, each model is trained from scratch in each of the 4,440 games based on the trajectory found in phase 1 of Go-Explore (previous step). As shown in Table TABREF26, the LSTM-DQN BIBREF7, BIBREF8 approach without the use of admissible actions performs poorly. One explanation for this could be that it is difficult for this model to explore both language and game strategy at the same time; it is hard for the model to find a reward signal before it has learned to model language, since almost none of its actions will be admissible, and those reward signals are what is necessary in order to learn the language model. As we see in Table TABREF26, however, by using the admissible actions in the $\epsilon $-greedy step the score achieved by the LSTM-DQN increases dramatically (+ADM row in Table TABREF26). DRRN BIBREF10 achieves a very high score, since it explicitly learns how to rank admissible actions (i.e. a much simpler task than generating text). Finally, our approach of using a Seq2Seq model trained on the single trajectory provided by phase 1 of Go-Explore achieves the highest score among all the methods, even though we do not use admissible actions in this phase. However, in this experiment the Seq2Seq model cannot perfectly replicate the provided trajectory and the total score that it achieves is in fact 9.4% lower compared to the total score achieved by phase 1 of Go-Explore. Figure FIGREF61 (in Appendix SECREF60) shows the score breakdown for each level and model, where we can see that the gap between our model and other methods increases as the games become harder in terms of skills needed. Results ::: CookingWorld ::: Joint In this setting, a single model is trained on all the games at the same time, to test whether one agent can learn to play multiple games. Overall, as expected, all the evaluated models achieved a lower performance compared to the single game setting. One reason for this could be that learning multiple games at the same time leads to a situation where the agent encounters similar observations in different games, and the correct action to take in different games may be different. Furthermore, it is important to note that the order in which games are presented greatly affects the performance of LSTM-DQN and DRRN. In our experiments, we tried both an easy-to-hard curriculum (i.e. sorting the games by increasing level of difficulty) and a shuffled curriculum. Shuffling the games at each epoch resulted in far better performance, thus we only report the latter. In Figure FIGREF28 we show the score breakdown, and we can see that all the baselines quickly fail, even for easier games. Results ::: CookingWorld ::: Zero-Shot In this setting the 4,440 games are split into training, validation, and test games. The split is done randomly but in a way that different difficulty levels (recipes 1, 2 and 3), are represented with equal ratios in all the 3 splits, i.e. stratified by difficulty. As shown in Table TABREF26, the zero-shot performance of the RL baselines is poor, which could be attributed to the same reasons why RL baselines under-perform in the Joint case. Especially interesting is that the performance of DRRN is substantially lower than that of the Go-Explore Seq2Seq model, even though the DRRN model has access to the admissible actions at test time, while the Seq2Seq model (as well as the LSTM-DQN model) has to construct actions token-by-token from the entire vocabulary of 20,000 tokens. On the other hand, Go-Explore Seq2Seq shows promising results by solving almost half of the unseen games. Figure FIGREF62 (in Appendix SECREF60) shows that most of the lost games are in the hardest set, where a very long sequence of actions is required for winning the game. These results demonstrate both the relative effectiveness of training a Seq2Seq model on Go-Explore trajectories, but they also indicate that additional effort needed for designing reinforcement learning algorithms that effectively generalize to unseen games. Discussion Experimental results show that our proposed Go-Explore exploration strategy is a viable methodology for extracting high-performing trajectories in text-based games. This method allows us to train supervised models that can outperform existing models in the experimental settings that we study. Finally, there are still several challenges and limitations that both our methodology and previous solutions do not fully address yet. For instance: Discussion ::: State Representation The state representation is the main limitation of our proposed imitation learning model. In fact, by examining the observations provided in different games, we notice a large overlap in the descriptions ($D$) of the games. This overlap leads to a situation where the policy receives very similar observations, but is expected to imitate two different actions. This show especially in the joint setting of CookingWorld, where the 222 games are repeated 20 times with different entities and room maps. In this work, we opted for a simple Seq2Seq model for our policy, since our goal is to show the effectiveness of our proposed exploration methods. However, a more complex Hierarchical-Seq2Seq model BIBREF37 or a better encoder representation based on knowledge graphs BIBREF38, BIBREF39 would likely improve the of performance this approach. Discussion ::: Language Based Exploration In Go-Explore, the given admissible actions are used during random exploration. However, in more complex games, e.g. Zork I and in general the Z-Machine games, these admissible actions are not provided. In such settings, the action space would explode in size, and thus Go-Explore, even with an appropriate cell representation, would have a hard time finding good trajectories. To address this issue one could leverage general language models to produce a set of grammatically correct actions. Alternatively one could iteratively learn a policy to sample actions, while exploring with Go-Explore. Both strategies are viable, and a comparison is left to future work. It is worth noting that a hand-tailored solution for the CookingWorld games has been proposed in the “First TextWorld Problems” competition BIBREF3. This solution managed to obtain up to 91.9% of the maximum possible score across the 514 test games on an unpublished dataset. However, this solution relies on entity extraction and template filling, which we believe limits its potential for generalization. Therefore, this approach should be viewed as complementary rather than competitor to our approach as it could potentially be used as an alternative way of getting promising trajectories. Conclusion In this paper we presented a novel methodology for solving text-based games which first extracts high-performing trajectories using phase 1 of Go-Explore and then trains a simple Seq2Seq model that maps observations to actions using the extracted trajectories. Our experiments show promising results in three settings, with improved generalization and sample efficiency compared to existing methods. Finally, we discussed the limitations and possible improvements of our methodology, which leads to new research challenges in text-based games. Appendix ::: Text-Games ::: CoinCollector In the hard setting (mode 2), each room on the path to the coin has two distractor rooms, and the level (e.g. 30) indicates the shortest path from the starting point to the coin room. Appendix ::: Text-Games ::: CookingWorld The game's complexity is determined by the number of skills and the types of skills that an agent needs to master. The skills are: recipe {1,2,3}: number of ingredients in the recipe take {1,2,3}: number of ingredients to find (not already in the inventory) open: whether containers/doors need to be opened cook: whether ingredients need to be cooked cut: whether ingredients need to be cut drop: whether the inventory has limited capacity go {1,6,9,12}: number of locations Thus the hardest game would be a recipe with 3 ingredients, which must all be picked up somewhere across 12 locations and then need to be cut and cooked, and to get access to some locations, several doors or objects need to be opened. The handicap of a limited capacity in the inventory makes the game more difficult by requiring the agent to drop an object and later on take it again if needed. The grammar used for the text-based games is the following: go, look, examine, inventory, eat, open/close, take/drop, put/insert cook X with Y $\longrightarrow $ grilled X (when Y is the BBQ) cook X with Y $\longrightarrow $ roasted X (when Y is the oven) cook X with Y $\longrightarrow $ fried X (when Y is the stove) slice X with Y $\longrightarrow $ sliced X chop X with Y $\longrightarrow $ chopped X dice X with Y $\longrightarrow $ diced X prepare meal Where Y is something sharp (e.g. knife).
How better does new approach behave than existing solutions?
df0257ab04686ddf1c6c4d9b0529a7632330b98e
How Ġbetter Ġdoes Ġnew Ġapproach Ġbehave Ġthan Ġexisting Ġsolutions ?
ĠOn Ġthe Ġother Ġhand , Ġphase Ġ1 Ġof ĠGo - Explore Ġfinds Ġan Ġoptimal Ġtrajectory Ġwith Ġapproximately Ġhalf Ġthe Ġinteractions Ġwith Ġthe Ġenvironment , ĠMoreover , Ġthe Ġtrajectory Ġlength Ġfound Ġby ĠGo - Explore Ġis Ġalways Ġoptimal Ġ( i . e . Ġ30 Ġsteps ) Ġwhereas Ġboth ĠD Q N ++ Ġand ĠDR Q N ++ Ġhave Ġan Ġaverage Ġlength Ġof Ġ38 Ġand Ġ42 Ġrespectively ., ĠEspecially Ġinteresting Ġis Ġthat Ġthe Ġperformance Ġof ĠDR RN Ġis Ġsubstantially Ġlower Ġthan Ġthat Ġof Ġthe ĠGo - Explore ĠSe q 2 Se q Ġmodel
<s> How Ġbetter Ġdoes Ġnew Ġapproach Ġbehave Ġthan Ġexisting Ġsolutions ? </s> Introduction </s> Text - based Ġgames Ġbecame Ġpopular Ġin Ġthe Ġmid Ġ80 s Ġwith Ġthe Ġgame Ġseries ĠZ ork ĠB IB REF 1 Ġresulting Ġin Ġmany Ġdifferent Ġtext - based Ġgames Ġbeing Ġproduced Ġand Ġpublished ĠB IB REF 2 . ĠThese Ġgames Ġuse Ġa Ġplain Ġtext Ġdescription Ġof Ġthe Ġenvironment Ġand Ġthe Ġplayer Ġhas Ġto Ġinteract Ġwith Ġthem Ġby Ġwriting Ġnatural - language Ġcommands . ĠRecently , Ġthere Ġhas Ġbeen Ġa Ġgrowing Ġinterest Ġin Ġdeveloping Ġagents Ġthat Ġcan Ġautomatically Ġsolve Ġtext - based Ġgames ĠB IB REF 3 Ġby Ġinteracting Ġwith Ġthem . ĠThese Ġsettings Ġchallenge Ġthe Ġability Ġof Ġan Ġartificial Ġagent Ġto Ġunderstand Ġnatural Ġlanguage , Ġcommon Ġsense Ġknowledge , Ġand Ġto Ġdevelop Ġthe Ġability Ġto Ġinteract Ġwith Ġenvironments Ġusing Ġlanguage ĠB IB REF 4 , ĠB IB REF 5 . </s> Since Ġthe Ġactions Ġin Ġthese Ġgames Ġare Ġcommands Ġthat Ġare Ġin Ġnatural Ġlanguage Ġform , Ġthe Ġmajor Ġobstacle Ġis Ġthe Ġextremely Ġlarge Ġaction Ġspace Ġof Ġthe Ġagent , Ġwhich Ġleads Ġto Ġa Ġcomb inator ially Ġlarge Ġexploration Ġproblem . ĠIn Ġfact , Ġwith Ġa Ġvocabulary Ġof Ġ$ N $ Ġwords Ġ( e . g . Ġ20 K ) Ġand Ġthe Ġpossibility Ġof Ġproducing Ġsentences Ġwith Ġat Ġmost Ġ$ m $ Ġwords Ġ( e . g . Ġ7 Ġwords ), Ġthe Ġtotal Ġnumber Ġof Ġactions Ġis Ġ$ O ( N ^ m ) $ Ġ( e . g . Ġ20 K $ ^ 7 Ġ\ app rox Ġ1 . 28 Ġe ^{ 30 } $ ). ĠTo Ġavoid Ġthis Ġlarge Ġaction Ġspace , Ġseveral Ġexisting Ġsolutions Ġfocus Ġon Ġsimpler Ġtext - based Ġgames Ġwith Ġvery Ġsmall Ġvoc ab ular ies Ġwhere Ġthe Ġaction Ġspace Ġis Ġconstrained Ġto Ġverb - object Ġpairs ĠB IB REF 6 , ĠB IB REF 7 , ĠB IB REF 8 , ĠB IB REF 9 . ĠMoreover , Ġmany Ġexisting Ġworks Ġrely Ġon Ġusing Ġpredetermined Ġsets Ġof Ġad missible Ġactions ĠB IB REF 10 , ĠB IB REF 11 , ĠB IB REF 12 . ĠHowever , Ġa Ġmore Ġideal , Ġand Ġstill Ġunder Ġexplored , Ġalternative Ġwould Ġbe Ġan Ġagent Ġthat Ġcan Ġoperate Ġin Ġthe Ġfull , Ġuncon str ained Ġaction Ġspace Ġof Ġnatural Ġlanguage Ġthat Ġcan Ġsystematically Ġgeneral ize Ġto Ġnew Ġtext - based Ġgames Ġwith Ġno Ġor Ġfew Ġinteractions Ġwith Ġthe Ġenvironment . </s> To Ġaddress Ġthis Ġchallenge , Ġwe Ġpropose Ġto Ġuse Ġthe Ġidea Ġbehind Ġthe Ġrecently Ġproposed ĠGo - Explore ĠB IB REF 0 Ġalgorithm . ĠSpecifically , Ġwe Ġpropose Ġto Ġfirst Ġextract Ġhigh Ġreward Ġtraject ories Ġof Ġstates Ġand Ġactions Ġin Ġthe Ġgame Ġusing Ġthe Ġexploration Ġmethodology Ġproposed Ġin ĠGo - Explore Ġand Ġthen Ġtrain Ġa Ġpolicy Ġusing Ġa ĠSe q 2 Se q ĠB IB REF 13 Ġmodel Ġthat Ġmaps Ġobservations Ġto Ġactions , Ġin Ġan Ġimitation Ġlearning Ġfashion . ĠTo Ġshow Ġthe Ġeffectiveness Ġof Ġour Ġproposed Ġmethodology , Ġwe Ġfirst Ġbenchmark Ġthe Ġexploration Ġability Ġof ĠGo - Explore Ġon Ġthe Ġfamily Ġof Ġtext - based Ġgames Ġcalled ĠCoin Collect or ĠB IB REF 8 . ĠThen Ġwe Ġuse Ġthe Ġ4 , 440 Ġgames Ġof ĠâĢ ľ First ĠText World ĠProblems âĢ Ŀ ĠB IB REF 14 , Ġwhich Ġare Ġgenerated Ġusing Ġthe Ġmachinery Ġintroduced Ġby ĠB IB REF 3 , Ġto Ġshow Ġthe Ġgeneral ization Ġability Ġof Ġour Ġproposed Ġmethodology . ĠIn Ġthe Ġformer Ġexperiment Ġwe Ġshow Ġthat ĠGo - Explore Ġfinds Ġwinning Ġtraject ories Ġfaster Ġthan Ġexisting Ġsolutions , Ġand Ġin Ġthe Ġlatter , Ġwe Ġshow Ġthat Ġtraining Ġa ĠSe q 2 Se q Ġmodel Ġon Ġthe Ġtraject ories Ġfound Ġby ĠGo - Explore Ġresults Ġin Ġstronger Ġgeneral ization , Ġas Ġsuggested Ġby Ġthe Ġstronger Ġperformance Ġon Ġunseen Ġgames , Ġcompared Ġto Ġexisting Ġcompetitive Ġbas elines ĠB IB REF 10 , ĠB IB REF 7 . </s> Introduction Ġ: :: ĠRein forcement ĠLearning ĠBased ĠAppro aches Ġfor ĠText - Based ĠGames </s> Among Ġreinforcement Ġlearning Ġbased Ġefforts Ġto Ġsolve Ġtext - based Ġgames Ġtwo Ġapproaches Ġare Ġprominent . ĠThe Ġfirst Ġapproach Ġassumes Ġan Ġaction Ġas Ġa Ġsentence Ġof Ġa Ġfixed Ġnumber Ġof Ġwords , Ġand Ġassociates Ġa Ġseparate Ġ$ Q $ - function ĠB IB REF 15 , ĠB IB REF 16 Ġwith Ġeach Ġword Ġposition Ġin Ġthis Ġsentence . ĠThis Ġmethod Ġwas Ġdemonstrated Ġwith Ġtwo - word Ġsentences Ġconsisting Ġof Ġa Ġverb - object Ġpair Ġ( e . g . Ġtake Ġapple ) ĠB IB REF 6 , ĠB IB REF 7 , ĠB IB REF 8 , ĠB IB REF 9 , ĠB IB REF 17 . ĠIn Ġthe Ġsecond Ġapproach , Ġone Ġ$ Q $ - function Ġthat Ġscores Ġall Ġpossible Ġactions Ġ( i . e . Ġsentences ) Ġis Ġlearned Ġand Ġused Ġto Ġplay Ġthe Ġgame ĠB IB REF 10 , ĠB IB REF 11 , ĠB IB REF 12 . ĠThe Ġfirst Ġapproach Ġis Ġquite Ġlimiting Ġsince Ġa Ġfixed Ġnumber Ġof Ġwords Ġmust Ġbe Ġselected Ġin Ġadvance Ġand Ġno Ġtemporal Ġdependency Ġis Ġenforced Ġbetween Ġwords Ġ( e . g . Ġlack Ġof Ġlanguage Ġmodelling ). ĠIn Ġthe Ġsecond Ġapproach , Ġon Ġthe Ġother Ġhand , Ġthe Ġnumber Ġof Ġpossible Ġactions Ġcan Ġbecome Ġexponentially Ġlarge Ġif Ġthe Ġad missible Ġactions Ġ( a Ġpredetermined Ġlow Ġcardinal ity Ġset Ġof Ġactions Ġthat Ġthe Ġagent Ġcan Ġtake ) Ġare Ġnot Ġprovided Ġto Ġthe Ġagent . ĠA Ġpossible Ġsolution Ġto Ġthis Ġissue Ġhas Ġbeen Ġproposed Ġby ĠB IB REF 18 , Ġwhere Ġa Ġhierarchical Ġpointer - gener ator Ġis Ġused Ġto Ġfirst Ġproduce Ġthe Ġset Ġof Ġad missible Ġactions Ġgiven Ġthe Ġobservation , Ġand Ġsubsequently Ġone Ġelement Ġof Ġthis Ġset Ġis Ġchosen Ġas Ġthe Ġaction Ġfor Ġthat Ġobservation . ĠHowever , Ġin Ġour Ġexperiments Ġwe Ġshow Ġthat Ġeven Ġin Ġsettings Ġwhere Ġthe Ġtrue Ġset Ġof Ġad missible Ġactions Ġis Ġprovided Ġby Ġthe Ġenvironment , Ġa Ġ$ Q $ - sc orer ĠB IB REF 10 Ġdoes Ġnot Ġgeneral ize Ġwell Ġin Ġour Ġsetting Ġ( Section Ġ5 . 2 ĠZero - Shot ) Ġand Ġwe Ġwould Ġexpect Ġperformance Ġto Ġdegrade Ġeven Ġfurther Ġif Ġthe Ġad missible Ġactions Ġwere Ġgenerated Ġby Ġa Ġseparate Ġmodel . ĠLess Ġcommon Ġare Ġmodels Ġthat Ġeither Ġlearn Ġto Ġreduce Ġa Ġlarge Ġset Ġof Ġactions Ġinto Ġa Ġsmaller Ġset Ġof Ġad missible Ġactions Ġby Ġeliminating Ġactions ĠB IB REF 12 Ġor Ġby Ġcomp ressing Ġthem Ġin Ġa Ġlatent Ġspace ĠB IB REF 11 . </s> Introduction Ġ: :: ĠExploration Ġin ĠRein forcement ĠLearning </s> In Ġmost Ġtext - based Ġgames Ġrewards Ġare Ġsparse , Ġsince Ġthe Ġsize Ġof Ġthe Ġaction Ġspace Ġmakes Ġthe Ġprobability Ġof Ġobserving Ġa Ġreward Ġextremely Ġlow Ġwhen Ġtaking Ġonly Ġrandom Ġactions . ĠSp arse Ġreward Ġenvironments Ġare Ġparticularly Ġchallenging Ġfor Ġreinforcement Ġlearning Ġas Ġthey Ġrequire Ġlonger Ġterm Ġplanning . ĠMany Ġexploration Ġbased Ġsolutions Ġhave Ġbeen Ġproposed Ġto Ġaddress Ġthe Ġchallenges Ġassociated Ġwith Ġreward Ġsp arsity . ĠAmong Ġthese Ġexploration Ġapproaches Ġare Ġnovelty Ġsearch ĠB IB REF 19 , ĠB IB REF 20 , ĠB IB REF 21 , ĠB IB REF 22 , ĠB IB REF 23 , Ġintrinsic Ġmotivation ĠB IB REF 24 , ĠB IB REF 25 , ĠB IB REF 26 , Ġand Ġcuriosity Ġbased Ġrewards ĠB IB REF 27 , ĠB IB REF 28 , ĠB IB REF 29 . ĠFor Ġtext Ġbased Ġgames Ġexploration Ġmethods Ġhave Ġbeen Ġstudied Ġby ĠB IB REF 8 , Ġwhere Ġthe Ġauthors Ġshowed Ġthe Ġeffectiveness Ġof Ġthe Ġepis odic Ġdiscovery Ġbonus ĠB IB REF 30 Ġin Ġenvironments Ġwith Ġsparse Ġrewards . ĠThis Ġexploration Ġmethod Ġcan Ġonly Ġbe Ġapplied Ġin Ġgames Ġwith Ġvery Ġsmall Ġaction Ġand Ġstate Ġspaces , Ġsince Ġtheir Ġcounting Ġmethods Ġrely Ġon Ġthe Ġstate Ġin Ġits Ġexplicit Ġraw Ġform . </s> Method ology </s> Go - Explore ĠB IB REF 0 Ġdiffers Ġfrom Ġthe Ġexploration - based Ġalgorithms Ġdiscussed Ġabove Ġin Ġthat Ġit Ġexplicitly Ġkeeps Ġtrack Ġof Ġunder - expl ored Ġareas Ġof Ġthe Ġstate Ġspace Ġand Ġin Ġthat Ġit Ġutilizes Ġthe Ġdetermin ism Ġof Ġthe Ġsimulator Ġin Ġorder Ġto Ġreturn Ġto Ġthose Ġstates , Ġallowing Ġit Ġto Ġexplore Ġsparse - re ward Ġenvironments Ġin Ġa Ġsample Ġefficient Ġway Ġ( see ĠB IB REF 0 Ġas Ġwell Ġas Ġsection ĠSEC REF 27 ). ĠFor Ġthe Ġexperiments Ġin Ġthis Ġpaper Ġwe Ġmainly Ġfocus Ġon Ġthe Ġfinal Ġperformance Ġof Ġour Ġpolicy , Ġnot Ġhow Ġthat Ġpolicy Ġis Ġtrained , Ġthus Ġmaking ĠGo - Explore Ġa Ġsuitable Ġalgorithm Ġfor Ġour Ġexperiments . ĠGo - Explore Ġis Ġcomposed Ġof Ġtwo Ġphases . ĠIn Ġphase Ġ1 Ġ( also Ġreferred Ġto Ġas Ġthe ĠâĢ ľ expl oration âĢ Ŀ Ġphase ) Ġthe Ġalgorithm Ġexplores Ġthe Ġstate Ġspace Ġthrough Ġkeeping Ġtrack Ġof Ġpreviously Ġvisited Ġstates Ġby Ġmaintaining Ġan Ġarchive . ĠDuring Ġthis Ġphase , Ġinstead Ġof Ġres uming Ġthe Ġexploration Ġfrom Ġscratch , Ġthe Ġalgorithm Ġstarts Ġexploring Ġfrom Ġpromising Ġstates Ġin Ġthe Ġarchive Ġto Ġfind Ġhigh Ġperforming Ġtraject ories . ĠIn Ġphase Ġ2 Ġ( also Ġreferred Ġto Ġas Ġthe ĠâĢ ľ rob ust ification âĢ Ŀ Ġphase , Ġwhile Ġin Ġour Ġvariant Ġwe Ġwill Ġcall Ġit ĠâĢ ľ general ization âĢ Ŀ ) Ġthe Ġalgorithm Ġtrains Ġa Ġpolicy Ġusing Ġthe Ġtraject ories Ġfound Ġin Ġphase Ġ1 . ĠFollowing Ġthis Ġframework , Ġwhich Ġis Ġalso Ġshown Ġin ĠFigure ĠFIG REF 56 Ġ( App endix ĠA . 2 ), Ġwe Ġdefine Ġthe ĠGo - Explore Ġphases Ġfor Ġtext - based Ġgames . </s> Let Ġus Ġfirst Ġdefine Ġtext - based Ġgames Ġusing Ġthe Ġsame Ġnotation Ġas ĠB IB REF 8 . ĠA Ġtext - based Ġgame Ġcan Ġbe Ġframed Ġas Ġa Ġdiscrete - time ĠPart ially ĠObserv able ĠMark ov ĠDecision ĠProcess Ġ( P OM DP ) ĠB IB REF 31 Ġdefined Ġby Ġ$( S , ĠT , ĠA , Ġ\ O mega Ġ, ĠO , ĠR ) $, Ġwhere : Ġ$ S $ Ġis Ġthe Ġset Ġof Ġthe Ġenvironment Ġstates , Ġ$ T $ Ġis Ġthe Ġstate Ġtransition Ġfunction Ġthat Ġdefines Ġthe Ġnext Ġstate Ġprobability , Ġi . e . Ġ$ T ( s _{ t + 1 } | a _ t ; s _ t ) Ġ\ for all Ġs _ t \ in ĠS $, Ġ$ A $ Ġis Ġthe Ġset Ġof Ġactions , Ġwhich Ġin Ġour Ġcase Ġis Ġall Ġthe Ġpossible Ġsequences Ġof Ġtokens , Ġ$\ O mega Ġ$ Ġis Ġthe Ġset Ġof Ġobservations , Ġi . e . Ġtext Ġobserved Ġby Ġthe Ġagent Ġevery Ġtime Ġhas Ġit Ġto Ġtake Ġan Ġaction Ġin Ġthe Ġgame Ġ( i . e . Ġdialogue Ġturn ) Ġwhich Ġis Ġcontrolled Ġby Ġthe Ġconditional Ġobservation Ġprobability Ġ$ O $, Ġi . e . Ġ$ O ( o _ t | s _ t , Ġa _{ t - 1 }) $, Ġand , Ġfinally , Ġ$ R $ Ġis Ġthe Ġreward Ġfunction Ġi . e . Ġ$ r = R ( s , a ) $. </s> Let Ġus Ġalso Ġdefine Ġthe Ġobservation Ġ$ o _ t Ġ\ in Ġ\ O mega Ġ$ Ġand Ġthe Ġaction Ġ$ a _ t Ġ\ in ĠA $. ĠText - based Ġgames Ġprovide Ġsome Ġinformation Ġin Ġplain Ġtext Ġat Ġeach Ġturn Ġand , Ġwithout Ġloss Ġof Ġgener ality , Ġwe Ġdefine Ġan Ġobservation Ġ$ o _ t $ Ġas Ġthe Ġsequence Ġof Ġtokens Ġ$\ l brace Ġo _ t ^ 0 , \ cd ots Ġ, o _ t ^ n \ r brace Ġ$ Ġthat Ġform Ġthat Ġtext . ĠSimilarly , Ġwe Ġdefine Ġthe Ġtokens Ġof Ġan Ġaction Ġ$ a _ t $ Ġas Ġthe Ġsequence Ġ$\ l brace Ġa _ t ^ 0 , \ cd ots Ġ, a _ t ^ m \ r brace Ġ$ . ĠFurthermore , Ġwe Ġdefine Ġthe Ġset Ġof Ġad missible Ġactions Ġ$\ math cal Ġ{ A } _ t Ġ\ in ĠA $ Ġas Ġ$\ math cal Ġ{ A } _ t = \ l brace Ġa _ 0 , \ cd ots Ġ, a _ z \ r brace Ġ$ , Ġwhere Ġeach Ġ$ a _ i $, Ġwhich Ġis Ġa Ġsequence Ġof Ġtokens , Ġis Ġgram matically Ġcorrect Ġand Ġad missible Ġwith Ġreference Ġto Ġthe Ġobservation Ġ$ o _ t $. </s> Method ology Ġ: :: ĠPhase Ġ1 : ĠExploration </s> In Ġphase Ġ1 , ĠGo - Explore Ġbuilds Ġan Ġarchive Ġof Ġcells , Ġwhere Ġa Ġcell Ġis Ġdefined Ġas Ġa Ġset Ġof Ġobservations Ġthat Ġare Ġmapped Ġto Ġthe Ġsame , Ġdiscrete Ġrepresentation Ġby Ġsome Ġmapping Ġfunction Ġ$ f ( x ) $. ĠEach Ġcell Ġis Ġassociated Ġwith Ġmeta - data Ġincluding Ġthe Ġtrajectory Ġtowards Ġthat Ġcell , Ġthe Ġlength Ġof Ġthat Ġtrajectory , Ġand Ġthe Ġcumulative Ġreward Ġof Ġthat Ġtrajectory . ĠNew Ġcells Ġare Ġadded Ġto Ġthe Ġarchive Ġwhen Ġthey Ġare Ġencountered Ġin Ġthe Ġenvironment , Ġand Ġexisting Ġcells Ġare Ġupdated Ġwith Ġnew Ġmeta - data Ġwhen Ġthe Ġtrajectory Ġtowards Ġthat Ġcells Ġis Ġhigher Ġscoring Ġor Ġequal Ġscoring Ġbut Ġshorter . </s> At Ġeach Ġiteration Ġthe Ġalgorithm Ġselects Ġa Ġcell Ġfrom Ġthis Ġarchive Ġbased Ġon Ġmeta - data Ġof Ġthe Ġcell Ġ( e . g . Ġthe Ġaccumulated Ġreward , Ġetc .) Ġand Ġstarts Ġto Ġrandomly Ġexplore Ġfrom Ġthe Ġend Ġof Ġthe Ġtrajectory Ġassociated Ġwith Ġthe Ġselected Ġcell . ĠPhase Ġ1 Ġrequires Ġthree Ġcomponents : Ġthe Ġway Ġthat Ġobservations Ġare Ġembedded Ġinto Ġcell Ġrepresentations , Ġthe Ġcell Ġselection , Ġand Ġthe Ġway Ġactions Ġare Ġrandomly Ġselected Ġwhen Ġexploring Ġfrom Ġa Ġselected Ġcell . ĠIn Ġour Ġvariant Ġof Ġthe Ġalgorithm , Ġ$ f ( x ) $ Ġis Ġdefined Ġas Ġfollows : Ġgiven Ġan Ġobservation , Ġwe Ġcompute Ġthe Ġword Ġembed ding Ġfor Ġeach Ġtoken Ġin Ġthis Ġobservation , Ġsum Ġthese Ġembed d ings , Ġand Ġthen Ġconc aten ate Ġthis Ġsum Ġwith Ġthe Ġcurrent Ġcumulative Ġreward Ġto Ġconstruct Ġthe Ġcell Ġrepresentation . ĠThe Ġresulting Ġvectors Ġare Ġsubsequently Ġcompressed Ġand Ġdisc ret ized Ġby Ġbin ning Ġthem Ġin Ġorder Ġto Ġmap Ġsimilar Ġobservations Ġto Ġthe Ġsame Ġcell . ĠThis Ġway , Ġthe Ġcell Ġrepresentation , Ġwhich Ġis Ġthe Ġkey Ġof Ġthe Ġarchive , Ġincorporates Ġinformation Ġabout Ġthe Ġcurrent Ġobservation Ġof Ġthe Ġgame . ĠAdding Ġthe Ġcurrent Ġcumulative Ġreward Ġto Ġthe Ġcell Ġrepresentation Ġis Ġnew Ġto Ġour ĠGo - Explore Ġvariant Ġas Ġin Ġthe Ġoriginal Ġalgorithm Ġonly Ġdown - sc aled Ġimage Ġpixels Ġwere Ġused . ĠIt Ġturned Ġout Ġto Ġbe Ġa Ġvery Ġvery Ġeffective Ġto Ġincrease Ġthe Ġspeed Ġat Ġwhich Ġhigh Ġreward Ġtraject ories Ġare Ġdiscovered . ĠIn Ġphase Ġ1 , Ġwe Ġrestrict Ġthe Ġaction Ġspace Ġto Ġthe Ġset Ġof Ġad missible Ġactions Ġ$\ math cal Ġ{ A } _ t $ Ġthat Ġare Ġprovided Ġby Ġthe Ġgame Ġat Ġevery Ġstep Ġof Ġthe Ġgame Ġ. ĠThis Ġtoo Ġis Ġparticularly Ġimportant Ġfor Ġthe Ġrandom Ġsearch Ġto Ġfind Ġa Ġhigh Ġreward Ġtrajectory Ġfaster . ĠFinally , Ġwe Ġdenote Ġthe Ġtrajectory Ġfound Ġin Ġphase Ġ1 Ġfor Ġgame Ġ$ g $ Ġas Ġ$\ math cal Ġ{ T } _ g = Ġ[( o _ 0 , Ġa _ 0 , Ġr _ 0 ), Ġ\ cd ots Ġ, Ġ( o _ t , a _ t , r _ t )] $. </s> Method ology Ġ: :: ĠPhase Ġ2 : ĠGeneral ization </s> Phase Ġ2 Ġof ĠGo - Explore Ġuses Ġthe Ġtraject ories Ġfound Ġin Ġphase Ġ1 Ġand Ġtrains Ġa Ġpolicy Ġbased Ġon Ġthose Ġtraject ories . ĠThe Ġgoal Ġof Ġthis Ġphase Ġin Ġthe Ġoriginal ĠGo - Explore Ġalgorithm Ġis Ġto Ġturn Ġthe Ġfragile Ġpolicy Ġof Ġplaying Ġa Ġtrajectory Ġof Ġactions Ġin Ġsequence Ġinto Ġa Ġmore Ġrobust , Ġstate - condition ed Ġpolicy Ġthat Ġcan Ġthus Ġdeal Ġwith Ġenvironmental Ġsto ch astic ity . ĠIn Ġour Ġvariant Ġof Ġthe Ġalgorithm Ġthe Ġpurpose Ġof Ġthe Ġsecond Ġphase Ġis Ġgeneral ization : Ġalthough Ġin Ġour Ġenvironment Ġthere Ġis Ġno Ġsto ch astic ity , Ġour Ġgoal Ġis Ġto Ġlearn Ġa Ġgeneral Ġpolicy Ġthat Ġcan Ġbe Ġapplied Ġacross Ġdifferent Ġgames Ġand Ġgeneral ize Ġto Ġunseen Ġgames . ĠIn Ġthe Ġoriginal ĠGo - Explore Ġimplementation , Ġthe Ġauthors Ġused Ġthe Ġbackward ĠPro x imal ĠPolicy ĠOptim ization Ġalgorithm Ġ( PP O ) ĠB IB REF 32 , ĠB IB REF 33 Ġto Ġtrain Ġthis Ġpolicy . ĠIn Ġthis Ġwork Ġwe Ġopt Ġfor Ġa Ġsimple Ġbut Ġeffective ĠSe q 2 Se q Ġimitation Ġlearning Ġapproach Ġthat Ġdoes Ġnot Ġuse Ġthe Ġreward Ġdirectly Ġin Ġthe Ġloss . ĠMore Ġspecifically , Ġgiven Ġthe Ġtrajectory Ġ$\ math cal Ġ{ T } _ g $, Ġwe Ġtrain Ġa ĠSe q 2 Se q Ġmodel Ġto Ġminimize Ġthe Ġnegative Ġlog - like lihood Ġof Ġthe Ġaction Ġ$ a _ t $ Ġgiven Ġthe Ġobservation Ġ$ o _ t $. ĠIn Ġother Ġwords , Ġconsider Ġa Ġword Ġembed ding Ġmatrix Ġ$ E Ġ\ in Ġ\ math bb Ġ{ R } ^{ d Ġ\ times Ġ| V | } $ Ġwhere Ġ$ d $ Ġis Ġthe Ġembed ding Ġsize Ġand Ġ$ | V | $ Ġis Ġthe Ġcardinal ity Ġof Ġthe Ġvocabulary , Ġwhich Ġmaps Ġthe Ġinput Ġtoken Ġto Ġan Ġembedded Ġvector . ĠThen , Ġwe Ġdefine Ġan Ġenc oder ĠL ST M $ _{ enc } $ Ġand Ġa Ġdec oder ĠL ST M $ _{ dec } $. ĠEvery Ġtoken Ġ$ o _ t $ Ġfrom Ġthe Ġtrajectory Ġ$\ math cal Ġ{ T } _ g $ Ġis Ġconverted Ġto Ġits Ġembedded Ġrepresentation Ġusing Ġthe Ġembed ding Ġmatrix Ġ$ E $ Ġand Ġthe Ġsequence Ġof Ġthese Ġembed ding Ġvectors Ġis Ġpassed Ġthrough ĠL ST M $ _{ enc } $ : </s> The Ġlast Ġhidden Ġstate Ġ$ h _{ | o _ t | } ^{ enc } $ Ġis Ġused Ġas Ġthe Ġinitial Ġhidden Ġstate Ġof Ġthe Ġdec oder Ġwhich Ġgenerates Ġthe Ġaction Ġ$ a _ t $ Ġtoken Ġby Ġtoken . ĠSpecifically , Ġgiven Ġthe Ġsequence Ġof Ġhidden Ġstates Ġ$ H Ġ\ in Ġ\ math bb Ġ{ R } ^{ d Ġ\ times Ġ| o _ t | } $ Ġof Ġthe Ġenc oder , Ġtokens Ġ$ a _ t ^ j $ Ġare Ġgenerated Ġas Ġfollows : </s> where Ġ$ W Ġ\ in Ġ\ math bb Ġ{ R } ^{ 2 d Ġ\ times Ġ| V | } $ Ġis Ġa Ġmatrix Ġthat Ġmaps Ġthe Ġdec oder Ġhidden Ġstate , Ġconc aten ated Ġwith Ġthe Ġcontext Ġvector , Ġinto Ġa Ġvocabulary Ġsize Ġvector . ĠDuring Ġtraining , Ġthe Ġparameters Ġof Ġthe Ġmodel Ġare Ġtrained Ġby Ġminimizing : </s> which Ġis Ġthe Ġsum Ġof Ġthe Ġnegative Ġlog Ġlikelihood Ġof Ġeach Ġtoken Ġin Ġ$ a _ t $ Ġ( using Ġteacher Ġforcing ĠB IB REF 34 ). ĠHowever , Ġat Ġtest Ġtime Ġthe Ġmodel Ġproduces Ġthe Ġsequence Ġin Ġan Ġauto - reg ressive Ġway ĠB IB REF 35 Ġusing Ġgreedy Ġsearch . </s> Exper iments Ġ: :: ĠGames Ġand Ġexperiments Ġsetup </s> A Ġset Ġof Ġcommonly Ġused Ġstandard Ġbenchmarks ĠB IB REF 8 , ĠB IB REF 3 , ĠB IB REF 7 Ġfor Ġagents Ġthat Ġplay Ġtext - based Ġgames Ġare Ġsimple Ġgames Ġwhich Ġrequire Ġno Ġmore Ġthan Ġtwo Ġwords Ġin Ġeach Ġstep Ġto Ġsolve Ġthe Ġgame , Ġand Ġhave Ġa Ġvery Ġlimited Ġnumber Ġof Ġad missible Ġactions Ġper Ġobservation . ĠWhile Ġsimpl ifying , Ġthis Ġsetting Ġlimits Ġthe Ġagent 's Ġability Ġto Ġfully Ġexpress Ġnatural Ġlanguage Ġand Ġlearn Ġmore Ġcomplex Ġways Ġto Ġspeak . ĠIn Ġthis Ġpaper , Ġwe Ġembrace Ġmore Ġchallenging Ġenvironments Ġwhere Ġmultiple Ġwords Ġare Ġneeded Ġat Ġeach Ġstep Ġto Ġsolve Ġthe Ġgames Ġand Ġthe Ġreward Ġis Ġparticularly Ġsparse . ĠHence , Ġwe Ġhave Ġselected Ġthe Ġfollowing Ġenvironments : </s> [ left margin = * ] </s> Coin Collect or ĠB IB REF 8 Ġis Ġa Ġclass Ġof Ġtext - based Ġgames Ġwhere Ġthe Ġobjective Ġis Ġto Ġfind Ġand Ġcollect Ġa Ġcoin Ġfrom Ġa Ġspecific Ġlocation Ġin Ġa Ġgiven Ġset Ġof Ġconnected Ġrooms Ġ. ĠThe Ġagent Ġwins Ġthe Ġgame Ġafter Ġit Ġcollects Ġthe Ġcoin , Ġat Ġwhich Ġpoint Ġ( for Ġthe Ġfirst Ġand Ġonly Ġtime ) Ġa Ġreward Ġof Ġ+ 1 Ġis Ġreceived Ġby Ġthe Ġagent . ĠThe Ġenvironment Ġpars es Ġonly Ġfive Ġad missible Ġcommands Ġ( go Ġnorth , Ġgo Ġeast , Ġgo Ġsouth , Ġgo Ġwest , Ġand Ġtake Ġcoin ) Ġmade Ġby Ġtwo Ġworlds ; </s> Cook ing World ĠB IB REF 14 Ġin Ġthis Ġchallenge , Ġthere Ġare Ġ4 , 440 Ġgames Ġwith Ġ222 Ġdifferent Ġlevels Ġof Ġdifficulty , Ġwith Ġ20 Ġgames Ġper Ġlevel Ġof Ġdifficulty , Ġeach Ġwith Ġdifferent Ġentities Ġand Ġmaps . ĠThe Ġgoal Ġof Ġeach Ġgame Ġis Ġto Ġcook Ġand Ġeat Ġfood Ġfrom Ġa Ġgiven Ġrecipe , Ġwhich Ġincludes Ġthe Ġtask Ġof Ġcollecting Ġingredients Ġ( e . g . Ġtomato , Ġpotato , Ġetc .), Ġobjects Ġ( e . g . Ġknife ), Ġand Ġprocessing Ġthem Ġaccording Ġto Ġthe Ġrecipe Ġ( e . g . Ġcook Ġpotato , Ġslice Ġtomato , Ġetc .). ĠThe Ġparser Ġof Ġeach Ġgame Ġaccepts Ġ18 Ġverbs Ġand Ġ51 Ġentities Ġwith Ġa Ġpred efined Ġgrammar , Ġbut Ġthe Ġoverall Ġsize Ġof Ġthe Ġvocabulary Ġof Ġthe Ġobservations Ġis Ġ20 , 000 . ĠIn ĠAppendix ĠSEC REF 36 Ġwe Ġprovide Ġmore Ġdetails Ġabout Ġthe Ġlevels Ġand Ġthe Ġgames ' Ġgrammar . </s> In Ġour Ġexperiments , Ġwe Ġtry Ġto Ġaddress Ġtwo Ġmajor Ġresearch Ġquestions . ĠFirst , Ġwe Ġwant Ġto Ġbenchmark Ġthe Ġexploration Ġpower Ġof Ġphase Ġ1 Ġof ĠGo - Explore Ġin Ġcomparison Ġto Ġexisting Ġexploration Ġapproaches Ġused Ġin Ġtext - based Ġgames . ĠFor Ġthis Ġpurpose , Ġwe Ġgenerate Ġ10 ĠCoin Collect or Ġgames Ġwith Ġthe Ġhardest Ġsetting Ġused Ġby ĠB IB REF 8 , Ġi . e . Ġhard - level Ġ30 Ġ( re fer Ġto Ġthe ĠAppendix ĠSEC REF 36 Ġfor Ġmore Ġinformation ) Ġand Ġuse Ġthem Ġas Ġa Ġbenchmark . ĠIn Ġfact , ĠCoin Collect or Ġrequires Ġmany Ġactions Ġ( at Ġleast Ġ30 Ġon Ġhard Ġgames ) Ġto Ġfind Ġa Ġreward , Ġwhich Ġmakes Ġit Ġsuitable Ġfor Ġtesting Ġthe Ġexploration Ġcapabilities Ġof Ġdifferent Ġalgorithms . ĠSecondly , Ġwe Ġwant Ġto Ġverify Ġthe Ġgeneral ization Ġability Ġof Ġour Ġmodel Ġin Ġcreating Ġcomplex Ġstrategies Ġusing Ġnatural Ġlanguage . ĠCoin Collect or Ġhas Ġa Ġvery Ġlimited Ġaction Ġspace , Ġand Ġis Ġmainly Ġdesigned Ġto Ġbenchmark Ġmodels Ġon Ġtheir Ġcapability Ġof Ġdealing Ġwith Ġsparse Ġrewards . ĠTherefore Ġwe Ġuse Ġthe Ġmore Ġcomplex ĠCooking World Ġgames Ġto Ġevaluate Ġthe Ġgeneral ization Ġcapabilities Ġof Ġour Ġproposed Ġapproach . ĠWe Ġdesign Ġthree Ġdifferent Ġsettings Ġfor ĠCooking World : Ġ1 ) ĠSingle : Ġtreat Ġeach Ġgame Ġindependently , Ġwhich Ġmeans Ġwe Ġtrain Ġand Ġtest Ġone Ġagent Ġfor Ġeach Ġgame Ġto Ġevaluate Ġhow Ġrobust Ġdifferent Ġmodels Ġare Ġacross Ġdifferent Ġgames .; Ġ2 ) ĠJoint : Ġtraining Ġand Ġtesting Ġa Ġsingle Ġpolicy Ġon Ġall Ġthe Ġ4 , 440 ĠCooking World Ġgames Ġat Ġthe Ġsame Ġtime Ġto Ġverify Ġthat Ġmodels Ġcan Ġlearn Ġto Ġplay Ġmultiple Ġgames Ġat Ġthe Ġsame Ġtime ; Ġ3 ) ĠZero - Shot : Ġsplit Ġthe Ġgames Ġinto Ġtraining , Ġvalidation , Ġand Ġtest Ġsets , Ġand Ġthen Ġtrain Ġour Ġpolicy Ġon Ġthe Ġtraining Ġgames Ġand Ġtest Ġit Ġon Ġthe Ġunseen Ġtest Ġgames . ĠThis Ġsetting Ġis Ġthe Ġhardest Ġamong Ġall , Ġsince Ġit Ġrequires Ġgeneral ization Ġto Ġunseen Ġgames . </s> In Ġboth ĠCoin Collect or Ġand ĠCooking World Ġgames Ġan Ġobservation Ġ$ o _ t $ Ġprovided Ġby Ġthe Ġenvironment Ġconsists Ġof Ġa Ġroom Ġdescription Ġ$ D $, Ġinventory Ġinformation Ġ$ I $, Ġquest Ġ$ Q $, Ġprevious Ġaction Ġ$ P $ Ġand Ġfeedback Ġ$ F $ Ġprovided Ġin Ġthe Ġprevious Ġturn . ĠTable ĠT AB REF 3 Ġshows Ġan Ġexample Ġfor Ġeach Ġof Ġthese Ġcomponents . ĠIn Ġour Ġexperiments Ġfor Ġphase Ġ1 Ġof ĠGo - Explore Ġwe Ġonly Ġuse Ġ$ D $ Ġas Ġthe Ġobservation . </s> Exper iments Ġ: :: ĠBas elines </s> For Ġthe ĠCoin Collect or Ġgames , Ġwe Ġcompared ĠGo - Explore Ġwith Ġthe Ġepis odic Ġdiscovery Ġbonus ĠB IB REF 30 Ġthat Ġwas Ġused Ġby ĠB IB REF 8 Ġto Ġimprove Ġtwo ĠQ - learning - based Ġbas elines : ĠD Q N ++ Ġand ĠDR Q N ++ . ĠWe Ġused Ġthe Ġcode Ġprovided Ġby Ġthe Ġauthors Ġand Ġthe Ġsame Ġhyper - param eters . </s> For Ġthe ĠCooking World Ġgames , Ġwe Ġimplemented Ġthree Ġdifferent Ġtreatments Ġbased Ġon Ġtwo Ġexisting Ġmethods : </s> [ left margin = * ] </s> L ST M - D Q N ĠB IB REF 7 , ĠB IB REF 8 : ĠAn ĠL ST M Ġbased Ġstate Ġenc oder Ġwith Ġa Ġseparate Ġ$ Q $ - fun ctions Ġfor Ġeach Ġcomponent Ġ( word ) Ġof Ġa Ġfixed Ġpattern Ġof ĠVerb , ĠAd ject ive 1 , ĠN oun 1 , ĠAd ject ive 2 , Ġand ĠN oun 2 . ĠIn Ġthis Ġapproach , Ġgiven Ġthe Ġobservation Ġ$ o _ t $, Ġthe Ġtokens Ġare Ġfirst Ġconverted Ġinto Ġembed d ings , Ġthen Ġan ĠL ST M Ġis Ġused Ġto Ġextract Ġa Ġsequence Ġof Ġhidden Ġstates Ġ$ H _{ dq n }\ in Ġ\ math bb Ġ{ R } ^{ d Ġ\ times Ġ| o _ t | } $. ĠA Ġmean - pool Ġlayer Ġis Ġapplied Ġto Ġ$ H _{ dq n } $ Ġto Ġproduce Ġa Ġsingle Ġvector Ġ$ h _{ o ^ t } $ Ġthat Ġrepresents Ġthe Ġwhole Ġsequence . ĠNext , Ġa Ġlinear Ġtransformation Ġ$ W _{ \ text { type }} \ in Ġ\ math bb Ġ{ R } ^{ d Ġ\ times Ġ| V _{ \ text { type }} | } $ Ġis Ġused Ġto Ġgenerate Ġeach Ġof Ġthe ĠQ Ġvalues , Ġwhere Ġ$ | V _{ \ text { type }} | Ġ\ ll Ġ| V | $ Ġis Ġthe Ġsubset Ġof Ġthe Ġoriginal Ġvocabulary Ġrestricted Ġto Ġthe Ġword Ġtype Ġof Ġa Ġparticular Ġgame Ġ( e . g Ġfor ĠVerb Ġtype : Ġtake , Ġdrop , Ġetc .). ĠForm ally , Ġwe Ġhave : </s> Next , Ġall Ġthe Ġ$ Q $ - fun ctions Ġare Ġjointly Ġtrained Ġusing Ġthe ĠD Q N Ġalgorithm Ġwith Ġ$\ ep sil on Ġ$ - gre edy Ġexploration ĠB IB REF 15 , ĠB IB REF 16 . ĠAt Ġevaluation Ġtime , Ġthe Ġarg max Ġof Ġeach Ġ$ Q $ - function Ġis Ġconc aten ated Ġto Ġproduce Ġ$ a _ t $. ĠImport antly , Ġin Ġ$ V _{ \ text { type }} $ Ġa Ġspecial Ġtoken Ġ$ < $ s $ > $ Ġis Ġused Ġto Ġdenote Ġthe Ġabsence Ġof Ġa Ġword , Ġso Ġthe Ġmodel Ġcan Ġproduce Ġactions Ġwith Ġdifferent Ġlengths . ĠFigure ĠFIG REF 57 Ġin ĠAppendix ĠSEC REF 55 Ġshows Ġa Ġdepiction Ġof Ġthis Ġmodel . </s> L ST M - D Q N + AD M : ĠIt Ġis Ġthe Ġsame Ġmodel Ġas ĠL ST M - D Q N , Ġexcept Ġthat Ġthe Ġrandom Ġactions Ġfor Ġ$\ ep sil on Ġ$ - gre edy Ġexploration Ġare Ġsampled Ġfrom Ġthe Ġset Ġof Ġad missible Ġactions Ġinstead Ġof Ġcreating Ġthem Ġby Ġsampling Ġeach Ġword Ġseparately . </s> DR RN ĠB IB REF 10 : ĠIn Ġthis Ġapproach Ġa Ġmodel Ġlearns Ġhow Ġto Ġscore Ġad missible Ġactions Ġinstead Ġof Ġdirectly Ġgenerating Ġthe Ġaction Ġtoken Ġby Ġtoken . ĠThe Ġpolicy Ġuses Ġan ĠL ST M Ġfor Ġencoding Ġthe Ġobservation Ġand Ġactions Ġare Ġrepresented Ġas Ġthe Ġsum Ġof Ġthe Ġembed ding Ġof Ġthe Ġword Ġtokens Ġthey Ġcontain . ĠThen , Ġthe Ġ$ Q $ Ġvalue Ġis Ġdefined Ġas Ġthe Ġdot Ġproduct Ġbetween Ġthe Ġembedded Ġrepresentations Ġof Ġthe Ġobservation Ġand Ġthe Ġaction . ĠFollowing Ġthe Ġaforementioned Ġnotation , Ġ$ h _{ o ^ t } $ Ġis Ġgenerated Ġas Ġin Ġthe ĠL ST M - D Q N Ġbaseline . ĠNext , Ġwe Ġdefine Ġits Ġembedded Ġrepresentation Ġas Ġ$ c _ i = \ sum Ġ_ k ^{ | a _ i | } ĠE ( a _ i ^ k ) $, Ġwhere Ġ$ E $ Ġis Ġan Ġembed ding Ġmatrix Ġas Ġin ĠEqu ation Ġ1 . ĠThus , Ġthe Ġ$ Q $ - function Ġis Ġdefined Ġas : </s> At Ġtesting Ġtime Ġthe Ġaction Ġwith Ġthe Ġhighest Ġ$ Q $ Ġvalue Ġis Ġchosen . ĠFigure ĠFIG REF 58 Ġin ĠAppendix ĠSEC REF 55 Ġshows Ġa Ġdepiction Ġof Ġthis Ġmodel . </s> Exper iments Ġ: :: ĠHyper - param eters </s> In Ġall Ġthe Ġgames Ġthe Ġmaximum Ġnumber Ġof Ġsteps Ġhas Ġbeen Ġset Ġto Ġ50 . ĠAs Ġmentioned Ġearlier , Ġthe Ġcell Ġrepresentation Ġused Ġin Ġthe ĠGo - Explore Ġarchive Ġis Ġcomputed Ġby Ġthe Ġsum Ġof Ġembed d ings Ġof Ġthe Ġroom Ġdescription Ġtokens Ġconc aten ated Ġwith Ġthe Ġcurrent Ġcumulative Ġreward . ĠThe Ġsum Ġof Ġembed d ings Ġis Ġcomputed Ġusing Ġ50 Ġdimensional Ġpre - trained ĠGl o Ve ĠB IB REF 36 Ġvectors . ĠIn Ġthe ĠCoin Collect or Ġbas elines Ġwe Ġuse Ġthe Ġsame Ġhyper - param eters Ġas Ġin Ġthe Ġoriginal Ġpaper . ĠIn ĠCooking World Ġall Ġthe Ġbas elines Ġuse Ġpre - trained ĠGl o Ve Ġof Ġdimension Ġ100 Ġfor Ġthe Ġsingle Ġsetting Ġand Ġ300 Ġfor Ġthe Ġjoint Ġone . ĠThe ĠL ST M Ġhidden Ġstate Ġhas Ġbeen Ġset Ġto Ġ300 Ġfor Ġall Ġthe Ġmodels . </s> Results Ġ: :: ĠCoin Collect or </s> In Ġthis Ġsetting , Ġwe Ġcompare Ġthe Ġnumber Ġof Ġactions Ġplayed Ġin Ġthe Ġenvironment Ġ( frames ) Ġand Ġthe Ġscore Ġachieved Ġby Ġthe Ġagent Ġ( i . e . Ġ+ 1 Ġreward Ġif Ġthe Ġcoin Ġis Ġcollected ). ĠIn ĠGo - Explore Ġwe Ġalso Ġcount Ġthe Ġactions Ġused Ġto Ġrestore Ġthe Ġenvironment Ġto Ġa Ġselected Ġcell , Ġi . e . Ġto Ġbring Ġthe Ġagent Ġto Ġthe Ġstate Ġrepresented Ġin Ġthe Ġselected Ġcell . ĠThis Ġallows Ġa Ġone - to - one Ġcomparison Ġof Ġthe Ġexploration Ġefficiency Ġbetween ĠGo - Explore Ġand Ġalgorithms Ġthat Ġuse Ġa Ġcount - based Ġreward Ġin Ġtext - based Ġgames . ĠImport antly , ĠB IB REF 8 Ġshowed Ġthat ĠD Q N Ġand ĠDR Q N , Ġwithout Ġsuch Ġcounting Ġrewards , Ġcould Ġnever Ġfind Ġa Ġsuccessful Ġtrajectory Ġin Ġhard Ġgames Ġsuch Ġas Ġthe Ġones Ġused Ġin Ġour Ġexperiments . ĠFigure ĠFIG REF 17 Ġshows Ġthe Ġnumber Ġof Ġinteractions Ġwith Ġthe Ġenvironment Ġ( frames ) Ġversus Ġthe Ġmaximum Ġscore Ġobtained , Ġaveraged Ġover Ġ10 Ġgames Ġof Ġthe Ġsame Ġdifficulty . ĠAs Ġshown Ġby ĠB IB REF 8 , ĠDR Q N ++ Ġfinds Ġa Ġtrajectory Ġwith Ġthe Ġmaximum Ġscore Ġfaster Ġthan Ġto ĠD Q N ++ . ĠOn Ġthe Ġother Ġhand , Ġphase Ġ1 Ġof ĠGo - Explore Ġfinds Ġan Ġoptimal Ġtrajectory Ġwith Ġapproximately Ġhalf Ġthe Ġinteractions Ġwith Ġthe Ġenvironment . ĠMoreover , Ġthe Ġtrajectory Ġlength Ġfound Ġby ĠGo - Explore Ġis Ġalways Ġoptimal Ġ( i . e . Ġ30 Ġsteps ) Ġwhereas Ġboth ĠD Q N ++ Ġand ĠDR Q N ++ Ġhave Ġan Ġaverage Ġlength Ġof Ġ38 Ġand Ġ42 Ġrespectively . </s> Results Ġ: :: ĠCooking World </s> In ĠCooking World , Ġwe Ġcompared Ġmodels Ġin Ġthe Ġthree Ġsettings Ġmentioned Ġearlier , Ġnamely , Ġsingle , Ġjoint , Ġand Ġzero - shot . ĠIn Ġall Ġexperiments , Ġwe Ġmeasured Ġthe Ġsum Ġof Ġthe Ġfinal Ġscores Ġof Ġall Ġthe Ġgames Ġand Ġtheir Ġtrajectory Ġlength Ġ( number Ġof Ġsteps ). ĠTable ĠT AB REF 26 Ġsummarizes Ġthe Ġresults Ġin Ġthese Ġthree Ġsettings . ĠPhase Ġ1 Ġof ĠGo - Explore Ġon Ġsingle Ġgames Ġachieves Ġa Ġtotal Ġscore Ġof Ġ19 , 530 Ġ( sum Ġover Ġall Ġgames ), Ġwhich Ġis Ġvery Ġclose Ġto Ġthe Ġmaximum Ġpossible Ġpoints Ġ( i . e . Ġ19 , 882 ), Ġwith Ġ47 , 562 Ġsteps . ĠA Ġwinning Ġtrajectory Ġwas Ġfound Ġin Ġ4 , 279 Ġout Ġof Ġthe Ġtotal Ġof Ġ4 , 440 Ġgames . ĠThis Ġresult Ġconfirms Ġagain Ġthat Ġthe Ġexploration Ġstrategy Ġof ĠGo - Explore Ġis Ġeffective Ġin Ġtext - based Ġgames . ĠNext , Ġwe Ġevaluate Ġthe Ġeffectiveness Ġand Ġthe Ġgeneral ization Ġability Ġof Ġthe Ġsimple Ġimitation Ġlearning Ġpolicy Ġtrained Ġusing Ġthe Ġextracted Ġtraject ories Ġin Ġphase Ġ1 Ġof ĠGo - Explore Ġin Ġthe Ġthree Ġsettings Ġmentioned Ġabove . </s> Results Ġ: :: ĠCooking World Ġ: :: ĠSingle </s> In Ġthis Ġsetting , Ġeach Ġmodel Ġis Ġtrained Ġfrom Ġscratch Ġin Ġeach Ġof Ġthe Ġ4 , 440 Ġgames Ġbased Ġon Ġthe Ġtrajectory Ġfound Ġin Ġphase Ġ1 Ġof ĠGo - Explore Ġ( pre vious Ġstep ). ĠAs Ġshown Ġin ĠTable ĠT AB REF 26 , Ġthe ĠL ST M - D Q N ĠB IB REF 7 , ĠB IB REF 8 Ġapproach Ġwithout Ġthe Ġuse Ġof Ġad missible Ġactions Ġperforms Ġpoorly . ĠOne Ġexplanation Ġfor Ġthis Ġcould Ġbe Ġthat Ġit Ġis Ġdifficult Ġfor Ġthis Ġmodel Ġto Ġexplore Ġboth Ġlanguage Ġand Ġgame Ġstrategy Ġat Ġthe Ġsame Ġtime ; Ġit Ġis Ġhard Ġfor Ġthe Ġmodel Ġto Ġfind Ġa Ġreward Ġsignal Ġbefore Ġit Ġhas Ġlearned Ġto Ġmodel Ġlanguage , Ġsince Ġalmost Ġnone Ġof Ġits Ġactions Ġwill Ġbe Ġad missible , Ġand Ġthose Ġreward Ġsignals Ġare Ġwhat Ġis Ġnecessary Ġin Ġorder Ġto Ġlearn Ġthe Ġlanguage Ġmodel . ĠAs Ġwe Ġsee Ġin ĠTable ĠT AB REF 26 , Ġhowever , Ġby Ġusing Ġthe Ġad missible Ġactions Ġin Ġthe Ġ$\ ep sil on Ġ$ - gre edy Ġstep Ġthe Ġscore Ġachieved Ġby Ġthe ĠL ST M - D Q N Ġincreases Ġdramatically Ġ(+ AD M Ġrow Ġin ĠTable ĠT AB REF 26 ). ĠDR RN ĠB IB REF 10 Ġachieves Ġa Ġvery Ġhigh Ġscore , Ġsince Ġit Ġexplicitly Ġlearns Ġhow Ġto Ġrank Ġad missible Ġactions Ġ( i . e . Ġa Ġmuch Ġsimpler Ġtask Ġthan Ġgenerating Ġtext ). ĠFinally , Ġour Ġapproach Ġof Ġusing Ġa ĠSe q 2 Se q Ġmodel Ġtrained Ġon Ġthe Ġsingle Ġtrajectory Ġprovided Ġby Ġphase Ġ1 Ġof ĠGo - Explore Ġachieves Ġthe Ġhighest Ġscore Ġamong Ġall Ġthe Ġmethods , Ġeven Ġthough Ġwe Ġdo Ġnot Ġuse Ġad missible Ġactions Ġin Ġthis Ġphase . ĠHowever , Ġin Ġthis Ġexperiment Ġthe ĠSe q 2 Se q Ġmodel Ġcannot Ġperfectly Ġreplicate Ġthe Ġprovided Ġtrajectory Ġand Ġthe Ġtotal Ġscore Ġthat Ġit Ġachieves Ġis Ġin Ġfact Ġ9 . 4 % Ġlower Ġcompared Ġto Ġthe Ġtotal Ġscore Ġachieved Ġby Ġphase Ġ1 Ġof ĠGo - Explore . ĠFigure ĠFIG REF 61 Ġ( in ĠAppendix ĠSEC REF 60 ) Ġshows Ġthe Ġscore Ġbreakdown Ġfor Ġeach Ġlevel Ġand Ġmodel , Ġwhere Ġwe Ġcan Ġsee Ġthat Ġthe Ġgap Ġbetween Ġour Ġmodel Ġand Ġother Ġmethods Ġincreases Ġas Ġthe Ġgames Ġbecome Ġharder Ġin Ġterms Ġof Ġskills Ġneeded . </s> Results Ġ: :: ĠCooking World Ġ: :: ĠJoint </s> In Ġthis Ġsetting , Ġa Ġsingle Ġmodel Ġis Ġtrained Ġon Ġall Ġthe Ġgames Ġat Ġthe Ġsame Ġtime , Ġto Ġtest Ġwhether Ġone Ġagent Ġcan Ġlearn Ġto Ġplay Ġmultiple Ġgames . ĠOverall , Ġas Ġexpected , Ġall Ġthe Ġevaluated Ġmodels Ġachieved Ġa Ġlower Ġperformance Ġcompared Ġto Ġthe Ġsingle Ġgame Ġsetting . ĠOne Ġreason Ġfor Ġthis Ġcould Ġbe Ġthat Ġlearning Ġmultiple Ġgames Ġat Ġthe Ġsame Ġtime Ġleads Ġto Ġa Ġsituation Ġwhere Ġthe Ġagent Ġencounters Ġsimilar Ġobservations Ġin Ġdifferent Ġgames , Ġand Ġthe Ġcorrect Ġaction Ġto Ġtake Ġin Ġdifferent Ġgames Ġmay Ġbe Ġdifferent . ĠFurthermore , Ġit Ġis Ġimportant Ġto Ġnote Ġthat Ġthe Ġorder Ġin Ġwhich Ġgames Ġare Ġpresented Ġgreatly Ġaffects Ġthe Ġperformance Ġof ĠL ST M - D Q N Ġand ĠDR RN . ĠIn Ġour Ġexperiments , Ġwe Ġtried Ġboth Ġan Ġeasy - to - hard Ġcurriculum Ġ( i . e . Ġsorting Ġthe Ġgames Ġby Ġincreasing Ġlevel Ġof Ġdifficulty ) Ġand Ġa Ġshuff led Ġcurriculum . ĠSh uff ling Ġthe Ġgames Ġat Ġeach Ġepoch Ġresulted Ġin Ġfar Ġbetter Ġperformance , Ġthus Ġwe Ġonly Ġreport Ġthe Ġlatter . ĠIn ĠFigure ĠFIG REF 28 Ġwe Ġshow Ġthe Ġscore Ġbreakdown , Ġand Ġwe Ġcan Ġsee Ġthat Ġall Ġthe Ġbas elines Ġquickly Ġfail , Ġeven Ġfor Ġeasier Ġgames . </s> Results Ġ: :: ĠCooking World Ġ: :: ĠZero - Shot </s> In Ġthis Ġsetting Ġthe Ġ4 , 440 Ġgames Ġare Ġsplit Ġinto Ġtraining , Ġvalidation , Ġand Ġtest Ġgames . ĠThe Ġsplit Ġis Ġdone Ġrandomly Ġbut Ġin Ġa Ġway Ġthat Ġdifferent Ġdifficulty Ġlevels Ġ( rec ipes Ġ1 , Ġ2 Ġand Ġ3 ), Ġare Ġrepresented Ġwith Ġequal Ġratios Ġin Ġall Ġthe Ġ3 Ġsplits , Ġi . e . Ġstrat ified Ġby Ġdifficulty . ĠAs Ġshown Ġin ĠTable ĠT AB REF 26 , Ġthe Ġzero - shot Ġperformance Ġof Ġthe ĠRL Ġbas elines Ġis Ġpoor , Ġwhich Ġcould Ġbe Ġattributed Ġto Ġthe Ġsame Ġreasons Ġwhy ĠRL Ġbas elines Ġunder - per form Ġin Ġthe ĠJoint Ġcase . ĠEspecially Ġinteresting Ġis Ġthat Ġthe Ġperformance Ġof ĠDR RN Ġis Ġsubstantially Ġlower Ġthan Ġthat Ġof Ġthe ĠGo - Explore ĠSe q 2 Se q Ġmodel , Ġeven Ġthough Ġthe ĠDR RN Ġmodel Ġhas Ġaccess Ġto Ġthe Ġad missible Ġactions Ġat Ġtest Ġtime , Ġwhile Ġthe ĠSe q 2 Se q Ġmodel Ġ( as Ġwell Ġas Ġthe ĠL ST M - D Q N Ġmodel ) Ġhas Ġto Ġconstruct Ġactions Ġtoken - by - token Ġfrom Ġthe Ġentire Ġvocabulary Ġof Ġ20 , 000 Ġtokens . ĠOn Ġthe Ġother Ġhand , ĠGo - Explore ĠSe q 2 Se q Ġshows Ġpromising Ġresults Ġby Ġsolving Ġalmost Ġhalf Ġof Ġthe Ġunseen Ġgames . ĠFigure ĠFIG REF 62 Ġ( in ĠAppendix ĠSEC REF 60 ) Ġshows Ġthat Ġmost Ġof Ġthe Ġlost Ġgames Ġare Ġin Ġthe Ġhardest Ġset , Ġwhere Ġa Ġvery Ġlong Ġsequence Ġof Ġactions Ġis Ġrequired Ġfor Ġwinning Ġthe Ġgame . ĠThese Ġresults Ġdemonstrate Ġboth Ġthe Ġrelative Ġeffectiveness Ġof Ġtraining Ġa ĠSe q 2 Se q Ġmodel Ġon ĠGo - Explore Ġtraject ories , Ġbut Ġthey Ġalso Ġindicate Ġthat Ġadditional Ġeffort Ġneeded Ġfor Ġdesigning Ġreinforcement Ġlearning Ġalgorithms Ġthat Ġeffectively Ġgeneral ize Ġto Ġunseen Ġgames . </s> Discussion </s> Exper imental Ġresults Ġshow Ġthat Ġour Ġproposed ĠGo - Explore Ġexploration Ġstrategy Ġis Ġa Ġviable Ġmethodology Ġfor Ġextracting Ġhigh - performing Ġtraject ories Ġin Ġtext - based Ġgames . ĠThis Ġmethod Ġallows Ġus Ġto Ġtrain Ġsupervised Ġmodels Ġthat Ġcan Ġoutper form Ġexisting Ġmodels Ġin Ġthe Ġexperimental Ġsettings Ġthat Ġwe Ġstudy . ĠFinally , Ġthere Ġare Ġstill Ġseveral Ġchallenges Ġand Ġlimitations Ġthat Ġboth Ġour Ġmethodology Ġand Ġprevious Ġsolutions Ġdo Ġnot Ġfully Ġaddress Ġyet . ĠFor Ġinstance : </s> Discussion Ġ: :: ĠState ĠRepresent ation </s> The Ġstate Ġrepresentation Ġis Ġthe Ġmain Ġlimitation Ġof Ġour Ġproposed Ġimitation Ġlearning Ġmodel . ĠIn Ġfact , Ġby Ġexamining Ġthe Ġobservations Ġprovided Ġin Ġdifferent Ġgames , Ġwe Ġnotice Ġa Ġlarge Ġoverlap Ġin Ġthe Ġdescriptions Ġ($ D $ ) Ġof Ġthe Ġgames . ĠThis Ġoverlap Ġleads Ġto Ġa Ġsituation Ġwhere Ġthe Ġpolicy Ġreceives Ġvery Ġsimilar Ġobservations , Ġbut Ġis Ġexpected Ġto Ġimitate Ġtwo Ġdifferent Ġactions . ĠThis Ġshow Ġespecially Ġin Ġthe Ġjoint Ġsetting Ġof ĠCooking World , Ġwhere Ġthe Ġ222 Ġgames Ġare Ġrepeated Ġ20 Ġtimes Ġwith Ġdifferent Ġentities Ġand Ġroom Ġmaps . ĠIn Ġthis Ġwork , Ġwe Ġopted Ġfor Ġa Ġsimple ĠSe q 2 Se q Ġmodel Ġfor Ġour Ġpolicy , Ġsince Ġour Ġgoal Ġis Ġto Ġshow Ġthe Ġeffectiveness Ġof Ġour Ġproposed Ġexploration Ġmethods . ĠHowever , Ġa Ġmore Ġcomplex ĠHier arch ical - Se q 2 Se q Ġmodel ĠB IB REF 37 Ġor Ġa Ġbetter Ġenc oder Ġrepresentation Ġbased Ġon Ġknowledge Ġgraphs ĠB IB REF 38 , ĠB IB REF 39 Ġwould Ġlikely Ġimprove Ġthe Ġof Ġperformance Ġthis Ġapproach . </s> Discussion Ġ: :: ĠLanguage ĠBased ĠExploration </s> In ĠGo - Explore , Ġthe Ġgiven Ġad missible Ġactions Ġare Ġused Ġduring Ġrandom Ġexploration . ĠHowever , Ġin Ġmore Ġcomplex Ġgames , Ġe . g . ĠZ ork ĠI Ġand Ġin Ġgeneral Ġthe ĠZ - Machine Ġgames , Ġthese Ġad missible Ġactions Ġare Ġnot Ġprovided . ĠIn Ġsuch Ġsettings , Ġthe Ġaction Ġspace Ġwould Ġexplode Ġin Ġsize , Ġand Ġthus ĠGo - Explore , Ġeven Ġwith Ġan Ġappropriate Ġcell Ġrepresentation , Ġwould Ġhave Ġa Ġhard Ġtime Ġfinding Ġgood Ġtraject ories . ĠTo Ġaddress Ġthis Ġissue Ġone Ġcould Ġleverage Ġgeneral Ġlanguage Ġmodels Ġto Ġproduce Ġa Ġset Ġof Ġgram matically Ġcorrect Ġactions . ĠAlternatively Ġone Ġcould Ġiter atively Ġlearn Ġa Ġpolicy Ġto Ġsample Ġactions , Ġwhile Ġexploring Ġwith ĠGo - Explore . ĠBoth Ġstrategies Ġare Ġviable , Ġand Ġa Ġcomparison Ġis Ġleft Ġto Ġfuture Ġwork . </s> It Ġis Ġworth Ġnoting Ġthat Ġa Ġhand - tail ored Ġsolution Ġfor Ġthe ĠCooking World Ġgames Ġhas Ġbeen Ġproposed Ġin Ġthe ĠâĢ ľ First ĠText World ĠProblems âĢ Ŀ Ġcompetition ĠB IB REF 3 . ĠThis Ġsolution Ġmanaged Ġto Ġobtain Ġup Ġto Ġ91 . 9 % Ġof Ġthe Ġmaximum Ġpossible Ġscore Ġacross Ġthe Ġ5 14 Ġtest Ġgames Ġon Ġan Ġunpublished Ġdataset . ĠHowever , Ġthis Ġsolution Ġrelies Ġon Ġentity Ġextraction Ġand Ġtemplate Ġfilling , Ġwhich Ġwe Ġbelieve Ġlimits Ġits Ġpotential Ġfor Ġgeneral ization . ĠTherefore , Ġthis Ġapproach Ġshould Ġbe Ġviewed Ġas Ġcomplementary Ġrather Ġthan Ġcompetitor Ġto Ġour Ġapproach Ġas Ġit Ġcould Ġpotentially Ġbe Ġused Ġas Ġan Ġalternative Ġway Ġof Ġgetting Ġpromising Ġtraject ories . </s> Conclusion </s> In Ġthis Ġpaper Ġwe Ġpresented Ġa Ġnovel Ġmethodology Ġfor Ġsolving Ġtext - based Ġgames Ġwhich Ġfirst Ġextracts Ġhigh - performing Ġtraject ories Ġusing Ġphase Ġ1 Ġof ĠGo - Explore Ġand Ġthen Ġtrains Ġa Ġsimple ĠSe q 2 Se q Ġmodel Ġthat Ġmaps Ġobservations Ġto Ġactions Ġusing Ġthe Ġextracted Ġtraject ories . ĠOur Ġexperiments Ġshow Ġpromising Ġresults Ġin Ġthree Ġsettings , Ġwith Ġimproved Ġgeneral ization Ġand Ġsample Ġefficiency Ġcompared Ġto Ġexisting Ġmethods . ĠFinally , Ġwe Ġdiscussed Ġthe Ġlimitations Ġand Ġpossible Ġimprovements Ġof Ġour Ġmethodology , Ġwhich Ġleads Ġto Ġnew Ġresearch Ġchallenges Ġin Ġtext - based Ġgames . </s> App endix Ġ: :: ĠText - Games Ġ: :: ĠCoin Collect or </s> In Ġthe Ġhard Ġsetting Ġ( mode Ġ2 ), Ġeach Ġroom Ġon Ġthe Ġpath Ġto Ġthe Ġcoin Ġhas Ġtwo Ġdistract or Ġrooms , Ġand Ġthe Ġlevel Ġ( e . g . Ġ30 ) Ġindicates Ġthe Ġshortest Ġpath Ġfrom Ġthe Ġstarting Ġpoint Ġto Ġthe Ġcoin Ġroom . </s> App endix Ġ: :: ĠText - Games Ġ: :: ĠCooking World </s> The Ġgame 's Ġcomplexity Ġis Ġdetermined Ġby Ġthe Ġnumber Ġof Ġskills Ġand Ġthe Ġtypes Ġof Ġskills Ġthat Ġan Ġagent Ġneeds Ġto Ġmaster . ĠThe Ġskills Ġare : </s> reci pe Ġ{ 1 , 2 , 3 }: Ġnumber Ġof Ġingredients Ġin Ġthe Ġrecipe </s> take Ġ{ 1 , 2 , 3 }: Ġnumber Ġof Ġingredients Ġto Ġfind Ġ( not Ġalready Ġin Ġthe Ġinventory ) </s> open : Ġwhether Ġcontainers / doors Ġneed Ġto Ġbe Ġopened </s> cook : Ġwhether Ġingredients Ġneed Ġto Ġbe Ġcooked </s> cut : Ġwhether Ġingredients Ġneed Ġto Ġbe Ġcut </s> drop : Ġwhether Ġthe Ġinventory Ġhas Ġlimited Ġcapacity </s> go Ġ{ 1 , 6 , 9 , 12 }: Ġnumber Ġof Ġlocations </s> Thus Ġthe Ġhardest Ġgame Ġwould Ġbe Ġa Ġrecipe Ġwith Ġ3 Ġingredients , Ġwhich Ġmust Ġall Ġbe Ġpicked Ġup Ġsomewhere Ġacross Ġ12 Ġlocations Ġand Ġthen Ġneed Ġto Ġbe Ġcut Ġand Ġcooked , Ġand Ġto Ġget Ġaccess Ġto Ġsome Ġlocations , Ġseveral Ġdoors Ġor Ġobjects Ġneed Ġto Ġbe Ġopened . ĠThe Ġhandic ap Ġof Ġa Ġlimited Ġcapacity Ġin Ġthe Ġinventory Ġmakes Ġthe Ġgame Ġmore Ġdifficult Ġby Ġrequiring Ġthe Ġagent Ġto Ġdrop Ġan Ġobject Ġand Ġlater Ġon Ġtake Ġit Ġagain Ġif Ġneeded . ĠThe Ġgrammar Ġused Ġfor Ġthe Ġtext - based Ġgames Ġis Ġthe Ġfollowing : </s> go , Ġlook , Ġexamine , Ġinventory , Ġeat , Ġopen / close , Ġtake / drop , Ġput / insert </s> cook ĠX Ġwith ĠY Ġ$\ long right arrow Ġ$ Ġgrilled ĠX Ġ( when ĠY Ġis Ġthe ĠBBQ ) </s> cook ĠX Ġwith ĠY Ġ$\ long right arrow Ġ$ Ġroasted ĠX Ġ( when ĠY Ġis Ġthe Ġoven ) </s> cook ĠX Ġwith ĠY Ġ$\ long right arrow Ġ$ Ġfried ĠX Ġ( when ĠY Ġis Ġthe Ġstove ) </s> slice ĠX Ġwith ĠY Ġ$\ long right arrow Ġ$ Ġsliced ĠX </s> ch op ĠX Ġwith ĠY Ġ$\ long right arrow Ġ$ Ġchopped ĠX </s> d ice ĠX Ġwith ĠY Ġ$\ long right arrow Ġ$ Ġdiced ĠX </s> prep are Ġmeal </s> Where ĠY Ġis Ġsomething Ġsharp Ġ( e . g . Ġknife ).