Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: 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.

The 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:

1. 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. 

2. 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.

3. 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.

4. 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.

5. 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.

6. 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. 

7. 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.
review_title: Neat idea with promising results, but deserves deeper experimental investigation

final_score: rating: 4: Ok but not good enough - rejection
review_content: 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.

Pros:
1. 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.
2. 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.

Cons:
Some of the claims are not quite accurate even when compared to the works already cited here -
1. PUCT-RL is the only directly comparable baseline given action space and other handicap differences. 
(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).
(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. 
(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)
2. 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? 
3. 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.

Overall, 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.

After author response:
See reply comment in the thread below for further score justification.
review_title: Review 1

final_score: rating: 6: Marginally above acceptance threshold
review_content: 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.

The modification is small, but it is intuitive and shows consistent gains over the baseline without this modification. Some concerns I have are:

1. what is the variance for the experiments in Table 1?
2. sample size of 3 is very small, can you increase this and report the mean/variance?
3. 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?
4. 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.
review_title: Small modification with interesting results

final_score: rating: 7: Good paper, accept
review_content: 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.

I 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.

I 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.

My 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.

The 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.
review_title: Language Value Estimates in MCTS Search

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)