IMPALA: Scalable Distributed Deep-RL with Importance Weighted Actor-Learner Architectures
machine learning ml ai artificial intellgence deepmind reinforcement learning deep rl a2c a3c actor critic distributed scale bias off-policy policy gradient deepmind lab vtrace
Policy Gradient RL on a massively distributed scale with theoretical guarantees!

Abstract:
In this work we aim to solve a large collection of tasks using a single reinforcement learning agent with a single set of parameters. A key challenge is to handle the increased amount of data and extended training time. We have developed a new distributed agent IMPALA (Importance Weighted Actor-Learner Architecture) that not only uses resources more efficiently in single-machine training but also scales to thousands of machines without sacrificing data efficiency or resource utilisation. We achieve stable learning at high throughput by combining decoupled acting and learning with a novel off-policy correction method called V-trace. We demonstrate the effectiveness of IMPALA for multi-task reinforcement learning on DMLab-30 (a set of 30 tasks from the DeepMind Lab environment (Beattie et al., 2016)) and Atari-57 (all available Atari games in Arcade Learning Environment (Bellemare et al., 2013a)). Our results show that IMPALA is able to achieve better performance than previous agents with less data, and crucially exhibits positive transfer between tasks as a result of its multi-task approach.

Authors: Lasse Espeholt, Hubert Soyer, Remi Munos, Karen Simonyan, Volodymir Mnih, Tom Ward, Yotam Doron, Vlad Firoiu, Tim Harley, Iain Dunning, Shane Legg, Koray Kavukcuoglu

