Learning World Graphs to Accelerate Hierarchical Reinforcement Learning
deep learning reinforcement learning deep reinforcement learning world model hierarchical reinforcement learning planning salesforce research machine learning navigation pivot states ai artificial intelligence
The goal of hierarchical reinforcement learning is to divide a task into different levels of coarseness with the top-level agent planning only over a high-level view of the world and each subsequent layer having a more detailed view. This paper proposes to learn a set of important states as well as their connections to each other as a high-level abstraction.

https://arxiv.org/abs/1907.00664

Abstract:
In many real-world scenarios, an autonomous agent often encounters various tasks within a single complex environment. We propose to build a graph abstraction over the environment structure to accelerate the learning of these tasks. Here, nodes are important points of interest (pivotal states) and edges represent feasible traversals between them. Our approach has two stages. First, we jointly train a latent pivotal state model and a curiosity-driven goal-conditioned policy in a task-agnostic manner. Second, provided with the information from the world graph, a high-level Manager quickly finds solution to new tasks and expresses subgoals in reference to pivotal states to a low-level Worker. The Worker can then also leverage the graph to easily traverse to the pivotal states of interest, even across long distance, and explore non-locally. We perform a thorough ablation study to evaluate our approach on a suite of challenging maze tasks, demonstrating significant advantages from the proposed framework over baselines that lack world graph knowledge in terms of performance and efficiency.

