PROC IEEE, VOL. 101, NO. 5, 1160-1179, 2013

1

POMDP-based Statistical Spoken Dialogue
Systems: a Review
Steve Young, Fellow, IEEE, Milica Gašić, Member, IEEE, Blaise Thomson, Member, IEEE,
and Jason D Williams, Member, IEEE
(Invited Paper)

Abstract—Statistical dialogue systems are motivated by theneed for a data-driven framework that reduces the cost oflaboriously hand-crafting complex dialogue managers and thatprovides robustness against the errors created by speech recognisers operating in noisy environments. By including an explicit
Bayesian model of uncertainty and by optimising the policy via
a reward-driven process, partially observable Markov decision
processes (POMDPs) provide such a framework. However, exact model representation and optimisation is computationallyintractable. Hence, the practical application of POMDP-based
systems requires efficient algorithms and carefully constructed
approximations. This review article provides an overview of thecurrent state of the art in the development of POMDP-based
spoken dialogue systems.
Index Terms—Spoken dialogue systems, POMDP, reinforcement learning, belief monitoring, policy optimisation.

I. I NTRODUCTION
POKEN dialogue systems (SDS) allow users to interact
with a wide variety of information systems using speechas the primary, and often the only, communication medium[1], [2], [3]. Traditionally, SDS have been mostly deployedin call centre applications where the system can reduce theneed for a human operator and thereby reduce costs. Morerecently, the use of speech interfaces in mobile phones has
become common with developments such as Apple’s “Siri”
and Nuance’s “Dragon Go!” demonstrating the value of integrating natural, conversational speech interactions into mobile
products, applications, and services.
The principal elements of a conventional SDS are shownin Fig 11 . At each turn t, a spoken language understanding(SLU) component converts each spoken input into an abstract
semantic representation called a user dialogue act ut . The
system updates its internal state st and determines the next
system act via a decision rule at = π(st ), also known as apolicy. The system act at is then converted back into speech
via a natural language generation (NLG) component. The state
st consists of the variables needed to track the progress ofS

S. Young, M. Gašić and B. Thomson are with the Dept of Engineering, Trumpington Street, Cambridge University, Cambridge, UK, e-mail:{sjy,mg436, brmt2}@eng.cam.ac.uk
JD Williams is with Microsoft Research, Redmond, WA, USA, e-mail:jawillia@microsoft.com
1 Multimodal dialogue is beyond the scope of this paper, but it should be
noted that the POMDP framework can be extended to handle multimodal
input and output [4]. Depending on the application, both the input andoutput may include a variety of modalities including gestures, visual displays,
haptic feedback, etc. Of course, this could result in larger state spaces, andsynchronisation issues would need to be addressed.

the dialogue and the attribute values (often called slots) that
determine the user’s requirements. In conventional systems,
the policy is usually defined by a flow chart with nodes
representing states and actions, and arcs representing user
inputs[5], [6].
Despite steady progress over the last few decades in speech
recognition technology, the process of converting conversational speech into words still incurs word error rates in therange 15% to 30% in many real world operating environments such as in public spaces and in motor cars [7], [8].
Systems which interpret and respond to spoken commands
must therefore implement dialogue strategies that accountfor the unreliability of the input and provide error checking
and recovery mechanisms. As a consequence, conventional
deterministic flowchart-based systems are expensive to buildand often fragile in operation.
Input
speechSpokenLanguage
Understanding
(SLU)

ut

State
Estimator

st

User

SystemResponse

NaturalLanguage
Generation
(NLG)

at

PolicyDialogue Manager

Fig. 1. Components of a finite state-based spoken dialogue system. At eachturn the input speech is converted to an abstract representation of the user’s
intent ut , the dialogue state st is updated and a deterministic decision rulecalled a policy maps the state into an action at in response.

During the last few years, a new approach to dialogue management has emerged based on the mathematical frameworkof partially observable Markov decision processes (POMDPs2 )[9], [10], [11]. This approach assumes that dialogue evolves
as a Markov process, i.e., starting in some initial state s0 ,each subsequent state is modelled by a transition probability:p(st |st−1 , at−1 ). The state st is not directly observable reflecting the uncertainty in the interpretation of user utterances;instead, at each turn, the system regards the output of the SLU
as a noisy observation ot of the user input with probabilityp(ot |st ) (see Fig 2). The transition and observation probability
functions are represented by a suitable stochastic model, called
here the dialogue model M. The decision as to which action
to take at each turn is determined by a second stochastic
2 pronounced “pom dee pees”

PROC IEEE, VOL. 101, NO. 5, 1160-1179, 2013

2

model encoding the policy P. As the dialogue progresses, areward is assigned at each step designed to mirror the desired
characteristics of the dialogue system. The dialogue model
M and policy model P can then be optimised by maximising
the expected accumulated sum of these rewards either on-line
through interaction with users or off-line from a corpus of
dialogues collected within a similar domain.
Input
observation

Belief
state

ot

bt

SLU

Dialogue Model 𝛭(parameters 𝜏)

bt

User
NLG

at
Systemactionat

RewardFunction RrtΣRewardPolicy Model P(parameters 𝜃)
Dialogue Manager

Maximise 𝛴
wrt 𝜃, 𝜏

Fig. 2. Components of a POMDP-based spoken dialogue system. In contrast
to Fig. 1, the decoded input speech is now regarded as a noisy observation
ot of the underlying user intent ut . Since ut is hidden, the system maintains
a distribution bt over all possible dialogue states and instead of trying toestimate the hidden dialogue state, the system response is determined directlyfrom bt . In addition, the dialogue model and policy are parameterised,and given an appropriate reward function, they can be optimised using
reinforcement learning.

This POMDP-based model of dialogue combines two key
ideas: belief state tracking and reinforcement learning. These
ideas are separable and have benefits on their own. However, combining them results in a complete and well-foundedmathematical framework that offers opportunities for further
synergistic gains. The potential advantages of this approachcompared to conventional methods can be summarised asfollows:
1) the belief state provides an explicit representation of uncertainty leading to systems that are much more robust to
speech recognition errors [11]. The posterior probabilityof the belief state after each user input is updated via
Bayesian inference in a process called belief monitoring.
The design of the belief state allows user behaviour to be
captured via the model priors and the inference process
is able to exploit the full distribution of recognition
hypotheses such as confusion networks and N -best lists.
Thus, evidence is integrated across turns such that a single
error has significantly reduced impact, and in contrast toconventional systems, user persistence is rewarded. If theuser repeats something often enough, the system’s belief
in what they said will increase in time as long as thecorrect hypothesis appears repeatedly in the N -best list.
2) by maintaining a belief distribution over all states, thesystem is effectively pursuing all possible dialogue paths
in parallel, choosing its next action not based on the most
likely state but on the probability distribution across allstates. When the user signals a problem, the probabilityof the current most likely state is reduced and the focus
simply switches to another state. Thus, there is no requirement for back-tracking or specific error correction
dialogues. This allows powerful dialogue policies to beembedded in a simple homogenous mapping from belief
state to action.
3) the explicit representation of state and policy-derived
action allows dialogue design criteria to be incorporated
by associating rewards with state-action pairs. The sumof these rewards constitutes an objective measure of
dialogue performance and enables reinforcement learning
to be used to maximise performance both off-line using
dialogue corpora and on-line through interaction withreal users. This leads to optimal decision policies, avoids
the cost of expensive manual tuning and refinement
procedures, and enables more complex planning to be
implemented than would be feasible using only manual
hand-crafted designs.

Converting these potential benefits of the POMDP approach
into practice is, however, far from trivial and there are many
issues to resolve. The state-action space of a real-world
SDS is extremely large and its efficient representation andmanipulation requires complex algorithms and software. Realtime Bayesian inference is equally challenging and exact
policy learning for POMDPs is intractable, hence efficientapproximation techniques must be used. Finally, the moststraightforward way to optimise a POMDP-based SDS isthrough direct interaction with users. However, real users
willing to help train a system are often not available insufficient numbers, hence, user simulators are required thatcan replicate user behaviour with sufficient accuracy to enablemodel parameters to be optimised to an acceptable levelof performance (a discussion of user simulation is given in
section V).
Despite these difficulties considerable progress has been
made over the last five years in solving these problems and the
purpose of this paper is to review that progress and provide
a coherent up-to-date view of the state of the art in POMDPbased dialogue systems.
The paper is organised as follows. Firstly, section II outlines
the basic mathematics underlying POMDP-based dialoguesystems in order to provide the necessary background forthe subsequent sections and to establish a consistent notation.
Section III then explains the options available for approximating the belief state and presents algorithms for efficient belief
monitoring. Section IV reviews policy representation, the useof reward functions and policy optimisation via reinforcement
learning. Section V completes the review of core technology
with an overview of current approaches to user simulation.
Having established the basic framework, sections VI and VII
review a number of recent developments in optimisation of
dialogue model parameters and fast adaptation. To give someindication of the potential for real-world deployment, section VIII briefly describes some existing prototype systems andapplications that incorporate POMDP-based dialogue management, with some example evaluations given in section IX.
Finally, for completeness, section X provides a historicalperspective and section XI concludes.

PROC IEEE, VOL. 101, NO. 5, 1160-1179, 20133

II. PARTIALLY O BSERVABLE M ARKOV D ECISIONP ROCESSES
Formally, a partially observable Markov decision process isdefined as a tuple (S, A, T, R, O, Z, γ, b0 ) where S is a set ofstates with s ∈ S; A is a set of actions with a ∈ A; T defines atransition probability P (st |st−1 , at−1 ); R defines the expected(immediate, real-valued) reward r(st , at ) ∈ <; O is a set ofobservations with o ∈ O; Z defines an observation probability
P (ot |st , at−1 ); γ is a geometric discount factor 0 ≤ γ ≤ 1;and b0 is an initial belief state, defined below.
The POMDP operates as follows. At each time-step, theworld is in some unobserved state st . Since st is not known
exactly, a distribution over possible states called a belief statebt is maintained where bt (st ) indicates the probability of being
in a particular state st . Based on bt , the machine selects anaction at , receives a reward rt , and transitions to (unobserved)
state st+1 , where st+1 depends only on st and at . The machinethen receives an observation ot+1 , which is dependent on st+1
and at . This process is represented graphically as an influence
diagram in Fig 3.

both types of policy will use the same symbol π, with thepresence of the action in the notation determining whether thepolicy is deterministic or stochastic. Note, however, that otherdefinitions are possible such as finite state controllers [13],or mappings from finite-length sequences of observations toactions (c.f. predictive state representations [14]).
The discounted sum of rewards expected by starting in
belief state bt and following
policy π is given by the valuefunction V π (bt ) = E rt + γrt+1 + γ 2 rt+2 + . . . , which canbe expressed recursively for a deterministic policy as
V π (bt ) = r(bt , π(bt ))X+γ
P (ot+1 |bt , π(bt ))V π (bt+1 )and byV π (bt ) =Xπ(at |bt )

+γ

X

st+1
rt

ot

at

rt+1

ot+1




r(bt , at )



at

ot+1

st

(2)

ot+1



P (ot+1 |bt , at )V π (bt+1 )(3)for a stochastic policy. A related quantity is the Q-function
Qπ (b, a), which provides the expected discounted sum of
rewards if a specific action a is taken given belief state b, andthen policy π is followed. Clearly for a deterministic policy,
V π (b) = Qπ (b, π(b)) and for a stochastic policyX
V π (b) =π(a|b)Qπ (b, a).
(4)

at+1

a
∗

Time step t

Time step t+1

Fig. 3. A partially observable Markov decision process, shown as an influence
diagram. In this paper, clear circles are hidden random variables; shaded
circles are observed random variables; squares are system actions; diamonds
are real-valued rewards; and arrows show causality.

Given an existing belief state bt , the last system action at ,and a new observation ot+1 , the new updated belief state bt+1
is given by [12]:X
bt+1 (st+1 ) = ηP (ot+1 |st+1 , at ) P (st+1 |st , at )bt (st ) (1)stwhere η = P (ot+1 |bt , at ) is a normalization constant andwhere b0 is the initial belief state distribution before the firstsystem action has been taken.3
The system action is determined by a policy π, which canbe represented in a variety of ways. It is most commonly
either a deterministic mapping from belief states to actions
π(b) ∈ A or stochastically via a distribution over actions
π(a|b) ∈ [0, 1] where π(a|b)
P is the probability of taking action
a in belief state b, and a π(a|b) = 1 ∀ b. For convenience,
3 The notation for belief states can be confusing: b represents a probabilitytdistribution over the hidden state space S at time t; bt (s) denotes theprobability of a specific state s given belief state bt ; bt+1 (s) represents theprobability of state s given a new updated belief state bt+1 , which in general
will be different from bt (s).

