2.1 State features and action set

In learning strategies for the ATIS task, Levin et al. (Reference Levin, Pieraccini and Eckert1998, Reference Levin, Pieraccini and Eckert2000) used state vectors consisting of the following fields (in addition to slot-status):

1. 1. the number of data tuples retrieved from the database according to the user request;

2. 2. a feature that records whether the system has already presented data to the user.

Possible system actions for learning include:

1. 1. an open-ended question i.e. ‘How can I help you?’;

2. 2. ask the user to provide information about a slot/specific attribute of the task (e.g. origin, airline, departure time, and so on);

3. 3. retrieve data from the database according to the current user request;

4. 4. present the retrieved data to the user;

5. 5. ask the user to relax a particular constraint, for example, ‘Do you mind considering other airlines?’;

6. 6. close the dialogue.

2.2 Reward function

In the ATIS domain, the system’s goal is to provide the user with information about flights in an efficient way. Efficiency here involves the duration of the dialogue (in turns), the cost of external resources (database retrieval), and the effectiveness of the system output to the user. Hence Levin et al. (Reference Levin, Pieraccini and Eckert2000) used a reward function that was a weighted sum of the following:

1. 1. length of the dialogue in number of turns;

2. 2. expected number of tuples retrieved from the database;

3. 3. a data presentation cost function, f ₀(N ₀);

4. 4. overall task success measure.

For the third term, the data presentation cost function, N ₀ is the number of records that are presented to the user, and generally, f ₀(N ₀) is zero for N ₀ smaller than a reasonable N*, and increases rapidly thereafter, where N* depends on the medium used to output information to the user (it is generally small for voice-based communication, and higher for display). The fourth term is an overall binary task success measure that is changed to ‘successful’ if any data is presented to the user—the data is assumed to match the user request, that is, there are no recognition or understanding errors. As we shall see, the majority of previous research described in this survey uses a reward function based on task completion and dialogue length, and the weights are set in a fairly ad hoc manner.

2.3 User simulation

Unlike other earlier research between 1998 and 2002, Levin et al. (Reference Levin, Pieraccini and Eckert2000) applies the simulation-based approach for using RL to learn a dialogue strategy (see Section 1.1 for definitions of model and simulation-based approaches). Levin et al. (Reference Levin, Pieraccini and Eckert2000)’s user simulation is partly stochastic, and is made up of unigram and bigram models, which output a user response based on the previous system action. As in all cases where a user simulation has been used for RL of dialogue strategies, training dialogues between the system and user simulation are conducted via abstract representations of utterances such as Dialogue Acts (DAs). This is because such abstract representations are easier to generate than word sequences, let alone speech signals, and they also make it easier to simulate ASR and NLU errors. Note that Levin et al. (Reference Levin, Pieraccini and Eckert2000) do not use any kind of ASR/NLU error simulation. Levin et al. (Reference Levin, Pieraccini and Eckert2000)’s user simulation supplies slot-values rather than abstracting away from them (e.g. if it is trying to fill the ‘destination_city’ slot, it will output something of the form ‘destination_city(Pittsburgh)’ rather than just ‘destination_city’). This necessitates the deterministic part of the simulation, which ensures consistent or goal-directed behavior, so that within a dialogue, the simulation always supplies the same values for each slot, for example, the simulated user does not change its mind halfway through so that it wants to fly to ‘Philadelphia’ instead of ‘Pittsburgh’.

The simulation used unigram and bigram models for the following, where X and Y can refer to any slot, including the same slot:

1. 1. the number of values to supply in response to a greeting, e.g. P(n), n = 0, 1, 2;

2. 2. which slot to supply a value for in response to a greeting, e.g. P(ORIGIN), P(AIRLINE);

3. 3. which value to supply given the slot, e.g. P(Boston|ORIGIN), P(Delta|AIRLINE);

4. 4. supplying a value for slot X given that the system asked about slot Y, e.g. P(AIRLINE|AIRLINE), P(AIRLINE|DEPARTURE_TIME);

5. 5. supplying values for N unsolicited slots given that the system has just asked about slot X, e.g. P(2|AIRLINE);

6. 6. accepting the relaxation prompt, given which slot the system wishes to relax, e.g. P(yes|AIRLINE) = 1−P(no|AIRLINE).

The original ATIS dialogue corpus Walker et al. (Reference Walker, Litman, Kamm and Abella1997) could only be used to estimate the parameters for 1 and 2 in the above list, because in this corpus, the system never takes the initiative, and does not ask constraining or relaxing questions. Hence, the parameters for the other models were set using intuition. This simulation was not evaluated to assess how realistic it is.

As we will see, this is a fairly typical approach to user simulation for RL in SDS, featuring:

• • partly deterministic and partly-stochastic behavior;

• • consistent/goal-driven behavior;

• • some probabilities are derived from appropriate data, some are hand-coded;

• • the user simulation and system communicate via abstract representations of utterances, e.g. DAs;

• • no evaluation of the simulation quality.

Later in this survey, more recent research will be described in which efforts are made to establish the accuracy of the user simulation, for example, Scheffler and Young (Reference Scheffler and Young2002) and Henderson et al. (Reference Henderson, Lemon and Georgila2008).

2.4 Experimental results

Levin et al. (Reference Levin, Pieraccini and Eckert2000) reports that by the end of training, the system had explored 111 states, and converged to the optimal strategy. A summary of how the strategy behaves is provided. First, the system always starts the dialogue by greeting. Depending on the system state after getting the user response to this greeting, the system, if needed, proceeds by asking constraining questions until the origin, destination and airline are specified. Note that the strategy does not take into account the number of database entries that match the user’s constraints after every user turn, meaning that the strategy continues to ask for all constraints even if there is only 1 or 0 current results. Next, the strategy retrieves data from the database. After the retrieval, if the resulting data set is empty (because the query was over-constrained), then the system, depending on the current state, relaxes the airline or the departure time, and then retrieves again. If there are too many flights in the data set, then it asks for additional constraints (e.g. the departure time) and retrieves again. If at any point during the dialogue the retrieved data set has a reasonable number of flights, then the data is output and the dialogue is closed.

Levin et al. (Reference Levin, Pieraccini and Eckert2000)’s evaluation is unsatisfactory for the following reasons:

• • There is no quantitative evaluation of the learned strategy based on average final reward.

• • There are no quantitative comparisons to any other strategy, e.g. a handcrafted strategy, a random baseline strategy, or some other kind of learned baseline strategy (only one strategy is learned in any case).

• • As a result of these deficiencies, no statistical significance results can be reported.

• • The learned strategy is tested with the same simulation with which it was trained.

• • The learned strategy is not tested on real users.

As we shall see, evaluation methodologies have become more sophisticated in recent years, for example, Lemon et al. (Reference Lemon, Georgila and Henderson2006a).

2.5 Summary

This early work was very important in pioneering the basic concepts and methods in RL for SDSs. All subsequent work builds on this approach to some degree, but as we shall show, many aspects of the methodology have been improved upon. We now describe work which closely followed the initial presentation by Levin and Pieraccini (Reference Levin and Pieraccini1997).

3.1 State features and action sets

Singh et al. (Reference Singh, Kearns, Litman and Walker1999) used different state features depending on the aim of the experiment. The state features used for TOOT in the first experiment were the slot-status features only. Here the aim was simply to check that RLDS was working and could learn a sensible policy, that is, one which filled all the slots, confirmed them, and then queried the database. Subsequent experiments also used the following two state features:

1. 1. number of filled slots;

2. 2. length of the dialogue.

One interesting experiment aimed to find a correlation between the value function and the number of ‘distress indicators’ in a dialogue, for example, timeouts, resets, user requests for help, and other indicators that the dialogue is potentially in trouble. Hence a feature that kept track of the number of distress indicators was added to the state representation.

Singh et al. (Reference Singh, Litman, Kearns and Walker2002) aimed to learn which of two actions (initiative and confirmation type) to take in 42 different states (the other action choices were hand-coded). Each of these states was represented using the following features:

1. 1. whether the system has greeted the user (0 or 1);

2. 2. which slot is being worked on (1–4);

3. 3. confidence/confirmed (0, 1, 2 for low, medium and high ASR Confidence Levels (CL)Footnote 3, 3, 4 for explicitly confirmed and disconfirmed);

4. 4. whether a value has been obtained for current slot (0 or 1);

5. 5. how many times the current slot has been asked (0, 1, 2);

6. 6. whether a non-restrictive or restrictive grammar was used (0 or 1);

7. 7. whether there was trouble on any previous slot (0 or 1).

