DOI: 10.1017/S000000000000000 Printed in the United Kingdom A Survey of Statistical User Simulation Techniques for Reinforcement-Learning of Dialogue Management Strategies <s> Model-based and Simulation-based Learning <s> This paper describes a novel method by which a dialogue agent can learn to choose an optimal dialogue strategy. While it is widely agreed that dialogue strategies should be formulated in terms of communicative intentions, there has been little work on automatically optimizing an agent's choices when there are multiple ways to realize a communicative intention. Our method is based on a combination of learning algorithms and empirical evaluation techniques. The learning component of our method is based on algorithms for reinforcement learning, such as dynamic programming and Q-learning. The empirical component uses the PARADISE evaluation framework (Walker et al., 1997) to identify the important performance factors and to provide the performance function needed by the learning algorithm. We illustrate our method with a dialogue agent named ELVIS (EmaiL Voice Interactive System), that supports access to email over the phone. We show how ELVIS can learn to choose among alternate strategies for agent initiative, for reading messages, and for summarizing email folders. <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> Model-based and Simulation-based Learning <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> BIB002 </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> Model-based and Simulation-based Learning <s> Dialog management is a critical component of an effective spoken language application. It is also one of the most difficult and time consuming to engineer. This paper examines the application of reinforcement learning and Markov decision processes (MDPs) to the problem of learning the dialog strategies. It extends work done at AT&T in two directions. First it examines the ability of RL to learn optimal strategies in the presence of speech recognition errors. Second, it describes a technique for reducing the amount of data required to train these models. This is significant as the difficulty of training MDP-based dialog managers is a serious roadblock to deploying them in realistic applications. <s> BIB003 </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> Model-based and Simulation-based Learning <s> The learning of dialogue strategies in spoken dialogue systems using reinforcement learning is a promising approach to acquire robust dialogue strategies. However, the trade-off between available dialogue data and information in the dialogue state either forces information to be excluded from the state representations or requires large amount of training data. In this paper, we propose to use dynamic state aggregation to efficiently learn dialogue policies using less data. State aggregation reduces the size of the problem to be solved. Experimental results show that the proposed method converges faster and that in case of data sparseness, the proposed method is less sensitive to atypical training examples. <s> BIB004
Dialogue strategy learning has been approached using two different forms of reinforcement learning which are referred to as model-based and simulation-based learning. The model-based approach uses the training data to build a complete model of the environment, i.e. it estimates the transition probabilities T from a corpus in which the state transitions have been logged. Parameter estimation can be done using simple Maximum Likelihood Estimation based on the relative frequency of occurrence of each transition The model-based approach neglects the actual user responses to system actions -it only considers the system-state transitions and the rewards associated with them. Once the transition probabilities have been estimated and the reward function has been set by the system designer, the optimal strategy can be found off-line (i.e. without any interaction between the DM and its environment) as described in the preceding section. This approach has been heavily used by research groups between 1998 and 2002, most notably by M. Walker, D. J. Litman and S. Singh BIB001 BIB002   and also in very early work by . The model-based approach is a simple form of reinforcement-learning and does not require a user simulation tool. However, it has not been used in more recent research due to a number of significant deficiencies: 1. Currently available corpora are not large enough to reliably estimate transition probabilities for practical systems. Even for trivial problems, the number of possible combinations of states and actions easily exceeds 100, 000 4 and the provision of training data large enough to explore this state space and obtain reliable estimates is simply not tractable. To cope with data sparsity, state-aggregation and back-off schemes for parameter estimation have been proposed by BIB004 BIB003 , but these are essentially smoothing methods and they offer no guarantee that the learned strategy is indeed robust. 2. When learning from a fixed corpus, the DM can only use state-action combinations that were explored at the time of the corpus data collection. It cannot try out entirely new strategies, since no transition probabilities can be computed for unseen state-action combinations. A deviation in user behaviour during the live operation of the system is likely to move the system into an unexplored portion of the state space, possibly causing the system to fail. Furthermore, the optimal strategy is not guaranteed to be present in the training corpus. 3. The model-based approach has the principal drawback, that the dialogue model (i.e. the state-space and action set representation) needs to be known in advance so that the corpus can be annotated correspondingly for estimating the state transition probabilities. Preferably, the state space and action set should be fixed even before the data collection in order to be able to log state transitions during the collection. However, if the chosen state space representation or action set turns out to be problematic, it is very difficult to change the dataset or its transcriptions. The simulation-based approach, pictured in Figure 1 on page 2, is an alternative to off-line modelbased learning and involves two phases: First a user simulation tool is trained on the given corpus using supervised learning. The dialogue strategy is then learned on-line through interaction between the simulated user and the dialogue manager using an algorithm such as Q-Learning as explained in the previous subsection. The simulation-based approach requires a reliable user model which generalises to unseen dialogue situations. As such it is the more complex approach but it offers the following advantages: 1. The simulated user allows any number of training episodes to be generated, so that the learning dialogue manager can exhaustively explore the space of possible strategies.