A theoretical analysis of Model-Based Interval Estimation

ABSTRACT

Several algorithms for learning near-optimal policies in Markov Decision Processes have been analyzed and proven efficient. Empirical results have suggested that Model-based Interval Estimation (MBIE) learns efficiently in practice, effectively balancing exploration and exploitation. This paper presents the first theoretical analysis of MBIE, proving its efficiency even under worst-case conditions. The paper also introduces a new performance metric, average loss, and relates it to its less "online" cousins from the literature.

REFERENCES

• 1: Ronen I. Brafman , Moshe Tennenholtz, R-max - a general polynomial time algorithm for near-optimal reinforcement learning, The Journal of Machine Learning Research, 3, p.213-231, 3/1/2003 [doi>10.1162/153244303765208377]
• 2: Claude-Nicolas Fiechter, Expected Mistake Bound Model for On-Line Reinforcement Learning, Proceedings of the Fourteenth International Conference on Machine Learning, p.116-124, July 08-12, 1997
• 3: Fong, P. W. L. (1995). A quantitative study of hypothesis selection. Proceedings of the Twelfth International Conference on Machine Learning (ICML-95) (pp. 226--234).
• 4: Leslie Pack Kaelbling, Learning in embedded systems, MIT Press, Cambridge, MA, 1993
• 5: Kakade, S. M. (2003). On the sample complexity of reinforcement learning. Doctoral dissertation, Gatsby Computational Neuroscience Unit, University College London.
• 6: Michael Kearns , Satinder Singh, Near-Optimal Reinforcement Learning in Polynomial Time, Machine Learning, v.49 n.2-3, p.209-232, November-December 2002 [doi>10.1023/A:1017984413808]
• 7: Martin L. Puterman, Markov Decision Processes: Discrete Stochastic Dynamic Programming, John Wiley & Sons, Inc., New York, NY, 1994
• 8: Alexander L. Strehl , Michael L. Littman, An Empirical Evaluation of Interval Estimation for Markov Decision Processes, Proceedings of the 16th IEEE International Conference on Tools with Artificial Intelligence (ICTAI'04), p.128-135, November 15-17, 2004 [doi>10.1109/ICTAI.2004.28]
• 9: Strehl, A. L., & Littman, M. L. (2005). A theoretical analysis of model-based interval estimation: Proofs. Forthcoming tech report, Rutgers University.
• 10: Richard S. Sutton , Andrew G. Barto, Introduction to Reinforcement Learning, MIT Press, Cambridge, MA, 1998
• 11: Voltaire (1759). Candide.
• 12: Weissman, T., Ordentlich, E., Seroussi, G., Verdu, S., & Weinberger, M. J. (2003). Inequalities for the L1 deviation of the empirical distribution (Technical Report HPL-2003-97R1). Hewlett-Packard Labs.
• 13: Marco Wiering , Jürgen Schmidhuber, Efficient model-based exploration, Proceedings of the fifth international conference on simulation of adaptive behavior on From animals to animats 5, p.223-228, September 1998, Univ. of Zurich, Zurich, Switzerland