An optimal policy π is one that maximizes V π to yield V ∗X
P (ot+1 |bt , at )V ∗ (bt+1 )(5)V ∗ (bt )=maxr(bt , at ) + γ
at

ot+1

which is the Bellman optimality equation for POMDPs [15].
In the POMDP literature, finding a policy π that satisfies (5)is often called “solving” or “optimizing” the POMDP. For
simple tasks, both exact [12] and approximate [16], [17], [18],[19], [20] solution methods have been developed. However,standard POMDP methods do not scale to the complexity
needed to represent a real-world dialogue system. Even in amoderately-sized system, the number of states, actions, andobservations can each easily be more than 1010 . Even enumerating P (st+1 |st , at ) is intractable, and as a result computing(1) directly and applying direct solution methods to (5) isvery difficult. Instead, approximations have been developedthat exploit domain-specific properties of the spoken dialogue
task in order to provide compact representations for both themodel and the policy; and to allow tractable algorithms for
performing belief monitoring and policy optimisation. These
are described in the following sections.
III. B ELIEF S TATE R EPRESENTATION AND M ONITORING
This section reviews the possible approaches to representing
the dialogue model M shown in Fig. 2. In a practical taskoriented SDS, the state must encode three distinct types of

PROC IEEE, VOL. 101, NO. 5, 1160-1179, 2013

4

information: the user’s goal gt , the intent of the most recent
user utterance ut and the dialogue history ht [21], [11]. The
goal encompasses the information that must be gleaned fromthe user in order to fulfil the task, the most recent user
utterance represents what was actually said in contrast to what
was recognised, and the history tracks pertinent information
relating to previous turns. This suggests that the state should
be factored into three components
st = (gt , ut , ht ).

(6)

The resulting influence diagram is shown in Fig. 4 in whichsome reasonable independence assumptions have been introduced. Factoring the state in this way is helpful because it
reduces the dimensions of the state transition matrix and it
reduces the number of conditional dependencies.
st

st+1

gt

gt+1
ht

ht+1

ut

ut+1

rt

ot

A. N -best approaches
rt+1

at

ot+1

Time step t

at+1

Time step t+1

Fig. 4. Influence diagram representation of a factored state SDS-POMDP.
The hidden dialogue state st is factored into a user goal gt , the user’s last
input ut and key elements of the dialogue history ht . This allows conditional
independence assumptions to be introduced both within the state and from
one time-slice to the next. No arc is required from actions to observations
since the recognised speech ot is conditionally independent given the user’s
actual utterance ut .

Plugging the factorisation in (6) into the belief update
equation (1) and simplifying according to the independence
assumptions shown in Fig 4 gives the basic belief update
equation for a statistical SDS:
bt+1 (gt+1 , ut+1 , ht+1 ) = ηP (ot+1 |ut+1 )· P (ut+1 |gt+1 , at )X·
P (gt+1 |gt , at )

(a)
(b)
(c)

gt

·

X

P (ht+1 |gt+1 , ut+1 , ht , at ) (d)In N -best approaches, the belief state is approximated bya list of the most likely states (or groups of states) with theirprobabilities. This means that dialogue states corresponding
to the most likely interpretations of the user’s intent are wellmodelled, with other states given low probability mass. One
example of this approach is the Hidden Information Statemodel (HIS) [23], which groups similar user goals into equivalence classes called partitions on the assumption that all of thegoals in the same partition are equally probable. The partitions
are tree-structured to take account of the dependencies definedin the domain ontology and they are built using slot-value
pairs from the N -best list of recognition hypotheses and thelast system output. The combination of a partition, a user
act from the N -best list and the associated dialogue history
forms a hypothesis. A probability distribution over the most
likely hypotheses is maintained during the dialogue and thisconstitutes the belief space. Belief monitoring then requires
only the hypothesis beliefs to be updated and since there are
relatively few hypotheses, this can easily be done in real time.
The update equation for the HIS model follows directly from
(7) with the further simplification that the user goal is normallyassumed to be constant [23]bt+1 (pt+1 , ut+1 , ht+1 )= ηP (ot+1 |ut+1 )P (ut+1 |pt+1 , at )X
P (ht+1 |pt+1 , ut+1 , ht , at )ht

P (pt+1 |pt )b(ht )ht· bt (gt , ht )(b) the user model represents the likelihood that the user
would utter u given the previous system output and the
new system state. This encapsulates user behaviour.
(c) the goal transition model represents the likelihood that theuser goal has changed.
(d) the history model represents the system’s memory of the
dialogue to date.
There are of course possible variations to this factorisation.
For example, user affect may also be factorised out [22] but
most current approaches fit broadly within this model.
While the factorisation in (6) does significantly reduce
the POMDP model complexity, it is still too complex tosupport tractable real-world systems. Further approximationis therefore necessary for which two main approaches haveemerged:1) the N -best approach including pruning and recombination strategies [23], [24], [25], [26], and2) the factored Bayesian Network approach [27], [22], [28].
These two approaches are discussed below.

(7)

The terms on the right hand side in (7) reflect each of thefactors determining the belief state and the underlying models
which are therefore needed to represent these factors in apractical system:(a) the observation model represents the probability of anobservation o given the user’s actual utterance u. This
encapsulates the effects of speech understanding errors.

(8)

where pt is a partition and the term P (pt+1 |pt ) represents
the probability that a partition pt will be split into two subpartitions pt → {pt+1 , pt − pt+1 }. A similar approach is takenin [24], except that both slot values and their complements areused to build a frame. This is particularly useful in negotiationtype dialogues, where the users can change their mind and ask
for an alternative. It also enables a form of first-order logic
to be expressed and understood by the system. However, thePROC IEEE, VOL. 101, NO. 5, 1160-1179, 2013

domain ontology is not used when building frames losing thebenefits of modelling conditional dependence. In [26], it isshown that complements can also be incorporated into the HIS
approach giving the advantage of modelling both conditional
dependence and first order logic.
The N -best approach can also be viewed as running N
conventional dialogue systems in parallel such that each parallel thread tracks a different interpretation of what the user
said. In this case, a list of hypothesised dialogue states ismaintained; associated probabilities can be assigned using a
mixture distribution [29], a discriminative classifier [30], orwith a heuristic scoring function [31]. Although it lacks thecompactness of the HIS representation, this approach provides
a simple upgrade path for conventional deterministic dialoguesystems.
Both the partition-based and the frame-based approaches
have the inherent problem that the number of partitions(frames) grows exponentially with dialogue length. Hence, inpractical implementations, some form of pruning is required.
In [25], partitions are organised into a tree and then low probability partitions are recombined with their parent, thus limiting
the number of partitions. This has the problem however thathigh probability slots can be pruned if they are distributed
over many partitions. A more effective solution is proposedin [26], where at every dialogue turn a marginal probability
distribution is calculated for each slot. Then, low probability
slot-value pairs are pruned by recombining all the partitions
that have that slot-value pair with the partitions that have thecomplement of that slot-value pair. In this way, the method
supports dialogues of arbitrary length.
B. Factored approaches
The alternative to maintaining an N -best list of user goals is
to factor the user goal into concepts that can be spoken about
by the system. This is illustrated in Fig. 5, which shows an example from a tourist information system in which entities havea type such as {hotel, restaurant, bar}, the kind of food served
and an area such as {north, south, centre, ...} [28]. The foodand area slots are dependent only on the type, even though
in practice, there are many more restaurants in the centre of
town. This illustrates the differing trade-offs between the N best approach, which can model all dependencies but with anincomplete distribution, and the slot-level factoring approach,which can handle only a limited number of dependencies but
can model the complete distribution.
Once the Bayesian network for the slot-level factoring has
been compiled, standard belief propagation algorithms can beused to update the beliefs [32]. In the case of concepts thatare conditionally independent, the belief propagation algorithm
will give exact updates of the marginal distributions for eachof the concepts, as used in [22]. Limited dependencies can also
be modelled, although this requires approximate methods suchas loopy belief propagation. The Bayesian update of dialogue
state (BUDS) model is one example that is based on thisapproach [27], particle filters can also be used [33].
It is interesting to note that N -best approximations can also
be used within a factored model. Instead of the factored model

5

updating beliefs for all the possible values of a node in the
network, only an N -best list of values is updated. Partitionsof the states in a node are also possible [34]. This combines
many of the benefits of the two approaches.
gtype

garea
gfood

a
utype

ufood

uarea

u
htype

hfood

Time step t

harea
o

Fig. 5. Influence diagram for a single time slice of a BUDS POMDP inwhich the state is further factored into concept or slot level components. In
this simplified example taken from the tourist information domain, three slot
level values are required: the type of venue, the kind of food served and thearea in which the venue is located. Note that food and area are conditionallyindependent given the type of venue and last action. (Although not shown
explicitly to avoid cluttering the diagram, all slot-level nodes are dependent
on the last system action.)

IV. P OLICY R EPRESENTATION AND R EINFORCEMENTL EARNING
This section presents the representation and estimation of
the policy model P shown in Fig. 2, which provides a mapping
between the belief state b and the appropriate system action a.
The objective is to find an optimal policy π ∗ that maximizes
the expected sum of discounted rewards at the end of the
dialogue.
The belief space of a POMDP spans an (|S|−1)-dimensional
simplex where |S| is the cardinality of the underlying hidden
state space. Points in belief space that are close to eachother will share the same action, and hence, a non-parametricpolicy must encode firstly a partitioning of belief space suchthat all points within any partition map to the same action,and secondly it must encode the optimal action to take foreach partition. Whilst exact representations of a POMDP
dialogue policy are possible, for example by compressing
belief space [35] or dynamically re-assigning states [36], exact
representations are all intractable for real world problems
such as spoken dialogue systems where both the state andaction spaces will typically be very large. Thus, a compact
representation of the policy is essential.
Fortunately, there are some mitigating constraints that canbe exploited. Firstly, only a relatively small part of belief
space will actually be visited during any normal dialogue, andsecondly, the range of plausible actions at any specific point
in belief space will often be restricted. This introduces thenotion of a compressed feature space called summary spacein which both states and actions are simplified in order toPROC IEEE, VOL. 101, NO. 5, 1160-1179, 2013

allow tractable policy representation and optimisation [37],[38]. Summary space can therefore be regarded as a subspaceof the full master space whereby belief tracking is performed
in master space, and decision-taking and policy optimisation
take place in summary space. The run-time operation of amaster-summary space POMDP is therefore as follows. After
belief updating, the belief state b in master space is mapped
to a vector of features b̂ and a corresponding set of candidate
actions {â}. The policy is then used to select the best action
to take b̂ → â from the set of candidate actions and a second
heuristic is used to map â back into a full action a in masterspace.
Summary-space mapping requires two components: a mechanism to select candidate actions in master space and functions
to extract features from the belief state and candidate actions.
The simplest method for selecting candidate actions is toinclude all types of dialog acts (e.g., greet, ask, confirm,
inform, etc.) applicable to any concept or slot (e.g., venuetype, food-type, star-rating, etc.), populating slot values byhighest belief [28], [37]. This approach has the benefit ofbeing entirely automatic; however, it still admits some spurious
candidate actions, such as taking a greeting action in the
middle of a dialog, or attempting to confirm a value before
the system has asked about it. An alternative method forselecting candidate actions is to construct a hand-craftedpartial program [39], [40] or a Markov logic network [41].
These approaches have the benefit of allowing arbitrary humanknowledge about dialogue flow to be incorporated, and to
explicitly set business rules, for example, requiring that certain
actions be taken before others such as successfully collecting
a password before allowing funds to be transferred. It has
also been shown that constraining the set of candidate actions
results in faster convergence to an optimal policy, since many
spurious actions are pruned away [40]. However, rules require
human effort to encode, and there is a risk that optimalcandidate actions may be inadvertently excluded. Intermediate
methods are possible too, such as allowing every dialogue act
to be a candidate action, but constraining the slots that the act
operates on using hand-crafted heuristics [42].
The second component required for summary-space mapping are functions to extract features from the belief stateand each candidate action. For actions, typically one binaryfeature is created for each dialog act, or for each valid
dialog act/slot pair, such as confirm(food). This generally
results in a 20-30 dimensional vector of action features, where
each dimension represents a unique (summary) action. State
features are typically heterogeneous, consisting of real-valued
quantities, binary values, categorical values, etc. Typical statefeatures include: the belief in the top N user goals or partitions;the top marginal belief in each slot; properties of the top user
goal or partition, such as the number of matching databaseentries; an indication of which system actions are available;
properties of the dialogue history, such as whether the top user
goal/partition has been confirmed; the most likely previous
user action; or combinations of these features [37], [40], [28],[42], [43]. A typical system has 5 to 25 features in total
which are usually hand-selected, although some work has been
done to automate feature selection [43], [44]. State features6

need not be limited to information in the belief state: features
may also draw on information being tracked outside the belief
state, such as information in databases, information from pastdialogues, usage context, etc.
Given a specific summary space, a policy may be represented as an explicit deterministic mapping: π(b̂) → â or as aconditional probability distribution π(b̂, â) = p(â|b̂) where therequired action is selected by sampling the distribution. Notethat the policy is now a function of the summary belief state
and actions, instead of the original belief state and actions.
One can think of this either as a new function that gives anapproximation to the value in the original space, or as a policy
over a new Markov decision process, where the states andactions are now the summary states and actions. The same istrue of the Q function, and both these functions will now be
used in this context.
In the case of deterministic mappings, the dominant approach is to find an optimal Q-function (see section II) Q∗
that maximises maxâ {Q(b̂, â)} for all b̂, thenπ ∗ (b̂) = arg max{Q∗ (b̂, â)}.
â

(9)The Q-function itself can either be parametric or nonparametric in which case the belief state is quantised intoa codebook {b̂i } and Q∗ (b̂i , â) can be computed for eachdiscrete codebook entry b̂i .
To illustrate some of these options, five different methods ofpolicy optimisation are now presented: planning under uncertainty, value iteration, Monte-Carlo optimisation, least-squares
policy iteration, and natural actor-critic. These methods havebeen selected because all have been applied to end-to-end
working dialogue systems. Some further optimisation methods
will be covered later in section VII on fast adaptation. While
representative, these five methods are not exhaustive – forexample, Q-Learning [45], [46], [47], [48] and SARSA [49],[50], [51] are also popular techniques.
A. Planning under uncertainty
One approach to policy optimisation is to view action
selection in summary space as planning under uncertainty. In
this approach, b̂ is viewed not as a vector of arbitrary features,but rather as a distribution over a hidden state variable insummary space ŝ. This hidden summary state might express,for example, whether the top hypothesis in master space iscorrect or not. In addition, it is assumed observations o (inmaster space) can be mapped to a compact observation insummary space ô.
With these definitions in place, dialogues can be collectedwith a random policy, and three models of summary space dynamics can be estimated – P (ŝ0 |ŝ, â), P (ô0 |ŝ, â), and R(ŝ, â).
These models define a classical POMDP in summary space
and admit standard methods for planning under uncertainty,
including different versions of point-based value iteration [16],[18], SARSOP [52], heuristic search value iteration [17], [19],and short look-aheads [53], [22]. These methods have been
applied to dialogue systems in a variety of domains, mainly
in simulation [37], [54], [53], [22], [55], [56], [57], [58], [59],[60] and also in an end-to-end spoken dialogue system [61].

PROC IEEE, VOL. 101, NO. 5, 1160-1179, 2013

7

Optimization by planning under uncertainty is attractive inthat optimization methods are principled, and in some cases
provide well-defined optimality bounds [17], [19]. Anotherstrength is that a policy can be computed from any corpusthat contains sufficient exploration of possible dialog paths.
However, it suffers from several problems. First, the summary
state ŝ and observation ô may be difficult to define, andincorporation of extrinsic features in b̂ may require careful
engineering of the models P (ŝ0 |ŝ, â) and P (ô0 |ŝ, â). Also,
while great strides have been made in scaling optimization
methods for planning under uncertainty, supporting large stateor observation spaces in summary space can be problematic.
For these reasons, techniques have been developed which
avoid defining states and observations in summary space.
These are described in the next four sections.

mitigates against the effects of any non-Markovian dynamics
in the state features.
To perform Monte Carlo optimization, the sequence ofstates, actions, and rewards
in each dialogue of length observed 
T are recorded as tuples b̂i(t) , ât , rt for t = 0, 1, . . . , T . The
discounted return from each belief point b̂i visited at time t isgiven by
X
Ri(t) =γ (τ −t) rτ .
(11)t≤τ ≤T

Two functions accumulate sums across all dialogues in the
corpus. First, q(i, â) is a sum of all returns R observed when
action â was taken in grid point b̂i . Second, n(i, â) is a countof the instances of action â being taken in gridpoint b̂i . Bothq(i, â) and n(i, â) are initialized to zero for all i and â. At
the end of each dialogue, these tallies are then updated

B. Value Iteration
Instead of defining states and observations in summary
space, in value iteration belief states b̂ are viewed as arbitrary
feature vectors, and dynamics are estimated directly in thisfeature space. Starting again with dialogues collected withactions taken randomly, feature vectors are quantised into
grid points {b̂i }, and then the transition function P (b̂j |b̂i , â)and reward function R(b̂i , â) are estimated [40], [62]. Finally,
standard value iteration can be applied [63]X
Q(b̂i , â) = r(b̂i , â) + γ
Q(b̂j , â0 ) (10)P (b̂j |b̂i , â) max
0jâ

where Eq. 10 is applied repeatedly until convergence. The
clusters b̂i can either be distinct hard clusters, or soft clusters
where observed b̂ are shared by nearby b̂i . In this case, thecontributions of b̂i that are further away from b̂ can be downweighted [40], [62].
Value iteration’s main attraction is that it is simple toapply, and it allows a policy to be estimated from any
corpus that contains sufficient exploration of possible dialogue
paths. However, it suffers from several problems. Firstly, it
requires an estimate of transition dynamics for the entire space
P (b̂j |b̂i , â), when in practice it is only important to estimate
the portions of space traversed by the currently optimal policy.
Hence, value iteration is sample inefficient. Secondly, if thestate features are not Markovian – i.e., if they do not accurately
capture all relevant history for conditioning transitions – errors
will be introduced into the policy. To address both of theseissues, incremental on-line learning methods have also been
explored.
C. Monte Carlo optimization
In Monte Carlo optimization, the value function Q is
estimated on-line – iteratively, whilst interacting with the user(or more likely interacting with a user simulator - see section V). The current estimate of the policy guides future action
selection, so less exploration time is expended on regionsof the state space with low value. In addition, updates are
performed at the end of each dialogue; hence, whole-dialogue
rewards can be used to directly value the current policy, whichq(i(t), â)=q(i(t), â) + Ri(t)(12)

n(i(t), â)=n(i(t), â) + 1,

(13)

for t = 0, 1, . . . , T . The Q values can then be re-estimated forall belief points i visited in the dialogue and all â as
Q(b̂i , â)=1q(i, â).
n(i, â)(14)

To converge to an optimal policy, the dialogue system musttake a mixture of currently optimal and exploratory actions

RandomAction
with probability 
(15)
â =
arg maxâ Q(b̂i , â) with probability 1 − 
where  controls the exploration rate. Typically this is large
initially but reduces as learning progresses. As in the value
iteration case, the state discretization can be done by clustering
neighbouring points into distinct hard clusters [42], or softclusters where the contribution of a belief point b̂ to the tallies
q(i, â) and n(i, â) is reduced in proportion to its distance fromthe template point b̂i [64].
One important consideration for Monte Carlo optimisationis the number of grid points to use. If too many grid points
are used, poor performance will result due to over-fitting.
Conversely, having too few grid points leads to poor performance due to a lack of discrimination in decision making. For
building practical systems with 5 summary state components
and 10 distinct summary actions, 750–1000 grid points havebeen found to be sufficient when trained with around 100,000
simulated dialogues [42].
As compared to value iteration, on-line Monte Carlo optimisation is more sample efficient and suffers less when thetransitions are non-Markovian in the state features. However,since Monte Carlo optimisation is an on-line method, it cannot
be performed using a previously collected corpus. Like value
iteration, Monte Carlo optimization requires quantizing thefeature space into grid regions. As the number of features
grows, this becomes a source of intractability, which motivates
the use of functional approximations for the Q-function,
presented next.

PROC IEEE, VOL. 101, NO. 5, 1160-1179, 20138

D. Least-squares policy iteration
Instead of using discrete grid points in summary space, thenext two methods utilise linear models to represent a policy.
The first is least-squares policy iteration (LSPI) [65]. LSPI
assumes that the Q function can be represented as a weighted
sum of the features φ>Q(b, â) ≈ φ(b, â) θr + γQ(b0 , π(â)).

=

(17)

Substituting Eq 16 into Eq 17 yields a system of N equations
in K unknowns
φ(bn , â)> θ=

rn + γφ(b0n , π(b0n ))> θπ(â|b, θ)(16)where θ is a (column) weight vector, φ(b, â) outputs features ofb that are important for making decisions relevant to summary
action â, and θ and φ(b, â) are both of size K. Notice thatthe functional mapping from master belief space to summary
belief space is now explicit in the function φ. The Q-functionis thus approximated as a plane in feature space. This may
result in sub-optimal policies if the representation is not richenough.
LSPI operates on a given, fixed dialogue corpus with N + 1
turns {bn , ân , rn , b0n } where b0n is the belief state following bn
in the corpus. LSPI begins with some policy π, and optimizes
it by iteratively estimating its value function Q, then using Q
to improve π. To estimate Q, we start with the identity thatdefines the value function Q
Q(b, â)E. Natural actor-critic optimization
LSPI uses a linear model to estimate the value function Q.
An alternative approach is to represent the policy directly as
an explicit probability distribution over actions, parameterized
by an adjustable weight vector θ,(18)

for n = 0..N −1. This system of equations can be solved ina least squares sense by setting θ = Z −1 y where [65]X>
φ(bn , ân ) (φ(bn , ân ) − γφ(b0n , π(b0n ))) (19)Z ==eθ·φâ (b),θ·φâ0 (b)
â0 e

P

(22)

where φâ (b) determines the features of the belief state b thatare important for making decisions relevant to summary actionâ. As above, φ is specified by the system designer, and φand θ both have dimensionality K. π is as before, with the θ
simply indexing which policy parameters to use (i.e., policyπθ (â|b) = π(â|b, θ)).
Representing the policy in this way has two advantages.
Firstly, it avoids the need to choose grid points and the
problems that result. Secondly, since π(â|b, θ) is differentiablewith respect to θ, it allows gradient ascent to be applied for
optimisation. The expected cumulative reward for a single
dialogue as a function of θ is
"T −1
#
X
r(bt , ât )|πθ .
R(θ) = E(23)
t=0

By rewriting the log likelihood-ratio [66] and Monte Carlosampling from a batch of N dialogues, the gradient can be
estimated as
N T −1∇R(θ) =n
1 X X
∇θ log π(ânt |bnt , θ)Q(bnt , ânt ) (24)N n=1 t=0(21)

Although (24) provides an estimate for the plain gradient, it˜
has been shown that the natural gradient ∇R(θ)= Fθ−1 ∇R(θ)
is more effective for optimisation of statistical models whereFθ is the Fisher Information Matrix [67]. Furthermore, thisnatural gradient w can be found without actually computing
the Fisher Matrix by using a least square method to solve thefollowing system of equations
#
"T −1
n
X
n
n n
>
∇θ log π(ât |bt , θ) · w + C
(25)
R =

and re-estimation of θ and π then continues until both have
converged.
LSPI is attractive in that it avoids estimating grid points inbelief space in favour of a linear model for Q. It also has nolearning parameters to tune and it can be used both on-line andoff-line, although in the case of the latter it can be difficult tofind corpora with sufficient variability to learn policies that are
significantly different to the policy used to collect the corpus.
One drawback of LSPI is that the least-squares solution
step is cubic in K; hence, for practical applications of LSPI
the feature set must be kept quite small. To assist this,methods have been developed that perform feature selection in
conjunction with LSPI [43] whereby, at each iteration, a fast
but approximate estimate of θ is computed on the full set offeatures; then only the features with the highest weights areused in the expensive but more accurate least-squares solution.
Experiments show this method produces policies of similar
performance but with far fewer features [43].

for each dialogue n = 1..N where Rn is the actual cumulative
reward earned for dialogue n and C is a constant that can beinterpreted as the expected cumulative reward of the dialoguesystem starting from the initial state. The total expected reward
can then be iteratively maximised through gradient ascent via
the parameter update θ0 ← θ + δw where δ is the step size.
This is called the Natural Actor Critic (NAC) algorithm [68],and has been applied to a number of spoken dialogue systems[28], [69], [70], [71], [72].
NAC is particularly well-suited for on-line operation because the policy is represented as an explicit distribution overactions. Unlike the -greedy exploration used in Monte-Carlo
optimisation (where random actions are chosen with a uniform
distribution), the NAC optimisation process can differentiate
between less-promising and more-promising actions and therefore explores the solution space more efficiently.
As with LSPI, NAC requires the solution of a system of
linear equations (25), which is again cubic in the number

