Heriberto Cuayáhuitl
email: h.cuayahuitl@ed.ac.uk

Steve Renals

Oliver Lemon

Hiroshi Shimodaira

Evaluation of a hierarchical reinforcement learning spoken dialogue system

Keywords: Spoken dialogue systems, hierarchical reinforcement learning, human-machine dialogue simulation, dialogue strategies, system evaluation

We describe an evaluation of spoken dialogue strategies designed using hierarchical reinforcement learning agents. The dialogue strategies were learnt in a simulated environment and tested in a laboratory setting with 32 users. These dialogues were used to evaluate three types of machine dialogue behaviour: hand-coded, fully-learnt and semi-learnt. These experiments also served to evaluate the realism of simulated dialogues using two proposed metrics contrasted with 'precision-recall'. The learnt dialogue behaviours used the Semi-Markov Decision Process (SMDP) model, and we report the first evaluation of this model in a realistic conversational environment. Experimental results in the travel planning domain provide evidence to support the following claims: (a) hierarchical semi-learnt dialogue agents are a better alternative (with higher overall performance) than deterministic or fully-learnt behaviour; (b) spoken dialogue strategies learnt with highly coherent user behaviour and conservative recognition error rates (keyword error rate of 20%) can outperform a reasonable hand-coded strategy; and (c) hierarchical reinforcement learning dialogue agents are feasible and promising for the (semi) automatic design of optimized dialogue behaviours in larger-scale systems.

Introduction

A spoken dialogue system can be defined as consisting of four interlinked modules: speech understanding, dialogue management, response generation, and a knowledge base. In a human-machine dialogue, a user's spoken utterance is received as a speech waveform, which may have been distorted, by the speech understanding module which extracts a user dialogue act from the speech signal. The dialogue act is entered into the machine's knowledge base, and the machine then updates its dialogue state using information extracted from the knowledge base. The machine dialogue state is used by the dialogue manager to choose a machine dialogue act which is then used by the response generation module to produce a corresponding machine speech signal in reply to the user. This is a cyclical process, illustrated in Figure 1, which continues until one of the participants in the conversation (human or machine) ends the dialogue.

In this paper we are primarily concerned with the dialogue manager. Given the current state of the dialogue, the principal role of the dialogue manager is to choose an action, which will result in a change of dialogue state. The strategy followed by the dialogue manager, sometimes referred to as the policy, should be designed to enable successful, efficient and natural conversations. This is a challenging goal, and in most fielded spoken dialogue systems the dialogue manager is handcrafted by a human designer. This hand-crafted approach is limited since it is not always easy to specify the optimal action at each state of the dialogue, a dialogue behaviour for the entire user population which is generic and static is usually assumed, and designing such strategies is labour-intensive, especially for large systems.

Since the mid-1990s a number of researchers have explored the development of automatic algorithms that can specify a dialogue strategy. In particular, reinforcement learning approaches [START_REF] Sutton | Reinforcement Learing: An Introduction[END_REF] have been used to optimize a machine's dialogue behaviour [START_REF] Levin | A stochastic model of computerhuman interaction for learning dialog strategies[END_REF][START_REF] Walker | Learning optimal dialogue strategies: a case study of a spoken dialogue agent for email[END_REF][START_REF] Levin | A stochastic model of human machine interaction for learning dialog strategies[END_REF][START_REF] Young | Probabilistic methods in spoken dialogue systems[END_REF]. In this scenario, a conversation is regarded as a sequence of dialogue states, with the machine receiving a reward for executing an action inducing a state transition in the conversational environment, as illustrated in figure 2.

A reinforcement learning dialogue agent aims to learn its behaviour from interaction with an environment, where situations are mapped to actions by maximizing a long-term reward signal. Briefly, the standard reinforcement learning paradigm works by using the formalism of Markov Decision Pro- cesses (MDPs) [START_REF] Kaelbling | Reinforcement learning: a survey[END_REF][START_REF] Sutton | Reinforcement Learing: An Introduction[END_REF]). An MDP is characterized by a set of states S, a set of actions A, a state transition function, and a reward or performance function that rewards the agent for each selected action. Solving the MDP means finding a mapping from the current state s t to an action a t corresponding to a dialogue policy π * (s t ):

π * (s t ) = arg max at∈A Q * (s t , a t ).
(1)

The Q function specifies the cumulative rewards for each state-action pair.

An alternative but more computationally intensive model for sequential decisionmaking under uncertainty is the partially observed MDP (POMDP). In a POMDP the dialogue state is not known with certainty (as opposed to an MDP), and solving it means finding a mapping from belief states to actions [START_REF] Williams | Partially observableMarkov decision processes for spoken dialog systems[END_REF].

Most previous work on dialogue strategy learning has aimed to obtain a single global solution [START_REF] Levin | A stochastic model of human machine interaction for learning dialog strategies[END_REF][START_REF] Walker | An application of reinforcement learning to dialogue strategy selection in a spoken dialogue system for email[END_REF][START_REF] Young | Probabilistic methods in spoken dialogue systems[END_REF][START_REF] Singh | Optimizing dialogue management with reinforcement learning: Experiments with the NJFun system[END_REF][START_REF] Scheffler | Automatic learning of dialogue strategy using dialogue simulation and reinforcement learning[END_REF][START_REF] Pietquin | A Framework for Unsupervised Learning of Dialogue Strategies[END_REF][START_REF] Williams | Partially observable Markov decision processes for spoken dialogue management[END_REF][START_REF] Young | The hidden information state approach to dialogue management[END_REF]. The optimization of dialogue strategies has been carried out using two main approaches: corpus-based approaches [START_REF] Walker | An application of reinforcement learning to dialogue strategy selection in a spoken dialogue system for email[END_REF][START_REF] Litman | Automatic optimization of dialogue management[END_REF] which make use of an experimentally collected set of dialogues for training the dialogue strategy (or some aspects of it); and simulationbased approaches [START_REF] Scheffler | Automatic learning of dialogue strategy using dialogue simulation and reinforcement learning[END_REF][START_REF] Frampton | Using Dialogue Acts in Dialogue Strategy Learning: Optimizing Repair Strategies[END_REF][START_REF] Rieser | Bootstrapping Reinforcement Learning-Based Dialogue Strategies from Wizard-Of-Oz data[END_REF][START_REF] Henderson | Hybrid reinforcement/supervised learning of dialogue policies from from fixed data sets[END_REF] in which a simulation environment including a user model is employed to generate simulated dialogues for training.

A dialogue strategy may not require complete world knowledge, nor is it always necessary for the whole action set to be available at each state. In this paper we address such issues using a hierarchical sequential decision making approach, in which dialogue states can be described at different levels of granularity, and an action can execute behaviour using either a single dialogue act or a composite sub-dialogue. This approach offers several benefits. First, modularity helps to solve sub-problems that may be easier to solve than the whole problem. Second, sub-problems may include only relevant dialogue knowledge in the states and relevant actions, thus reducing significantly the size of possible solutions: consequently they can be found faster. Finally, there is the possibility to reuse sub-solutions when dealing with new problems. These properties are crucial for learning the behaviour of large-scale spoken dialogue systems in which there may be a large set of state variables or a large number of actions. The cost of this approach is that optimal solutions may not be guaranteed; however, this suboptimality may be well worth the gains in terms of scalability to large systems.

This paper has two main contributions. First, we have developed and evaluated a heuristic simulation environment used to learn dialogue strategies in an automatic way. Second, we have developed and evaluated hierarchical spoken dialogue behaviours learnt using a Semi-Markov Decision Process (SMDP) to address the problem of scalable dialogue optimization, described in more detail in [START_REF] Cuayáhuitl | Hierarchical Reinforcement Learning for Spoken Dialogue Systems[END_REF]. We have compared these hierarchical, or 'semi-learnt' behaviours, with both hand-crafted and fully-learnt behaviours and we have found that the semi-learnt behaviours are more suited to deployment. Our evaluations have been carried out in tests with real users in the context of a spoken dialogue system in the travel planning domain.

The rest of the paper is organized as follows: Section 2 describes the dialogue simulation environment. Section 3 briefly describes the hierarchical reinforcement learning dialogue agents. Section 4 describes the travel planning spoken dialogue system. Sections 5 reports an evaluation of machine dialogue behaviours. Section 6 provides a quantitative evaluation of the simulated environment. Finally, Sections 7 and 8 discuss and summarize our findings.

A heuristic dialogue simulation environment

A simulation environment for human-machine conversations involves modelling the dynamics of everything that is outside the dialogue manager. This section presents a heuristic simulation approach for generating humanmachine conversations based on dialogue acts. The proposed approach generates both coherent and distorted conversations, useful for testing and learning dialogue strategies for information-seeking mixed-initiative spoken dialogue systems. This approach does not require data for training the models in the simulation environment (this is useful in scenarios where dialogue data does not exist), as it uses heuristics to simulate the dynamics of task-oriented conversations based on dialogue acts. It employs two main simulation modelssimulated user behaviour and ASR error simulation-which are shown in the bottom of Figure 3. The first simulation model (on the right of the figure) generates coherent user responses, i.e. responses that make sense to humans.

Here it was assumed that real users behave in a coherent fashion, based on user dialogue acts that are consistent according to a user Knowledge Base (KB) that keeps the history of the conversation. This is a strong assumption and its validity is addressed later. The second model distorts coherent user dialogue acts due to imperfect speech recognition and understanding. The distorted user responses and database results update the machine's KB so that the dialogue strategy can choose actions accordingly. The proposed dialogue simulator uses an ontology to represent the conversant's knowledge base.

Figure 3 shows the agent-environment interaction for human-machine dialogue simulation. The interaction is as follows: the machine is in a given dialogue state s m t , and emits dialogue act a m t by following dialogue strategy π(s m t ). A distorted machine dialogue act ãm t (machine response 1 ) is fed into the user's KB to observe the user dialogue state s u t , from which an action a u t 1 The reason for distorting machine responses was to model user confusions.

Figure 3: The agent-environment interaction for simulating human-machine conversations, useful for learning or testing dialogue strategies for spoken dialogue systems.

is taken (user response). This user response is distorted with ASR errors into ãu t , and is fed into the machine's KB. The machine action may require interaction with simulated database behaviour by sending queries and retrieving database results d t . Then the next machine state s m t+1 is observed from the machine's current KB. Once the machine is in a new state, it takes another dialogue act, and so on until the end of the conversation.

Modelling conversational behaviour

A human-machine dialogue can be modelled by the perceptions and actions of both conversants. Figure 4 shows the dynamics of communication at the dialogue act level. The conversants use two sources of knowledge at different levels of granularity: knowledge-rich states k t (also referred to as "knowledge base") to represent all possible perceptions about the conversation, and knowledge-compact states s t to represent a compact version of the current dialogue state. The latter are used for action selection.

