The adaptive k-meteorologists problem and its application to structure learning and feature selection in reinforcement learning

ABSTRACT

The purpose of this paper is three-fold. First, we formalize and study a problem of learning probabilistic concepts in the recently proposed KWIK framework. We give details of an algorithm, known as the Adaptive k-Meteorologists Algorithm, analyze its sample-complexity upper bound, and give a matching lower bound. Second, this algorithm is used to create a new reinforcement-learning algorithm for factored-state problems that enjoys significant improvement over the previous state-of-the-art algorithm. Finally, we apply the Adaptive k-Meteorologists Algorithm to remove a limiting assumption in an existing reinforcement-learning algorithm. The effectiveness of our approaches is demonstrated empirically in a couple benchmark domains as well as a robotics navigation problem.

REFERENCES

• 1: Pieter Abbeel , Daphne Koller , Andrew Y. Ng, Learning Factor Graphs in Polynomial Time and Sample Complexity, The Journal of Machine Learning Research, 7, p.1743-1788, 12/1/2006
• 2: Boutilier, C., Dean, T., & Hanks, S. (1999). Decision-theoretic planning: Structural assumptions and computational leverage. Journal of Artificial Intelligence Research, 11, 1--94.
• 3: 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]
• 4: Brunskill, E., Leffler, B. R., Li, L., Littman, M. L., & Roy, N. (2008). CORL: A continuous-state offset-dynamics reinforcement learner. Proceedings of the Twenty-Fourth Conference on Uncertainty in Artificial Intelligence (UAI-08).
• 5: Nicolò Cesa-Bianchi , Yoav Freund , David Haussler , David P. Helmbold , Robert E. Schapire , Manfred K. Warmuth, How to use expert advice, Journal of the ACM (JACM), v.44 n.3, p.427-485, May 1997 [doi>10.1145/258128.258179]
• 6: Thomas Dean , Keiji Kanazawa, A model for reasoning about persistence and causation, Computational Intelligence, v.5 n.3, p.142-150, Aug. 1990 [doi>10.1111/j.1467-8640.1989.tb00324.x]
• 7: Guestrin, C., Koller, D., Parr, R., & Venkataraman, S. (2003). Efficient solution algorithms for factored MDPs. Journal of Artificial Intelligence Research, 19, 399--468.
• 8: Kakade, S. (2003). On the sample complexity of reinforcement learning. Doctoral dissertation, Gatsby Computational Neuroscience Unit, University College London, UK.
• 9: Michael J. Kearns , Daphne Koller, Efficient Reinforcement Learning in Factored MDPs, Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence, p.740-747, July 31-August 06, 1999
• 10: Michael J. Kearns , Robert E. Schapire, Efficient distribution-free learning of probabilistic concepts, Journal of Computer and System Sciences, v.48 n.3, p.464-497, June 1994 [doi>10.1016/S0022-0000(05)80062-5]
• 11: 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]
• 12: Leffler, B. R., Littman, M. L., & Edmunds, T. (2007). Efficient reinforcement learning with relocatable action models. Proceedings of the Twenty-Second Conference on Artificial Intelligence (AAAI-07) (pp. 572--577).
• 13: Li, L. (2009). A unifying framework for computational reinforcement learning theory. Doctoral dissertation, Department of Computer Science, Rutgers University, New Brunswick, NJ.
• 14: Lihong Li , Michael L. Littman , Thomas J. Walsh, Knows what it knows: a framework for self-aware learning, Proceedings of the 25th international conference on Machine learning, p.568-575, July 05-09, 2008, Helsinki, Finland [doi>10.1145/1390156.1390228]
• 15: Shie Mannor , John N. Tsitsiklis, The Sample Complexity of Exploration in the Multi-Armed Bandit Problem, The Journal of Machine Learning Research, 5, p.623-648, 12/1/2004
• 16: Martin L. Puterman, Markov Decision Processes: Discrete Stochastic Dynamic Programming, John Wiley & Sons, Inc., New York, NY, 1994
• 17: Strehl, A. L. (2007). Model-based reinforcement learning in factored-state MDPs. Proceedings of the IEEE International Symposium on Approximate Dynamic Programming and Reinforcement Learning (pp. 103--110).
• 18: Strehl, A. L., Diuk, C., & Littman, M. L. (2007). Efficient structure learning in factored-state MDPs. Proceedings of the Twenty-Second AAAI Conference on Artificial Intelligence (AAAI-07) (pp. 645--650).
• 19: Strehl, A. L., Li, L., & Littman, M. L. (2006a). Incremental model-based learners with formal learning-time guarantees. Proceedings of the Twenty-Second Conference on Uncertainty in Artificial Intelligence (UAI-06) (pp. 485--493).
• 20: Alexander L. Strehl , Lihong Li , Eric Wiewiora , John Langford , Michael L. Littman, PAC model-free reinforcement learning, Proceedings of the 23rd international conference on Machine learning, p.881-888, June 25-29, 2006, Pittsburgh, Pennsylvania [doi>10.1145/1143844.1143955]
• 21: L. G. Valiant, A theory of the learnable, Communications of the ACM, v.27 n.11, p.1134-1142, Nov. 1984 [doi>10.1145/1968.1972]
• 22: Kenji Yamanishi, A Learning Criterion for Stochastic Rules, Machine Learning, v.9 n.2-3, p.165-203, July 1992 [doi>10.1007/BF00992676]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning

Additional Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Probabilistic algorithms (including Monte Carlo)

  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.2 Design Methodology
          Subjects: Classifier design and evaluation; Feature evaluation and selection
  I.6 SIMULATION AND MODELING
      I.6.4 Model Validation and Analysis
      I.6.5 Model Development
          Subjects: Modeling methodologies

General Terms:
Algorithms, Design, Performance, Theory