查看文章

Factored representations, model-based learning, and hierarchies are well-studied techniques for improving the learning efficiency of reinforcement-learning algorithms in largescale state spaces. We bring these three ideas together in a new algorithm we call MaxQRmax. Our algorithm solves two open problems from the reinforcement-learning literature. First, it shows how models can improve learning speed in the hierarchy-based MaxQ framework without disrupting opportunities for state abstraction. We illustrate the resulting performance gains in a set of example domains. Second, we show how hierarchies can augment existing factored exploration algorithms to achieve not only low sample complexity for learning, but provably efficient planning as well. We prove polynomial bounds on the computational effort needed by MaxQ-Rmax to attain nearoptimal performance within the hierarchy with high probability.