Algorithm 1 specifies the high-level steps for simulating a task-oriented human-machine dialogue. Briefly, the algorithm starts initializing parame-Figure 4: Dynamics of human-machine communication at the dialogue act level (this diagram does not follow the conventions of dynamic Bayesian networks). A conversant in a knowledge-rich state k t , observes a knowledge-compact state s t , and takes dialogue act a t in order to feed it to its knowledge-rich state and convey it to its partner, received distortedly as ãt . The current knowledge k t , action a t and partner response determine the next knowledge-rich state k t+1 , and so on until the end of the dialogue.

ters for the knowledge bases (ontologies of dialogue entities) of both conversants. The algorithm invokes three simulated behaviours: the machine's dialogue strategy π m t , the user's dialogue strategy π u t , and the distorter of machine/user dialogue acts δ. A conversant at a time interacts with its partner as follows: (a) observes the current knowledge-compact state, (b) selects an appropriate dialogue act type, (c) generates a dialogue act with the current dialogue act type in context, (d) distorts such dialogue act to simulate misrecognitions or misunderstandings, (e) updates its knowledge-rich state with the undistorted dialogue act, and (f) updates the knowledge-rich state of its partner with the distorted dialogue act. This process iterates until one of the conversants terminates the dialogue. until one of the conversants terminates the conversation 18: end function Enumerating all possible machine or user dialogue acts usually results in large sets. Therefore, our approach assumes that action selection of both conversants is based on dialogue act types rather than dialogue acts. This is beneficial because for task-oriented conversations a small set of dialogue act types can be employed. Table 1 shows the core dialogue act types that define the behaviour of our human-machine simulated conversations. The user dialogue act types are a subset of the ones used by Georgila et al. (2005), and the set of machine dialogue act types are an extension of the ones used by [START_REF] Walker | DATE: A dialogue act tagging scheme for evaluation of spoken dialogue systems[END_REF]. Based on this, the agent selects dialogue act types following dialogue strategy π m , and the user selects dialogue act types following dialogue strategy π u . Once an action has been chosen, it takes context into account so that conversations can be generated at the dialogue act level. Context is given by the dialogue state, which specifies the slot in focus, slots to fill or confirm, etc. A sample machine action for requesting the slot date is "a m t = req(date)" and a corresponding sample user response is "a u t = pro(date = 01dec2007, time = morning)". Based on this, the user takes actions following dialogue strategy π u defined by

π u (s u t ) =           
pro if last machine action a m is a request or offer con if last action a m is a correct explicit confirmation or incorrect explicit confirmation (the latter with some probability, e.g. 0.2) rep if last action a m is an apology or incorrect confirmation sil otherwise,

(2) and the machine takes actions a following dialogue strategy π m (s m t ) defined by (3) Although the strategy π u may not include all possible realistic behaviours, it yields coherent behaviour, and its evaluation is addressed later. Finally, the hand-crafted strategy π m acts as the baseline strategy in our experiments using reinforcement learning agents as described in the next sections.

a =                                                    ope if first

Speech recognition error simulation

Due to the fact that current Automatic Speech Recognition (ASR) technology is far from perfect, errors have to be modelled in the simulated environment. This simulation model operated with a two-stage approach. First, slot values of user dialogue acts were distorted with probability p(user) = 0.2 in order to model machine confusions; applying equal amounts of insertions, substitutions and deletions. Second, slot values were assigned with random confidence levels; they were assigned the well known three-tiered confidence levels (low, medium, high) to indicate their speech recognition confidence. In addition, slot values of machine dialogue acts were distorted with probability p(agent) = 0.1 in order to model user confusions.

An illustrative decision-making problem

Consider that you have the task of designing a spoken dialogue strategy for a flight booking system. In such a system the user can say things such as 'a flight from London to Prague for the twenty second of October in the morning travelling with KLM'-alternatively, the user may provide the information across several shorter utterances. A dialogue strategy is a mapping from dialogue states to actions and specifies the system's way of behaving. The dialogue state (used to describe the current situation in the conversation) is defined by a vector of state variables as illustrated in Figure 5. This decision-making problem has 281 250 states ( X i ∈X |X i |). A sample dialogue using this state space is shown in Table 2. Table 3 shows the same sample dialogue but including dialogue acts generated as described in the previous two sub-sections. The mapping from states to actions can be done either manually, or using flat reinforcement learning methods, or using hierarchical reinforcement learning methods as described in the rest of this paper. The benefits of reinforcement learning include automatic design and optimal behaviour according to a performance measure, while hierarchical methods aim to have a more practical application for systems with large state-action spaces.

Hierarchical reinforcement learning dialogue agents

A critical problem in flat Reinforcement Learning (RL) is scalability since it operates with a single policy that behaves by executing only primitive actions. The size of state spaces grows exponentially with the number of state variables incorporated into the environment state-the 'curse of dimensionality'. As a result, RL agents find solutions only very slowly. Temporal abstraction addresses these problems by incorporating hierarchical structures into RL agents. This is attractive for dialogue systems for several reasons. First, human decision-making activity occurs in sequential courses of action, where decisions do not happen at each step, but rather in temporally extended activities following their own policies until termination (Barto and Mahadevan,

Agent Dialogue State Action

Sample Utterance SYS 0,0,0,0,0,0,0,1 req Tell me your flight information.

USR

A flight from Edinburgh to Paris. SYS 3,2,0,0,0,0,0,1 acc 3,2,0,0,0,0,2,1 mic+req OK, a flight from Edinburgh to Rome, when do you want to travel? USR I said 'to Paris'. SYS 4,3,0,0,0,0,2,1 sic+req OK, a flight to Paris, when do you want to fly? USR December first, flying with British Airways. SYS 4,4,1,0,2,0,2,1 apo+req I'm sorry, when do you want to travel? USR On the first of December. SYS 4,4,3,0,2,0,2,1 acc 4,4,3,0,2,0, SYS 4,4,4,4,4,4,5,2 [terminal state] Notes: This example is used for illustration purposes and shows basic behaviour of more complex interactions. Abbreviations: req=request, acc=accept w/high confidence, mic=multiple implicit confirmation, sic=single implicit confirmation, apo=apology, sec=single explicit confirmation, dbq=database query, sta=status of dialogue, pre=present information, ofr=offer choices. The second one please. SYS sec(flight=choice2) Did you say choice two? USR con(flight=yes)

That's right.

Note: more complex information presentation is beyond the scope of this work. 2003). Second, hierarchical decision makers can solve more complex problems than flat ones (Dietterich, 2000). Third, task-oriented dialogues have shown evidence of following hierarchical structures [START_REF] Grosz | Attention, intentions and the structure of discourse[END_REF][START_REF] Litman | A plan recognition model for subdialogues in conversations[END_REF]. This section presents two forms of hierarchical dialogue control and a case study that is evaluated in the rest of the paper.

Dialogue control using Semi-Markov decision processes

We formulate spoken dialogue control as a discrete Semi-Markov Decision Process (SMDP), following Dietterich (2000). A discrete-time SMDP M = <S, A, T, R> is characterized by a set of states S; a set of actions A; a transition function T that specifies the next state s ′ given the current state s and action a with probability P (s ′ , τ |s, a); and a reward function R(s ′ , τ |s, a) that specifies the reward given to the agent for choosing action a when the environment makes a transition from state s to state s ′ . The random variable τ denotes the number of time-steps taken to execute action a in state s. The SMDP model allows temporal abstraction, where actions take a variable amount of time to complete their execution. In this model two types of actions can be distinguished: (a) single-step actions roughly corresponding to dialogue acts, and (b) multi-step actions corresponding to sub-dialogues.

Figure 6: Conceptual hierarchical dialogue at runtime with states s t , actions a t (lasting τ time steps) and rewards r t+τ . Actions a t can be either primitive or composite, the former yield single rewards and the latter yield cumulative discounted rewards.

Figure 6 illustrates a conceptual dialogue at runtime with states s t , actions a t and rewards r t . Whilst the full dialogue and child dialogue execute primitive and composite actions, the grandchildren dialogues execute only primitive actions. Note that the execution of primitive actions yields single rewards and the execution of composite actions lasting τ time steps yields cumulative discounted rewards given at time t + τ .

In this paper we treat each composite dialogue action as a separate SMDP as described in [START_REF] Cuayáhuitl | Hierarchical dialogue optimization using semi-Markov decision processes[END_REF][START_REF] Cuayáhuitl | Hierarchical Reinforcement Learning for Spoken Dialogue Systems[END_REF]. In this way an MDP can be decomposed into multiple SMDPs hierarchically organized into L levels and N models per level, denoted as M = {M i j }, where j ∈ {0, ..., N -1} and i ∈ {0, ..., L -1}. Thus, any given SMDP in the hierarchy is denoted as M i j = <S i j , A i j , T i j , R i j >, see the environment of Figure 7 for an illustration.

The goal in an SMDP is to find an optimal policy π * , that maximizes the reward of each visited state. The optimal action-value function Q * (s, a) specifies the expected cumulative reward for executing action a in s and then following π * . The Bellman equation for Q * of subtask M i j can be expressed as

Q * i j (s, a) = s ′ ,τ P i j (s ′ , τ |s, a) R i j (s ′ , τ |s, a) + γ τ max a ′ Q * i j (s ′ , a ′ ) , (4)
where the discount rate 0 ≤ γ ≤ 1 makes future rewards less valuable than immediate rewards as it approaches 0. Finally, the optimal policy for each subtask is defined by

π * i j (s) = arg max a∈A i j Q * i j (s, a). (5)
These policies can be found by dynamic programming or reinforcement learning algorithms for SMDPs. For instance, the HSMQ-Learning algorithm of Dietterich (2000) approximates equation 4 according to

Q i j (s, a) ← (1 -α)Q i j (s, a) + r τ + γ τ max a ′ Q i j (s ′ , a ′ ) . (6)
This behaviour (also referred to as fully-learnt) receives rewards in the following form when executing actions a lasting τ time steps:

r τ = r 1 + γr 2 + γ 2 r 3 + ... + γ τ -1 r τ . (7)
The HSMQ-Learning algorithm converges to optimal context-independent policies (Dietterich, 2000). Although this is a weaker form of optimality than other forms for being only locally optimal, context-independent policies facilitate state abstraction (useful to compress the state) and policy reuse.

Dialogue control using constrained hierarchical SMDPs

The behaviour of reinforcement learning dialogue agents can be constrained with prior expert knowledge, aiming to combine behaviours specified by human designers and inferred automatically (Paek and Pieracini, 2008). In this direction we have reported an approach using reinforcement learning with Hierarchical Abstract Machines (HAMs) [START_REF] Cuayáhuitl | Reinforcement learning of dialogue strategies using hierarchical abstract machines[END_REF]. HAMs are used to reduce the available actions per state, similar to nondeterministic finite state machines whose transitions may invoke lower-level machines, each machine specifying a sub-dialogue. Because the HAMs approach does not overcome the curse of dimensionality, we extend the previous form of dialogue control by constraining each hierarchical SMDP with some prior expert knowledge. For such a purpose, we associate a HAM denoted as H i j to SMDP M i j in order to specify the prior knowledge [START_REF] Cuayáhuitl | Hierarchical Reinforcement Learning for Spoken Dialogue Systems[END_REF]. In this way, dialogue control can be seen as executing two decision-making models in parallel: a HAM, and a hierarchy of SMDPs. Each HAM partially specifies the behaviour of its corresponding subtask, and therefore constrains the actions that a reinforcement learning agent can take in each state. For such a purpose, a cross product of models per subtask is used, referred to as induced SMDP