https://arxiv.org/abs/1802.01561
https://github.com/deepmind/scalable_agent
 Hi there! Today we're looking at Impala, scalable distributed deep RL with importance-weighted actor learner architectures by Lasse Espejolt, Hubert Sawyer, Remy Munoz and Al. So this paper deals with a new architecture for deep reinforcement learning, specifically distributed deep reinforcement learning. So that means settings where you go beyond one single machine or beyond one single accelerator like a GPU. So I want to introduce this by showing you this task here. This is called the DeepMind lab and the DeepMind lab is a kind of a 3D environment as you can see here. These are screenshots where they're very different goals but some of this as you can see are kind of labyrinth style things where you have to collect apples, some are platformers where you I guess have to jump around and so on or find objects. So the DeepMind introduced this as kind of a as an reinforcement learning environment and what you can do the agent as you can see here has a camera it perceives pixels and it can get rewards for performing actions. The actions it can perform is it can you know walk back and forth, it can jump, it can crouch, it can rotate. So this is kind of a limited set of actions that it can do but it can move around in this 3D world and it needs to achieve some goals. So that usually this is kind of a good setting for reinforcement learning and this paper doesn't do a whole lot of new things in terms of reinforcement learning but it does a lot of things to kind of make it work in a distributed setting. So usually what you would like to do is something like A2C. A2C is advantage actor critic learning and it's a very successful algorithm in reinforcement learning. We won't go into this much here but basic elements of it is you have are two things you have a policy and usually this is called PI, sorry about that, usually this is called PI policy that you input your current state so your current observation at time t and you want to score an action right action A. Now you might have maybe as we saw before you can walk left walk right and so on so you might have ten actions or so. So in here you would put action one or action two or action three and for this you would get probability distributions over each action so maybe in this particular state so each time with the same state. So you would get a distribution something like this right so here you should probably go with action three. That's your policy function. Policy function PI tells you in this particular state which action should you take how often kind of gives you distribution. The second thing you want is a what's called a value function so the value function V, capital V usually, you input your state and it will output it will output what the value is of that state and that's usually termed kind of as a lowercase V. The value of the state is given if you're in a maze right I'm gonna draw maze from the top here right you can't reach there like here so here is the goal and let's say you are oops you're right here the green right and you have the choice of going forward to the right or to the left. Now this would be your policy here. You would ask your policy and A1 would maybe be go forward A2 go to the left A3 to the right so your policy would decide what to do. Your value function however would decide in each of the states so where you are plus where you could go here here here so basically for each state in the system it would give you a value in particular in this case it would probably give you a very very high value here like yeah this is a good point because you're very close to the goal right here this is probably not so good a point and this is a very bad point because you're you're going to corner you're actually moving farther away from the goal so if your value function is trained well then you can you can use that also to assess your situation so the value function for each state s it will give you a numerical value of how good that state is in terms of reaching your goal and the A2C algorithm now deals with the interplay of these the A2C uses actually both of these in an interplay so it will use one to teach the other one right and this interplay between those gives makes for a very successful reinforcement learning algorithm now the way A2C does it is as you can see here what it does is it has to there are two variants here think synced step and synced trajectories but in essence it has to run these episodes and these here are steps in the episodes and let's say an episode as four steps before it can do the learning part and the learning part is here the orange thing once it has done a step of learning it has to run episodes again and then it has can do learning again and that's because of a limitation of this which is called on policy learning so on in on policy learning you always want to have your update step which is the orange part to be fed with data so the this all of these app all of these steps here go into this update steps and it's necessary that the steps that you make the updates from are computed with kind of the most current version of the of the agent right so that the agent will go into the world make some steps using its neural network maybe I should explain so that the agent right is this box and the agent has this policy right and with this policy as we saw it will go and it will interact with the world right outside of itself and it will kind of the world will give back observations and it will then interact again so you can move a step forward right first first thing is move the step step forward and then the world gives it back a high you are now no longer here you've moved here right and then it's on I want to move to the left and the world says okay so you're no longer here you've moved one to the left and this on the right here are the observations and is on the left here are the actions and for the a to see is kind of necessary that we always have a current version of the policy generating these steps in order to be able to learn from them and then the next steps also need to be kind of current to be learned now there have been attempts to decentralize this and is exactly what impala does impala splits this into multiple workers you can think of this as different machines so there is a split here and these are called actors and this is called a learner now the actors they will go ahead and they will run episodes on their own right occasionally or they will run episodes and they will communicate those episodes to the learner and the learner will continuously here learn so these orange steps can be made in much more quick success succession and don't have to be like synchronized as in the a to see here is another way of seeing this over here and we'll just concentrate on this on this left thing here so there is a learner and there are actors and every now and then the actor sinks its model from the learner these are different machines so this can happen over the network every now and then the actor gets like an update of the newest policy network and then the actor will just go ahead and run episodes using that policy right episode episode episode episode step steps without interfering with anything else and then once it has run an episode or multiple ones it will communicate this back to the learner and if all the actors do this all right the learner gets a whole bunch of these episodes and then can learn from all of them simultaneously and it can do so in kind of with in in kind of very fast succession as you see here so the work is split of course you run into a problem namely as we saw in the a to see algorithm this type of reinforcement learning requires basically that you always run the episode with the current model and that's not the case here right the actor may sink the parameters they sink the parameters once in a while but then it will run these episodes right when it runs these episodes here it has no idea or it the learner in the meantime has continually been updating the model while the actor kind of has an old model so these episodes here are run with an old model so the learner if it tries to learn from this must kind of correct for this fact and the big kind of theoretical contribution of this paper is how to correct for the fact that the data you learn from comes from an outdated policy model and this is what's called V trace correction so without going too much into the into the details here V trace correction happens as as fall it happens as follows so what you define are what's called V trace targets and these V trace targets are basically the targets that you train your value function towards right so the the the value function as we discussed before that is a that is the thing that tells you how good each state is and the targets you train this towards and you're also by the way using this V V trace corrections in policy updates but these are defined as follows so the V trace target for step s is the value function at step s plus this correction thing and the the correction thing basically well I've I want to break this down some more so the V at current s is your value function plus and this is a sum over all future steps over and this is a discount factor and this is kind of a delta from one step to the next so you're in an episode and you've made some steps right and let's say we are here right this is s and so your your little V s will be whatever your value function says of s plus kind of a correction for each step that you make go into the future like this and the main part of these is is this here which is basically the reward at the step plus the difference of the value functions of the steps after it and what V trace introduces now is this bit here and these CI again are computed as such so all of this kind of is very nested so there is a there's a big multiplication here it's a very nested thing but in the very very very core of it you can see the following these V trace corrections are a ratio between pi and mu and pi is the policy of the learner that is the current policy and mu is the policy that has been used to generate the to generate the episode and this is truncated by a minimum and usually the C bar is one so let's consider what happens here what happens is let's say that mu is higher than pi for a given pair of AI index a what does it mean it means that in the past you run an episode you come you are in this maze right such to them and you're here right now the and the goal let's say the goal is down here and the action is going over here that does the action that you're considering here now your mu which is your old policy that the actor has synced at some point mu might say this is very good right because it moves you towards the goal more but then your your pie the learner has been learning since the eight since the agent the actor has synchronized the weights the learner has been learning and the learner might know wait wait since you have decided this I have actually learned that this might not be such a good move because you know there's a wall here and I'd rather go down here and then over here so what it will do it will since pi is low and mu is higher it will down weigh this action and this is how you correct for the fact that there are old weights by basically down weighing wherever the old policy thought of an action as being worth more than the new policy does and this is how you make up for the fact that the new policy you assume it knows better because it has learned more and thereby you you give lower weight to the data points where the the policies have diverged a lot so that's at the core of it and you can think of in terms of here you can think of it as maybe here at this step you're at a point where the old policy that the actor has has updated itself to says we should do action one right but the new policy that the learner has in the meantime has learned more says now we should do action two and if this is the case then this whole rest of the episode is down weight because it is no longer current knowledge right and this is not just kind of a heuristic but they actually do prove that this this this comes with some guarantees especially reduces to kind of the classic reinforcement algorithms if you assume that mu is always pi so that current policy is the old policy and therefore you're in the old setting alright so this was a bit of a lengthy explanation of the math behind it and at the end what you do is following you train your value function using this update and you can see here it's simply the gradient of the value function scaled by the thing that contains this V trace target right you then you update your policy in this direction and this is the classic reinforcement learning reinforce style policy update where here you have the gradient of the of the policy and here you have the weighing by the reward and specifically here it is the reward plus this V trace target and this thing here is a bias correction or a bias reducing sorry variance reducing bias that was terrible the final form is what's called an entropy penalty where you want to push the entropy of your policy up such that the agent kind of is biased towards exploring more than exploiting if you know of the classic exploration exploitation dilemma so that's that's what you do compute these V trace targets update your value and policy according to these equations and there you go so what do what does Impala do specifically in this deep mind lab they have two architectures first of all they have this they have this small architecture second they have this large architecture and they just kind of try it out on these and they measure how many frames per second they can get in and you see here compared to on single machine compared to a 3c they bring in a lot more frames per second this is just on a single machine but then on distributed setting the scale up also is very significant that they reach that's because they don't have to wait for other things they can just go ahead everything runs at full speed basically and everything runs in parallel and the fact that that some of the information is old is corrected by V trace and the last thing I want to show is the wall clock time I think this is the important plot in this deep mind lab on over all the tasks the wall clock time compared to the score you can see a 3c while it does you know increase over time the Impala variants up here increase in much much faster wall clock time so that's the that's the paper they have a lot of proofs in the appendix which I'm not gonna go over if you want to give it a try then it is it is not called Impala on github it is called I think scalable agent so on github it is called scalable agent I think but you'll find it if you if you search for Impala github or something like this yeah other than that thanks for listening and see you next time
 Hi there! Today we're looking at Impala, scalable distributed deep RL with
 importance-weighted actor learner architectures by Lasse Espejolt, Hubert
 Sawyer, Remy Munoz and Al. So this paper deals with a new architecture for deep
 reinforcement learning, specifically distributed deep reinforcement learning.
 So that means settings where you go beyond one single machine or beyond one
 single accelerator like a GPU. So I want to introduce this by showing you this
 task here. This is called the DeepMind lab and the DeepMind lab is a kind of a
 3D environment as you can see here. These are screenshots where they're very
 different goals but some of this as you can see are kind of labyrinth style
 things where you have to collect apples, some are platformers where you I guess
 have to jump around and so on or find objects. So the DeepMind introduced this
 as kind of a as an reinforcement learning environment and what you can do
 the agent as you can see here has a camera it perceives pixels and it can
 get rewards for performing actions. The actions it can perform is it can you
 know walk back and forth, it can jump, it can crouch, it can rotate. So this is
 kind of a limited set of actions that it can do but it can move around in this
 3D world and it needs to achieve some goals. So that usually this is
 kind of a good setting for reinforcement learning and this paper doesn't
 do a whole lot of new things in terms of reinforcement learning but it does a lot
 of things to kind of make it work in a distributed setting. So usually what you
 would like to do is something like A2C. A2C is advantage actor critic learning
 and it's a very successful algorithm in reinforcement learning. We won't go into
 this much here but basic elements of it is you have are two things you have
 a policy and usually this is called PI, sorry about that, usually this is called
 PI policy that you input your current state so your current observation at
 time t and you want to score an action right action A. Now you might have maybe
 as we saw before you can walk left walk right and so on so you might have ten
 actions or so. So in here you would put action one or action two or action three
 and for this you would get probability distributions over each action so maybe
 in this particular state so each time with the same state. So you would get a
 distribution something like this right so here you should probably go with
 action three. That's your policy function. Policy function PI tells you in this
 particular state which action should you take how often kind of gives you
 distribution. The second thing you want is a what's called a value function so
 the value function V, capital V usually, you input your state and it will output
 it will output what the value is of that state and that's usually termed kind of
 as a lowercase V. The value of the state is given if you're in a maze right I'm
 gonna draw maze from the top here right you can't reach there like here so here
 is the goal and let's say you are oops you're right here the green right and
 you have the choice of going forward to the right or to the left. Now this
 would be your policy here. You would ask your policy and A1
 would maybe be go forward A2 go to the left A3 to the right so your policy
 would decide what to do. Your value function however would decide in each of
 the states so where you are plus where you could go here here here so basically
 for each state in the system it would give you a value in particular in this
 case it would probably give you a very very high value here like yeah this is
 a good point because you're very close to the goal right here this is probably
 not so good a point and this is a very bad point because you're you're going to
 corner you're actually moving farther away from the goal so if your value
 function is trained well then you can you can use that also to assess your
 situation so the value function for each state s it will give you a numerical
 value of how good that state is in terms of reaching your goal and the A2C
 algorithm now deals with the interplay of these the A2C uses actually both of
 these in an interplay so it will use one to teach the other one right and this
 interplay between those gives makes for a very successful reinforcement learning
 algorithm now the way A2C does it is as you can see here what it does is it has
 to there are two variants here think synced step and synced trajectories but
 in essence it has to run these episodes and these here are steps in the episodes
 and let's say an episode as four steps before it can do the learning part and
 the learning part is here the orange thing once it has done a step of
 learning it has to run episodes again and then it has can do learning again
 and that's because of a limitation of this which is called on policy learning
 so on in on policy learning you always want to have your update step which is
 the orange part to be fed with data so the this all of these app all of these
 steps here go into this update steps and it's necessary that the steps that you
 make the updates from are computed with kind of the most current version of the
 of the agent right so that the agent will go into the world make some steps
 using its neural network maybe I should explain so that the agent right is this
 box and the agent has this policy right and with this policy as we saw it will
 go and it will interact with the world right outside of itself and it will kind
 of the world will give back observations and it will then interact again so you
 can move a step forward right first first thing is move the step step forward
 and then the world gives it back a high you are now no longer here you've moved
 here right and then it's on I want to move to the left and the world says okay
 so you're no longer here you've moved one to the left and this on the right
 here are the observations and is on the left here are the actions and for the a
 to see is kind of necessary that we always have a current version of the
 policy generating these steps in order to be able to learn from them and then
 the next steps also need to be kind of current to be learned now there have
 been attempts to decentralize this and is exactly what impala does impala
 splits this into multiple workers you can think of this as different machines
 so there is a split here and these are called actors and this is called a
 learner now the actors they will go ahead and they will run episodes on
 their own right occasionally or they will run episodes and they will
 communicate those episodes to the learner and the learner will continuously
 here learn so these orange steps can be made in much more quick success
 succession and don't have to be like synchronized as in the a to see here is
 another way of seeing this over here and we'll just concentrate on this on this
 left thing here so there is a learner and there are actors and every now and
 then the actor sinks its model from the learner these are different machines so
 this can happen over the network every now and then the actor gets like an
 update of the newest policy network and then the actor will just go ahead and
 run episodes using that policy right episode episode episode episode step
 steps without interfering with anything else and then once it has run an episode
 or multiple ones it will communicate this back to the learner and if all the
 actors do this all right the learner gets a whole bunch of these episodes and
 then can learn from all of them simultaneously and it can do so in kind
 of with in in kind of very fast succession as you see here so the work
 is split of course you run into a problem namely as we saw in the a to see
 algorithm this type of reinforcement learning requires basically that you
 always run the episode with the current model and that's not the case here right
 the actor may sink the parameters they sink the parameters once in a while but
 then it will run these episodes right when it runs these episodes here it has
 no idea or it the learner in the meantime has continually been updating
 the model while the actor kind of has an old model so these episodes here are run
 with an old model so the learner if it tries to learn from this must kind of
 correct for this fact and the big kind of theoretical contribution of this
 paper is how to correct for the fact that the data you learn from comes from
 an outdated policy model and this is what's called V trace correction so
 without going too much into the into the details here V trace correction happens
 as as fall it happens as follows so what you define are what's called V trace
 targets and these V trace targets are basically the targets that you train
 your value function towards right so the the the value function as we discussed
 before that is a that is the thing that tells you how good each state is and the
 targets you train this towards and you're also by the way using this V V
 trace corrections in policy updates but these are defined as follows so the V
 trace target for step s is the value function at step s plus this correction
 thing and the the correction thing basically well I've I want to break this
 down some more so the V at current s is your value function plus and this is a
 sum over all future steps over and this is a discount factor and this is kind of
 a delta from one step to the next so you're in an episode and you've made
 some steps right and let's say we are here right this is s and so your your
 little V s will be whatever your value function says of s plus kind of a
 correction for each step that you make go into the future like this and the
 main part of these is is this here which is basically the reward at the step plus
 the difference of the value functions of the steps after it and what V trace
 introduces now is this bit here and these CI again are computed as such so
 all of this kind of is very nested so there is a there's a big multiplication
 here it's a very nested thing but in the very very very core of it you can see
 the following these V trace corrections are a ratio between pi and mu and pi is
 the policy of the learner that is the current policy and mu is the policy that
 has been used to generate the to generate the episode and this is truncated
 by a minimum and usually the C bar is one so let's consider what happens here
 what happens is let's say that mu is higher than pi for a given pair of AI
 index a what does it mean it means that in the past you run an episode you come
 you are in this maze right such to them and you're here right now the and the
 goal let's say the goal is down here and the action is going over here that
 does the action that you're considering here now your mu which is your old
 policy that the actor has synced at some point mu might say this is very good
 right because it moves you towards the goal more but then your your pie the
 learner has been learning since the eight since the agent the actor has
 synchronized the weights the learner has been learning and the learner might know
 wait wait since you have decided this I have actually learned that this might
 not be such a good move because you know there's a wall here and I'd rather go
 down here and then over here so what it will do it will since pi is low and mu
 is higher it will down weigh this action and this is how you correct for the fact
 that there are old weights by basically down weighing wherever the old policy
 thought of an action as being worth more than the new policy does and this is how
 you make up for the fact that the new policy you assume it knows better
 because it has learned more and thereby you you give lower weight to the data
 points where the the policies have diverged a lot so that's at the core of
 it and you can think of in terms of here you can think of it as maybe here at
 this step you're at a point where the old policy that the actor has has
 updated itself to says we should do action one right but the new policy that
 the learner has in the meantime has learned more says now we should do action
 two and if this is the case then this whole rest of the episode is down weight
 because it is no longer current knowledge right and this is not just
 kind of a heuristic but they actually do prove that this this this comes with
 some guarantees especially reduces to kind of the classic reinforcement
 algorithms if you assume that mu is always pi so that current policy is the
 old policy and therefore you're in the old setting alright so this was a bit of
 a lengthy explanation of the math behind it and at the end what you do is
 following you train your value function using this update and you can see here
 it's simply the gradient of the value function scaled by the thing that
 contains this V trace target right you then you update your policy in this
 direction and this is the classic reinforcement learning reinforce style
 policy update where here you have the gradient of the of the policy and here
 you have the weighing by the reward and specifically here it is the reward plus
 this V trace target and this thing here is a bias correction or a bias reducing
 sorry variance reducing bias that was terrible the final form is what's called
 an entropy penalty where you want to push the entropy of your policy up such
 that the agent kind of is biased towards exploring more than exploiting if you
 know of the classic exploration exploitation dilemma so that's that's
 what you do compute these V trace targets update your value and policy
 according to these equations and there you go so what do what does Impala do
 specifically in this deep mind lab they have two architectures first of all they
 have this they have this small architecture second they have this large
 architecture and they just kind of try it out on these and they measure how
 many frames per second they can get in and you see here compared to on single
 machine compared to a 3c they bring in a lot more frames per second this is just
 on a single machine but then on distributed setting the scale up also is
 very significant that they reach that's because they don't have to wait for
 other things they can just go ahead everything runs at full speed basically
 and everything runs in parallel and the fact that that some of the information
 is old is corrected by V trace and the last thing I want to show is the wall
 clock time I think this is the important plot in this deep mind lab on over all
 the tasks the wall clock time compared to the score you can see a 3c while it
 does you know increase over time the Impala variants up here increase in much
 much faster wall clock time so that's the that's the paper they have a lot of
 proofs in the appendix which I'm not gonna go over if you want to give it a
 try then it is it is not called Impala on github it is called I think scalable
 agent so on github it is called scalable agent I think but you'll find it if you
 if you search for Impala github or something like this yeah other than that
 thanks for listening and see you next time