Learning model-based planning from scratch
machine learning artificial intelligence ai deep learning reinforcement learning deep mind research academia paper review imagination planning agents
https://arxiv.org/abs/1707.06170

Abstract:
Conventional wisdom holds that model-based planning is a powerful approach to sequential decision-making. It is often very challenging in practice, however, because while a model can be used to evaluate a plan, it does not prescribe how to construct a plan. Here we introduce the "Imagination-based Planner", the first model-based, sequential decision-making agent that can learn to construct, evaluate, and execute plans. Before any action, it can perform a variable number of imagination steps, which involve proposing an imagined action and evaluating it with its model-based imagination. All imagined actions and outcomes are aggregated, iteratively, into a "plan context" which conditions future real and imagined actions. The agent can even decide how to imagine: testing out alternative imagined actions, chaining sequences of actions together, or building a more complex "imagination tree" by navigating flexibly among the previously imagined states using a learned policy. And our agent can learn to plan economically, jointly optimizing for external rewards and computational costs associated with using its imagination. We show that our architecture can learn to solve a challenging continuous control problem, and also learn elaborate planning strategies in a discrete maze-solving task. Our work opens a new direction toward learning the components of a model-based planning system and how to use them.

Authors:
Razvan Pascanu, Yujia Li, Oriol Vinyals, Nicolas Heess, Lars Buesing, Sebastien Racanière, David Reichert, Théophane Weber, Daan Wierstra, Peter Battaglia
 Hi there, today we're taking a look at learning model-based planning from scratch by DeepMind. So as a recap, what is model-based planning? Basically a model, also called an environment model, is just kind of a black box thing, you can imagine, where you have a state of your current environment, you put it in there and you have an action that you want to take, you put it in there as well. And the environment model tells you what the new state, S' here, and possibly also the new reward for taking that action is going to be. So this, of course it's always good to have such an environment model, because you can use it to plan ahead, but the authors here question how do you plan and propose a new algorithm to learn this planning. For now, people have mostly used heuristics to plan either things like A star search, where you have a maze and you want to go here, and you kind of have a heuristic, say the distance between the two points, but there's kind of walls in between, so you try to go there but then there's a wall and you kind of explore around it. So these are kind of the techniques that have existed so far. Also we've seen stuff like Monte Carlo tree search for AlphaGo and other things like this that are not really learned. So this kind of paper pros and mechanisms to learn how to plan using such a model. So basically they devise an algorithm or a framework, you can say, where they have this, what you see here, this schematic. This schematic tells you that you have this thing called a manager. Let me just quickly bring up my comment thingy thing. You can see here there's this kind of manager and this manager can decide to imagine or act. If it acts, then it simply takes kind of the current state and all the things that happened so far and decides on an action to do in the world. And then it kind of trains on the action like classic reinforcement learning. But if it decides to imagine, it can use its model of the world, its imagination model to perform an action and see what would happen if it did that action. And it can then also append that to the memory and use it to further learn. Even though it didn't do the action, it can imagine what happens. So how can it imagine? The authors in particular propose different methods of imagining. This graph you see there are proposed methods. The first two methods basically, so here every row is a method of imagining. The first method, the one step imagining, simply means you have the current state of the world, which is the grey blob here. And what you do is you always go from the current state of the world, imagine one step ahead. So basically you select the state to imagine from, you imagine one step. And if you decide to not take an action after that, but imagine again, because maybe you're not sure yet what you want to do, so you want to imagine another action, you would again go from this initial state, so this in the horizontal direction is time, time, internal time basically. You would again go from this state, imagine another action based on it, and so on, imagine another action. Until you're satisfied, you've imagined enough so you can actually take a real world step. In contrast, the end step strategy, so these are hard coded strategies as you can see. The learned part is which action should I take? The hard coded part is where do I base this action off? The end step strategy also selects the first state at first, imagines one action on top of it, but then always selects that new imagined action. So you can see here it selects this one to propose this action, and then it selects that imagined action to propose yet another action. So you can see it kind of imagines one path into the future instead of many paths, just one step ahead. And then lastly, this imagination tree strategy is basically the only one that's actually kind of a learned strategy where the manager can now propose any previously imagined or real world states in order to imagine from. So you always have the current world state, which is the first node in the graph. You select it, of course, at the beginning you have no choice. You imagine an action on top of it, but then you can select any of these two nodes to imagine from and here again the first is selected and action is imagined. Then you have three nodes. You can choose any of those where you want to imagine the next step. Here in this example, the manager selects this state right here and decides to imagine another action on top of it until it is satisfied and can then actually go over to plan to actually perform an action in the real world. So if you then decide to do an action in the real world, what you can do is you can take all of the things you've imagined and use that. So you see in this pathway here, this flows back to the manager. At some point it decides, okay, I've imagined enough and we can use all of these imagined steps in order to take a real world step. And after the real world step, the entire thing starts again. So that's how it learns to plan. Really interesting of course is this imagination tree strategy where it actually learns to plan ahead. So the model is described in detail in a formal manner and then it already goes over to experiments and there's this spaceship task where you have to get the spaceship to move around stuff and around these asteroids and get a reward. So you can see different imagination projectives here in the top row. You see the red ones is the kind of executed actions, the blue ones are imagined ones and you see the tree it's constructed. So first it takes an action right here, just without imagining. Then it imagines one step but then decides to take another action. It imagines two actions but decides on a third one. So you see to the left in this picture you see the first action. Then it imagines one action and decides to take an action. Then it imagines two actions and based on these imaginations, I'm going to guess it's fairly satisfied with the one that's very close to the target and it can then take an action. So it's pretty smart in that it sees that the second imagined action is fairly close to where it wants to go and it doesn't need to imagine yet another action. That then actually hits the target. It can go over to performing the action right away because the imagination gives enough information. So these kind of things are pretty cool to look at and check out the more experiments if you want to know. Here is even more experiments in discrete mazes. They feature multiple goals. They feature the system optimizing not only for its reward but also for kind of internal costs, so having a budget for imagining and optimizing not doing too many imagination steps. On this experiment the kind of thing that bugs me here is the fact that they didn't actually use the full imagination tree algorithm but the manager only selected from what you can see here. So do an actual action, then SJ0 is the first imagined state and SJK is the last imagined state. So basically the manager can only choose between actually acting, then doing this one step strategy and then doing kind of this end step strategy in each step. So it kind of limits the way it can plan but I'm going to guess they did this because otherwise they couldn't have trained the model and it seems a pretty reasonable simplification to make in order to get this to work. Also check out the paper if you want to see how all of these different parts are implemented. Of course you can guess most of them are neural networks and it's pretty standard so far and check out for the additional experiments. They're pretty cool. See you next time.
 Hi there, today we're taking a look at learning model-based planning from scratch by DeepMind.
 So as a recap, what is model-based planning?
 Basically a model, also called an environment model, is just kind of a black box thing,
 you can imagine, where you have a state of your current environment, you put it in there
 and you have an action that you want to take, you put it in there as well.
 And the environment model tells you what the new state, S' here, and possibly also the
 new reward for taking that action is going to be.
 So this, of course it's always good to have such an environment model, because you can
 use it to plan ahead, but the authors here question how do you plan and propose a new
 algorithm to learn this planning.
 For now, people have mostly used heuristics to plan either things like A star search,
 where you have a maze and you want to go here, and you kind of have a heuristic, say the
 distance between the two points, but there's kind of walls in between, so you try to go
 there but then there's a wall and you kind of explore around it.
 So these are kind of the techniques that have existed so far.
 Also we've seen stuff like Monte Carlo tree search for AlphaGo and other things like this
 that are not really learned.
 So this kind of paper pros and mechanisms to learn how to plan using such a model.
 So basically they devise an algorithm or a framework, you can say, where they have this,
 what you see here, this schematic.
 This schematic tells you that you have this thing called a manager.
 Let me just quickly bring up my comment thingy thing.
 You can see here there's this kind of manager and this manager can decide to imagine or
 act.
 If it acts, then it simply takes kind of the current state and all the things that happened
 so far and decides on an action to do in the world.
 And then it kind of trains on the action like classic reinforcement learning.
 But if it decides to imagine, it can use its model of the world, its imagination model
 to perform an action and see what would happen if it did that action.
 And it can then also append that to the memory and use it to further learn.
 Even though it didn't do the action, it can imagine what happens.
 So how can it imagine?
 The authors in particular propose different methods of imagining.
 This graph you see there are proposed methods.
 The first two methods basically, so here every row is a method of imagining.
 The first method, the one step imagining, simply means you have the current state of
 the world, which is the grey blob here.
 And what you do is you always go from the current state of the world, imagine one step
 ahead.
 So basically you select the state to imagine from, you imagine one step.
 And if you decide to not take an action after that, but imagine again, because maybe you're
 not sure yet what you want to do, so you want to imagine another action, you would again
 go from this initial state, so this in the horizontal direction is time, time, internal
 time basically.
 You would again go from this state, imagine another action based on it, and so on, imagine
 another action.
 Until you're satisfied, you've imagined enough so you can actually take a real world step.
 In contrast, the end step strategy, so these are hard coded strategies as you can see.
 The learned part is which action should I take?
 The hard coded part is where do I base this action off?
 The end step strategy also selects the first state at first, imagines one action on top
 of it, but then always selects that new imagined action.
 So you can see here it selects this one to propose this action, and then it selects that
 imagined action to propose yet another action.
 So you can see it kind of imagines one path into the future instead of many paths, just
 one step ahead.
 And then lastly, this imagination tree strategy is basically the only one that's actually
 kind of a learned strategy where the manager can now propose any previously imagined or
 real world states in order to imagine from.
 So you always have the current world state, which is the first node in the graph.
 You select it, of course, at the beginning you have no choice.
 You imagine an action on top of it, but then you can select any of these two nodes to imagine
 from and here again the first is selected and action is imagined.
 Then you have three nodes.
 You can choose any of those where you want to imagine the next step.
 Here in this example, the manager selects this state right here and decides to imagine
 another action on top of it until it is satisfied and can then actually go over to plan to actually
 perform an action in the real world.
 So if you then decide to do an action in the real world, what you can do is you can take
 all of the things you've imagined and use that.
 So you see in this pathway here, this flows back to the manager.
 At some point it decides, okay, I've imagined enough and we can use all of these imagined
 steps in order to take a real world step.
 And after the real world step, the entire thing starts again.
 So that's how it learns to plan.
 Really interesting of course is this imagination tree strategy where it actually learns to
 plan ahead.
 So the model is described in detail in a formal manner and then it already goes over to experiments
 and there's this spaceship task where you have to get the spaceship to move around stuff
 and around these asteroids and get a reward.
 So you can see different imagination projectives here in the top row.
 You see the red ones is the kind of executed actions, the blue ones are imagined ones and
 you see the tree it's constructed.
 So first it takes an action right here, just without imagining.
 Then it imagines one step but then decides to take another action.
 It imagines two actions but decides on a third one.
 So you see to the left in this picture you see the first action.
 Then it imagines one action and decides to take an action.
 Then it imagines two actions and based on these imaginations, I'm going to guess it's
 fairly satisfied with the one that's very close to the target and it can then take an
 action.
 So it's pretty smart in that it sees that the second imagined action is fairly close
 to where it wants to go and it doesn't need to imagine yet another action.
 That then actually hits the target.
 It can go over to performing the action right away because the imagination gives enough
 information.
 So these kind of things are pretty cool to look at and check out the more experiments
 if you want to know.
 Here is even more experiments in discrete mazes.
 They feature multiple goals.
 They feature the system optimizing not only for its reward but also for kind of internal
 costs, so having a budget for imagining and optimizing not doing too many imagination
 steps.
 On this experiment the kind of thing that bugs me here is the fact that they didn't
 actually use the full imagination tree algorithm but the manager only selected from what you
 can see here.
 So do an actual action, then SJ0 is the first imagined state and SJK is the last imagined
 state.
 So basically the manager can only choose between actually acting, then doing this one step
 strategy and then doing kind of this end step strategy in each step.
 So it kind of limits the way it can plan but I'm going to guess they did this because otherwise
 they couldn't have trained the model and it seems a pretty reasonable simplification to
 make in order to get this to work.
 Also check out the paper if you want to see how all of these different parts are implemented.
 Of course you can guess most of them are neural networks and it's pretty standard so far and
 check out for the additional experiments.
 They're pretty cool.
 See you next time.