MuZero: Mastering Atari, Go, Chess and Shogi by Planning with a Learned Model
ml ai machine learning reinforcement learning deep rl deepmind google alphago alphazero value function policy artificial intelligence rl deep reinforcement learning model-free model-based environment model hidden representation latent state transition chess shogi go atari
MuZero harnesses the power of AlphaZero, but without relying on an accurate environment model. This opens up planning-based reinforcement learning to entirely new domains, where such environment models aren't available. The difference to previous work is that, instead of learning a model predicting future observations, MuZero predicts the future observations' latent representations, and thus learns to only represent things that matter to the task!

Abstract:
Constructing agents with planning capabilities has long been one of the main challenges in the pursuit of artificial intelligence. Tree-based planning methods have enjoyed huge success in challenging domains, such as chess and Go, where a perfect simulator is available. However, in real-world problems the dynamics governing the environment are often complex and unknown. In this work we present the MuZero algorithm which, by combining a tree-based search with a learned model, achieves superhuman performance in a range of challenging and visually complex domains, without any knowledge of their underlying dynamics. MuZero learns a model that, when applied iteratively, predicts the quantities most directly relevant to planning: the reward, the action-selection policy, and the value function. When evaluated on 57 different Atari games - the canonical video game environment for testing AI techniques, in which model-based planning approaches have historically struggled - our new algorithm achieved a new state of the art. When evaluated on Go, chess and shogi, without any knowledge of the game rules, MuZero matched the superhuman performance of the AlphaZero algorithm that was supplied with the game rules.

Authors: Julian Schrittwieser, Ioannis Antonoglou, Thomas Hubert, Karen Simonyan, Laurent Sifre, Simon Schmitt, Arthur Guez, Edward Lockhart, Demis Hassabis, Thore Graepel, Timothy Lillicrap, David Silver

https://arxiv.org/abs/1911.08265

