Online exploration in least-squares policy iteration

ABSTRACT

One of the key problems in reinforcement learning is balancing exploration and exploitation. Another is learning and acting in large or even continuous Markov decision processes (MDPs), where compact function approximation has to be used. In this paper, we provide a practical solution to exploring large MDPs by integrating a powerful exploration technique, Rmax, into a state-of-the-art learning algorithm, least-squares policy iteration (LSPI). This approach combines the strengths of both methods, and has shown its effectiveness and superiority over LSPI with two other popular exploration rules in several benchmark problems.

REFERENCES

• 1: András Antos , Csaba Szepesvári , Rémi Munos, Learning near-optimal policies with Bellman-residual minimization based fitted policy iteration and a single sample path, Machine Learning, v.71 n.1, p.89-129, April 2008 [doi>10.1007/s10994-007-5038-2]
• 2: L. Baird. Residual algorithms: Reinforcement learning with function approximation. In Proceedings of the Twelfth International Conference on Machine Learning (ICML-95), pages 30--37, 1995.
• 3: A. G. Barto, R. S. Sutton, and C. W. Anderson. Neuronlike elements that can solve difficult learning control problems. IEEE Trans on Systems, Man, and Cybernetics, 13:835--846, 1983.
• 4: Dimitri P. Bertsekas , John N. Tsitsiklis, Neuro-Dynamic Programming, Athena Scientific, 1996
• 5: Justin A. Boyan, Technical Update: Least-Squares Temporal Difference Learning, Machine Learning, v.49 n.2-3, p.233-246, November-December 2002 [doi>10.1023/A:1017936530646]
• 6: J. A. Boyan and A. W. Moore. Generalization in reinforcement learning: Safely approximating the value function. In Advances in Neural Information Processing Systems 7, pages 369--376, 1995.
• 7: Steven J. Bradtke , Andrew G. Barto, Linear least-squares algorithms for temporal difference learning, Machine Learning, v.22 n.1-3, p.33-57, Jan./Feb./March 1996 [doi>10.1007/BF00114723]
• 8: 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]
• 9: C.-S. Chow and J. N. Tsitsiklis. An optimal one-way multigrid algorithm for discrete-time stochastic control. IEEE Trans on Automatic Control, 36(8):898--814, 1991.
• 10: Michael O'Gordon Duff , Andrew Barto, Optimal learning: computational procedures for bayes-adaptive markov decision processes, University of Massachusetts Amherst, 2002
• 11: Yaakov Engel , Shie Mannor , Ron Meir, Reinforcement learning with Gaussian processes, Proceedings of the 22nd international conference on Machine learning, p.201-208, August 07-11, 2005, Bonn, Germany [doi>10.1145/1102351.1102377]
• 12: Jerome H. Friedman , Jon Louis Bentley , Raphael Ari Finkel, An Algorithm for Finding Best Matches in Logarithmic Expected Time, ACM Transactions on Mathematical Software (TOMS), v.3 n.3, p.209-226, Sept. 1977 [doi>10.1145/355744.355745]
• 13: S. Kakade. On the Sample Complexity of Reinforcement Learning. PhD thesis, University College London, UK, 2003.
• 14: S. Kakade, M. J. Kearns, and J. Langford. Exploration in metric state spaces. In Proceedings of the Twentieth International Conference on Machine Learning (ICML-03), pages 306--312, 2003.
• 15: 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]
• 16: Sven Koenig , Reid G. Simmons, The effect of representation and knowledge on goal-directed exploration with reinforcement-learning algorithms, Machine Learning, v.22 n.1-3, p.227-250, Jan./Feb./March 1996 [doi>10.1007/BF00114729]
• 17: Michail G. Lagoudakis , Ronald Parr, Least-squares policy iteration, The Journal of Machine Learning Research, 4, p.1107-1149, 12/1/2003
• 18: A. Nouri and M. L. Littman. Multi-resolution exploration in continuous spaces. In Advances in Neural Information Processing Systems 21 (NIPS-08), 2009.
• 19: Pascal Poupart , Nikos Vlassis , Jesse Hoey , Kevin Regan, An analytic solution to discrete Bayesian reinforcement learning, Proceedings of the 23rd international conference on Machine learning, p.697-704, June 25-29, 2006, Pittsburgh, Pennsylvania [doi>10.1145/1143844.1143932]
• 20: Martin L. Puterman, Markov Decision Processes: Discrete Stochastic Dynamic Programming, John Wiley & Sons, Inc., New York, NY, 1994
• 21: Jette Randløv , Preben Alstrøm, Learning to Drive a Bicycle Using Reinforcement Learning and Shaping, Proceedings of the Fifteenth International Conference on Machine Learning, p.463-471, July 24-27, 1998
• 22: A. L. Strehl and M. L. Littman. Online linear regression and its application to model-based reinforcement learning. In Advances in Neural Information Processing Systems 20 (NIPS-07), pages 1417--1424, 2008.
• 23: R. S. Sutton. Generalization in reinforcement learning: Successful examples using sparse coarse coding. In Advances in Neural Information Processing Systems 8, pages 1038--1044, 1996.
• 24: Richard S. Sutton , Andrew G. Barto, Introduction to Reinforcement Learning, MIT Press, Cambridge, MA, 1998
• 25: S. Thrun. The role of exploration in learning control. In D. A. White and D. A. Sofge, editors, Handbook of Intelligent Control: Neural, Fuzzy and Adaptive Approaches, pages 527--559. 1992.

INDEX TERMS

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

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

General Terms:
Algorithms

Keywords:
Markov decision processes, PAC-MDP, exploration, least-squares policy iteration (LSPI), reinforcement learning