M ′ i j = H i j • M i j .
Briefly, the cross product operates as follows: (1) the induced state space uses joint states (s, s), where s is an environment state in SMDP M i j and s is a choice state in HAM H i j ;

(2) a HAM tells its corresponding SMDP the available actions at state s; (3) the transition functions of both models are executed in parallel; and (4) the SMDP's reward function rewards each chosen primitive action. In this joint model the HAMs make decisions in states with a single action, and the policies of the SMDPs make decisions in states with multiple actions.

This form of behaviour (also referred to as semi-learnt) is based on the SMDP state s and the HAM choice state s. Using a more compact notation for the joint dialogue state w = (s, s) [START_REF] Marthi | A compact, hierarchical Qfunction decomposition[END_REF], the Bellman equation for the action-value function of induced subtask M ′ i j can be expressed as

Q * i j (w, a) = w ′ ,τ P i j (w ′ , τ |w, a) R i j (w ′ , τ |w, a) + γ τ max a ′ Q * i j (w ′ , a ′ ) . (8)
Optimal context-independent policies for the Q-value function above can be found by combining the algorithms HAMQ-Learning [START_REF] Parr | Reinforcement learning with hierarchies of machines[END_REF] and HSMQ-Learning (Dietterich, 2000) using the following update rule

Q ′i j (w t , a t ) ← (1 -α)Q ′i j (w t , a t ) + r t+τ + γ τ max a ′ Q ′i j (w t+τ , a ′ ) . (9)

Case study: A travel planning dialogue system

This is a multi-goal mixed-initiative spoken dialogue system in the travel planning domain, allowing users to book single flights, return flights, hotels and cars. It supports the following features: hand-crafted or learnt dialogue strategies, multiple goals within a single dialogue, and implicit switching across flight dialogue goals. For fully-learnt behaviour, the state space is described in Table 4 using a hierarchy of 21 dialogue subtasks. This hierarchy employed 43 non-binary state variables, 15 primitive actions and 20 composite actions. The latter correspond to the child subtasks. The reward function focused on efficient conversations (i.e. the shorter the dialogue the better), and is defined by the following rewards given to the agent for choosing action a when the environment makes a transition from state s to state s ′ :

r(s, a, s ′ ) =                    0 for successful (sub)dialogue -10 for an already collected subtask M i j -10 for collecting subtask M i i before M i i-1
-10 for presenting many/none items of information -10 for multiple greetings or closings -10 for executing action a and remaining in state

s ′ = s -1 otherwise. ( 10
)
Table 4: State variables and actions of the subtask hierarchy in the travel planning system. Whilst a flat approach involves a large state-action space in the order of 10 23 [START_REF] Cuayáhuitl | Hierarchical Reinforcement Learning for Spoken Dialogue Systems[END_REF], our hierarchical representation is only using a space of 800K state-actions.

Subtask State Variables

Actions (composite actions are For semi-learnt behaviour, the state-action space was similar to that of fully-learnt behaviour. The difference here is that the dialogue subtasks M i j were extended with Hierarchical Abstract Machines (HAMs) H k l , where their cross product yields the induced subtasks

M i j ) M 0 0 GIF,SAL,G00,G03,G04,G05 M 1 0 ,M 2 2 ,M 2 3 ,M 2 4 ,gre,clo M 1 0 GIF,G01,G02 M 2 0 ,M 2 1 M 2 0 DBT,END,MAN,OPT,TER M 3 0 ,M 3 1 ,M 3 2 ,dbq+sta,rel M 2 1 DBT,END,MAN,TER M 3 3 ,M 3 4 ,dbq+sta,rel M 2 2 DBT,END,INI,MAN,TER M 3 5 ,M 3 6 ,M 3 7 ,dbq+sta,rel M 2 3 DBT,END,INI,MAN, M 3 8 ,M 3 9 ,M 3 A ,M 3 B , OPT,TER dbq+sta,rel M 2 4 DBT,END,MAN,TER M 3 C ,M 3 D ,dbq+sta,rel M 3 0 SIF,C00,C01,C02,C03,C04,
M ′ i j = H k l • M i j .
The hierarchy of induced subtasks for the travel planning system is shown in Figure 8, and used the abstract machines described in Figures 9 and 10 (prohibiting apologies in medium and high confidence levels). These HAMs control the machine's dialogue behaviour in deterministic state transitions, but in stochastic state transitions the reinforcement learning agents optimized decision-making.

The learning parameters used by the algorithms were the same for both learning approaches. The learning rate parameter α decays from 1 to 0 according to α = 100/(100 + τ ), where τ represents elapsed time-steps in the current subtask. Each subtask M i j had its own learning rate. The discount factor γ = 1 makes future rewards equally as valuable as immediate rewards, as in [START_REF] Singh | Optimizing dialogue management with reinforcement learning: Experiments with the NJFun system[END_REF]. The action selection strategy used ǫ-Greedy with ǫ = 0.01, and initial Q-values of 0. This choice of parameters satisfies the requirements for convergence to optimal context-independent policies.

Qualitative description of hand-crafted and learnt dialogue strategies

The hand-crafted baseline strategy operated as follows: (a) if slot in focus is unknown then request information, with implicit confirmation if there were any filled slots; (b) if slot in focus is known with low confidence then do an apology; (c) if slot in focus is known with medium confidence then do an explicit confirmation; and (d) if slot in focus is known with high confidence then move the slot in focus to the next ascending one with lower value (this is also referred to as 'slot acceptance'). This behaviour is specified more concretely in equation 3, and its evaluation is reported in section 6.3.

The fully-learnt behaviour was inferred by the approach described in section 3.1. This strategy used all actions in every state and differs from the hand-crafted one by allowing acceptance, confirmation and rejection in any filled slot regardless of confidence level. For instance, action 'mic' can be chosen with low/medium/high confidence levels. Briefly, the learnt behaviour differed from the hand-crafted one in the use of more acceptances (action 'acc'), more multiple implicit confirmations (action 'mic'), fewer apologies (actions 'apo+req' and 'apo+ofr'), and fewer multiple explicit confirmations (action 'mec'). In addition, although the fully-learnt policy inferred the sequence of sub-dialogues, it used the same sequence as the other behaviours. 4.

Thus, the dialogue strategies of this paper differ in the selection of primitive (low level) actions rather than composite (high level) actions2 . The semi-learnt behaviour was inferred by the approach described in section 3.2. Similarly to the fully-learnt behaviour, this strategy differs from the hand-crafted one by allowing acceptance, confirmation and rejection in any filled slot regardless of confidence level. The semi-learnt behaviour differed from the hand-crafted one in the use of more acceptances (action 'acc'), more multiple implicit confirmations (action 'mic'), fewer apologies (actions 'apo+req' and 'apo+ofr'), and fewer multiple explicit confirmations (action 'mec'). However, it differs from the fully-learnt behaviour by constraining the actions available per state as shown in Figures 9 and10, where the semilearnt policy prohibited apologies in slots with medium or high confidence levels. See [START_REF] Cuayáhuitl | Hierarchical Reinforcement Learning for Spoken Dialogue Systems[END_REF] for a detailed quantitative comparison of dialogue strategies using simulated conversations.

Spoken dialogue system architecture

Our experiments were based on a travel planning spoken dialogue system supported hand-crafted or learnt dialogue behaviour. The latter uses dialogue strategies designed by hierarchical reinforcement learning agents on a simulated environment. This system is based on the Open Agent Architecture (OAA) [START_REF] Cheyer | The open agent architecture[END_REF]. Alternatively, other architectures can be used such as Galaxy-II [START_REF] Seneff | Galaxy-II: A reference architecture for conversational system development[END_REF]. Figure 11 shows a highlevel architecture using eight OAA-based agents in order to support speechbased task-oriented human-machine communication. The communication flows between facilitator (parent) and the other agents (children). Briefly, the user gives speech signals x u t corresponding to words w u t , concepts or slots c u t , and dialogue acts a u t . However, the machine understands them with distortions ( wu t , cu t , ãu t ), and answers back to the user with speech signals x m t corresponding to words w m t , slots c m t , and dialogue acts a m t . The user may also misunderstand the machine, and so on until one of the conversants terminates the conversation. The rest of this section describes each agent in the system.

Figure 11: Architecture of the CSTR travel planning spoken dialogue system supporting deterministic or learnt dialogue behaviour. Human-machine communication is carried out with speech signals x t , words w t , concepts or slots c t , and dialogue acts a t .

Facilitator agent

OAA is an agent-based framework to build autonomous, flexible, faulttolerant, distributed and reusable software systems [START_REF] Cheyer | The open agent architecture[END_REF]. OAA agents can be written in multiple programming languages and run on a computer network with different operating systems. They have a parent facilitator agent, which coordinates the communication of child agents by keeping a knowledge base of their services. Child agents are service providers and service requesters. Service providers let the facilitator know of their own capabilities, and service requesters request capabilities from other agents. They communicate by passing string messages between child agents and facilitator.

Speech recognition agent

The task of the speech recognition agent was to receive user speech signals after each machine prompt w m t and to generate a word sequence including confidence levels wu t , derived from the recognition hypothesis incorporating confidence scores wu t . This agent used the multithreaded ATK API, which is a layer on top of the HTK speech recognition libraries [START_REF] Young | The HTK Book[END_REF][START_REF] Young | ATK: An Application Toolkit for HTK[END_REF]. This agent used the acoustic models (trained with data from British speakers) generated from the TALK project3 , and customized-based language models with a lexicon of 263 words. The confidence levels were assigned by dividing the confidence score range [0...1] into three equal areas, equivalent to l =low, m =medium, and h =high confidence. The following table illustrates this process.

Semantic parsing agent

The semantic parsing agent generated concept or keyword sequences cu t from a (distortedly) recognised word sequence wu t . This agent used the Phoenix spontaneous speech parser [START_REF] Ward | Extracting information from spontaneous speech[END_REF] that maps a word string into a semantic frame. A semantic frame is a set of slots of information, each slot with an associated context-free grammar. Such grammars are compiled into recursive transition networks, which are matched with the given word sequence by a top-down chart parsing algorithm. This agent used 3 frames (corresponding to flights, hotels and cars) including 18 semantic networks. See the table below for a sample parsed word sequence.

Dialogue act recognition agent

This agent generated user dialogue acts ãu t using a two-stage approach. First, a user dialogue act type was selected taking into account the current concept sequence cu t and last machine dialogue act corresponding to the machine prompt w m t . Once a dialogue act type had been selected, it took context into account to become a user dialogue act ãu t . Although it is possible to generate more than one dialogue act per user utterance, this agent generated a single user dialogue act (see the table above for an example).

Database system agent

