The utility of temporal abstraction in reinforcement learning

ABSTRACT

The hierarchical structure of real-world problems has motivated extensive research into temporal abstractions for reinforcement learning, but precisely how these abstractions allow agents to improve their learning performance is not well understood. This paper investigates the connection between temporal abstraction and an agent's exploration policy, which determines how the agent's performance improves over time. Experimental results with standard methods for incorporating temporal abstractions show that these methods benefit learning only in limited contexts. The primary contribution of this paper is a clearer understanding of how hierarchical decompositions interact with reinforcement learning algorithms, with important consequences for the manual design or automatic discovery of action hierarchies.

REFERENCES

• 1: Andrew G. Barto , Sridhar Mahadevan, Recent Advances in Hierarchical Reinforcement Learning, Discrete Event Dynamic Systems, v.13 n.1-2, p.41-77, January-April 2003 [doi>10.1023/A:1022140919877]
• 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: T. G. Dietterich. Hierarchical reinforcement learning with the MAXQ value function decomposition. Journal of Artificial Intelligence Research, 13:227--303, 2000.
• 4: M. Hauskrecht, N. Meuleau, L. P. Kaelbling, T. Dean, and C. Boutilier. Hierarchical solution of Markov decision processes using macro-actions. In Proceedings of the Fourteenth Conference on Uncertainty in Artificial Intelligence, pages 220--229, 1998.
• 5: Michael J. Kearns , Satinder P. Singh, Near-Optimal Reinforcement Learning in Polynominal Time, Proceedings of the Fifteenth International Conference on Machine Learning, p.260-268, July 24-27, 1998
• 6: Long-Ji Lin, Self-Improving Reactive Agents Based on Reinforcement Learning, Planning and Teaching, Machine Learning, v.8 n.3-4, p.293-321, May 1992 [doi>10.1007/BF00992699]
• 7: Shie Mannor , Ishai Menache , Amit Hoze , Uri Klein, Dynamic abstraction in reinforcement learning via clustering, Proceedings of the twenty-first international conference on Machine learning, p.71, July 04-08, 2004, Banff, Alberta, Canada [doi>10.1145/1015330.1015355]
• 8: Amy McGovern , Andrew G. Barto, Automatic Discovery of Subgoals in Reinforcement Learning using Diverse Density, Proceedings of the Eighteenth International Conference on Machine Learning, p.361-368, June 28-July 01, 2001
• 9: Martin L. Puterman, Markov Decision Processes: Discrete Stochastic Dynamic Programming, John Wiley & Sons, Inc., New York, NY, 1994
• 10: Özgür Şimşek , Andrew G. Barto, Using relative novelty to identify useful temporal abstractions in reinforcement learning, Proceedings of the twenty-first international conference on Machine learning, p.95, July 04-08, 2004, Banff, Alberta, Canada [doi>10.1145/1015330.1015353]
• 11: S. Singh, A. G. Barto, and N. Chentanez. Intrinsically motivated reinforcement learning. In Advances in Neural Information Processing Systems 17, 2005.
• 12: 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]
• 13: Richard S. Sutton , Andrew G. Barto, Introduction to Reinforcement Learning, MIT Press, Cambridge, MA, 1998
• 14: Richard S. Sutton , Doina Precup , Satinder Singh, Between MDPs and semi-MDPs: a framework for temporal abstraction in reinforcement learning, Artificial Intelligence, v.112 n.1-2, p.181-211, Aug. 1999 [doi>10.1016/S0004-3702(99)00052-1]
• 15: C. Watkins. Learning From Delayed Rewards. PhD thesis, University of Cambridge, 1989.

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, Experimentation

Keywords:
reinforcement learning, temporal abstraction