Authors: Wenling Shang, Alex Trott, Stephan Zheng, Caiming Xiong, Richard Socher
 Hi there. Today we're looking at learning world graphs to accelerate hierarchical reinforcement learning by Wenling Sheng et al from Salesforce Research. This work is based in the world of reinforcement learning and especially hierarchical reinforcement learning. So in hierarchical reinforcement learning the idea is that in order to perform a task like in this case they perform all of their experiments on mazes like this. So imagine you have this maze and this red thing here is the agent and the goal is the green square and the gray things obviously are walls and the black things are everywhere the agent can move. The agent can always move one step in any direction that it wants and that isn't blocked by a wall. So in order to fulfill such a task the agent needs to take many many steps like go here here here here here here each one of those is a step. In addition this specific maze has an additional property namely that there's a locked door here and first you need to pick up the key to basically to open the locked door. So in order to reach the goal the agent needs first to pick up the key then open the door then go to the goal and each one of these it has to traverse many many steps. So the idea in hierarchical reinforcement learning is that you have two parts to it to the agent. So your agent which is this entire box here is divided into what's called a manager and a worker and this is a divide. So what the manager sees the manager sees basically I do an example here they do it differently but the manager could see large could see the world basically only in these large chunks right and it doesn't really care what is in or it cares what is in the chunks but it doesn't distinguish points within the chunks it just knows about these these chunks basically and what the manager will say oh first I need to go to this chunk here then because there's the key in this chunk and then I need to go to this chunk here because there is the door and then I need to go to this chunk here because there's the goal. So the in the view of the manager which has a very high level view of the world is the the action sequence is down here over here then over here. Those are like three actions that's a pretty simple and then the manager would pass this information to the worker and it would say hey worker please go to this state here please go to the first state and then the worker would be tasked with basically moving the individual steps to go not to the final goal but only to go to that chunk and then in that chunk the worker would go to the key and then once it has the key the manager would say good job now please perform the second action which is go to to this chunk here so the second action that the worker would so you basically get the idea whoops I am doing something here you get the idea that the I'm creating text boxes that the worker and the manager work together and that the manager has a high level view of the world and then the worker can basically execute the actual actions that the manager has decided on in a fine-grained way. So this is gives you several advantages namely the manager can plan high level and far away things and then the worker really only has to care about its close neighborhood because each step the manager proposes is a fairly short range so the worker can implement it. They do this in a kind of different way so let's actually start from the back from of this paper which is I find is a bit more explanatory and it makes a bit more sense to look at it what they propose is to learn a world graph so in a world graph what is a world graph a world graph consists of two things first a set of states which is the are the blue states here so all these blue states which are so-called pivot states or important states so these are states in the world that are very important determined by some measure right so these are basically states that look at look at where they are they're often at like narrow passes you see here here they're at these narrow passes so basically if you if you reach those states as an intermediary goal then you can basically go a lot of places from here so these are very let's say powerful states and these states are connected by a neighborhood graph so basically which states of these are close to each other and for example here you would connect of course those two because they're neighbors those you would probably connect those some I'm attempting to to kind of draw the world graph you could you might connect those doesn't need to be like a tree it can be like such so you see that the graph kind of takes shape these are fairly reachable so whenever a node in the graph whenever one of these important states is fairly easily reachable by some other state it's designated as a neighbor so with that with this world graph here this is what you get you get an abstraction basically you get a set of states with connections between them that says how easy or hard is it to reach from one state to the other if you have these things then you can really easily imagine a hierarchical reinforcement learning algorithm that now in let incorporates this information namely the manager will only use the important states to plan so for example if the goal the goal isn't drawn in here but let's say the goal is here and then the door the door is here it's a locked door here and then the key let's draw in the key come on okay this doesn't want to all right the key is somewhere let's say here there's the key he is this all right then the no let's put the key further away come on door here I'm off with the colors and key here all right so what would the manager do the manager would then say ah okay the keys here so this would be a good state to reach of my importance if the manager is only allowed to go important states right so the manager says because it has the graph right it says aha this state is easily reachable from let's say this state and this state is easily reachable from this state so it plans go here and go here and then go here then get the key right this is a kind of a micro action that is not in the importance they then I need to you know go here this is reachable from this state that's reachable from this state and from this state and that's reachable from my origin so from the key then next go here go here go here go here and then open the door and then of course go here and solve the the task the worker then would only ever need to implement the following it starts here and it says aha I need to go here what do I need to do I need to go for example down and over and now once I've done this I need to go here so I need to go right down right so you see the worker only ever has to care about going from one hop to the next hop making it really easy for the worker while the manager only has these blue states available which makes its search space much more much more condensed and much more much more overviewable especially with the nodes in between the world graph so that's if you have the world graph right if you have this set of states and how important are how easily they reachable reachable they are between each other you can very easily do a reinforcement learning approach that that is a hierarchical has the manager plan on the world graph has and then has the worker implement the fine-grained actions and there is already a method that does this this paper here uses feudal networks so we won't go into that later just saying it's pretty easy if you have those things so the real question is how do they learn the world graph and what they do is the following and they describe it here in kind of this sorry this way what they want to to finally learn is a prior that tells them for a given state how important it is it and that's a beta prior a beta distribution is a continuous approximation on a on a kind of a binary zero one variable so how do they do it they use an LSTM to encode trajectories so these are trajectories from kind of rollouts of policy and then the the LSTM encodes it and for each step it outputs this posterior over the what's called these latent variables here they say how important is a state so these are the posteriors whereas this over here is the prior and the posterior of course only make sense in context of a trajectory that's why the ultimate decision happens for the prior because the state needs to be important or not important to any trajectory so what they do is they roll out policies and they have certain methods of of doing this so they have they have random exploration of curiosity goals but they also train this continuously so they updated continuously via this what's called a goal condition policy and what a goal condition policy is basically is you put the agent somewhere in the maze actually let's use this maze over here you put the agent somewhere in the maze let's say here you for example make a bunch of ran make a random exploration let's say here so you know these two things are reachable and then you train the agency go from here to here right this is your goal now the agent tries to kind of reconstruct this random walk to there and you can riff so so this is how you train an agent to go it basically go from any two well reachable states to each other right from here to here and so on now you won't train it to go directly from here to over here because a random walk would be very hard for a random walk to find its way over there but what you end up with is is somehow an agent that is able to reach close by states and that's exactly what the worker is supposed to do right here and so of of these trajectories you can then unroll them and decide on the kind of on these on these pivotal states so how do you do that and this is where this top part here comes in so down here you input the trajectory and you output how important is each state all right and now you see in this example here the light color means that the LSTM decides this state isn't important and the darker orange color means the LSTM decides this state is important so what you do next is the states where it decides it is important and notice the beginning at the end are always important it feeds to a second LSTM as an input you see here here here so in this case of these two of these six states in the trajectory three are important namely the start the end and this one here where the LSTM decides hey that's important that goes into a second LSTM which is generator so this here is an encoder and this here is a decoder and what it does is it decodes the sequence of actions right here given nothing just given this it decodes a sequence of actions and at the end what you want is that the actions output here reconstruct the actions input this might sound a little confusing but the core value of this is what you want is to reconstruct the actions of the trajectory taken given only the important states what does this mean in our example in our example here this means if I have to go from here to here right and for example I took the following path this is this so right right down down right this is these were my action sequence now if I only have the start the end and one state in between let's say this one right then can I reconstruct what actions were taken and if I erase the blue thing and I tell you I went from here via here to here then you could very much reconstruct the actions here so this state here is a good candidate for being an important state whereas if it were a different state if it were for example if I told you I went from over here to here and then to here you'd say well this could be either something like this or it could be a path like this right it could be many many paths or like this could be many paths leading from here to here so this state here is not probably not very important so that's kind of how they how they learn which one are the important state via this encoding trajectories in an LSTM and trying to reconstruct the state the actions taken in the trajectory given only the states that were deemed important by the LSTM so that's how you train the LSTM to recognize important states and once you've recognized the important states in a trajectory you can then use those to learn prior so basically you ask over all possible trajectories which of the states are generally important and that's how you end up with these blue states all right and then the last part is to connect the blue states and that is fairly easily done in their approach what they say is all right we have blue states we should be pick one and we do a random walk from it right random walk random walk random walk if we hit another blue state like this one here in the random walk we simply say well there are probably neighbors so we do this a bunch of times if you hit the blue states of course without hitting another blue state first then you connect the two in a graph so these would be connected these would probably be connected what we ended up at the beginning right you have this graph maybe these two are connected and so on so this gives you this world graph and now you end up with a set of important states and connections between them that tell you which ones are easily reachable from each other so you can train the manager on that you can train the worker as we said before to simply select two close by states train it to go from one to the other that by the worker will learn that so in essence that's how they they do it you can look at the experiments themselves they show that this basically transfers so if you train like this pre train then you can give more specific and more complicated tasks and this will this will rapidly accelerate the learning of this yeah look at the experiments if you have time that was it for me thank you for listening
 Hi there. Today we're looking at learning world graphs to accelerate
 hierarchical reinforcement learning by Wenling Sheng et al from Salesforce
 Research. This work is based in the world of reinforcement learning and
 especially hierarchical reinforcement learning. So in hierarchical reinforcement
 learning the idea is that in order to perform a task like in this case they
 perform all of their experiments on mazes like this. So imagine you have this
 maze and this red thing here is the agent and the goal is the green square
 and the gray things obviously are walls and the black things are everywhere the
 agent can move. The agent can always move one step in any direction that it
 wants and that isn't blocked by a wall. So in order to fulfill such a task the
 agent needs to take many many steps like go here here here here here here each
 one of those is a step. In addition this specific maze has an additional property
 namely that there's a locked door here and first you need to pick up the key to
 basically to open the locked door. So in order to reach the goal the agent needs
 first to pick up the key then open the door then go to the goal and each one of
 these it has to traverse many many steps. So the idea in hierarchical reinforcement
 learning is that you have two parts to it to the agent. So your agent which is
 this entire box here is divided into what's called a manager and a
 worker and this is a divide. So what the manager sees the manager sees basically
 I do an example here they do it differently but the manager could see
 large could see the world basically only in these large chunks right and it
 doesn't really care what is in or it cares what is in the chunks but it
 doesn't distinguish points within the chunks it just knows about these these
 chunks basically and what the manager will say oh first I need to go to this
 chunk here then because there's the key in this chunk and then I need to go to
 this chunk here because there is the door and then I need to go to this chunk
 here because there's the goal. So the in the view of the manager which has a very
 high level view of the world is the the action sequence is down here over here
 then over here. Those are like three actions that's a pretty simple and then
 the manager would pass this information to the worker and it would say hey worker
 please go to this state here please go to the first state and then the worker
 would be tasked with basically moving the individual steps to go not to the
 final goal but only to go to that chunk and then in that chunk the worker would
 go to the key and then once it has the key the manager would say good job now
 please perform the second action which is go to to this chunk here so the
 second action that the worker would so you basically get the idea whoops I am
 doing something here you get the idea that the I'm creating text boxes that
 the worker and the manager work together and that the manager has a high level
 view of the world and then the worker can basically execute the actual actions
 that the manager has decided on in a fine-grained way. So this is gives you
 several advantages namely the manager can plan high level and far away things
 and then the worker really only has to care about its close neighborhood
 because each step the manager proposes is a fairly short range so the worker
 can implement it. They do this in a kind of different way so let's actually start
 from the back from of this paper which is I find is a bit more explanatory and
 it makes a bit more sense to look at it what they propose is to learn a world
 graph so in a world graph what is a world graph a world graph consists of
 two things first a set of states which is the are the blue states here so all
 these blue states which are so-called pivot states or important states so
 these are states in the world that are very important determined by some measure
 right so these are basically states that look at look at where they are they're
 often at like narrow passes you see here here they're at these narrow passes so
 basically if you if you reach those states as an intermediary goal then you
 can basically go a lot of places from here so these are very let's say
 powerful states and these states are connected by a neighborhood graph so
 basically which states of these are close to each other and for example here
 you would connect of course those two because they're neighbors those you
 would probably connect those some I'm attempting to to kind of draw the world
 graph you could you might connect those doesn't need to be like a tree it can be
 like such so you see that the graph kind of takes shape these are fairly
 reachable so whenever a node in the graph whenever one of these important
 states is fairly easily reachable by some other state it's designated as a
 neighbor so with that with this world graph here this is what you get you get
 an abstraction basically you get a set of states with connections between them
 that says how easy or hard is it to reach from one state to the other if you
 have these things then you can really easily imagine a hierarchical
 reinforcement learning algorithm that now in let incorporates this information
 namely the manager will only use the important states to plan so for example
 if the goal the goal isn't drawn in here but let's say the goal is here and then
 the door the door is here it's a locked door here and then the key let's draw in
 the key come on okay this doesn't want to all right the key is somewhere let's
 say here there's the key he is this all right then the no let's put the key
 further away come on door here I'm off with the colors and key here all right
 so what would the manager do the manager would then say ah okay the keys here so
 this would be a good state to reach of my importance if the manager is only
 allowed to go important states right so the manager says because it has the
 graph right it says aha this state is easily reachable from let's say this
 state and this state is easily reachable from this state so it plans go here and
 go here and then go here then get the key right this is a kind of a micro
 action that is not in the importance they then I need to you know go here
 this is reachable from this state that's reachable from this state and from this
 state and that's reachable from my origin so from the key then next go here
 go here go here go here and then open the door and then of course go here and
 solve the the task the worker then would only ever need to implement the
 following it starts here and it says aha I need to go here what do I need to do
 I need to go for example down and over and now once I've done this I need to
 go here so I need to go right down right so you see the worker only ever has to
 care about going from one hop to the next hop making it really easy for the
 worker while the manager only has these blue states available which makes its
 search space much more much more condensed and much more much more
 overviewable especially with the nodes in between the world graph so that's if
 you have the world graph right if you have this set of states and how important
 are how easily they reachable reachable they are between each other you can very
 easily do a reinforcement learning approach that that is a hierarchical has
 the manager plan on the world graph has and then has the worker implement the
 fine-grained actions and there is already a method that does this this
 paper here uses feudal networks so we won't go into that later just saying
 it's pretty easy if you have those things so the real question is how do
 they learn the world graph and what they do is the following and they describe it
 here in kind of this sorry this way what they want to to finally learn is a prior
 that tells them for a given state how important it is it and that's a beta
 prior a beta distribution is a continuous approximation on a on a kind
 of a binary zero one variable so how do they do it they use an LSTM to encode
 trajectories so these are trajectories from kind of rollouts of policy and then
 the the LSTM encodes it and for each step it outputs this posterior over the
 what's called these latent variables here they say how important is a state
 so these are the posteriors whereas this over here is the prior and the posterior
 of course only make sense in context of a trajectory that's why the ultimate
 decision happens for the prior because the state needs to be important or not
 important to any trajectory so what they do is they roll out policies and they
 have certain methods of of doing this so they have they have random
 exploration of curiosity goals but they also train this continuously so they
 updated continuously via this what's called a goal condition policy and what
 a goal condition policy is basically is you put the agent somewhere in the maze
 actually let's use this maze over here you put the agent somewhere in the maze
 let's say here you for example make a bunch of ran make a random exploration
 let's say here so you know these two things are reachable and then you train
 the agency go from here to here right this is your goal now the agent tries to
 kind of reconstruct this random walk to there and you can riff so so this is how
 you train an agent to go it basically go from any two well reachable states to
 each other right from here to here and so on now you won't train it to go
 directly from here to over here because a random walk would be very hard for a
 random walk to find its way over there but what you end up with is is somehow an
 agent that is able to reach close by states and that's exactly what the
 worker is supposed to do right here and so of of these trajectories you can then
 unroll them and decide on the kind of on these on these pivotal states so how do
 you do that and this is where this top part here comes in so down here you
 input the trajectory and you output how important is each state all right and
 now you see in this example here the light color means that the LSTM decides
 this state isn't important and the darker orange color means the LSTM decides
 this state is important so what you do next is the states where it decides it
 is important and notice the beginning at the end are always important it feeds to
 a second LSTM as an input you see here here here so in this case of these two
 of these six states in the trajectory three are important namely the start
 the end and this one here where the LSTM decides hey that's important that goes
 into a second LSTM which is generator so this here is an encoder and this here is
 a decoder and what it does is it decodes the sequence of actions right here given
 nothing just given this it decodes a sequence of actions and at the end what
 you want is that the actions output here reconstruct the actions input this might
 sound a little confusing but the core value of this is what you want is to
 reconstruct the actions of the trajectory taken given only the important
 states what does this mean in our example in our example here this means
 if I have to go from here to here right and for example I took the following
 path this is this so right right down down right this is these were my action
 sequence now if I only have the start the end and one state in between let's
 say this one right then can I reconstruct what actions were taken and
 if I erase the blue thing and I tell you I went from here via here to here then
 you could very much reconstruct the actions here so this state here is a
 good candidate for being an important state whereas if it were a different
 state if it were for example if I told you I went from over here to here and
 then to here you'd say well this could be either something like this or it
 could be a path like this right it could be many many paths or like this
 could be many paths leading from here to here so this state here is not probably
 not very important so that's kind of how they how they learn which one are the
 important state via this encoding trajectories in an LSTM and trying to
 reconstruct the state the actions taken in the trajectory given only the states
 that were deemed important by the LSTM so that's how you train the LSTM to
 recognize important states and once you've recognized the important states
 in a trajectory you can then use those to learn prior so basically you ask over
 all possible trajectories which of the states are generally important and
 that's how you end up with these blue states all right and then the last part
 is to connect the blue states and that is fairly easily done in their approach
 what they say is all right we have blue states we should be pick one and we do a
 random walk from it right random walk random walk random walk if we hit another
 blue state like this one here in the random walk we simply say well there are
 probably neighbors so we do this a bunch of times if you hit the blue states of
 course without hitting another blue state first then you connect the two in a
 graph so these would be connected these would probably be connected what we
 ended up at the beginning right you have this graph maybe these two are connected
 and so on so this gives you this world graph and now you end up with a set of
 important states and connections between them that tell you which ones are easily
 reachable from each other so you can train the manager on that you can train
 the worker as we said before to simply select two close by states train it to
 go from one to the other that by the worker will learn that so in essence
 that's how they they do it you can look at the experiments themselves they show
 that this basically transfers so if you train like this pre train then you can
 give more specific and more complicated tasks and this will this will rapidly
 accelerate the learning of this yeah look at the experiments if you have time
 that was it for me thank you for listening