A hierarchical approach to efficient reinforcement learning in deterministic domains

ABSTRACT

Factored representations, model-based learning, and hierarchies are well-studied techniques for improving the learning efficiency of reinforcement-learning algorithms in large-scale state spaces. We bring these three ideas together in a new algorithm. Our algorithm tackles two open problems from the reinforcement-learning literature, and provides a solution to those problems in deterministic domains. First, it shows how models can improve learning speed in the hierarchy-based MaxQ framework without disrupting opportunities for state abstraction. Second, we show how hierarchies can augment existing factored exploration algorithms to achieve not only low sample complexity for learning, but provably efficient planning as well. We illustrate the resulting performance gains in example domains. We prove polynomial bounds on the computational effort needed to attain near optimal performance within the hierarchy.

REFERENCES

• 1: {Boutilier et al., 1999} Craig Boutilier, Thomas Dean, and Steve Hanks. Decision-theoretic planning: Structural assumptions and computational leverage. Journal of Artificial Intelligence Research, 11:1--94, 1999.
• 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: {Dietterich, 2000a} Thomas G. Dietterich. Hierarchical reinforcement learning with the MAXQ value function decomposition. Journal of Artificial Intelligence Research, 13:227--303, 2000.
• 4: Thomas G. Dietterich, An Overview of MAXQ Hierarchical Reinforcement Learning, Proceedings of the 4th International Symposium on Abstraction, Reformulation, and Approximation, p.26-44, July 26-29, 2000
• 5: {Dietterich, 2000c} Thomas G. Dietterich. State abstraction in MAXQ hierarchical reinforcement learning. In Advances in Neural Information Processing Systems 12, pages 994--1000, 2000.
• 6: Carlos Guestrin , Relu Patrascu , Dale Schuurmans, Algorithm-Directed Exploration for Model-Based Reinforcement Learning in Factored MDPs, Proceedings of the Nineteenth International Conference on Machine Learning, p.235-242, July 08-12, 2002
• 7: Bernhard Hengst, Discovering Hierarchy in Reinforcement Learning with HEXQ, Proceedings of the Nineteenth International Conference on Machine Learning, p.243-250, July 08-12, 2002
• 8: {Kaelbling, 1993} Leslie Pack Kaelbling. Hierarchical learning in stochastic domains: Preliminary results. In Proceedings of the Tenth International Conference on Machine Learning, Amherst, MA, 1993. Morgan Kaufmann.
• 9: {Kakade, 2003} Sham M. Kakade. On the Sample Complexity of Reinforcement Learning. PhD thesis, Gatsby Computational Neuroscience Unit, University College London, 2003.
• 10: 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
• 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: Daphne Koller , Ronald Parr, Policy Iteration for Factored MDPs, Proceedings of the 16th Conference on Uncertainty in Artificial Intelligence, p.326-334, June 30-July 03, 2000
• 13: Andrew W. Moore , Christopher G. Atkeson, Prioritized Sweeping: Reinforcement Learning with Less Data and Less Time, Machine Learning, v.13 n.1, p.103-130, Oct. 1993 [doi>10.1023/A:1022635613229]
• 14: Richard S. Sutton , Andrew G. Barto, Introduction to Reinforcement Learning, MIT Press, Cambridge, MA, 1998
• 15: Richard S. Sutton, Integrated architecture for learning, planning, and reacting based on approximating dynamic programming, Proceedings of the seventh international conference (1990) on Machine learning, p.216-224, June 1990, Austin, Texas, United States
• 16: 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.6 Learning

General Terms:
Algorithms

Keywords:
factored representations, hierarchical reinforcement learning, reinforcement learning, sample complexity