Proceedings

Efficient Reinforcement Learning in Factored MDPs

Download BibTeX Cite

Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence. Machine Learning. Pages 740-746.

© 1999 International Joint Conferences on Artificial Intelligence

Abstract

We present a provably efficient and near-optimal algorithm for reinforcement learning in Markov decision processes (MDPs) whose transition model can be factored as a dynamic Bayesian network (DBN). Our algorithm generalizes the recent E 3 algorithm of Kearns and Singh, and assumes that we are given both an algorithm for approximate planning, and the graphical structure (but not the parameters) of the DBN. Unlike the original E 3 algorithm, our new algorithm exploits the DBN structure to achieve a running time that scales polynornially in the number of parameters of the DBN, which may be exponentially smaller than the number of global states.

  1. [Boutilier et al., 1999] C. Boutilier, T. Dean, and S. Hanks. De- ~ision theoretic planning: Structural assumptions and computa- tiOnal leverage. Journal of Artificial Intelligence Research, 1999. To appear.
  2. [Boyen and Koller, 1998] X. Boyen and D. Koller. Tractable in- ference for complex stochastic processes. In Proc. UA/, pages 33-42, 1998.
  3. [Dobrushin, 1956] R.L. Dobrushin. Central limit theorem for non- stationary Markov chains. Theory of Probability and its Applica- tions, pages 65-80, 1956.
  4. [Forbes eta/., 1995] J. Forbes, T. Huang, K. Kanazawa, and S.J. Russell. The BATmobile: Towards a Bayesian automated taxi. In Proc. IJCAI, 1995. IJCAI
  5. [Heckerman, 1995] D. Heckerman. A tutorial on learning with Bayesian networks. Technical Report MSR-TR-95-06, Microsoft Research, 1995.
  6. [Howard and Matheson, 1984] R. A. Howard and J. E. Matheson. Influence diagrams. In R. A. Howard and J. E. Matheson, editors, R. eadings on the Principles and Applications of Decision Analy- SIS, pages 721-762. Strategic Decisions Group, Menlo Park, Cal- ifornia, 1984.
  7. [Jensenetal., 1989] F.V. Jensen, U. Kjrerulff, K.G. Olesen, and J. Pedersen. An expert system for control of waste water treatment-a pilot project. Technical report, Judex Datasystemer AJS, Aalborg, 1989. In Danish.
  8. [Je~m and Sinclair, 1993] M. Jerrum and A. Sinclair. Polynomial- time approximation algorithms for the Ising model. SIAM Jour- nal on Computing, 22:1087~1116, 1993.
  9. [Kearns and Singh, 1998] M. Kearns and S.P. Singh. Near-optimal performance for reinforcement learning in polynomial time. In Proc. ICML, pages 260-268, 1998. [
  10. Kearns ~tal., 199?
  11. M. Kearns, Y. Mansour, and A. Ng. A sparse samphng algonthrn for near-optimal planning in large markov decision processes. In these proceedings, 1999.
  12. [Koller and Parr, 1999] D. Koller and R. Parr. Computing factored value functions for policies in structured MDPs. In these pro- ceedings, 1999. IJCAI
  13. [Lindvall, 1992] T. Lindvall. Lectures on the Coupling Method. Wi- ley, 1992.
  14. [Meuleau et al., 1998] N. Meuleau, M. Hauskrecht, K-E. Kim, L. Peshkin, L.P. Kaelbling, T. Dean, and C. Boutilier. Solving very large weakly coupled Markov decision processes. In Proc. AAAI, pages 165-172, 1998.

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

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