This agent returned database tuples based on SQL queries from the dialogue manager. It used a web scraper to populate a local database, retrieving travel data from a commercial web site (www.opodo.co.uk). This strategy was selected for avoiding long time responses from direct queries to the web.

Dialogue management agent

The dialogue management agent is the key component to evaluate. It generated machine dialogue acts a m t from the hierarchy of policies π i j based on three different types of dialogue behaviours: deterministic (described in section 2), fully-learnt and semi-learnt (described in section 3, more details in [START_REF] Cuayáhuitl | Hierarchical Reinforcement Learning for Spoken Dialogue Systems[END_REF]). Since these dialogue behaviours only differ in their action-selection mechanism, and the rest of the OAA-based agents (see Figure 11) did not change regardless of the behaviour of choice, it is fair to say that these behaviours were evaluated under similar conditions.

Language generation agent

The task of the language generation agent was to generate a machine prompt w m t in natural language based on a template-based approach. A prompt template has a word sequence embedding variables, and was selected given the current machine dialogue act a

Machine prompt

Welcome to the CSTR travel planning system. Tell me your flight information. ãu

Speech synthesis agent

The speech synthesis agent generated speech signals x m t from a given word sequence w m t . This agent is based on the Festival text-to-speech system 5 with an HTS voice generated from eight hours of recorded speech [START_REF] Yamagishi | Speaker-independent HMM-based speech synthesis system -HTS-2007 system for the Blizzard challenge[END_REF]. The speech signals were generated online, using a pre-processing stage to split word sequences at punctuation symbols in order to avoid long silences in the machine's utterance.

Spoken dialogue system evaluation

The aim of our experiments was to investigate if the learnt dialogue agents can outperform deterministic behaviour in a realistic environment. For such a purpose the spoken dialogue system described in the previous section was implemented and tested with a set of users, in laboratory conditions. Table 7 shows a sample dialogue.

Evaluation methodology

The CSTR travel planning spoken dialogue system was evaluated using a number of metrics, mostly derived from the PARADISE framework [START_REF] Walker | Towards developing general models of usability with PARADISE[END_REF], which has been widely accepted for evaluating the performance of spoken dialogue systems.

(i) Dialogue Efficiency: This group of quantitative metrics includes system turns, user turns, and elapsed time (in seconds). All of them report averages per dialogue goal (a conversation may have several dialogue goals). Elapsed time includes the time used by both conversants.

(ii) Dialogue Quality: These metrics consists of Word Error Rate (WER), Keyword Error Rate (KER), and Event Error Rate (EvER). The latter metric is useful because dialogue systems have to handle trade-offs among acceptance, confirmation and rejection events. The EvER metric is decomposed into the following metrics reported as percentages: correct acceptances, correct confirmations, correct rejections, false acceptances, false confirmations and false rejections. Other commonly reported metrics include percentages of commands and barge-in, but the CSTR system did not support them.

(iii) Task Success: This group of quantitative metrics includes task success and dialogue reward. Task success uses a binary approach, where each dialogue task is classified as successful if the user achieved the goal (e.g. booking a flight, hotel or car) as in (Bohus and Rudnicky, 2005).

Dialogue reward combines task success and dialogue length in terms of system turns as in (Lemon et al., 2006):

DialogueReward = 100 -|SystemTurns| for successful dialogue 0 -|SystemTurns| for failed dialogue (11)
(iv) User Satisfaction: These qualitative metrics include easy to understand, system understood, task easy, interaction pace, what to say, system response, expected behaviour, and future use. The sum of these metrics represents the overall user satisfaction score.

Experimental setup

Our experiments evaluated the three machine dialogue behaviours described in sections 2 and 3-deterministic ('D'), fully-learnt ('F'), and semilearnt ('S')-and were carried out with a user population of native speakers of English. Each user was presented with six dialogue tasks (travel bookings), with the system using each of the three behaviours twice, so that each user experienced all behaviours. The first three dialogues concerned single bookings and the last three dialogues concerned composite bookings. Table 5 shows examples of single and composite travel booking tasks. The six dialogues per user were collected using one of the following two sequences: DSFFSD and SDFFDS; i.e. half of the users interacted first with a deterministic behaviour, and the other half interacted first with a learnt behaviour. Whilst deterministic and semi-learnt behaviours started the dialogues interchangeably, fully-learnt behaviour always started the composite travel bookings. This sequence of dialogues was used because other alternative sequences such as {DSFFSD, DFSSFD, SDFFDS, SFDFDS, FSDDSF, FDSSDF} require larger data collections (the more data the more expensive and time-consuming). Each dialogue was logged using an extended version of the DATE dialogue annotation scheme [START_REF] Walker | DATE: A dialogue act tagging scheme for evaluation of spoken dialogue systems[END_REF]. These log files were used to compute quantitative results. In addition, at the end of each dialogue, participants were asked to fill in a questionnaire (Table 6) in order to compute qualitative results, evaluated with a 5-point Likert scale, where 5 represents the highest score.

The set of 32 users voluntarily agreed to participate in the experimental evaluation. They had an average age of 36 with a gender distribution of 22 male (69%) versus 10 female (31%). The participants' country of origin were as follows: 17 from the UK (53%), 12 from USA (38%), and 3 from Canada (9%). From this user population, 9 (28%) had no experience with spoken dialogue systems, 18 (56%) had some experience interacting with a spoken dialogue system at least once, and 5 (16%) were expert users. The latter were researchers in spoken dialogue processing (excluding the authors of this paper). What is the rental cost of the most expensive car?

Experimental results

This subsection describes an analysis of results obtained from automatic and manual transcriptions at the syntactic and semantic level. Table 8 summarises the results obtained using the three behaviours, using statistical significance tests to compare the semi-learnt behaviour against the deterministic and fully-learnt behaviours. For such a purpose data vectors (averaged per speaker) were verified through Lilliefors tests which indicated that they do not come from normal distributions. This suggests that non-parametric tests should be used. Thus, significance tests are reported with the Wilcoxon signed-rank test as suggested by [START_REF] Demsar | Statistical comparisons of classifiers over multiple data sets[END_REF].

Table 6: Subjective measures for qualitative evaluation of human-machine task-oriented spoken dialogues, adapted from [START_REF] Walker | Towards developing general models of usability with PARADISE[END_REF].

Measure

Question Easy to Understand Was the system easy to understand? System Understood Did the system understand what you said? Task Easy

Was it easy to find the flight/hotel/car you wanted? Interaction Pace

Was the pace of interaction with the system appropriate? What to Say Did you know what you could say at each point? System Response

Was the system fast and quick to reply to you? Expected Behaviour Did the system work the way you expected it to? Future Use Do you think you would use the system in the future?

Dialogue efficiency: The fully-learnt behaviour seems to outperform significantly the other behaviours by obtaining fewer system turns, fewer user turns and less time. The result is something of an artifact, since the fullylearnt policy could induce infinite loops in some dialogue states. In this case the dialogues were manually stopped after three repetitive actions (considered as evidence of an infinite loop), leading to shorter dialogues but a lower task success. The purpose of testing this dialogue policy was three-fold: (1) to evaluate how users perceive a dialogue policy with infinite loops; (2) to raise the issue of (in)coherent behaviour inferred by reinforcement learning agents, which has been ignored in previous related work; and (3) to compare its performance against a similar dialogue policy, but constrained with prior expert knowledge.

This phenomenon did not happen with deterministic or semi-learnt behaviours because their prior knowledge constrained more tightly the available actions per dialogue state. From these two dialogue strategies, it can be observed that semi-learnt behaviour outperformed deterministic, with significant differences in system and user turns. These results suggest that although learnt behaviours were optimized for dialogue efficiency, they cannot be evaluated in the same way. Therefore, a wider repertoire of evaluation metrics is preferable for a deeper analysis of dialogue behaviours.

Dialogue quality: Fully-learnt behaviour obtained the lowest word and keyword error rates. These results are not statistically significant, which suggests that behaviours were compared under similar recognition error rates. Deterministic and semi-learnt behaviours exhibited similar word and keyword Table 7: Fragment of a real dialogue in the CSTR travel planning spoken dialogue system using fully-learnt action-selection following policies π * i j . The dialogue states are formed by the state variables shown in Table 4.

Agent Policy State

Action Dialogue Act Utterance SYS π * 0 0 0,0,0,0,0,0 gre gre() Welcome to the CSTR travel planning system. 0,1,0,0,0,0 error rates, but different event error rates. Typically, spoken dialogue strategies have to handle trade-offs between acceptance, confirmation and rejection of recognition hypotheses, which can be classified as correct or incorrect. Ideally, dialogue behaviours should choose actions maximizing correct acceptance/confirmation/rejection events, whilst minimizing the incorrect ones.

M 1 0 π * 1 0 1,0,0 M 2 0 π * 2 0 0,0,0,0,0 M 3 0 π * 3 0 0,0,0,0,0,
From these results it can be inferred that semi-learnt behaviour handled such trade-offs better than deterministic behaviour by issuing more acceptances and fewer confirmations. This implies the use of more implicit confirmations and fewer explicit confirmations, which helps to explain why semilearnt behaviour was more efficient than the deterministic one. Although dialogue policies were not optimized for 'event error rate' (see equation 12, p 40), these results suggest that optimizing for dialogue efficiency produced an indirect optimization for such trade-offs. In addition, it can be observed that deterministic and semi-learnt behaviours are significantly different in all recognition events (correct/false acceptance/confirmation/rejection). In contrast, both learnt behaviours are significantly different in only half of the recognition events, suggesting that learnt behaviours act in a more similar way than deterministic behaviour.

Task success: Fully-learnt behaviour was significantly outperformed by the other behaviours that generated more successful conversations. This is where fully-learnt behaviour paid the price for generating some infinite dialogues that had to be artificially terminated before successful completion. In addition, whilst deterministic and semi-learnt behaviours were very similar in terms of task success, semi-learnt behaviour significantly outperformed its deterministic counterpart in terms of dialogue reward. This suggests that the dialogue reward metric is reflecting well the combined results from dialogue efficiency and dialogue accuracy.

User satisfaction: Users evaluated the semi-learnt behaviour as the best. Although, semi-learnt behaviour was significantly different to fully-learnt behaviour, it was not significantly different to its deterministic counterpart. A similar user satisfaction result was found by [START_REF] Singh | Optimizing dialogue management with reinforcement learning: Experiments with the NJFun system[END_REF] and Lemon et al. (2006). The performance of optimized confirmation strategies may be obscured by high recognition error rates. Future experiments could investigate optimized confirmation strategies under lower recognition error rates. In addition, the differences between learnt behaviours were statistically significant in the following qualitative metrics: system understood, task easy, expected behaviour, and future use. Similar differences were observed when comparing statistical significance between deterministic and fully learnt be-haviour. These results suggest that those are the metrics with more impact on perceived system performance in the presence of unexpected dialogue behaviour such as infinite loops.

