Expediting RL by using graphical structures

ABSTRACT

The goal of Reinforcement learning (RL) is to maximize reward (minimize cost) in a Markov decision process (MDP) without knowing the underlying model a priori. RL algorithms tend to be much slower than planning algorithms, which require the model as input. Recent results demonstrate that MDP planning can be expedited, by exploiting the graphical structure of the MDP. We present extensions to two popular RL algorithms, Q-learning and RMax, that learn and exploit the graphical structure of problems to improve overall learning speed. Use of the graphical structure of the underlying MDP can greatly improve the speed of planning algorithms, if the underlying MDP has a nontrivial topological structure. Our experiments show that use of the apparent topological structure of an MDP speeds up reinforcement learning, even if the MDP is simply connected.

REFERENCES

• 1: Richard Ernest Bellman, Dynamic Programming, Dover Publications, Incorporated, 2003
• 2: C. Boutilier, T. Dean, and S. Hanks. Decision-theoretic planning: Structural assumptions and computational leverage. J. of Artificial Intelligence Research, 11:1--94, 1999.
• 3: Ronen I. Brafman , Moshe Tennenholtz, R-max - a general polynomial time algorithm for near-optimal reinforcement learning, The Journal of Machine Learning Research, 3, p.213-231, 3/1/2003 [doi>10.1162/153244303765208377]
• 4: P. Dai and J. Goldsmith. Topological value iteration algorithm for Markov decision processes. In Proc. IJCAI-07, pages 1860--1865, 2007.
• 5: Eric Anton Hansen , Shlomo Zilberstein, Finite-memory control of partially observable systems, University of Massachusetts Amherst, 1998
• 6: S. M. Kakade. On the sample complexity of reinforcement learning. PhD thesis, Gatsby Computational Neuroscience Unit, University College London, 2003.
• 7: Michael Kearns , Satinder Singh, Near-Optimal Reinforcement Learning in Polynomial Time, Machine Learning, v.49 n.2-3, p.209-232, November-December 2002 [doi>10.1023/A:1017984413808]
• 8: 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]
• 9: R. Munos and A. Moore. Influence and variance of a Markov chain: Application to adaptive discretization in optimal control. In Proc. of IEEE Conference on Decision and Control, 1999.
• 10: David J. Pearce , Paul H. J. Kelly, A dynamic topological sort algorithm for directed acyclic graphs, Journal of Experimental Algorithmics (JEA), 11, 2006 [doi>10.1145/1187436.1210590]
• 11: Alexander L. Strehl , Michael L. Littman, A theoretical analysis of Model-Based Interval Estimation, Proceedings of the 22nd international conference on Machine learning, p.856-863, August 07-11, 2005, Bonn, Germany [doi>10.1145/1102351.1102459]
• 12: Richard S. Sutton , Andrew G. Barto, Introduction to Reinforcement Learning, MIT Press, Cambridge, MA, 1998
• 13: C. J. Watkins. Learning from Delayed Rewards. PhD thesis, Cambridge University, Cambridge, UK, 1989.
• 14: 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]
• 15: David Wingate , Kevin D. Seppi, Prioritization Methods for Accelerating MDP Solvers, The Journal of Machine Learning Research, 6, p.851-881, 12/1/2005

INDEX TERMS

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

Additional Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Markov processes

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.11 Distributed Artificial Intelligence
            Subjects: Intelligent agents
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Plan execution, formation, and generation
  I.6 SIMULATION AND MODELING
      I.6.4 Model Validation and Analysis

General Terms:
Algorithms, Design, Performance, Theory