Discovering Hierarchy in Reinforcement Learning with HEXQ

Discovering Hierarchy in Reinforcement Learning with HEXQ

Bernhard Hengst bernhardh@b681530cba1aa8114431d950.au Computer Science and Engineering,University of New South Wales,UNSW Sydney2052AUSTRALIA

Abstract

An open problem in reinforcement learning

is discovering hierarchical structure.HEXQ,

an algorithm which automatically attempts

to decompose and solve a model-free fac-

tored MDP hierarchically is described.By

searching for aliased Markov sub-space re-

gions based on the state variables the algo-

rithm uses temporal and state abstraction to

construct a hierarchy of interlinked smaller

MDPs.

1.Introduction

Bellman(1961)stated that sheer enumeration would not solve problems of any signi?cance.In reinforce-ment learning the size of the state space scales ex-ponentially with the number of variables.Designers try to manually decompose more complex problems to make them tractable.Finding good decompositions is usually an art-form.Many researchers have either ignored where decompositions come from or pointed to the desirability of automating this task(Boutilier et al.,1999;Hauskrecht et al.,1998;Dean&Lin, 1995).More recently,Dietterich(2000b)concluded that the biggest open problem in reinforcement learn-ing is to discover hierarchical structure.

It was recognised by Ashby(1956)that learning is worthwhile only when the environment shows con-straint.One type of constraint present in many en-vironments is the repetition of sub-structures.Ashby stated that repetition is of considerable practical im-portance in the regulation of very large systems.Rep-etitions are commonplace.They are evident,for exam-ple,at the molecular level,in daily routines,in o?ce layouts or even in just walking.One reason that re-inforcement learning scales poorly is that sub-policies, such as walking,need to be relearnt in every context. It makes more sense to learn how to walk only once and then reuse this skill wherever it is required.A reinforcement learning agent that can?nd and learn reusable sub-tasks and in turn employ them to learn higher level skills would be more e?cient.

In the rest of this paper we will describe the opera-tion of a hierarchical reinforcement learning algorithm, HEXQ,which attempts to solve model-free MDPs more e?ciently by?nding and exploiting repeatable sub-structures in the environment.The algorithm is designed to automatically discover state and temporal abstractions,?nd appropriate sub-goals and construct a hierarchical representation to solve the overall MDP. As a running example we will use the taxi task(Diet-terich,2000a)to illustrate how the algorithm works. We also show results for a noisy Tower of Hanoi puzzle.

2.Representation and Assumptions

We start with the usual formulation of a?nite MDP with discrete time steps,states and actions(Sutton &Barto,1998).The objective is to?nd an optimal policy by maximising the expected value of future dis-counted rewards represented by the action-value func-tion,Q(Watkins&Dayan,1992).We also employ semi-MDP theory(Puterman,1994)which generalizes MDPs to models with variable time between decisions. We assume that the state is de?ned by a vector of d state variables,x=(x1,x2,...,x d).Large MDPs are naturally described in this factored form.In this pa-per we consider only negative reward non-discounted ?nite horizon MDPs(stochastic shortest path prob-lems),but the algorithm has been extended to han-dle general?nite MDPs.The issue of solving MDPs e?ciently is largely orthogonal and complementary to the decomposition techniques discussed here.We have used simple one-step backup Q-learning throughout. HEXQ attempts to decompose a MDP by dividing the state space into nested sub-MDP regions.De-composition is possible when(1)some of the vari-ables in the state vector represent features in the en-vironment that change at less frequent time intervals, (2)variables that change value more frequently retain their transition properties in the context of the more persistent variables and(3)the interface between re-gions can be controlled.For example,if a robot nav-

igates around four equally sized rooms with intercon-necting doorways(Parr,1998)the state space can be represented by the two variables,room-identi?er and position-in-room.The room changes less frequently than the position.The position in each room needs to be represented consistently to allow generalisation across rooms,for example,by numbering cells from top to bottom,left to right in each room.Most represen-tations naturally label repeated sub-structures in this way.Finally we need to be able to?nd sub-policies to exit through each doorway with certainty.This will become clearer in the next sections.In the absence of these conditions or when they are only partially present HEXQ will nevertheless solve the MDP dis-covering abstractions where it can.In the worst case it has to solve the‘?at’problem.

3.The Taxi Domain

Dietterich(2000a)created the taxi task(Figure1)to demonstrate MAXQ hierarchical reinforcement learn-ing.For MAXQ the structure of the hierarchy is spec-i?ed by the user.We will use the same domain to illustrate how hierarchical decomposition can be au-tomated.We will keep our description of HEXQ gen-eral,but use the taxi domain to illustrate the basic concepts.We start by reviewing the taxi problem.

In the taxi domain,a taxi,started at a random loca-tion,navigates around a5-by-5grid world to pick up and then put down a passenger.There are four possi-ble source and destination locations,designated R,G, Y and B.We encode these1,2,3,4respectively.They are called taxi ranks.The objective of the taxi agent is to go to the source rank,pick up the passenger,then navigate with the passenger in the taxi to the desti-nation rank and put down the passenger.The source and destination ranks are also chosen at random for each new trial.At each …… 此处隐藏：480字，全部文档内容请下载后查看。喜欢就下载吧 ……