@inproceedings{branavan-zettlemoyer-09_reinforcement-learning-for-mapping-action-names,
  title={Reinforcement learning for mapping instructions to actions},
  author={Branavan, SRK and Chen, H. and Zettlemoyer, L.S. and Barzilay, R.},
  booktitle={Proceedings of the Joint Conference of the 47th Annual Meeting of the ACL and the 4th International Joint Conference on Natural Language Processing of the AFNLP: Volume 1-Volume 1},
  pages={82--90},
  year={2009},
  organization={Association for Computational Linguistics},
  annote = {
In this paper, they presented a reinforcement learning approach for inducing a mapping between instructions and actions. This approach is able to use environment-based rewards, such as task completion, to learn to analyze text. They showed that having access to a suitable reward function can significantly reduce the need for annotations.During training, the learner repeatedly constructs action sequences for a set of documents, executes those actions, and observes the resulting reward. They have used a policy gradient algorithm to estimate the parameters of a log-linear model for action selection.Their policy is modeled in a log-linear fashion, allowing to incorporate features of both the instruction text and the environment.
\\
They consider a document(d) as a sequence of sentences
\begin{displaymath} 
	d = (u_{1},u_{2}......,u_{l})
\end{displaymath}
Goal is to map d to a sequence of actions 
\begin{displaymath}
	\vec{a} = (a_{0},a_{1}......,a_{n}).
\end{displaymath}

An action \textbf{a} = (c, R, W') where c in command, R are it's parameter and W' are the words describing c and R. The environment state $\xi$ specifies the set of objects available for interaction, and their properties. On performing an action \emph{a} in state \emph{s} leads to a new state s' according to the distribution p(s'$\vert$s,a).Action is predicted by the rule  p(a$\vert$s;$\theta$) called the \emph{policy} and defined as follows:\\
\[p(a\vert s;\theta)=\frac{e^{\theta.\phi (s,a)}}{\sum_{a'} e^{\theta.\phi (s,a')}}\]
The goal of training is to estimate parameters $\theta$ of the action selection distribution p(a$\vert$s;$\theta$) where $\phi$(s,a)is an n-dimensional feature representation.
\\
They select $\theta$ so that the value function
\begin{displaymath} 
	V_{\theta}(s) = E_{p(h\vert\theta)}[r(h)]
\end{displaymath}
 is maximized.Here h is the history that is the sequence of states and actions and r(h) is the reward function that returns one when h matches the annotation for the document being analyzed, and zero otherwise.
 \\
When annotations are completely unavailable, learning is still possible given informative feedback from the environment.Crucially, this feedback only needs to correlate with action sequence quality.Reward function r(h) has a crucial role here.
\\
This is better than other ideas as it can work even without annotated data.They applied their work on Microsoft Window troubleshoot options and on a puzzle game.The result showed that if a fully unannotated document is provided then the results obtained are not that good when they there were some annotated instances.But still satisfying results were obtained for unannotated document also.
\\\\
--Bhavishya Mittal, 11198
}}