---
title: "Efficient Reinforcement Learning in Factored MDPs"
authors:
  - "Michael J. Kearns"
  - "Daphne Koller"
doi: ""
url: "https://ijcai.org/proceedings/1999/106"
pdf: "https://ijcai.org/proceedings/1999/0106.pdf"
venue: "Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence"
year: 1999
pages: "740-746"
track: "Machine Learning"
keywords:
---

# Efficient Reinforcement Learning in Factored MDPs

Michael J. Kearns, Daphne Koller

*Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence*, 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.