These results can be summarized as follows. First, dialogues by deterministic and semi-learnt behaviour were significantly more successful than dialogues by fully-learnt behaviour. These unsuccessful dialogues were reflected in the efficiency metrics, where fully-learnt behaviour falsely seems to be most efficient. Second, deterministic and semi-learnt behaviours are equally successful but the latter is more efficient (at p ≤ 0.05 in system/user turns). Third, real users perceived fully-learnt behaviour as the worst (with statistical trend for deterministic vs fully-learnt, and significant at p ≤ 0.05 for fully-learnt vs semi-learnt). Finally, the problem of infinite loops could have been avoided (e.g. by backing off from learnt behaviour to a deterministic one in dialogue states with potential infinite loops); however, if a dialogue policy uses fully-learnt behaviour without a good reward function or without constraints to generate dialogues that make sense to humans, then it may not learn successful and coherent behaviours. According to the quantitative and qualitative results above, it can be concluded that semi-learnt behaviour was better than the other behaviours.

Analysis of results based on users with only successful dialogues

A further (and possibly more fair) comparison of spoken dialogue behaviours was based on users with only successful dialogues (9 users out of 32, where each user did six dialogue tasks)-shown in Table 9. It shows a summary of results comparing deterministic, fully-learnt and semi-learnt behaviour; including statistical significance. Firstly, it can be observed that both learnt behaviours were more efficient (in system/user turns, at p ≤ 0.05) than their deterministic counterpart, and the differences between learnt behaviours were not statistically significant. Secondly, no significant differences were observed in dialogue quality. However, the statistical trend in event error rate suggests that the semi-learnt behaviour handled the trade-offs of acceptance/confirmation/rejection events more effectively. Thirdly, it can be noted that both learnt behaviours obtained more reward than their deterministic counterpart, and that therefore this metric is reflecting the significant differences observed from efficiency metrics. Last, similar to the results for all dialogues, the semi-learnt behaviour obtained the highest score in user satisfaction, but the differences were not statistically significant.

These results lead us to conclude that semi-learnt dialogue behaviour is a better alternative than deterministic, and indicate that its performance is comparable to that of fully-learnt behaviour when they are evaluated on only successful dialogues.

Table 9: Results of the CSTR travel planning spoken dialogue system using data from users-with only successful dialogues. They are organized in the following groups of metrics: dialogue efficiency, dialogue quality, task success and user satisfaction.

Measure

Behaviour p-values Deter-Fully-Semi-

(1,2) (1,3) (2,3) ministic (1) Learnt (2) Learnt (3) Avg.

Do people want to talk to spoken dialogue systems?

At the end of each experimental session, participants were asked the following question: 'Would you use spoken dialogue systems for other tasks based on this experience?' Participants ranked their preference using a 5point Likert scale, where the higher the score, the better the satisfaction. We observed that only 12%(4) percent of participants were pessimistic in their future use, 56%(18) of participants preferred to stay neutral, and 31%(10) were optimistic in its future use. The scores in preference of future use per user type were 3.0 for novice users, 3.28 for experienced users, and 3.2 for expert users (see p. 32 for proportions of user types). To further analyze this, consider splitting the group of participants: the first group with dialogue reward smaller than 80 and the rest in the second group. There was a 2.8 score in preference of future use for the first group of participants against a 3.7 score for the second group. Based on this result (significant at p = 0.006) it can be inferred that the higher the dialogue reward the higher the preference for future use of dialogue systems.

Evaluation of simulated behaviours

The evaluation of simulated behaviours described in this section have three purposes: (1) to investigate the differences between real and simulated speech recognition, (2) to investigate if simulated user behaviour generates user responses that resemble human responses, and (3) to investigate if the hand-crafted dialogue strategy is a reasonable baseline to compare against other competing dialogue strategies.

Real versus simulated speech recognition

The real conversational environment used the ATK/HTK speech recognizer, and the simulated one used a simulated speech recognition error model (see section 2.2). Recognition results in terms of Keyword Error Rate (KER) for both environments were as follows: 20% in the simulated environment and 29% in the real one. For confidence scoring, the real environment showed confidence scores based on the probability density functions shown in Figure 12 (estimated from real data based on a normal density function), and the simulated environment generated uniformly distributed random confidence scores resulting in equal numbers of confidence levels. It can be observed that simulation used a more conservative KER and different distributions of confidence levels. This is because no training data was assumed, where the realistic probability distributions for recognition errors and confidence scoring were unknown.

Previous work in Automatic Speech Recognition (ASR) simulation has assumed that exponential probability distributions can model the behaviour of ASR confidence scorers [START_REF] Pietquin | A Framework for Unsupervised Learning of Dialogue Strategies[END_REF][START_REF] Williams | Partially observable Markov decision processes for spoken dialogue management[END_REF]. This research found that this assumption does not hold for the ASR system used here. Instead, the gamma probability distributions are suggested to simulate ASR confidence scores, which are more flexible and include the exponential distribution. Thus, learnt dialogue policies in a second stage can be retrained with more realistic ASR behaviour in order to generate potentially even better policies. Nevertheless, it was found that even conservative ASR error modelling was sufficient to find better policies than deterministic behaviour.

Real versus simulated user behaviour

Simulated user behaviour was compared against real user behaviour and against random user behaviour (see section 2 for details on dialogue simulation). Because there is a variety of proposals on how to evaluate user simulations, we proposed two metrics to evaluate user behaviour based on dialogue similarity (using the Kulback-Leibler divergence) and dialogue coherence (using coherence error rate), and also validated their results with the more established Precision-Recall metric based on the F-Measure score (Schatzmann et al., 2005). These metrics were applied as described in appendix A. The objectives of this evaluation were: (a) to observe if the simulated user model used to learn the dialogue strategies was a reasonable thing to use, and (b) to validate that dialogue realism could be distinguished by the proposed metrics (KL-divergence and CER).

This evaluation used three sets of user responses: (1) real user responses were extracted from annotated data from the realistic environment, consisting in 192 dialogues including 4623 user utterances; (2) simulated coherent responses using algorithm 1 described in section 2; and (3) simulated random responses using the same algorithm, but with a random choice of user dialogue acts (at line 12) and with a random sequence of slots. All user responses (real, simulated coherent or simulated random) were derived from machine dialogue acts in the real logged data, which enabled a fairer comparison. In addition, the user responses were not distorted because they were compared before speech recognition occurred.

