Reinforcement Learning for Mapping Instructions to Actions

Proceedings of the 47th Annual Meeting of the ACL and the 4th IJCNLP of the AFNLP, pages 82–90, Suntec, Singapore, 2-7 August 2009. c⃝2009 ACL and AFNLP Reinforcement Learning for Mapping Instructions to Actions S.R.K. Branavan, Harr Chen, Luke S. Zettlemoyer, Regina Barzilay Computer Science and Artificial Intelligence Laboratory Massachusetts Institute of Technology {branavan, harr, lsz, regina}@csail.mit.edu Abstract In this paper, we present a reinforce- ment learning approach for mapping nat- ural language instructions to sequences of executable actions. We assume access to a reward function that defines the qual- ity of the executed actions. During train- ing, the learner repeatedly constructs ac- tion sequences for a set of documents, ex- ecutes those actions, and observes the re- sulting reward. We use a policy gradient algorithm to estimate the parameters of a log-linear model for action selection. We apply our method to interpret instructions in two domains — Windows troubleshoot- ing guides and game tutorials. Our results demonstrate that this method can rival su- pervised learning techniques while requir- ing few or no annotated training exam- ples.1 1 Introduction The problem of interpreting instructions written in natural language has been widely studied since the early days of artificial intelligence (Winograd, 1972; Di Eugenio, 1992). Mapping instructions to a sequence of executable actions would enable the automation of tasks that currently require human participation. Examples include configuring soft- ware based on how-to guides and operating simu- lators using instruction manuals. In this paper, we present a reinforcement learning framework for in- ducing mappings from text to actions without the need for annotated training examples. For concreteness, consider instructions from a Windows troubleshooting guide on deleting tem- porary folders, shown in Figure 1. We aim to map 1Code, data, and annotations used in this work are avail- able at http://groups.csail.mit.edu/rbg/code/rl/ Figure 1: A Windows troubleshooting article de- scribing how to remove the “msdownld.tmp” tem- porary folder. this text to the corresponding low-level commands and parameters. For example, properly interpret- ing the third instruction requires clicking on a tab, finding the appropriate option in a tree control, and clearing its associated checkbox. In this and many other applications, the valid- ity of a mapping can be verified by executing the induced actions in the corresponding environment and observing their effects. For instance, in the example above we can assess whether the goal described in the instructions is achieved, i.e., the folder is deleted. The key idea of our approach is to leverage the validation process as the main source of supervision to guide learning. This form of supervision allows us to learn interpretations of natural language instructions when standard su- pervised techniques are not applicable, due to the lack of human-created annotations. Reinforcement learning is a natural framework for building models using validation from an envi- ronment (Sutton and Barto, 1998). We assume that supervision is provided in the form of a reward function that defines the quality of executed ac- tions. During training, the learner repeatedly con- structs action sequences for a …

Content truncated to 500 words