y

=

n
X

φ(bn , ân )rn

(20)

n

where Z is a K × K matrix and y is a K-dimensional vector.
π(b) is then updated byπ(b)=arg max φ(b, â)> θâ

t=0PROC IEEE, VOL. 101, NO. 5, 1160-1179, 20139of features, so it is important to choose a compact set ofrepresentative features.
F. Section summary
To conclude this section, five approaches to policy representation and optimisation have been presented, which as well
as being representative of current practice also illustrate someof the principal design choices. In particular, planning under
uncertainty uses the belief state as a probability distribution
directly, whereas value iteration and Monte Carlo optimisation
require belief space to be quantised, and LSPI and NAC use
functional approximations based on weighted linear models
of belief state features. Monte Carlo methods and NAC (andSARSA) must be run on-policy; planning under uncertainty,
value iteration, and LSPI (and Q-Learning) may be run offpolicy, in batch: on-policy methods require that interactions
are obtained following the policy under optimization, whereas
off-policy methods can perform optimization with interactions
obtained by following a different policy. A distinction can also
be made between methods like planning under uncertainty
and value iteration that perform planning on a given modelof dynamics, and the other methods described (including QLearning and SARSA) which concurrently learn about theenvironment and plan simultaneously. NAC also differs in that
it utilises a stochastic policy from which actual actions canbe drawn by sampling the policy distribution. This allows a
dialogue system to explore alternative actions more effectively
by avoiding searching regions of the belief-action space thatare very unlikely to ever be visited. Unfortunately, this gain is
offset by the generally slow learning characteristics of gradientascent and in practice the NAC algorithm requires around 105
dialogues to optimise a policy [28]. Since the availability oflarge diverse corpora and/or large numbers of real users willingto interact with a partially trained dialogue system is normallylimited, significant attention has been paid to developing user
simulators for training statistical dialogue systems and this will
be dealt with next.
V. U SER S IMULATORS
Learning directly from corpora is problematic since the state
space that prevailed during the collection of the data may differ
from that used in policy optimisation and also it precludes theuse of on-line interactive learning algorithms. An alternative
is to build a model of the user that can interact directly witha dialogue system and which can itself be trained on corpora.
Such a user simulator can then be used for a wide variety ofdevelopment, training and evaluation purposes [73].
User simulators normally operate at the abstract level of
dialogue acts. Given a sequence of user acts and system
responses, the aim is to model the distribution of plausibleuser responsesp(ut |at , ut−1 , at−1 , ut−2 , . . .)(26)

from which an actual user response can be sampled. As
indicated in Fig. 2, in a real system the dialogue manager
only has access to a noisy observation ot = [ũ1t , . . . , ũNt ]where ũnt is a confused version of ut with confidence scorep(ũnt |ut ). Thus, an error model is needed as well as a usermodel. The model for p(ut | . . .) should match the statistics
of user responses in available corpora and the error model
should match the characteristics of the speech recognition andunderstanding system [74], [75], [76], [77].
A. User simulation models
One of the earliest approaches to user simulation used N grams to model (26) directly [78], [79], [80]. The problem
with this approach is that large N is needed to capture context
and ensure that the user conveys consistent behaviour with theresult that the model is inevitably undertrained. A response tothis problem was to design simulators that were essentiallydeterministic and goal-directed but which had trainable random variables wherever there is genuine user choice [81], [82],[83], [84], [85], [86], [87]. These systems can work well but inpractice a large amount of hand-crafting is required to achieve
acceptable performance.
More recent approaches to user simulation have focused on
the use of dynamic Bayesian networks and hidden Markov
models paralleling the user model in the POMDP itself [88],[89], [90], [91]. They can also incorporate explicit goals byusing a Bayesian network to maintain the goal state of theuser [92]. Bayesian network approaches have the advantagethat they can model a rich set of conditional dependencies
and can be trained on data, although once again data sparsity
is a major problem. An alternative promising technique, which
avoids the sparsity issues inherent in joint-probability models
uses conditional random fields [93]. These have the advantagethat they can model very long sequences as features much
more efficiently.
Ultimately, the most obvious approach to user simulation
will be to train a POMDP-based dialogue system to behave
like a user. The simulator could then talk to the system, withthe simulator and system each refining their individual policies
to maximise reward. The principal barrier to doing this is thelack of an appropriately detailed reward function for the userside of the dialogue. A solution to this might be to utilise
inverse reinforcement learning to infer users’ reward functions
from real human-human dialogues [94], [95].
B. Error simulation models
User simulation was first introduced to train Markov Decision Process (MDP) based dialogue systems where only
the single best output from the recogniser is used. In thiscase, the error model was required primarily to simulate ASR
errors [96], [97], [98], [99], [100]. In contrast, POMDP-based
systems use the full distribution of recognised hypotheses at
every turn. Hence, as noted at the start of this section, the error
model for a POMDP system must generate not just a single
confusion but a set of confusions, each with a probability
consistent with the behaviour of the actual recogniser. The
information content of this distribution makes a significant
difference to performance [101]. Hence, it is important tomodel it accurately.
To conclude this section, user simulation and error modelling are important practical tools for building complex

PROC IEEE, VOL. 101, NO. 5, 1160-1179, 2013

statistical dialogue systems for which training directly fromreal users would be impractical. Pragmatically, the approachworks reasonably well but the results are highly sensitive tothe simulator [102], [103]. POMDP policy optimisation isextremely good at exploiting inconsistent behaviour in a user
simulator in order to increase its reward. Thus, it is very easy
to obtain very high performance when training and testing on
the same simulator, but then to find actual performance in fieldtrials is poor. One way of mitigating against this is to train andtest on different simulators [102], [104].
VI. D IALOGUE MODEL PARAMETER OPTIMISATION
Referring back to Fig. 2, a complete POMDP-based dialogue system is characterised by two sets of parameters: thedialogue model M with parameters τ , which incorporates theuser, observation and transition probability distributions; andthe policy model P with parameters θ. Most current POMDP
development focusses on policy optimisation and the θ parameters, whereas the dialogue model and the τ parameters are
frequently hand-crafted. While hand-crafting the dialog model
may seem unsatisfactory, in many cases the dialogue designer
will have a strong prior on where the parameters should be. For
example, in many applications it may be reasonable to assume
that the user goal is constant throughout the dialogue. In thiscase the probability function p(st |st−1 , at−1 ) becomes a delta
function. Similarly, one might reasonably assume that the trueuser action cannot be a contradiction of the user goal, andthe distribution over all actions that are not contradictions is
uniform. Hence a user action like “I want a Chinese restaurant”
might have zero probability for goals where the food concept
is not Chinese but uniform probability otherwise.
In some situations, it is also possible to annotate dialogue
corpora to provide complete knowledge of the states of thesystem. Simple frequency counts can then be used to provide
maximum likelihood estimates of key parameters [105]. In[106], maximum likelihood is used to estimate a bigram modelof the type of user action while using a handcrafted model
to give zero probability to user goals that contradict a given
action. In this way simple maximum likelihood can be used
to tune relatively complex models.
However, user behaviour and the noise distributions of the
speech understanding components are complex and annotating dialogue corpora of sufficient quantity and accuracy isimpractical. Hence, key state variables such as the user’s
goal must be treated as hidden, and model parameters mustbe estimated using inference techniques. Recent research isstarting to address this problem of learning the dialogue model
parameters τ directly from dialogue corpora using a variety of
approaches.
A. Expectation maximisation
If the hidden state cannot be annotated then one must turnto an approximate inference algorithm. Since the POMDP has
an input-output hidden Markov model structure, the expectation maximisation algorithm (EM) is a sensible first choice.
EM operates by using a fixed set of parameters to estimate
marginal distributions of the hidden parameters in its first step.

10

It then uses these marginals to re-estimate the parameters ofthe model and repeats.
EM has been used to learn the user model for a small
spoken dialogue system with 7 states [107]. However, thisapproach does not scale well when the number of states issignificantly increased. The main problem is that marginals
must be computed for every possible state, which becomes
impractical for many applications. [108] has shown how
expectation maximisation (EM) can be used to build modelsof the user behaviour, although the method requires the user’s
goal in the dialogue to remain constant. This is an unsuitable
assumption for many real-world dialogues. Nevertheless, approaches based on EM have the major benefit that they do not
require annotations of the dialogue state.
B. Expectation propagation
Another algorithm that has been applied to learning theparameters of a spoken dialogue system is expectation propagation [109], [110]. This algorithm operates directly on afactored Bayesian network and simply extends the loopy belief
propagation algorithm to handle continuous state spaces. This
allows the parameters to be updated during the propagation
step and means that all the conditional independence assumptions are used in simplifying the update. This approach has
been used to learn the goal evolution parameters of a relatively
large tourist information system [111]. The main advantageof this approach is that it requires no annotations of either
the true semantics or the dialogue state. This means thatparameters can be improved with each dialogue without any
extra supervision.
C. Reinforcement learning
All of the above approaches are motivated by the objectiveof designing a dialogue model that captures the essential
elements of the user’s behaviour. An alternative would be toview the dialogue model as just another set of parameters that
influence the total reward earned by the system. Hence, thetask of the parameter optimisation changes from an inference
problem to a reinforcement learning task. Although this meansthat the parameters are no longer probabilities in the usual
sense, the final aim of the system is to maximise its performance and this approach directly optimises this metric.
One algorithm that has been proposed for this purpose
is an extension of the natural actor critic (NAC) algorithm
discussed in section IV called by analogy “natural belief critic(NBC)” [112]. This algorithm replaces the parameters of thepolicy that would usually be learned, with the parameters of
the user model, denoted τ . This is not entirely straightforward
because the reward is not differentiable with respect to τ .
However, if the τ parameters are fitted with Dirichlet priors,then the priors are differentiable. Hence, the priors can be
optimised using natural gradient ascent, and the required τparameters can then be obtained by sampling the optimised
priors. The NBC algorithm can be further extended to optimise
both the policy and the user model parameters at the sametime. Experiments have shown that policies optimised bythis joint “natural actor and belief critic (NABC)” algorithm

PROC IEEE, VOL. 101, NO. 5, 1160-1179, 201311

outperform policies trained solely with the natural actor critic
algorithm [70].
VII. FAST TRAINING AND USER ADAPTATIONAs noted in section IV, policy optimisation for a realworld spoken dialogue system takes an order of O(105 )training dialogues. This is too large for the policy to be
trained in direct interaction with human users and hence, as
discussed in section V, policy optimisation currently relies
on interaction with user simulators. These simulators requirea high level of sophistication and are not trivial to build.
Moreover, the policies trained with simulated users are biased
towards the particular behaviour that these models incorporate.
It is desirable therefore to speed up policy optimisation so thatpolicies can be trained with or adapted to real users.
A second issue with standard policy optimisation techniques
is that they do not provide a measure of certainty in theestimates. As dialogue systems become more complex it will
be important to convey to the user the system’s confidence
level. When the system is uncertain, then it needs to signal
to the user that it is uncertain. More pragmatically, knowing
the level of uncertainty in the various regions of belief-action
space will assist learning algorithms to explore parts of thespace it is uncertain about instead of exploring randomly.
A final issue concerns the inherent approximation introduced by parameterising the policy. As described in IV, typically a set of feature functions are chosen and then parameters
are optimised with respect to the chosen features. To beeffective, the feature functions must be carefully hand-craftedand even then the result will be suboptimal.
One method that has been recently applied to spoken
dialogue systems to address these issues is Gaussian processbased reinforcement learning, which allows a policy model
P to be defined and optimised in a non-parametric manner4 .
A Gaussian process (GP) is a generative model of Bayesianinference that can be used for function regression [113]. A GP
is specified by a mean and a kernel function, which definesprior function correlations and is crucial for obtaining good
estimates with just a few observations.
As with the Value Iteration and Monte Carlo methods
described in section IV, the GP approach represents the policy
via the Q-function (see (9)). However, unlike those methods,
it does not require discretisation of belief space. Furthermore,
given a suitable kernel, it can operate both in summary belief
space and in the full master belief space.5
Current research on using GP for dialogue systems isfocussed on the GP-Sarsa algorithm [114], which models the
Q-function as a zero mean Gaussian process
Q(b, a) ∼ GP (0, k((b, a), (b, a)))(27)

where k((b, a), (b, a)) is a kernel representing the correlations
in belief-action space (b, a).
The posterior of the Gaussian process provides not only themean estimate of the Q-function but also the variance, which
4 Here non-parametric does not mean parameter-free but rather that the
choice of parameters does not restrict the solution.
5 Hence in this section, master and summary space are not distinguished.

