Hierarchical learning and decision making

par/by Stuart Russell
Computer Science Division
University of California, Berkeley

Effective behaviour in complex environments requires some form of hierarchical structure. The first part of the talk covers hierarchical reinforcement learning, wherein guidance as to the correct hierarchical structure can be supplied to an agent in the form of a *partial program* in which choices may be left unspecified. The ALisp language - an partial programming extension of Lisp - includes reinforcement learning algorithms that converge to the optimal complete program consistent with the given partial program. ALisp includes constructs for specifying asynchronous concurrent activities. ALisp shows promise as a tool for scaling up reinforcement learning. The second part of the talk covers lookahead decision making with hierarchical constraints on behavior. Here the setting is classical hierarchical planning. We resolve a longstanding open problem by defining *angelic* semantics for high-level actions and providing the first algorithms capable of proving that a high-level plan is correct and optimal without considering its concrete implementations. We also consider online hierarchical search with bounded lookahead. [Joint work with Ron Parr, David Andre, Bhaskara Marthi, Andy Zimdars, David Latham, Carlos Guestrin, Jason Wolfe] Stuart Russell was born in Portsmouth, England. He received his B.A. with first-class honours in Physics from Wadham College, Oxford University in 1982, and his Ph.D. in Computer Science from Stanford in 1986. He then joined the faculty of the University of California, Berkeley, where he is currently Professor and Chair of Computer Science. In 2003 he was inducted as a Fellow of the Association for Computing Machinery. Stuart Russell is an author of the textbook Artificial Intelligence: A Modern Approach (together with Peter Norvig).