Links:
YouTube: https://www.youtube.com/c/yannickilcher
Twitter: https://twitter.com/ykilcher
BitChute: https://www.bitchute.com/channel/yannic-kilcher
Minds: https://www.minds.com/ykilcher
 Hi there! Today we're looking at mastering Atari Go, Chess and Shogi by planning with a learned model by Julian Schrittweiser and people generally from DeepMind. So this paper is an extension to AlphaZero, the kind of famous algorithm that learned to play Go and Chess simply by playing itself and the kind of cool thing about this model is that it has a learned environment model. So what does this mean? Usually if you have a game such as chess, I believe there is a picture of chess down here, if you have a game such as chess and you want to learn to play it, you need to know the kind of the rules of chess, right? So in chess you have the rules like the pawn can move two or one, right? The bishop can move diagonally and so on. Similarly in Shogi or Go here, you know where you can place the stones and when you win everything is clearly defined. So what you can do is actually you can plan, right? You can now think of okay if I do this opening, right, my opponent could do either this or this or you know this and for each of the three moves I'll have response. So if they do, if they move this pawn, I'll go for like a gambit here and if they move this pawn then I can, you know, move on. Something like this, right? So what in a sense what you have is a tree search. So you start out with the state you're currently in, right? And then your opponent, sorry, this should be your state you're currently in, your opponent has the option of performing any one of these moves. Let's say there are three moves and then from each of these three moves you again have the option of performing any of these moves. And the good thing is in chess you know each exactly what they do. Like if I move my pawn then the new board configuration will be the pawn will no longer be here but here, right? So you know exactly what's going to happen. You can calculate that you have perfect simulator. And other domains you don't have that. For example in Atari all you have in Atari is this screen, right? Maybe you have a little submarine here, right? You have some opponents, right? The opponent, I don't know, what do your opponents look like? Are they fish? I don't even know in this game, right? And you can, I think you can shoot? There's coins to select? I don't know. Okay, in any case and sometimes you need to go up and there is like a health bar. But in essence you only have this screen here, right? You don't have more. And if you press a button you don't exactly know what's going to happen. You don't exactly know what the pixel space will look like as this shot moves forward, right? I guess you could know but you can't use that to plan because the kind of space is too big and your actions may be not clearly predictable. And when you win aren't clearly predictable and there may be randomness. So all of this stuff, usually what people do is here they do use a model-free reinforcement learning. We've had this discussion before. So this would be model-free and while chess here you'd go about model-based. Now what MuZero does is it uses a model-based planning but it learns the model. So it tries to construct a model for this here. It tries to say, okay if I have this screen A here, right? My thing is here and I press the button right then probably my submarine is going to be a bit more to the right. But it doesn't do this exactly. So this has been done before and this is what's kind of known as learning an environment model where you map current environment plus action to the next step in the environment, right? And this usually doesn't work too well because you're really trying to generate this entire pixel space here. What the cool thing about MuZero is it doesn't do that. It doesn't predict the next state. What it does predict is a hidden state and let's draw the hidden state as a little cloud here. It predicts a hidden state of the next step and from the hidden state it will predict things like the reward, the policy, the value and then it can use from that hidden state it'll predict the next hidden state. And from that it will again predict the reward. So the base idea is you only predict what you absolutely need to obtain the values that are important for doing reinforcement learning. You're not trying to predict the full environment. You're simply trying to predict whatever is necessary and this here is a learned quantity. Whatever is necessary to predict what your RL model is going to need. So that's the basic gist of it and we'll look at how they do it or how they describe what they're doing. So basically the picture A here is how MuZero plans. So imagine you have a configuration, a current state. This is an observation. This could be a chessboard. This could also be a position in shogi but it could also be a screen in an Atari game or a camera input of a self-driving car and so on. And the first thing it does it encodes that observation using this H here. I believe they call this a representation function. You encode that to this hidden state. Now the hidden state, this is appropriately sized, the hidden state here is supposed to capture everything you need about the state to predict the kind of RL quantities in the future. And you learn this function H which in this case of course is going to be a neural network in order to produce such a state. Now from this state you do two things. First of all you have this function F here and they call this the I don't remember but you have a function to predict the following two quantities. You predict the value function at that state and the value function simply means if you are in this state here, this is now not a true state but a hidden state, but still if you're in this state, in this hidden state that belongs to this observation, then in the future you're going to make this much reward on average with your current policy. That's the value function. So the value function basically tells you how good it is to be in a given state. And then the policy, this is a bit special, the policy is predicting how you would act in this state. Now this is a bit confusing or it was to me when I first learned it because we're going to see over here how a mu0 decides on how to act. Namely it does this entire tree search thing up to a certain depth, right? And then it creates this histogram and from that it produces the action. But in order to produce, to do this tree search, this is exactly this picture A. This is that tree search that is done. And in order to do that you need these p-values because we'll go there in a second, you need these p-values and they cannot themselves again do a tree search, right? That would be like infinite recursion. So what you need is you need kind of an estimate, right? Like if I were, and especially down, it makes more sense, if I were in that state how would I act, right? If I were to do a tree search like this. So you simply build a neural network that tells you with one evaluation without having to do the entire tree search down from here how you would act. This doesn't need to be a perfect approximation of how you would actually act but it needs to be good enough, right? So this simply tells you how you would act in that state. And that's important because what we do next is we use this policy to generate this action. And this is a simulated action. This isn't a real action because the real action would go here to the next actual observation. This is a simulated action saying if I'm in this hidden state, right, my policy approximately would be this thing. And so I can sample from that and say my action in that state would be this action. And so now I have a hidden state and an action and from that I can produce the next hidden state. Now of course if I were to apply the action up here to the observation, right, action one, I would get the next observation. And that is exactly how alpha zero works, right? You use your simulator, your perfect simulator, to take the current observation, the current state, with a given action that this policy gives you and you produce the next state. But we don't have a perfect simulator, right? And we don't want to learn a model that predicts the entire state. But what we want to do is we want to predict the following. If we were to take a one here, if, right, we would get an observation, can we predict the result when we would apply the function h to that, right, giving me s prime, right? This is observation prime. So this function h here, which is the function that maps from observation space to hidden space, if we were to apply this to the next hidden, to the next observation, we would obtain some hidden state for that observation. Can we predict that thing? So we need a function that maps from the hidden state given an action, right, to the next hidden state. And that's exactly what what happens down here, right? This function g here maps exactly this hidden state plus the action to the next hidden state. And also, also at the same time, it will predict a reward, right? Because in each step you might get a reward. So each transition here gives you a reward. And we're trying to predict that as well. Not that important, especially for games like chess or shogi, where there's only win or lose at the very end. But they incorporate this here to also be able to play these Atari games and like a broader range of reinforcement learning games. But in essence, that's what it is, right? We're trying to predict the next hidden state. And now we can basically recursively apply this. So from here, I have an idea of what my policy might be in that state, right? My proximate policy, my kind of mini policy that only needs one evaluation. I can sample an action from that policy. And if maybe it's action two here, and I can then predict the next hidden state that I would be in. Also the reward, right? And therefore, using this, I can do like a tree search. So I can simulate future trajectories, right? First, all of these policies, I can sample from them. I can sample from them, giving me different actions so that that will lead me down the tree different routes. So I can simulate future trajectories in this tree. And at the end, I have a pretty good idea. I can do this up to a certain depth, right? I don't have to do it until the very end, I can. And then I'll have a pretty good idea of how my immediate the immediate future looks right, which actions lead me to approximately which states and for each state, of course, especially for each bottom state here, I have an estimation of the value of that state. So basically, I can, the easiest thing would simply be to whatever search, how many steps is this? One, no, this is zero. One, two, three steps into the future. And for each of these states, obtain the value v here, v here, v, v, v, v, v. And then I simply pick the action up, the action up here. I'm running out of colors. And simply pick the action up here that will lead me eventually to the highest value state. So that's, we of course, we've not incorporated opponent plays here and so on. But that's the basic idea. You can do this more sophisticated this tree search. And this is a topic that we might cover in a video about AlphaGo or AlphaZero. But in essence, you can do the same thing as AlphaGo or AlphaZero, except if you're not working with the simulator, but you're working with a learned model on the hidden states of the true observations. So B is how you would actually act, right? So for each observation here, we'd say you'd run such a tree search, and you kind of get a histogram over visited actions. And again, we'll skip over that here. But this, this is part of the AlphaZero paper. And you decide on an action. And that will give you a reward and a next observation. And that's how you act. And then you train these things end to end. So you train the networks such that, of course, the reward, you know what the rewards are, right? The reward prediction of G, you know what that should be, right? From given a trajectory and action sequence, you know what the individual reward should be. So that's, you can train G for that. First of all, you can also train to predict the correct value functions like in classic reinforcement learning, you can do like an end step into the future prediction, or you can play until the end sample trajectories and so on. And the policy you predict, you, you predict the policy, your approximate policy to to match your true actions, right? Because your true actions you've generated by doing this entire tree search thing, which is, you know, the your what you're actually going to do. So you're training your approximate policy predictor that you use to run the tree search to match as close as possible to your actual actions, right? This in this fashion. So this policy resulting from hidden state zero should be as close as possible to the action you actually took in the observation that led to hidden state zero. Yeah, so this is how you search, search, act and train using mu zero. And this is pretty, this is it, right? This is the rest is experiments. The rest is simply showing that they can handle these games, they can keep the performance basically of the simulator based alpha zero in, in games. Sorry, where are the results here? Yeah, so in these games in these left hand games, they can keep the performance of alpha zero even exceeded here in go. And remember, they don't have a simulator like alpha zero, they have to learn this model. And in Atari, they actually out compete the current state of the art, which is I think, or to D two, or Impala. But it's it's some model, I guess some model free RL baseline here on the on Atari. So that's pretty cool. And I think that brings RL to kind of a new level with this hidden learning. And yeah, they so they compare it against against multiple ones are two D two different things. All right. Yeah, so that's that's that. For me, it's a cool paper. It's short. Read it if you if you want. I invite you to also look at the additional experiments where they basically ablate what they need is the learned model really as good or better as the real simulator? Does it take as much time actually takes less time, which for for higher elo, which is pretty cool. How many simulations are needed? Things like this. All right, that was it. I like this paper, check it out. Bye bye.
 Hi there! Today we're looking at mastering Atari Go, Chess and Shogi by
 planning with a learned model by Julian Schrittweiser and people generally from
 DeepMind. So this paper is an extension to AlphaZero, the kind of famous
 algorithm that learned to play Go and Chess simply by playing itself and the
 kind of cool thing about this model is that it has a learned environment
 model. So what does this mean? Usually if you have a game such as chess, I believe
 there is a picture of chess down here, if you have a game such as chess and you
 want to learn to play it, you need to know the kind of the rules of chess,
 right? So in chess you have the rules like the pawn can move two or one, right?
 The bishop can move diagonally and so on. Similarly in Shogi or Go here, you know
 where you can place the stones and when you win everything is clearly defined.
 So what you can do is actually you can plan, right? You can now think of
 okay if I do this opening, right, my opponent could do either this or
 this or you know this and for each of the three moves I'll have response. So if
 they do, if they move this pawn, I'll go for like a gambit here and if they move
 this pawn then I can, you know, move on. Something like this, right? So what in a
 sense what you have is a tree search. So you start out with the state you're
 currently in, right? And then your opponent, sorry, this should be your
 state you're currently in, your opponent has the option of performing any one of
 these moves. Let's say there are three moves and then from each of these three
 moves you again have the option of performing any of these moves. And the
 good thing is in chess you know each exactly what they do. Like if I move my
 pawn then the new board configuration will be the pawn will no longer be here
 but here, right? So you know exactly what's going to happen. You can calculate
 that you have perfect simulator. And other domains you don't have that. For example
 in Atari all you have in Atari is this screen, right? Maybe you have a
 little submarine here, right? You have some opponents, right? The
 opponent, I don't know, what do your opponents look like? Are they fish? I don't even know in this
 game, right? And you can, I think you can shoot? There's coins to select? I don't
 know. Okay, in any case and sometimes you need to go up and there is like a health
 bar. But in essence you only have this screen here, right? You don't
 have more. And if you press a button you don't
 exactly know what's going to happen. You don't exactly know what the pixel space
 will look like as this shot moves forward, right? I guess you could know but
 you can't use that to plan because the kind of space is too big and
 your actions may be not clearly predictable. And when you win aren't
 clearly predictable and there may be randomness. So all of this stuff, usually
 what people do is here they do use a model-free reinforcement learning. We've
 had this discussion before. So this would be model-free and while chess
 here you'd go about model-based. Now what MuZero does is it uses a model-based
 planning but it learns the model. So it tries to construct a model for this here.
 It tries to say, okay if I have this screen A here, right? My thing is here and
 I press the button right then probably my submarine is going to be a bit more to
 the right. But it doesn't do this exactly. So this has been done before and this is
 what's kind of known as learning an environment model where you map current
 environment plus action to the next step in the environment, right? And this
 usually doesn't work too well because you're really trying to generate this
 entire pixel space here. What the cool thing about MuZero is it doesn't do that.
 It doesn't predict the next state. What it does predict is a hidden state and
 let's draw the hidden state as a little cloud here. It predicts a hidden
 state of the next step and from the hidden state it will predict things like
 the reward, the policy, the value and then it can use from that hidden state it'll
 predict the next hidden state. And from that it will again predict the
 reward. So the base idea is you only predict what you
 absolutely need to obtain the values that are important for doing reinforcement
 learning. You're not trying to predict the full environment. You're simply trying
 to predict whatever is necessary and this here is a learned quantity. Whatever
 is necessary to predict what your RL model is going to need. So
 that's the basic gist of it and we'll look at how they do it or how
 they describe what they're doing. So basically the picture A here is how MuZero
 plans. So imagine you have a configuration, a current state. This is an
 observation. This could be a chessboard. This could also be a position in
 shogi but it could also be a screen in an Atari game or a camera input of a
 self-driving car and so on. And the first thing it does it encodes that
 observation using this H here. I believe they call this a representation
 function. You encode that to this hidden state. Now the hidden state, this is
 appropriately sized, the hidden state here is supposed to capture everything
 you need about the state to predict the kind of RL quantities in the future.
 And you learn this function H which in this case of course is going to be a
 neural network in order to produce such a state. Now from this state you do two
 things. First of all you have this function F here and they call this the
 I don't remember but you have a function to predict the following two quantities.
 You predict the value function at that state and the value function simply
 means if you are in this state here, this is now not a true state but a
 hidden state, but still if you're in this state, in this hidden state that belongs
 to this observation, then in the future you're going to make this much reward on
 average with your current policy. That's the value function. So the value
 function basically tells you how good it is to be in a given state. And
 then the policy, this is a bit special, the policy is predicting how you would
 act in this state. Now this is a bit confusing or it was to me when I
 first learned it because we're going to see over here how a mu0 decides on how
 to act. Namely it does this entire tree search thing up to a certain depth, right?
 And then it creates this histogram and from that it produces the action. But in
 order to produce, to do this tree search, this is exactly this picture A. This is
 that tree search that is done. And in order to do that you need these p-values
 because we'll go there in a second, you need these p-values and they cannot
 themselves again do a tree search, right? That would be like infinite recursion. So
 what you need is you need kind of an estimate, right? Like if I were, and
 especially down, it makes more sense, if I were in that state how would I
 act, right? If I were to do a tree search like this. So you simply build a neural
 network that tells you with one evaluation without having to do the
 entire tree search down from here how you would act. This doesn't need to be a
 perfect approximation of how you would actually act but it needs to be good
 enough, right? So this simply tells you how you would act in that state. And
 that's important because what we do next is we use this policy to generate this
 action. And this is a simulated action. This isn't a real action because the
 real action would go here to the next actual observation. This is a simulated
 action saying if I'm in this hidden state, right, my policy approximately
 would be this thing. And so I can sample from that and say my action in that
 state would be this action. And so now I have a hidden state and an action and
 from that I can produce the next hidden state. Now of course if I were to apply
 the action up here to the observation, right, action one, I would get the next
 observation. And that is exactly how alpha zero works, right? You use your
 simulator, your perfect simulator, to take the current observation, the current
 state, with a given action that this policy gives you and you produce the
 next state. But we don't have a perfect simulator, right? And we don't want to
 learn a model that predicts the entire state. But what we want to do is we want
 to predict the following. If we were to take a one here, if, right, we would get
 an observation, can we predict the result when we would apply the function h to
 that, right, giving me s prime, right? This is observation prime. So this
 function h here, which is the function that maps from observation space to
 hidden space, if we were to apply this to the next hidden, to the next observation,
 we would obtain some hidden state for that observation. Can we predict that
 thing? So we need a function that maps from the hidden state given an action,
 right, to the next hidden state. And that's exactly what what happens down
 here, right? This function g here maps exactly this hidden state plus the
 action to the next hidden state. And also, also at the same time, it will predict a
 reward, right? Because in each step you might get a reward. So each transition
 here gives you a reward. And we're trying to predict that as well. Not that
 important, especially for games like chess or shogi, where there's only win
 or lose at the very end. But they incorporate this here to also be able to
 play these Atari games and like a broader range of reinforcement learning
 games. But in essence, that's what it is, right? We're trying to predict the next
 hidden state. And now we can basically recursively apply this. So from here, I
 have an idea of what my policy might be in that state, right? My proximate policy,
 my kind of mini policy that only needs one evaluation. I can sample an action
 from that policy. And if maybe it's action two here, and I can then predict
 the next hidden state that I would be in. Also the reward, right? And therefore,
 using this, I can do like a tree search. So I can simulate future trajectories,
 right? First, all of these policies, I can sample from them. I can sample
 from them, giving me different actions so that that will lead me down
 the tree different routes. So I can simulate future trajectories in this
 tree. And at the end, I have a pretty good idea. I can do this up to a certain
 depth, right? I don't have to do it until the very end, I can. And then I'll have a
 pretty good idea of how my immediate the immediate future looks right, which
 actions lead me to approximately which states and for each state, of course,
 especially for each bottom state here, I have an estimation of the value of that
 state. So basically, I can, the easiest thing would simply be to whatever
 search, how many steps is this? One, no, this is zero. One, two, three steps into
 the future. And for each of these states, obtain the value v here, v here, v, v, v,
 v, v. And then I simply pick the action up, the action up here. I'm running out
 of colors. And simply pick the action up here that will lead me eventually to the
 highest value state. So that's, we of course, we've not incorporated opponent
 plays here and so on. But that's the basic idea. You can do this more
 sophisticated this tree search. And this is a topic that we might cover in a
 video about AlphaGo or AlphaZero. But in essence, you can do the same thing as
 AlphaGo or AlphaZero, except if you're not working with the simulator, but
 you're working with a learned model on the hidden states of the true
 observations. So B is how you would actually act, right? So for each
 observation here, we'd say you'd run such a tree search, and you kind of get a
 histogram over visited actions. And again, we'll skip over that here. But this,
 this is part of the AlphaZero paper. And you decide on an action. And that will
 give you a reward and a next observation. And that's how you act. And then you
 train these things end to end. So you train the networks such that, of
 course, the reward, you know what the rewards are, right? The reward prediction
 of G, you know what that should be, right? From given a trajectory and action
 sequence, you know what the individual reward should be. So that's, you can train
 G for that. First of all, you can also train to predict the correct value
 functions like in classic reinforcement learning, you can do like an end step
 into the future prediction, or you can play until the end sample trajectories
 and so on. And the policy you predict, you, you predict the policy, your
 approximate policy to to match your true actions, right? Because your true
 actions you've generated by doing this entire tree search thing, which is, you
 know, the your what you're actually going to do. So you're training your
 approximate policy predictor that you use to run the tree search to match as
 close as possible to your actual actions, right? This in this fashion. So this
 policy resulting from hidden state zero should be as close as possible to the
 action you actually took in the observation that led to hidden state zero.
 Yeah, so this is how you search, search, act and train using mu zero. And this is
 pretty, this is it, right? This is the rest is experiments. The rest is simply
 showing that they can handle these games, they can keep the performance basically
 of the simulator based alpha zero in, in games. Sorry, where are the results here?
 Yeah, so in these games in these left hand games, they can keep the
 performance of alpha zero even exceeded here in go. And remember, they don't have
 a simulator like alpha zero, they have to learn this model. And in Atari, they
 actually out compete the current state of the art, which is I think, or to D two, or
 Impala. But it's it's some model, I guess some model free RL baseline here on the
 on Atari. So that's pretty cool. And I think that brings RL to kind of a new
 level with this hidden learning. And yeah, they so they compare it against against
 multiple ones are two D two different things. All right. Yeah, so that's that's
 that. For me, it's a cool paper. It's short. Read it if you if you want. I
 invite you to also look at the additional experiments where they basically ablate
 what they need is the learned model really as good or better as the real
 simulator? Does it take as much time actually takes less time, which for for
 higher elo, which is pretty cool. How many simulations are needed? Things like
 this. All right, that was it. I like this paper, check it out. Bye bye.