gives an estimate of the uncertainty in the approximation. In
online algorithms, this estimate of the uncertainly can be used
for more efficient exploration, either via an active learningmodel or by defining a stochastic policy model, both of whichhave been shown to speed up the process of learning [115].
The GP-Sarsa algorithm can be used to estimate the Qfunction for real-world problems [116], [115]. It has beenshown to optimise dialogue policies faster then a standard
reinforcement learning algorithm [117] and it has been used tosuccessfully train a dialogue policy in direct interaction withhuman users [118].
GP-Sarsa is an on-line on-policy algorithm in that it learns
by interaction, taking actions according to the same policythat it is optimising. While on-policy methods guarantee thatthe overall reward acquired during the optimisation process
is maximised, off-policy methods guarantee that a particularpolicy behaviour is followed during the process of optimisation. Off-policy sample-efficient methods have been exploredin the context of parametric optimisation using the frameworkof Kalman temporal differences [119]. On-line off-policy
learning typically uses a form of Q-learning that exploits the
Bellman equation
0Q(b, a)=E rt+1 +γ max
Q(b
,
a
)|b
=
b,
a
=
a
(28)
t+1
t
t
0
a ∈A

whose maximisation requires a non-linear parametrisation of
the Q-function. The KTD-Q algorithm is a sample efficientalgorithm that assumes a non-linear parametrisation of the Qfunction and optimises the parameters using Kalman filtering [120]. Similar to GP-Sarsa, this algorithm also provides
a measure of the uncertainty of the approximation that canbe used for more efficient policy optimisation [120]. Thisalgorithm has been successfully applied to dialogue policy
optimisation and shown to perform significantly faster thanstandard off-policy methods such as LSPI [121], [44].
VIII. S YSTEMS AND A PPLICATIONS
The preceding sections of this review provide an outline of
the core components of a statistical dialogue system. It will
be apparent that these systems are complex and the techniques
are being continually refined. Whilst commercial deployment
is probably still some way off, several working systems havebeen built in a number of application areas. This section
provides some specific examples of dialogue systems andapplications that have been implemented within the POMDP
framework.
Most of the systems implemented to date have been information inquiry applications. These include: voice dialling[122], tourist information [42], [28], appointment scheduling[123], and car navigation [24]. Command-and-control applications have also been demonstrated, such as control of devices
and services in the home via a multi-modal interface [124].
Another class of application is the troubleshooting domain,which is an interesting example of planning for uncertainty
where the observation space of the POMDP can be extended
to include non-speech variables such as the state of a modem
and the actions can include the invocation of test signals in
addition to verbal responses [125].

PROC IEEE, VOL. 101, NO. 5, 1160-1179, 2013

IX. E VALUATION AND P ERFORMANCE
Whilst methods for evaluation of most data-driven tasks
in speech and natural language processing are wellestablished [127], evaluating a spoken dialogue system requires interaction with users and is therefore difficult [128].
Moreover, a spoken dialogue system consists of distinct modules and although there are well-defined evaluation metrics
for most of them individually, joint evaluation of the complete
system is challenging. Ultimately the goal is usually to provide
user satisfaction, but this is hard to measure and is anyway
really only appropriate for real users with real needs. Testinga system by giving paid subjects artificial goals will inevitably
create biases and even then it is difficult to recruit sufficient
subjects to achieve statistical significance for each contrast
condition tested. Given these problems, evaluation of SDS
typically falls into one of 3 testing regimes: testing with someform of simulated user, testing with paid subjects and testing
within a live deployed system.
There are no standardised measures for dialogue manager evaluation. However, the PARADISE framework [129]suggests the general approach of predicting user satisfaction
ratings using a corpus of dialogues annotated with user satisfaction ratings and a set of objective measures. It defines
the dialogue manager performance as a weighted function of
the dialogue success and dialogue-based cost measures suchas the dialogue length or the number of times the systemproduced a confirmation. The weights can be inferred fromthe annotated corpus using regression, and this regression
can then be used as the reward function in reinforcement
learning [130], [131]. Whilst this enables a large number ofobjective measures to be considered, in practice the dialogue
success rate and the dialogue length are typically the mostimportant predictors. Hence, most statistical dialogue systems
are trained to maximise success whilst minimising the lengthof the dialogue.
The simplest and most efficient test regime is to use asimulated user. This enables wide coverage of the spaceof possible dialogues, with a variety of scenarios and theability to vary the effective recognition error rates over awide range [132], [133], [134]. An obvious disadvantage, ofcourse, is the potential discrepancy between the behaviour ofa simulated user and the behaviour of real users. Nevertheless,user simulation has been a very common way to evaluate
different POMDP approaches [125], [28].
As an illustration, Fig. 6 reproduces the results from [28].
Three different dialogue managers were evaluated with asimulated user at varying noise levels. These were a handcrafted deterministic dialogue manager that takes only themost likely input from the simulated user (HDC), the BUDS
dialogue manager (Section III-B) with a hand-coded policy(BUDS-HDC) and the BUDS dialogue manager with a policy
trained using NAC (BUDS-TRA) (Section IV-E). The systems
operate in a tourist information domain, where the users
may ask about hotels, restaurants, bars and amenities in a
fictitious town. The reward function is defined as 20 for a
successful dialogue minus the dialogue length6 . The confusion
rate is defined as the probability of a semantic concept from ahypothesis passed to the dialogue manager being incorrect. A
dialogue is successful if a suitable venue was offered and all
further pieces of information were given. The results in Fig. 6highlight some important features of the different managers.
Firstly, at low error rates all managers perform equally well,
but at higher error rates the BUDS systems are clearly morerobust to noise. By using belief tracking, the BUDS dialogue
manager is better able to handle conflicting evidence fromdifferent dialogue turns. Secondly, the BUDS manager withthe trained policy gives further improvement compared to the
BUDS system with a handcrafted policy, indicating that policy
optimisation via reinforcement learning is effective.
15.00

BUDS-TRABUDS-HDC

14.00

13.00

12.00

Mean reward

POMDP-systems have also been demonstrated in the “Let’s
Go” challenge run by Carnegie Mellon University, which involves providing live out-of-hours bus information to residents
in the Pittsburgh area [34], [126]. This application must deal
with casual callers using a variety of mobile phones, often
in noisy environments. When success rates were plotted as afunction of word error rate, the POMDP-based systems consistently outperformed the conventional baseline system [8].

12

11.00

10.00

HDC

9.00

8.00

7.00

6.00
0

5

10

15

20

25

30

35

40

45

50

Confusion rate (e)Fig. 6. Comparison between the BUDS POMDP-based dialogue manager
with a hand-crafted policy (BUDS-HDC) and a trained policy (BUDS-TRA),
and a conventional hand-crafted deterministic dialogue manager (HDC) as afunction of simulated confusion rate. Each point gives the mean reward for5000 simulated dialogues. Error bars show one standard error on each sideof the mean. Taken from [28].

The second commonly used evaluation regime is to recruit
human subjects to test the systems, with the aim of providing
more realistic dialogues. Until recently, this has typically been
done in a laboratory setting, where paid subjects are given
predefined tasks, instructed to talk to the system in a particular
way and then asked to rate the dialogues. For example, systems
using the POMDP approach have been evaluated in this way
and improvements have been demonstrated relative to handcoded or MDP baselines [49], [135], [28]. Setting aside theissue of how representative paid subjects are of real users,a major problem with this approach is the difficulty andexpense of recruiting sufficient subjects. The recent emergenceof crowd-sourcing and the ability to transport audio with
6 This is equivalent to giving a reward of -1 in all non-terminal states and+20 in all terminal states which denote success.

X. H ISTORICAL P ERSPECTIVE
The first reference to the use of POMDPs in spoken dialoguesystems is thought to be Roy et al in 2000 [9] and Zhang
et al in 2001 [138]. However, some of the key ideas werebeing explored before then. The idea of viewing dialogue
management as an observable Markov decision process (MDP)
and optimising a policy via reinforcement learning is due to
Levin and Pieraccini [139], [140]. This work was quickly
developed by others [141], [131], [142], [143], [144], [145],[45], [146], [147], [148], [49], [48], [50], [149], [150], [46],[151], [152], [51]. However, the use of MDP approaches lost
momentum as it became apparent that the lack of any explicit

0.8
0.6

Sys4

0.4

Sys3

Sys1

0.0

0.2

Success

minimal latency over the internet, has greatly mitigated thisproblem. For example, in [136] the Amazon Mechanical Turk
service was used to recruit subjects and provide them withpredefined tasks and basic instructions. Subjects then called
the dialogue system via a toll-free telephone number andprovided feedback after each dialogue. This now provides
an effective way of collecting a large number of humancomputer dialogues in order to achieve statistically significant
results [137]. However, the use of crowd-sourcing does notaddress the issue of how representative paid subjects are of
real users. Indeed, without the ability to monitor subjects ina laboratory setting, the problems of motivation and attention
are exacerbated. Furthermore, there is evidence to suggest that
crowd-sourced subjects do not rate their dialogue experienceaccurately [118].
The final evaluation regime is to test systems in the fieldwith real users. This normally requires partnership with acommercial provider or the setting up of a service that the
public are naturally motivated to use. Neither of these iseasy to arrange and as a response to this problem Carnegie
Melon University (CMU) have set up an evaluation framework
called the Spoken Dialogue System Challenge. This utilises
a live service for providing bus information for Pittsburgh,
Pennsylvania where users are able to call the system andask for bus information. This service has been provided forsome years using human agents during office hours, and byproviding a fully automated out-of-hours service, a genuineuser demand has been created which by default is serviced
by a baseline spoken dialogue system designed by CMU but
which can be substituted by other systems for testing. As an
example, in the 2010 challenge a number of systems were
tested, first by a cohort of students to ensure that the systems
were sufficiently robust to put before the public and then they
were tested in the live service. Two of those tested were basedon the POMDP framework.
The summary results are shown in Fig. 7 from [8], where thelogistic regression of dialogue success was computed against
word error rate (WER) for each of the systems. It can beseen that the hand-coded baseline system ”sys1” is slightly
better at low error rates which was to be expected given thelong period of development and refinement of that system.
However despite the very short development times of the othertwo POMDP-based systems, both were more robust on highnoise levels than the hand-coded baseline system.

13

1.0

PROC IEEE, VOL. 101, NO. 5, 1160-1179, 2013

0

20

40

60

80

100

WER

Fig. 7. Logistic regression of dialogue success vs word error rate (WER)
for the three systems subjected to live testing in the 2010 Spoken Dialogue
Challenge. Sys3 and Sys4 were POMDP-based systems and Sys 1 was a
hand-coded system. Taken from [8].

model of uncertainty was limiting performance, and although
the generalisation to POMDPs was known, their use appeared
to be intractable for real-world systems. The first reference
to the need for an explicit representation of uncertainty indialogue is believed to be Pulman in 1996 who proposedmodelling dialogue as a conversational game [153]. Soon after
Heckerman; Horvitz and Paek; and Meng, Wai and Pieraccini
showed how Bayesian networks could be used to provide morerobust conversational structures [154], [155], [156].
XI. C ONCLUSIONS
The development of statistical dialogue systems has been
motivated by the need for a data-driven framework that reduces the cost of laboriously hand-crafting complex dialogue
managers and which provides robustness against the errors
created by speech recognisers operating in noisy environments.
By providing an explicit Bayesian model of uncertainty andby providing a reward-driven process for policy optimisation,
POMDPs provide such a framework.
However, as will be clear from this review, POMDP-based
dialogue systems are complex and involve approximations andtrade-offs. Good progress has been made but there is still muchto do. There are many challenges, most of which have been
touched upon in this review such as finding ways to increase
the complexity of the dialogue model whilst maintaining
tractable belief tracking; and reducing policy learning times
so that systems can be trained directly on real users rather
than using simulators. Down the road, there is also the taskof packaging this technology to make it widely accessible tonon-experts in the industrial community.

PROC IEEE, VOL. 101, NO. 5, 1160-1179, 2013

