Proceedings

From Q(lambda) to Average Q-learning: Efficient Implementation of an Asymptotic Approximation

Download BibTeX Cite

Proceedings of the Seventeenth International Joint Conference on Artificial Intelligence. Pages 959-963.

© 2001 International Joint Conferences on Artificial Intelligence

Abstract

Q( ) is a reinforcement learning algorithm that combines Q-learning and TD( ). Online implementations of Q( ) that use eligibility traces have been shown to speed basic Q-learning. In this paper we present an asymptotic analysis of Watkins’ Q( ) with accumulative eligibility traces. We first introduce an asymptotic approximation of Q( ) that appears to be a gain matrix variant of basic Qlearning. Using the ODE method, we then determine an optimal gain matrix for Q-learning that maximizes its rate of convergence toward the optimal value function   . The similarity between this optimal gain and the asymptotic gain of Q( ) explains the relative efficiency of the latter for  . Furthermore, by minimizing the difference between these two gains, optimal values for the  parameter and the decreasing learning rates can be determined. This optimal  strongly depends on the exploration policy during learning. A robust approximation of these learning parameters leads to the definition of a new efficient algorithm called AQ-learning (Average Q-learning), that shows a close resemblance to Schwartz’ R-learning. Our results have been demonstrated through numerical simulations.

  1. [Benveniste et al., 1990] A. Benveniste, M. Metivier, and P. Priouret. Adaptive Algorithms and Stochastic Approx- imation. Springer-Verlag, Berlin,New York, 1990.
  2. [Bertsekas and Tsitsiklis, 1996] D. P. Bertsekas and J. N. Tsitsiklis. Neuro-Dynamic Programming. Athena Scien- tific, Belmont (MA), 1996.
  3. [Borkar and Meyn, 2000] V. S. Borkar and S. P. Meyn. The O.D.E. method for convergence of stochastic approxima- tion and reinforcement learning. SIAM Journal of Control and Optimization, 38:447-469, 2000.
  4. [Borkar, 1996] V. S. Borkar. Stochastic approximation with two-time scales. System and Control Letters, 29:291-294, 1996.
  5. [Cichosz, 1995] P. Cichosz. Truncating temporal differ- ences: On the efficient implementation of TD( ) for rein- forcement learning. Journal of Artificial Intelligence Re- search (JAIR), 2:287-318, 1995.
  6. [Garcia and Ndiaye, 1998] F. Garcia and S. Ndiaye. A Learning Rate Analysis of Reinforcement-Learning Algo- rithms in Finite-Horizon. In International Conference on Machine Learning, volume 15, Madison, USA, 1998.
  7. [Garcia and Serre, 2000] F. Garcia and F. Serre. Efficient asymptotic approximation in temporal difference learning. In Proceedings of the 14th European Conference on Arti- ficial Intelligence (ECAI 2000), Berlin, 2000.
  8. [Kearns and Singh, 2000] M. Kearns and S.P. Singh. "bias- Variance" error bounds for temporal difference updates. In Proceedings of the COLT 2000 conference, 2000.
  9. [Kushner and Yin, 1997] H. J. Kushner and G. G Yin. Stochastic Approximation Algorithms and Applications. Springer, 1997.
  10. [Peng and Williams, 1994] J. Peng and R. J. Williams. In- cremental Multi-Step Q-Learning. In International Con- ference on Machine Learning, volume 11, pages 226-232, 1994.
  11. [Puterman, 1994] M. L. Puterman. Markov decision pro- cesses: discrete stochastic dynamic programming. Wiley- Interscience, New York, 1994.
  12. [Schwartz, 1993] A. Schwartz. A Reinforcement Learning Method for Maximizing Undiscounted Rewards. In In- ternational Conference on Machine Learning, volume 10, 1993.
  13. [Singh and Dayan, 1998] S. P. Singh and P. Dayan. Analyt- ical Mean Squared Error Curves for Temporal Difference learning. Machine Learning, 1998.
  14. [Singh and Sutton, 1996] S. P. Singh and R. S. Sutton. Re- inforcement learning with replacing eligibility traces. Ma- chine Learning, 1996.
  15. [Sutton, 1988] R. S. Sutton. Learning to predict by the meth- ods of temporal differences. Machine Learning, 3:9-44, 1988.
  16. [Watkins, 1989] C. J. Watkins. Learning from Delayed Re- wards. PhD thesis, Cambridge University, Cambridge, England, 1989.
  17. [Wiering and Schmidhuber, 1997] M. A. Wiering and J. Schmidhuber. Fast online Q( ). Machine Learning, 1997.

References were extracted automatically from the PDF and may contain errors.

Welcome Future Conferences AI Journal Division IJCAI Proceedings About IJCAI IJCAI Awards