Using Strongly Connected Components as a Basis for Autonomous Skill Acquisition in Reinforcement Learning | SpringerLink
Skip to main content
Springer Nature Link
Log in

Using Strongly Connected Components as a Basis for Autonomous Skill Acquisition in Reinforcement Learning

  • Conference paper
Advances in Neural Networks – ISNN 2009 (ISNN 2009)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 5551))

Included in the following conference series:

Abstract

Hierarchical reinforcement learning (HRL) has had a vast range of applications in recent years. Preparing mechanisms for autonomous acquisition of skills has been a main topic of research in this area. While different methods have been proposed to achieve this goal, few methods have been shown to be successful both in performance and also efficiency in terms of time complexity of the algorithm. In this paper, a linear time algorithm is proposed to find subgoal states of the environment in early episodes of learning. Having subgoals available in early phases of a learning task, results in building skills that dramatically increase the convergence rate of the learning process.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Asadi, M., Huber, M.: Accelerating action dependent hierarchical reinforcement learning through autonomous subgoal discovery. In: Proceedings of the ICML 2005 Workshop on Rich Representations for Reinforcement Learning (2005)

    Google Scholar 

  2. Chen, F., Gao, Y., Chen, S., Ma, Z.: Connect-based subgoal discovery for options in hierarchical reinforcement learning. In: International Conference on Natural Computation, vol. 3 (2007)

    Google Scholar 

  3. Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 2nd edn. MIT Press, Cambridge (2001)

    MATH  Google Scholar 

  4. Dietterich, T.G.: Hierarchical reinforcement learning with the MAXQ value function decomposition. Journal of Artificial Intelligence Research 13, 227–303 (2000)

    MathSciNet  MATH  Google Scholar 

  5. Lin, L.-J.: Self-improving reactive agents based on reinforcement learning, planning and teaching. Mach. Learn. 8(3-4), 293–321 (1992)

    Article  Google Scholar 

  6. Mannor, S., Menache, I., Hoze, A., Klein, U.: Dynamic abstraction in reinforcement learning via clustering. In: Proceedings of the Twenty-First International Conference on Machine Learning, pp. 560–567. ACM Press, New York (2004)

    Google Scholar 

  7. McGovern, A., Barto, A.G.: Automatic discovery of subgoals in reinforcement learning using diverse density. In: International Conf. on Machine Learning, vol. 18, pp. 361–368. Morgan Kaufmann, San Francisco (2001)

    Google Scholar 

  8. Menache, I., Mannor, S., Shimkin, N.: Q-cut - dynamic discovery of sub-goals in reinforcement learning. In: Elomaa, T., Mannila, H., Toivonen, H. (eds.) ECML 2002. LNCS, vol. 2430, pp. 295–306. Springer, Heidelberg (2002)

    Chapter  Google Scholar 

  9. Parr, R., Russell, S.: Reinforcement learning with hierarchies of machines. In: Jordan, M.I., Kearns, M.J., Solla, S.A. (eds.) Advances in Neural Information Processing Systems, vol. 10, pp. 167–173. MIT Press, Cambridge (1997)

    Google Scholar 

  10. Şimşek, Ö., Barto, A.G.: Using relative novelty to identify useful temporal abstractions in reinforcement learning. In: International Conference on Machine Learning, vol. 21, pp. 751–758. ACM Press, New York (2004)

    Google Scholar 

  11. Şimşek, Ö., Wolfe, A.P., Barto, A.G.: Identifying useful subgoals in reinforcement learning by local graph partitioning. In: International Conference on Machine Learning, Bonn, Germany, vol. 22 (2005)

    Google Scholar 

  12. Stolle, M., Precup, D.: Learning options in reinforcement learning. In: Koenig, S., Holte, R.C. (eds.) SARA 2002. LNCS, vol. 2371, pp. 212–223. Springer, Heidelberg (2002)

    Chapter  Google Scholar 

  13. Sutton, R.S., Barto, A.G.: Reinforcement Learning: An Introduction (Adaptive Computation and Machine Learning). MIT Press, Cambridge (1998)

    Google Scholar 

  14. Sutton, R.S., Precup, D., Singh, S.P.: Between MDPs and semi-MDPs: A framework for temporal abstraction in reinforcement learning. Artificial Intelligence 112(1-2), 181–211 (1999)

    Article  MathSciNet  MATH  Google Scholar 

  15. Sutton, R.S., Singh, S.P., Precup, D., Ravindran, B.: Improved switching among temporally abstract actions. In: International Conference on Machine Learning, vol. 15. Morgan Kaufmann, San Francisco (1998)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Intelligent Systems Lab. Computer Eng. Department, Sharif Univeristy of Technology, Iran

    Seyed Jalal Kazemitabar & Hamid Beigy

Authors
  1. Seyed Jalal Kazemitabar
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Hamid Beigy
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Departamento de Control Automático, CINVESTAV-IPN, A.P. 14-740, Av.IPN 2508, 07360, México D.F., México

    Wen Yu

  2. Deptartment of Electrical and Computer Engineering, Stevens Institute of Technology, NJ 07030, Hoboken, USA

    Haibo He

  3. Dept. of Electrical and Computer Engineering, South Dakota School of Mines & Technology, 501 E. St. Joseph Street, Rapid City, SD 57701, USA

    Nian Zhang

Rights and permissions

Reprints and permissions

Copyright information

© 2009 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Kazemitabar, S.J., Beigy, H. (2009). Using Strongly Connected Components as a Basis for Autonomous Skill Acquisition in Reinforcement Learning. In: Yu, W., He, H., Zhang, N. (eds) Advances in Neural Networks – ISNN 2009. ISNN 2009. Lecture Notes in Computer Science, vol 5551. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-01507-6_89

Download citation

  • DOI: https://doi.org/10.1007/978-3-642-01507-6_89

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-642-01506-9

  • Online ISBN: 978-3-642-01507-6

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation