DOI: 10.1017/S000000000000000 Printed in the United Kingdom A Survey of Statistical User Simulation Techniques for Reinforcement-Learning of Dialogue Management Strategies <s> Concept Drift <s> Letizia is a user interface agent that assists a user browsing the World Wide Web. As the user operates a conventional Web browser such as Netscape, the agent tracks user behavior and attempts to anticipate items of interest by doing concurrent, autonomous exploration of links from the user's current position. The agent automates a browsing strategy consisting of a best-first search augmented by heuristics inferring user interest from browsing behavior. <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> Concept Drift <s> At first blush, user modeling appears to be a prime candidate for straightforward application of standard machine learning techniques. Observations of the user's behavior can provide training examples that a machine learning system can use to form a model designed to predict future actions. However, user modeling poses a number of challenges for machine learning that have hindered its application in user modeling, including: the need for large data sets; the need for labeled data; concept drift; and computational complexity. This paper examines each of these issues and reviews approaches to resolving them. <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> Concept Drift <s> On-line learning in domains where the target concept depends on some hidden context poses serious problems. A changing context can induce changes in the target concepts, producing what is known as concept drift. We describe a family of learning algorithms that flexibly react to concept drift and can take advantage of situations where contexts reappear. The general approach underlying all these algorithms consists of (1) keeping only a window of currently trusted examples and hypotheses; (2) storing concept descriptions and re-using them when a previous context re-appears; and (3) controlling both of these functions by a heuristic that constantly monitors the system's behavior. The paper reports on experiments that test the systems' performance under various conditions such as different levels of noise and different extent and rate of concept drift. <s> BIB003
A second concept from the realm of machine-learning for statistical user modelling which may be of use for future research on simulation-based strategy learning is Concept Drift BIB003 BIB002 . Concept drift describes the problem that user attributes change over the course of interaction with a system. Traditionally, this has been of particular relevance for user modelling in the areas of information retrieval and personalized news recommender systems. Systems of this type typically attempt to recommend documents to the user based on previously requested documents. The underlying assumption of "persistence of interest" BIB001 , however, is often flawed because a user's interests, preferences and behaviour can change. A person who has read several news articles concerning a certain current event, for example, may be dissatisfied if the system recommends yet another article on the same topic a week later. A similar problem applies to simulation-based learning. Some of the user models currently available for modelling user dialogue behaviour include the notion of a user goal, but they all assume that the user goal stays fixed over the course of a dialogue. This assumption is of course simplistic. In reality, a user might start a conversation (say with a flight booking system) with a vague idea of booking "a low-cost flight from London to Madrid for the Christmas Holidays". It is only as the dialogue evolves that the user goal becomes more concrete, for example as details regarding the exact departure date and time are added. The user may not have a specific airline in mind at the start of the conversation but may still express a preference when reminded about a frequent-flyer programme. The user goal may also change as the user becomes aware of system limitations: For example, the user may have a priority for sitting at a windowseat, but may change his mind when he realizes that the system cannot accommodate his request. He may also decide to drop this priority if only aisle seats are available on a significantly cheaper flight option. In research on statistical user modelling outside of spoken dialogue systems, suggestions have been made to address the problem of concept drift. One approach is to weight recent observations more strongly than old observations  , another idea is to use windowing techniques to adjust the span of training data which is used to make a prediction  . A common problem is that the amount of relevant recent training data is small, so that the use of back-off models has been suggested in instances when no reliable prediction can be made using the recent data   . However, all of the above suggestions apply to purely content-based forms of user modelling and are likely to require significant modifications to be useful for the primarily collaborative modelling techniques used for simulating user dialogue behaviour. One may also argue that the challenge of modelling changes in the user goal over the course of a dialogue is potentially even more complex than modelling the lack of persistence in user interests in other user modelling applications because it is not just a temporal problem. The key issue is that we require a better understanding and a better model of how the system's behaviour causes changes in the user goal. This is especially an issue in spoken dialogue systems where recognition performance can vary significantly over time thereby having a significant impact on the dialogue.