Some of the 42 states occurred when the system needed to ask or re-ask a slot, and then the action choices were to retain the initiative or to give it to the user. The rest of the 42 states occurred when the system has just obtained a slot-value, and then the action choices are to confirm, or to move onto another slot. The system was trained with 54 users (311 dialogues) by taking random choices at these points (the ‘Exploratory for Initiative and Confirmation’ strategy), and collecting rewards via task completion.

3.2 Reward functions

Singh et al. (Reference Singh, Kearns, Litman and Walker1999, Reference Singh, Litman, Kearns and Walker2002) only ever gave a reward in terminal dialogue states. For the TOOT experiments, this terminal state reward was obtained from a question in the user satisfaction survey. This reward was +1 if the user said that they would use the system again, 0 if they said ‘maybe’, and −1 if they said ‘no’. In Singh et al. (Reference Singh, Litman, Kearns and Walker2002) dialogue reward was automatically labeled by a +1 in the case of a completed task, or −1 otherwise.

3.3 Experimental results

The main findings of the six experiments described in Singh et al. (Reference Singh, Kearns, Litman and Walker1999) were the following:

1. 1. RLDS is capable of learning a sensible basic dialogue policy;

2. 2. the value function grows roughly linearly with the number of confirmed attributes;

3. 3. dialogues with a higher number of distress features have a lower value;

4. 4. within the same length dialogue it is better to have obtained more attributes;

5. 5. system initiative has higher value than mixed initiative;

6. 6. results were extremely similar using a reward function, based on whether the user perceived the task to have been completed, rather than actual task completion.

Singh et al. (Reference Singh, Litman, Kearns and Walker2002) found that the value function of the learned strategy was higher than the average value of the random ‘Exploratory for Initiative and Confirmation’ strategy used during training. Task completion increased from 52% in training to 64% in testing (p < 0.059 in a two-sample t-test over subject means). The experiments had also involved collecting subjective evaluations from the users, but these were not significantly different between the learned and random policies.

This work was the first to provide significant results showing that a learned policy can perform well with real users of a dialogue system. However, there are some unsatisfactory elements to this result:

• • the baseline strategy for comparison was random action choice, rather than a state-of-the-art handcrafted strategy;

• • the strategy was only learned for a small number of choice points, rather than for the entire state–action space (all actions in all possible states);

• • only small state-spaces were used (e.g. compared to Henderson et al., Reference Henderson, Lemon and Georgila2008).

We now discuss the related work of Walker (Reference Walker2000), which used a different, data-driven, methodology for determining the reward function for learning.

4.1 State features and action sets

As stated above, Walker (Reference Walker2000) explores different action choices with regard to initiative, and summarizing and reading messages. ELVIS explores two different types of initiative action:

1. 1. The system-initiative action constrains what the user can say by requesting a particular item of information.

2. 2. The user-initiative action allows the user to take control of the dialogue and specify exactly what (s)he wants to do next.

For the implementation of ELVIS used in Walker (Reference Walker2000), the choice of initiative is made early in the dialogue and then fixed for the remainder in order to avoid confusing the user. If the system is using a user-initiative strategy but the user fails to provide a recognizable response, then the system will take the initiative to repair the situation before switching back to user-initiative actions. ELVIS explores three alternative summarization actions:

1. 1. The Summarize-Both (SB) action uses both the sender and the subject attributes in the summary.

2. 2. The Summarize-System (SS) action summarizes by subject or by sender based on the current context.

3. 3. The Summarize-Choice-Prompt (SCP) action asks the user to specify which of the relevant attributes to summarize by.

Finally, ELVIS explores two different Read actions for reading multiple messages following a user request, for example, ‘Read my messages from Kim.’:

1. 1. The Read-First (RF) action involves summarizing all the messages from Kim, and then taking the initiative to read the first one.

2. 2. The Read-Summary-Only (RSO) action provides information that allows users to refine their selection criteria.

Walker (Reference Walker2000) uses the following state features:

1. 1. KnowUserName (U): 0, 1;

2. 2. InitStrat (I): 0, SM, MI;

3. 3. SummStrat (S): 0, SS, SCP, SB;

4. 4. ReadStrat (R): 0, RF, RSO, RCP;

5. 5. TaskProgress (P): 0, 1, 2;

6. 6. CurrentUserGoal (G): 0, Read, Summarize;

7. 7. NumMatches (M): 0, 1, N>1;

8. 8. WhichSelection (W): 0, Sender(Snd), Subject(Sub), InOrder(InO);

9. 9. KnowSelectionCriteria (SC): 0, 1;

10. 10. Confidence (C): 0, 1;

11. 11. Timeout (T): 0, 1;

12. 12. Help (H): 0, 1;

13. 13. Cancel (L): 0,1.

The KnowUserName (U) feature keeps track of whether ELVIS knows the user’s name or not, while the InitStrat (I), SummStrat (S) and ReadStrat (R) features record whether ELVIS has already employed a particular initiative, summarize, or reading strategy in the current dialogue, and if so, which strategy it was. The TaskProgress (P) feature then tracks how much progress the user has made in completing the experimental task, and the CurrentUserGoal (G) feature corresponds to the system’s belief about what the user’s current goal is. The WhichSelection (W) feature records whether the system knows what type of selection criteria the user would like to use to read her messages, and the KnowSelectionCriteria (SC) feature tracks whether the system believes it understood either a sender name or a subject name to use to select messages. The NumMatches (M) feature records how many messages match the user’s selection criteria, and the Confidence (C) feature is a threshold variable indicating whether the speech recognizer’s confidence that it understood what the user said was above a pre-set threshold. The Timeout (T) feature represents the system’s belief that the user said ‘Help’, and leads to the system providing context-specific help messages. Finally, the Cancel (L) feature represents the system’s belief that the user said ‘Cancel’, which leads to the system resetting the state to the state before the last user utterance was processed. Walker (Reference Walker2000) reports that these state features produced 110 592 possible states but that not all of these states occur.

4.2 PARADIgm for System Evaluation and the reward function

As stated previously, Walker (Reference Walker2000) proposes a methodology called PARADISE for developing predictive models of SDS performance (see also Walker et al., Reference Walker, Kamm and Litman2000). Walker (Reference Walker2000) describes an application of the methodology to the training dialogues collected with ELVIS. Recall that the training dialogues are generated using a strategy that randomly explores action choices for initiative, reading messages and summarizing folders. At the end of each dialogue with ELVIS, the user’s satisfaction is seen as the sum of the following features, where each has some positive weight:

1. 1. Actual Task Completion (0 or 1);

2. 2. Perceived Task Completion (1 or 1);

3. 3. Task Ease (0–4);

4. 4. Comprehension Ease (0–4);

5. 5. System behaved as Expected (0–4);

6. 6. Future Use (0–4).

The value for Actual Task Completion was obtained from the system logs, but the values for the other user satisfaction features (2–6 in the list above) were supplied by the users. The modeling technique, multivariate linear regression Footnote 4, is then used to learn to predict the user satisfaction score based on a number of metrics that can be directly measured from the system logs. These metrics include:

1. 1. Dialogue Efficiency Metrics—elapsed time, system turns, user turns;

2. 2. Dialogue Quality Metrics—mean recognition score, number of timeouts, ASR rejections, user requests for help, user requests to restart the dialogue, barge-ins.

The resulting model is a PARADISE model for predicting user satisfaction/SDS performance.

In learning the action choices for initiative, reading messages and summarizing folders, the actual user satisfaction score was used as reward, not the user satisfaction score as computed by the PARADISE model.

4.3 Experimental results

Regarding PARADISE, a stepwise linear regression on the training data showed that Task Completion, Mean Recognition Score (MRS), Barge-in% and Rejection% were significant contributors to User Satisfaction, accounting for 39% of the variance in R ²Footnote 5. How well the model generalized to unseen data was tested with a ten-fold cross-validationFootnote 6—90% of the training dialogues were randomly sampled and the goodness of fit was tested on the remaining 10%. The average R ² for the training set was 37% with a standard error of 0.005, while the average R ² for the held-out 10% of the dialogues was 38% with a standard error of 0.06. This suggests that the model will generalize to new ELVIS dialogues.

Regarding the learned strategy, statistical analysis indicated a significant increase in user satisfaction from training to test (p = 0.047). Wherever the choice arises, the learned strategy uses the System-Initiative and Read-First actions. The learned strategy uses the Summarize-Both action at the beginning of the dialogue, and then switches to the Summarize-System action in later phases.

