Estimating the Reliability of MDP Policies: a Confidence Interval Approach

Proceedings of NAACL HLT 2007, pages 276–283, Rochester, NY, April 2007. c⃝2007 Association for Computational Linguistics Estimating the Reliability of MDP Policies: A Confidence Interval Approach Joel R. Tetreault University of Pittsburgh LRDC Pittsburgh PA, 15260, USA tetreaul@pitt.edu Dan Bohus Carnegie Mellon University Dept. of Computer Science Pittsburgh, PA, 15213, USA dbohus@cs.cmu.edu Diane J. Litman University of Pittsburgh Dept. of Computer Science LRDC Pittsburgh PA, 15260, USA litman@cs.pitt.edu Abstract Past approaches for using reinforcement learning to derive dialog control policies have assumed that there was enough col- lected data to derive a reliable policy. In this paper we present a methodology for numerically constructing confidence inter- vals for the expected cumulative reward for a learned policy. These intervals are used to (1) better assess the reliability of the expected cumulative reward, and (2) perform a refined comparison between policies derived from different Markov Decision Processes (MDP) models. We applied this methodology to a prior ex- periment where the goal was to select the best features to include in the MDP state- space. Our results show that while some of the policies developed in the prior work exhibited very large confidence intervals, the policy developed from the best feature set had a much smaller confidence interval and thus showed very high reliability. 1 Introduction NLP researchers frequently have to deal with issues of data sparsity. Whether the task is machine transla- tion or named-entity recognition, the amount of data one has to train or test with can greatly impact the re- liability and robustness of one’s models, results and conclusions. One research area that is particularly sensitive to the data sparsity issue is machine learning, specifi- cally in using Reinforcement Learning (RL) to learn the optimal action for a dialogue system to make given any user state. Typically this involves learn- ing from previously collected data or interacting in real-time with real users or user simulators. One of the biggest advantages to this machine learning ap- proach is that it can be used to generate optimal poli- cies for every possible state. However, this method requires a thorough exploration of the state-space to make reliable conclusions on what the best actions are. States that are infrequently visited in the train- ing set could be assigned sub-optimal actions, and therefore the resulting dialogue manager may not provide the best interaction for the user. In this work, we present an approach for esti- mating the reliability of a policy derived from col- lected training data. The key idea is to take into ac- count the uncertainty in the model parameters (MDP transition probabilities), and use that information to numerically construct a confidence interval for the expected cumulative reward for the learned policy. This confidence interval approach allows us to: (1) better assess the reliability of the expected cumula- tive reward for a given policy, and (2) perform a re- fined comparison between policies derived from dif- ferent MDP models. We apply the proposed approach to our previous work (Tetreault and Litman, 2006) in …

Content truncated to 500 words