Table 10 shows an evaluation of simulated user behaviour using Precision-Recall and KL-divergence. It can be seen that both metrics agreed in the ranking of dialogue realism, including the proposed KL-divergence metric. These results show that simulated coherent behaviour is more similar to real user behaviour than simulated random behaviour. It can be observed that the Precision-Recall of simulated coherent behaviour obtained higher scores than those reported before (Schatzmann et al., 2005;[START_REF] Georgila | User simulation for spoken dialogue systems: Learning and evaluation[END_REF], approaching the upper-bound scores from real user behaviour. Notes: (1) The less strict F-Measure score considers a user response as a sequence of actions, and the more strict score considers a user response as a single action, (2) the real dialogues were divided into two subsets ('Real1' and 'Real2') to provide an upper-bound score, (3) KL-divergence used Witten-Bell discounting to smooth the probability distributions.

In addition, the results in terms of Coherence Error Rate (CER) for real, simulated and random responses were 8.23%, 2.99%, 30.10%, respectively. It can be observed that simulated coherent behaviour behaved very optimistically, that is not very different from real user behaviour, and it is significantly different from the coherence of random behaviour. This metric is interesting because it evaluates a different perspective from the existing metrics, it may be used as a complementary evaluation.

Evaluating the baseline of machine dialogue behaviour

The use of speech recognition confidence scores forces spoken dialogue strategies to handle tradeoffs among acceptance, confirmation and rejection events e i , which can be classified as correct E c = {ca, cc, cr} or incorrect E f = {f a, f c, f r}. Table 11 shows the categories of recognition events. A reasonable dialogue strategy would choose actions maximizing correct acceptance/confirmation/rejection events, whilst minimizing the incorrect ones. A simple metric to quantify these events is referred to as an Event Error Rate (EvER):

EvER = count(e i ∈ E f ) count(e j ∈ {E c , E f }) × 100. ( 12
)
Table 11: Speech recognition events in spoken dialogue systems.

Recognition Event Correct False (or incorrect) Acceptance ca f a Confirmation cc f c Rejection cr f r
For such a purpose, consider that speech recognition hypotheses fall within three equally distributed regions of confidence scores (assuming no training data): low confidence, medium confidence, and high confidence. In addition, consider the confirmation strategies Π of Table 12 for the three confidence regions. Which confirmation strategy is a better baseline of machine behaviour? For perfect speech recognizers it has to be 'Strategy1', because it leads to more efficient conversations in terms of number of system turns; but this is unrealistic. Thus, a more reasonable choice of dialogue strategy is the one obtaining the lowest EvER score, and can be expressed as Baseline Strategy = arg min This metric was used to evaluate-with real data-the deterministic (handcrafted) machine dialogue behaviour of the system, in order to to find a reasonable baseline of machine dialogue behaviour. From the data collected by the system, we used all keywords (with automatic and manual transcriptions) including their corresponding speech recognition confidence scores, and computed the EvER for such confirmation strategies (Table 13). It can be seen that the deterministic behaviour of choice in this research (Strategy3) indeed obtained the lowest EvER, together with 'Strategy4'. Although they obtained the same result, the former is more attractive, due to its use of implicit confirmations because it leads towards more efficient conversations. Therefore, it can be concluded that the learnt dialogue strategies were compared against a reasonable baseline of deterministic machine dialogue behaviour. [START_REF] Walker | Informational Redundancy and Resource Bounds in Dialogue[END_REF][START_REF] Walker | The effect of resource limits and task complexity on collaborative planning in dialogue[END_REF] developed the notion of a simulation environment to test dialogue strategies and [START_REF] Walker | Informational Redundancy and Resource Bounds in Dialogue[END_REF] and [START_REF] Biermann | The composition of messages in speechgraphics interactive systems[END_REF] proposed the notion of automatically optimizing a dialogue strategy. Reinforcement learning approaches based on the Markov Decision Process (MDP) model were first applied to dialogue strategy learning by [START_REF] Levin | A stochastic model of computerhuman interaction for learning dialog strategies[END_REF] in a simulation-based approach and by [START_REF] Walker | Learning optimal dialogue strategies: a case study of a spoken dialogue agent for email[END_REF] in a corpusbased approach. Since then there have been several developments in the field [START_REF] Levin | A stochastic model of human machine interaction for learning dialog strategies[END_REF][START_REF] Walker | An application of reinforcement learning to dialogue strategy selection in a spoken dialogue system for email[END_REF][START_REF] Young | Probabilistic methods in spoken dialogue systems[END_REF][START_REF] Singh | Optimizing dialogue management with reinforcement learning: Experiments with the NJFun system[END_REF][START_REF] Scheffler | Automatic Design of Spoken Dialogue Systems[END_REF][START_REF] Pietquin | A Framework for Unsupervised Learning of Dialogue Strategies[END_REF][START_REF] Williams | Partially observable Markov decision processes for spoken dialogue management[END_REF][START_REF] Young | The hidden information state approach to dialogue management[END_REF][START_REF] Frampton | Using Dialogue Acts in Dialogue Strategy Learning: Optimizing Repair Strategies[END_REF], largely adopting flat tabular reinforcement learning approaches. The scalability of such approaches is limited because of the curse of dimensionality: the exponential growth of the search space according to the number of state variables taken into account. Even a system with a simple state representations may have a large search space which can quickly become intractable. This problem has led to the use of function approximation [START_REF] Denecke | Fast reinforcement learning of dialogue policies using stable function approximation[END_REF][START_REF] Henderson | Hybrid reinforcement/supervised learning of dialogue policies from from fixed data sets[END_REF] in order to find solutions on reduced stateaction spaces. These investigations have been applied to small-scale dialogue systems aiming for a single global solution. However, less attention has been paid to finding solutions using a divide-and-conquer approach: hierarchical POMDPs with a bottom-up approach have been applied to small state-action spaces [START_REF] Pineau | Tractable Planning Under Uncertainty: Exploiting Structure[END_REF], and hierarchical reactive planning and learning has been used for dialogue systems with few slots of information (Lemon et al., 2006;Rieser and Lemon, 2008). Our spoken dialogue system in the travel planning domain was implemented with five dialogue goals and 26 slots of information. This is the largest scale spoken dialogue system so far (in terms of dialogue goals and slots) tested using the reinforcement learning paradigm.

π i ∈Π EvER(π i ). ( 13
)
Our approach for incorporating prior expert knowledge into reinforcement learning agents is based on the Hierarchical Abstract Machines (HAMs) of [START_REF] Parr | Reinforcement learning with hierarchies of machines[END_REF]. In this approach the system designer specifies a partial program (HAM) and leaves the unspecified part to the hierarchical reinforcement learning agent. This is an important extension to the fullylearnt approach by constraining each hierarchical SMDP with some prior expert knowledge, in order to combine dialogue behaviour specified by human designers with behaviour automatically inferred by reinforcement learning agents. [START_REF] Litman | Automatic optimization of dialogue management[END_REF], [START_REF] Walker | An application of reinforcement learning to dialogue strategy selection in a spoken dialogue system for email[END_REF], and [START_REF] Singh | Optimizing dialogue management with reinforcement learning: Experiments with the NJFun system[END_REF] incorporated prior knowledge into MDP-based spoken dialogue systems (NJFun, ELVIS) by means of hand-crafted rules used to compress the state-action space. This approach allowed them to perform very efficient dialogue strategy learning. However, NJFun and ELVIS do not provide a formal framework to incorporate prior knowledge and apply flat dialogue optimization. This is in contrast to our approach which is based on deterministic-stochastic finite state machines and adopts a hierarchical structure for optimization. [START_REF] Heeman | Combining reinforcement learning with information-state update rules[END_REF] proposed combining the information-state update approach with reinforcement learning agents. In this approach the informationstate (dialogue state) is hand-crafted by update rules based on preconditions and effects. A subset of preconditions that are easy to specify are handcrafted, and those less easy to specify are left to the reinforcement learning agent. Again this uses flat reinforcement learning. [START_REF] Williams | The best of both worlds: Unifying conventional dialog systems and POMDPs[END_REF] proposed executing a POMDP and a hand-crafted dia-logue controller in parallel. At each time step, the hand-crafted controller is in state s (e.g. semantic frame) and the POMDP is in belief state b (probability distribution over POMDP states), the hand-crafted controller nominates a subset of actions, and the POMDP updates a value function only for that particular subset of actions. Thus, a POMDP solution is found on a more compact space of policies. Our approach and Williams' approach share the idea of executing a partial program in parallel with an optimized decisionmaking model, but we use a decomposed MDP and optimize a hierarchy of partial programs, which is more scalable and suitable for reusability.

Evaluation of simulated user behaviour

Researchers in spoken dialogue tend to agree that realistic simulated user behaviour must exhibit 'human-like behaviour' [START_REF] Georgila | User simulation for spoken dialogue systems: Learning and evaluation[END_REF]. Schatzmann et al. (2005) found that the quality of the learnt dialogue strategies is strongly dependent on the simulated user model, where good (realistic) user models help to find better policies than poor user models. [START_REF] Ai | Assessing Dialog System User Simulation Evaluation Measures Using Human Judges[END_REF] evaluated real and simulated dialogues using human judges and found that no strong agreement can be reached by humans on the quality of the dialogues, but humans consistently rank models of simulated user behaviour.

Previous work has proposed several evaluation metrics for assessing the realism of user simulations and can be grouped into two broad approaches: dialogue similarity and system performance. The former approach assumes that given a set of metrics, a set of simulated dialogues, and a set of real dialogues, the realism of simulated dialogues increases as their scores approach those obtained by real ones. Most previously proposed evaluation metrics fall within this approach [START_REF] Eckert | User modeling for spoken dialogue system evaluation[END_REF][START_REF] Scheffler | Automatic Design of Spoken Dialogue Systems[END_REF]Young, 2000, 2002;Schatzmann et al., 2005;[START_REF] Filisko | Developing Attribute Acquisition Strategies in Spoken Dialogue Systems Via User Simulation[END_REF]Georgila et al., 2005;[START_REF] Cuayáhuitl | Humancomputer dialogue simulation using hidden Markov models[END_REF][START_REF] Rieser | Cluster-based user simulations for learning dialogue strategies[END_REF][START_REF] Ai | Knowledge consistent user simulations for dialogue systems[END_REF]. This approach is useful for giving a rough indication of the similarity between simulated and real dialogues, but it penalizes unseen behaviour (even when it may be realistic). The latter approach ranks simulated user models in terms of their prediction of the performance of a dialogue system. This is motivated by the fact that simulated user models should improve machine dialogue behaviours rather than generating human-like conversations [START_REF] Williams | A method for evaluating and comparing user simulations: The Cramer-Von Misses divergence[END_REF]. Both approaches are limited by the fact that they require real dialogue data, which may not exist at early stages of system development, and that they cannot distinguish if a given sequence of machine-user dialogue acts is realistic or not.

Our proposed KL-divergence metric complements the previous dialogue similarity metrics by comparing probability distributions of user dialogue acts, and showed agreement with the Precision-Recall metric. In contrast with previously proposed metrics, our proposed coherence error rate metric can distinguish if a given sequence of machine-user dialogue acts is realistic or not. Because this latter metric uses hand-crafted coherence rules, a potential future work is to induce such rules automatically from data.

Conclusions and future work

In this paper we have developed a hierarchical reinforcement learning spoken dialogue system, based on an SMDP, and evaluated it with real users in a laboratory setting. Both fully-learnt and semi-learnt machine dialogue behaviours were used and compared with a baseline hand-crafted dialogue strategy. To the best of our knowledge, this is the first evaluation of SMDPbased reinforcement learning dialogue agents in a realistic environment.

Semi-learnt behaviour was quantitatively better than the other dialogue behaviours. It achieved similar task success to deterministic behaviour (95%) and more efficient conversations by using 9% fewer system turns, 12% fewer user turns, and 7% less time (at p < 0.05). It also outperformed fully-learnt behaviour by 35% in terms of higher task success (at p < 0.05); an evaluation based on users with only successful dialogues did not report significant differences. However, although fully-learnt behaviour resulted in inferior overall performance, it cannot be discarded as a better alternative to hand-crafted behaviour. But it is less flexible and less coherent than semi-learnt behaviour because it does not include a mechanism to guarantee coherent actions, which is essential for successful dialogues. On the other hand, while users did perceive significant qualitative differences between fully-learnt behaviour and the semi-learn behaviour and statistical trend between fully-learnt and deterministic, users did not observe significant differences between deterministic and semi-learnt behaviours. Our key findings may be summarized as follows:

1. hierarchical semi-learnt dialogue agents are a better alternative (with higher overall performance) than deterministic or fully-learnt behaviour;

3. the evaluation metrics Precision-Recall and KL-divergence agreed in the ranking of dialogue realism;

4. real users act with highly coherent behaviour at the dialogue act level (real users behaved coherently 92% of the time according to the metric 'coherence error rate'); 5. hierarchical reinforcement learning dialogue agents are feasible and promising for the (semi)automatic design of optimized behaviours in larger-scale spoken dialogue systems.

We suggest the following research avenues for endowing conversational agents with optimized, adaptive, robust, scalable and effective spoken dialogue behaviours.

First, one of the most important limitations of this work was the lack of a robust approach for updating slot values. Due to the fact that speech recognition hypotheses may include errors, it is not trivial to know when to update the recognized slot values and when to reject them. The effect of non-robust keyword updating is that the system eventually gives the impression of forgetting what has been said before. This highlights the importance of effective and efficient mechanisms for dialogue history tracking. Future research can incorporate beliefs into the knowledge rich-states of the proposed framework with ideas from approaches such as regression methods (Bohus and Rudnicky, 2005), POMDPs [START_REF] Williams | Partially observable Markov decision processes for spoken dialogue management[END_REF], or Bayesian updates [START_REF] Thomson | Bayesian update of dialogue state for robust dialogue systems[END_REF].

Second, we focused on optimizing confirmation strategies to keep their assessment simple rather than evaluating multiple dimensions. But there is a wide range of optimized behaviours that can be incorporated into this kind of system. For example: learning initiative strategies, learning to give help, learning to ground, learning to present information, learning to clarify, learning to negotiate, learning to recover from errors, learning multimodal strategies, and learning to collaborate. The thorough integration of all these behaviours into a single framework remains to be investigated.

Third, our optimization approaches include support for tabular hierarchical reinforcement learning. However, if a given subtask is intractable (i.e. the state-action space becomes too large and indecomposable) then alternative methods should be adopted to make such subtasks feasible. One of the most promising approaches reported in the literature of reinforcement learning is that of function approximation. The optimization approaches employed in this paper could be combined with function approximators such as neural networks or linear function approximation [START_REF] Henderson | Hybrid reinforcement/supervised learning of dialogue policies from from fixed data sets[END_REF].

Fourth, the current practice of reinforcement learning for spoken dialogue uses a single reward function. Although the proposed approaches in this paper allowed the use of a different reward function per subtask, the experimental setting used the same performance function across the entire hierarchy. Intuitively, hierarchical dialogue optimizations may require different types of reward function at different levels of granularity. Moreover, as the dialogue complexity increases, it becomes more difficult to specify such performance functions. It remains to be investigated how to specify or infer such hierarchical reward functions since the learnt behaviour strongly depends on the reward function [START_REF] Walker | Informational Redundancy and Resource Bounds in Dialogue[END_REF][START_REF] Walker | An application of reinforcement learning to dialogue strategy selection in a spoken dialogue system for email[END_REF]Rieser and Lemon, 2008).

In the proposed approaches the system designer has manually to remove irrelevant state variables and actions for each subtask. Although this is useful because it allows the system designer to specify what to remove, it may become problematic if relevant information is removed, leading to unsafe state abstraction. Therefore, it would be useful to have a method for performing state abstraction of dialogue information in a safer way (Dietterich, 2000).