There are other challenges too. The POMDP framework
depends critically on the notion of rewards. In principle thisis a key benefit of the approach since it provides an objective
mechanism for specifying dialogue design criteria. However,the problem in practice is that it is very difficult to extract
reliable reward signals from users. Even the simple success/failcriterion is difficult to compute since even if asked “Did thesystem give you all that you asked for?”, many users will say“Yes” regardless just to be polite, or “No” because they had
completely unrealistic expectations of what the system cando for them. Reward functions based on user satisfaction as
predicted by a regression on objectively measurable features
such as in the PARADISE framework [129] may mitigate thisproblem and need to be explored further[130], [131]. However,much of the experience to date suggests that on-line learningwith real users will not be truly effective until robust biometrictechnology is available that enables the emotional state of theuser to be accurately measured [118]. In the meantime, there
is no shortage of further areas to develop and explore!
R EFERENCES[1] R. De Mori, Spoken Dialogues with Computers, ser. Signal Processing
and its Applications. Academic Press, 1998.
[2] R. Smith and D. Hipp, Spoken Natural Language Dialog Systems: A
Practical Approach. Oxford University Press, 1994.
[3] V. Zue and J. Glass, “Conversational Interfaces: Advances and Challenges,” Proc IEEE, vol. 88, no. 8, pp. 1166–1180, 2000.
[4] S. Young, “Cognitive User Interfaces,” Signal Processing Magazine,
vol. 27, no. 3, pp. 128–140, 2010.
[5] M. Oshry, P. Baggia, K. Rehor, M. Young, R. Akolkar, X. Yang, J. Barnett, R. Hosn, R. Auburn, J. Carter, S. McGlashan, M. Bodell, and D. C.
Burnett, “Voice extensible markup language (VoiceXML) 3.0,” W3C,W3C Working Draft, Dec. 2009, http://www.w3.org/TR/2009/WDvoicexml30-20091203/.
[6] T. Paek and R. Pieraccini, “Automating Spoken Dialogue Management
Design Using Machine Learning: An Industry Perspective,” Speechcommunication, vol. 50, no. 8-9, pp. 716–729, 2008.
[7] R. P. Lippmann, “Speech recognition by machines and humans,” Speechcommunication, vol. 22, no. 1, pp. 1–15, 1997.
[8] A. Black, S. Burger, A. Conkie, H. Hastie, S. Keizer, O. Lemon,
N. Merigaud, G. Parent, G. Schubiner, B. Thomson, J. Williams, K. Yu,
S. Young, and M. Eskenazi, “Spoken dialog challenge 2010: Comparison of live and control test results,” in Proceedings of SIGDIAL,
Portland, Oregon, 2011, pp. 2–7.
[9] N. Roy, J. Pineau, and S. Thrun, “Spoken Dialogue Management Using
Probabilistic Reasoning,” in Proceedings of ACL, Hong Kong, 2000,
pp. 93–100.
[10] S. Young, “Talking to Machines (Statistically Speaking),” in Proceedings of ICSLP, Denver, Colorado, 2002.
[11] J. Williams and S. Young, “Partially Observable Markov Decision Processes for Spoken Dialog Systems,” Computer Speech and Language,
vol. 21, no. 2, pp. 393–422, 2007.
[12] L. Kaelbling, M. Littman, and A. Cassandra, “Planning and acting
in partially observable stochastic domains,” Artificial Intelligence, vol.
101, pp. 99–134, 1998.
[13] E. Hansen, “Solving POMDPs by searching in policy space,” inProceedings of UAI, Madison, Wisconsin, 1998, pp. 211–219.
[14] M. L. Littman, R. S. Sutton, and S. Singh, “Predictive representationsof state,” in Proceedings of NIPS, 2002, pp. 1555–1561.
[15] R. E. Bellman, Dynamic Programming. Princeton University Press,
Princeton, NJ, 1957.
[16] J. Pineau, G. Gordon, and S. Thrun, “Point-based value iteration: An
anytime algorithm for POMDPs,” in Proceedings of IJCAI, Acapulco,
Mexico, 2003, pp. 1025–1032.
[17] T. Smith and R. G. Simmons, “Heuristic search value iteration for
POMDPs,” in Proceedings of UAI, Banff, Canada, 2004, pp. 520–527.
[18] M. Spaan and N. Vlassis, “Perseus: randomized point-based value
iteration for POMDPs,” Journal of Artificial Intelligence Research,
vol. 24, pp. 195–220, 2005.

14[19] T. Smith and R. Simmons, “Point-based pomdp algorithms: Improved
analysis and implementation,” in Proceedings of the Twenty-First
Conference Annual Conference on Uncertainty in Artificial Intelligence(UAI-05). Arlington, Virginia: AUAI Press, 2005, pp. 542–549.
[20] S. Ji, R. Parr, H. Li, X. Liao, and L. Carin, “Point-based policy
iteration,” in Proceedings of AAAI, Vancouver, Canada, 2007, pp. 1243–
1249.
[21] J. Williams, P. Poupart, and S. Young, “Factored Partially Observable
Markov Decision Processes for Dialogue Management,” in Proceedingsof the IJCAI Workshop on Knowledge and Reasoning in Practical
Dialog Systems, Edinburgh, United Kingdom, 2005, pp. 76–82.
[22] T. Bui, M. Poel, A. Nijholt, and J. Zwiers, “A tractable hybrid
DDN-POMDP approach to affective dialogue modeling for probabilistic frame-based dialogue systems,” Natural Language Engineering,
vol. 15, no. 2, pp. 273–307, 2009.
[23] S. Young, J. Schatzmann, K. Weilhammer, and H. Ye, “The Hidden
Information State Approach to Dialog Management,” in Proceedingsof ICASSP, Honolulu, Hawaii, 2007, pp. 149–152.
[24] K. Kim, C. Lee, S. Jung, and G. Lee, “A Frame-Based Probabilistic
Framework for Spoken Dialog Management Using Dialog Examples,”in Proceedings of SIGDIAL, Columbus, Ohio, 2008, pp. 120–127.
[25] J. Williams, “Incremental Partition Recombination for Efficient Tracking of Multiple Dialogue States.” in Proceedings of ICASSP, Dallas,
Texas, 2010, pp. 5382–5385.
[26] M. Gašić and S. Young, “Effective Handling of Dialogue State in
the Hidden Information State POMDP Dialogue Manager,” ACM
Transactions on Speech and Language Processing, vol. 7, no. 3, 2011.
[27] B. Thomson, J. Schatzmann, and S. Young, “Bayesian Update of
Dialogue State for Robust Dialogue Systems,” in Proceedings of
ICASSP, Las Vegas, Nevada, 2008, pp. 4937 – 4940.
[28] B. Thomson and S. Young, “Bayesian update of dialogue state: A
POMDP framework for spoken dialogue systems,” Computer Speechand Language, vol. 24, no. 4, pp. 562–588, 2010.
[29] J. Henderson and O. Lemon, “Mixture model POMDPs for efficient
handling of uncertainty in dialogue management,” in Proceedings of
ACL, Columbus, Ohio, 2008, pp. 73–76.
[30] D. Bohus and A. Rudnicky, “A ‘K hypotheses + other’ belief updating
model,” in Proceedigns of the AAAI Workshop on Statistical and Empirical Approaches for Spoken Dialogue Systems, Boston, Massachusetts,
2006, p. 1318.
[31] R. Higashinaka, M. Nakano, and K. Aikawa, “Corpus-based discourse
understanding in spoken dialogue systems,” in Proceedings of ACL,
Sapporo, Japan, 2003, pp. 240–247.
[32] C. Bishop, Pattern Recognition and Machine Learning. Springer,
2006.
[33] J. D. Williams, “Using particle filters to track dialogue state,” inProceedings of ASRU, Kyoto, Japan, 2007, pp. 502 – 507.
[34] B. Thomson, K. Yu, S. Keizer, M. Gasic, F. Jurcicek, F. Mairesse,and S. Young, “Bayesian Dialogue System for the Let’s Go Spoken
Dialogue Challenge,” in Proceedings of SLT, Berkeley, California,
2010, pp. 460–465.
[35] P. A. Crook and O. Lemon, “Lossless value directed compression ofcomplex user goal states for statistical spoken dialogue systems,” inProceedings of Interspeech, Florence, Italy, 2011, pp. 1029–1032.
[36] F. Doshi and N. Roy, “The permutable pomdp: fast solutions to pomdps
for preference elicitation,” in Proceedings of the international joint
conference on autonomous agents and multiagent systems, 2008, pp.
493–500.
[37] J. Williams and S. Young, “Scaling up POMDPs for dialog management: The “summary POMDP” method,” in Proceedings of ASRU,
Cancun, Mexico, 2005, pp. 177–182.
[38] ——, “Scaling POMDPs for spoken dialog management,” IEEE Transactions on Audio, Speech, and Language Processing, vol. 15, no. 7,
pp. 2116–2129, 2007.
[39] D. Andre and S. Russell, “State abstraction for programmable reinforcement learning agents,” in Proceedings of AAAI, Edmonton,
Alberta, 2002, pp. 119–125.
[40] J. D. Williams, “The best of both worlds: Unifying conventional
dialog systems and POMDPs,” in Proceedings of Interspeech, Brisbane,
Australia, 2008, pp. 1173–1176.
[41] P. Lison, “Towards Relational POMDPs for Adaptive Dialogue Management,” in Proceedings of the ACL Student Research Workshop.
Uppsala, Sweden: Association for Computational Linguistics, 2010,
pp. 7–12.
[42] S. Young, M. Gašić, S. Keizer, F. Mairesse, J. Schatzmann, B. Thomson, and K. Yu, “The Hidden Information State Model: a practical

PROC IEEE, VOL. 101, NO. 5, 1160-1179, 2013

