Monte-Carlo Planning and Learning with Language Action Value Estimates
Authors: Youngsoo Jang
Seokin Seo
Jongmin Lee
Kee-Eung Kim
Venue: ICLR 2021 Poster (2021)
Keywords: natural language processing
Monte-Carlo tree search
reinforcement learning
interactive fiction

Abstract: Interactive Fiction (IF) games provide a useful testbed for language-based reinforcement learning agents, posing significant challenges of natural language understanding, commonsense reasoning, and non-myopic planning in the combinatorial search space. Agents based on standard planning algorithms struggle to play IF games due to the massive search space of language actions. Thus, language-grounded planning is a key ability of such agents, since inferring the consequence of language action based on semantic understanding can drastically improve search. In this paper, we introduce Monte-Carlo planning with Language Action Value Estimates (MC-LAVE) that combines a Monte-Carlo tree search with language-driven exploration. MC-LAVE invests more search effort into semantically promising language actions using locally optimistic language value estimates, yielding a significant reduction in the effective search space of language actions. We then present a reinforcement learning approach via MC-LAVE, which alternates between MC-LAVE planning and supervised learning of the self-generated language actions. In the experiments, we demonstrate that our method achieves new high scores in various IF games.

Published as a conference paper at ICLR 2021
MONTE-CARLO PLANNING AND LEARNING WITH LANGUAGE ACTION VALUE ESTIMATES
Youngsoo Jang', Seokin Seo", Jongmin Lee', Kee-Eung Kim 'School of Computing, KAIST. Dacjeon, Republic of Korea "Grauuate School AI, KAIST, Daejeon, Republic Korea {ys Jysgang, s siseo, jmlee 8ai. haist.ac. ac..r,, xr, kekimekaist.ac.
ABSTRACT
Interactive Fiction (IF) games provide a useful testbed for language-based rein- forcement learning agents, posing significant challenges of natural language un- derstanding, commonsense reasoning. and non-myopic planning in the combina- torial search space. Agents using standard planning algorithms struggle to play games due to the massive search space of language actions. Thus, language- grounded planning is key ability of such agents, since inferring the conse- quence of language action based on semantic understanding can drastically im- prove search. In this paper, introduce Monte-Carlo planning with Language Action Value Estimates (MC-LAVE) that combines Monte-Card Carlo tree search with language-driven exploration. MC-LAVE concentrates search effort semanti- cally promising language actions using locally optimistic language value esti- mates, yielding a significant reduction the effective search space of language actions. We then present a reinforcement learning approach built on MC-LAVE, which alternates between MC-LAVE planning and supervised learning of the self- generated language actions. In the experiments, we demonstrate that our method achieves new high scores various IF games.
INTRODUCTION
Building an intelligent goal-oriented agent that can perceive and react via natural language is one of the grand challenges of artificial intelligence. In pursuit of this goal, we consider Interactive Fiction (IF) games (Nelson 2001 Montfort 2005). which are text-based simulation environments where the agent interacts with the environment only through natural language. They serve as a useful testbed for developing language-based goal-oriented agents, posing important challenges such as natural language understanding, commonsense reasoning, and non-myopic planning in the combinatorial search space of language actions. IF games naturally have large branching factor, with at least hundreds of natural language actions that can affect the simulation of game states. This renders naive grounded planning ability, i.e. effective search space is too large to choose an optimal action, without inferring the future impact of language actions by understanding the environment state described in natural language.
exhaustive search infeasible and raises the strong need for language-grounded
Still, standard planning methods such as Monte-Carlo tree search (MCTS) are language-agnostic and rely only on uncertainty-driivn exploration, encouraging more search on less-visited states and actions. This simple iicertainty-base strategy is not sufficient to find an optimal language action under limited search time, especially when each language action is treated as a discrete token. On the other hand, recent reinforcement learning agents for IF games have started to leverage pre-trained word embeddings for language understanding (He et al.] 2016) Fulda et al.) 2017 2 2020) knowledge graphs for commonsense reasoning (Ammanabrolu & Hausknecht) (2020), but their exploration strategies are still limited to the e-greedy or the softmax policies, lacking more structured and non-myopic planning ability. As consequence, current state-of-the-ar agents for IF games still have not yet been up to the human-level play.
Hausknecht al.)
In this paper, introduce Monte-Carbe planning with Language Action Value Estimates (MC- LAVE), a planning algorithm for the environments with text-based interactions. MC-LAVE com- bines Monte-Carlo tree search with language-driven exploration, addressing the search inefficiency

---

Published as a conference paper at ICLR 2021
attributed to the lack of language understanding. It starts with credit assignment to language actions via Q-learning of the experiences collected from the past searches. Then, MC-LAVE assigns non- uniform search priorities to each language action based on the optimistically aggregated Q-estimates of the past actions that share similar meanings with the candidate action, so as to focus more on the semantically promising actions. This is in contrast the previous methods that involve language understanding in the form of knowledge graph, where the insignificant language actions are uni- formly filtered out by the graph mask (Ammanabrolu & Hausknecht) 2020; Ammanabrolu et al. 2020). We show that the non-un unn-uniform search empowered by language understanding in MC-LAVE yields better search efficiency while not hurting the asymptotic guarantee of MCTS.
We then present our reinforcement learning approach that uses MC-LAVE as a strong policy im- provement operator. Since MCTS explores the combinatorial space of action sequences, its search results can be far better than the simple greedy improvement, demonstrated in the game of Go (Sil- ver et al., 2017). This final algorithm, MC-LAVE-RL,, alternates between planning via MC-LAVE and supervised learning of self-generated language actions. Experimental results demonstrate that MC-LAVE-RL achieves new high scores various IF games provided in the Jericho framework Hausknecht et al. 2020), showing the effectiveness of tanguage-grounde MC-LAVE planning.
BACKGROUND
2.1 INTERACTIVE FICTION GAME
Interactive Fiction (IF) games are fully text-based environments where the observation and the action spaces are defined as natural language. The game-playing agent observes textual descriptions of the world, selects modeled as a special case of partially observable Markov decision processes (POMDPs) defined by tuple (S, A, S2, T, O, R. 7), where S is the set of environment states s, A is the set of language actions a, is the set of text observations o. T(s'[s, a) = Pr($++1 = s' st 8, 0g = a) is the transition function, R(s, a) is the reward function for taking action in state O(s) = is the deterministic observation function in state 8, and y E (0,1) 1) is the discount factor. The history at time step t, h4 =ou, Ro..... Ot-1, a,-1, ), is sequence of observations and actions. The goal is to find an optimal policy x² that maximizes the expected cumulative rewards, i.e. n arg m F (Er 7 ((ss,,a))
sanguage-basede action, and receives the associated reward. IF games can be
We use the same definition of observation and action space as |Hausknecht et al. (2020): Am- manabrolu & Hausknecht (2020); Cōté et al. (2018), i.e. An observation is defined by Or Otacse Otaame Otiyy, ax-1) where Otamse is the textual description of the current location of the agent, Oguan is the simulator response to the previous action taken by the agent, Ot is the information of agent's ' inventory, and at-1 is the previous action taken by the agent. An action is denoted by a A the set of valid
sequence of words a = (at oz ..... a 1dt1)). Finally, we denote Avalia(o)) actions for the observation o,, which is provided by the Jericho environment interface. Figure shows an example of observation and action in ZoRK1, one of the representative IF games.
2.2 CHALLENGES IN INTERACTIVE FICTION GAME
IF games pose important challenges for reinforcement learning agents, requiring natural language understanding, commonsense reasoning, and non-myopic language-grounde planning ability in combinatorial search space of language actions (Hausknecht al.. 2020). More concretely, consider the particular game state of ZORK1 described in Figure || In this example situation, a human player would be naturally capable of performing strategic planning via language understanding and commonsense reasoning: (1) the 'ciesed trap door' will have to be opened and be explored to proceed with the game, (2) however, acquiring the 'lantern' should precede entering the trap door since the cellar, which is expected to exist below the trap door, could be likely pitch-dark. Without such language-grounded reasoning and planning, the agent may need to try out every actions uniformly, most of them making it vulnerable being eaten by monster in the cellar who always appears when there is no light source. As a result, any agent that lacks the ability of long- torg-term planning with language reasoning is prone to be stuck at suboptimal policy, which enters the cellar to obtain an immediate reward and does nothing further to avoid encountering the monster that kills the agent immediately.
2

