Automatic discovery and transfer of MAXQ hierarchies

ABSTRACT

We present an algorithm, HI-MAT (Hierarchy Induction via Models And Trajectories), that discovers MAXQ task hierarchies by applying dynamic Bayesian network models to a successful trajectory from a source reinforcement learning task. HI-MAT discovers subtasks by analyzing the causal and temporal relationships among the actions in the trajectory. Under appropriate assumptions, HI-MAT induces hierarchies that are consistent with the observed trajectory and have compact value-function tables employing safe state abstractions. We demonstrate empirically that HI-MAT constructs compact hierarchies that are comparable to manually-engineered hierarchies and facilitate significant speedup in learning when transferred to a target task.

REFERENCES

• 1: David Andre , Stuart J. Russell, State abstraction for programmable reinforcement learning agents, Eighteenth national conference on Artificial intelligence, p.119-125, July 28-August 01, 2002, Edmonton, Alberta, Canada
• 2: Şimşek, Ö., & Barto, A. (2004). Using Relative Novelty to Identify Useful Temporal Abstractions in Reinforcement Learning. ICML (pp. 751--758).
• 3: Dietterich, T. (2000). Hierarchical Reinforcement Learning with the MAXQ Value Function Decomposition. Journal of Artificial Intelligence Research, 13, 227--303.
• 4: Carlos Diuk , Alexander L. Strehl , Michael L. Littman, A hierarchical approach to efficient reinforcement learning in deterministic domains, Proceedings of the fifth international joint conference on Autonomous agents and multiagent systems, May 08-12, 2006, Hakodate, Japan [doi>10.1145/1160633.1160686]
• 5: 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
• 6: Anders Jonsson , Andrew Barto, Causal Graph Based Decomposition of Factored MDPs, The Journal of Machine Learning Research, 7, p.2259-2301, 12/1/2006
• 7: Marthi, B., Kaelbling, L., & Lozano-Perez, T. (2007). Learning Hierarchical Structure In Policies. NIPS Hierarchical Organization of Behavior Workshop.
• 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: Mehta, N., & Tadepalli, P. (2005). Multi-Agent Shared Hierarchy Reinforcement Learning. ICML Rich Representations in Reinforcement Learning Workshop.
• 10: Ishai Menache , Shie Mannor , Nahum Shimkin, Q-Cut - Dynamic Discovery of Sub-goals in Reinforcement Learning, Proceedings of the 13th European Conference on Machine Learning, p.295-306, August 19-23, 2002
• 11: Marc Pickett , Andrew G. Barto, PolicyBlocks: An Algorithm for Creating Useful Macro-Actions in Reinforcement Learning, Proceedings of the Nineteenth International Conference on Machine Learning, p.506-513, July 08-12, 2002
• 12: 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]
• 13: Prasad Tadepalli , Thomas G. Dietterich, Hierarchical Explanation-Based Reinforcement Learning, Proceedings of the Fourteenth International Conference on Machine Learning, p.358-366, July 08-12, 1997
• 14: Thrun, S., & Schwartz, A. (1995). Finding Structure in Reinforcement Learning. NIPS (pp. 385--392).

INDEX TERMS

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

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Data mining

  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.4 Model Validation and Analysis
      I.6.5 Model Development
          Subjects: Modeling methodologies

General Terms:
Algorithms, Design, Theory