DOI: 10.1017/S000000000000000 Printed in the United Kingdom A Survey of Statistical User Simulation Techniques for Reinforcement-Learning of Dialogue Management Strategies <s> Reinforcement Learning <s> Many of the complex problems faced by decision makers involve multiple conflicting objectives. This book describes how a confused decision maker, who wishes to make a reasonable and responsible choice among alternatives, can systematically probe his true feelings in order to make those critically important, vexing trade-offs between incommensurable objectives. The theory is illustrated by many real concrete examples taken from a host of disciplinary settings. The standard approach in decision theory or decision analysis specifies a simplified single objective like monetary return to maximise. By generalising from the single objective case to the multiple objective case, this book considerably widens the range of applicability of decision analysis. <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> Reinforcement Learning <s> \cal Q-learning (Watkins, 1989) is a simple way for agents to learn how to act optimally in controlled Markovian domains. It amounts to an incremental method for dynamic programming which imposes limited computational demands. It works by successively improving its evaluations of the quality of particular actions at particular states. ::: ::: This paper presents and proves in detail a convergence theorem for \cal Q-learning based on that outlined in Watkins (1989). We show that \cal Q-learning converges to the optimum action-values with probability 1 so long as all actions are repeatedly sampled in all states and the action-values are represented discretely. We also sketch extensions to the cases of non-discounted, but absorbing, Markov environments, and where many \cal Q values can be changed each iteration, rather than just one. <s> BIB002
We can define R to be the total discounted return the learning dialogue manager receives when starting at time t. A discount factor γ, with 0 ≤ γ ≤ 1, can be used to weight immediate rewards more strongly than distant future rewards. Following the Maximum Expected Utility Principle BIB001  , our goal is to find the optimal policy π * that maximizes the expected value of R. Reinforcement learning offers a variety of algorithms for finding π * within the MDP framework through trial-and-error interaction between the learning agent and its dynamic environment. Such algorithms are commonly based on the definition of a value-function V π (s) that estimates the expected return of being in a given state s given a policy π Alternatively, we can define a value function Q π (s, a) that estimates the expected return of taking action a in a given state s and following π thereafter. Using the following short-hand notation for the transition probabilities and the expected rewards R(s , a, s) = E(r t+1 |s t+1 = s , a t = a, s t = s) we can rewrite V π (s) and Q π (s, a) as follows: If the transition probabilities T (s , a, s) and the reward function R(s , a, s) are known in advance, Dynamic Programming techniques, Value Iteration, or Policy Iteration can be used to find an optimal policy π * off-line, i.e. without any interaction of the DM with its environment. If T (s , a, s) and R(s , a, s) are unknown, we cannot systematically account for every possible combination of state and action and instead the agent needs to interact with its environment to learn these probabilities. The Q-Learning algorithm BIB002 ) is one of the simplest forms of on-line reinforcement-learning. It works by maintaining Quality-values (Q-values) for every pair (s, a) of state s and action a. These values estimate the expected return of taking action a in state s and following π thereafter, as expressed in Equation 4.