---

Published as a conference paper at ICLR 2021
Observation
Mass
Living Room. You are in the living roon. There is a doorway to the east, west, which appears nailed shut, trophy case, and a closed trap door at your feet. Above the trophy case hangs an elvish sword great antiquity. battery-powered brass lantern on the trophy case.
wooden door with strange gothic lettering
"pme"
with a great effort, the rug is moved to one side the room, revealing the dusty cover of closed trap door
You are empty-handed. ar-1: push rug
Action
Valid actions
(oe:: fnorth, turn on lantern, open trap door, open case, take sword, take lantern, east, take all)
ac: open trap door
Figure 1: Example of observation and actions from ZORK
To overcome the bottleneck, the agent should be able to infer that 'take 1antern" is worthy enough to be chosen in preference to other actions even though it gives no immediate reward. In this work, will precisely address such failures of myopic planning that arise from the lack of gegguage-groundee exploration strategy. To this end, we first propose MCTS- long-tew Then we further improve the search efficiency of MCTS-based
planning for nonmyopic-plannin planning by incorporating our novel language-groundee exploration strategy based on Language Action Value Estimates, which will be detailed in the subsequent section.
2.3 MONTE- CARTE-CARLO TREE SEARCH
Monte-Carlo Tree Search (MCTS) (Kocsis & Szepesvári 2006 Coulom 2006 Browne et al. 2012)
generic online planning algorithm that combines random sampling and tree search, which has become the de-facto standard method for large sequential decision decision-making problems. Starting from an empty tree, MCTS repeatedly performs the phases of selection, expansion, rollout, and backprop- agation to evaluate the nodes of the search tree with increased accuracy. UCT (Kocsis & Szepesvári, 2006) is the standard MCTS method, which adopts UCB (Auer et al. rule at each internal node of the search tree:
2002) as an action selection
log Nh)) N(h, a)
arg max [Q(h..) a) +
(1)
a
where the history of past observations and actions, Q(h, a) the average value of sampled returns with taking action in h, (h) is the number of simulations performed in h. N (h, a) is the number of times action a is selected in h, and c is a constant that balances exploration and exploitation. However, UCT suffers from severe search inefficiency in the problems with large action space such as IF games, since it requires to take every action at least once and relies only on uncertainty-driver (or visit-count-based) exploration.
PUCT (Silver et al., 2017 2018) partially addresses the challenges of IF games by adopting PUCB [Rosin 2011), which involves prior action distribution ot (h) and eliminates the need for choosing every action at least once. The action selection rule is given by:
(h)
arg max (Q a) Greer ((ahh)
(h,, a)
The prior distribution <-IAh) in Eq. (2) can be trained by behavioral cloning of (hyoots Food sam- ples obtained by the result of tree search in previous time steps (Anthony et al., 2017 Silver al., 2018). However, this procedure not only discards other search information such as abun- dant (h,, (h,,at, ar, he+1) samples obtained during the search but also hardly encourages information sharing across the semantically similar actions. Therefore, PUCT is still limited in search efficiency for the tasks with language action space, raising the need for a Language-drivee exploration strategy.
3 MONTE-CARLE PLANNING WITH LANGUAGE ACTION VALUE ESTIMATES
Language- -groudddd planning is essential to address the challenges of IF games. To this end, we need a mechanism incorporate language understanding and commonsense reasoning into the
3

---

Published as a conference paper at ICLR 2021
ploration strategy of search. In this section, introduce Monte-Cate planning with Language Ac- tion Value Estimates (MC-LAVE), a novel planning algorithm that combines MCTS with language- driven exploration. MC-LAVE does not rely any handerafted heuristic evaluation but starts tabula rasa, based only upon pre-trained word embeddings that can well define the semantic similarities be- tween two language actions. In addition, it only requires black-box simulator (r, ,')'') ~ ((, which yields (o, a, r, o') samples at each simulator query.
3.1 CREDIT ASSIGNMENT WITH SEARCH EXPERIENCE
Language-driven exploration in MC-LAVE starts by identifying which word sequences of language action are likely to yield large long-term rewards. This credit assignment of language action is done by Q-learning using all the experiences
00.0, r.))) obtained during the past searches. Following the previous work (Hausknecht et al.) 2020 Ammanabrolu & Hausknecht 2020. Am- manabrolu et al. 2020 Madotto et al. 2020), we assume that the current observation captures all is just text description of the game state. There- fore, we represent the Q-function as a function of the current observation and action, rather than a function of full history and action. Our parameterization of Qo.0. a) basically follows that of Deep Reinforcement Learning Relevance Network (DRRN) (He et al. 2016, Hausknecht et al., 2020), and more details be found in Appendix A Finally, the Qo is trained by minimizing the temporal difference еттоr using D:
the information regarding the latent state,
arg min (o.D (
Qálo',d' - - "
max a'E ('Ennaia))"")
where an exponential moving average of Φ, i.e. soft target update, and Avalia (o') is set of valid actions in the observation o' provided by Jericho environment. While PUCT of Eq. (2) also uses previous search information to construct a prior policy स, it is typically trained only on plan- ning trajectories (Aroot (ooot) that generally cover very limited regions. Therefore, it can hardly provide informative search guides for areas outside the planning trajectories. In contrast, Qo of Eq. 33) is trained by using every search experience encountered during search processes, thus it can potentially provide more information over a much broader set of states and actions. However, the credit assignment provided by Qo still struggles to provide useful information for novel language observation-actionn regions that have never been experienced, making its direct adoption as an explo- ration strategy inappropriate: the search process necessarily entails visits novel areas where Q+ does not work properly, and thus Q& may instead promote exploitation.
3.2 LANGUAGE-DRIVEL EXPLORATION VIA LANGUAGE ACTION VALUE ESTIMATES
In order to generalize past experiences novel situations, we adopt context-agnostic information sharing between language actions based on their semantic similarities. For example, if an action of 'take something' has ever been useful in past, we may expect that the action of "take something else' can also be worthy in other situations. Motivated by such instances, troduce Language Action Value Estimates (LAVE), which assigns non-uniform search priorities to each language action by examining whether its semantic neighborhood actions have been beneficial in the past.
in-
As the first step for LAVE, define semantic neighborhood of action a, a set of the past experi- ences whose actions share similar semantics with action a by:
((a)= {ō, a) d(a, a) < 8 where (ō,a,f,0') E D)
where 8 is hyperparameter that controls proximity threshold, and d(a, a) is distance measure between two actions and ā in language embedding space represented by the pre-trained word embeddings e(-):
v(a) ((a) d(a, a) = (Iv(a) (a)] where vaa) =
e(aa)
For simplicity, the average of the word embeddings (aa) the language action (or sentence) embedding, where the semantic similarity can be well-measured by the cosine similarity in the embedding space.
4

---

Published as a conference paper at ICLR 2021
Monte-Carlo planning with Language Action Value Estimates
ag
10
7 [1o
Planning trajectory U 7
Policy (a 0)
aigg utaK og Asnuil))
Qik. + (1..)) +1
Gruen Kotalo) + h bola)
Q-network (0.0)
Transition tuples { a.
any min of
log (0 (1()1))) (o("))
arg miin Bioaanor boD
2old df 2))mm))
Update Policy and Q-network
Figure 2: Overall architecture of policy improvement via MC-LAVE.
Then, the LAVE exploration bonus for the action a is estimated through a soft maximum over the Q-values of a's semantic neighborhood actions in order to encourage optimistic exploration.
[a(a) = loog [N(a) (o,0)EM(())
Σ
exp exp(Q((o.a))
(5)
Note that (a) in Eq. 5 relies only on the Q-values of (ō samples experienced in the past, thus can be reliably estimated. Also, it is context-agnostic in which the action is taken, thus circumvents the challenge of measuring the similarity between the very long textual observations, while promoting active information sharing between affordable language actions.
Finally, MC-LAVE encourages the language-driven exploration the selection phase of MCTS via LAVE (a),, which selects actions at each intermediate nodes by the following rule:
(N(h)
arg max at (vstia(())
Q(h,a)+ + N(h, a) +1
CevorTol(alo + GLAvE Inp (ap(a))
(6)
uncertainty driven exploration
prior knowledge encoding
language driven exploration
where (a)o)) a prior policy trained by behavior cloning past planning results, (a(a)) language-driven exploration bonus, CLAVE is exploration constant. MC-LAVE uses the policy for incorporating prior knowledge of the past planning trajectories. as well as the language-driven bonus (a(a) for facilitating information sharing between semantic neighborhood actions. MC- LAVE initially encourages to explore the actions with high language-driven exploration bonuses and low visit count, but it does not hurt the asymptotic behavior of MCTS (Theorem in Appendix C. The poeudo-code for the MC-LAVE is provided in Appendix
REINFORCEMENT LEARNING VIA MC-LAVE
As shown Silver al. 2017). MCTS can used as a strong policy improvement operator for reinforcement learning. Similarly, we use MC-LAVE as policy improvement operator for learning IF game. As a result, our reinforcement learning algorithm, MC-LAVE-RL, alternates between MC-LAVE planning and supervised learning of self-generated actions:
1. Planning Use the MC-LAVE with current policy тe and Q-function Q& to collect the n planning trajectories T U, (()) and experience replay D:
(1) = ((
(of a ()) D ((,,,r,,d)
where (1) is selected action at i-th trajectory t-th timestep by MCTS and T denotes episode length. (For the first iteration, MC-LAVE uses uniform policy and randomly ini- tialized Q-function.)

---

Published as a conference paper at ICLR 2021
Algorithms
DRRNI
TDQN'
KG-A2C1
MCRQ"BERT'
PUCT-RL
MC-LAVE-RL
Require-
Valid Action
Hard
Soft
Soft
Soft
Hard
Hard
ments
Resettable
External Info
ALBERT& &
Jericho-Q2 QA
Word Emhecding
Diflicult Games
ZOBK1
45.2
DEEPHOME
35
LUDICORP
6
22.8
PENTARI
27.2
17.4
50.7
58
64
68
DETECTIVE
197.8
169
207.9
330
322
330
Possible
Games
LIBRARY
6.3
14.3
19
TEMPLE
7.9
ZrUU
4.9
Table 1: Performance evaluation of various approaches for IF games in Jericho (Hausknecht al. 2020). Handicaps leveraged in each algorithm are described in the table. Valid Action indicates whether an algorithm uses valid action handicap provided by Jericho as hard constraint for the effective action space or as soft constraint via entropy loss over the valid actions (Ammanabrolu Hausknecht 2020). Resettable indicates whether an algorithm requires resettable simulator, i.e. the previously visited state can be restored. 10 DEEPHOME, LUDICORP are categorized as difficult games the other games are categorized as possible games by Hausknecht et al. (2020).
The results of other algorithms are from Hausknecht et al. 2222 Ammanabrolu & Hausknecht 20200', and Ammanabrolu et al. (2020)* respectively. All our results (PUCT-RL, MC-LAVE-RL) indicate averages over independent runs, and their standard errors provided in Appendix due to space limit.
Policy training Update the policy network parameter by minimizing the negative log- likelihood with using collected planning trajectories T, i.e. supervised learning with cross- entropy loss:
.0:00~ [- log No (0) (oo")))
arg min E, 1
3. Q-learning Update the Q-function parameter & by minimizing the temporal difference error from experience replay D:
[1+
Qold', - )
arg min E (o.....)))
max a' EdEvaata
We continue to update the policy through the above policy iteration with the MC-LAVE operator until the policy performance converges.
EXPERIMENTS
In this section, we show experimental results our approach on IF games included in the Jericho environment (Hausknecht et al.] 2020). The action spaces of IF games in the Jericho environment defined by the sequences of the game-dependent input vocabulary whose size is roughly from 500 to 2000. While the size of the vocabulary is limited compared large-scale open domain dialogues, still serves as a useful testbed to demonstrate the effectiveness of semantic-based information shar- ing of MC-LAVE" First, evaluate the performances of MC-LAVE-RL comparing with baseline methods. Second, we compare intermediate scores of MC-LAVE-RL on ZORK1 with a baseline (PUCT-RL) that uses PUCT as policy improvement operator, to show that MC-LAVE more effective for IF games than PUCT. Third, we investigate the effectiveness of semantic neighbor- hood by comparing the planning performance MC-LAVE under the various sizes of the semantic neighborhood. Finally, give qualitative analysis of our approach using representative ample, which shows how MC-LAVE focuses on semantically promising actions during the search. Detailed configurations of our experiments are described in Appendix B
For example, the ZORK] environment produces identical observations for taking the actions 'take 1antern' and 'get 1antern', where MC-LAVE can readily take advantage by exploiting the informa- tion sharing those semantically similar actions (Appendix H))

---

Published as a conference paper at ICLR 2021
PUCT-RL
MC-LAVE-RL
Methods
Planning
Learning
Planning
Learning
Iteration
31.9 + 1.4
36.6 + 1.0
30.4 2.0
36.6 + 1.0
Iteration
35.8 0.0
37.4 + 1.0
36.1 0.1
38.2 +
Iteration
35.3 0.2
39.0
0.0
41.2 - 0.5
43.0 = 1.0
Iteration 4
35.2 +: 0.4
38.2
= 0.8
43.8 - 0.1
45.2 = 1.2
Experimental results of the policy improvement with PUCT and MC-LAVE on ZoRK1. For each iteration, we perform the 25 planning with PUCT and MC-LAVE to collect planning tra- jectories and experience replay. All results indicate averages and standard errors over 5 trials.
Table 2:
5.1 EVALUATION ON INTERACTIVE FICTION GAMES
First, we compare the performance of MC-LAVE-RIL with the following algorithms: (1) DRRN
(Hausknecht et al. 2020p. variant of the DON algorithm (Mnih et al., (013) for natural lan-
guage action space, (2) TDQN (Hausknecht al. 2020), an extension of LSTM-DQN algorithm
Narasimhan et al. 2015) incorporating with lemplate-based action generation, (3) KG-A2C (Am-)
manabrolu & Hausknecht 2020), an actor-critic method with knowledge graph state representation, (4) MC!Q*BERT (Ammanabrolu et al. 2020), extension of KG-A2C with BERT-base knowl- edge graph construction and knowledge- graph-based intrinsic reward. In addition, we also compare MC-LAVE-RL with baseline called PUCT-RL, which uses PUCT policy improvement op-
erator.
Table 1 summarizes handicaps leveraged in each algorithm and the performance of MC-LAVE-RL.
and baseline algorithms across 9 IF games included in the Jericho environment. The results show that MC-LAVE-RL outperforms or matches the state-of-the-art results on 8 out of 9 games. Although MC-LAVE-RL requires more handicap or assumption, it performs the same or better than strong baseline MCIQ"BERT which requires similar assumptions and more requirements. In addition, MC-LAVE-RE RL achieves higher game scores on overall games compared to PUCT-RL, which is baseline algorithm that only excludes language-driven exploration strategy from MC-LAVE-RL-. Furthermore, MC-LAVE-RI. performs significantly better than other methods on difficult games such as ZO DEEPHOME, and LUDICORP, which are categorized by Hausknecht et al. (2020) as relatively challenging game due to the large action space and sparse rewards.
In the case of IORKI, as described in Section 2.2 other algorithms (except MC!Q*BERT, which concurrent work by Ammanabrolu et al. (2020) fail to overcome the bottleneck and stuck into the suboptimal policy, which leaves the agent being eaten by a monster in the dark with- out light source. On the other hand, MC-LAVE-RL successfully finds the optimal action (i.c. 'take lantern') on the bottleneck state by using the exploration strategy suitable for natural lan- guage spaces and obtains additional rewards by discovering novel states that cannot be reached with other methods. For instance, trajectories of MC-LAVE-RL agent frequently show that the agent overcomes bottlenecks and behaves crucial actions to complete the game, such as "killing the monster with sword' and 'putting the painting in the trophy case'. Further illus- trative examples of trajectories are provided in Appendix
5.2 REINFORCEMENT LEARNING VIA MC-LAVE
In order to understand the effectiveness of MC-LAVE as a policy improvement operator, we compare the performances of PUCT-RL and MC-LAVE-RL in ZORK Table 2 reports the intermediate results of planning and supervised learning in each iteration of the policy iteration. In each iteration, the policy and the Q-function are trained using planning trajectories and experience replay collected from 25 independent planning agents. As can be seen in Table 2 the performance of MC-LAVE-RL. improved more consistently than PUCT-RL, both in planning and learning- the beginning of the policy iteration, PUCT-RL improves the performance, but it fails to overcome bottleneck and converges to a suboptimal policy: PUCT utilizes the prior policy learned by imitating the planning method
results of the previous iteration to estimate the exploration bonus, but this uncertainty-base not much effective to encourage the agent to explore the action space that is not sufficiently covered. On the other hand, MC-LAVE-RL not only uses the prior policy, but also uses Q-Network for credit assignment to language actions. This allows a more focused exploration on semantically promising actions and consequently overcomes the bottleneck further improve the performance.
7

---

Published as a conference paper at ICLR 2021
PUCT
east
open
case
open door
take all
take lantern
take aword
lentern
curn on
Q(h,0)
2.65
6.80
13.81
2.03
11.34
0.22
9.00
Ta (a]o)
0.08
0.08
0.50
0.08
0.88
0.08
0.08
N(h, a)
30
105
37
52
42
MC-LAVE
east
open
tzep dooz
open
take all
take lantern
take aword
Juz on
7,86
10:59
14,10
2.30
14:23
-1.33
13.11
Via [a]o]
0.08
0.08
0.50
0.08
0.08
0.08
0.08
N(h, a)
58
85
(a(a)
13.21
35,55
25.35
38.21
49.81
2.25
34.72
Table 3: Illustrative examples of search results of PUCT and MC-LAVE on bottleneck state in ZORK I (see Figure D. Q(h, a) denotes the average of Monte-Carlo returns, To(alo) represents policy prior, (h,, a)) represents visit count of each action, Lg((a) represents language- -riven explo- ration bonus of MC-LAVE, Cpuer 200 and GLAVE 0.1 are used for the exploration constants.
5.3 THE EFFECT OF THE SIZE OF SEMANTIC NEIGHBORHOOD
The size of semantic the neighborhood is particularly cru- cial for the performance of MC-LAVE planning. To see this, we conducted a simple ablation experiment in ZORK I on the effect of varying proximity threshold 6, which con- trols the size of the semantic neighborhood of action (a)
Zork1
PUCT PUCT+RANDOM
Waaning performance
40
MC-LAVE
in Eq. 4 Moreover, to demonstrate that the LAVE ex- ploration bonus works as meaningful exploration bonus beyond simple random noise injection, we also present the result of a simple baseline PUCT+RANDOM, which uses MC-LAVE action selection rule of Eq. (6) with the neigh- borhood given by 10 randomly sampled actions. This base- line can be understood as performing the search with noise injection via the randomly chosen neighborhood, while not considering information sharing between semantically similar actions. As shown Figure 3 the performance of RANDOM is almost identical to PUCT, which supports that random noise injection alone does not lead to improving search efficiency. Moreover, the results of MC-LAVE shows that too small or too large 8 are not effective, which can be naturally explained as follows: (1) when = O, no sample in the replay buffer is considered as neighborhood, leading LAVE exploration bonus to always zero, (2) when ó (the largest possible value), every sample in the replay buffer is considered as neighborhood, yielding LAVE exploration bonus to a constant value for all a. Therefore, with either two extremes of 6, the MC-LAVE action selection rule of Eq. (6) is reduced to the PUCT action selection rule of Eq. (2). Finally, the moderately
38
36
0.0
0.2 0.4 0.6 0.8 1.0
1.5
2.0
Proximity threshold (6)
Figure 3: Performance of MC-LAVE planning ZORK1 for varying 6. The results are averaged over 100 trials, and error bars indicate the standard er- rors.
small 0.3 works the best, which highlights the importance of information sharing between meaningfully defined semantic neighborhoods to solve IF games efficiently.
5.4 QUALITATIVE ANALYSIS
In this section, we provide a qualitative analysis on the effectiveness of language-driven exploration in MC-LAVE. We show an illustrative example in Table demonstrates how MC-LAVE focuses more on the semantically promising actions, comparing the search results of PUCT and MC-LAVE in the bottleneck state of I described in Figure ! In this example, the 'open trap door' is a suboptimal action that obtains an immediate reward, while "take Lantern' gives no immediate reward, but it an optimal action when considering long-term outcome. can be seen in Table PUCT cannot explore effectively because the search is mostly based on uncertainty, and converges to suboptimal action (i.e. 'open trap door") that obtains an immediate reward. On the other hand, MC-LAVE assigns search priorities to actions based the optimistically aggregated Q-estimates of the past actions. As the result of focusing on semantically promising actions, MC-LAVE selects the optimal action (i.e. 'take lantern') even though it does not give any immediate reward. PUCT also performs non-uniform search based on prior policy, but this only encourages to explore the actions of previous behavior and does not focus semantically promising actions.
8

---

Published as a conference paper at ICLR 2021
6 RELATED WORK
Variants of Monte-Carlo tree search. Leveraging prior knowledge for MCTS has been one of the
most important directions for improving MCTS (Gelly & Silver 2007 Silver et al. 2016 2017 2018 Gelly & Silver 2011). PUCT (Rosin 2011 Silver et al. 2017) is one of the most popular PUCT is typically trained by imitation learning of past behavior; other search information, such as transition tuples and inferred Q-values, is discarded. To address this limitation, |Hamrick al. (2019) present Search with Amortized Value Estimates (SAVE), which incorporates Q-based prior knowledge into MCTS. SAVE, Q-function is fit by inferred Q-values and transition tuples from search, then is used as prior into MCTS. Although SAVE improves sample efficiency in MCTS, it lacks sunguage-grounder exploration strategy. Rapid Action Value Estimation (RAVE) (Gelly & Silver, 2011 is another notable method that addresses information sharing, which allows sharing action values in the search tree. However, RAVE is designed especially for the game Go and cannot be straightforwardyy applied to IF games. Furthermore, to leverage the prior knowledge given textual information, BBanavan et al. (2011) present a method that extracts the most relevant information to the current state and incorporates linguistic information into the Monte-Carlo search framework. However, they assume natural language documents that contain domain knowledge of the task.
MCTS algorithms, which incorporates prior knowledge as a policy. The prior policy
Reinforcement Learning via Monte-Carlo tree search. There are a number of recent works on using MCTS for reinforcement learning. Siilerr et al. (217) achieved successful results with MCTS as a policy improvement operator in the game of Go. Also, in the negotiation dialogue domain, Jang et al. (020) used Bayes-adaptive Monte-Carlo planning as a policy improvement operator to prevent the issue of diverging from human language. Inspired by these successes, we use the MC-LAVE algorithm as a policy improvement operator which effectively works on IF games.
Deep Reinforcement Learning for Interactive Fiction Games, IF games have attracted lot of interest from the RL research since the introduction of Jericho (Hausknecht et al. 2020), an OpenAI Gym-like (Brockman et al. 2016) learning environment for IF games. Jericho includes baseline RL agents such DRRN and IDQN. DRRN is variant of deep Q-Network architecture for handling natural language actions in text-based decision making tasks. TDQN is an extension of LSTM-DQN Narasimhan et al. 2015)) utilizing predefined templates in order to reduce effective search spaces of combinatorial language action space. More recently, wewellggegrrahh-aaee
approaches have been introduced to address the issues of partial observability and commonsense reasoning (Ammanabrolu
& Riedl 2019 Ammanabrolu & Hausknechi] [2200] Ammanabrolu et al.) 2020). KG-A2C (Am- manabrolu & Hausknecht] (2000) is an actor-critic algorithm that leverages knowledge graph state representation for commonsense reasoning. Ammanabrollu et al. (2020) introduce Q*BERT, an ex- tension of KG-A2C, which updates the knowledge graph by using the pre-trained language model ALBERT (Lan et al.] 20000), variant of BERT (Devlin et al., 2019). To encourage better exploration and overcome the bottleneck state IF games, they introduce MC!Q*BERT that additionally uses intrinsic motivation based on changes of the knowledge graphs.
7 CONCLUSION
We presented Monte-Carlo planning with Language Action Value Estimates (MC-LAVE), an MCTS-based algorithm for language action space, which combines MCTS with language-driven exploration strategy. MC-LAVE assigns search priorities to cach language action based Q-values of previously executed actions that share similar meanings, then invests more search effort into semantically promising actions. We then incorporated MC-LAVE into reinforcement learning by using MC-LAVE as a policy improvement operator. Our approach achieved remarkable results in difficult games that feature large action space and sparse reward and outperforms matches the state-of-the-art on the various IF games.
ACKNOWLEDGMENTS
This work was supported by the National Research Foundation (NRF) of Korea (NRF- the Ministry of Science and Information communication Technology (MSIT) of Korea (ITTP No. 2019-0-00075, IITP No. 2020-0-00940 and UITP No. 2017-0-01779 XAI), and the ETRI (Contract No. 20ZS1100).
2019M3F2A10722388 and A1F-20019IAA2C108766

---

Published as a conference paper at ICLR 2021
REFERENCES
Prithviraj Ammanabrolu and Matthew Hausknecht. Graph constrained reinforcement learning for natural language action spaces. International Conference on Learning Representations (ICLR), 2020.
Prithviraj Ammanabrolu and Mark Riedl. Playing text-adventure games with graph-based deep reinforcement learning. In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies (NAACI-HL.T), 2019.
Prithviraj Ammanabrolu, Ethan Tien, Matthew Hausknecht, and Mark O. Riedl. How to avoid being caten by grue: Structured exploration strategies for textual worlds. CoRR, abs/2006.07409 2020.
Thomas Anthony, Zheng Tian, and David Barber. Thinking fast and slow with deep learning and tree search. In Proceedings of the 31st International Conference Neural Information Processing Systems (NeurIPS), 2017.
Peter Auer, Nicolò Tesa-Bianchi and Paul Fischer. Finite-time analysis of the multiarmed bandit problem. Machine Learning, 2002.
S.R.K. Branavan, David Silver, and Regina Barzilay. Learning win by reading manuals in Monte-Carlo framework. In Proceedings of the 49th Annual Meeting of the Association for Com- putational Linguisties (ACL): Human Language Technologies, 2011.
Greg Brockman, Vicki Cheung, Ludwig Pettersson, Jonas Schneider, John Schulman, Jie Tang, and Wojciech Zaremba. Openai gym. CoRR, abs/1606.01544 2016
Cameron Browne, Edward Powley, Daniel Whitehouse, Simon Lucas, Peter I. Cowling, Stephen Tavener, Diego Perez, Spyridon Samothrakis, and Simon Colton. A survey of Monte Carlo tree search methods. IEEE Transactions on Computational Intelligence and Al in Games, 4:1-49, 2012.
Rémi Coulom. Efficient selectivity and backup operators in Monte-Carke tree search. Proceedings of the 5th International Conference Computers and Games, pp. 72-83, 2006.
Mare-Alexandre Côté, Ákos Kádár, Xingdi (Eric) Yuan, Ben Kybartas, Tavian Barnes, Emery Fine, James Moore, Matthew Hausknecht, Layla El Asri, Mahmoud Adada, Wendy Tay, and Adam Trischler. Textworld: A learning environment for text-based games. In Computer Games Work- shop at ICML/IJAII 2018, 2018.
Jacob Devlin, Ming-Woi Wei Chang, Kenton Lee, and Kristina Toutanova. BERT: Pre-training of deep bidirectional transformers for language understanding. In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguisties: Human Language Technologies CNAiiiessANAAA (NAACI-HLTT, pp. 4171-4188 2019.
Nancy Fulda, Daniel Ricks, Ben Murdoch, and David Wingate. What can you do with a rock? affor- dance extraction via word embeddings. In Proceedings of the 26th International Joint Conference on Artificial Intelligence (ICCAI), 2017.
Sylvain Gelly and David Silver. Combining online and offline knowledge in uct. In International Conference on Machine Learning (ICML), 2007.
Sylvain Gelly and David Silver. Monte-carlo tree search and rapid action value estimation com- puter go. Artificial Intelligence, 175(11):1856-117) 2011.
Jessica B Hamrick, Victor Bapst, Alvaro Gonzalz, Tobias Pfaff, Theophane Weber, Lars Bucsing, and Peter W Battaglia. Combining q gllaaringg and search with amortized value estimates. In International Conference on Learning Representations (ICLR), 2019.
Matthew Hausknecht, Prithviraj Ammanabrolu, Mare-Alexandre Côté. and Xingdi Yuan. Interac- tive fiction games: colossal adventure. In Proceedings of the AAAI Conference on Artificial Intelligence (AAAI), 2020.
10

---

Published as a conference paper at ICLR 2021
Ji He, Jianshu Chen, Xiaodong He, Jianfeng Gao, Lihong Li, Li Deng, and Mari Ostendorf, Deep reinforcement learning with natural language action space. In Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (ACL), 2016.
Youngsoo Jang, Jongmin Lee, and Kee-Eung Kim. Bayes-adaptive monte-carlo planning and learn- ing for goal-oriented dialogues. In Proceedings of the AAAI Conference on Artificial Intelligence (AAAI), 2020.
Levente Kocsis and Csaba Szepesvári. Bandit based Monte- Carlo planning. In Proceedings of the Seventeenth European Conference Machine Learning (ECML), 2006.
Zhenzhong Lan, Mingda Chen, Sebastian Goodman, Kevin Gimpel, Piyush Sharma, and Radu Sori- cut. ALBERT: A lite BERT for self-supervised learning of language representations. In Interna- fional Conference on Learning Representations (ICLR), 2020.
Andrea Madotto, Mahdi Namazifar, Joost Huizinga, Piero Molino, Adrien Ecoffet, Huaixiu Zheng, Alexandros Papangelis, Dian Yu, Chandra Khatri, and Gokhan Tur. Exploration based language learning for text-based games. Proceedings of the Twenty-Nint International Joint Conference on Artificial Intelligence (ICCAI), 2020.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Alex Graves, Ioannis Antonoglou, Daan Wier- stra, and Martin Riedmiller. Playing atari with deep reinforcement learning. 2013.
Nick Montfort. Twisty Little Passages: An Approach to Interactive Fiction. 2005.
Karthik Narasimhan, Tejas Kulkarni, and Regina Barzilay. Language understanding for text-based games using deep reinforcement learning. In Proceedings of the 2015 Conference on Empirical Methods in Natural Language Processing (EMNLP), 2015.
Graham Nelson. The Inform Designer's 's Manual. 2001.
Christopher D Rosin. Multi-armed bandits with episode context. Annals of Mathematics and Artifi- cial Intelligence, (13):203-230 2011.
David Silver, Aja Huang, Chris Maddison, Arthur Guez, Laurent Sifre,, George Van Den Driessche, Julian Schrittweeser, Ioannis Antonoglou, Veda Panneershelvam, Marc Lanctot, al. Mastering the game of go with deep neural networks and tree search. nature, 529(75877:484-49) 2016.
David Silver, Julian Schrittieser, Karen Simonyan, Ioannis Antonoglou, Aja Huang, Arthur Guez, Thomas Hubert, Lucas Baker, Matthew Lai, Adrian Bolton, Yutian Chen, Timothy Lillicrap, Fan Hui. Laurent Sifre. George van den Driessche, Thore Graepel, and Demis Hassabis. Mastering the game go without human knowledge. Nature, 2017.
David Silver, Thomas Hubert, Julian Schrittwieser, Ioannis Antonoglou, Matthew Lai, Arthur Guez, Mare Lanctot, Laurent Sifre, Dharshan Kumaran, Thore Graepel, al. A general reinforcement learning algorithm that masters chess, shogi, and through self- play. Science, 1126 1144, 2018

---

Published as a conference paper at ICLR 2021
A IMPLEMENTATION DETAILS
As discussed in section 4, MC-LAVE-RL. alternates (1) planning, (2) supervised learning and Q- learning. In the planning phase, multiple planning workers are run in parallel on distributed computing system to collect various planning trajectories and experience replay. After planning, we merge collected trajectories and experience replay and train the policy network and Q-Network using merged trajectories and experience replay respectively. For Q-Network, we exploit the same architecture used DRRN (He al. 2016) illustrated as Figure [5] which takes an observation or, an action as input and outputs (o (z).. For the policy network, we use network architec- ture similar with DRRN as described Figure which directly outputs fa lr), an unnormalized probability of action a₂ given observation or, i.c. To ve(aolor) fo fa(aloo)). Our code is publicly available
So (a)()))))
Qo(or, as)
Sigmoid
ReL.U
Dense
Concatenate
Concatenate
LSTM
LSTM
LSTM
LSTM
LSTM
LSTM
LSTM
0 Fdese
Sgnsse
tnnw
1
Ldesc
Or
Saame
a2 -
a2
Figure 4: Policy network
Figure 5: Q-Network
B EXPERIMENTS DETAILS
Hyperpuraneters
ZORKI
DEEPHOME
LUDICORP
PENTARI
DETECTIVE
LIBRARY
BALANCES
TEMPLE
ZrUU
À (discount (actor)
0.95
0.95
0.95
0.95
of max iterations
4
4
Eneighbothood (hreshold)
0.3
0.3
0.3
0.3
0.3
0.3
Max search depth
10
10
20
10
10
15
10
15
episode length
8 of simulations per action
50
50
50
50
50
50
50
50
50
planning workers
GLavE QuICT
1.0
1.0
2.0
1.0
0.1
1.0
1.0
1.0
1.0
50
200
Table 4: Configurations of MC-LAVE-RL used in our experimental results. Hyperparameters in the upside of the table were globally adapted in the planning-learning framework and the other hyperparameters are used only in the MCTS planning phase.
12

---

Published as a conference paper at ICLR 2021
C ASYMPTOTIC OPTIMALITY OF MC-LAVE
In this section, we show that the asymptotic optimality of PUCB (Rosin 2011) is still held after the introduction of the aaguage-driven exploration bonus in Eq. 5 We start by restating the theoretical result for PUCB.
Lemma 1. (Theorem / in (Rosin 2011)) For any stochastic policy vta) > 0 with Σ. ((a) 1,
e > O, and 02 > PUCB action selection rule at trial t. defined as:
logt r((,a) +aV N(a)
logt
arg max
02
T(a)
where N(a) is the number of simulations action a taken in the past, r(t, a) an empirical average
reward of action a at the start of trial t., Then, expected regret of PUCB action selection rule is bounded by O( O(yn l) Vn
Note that the prior policy x in the PUCB rule encourages the actions that have a high value of π (() be selected more often. In this work, use a variant of PUCB in (Silver al. 2017).
Theorem 2. MC-LAVE action selection rule at trial is defined as:
logt arg max r(t,a) + o N(a)
logl
log L
C2 T(a)
C3
L(a)
where (()) is the number of simulations action a taken in the past, r(I, a) an empirical average reward of action at the start of trial x(a) > O is a stochastic policy with E. T(a) = 1, e >> 0, 09 > 0, 03 > and L(a) > a bonus of action a. Then MC-LAVE action selection rule also achieves expected regret bounded by O O(ynlogn) vn 1.
Proof. The theorem can be proved by showing that the MC-LAVE action selection rule can be represented the PUCB action selection rule with another policy. MC-LAVE action selection rule is defined as
logt arg r(t, a) + + N(a)
logt
1
log
C2 T((a)
V
C3
L(a)
V
logt
C3
1
log
arg max
r(t, + c1
02 T(a)
N(a)
C2 L(a)
t
Define p(a), n/ (a), cg as follows:
p(a)
1
p(a)
n <a
E. p(a)
02
Σ. P(a)
L(a)
Then MC-LAVE action selection rule can be represented as follows:
log N(a)
log
arg max
al,,a) + +
C2 p(a)
logt
1
logt t
arg max
r(t, a) + +c1 |
N ((a)
C2 Σn p(a)
p(a)
Σ, p(a)
logt
log
arg max
al, + +c
N(a)
n (((aa
which induces PUCB action selection rule with another policy n' and coefficient de Hence, by Lemma I MC-LAVE achieves expected regret bounded by the same order with PUCB, which is O( log(n)) Vn > 1.
Thus, in the same manner, obtain the analysis of UCT from that of UCB, i.e. induction with mild assumption on the drift-condition of the inherent non-stationary bandit problem, we can obtain the analysis of MCTS using MC-LAVE using the above result.
13

---

Published as a conference paper at ICLR 2021
D PSEUDOCODE OF MC-LAVE
Algorithm Monte-Carlo Planning with Language Action Value Estimates (MC-LAVE)
procedure SEARCH(>O)
Ou (sv)
hg -
procedure SELECTACTION(H)
repeat
SIMULATE (so, ho, 0)
f- arg max of (vaii
Q(h,a) + (o((o) V Nia
until TIMEOUT O
return arg max a(
aEAvati (og)
+LAVV La((a) V (((A)
N(k.o)41
end procedure
if 2V (h. a) = 0 then
procedure SIMULATE(S, h, if = (planning horizon H) then return O
rollout + truc else
rollout <- false end if
end if
a, rololoout + SELECTACTION(1)
return (a, rollout] end procedure
r. rr, o < G(s,a) a)
h' + hao'
if rollout then
procedure ROLLOUT(s,) ()
ROLLOUT(S' (s
if = (planning horizon H) then return 0 end if
else
R'' + SIMULATE(S',Ht (1,11
end if
f O(s)
R a --r--- R'
(T(
TH
N(h) + ((h) +1
[r,s' o0]
<- as
N(h, a) + N(h, 0) +
return ROLLOUT(s +-1) 1)
Q(h, a) < a(h,a) + R a(h
end procedure
N(..))
return
end procedure
14

---

Published as a conference paper at ICLR 2021
E
COMPARISON RESULTS OF SOFT AND HARD CONSTRAINTS
Algorithms
KG-A2C-Soft
KG-A2C-Hard
PUCT-RL
MC-LAVE
Valid Action
Soft
Hard
Hard
Hard
Roquie-
ments
Resettable
External Info
Emhedding
ZORKI
40.2
38.2 0.8
45.2 1.2
Diltiull Games
DEEPHOME
1 0.0
20 2.1
28.6 2.9
35 : 0.6
LUDICORP
18.6 - 0.5
19.8 1.0
18 + 0.0
22.8 +: 0.2
PENTARI
+
4.9
64 2.4
68 + 2.0
DETECTIVE
318
338 3.4
322 2.0
330 + 0.0
Possable
LIBRARY
15.8
1.0
1.0
19 : 0.0
BALANCES
10 + 0.0
10
10+
10 + 0.0
TEMPLE
8 & 0.0
8
8
8 + 0.0
ZTUU
5 0.0
5
5.0
7 7 2.7
Table 5: Experimental results comparing soft and hard constraints of valid action handicap. KG- A2C (Soft/Hard) indicates the use of valid action handicap as a (soft constraint via entropy loss over the valid actions/hard constraint for the effective action space). All results indicate averages and standard errors over independent runs.
The original KG-A2C (published state-of-the-ar,, denoted as KG-A2C-Soft in Table 5) uses the valid action handicap as a soft constraint via entropy loss over valid actions, while our MC-LAVE- RL exploits the valid action handicap hard constraint that constrains the effective action space directly. For an equivalent comparison in terms how a valid action handicap is handled, we also implemented KG-A2C-Hard, which uses the valid action handicap as hard constraint for the effective action space. Ta shows that MC-LAVF-RI. still significantly outperforms or matches both KG-A2C-Soft and KG-A2C-Hard on the 8 out of games. This result implies that reducing an effective search space alone may not be sufficient, and iinuaage-grouded planning ability is the key to solve IF games successfully. Still, care must be taken to interpret the result of Table in that KG-A2C is pure RL method and MC-LAVE-RL. is an RL algorithm that requires an additional planning assumption (i.e. resettable simulator).
15

---

Published as a conference paper at ICLR 2021
F ILLUSTRATIVE BEHAVIOR EXAMPLES
To understand how MC-LAVE-RL. discovers more novel states than other reinforcement learning agents, we provide illustrative examples that represent the behavior of each agent playing ZORKl.
normal
North of House
gives a reward when agent firet reached
(1northh
(2)eaa
bottieneck state
Nest of Start
Living
weat
Kitchen
(4) west
Behiind House
Cellar
Roon
(+10)
open
window
(+25)
(u)p rug (T)n trap deor (8)
Ground
Basement
(a) Behavior DRRN, KG-A2C and PUCT-RL playing ZORK1
Up
(4) (gg(+5)
normal state
Tree
gives reward when agent take first some item
up) up
(6) south
givns rewore when agent first reached
Forest Parth
bottleneck
(15)turn on lantern
north
so)th
(+25)
Collar
(1)ortth
House
(?) east
(:6)
Wes't of House
Living Room
(10)
Kitchen
we)
Behind House
East of (17)east Chasn
Gallery
Start
(+10)
(8) op)n
window
(18) painting(+4)
(11)puah rug t12) lantern (13)spen trap door d14)
Ground
Basement
(b) Behavior of MCIQ"BERT playing Z
take egg egg(-5) (+5)
(23)up
givns roward agent first itom
Forest
gives agent first reached
Patth
bottlenack state
north
North of House
(10)
(1b)up
(21)
(1)oothh
(2)east
(+25)
Cellar
Studio
(pr) trophy case (18)put painting in the case(+6)
(:1)aouth
(14)north
West of House
Living
(5)sest
Kitchen
(4)rest
Behind House
East of Chass
(12)
Gallery
Room
(16) (19)
(20) east
(+10)
(3)open window
(13) painting(+4)
(6)push rug
(?) take lantern
open trap door
down
Ground
Basement
(c) Behavior of MC-LAVE-RL playing ZORK]
Figure 6: Illustrative examples on ZORK1 1 that represents the behavior of learned policy by baselines and our algorithms.
16

---

Published as a conference paper at ICLR 2021
G ILLUSTRATIVE EXAMPLES FOR LANGUAGE-ACTION EMBEDDING
We present the t-SNE visualization for the language-action embedding and the (semantic) neigh- borhood of the action 'take lantern' ZORKl. In the following figures, the color of points indicates the observation-maaginnlizzee Q-value of each action with respect to the replay buffer, which is defined as:
((aa))-D(a)
(((-))) [Q) s.t. D(a) ((ā ā where (ō, D}
Only a subset of the entire language actions is presented in the figures to prevent the cluttered presentation. The bold fonts with cyan and yellow indicate the (semantic) neighborhood of action 'take lantern' and 'open trap door', and the bold font with magenta indicates the common neighborhood of them. As shown Figure 7 the semantic neighborhood of language actions defined by the pre-trained word embedding composed of semantically similar actions. However, as shown in Figure 7 when using the word embedding fine-tuned by Qo training, the semantic neighborhood includes number of irrelevant actions. This result highlights the importance of word embedding for effective information sharing in MC-LAVE-RL.
visualization with pre-trained embedding
1-SNE visualization with fine-tuned word embedding
Sre
Cost white
clortie 19th
geve
chis
Focch
Com
take
ta
epen
jos Lillomm
rale
tuki App
take parfingg
fruit
Take Like Sirk
wild
take
open widaan
lake Sertigg slows wetern tare 2 lastem
take bettle
oper sweerd
Figure 7: (Left) The t-SNE visualization for the semantic neighborhood of language actions defined by the pre-trained word embedding. The language-actions sharing similar meanings are located at similar points in the embedding space. (Right) The t-SNE visualization for the neighborhood of language actions defined by the word embedding fine-tuned by Qs training. The training objective of Qo does not account for the semantics of language actions but only considers rewards, thus the resulting embedding loses the linguistic semantics of words.
17

---

Published as a conference paper at ICLR 2021
H ILLUSTRATIVE EXAMPLE FOR SEMANTIC-BASED INFORMATION SHARING
MC-LAVE
east
open
open
lantern
aword
tuzn on
Crap door
lantera
@(h,a)
7.86
10.59
14.10
2.30
14.23
-1.33
13.11
0.08
0.08
0.50
0.08
0.08
0.08
0.08
N(h,0 a)
23
58
85
47
67
63
(a(a)
13.21
35.55
25.35
38.21
49.81
2.25
34.72
MC-LAVE
open
open
take all
lantern
take sword
buza on
trap door
lantern
Q(h,a)
6.22
11.37
14.29
4.05
15.31
-0,82
13,88
(a
0.08
0.08
0.50
0.08
0.08
0..8
0.08
N(h,0 a
21
47
125
35
57
54
La(a)
13.21
35,55
25.35
38.21
41.43
2.25
34.72
Table 6: An illustrative example of search results of MC-LAVE bottleneck state in ZORK (see Figure I with modifying the action 'take Lanterd to "get lantern'. The above result with the action 'take lantern' is the same
Qh,, a) denotes the average of Monte- Carlo returns, To (a(a)) represents policy prior, N(,, a represents visit count of each action, Lş(a) represents language-driven exploration bonus of MC-LAVE. Note that some differences in Q(h, a) and N (h, a) between results are due to two independent simulation runs.
Table 3
In order to show the effectiveness of language-action embedding, we further investigate MC-LAVE planning on the bottleneck state presented Figure [ and Table 3 Specifically, in the bottleneck state, we artificially modified the action "take Iant ern to 'get lantern' within the valid action set which is used for MC-LAVE planning. As shown Table 6 MC-LAVE still can successfully select the modified 'get lantern' over 'open trap door' as a final action, even though 'get lantern had never seen by the agent before. This generalization property of MC-LAVE due to the effect of pre-trained embedding, which shows the importance of language-action embedding for information sharing across semantic space.
18


Reviews:
[{"review_id": "zUmR2mUr-3", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary: This paper presents a method of incorporating prior knowledge into MCTS via language, using interactive fiction games as a test bed. Their method MC-LAVE used word embeddings on the language action space to help induce a non-uniform distribution over the action space.\n\nPros:\n1. The motivation is very clear, MCTS is generally action agnostic and using language to provide additional semantic information to it can prove to be very effective. The search + RL paradigm has already been shown to work well in cases like Go. The idea of using cosine similarity in word embeddings is a simple but effective way of biasing the MCTS in the right directions.\n2. The paper in general is well-written and easy to follow, the qualitative analysis and the additional diagrams in the appendix illustrating the variations in policies are appreciated.\n\nCons:\nSome of the claims are not quite accurate even when compared to the works already cited here -\n1. PUCT-RL is the only directly comparable baseline given action space and other handicap differences. \n(i) It appears that MC-LAVE is using the valid action handicap in Jericho as a *hard constraint* (Eq. 6 and Algorithm 1) - this means that the MC-LAVE only has a search space of on average < 100 actions per step. The other baselines all use the full template-based action space (except the DRRN) of size 10^8 - a auxiliary entropy loss is used there derived from the valid actions but it is not a hard constraint. As noted in contemporary works such assumptions dramatically reduce the difficulty and language understanding capabilities of text games (Yao et al. 2020 https://arxiv.org/abs/2010.02903).\n(ii) The second issue is that MC-LAVE assumes that the simulator is deterministic and can conduct rollouts and reset within the span of an episode - standard planning assumptions but incompatible with all other baselines (except for MC!Q\\*BERT) which do not use this handicap. \n(iii) Some suggested baselines that make these assumptions would be a heuristic A\\* search, or modifying any of the existing algorithms to use smaller action spaces and/or apply alternative exploration strategies seen in previous works such as modular policy chaining (that MC!Q*BERT uses) or Go-Explore (Madotto et al. https://arxiv.org/abs/2001.08868)\n2. Even with the results that already exist, it is claimed (for example in section 5.1) that MC-LAVE-RL is the only algorithm to pass bottlenecks such as getting the action \"take lantern\" right. But the diagrams in the appendix for the policy the MC!Q*BERT agent learns as well as the original paper for that agent show otherwise? \n3. Other concerns along these lines: all of this paper's results are averaged over 3 runs while the other baselines are over 5 runs - an indication of variance would be useful to assess whether the differences are significant, especially since some of the margins quite small (23 on MC-LAVE-RL vs 22.8 for the next best on Ludicorp) added to the fact that hyperparameters are different for each game - does that imply that the authors tuned the hyperparameters for each game? The analysis shows that it outperforms only all the other baselines only on 5/9 games and matches on 3. The abstract and intro claim state of the art across all games. I think this means that some amount of claim rewriting is required in addition to the changed baselines.\n\nOverall, I think this paper has a clear motivation and some interesting ideas on how to incorporate semantic language information into planning algorithms. However, in its current state - the comparisons made are not meaningful which makes the claim of state of the art tenuous (state of the art does not matter so much as showing that you make progress in line with the motivation). Making these comparisons would require a heavy rewrite starting from the abstract to the analysis and so I would recommend reject right now but look forward to seeing an updated version of the paper in the future with some of these changes.\n\nAfter author response:\nSee reply comment in the thread below for further score justification.", "extra_scores": {}, "extra_text": {}}, {"review_id": "tZAqxg5rBSJ", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper introduces Monte-Carlo planning with language action value estimates to guide exploration. The method builds on top of MCTS w/ PUCT, where a policy distribution over actions is introduced to estimate Q for actions not seen during sampling. The modification proposed here is an additional term to the Q estimate, which is a weighted average of Q values of similar actions, where similarity is computed using word embeddings of words that make up an action. The authors show gains over MCTS  w/ PUCT on 8/9 real text games.\n\nThe modification is small, but it is intuitive and shows consistent gains over the baseline without this modification. Some concerns I have are:\n\n1. what is the variance for the experiments in Table 1?\n2. sample size of 3 is very small, can you increase this and report the mean/variance?\n3. it seems like a single bottle-neck state is crucial for achieving good Zork1 performance. Is this the case with the other two \"difficult games\" DeepHome and Ludicorp? Do the authors have qualitative observations as to why this method helps on these two games?\n4. this paper is missing what I think is a very relevant citation in Branavan 2012 (https://arxiv.org/abs/1401.5390), which uses language from a game manual to guide MCTS.", "extra_scores": {}, "extra_text": {}}, {"review_id": "LDtsxV76aoa", "reviewer": "AnonReviewer5", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper presents a novel MCTS-based policy improvement operator called MC-LAVE designed specifically for environments with text-based action spaces. MC-LAVE adds an additional term to PUCT that shares information across semantically similar actions. This additional term for a given action $a$ is set to the soft maximum over the Q function evaluated at all $(o, \\bar{a})$ pairs of transitions in the replay buffers whose transition action $\\bar{a}$ is within some cosine distance $\\delta$ of the action $a$.  As shown in Appendix C, addition of this term preserves the expected regret bounds of PUCB. The paper reports empirical improvements over existing methods on various interactive fiction (IF) games in the Jericho suite.\n\nThe results of MC-LAVE are promising, however, the paper leaves me with a few lingering questions that I feel should be resolved before I would feel this paper were ready for conference publication:\n\n1. It is not clear to me that the improvements are, as repeatedly emphasized by the authors throughout the paper, due specifically to MC-LAVE leveraging semantic similarity of useful actions to focus on the most promising actions: It is possible that the additional term is simply injecting additional randomness to the action selection rule, which benefits exploration. To control for this possibility, the authors should include a baseline that performs the action selection rule of MC-LAVE with the semantic neighborhood N(a) of action $a$ set to a uniformly randomly sampled set of valid actions in each corresponding state of the replay buffer. \n\n2. Related to the above point, the hyperparameter $\\delta$ seems to be quite important, as it effectively defines the size of the neighborhood. However, neither the exact setting of $\\delta$ used in the experiments nor the effect of varying $\\delta$ is presented in the paper. Relatedly, another important baseline similar to the random neighborhood baseline mentioned above is setting $\\delta$ to a very large number.\n\n3. I am not entirely convinced that the action-spaces of the IF games present a suitable testbed for the semantics-based information sharing that MC-LAVE attempts to achieve, as the action space vocabulary for valid actions in each state seems quite limited and tending to repeat the same key verbs, based on the presented examples in Table 3. Perhaps some comment about the diversity of these games could be made to defend against this criticism, or perhaps the action space of the games could be edited to exhibit a more diverse vocabulary to allow better empirical demonstration of the effectiveness of MC-LAVE in performing semantics-based info sharing across related actions.\n\n4. How important are the embeddings? Based on the presented examples, it is not clear to me how the semantics-based info sharing defined in the MC-LAVE action selection rule should benefit the agent in choosing \"take lantern\" over \"open trap door\" in a meaningful way beyond just recognizing that \"take\" is often useful in other, albeit, completely different contexts. In that case, perhaps word embeddings are not even necessary, but rather maintaining a table of Q-values for $(o, a_i)$ for each action word token $a_i$ and taking the soft maximum over the corresponding Q-values of action tokens might suffice.\n\n5. I would love to see some examples of how the language-driven exploration term in the MC-LAVE action-selection rule weighs the various action tokens in a fully-trained policy, and which words from other states in the replay buffer the words are being linked to. I think such a qualitative analysis would be useful in better understanding how the \"language-driven exploration\" term enables the agent to attain the empirical gains reported.\n\n6. It's not clear how MC-LAVE, even if effectively sharing info between semantically-related words at each node of the MCTS tree, is improving \"non-myopic exploration\" over alternative methods, which point the authors seem to emphasize throughout the preliminary sections of the paper. \n\n7. Some discussion around why the authors think MC-LAVE underperforms w.r.t. existing methods on ZTUU would improve the discussion of the experimental results.", "extra_scores": {}, "extra_text": {}}, {"review_id": "8gOMLCJbqFm", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper presents a method for combining planning an learning in text-based games. In particular it augments Monte-Carlo Tree Search to include a language-similarity bonus to encourage exploration of similar actions. This bonus works by computing a Language Action Value Estimate - which is based on increasing the score of an action by an amount corresponding to the Q-Values of similar actions the agent has experienced. Similarity here is defined by cosine distance in action-embedding space. Using this augmented MCTS algorithm the authors introduce their MC-LAVE agent which alternates between MCTS planning and policy training via supervised learning from the planned trajectories. Experiments across nine IF games show consistent improvement relative to prior RL and planning-based agents. Additional analysis is performed to show how MC-LAVE uses the language action value estimates to learn how to overcome a notable bottleneck in the game of Zork.\n\nI found this paper is well-motivated and principled in its application of Monte-Carlo methods to text-based games. The results show clear improvement over previous agents on a large majority of games and the utility of the Language Value Estimator is clearly shown by the comparison against PUCT-RL.\n\nI have read the author rebuttal and appreciate the changes made to clarify the distinctions and handicaps used by each of the algorithms. Additionally the exploration into ranges of the delta parameter was appreciated.\n\nMy largest issue with the paper is that it does not make a clear distinction between pure-RL methods (DRRN/TDQN/KG-A2C) and methods that leverage additional functionality/handicaps to make planning possible (MC!Q*Bert/PUCT-RL/MC-LAVE-RL). Reinforcement learning and planning are different paradigms and even though MC-LAVE-RL does both planning and policy learning - its use of the MCTS planner makes it not an apples-to-apples comparison with the pure RL methods. To this end, I'd strongly encourage the authors to include a discussion of which Jericho handicaps are used by MC-LAVE and make a clear distinction in the presented results between the planning and the pure-RL agents.\n\nThe delta hyperparameter for neighborhood size is not given in Table 4 - it would be good to understand what value was used in practice and how large was the effective neighborhood. For example, it would be interesting to understand the effective edit distance in terms of the number of words that could be substituted while remaining in the same neighborhood - e.g. are \"take lantern\" and \"take egg\" in the same neighborhood? Taking this idea further - I would be interested to understand how algorithmic performance changes as a function of the neighborhood size - I imagine there may be a sweet spot in terms of this hyperparameter.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: I thank the authors for their submission and very active participation in the author response period. The paper is well motivated, clearly written and demonstrates empirical gains. In discussions, R4 and R5 were championing the paper. R1 stated that the paper improved, but insists that claims of state-of-the-art, given the simplifications induced by a deterministic simulator and hard valid action constraint, are not justified without additional baselines to compare to. The authors have toned down state-of-the-art claims in the revised version of the paper. I agree with R4 that the added requirements in Table 1 sufficiently explain the constraints under which MC-LAVE can be applied. Given the strong positive sentiment by R4 and R5, the positive assessment by R3, and the detailed response by the authors, I am recommending acceptance of the paper.
Decision: Accept (Poster)