This work then shows that using a more data-driven definition of reward leads to a better-learned strategy than a random strategy. We now turn to another strand of research, which has focused on simulated users and ASR systems rather than training with real user data (the simulation-based approach to learning dialogue strategies—see Section 1.1).

5.1 State features and action sets

For the computer-dealing application, each state is represented with a confidence feature for each of the seven slots, and the possible values for each of these features are: 0 if the slot is unfilled, 1 if the confidence is low or 2 if it is high. This means that there are 3⁷ possible states.

The action set contains six generic actions:

1. 1. Greeting, e.g. ‘How may I help you?’.

2. 2. Ask: ask to constrain the value of a slot.

3. 3. Conf: ask to confirm the value of a slot.

4. 4. Relax: ask to relax the value of a slot.

5. 5. Database query: perform a database query.

6. 6. Close: present data and close the dialogue session.

With seven slots, this gives 24 different actions. When the database was queried, only values with a high CL were used.

5.2 Reward functions

After each turn, the reward is a weighted sum of the following:

1. 1. a negative reward if the final state has not yet been reached;

2. 2. number of database accesses;

3. 3. number of presented records;

4. 4. confidence level of the current user’s utterance;

5. 5. a ‘function of the modeled user’s satisfaction’.

Pietquin and Renals (Reference Pietquin and Renals2002) does not provide any details about the ‘function of the modeled user’s satisfaction’.

5.3 A stochastic user and error simulation

Like the simulation used by Levin et al. (Reference Levin, Pieraccini and Eckert2000), the simulation used by Pietquin and Renals (Reference Pietquin and Renals2002) is partly stochastic and able to simulate mixed-initiative behavior. Another common feature is that the purpose of its deterministic element is to ensure that the simulation maintains the same goal within an individual dialogue—a main user goal is randomly defined at the start of each dialogue and user actions are consistent with this goal. Here, since the domain is computer-dealing, a user goal describes a set of specifications for a computer. A difference to the Levin et al. (Reference Levin, Pieraccini and Eckert2000) simulation is that for the Pietquin and Renals (Reference Pietquin and Renals2002) simulation, none of the probabilities are learned from data—they are all supplied via intuition.

Pietquin and Renals (Reference Pietquin and Renals2002) denotes n to mean the number of slots, g is the user goal (the user’s preferred value for each slot), k_t is the user knowledge at time t (how many times the user has supplied a value for each slot), s ^β is the slot which the system has just asked about, and u ^α is the slot which the user simulation provides a value for in response to the system prompt. The probabilities used by the user simulation then include:

1. 1. probabilities associated with responses to greeting, e.g. P(n|Greeting, g), P(u ^α|s ^β, k_t, g);

2. 2. probabilities associated with responses to constraining questions, e.g. P(u ^α|s ^β, k_t, g), P(n|s ^β);

3. 3. probabilities associated with responses to relaxation prompts, e.g. P(yes|s ^β, k_t, g), P(no|s ^β, k_t, g);

4. 4. probability associated with user satisfaction: , i.e. the user simulation can indicate its dissatisfaction by closing the dialogue early, and this probability is set so that as the number of times the simulation has to supply a particular slot-value increases, the chances of it hanging up also increase.

The novel feature of this work is that it uses a stochastic ASR simulation that simulates ASR errors and outputs CL scores. Just as for the user simulation, the probabilities are not learned from data—they are set using intuition. Pietquin and Renals (Reference Pietquin and Renals2002)’s ASR simulation uses different CL and error rate distributions for a finite number of recognition tasks, which include:

1. 1. digits;

2. 2. numbers;

3. 3. dates;

4. 4. unrestricted continuous speech.

A CL distribution is composed of two distinct curves respectively for good and bad recognition results—Figure 1 represents a CL distribution output from a real ASR system obtained using some of its training data (isolated words). As the two curves cover each other, it is unavoidable to reject some well-recognized utterances as well as to accept a few bad recognition results by defining a single CL threshold. The ASR simulation used here receives lists of one or more attribute–value pairs from the user simulation, which it then splits into individual attribute–value elements. The probability of it simulating an ASR error for a particular attribute–value pair is then dependent on the average Word Error Rate (WER) for the task in question. Note that the simulation assumes that recognition errors only affect values of the attribute-value pairs and that only words occurring in the same context can be substituted with each other. If the simulation simulates an ASR error, then it produces a partial CL according to the ‘bad recognition’ curve of the corresponding CL distribution, and if it does not, then it produces a partial CL according to the ‘good recognition’ curve. A global CL is generated for the list by multiplying all partial CLs.

Figure 1

A Confidence Level (CL) distribution for good and bad recognitions (taken from Pietquin and Renals, Reference Pietquin and Renals2002)

5.4 Experimental results

Pietquin and Renals (Reference Pietquin and Renals2002) reports that after several thousand simulated dialogues, the learned strategy stabilizes and appears to be optimal. A summary description of the strategy is provided: after greeting the user, the system uses the ask and relax actions until it has enough information with a high CL to query the database and return a set which is not empty, but not ‘too large’. No details are given as to what ‘too large’ means in practice.

Pietquin and Renals (Reference Pietquin and Renals2002) reports that the ASR simulation affected the order in which the ask action was applied for each slot. The learned strategy first asks questions about values that present better recognition results such as numbers. For example, it will ask for a value for the RAM size slot before the computer brand slot.

This work then shows that reasonable dialogue strategies can be trained in simulation rather than with real data, and that with only slot-status features represented in the state, the reinforcement learner can learn to ask the slots in an order which is sensitive to the likelihood of ASR errors. However, the evaluation here is lacking in the same way as that of Levin and Pieraccini (see Section 2.4)—for example, there is no quantitative evaluation of the learned strategy or testing with real users. We now present similar work.

6.1 State features and action sets

Scheffler and Young (Reference Scheffler and Young2002) used five different state representations composed from different combinations of the following features (in addition to slot-status):

1. 1. slot currently in focus (Type, Day, Film, Cinema);

2. 2. ‘InfoSource’ (Default, Negated, Elicited, Unelicited);

3. 3. confidence (Default, 0.2, 0.3,…,1.0);

4. 4. ‘ConfLevel’ (Default, Low, High).

Of these five state representations, the one with the greatest number of state–action pairs included features 1 and 3, in addition to standard slot-status features. Once the impossible state–action pairs had been ruled out, this state-representation was left with 1298 possible state–action pairs.

The different actions that the learner had to choose between were:

1. 1. Mixed Initiative—mixed initiative query for more information (available if current slot is empty).

2. 2. System Initiative—query for information on the current slot (available if current slot is empty).

3. 3. Explicit confirmation—confirm the contents of the current slot explicitly.

4. 4. Confirm all—confirm the contents of all slots.

5. 5. Implicit confirmation—confirm the contents of the current slot implicitly while querying for information on the next slot.

6. 6. Accept—accept information in the current slot without confirmation at present. Terminate if a complete transaction has been specified.

This action set allows for automatic design of the choice between mixed and system initiative and the confirmation strategy (a choice between explicit confirmation, implicit confirmation, and delaying confirmation until later).

6.2 Reward function

Scheffler and Young (Reference Scheffler and Young2002) use a simple reward function that gives a reward at the end of each dialogue. This reward function includes a per-turn penalty and a task failure penalty.

6.3 User simulation and error model

As in Levin et al. (Reference Levin, Pieraccini and Eckert2000) and Pietquin and Renals (Reference Pietquin and Renals2002), the user simulation of Scheffler and Young (Reference Scheffler and Young2001, Reference Scheffler and Young2002) is partially stochastic and is able to simulate mixed-initiative behavior. Again, the deterministic element of the simulation is that it is goal-directed—a main user goal is randomly defined at the start of each dialogue and user actions are consistent with this goal. There is also a probabilistic error model.

The user simulation generates utterances using lattices. Nodes are probabilistic or deterministic choice points relating to user behavior. The deterministic choices are based on user state and so ensure consistent goal-directed behavior. The parameters for the probabilistic user behavior choice points and error model are estimated based on training data collected with a prototype cinema information SDS. For the probabilistic user behavior choice points, an event is a user action, and the context is the previous system action(s) and a representation of the internal user state, while for the error model, an event would be whether or not a recognition/understanding error occurred. In all cases, probabilities are estimated from the data using Maximum Likelihood Estimation (MLE)Footnote 7. Counts are obtained for both specific and more general contexts, so that it is possible to back-off to a more general case whenever the number of training examples falls below a certain threshold.

