Fast gradient-descent methods for temporal-difference learning with linear function approximation

ABSTRACT

Sutton, Szepesvári and Maei (2009) recently introduced the first temporal-difference learning algorithm compatible with both linear function approximation and off-policy training, and whose complexity scales only linearly in the size of the function approximator. Although their gradient temporal difference (GTD) algorithm converges reliably, it can be very slow compared to conventional linear TD (on on-policy problems where TD is convergent), calling into question its practical utility. In this paper we introduce two new related algorithms with better convergence rates. The first algorithm, GTD2, is derived and proved convergent just as GTD was, but uses a different objective function and converges significantly faster (but still not as fast as conventional TD). The second new algorithm, linear TD with gradient correction, or TDC, uses the same update rule as conventional TD except for an additional term which is initially zero. In our experiments on small test problems and in a Computer Go application with a million features, the learning rate of this algorithm was comparable to that of conventional TD. This algorithm appears to extend linear TD to off-policy learning with no penalty in performance while only doubling computational requirements.

REFERENCES

• 1: András Antos , Csaba Szepesvári , Rémi Munos, Learning near-optimal policies with Bellman-residual minimization based fitted policy iteration and a single sample path, Machine Learning, v.71 n.1, p.89-129, April 2008 [doi>10.1007/s10994-007-5038-2]
• 2: Baird, L. C. (1995). Residual algorithms: Reinforcement learning with function approximation. In Proceedings of the 12th Int. Conf. on Machine Learning, pp. 30--37.
• 3: Baird, L. C. (1999). Reinforcement Learning Through Gradient Descent. PhD thesis, Carnegie-Mellon University.
• 4: Barnard, E. (1993). Temporal-difference methods and Markov models. IEEE Transactions on Systems, Man, and Cybernetics 23(2):357--365.
• 5: Vivek S. Borkar, Stochastic approximation with two time scales, Systems & Control Letters, v.29 n.5, p.291-294, Feb. 1997 [doi>10.1016/S0167-6911(97)90015-3]
• 6: V. S. Borkar , S. P. Meyn, The O.D. E. Method for Convergence of Stochastic Approximation and Reinforcement Learning, SIAM Journal on Control and Optimization, v.38 n.2, p.447-469, Jan. 2000 [doi>10.1137/S0363012997331639]
• 7: Justin A. Boyan, Technical Update: Least-Squares Temporal Difference Learning, Machine Learning, v.49 n.2-3, p.233-246, November-December 2002 [doi>10.1023/A:1017936530646]
• 8: Steven J. Bradtke , Andrew G. Barto, Linear least-squares algorithms for temporal difference learning, Machine Learning, v.22 n.1-3, p.33-57, Jan./Feb./March 1996 [doi>10.1007/BF00114723]
• 9: Peter Dayan, The Convergence of TD(λ) for General λ, Machine Learning, v.8 n.3-4, p.341-362, May 1992 [doi>10.1007/BF00992701]
• 10: Geramifard, A., Bowling, M., Sutton, R. S. (2006). Incremental least-square temporal difference learning. Proceedings AAAI, pp. 356--361.
• 11: M. W. Hirsch, Convergent activation dynamics in continuous time networks, Neural Networks, v.2 n.5, p.331-349, 1989 [doi>10.1016/0893-6080(89)90018-X]
• 12: Doina Precup , Richard S. Sutton , Sanjoy Dasgupta, Off-Policy Temporal Difference Learning with Function Approximation, Proceedings of the Eighteenth International Conference on Machine Learning, p.417-424, June 28-July 01, 2001
• 13: Precup, D., Sutton, R. S., Paduraru, C., Koop, A., Singh, S. (2006). Off-policy learning with recognizers. Advances in Neural Information Processing Systems 18.
• 14: Silver, D., Sutton, R. S., Müller, M. (2007). Reinforcement learning of local shape in the game of Go. Proceedings of the 20th IJCAI, pp. 1053--1058.
• 15: Sturtevant, N. R., White, A. M. (2006). Feature construction for reinforcement learning in hearts. In Proceedings of the 5th International Conf. on Computers and Games.
• 16: Richard S. Sutton, Learning to Predict by the Methods of Temporal Differences, Machine Learning, v.3 n.1, p.9-44, August 1988 [doi>10.1023/A:1022633531479]
• 17: Richard S. Sutton , Doina Precup , Satinder Singh, Between MDPs and semi-MDPs: a framework for temporal abstraction in reinforcement learning, Artificial Intelligence, v.112 n.1-2, p.181-211, Aug. 1999 [doi>10.1016/S0004-3702(99)00052-1]
• 18: Sutton, R. S., Szepesvári, Cs., Maei, H. R. (2009). A convergent O(n) algorithm for off-policy temporal-difference learning with linear function approximation. Advances in Neural Information Processing Systems 21.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Gradient methods

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.2 Approximation
          Subjects: Linear approximation

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning
  I.6 SIMULATION AND MODELING
      I.6.4 Model Validation and Analysis
      I.6.5 Model Development
          Subjects: Modeling methodologies

General Terms:
Algorithms, Design, Performance, Theory