The in the training set  The average R2 for the training set was with a standard error of while the average R 2 for the held out of the dialogues was with a standard Since the average R 2 for the test set is statistically indistinguishable from the error of training set  we assume that the performance model will generalize to new ELVIS dialogues

## Training An Optimized Policy

Given the learned performance function described above  we apply this function to the measures logged for each dialogue D i  thereby replacing a range of measures with a sin gle performance value P i  which is used as the utility  reward  for the final state of each dialogue 9  We then apply reinforcement learning with Pi as the utility of the final state of the dialogue Di  Bellman Sutton Tesauro Russell Norvig Watkins The utility of doing action a in state Si U a, Si   its value  can be calculated in terms of the utility of a successor state Sj  by obeying the recursive equation

$$\begin{array}{l l l}{{U~a\,,S_{i}}}&{{}}&{{R~a\,,S_{i}}}&{{}}&{{\sum_{j}M_{i j}^{a}\operatorname*{max}_{a^{\prime}}U~a^{\prime}\,,S_{j}}}\end{array}$$

where R a, Si is the immediate reward received for doing action a in Si a is a strategy from a finite set of strategies A that are admissable in state Si and Mf, is the probability of reaching state S i if strategy a is selected in state S i In the experiments reported here the reward associated with each state R Si is zero  In addition since reliable a priori prediction of a user action in a particular state is not possible  for example the user may say Help or the speech recognizer may fail to understand the user   the state transition model M is is estimated from the logged state strategy history for the dialogue The utility values can be estimated to within a desired threshold using value iteration which updates the estimate of U a, Si based on updated utility estimates for neighboring states so that the equation above becomes

$$U_{n\,+1}\,\,\,a\,,\,S_{i}\qquad R\,\,\,S_{i}\qquad\sum_{j}M_{i\,j}^{a}\operatorname*{max}_{a^{\prime}}U_{n}\,\,\,a^{\prime}\,,\,S_{j}\,,$$

where Un a, Si is the utility estimate for doing a in state Si after n iterations  Sutton Value iteration stops when the difference between Un a, Si and Barto p U n +1 a, Si  is below a threshold and utility values have been associated with states where strategy selections were made 10  Once value iteration is completed the optimal policy is obtained by selecting the action with the maximal    value in each dialogue state enumerates the subset of the states in the aggregrated state space used for Figure reinforcement learning and potential actions defining the policy space The strategy with the greatest value in each state after training is indicated by boldface in Figure This optimized policy will then be tested as a fixed policy in the operation of ELVIS In all the states of the task the System Initiative strategy in Figure is predicted to be the optimal initiative strategy  and the Read First strategy in Figure   is predicted to have the best performance of the Read strategies  As Figure    shows  the learned strategy