The user simulation and error model are shown to simulate different scenarios well enough to perform relative predictions of their durations. Hence some evaluation is undertaken in order to assess how realistic the user and error simulations are, but this evaluation is not very convincing, since it is only based on the gross metric of dialogue duration.

6.4 Experimental results

In evaluating the learned strategies, Scheffler and Young (Reference Scheffler and Young2002) used two handcrafted strategies as baselines. The first used a small state-space—slot-status features and feature 1 from Section 6.1, while the second used a large state-space, which included additional features such as a confidence feature, and a feature that counts how many times each slot has been asked. The performance of the learned and handcrafted strategies was evaluated in test dialogues with the user simulation according to the reward function of Section 6.2. Of the learned strategies, those learned with larger state-spaces tended to outperform those learned with smaller ones, but the improvement was not great. The learned strategies outperformed the small-state-space-handcrafted strategy by a large margin, and performed roughly as well as with the large-state-space-handcrafted system.

Like Levin et al. (Reference Levin, Pieraccini and Eckert2000) and Pietquin and Renals (Reference Pietquin and Renals2002), this work then shows that reasonable strategies can be learned using simulated users, but again:

• • testing and training are performed with the same user simulation;

• • no tests with real users were performed;

• • the quality of the user simulation is not established convincingly—we are only told that the user simulation and error model are shown to simulate different scenarios well enough to perform relative predictions of their durations;

• • the learned strategies are not shown to be better than hand-coded strategies.

We now discuss an alternative approach that treated both the user simulation and DM as RL systems.

7.1 State features and action sets

The state representation for each of the system and user agents includes the following binary features:

1. 1. Pending-Proposal;

2. 2. I-Proposed;

3. 3. Violated-Preference;

4. 4. Prior-Violated-Preferences;

5. 5. Better-Alternative.

A Pending-Proposal indicates whether an item has been proposed but not accepted or rejected, and I-Proposed whether the agent made the most recent proposal. Violated-Preference indicates that the pending proposal has caused one or more violations of the conversant’s private preferences, while Prior-Violated-Preferences indicates whether the conversant had one or more violated preferences when the pending proposal was made. Better-Alternative indicates that the agent thinks it knows an item which would achieve a better score than the item currently proposed.

The action set for each of the system and user agents includes:

1. 1. propose;

2. 2. accept;

3. 3. reject;

4. 4. inform;

5. 5. release turn.

The propose, accept and reject actions refer to proposing, accepting and rejecting different items of furniture for the room. An agent uses the inform action to inform the other conversant of preferences that are violated by the current proposal. Since a turn does not finish until the speaker uses the release turn action, a single turn can include multiple actions e.g. a reject, followed by an inform and then a propose.

7.2 Reward functions

The agents only receive non-zero rewards at the end of each dialogue. The reward function is a linear combination of the solution quality (S) and the dialogue length (L), taking the form:

(1)

where w ₁ and w ₂ are positive constants. The authors explore the effects of different values for the constants.

7.3 User simulation using Reinforcement Learning

The user simulation is also an RL agent and so which action it takes at any given time is determined by:

1. 1. the action selection method, e.g. ε-greedy and the relevant parameter’s value e.g. ε (see Sutton & Barto, Reference Sutton and Barto1998);

2. 2. the Q-values (see Sutton & Barto, Reference Sutton and Barto1998) for the different actions in the current state.

7.4 Experimental results

English and Heeman (Reference English and Heeman2005) report that they succeeded in learning system and user dialogue strategies that achieved comparable performance with handcrafted system and user strategy pairs. The authors also claim that the learned system strategies are robust—when the learned system strategies ‘conversed’ with the handcrafted user strategies, the resulting dialogues had comparable solution quality to what the handcrafted and user strategies achieved together. They acknowledge that there was a lack of convergence in the Q-values over a number of learning trials, presumably because the RL problem becomes more complex with two interacting learning agents.

However, if the goal is to produce system strategies for interacting with real users, the approach of using RL to simultaneously learn both the system and user strategies seems to be problematic. To learn a strategy that works well with real users, we need to train with a simulation that accurately simulates real users. For example, we will see in the discussion of Frampton and Lemon (Reference Frampton and Lemon2006, Reference Frampton and Lemon2008) in Section 11 that real users seem to respond better to different repair strategies in different contexts. Hence, unless we train with an accurate simulation, we cannot expect to learn these appropriate repair strategies. Therefore, it seems that the type of co-training used by English and Heeman (Reference English and Heeman2005) cannot be relied upon to produce optimal strategies for real users.

We now discuss about the work which presents a method for automatically selecting features to include in the state, and which investigates alternatives to MDPs for modeling the dialogue management problem.

8.1 State features and action sets

The potential state features in the data fell into the following three broad categories:

1. 1. Within-utterance ASR features: Features pertaining to a single utterance such as the number of hypotheses in an n-best listFootnote 8 of variable length, the mean of the confidence scores, and so on.

2. 2. Between-utterance ASR features: Features pertaining to matches across utterances, such as whether the top rule in the n-best list matched the previous top rules, and so on.

3. 3. Dialogue features: Features pertaining to the overall dialogue such as the number of repairs so far, whether the system has engaged in a confirmation yet, and so on.

Four different DM models were constructed:

1. 1. a zero-order Markov model;

2. 2. a first-order Markov model, i.e. an MDP;

3. 3. a second-order Markov model;

4. 4. a cumulative total reward model.

As we already know, in an MDP, a time slice’s state variables depend on those from the previous time slice. For a second order Markov model, the third time slice state variables can also depend on those in the first time slice, while for a zero-order Markov model, there are no dependencies between time slices. For a cumulative total reward model, state features accumulate for each slice.

Here is a summary of the state features which Paek and Chickering (Reference Paek and Chickering2005)’s data-driven method learned should be represented in the MDP:

1. 1. a number of features related to the n-best list confidence scores;

2. 2. the mean confidence score in the n-best list;

3. 3. sum of all confidence scores from n-best list;

4. 4. range of score values from n-best list;

5. 5. whether all the rules in the list were the same though the actual phrases or wording were different;

6. 6. the grammar rule that was observed, e.g. the first or top rule in the n-best list.

Hence this includes a number of features related to the n-best list confidence scores, which makes sense given that most handcrafted dialogue management strategies use some kind of confidence threshold for taking actions, for example, ‘Do the top recognized command if its confidence is greater than 95%’. When applied to the other models, Paek and Chickering (Reference Paek and Chickering2005)’s method learned different feature sets, for example, feature sets including between-utterance ASR features.

The action choices for the first turn were:

1. 1. DoTop: execute the most likely command in the n-best list;

2. 2. Confirm: confirm among the top three choices while giving the option that it may not be any of them;

3. 3. Ignore: ignore the utterance as spurious;

4. 4. Repeat: ask for a repetition.

For the second turn they were:

1. 1. DoTop;

2. 2. Confirm;

3. 3. Repeat.

Finally, the action choices for the third turn were:

1. 1. DoTop;

2. 2. Bail: make an apology and terminate the dialogue.

In generating the training data, all possible system actions were explored for each user command—Section 8.3 will provide more details about this training simulation environment.

8.2 Reward functions

If the simulation selected either the DoTop, Ignore or Bail action, then the session finished and a reward was given. When the final action was DoTop, if the system executed the correct command, then it received a reward of +100, else it received −100. If the final action was Ignore and there was no command, then it received +100, else −100. For Bail, it received −100. If either the repair action Confirm or Repeat was selected, a penalty of −75 was received.

8.3 User simulation

The simulation randomly selects a command from the command-and-control grammar for the browser (e.g., ‘go back’, ‘go forward’, ‘go to link x’). Using state-of-the-art Text-To-Speech (TTS) generation, an utterance is then produced for the command, varying all possible TTS parameters, such as engine, pitch, rate and volume. Since Paek and Chickering (Reference Paek and Chickering2005) were interested in building models that were robust to noise, they included empty commands and added various types of background noise to see if a model could learn to ignore spurious commands. The produced utterance was then recognized by a Microsoft Speech API (SAPI) recognition engine. All possible SAPI events were logged, and these events, and functions of these events constituted the potential state feature set already provided in Section 8.1.

8.4 Experimental results

Paek and Chickering (Reference Paek and Chickering2005) found that the strategy learned for the cumulative total reward model outperformed the strategies learned for the other models, including the MDP. Hence it seems that the cumulative total reward model may offer an attractive alternative to the MDP. However Paek and Chickering (Reference Paek and Chickering2005) say they cannot draw any strong conclusions for the following reasons:

1. 1. The domain was small with a relatively restricted command-and-control grammar and a small action space.

2. 2. It is possible that certain features that would have enabled the MDP to perform best were not annotated.

3. 3. The results depend on the techniques used for learning the structure of the state space and so these results may have turned out differently with other model selection techniques. Feature selection techniques such as Correlation-based Feature Selection (CFS) (Hall, Reference Hall1999) offer an alternative.

The work described here in this section proposed a method for automatically identifying features that should be included in the state. We now present some alternative work that has used RL itself to assess the importance of different state features. The basic methodology is to learn strategies with different state features, and to then subject these strategies to quantitative and qualitative analysis.

9.1 State features and action sets

The state is always represented by a subset of the following features, which all relate to the student (user):

1. 1. Correctness: Correct (C), Incorrect or Partially Correct (IPC);

2. 2. Certainty: Certain (cer), Uncertain (unc), Neutral (neu);

3. 3. Concept Repetition: Concept is new (0), Concept is repeated (R);

4. 4. Frustration: Frustrated (F), Neutral (N);

5. 5. Percent Correct: 50%–100% = (H)igh, 0%–49% = (L)ow.

Forbes-Riley and Litman (Reference Forbes-Riley and Litman2005) describes how the emotion-related features, Certainty and Frustration, were annotated manually in the corpus. Certainty describes how confident a student seemed to be in their answer, while Frustration describes how frustrated the student seemed to be when they responded. The other three features, (Correctness, Concept Repetition, Percent Correct) are automatically extracted. Correctness describes whether the student was correct or not, Percent Correct, the percentage of correctly answered questions so far for the current problem, and Concept Repetition, whether the system is forced to cover a concept again which reflects an area of difficulty for the student. Tetreault and Litman (Reference Tetreault and Litman2006) were interested in the utility of Concept Repetition, Frustration and Percent Correct. Hence they learned a baseline with only features 1 and 2 in the state, and then three further strategies with features 1 and 2 and then one of 3 to 5.

As stated previously, where it is thought appropriate to ask a question, Tetreault and Litman (Reference Tetreault and Litman2006) use RL to learn to choose between the following actions:

1. 1. Simple Answer Question (SAQ), e.g. ‘Good. What is the direction of that force relative to your first?’;

2. 2. Complex Answer Question (CAQ), e.g. ‘What is the definition of Newton’s Second Law?’;

3. 3. Mix of SAQ and CAQ, e.g. ‘Good. If it doesn’t hit the centre of the pool what do you know about the magnitude of its displacement from the centre of the pool when it lands? Can it be zero? Can it be nonzero?’;

4. 4. No Question (NoQ), e.g. ‘So you can compare it to my response…’.

For other states, the action is fixed as either giving some kind of feedback or some other type of helpful measure, for example, a hint or a restatement.

9.2 Reward functions

The 10 students with the highest normalized learning gain scores were labeled high learners and their respective five dialogues were given a final reward of 100. The other ten students were labeled low learners and their respective dialogues were given a final reward of −100.

9.3 Experimental results

Tetreault and Litman (Reference Tetreault and Litman2006) provide qualitative analysis of the effects of adding the new state features. They state that in general, the Concept Repetition feature causes the reinforcement learner to learn a complex answer question after a concept has been repeated, and especially if the student is correct when addressing a question about the repeated concept. This seems to make sense, because if a concept has been repeated, then this should signal that the student did not grasp the concept, and a clarification dialogue was initiated to help the student understand it better. Once the student answers the repeated concept correctly, this indicates that the student understands the concept and that the tutor can once again ask more difficult questions to challenge the student. The Frustration feature changes the policies most when the student is frustrated, but when the student is not frustrated (neutral), the policy stays the same as the baseline with the exception of when the student is either Correct and Certain, or Incorrect and Uncertain. Finally, the Percent Correctness Feature does not produce a large policy change—most learned actions remain ‘Mix of SAQ and CAQ’, just as they were for the baseline.

Tetreault and Litman (Reference Tetreault and Litman2006) go on to provide quantitative analysis of the learned strategies in order to compare the utility of the three new state features. Three metrics are used: (i) Diff’s (ii) % Policy Change and (iii) Expected Cumulative Reward (ECR). The number of Diff’s is the number of states whose learned action differs from the baseline. %Policy Change weight each difference by the number of times that state–action sequence actually occurs in the data and then divides by the total number of state–action sequences. This more accurately measures the utility of a feature because although a first feature may produce a higher number of Diff’s than a second feature, its overall impact could actually be lower if the states that it affects occur less frequently. However, % Policy Change still does not take into account the effect which the state feature has on the V-values (for each state the expected total future reward when starting from that state and following the learned strategy; Sutton & Barto, Reference Sutton and Barto1998). The third metric, ECR, does take this into account. ECR is calculated by normalizing the V-value of each state by the number of times it occurs as a start state in a dialogue and the summing over all states. Tetreault and Litman (Reference Tetreault and Litman2006) report that according to all three metrics, Concept Repetition has the greatest utility, followed by Frustration, and then Percent Correctness. For example, the +Concept Repetition strategy obtained an ECR of 39.52, the +Frustration strategy, 31.30, and the +Percent Correctness, 28.17. Note that the learned strategies are not compared to a handcrafted strategy.

This work then demonstrates a simple but useful approach to performing feature selection for state features. The use of automatic feature selection methods such as CFS subset evaluation (Hall, Reference Hall1999) is very much an open problem.

10.1 Dialogue Act Tagging Scheme

This section describes DATE (Dialogue Act Tagging Scheme for Evaluation of Spoken Dialogue Systems; Walker & Passonneau, Reference Walker and Passonneau2001). DATE was developed to provide finer-grained quantitative dialogue metrics for comparing and evaluating COMMUNICATOR SDSs. DATE tags each utterance according to three dimensions:

1. 1. Speech act;

2. 2. Task/Subtask;

3. 3. Conversational domain.

The Speech act dimension characterizes the utterance’s communicative goal, and the different types are:

1. 1. Request-info;

2. 2. Present-info;

3. 3. Offer;

4. 4. Acknowledgement;

5. 5. Status-report;

6. 6. Explicit-confirm;

7. 7. Implicit-confirm;

8. 8. Instruction;

9. 9. Apology;

10. 10. Openings/Closings.

The Task/Subtask dimension gives the task or subtask to which the utterance relates. This dimension is present so that the amount of effort a system expends on particular subtasks can be quantified. Below are the different tasks/subtasks:

1. 1. Top-level-trip;

2. 2. Origin;

3. 3. Destination;

4. 4. Date;

5. 5. Time;

6. 6. Airline;

7. 7. Trip-type;

8. 8. Retrieval;

9. 9. Itinerary;

10. 10. Ground;

11. 11. Hotel;

12. 12. Car.

Finally, the Conversational domain dimension characterizes the utterance as relating to one of the following three conversational domains.

1. 1. About task;

2. 2. About communication;

3. 3. About situation frame.

An About task utterance will typically directly ask for or present task-related information, or offers a solution to a task goal. About communication utterances are concerned with managing the verbal channel and providing evidence of what has been understood, for example, via implicit confirmation. Finally, the Situation frame domain pertains to the goal of managing the culturally relevant framing expectations. Most of the About frame DAs fall into the speech-act category of Instruction, utterances directed at shaping the user’s behavior and expectations about how to interact with a machine.

10.2 State features and action set for Linear Function Approximation

As stated previously, prior to learning the strategy, HLG first annotated the COMMUNICATOR data with additional information. An automatic system which was implemented using DIPPER (Bos et al., Reference Bos, Klein, Lemon and Oka2003) to track dialogue context and several Open Agent Architecture (OAA) agents (Cheyer & Martin, Reference Cheyer and Martin2001) was used to assign DATE tags to the user utterances, and to compute information states for each point in the system, (see Georgila et al. (Reference Georgila, Lemon and Henderson2005b) for more details). The new state features produced a very large state-space (as already stated, 10³⁸⁶ are theoretically possible), and there were 74 different system actions.

State features relate to the following:

1. 1. WER;

2. 2. complete speech acts history;

3. 3. complete tasks history;

4. 4. complete filled slots history;

5. 5. complete filled slots values history;

6. 6. complete grounded slots history.

The majority of the 74 different action choices are for asking or confirming a slot-value, where confirming can be implicit or explicit. Other actions include querying the database of flights/hotels/cars, presenting database query results to the user, and giving some kind of help to the user.

10.3 Reward function

For learning the strategy, each system turn received a reward of −1, and the user satisfaction score was the dialogue final reward. The PARADISE user satisfaction features listed in Section 4.2 were used to compute this user satisfaction score. They were summed with the following positive weights:

