Generalized model learning for reinforcement learning in factored domains

ABSTRACT

Improving the sample efficiency of reinforcement learning algorithms to scale up to larger and more realistic domains is a current research challenge in machine learning. Model-based methods use experiential data more efficiently than model-free approaches but often require exhaustive exploration to learn an accurate model of the domain. We present an algorithm, Reinforcement Learning with Decision Trees (rl-dt), that uses supervised learning techniques to learn the model by generalizing the relative effect of actions across states. Specifically, rl-dt uses decision trees to model the relative effects of actions in the domain. The agent explores the environment exhaustively in early episodes when its model is inaccurate. Once it believes it has developed an accurate model, it exploits its model, taking the optimal action at each step. The combination of the learning approach with the targeted exploration policy enables fast learning of the model. The sample efficiency of the algorithm is evaluated empirically in comparison to five other algorithms across three domains. rl-dt consistently accrues high cumulative rewards in comparison with the other algorithms tested.

REFERENCES

• 1: J. S. Albus. A new approach to manipulator control: The cerebellar model articulation controller. Journal of Dynamic Systems, Measurement, and Control, 97(3):220--227, 1975.
• 2: R. I. Brafman and M. Tennenholtz. R-MAX - a general polynomial time algorithm for near-optimal reinforcement learning. In Proceedings of the Seventeenth International Joint Conference on Artificial Intelligence, pages 953--958, 2001.
• 3: Thomas Degris , Olivier Sigaud , Pierre-Henri Wuillemin, Learning the structure of Factored Markov Decision Processes in reinforcement learning problems, Proceedings of the 23rd international conference on Machine learning, p.257-264, June 25-29, 2006, Pittsburgh, Pennsylvania [doi>10.1145/1143844.1143877]
• 4: 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
• 5: Nicholas K. Jong , Peter Stone, Model-based function approximation in reinforcement learning, Proceedings of the 6th international joint conference on Autonomous agents and multiagent systems, May 14-18, 2007, Honolulu, Hawaii [doi>10.1145/1329125.1329242]
• 6: B. R. Leffler, M. L. Littman, and T. Edmunds. Efficient reinforcement learning with relocatable action models. In Proceedings of the Twenty-Second National Conference on Artificial Intelligence, pages 572--577, 2007.
• 7: Andrew W. Moore , Christopher G. Atkeson, Prioritized Sweeping: Reinforcement Learning with Less Data and Less Time, Machine Learning, v.13 n.1, p.103-130, Oct. 1993 [doi>10.1023/A:1022635613229]
• 8: J. R. Quinlan, Induction of Decision Trees, Machine Learning, v.1 n.1, p.81-106 [doi>10.1023/A:1022643204877]
• 9: 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.
• 10: A. L. Strehl, C. Diuk, and M. L. Littman. Efficient structure learning in factored-state mdps. In AAAI, pages 645--650. AAAI Press, 2007.
• 11: Richard S. Sutton , Andrew G. Barto, Introduction to Reinforcement Learning, MIT Press, Cambridge, MA, 1998
• 12: C. Watkins. Learning From Delayed Rewards. PhD thesis, University of Cambridge, 1989.
• 13: 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]

INDEX TERMS

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

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search

General Terms:
Algorithms, Experimentation

Keywords:
reinforcement learning, supervised learning