An empirical analysis of value function-based and policy search reinforcement learning

ABSTRACT

In several agent-oriented scenarios in the real world, an autonomous agent that is situated in an unknown environment must learn through a process of trial and error to take actions that result in long-term benefit. Reinforcement Learning (or sequential decision making) is a paradigm well-suited to this requirement. Value function-based methods and policy search methods are contrasting approaches to solve reinforcement learning tasks. While both classes of methods benefit from independent theoretical analyses, these often fail to extend to the practical situations in which the methods are deployed. We conduct an empirical study to examine the strengths and weaknesses of these approaches by introducing a suite of test domains that can be varied for problem size, stochasticity, function approximation, and partial observability. Our results indicate clear patterns in the domain characteristics for which each class of methods excels. We investigate whether their strengths can be combined, and develop an approach to achieve that purpose. The effectiveness of this approach is also demonstrated on the challenging benchmark task of robot soccer Keepaway. We highlight several lines of inquiry that emanate from this study.

REFERENCES

• 1: J. Baxter and P. L. Bartlett. Infinite-horizon policy-gradient estimation. Journal of Artificial Intelligence Research, 15:319--350, 2001.
• 2: R. E. Bellman. Dynamic Programming. Princeton University Press, Princeton, NJ, June 1957.
• 3: S. Bhatnagar, R. Sutton, M. Ghavamzadeh, and M. Lee. Incremental natural actor-critic algorithms. In J. Platt, D. Koller, Y. Singer, and S. Roweis, editors, Advances in Neural Information Processing Systems 20, pages 105--112. MIT Press, Cambridge, MA, 2008.
• 4: Anthony R. Cassandra , Leslie Pack Kaelbling , Michael L. Littman, Acting optimally in partially observable stochastic domains, Proceedings of the twelfth national conference on Artificial intelligence (vol. 2), p.1023-1028, October 1994, Seattle, Washington, United States
• 5: R. H. Crites and A. G. Barto. Improving elevator performance using reinforcement learning. In D. S. Touretzky, M. Mozer, and M. E. Hasselmo, editors, Advances in Neural Information Processing Systems 8, NIPS, Denver, CO, November 27--30, 1995, pages 1017--1023. MIT Press, 1996.
• 6: P. T. De Boer, D. P. Kroese, S. Mannor, and R. Rubinstein. A tutorial on the cross-entropy method. Annals of Operations Research, 134(1):19--67, 2005.
• 7: S. Kakade. A natural policy gradient. In T. G. Dietterich, S. Becker, and Z. Ghahramani, editors, Advances in Neural Information Processing Systems 14, pages 1531--1538. MIT Press, 2001.
• 8: Nate Kohl , Peter Stone, Machine learning for fast quadrupedal locomotion, Proceedings of the 19th national conference on Artifical intelligence, p.611-616, July 25-29, 2004, San Jose, California
• 9: Michail G. Lagoudakis , Ronald Parr, Least-squares policy iteration, The Journal of Machine Learning Research, 4, p.1107-1149, 12/1/2003
• 10: John Loch , Satinder P. Singh, Using Eligibility Traces to Find the Best Memoryless Policy in Partially Observable Markov Decision Processes, Proceedings of the Fifteenth International Conference on Machine Learning, p.323-331, July 24-27, 1998
• 11: A. Y. Ng, H. J. Kim, M. I. Jordan, and S. Sastry. Autonomous helicopter flight via reinforcement learning. In S. Thrun, L. Saul, and B. Schölkopf, editors, Advances in Neural Information Processing Systems 16. MIT Press, Cambridge, MA, 2004.
• 12: T. J. Perkins and D. Precup. A convergent form of approximate policy iteration. In S. T. S. Becker and K. Obermayer, editors, Advances in Neural Information Processing Systems 15, pages 1595--1602. MIT Press, Cambridge, MA, 2003.
• 13: Jan Peters , Stefan Schaal, Natural Actor-Critic, Neurocomputing, v.71 n.7-9, p.1180-1190, March, 2008 [doi>10.1016/j.neucom.2007.11.026]
• 14: G. A. Rummery and M. Niranjan. On-line Q-learning using connectionist systems. Technical Report CUED/F-INFENG/TR 166, Cambridge University Engineering Department, 1994.
• 15: K. O. Stanley. Efficient evolution of neural networks through complexification. Technical Report AI-TR-04-314, Department of Computer Sciences, University of Texas at Austin, August 2004.
• 16: P. Stone, R. S. Sutton, and G. Kuhlmann. Reinforcement learning for RoboCup-soccer keepaway. Adaptive Behavior, 13(3):165--188, 2005.
• 17: Richard S. Sutton , Andrew G. Barto, Introduction to Reinforcement Learning, MIT Press, Cambridge, MA, 1998
• 18: István Szita , András Lörincz, Learning tetris using the noisy cross-entropy method, Neural Computation, v.18 n.12, p.2936-2941, December 2006 [doi>10.1162/neco.2006.18.12.2936]
• 19: Matthew E. Taylor , Shimon Whiteson , Peter Stone, Comparing evolutionary and temporal difference methods in a reinforcement learning domain, Proceedings of the 8th annual conference on Genetic and evolutionary computation, July 08-12, 2006, Seattle, Washington, USA [doi>10.1145/1143997.1144202]
• 20: Matthew E. Taylor , Peter Stone, Behavior transfer for value-function-based reinforcement learning, Proceedings of the fourth international joint conference on Autonomous agents and multiagent systems, July 25-29, 2005, The Netherlands [doi>10.1145/1082473.1082482]
• 21: Gerald Tesauro , Nicholas K. Jong , Rajarshi Das , Mohamed N. Bennani, On the use of hybrid reinforcement learning for autonomic resource allocation, Cluster Computing, v.10 n.3, p.287-299, September 2007 [doi>10.1007/s10586-007-0035-6]
• 22: Christopher J. C. H. Watkins , Peter Dayan, Technical Note: $\backslash cal\; Q$-Learning, Machine Learning, v.8 n.3-4, p.279-292, May 1992 [doi>10.1007/BF00992698]
• 23: Shimon Whiteson , Peter Stone, Evolutionary Function Approximation for Reinforcement Learning, The Journal of Machine Learning Research, 7, p.877-917, 12/1/2006

INDEX TERMS

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

General Terms:
Algorithms, Experimentation

Keywords:
function approximation, policy search, reinforcement learning, temporal difference learning