1. 1. Actual Task Completion: 100.

2. 2. Perceived Task Completion: 100.

3. 3. Task Ease: 9.

4. 4. Comprehension Ease: 7.

5. 5. System behaved as Expected: 8.

6. 6. Future Use: 9.

The weights for features 3–6 were determined by the application of PARADISE to the COMMUNICATOR data, reported in (Walker et al., Reference Walker, Aberdeen, Boland, Bratt, Garofolo, Hirschman, Le, Lee, Narayanan, Papineni, Pellom, Polifroni, Potamianos, Prabhu, Rudnicky, Sanders, Seneff, Stallard and Whittaker2001a).

When testing the strategy in simulation, HLG used a reward function based only on dialogue length and task completion. We refer to this reward function as ‘HLG05’ (it is first introduced in Henderson et al. (Reference Henderson, Lemon and Georgila2005)), and it is as follows:

1. 1. Database query: +25 for each filled slot, another +25 for each slot which is confirmed.

2. 2. System turn penalty: −1.

The training reward function could not be used when testing in simulation because the simulations do not generate PARADISE user satisfaction scores. Section 11 will describe work by Frampton and Lemon (Reference Frampton and Lemon2006) which also evaluates learned strategies with the HLG05 reward function. This is so as to enable comparison with the Hybrid Strategy and the handcrafted COMMUNICATOR systems.

10.4 Stochastic User simulations

HLG used a user simulation in order to test the learned strategy. This user simulation was trained on the COMMUNICATOR data using linear function approximation. The simulation is given a vector of features representing the current context of the dialogue, and outputs one or more actions, which consist of DATE speech act–task pairs. ASR and NLU errors are incorporated since the model is built from the user utterances as they are recognized by the ASR and NLU components of the original COMMUNICATOR systems. Note that the user simulation does not provide instantiated slot-values, for example, a response to provide a destination city is the speech act–task pair ‘[provide info] [dest city]’. It cannot be assumed that two such responses in the same dialogue refer to the same destination cities, and so slot-status features in the DM’s information state are only updated from filled to confirmed when the slot-value is implicitly or explicitly confirmed.

HLG also report how the COMMUNICATOR data was used to estimate the parameters for user simulations based on n-grams. These n-gram models take as input the speech act–task pairs of the n − 1 most recent turns in the dialogue history and then output a user utterance as one or more new speech act–task pairs. They simulate ASR and NLU errors in the same way as the linear function approximation simulation, and also like the linear function approximation simulation, they do not provide instantiated slot-values. A criticism of some stochastic user models is that they do not do a good job of simulating the different types of user in the data from which they are derived (e.g. users with varying levels of expertise and cooperativeness), and instead simulate an average userFootnote 9. However, user simulations which generate a new action based on some amount of dialogue history (such as n-gram simulations) ought to be able to generate actions that bear common traits with previously generated actions. The degree to which n-gram simulations are able to achieve this is obviously limited by the size of n. Note that the n-gram simulations of HLG were also used for training and testing strategies by Frampton and Lemon (Reference Frampton and Lemon2006, Reference Frampton and Lemon2008), and so will be mentioned again in the discussion of this work in Section 11.

In order to establish their accuracy, the linear function approximation simulation and the n-gram simulations were evaluated on the annotated COMMUNICATOR data using perplexity (see Schatzmann et al. (Reference Schatzmann, Weilhammer, Stuttle and Young2006) for a formal definition of perplexity). Perplexity is a measurement in Information Theory, which is used here for determining whether the simulated dialogues contain similar action sequences (or dialogue state sequences) to the real human–computer dialogue in the COMMUNICATOR data. If they do, then the resulting perplexity will be lower. However, perplexity is not necessarily a good indicator for how likely the user model is to predict a realistic response in the context of an unseen dialogue situation. This is problematic, since in simulation-based learning, our goal is to apply new strategies to the user model, and there is no guarantee that a user model with a low perplexity will produce reasonable user responses in such situations. Nevertheless, the model based on linear feature combination gave the best perplexity, followed by the 4-gram. Each one of the user models was also run against a system strategy learned with purely SL (with linear function approximation) and no RL. The quality of the simulated dialogues produced was then measured as a function of the filled slots, confirmed slots, and number of actions performed by the system in each dialogue. In this experiment, both the linear feature combination model and the best n-grams (5-gram and 4-gram) produced similar results. Hence the accuracy of the simulations is evaluated more thoroughly here than in Scheffler and Young (Reference Scheffler and Young2002) (see Section 6.3). Recall that Scheffler and Young (Reference Scheffler and Young2002) only showed that their user and error models simulate different scenarios well enough to perform relative predictions of their durations.

10.5 Experimental results

A dialogue strategy was learned from the annotated COMMUNICATOR data, and then tested with a user simulation trained on the same data. The strategy outperformed all the COMMUNICATOR systems—it scores 35.42% higher than the average COMMUNICATOR system. The authors find that when the relative importance of the RL and SL components are adjusted, the best hybrid policy performs 302% better than the standard RL policy, and 1.4% better than the supervised policy. The standard RL technique (i.e. without the SL component to constrain exploration) has an enormous policy space to search, so it is clear that the optimal strategy has not yet been found with this method. The main advantage of the hybrid method in fact comes from its supervised component: a ‘multi-version’ system is being learned which blends the best aspects of the original COMMUNICATOR systems. RL, in the hybrid method, is able to improve slightly, but significantly, over this SL policy.

Lemon et al. (Reference Lemon, Georgila and Henderson2006a) shows that the Hybrid Strategy also outperforms a state-of-the-art handcrafted system when tested on real users with the ‘TownInfo’ SDS (Lemon et al., Reference Lemon, Georgila, Henderson and Stuttle2006b). Since the ‘TownInfo’ system operates in a different domain, (the Tourist Information domain as opposed to the COMMUNICATOR domain), this result also demonstrates that it is possible to learn effective generic slot-filling strategies. This suggests that it should be unnecessary to collect new training data for every different slot-filling domain, and indeed that data from different slot-filling domains can be pooled. Such an outcome is welcome because collecting dialogue data can be very time-consuming.

These results show that large state-spaces can be handled, and that good policies can be learned by doing so. However, the approach of simply using all available state information for COMMUNICATOR systems does not tell us which aspects of the state (in particular, of the dialogue history) are really important for the dialogue management task. Additionally, no qualitative analysis of the learned strategy is provided. Despite the positive results described above, the very small improvement of the hybrid policy over the purely supervised policy suggests that it is sub-optimal. It would also be interesting to know whether this learned strategy is better than what could have been learned using a small state-space and standard RL without a generalization method. In the next section, we go on to describe work that addresses these issues.

11.1 State features and action sets

In Frampton and Lemon (Reference Frampton and Lemon2006), strategies are learned for a 4-slot system, but in Frampton and Lemon (Reference Frampton and Lemon2008), they are learned for a 3-slot system because the ‘TownInfo’ SDS (Lemon et al., Reference Lemon, Georgila, Henderson and Stuttle2006b) used in the real user experiment has three information slots. Both Frampton and Lemon (Reference Frampton and Lemon2006, 2008) use the following three state representations:

1. 1. Slot-status baseline strategy: a slot-status feature for each of the slots, with the values ‘empty’, ‘filled’ and ‘confirmed’;

2. 2. DA1 strategy: the slot-status features plus the DA(s) of the last user turn;

3. 3. DA2 strategy: the slot-status features plus the DAs of both the last user and system turns.

Below is a list of all of the different actions that the RL DM can take and must learn to choose between based on the context, (i = the total number of slots):

1. 1. an open question e.g. ‘How may I help you?’;

2. 2. ask the value for any of slots 1…i;

3. 3. explicitly confirm any of slots 1…i;

4. 4. ask for the ith slot whilst implicitly confirming slot value i − 1 or i + 1Footnote 10.

5. 5. give help;

6. 6. pass to human operator;

7. 7. database query.

There are two restrictions regarding which actions can be taken in which states:

1. 1. An open question is only available at the start of the dialogue.

2. 2. It is only possible to attempt to confirm non-empty slots.

As stated above, following the real user experiment, Frampton and Lemon (Reference Frampton and Lemon2008) describes two additional simulation experiments that further investigate how the DAs improve the learned strategies. These experiments involve learning three new strategies using three new state representations, which are listed below. The DA1^β and DA2^β strategies are used in the first experiment to investigate whether the recent DAs only improve the learned strategy through repair strategies for when the last user turn fails to change the slot-status features. The Slot Features Unchanged (SFU) strategy is used in the second experiment to investigate whether the recent DAs also affect which is the best repair strategy to apply.

1. 1. DA1^β Strategy: Same as DA1 except that the last user turn DA(s) feature was changed to only take a DA value when the slot-status features are unchanged.

2. 2. DA2^β Strategy: Same as DA2 except that the last user and system DA features were changed to only take DA values when the slot-status features are unchanged.

3. 3. SFU Strategy: the slot-status features plus a binary feature that records whether the slot-status features have been changed by the last user turn.

In investigating how the recent DAs affect which repair strategy is best to apply, the second experiment also involves testing strategies which follow the learned DA2 strategy except when the slot-status features are unchanged, whereupon they use handcrafted repair strategies. More details will be provided in Section 11.4.

11.2 Reward function

Frampton and Lemon (Reference Frampton and Lemon2006) uses the following ‘all-or-nothing’ reward function:

1. 1. database query, all slots confirmed: +100.

2. 2. any other database query: −75.

3. 3. user simulation hangs-up: −100.

4. 4. dialogue system passes the call to a human operator: −50.

5. 5. each system turn: −5.

This reward function rewards confirmed slots because the slot-values are more likely to be correct if they are confirmed. The maximum reward that can be obtained for a single dialogue is 85 (the DM prompts the user, the user replies by filling all of the slots in a single utterance, and the DM asks for confirmation of all of the slots, the user gives it, and the DM submits a database query). The reward function is called ‘all-or-nothing’ because it only awards positive reward when a database query is made with all four slots confirmed. An alternative kind of reward function would give some positive reward for each confirmed slot. Such a reward function can be referred to as a ‘partial’ reward function. An ‘all-or-nothing’ training reward function was preferred here because the n-gram simulations do not simulate unobtainable slot-values, and given that this is the case, an ‘all-or-nothing’ reward function will produce faster learning. Frampton and Lemon (Reference Frampton and Lemon2005) provides an example of this. Frampton and Lemon (Reference Frampton and Lemon2008) also learns strategies using a reward function which gives +100 for a database query with all slots confirmed, and −5 for each system turn.

For evaluating strategies, Frampton and Lemon (Reference Frampton and Lemon2006) used both the reward function described above, and the ‘HLG05’ reward function, which was used by HLG and was introduced in Section 10.3. Frampton and Lemon (Reference Frampton and Lemon2006) used the ‘HLG05’ reward function in evaluation in order to enable performance comparisons between their own learned strategies, and the Hybrid Strategy of HLG and the handcrafted COMMUNICATOR systems.

11.3 Stochastic user and error simulations

Both Frampton and Lemon (Reference Frampton and Lemon2006, Reference Frampton and Lemon2008) trained and tested strategies using the n-gram simulations already described in 10.4. Recall that the n-gram probabilities are learned from the COMMUNICATOR data, and that ASR and NLU errors are incorporated since the model is built from the user utterances as they are recognized by the ASR and NLU components of the original COMMUNICATOR systems. Frampton and Lemon (Reference Frampton and Lemon2006, Reference Frampton and Lemon2008) used 4- and 5-gram simulations. For each state representation, a strategy was learned with the 4-gram and then tested with the 5-gram, and then vice-versa. With regard to the state representation, note that DAs of turns further back than the last system turn were beyond the context window to which the 4-gram user simulation can be sensitive, and so could not have improved the learned strategy.

11.4 Experimental results

Initial simulation experiments. Frampton and Lemon (Reference Frampton and Lemon2006) reports that in testing with the n-gram simulations, DA2 performs significantly better than DA1, which performs significantly better than the Slot-Status Strategy. This is as a result of significant improvements in dialogue length (8.84 system turns versus 9.25 versus 9.7), rather than task completion—since the n-gram simulations do not simulate unobtainable slot-values, all three of the learned strategies are always able to fill and confirm all of the slot-values. Analysis strongly suggests that the improvement in dialogue length is due to better repair strategies for states in which dialogue progress has stalled and hence the slot-status features are unchanged. Such states are caused by ASR rejections or user utterances that are recognized as out-of-domainFootnote 11, and the better repair strategies of DA1 and DA2 are more likely to ensure that the same is not also true in the next user turn. Whereas the Slot-Status Strategy always repeats its last question/confirmation, the DA strategies use additional repair strategies, for example, ‘switching focus’ (asking/confirming a different unfilled/unconfirmed slot), and giving help. Frampton (Reference Frampton2008) and Frampton and Lemon (Reference Frampton and Lemon2008) also mention ‘backtracking’ (re-asking a filled slot). Frampton (Reference Frampton2008) provides more detailed analysis, and points out that the findings make sense given that previous research on repair strategies has shown that in such contexts, repeating the last action is often not the best choice (e.g., Skantze, Reference Skantze2003; Bohus & Rudnicky, Reference Bohus and Rudnicky2005).

According to the HLG05 reward function, the learned strategies also outperform the handcrafted COMMUNICATOR systems and the Hybrid Strategy of HLG (191.16 on average per dialogue versus 103.6 and 140.3 respectively). Note that the comparison with the handcrafted COMMUNICATOR systems must be taken with-a-pinch-of-salt, because these systems were tested with real users (who could fail to fill slots) rather than in simulation. On the comparison with the Hybrid Strategy, this performs worse than DA2 because it is almost entirely a supervised strategy (the RL component only leads to an approximately 1% improvement over the purely supervised policy) and thus does not fully exploit the power of exploratory RL as the DA2 strategy does. Recall that the Hybrid Strategy has an enormous policy space to search, with relatively little data to work with, so it is clear that the optimal strategy has not yet been found with this method. A further potential reason why the Hybrid Strategy performs worse is that it was trained with PARADISE scores rather than with a reward function based only on filling/confirming slots and dialogue length. Recall that PARADISE scores indicate user satisfaction (see Section 4.2 for the list of features). We would expect the HLG and PARADISE reward functions to be directly correlated in general, but this is not necessarily always true. For example, it may well be that in certain circumstances, user satisfaction is higher when fewer slots are filled/confirmed—if there are a large number of speech recognition errors, the process of filling/confirming another slot may cause the user great frustration and so reduce their overall satisfaction.

Real user experiment. In the real user experiment of Frampton and Lemon (Reference Frampton and Lemon2008), DA2 outperforms both the state-of-the-art handcrafted strategy and the Slot-Status Strategy in terms of task completion (+9% average, p < 0.05), and dialogue length (p < 0.05 versus Slot-Status). It is said that analysis of these experiments emphasized why re-asking or re-attempting a confirmation is often a poor repair strategy. When the last user turn had failed to fill/confirm a slot-value it was usually due to one or more ASR errors. The repetition then employed by the Slot-Status and handcrafted strategies was very likely to frustrate the user, eliciting irritated/hyperarticulate speech which caused further ASR errors, and so longer dialogues and lower task completion. Note that since the strategy was tested here in a different domain from the one in which it was trained, like Lemon et al. (Reference Lemon, Georgila and Henderson2006a), this result suggests that it is possible to learn generic slot-filling strategies.

How do Dialogue Acts improve the learned strategy? In the first additional simulation experiment in Frampton and Lemon (Reference Frampton and Lemon2008), no significant difference in performance is found between DA1 and DA1^β, or DA2 and DA2^β. Hence, ignoring DAs in contexts where progress is being made in the dialogue has no significant impact on the learned strategy’s performance. The value of the DAs here seems to be entirely in learning repair strategies for when the slot-status features are unchanged by the last user turn.

In the second additional simulation experiment, the SFU Strategy is found to perform significantly worse than DA2 (p < 0.005), showing that recent DAs not only indicate when a repair strategy is required, but also which is best to apply. However, given that previous research, Bohus and Rudnicky (Reference Bohus and Rudnicky2005) and Skantze (Reference Skantze2003) and the real user experiment highlighted that repetition can be a poor repair strategy, it is still possible that choosing the best repair strategy is very simple because any ‘sensible’ avoidance of repetition will always be optimal. This hypothesis is also investigated by the second simulation experiment. Here any of the repair strategies that emerged from the RL are considered ‘sensible’, for example, having asked for a slot-value on the last turn, switching focus, giving help or backtracking would be ‘sensible’. Hence, in order to investigate this, tests were conducted for three new strategies that follow DA2 until the slot-status features are unchanged, whereupon they always take a sensible action that is different from the last system action. The first switches focus to an unfilled/unconfirmed slotFootnote 12, while assuming that the slot-status features remain unchanged, the second alternates between first giving help and then re-attempting the original question/confirmation, and the third between giving help and then switching focus. However all three of these strategies perform significantly worse than DA2 (p < 0.005), and so the conclusion is that it is at least not always true that any sensible repair strategy which avoids repetition will be optimal.

