Efficient Reinforcement Learning in Factored MDPs

Kearns, Michael J.; Koller, Daphne

Efficient Reinforcement Learning in Factored MDPs

Download BibTeX Cite

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

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.

Michael J. Kearns, and Daphne Koller. 1999. Efficient Reinforcement Learning in Factored MDPs. In Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence, IJCAI-99. IJCAI, 740–746. https://ijcai.org/proceedings/1999/106

@inproceedings{ijcai1999p106,
  title     = {Efficient Reinforcement Learning in Factored MDPs},
  author    = {Kearns, Michael J. and Koller, Daphne},
  booktitle = {Proceedings of the Sixteenth International Joint Conference on
               Artificial Intelligence, {IJCAI-99}},
  publisher = {International Joint Conferences on Artificial Intelligence},
  editor    = {Thomas Dean},
  pages     = {740--746},
  year      = {1999},
  note      = {Machine Learning},
  url       = {https://ijcai.org/proceedings/1999/106},
}

TY  - CPAPER
TI  - Efficient Reinforcement Learning in Factored MDPs
AU  - Kearns, Michael J.
AU  - Koller, Daphne
T2  - Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence, IJCAI-99
PB  - International Joint Conferences on Artificial Intelligence
PY  - 1999
SP  - 740
EP  - 746
UR  - https://ijcai.org/proceedings/1999/106
ER  -