Finally, the simulated conversational environment that we used did not model errors as in a real environment, which was expected due to the lack of training data. Nonetheless, the experimental results provided evidence to conclude that this heuristic-based dialogue simulation approach was useful to learn dialogue strategies with superior performance compared with a reasonable baseline of deterministic behaviour. This result is relevant for spoken dialogue systems in new domains, where annotated dialogue data is not available. Our simulated environment could be enhanced with probability distributions estimated from real annotated data as in Schatzmann et al. (2007). However, due to the fact that collecting training data is costly and time consuming, a potential future work is to investigate methods to generalize simulated behaviours for dialogue systems across different domains.

A. Evaluation metrics for user behaviour

The evaluation of real and simulated user behaviour was carried out with three evaluation metrics from two different perspectives. The first perspective evaluates 'dialogue similarity', where precision-recall quantifies the predicted user responses from a user simulation model (strongly penalizes unseen responses (Schatzmann et al., 2005)), and probabilistic dialogue similarity complements the previous metric by comparing probability distributions of user dialogue acts based on the Kulback-Leibler divergence [START_REF] Cuayáhuitl | Humancomputer dialogue simulation using hidden Markov models[END_REF]. The second perspective evaluates 'dialogue coherence', where coherence error rate ignores the seen or unseen user responses, instead, it classifies them into coherent or incoherent responses.

To illustrate the evaluation metrics consider the sub-dialogues below with common system responses assumed from logged real data, but user responses may be real (as in Table 14) or simulated (as in Tables 15 and16). The acronyms of dialogue act types are described in Table 1.

Agent Dialogue Act

Wording SYS gre(), Welcome to the travel planning system. req(dep city)

Tell me your flight information. USR pro(dep city=amsterdam, I would like a return flight leaving from flight type=return) Amsterdam.

SYS sic(flight type=return),

A return flight, where are you leaving from? req(dep city) USR pro(dep city=amsterdam) Amsterdam

A.1. Precision-Recall

This measure is commonly used in the information retrieval field, and was suggested by (Schatzmann et al., 2005)

These scores are interpreted as the higher the more realistic the user responses. An average score of recall (R) and precision (P) called F-measure is defined by

F = 2P R (P + R) . (16)
If we want to compute the F-measure score in dialogue data, the slot values can be ignored to reduce data sparsity while preserving the conveyed information. (Schatzmann et al., 2005) suggested to compute precision-recall by considering a user dialogue act as a sequence of actions, e.g. the dialogue act 'pro(dep city,flight type)' is equivalent to {pro(dep city), pro(flight type)}. Considering the given sample sub-dialogues, the F-measure score for real vs simulated coherent responses is F = 0.75, and the score for real vs simulated random responses is F = 0. Alternatively, the scores can be computed in a more strict way by considering each user response as a single user action instead of multiple ones. Precision-recall can be recomputed as follows: the scores for real vs simulated coherent responses are F = 0.5; and the score for real vs simulated random responses is F = 0.

A.2. Probabilistic Dialogue Similarity

The purpose of this measure is to evaluate the probabilistic similarity between two sets of dialogues. The similarity between real and simulated dialogues has been analyzed using the Kulback-Leibler divergence [START_REF] Cuayáhuitl | Humancomputer dialogue simulation using hidden Markov models[END_REF], and here we propose to apply it in a simpler way. First, compute two smoothed probability distributions of machine-user dialogue acts, without slot values for reduced combinations: P for one data set and Q for the other. For example: P represents a distribution of the set of real dialogues and Q a distribution of the set of simulated ones. Then compute the symmetric distance according to

D(P, Q) = D KL (P Q) + D KL (Q P ) 2 , (17)
where D KL is the Kulback-Leibler divergence (distance) between P and Q:

D KL (P Q) = i p i log 2 ( p i q i ). ( 18
)
Tables 17 and 18 use the sample sub-dialogues of this subsection in order to show the divergence between real and simulated coherent user responses, and between real and simulated random user responses. The probability distributions of occurrence P and Q were smoothed by assigning a probability mass of 0.1 to unseen events, and the method of preference can be used to address the issue of data sparsity. It can be observed that the symmetric divergence between real and simulated random user responses (2.536) is greater than between real and simulated coherent ones (0.759). This reflects the intuitive perception that the more realistic the user responses, the shorter the divergence.

It can be observed that this metric gives the same ordering on user simulations than the precision-recall metric. A validation of this ordering based on a corpus of real human-machine dialogues is reported on section 6. CER) is proposed due to the fact that most previously used metrics penalize unseen user responses even when they may be realistic. The key assumption in this metric is that given a user knowledge-base k u t and a set of dialogue coherence rules encoded into a function, we can evaluate-in an approximated form-whether a user action a u t is coherent or not. This metric rates errors (in this context, incoherent dialogue acts) from a set of observed events (user dialogue acts in the data), in terms of dialogue act types (see

) 20
Equation 20 is suited for simple slot-filling applications, but for more complex dialogues more rules have to be added. This metric takes into account user dialogue acts and decomposes them into dialogue acts with a single slot and without slot value, e.g. pro(des city). This procedure incorporates the conveyed information, and assumes that the slot values are always consistent given a user goal at the beginning of the conversation. In addition, this evaluation metric considers user responses with silences or incomplete dialogue acts as incoherent, the explanation for this consideration is because whatever the user said (e.g. mumbles or out-of-vocabulary words), it was not possible to extract a user dialogue act contributing to the conversation.

Given the sample sub-dialogues of this subsection, Table 19 shows the results of coherence for real, simulated coherent and simulated random user responses: 0%, 0%, 50%, respectively. Note that although simulated coherent user responses do not match the real ones, they are not being penalized because they are responses that make sense according to the dialogue history.

Figure 1 :

 1 Figure 1: A pipeline architecture of speech-based human-machine communication, where dialogue state s mt is used by the dialogue manager to choose action a m t . Modelling the dialogue strategy at the semantic level allows us to omit the speech signal and word levels.

Figure 2 :

 2 Figure2: A dialogue of length T described in terms of a state sequence s t , with state transitions induced by actions a t .

Figure 5 :

 5 Figure 5: Dialogue state for the flight booking spoken dialogue strategy. Each variable X i with domain values D 0 has five possible values, variable X 7 has six possible values, and variable X 8 has 3 possible values, resulting in 5 6 × 6 × 3 = 281250 states.

Figure 7 :

 7 Figure7: Architecture of the agent-environment interaction using multiple SMDPs M i j , circles represent states, squares represent actions, and diamonds represent rewards.

Figure 8 :

 8 Figure 8: A hierarchy of induced subtasks for the travel planning system. The abstract machines H k l are specified in Figures 9 and 10, and the state variables for each dialogue subtask M i j are specified in Table4.

  Machine prompt Welcome to the CSTR travel planning system.Tell me your flight information. w u t User response I would like a single flight from Edinburgh to Paris. wu t ASR hypothesis how(0.27) about(0.31) a(0.15) single(0.60) with confidence flight(0.56) with(0.32) b. m. i.(0.47) from(0.70) scores edinburgh(0.59) to(0.40) paris(0.56) wu t ASR hypothesis how(l) about(l) a(l) single(m) flight(m) with(l) w/conf. levels b. m. i.(m) from(h) edinburgh(m) to(m) paris(m) w m t+1 Machine prompt A single flight from Edinburgh to Paris. travelling with BMI. When do you want to travel? w u t+1 User response I would like to travel with Air France. ...

  to the CSTR travel planning system. Tell me your flight information. w u t User response I would like a single flight from Edinburgh to Paris. wu t ASR hypothesis how about a single flight with b. m. i. from wo/conf. scores edinburgh to paris cu single flight from Edinburgh to Paris travelling with BMI. When do you want to travel? w u t+1 User response I would like to travel with Air France. ...

  Prompt for action 'mic' A $FlightType flight from $DepCity to $DesCity travelling with $Airline. Prompt for action 'req' When do you want to travel? w m t+1 Machine prompt A single flight from Edinburgh to Paris travelling with BMI. When do you want to travel? w u t+1 User response I would like to travel with Air France. ...

  a single flight from London to Paris leaving on December 6th in the afternoon, and travelling with any airline. What is the cost of the most expensive flight? Composite (a) Try to book a return flight from Edinburgh to Amsterdam leaving on January 22nd in the morning, and returning on the 1st of February in the evening. What is the cost of the cheapest flight with British Airways? (b) Try to book a cheap hotel in downtown with any hotel brand . What is the cost of the cheapest hotel in downtown? (c) Try to rent a compact car near the airport for three days on January 22nd with pick-up time at 7PM. You don't have preference in rental company.

Figure 12 :

 12 Figure12: Probability density functions estimated from observed speech recognition confidence scores of keywords in data collected by the CSTR travel planning system.

  to evaluate how well a user simulation model can predict real user dialogue behaviour. Precision specifies the fraction of correctly predicted real user responses from all simulated responses. Recall specifies the fraction of correctly predicted real user responses from all real responses. They are expressed as Precision = Number of correctly predicted user responses Total number of simulated user responses ,(14)

Dialogue

  Act Pairs (SYS:USR) P Q D KL (P ||Q) D KL (Q||P ) gre(),req(dep city):pro(dep city,flight type) 0

  req(dep city):pro(dep city) 0 gre(),req(dep city):pro(flight type) 0 sic(flight type),req(dep city):pro(dep city) 0 Simulated gre(),req(dep city):pro(dep city) 0 gre(),req(dep city):pro(dep time) 0 gre(),req(dep city):pro(airline) 0 coherent gre(),req(dep city):pro(flight type) 0 sic(flight type),req(dep city):pro(dep city) 0 Simulated gre(),req(dep city):con(dest city) 1 random sic(flight type),req(dep city):pro(des city) 0

  Algorithm 1 Simulator of Task-Oriented Human-Machine Conversations 1: function HumanMachineDialogueSimulator( )

	2: 3:	k m 0 ← initialize machine knowledge-rich state k u 0 ← initialize user knowledge-rich state
	4:
	9: 10:	ãm t ← get distorted dialogue act from δ(a m t , k m t ) Update k m t with a m t and update k u t with ãm

t ← initialize time-step to 0 5: repeat 6: s m t ← observe machine dialogue state from k m t 7: a m t ← choose machine dialogue act type following π m (s m t ) 8: Generate machine dialogue act ≡ dialogue act type a m t in context t 11: s u t ← observe user dialogue state from k u t 12: a u t ← choose user dialogue act type following π u (s u t ) 13: Generate user dialogue act ≡ dialogue act type a u t in context 14: ãu t ← get distorted dialogue act from δ(a u t , k u t ) 15: Update k u t with a u and update k m with ãu t 16: t ← t + 1 17:

