Timezone: »

 
Poster
On Efficiency in Hierarchical Reinforcement Learning
Zheng Wen · Doina Precup · Morteza Ibrahimi · Andre Barreto · Benjamin Van Roy · Satinder Singh

Tue Dec 08 09:00 AM -- 11:00 AM (PST) @ Poster Session 1 #500
in Poster Session 2 »

Hierarchical Reinforcement Learning (HRL) approaches promise to provide more efficient solutions to sequential decision making problems, both in terms of statistical as well as computational efficiency. While this has been demonstrated empirically over time in a variety of tasks, theoretical results quantifying the benefits of such methods are still few and far between. In this paper, we discuss the kind of structure in a Markov decision process which gives rise to efficient HRL methods. Specifically, we formalize the intuition that HRL can exploit well repeating "subMDPs", with similar reward and transition structure. We show that, under reasonable assumptions, a model-based Thompson sampling-style HRL algorithm that exploits this structure is statistically efficient, as established through a finite-time regret bound. We also establish conditions under which planning with structure-induced options is near-optimal and computationally efficient.

Author Information

Zheng Wen (DeepMind)
Doina Precup (DeepMind)
Morteza Ibrahimi (DeepMind)
Andre Barreto (DeepMind)
Benjamin Van Roy (Stanford University)
Satinder Singh (DeepMind)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors