MuZero - Mastering Atari, Go, Chess and Shogi by Planning with a Learned Model | RL Paper explained
❤️ Become The AI Epiphany Patreon ❤️ ► https://www.patreon.com/theaiepiphany
▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬

MuZero - the latest agent in the lineage of AlphaGo agents. Zero human knowledge, zero rules, and cracks not only Go, Chess and Shogi but additionally it achieves SOTA on the Atari benchmark.

You'll learn about:
✔️ How can MuZero learn to play without the rules
✔️ How does it learn the dynamics/model
▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬ 
✅ Paper: https://arxiv.org/abs/1911.08265
✅ Blog: https://deepmind.com/blog/article/muzero-mastering-go-chess-shogi-and-atari-without-rules
▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬ 

⌚️ Timetable: 
00:00 Overview of the AlphaGo lineage
03:00 MuZero actors explained
11:10 How can MuZero work without any rules?
14:50 MuZero learner explained
21:15 Results
25:15 Update to the search algorithm

▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬ 
💰 BECOME A PATREON OF THE AI EPIPHANY ❤️ 

If these videos, GitHub projects, and blogs help you,
consider helping me out by supporting me on Patreon! 

The AI Epiphany ► https://www.patreon.com/theaiepiphany
One-time donation: 
https://www.paypal.com/paypalme/theaiepiphany 

Much love! ❤️

Huge thank you to these AI Epiphany patreons:
Petar Veličković
Zvonimir Sabljic
▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬ 

💡 The AI Epiphany is a channel dedicated to simplifying the field of AI using creative visualizations and in general, a stronger focus on geometrical and visual intuition, rather than the algebraic and numerical "intuition". 

▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬ 
👋 CONNECT WITH ME ON SOCIAL 
LinkedIn ► https://www.linkedin.com/in/aleksagordic/ 
Twitter ► https://twitter.com/gordic_aleksa 

Instagram ► https://www.instagram.com/aiepiphany/ 
Facebook ► https://www.facebook.com/aiepiphany/ 

👨‍👩‍👧‍👦 JOIN OUR DISCORD COMMUNITY:
Discord ► https://discord.gg/peBrCpheKE

📢 SUBSCRIBE TO MY MONTHLY AI NEWSLETTER:
Substack ► https://aiepiphany.substack.com/

💻 FOLLOW ME ON GITHUB FOR COOL PROJECTS: 
GitHub ► https://github.com/gordicaleksa 

📚 FOLLOW ME ON MEDIUM:
Medium ► https://gordicaleksa.medium.com/ 
▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬

#muzero #atari #reinforcementlearning
 Finally, I'm going to cover Mu0, the latest agent in the lineage of AlphaGo agents, in this paper called Mastering Atari, Go, Chess, and Shogi, by planning with a learn model, and again, that's the DeepMind crew that's been working on this since 2014 or something, and basically, it'd be really helpful if you already watched my previous videos on AlphaGo, AlphaGo 0, and Alpha0, because many of the details still apply here, so do watch those, I'll link it somewhere here. Okay, before I start digging into the paper, let me just quickly walk you through what happened with this lineage of agents, and the first thing that happened was AlphaGo, back in 2015, they developed this agent which could solve the game of Go, but the trick was it used a lot of human data, so the professional games played by Go players, and it had a lot of Go-specific heuristics integrated into the agent itself, and it also knew the rules of the game, obviously, and then they had AlphaGo 0, which basically also played Go, and was even better than AlphaGo, but the trick was they didn't use any human data, they were just using pure self-play reinforcement learning, and the algorithm, the agent, learned how to play by itself, and became the best player ever so far. The next step was doing the Alpha0, which basically was a minor, let's say minor, probably a lot of engineering, but a minor conceptual change, so they had to prune a couple more details from AlphaGo 0 in order to make it general enough so that it can play not only Go, but also chess and shogi, which is a so-called Japanese chess, and again, we didn't have any human data, but we did have the rules, and the latest agent in this lineage is Mu0, which is this paper, and basically, they just ditched the rules, and I'll explain in a minute what that means, and it can also play Atari games now, so the Atari 57 games in the Atari benchmark, so when they say they don't have the rules, what does that mean? Well, basically, that means that during the, so if you watched my previous videos, you know what Monte Carlo Tree Search is, and basically what it means is that during the Monte Carlo Tree Search, you don't have the available simulator, so you don't know how to, given some action, so starting from a root state, S0, given some action, you don't know what the next state here will be, you don't know how the exact layout of the boards will look like in the case of board games, or in the case of Atari, you don't know what the next screen will look like, and basically, because you don't have the simulator, you'll have to learn the dynamics model, and we'll see, and that's the whole main paper, the main idea of this paper, is to learn the dynamics model, and then subsequently use it in order to plan, in order to play all of these games, so let's see how they managed to pull it off, so they say here, we present the Mu0 algorithm, which by combining a Tree-based search, so again, Monte Carlo Tree Search, with a learned model, that's the novelty, achieves superhuman performance in a range of challenging and visually complex domains, without any knowledge of the underlying dynamics, so that's what I mentioned already, and you'll understand that as this video progresses, so when evaluating on Go, Chess, and Shogi, without any knowledge of the game rules, Mu0 matched the superhuman performance of the AlphaZero agent, so that's this one, algorithm that was supplied with the game rules, and it also achieves state of the art on this Atari 57 benchmark, and that's pretty awesome as well. Okay, so let's dig into the algorithm straight away, and I'll skip this part for now, and let's just explain how everything looks like in Mu0. Okay, so first, let's understand the algorithm itself. First things first, the Mu0 agent consists out of three parts, so the first part is the representation function, H, the second function is the prediction function, F, which will give us the policy and the value function, and finally, we'll have something called G function, or the dynamics function, and given the state and given the action, it will just output the next state, and it will output the reward, okay, and this is what we're trying to learn here, so we don't have the simulator, the perfect simulator, we have this dynamics model, which we're trying to learn, and so these three components together comprise the Mu0 model, okay, so this is the input state, and the thing is, because we have Atari, we have Go, Chess, and Shogi, and I'll just give you an example of how this thing looks like for Go, and how it looks for Atari as two representative cases, so for Go, this thing, whoops, will look like this, so we'll have eight planes, and each plane will have 19 by 19 resolution, because that's how the Go board looks like, so this is going to be, so eight, and the reason we have eight is because in order to play Go, you need to have some past observations, otherwise you can't play the game, okay, so for Atari, this is going to look like, so similarly, we'll have 32 times three, because we have RGB frames, we'll have to encode 32 frames, and so this is going to look like this, and that's like, I think, 96 by 96 resolution, and we'll have additionally 32 planes for the 32 previous actions, and that's also needed, because in order to play Atari, you just need those actions encoded, and we're just going to broadcast, for example, if the action was zero, you're just going to put a bias plane with all zeros stacked here, if it was one, you're just going to input one over 18, because Atari has 18 actions, so that's how they encode the actions, as just constant bias planes here, so once we have those volumes, those represent the input states, and now we have the H function, which is a simple resonant, so you'll just pass that volume into a resonant, and out comes the hidden representation, the hidden state, and it's going to look similarly, it's going to have 256 planes, and depending on whether we have Atari, or whether we have Go, or whatever, for Atari, it's going to be 6 by 6 resolution, and for Go, it's going to remain the same, so 19 by 19, because again, the board has 19 by 19 resolution, okay, and now we just apply Monte Carlo Tree search in the following manner, we have the F function, which is the prediction function, which is also a convolutional neural network, and we just pass this hidden state into it, and out comes the policy, so the policy will be like 361 dimensional vector, in the case of Go, and the value will just be the value function, which gives you the expected reward you'll get going from this state to the end of the game, just basic reinforcement learning stuff, so that's that part, and using those priors, using those probabilities coming from the policy, that's going to be your prior in your Monte Carlo Tree search, if you remember from the previous videos, and you're just going to take the maximum, like the PUCT value, and for example, you took this branch, and once you have that action, you're going to pass it into this G function, so let's see how that functions, so again, I explained we have this hidden state, and it looks like this, so 256 there, and this is dependent on the game itself, so this is 256, and what we're going to do is, we're going to encode this action, again, spatially, so as I previously said, for example, for Atari, you're just going to add a bias plane here, and this is what's going into the G function, and out goes the next hidden state, which will again have 256 planes, and out goes the reward here, so just by doing this, and doing the simulations through the Monte Carlo, using this G model, the dynamics model, and the prediction, and the representation models, you'll build up the Monte Carlo tree search, and then, as you know, you just take the highest visitation count in the root, and that's your next action, and so, as you can see here, you just pick the maximum visitation count action, and you pass it to the environment, the environment gives you some reward, and it gives you the next observation, so basically, you'll just, in the case of, say, Go, because those are 8 boards, you'll just pop the oldest one, and you'll just append the newest board state that came from the environment, and that's your new input state, and then you just recursively repeat this until the end of the game, and then the environment tells you, okay, this environment will just stop you, and what you'll do is you'll be saving those trajectories into this centralized replay buffer, where all of these actors are going to store their experience, so basically, Mu0 is a distributed agent, that means you'll have multiple actors, so all of these are maybe separate threads, and they'll be executing this thing here, they'll be collecting experience, they'll be saving stuff like this thing, like the policy coming, the refund policy from the Monte Carlo tree search, and rewards, and states, they'll be saving those tuples here, and later, you can use those to train this thing. Now, there is one thing that may confuse you, and that's how does this thing play without any rules, and the answer is, like the partial answer, and we'll dig into it a bit later, is basically, only in this root state, you can query the environment and ask what the valid actions are, so as you can imagine, for example, in the case of Go, you'll have 361 branches here, and not every single one is going to be legal, so once you communicate with the environment, it tells you maybe these actions here are invalid, that means you'll just pull the priors, the probabilities to zero, and you'll take that probability mass, and you'll just proportionally distribute it across all of the other branches, and so doing that, you'll basically be building the Monte Carlo tree search, where the root node will kind of constrain you, constrain your space, but all of the other nodes here, like all of these, they'll have all of the 361 actions available in the case of Go, and that means you may play some, initially, you'll be playing maybe some impossible games, illegal games, but that doesn't matter, eventually, during training, the model will learn how to basically do the correct steps, it will learn the rules of the game, basically. Okay, before explaining the actual training procedure, let me just further clarify how it works without any rules, and that's the part that bugged me a lot, initially, so let me try and explain it. So, first of all, specifically, AlphaGo Zero and AlphaZero use knowledge of the rules of the game in three places, so state transitions in the search tree, actions available at each node of the search tree, and episode termination within the search tree, so there are three parts to understanding how this thing works without any rules. First things first, this one. So, AlphaZero had access to a perfect simulator of the true dynamics process, so this is how the thing looks like. You basically have, so this is the root of the Monte Carlo tree search, so this is your initial state, you start building the Monte Carlo tree search like this, and what's the difference? Well, I already explained how the input state looks like, so in the case of Go, you have the eight planes, 19 by 19 spatial resolution, and once you take some action in the Monte Carlo tree search, what you'll end up here is, again, basically the input observations, and not some uninterpretable hidden state like in the case of Mu Zero, so you'll end up here with, again, with some eight planes, and you'll have 19 by 19 basically boards, and that's here, and again, once you play some other action here, a prime, again here you'll have the interpretable result. Because you have the rules, because you have the simulator, you can do that. In the case of Mu Zero, you don't have that, so here you'll have, instead of eight, you'll have those 256 planes, and you don't have any interpretation of that hidden volume, there's just some state that the Mu Zero learns how to build up, so that you can predict the policy, the value, and the rewards. So that's what I want you to understand, that's the first thing. The second part is, and I already kind of explained this, Mu Zero only masks legal actions at the root of the search tree where the environment can be queried, but does not perform any masking within the search tree itself. Okay, so what does that mean? Basically, in the case of Go again, you have 361 actions going from the root node, you'll mask some of those out because you can query the environment, and that means maybe you mask some portion here, and you'll have this part available for simulations, and you'll be building the tree, but the thing is, all of the other nodes here will have all of the actions available because you don't have the simulator, and so that's the second part. And the third part is the terminal node, so inside the tree, the search can proceed past a terminal node. In this case, the network is expected to always predict the same value. This is achieved by treating terminal states as absorbing states during training. So what they say here is the following, so because once you have the simulator, once you arrive at a certain state, the terminal state, the simulator will just tell you, hey, this is a terminal state, you can take the reward, you just back up the reward, up the Monte Carlo tree search, and that's it. That's what we've done in AlphaGo, in AlphaGo Zero, and AlphaZero. Here, you can actually go past this state because you don't know that it's a terminal state, and that's kind of a problem. And they mention here that somehow, and I don't understand this part really well, like it's kind of confusing, they didn't explain it really well in the paper how they enforce that the value function always predicts the same value. Yeah, so if you maybe know the answer, just comment down below, but for now, we can just treat it as a black box and continue with this video. Let me just now explain to you the training procedure itself. Okay. So we've been saving these experience replays into the replay buffer, and now what we do is we sample one of the real sequences. So this is one of the real sequences we've stored, and you can see the input states, and you can see some actions. And what we do is we take one state, so the first state, we pass it into our representation functions of the resonant, and we get some hidden state here. Okay. What we do is we pass it into the prediction model, we get the policy, we get the value. Then we basically take this section that we have from the replay buffer, and we concatenate it spatially again with the hidden representation, and we pass it into the G function, the dynamics model, and out comes the reward, and out comes the next state. We repeat the process again, so we pass it through the prediction function, we get the policy, we get the value, we take the action again, we concatenate it with the hidden state, we pass it into the G, the dynamics model, and again we get the hidden state, etc., etc. So basically, they've been using these, and they say it somewhere here. So in each case, we train mu0 for K5 hypothetical steps. So that means they'll have, even though you can see only three here, they basically in practice use five of these steps, and now once you have this, this is how you train the thing. So you make sure that this policy here is the same as this one, and you've stored this one in the replay buffer, so you can use it as the target, and just apply a simple cross entropy law, so you minimize the KL divergence, you make this to the same, and that's one component of the loss. The second component, you want to make sure the value function becomes as close as possible to the outcome of the game. So in the case of Go, the game will, after you roll this out, at the end you'll either win and get plus one, you'll have a tie, so zero, or you'll lose, that's minus one, and you'll make sure to, and let's just kind of denote this as Z, and you'll just want to make sure that V minus Z squared gets to zero, and that's simple mean square error loss, and finally you do the same thing for rewards, except that in board games such as Go, because the rewards are always zero, until the very end you actually won't be using this component, so that this thing will be used for Atari, where you have rewards along the way, but just remember there's a third component, and that's pretty much it, there is some regularization of the parameters, and that's pretty much it. So, as you can see, by putting the loss here and here, you'll be modifying, and this is some, as you can see, recurrent process, so whatever came here is going to influence the values here, so you can treat this as a rule, like the recurrent neural network, even though they are not using recurrent neural network here, basically they'll be tweaking all of these parameters, the parameters of the dynamics model, the parameters of the prediction functions, and the parameters of H, the representation function, to learn this model, and eventually you'll have a pretty decent dynamics model, which basically now contains the rules of the game, and that's awesome. So, the part that's maybe confusing is, as you can see here, what keeps this hidden state, which doesn't have any interpretation, correlated to this input real state that we sampled from the replay buffer, is exactly the loss. So, by making sure that the prediction function from this state gives you valid policy and value, eventually this state will have something to do with this state, even though they didn't enforce any constraints upon this hidden state, so you can't reconstruct the actual observations going from this state, that's not how they train it, and yet it works, because the only thing we want to encode into this is, we want to be sure, we want to make sure that we can actually get the policy, get the value, and get the reward from these states, and that's it. And they mentioned that here, so, at every one of these steps, the model predicts the policy, the value function, and the immediate reward. The model is trained end-to-end with the sole objective of accurately estimating these three important quantities, so as to match the improved estimates of policy, coming from the Monte Carlo Tree Search, and value generated by search, as well as the observed reward. There is no direct constraint or requirement for the hidden state to capture all information necessary to reconstruct the original observation, so you can go from the hidden state to the actual input observations, and that's not needed, because we only care about the three quantities. Finally, instead, the hidden states are free to represent state in whatever way is relevant to predicting the current and future values and policies. Intuitively, the agent can invent internally the rules of dynamics that lead to most accurate planning, and that's what's so awesome about Mu0. Basically, by doing this process here, you learn this model, and it just works. They say here, again, no semantics attached to the state. You just predict these, and it's just solved all by itself. Here is the loss function. Again, basically, this is the cross-entropy I mentioned, so this is the raw policy, this is the Monte Carlo policy. You want to make sure those are the same. Just a simple mean square error here for the value function, and for the reward, you also do MSE between the reward you got and between your output from your dynamics model G. Finally, the regularization, so theta just comprises out of theta F plus theta H, and finally, you have theta G. That's the Mu0 model, and you just do L2 regularization. That's the final loss. You have five hypothetical steps. You just train it on the bunch of trajectories, and we can see now the results. Let me show you this. Basically, comparing Mu0 on chess, so this is Y-axis is dealer score, number of training steps. You can see that this is probably stockfish, so it got better than stockfish at one point of time. Then we have for shrogis, similar, and finally, the game of Go. Here, you can see it gets better than Alpha0, and finally, on Atari, they took something called RT D2 agent, and this is the mean value. This is the median, and you can see that the Mu0 achieves a higher median and mean scores than the state of the art, so that's awesome. Now, there is one catch here, and that's that actually on some of the tough games like Montezuma's Revenge and Pitfall and Solaris, etc., you have zero score pretty much with Mu0. If you take a look at the distribution across all of the 57 games, so these are the 57 games here, it will have a really high score for some games, and then we'll just dip here, and for the last five or seven games, the score is going to be really low, but you can't catch that using just these two statistics, like mean and median. You need to show the fifth percentile, etc. So, like an agent called Agent57 later solved this thing and achieved much better results here, but you actually had lower results here, so it's a more general agent, but it still had lower mean and median scores than Mu0. Okay, so those are some results, and I mentioned it here, and now let me just show you some more results. Basically, this is for when you have a bunch of data, like 20 billion frames, you can see Mu0 achieved much better results than R2D2, Apex is also some distributed agent, and when they use 10x less data and something called Mu0 reanalyze, which learns how to better, basically has better data efficiency because it can reuse some of the trajectories from the replay buffer and train multiple times on those trajectories by using the freshest weights, and they show that they get much better data efficiency. Again, the scores are lower, but it still achieves state-of-the-art with less data, and that's awesome. That's pretty much it. There's a couple more things I want to mention, and that's here. So, for the game of Go, basically, after training the agent with 800 simulations for every single Monte Carlo tree search, so when you do those rollouts, you use 800 simulations, and that takes around 0.1 seconds, and they can show that by using more, by giving the agent in the evaluation, by giving it more search time, so more simulations, it achieves much better ELO, which means it generalizes to search trees that it hasn't encountered during training, and that's awesome. You can see that until, like, two orders of magnitude, it still has a pretty decent increase in ELO score. The same thing doesn't apply for Atari, because Atari, they speculate that the dynamics model, the G model, is harder to learn there, so you can imagine why, because you have to kind of understand how to transition the frames, which are a tougher problem than analyzing the board states, and basically, they train it with 50 simulations, and you can see it does improve until 100, but then it just kind of flattens and just slowly starts to actually go down. So, yeah, so Atari is a bit different. Here, nothing interesting, basically, the more simulations, the better results, as we can expect. That's pretty much it, let me just see whether there is something more interesting to tell you here. Yeah, there is a small difference in the search algorithm, because now we have rewards along the way, and not just in the terminal states, like in the case of board games, and because of that, they had to introduce this, as you can see, this notion of this cumulative reward, and they say here the backup is generalized to the case where the environment can emit intermediate rewards, have a discount gamma different from one, and the value estimates are unbounded. And basically, now, once you, as you can see here, this is familiar, so your visitation count and your, this is the action value function, the way you're now updating it is by adding this G estimate, and that's just the sum of discounted rewards plus the bootstrapped value here. So, yeah, so in the case of board games, these would all be zero, pretty much, and you'll just have the bootstrap from the leaf node, and you'd propagate that one up the tree, so you'd back up those values, but here you have all of these in case of Atari. That also has some consequences that we have to now normalize the Q values, because, as I said, rewards are, you have intermediate rewards which can be unbounded, so you have to do this normalization in order to have this thing interact really well with the other part of the PUCT algorithm. So basically, you have, as you remember, you have the Q, and you have this prior times the visitations, so the more you visit something, this will get higher, so this will get lower, and basically, finally, you'll just rely on the Q value, so you want to make sure that this is of similar scale as this thing, so you just have the normalization by saving the max and min Q values throughout the Monte Carlo tree search. You'll be logging that statistic, and you can use it here to normalize your Q. So just a couple of technical details, but hopefully you got the gist of the algorithm. I think it's pretty neat, basically, it achieved really good scores, so again, it'd be really nice if, in my opinion, if we could have the scores be as close, like even better than Agent 57, that would be really impressive, but yeah, those games require long-term planning, and Mew Zero just couldn't solve it with this approach. Maybe that's the forward, like future research direction. That's it. Hopefully you enjoyed this video, if you did, leave a like, subscribe, share, and see you in the next video.
[{"start": 0.0, "end": 5.82, "text": " Finally, I'm going to cover Mu0, the latest agent in the lineage of AlphaGo agents, in this paper called"}, {"start": 5.82, "end": 14.46, "text": " Mastering Atari, Go, Chess, and Shogi, by planning with a learn model, and again, that's the DeepMind crew"}, {"start": 14.46, "end": 24.060000000000002, "text": " that's been working on this since 2014 or something, and basically, it'd be really helpful if you already watched"}, {"start": 24.06, "end": 31.68, "text": " my previous videos on AlphaGo, AlphaGo 0, and Alpha0, because many of the details still apply here, so do watch those,"}, {"start": 31.68, "end": 37.879999999999995, "text": " I'll link it somewhere here. Okay, before I start digging into the paper, let me just quickly walk you through"}, {"start": 37.879999999999995, "end": 45.06, "text": " what happened with this lineage of agents, and the first thing that happened was AlphaGo, back in 2015,"}, {"start": 45.06, "end": 51.599999999999994, "text": " they developed this agent which could solve the game of Go, but the trick was it used a lot of human data,"}, {"start": 51.6, "end": 62.1, "text": " so the professional games played by Go players, and it had a lot of Go-specific heuristics integrated into the agent itself,"}, {"start": 62.1, "end": 71.6, "text": " and it also knew the rules of the game, obviously, and then they had AlphaGo 0, which basically also played Go,"}, {"start": 71.6, "end": 78.56, "text": " and was even better than AlphaGo, but the trick was they didn't use any human data, they were just using pure self-play"}, {"start": 78.56, "end": 86.32000000000001, "text": " reinforcement learning, and the algorithm, the agent, learned how to play by itself, and became the best player ever so far."}, {"start": 86.32000000000001, "end": 94.22, "text": " The next step was doing the Alpha0, which basically was a minor, let's say minor, probably a lot of engineering,"}, {"start": 94.22, "end": 100.96000000000001, "text": " but a minor conceptual change, so they had to prune a couple more details from AlphaGo 0 in order to make it general enough"}, {"start": 100.96000000000001, "end": 107.16, "text": " so that it can play not only Go, but also chess and shogi, which is a so-called Japanese chess,"}, {"start": 107.16, "end": 115.52, "text": " and again, we didn't have any human data, but we did have the rules, and the latest agent in this lineage is Mu0,"}, {"start": 115.52, "end": 122.92, "text": " which is this paper, and basically, they just ditched the rules, and I'll explain in a minute what that means,"}, {"start": 122.92, "end": 128.92, "text": " and it can also play Atari games now, so the Atari 57 games in the Atari benchmark,"}, {"start": 128.92, "end": 134.72, "text": " so when they say they don't have the rules, what does that mean? Well, basically, that means that during the,"}, {"start": 134.72, "end": 140.12, "text": " so if you watched my previous videos, you know what Monte Carlo Tree Search is, and basically what it means is that"}, {"start": 140.12, "end": 147.52, "text": " during the Monte Carlo Tree Search, you don't have the available simulator, so you don't know how to, given some action,"}, {"start": 147.52, "end": 154.96, "text": " so starting from a root state, S0, given some action, you don't know what the next state here will be,"}, {"start": 154.96, "end": 159.92, "text": " you don't know how the exact layout of the boards will look like in the case of board games, or in the case of Atari,"}, {"start": 159.92, "end": 166.11999999999998, "text": " you don't know what the next screen will look like, and basically, because you don't have the simulator,"}, {"start": 166.11999999999998, "end": 172.72, "text": " you'll have to learn the dynamics model, and we'll see, and that's the whole main paper, the main idea of this paper,"}, {"start": 172.72, "end": 179.39999999999998, "text": " is to learn the dynamics model, and then subsequently use it in order to plan, in order to play all of these games,"}, {"start": 179.39999999999998, "end": 187.11999999999998, "text": " so let's see how they managed to pull it off, so they say here, we present the Mu0 algorithm, which by combining a Tree-based search,"}, {"start": 187.12, "end": 194.32, "text": " so again, Monte Carlo Tree Search, with a learned model, that's the novelty, achieves superhuman performance in a range of challenging"}, {"start": 194.32, "end": 200.72, "text": " and visually complex domains, without any knowledge of the underlying dynamics, so that's what I mentioned already,"}, {"start": 200.72, "end": 209.72, "text": " and you'll understand that as this video progresses, so when evaluating on Go, Chess, and Shogi, without any knowledge of the game rules,"}, {"start": 209.72, "end": 216.92000000000002, "text": " Mu0 matched the superhuman performance of the AlphaZero agent, so that's this one, algorithm that was supplied"}, {"start": 216.92, "end": 226.92, "text": " with the game rules, and it also achieves state of the art on this Atari 57 benchmark, and that's pretty awesome as well."}, {"start": 226.92, "end": 238.32, "text": " Okay, so let's dig into the algorithm straight away, and I'll skip this part for now, and let's just explain how everything looks like in Mu0."}, {"start": 238.32, "end": 246.32, "text": " Okay, so first, let's understand the algorithm itself. First things first, the Mu0 agent consists out of three parts,"}, {"start": 246.32, "end": 258.71999999999997, "text": " so the first part is the representation function, H, the second function is the prediction function, F, which will give us the policy and the value function,"}, {"start": 258.71999999999997, "end": 267.32, "text": " and finally, we'll have something called G function, or the dynamics function, and given the state and given the action,"}, {"start": 267.32, "end": 274.12, "text": " it will just output the next state, and it will output the reward, okay, and this is what we're trying to learn here,"}, {"start": 274.12, "end": 278.92, "text": " so we don't have the simulator, the perfect simulator, we have this dynamics model, which we're trying to learn,"}, {"start": 278.92, "end": 289.52, "text": " and so these three components together comprise the Mu0 model, okay, so this is the input state, and the thing is,"}, {"start": 289.52, "end": 296.92, "text": " because we have Atari, we have Go, Chess, and Shogi, and I'll just give you an example of how this thing looks like for Go,"}, {"start": 296.92, "end": 303.12, "text": " and how it looks for Atari as two representative cases, so for Go, this thing, whoops, will look like this,"}, {"start": 303.12, "end": 312.12, "text": " so we'll have eight planes, and each plane will have 19 by 19 resolution, because that's how the Go board looks like,"}, {"start": 312.12, "end": 319.32, "text": " so this is going to be, so eight, and the reason we have eight is because in order to play Go, you need to have some past observations,"}, {"start": 319.32, "end": 327.32, "text": " otherwise you can't play the game, okay, so for Atari, this is going to look like, so similarly, we'll have 32 times three,"}, {"start": 327.32, "end": 339.12, "text": " because we have RGB frames, we'll have to encode 32 frames, and so this is going to look like this, and that's like, I think, 96 by 96 resolution,"}, {"start": 339.12, "end": 346.92, "text": " and we'll have additionally 32 planes for the 32 previous actions, and that's also needed, because in order to play Atari,"}, {"start": 346.92, "end": 353.52, "text": " you just need those actions encoded, and we're just going to broadcast, for example, if the action was zero,"}, {"start": 353.52, "end": 361.71999999999997, "text": " you're just going to put a bias plane with all zeros stacked here, if it was one, you're just going to input one over 18,"}, {"start": 361.71999999999997, "end": 369.71999999999997, "text": " because Atari has 18 actions, so that's how they encode the actions, as just constant bias planes here,"}, {"start": 369.71999999999997, "end": 377.91999999999996, "text": " so once we have those volumes, those represent the input states, and now we have the H function, which is a simple resonant,"}, {"start": 377.92, "end": 385.32, "text": " so you'll just pass that volume into a resonant, and out comes the hidden representation, the hidden state,"}, {"start": 385.32, "end": 395.32, "text": " and it's going to look similarly, it's going to have 256 planes, and depending on whether we have Atari, or whether we have Go, or whatever,"}, {"start": 395.32, "end": 404.72, "text": " for Atari, it's going to be 6 by 6 resolution, and for Go, it's going to remain the same, so 19 by 19, because again, the board has 19 by 19 resolution,"}, {"start": 404.72, "end": 413.52000000000004, "text": " okay, and now we just apply Monte Carlo Tree search in the following manner, we have the F function, which is the prediction function,"}, {"start": 413.52000000000004, "end": 420.12, "text": " which is also a convolutional neural network, and we just pass this hidden state into it, and out comes the policy,"}, {"start": 420.12, "end": 430.72, "text": " so the policy will be like 361 dimensional vector, in the case of Go, and the value will just be the value function,"}, {"start": 430.72, "end": 440.12, "text": " which gives you the expected reward you'll get going from this state to the end of the game, just basic reinforcement learning stuff,"}, {"start": 440.12, "end": 450.72, "text": " so that's that part, and using those priors, using those probabilities coming from the policy, that's going to be your prior in your Monte Carlo Tree search,"}, {"start": 450.72, "end": 458.92, "text": " if you remember from the previous videos, and you're just going to take the maximum, like the PUCT value, and for example, you took this branch,"}, {"start": 458.92, "end": 467.12, "text": " and once you have that action, you're going to pass it into this G function, so let's see how that functions,"}, {"start": 467.12, "end": 477.72, "text": " so again, I explained we have this hidden state, and it looks like this, so 256 there, and this is dependent on the game itself,"}, {"start": 477.72, "end": 486.12, "text": " so this is 256, and what we're going to do is, we're going to encode this action, again, spatially,"}, {"start": 486.12, "end": 495.12, "text": " so as I previously said, for example, for Atari, you're just going to add a bias plane here, and this is what's going into the G function,"}, {"start": 495.12, "end": 503.92, "text": " and out goes the next hidden state, which will again have 256 planes, and out goes the reward here,"}, {"start": 503.92, "end": 513.52, "text": " so just by doing this, and doing the simulations through the Monte Carlo, using this G model, the dynamics model, and the prediction, and the representation models,"}, {"start": 513.52, "end": 520.52, "text": " you'll build up the Monte Carlo tree search, and then, as you know, you just take the highest visitation count in the root,"}, {"start": 520.52, "end": 527.3199999999999, "text": " and that's your next action, and so, as you can see here, you just pick the maximum visitation count action,"}, {"start": 527.3199999999999, "end": 532.92, "text": " and you pass it to the environment, the environment gives you some reward, and it gives you the next observation,"}, {"start": 532.92, "end": 540.92, "text": " so basically, you'll just, in the case of, say, Go, because those are 8 boards, you'll just pop the oldest one,"}, {"start": 540.92, "end": 548.52, "text": " and you'll just append the newest board state that came from the environment, and that's your new input state,"}, {"start": 548.52, "end": 553.52, "text": " and then you just recursively repeat this until the end of the game, and then the environment tells you,"}, {"start": 553.52, "end": 562.52, "text": " okay, this environment will just stop you, and what you'll do is you'll be saving those trajectories into this centralized replay buffer,"}, {"start": 562.52, "end": 571.92, "text": " where all of these actors are going to store their experience, so basically, Mu0 is a distributed agent,"}, {"start": 571.92, "end": 578.52, "text": " that means you'll have multiple actors, so all of these are maybe separate threads, and they'll be executing this thing here,"}, {"start": 578.52, "end": 586.12, "text": " they'll be collecting experience, they'll be saving stuff like this thing, like the policy coming, the refund policy from the Monte Carlo tree search,"}, {"start": 586.12, "end": 592.92, "text": " and rewards, and states, they'll be saving those tuples here, and later, you can use those to train this thing."}, {"start": 592.92, "end": 598.72, "text": " Now, there is one thing that may confuse you, and that's how does this thing play without any rules,"}, {"start": 598.72, "end": 606.52, "text": " and the answer is, like the partial answer, and we'll dig into it a bit later, is basically, only in this root state,"}, {"start": 606.52, "end": 613.72, "text": " you can query the environment and ask what the valid actions are, so as you can imagine, for example, in the case of Go,"}, {"start": 613.72, "end": 620.72, "text": " you'll have 361 branches here, and not every single one is going to be legal, so once you communicate with the environment,"}, {"start": 620.72, "end": 627.32, "text": " it tells you maybe these actions here are invalid, that means you'll just pull the priors, the probabilities to zero,"}, {"start": 627.32, "end": 633.72, "text": " and you'll take that probability mass, and you'll just proportionally distribute it across all of the other branches,"}, {"start": 633.72, "end": 641.72, "text": " and so doing that, you'll basically be building the Monte Carlo tree search, where the root node will kind of constrain you,"}, {"start": 641.72, "end": 650.52, "text": " constrain your space, but all of the other nodes here, like all of these, they'll have all of the 361 actions available in the case of Go,"}, {"start": 650.52, "end": 658.9200000000001, "text": " and that means you may play some, initially, you'll be playing maybe some impossible games, illegal games, but that doesn't matter,"}, {"start": 658.9200000000001, "end": 668.12, "text": " eventually, during training, the model will learn how to basically do the correct steps, it will learn the rules of the game, basically."}, {"start": 668.12, "end": 678.52, "text": " Okay, before explaining the actual training procedure, let me just further clarify how it works without any rules,"}, {"start": 678.52, "end": 683.32, "text": " and that's the part that bugged me a lot, initially, so let me try and explain it."}, {"start": 683.32, "end": 688.92, "text": " So, first of all, specifically, AlphaGo Zero and AlphaZero use knowledge of the rules of the game in three places,"}, {"start": 688.92, "end": 697.52, "text": " so state transitions in the search tree, actions available at each node of the search tree, and episode termination within the search tree,"}, {"start": 697.52, "end": 701.12, "text": " so there are three parts to understanding how this thing works without any rules."}, {"start": 701.12, "end": 710.3199999999999, "text": " First things first, this one. So, AlphaZero had access to a perfect simulator of the true dynamics process, so this is how the thing looks like."}, {"start": 710.3199999999999, "end": 718.92, "text": " You basically have, so this is the root of the Monte Carlo tree search, so this is your initial state, you start building the Monte Carlo tree search like this,"}, {"start": 718.92, "end": 725.52, "text": " and what's the difference? Well, I already explained how the input state looks like, so in the case of Go, you have the eight planes,"}, {"start": 725.52, "end": 737.12, "text": " 19 by 19 spatial resolution, and once you take some action in the Monte Carlo tree search, what you'll end up here is, again, basically the input observations,"}, {"start": 737.12, "end": 745.72, "text": " and not some uninterpretable hidden state like in the case of Mu Zero, so you'll end up here with, again, with some eight planes,"}, {"start": 745.72, "end": 758.32, "text": " and you'll have 19 by 19 basically boards, and that's here, and again, once you play some other action here, a prime, again here you'll have the interpretable result."}, {"start": 758.32, "end": 767.12, "text": " Because you have the rules, because you have the simulator, you can do that. In the case of Mu Zero, you don't have that, so here you'll have, instead of eight,"}, {"start": 767.12, "end": 779.72, "text": " you'll have those 256 planes, and you don't have any interpretation of that hidden volume, there's just some state that the Mu Zero learns how to build up,"}, {"start": 779.72, "end": 786.12, "text": " so that you can predict the policy, the value, and the rewards. So that's what I want you to understand, that's the first thing."}, {"start": 786.12, "end": 794.72, "text": " The second part is, and I already kind of explained this, Mu Zero only masks legal actions at the root of the search tree where the environment can be queried,"}, {"start": 794.72, "end": 806.12, "text": " but does not perform any masking within the search tree itself. Okay, so what does that mean? Basically, in the case of Go again, you have 361 actions going from the root node,"}, {"start": 806.12, "end": 817.12, "text": " you'll mask some of those out because you can query the environment, and that means maybe you mask some portion here, and you'll have this part available for simulations,"}, {"start": 817.12, "end": 825.52, "text": " and you'll be building the tree, but the thing is, all of the other nodes here will have all of the actions available because you don't have the simulator,"}, {"start": 825.52, "end": 833.72, "text": " and so that's the second part. And the third part is the terminal node, so inside the tree, the search can proceed past a terminal node."}, {"start": 833.72, "end": 842.12, "text": " In this case, the network is expected to always predict the same value. This is achieved by treating terminal states as absorbing states during training."}, {"start": 842.12, "end": 850.32, "text": " So what they say here is the following, so because once you have the simulator, once you arrive at a certain state, the terminal state,"}, {"start": 850.32, "end": 859.32, "text": " the simulator will just tell you, hey, this is a terminal state, you can take the reward, you just back up the reward, up the Monte Carlo tree search, and that's it."}, {"start": 859.32, "end": 868.12, "text": " That's what we've done in AlphaGo, in AlphaGo Zero, and AlphaZero. Here, you can actually go past this state because you don't know that it's a terminal state,"}, {"start": 868.12, "end": 876.72, "text": " and that's kind of a problem. And they mention here that somehow, and I don't understand this part really well, like it's kind of confusing,"}, {"start": 876.72, "end": 885.52, "text": " they didn't explain it really well in the paper how they enforce that the value function always predicts the same value."}, {"start": 885.52, "end": 894.32, "text": " Yeah, so if you maybe know the answer, just comment down below, but for now, we can just treat it as a black box and continue with this video."}, {"start": 894.32, "end": 903.9200000000001, "text": " Let me just now explain to you the training procedure itself. Okay. So we've been saving these experience replays into the replay buffer,"}, {"start": 903.9200000000001, "end": 911.72, "text": " and now what we do is we sample one of the real sequences. So this is one of the real sequences we've stored, and you can see the input states,"}, {"start": 911.72, "end": 919.32, "text": " and you can see some actions. And what we do is we take one state, so the first state, we pass it into our representation functions of the resonant,"}, {"start": 919.32, "end": 928.32, "text": " and we get some hidden state here. Okay. What we do is we pass it into the prediction model, we get the policy, we get the value."}, {"start": 928.32, "end": 938.12, "text": " Then we basically take this section that we have from the replay buffer, and we concatenate it spatially again with the hidden representation,"}, {"start": 938.12, "end": 944.9200000000001, "text": " and we pass it into the G function, the dynamics model, and out comes the reward, and out comes the next state."}, {"start": 944.92, "end": 952.3199999999999, "text": " We repeat the process again, so we pass it through the prediction function, we get the policy, we get the value, we take the action again,"}, {"start": 952.3199999999999, "end": 958.92, "text": " we concatenate it with the hidden state, we pass it into the G, the dynamics model, and again we get the hidden state, etc., etc."}, {"start": 958.92, "end": 969.92, "text": " So basically, they've been using these, and they say it somewhere here. So in each case, we train mu0 for K5 hypothetical steps."}, {"start": 969.92, "end": 976.7199999999999, "text": " So that means they'll have, even though you can see only three here, they basically in practice use five of these steps,"}, {"start": 976.7199999999999, "end": 988.92, "text": " and now once you have this, this is how you train the thing. So you make sure that this policy here is the same as this one,"}, {"start": 988.92, "end": 995.92, "text": " and you've stored this one in the replay buffer, so you can use it as the target, and just apply a simple cross entropy law,"}, {"start": 995.92, "end": 1001.92, "text": " so you minimize the KL divergence, you make this to the same, and that's one component of the loss."}, {"start": 1001.92, "end": 1009.52, "text": " The second component, you want to make sure the value function becomes as close as possible to the outcome of the game."}, {"start": 1009.52, "end": 1016.92, "text": " So in the case of Go, the game will, after you roll this out, at the end you'll either win and get plus one, you'll have a tie,"}, {"start": 1016.92, "end": 1024.52, "text": " so zero, or you'll lose, that's minus one, and you'll make sure to, and let's just kind of denote this as Z,"}, {"start": 1024.52, "end": 1033.92, "text": " and you'll just want to make sure that V minus Z squared gets to zero, and that's simple mean square error loss,"}, {"start": 1033.92, "end": 1041.32, "text": " and finally you do the same thing for rewards, except that in board games such as Go, because the rewards are always zero,"}, {"start": 1041.32, "end": 1048.52, "text": " until the very end you actually won't be using this component, so that this thing will be used for Atari, where you have rewards along the way,"}, {"start": 1048.52, "end": 1056.72, "text": " but just remember there's a third component, and that's pretty much it, there is some regularization of the parameters, and that's pretty much it."}, {"start": 1056.72, "end": 1065.52, "text": " So, as you can see, by putting the loss here and here, you'll be modifying, and this is some, as you can see, recurrent process,"}, {"start": 1065.52, "end": 1072.72, "text": " so whatever came here is going to influence the values here, so you can treat this as a rule, like the recurrent neural network,"}, {"start": 1072.72, "end": 1077.92, "text": " even though they are not using recurrent neural network here, basically they'll be tweaking all of these parameters,"}, {"start": 1077.92, "end": 1087.1200000000001, "text": " the parameters of the dynamics model, the parameters of the prediction functions, and the parameters of H, the representation function,"}, {"start": 1087.1200000000001, "end": 1099.1200000000001, "text": " to learn this model, and eventually you'll have a pretty decent dynamics model, which basically now contains the rules of the game, and that's awesome."}, {"start": 1099.12, "end": 1109.9199999999998, "text": " So, the part that's maybe confusing is, as you can see here, what keeps this hidden state, which doesn't have any interpretation,"}, {"start": 1109.9199999999998, "end": 1117.7199999999998, "text": " correlated to this input real state that we sampled from the replay buffer, is exactly the loss."}, {"start": 1117.7199999999998, "end": 1127.52, "text": " So, by making sure that the prediction function from this state gives you valid policy and value,"}, {"start": 1127.52, "end": 1135.12, "text": " eventually this state will have something to do with this state, even though they didn't enforce any constraints upon this hidden state,"}, {"start": 1135.12, "end": 1142.12, "text": " so you can't reconstruct the actual observations going from this state, that's not how they train it, and yet it works,"}, {"start": 1142.12, "end": 1149.72, "text": " because the only thing we want to encode into this is, we want to be sure, we want to make sure that we can actually get the policy,"}, {"start": 1149.72, "end": 1153.92, "text": " get the value, and get the reward from these states, and that's it."}, {"start": 1153.92, "end": 1162.72, "text": " And they mentioned that here, so, at every one of these steps, the model predicts the policy, the value function, and the immediate reward."}, {"start": 1162.72, "end": 1168.72, "text": " The model is trained end-to-end with the sole objective of accurately estimating these three important quantities,"}, {"start": 1168.72, "end": 1177.52, "text": " so as to match the improved estimates of policy, coming from the Monte Carlo Tree Search, and value generated by search, as well as the observed reward."}, {"start": 1177.52, "end": 1185.52, "text": " There is no direct constraint or requirement for the hidden state to capture all information necessary to reconstruct the original observation,"}, {"start": 1185.52, "end": 1193.72, "text": " so you can go from the hidden state to the actual input observations, and that's not needed, because we only care about the three quantities."}, {"start": 1193.72, "end": 1201.92, "text": " Finally, instead, the hidden states are free to represent state in whatever way is relevant to predicting the current and future values and policies."}, {"start": 1201.92, "end": 1210.52, "text": " Intuitively, the agent can invent internally the rules of dynamics that lead to most accurate planning, and that's what's so awesome about Mu0."}, {"start": 1210.52, "end": 1217.1200000000001, "text": " Basically, by doing this process here, you learn this model, and it just works."}, {"start": 1217.1200000000001, "end": 1224.3200000000002, "text": " They say here, again, no semantics attached to the state. You just predict these, and it's just solved all by itself."}, {"start": 1224.32, "end": 1235.52, "text": " Here is the loss function. Again, basically, this is the cross-entropy I mentioned, so this is the raw policy, this is the Monte Carlo policy."}, {"start": 1235.52, "end": 1243.72, "text": " You want to make sure those are the same. Just a simple mean square error here for the value function, and for the reward,"}, {"start": 1243.72, "end": 1250.12, "text": " you also do MSE between the reward you got and between your output from your dynamics model G."}, {"start": 1250.12, "end": 1262.9199999999998, "text": " Finally, the regularization, so theta just comprises out of theta F plus theta H, and finally, you have theta G."}, {"start": 1262.9199999999998, "end": 1268.12, "text": " That's the Mu0 model, and you just do L2 regularization. That's the final loss."}, {"start": 1268.12, "end": 1276.52, "text": " You have five hypothetical steps. You just train it on the bunch of trajectories, and we can see now the results."}, {"start": 1276.52, "end": 1286.12, "text": " Let me show you this. Basically, comparing Mu0 on chess, so this is Y-axis is dealer score, number of training steps."}, {"start": 1286.12, "end": 1290.72, "text": " You can see that this is probably stockfish, so it got better than stockfish at one point of time."}, {"start": 1290.72, "end": 1297.52, "text": " Then we have for shrogis, similar, and finally, the game of Go. Here, you can see it gets better than Alpha0,"}, {"start": 1297.52, "end": 1306.72, "text": " and finally, on Atari, they took something called RT D2 agent, and this is the mean value. This is the median,"}, {"start": 1306.72, "end": 1314.32, "text": " and you can see that the Mu0 achieves a higher median and mean scores than the state of the art, so that's awesome."}, {"start": 1314.32, "end": 1324.52, "text": " Now, there is one catch here, and that's that actually on some of the tough games like Montezuma's Revenge and Pitfall and Solaris, etc.,"}, {"start": 1324.52, "end": 1331.92, "text": " you have zero score pretty much with Mu0. If you take a look at the distribution across all of the 57 games,"}, {"start": 1331.92, "end": 1339.12, "text": " so these are the 57 games here, it will have a really high score for some games, and then we'll just dip here,"}, {"start": 1339.12, "end": 1348.72, "text": " and for the last five or seven games, the score is going to be really low, but you can't catch that using just these two statistics,"}, {"start": 1348.72, "end": 1357.52, "text": " like mean and median. You need to show the fifth percentile, etc. So, like an agent called Agent57 later solved this thing"}, {"start": 1357.52, "end": 1363.72, "text": " and achieved much better results here, but you actually had lower results here, so it's a more general agent,"}, {"start": 1363.72, "end": 1373.52, "text": " but it still had lower mean and median scores than Mu0. Okay, so those are some results, and I mentioned it here,"}, {"start": 1373.52, "end": 1381.72, "text": " and now let me just show you some more results. Basically, this is for when you have a bunch of data, like 20 billion frames,"}, {"start": 1381.72, "end": 1390.12, "text": " you can see Mu0 achieved much better results than R2D2, Apex is also some distributed agent, and when they use 10x less data"}, {"start": 1390.12, "end": 1402.32, "text": " and something called Mu0 reanalyze, which learns how to better, basically has better data efficiency because it can reuse some of the trajectories"}, {"start": 1402.32, "end": 1412.52, "text": " from the replay buffer and train multiple times on those trajectories by using the freshest weights, and they show that they get much better data efficiency."}, {"start": 1412.52, "end": 1420.52, "text": " Again, the scores are lower, but it still achieves state-of-the-art with less data, and that's awesome. That's pretty much it."}, {"start": 1420.52, "end": 1430.72, "text": " There's a couple more things I want to mention, and that's here. So, for the game of Go, basically, after training the agent"}, {"start": 1430.72, "end": 1440.32, "text": " with 800 simulations for every single Monte Carlo tree search, so when you do those rollouts, you use 800 simulations, and that takes around 0.1 seconds,"}, {"start": 1440.32, "end": 1450.1200000000001, "text": " and they can show that by using more, by giving the agent in the evaluation, by giving it more search time, so more simulations,"}, {"start": 1450.1200000000001, "end": 1458.92, "text": " it achieves much better ELO, which means it generalizes to search trees that it hasn't encountered during training, and that's awesome."}, {"start": 1458.92, "end": 1468.1200000000001, "text": " You can see that until, like, two orders of magnitude, it still has a pretty decent increase in ELO score."}, {"start": 1468.1200000000001, "end": 1477.72, "text": " The same thing doesn't apply for Atari, because Atari, they speculate that the dynamics model, the G model, is harder to learn there,"}, {"start": 1477.72, "end": 1487.52, "text": " so you can imagine why, because you have to kind of understand how to transition the frames, which are a tougher problem than analyzing the board states,"}, {"start": 1487.52, "end": 1499.12, "text": " and basically, they train it with 50 simulations, and you can see it does improve until 100, but then it just kind of flattens and just slowly starts to actually go down."}, {"start": 1499.12, "end": 1507.92, "text": " So, yeah, so Atari is a bit different. Here, nothing interesting, basically, the more simulations, the better results, as we can expect."}, {"start": 1507.92, "end": 1513.72, "text": " That's pretty much it, let me just see whether there is something more interesting to tell you here."}, {"start": 1513.72, "end": 1522.52, "text": " Yeah, there is a small difference in the search algorithm, because now we have rewards along the way, and not just in the terminal states, like in the case of board games,"}, {"start": 1522.52, "end": 1531.1200000000001, "text": " and because of that, they had to introduce this, as you can see, this notion of this cumulative reward,"}, {"start": 1531.1200000000001, "end": 1540.1200000000001, "text": " and they say here the backup is generalized to the case where the environment can emit intermediate rewards, have a discount gamma different from one, and the value estimates are unbounded."}, {"start": 1540.12, "end": 1551.12, "text": " And basically, now, once you, as you can see here, this is familiar, so your visitation count and your, this is the action value function,"}, {"start": 1551.12, "end": 1563.7199999999998, "text": " the way you're now updating it is by adding this G estimate, and that's just the sum of discounted rewards plus the bootstrapped value here."}, {"start": 1563.72, "end": 1572.52, "text": " So, yeah, so in the case of board games, these would all be zero, pretty much, and you'll just have the bootstrap from the leaf node,"}, {"start": 1572.52, "end": 1582.1200000000001, "text": " and you'd propagate that one up the tree, so you'd back up those values, but here you have all of these in case of Atari."}, {"start": 1582.12, "end": 1595.12, "text": " That also has some consequences that we have to now normalize the Q values, because, as I said, rewards are, you have intermediate rewards which can be unbounded,"}, {"start": 1595.12, "end": 1604.52, "text": " so you have to do this normalization in order to have this thing interact really well with the other part of the PUCT algorithm."}, {"start": 1604.52, "end": 1613.72, "text": " So basically, you have, as you remember, you have the Q, and you have this prior times the visitations, so the more you visit something, this will get higher,"}, {"start": 1613.72, "end": 1622.32, "text": " so this will get lower, and basically, finally, you'll just rely on the Q value, so you want to make sure that this is of similar scale as this thing,"}, {"start": 1622.32, "end": 1629.92, "text": " so you just have the normalization by saving the max and min Q values throughout the Monte Carlo tree search."}, {"start": 1629.92, "end": 1633.92, "text": " You'll be logging that statistic, and you can use it here to normalize your Q."}, {"start": 1633.92, "end": 1638.3200000000002, "text": " So just a couple of technical details, but hopefully you got the gist of the algorithm."}, {"start": 1638.3200000000002, "end": 1650.92, "text": " I think it's pretty neat, basically, it achieved really good scores, so again, it'd be really nice if, in my opinion, if we could have the scores be as close,"}, {"start": 1650.92, "end": 1663.72, "text": " like even better than Agent 57, that would be really impressive, but yeah, those games require long-term planning, and Mew Zero just couldn't solve it with this approach."}, {"start": 1663.72, "end": 1667.92, "text": " Maybe that's the forward, like future research direction."}, {"start": 1667.92, "end": 1694.92, "text": " That's it. Hopefully you enjoyed this video, if you did, leave a like, subscribe, share, and see you in the next video."}]