framework for POMDP-based spoken dialogue management,” Computer Speech and Language, vol. 24, no. 2, pp. 150–174, 2010.
[43] L. Li, J. D. Williams, and S. Balakrishnan, “Reinforcement learning for
dialog management using least-squares policy iteration and fast feature
selection,” in Proceedings of Interspeech, Brighton, United Kingdom,
2009, pp. 2475–2478.
[44] O. Pietquin, M. Geist, S. Chandramohan, and H. Frezza-Buet, “Sampleefficient batch reinforcement learning for dialogue management optimization,” ACM Transactions on Speech and Language Processing,vol. 7, no. 3, pp. 1–21, 2011.
[45] K. Scheffler and S. Young, “Automatic Learning of Dialogue Strategy
using Dialogue Simulation and Reinforcement Learning,” in Proceedings of HLT, San Diego, California, 2002, pp. 12–19.
[46] H. Cuayáhuitl, S. Renals, O. Lemon, and H. Shimodaira, “Reinforcement learning of dialogue strategies with hierarchical abstract
machines,” in Proceedings of SLT, Aruba, 2006, pp. 182–185.
[47] H. Cuayáhuitl, S. Renals, and O. Lemon, “Learning multi-goal dialogue strategies using reinforcement learning with reduced state-action
spaces,” in Proceedings of Interspeech, Pittsburgh, Pennsylvania, 2006.
[48] O. Pietquin and T. Dutoit, “A probabilistic framework for dialog
simulation and optimal strategy learning,” IEEE Transactions on Audio,
Speech, and Language Processing, vol. 14, no. 2, pp. 589–599, 2006.
[49] J. Henderson, O. Lemon, and K. Georgila, “Hybrid reinforcement/supervised learning for dialogue policies from Communicator
data,” in Proceedings of the IJCAI Workshop on Knowledge andReasoning in Practical Dialog Systems, Edinburgh, United Kingdom,
2005, pp. 68–75.
[50] M. Frampton and O. Lemon, “Learning more effective dialogue strategies using limited dialogue move features,” in Proceedings of ACL,
Sydney, Australia, 2006, pp. 185–192.
[51] J. Henderson, O. Lemon, and K. Georgila, “Hybrid reinforcement /supervised learning of dialogue policies from fixed datasets,” Computational Linguistics, vol. 34, no. 4, 2008.
[52] H. Kurniawati, D. Hsu, and W. Lee, “SARSOP: efficient point-based
POMDP planning by approximating optimally reachable belief spaces,”in Proceedings of Robotics: Science and Systems, 2008.
[53] T. H. Bui, M. Poel, A. Nijholt, and J. Zwiers, “A tractable DDNPOMDP approach to affective dialogue modeling for general probabilistic frame-based dialogue systems,” in Proceedings of the IJCAIWorkshop on Knowledge and Reasoning in Practical Dialog Systems,
Hyderabad, India, 2007, pp. 34–37.
[54] T. H. Bui, B. W. van Schooten, and D. H. W. Hofs, “Practical dialogue
manager development using POMDPs,” in Proceedings of SIGDIAL,
Antwerp, Belgium, 2007, pp. 215–218.
[55] F. Pinault, F. Lefevre, and R. D. Mori, “Feature-based summary spacefor stochastic dialogue modeling with hierarchical semantic frames,”in Proceedings of Interspeech, Brighton, United Kingdom, 2009, pp.
284–287.
[56] A. Boularias, H. R. Chinaei, and B. Chaib-draa, “Learning the reward
model of dialogue pomdps from data,” in NIPS Workshop on Machine
Learning for Assistive Techniques, 2010.
[57] F. Pinault and F. Lefevre, “Semantic graph clustering for POMDPbased spoken dialog systems,” in Proceedings of Interspeech, Florence,
Italy, 2011, pp. 1321–1324.
[58] ——, “Unsupervised clustering of probability distributions of semantic
frame graphs for pomdp-based spoken dialogue systems with summary
space,” in Proceedings of the IJCAI Workshop on Knowledge andReasoning in Practical Dialog Systems, Barcelona, Spain, 2011.
[59] H. R. Chinaei and B. Chaib-draa, “Learning dialogue pomdp models
from data,” in Canadian Conference on Artificial Intelligence, 2011,
pp. 86–91.
[60] H. R. Chinaei, B. Chaib-draa, and L. Lamontagne, “Learning observation models for dialogue pomdps,” in Canadian Conference on
Artificial Intelligence, 2012.
[61] S. Varges, G. Riccardi, S. Quarteroni, and A. Ivanov, “POMDP
concept policies and task structures for hybrid dialog management,”in Proceedings of ICASSP, Prague, Czech Republic, 2011, pp. 5592 –
5595.
[62] J. D. Williams, “Integrating expert knowledge into POMDP optimization for spoken dialog systems,” in Proceedings of the AAAI Workshop
on Advancements in POMDP Solvers, Chicago, Chicago, Illinois, 2008.
[63] R. Sutton and A. Barto, Reinforcement Learning: An Introduction,
ser. Adaptive Computation and Machine Learning.
Cambridge,
Massachusetts: MIT Press, 1998.
[64] F. Lefevre, M. Gasic, F. Jurcicek, S. Keizer, F. Mairesse, B. Thomson,
K. Yu, and S. J. Young, “k-nearest neighbor monte-carlo control algo-15rithm for pomdp-based dialogue systems,” in Proceedings of SIGDIAL,
London, United Kingdom, 2009.
[65] M. G. Lagoudakis and R. Parr, “Least-squares policy iteration,” Journalof Machine Learning Research, no. 4, pp. 1107–1149, 2003.
[66] R. J. Williams, “Simple statistical gradient-following algorithms forconnectionist reinforcement learning,” Machine Learning, vol. 8, 1992.
[67] S. Amari, “Natural gradient works efficiently in learning,” NeuralComputation, vol. 10, no. 2, pp. 251–276, 1998.
[68] J. Peters and S. Schaal, “Natural Actor-Critic,” Neurocomputing,vol. 71, no. 7-9, pp. 1180–1190, 2008.
[69] T. Misu, “Dialogue strategy optimization to assist user’s decision for
spoken consulting dialogue systems,” in Proceedings of SLT, Berkeley,
California, 2010, pp. 354 – 359.
[70] F. Jurčı́ček, B. Thomson, and S. Young, “Natural Actor and Belief
Critic: Reinforcement algorithm for learning parameters of dialoguesystems modelled as POMDPs,” ACM Transactions on Speech andLanguage Processing, vol. 7, no. 3, 2011.
[71] T. Misu, K. Sugiura, K. Ohtake, and C. Hori, “Modeling spoken
decision making dialogue and optimization of its dialogue strategy,”in Proceedings of SIGDIAL, Portland, Oregon, 2011, pp. 221–224.
[72] T. Misu, K. Georgila, A. Leuski, and D. Traum, “Reinforcement
learning of question-answering dialogue policies for virtual museum
guides,” in Proceedings of SIGDIAL, Seoul, South Korea, 2012, pp.
84–93.
[73] J. Schatzmann, K. Weilhammer, M. Stuttle, and S. Young, “A surveyof statistical user simulation techniques for reinforcement-learning of
dialogue management strategies,” The knowledge engineering review,
vol. 21, no. 2, pp. 97–126, Jun. 2006.
[74] H. Hastie, “Metrics and evaluation of spoken dialogue systems,” inData-Driven Methods for Adaptive Spoken Dialogue Systems: Computational Learning for Conversational Interfaces. Springer, 2012.
[75] O. Pietquin and H. Hastie, “A survey on metrics for the evaluation ofuser simulations,” The knowledge engineering review, 2011.
[76] J. Schatzmann, K. Georgila, and S. Young, “Quantitative Evaluationof User Simulation Techniques for Spoken Dialogue Systems,” inProceedings of SIGDIAL, Lisbon, Portugal, 2005, pp. 45–54.
[77] J. Williams, “Evaluating user simulations with the Cramervon Mises
divergence,” Speech communication, vol. 50, pp. 829–846, 2008.
[78] W. Eckert, E. Levin, and R. Pieraccini, “User Modelling for Spoken
Dialogue System Evaluation,” in Proceedings of ASRU, Santa Barbara,
California, 1997, pp. 80–87.
[79] K. Georgila, J. Henderson, and O. Lemon, “Learning user simulations
for information state update dilaogue systems,” in Proceedings ofInterspeech, Lisbon, Portugal, 2005, pp. 893–896.
[80] ——, “User Simulation for Spoken Dialogue Systems: Learning and
Evaluation,” in Proceedings of ICSLP, Pittsburgh, Pennsylvania, 2006,
pp. 45–54.
[81] K. Scheffler and S. Young, “Probabilistic simulation of human-machinedialogues,” in Proceedings of ICASSP, Istanbul, Turkey, 2000, pp.
1217–1220.
[82] V. Rieser and O. Lemon, “Cluster-based user simulations for learning
dialogue strategies,” in Proceedings of Interspeech, Pittsburgh, Pennsylvania, 2006.
[83] O. Pietquin, “Consistent goal-directed user model for realistic manmachine task-oriented spoken dialogue simulation,” in IEEE International Conference on Multimedia and Expo, Toronto, Canada, 2006,
pp. 425 – 428.
[84] J. Schatzmann, B. Thomson, K. Weilhammer, H. Ye, and S. Young,“Agenda-Based User Simulation for Bootstrapping a POMDP Dialogue
System,” in Proceedings of HLT/NAACL, Rochester, New York, 2007,
pp. 149–152.
[85] H. Ai and D. J. Litman, “Knowledge consistent user simulations for
dialog systems,” in Proceedings of Interspeech, Antwerp, Belgium,
2007, pp. 2697–2700.
[86] J. Schatzmann and S. Young, “The Hidden Agenda User Simulation
Model,” IEEE Transactions on Audio, Speech, and Language Processing, vol. 17, no. 4, pp. 733–747, 2009.
[87] S. Keizer, M. Gasic, F. Jurcicek, F. Mairesse, B. Thomson, K. Yu, andS. Young, “Parameter estimation for agenda-based user simulation,” inProceedings of SIGDIAL, Tokyo, Japan, 2010, pp. 116–123.
[88] O. Pietquin, A Framework for Unsupervised Learning of Dialogue
Strategies, ser. SIMILAR Collection.
Presses Universitaires deLouvain, 2004.
[89] H. Cuayahuitl, S. Renals, O. Lemon, and H. Shimodaira, “HumanComputer Dialogue Simulation using Hidden Markov Models,” inProceedings of ASRU, Puerto Rico, 2005, pp. 290–295.

PROC IEEE, VOL. 101, NO. 5, 1160-1179, 2013[90] H. Cuayáhuitl, S. Renals, O. Lemon, and H. Shimodaira, “Humancomputer dialogue simulation using hidden markov models,” in Proceedings of ASRU, Cancun, Mexico, 2005, pp. 290–295.
[91] O. Pietquin and T. Dutoit, “A Probabilistic Framework for Dialog
Simulation and Optimal Strategy Learning,” IEEE Transactions on
Audio, Speech, and Language Processing, vol. 14, no. 2, pp. 589–599,
2006.
[92] S. Rossignol, M. Ianotto, and O. Pietquin, “Training a BN-based usermodel for dialogue simulation with missing data,” in Proceedings of
IJCNLP. Chiang Mai, Thailand: ACLWeb, November 2011, pp. 598–604.
[93] S. Jung, C. Lee, K. Kim, M. Jeong, and G. G. Lee, “Data-driven
user simulation for automated evaluation of spoken dialog systems,”
Computer Speech and Language, vol. 23, no. 4, pp. 479 – 509, 2009.
[94] A. Ng and S. Russell, “Algorithms for inverse reinforcement learning,”
in Proceedings of ICML. Stanford, California: Morgan Kaufmann,
2000, pp. 663–670.
[95] S. Chandramohan, M. Geist, F. Lefevre, and O. Pietquin, “User Simulation in Dialogue Systems using Inverse Reinforcement Learning,” inProceedings of Interspeech, Florence, Italy, 2011, pp. 1025–1028.
[96] O. Pietquin and S. Renals, “ASR System Modelling for Automatic
Evaluation and Optimisation of Dialogue Systems,” in Proceedings of
ICASSP, Orlando, Florida, 2002, pp. 46–49.
[97] O. Pietquin and R. Beaufort, “Comparing asr modeling methods for
spoken dialogue simulation and optimal strategy learning,” in Proceedings of Interspeech, Lisbon, Portugal, 2005, pp. 861–864.
[98] O. Pietquin and T. Dutoit, “Dynamic bayesian networks for nlu
simulation with application to dialog optimal strategy learning,” inProceedings of ICASSP, Toulouse, France, 2006, pp. 49–52.
[99] J. Schatzmann, B. Thomson, and S. Young, “Error Simulation forTraining Statistical Dialogue Systems,” in Proceedings of ASRU, Kyoto,
Japan, 2007, pp. 526– 531.
[100] F. Garcı́a, L. F. Hurtado, D. Griol, M. J. Castro, E. Segarra, and
E. Sanchis, “Recognition and understanding simulation for a spoken
dialog corpus acquisition,” in Proceedings Text, Speech and Dialogue,
2007, pp. 574–581.
[101] B. Thomson, K. Yu, M. Gasic, S. Keizer, F. Mairesse, J. Schatzmann,and S. Young, “Evaluating Semantic-level Confidence Scores with Multiple Hypotheses,” in Proceedings of Interspeech, Brisbane, Australia,
2008, pp. 1153–1156.
[102] J. Schatzmann, K. Weilhammer, M. Stuttle, and S. Young, “Effects of
the User Model on Simulation-based Learning of Dialogue Strategies,”in Proceedings of ASRU, Cancun, Mexico, 2005, pp. 220–225.
[103] D. L. Hua Ai, Joel Tetreault, “Comparing user simulation models for
dialog strategy learning,” in Proceedings of NAACL, Rochester, New
York, 2007, pp. 1–4.
[104] D. Kim, J. Kim, and K.-E. Kim, “Robust Performance Evaluationof POMDP-Based Dialogue Systems ,” IEEE Transactions on Audio,
Speech, and Language Processing, vol. 19, no. 4, pp. 1029–1040, 2011.
[105] J. D. Williams, “Exploiting the ASR N-Best by tracking multiple dialog
state hypotheses,” in Proceedings of Interspeech, Brisbane, Australia,
2008, pp. 191–194.
[106] S. Keizer, M. Gašić, F. Mairesse, B. Thomson, K. Yu, and S. Young,“Modelling user behaviour in the HIS-POMDP dialogue manager,” inProceedings of SLT, Goa, India, 2008, pp. 121–124.
[107] F. Doshi and N. Roy, “Spoken language interaction with model
uncertainty: an adaptive human-robot interaction system,” Connection
Science, vol. 20, no. 4, p. 299318, 2008.
[108] U. Syed and J. D. Williams, “Using automatically transcribed dialogs
to learn user models in a spoken dialog system,” Proceedings of
ACL:HLT, p. 121124, 2008.
[109] T. Minka, “Expectation Propagation for Approximate Bayesian Inference,” in Proceedings of UAI.
Seattle, Washington: MorganKaufmann, 2001, pp. 362–369.
[110] B. Thomson, F. Jurčı́ček, M. Gašić, S. Keizer, F. Mairesse, K. Yu, andS. Young, “Parameter learning for POMDP spoken dialogue models,”in Proceedings of SLT, Berkeley, California, 2010, pp. 271 – 276.
[111] B. Thomson, “Statistical methods for spoken dialogue management,”
Ph.D. dissertation, Cambridge, 2009.
[112] F. Jurčı́ček, B. Thomson, S. Keizer, F. Mairesse, M. Gašić, K. Yu, andS. Young, “Natural Belief-Critic: a reinforcement algorithm for parameter estimation in statistical spoken dialogue systems,” in Proceedingsof Interspeech. Tokyo, Japan: ISCA, 2010, pp. 90–93.
[113] C. Rasmussen and C. Williams, Gaussian Processes for Machine
Learning. Cambridge, Massachusetts: MIT Press, 2006.

