Discovering options from example trajectories

ABSTRACT

We present a novel technique for automated problem decomposition to address the problem of scalability in reinforcement learning. Our technique makes use of a set of near-optimal trajectories to discover options and incorporates them into the learning process, dramatically reducing the time it takes to solve the underlying problem. We run a series of experiments in two different domains and show that our method offers up to 30 fold speedup over the baseline.

REFERENCES

• 1: Thomas G. Dietterich, The MAXQ Method for Hierarchical Reinforcement Learning, Proceedings of the Fifteenth International Conference on Machine Learning, p.118-126, July 24-27, 1998
• 2: 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
• 3: Anders Jonsson , Andrew Barto, Causal Graph Based Decomposition of Factored MDPs, The Journal of Machine Learning Research, 7, p.2259-2301, 12/1/2006
• 4: 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]
• 5: 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
• 6: Neville Mehta , Soumya Ray , Prasad Tadepalli , Thomas Dietterich, Automatic discovery and transfer of MAXQ hierarchies, Proceedings of the 25th international conference on Machine learning, p.648-655, July 05-09, 2008, Helsinki, Finland [doi>10.1145/1390156.1390238]
• 7: Ronald Parr , Stuart Russell, Reinforcement learning with hierarchies of machines, Proceedings of the 1997 conference on Advances in neural information processing systems 10, p.1043-1049, July 1998, Denver, Colorado, United States
• 8: 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
• 9: Richard S. Sutton , Andrew G. Barto, Introduction to Reinforcement Learning, MIT Press, Cambridge, MA, 1998
• 10: 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]
• 11: Esko Ukkonen, Constructing Suffix Trees On-Line in Linear Time, Proceedings of the IFIP 12th World Computer Congress on Algorithms, Software, Architecture - Information Processing '92, Volume 1, p.484-492, September 07-11, 1992

INDEX TERMS

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

Additional Classification:
  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.2 Design Methodology
          Subjects: Feature evaluation and selection; Classifier design and evaluation
  I.6 SIMULATION AND MODELING
      I.6.4 Model Validation and Analysis
      I.6.5 Model Development
          Subjects: Modeling methodologies

General Terms:
Algorithms, Design, Performance, Theory