Co-evolving recurrent neurons learn deep memory POMDPs

ABSTRACT

Recurrent neural networks are theoretically capable of learning complex temporal sequences, but training them through gradient-descent is too slow and unstable for practical use in reinforcement learning environments. Neuroevolution, the evolution of artificial neural networks using genetic algorithms, can potentially solve real-world reinforcement learning tasks that require deep use of memory, i.e. memory spanning hundreds or thousands of inputs, by searching the space of recurrent neural networks directly. In this paper, we introduce a new neuroevolution algorithm called Hierarchical Enforced SubPopulations that simultaneously evolves networks at two levels of granularity: full networks and network components or neurons. We demonstrate the method in two POMDP tasks that involve temporal dependencies of up to thousands of time-steps, and show that it is faster and simpler than the current best conventional reinforcement learning system on these tasks.

REFERENCES

• 1: B. Bakker. Reinforcement learning with long short-term memory. In T. Dietterich, S. Becker, and Z. Ghahramani, editors, Advances in Neural Information Processing Systems 14, volume 14, pages 1475--1482, Cambridge, MA, 2002. MIT Press.
• 2: Randall D. Beer , John C. Gallagher, Evolving dynamical neural networks for adaptive behavior, Adaptive Behavior, v.1 n.1, p.91-122, Summer 1992 [doi>10.1177/105971239200100105]
• 3: Y. Bengio, P. Simard, and P. Frasconi. Learning long-term dependencies with gradient descent is difficult. IEEE Transactions on Neural Networks, 5(2):157--166, 1994.
• 4: Faustino John Gomez , Risto Miikkulainen, Robust non-linear control through neuroevolution, 2003
• 5: S. Hochreiter. Untersuchungen zu dynamischen neuronalen Netzen. Diploma thesis, Institut für Informatik, Lehrstuhl Prof. Brauer, Technische Universität München, 1991.
• 6: Sepp Hochreiter , Jürgen Schmidhuber, Long short-term memory, Neural Computation, v.9 n.9, p.1735-1780, Nov. 15, 1997 [doi>10.1162/neco.1997.9.8.1735]
• 7: Michael L. Littman, Memoryless policies: theoretical limitations and practical results, Proceedings of the third international conference on Simulation of adaptive behavior : from animals to animats 3: from animals to animats 3, p.238-245, July 1994, Brighton, United Kingdom
• 8: David E. Moriarty , Risto Mikkulainen, Efficient reinforcement learning through symbiotic evolution, Machine Learning, v.22 n.1-3, p.11-32, Jan./Feb./March 1996 [doi>10.1007/BF00114722]
• 9: Stefano Nolfi , Domenico Parisi , Jeffrey L. Elman, Learning and evolution in neural networks, Adaptive Behavior, v.3 n.1, p.5-28, Summer 1994 [doi>10.1177/105971239400300102]
• 10: Mitchell A. Potter , Kenneth A. De Jong, Cooperative Coevolution: An Architecture for Evolving Coadapted Subcomponents, Evolutionary Computation, v.8 n.1, p.1-29, March 2000 [doi>10.1162/106365600568086]
• 11: A. J. Robinson and F. Fallside. The utility driven dynamic error propagation network. Technical Report CUED/F-INFENG/TR.1, Engineering Department, Cambridge University, Cambridge, UK, 1987.
• 12: P. Werbos. Backpropagation through time: what does it do and how to do it. In Proceedings of IEEE, volume 78, pages 1550--1560, 1990.
• 13: A. Wieland. Evolving neural network controllers for unstable systems. In Proceedings of the International Joint Conference on Neural Networks (Seattle, WA), pages 667--673. Piscataway, NJ: IEEE, 1991.
• 14: R. J. Williams and D. Zipser. A learning algorithm for continually running fully recurrent neural networks. Neural Computation, 1:270--280, 1989.
• 15: X. Yao. Evolving artificial neural networks. Proceedings of the IEEE, 87(9):1423--1447, 1999.

INDEX TERMS

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

General Terms:
Algorithms, Experimentation, Performance

Keywords:
POMDP, coevolution, recurrent neural networks