This work of Frampton (Reference Frampton2008) and Frampton and Lemon (Reference Frampton and Lemon2006, Reference Frampton and Lemon2008) then shows that recent DAs can be used to learn improved, full, slot-filling dialogue strategies. They improve the learned strategies here by producing more effective repair strategies for when the slot-status features are unchanged by the last user turn. They indicate when a repair strategy is required (when the slot-status features are unchanged), and also which is best to apply. Although repetition is shown to often be a poor repair strategy, the final experiment also shows that it is at least not always true that any sensible repair strategy that avoids repetition will be optimal.

We now provide a summary and comparison of the research described in this survey, and open problems for the field.

12.1 Learning methods

Researchers followed one of two general methods, these being:

1. 1. Model-based approaches. Learn partial strategies from exploratory data generated by dialogues with real users (Walker, Reference Walker2000; Singh et al., Reference Singh, Kearns, Litman and Walker1999, Reference Singh, Litman, Kearns and Walker2002; Tetreault & Litman, Reference Tetreault and Litman2006). Due to the smaller number of variables, DP can be an option for the learning algorithm.

2. 2. Simulation-based approaches. Learn full strategies from exploratory data generated by dialogues with simulated users (Levin et al., Reference Levin, Pieraccini and Eckert2000; Pietquin & Renals, Reference Pietquin and Renals2002; Scheffler & Young, Reference Scheffler and Young2002; English & Heeman, Reference English and Heeman2005; Paek & Chickering, Reference Paek and Chickering2005; Frampton & Lemon, Reference Frampton and Lemon2006, Reference Frampton and Lemon2008). A larger number of variables means some approximation to DP must be applied, e.g. MC or TDL.

The exception to this is HLG. Here, a ‘hybrid’ SL/RL approach is used for learning full strategies from data generated by dialogues with real users. Additionally, a generalization technique is used to cope with the very large state–action space. Like a model-based approach, HLG do not use a user simulation for training, and instead, learn a dialogue strategy from a fixed data set of real user dialogues. However, they do not try to directly model the transition probabilities and apply DP. Instead they use an alternative learning approach that means that they can learn full strategies with a very large state–action space: ‘hybrid’ SL/RL (TDL) with a generalization method.

One drawback with applying RL to learn dialogue strategies is that it can be very time-consuming to collect the initial data set. However, it should be noted that both Lemon et al. (Reference Lemon, Georgila and Henderson2006a) and Frampton and Lemon (Reference Frampton and Lemon2008) showed that it was possible to learn a strategy in one slot-filling domain (flight-booking) which works well in another (tourist information). This finding suggests that it should be unnecessary to collect new training data for every different slot-filling domain, and indeed that data from different slot-filling domains can be pooled. In the future, dialogue strategy designers may find it more profitable to map between slots based on how likely it is that a user’s slot-value will be correctly recognized—recall that Pietquin and Renals (Reference Pietquin and Renals2002) learned a strategy which asks the slots in an order that is sensitive to WER (see Section 5).

12.2 Comparing the state spaces

In constructing their state space, researchers must try to include as much important contextual information as possible without making it so large that the RL problem becomes intractable. All of the researchers apart from Paek and Chickering (Reference Paek and Chickering2005) hand-picked their state features. Paek and Chickering (Reference Paek and Chickering2005) treated the MDP as a special case of an influence diagram, and then applied techniques for learning which features should be represented in the state. Of those that learned full strategies for slot-filling systems, Levin et al., (Reference Levin, Pieraccini and Eckert2000), Pietquin and Renals (Reference Pietquin and Renals2002) and Scheffler and Young (Reference Scheffler and Young2002) only used slot-based features, for example, whether a slot is filled, any associated confidence score, and so on. HLG used additional features, for example, features for the complete dialogue history, which produced a very large state-space and necessitated a hybrid SL/RL method with linear function approximation. Frampton and Lemon (Reference Frampton and Lemon2006, Reference Frampton and Lemon2008) used recent DAs in addition to slot-status features. Tetreault and Litman (Reference Tetreault and Litman2006) learned strategies in the tutorial domain, and used state features for user Correctness (in their most recent answer), user Certainty, Concept Repetition (whether the system has repeated a concept), user Frustration and Percent Correct (the proportion of questions on the current topic answered correctly by the user).

12.3 Different reward functions

Most of the researchers use a simple reward function that rewards task completion and penalizes dialogue length, and the weights for each are set in a fairly ad hoc manner. By contrast Walker (Reference Walker2000) and HLG use PARADISE (Walker et al., Reference Walker, Kamm and Litman2000) user satisfaction scores. Such scores have the advantage that they are data-driven (they were supplied by real users), and secondly, they take account of more than just task completion and dialogue length. PARADISE is a framework for predicting user satisfaction based on metrics, which can be automatically logged by the system, and so future researchers may find it productive to experiment with this framework and perhaps add new and different variables.

12.4 User simulation and error modeling methods

Of the user simulations used by researchers, all are at least partially stochastic and are capable of simulating mixed-initiative dialogues. The user simulations of Levin et al. (Reference Levin, Pieraccini and Eckert2000), Pietquin and Renals (Reference Pietquin and Renals2002) and Scheffler and Young (Reference Scheffler and Young2002) supply actual slot-values, and so have a deterministic element to ensure that their behavior is consistent within a dialogue. The simulations developed by HLG (linear function approximation and n-grams derived from COMMUNICATOR data; Walker et al., Reference Walker and Passonneau2001) do not supply actual slot-values and so do not have this deterministic element. All of the probabilities for the user simulations of Scheffler and Young (Reference Scheffler and Young2002) and HLG are learned from data, and some of the probabilities for the user simulation of Levin et al. (Reference Levin, Pieraccini and Eckert2000) are. The probabilities for the simulation of Pietquin and Renals (Reference Pietquin and Renals2002) are entirely supplied using intuition.

To simulate ASR/NLU errors Pietquin and Renals (Reference Pietquin and Renals2002), Scheffler and Young (Reference Scheffler and Young2002), and HLG also have a probabilistic error model. The probabilities for the error model of Scheffler and Young (Reference Scheffler and Young2002) and HLG are learned from data, while the probabilities for the error model of Pietquin and Renals (Reference Pietquin and Renals2002) are supplied using intuition.

Efforts were made to establish the accuracy of the simulations used by Scheffler and Young (Reference Scheffler and Young2002), HLG (linear function approximation simulation derived from COMMUNICATOR data; Walker et al., Reference Walker, Aberdeen, Boland, Bratt, Garofolo, Hirschman, Le, Lee, Narayanan, Papineni, Pellom, Polifroni, Potamianos, Prabhu, Rudnicky, Sanders, Seneff, Stallard and Whittaker2001a), and Frampton and Lemon (Reference Frampton and Lemon2006, Reference Frampton and Lemon2008) (n-gram simulations derived from COMMUNICATOR). Scheffler and Young (Reference Scheffler and Young2002) showed that their user and error models simulate different scenarios well enough to perform relative predictions of their durations. The accuracy of the linear function approximation and n-gram simulations is evaluated more thoroughly (Georgila et al., Reference Georgila, Henderson and Lemon2005a, 2005b). These simulations were evaluated on the COMMUNICATOR data in terms of perplexity. Each one of the user models was also run against a system strategy learned with purely SL (using linear function approximation) and the quality of the simulated dialogues produced was then measured as a function of the filled slots, confirmed slots, and number of actions performed by the system in each dialogue. The accuracy of the n-gram simulations is further established by the positive results in the real user tests of Frampton and Lemon (Reference Frampton and Lemon2008).

12.5 Open problems

The prior work brings to light a number of open problems for the field, which include:

• • Can we develop user simulations that are accurate enough to reliably train RL dialogue managers? What metrics can be used to evaluate user simulations?

• • What additional contextual information will it be useful to represent in the state, particularly for non-slot-filling systems which have received less attention so far? Can automatic feature selection methods be applied to dialogue data to provide an automatic method for identifying the important contextual features?

• • Is additional contextual information only useful in certain portions of the policy space? If it is, then it could be sacrificed where it is known to be redundant, so helping to reduce the size of the policy search-space.

• • Can we develop better reward functions using the PARADISE framework, e.g. are there additional factors that we should consider in evaluating user satisfaction and are these domain-specific or domain-independent?

These questions provide very interesting avenues for future research.