Proceedings

Efficient Learning in Linearly Solvable MDP Models

Download BibTeX Cite

Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence. Pages 248-252.

© 2013 International Joint Conferences on Artificial Intelligence

Abstract

Linearly solvable Markov Decision Process (MDP) models are a powerful subclass of problems with a simple structure that allow the policy to be written directly in terms of the uncontrolled (passive) dynamics of the environment and the goals of the agent. However, there have been no learning algorithms for this class of models. In this research, we develop a robust learning approach to linearly solvable MDPs. To exploit the simple solution for general problems, we show how to construct passive dynamics from any transition matrix, use Bayesian updating to estimate the model parameters and apply approximate and efficient Bayesian exploration to speed learning. In addition, we reduce the computational cost of learning using intermittent Bayesian updating and policy solving. We also gave a polynomial theoretical time complexity bound for the convergence of our learning algorithm, and demonstrate a linear bound for the subclass of the reinforcement learning problems with the property that the transition error depends only on the agent itself. Test results for our algorithm in a grid world are presented, comparing our algorithm with the BEB algorithm. The results showed that our algorithm learned more than the BEB algorithm without losing convergence speed, so that the advantage of our algorithm increased as the environment got more complex. We also showed that our algorithm's performance is more stable after convergence. Finally, we show how to apply our approach to the Cellular Telephones problem by defining the passive dynamics.

  1. [Bellman, 2003] R. Bellman. Dynamic programming. Dover Publications, 2003.
  2. [Dearden et al., 1998] R. Dearden, N. Friedman, and S. Rus- sell. Bayesian q-learning. In National Conference on Ar- tificial Intelligence, pages 761-768.
  3. [Kaelbling et al., 1996] L.P. Kaelbling, M.L. Littman, and A.W. Moore. Reinforcement learning: A survey. Journal of Artificial Intelligence Research, 4, 1996.
  4. [Kolter and Ng, 2009] J.Z. Kolter and A.Y. Ng. Near- bayesian exploration in polynomial time. In International Conference on Machine Learning, pages 513-520. ACM, 2009.
  5. [Pitman and Yor, 1997] J. Pitman and M. Yor. The two- parameter poisson-dirichlet distribution derived from a stable subordinator. The Annals of Probability, 25(2):855- 900, 1997.
  6. [Poupart, 2007] P. Poupart. Tutorial on bayesian methods for reinforcement learning. In ICML, 2007.
  7. [Puterman, 1994] M.L. Puterman. Markov decision pro- cesses: Discrete stochastic dynamic programming. John Wiley & Sons, Inc., 1994.
  8. [Seijen and Whiteson, 2009] H.V. Seijen and S. Whiteson. Postponed updates for temporal-difference reinforcement learning. In International Conference on Intelligent Sys- tems Design and Applications, pages 665-672. IEEE, 2009.
  9. S. Singh and D. Bertsekas. Re- inforcement learning for dynamic channel allocation in cellular telephone systems. Advances in neural informa- tion processing systems, pages 974-980, 1997.
  10. [Singh, 1997] S. Singh. Dynamic channel allocation in cel- lular telephones: a demo. http://web.eecs.umich.edu/ ∼ baveja/Demo.html, 1997. Link
  11. [Strens, 2000] M.J.A. Strens. A bayesian framework for re- inforcement learning. In International Conference on Ma- chine Learning, pages 943-950, 2000.
  12. [Sutton, 1988] R.S. Sutton. Learning to predict by the meth- ods of temporal differences. Machine learning, 3(1):9-44, 1988.
  13. [Teh et al., 2006] Y.W. Teh, M.I. Jordan, M.J. Beal, and D.M. Blei. Hierarchical dirichlet processes. Journal of the American Statistical Association, 101(476):1566- 1581, 2006.
  14. [Thrun, 1992] S.B. Thrun. The role of exploration in learn- ing control with neural networks. In In Handbook of Intel- ligent Control: Neural, Fuzzy and Adaptive Approaches, 1992.
  15. [Todorov, 2009] E. Todorov. Efficient computation of opti- mal actions. Proceedings of the national academy of sci- ences, 106(28):11478-11483, 2009.

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

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