DOI: 10.1017/S000000000000000 Printed in the United Kingdom A Survey of Statistical User Simulation Techniques for Reinforcement-Learning of Dialogue Management Strategies <s> Dialogue as a Markov Decision Process <s> Recently, a number of authors have proposed treating dialogue systems as Markov decision processes (MDPs). However, the practical application of MDP algorithms to dialogue systems faces a number of severe technical challenges. We have built a general software tool (RLDS, for Reinforcement Learning for Dialogue Systems) based on the MDP framework, and have applied it to dialogue corpora gathered from two dialogue systems built at AT&T Labs. Our experiments demonstrate that RLDS holds promise as a tool for "browsing" and understanding correlations in complex, temporally dependent dialogue corpora. <s> BIB001 </s> DOI: 10.1017/S000000000000000 Printed in the United Kingdom A Survey of Statistical User Simulation Techniques for Reinforcement-Learning of Dialogue Management Strategies <s> Dialogue as a Markov Decision Process <s> We propose a quantitative model for dialog systems that can be used for learning the dialog strategy. We claim that the problem of dialog design can be formalized as an optimization problem with an objective function reflecting different dialog dimensions relevant for a given application. We also show that any dialog system can be formally described as a sequential decision process in terms of its state space, action set, and strategy. With additional assumptions about the state transition probabilities and cost assignment, a dialog system can be mapped to a stochastic model known as Markov decision process (MDP). A variety of data driven algorithms for finding the optimal strategy (i.e., the one that optimizes the criterion) is available within the MDP framework, based on reinforcement learning. For an effective use of the available training data we propose a combination of supervised and reinforcement learning: the supervised learning is used to estimate a model of the user, i.e., the MDP parameters that quantify the user's behavior. Then a reinforcement learning algorithm is used to estimate the optimal strategy while the system interacts with the simulated user. This approach is tested for learning the strategy in an air travel information system (ATIS) task. The experimental results we present in this paper show that it is indeed possible to find a simple criterion, a state space representation, and a simulated user parameterization in order to automatically learn a relatively complex dialog behavior, similar to one that was heuristically designed by several research groups. <s> BIB002
The Markov-Decision-Process (MDP) model serves as a formal representation of human-machine dialogue and provides the basis for formulating strategy learning problems   Figure 3 Dialogue as a Markov Decision Process (MDP): The Dialogue Manager acts as a learning agent travelling through a network of interconnected dialogue states. At each time t, the DM is in state st, takes action at, transitions into state st+1 and receives a reward rt+1. A dialogue strategy π(s) → a can be viewed as a deterministic mapping from states to actions. BIB001 BIB002 . Every MDP is formally described by a finite state space S, a finite action set A, a set of transition probabilities T and a reward function R. At each time step t, the dialogue manager is in a particular state s t ∈ S. It executes the discrete action a t ∈ A, transitions into the next state s t+1 according to the transition probability p(s t+1 |s t , a t ) and receives a reward r t+1 . The Markov Property ensures that the state and reward at time t + 1 only depend on the state and action at time t. Using the MDP model of dialogue, we can visualise the DM as an agent travelling through a network of interconnected dialogue states (see Figure 3 ). Starting in some initial state, the DM transitions from state to state by taking actions and collecting rewards as it goes along. Since the user response to a system action is uncertain, the transitions are non-deterministic, meaning that the choice of some action a in some state s at time t does not always lead to the same next state and reward at time t + 1. The MDP model allows a dialogue management strategy (or policy) π(s) → a to be viewed as a deterministic 2 mapping from states to actions: For every state s, the policy selects the next system action a. It also enables us to formalize dialogue management as a mathematical optimization problem. The optimal policy π * is the policy that maximizes the cumulative reward over time, i.e. the policy that selects those actions that yield the highest reward over the course of the dialogue.