Table 1 :

 1 Dialogue Act Types (DATs) for task-oriented human-machine spoken dialogues. Abbreviations: IC=Implicit Confirmation, EC=Explicit Confirmation.

	Agent	ID DAT	Sample Utterance
		pro provide	I want a flight from Edinburgh to London.
	User	rep reprovide con confirm	I said a flight to London from Edinburgh. Yes, please.
		sil silence	[remain in silence]
		req request	And, what is your destination city?
		apo apology	I am sorry, I didn't understand that.
		sic single IC	A flight to London.
		mic multiple IC	A flight from Edinburgh to London.
		sec single EC	I think you said London, is that correct?
		mec multiple EC	I heard from Paris to London, is that right?
		acc accept slot	[move to next ascending slot with lowest value]
	Machine	dbq db query of r offer	[performs a database query] Would you like A, B or C?
		sta status	Please wait while I query the database.
		pre present	The cost of this flight is 120 pounds.
		rel relax	Try again with some different information.
		ack acknowledgement All right, this flight has been booked.
		ope opening	Welcome to the travel planning system.
		clo closing	Thank you for calling, good bye.

  time step req if unknown slot in focus sic + req if unknown slot in focus and Single Slot to Confirm (SSC) mic + req if unknown slot in focus and Multiple Slots to Confirm (MSC) apo + req if slot in focus with low confidence level sec if slot in focus with medium confidence level and SSC mec if slot in focus with medium confidence level and MSC acc if slot in focus with high confidence level dbq + sta if null database result and confirmed non-terminal slots pre + of r if database result with few uninformed tuples

	apo + of r if terminal slot with low confidence level
	of r	if unconfirmed terminal slot and db tuples presented before
	ack	if unacknowledged dialogue goal and confirmed terminal slot
	rel	if empty database result and confirmed non-terminal slots
	clo	otherwise.

Table 2 :

 2 Sample human-machine dialogue in the flight booking domain, where the dialogue state is formed by the state variables shown in Figure5, and a set of actions is available per state. At this point action-selection is arbitrary (before learning).

Table 3 :

 3 Sample

	dialogue in the flight booking system. Although simulations are only based
	on dialogue acts, an equivalent wording is given for a better understanding. This dialogue
	shows a sample speech recognition error after the first user utterance.
	Agent Dialogue Act	Wording
	SYS req(dep city)	Tell me your flight information.
	USR pro(dep city=edinburgh,	I would like a flight from Edinburgh to Paris.
	des city=paris)
	ASR	[I would like a flight from Edinburgh to Rome]
	SYS mic(dep city=edinburgh,	OK, a flight from Edinburgh to Rome,
	des city=rome)+req(date) when do you want to travel?
	USR rep(des city=paris)	I said 'to Paris.'
	SYS sic(des city=paris)	OK, a flight to Paris,
	+req(date)	when do you want to fly?
	USR pro(date=01dec,	December first, flying with British Airways.
	airline=british airways)
	SYS apo(date)+req(date)	I'm sorry, when do you want to travel?
	USR pro(date=01dec)	On the first of December.
	SYS mic(date=01dec, airline=	Travelling on the first of December with
	british airways)+req(time) British Airways, at what time do you prefer
		your flight?
	USR pro(time=morning)	In the morning.
	SYS apo(time)+req(time)	Sorry, at what time do you prefer your flight?
	USR rep(time=morning)	In the morning.
	SYS sec(time=morning)	Did you say in the morning?
	USR con(time=yes)	Yes please.
	SYS dbq(db query)+sta(db)	Please wait while I retrieve information ...
	USR
	SYS pre(db result)+ofr(flight)	All right, flights from Edinburgh to Paris on
		the first of December in the morning travelling
		with British Airways: [present information]
		Would you like choice 1, choice 2 or choice 3?
	USR pro(flight=choice2)

  m t , dialogue state s m t or joint state w m t , and a simple help mechanism 4 . Once a prompt template had been selected, it took context into account by replacing variables with values in the machine's knowledge base in order to generate the word sequence w m t+1 . This agent included 463 prompt templates. The next table shows a sample prompt template c m t and its corresponding machine prompt w m t+1 .

	ID Event	Outcome
	w m t

Table 5 :

 5 Sample travel booking tasks.

Table 8 :

 8 Results of the CSTR travel planning spoken dialogue system comparing three different dialogue behaviours, organized according to the following groups of metrics: dialogue efficiency, dialogue quality, task success and user satisfaction.

	Measure		Behaviour			p-values
		Deter-	Fully-	Semi-	(1,2)	(1,3)	(2,3)
		ministic (1) Learnt (2) Learnt (3)
	Avg. System Turns	16.63	12.24	15.09	≤ .05 ≤ .05 ≤ .05
	Avg. User Turns	14.38	9.69	12.63	≤ .05 ≤ .05 ≤ .05
	Avg. Time (secs)	177.23	139.59	165.11	≤ .05
	Word Error Rate	0.429	0.410	0.428
	Keyword Error Rate	0.300	0.278	0.301
	Event Error Rate	0.409	0.351	0.372
	Correct Acceptance	5.51	26.34	20.95	≤ .05 ≤ .05
	Correct Confirmation	48.51	36.17	39.86	≤ .05 ≤ .05 ≤ .05
	Correct Rejection	5.18	2.37	1.92	≤ .05 ≤ .05
	False Acceptance	3.25	12.27	9.30	≤ .05 ≤ .05 ≤ .05
	False Confirmation	32.64	20.11	26.60	≤ .05 ≤ .05 ≤ .1
	False Rejection	4.91	2.55	1.36	≤ .05 ≤ .05
	Avg. Task Success	0.94	0.62	0.95	≤ .05		≤ .05
	Avg. Dialogue Reward	79.46	54.68	82.56	≤ .05 ≤ .05 ≤ .05
	Easy to Understand	4.34	4.31	4.44
	System Understood	3.09	2.72	3.28	≤ .05		≤ .05
	Task Easy	3.50	3.00	3.45	≤ .1		≤ .05
	Interaction Pace	3.52	3.55	3.50
	What to Say	3.45	3.47	3.58
	System Response	3.67	3.64	3.63
	Expected Behaviour	3.42	3.08	3.52	≤ .05		≤ .05
	Future Use	3.14	2.83	3.28	≤ .05		≤ .05
	User Satisfaction	28.14	26.59	28.67	≤ .1		≤ .05

Table 10 :

 10 Evaluation of real and simulated user behaviour with Precision-Recall in terms of F-Measure (the higher the better) and KL-divergence (the lower the better).

	Compared Dialogues	F-Measure less strict more strict	KL-divergence
	Real1 vs Real2	0.915	0.749	1.386
	Real vs Simulated Coherent	0.708	0.612	4.281
	Real vs Simulated Random	0.633	0.360	5.025
	Simulated Coherent vs Simulated Random	0.417	0.247	6.532

Table 12 :

 12 Confirmation strategies for different recognition confidence score regions. Notation: IC=implicit confirmations, EC=explicit confirmations, and AP=apologies.

	Strategy Low Confidence Medium Confidence High Confidence
	Strategy1	IC	IC	IC
	Strategy2	EC	IC	IC
	Strategy3	AP	EC	IC
	Strategy4	AP	EC	EC
	Strategy5	EC	EC	EC

Table 13 :

 13 Event Error Rate (EvER) results of real dialogues for confirmation strategies of Table12. Abbreviations: ca=correct acceptance, cc=correct confirmation, cr=correct rejection, fa=false acceptance, fc=false confirmation, fr=false rejection.

	Strategy ca(%) cc(%) cr(%) fa(%) fc(%) fr(%) EvER(%)
	Strategy1 73.6	0	0	26.3	0	0	26.3
	Strategy2 71.9	2.2	0	17.0	9.3	0	26.3
	Strategy3 26.7	44.6	9.3	2.5	14.4	2.2	19.2
	Strategy4	0	71.4	9.3	0	17.0	2.2	19.2
	Strategy5	0	73.6	0	0	26.3	0	26.3
	7. Related work
	7.1. Dialogue strategy learning

Table 14 :

 14 Sample sub-dialogue with user responses assumed from logged real data.

Table 15 :

 15 Sample sub-dialogue with simulated coherent user responses.

	Agent Dialogue Act	Wording
	SYS gre(),	Welcome to the travel planning system.
	req(dep city)	Tell me your flight information.
	USR pro(dep city=amsterdam, A return flight from Amsterdam travelling
	dep time=morning,	in the morning with Air France
	airline=air france,
	flight type=return)
	SYS sic(flight type=return),	A return flight, where are you leaving from?
	req(dep city)
	USR pro(dep city=amsterdam) Amsterdam

Table 16 :

 16 Sample sub-dialogue with simulated random user responses.

	Agent Dialogue Act		Wording
	SYS gre(),		Welcome to the travel planning system.
		req(dep city)		Tell me your flight information.
	USR con(dest city=yes)	Yes
	SYS sic(flight type=return),	A return flight, where are you leaving from?
		req(dep city)
	USR pro(des city=amsterdam) To Amsterdam
	and	Recall =	Number of correctly predicted user responses Total number of real user responses	.

Table 18 :

 18 Dialogue similarity results for real vs simulated random sub-dialogues. KL (P ||Q) D KL (Q||P ) gre(),req(dep city):pro(dep city,flight type) 0.45 0.05

	Dialogue Act Pairs (SYS:USR)	P	Q D 1.426	-0.158
	sic(flight type)+req(dep city):pro(dep city) 0.45 0.05	1.426	-0.158
	gre(),req(dep city):con(des city)	0.05 0.45	-0.158	1.426
	sic(flight type)+req(dep city):pro(des city) 0.05 0.45	-0.158	1.426
	Divergence			2.536	2.536

A.3. Coherence Error Rate

An evaluation metric called Coherence Error Rate (

Table 1

 1

	):

Table 19 :

 19 Results of coherence for real and simulated user responses.

The benefit of learning the sequence of sub-dialogues is relevant for adaptive behaviour at different levels of granularity, and further experimentation using different sequences of sub-dialogues is left as future work.

Our speech recognition and speech synthesis OAA agents used wrappers generated from the TALK project(Lemon et al., 2006).

Simple automatic help: a) 1 st slot collection=no help, b) 2 nd collection=help prompt suggesting to fill multiple slots, c) 3 rd collection: help prompt suggesting a shorter sentence, d) 4 rd collection=help prompt suggesting to fill a single slot, e) others=help prompt suggesting to rephrase the sentence.

5 http://www.cstr.ed.ac.uk/projects/festival

(1) Note on statisfical significance: typically, p-values p ≤ 0.05 are considered to be statistically significant, and p-values p ≤ 0.1 are indicative of a statistical trend.(2) Note on task success: the drop of performance in fully-learnt behaviour was mainly caused by infinite loops, where the execution of action a in state s did not change the state s ′ = s.

the proposed simulated environment with coherent user behaviour, and distorted with conservative speech recognition error rates (keyword error rate of 20%) were sufficient for learning dialogue policies with superior performance than a reasonable hand-crafted behaviour;

Acknowledgements

Heriberto Cuayáhuitl was sponsored by PROMEP (http://promep.sep. gob.mx) and the Autonomous University of Tlaxcala (www.uatx.mx), and Oliver Lemon by EC FP6 "TALK". We thank Johanna Moore, Steve Young and the anonymous reviewers for their helpful comments on this work.