16[114] E. Engel, S. Mannor, and R. Meir, “Reinforcement learning with
Gaussian processes,” in Proceedings of ICML, Bonn, Germany, 2005,
pp. 201–208.
[115] M. Gašić, “Statistical dialogue modelling,” Ph.D. dissertation, University of Cambridge, 2011.
[116] Y. Engel, “Algorithms and Representations for Reinforcement Learning,” PhD thesis, Hebrew University, 2005.
[117] M. Gašić, F. Jurčı́ček, S. Keizer, F. Mairesse, B. Thomson, K. Yu,
and S. Young, “Gaussian Processes for Fast Policy Optimisation of a
POMDP Dialogue Manager for a Real-world Task,” in Proceedings of
SIGDIAL, Tokyo, Japan, 2010, pp. 201–204.
[118] M. Gašić, F. Jurčı́ček, B. Thomson, K. Yu, and S. Young, “On-line
policy optimisation of spoken dialogue systems via live interaction
with human subjects,” in Proceedings of ASRU, Hawaii, 2011, pp. 312– 317.
[119] M. Geist, O. Pietquin, and G. Fricout, “Kalman temporal differences:
The deterministic case,” in IEEE Symposium on Adaptive Dynamic
Programming and Reinforcement Learning, 2009, pp. 185 –192.
[120] M. Geist and O. Pietquin, “Managing uncertainty within the KTD
framework,” in JMLR: Workshop and Conference Proceedings. Workshop on Active Learning and Experimental Design, 2011, pp. 157–168.
[121] O. Pietquin, M. Geist, and S. Chandramohan, “Sample efficient online learning of optimal dialogue policies with Kalman temporal
differences,” in Proceedings of IJCAI, Barcelona, Spain, 2011, pp.
1878–1883.
[122] J. Williams, “Demonstration of a POMDP voice dialer,” in Demonstration Session, Annual Meeting of the ACL, Columbus, Ohio, 2008.
[123] S. Janarthanam, H. Hastie, O. Lemon, and X. Liu, “”The day after
the day after tomorrow?” A machine learning approach to adaptive
temporal expression generation: training and evaluation with realusers,” in Proceedings of SIGDIAL, Portland, Oregon, 2011, pp. 142–
151.
[124] K. Kim and G. G. Lee, “Multimodal dialog system using hidden
information state dialog manager,” in Proceedings of the international
conference on multimodal interfaces demonstration session, Nagoya,Japan, 2007.
[125] J. Williams, “Applying POMDPs to Dialog Systems in the Troubleshooting Domain,” in Proceedings of the HLT/NAACL Workshop
on Bridging the Gap: Academic and Industrial Research in Dialog
Technology, Rochester, New York, 2007, pp. 1–8.
[126] ——, “An Empirical Evaluation of a Statistical Dialog System in PublicUse,” in Proceedings of SIGDIAL, Portland, Oregon, 2011, pp. 130–
141.
[127] L. Hirschman and H. S. Thompson, Overview of evaluation in speechand natural language processing.
New York City, New York:
Cambridge University Press, 1997, pp. 409–414.
[128] S. Gandhe and D. Traum, “An evaluation understudy for dialogue
coherence models,” in Proceedings of SIGDIAL, Columbus, Ohio,
2008, pp. 172–181.
[129] M. Walker, D. Litman, C. Kamm, and A. Abella, “Paradise: A
framework for evaluating spoken dialogue agents,” in Proceedings of
ACL, Madrid, Spain, 1997, pp. 271–280.
[130] E. Levin, R. Pieraccini, and W. Eckert, “Learning dialogue strategies
within the Markov decision process framework,” in Proceedings of
ASRU, Santa Barbara, California, 1997.
[131] S. Singh, M. Kearns, D. Litman, and M. Walker, “Reinforcement
learning for spoken dialogue systems,” in Proceedings of NIPS, 1999.
[132] T. Watambe, M. Araki, and S. Doshita, “Evaluating Dialogue Strategies
under Communication Errors Using Computer-to-Computer Simulation,” IEICE Transactions on Information and Systems, vol. E81-D, no. 9,
pp. 1025–1033, 1998.
[133] H. Ai and F. Weng, “User simulation as testing for spoken dialog
systems,” in Proceedings of SIGDIAL, Columbus, Ohio, 2008, pp. 164–
171.
[134] J. Schatzmann, “Statistical user and error modelling for spoken dialogue systems,” Ph.D. dissertation, University of Cambridge, 2008.
[135] M. Gašić, F. Lefevre, F. Jurčı́ček, S. Keizer, F. Mairesse, B. Thomson,
K. Yu, and S. Young, “Back-off Action Selection in Summary SpaceBased POMDP Dialogue Systems,” in Proceedings of ASRU, Merano,
Italy, 2009, pp. 456–461.
[136] F. Jurčı́ček, S. Keizer, M. Gašić, F. Mairesse, B. Thomson, K. Yu,
and S. Young, “Real user evaluation of spoken dialogue systems using
Amazon Mechanical Turk,” in Proceedings of Interspeech, Florence,
Italy, 2011, pp. 3061–3064.
[137] I. McGraw, C. Lee, L. Hetherington, S. Seneff, and J. Glass, “Collecting Voices from the Cloud,” in Proc. International Conference on
Language Resources and Evaluation, Malta, 2010, pp. 1576–1583.

PROC IEEE, VOL. 101, NO. 5, 1160-1179, 2013[138] B. Zhang, Q. Cai, J. Mao, E. Chang, and B. Guo, “Spoken Dialogue
Management as Planning and Acting under Uncertainty,” in Proceedings of Eurospeech, Aalborg, Denmark, 2001, pp. 2169–2172.
[139] E. Levin and R. Pieraccini, “A Stochastic Model Of ComputerHuman Interaction For Learning Dialogue Strategies,” in Proceedingsof Eurospeech, Rhodes,Greece, 1997, pp. 1883–1886.
[140] E. Levin, R. Pieraccini, and W. Eckert, “Using Markov Decision Processes For Learning Dialogue Strategies,” in Proceedings of ICASSP,
Seattle, Washington, 1998, pp. 201–204.
[141] M. Walker, J. Fromer, and S. Narayanan, “Learning Optimal Dialogue
Strategies: A Case Study of a Spoken Dialogue Agent for Email.” inProceedings of ACL/COLING 98, Montreal, Canada, 1998, pp. 1345–
1351.
[142] M. Kearns, D. Litman, and M. Walker, “Automatic Detection of Poor
Speech Recognition at the Dialogue Level,” in Proceedings of ACL,
College Park, Maryland, 1999, pp. 309–316.
[143] D. Goddeau and J. Pineau, “Fast reinforcement learning of dialog
strategies,” in Proceedings of ICASSP, Istanbul, Turkey, 2000, pp.
1233–1236.
[144] S. Young, “Probabilistic Methods in Spoken Dialogue Systems,” Philosophical Transactions of the Royal Society (Series A), vol. 358, no.
1769, pp. 1389–1402, 2000.
[145] S. Singh, D. Litman, M. Kearns, and M. Walker, “Optimizing Dialogue
Management with Reinforcement Learning: Experiments with the
NJFun System,” Journal of Artificial Intelligence Research, vol. 16,
pp. 105–133, 2002.
[146] M. Denecke, K. Dohsaka, and M. Nakano, “Learning dialogue policies
using state aggregation in reinfocement learning,” in Proceedings ofInterspeech, Jeju Island, South Korea, 2004, pp. 325–328.
[147] ——, “Fast reinforcement learning of dialogue policies using stablefunction approximation,” in Proceedings of IJCNLP, 2005, pp. 1–11.
[148] O. Pietquin, “A probabilistic description of man-machine spoken communication,” in IEEE International Conference on Multimedia andExpo, Amsterdam, The Netherlands, 2005, pp. 410 – 413.
[149] J. Tetreault and D. Litman, “Comparing the utility of state features inspoken dialogue using reinforcement learning,” in Proceedings of HLT,New York City, New York, 2006, pp. 272–279.
[150] ——, “Using reinforcement learning to build a better model of dialogue
state,” in Proceedings of EACL, Trento, Italy, 2006.
[151] P. Heeman, “Combining reinforcement learning with information-state
update rules,” in Proceedings of HLT/NAACL, Rochester, New York,2007, pp. 268–275.
[152] O. Pietquin, “Learning to ground in spoken dialogue systems,” inProceedings of ICASSP, Honolulu, Hawaii, 2007, pp. 165–168.
[153] S. Pulman, “Conversational Games, Belief Revision and Bayesian Networks,” in CLIN VII: 7th Computational Linguistics in the Netherlands
meeting, 1996.
[154] D. Heckerman and E. Horwitz, “Inferring Informational Goals from
Free-text Queries: a Bayesian Approach,” in Proceedings of UAI,
Madison, Wisconsin, 1998, pp. 230–238.
[155] E. Horvitz and T. Paek, “A Computational Architecture for Conversation,” in Proceedings of the Seventh International Conference on User
Modeling, Banff, Canada, 1999, pp. 201–210.
[156] H. Meng, C. Wai, and R. Pieraccini, “The use of belief networks for
Mixed-Initiative dialog modeling,” IEEE Transactions on Speech andAudio Processing, vol. 11, no. 6, pp. 757–773, Nov. 2003.

17

Steve Young Steve Young received a BA in Electrical Sciences from Cambridge University in 1973
and a PhD in Speech Processing in 1978. He waselected to the Chair of Information Engineering
at Cambridge University in 1994. He was a cofounder and Technical Director of Entropic Ltd from1995 until 1999 when the company was taken overby Microsoft. After a short period as an Architect
at Microsoft, he returned full-time to Cambridge
University in January 2001 where he was Headof Information Engineering until 2009 and is now
Senior Pro-Vice-Chancellor.
His research interests include speech recognition, expressive synthesis andspoken dialogue systems. He has written and edited books on software
engineering and speech processing, and he has published as author and coauthor, more than 200 papers in these areas. He is a Fellow of the UK Royal
Academy of Engineering, the IET, IEEE and RSA. He served as the senior
editor of Computer Speech and Language from 1993 to 2004, and he was
Chair of the IEEE Speech and Language Technical Committee from 2008 to
2010. He was the recipient of an IEEE Signal Processing Society TechnicalAchievement Award in 2004. He was elected a Fellow of the International
Speech Communication Association (ISCA) in 2009 and he was the recipientof the ISCA Medal in 2010 for Scientific Achievement.

Milica Gašić Milica Gašić is a Research Associate
in the Dialogue Systems Group at the Universityof Cambridge. She graduated in Computer Scienceand Mathematics from the University of Belgradein 2006. Since then she has been at the Universityof Cambridge first as an MPhil student reading
Computer Speech, Text and Internet Technology.
Subsequently, she did a PhD in Statistical Dialogue
Modelling in 2011. She has published around 20
peer-reviewed conference and journal papers in thearea of dialogue management. She served on theorganising committee for Young Researcher’s Roundtable on Spoken Dialogue
Systems in 2009.

Blaise Thomson Blaise Thomson is a Research
Fellow at St John’s College in the University ofCambridge. He obtained a Bachelors degree in Pure
Mathematics, Computer Science, Statistics and Actuarial Science at the University of Cape Town,
South Africa, before completing an MPhil at the
University of Cambridge in 2006 and a PhD in
Statistical Dialogue Modelling in 2010. He has published around 30 peer-reviewed journal and conference papers, largely in the field of dialogue management. In 2008 he was awarded the IEEE Student
Spoken Language Processing award for a paper at ICASSP and in 2010 heco-authored best papers at SLT and Interspeech. He was co-chair of the 2009
ACL Student Research Workshop and co-presented a tutorial on POMDP
dialogue management at Interspeech 2009.

PROC IEEE, VOL. 101, NO. 5, 1160-1179, 2013

Jason Williams Jason Williams is with Microsoft
Research. His interests include spoken dialog systems, planning under uncertainty, spoken language
understanding, and speech recognition. He is on
the Scientific Committee of SigDial (the Special
Interest Group on Dialog and Discourse) and is on
the board of directors of the Association for Voice
Interaction Design (AVIxD). From 2009-2011, heserved on the IEEE Speech and Language TechnicalCommittee (SLTC) in the area of spoken dialoguesystems. He holds a PhD and Masters in Speechand Language Processing from Cambridge University (UK), and a BSE in
Electrical Engineering from Princeton University (USA). Prior to Microsoft,
Jason was Principal Member of Technical Staff at AT&T Labs – Researchfrom 2006-2012. Jason has also held several positions in industry building
spoken dialog systems, including at Tellme Networks (now Microsoft) as
Voice Application Development Manager.

18