PAC model-free reinforcement learning

ABSTRACT

For a Markov Decision Process with finite state (size S) and action spaces (size A per state), we propose a new algorithm---Delayed Q-Learning. We prove it is PAC, achieving near optimal performance except for Õ(SA) timesteps using O(SA) space, improving on the Õ(S² A) bounds of best previous algorithms. This result proves efficient reinforcement learning is possible without learning a model of the MDP from experience. Learning takes place from a single continuous thread of experience---no resets nor parallel sampling is used. Beyond its smaller storage and experience requirements, Delayed Q-learning's per-experience computation cost is much less than that of previous PAC algorithms.

REFERENCES

• 1: Andrew G. Barto , Steven J. Bradtke , Satinder P. Singh, Learning to act using real-time dynamic programming, Artificial Intelligence, v.72 n.1-2, p.81-138, Jan. 1995 [doi>10.1016/0004-3702(94)00011-O]
• 2: 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]
• 3: Eyal Even-Dar , Yishay Mansour, Learning Rates for Q-learning, The Journal of Machine Learning Research, 5, p.1-25, 12/1/2004
• 4: Claude-Nicolas Fiechter, Efficient reinforcement learning, Proceedings of the seventh annual conference on Computational learning theory, p.88-97, July 12-15, 1994, New Brunswick, New Jersey, United States [doi>10.1145/180139.181019]
• 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, Finite-sample convergence rates for Q-learning and indirect algorithms, Proceedings of the 1998 conference on Advances in neural information processing systems II, p.996-1002, July 1999
• 7: 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]
• 8: Alexander L. Strehl , Michael L. Littman, A theoretical analysis of Model-Based Interval Estimation, Proceedings of the 22nd international conference on Machine learning, p.856-863, August 07-11, 2005, Bonn, Germany [doi>10.1145/1102351.1102459]
• 9: Richard S. Sutton , Andrew G. Barto, Introduction to Reinforcement Learning, MIT Press, Cambridge, MA, 1998
• 10: Christopher J. C. H. Watkins , Peter Dayan, Technical Note: $\backslash cal\; Q$-Learning, Machine Learning, v.8 n.3-4, p.279-292, May 1992 [doi>10.1007/BF00992698]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Backtracking

Additional Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Markov processes

  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.2 Design Methodology

General Terms:
Algorithms