However there is an additional constraint on state aggregration Reinforcement learning 1 backs up rewards received in the final states of the dialogue sf to earlier states s; where strategy choices were explored However the algorithm can only distinguish strategy choices when the trajectory between si and si are distinct for each strategy choice In other words if two actions at some point lead to the same state then without local reward the values of these two actions will be equal

![0_image_0.png](0_image_0.png)

Figure specifies the subset of the state variables given in Figure that we devel Figure oped to represent the state space for the purpose of applying reinforcement learning  The combination of these state variables is very compact  but provides distinct trajectories for different strategy choices  The reduced state space has only     states  but supports dialogue optimization over a policy space of   *  12 different policies   All of the policies are prima facie candidates for optimal policies in that they can all support human users in completing a set of experimental email tasks

## 3. Experimental Design

Experimental dialogues for both the training and testing phase were collected via experi ments in which human users interacted with ELVIS to complete three representative appli cation tasks that required them to access email messages in three different email inboxes We collected data from    users performing three tasks       dialogues  for training ELVIS
and then tested the learned policy against a corpus from six users performing the same three tasks dialogues Instructions to the users were given on a set of web pages  with one page for each exper imental dialogue The web page for each dialogue also contained a brief general description of the functionality of the system  a list of hints for talking to the system  a description of the tasks that the user was supposed to complete  and information on how to call ELVIS
Each page also contained a form for specifying information acquired from ELVIS during the dialogue  and a survey  to be filled out after task completion  designed to probe the users ssse from their office phone Each of the three calls to ELVIS was made in sequence  and each conversation consisted of two task scenarios where the system and the user exchanged information about criteria for selecting messages and information within the message The tasks are given in Figure where eg  Task    and Task    were done in the same conversation with ELVIS  The motivation for asking the caller to complete multiple tasks in a call was to create subdialogue structure in the experimental dialogues   Litman Grosz Sidner