DQN - Playing Atari with Deep Reinforcement Learning | RL Paper Explained
❤️ Become The AI Epiphany Patreon ❤️ ► https://www.patreon.com/theaiepiphany
▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬

In this video, I cover the paper that started the hype for deep RL - Playing Atari with deep RL, which introduced the DQN or deep Q-network.

You'll learn about:
✔️ All of the nitty-gritty details behind the paper

▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬ 
✅ Paper: https://arxiv.org/abs/1312.5602
✅ A decent gist: https://github.com/higgsfield/RL-Adventure/blob/master/1.dqn.ipynb

Note: there is an error with the target Q-function he didn't freeze it but it's good enough - until I implement something myself :P
▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬ 

⌚️ Timetable: 
01:05 High-level overview of the paper
07:00 Experience replay buffer
10:35 Difficulties with RL (correlations, non-stationary distributions)
13:30 DQN is very general
17:00 MDP formalism and optimal Q function
22:37 Function approximators
23:50 The loss function explained
28:40 The deadly triad
30:55 Algorithm walk-through
35:00 Preprocessing and architecture details
37:20 Additional details - normalizing score, schedule, etc.
42:50 Agent training metrics
47:15 Results

▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬ 
💰 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! ❤️
▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬ 

💡 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/
▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬

#dqn #deepreinforcementlearning #aiepiphany
 What's up folks? In this video I'm going to cover the paper that caused the ImageNet moment for the reinforcement learning field, the DQN paper, also known as the Playing Atari with Deep Reinforcement Learning paper by Volodymyr Mni and his collaborator at DeepMind. And I hopefully pronounce his name right. So let's dig into it. We present the first deep learning model to successfully learn control policies directly from high dimensional sensory input, IE images in this case, using RL. The model is a CNN trained with a variant of Q-learning and we'll see what it is in a moment, whose input is raw pixels and the output is a value function, actually the action value function or the Q function estimating the future rewards. We apply our method to seven Atari games and they don't adjust the architecture or the learning algorithm which makes this algorithm much more general than all of the previous ones. We find that it outperforms all previous approaches on six of the games and even surpasses a human expert on three of them. So before I start digging into the paper, I'll just give you a rough sketch so that you have a high level understanding of all of the components and then we'll start going into a lot of details as I usually do in my paper overviews. So okay, let's start. So the first thing is first, the most general framework of how RL problem is constructed is the following. So we have an agent and you'll see this all over the place and we have environment and basically the agent sends some action to the environment and the environment gives it back some observation, let's call it O and also some reward. And now the whole goal of this agent in this environment is to maximize the future expected reward and that's pretty much it. Now this can mean like every single thing you can imagine can be constructed like this pretty much, many things, maybe not everything. So let me just concretize this for the specific problem we are coping with in this paper and that's Atari. So in our case, what will happen is the following. So agent is actually a CNN. So we have a deep convolutional neural network, not so deep, you'll see soon it was actually only two convoliers. And so what we do is the following. So we interact with the environment in the following way. So the environment is the Atari emulator. So let's just draw it like some screen. And what we do is we in the case, so just a small digression here are the games in Atari. So basically here are five examples, we have Pong, we have something called Breakout, Space Invaders, SeaQuest and Beam Rider. And hopefully you're at least familiar with some of these, maybe Pong is the easiest example. So you basically have two pedals and you have a ball here and you're trying to not to miss the ball, you're trying to beat the opponent by just shooting the balls past through the opponent. And once you do that, you receive the reward one. If the opponent wins, he gets the reward of one and you get just zero. So as you can see, the problem is that the reward is very sparse, you have to play for some time in order to get one and that's it. We don't have as in supervised learning in every single step, maybe when you're doing image classification for every single image, you have a label and that's how you train. So here the reward is sparse, it's delayed and you're not sure whether the award will come at all if you're having, if you have in the beginning, especially when you have a random policy, you'll be getting zero rewards for a long, long time. So having that context in mind, so this is the image we get in Pong, this is the reward, zeros or ones in Pong. Let me get back to the thing I was trying to explain. Whoop, if I can find it, okay. Okay, so basically what happens is the following. In the Pong game, we'll have three actions. We'll have up, we'll have no up, basically just don't move and we have the down action, okay? Just three simple actions. And the state will be the following thing. The state will be not the single image because unfortunately the single image is ambiguous because for example, if you have an image and you have a ball here, you don't know whether the ball is going to go in this direction, whether it's going to go in this direction, maybe even in the opposite direction here. So you need to have at least two frames to have the temporal information so that you can solve this task. So because of that, what they actually did is they represented the state after doing some pre-processing on images. We'll see that later, they just lump four frames together. So like this, one, two, three, four, whatever. And that's a state, this is a state. And this state goes into the CNN and that's our agent and it outputs the actions. So once we put the state into the CNN, we get some numbers here and these are the action values. And basically maybe if the up value was eight and this one was two and this one was maybe minus one, with the best thing to do would be to pick eight because that promises the biggest expected reward in the future if we're following the greedy policy. And so we pick eight and that's up, we send that to the emulator. The emulator does its thing, it just renders new screen and sends it back. So it sends us back the new frame and some reward or maybe zero reward if nothing happens, if the game still hasn't finished. And what we do is the following. So we treat this as a circular buffer. So basically what we do is we just take the last frame in this state, we just get rid of it and we append to the front of this queue, the newest frame and that's our new state. So once the model is trained and I'll skip the training part for a second, let's see what happens once the model is fully trained. So the following thing happens. We have a CNN, we get the first observation, the first frame and we start stacking the frames until we get four frames. Once we have four frames, we have the full state, we do the forward prop, we get the actions, we send the action maybe up, we send it to the emulator, the emulator sends us back the reward and the observed state and we just do that in circle. And we're actually following something called Epsilon Greedy Policy and we'll see what it is in a minute. So Epsilon Greedy, which basically means the following. So instead of just taking the max action every single time, so eight in this particular case, we'll sometimes with Epsilon Probability, which is usually, let's say 0.1, we'll take a random action. So either up, either down or no up with equal probability or with 0.9 probability, we'll be following this Greedy Policy where we're actually taking the action that has the highest action value associated with it. So that's the rough sketch of how this looks like and this is just going to run in cycles, blah, blah, blah, until we receive the dawn flag from the emulator and once the dawn flag is over, that's it, we stop the game. And one important thing to note here is that during this game, we have something called a memory replay, experience replay buffer. And it's nothing else but collection of the experiences we collected during the gameplay. So what happens is the following. So we have, let me call this state S, let me call the reward R, let me call the new state. So after we receive this frame and we update the old state, we'll have S prime and let me call the action that we send to the emulator A. So we'll be collecting these tuples, S, A, R, S, SARS. Okay, we'll just be plugging these in into this replay buffer as we're playing. So we have a state, we send some action, depending on that state, we received some reward, we received a frame, we updated our state, we got S prime, and we just kind of store this in this replay buffer and this one is huge, like they use one million frames, one million slots here, so just keep that in mind. Once we have this, we'll be later using these tuples to actually train the agent. So, so far you just saw how the agent is actually acting in the environment once it's fully trained. Now we can use these SARS tuples to actually train it. And I was just gonna give you like a really high level overview and then we'll jump into the details. So what we actually do is the following. So we have a state S and we perform some action, we got into state S prime and we received some reward for doing this and this is a tuple from our experience replay buffer, okay? So what happens the following? So the Q network here, the CNM, will basically have some output for this state. So we pass in the S and it will give us some Q of S, so some value for this particular action. Maybe this is the action like whatever, we were using up. So we get some value, maybe eight. And that was received some reward here and we get some new value here, Q S prime. And the important thing to note is, this is an important detail, is this Q network here is gonna be some old frozen Q network from some previous iteration and that's gonna be used here and not the current network. Once we have the Q S prime and R, we're gonna try and do a simple L2 loss minimization. IE, so we're gonna try to do, we're gonna try and make QS as close as possible to the reward we got plus this Q in this new state S prime. So that's the whole goal of this training. We're gonna take mini batches of these SAR stouples, they were using 32 of these stouples and we're just gonna do a simple graded descent and do L2 minimization, that's it. So basically, MSC loss on these fake labeled data, the stouples we were collecting. So having said that, now let's jump into all of the details and see how this actually, actually works. Okay, let's go step by step. First things first. So usually, deep learning applications, they require a large amount of hand labeled training data. If you're familiar with computer vision, with NLP, with graph, ML, with whatever other subfield of machine learning or deep learning, you know that we need a lot of hand labeled data. On the other hand, ARIA algorithms have, they have to learn from a scalar reward as we saw, like the score may be in Pong that's one or zero, maybe in breakout game, it could be, or in Space Invaders for every single, like spaceship you kill, maybe get three points, whatever. So it's a scalar reward and it's sparse. You only get it at the end of the episode, potentially. It's noisy and it's delayed, obviously, because it's sparse. I guess these two are kind of correlated. Okay, that's the first thing. Another issue is that most algorithms assume that the data is independent. You'll see the IID thing thrown around every single, every now and then. So that basically means we have independent, identically distributed data points from our data set. But here in RL, you typically encounter a sequence of highly correlated states. So why is that? Well, it's pretty simple. When you have a Pong game and the ball is here, in the next frame, you can expect the ball to be anywhere. It won't be here or here. It's gonna be somewhere in this like circle. And that means the next state is highly correlated with the last one. And that's the problem in RL that we don't have in the computer vision. Usually we don't have it. So furthermore, the data distribution changes as the algorithm learns new behaviors, which can be problematic for deep learning methods that assume a fixed underlying distribution. So what it means when you're training your classifier on images in computer vision, you basically have a data set of images and they form some static distribution, which you're trying to figure out so that you can predict the class successfully. Here in RL, when you're learning new policy, you'll be, because of your new behavior, your new policy, as we call it in RL, you'll be visiting different states. And that means you'll be seeing different data every now and then. And that means that the distribution shifts and that's problematic. And the way they solve this in this DQM paper is by using this replay buffer because it's gonna have these source tuples from various, various policies, because in the meanwhile, we're gonna update the network and we're gonna be storing new tuples with the updated network. So we'll have data from different distributions stored in this replay buffer. And that's one of the ways they couple, they kind of fixed this thing, these instabilities caused by these assumptions being violated. Okay, let's continue. I already explained the games in Atari we have. Just for your kind of mental picture, the imagery is really small. It's 210 by 160 at 60 hertz. So that's definitely not your 4K video. So just keep that in mind. The problem was really small. Like otherwise, the problem of learning these agents would be really hard back then in 2013 when the paper was originally published. Okay, so important things to notice here is the following. So the network was not provided with any game specific information or hand designed visual features. So basically, you don't know the only thing you get for every single one of these games is the observation, I the frame, and you get the reward, the scalar, that's it. So nothing else, non game specific information. You don't get the hand designed visual features, you're using CNN to learn the future representations. So no hand designing, no hand crafting here. And we don't have the internal state of the emulator. So that means we're dealing with a partially observed MDP. So that may be a mouthful. So basically MDP is this formalism in RL, which I won't get too deep into now. So just a mark of decision process. And basically it's partially observed because you don't know the state behind the emulator. You just get the frame. You don't know all of the processes that are happening to actually render and prepare that frame. So that means we're partially observing the system and that's one more difficulty that we have in Atari here. And it's a common thing in the real world applications, but yeah. Okay, so it learned nothing. It just learns from the video input, from the reward and that's it. And the only thing that's actually specific to every single of these games is the number of actions. That's it. So you have a CNN here, CNN agent. And because this is Pong, you'll have three outputs probably. So the no up, the down and the up action. In Break Board it's gonna be similar. Maybe in Space Invaders you can shoot aside from moving the paddle. So maybe have, I don't know, like four actions. So this is the only thing that's game specific. The number of actions. And that's kinda meaningful because even humans will have a different joystick so that makes sense. Okay, so that's the only thing that's kinda game specific. And the architecture, so the CNN and the hyperparams were actually kept constant for every single one of these Atari games. So that's a good step towards the artificial general intelligence. Although we are very far off because one thing you need to know here is that for every single one of these games, they had a specific network trained only for that game. So that means if you have seven games or 57 games, you'll have 57 differently trained CNNs. So you can train one CNN and then deploy it as an agent in all of these environments. You have to train a single CNN on a single game and use it only there. And fun thing about RL, like I just recently read this quote, like RL is the only field, the only subfield of deep learning where it's socially acceptable to train on your test data. And yeah, that's pretty much true because you're training on Pong and then you're actually deploying the agent in that very same environment. So just keep that in mind. Okay, that was the initial things I wanted to explain here. And now let's see, let's go further. Now we're gonna see some mathematical formalism of MDPs and stuff. So yeah, let's start. First things first, the task is partially observed and many other states are perceptually aliased as I already mentioned that the example with the Pong ball that can go in any direction. So it's impossible to fully understand the current situation from only the current frame. And that's the reason they're stacking four frames together. We need the temporal information in order to play the game. Okay, let's see the formalism. This is the quantity we wanna actually maximize. It's the future discounted because of this gamma factor reward. And gamma is just a mathematical formalism which makes you, when t goes to infinity, when the number of steps here goes to infinity, if we have gamma that's usually between, that's always between zero and one, and it's usually actually 0.99, when you have that, this array is gonna converge to a finite number and that's desirable when you're dealing, you don't wanna deal with infinities, right? But usually you deal with finite episodes so this gamma doesn't matter so much. You can sometimes even set it to one and nothing will break. That's the first quantity. The second one is the action value function and aside from this one you'll be seeing something called state value function, but for now let's just focus on this one. And in optimal case you wanna find the policy P, this is what this equation is telling us. So we wanna find the policy P that will maximize this expression here. And this is just the reward, the expected reward from this particular state and taking this particular action. So that's what the Q value is telling you. It's telling you the following. If I'm in this state and I perform this specific action, what's the expected reward I'll get? I can expect from this action in this state. And once you get to the actual action value, it's gonna be something called Bellman equation. And you're gonna see this a lot, especially in the older RL algorithms where they used to use table lookups instead of neural networks. So basically this is what the Bellman equation looks like. For the specific case of using something called TD or temporal difference learning. And basically the Q will be equal, the optimal value, the Q star will be equal to R, the reward, plus gamma, discounted, maximum Q star across all the actions in the future state S prime. So this is just something to wrap your head around. If you've never seen this before, it's gonna be kind of look really strange, but it's actually much easier when you see the implementation because this tells us the following thing. We take the CNN and we input the current state S. And basically then we take another CNN and we put the state S prime. And now we're gonna find the max, whatever the max here is, we're gonna sum it up with R and once we have the true action value function, which we're trying to approximate during this training, it's gonna satisfy this equation. That's what it says. And don't get scared because of the expectation operator. It just tells us that we are basically sampling this next state from the distribution that the emulator is providing us. That's this epsilon here. But for the old purposes, you can just ignore it because this is how it's actually gonna work when you try and code it up. You're just gonna do this and then an expectation because you're sampling different states as you're playing the game, this thing is gonna be solved for itself. So there is this discrepancy between equations and how it actually works. The second discrepancy you could maybe notice here is that Q is fed with S and A, but actually as we saw, CNN is only taking S and it's outputting the actions. So that's just the legacy formalism that most of these papers have. And once you actually see the code, believe me, it's much easier. I mean, it's not easier. It's just the discrepancies what makes me kinda have this dissonance in my brain. So I guess most of you already experienced it. Okay, so now the theory goes like this. So this is what the optimal, the true Q value function will look like. It's gonna obey this Bellman equation. But initially our neural network is random. So it's not gonna obey this. And in order to actually converge to this true Q value function, we're gonna do something called value iteration. And they converge to the optimal action value function. So basically by just doing this thing here, by just iterating, and we'll see the exact algorithm a bit later, but just stick with me for now. So by just doing this, we're gonna slowly get to the true value. And after we update the Q value, because our policy is coupled, if you remember, with this Q value by the Epsilon greedy algorithm, we're gonna improve the policy automatically. And that there is this theory from RL that says, if you do that, if you're improving Q, and if you're improving your policy, which we're automatically doing here because we're coupled by Epsilon greedy, we're gonna converge to the actual optimal Q value, the Q star action value function. So yeah. And all of this theory actually was first invented, let's call it invented for the table lookup example, where you had something like this. So you basically had a matrix, and along this dimension you'd have states S, and along this one you'd have actions. And now you can see why this is totally impractical. S is gonna explode in any serious real world problem, as well as actions that can be continuous in some cases, when in robotics, for example. So there's gonna be huge and impractical. And the second thing, aside from memory problems, we have something even more serious, and that's once you figure out the value for this state action point, how are you going to generalize to every single other point in this state action space? You won't, unless you do some interpolation, but that's again computationally expensive because you have to interpolate. Because of that, the neural networks are really cool because they can just automatically, by just updating the parameters, you get the close, you also update the states around this state for free, let's call it like that. So that's something I wanted to mention there. And now this is the thing I initially explained, how we actually train this network. So we have the targets, and we're just trying to minimize the L2 loss. So you see here, we just have the difference and then squared, we're just trying to minimize the L2 loss between the target and between the queue. And the target is, as I mentioned, the frozen network, so this theta, I minus one, let me zoom in a little bit. So we're gonna freeze in some point the parameters, and we're not gonna change it, and we're going to use that network for the target network. So how it goes is the following. We have the SARS top, remember? So we have the SARS. So what we're going to do is we have the queue network, that's our current CNN, okay? We input S here, we know what the action is, so we'll focus on that queue value, and that's this queue, okay? So how do we get a target? Well, we take that frozen CNN, some old CNN, old like this, we input the S prime, so from the tuple again, we have that information, we input the S prime, and now we're gonna actually maximize, find the biggest value here, and we're gonna add the R, which we also have from the tuple, and that's gonna be our target. So that's gonna be Y of I, and once we have that value, we're just gonna try and tweak the parameters here, so as to approach that R plus Q, the new Q, the Q prime, let's call it, whatever. So that's the whole point, that's how it works. You're doing L2, you're doing the mean squared error when you have the mini-batch, and that's how you train the parameters. So now you may be puzzled with this replay buffer, you may be puzzled with this frozen network, some of those are actually just heuristics, and there is no theoretical guarantee that it's gonna converge, but it does in practice, and was inspired by the actual theory that came from these exact cases where we had the table lookups and not the function approximations. So yeah, hopefully that makes sense, and they say here the parameters from the previous iteration theta I minus one are held fixed when optimizing the loss function, blah blah. So we won't be back propagating through this one, so this is just, yeah, just the parameters are frozen. Okay, I think I've covered everything here. They just explicitly derived the gradient for the loss, this is something that your favorite deep learning framework of choice does for you, so we don't have to cover this one. So either PyTorch or TensorFlow will just, once you specify the loss like this, so the simple L2, the framework will find the gradients automatically using the autodef engine, okay? So let's see these two things. First, this Q learning algorithm is model-free. That means we're not trying to explicitly model the transition from S to S prime, from this state to the next state. We don't know the probability of transiting into the next state, we don't care about it, we're just doing model-free RL, interacting with the environment and learning the action value functions directly without caring about the actual probabilities and modeling these. So that's why this thing is model-free. Why is it off-policy? Well, it's off-policy because it's using the epsilon greedy to collect the data into the replay buffer, if you remember. So we are collecting into the replay buffer using the epsilon greedy, and then the target is actually using the max policy, the greedy policy, and that's another policy. And so we're trying to learn the max Q value while using the behavior policy, that's how they call it, the epsilon greedy and the target policy is the greedy policy. That's why it's off-policy. So intuitively, what we're trying to do here is we wanna have this Q, our CNN here, be able to predict what will be the expected reward plus the whatever max here is. So we're gonna try and learn what this particular state, what's the max value we can expect. So hopefully I didn't confuse you here. Let me know in the comments if this was clear enough, I can try and explain a bit better next time, whatever. Okay, let's continue and see what else is there. So furthermore, it was shown that combining model-free reinforcement learning such as Q learning with nonlinear function approximators and using off-policy learning could cause the Q network to diverge. So that's the theory. And that's pretty problematic because you wanna have stable training. And fortunately, DQM paper, they didn't have the problem because of the memory replay buffer and because of the target network being frozen, actually, they avoided the instabilities. But this problem is something known as the deadly triad in the literature. So this is just an excerpt from the Rich Sutton's book and an introduction to RL, which is like a must read if you're doing RL really seriously. At one point of time, you should probably check it out. I still haven't. I usually start by doing high level resources first and then slowly going down to papers and only later do I read the book. So that's maybe counterintuitive, but that's the best approach for me. And he said also here, so when you combine the function approximation, the bootstrapping, so bootstrapping being TD, and other than TD, you could be using something called MC, like Monte Carlo, or you could be using something in between, like TD lambda, and you don't have to know what all of these are. But it's basically, instead of doing just R plus the Q value here and your bootstrapping that way, you just roll out until the end of the episodes and just use the actual rewards instead of trying to use the Q value to bootstrap and figure out the actual Q value now. So that's the bootstrapping part. And finally, the off policy, and that's why it's called a triad, tri for three. So basically, when you have these three elements combined together, you're roughly, you're probably going to have instability problems, but yeah, as DQN folks showed, they didn't have it because of some of the hacks, hacks they used, the replay buffer and the target network are the main two components that made it work. Okay, that's that part, let's go further. And let's actually see the algorithm, and I'll try to walk you through this one. So first, we initialize the memory, the replay buffer to capacity N. And they had 1 million slots here, just for being less abstract. They initialized the action value function Q with random weights. So just take your CNN and use whatever your favorite in it method is, maybe Gloroth or Xavier, whatever your initialization method is. And then we do the following, we trade over the episode, we have M episodes, we initialize the sequence, we take the initial frame from the Atari environment, we just do some pre-processing, so that's the four frames, the cropping, some details you'll see in a bit. And then for every single step in that particular episode, we do the following, we perform an action using epsilon greedy policy, so that's this. We probability epsilon, we select a random action, otherwise we select the max, we max it out, we do the greedy approach. Then we send the action to the environment. So that's if you're using, you're usually gonna be using something like OpenAI's gym, so that's gonna be roughly correspond to dot step, and you're gonna pass the action, and then the environment's gonna return the observation, the reward, and the dom flag, which signals whether the episode is over or not. Once we have that, we just pre-process that frame, and we store the transition, the star stopple, where they're using this five to denote the processed state. So this is basically the state. So we just store the star stopple inside of the replay buffer, and then we're gonna sample random mini-batch from D. Now, just for your understanding, they're going to do this, I think the actual number was four. So every four actions, you perform four actions, and only then do you sample the mini-batch. Because otherwise, you need to fill in, remember, this pre-processing function expects four frames, so we have to kind of fill it up before we start doing the inference with the Q network. So that's why they're gonna do, I think that's the reason they're going to do it every four steps. And again, you can see we just formed the target, and that's either reward if you're in the terminal state, if you're at the last frame of the game, otherwise we're gonna bootstrap using Q, the old Q function, and that's the target, and then we're going to do gradient descent on the L2 of these two. And that's it. So I think the mini-batch size was 32. That means we'll take 32 samples randomly from this buffer, so just 32 random source tuples, and we're gonna form this, and we're just gonna average it out and let the deep learning framework do the rest for us, find the gradient automatically, and minimize this loss. And that's the whole algorithm. Hopefully now it's a bit more clear. And I think I mentioned this, but let me just reiterate. So learning directly from consecutive samples is inefficient due to strong correlations. So I mentioned the example with the ball in Pong and being correlated with the next frame. So randomizing the samples by taking random samples from the replay buffer, we are breaking these correlations, and we are reducing the variance of the updates. So that's the important trick to make this thing stable and to make it work. I just took a snippet from the, so this paper is from 2013, and later they published a paper in Nature, and so I just took a snippet from that paper, and they have additional line here, so every C steps just swap the target, that's the frozen Q network I was talking about. So you just take the current network, and every C steps, which is maybe every, I don't know, 1,000, I think they use 1K batch updates, you just swap the networks and use that one as the frozen network to predict your target labels. And that's the additional detail I wanted to mention. Okay, with that out of the way, let's continue and dive into a bit more details about the pre-processing. So what they do is they convert the RGB to grayscale, they down sample it to this resolution, and then they crop to 84 by 84 because that was a constraint from the network they were using, and they were using, if you take a look at this reference 11, that's actually AlexNet, the famous network that caused the ImageNet moment, and it had the constraint of using only square inputs, that's why they crop to a square resolution. The second thing they do is, as I already mentioned, is they take the last four frames of history and they stack them together to produce the input to the Q function, and that was the state that we were using all along. Okay, so those were some additional details, and now one more thing, I kind of highlighted this eight by eight because AlexNet, back in the days, they were using much wider kernels compared to, and shallower networks compared to today's networks, which have kernels that are usually three by three, and they are much deeper, especially with the arrival of ResNet that allowed us to, using those skip connections to have much deeper networks going to 150 and more layers, and yeah, that's just kind of thought, it's interesting. One thing they mentioned here additionally is, so the main advantage of this type of architecture is to compute the QVLs for all possible actions in a given state with only a single forward pass. So imagine if we were actually treating the formulas like exactly, so you'd have to do the following thing, you'd have a CNN, you'd input a state, and you'd input an action, and then you'd get a QVL for that action, but then you'd have to do a for loop, you just had to kind of iterate this in a for loop to get all the QVLs, and you'd be storing them somewhere in summary, and so you'd be using additional time, you'd be using additional compute, and you'd be using additional memory if they haven't made it the way they had, and that's just input a single state, and you get all of the actions, you get the QVLs for all of the actions, and that's how it works. So that's additional engineering detail, that's kind of fun. Let's jump to experiments finally. Let's see how this thing performed. I already mentioned it kind of surpassed the humans in some games and many previous methods, so let's see details about that. Additionally, because some games like Breakout or Space Invader, maybe when you kill a spaceship in Space Invader, you'd get plus reward, where in Pong you get plus one, so because these scales differ between the games, what it did, and this is again something that's Atari specific, so they are not completely agnostic to the setup, they are actually clipping it to plus one or minus one, if we get minus seven reward, that would get clipped to minus one, if we get plus three, that would get clipped to plus one, and that's additional trick they used to make it more stable and to be able to use the same set of hyperparams like the learning rate for every single one of these games, Atari games. Again, one more detail, the epsilon was actually, the epsilon really, the epsilon was annealed linearly from one to zero one over the first million frames and fixed to 0.1 afterwards, so what that means, that means the following, so we have epsilon, we have the steps in our RL environment, and basically it starts with one and linearly annealed to zero one, and this is one million frames here, and that means we start off being completely random, our policy is completely random, so we'll be picking whatever state comes into the Q network, we pick the action without caring which is the max one, we just take one action, and that's how we behave, that's how we explore the environment initially, and that's an important concept in RL exploration versus exploitation trade-off, and here you can see usually the RL algorithm start exploring maximally to let it explore the environment and learn which states are better by random, and then start kind of being more greedy, being more deterministic about your actions and less sarcastic, and that's, you'll usually see policies like the schedules like this one, and then we'll end up having 0.1 epsilon throughout the rest of the training, that's what I did. They also additionally use this frame skipping technique which means that, just a simple, again Atari specific thing, they just pick an action for, and then they just repeat the action for the next three steps, they're just sending the same action to the emulator, and only after the fourth frame do they actually pick the new action, here they say that they use K4, so they actually pick the action every four frames that comes from the emulator, except for the Space Invaders where they actually notice that the lasers are invisible if they take that period, so they actually had to use three, which is again, I think this is the only game specific detail they actually use, so just, yeah, it's a fun fact. Here I'm not sure whether once they are doing those dummy actions where they're just repeating the last intelligent action, where they're actually feeding those frames into the state, into the circular buffer that has four slots, so I'm not sure if they're using these frames to fill that up, or they're only using the frames that got received from the environment when they produce an intelligent action. So that's just something I'm confused about, maybe if you know, write it down in the comments, I haven't checked the original implementation, I did check some other GISTs and implementations of DQN, so I'm familiar how it works. There is one thing I wanna mention here, and this nicely summarizes the difference between research and engineering, and that's that for this particular Atari game, they noticed this thing, so first encode a single frame, we take the maximum value for each pixel color value of the frame being encoded and the previous frame. This was necessary to remove flickering that is present in games where some objects appear only in even frames, while other objects appear only in odd frames. An artifact caused by the limited number of sprites in Atari 2600 that can display at once. So this is totally not important for this research paper and for you understanding this paper, but it is important to understand that there are so many details that you actually understand when you start implementing the thing. So reading research is really nice and everything, but until you start looking at the actual code and try to implement it, you probably first don't understand the actual theory, and secondly, you don't understand all of the pain points to actually make this work in a real world product. So just something I want to mention. And also, what I found useful is, for example, when I read this DQM paper the first time, I just found some gists and I went through the code and that made it much less abstract and clear how it works. So I kinda suggest that you, aside from reading papers, maybe consult some code, and that's a good nice trade-off to understand the research better. And that's somewhere like half the way between you actually implementing the project and you not seeing any code whatsoever. So yeah, that was a small digression. Hopefully it was useful for some of you. Let me know if this was useful in the comments, things like this or whether this just distracts you. Okay, let's continue. Let us see how the agent progresses during the training. Basically, here you can see that the rewards, so here we can see the training epochs, so and here we can see the average reward that the agent is receiving, and we can see on the breakout game an upward trend, so that means that the agent is learning better policies and better action values or Q values. So basically, on the Sequest, we can see the same trend. There is a lot of noise, but still the trend is kind of upward, so yeah. A better metric they used is this, the average Q on breakout and the average Q on whatever game there may be. And you can see that that one is pretty much monotonically increasing and has less noise than these ones here. And let me just explain to you how they actually calculate that one. So we collect a fixed set of states by running a random policy before training even starts, and they track the average of the maximum predicted Q values for these states. So that looks the following. Basically, before the training even starts, before the agent starts learning, they do the following. So we can represent the environment and the game as an MDP, and I didn't explain quite what MDP is, but for now, you can imagine it as a bunch of states and you can transition and you can receive rewards, and yeah, that's the formalism. But basically what they did is they took a couple of states, and those are those four frame tuples, remember? So they took a couple of these, and they just stored them into some memory, and basically later on, while the agent is actually learning, they just pass these specific values. So let's call this one, let's call this two. They'll just feed it through the CNN, and they'll find the max Q value for this state, max Q value for this state, and they're just gonna be accumulating these, like summing them up and then averaging by the number of states, i.e. they are gonna keep the average of the max Q values for these states. And that's the metric they were using here, and it proved to be much more stable and better to keep track of the learning progress of the agent. Okay, those are the curves. Here, once you actually train the agent, you can see interesting behavior, and here you can see the following. So here you can see that that's our ship that we're controlling, that's the agent. The algorithm is controlling the ship, and once the enemy ship enters the screen, that's the point A, and you can see that the Q value increases, because we're expecting reward once we kill the enemy spaceship, we're gonna see an increase in score, and the Q value correctly anticipates that score increase, and then has a spike. And then you can see once the torpedo is shot, and we are really close to killing the enemy ship, we're at point B, where we expect a huge reward, and once we actually kill the ship and we enter in this state here, the value drops, and it drops because it only expects the future rewards. So we just received a huge reward, and that's why we dipped. So you can see that it's really meaningful for this specific scenario, and it makes a lot of sense. That was another interesting thing that I wanted to mention, and here is one additional detail. So in addition to seeing relatively smooth improvements to predicted Q during training, we did not experience any divergence issues in any of the experiments, so despite lacking any theoretical convergence guarantees, the method is able to train the network with RL algorithm signal, and gradient descent in a stable manner. So again, small discrepancy between the theory and the engineering or the practice. Sometimes things just work, and later a couple of years down the road, somebody figures out why this was working, or yeah, but yeah, sometimes, a lot of times, the engineering and the technology is way in front of the actual research and theoretical understanding. That's my honest opinion about this. You can disagree, and I'd love to hear your comments on that. Yeah. So results are here. DQN kinda destroyed every single other baseline. So this is the random policy. If you just play it random, if you play the game at random, these are the scores you get. SARSA, it's an online algorithm similar to Q-learning. I won't get into the details. Contingency, again, very similar, and you can see usually Q-learning has better results, and DQN has much better results, and all of those baselines, and it's actually even better than humans in some games, like here on Breakout, Enduro, and Pong. It's actually better than the human, and that's kinda interesting, and the scores here, how they got these are, so they just took some human, and that guy, that poor guy or girl, they were just playing the game for two hours, and once the two hours are done, they just take the scores that they achieved, they sort them, and they find the middle one, that's the median or the 50th percentile, and that's the score they publish here, and you can see that, yeah, in some cases, DQN achieved better results. So one important thing to mention here is that in their subsequent paper that were published in Nature in 2015, they actually played on all the 57 Atari games, and they achieved impressive results where they were actually better than humans on 29 out of 57 games, and that's, yeah, quite impressive, especially back in 2015. Now we have some improvements like Agent 57, and some other algorithms, and I'll be covering those in the subsequent videos, so yeah, stay tuned, but the interesting thing you can notice here is that all of the games that require fast reflexes, like boxing, like Pong, are much easier for our agents to learn how to play than some games like Montezuma's Revenge, it's a really famous game. It's a tough one, you need to play it to understand why I'm saying this. It requires a lot more strategy than Pong or Breakout or those other games, and that's why you can see we have actually zero score here, so the algorithm cannot, DQN cannot learn in this vanilla form, cannot learn to play this game at all. So that was just some fun fact, and as I mentioned, so this Qbert, Sequest, and Space Invaders, so those are these three games, you can see that results are really poor compared to humans, and the reason is that they're challenging because they require us to find a strategy that extends over long time scales, and that's something that if you're familiar with any other field like NLP, when you're dealing with long sequences, you're gonna end up having problems, catastrophic forgetting whatever, the problems that RNN's had, and then LSTM's kind of solved, and Transformers, so yeah, that's the reason they, you can basically just by analyzing the game kind of get an intuition why the algorithm is failing on specific games. And that's pretty much it, these are just some references, I think I've covered it pretty detailed. Hopefully if you stuck with me until the end of the video, I'd love to hear your thoughts, did you like this one better than the last ones, and if you have any tips on how to improve this further, feel free to comment down below, I'll try to answer ASAP, so until next time, you know the drill, hit that bell icon, subscribe, and share the good word, and see you in the next video, until then, keep learning deep. Yeah.
[{"start": 0.88, "end": 1.72, "text": " What's up folks?"}, {"start": 1.72, "end": 3.7800000000000002, "text": " In this video I'm going to cover the paper"}, {"start": 3.7800000000000002, "end": 5.44, "text": " that caused the ImageNet moment"}, {"start": 5.44, "end": 7.32, "text": " for the reinforcement learning field,"}, {"start": 7.32, "end": 10.74, "text": " the DQN paper, also known as the Playing Atari"}, {"start": 10.74, "end": 14.32, "text": " with Deep Reinforcement Learning paper by Volodymyr Mni"}, {"start": 14.32, "end": 16.8, "text": " and his collaborator at DeepMind."}, {"start": 16.8, "end": 19.48, "text": " And I hopefully pronounce his name right."}, {"start": 19.48, "end": 21.88, "text": " So let's dig into it."}, {"start": 21.88, "end": 23.6, "text": " We present the first deep learning model"}, {"start": 23.6, "end": 26.3, "text": " to successfully learn control policies"}, {"start": 26.3, "end": 29.060000000000002, "text": " directly from high dimensional sensory input,"}, {"start": 29.06, "end": 32.36, "text": " IE images in this case, using RL."}, {"start": 32.36, "end": 35.32, "text": " The model is a CNN trained with a variant of Q-learning"}, {"start": 35.32, "end": 37.44, "text": " and we'll see what it is in a moment,"}, {"start": 37.44, "end": 39.96, "text": " whose input is raw pixels and the output"}, {"start": 39.96, "end": 42.4, "text": " is a value function, actually the action value function"}, {"start": 42.4, "end": 46.28, "text": " or the Q function estimating the future rewards."}, {"start": 46.28, "end": 49.7, "text": " We apply our method to seven Atari games"}, {"start": 49.7, "end": 52.44, "text": " and they don't adjust the architecture"}, {"start": 52.44, "end": 55.36, "text": " or the learning algorithm which makes this algorithm"}, {"start": 55.36, "end": 57.7, "text": " much more general than all of the previous ones."}, {"start": 57.7, "end": 60.120000000000005, "text": " We find that it outperforms all previous approaches"}, {"start": 60.120000000000005, "end": 63.68000000000001, "text": " on six of the games and even surpasses a human expert"}, {"start": 63.68000000000001, "end": 65.0, "text": " on three of them."}, {"start": 65.0, "end": 67.68, "text": " So before I start digging into the paper,"}, {"start": 67.68, "end": 69.56, "text": " I'll just give you a rough sketch"}, {"start": 69.56, "end": 72.64, "text": " so that you have a high level understanding"}, {"start": 72.64, "end": 74.92, "text": " of all of the components and then we'll start"}, {"start": 74.92, "end": 76.96000000000001, "text": " going into a lot of details as I usually do"}, {"start": 76.96000000000001, "end": 78.44, "text": " in my paper overviews."}, {"start": 78.44, "end": 80.2, "text": " So okay, let's start."}, {"start": 80.2, "end": 84.28, "text": " So the first thing is first, the most general framework"}, {"start": 84.28, "end": 87.02000000000001, "text": " of how RL problem is constructed is the following."}, {"start": 87.02, "end": 90.84, "text": " So we have an agent and you'll see this all over the place"}, {"start": 90.84, "end": 94.92, "text": " and we have environment and basically the agent"}, {"start": 94.92, "end": 97.8, "text": " sends some action to the environment"}, {"start": 97.8, "end": 101.56, "text": " and the environment gives it back some observation,"}, {"start": 101.56, "end": 105.03999999999999, "text": " let's call it O and also some reward."}, {"start": 105.03999999999999, "end": 108.88, "text": " And now the whole goal of this agent in this environment"}, {"start": 108.88, "end": 112.8, "text": " is to maximize the future expected reward"}, {"start": 112.8, "end": 114.39999999999999, "text": " and that's pretty much it."}, {"start": 114.4, "end": 118.68, "text": " Now this can mean like every single thing you can imagine"}, {"start": 118.68, "end": 121.80000000000001, "text": " can be constructed like this pretty much,"}, {"start": 121.80000000000001, "end": 123.60000000000001, "text": " many things, maybe not everything."}, {"start": 123.60000000000001, "end": 126.56, "text": " So let me just concretize this for the specific problem"}, {"start": 126.56, "end": 129.64000000000001, "text": " we are coping with in this paper and that's Atari."}, {"start": 129.64000000000001, "end": 132.20000000000002, "text": " So in our case, what will happen is the following."}, {"start": 132.20000000000002, "end": 135.28, "text": " So agent is actually a CNN."}, {"start": 136.12, "end": 139.12, "text": " So we have a deep convolutional neural network,"}, {"start": 139.12, "end": 141.04000000000002, "text": " not so deep, you'll see soon it was actually"}, {"start": 141.04000000000002, "end": 143.04000000000002, "text": " only two convoliers."}, {"start": 143.04, "end": 145.88, "text": " And so what we do is the following."}, {"start": 145.88, "end": 149.32, "text": " So we interact with the environment in the following way."}, {"start": 149.32, "end": 152.04, "text": " So the environment is the Atari emulator."}, {"start": 152.04, "end": 154.95999999999998, "text": " So let's just draw it like some screen."}, {"start": 154.95999999999998, "end": 158.07999999999998, "text": " And what we do is we in the case,"}, {"start": 158.07999999999998, "end": 162.45999999999998, "text": " so just a small digression here are the games in Atari."}, {"start": 162.45999999999998, "end": 165.26, "text": " So basically here are five examples, we have Pong,"}, {"start": 165.26, "end": 167.88, "text": " we have something called Breakout, Space Invaders,"}, {"start": 167.88, "end": 169.88, "text": " SeaQuest and Beam Rider."}, {"start": 169.88, "end": 174.04, "text": " And hopefully you're at least familiar with some of these,"}, {"start": 174.04, "end": 176.1, "text": " maybe Pong is the easiest example."}, {"start": 176.1, "end": 179.12, "text": " So you basically have two pedals and you have a ball here"}, {"start": 179.12, "end": 181.85999999999999, "text": " and you're trying to not to miss the ball,"}, {"start": 181.85999999999999, "end": 185.4, "text": " you're trying to beat the opponent by just shooting"}, {"start": 185.4, "end": 187.4, "text": " the balls past through the opponent."}, {"start": 187.4, "end": 190.84, "text": " And once you do that, you receive the reward one."}, {"start": 190.84, "end": 194.34, "text": " If the opponent wins, he gets the reward of one"}, {"start": 194.34, "end": 195.84, "text": " and you get just zero."}, {"start": 195.84, "end": 198.72, "text": " So as you can see, the problem is that the reward"}, {"start": 198.72, "end": 201.48, "text": " is very sparse, you have to play for some time"}, {"start": 201.48, "end": 203.62, "text": " in order to get one and that's it."}, {"start": 203.62, "end": 205.72, "text": " We don't have as in supervised learning"}, {"start": 205.72, "end": 208.76, "text": " in every single step, maybe when you're doing"}, {"start": 208.76, "end": 210.44, "text": " image classification for every single image,"}, {"start": 210.44, "end": 212.32, "text": " you have a label and that's how you train."}, {"start": 212.32, "end": 214.8, "text": " So here the reward is sparse, it's delayed"}, {"start": 214.8, "end": 217.07999999999998, "text": " and you're not sure whether the award will come at all"}, {"start": 217.07999999999998, "end": 218.92, "text": " if you're having, if you have in the beginning,"}, {"start": 218.92, "end": 221.04, "text": " especially when you have a random policy,"}, {"start": 221.04, "end": 224.57999999999998, "text": " you'll be getting zero rewards for a long, long time."}, {"start": 224.57999999999998, "end": 227.2, "text": " So having that context in mind,"}, {"start": 227.2, "end": 229.16, "text": " so this is the image we get in Pong,"}, {"start": 229.16, "end": 231.72, "text": " this is the reward, zeros or ones in Pong."}, {"start": 231.72, "end": 234.79999999999998, "text": " Let me get back to the thing I was trying to explain."}, {"start": 234.79999999999998, "end": 236.44, "text": " Whoop, if I can find it, okay."}, {"start": 237.92, "end": 240.2, "text": " Okay, so basically what happens is the following."}, {"start": 240.2, "end": 242.44, "text": " In the Pong game, we'll have three actions."}, {"start": 242.44, "end": 247.44, "text": " We'll have up, we'll have no up, basically just don't move"}, {"start": 248.2, "end": 251.1, "text": " and we have the down action, okay?"}, {"start": 251.1, "end": 252.92, "text": " Just three simple actions."}, {"start": 252.92, "end": 255.48, "text": " And the state will be the following thing."}, {"start": 255.48, "end": 257.59999999999997, "text": " The state will be not the single image"}, {"start": 257.59999999999997, "end": 260.8, "text": " because unfortunately the single image is ambiguous"}, {"start": 260.8, "end": 263.3, "text": " because for example, if you have an image"}, {"start": 263.3, "end": 264.8, "text": " and you have a ball here, you don't know"}, {"start": 264.8, "end": 267.15999999999997, "text": " whether the ball is going to go in this direction,"}, {"start": 267.15999999999997, "end": 268.92, "text": " whether it's going to go in this direction,"}, {"start": 268.92, "end": 271.08, "text": " maybe even in the opposite direction here."}, {"start": 271.08, "end": 273.15999999999997, "text": " So you need to have at least two frames"}, {"start": 273.15999999999997, "end": 275.28, "text": " to have the temporal information"}, {"start": 275.28, "end": 276.82, "text": " so that you can solve this task."}, {"start": 276.82, "end": 278.8, "text": " So because of that, what they actually did"}, {"start": 278.8, "end": 280.12, "text": " is they represented the state"}, {"start": 280.12, "end": 282.36, "text": " after doing some pre-processing on images."}, {"start": 282.36, "end": 285.92, "text": " We'll see that later, they just lump four frames together."}, {"start": 285.92, "end": 290.92, "text": " So like this, one, two, three, four, whatever."}, {"start": 291.04, "end": 293.56, "text": " And that's a state, this is a state."}, {"start": 293.56, "end": 296.76, "text": " And this state goes into the CNN and that's our agent"}, {"start": 296.76, "end": 298.56, "text": " and it outputs the actions."}, {"start": 298.56, "end": 300.84000000000003, "text": " So once we put the state into the CNN,"}, {"start": 300.84000000000003, "end": 304.64, "text": " we get some numbers here and these are the action values."}, {"start": 304.64, "end": 307.04, "text": " And basically maybe if the up value was eight"}, {"start": 307.04, "end": 309.88, "text": " and this one was two and this one was maybe minus one,"}, {"start": 309.88, "end": 312.68, "text": " with the best thing to do would be to pick eight"}, {"start": 312.68, "end": 314.92, "text": " because that promises the biggest expected reward"}, {"start": 314.92, "end": 318.0, "text": " in the future if we're following the greedy policy."}, {"start": 318.0, "end": 319.84, "text": " And so we pick eight and that's up,"}, {"start": 319.84, "end": 321.65999999999997, "text": " we send that to the emulator."}, {"start": 321.65999999999997, "end": 323.15999999999997, "text": " The emulator does its thing,"}, {"start": 323.15999999999997, "end": 326.52, "text": " it just renders new screen and sends it back."}, {"start": 326.52, "end": 330.74, "text": " So it sends us back the new frame and some reward"}, {"start": 330.74, "end": 332.94, "text": " or maybe zero reward if nothing happens,"}, {"start": 332.94, "end": 334.84, "text": " if the game still hasn't finished."}, {"start": 334.84, "end": 336.12, "text": " And what we do is the following."}, {"start": 336.12, "end": 338.36, "text": " So we treat this as a circular buffer."}, {"start": 338.36, "end": 342.52000000000004, "text": " So basically what we do is we just take the last frame"}, {"start": 342.52000000000004, "end": 345.32, "text": " in this state, we just get rid of it"}, {"start": 345.32, "end": 350.0, "text": " and we append to the front of this queue,"}, {"start": 350.0, "end": 351.8, "text": " the newest frame and that's our new state."}, {"start": 351.8, "end": 353.56, "text": " So once the model is trained"}, {"start": 353.56, "end": 356.04, "text": " and I'll skip the training part for a second,"}, {"start": 356.04, "end": 358.24, "text": " let's see what happens once the model is fully trained."}, {"start": 358.24, "end": 360.52000000000004, "text": " So the following thing happens."}, {"start": 360.52000000000004, "end": 364.6, "text": " We have a CNN, we get the first observation, the first frame"}, {"start": 364.6, "end": 367.40000000000003, "text": " and we start stacking the frames until we get four frames."}, {"start": 367.4, "end": 369.56, "text": " Once we have four frames, we have the full state,"}, {"start": 369.56, "end": 372.79999999999995, "text": " we do the forward prop, we get the actions,"}, {"start": 372.79999999999995, "end": 376.15999999999997, "text": " we send the action maybe up, we send it to the emulator,"}, {"start": 376.15999999999997, "end": 378.84, "text": " the emulator sends us back the reward and the observed state"}, {"start": 378.84, "end": 380.44, "text": " and we just do that in circle."}, {"start": 380.44, "end": 382.08, "text": " And we're actually following something called"}, {"start": 382.08, "end": 385.56, "text": " Epsilon Greedy Policy and we'll see what it is in a minute."}, {"start": 385.56, "end": 390.28, "text": " So Epsilon Greedy, which basically means the following."}, {"start": 390.28, "end": 394.03999999999996, "text": " So instead of just taking the max action every single time,"}, {"start": 394.03999999999996, "end": 395.91999999999996, "text": " so eight in this particular case,"}, {"start": 395.92, "end": 398.48, "text": " we'll sometimes with Epsilon Probability,"}, {"start": 398.48, "end": 400.96000000000004, "text": " which is usually, let's say 0.1,"}, {"start": 400.96000000000004, "end": 402.28000000000003, "text": " we'll take a random action."}, {"start": 402.28000000000003, "end": 406.84000000000003, "text": " So either up, either down or no up with equal probability"}, {"start": 407.8, "end": 410.84000000000003, "text": " or with 0.9 probability, we'll be following"}, {"start": 410.84000000000003, "end": 414.48, "text": " this Greedy Policy where we're actually taking the action"}, {"start": 414.48, "end": 418.0, "text": " that has the highest action value associated with it."}, {"start": 418.0, "end": 421.16, "text": " So that's the rough sketch of how this looks like"}, {"start": 421.16, "end": 425.36, "text": " and this is just going to run in cycles, blah, blah, blah,"}, {"start": 425.36, "end": 429.76, "text": " until we receive the dawn flag from the emulator"}, {"start": 429.76, "end": 433.04, "text": " and once the dawn flag is over, that's it, we stop the game."}, {"start": 433.04, "end": 437.0, "text": " And one important thing to note here is that during this game,"}, {"start": 437.0, "end": 440.16, "text": " we have something called a memory replay,"}, {"start": 440.16, "end": 441.84000000000003, "text": " experience replay buffer."}, {"start": 441.84000000000003, "end": 445.44, "text": " And it's nothing else but collection of the experiences"}, {"start": 445.44, "end": 448.76, "text": " we collected during the gameplay."}, {"start": 448.76, "end": 450.48, "text": " So what happens is the following."}, {"start": 450.48, "end": 454.72, "text": " So we have, let me call this state S,"}, {"start": 454.72, "end": 458.48, "text": " let me call the reward R, let me call the new state."}, {"start": 458.48, "end": 462.16, "text": " So after we receive this frame and we update the old state,"}, {"start": 462.16, "end": 465.96000000000004, "text": " we'll have S prime and let me call the action"}, {"start": 465.96000000000004, "end": 469.66, "text": " that we send to the emulator A."}, {"start": 469.66, "end": 474.66, "text": " So we'll be collecting these tuples, S, A, R, S, SARS."}, {"start": 479.56, "end": 482.40000000000003, "text": " Okay, we'll just be plugging these in"}, {"start": 482.40000000000003, "end": 484.68, "text": " into this replay buffer as we're playing."}, {"start": 484.68, "end": 486.88, "text": " So we have a state, we send some action,"}, {"start": 486.88, "end": 489.76, "text": " depending on that state, we received some reward,"}, {"start": 489.76, "end": 493.0, "text": " we received a frame, we updated our state, we got S prime,"}, {"start": 493.0, "end": 498.0, "text": " and we just kind of store this in this replay buffer"}, {"start": 498.0, "end": 501.8, "text": " and this one is huge, like they use one million frames,"}, {"start": 501.8, "end": 504.7, "text": " one million slots here, so just keep that in mind."}, {"start": 505.96000000000004, "end": 509.4, "text": " Once we have this, we'll be later using these tuples"}, {"start": 509.4, "end": 511.56, "text": " to actually train the agent."}, {"start": 511.56, "end": 513.52, "text": " So, so far you just saw how the agent"}, {"start": 513.52, "end": 515.3199999999999, "text": " is actually acting in the environment"}, {"start": 515.3199999999999, "end": 516.6999999999999, "text": " once it's fully trained."}, {"start": 516.6999999999999, "end": 519.98, "text": " Now we can use these SARS tuples to actually train it."}, {"start": 519.98, "end": 522.68, "text": " And I was just gonna give you like a really high level"}, {"start": 522.68, "end": 524.64, "text": " overview and then we'll jump into the details."}, {"start": 524.64, "end": 526.64, "text": " So what we actually do is the following."}, {"start": 526.64, "end": 531.5799999999999, "text": " So we have a state S and we perform some action,"}, {"start": 531.5799999999999, "end": 536.16, "text": " we got into state S prime and we received some reward"}, {"start": 536.16, "end": 538.52, "text": " for doing this and this is a tuple"}, {"start": 538.52, "end": 541.64, "text": " from our experience replay buffer, okay?"}, {"start": 541.64, "end": 542.84, "text": " So what happens the following?"}, {"start": 542.84, "end": 546.44, "text": " So the Q network here, the CNM,"}, {"start": 546.44, "end": 550.6800000000001, "text": " will basically have some output for this state."}, {"start": 550.6800000000001, "end": 555.1600000000001, "text": " So we pass in the S and it will give us some Q of S,"}, {"start": 555.1600000000001, "end": 557.62, "text": " so some value for this particular action."}, {"start": 557.62, "end": 562.22, "text": " Maybe this is the action like whatever, we were using up."}, {"start": 562.22, "end": 564.2800000000001, "text": " So we get some value, maybe eight."}, {"start": 564.2800000000001, "end": 566.6, "text": " And that was received some reward here"}, {"start": 566.6, "end": 571.6, "text": " and we get some new value here, Q S prime."}, {"start": 571.6, "end": 574.44, "text": " And the important thing to note is,"}, {"start": 574.44, "end": 577.96, "text": " this is an important detail, is this Q network here"}, {"start": 577.96, "end": 580.62, "text": " is gonna be some old frozen Q network"}, {"start": 580.62, "end": 584.28, "text": " from some previous iteration and that's gonna be used here"}, {"start": 584.28, "end": 586.28, "text": " and not the current network."}, {"start": 586.28, "end": 588.64, "text": " Once we have the Q S prime and R,"}, {"start": 588.64, "end": 593.16, "text": " we're gonna try and do a simple L2 loss minimization."}, {"start": 593.16, "end": 596.9200000000001, "text": " IE, so we're gonna try to do, we're gonna try and make QS"}, {"start": 596.92, "end": 601.92, "text": " as close as possible to the reward we got plus this Q"}, {"start": 603.4, "end": 605.4, "text": " in this new state S prime."}, {"start": 605.4, "end": 608.4, "text": " So that's the whole goal of this training."}, {"start": 608.4, "end": 611.7199999999999, "text": " We're gonna take mini batches of these SAR stouples,"}, {"start": 611.7199999999999, "end": 614.9599999999999, "text": " they were using 32 of these stouples"}, {"start": 614.9599999999999, "end": 618.56, "text": " and we're just gonna do a simple graded descent"}, {"start": 618.56, "end": 621.88, "text": " and do L2 minimization, that's it."}, {"start": 621.88, "end": 626.88, "text": " So basically, MSC loss on these fake labeled data,"}, {"start": 629.0, "end": 631.4, "text": " the stouples we were collecting."}, {"start": 631.4, "end": 634.6, "text": " So having said that, now let's jump into all of the details"}, {"start": 634.6, "end": 637.06, "text": " and see how this actually, actually works."}, {"start": 637.06, "end": 639.12, "text": " Okay, let's go step by step."}, {"start": 639.12, "end": 641.08, "text": " First things first."}, {"start": 641.08, "end": 644.16, "text": " So usually, deep learning applications,"}, {"start": 644.16, "end": 647.32, "text": " they require a large amount of hand labeled training data."}, {"start": 647.32, "end": 649.68, "text": " If you're familiar with computer vision, with NLP,"}, {"start": 649.68, "end": 653.4399999999999, "text": " with graph, ML, with whatever other subfield"}, {"start": 653.4399999999999, "end": 656.06, "text": " of machine learning or deep learning,"}, {"start": 656.06, "end": 658.64, "text": " you know that we need a lot of hand labeled data."}, {"start": 658.64, "end": 661.26, "text": " On the other hand, ARIA algorithms have,"}, {"start": 661.26, "end": 663.88, "text": " they have to learn from a scalar reward as we saw,"}, {"start": 663.88, "end": 667.14, "text": " like the score may be in Pong that's one or zero,"}, {"start": 667.14, "end": 669.8599999999999, "text": " maybe in breakout game, it could be,"}, {"start": 669.8599999999999, "end": 671.92, "text": " or in Space Invaders for every single,"}, {"start": 671.92, "end": 674.8399999999999, "text": " like spaceship you kill, maybe get three points, whatever."}, {"start": 674.8399999999999, "end": 678.24, "text": " So it's a scalar reward and it's sparse."}, {"start": 678.24, "end": 681.64, "text": " You only get it at the end of the episode, potentially."}, {"start": 681.64, "end": 685.26, "text": " It's noisy and it's delayed, obviously, because it's sparse."}, {"start": 685.26, "end": 688.2, "text": " I guess these two are kind of correlated."}, {"start": 688.2, "end": 689.92, "text": " Okay, that's the first thing."}, {"start": 689.92, "end": 692.6800000000001, "text": " Another issue is that most algorithms assume"}, {"start": 692.6800000000001, "end": 694.58, "text": " that the data is independent."}, {"start": 694.58, "end": 698.84, "text": " You'll see the IID thing thrown around every single,"}, {"start": 698.84, "end": 699.76, "text": " every now and then."}, {"start": 699.76, "end": 702.36, "text": " So that basically means we have independent,"}, {"start": 702.36, "end": 705.12, "text": " identically distributed data points from our data set."}, {"start": 705.12, "end": 708.92, "text": " But here in RL, you typically encounter a sequence"}, {"start": 708.92, "end": 710.64, "text": " of highly correlated states."}, {"start": 710.64, "end": 711.48, "text": " So why is that?"}, {"start": 711.48, "end": 712.32, "text": " Well, it's pretty simple."}, {"start": 712.32, "end": 715.72, "text": " When you have a Pong game and the ball is here,"}, {"start": 715.72, "end": 720.0, "text": " in the next frame, you can expect the ball to be anywhere."}, {"start": 720.0, "end": 721.2, "text": " It won't be here or here."}, {"start": 721.2, "end": 725.24, "text": " It's gonna be somewhere in this like circle."}, {"start": 725.24, "end": 728.4, "text": " And that means the next state is highly correlated"}, {"start": 728.4, "end": 729.5600000000001, "text": " with the last one."}, {"start": 729.5600000000001, "end": 731.24, "text": " And that's the problem in RL"}, {"start": 731.24, "end": 733.6800000000001, "text": " that we don't have in the computer vision."}, {"start": 733.6800000000001, "end": 735.04, "text": " Usually we don't have it."}, {"start": 735.04, "end": 738.36, "text": " So furthermore, the data distribution changes"}, {"start": 738.36, "end": 740.92, "text": " as the algorithm learns new behaviors,"}, {"start": 740.92, "end": 743.56, "text": " which can be problematic for deep learning methods"}, {"start": 743.56, "end": 746.1999999999999, "text": " that assume a fixed underlying distribution."}, {"start": 746.1999999999999, "end": 748.9599999999999, "text": " So what it means when you're training your classifier"}, {"start": 748.9599999999999, "end": 750.52, "text": " on images in computer vision,"}, {"start": 750.52, "end": 752.16, "text": " you basically have a data set of images"}, {"start": 752.16, "end": 754.64, "text": " and they form some static distribution,"}, {"start": 754.64, "end": 756.26, "text": " which you're trying to figure out"}, {"start": 756.26, "end": 758.4399999999999, "text": " so that you can predict the class successfully."}, {"start": 758.4399999999999, "end": 762.0999999999999, "text": " Here in RL, when you're learning new policy,"}, {"start": 762.0999999999999, "end": 764.28, "text": " you'll be, because of your new behavior,"}, {"start": 764.28, "end": 766.88, "text": " your new policy, as we call it in RL,"}, {"start": 766.88, "end": 768.76, "text": " you'll be visiting different states."}, {"start": 768.76, "end": 770.8399999999999, "text": " And that means you'll be seeing different data"}, {"start": 770.8399999999999, "end": 771.92, "text": " every now and then."}, {"start": 771.92, "end": 774.04, "text": " And that means that the distribution shifts"}, {"start": 774.04, "end": 775.3199999999999, "text": " and that's problematic."}, {"start": 775.3199999999999, "end": 778.04, "text": " And the way they solve this in this DQM paper"}, {"start": 778.04, "end": 780.1999999999999, "text": " is by using this replay buffer"}, {"start": 780.1999999999999, "end": 782.9599999999999, "text": " because it's gonna have these source tuples"}, {"start": 782.9599999999999, "end": 784.74, "text": " from various, various policies,"}, {"start": 784.74, "end": 787.0, "text": " because in the meanwhile, we're gonna update the network"}, {"start": 787.0, "end": 788.9599999999999, "text": " and we're gonna be storing new tuples"}, {"start": 788.9599999999999, "end": 790.3199999999999, "text": " with the updated network."}, {"start": 790.3199999999999, "end": 792.76, "text": " So we'll have data from different distributions"}, {"start": 792.76, "end": 795.04, "text": " stored in this replay buffer."}, {"start": 795.04, "end": 797.4399999999999, "text": " And that's one of the ways they couple,"}, {"start": 797.4399999999999, "end": 801.2, "text": " they kind of fixed this thing,"}, {"start": 801.2, "end": 804.56, "text": " these instabilities caused by these assumptions"}, {"start": 804.56, "end": 806.4, "text": " being violated."}, {"start": 806.4, "end": 808.48, "text": " Okay, let's continue."}, {"start": 808.48, "end": 812.46, "text": " I already explained the games in Atari we have."}, {"start": 812.46, "end": 815.52, "text": " Just for your kind of mental picture,"}, {"start": 815.52, "end": 817.4, "text": " the imagery is really small."}, {"start": 817.4, "end": 821.38, "text": " It's 210 by 160 at 60 hertz."}, {"start": 821.38, "end": 824.04, "text": " So that's definitely not your 4K video."}, {"start": 824.04, "end": 825.24, "text": " So just keep that in mind."}, {"start": 825.24, "end": 827.08, "text": " The problem was really small."}, {"start": 827.08, "end": 830.66, "text": " Like otherwise, the problem of learning these agents"}, {"start": 830.66, "end": 833.12, "text": " would be really hard back then in 2013"}, {"start": 833.12, "end": 835.6, "text": " when the paper was originally published."}, {"start": 835.6, "end": 839.0, "text": " Okay, so important things to notice here is the following."}, {"start": 839.0, "end": 841.08, "text": " So the network was not provided"}, {"start": 841.08, "end": 843.68, "text": " with any game specific information"}, {"start": 843.68, "end": 846.4, "text": " or hand designed visual features."}, {"start": 846.4, "end": 849.38, "text": " So basically, you don't know the only thing you get"}, {"start": 849.38, "end": 852.56, "text": " for every single one of these games is the observation,"}, {"start": 852.56, "end": 856.4, "text": " I the frame, and you get the reward, the scalar, that's it."}, {"start": 856.4, "end": 860.32, "text": " So nothing else, non game specific information."}, {"start": 860.32, "end": 862.64, "text": " You don't get the hand designed visual features,"}, {"start": 862.64, "end": 865.76, "text": " you're using CNN to learn the future representations."}, {"start": 865.76, "end": 869.04, "text": " So no hand designing, no hand crafting here."}, {"start": 869.04, "end": 871.76, "text": " And we don't have the internal state of the emulator."}, {"start": 871.76, "end": 874.82, "text": " So that means we're dealing with a partially observed MDP."}, {"start": 874.82, "end": 875.96, "text": " So that may be a mouthful."}, {"start": 875.96, "end": 878.64, "text": " So basically MDP is this formalism in RL,"}, {"start": 878.64, "end": 881.08, "text": " which I won't get too deep into now."}, {"start": 881.08, "end": 883.5, "text": " So just a mark of decision process."}, {"start": 883.5, "end": 885.08, "text": " And basically it's partially observed"}, {"start": 885.08, "end": 888.78, "text": " because you don't know the state behind the emulator."}, {"start": 888.78, "end": 890.08, "text": " You just get the frame."}, {"start": 890.08, "end": 892.02, "text": " You don't know all of the processes that are happening"}, {"start": 892.02, "end": 893.96, "text": " to actually render and prepare that frame."}, {"start": 893.96, "end": 896.0, "text": " So that means we're partially observing the system"}, {"start": 896.0, "end": 899.54, "text": " and that's one more difficulty that we have in Atari here."}, {"start": 899.54, "end": 902.64, "text": " And it's a common thing in the real world applications,"}, {"start": 902.64, "end": 903.48, "text": " but yeah."}, {"start": 904.6, "end": 906.28, "text": " Okay, so it learned nothing."}, {"start": 906.28, "end": 908.72, "text": " It just learns from the video input, from the reward"}, {"start": 908.72, "end": 910.48, "text": " and that's it."}, {"start": 910.48, "end": 912.4599999999999, "text": " And the only thing that's actually specific"}, {"start": 912.4599999999999, "end": 916.4399999999999, "text": " to every single of these games is the number of actions."}, {"start": 916.4399999999999, "end": 917.26, "text": " That's it."}, {"start": 917.26, "end": 919.8199999999999, "text": " So you have a CNN here, CNN agent."}, {"start": 919.8199999999999, "end": 924.36, "text": " And because this is Pong, you'll have three outputs probably."}, {"start": 924.36, "end": 927.4, "text": " So the no up, the down and the up action."}, {"start": 927.4, "end": 929.16, "text": " In Break Board it's gonna be similar."}, {"start": 929.16, "end": 932.06, "text": " Maybe in Space Invaders you can shoot aside"}, {"start": 932.06, "end": 933.36, "text": " from moving the paddle."}, {"start": 933.36, "end": 935.72, "text": " So maybe have, I don't know, like four actions."}, {"start": 935.72, "end": 937.84, "text": " So this is the only thing that's game specific."}, {"start": 937.84, "end": 939.12, "text": " The number of actions."}, {"start": 939.12, "end": 942.5, "text": " And that's kinda meaningful because even humans"}, {"start": 942.5, "end": 945.0, "text": " will have a different joystick so that makes sense."}, {"start": 946.08, "end": 950.36, "text": " Okay, so that's the only thing that's kinda game specific."}, {"start": 950.36, "end": 954.32, "text": " And the architecture, so the CNN and the hyperparams"}, {"start": 954.32, "end": 957.3000000000001, "text": " were actually kept constant for every single one"}, {"start": 957.3000000000001, "end": 958.2, "text": " of these Atari games."}, {"start": 958.2, "end": 963.1, "text": " So that's a good step towards the artificial"}, {"start": 963.1, "end": 964.32, "text": " general intelligence."}, {"start": 964.32, "end": 967.1, "text": " Although we are very far off because one thing"}, {"start": 967.1, "end": 969.9200000000001, "text": " you need to know here is that for every single one"}, {"start": 969.9200000000001, "end": 972.8000000000001, "text": " of these games, they had a specific network trained"}, {"start": 972.8000000000001, "end": 973.88, "text": " only for that game."}, {"start": 973.88, "end": 976.7600000000001, "text": " So that means if you have seven games or 57 games,"}, {"start": 976.7600000000001, "end": 980.58, "text": " you'll have 57 differently trained CNNs."}, {"start": 980.58, "end": 983.88, "text": " So you can train one CNN and then deploy it as an agent"}, {"start": 983.88, "end": 985.1600000000001, "text": " in all of these environments."}, {"start": 985.1600000000001, "end": 988.86, "text": " You have to train a single CNN on a single game"}, {"start": 988.86, "end": 990.32, "text": " and use it only there."}, {"start": 990.32, "end": 993.62, "text": " And fun thing about RL, like I just recently read"}, {"start": 993.62, "end": 997.72, "text": " this quote, like RL is the only field,"}, {"start": 997.72, "end": 1000.28, "text": " the only subfield of deep learning where it's socially"}, {"start": 1000.28, "end": 1003.04, "text": " acceptable to train on your test data."}, {"start": 1003.04, "end": 1006.3, "text": " And yeah, that's pretty much true because you're training"}, {"start": 1006.3, "end": 1009.6, "text": " on Pong and then you're actually deploying the agent"}, {"start": 1009.6, "end": 1011.6, "text": " in that very same environment."}, {"start": 1011.6, "end": 1012.9, "text": " So just keep that in mind."}, {"start": 1013.76, "end": 1017.86, "text": " Okay, that was the initial things I wanted to explain here."}, {"start": 1017.86, "end": 1020.44, "text": " And now let's see, let's go further."}, {"start": 1020.44, "end": 1023.7, "text": " Now we're gonna see some mathematical formalism"}, {"start": 1023.7, "end": 1024.8600000000001, "text": " of MDPs and stuff."}, {"start": 1024.8600000000001, "end": 1026.6200000000001, "text": " So yeah, let's start."}, {"start": 1026.6200000000001, "end": 1029.8600000000001, "text": " First things first, the task is partially observed"}, {"start": 1029.8600000000001, "end": 1032.16, "text": " and many other states are perceptually aliased"}, {"start": 1032.16, "end": 1034.94, "text": " as I already mentioned that the example with the Pong ball"}, {"start": 1034.94, "end": 1036.88, "text": " that can go in any direction."}, {"start": 1036.88, "end": 1039.46, "text": " So it's impossible to fully understand the current situation"}, {"start": 1039.46, "end": 1040.78, "text": " from only the current frame."}, {"start": 1040.78, "end": 1043.6200000000001, "text": " And that's the reason they're stacking four frames together."}, {"start": 1043.6200000000001, "end": 1046.1200000000001, "text": " We need the temporal information in order to play the game."}, {"start": 1046.1200000000001, "end": 1048.3200000000002, "text": " Okay, let's see the formalism."}, {"start": 1048.32, "end": 1051.54, "text": " This is the quantity we wanna actually maximize."}, {"start": 1051.54, "end": 1055.06, "text": " It's the future discounted"}, {"start": 1055.06, "end": 1058.3799999999999, "text": " because of this gamma factor reward."}, {"start": 1058.3799999999999, "end": 1061.24, "text": " And gamma is just a mathematical formalism"}, {"start": 1061.24, "end": 1064.1, "text": " which makes you, when t goes to infinity,"}, {"start": 1064.1, "end": 1067.1599999999999, "text": " when the number of steps here goes to infinity,"}, {"start": 1067.1599999999999, "end": 1069.1, "text": " if we have gamma that's usually between,"}, {"start": 1069.1, "end": 1071.12, "text": " that's always between zero and one,"}, {"start": 1071.12, "end": 1074.62, "text": " and it's usually actually 0.99,"}, {"start": 1074.62, "end": 1078.4599999999998, "text": " when you have that, this array is gonna converge"}, {"start": 1078.4599999999998, "end": 1081.26, "text": " to a finite number and that's desirable"}, {"start": 1081.26, "end": 1082.7399999999998, "text": " when you're dealing, you don't wanna deal"}, {"start": 1082.7399999999998, "end": 1084.4799999999998, "text": " with infinities, right?"}, {"start": 1084.4799999999998, "end": 1086.8799999999999, "text": " But usually you deal with finite episodes"}, {"start": 1086.8799999999999, "end": 1088.9799999999998, "text": " so this gamma doesn't matter so much."}, {"start": 1088.9799999999998, "end": 1091.1399999999999, "text": " You can sometimes even set it to one"}, {"start": 1091.1399999999999, "end": 1092.86, "text": " and nothing will break."}, {"start": 1092.86, "end": 1093.6999999999998, "text": " That's the first quantity."}, {"start": 1093.6999999999998, "end": 1096.02, "text": " The second one is the action value function"}, {"start": 1096.02, "end": 1097.62, "text": " and aside from this one you'll be seeing"}, {"start": 1097.62, "end": 1099.6399999999999, "text": " something called state value function,"}, {"start": 1099.6399999999999, "end": 1101.62, "text": " but for now let's just focus on this one."}, {"start": 1101.62, "end": 1106.62, "text": " And in optimal case you wanna find the policy P,"}, {"start": 1106.8999999999999, "end": 1108.34, "text": " this is what this equation is telling us."}, {"start": 1108.34, "end": 1110.6799999999998, "text": " So we wanna find the policy P"}, {"start": 1110.6799999999998, "end": 1113.82, "text": " that will maximize this expression here."}, {"start": 1113.82, "end": 1115.7399999999998, "text": " And this is just the reward,"}, {"start": 1115.7399999999998, "end": 1118.84, "text": " the expected reward from this particular state"}, {"start": 1118.84, "end": 1121.12, "text": " and taking this particular action."}, {"start": 1121.12, "end": 1123.4599999999998, "text": " So that's what the Q value is telling you."}, {"start": 1123.4599999999998, "end": 1124.5, "text": " It's telling you the following."}, {"start": 1124.5, "end": 1128.1399999999999, "text": " If I'm in this state and I perform this specific action,"}, {"start": 1128.1399999999999, "end": 1130.62, "text": " what's the expected reward I'll get?"}, {"start": 1130.62, "end": 1133.6999999999998, "text": " I can expect from this action in this state."}, {"start": 1133.6999999999998, "end": 1137.3, "text": " And once you get to the actual action value,"}, {"start": 1137.3, "end": 1139.7399999999998, "text": " it's gonna be something called Bellman equation."}, {"start": 1139.7399999999998, "end": 1141.1799999999998, "text": " And you're gonna see this a lot,"}, {"start": 1141.1799999999998, "end": 1144.6799999999998, "text": " especially in the older RL algorithms"}, {"start": 1145.58, "end": 1148.62, "text": " where they used to use table lookups"}, {"start": 1148.62, "end": 1150.1, "text": " instead of neural networks."}, {"start": 1150.1, "end": 1153.9399999999998, "text": " So basically this is what the Bellman equation looks like."}, {"start": 1156.3799999999999, "end": 1159.4199999999998, "text": " For the specific case of using something called TD"}, {"start": 1159.42, "end": 1161.94, "text": " or temporal difference learning."}, {"start": 1161.94, "end": 1166.42, "text": " And basically the Q will be equal,"}, {"start": 1166.42, "end": 1170.1000000000001, "text": " the optimal value, the Q star will be equal to R,"}, {"start": 1170.1000000000001, "end": 1172.98, "text": " the reward, plus gamma, discounted,"}, {"start": 1172.98, "end": 1177.22, "text": " maximum Q star across all the actions"}, {"start": 1177.22, "end": 1179.6200000000001, "text": " in the future state S prime."}, {"start": 1179.6200000000001, "end": 1182.0600000000002, "text": " So this is just something to wrap your head around."}, {"start": 1182.0600000000002, "end": 1183.54, "text": " If you've never seen this before,"}, {"start": 1183.54, "end": 1185.94, "text": " it's gonna be kind of look really strange,"}, {"start": 1185.94, "end": 1189.7, "text": " but it's actually much easier when you see the implementation"}, {"start": 1189.7, "end": 1193.1000000000001, "text": " because this tells us the following thing."}, {"start": 1193.1000000000001, "end": 1198.1000000000001, "text": " We take the CNN and we input the current state S."}, {"start": 1199.38, "end": 1202.42, "text": " And basically then we take another CNN"}, {"start": 1204.22, "end": 1206.42, "text": " and we put the state S prime."}, {"start": 1207.98, "end": 1210.02, "text": " And now we're gonna find the max,"}, {"start": 1210.02, "end": 1212.1200000000001, "text": " whatever the max here is,"}, {"start": 1212.1200000000001, "end": 1214.06, "text": " we're gonna sum it up with R"}, {"start": 1214.06, "end": 1219.06, "text": " and once we have the true action value function,"}, {"start": 1219.58, "end": 1221.94, "text": " which we're trying to approximate during this training,"}, {"start": 1221.94, "end": 1223.76, "text": " it's gonna satisfy this equation."}, {"start": 1223.76, "end": 1224.8999999999999, "text": " That's what it says."}, {"start": 1224.8999999999999, "end": 1228.86, "text": " And don't get scared because of the expectation operator."}, {"start": 1228.86, "end": 1232.86, "text": " It just tells us that we are basically sampling"}, {"start": 1232.86, "end": 1235.5, "text": " this next state from the distribution"}, {"start": 1235.5, "end": 1237.26, "text": " that the emulator is providing us."}, {"start": 1237.26, "end": 1239.1, "text": " That's this epsilon here."}, {"start": 1239.1, "end": 1243.58, "text": " But for the old purposes, you can just ignore it"}, {"start": 1243.58, "end": 1245.86, "text": " because this is how it's actually gonna work"}, {"start": 1245.86, "end": 1247.48, "text": " when you try and code it up."}, {"start": 1247.48, "end": 1251.28, "text": " You're just gonna do this and then an expectation"}, {"start": 1251.28, "end": 1252.74, "text": " because you're sampling different states"}, {"start": 1252.74, "end": 1254.1799999999998, "text": " as you're playing the game,"}, {"start": 1254.1799999999998, "end": 1256.5, "text": " this thing is gonna be solved for itself."}, {"start": 1256.5, "end": 1258.6999999999998, "text": " So there is this discrepancy between equations"}, {"start": 1258.6999999999998, "end": 1260.06, "text": " and how it actually works."}, {"start": 1260.06, "end": 1262.26, "text": " The second discrepancy you could maybe notice here"}, {"start": 1262.26, "end": 1265.08, "text": " is that Q is fed with S and A,"}, {"start": 1265.08, "end": 1266.34, "text": " but actually as we saw,"}, {"start": 1266.34, "end": 1270.22, "text": " CNN is only taking S and it's outputting the actions."}, {"start": 1270.22, "end": 1273.7, "text": " So that's just the legacy formalism"}, {"start": 1273.7, "end": 1275.78, "text": " that most of these papers have."}, {"start": 1275.78, "end": 1277.7, "text": " And once you actually see the code,"}, {"start": 1277.7, "end": 1279.3, "text": " believe me, it's much easier."}, {"start": 1279.3, "end": 1280.38, "text": " I mean, it's not easier."}, {"start": 1280.38, "end": 1282.6200000000001, "text": " It's just the discrepancies what makes me"}, {"start": 1282.6200000000001, "end": 1285.64, "text": " kinda have this dissonance in my brain."}, {"start": 1285.64, "end": 1288.14, "text": " So I guess most of you already experienced it."}, {"start": 1289.66, "end": 1292.18, "text": " Okay, so now the theory goes like this."}, {"start": 1292.18, "end": 1293.74, "text": " So this is what the optimal,"}, {"start": 1293.74, "end": 1296.94, "text": " the true Q value function will look like."}, {"start": 1296.94, "end": 1298.84, "text": " It's gonna obey this Bellman equation."}, {"start": 1298.84, "end": 1301.4599999999998, "text": " But initially our neural network is random."}, {"start": 1301.4599999999998, "end": 1302.9199999999998, "text": " So it's not gonna obey this."}, {"start": 1302.9199999999998, "end": 1305.9399999999998, "text": " And in order to actually converge"}, {"start": 1305.9399999999998, "end": 1307.58, "text": " to this true Q value function,"}, {"start": 1307.58, "end": 1310.3799999999999, "text": " we're gonna do something called value iteration."}, {"start": 1310.3799999999999, "end": 1314.6999999999998, "text": " And they converge to the optimal action value function."}, {"start": 1314.6999999999998, "end": 1317.6999999999998, "text": " So basically by just doing this thing here,"}, {"start": 1317.6999999999998, "end": 1319.86, "text": " by just iterating,"}, {"start": 1319.86, "end": 1321.6999999999998, "text": " and we'll see the exact algorithm a bit later,"}, {"start": 1321.6999999999998, "end": 1323.76, "text": " but just stick with me for now."}, {"start": 1323.76, "end": 1325.1999999999998, "text": " So by just doing this,"}, {"start": 1325.1999999999998, "end": 1327.8799999999999, "text": " we're gonna slowly get to the true value."}, {"start": 1327.88, "end": 1331.22, "text": " And after we update the Q value,"}, {"start": 1331.22, "end": 1333.88, "text": " because our policy is coupled, if you remember,"}, {"start": 1333.88, "end": 1336.44, "text": " with this Q value by the Epsilon greedy algorithm,"}, {"start": 1336.44, "end": 1338.5800000000002, "text": " we're gonna improve the policy automatically."}, {"start": 1338.5800000000002, "end": 1341.8200000000002, "text": " And that there is this theory from RL that says,"}, {"start": 1341.8200000000002, "end": 1343.5400000000002, "text": " if you do that, if you're improving Q,"}, {"start": 1343.5400000000002, "end": 1345.18, "text": " and if you're improving your policy,"}, {"start": 1345.18, "end": 1346.5, "text": " which we're automatically doing here"}, {"start": 1346.5, "end": 1348.8200000000002, "text": " because we're coupled by Epsilon greedy,"}, {"start": 1348.8200000000002, "end": 1352.5, "text": " we're gonna converge to the actual optimal Q value,"}, {"start": 1352.5, "end": 1356.3400000000001, "text": " the Q star action value function."}, {"start": 1356.3400000000001, "end": 1357.72, "text": " So yeah."}, {"start": 1357.72, "end": 1361.38, "text": " And all of this theory actually was first invented,"}, {"start": 1361.38, "end": 1365.04, "text": " let's call it invented for the table lookup example,"}, {"start": 1365.04, "end": 1367.8, "text": " where you had something like this."}, {"start": 1367.8, "end": 1370.1000000000001, "text": " So you basically had a matrix,"}, {"start": 1370.1000000000001, "end": 1374.04, "text": " and along this dimension you'd have states S,"}, {"start": 1374.04, "end": 1376.06, "text": " and along this one you'd have actions."}, {"start": 1376.06, "end": 1378.94, "text": " And now you can see why this is totally impractical."}, {"start": 1378.94, "end": 1383.94, "text": " S is gonna explode in any serious real world problem,"}, {"start": 1383.94, "end": 1386.74, "text": " as well as actions that can be continuous in some cases,"}, {"start": 1386.74, "end": 1388.42, "text": " when in robotics, for example."}, {"start": 1388.42, "end": 1390.78, "text": " So there's gonna be huge and impractical."}, {"start": 1390.78, "end": 1394.06, "text": " And the second thing, aside from memory problems,"}, {"start": 1394.06, "end": 1395.9, "text": " we have something even more serious,"}, {"start": 1395.9, "end": 1398.66, "text": " and that's once you figure out the value"}, {"start": 1398.66, "end": 1401.42, "text": " for this state action point,"}, {"start": 1401.42, "end": 1403.14, "text": " how are you going to generalize"}, {"start": 1403.14, "end": 1407.54, "text": " to every single other point in this state action space?"}, {"start": 1407.54, "end": 1410.14, "text": " You won't, unless you do some interpolation,"}, {"start": 1410.14, "end": 1412.66, "text": " but that's again computationally expensive"}, {"start": 1412.66, "end": 1414.58, "text": " because you have to interpolate."}, {"start": 1414.58, "end": 1417.1399999999999, "text": " Because of that, the neural networks are really cool"}, {"start": 1417.1399999999999, "end": 1419.1399999999999, "text": " because they can just automatically,"}, {"start": 1419.1399999999999, "end": 1421.78, "text": " by just updating the parameters,"}, {"start": 1421.78, "end": 1426.22, "text": " you get the close, you also update the states"}, {"start": 1426.22, "end": 1429.9399999999998, "text": " around this state for free, let's call it like that."}, {"start": 1429.9399999999998, "end": 1432.26, "text": " So that's something I wanted to mention there."}, {"start": 1432.26, "end": 1436.06, "text": " And now this is the thing I initially explained,"}, {"start": 1436.06, "end": 1438.1799999999998, "text": " how we actually train this network."}, {"start": 1438.1799999999998, "end": 1439.58, "text": " So we have the targets,"}, {"start": 1439.58, "end": 1443.1, "text": " and we're just trying to minimize the L2 loss."}, {"start": 1443.1, "end": 1446.1399999999999, "text": " So you see here, we just have the difference"}, {"start": 1446.1399999999999, "end": 1448.1, "text": " and then squared, we're just trying to minimize"}, {"start": 1448.1, "end": 1452.54, "text": " the L2 loss between the target and between the queue."}, {"start": 1452.54, "end": 1456.3, "text": " And the target is, as I mentioned, the frozen network,"}, {"start": 1456.3, "end": 1460.02, "text": " so this theta, I minus one, let me zoom in a little bit."}, {"start": 1460.02, "end": 1464.6399999999999, "text": " So we're gonna freeze in some point the parameters,"}, {"start": 1464.6399999999999, "end": 1466.2199999999998, "text": " and we're not gonna change it,"}, {"start": 1466.2199999999998, "end": 1470.1999999999998, "text": " and we're going to use that network for the target network."}, {"start": 1470.1999999999998, "end": 1472.9399999999998, "text": " So how it goes is the following."}, {"start": 1472.94, "end": 1475.78, "text": " We have the SARS top, remember?"}, {"start": 1475.78, "end": 1476.98, "text": " So we have the SARS."}, {"start": 1478.8200000000002, "end": 1482.02, "text": " So what we're going to do is we have the queue network,"}, {"start": 1482.02, "end": 1486.02, "text": " that's our current CNN, okay?"}, {"start": 1487.26, "end": 1492.26, "text": " We input S here, we know what the action is,"}, {"start": 1492.72, "end": 1496.18, "text": " so we'll focus on that queue value,"}, {"start": 1496.18, "end": 1498.8400000000001, "text": " and that's this queue, okay?"}, {"start": 1498.8400000000001, "end": 1500.7, "text": " So how do we get a target?"}, {"start": 1500.7, "end": 1505.42, "text": " Well, we take that frozen CNN, some old CNN,"}, {"start": 1505.42, "end": 1510.42, "text": " old like this, we input the S prime,"}, {"start": 1510.94, "end": 1513.9, "text": " so from the tuple again, we have that information,"}, {"start": 1513.9, "end": 1518.9, "text": " we input the S prime, and now we're gonna actually maximize,"}, {"start": 1519.38, "end": 1523.88, "text": " find the biggest value here, and we're gonna add the R,"}, {"start": 1523.88, "end": 1525.88, "text": " which we also have from the tuple,"}, {"start": 1525.88, "end": 1528.14, "text": " and that's gonna be our target."}, {"start": 1528.14, "end": 1532.66, "text": " So that's gonna be Y of I, and once we have that value,"}, {"start": 1532.66, "end": 1537.66, "text": " we're just gonna try and tweak the parameters here,"}, {"start": 1538.1000000000001, "end": 1542.4, "text": " so as to approach that R plus Q,"}, {"start": 1542.4, "end": 1545.16, "text": " the new Q, the Q prime, let's call it, whatever."}, {"start": 1545.16, "end": 1547.74, "text": " So that's the whole point, that's how it works."}, {"start": 1547.74, "end": 1551.38, "text": " You're doing L2, you're doing the mean squared error"}, {"start": 1551.38, "end": 1552.6000000000001, "text": " when you have the mini-batch,"}, {"start": 1552.6000000000001, "end": 1555.24, "text": " and that's how you train the parameters."}, {"start": 1555.24, "end": 1560.24, "text": " So now you may be puzzled with this replay buffer,"}, {"start": 1560.78, "end": 1562.86, "text": " you may be puzzled with this frozen network,"}, {"start": 1562.86, "end": 1564.82, "text": " some of those are actually just heuristics,"}, {"start": 1564.82, "end": 1567.06, "text": " and there is no theoretical guarantee"}, {"start": 1567.06, "end": 1569.86, "text": " that it's gonna converge, but it does in practice,"}, {"start": 1569.86, "end": 1572.74, "text": " and was inspired by the actual theory"}, {"start": 1572.74, "end": 1575.96, "text": " that came from these exact cases"}, {"start": 1575.96, "end": 1577.32, "text": " where we had the table lookups"}, {"start": 1577.32, "end": 1579.34, "text": " and not the function approximations."}, {"start": 1579.34, "end": 1581.44, "text": " So yeah, hopefully that makes sense,"}, {"start": 1582.54, "end": 1583.98, "text": " and they say here the parameters"}, {"start": 1583.98, "end": 1587.02, "text": " from the previous iteration theta I minus one"}, {"start": 1587.02, "end": 1590.6200000000001, "text": " are held fixed when optimizing the loss function, blah blah."}, {"start": 1590.6200000000001, "end": 1593.22, "text": " So we won't be back propagating through this one,"}, {"start": 1593.22, "end": 1598.06, "text": " so this is just, yeah, just the parameters are frozen."}, {"start": 1598.06, "end": 1601.38, "text": " Okay, I think I've covered everything here."}, {"start": 1601.38, "end": 1605.58, "text": " They just explicitly derived the gradient for the loss,"}, {"start": 1605.58, "end": 1607.02, "text": " this is something that your favorite"}, {"start": 1607.02, "end": 1609.98, "text": " deep learning framework of choice does for you,"}, {"start": 1609.98, "end": 1611.7, "text": " so we don't have to cover this one."}, {"start": 1611.7, "end": 1613.14, "text": " So either PyTorch or TensorFlow"}, {"start": 1613.14, "end": 1615.5800000000002, "text": " will just, once you specify the loss like this,"}, {"start": 1615.5800000000002, "end": 1620.5800000000002, "text": " so the simple L2, the framework will find the gradients"}, {"start": 1620.66, "end": 1622.98, "text": " automatically using the autodef engine, okay?"}, {"start": 1624.14, "end": 1626.38, "text": " So let's see these two things."}, {"start": 1626.38, "end": 1630.3200000000002, "text": " First, this Q learning algorithm is model-free."}, {"start": 1630.3200000000002, "end": 1633.3400000000001, "text": " That means we're not trying to explicitly model"}, {"start": 1633.3400000000001, "end": 1635.98, "text": " the transition from S to S prime,"}, {"start": 1635.98, "end": 1637.7800000000002, "text": " from this state to the next state."}, {"start": 1637.7800000000002, "end": 1639.4, "text": " We don't know the probability"}, {"start": 1639.4, "end": 1641.0600000000002, "text": " of transiting into the next state,"}, {"start": 1641.0600000000002, "end": 1642.1000000000001, "text": " we don't care about it,"}, {"start": 1642.1, "end": 1644.6999999999998, "text": " we're just doing model-free RL,"}, {"start": 1644.6999999999998, "end": 1646.32, "text": " interacting with the environment"}, {"start": 1646.32, "end": 1650.2199999999998, "text": " and learning the action value functions directly"}, {"start": 1650.2199999999998, "end": 1652.54, "text": " without caring about the actual probabilities"}, {"start": 1652.54, "end": 1653.82, "text": " and modeling these."}, {"start": 1653.82, "end": 1656.1799999999998, "text": " So that's why this thing is model-free."}, {"start": 1656.1799999999998, "end": 1657.54, "text": " Why is it off-policy?"}, {"start": 1657.54, "end": 1661.02, "text": " Well, it's off-policy because it's using the epsilon greedy"}, {"start": 1661.02, "end": 1664.5, "text": " to collect the data into the replay buffer, if you remember."}, {"start": 1664.5, "end": 1667.2199999999998, "text": " So we are collecting into the replay buffer"}, {"start": 1667.2199999999998, "end": 1669.54, "text": " using the epsilon greedy,"}, {"start": 1669.54, "end": 1673.42, "text": " and then the target is actually using the max policy,"}, {"start": 1673.42, "end": 1676.1, "text": " the greedy policy, and that's another policy."}, {"start": 1676.1, "end": 1681.1, "text": " And so we're trying to learn the max Q value"}, {"start": 1681.58, "end": 1684.06, "text": " while using the behavior policy,"}, {"start": 1684.06, "end": 1685.42, "text": " that's how they call it,"}, {"start": 1685.42, "end": 1687.34, "text": " the epsilon greedy and the target policy"}, {"start": 1687.34, "end": 1688.94, "text": " is the greedy policy."}, {"start": 1688.94, "end": 1690.42, "text": " That's why it's off-policy."}, {"start": 1690.42, "end": 1692.94, "text": " So intuitively, what we're trying to do here"}, {"start": 1692.94, "end": 1696.54, "text": " is we wanna have this Q, our CNN here,"}, {"start": 1696.54, "end": 1700.54, "text": " be able to predict what will be the expected reward"}, {"start": 1700.54, "end": 1702.46, "text": " plus the whatever max here is."}, {"start": 1702.46, "end": 1707.46, "text": " So we're gonna try and learn what this particular state,"}, {"start": 1707.8, "end": 1709.36, "text": " what's the max value we can expect."}, {"start": 1709.36, "end": 1711.8999999999999, "text": " So hopefully I didn't confuse you here."}, {"start": 1711.8999999999999, "end": 1713.78, "text": " Let me know in the comments if this was clear enough,"}, {"start": 1713.78, "end": 1718.42, "text": " I can try and explain a bit better next time, whatever."}, {"start": 1718.42, "end": 1722.1, "text": " Okay, let's continue and see what else is there."}, {"start": 1723.7, "end": 1725.1, "text": " So furthermore, it was shown"}, {"start": 1725.1, "end": 1727.5, "text": " that combining model-free reinforcement learning"}, {"start": 1727.5, "end": 1731.34, "text": " such as Q learning with nonlinear function approximators"}, {"start": 1732.6599999999999, "end": 1734.78, "text": " and using off-policy learning"}, {"start": 1734.78, "end": 1737.1, "text": " could cause the Q network to diverge."}, {"start": 1737.1, "end": 1738.78, "text": " So that's the theory."}, {"start": 1738.78, "end": 1740.1, "text": " And that's pretty problematic"}, {"start": 1740.1, "end": 1742.2199999999998, "text": " because you wanna have stable training."}, {"start": 1742.2199999999998, "end": 1746.3799999999999, "text": " And fortunately, DQM paper,"}, {"start": 1746.3799999999999, "end": 1747.5, "text": " they didn't have the problem"}, {"start": 1747.5, "end": 1749.2199999999998, "text": " because of the memory replay buffer"}, {"start": 1749.2199999999998, "end": 1752.02, "text": " and because of the target network being frozen,"}, {"start": 1752.02, "end": 1754.48, "text": " actually, they avoided the instabilities."}, {"start": 1754.48, "end": 1755.78, "text": " But this problem is something known"}, {"start": 1755.78, "end": 1758.6200000000001, "text": " as the deadly triad in the literature."}, {"start": 1758.6200000000001, "end": 1762.38, "text": " So this is just an excerpt from the Rich Sutton's book"}, {"start": 1762.38, "end": 1765.0, "text": " and an introduction to RL,"}, {"start": 1765.0, "end": 1766.78, "text": " which is like a must read"}, {"start": 1766.78, "end": 1769.42, "text": " if you're doing RL really seriously."}, {"start": 1769.42, "end": 1771.52, "text": " At one point of time, you should probably check it out."}, {"start": 1771.52, "end": 1772.3600000000001, "text": " I still haven't."}, {"start": 1772.3600000000001, "end": 1776.82, "text": " I usually start by doing high level resources first"}, {"start": 1776.82, "end": 1779.82, "text": " and then slowly going down to papers"}, {"start": 1779.82, "end": 1781.5, "text": " and only later do I read the book."}, {"start": 1781.5, "end": 1783.08, "text": " So that's maybe counterintuitive,"}, {"start": 1783.08, "end": 1785.3, "text": " but that's the best approach for me."}, {"start": 1785.3, "end": 1786.6999999999998, "text": " And he said also here,"}, {"start": 1786.6999999999998, "end": 1789.62, "text": " so when you combine the function approximation,"}, {"start": 1789.62, "end": 1792.74, "text": " the bootstrapping, so bootstrapping being TD,"}, {"start": 1792.74, "end": 1797.26, "text": " and other than TD, you could be using something called MC,"}, {"start": 1797.26, "end": 1801.02, "text": " like Monte Carlo, or you could be using something in between,"}, {"start": 1801.02, "end": 1804.46, "text": " like TD lambda, and you don't have to know"}, {"start": 1804.46, "end": 1805.8799999999999, "text": " what all of these are."}, {"start": 1805.8799999999999, "end": 1810.26, "text": " But it's basically, instead of doing just R"}, {"start": 1810.26, "end": 1813.86, "text": " plus the Q value here and your bootstrapping that way,"}, {"start": 1813.86, "end": 1816.42, "text": " you just roll out until the end of the episodes"}, {"start": 1816.42, "end": 1818.34, "text": " and just use the actual rewards"}, {"start": 1818.34, "end": 1821.82, "text": " instead of trying to use the Q value to bootstrap"}, {"start": 1821.82, "end": 1824.24, "text": " and figure out the actual Q value now."}, {"start": 1824.24, "end": 1826.46, "text": " So that's the bootstrapping part."}, {"start": 1826.46, "end": 1828.02, "text": " And finally, the off policy,"}, {"start": 1828.02, "end": 1830.58, "text": " and that's why it's called a triad, tri for three."}, {"start": 1830.58, "end": 1832.56, "text": " So basically, when you have these three elements"}, {"start": 1832.56, "end": 1835.46, "text": " combined together, you're roughly,"}, {"start": 1835.46, "end": 1837.78, "text": " you're probably going to have instability problems,"}, {"start": 1837.78, "end": 1842.26, "text": " but yeah, as DQN folks showed,"}, {"start": 1842.26, "end": 1844.42, "text": " they didn't have it because of some of the hacks,"}, {"start": 1844.42, "end": 1847.3, "text": " hacks they used, the replay buffer and the target network"}, {"start": 1847.3, "end": 1850.6, "text": " are the main two components that made it work."}, {"start": 1850.6, "end": 1855.54, "text": " Okay, that's that part, let's go further."}, {"start": 1855.54, "end": 1858.12, "text": " And let's actually see the algorithm,"}, {"start": 1858.12, "end": 1860.5, "text": " and I'll try to walk you through this one."}, {"start": 1860.5, "end": 1862.78, "text": " So first, we initialize the memory,"}, {"start": 1862.78, "end": 1865.8799999999999, "text": " the replay buffer to capacity N."}, {"start": 1865.88, "end": 1869.7800000000002, "text": " And they had 1 million slots here,"}, {"start": 1869.7800000000002, "end": 1872.18, "text": " just for being less abstract."}, {"start": 1872.18, "end": 1874.66, "text": " They initialized the action value function Q"}, {"start": 1874.66, "end": 1875.7, "text": " with random weights."}, {"start": 1875.7, "end": 1879.8200000000002, "text": " So just take your CNN and use whatever your favorite"}, {"start": 1879.8200000000002, "end": 1882.74, "text": " in it method is, maybe Gloroth or Xavier,"}, {"start": 1882.74, "end": 1885.3400000000001, "text": " whatever your initialization method is."}, {"start": 1885.3400000000001, "end": 1887.6000000000001, "text": " And then we do the following, we trade over the episode,"}, {"start": 1887.6000000000001, "end": 1890.6200000000001, "text": " we have M episodes, we initialize the sequence,"}, {"start": 1890.6200000000001, "end": 1894.9, "text": " we take the initial frame from the Atari environment,"}, {"start": 1894.9, "end": 1897.92, "text": " we just do some pre-processing, so that's the four frames,"}, {"start": 1897.92, "end": 1901.0600000000002, "text": " the cropping, some details you'll see in a bit."}, {"start": 1901.0600000000002, "end": 1904.6200000000001, "text": " And then for every single step in that particular episode,"}, {"start": 1904.6200000000001, "end": 1907.0, "text": " we do the following, we perform an action"}, {"start": 1907.0, "end": 1909.44, "text": " using epsilon greedy policy, so that's this."}, {"start": 1909.44, "end": 1911.98, "text": " We probability epsilon, we select a random action,"}, {"start": 1911.98, "end": 1915.5400000000002, "text": " otherwise we select the max, we max it out,"}, {"start": 1915.5400000000002, "end": 1917.3000000000002, "text": " we do the greedy approach."}, {"start": 1917.3000000000002, "end": 1919.94, "text": " Then we send the action to the environment."}, {"start": 1919.94, "end": 1922.98, "text": " So that's if you're using, you're usually gonna be using"}, {"start": 1922.98, "end": 1927.5, "text": " something like OpenAI's gym, so that's gonna be roughly"}, {"start": 1927.5, "end": 1931.06, "text": " correspond to dot step, and you're gonna pass the action,"}, {"start": 1931.06, "end": 1933.26, "text": " and then the environment's gonna return the observation,"}, {"start": 1933.26, "end": 1935.6, "text": " the reward, and the dom flag, which signals whether"}, {"start": 1935.6, "end": 1938.26, "text": " the episode is over or not."}, {"start": 1939.7, "end": 1942.82, "text": " Once we have that, we just pre-process that frame,"}, {"start": 1942.82, "end": 1946.3, "text": " and we store the transition, the star stopple,"}, {"start": 1946.3, "end": 1950.26, "text": " where they're using this five to denote the processed state."}, {"start": 1950.26, "end": 1952.3, "text": " So this is basically the state."}, {"start": 1952.3, "end": 1956.02, "text": " So we just store the star stopple inside of the replay"}, {"start": 1956.02, "end": 1960.7, "text": " buffer, and then we're gonna sample random mini-batch"}, {"start": 1960.7, "end": 1961.54, "text": " from D."}, {"start": 1961.54, "end": 1965.34, "text": " Now, just for your understanding, they're going to do this,"}, {"start": 1965.34, "end": 1967.48, "text": " I think the actual number was four."}, {"start": 1967.48, "end": 1970.82, "text": " So every four actions, you perform four actions,"}, {"start": 1970.82, "end": 1973.76, "text": " and only then do you sample the mini-batch."}, {"start": 1973.76, "end": 1977.26, "text": " Because otherwise, you need to fill in, remember,"}, {"start": 1977.26, "end": 1979.68, "text": " this pre-processing function expects four frames,"}, {"start": 1979.68, "end": 1982.6200000000001, "text": " so we have to kind of fill it up before we start"}, {"start": 1982.6200000000001, "end": 1984.42, "text": " doing the inference with the Q network."}, {"start": 1984.42, "end": 1987.02, "text": " So that's why they're gonna do, I think that's the reason"}, {"start": 1987.02, "end": 1989.98, "text": " they're going to do it every four steps."}, {"start": 1989.98, "end": 1994.3600000000001, "text": " And again, you can see we just formed the target,"}, {"start": 1995.22, "end": 1998.54, "text": " and that's either reward if you're in the terminal state,"}, {"start": 1998.54, "end": 2000.78, "text": " if you're at the last frame of the game,"}, {"start": 2000.78, "end": 2003.18, "text": " otherwise we're gonna bootstrap using Q,"}, {"start": 2003.18, "end": 2005.66, "text": " the old Q function, and that's the target,"}, {"start": 2005.66, "end": 2007.96, "text": " and then we're going to do gradient descent"}, {"start": 2007.96, "end": 2011.02, "text": " on the L2 of these two."}, {"start": 2011.02, "end": 2012.0, "text": " And that's it."}, {"start": 2012.0, "end": 2015.22, "text": " So I think the mini-batch size was 32."}, {"start": 2015.22, "end": 2018.66, "text": " That means we'll take 32 samples randomly"}, {"start": 2018.66, "end": 2023.1000000000001, "text": " from this buffer, so just 32 random source tuples,"}, {"start": 2023.1000000000001, "end": 2025.3400000000001, "text": " and we're gonna form this, and we're just gonna"}, {"start": 2025.3400000000001, "end": 2028.06, "text": " average it out and let the deep learning framework"}, {"start": 2028.06, "end": 2030.16, "text": " do the rest for us, find the gradient automatically,"}, {"start": 2030.16, "end": 2032.46, "text": " and minimize this loss."}, {"start": 2032.46, "end": 2034.44, "text": " And that's the whole algorithm."}, {"start": 2034.44, "end": 2037.06, "text": " Hopefully now it's a bit more clear."}, {"start": 2037.06, "end": 2041.08, "text": " And I think I mentioned this, but let me just reiterate."}, {"start": 2041.08, "end": 2043.4199999999998, "text": " So learning directly from consecutive samples"}, {"start": 2043.4199999999998, "end": 2045.3799999999999, "text": " is inefficient due to strong correlations."}, {"start": 2045.3799999999999, "end": 2048.2599999999998, "text": " So I mentioned the example with the ball in Pong"}, {"start": 2048.2599999999998, "end": 2051.34, "text": " and being correlated with the next frame."}, {"start": 2051.34, "end": 2055.54, "text": " So randomizing the samples by taking random samples"}, {"start": 2055.54, "end": 2059.22, "text": " from the replay buffer, we are breaking these correlations,"}, {"start": 2059.22, "end": 2061.74, "text": " and we are reducing the variance of the updates."}, {"start": 2061.74, "end": 2066.34, "text": " So that's the important trick to make this thing stable"}, {"start": 2066.34, "end": 2067.7000000000003, "text": " and to make it work."}, {"start": 2067.7000000000003, "end": 2072.3, "text": " I just took a snippet from the, so this paper is from 2013,"}, {"start": 2072.3, "end": 2074.54, "text": " and later they published a paper in Nature,"}, {"start": 2074.54, "end": 2076.7000000000003, "text": " and so I just took a snippet from that paper,"}, {"start": 2076.7000000000003, "end": 2080.86, "text": " and they have additional line here, so every C steps"}, {"start": 2080.86, "end": 2084.7000000000003, "text": " just swap the target, that's the frozen Q network"}, {"start": 2084.7000000000003, "end": 2085.6600000000003, "text": " I was talking about."}, {"start": 2085.6600000000003, "end": 2088.46, "text": " So you just take the current network, and every C steps,"}, {"start": 2088.46, "end": 2090.6400000000003, "text": " which is maybe every, I don't know, 1,000,"}, {"start": 2090.6400000000003, "end": 2094.02, "text": " I think they use 1K batch updates, you just swap"}, {"start": 2094.02, "end": 2097.02, "text": " the networks and use that one as the frozen network"}, {"start": 2097.02, "end": 2098.94, "text": " to predict your target labels."}, {"start": 2098.94, "end": 2101.86, "text": " And that's the additional detail I wanted to mention."}, {"start": 2101.86, "end": 2105.5, "text": " Okay, with that out of the way, let's continue"}, {"start": 2105.5, "end": 2109.96, "text": " and dive into a bit more details about the pre-processing."}, {"start": 2109.96, "end": 2114.78, "text": " So what they do is they convert the RGB to grayscale,"}, {"start": 2114.78, "end": 2118.54, "text": " they down sample it to this resolution,"}, {"start": 2118.54, "end": 2122.7, "text": " and then they crop to 84 by 84 because that was"}, {"start": 2122.7, "end": 2125.14, "text": " a constraint from the network they were using,"}, {"start": 2125.14, "end": 2127.54, "text": " and they were using, if you take a look at this reference"}, {"start": 2127.54, "end": 2130.3799999999997, "text": " 11, that's actually AlexNet, the famous network"}, {"start": 2130.3799999999997, "end": 2135.3799999999997, "text": " that caused the ImageNet moment, and it had the constraint"}, {"start": 2136.8399999999997, "end": 2139.06, "text": " of using only square inputs, that's why they crop"}, {"start": 2139.06, "end": 2140.98, "text": " to a square resolution."}, {"start": 2142.3799999999997, "end": 2144.8999999999996, "text": " The second thing they do is, as I already mentioned,"}, {"start": 2144.8999999999996, "end": 2147.14, "text": " is they take the last four frames of history"}, {"start": 2147.14, "end": 2149.02, "text": " and they stack them together to produce the input"}, {"start": 2149.02, "end": 2150.9399999999996, "text": " to the Q function, and that was the state"}, {"start": 2150.94, "end": 2153.02, "text": " that we were using all along."}, {"start": 2153.02, "end": 2155.42, "text": " Okay, so those were some additional details,"}, {"start": 2155.42, "end": 2160.42, "text": " and now one more thing, I kind of highlighted"}, {"start": 2161.66, "end": 2164.7400000000002, "text": " this eight by eight because AlexNet, back in the days,"}, {"start": 2164.7400000000002, "end": 2169.7400000000002, "text": " they were using much wider kernels compared to,"}, {"start": 2169.82, "end": 2172.58, "text": " and shallower networks compared to today's networks,"}, {"start": 2172.58, "end": 2175.98, "text": " which have kernels that are usually three by three,"}, {"start": 2175.98, "end": 2178.58, "text": " and they are much deeper, especially with the arrival"}, {"start": 2178.58, "end": 2182.02, "text": " of ResNet that allowed us to, using those skip connections"}, {"start": 2182.02, "end": 2185.5, "text": " to have much deeper networks going to 150 and more layers,"}, {"start": 2185.5, "end": 2188.34, "text": " and yeah, that's just kind of thought, it's interesting."}, {"start": 2188.34, "end": 2191.34, "text": " One thing they mentioned here additionally is,"}, {"start": 2191.34, "end": 2193.62, "text": " so the main advantage of this type of architecture"}, {"start": 2193.62, "end": 2195.98, "text": " is to compute the QVLs for all possible actions"}, {"start": 2195.98, "end": 2198.8199999999997, "text": " in a given state with only a single forward pass."}, {"start": 2198.8199999999997, "end": 2203.06, "text": " So imagine if we were actually treating the formulas"}, {"start": 2203.06, "end": 2205.7, "text": " like exactly, so you'd have to do the following thing,"}, {"start": 2205.7, "end": 2208.42, "text": " you'd have a CNN, you'd input a state,"}, {"start": 2208.42, "end": 2212.1, "text": " and you'd input an action, and then you'd get a QVL"}, {"start": 2212.1, "end": 2215.42, "text": " for that action, but then you'd have to do a for loop,"}, {"start": 2215.42, "end": 2218.38, "text": " you just had to kind of iterate this in a for loop"}, {"start": 2218.38, "end": 2221.1, "text": " to get all the QVLs, and you'd be storing them"}, {"start": 2221.1, "end": 2225.46, "text": " somewhere in summary, and so you'd be using additional time,"}, {"start": 2225.46, "end": 2227.0, "text": " you'd be using additional compute,"}, {"start": 2227.0, "end": 2228.7400000000002, "text": " and you'd be using additional memory"}, {"start": 2228.7400000000002, "end": 2231.2200000000003, "text": " if they haven't made it the way they had,"}, {"start": 2231.2200000000003, "end": 2233.54, "text": " and that's just input a single state,"}, {"start": 2233.54, "end": 2236.34, "text": " and you get all of the actions, you get the QVLs"}, {"start": 2236.34, "end": 2238.06, "text": " for all of the actions, and that's how it works."}, {"start": 2238.06, "end": 2241.06, "text": " So that's additional engineering detail, that's kind of fun."}, {"start": 2242.98, "end": 2246.04, "text": " Let's jump to experiments finally."}, {"start": 2246.04, "end": 2247.7799999999997, "text": " Let's see how this thing performed."}, {"start": 2247.7799999999997, "end": 2250.2999999999997, "text": " I already mentioned it kind of surpassed the humans"}, {"start": 2250.2999999999997, "end": 2253.2999999999997, "text": " in some games and many previous methods,"}, {"start": 2253.2999999999997, "end": 2255.98, "text": " so let's see details about that."}, {"start": 2255.98, "end": 2259.02, "text": " Additionally, because some games like Breakout"}, {"start": 2259.02, "end": 2261.62, "text": " or Space Invader, maybe when you kill a spaceship"}, {"start": 2261.62, "end": 2263.72, "text": " in Space Invader, you'd get plus reward,"}, {"start": 2263.72, "end": 2265.66, "text": " where in Pong you get plus one,"}, {"start": 2265.66, "end": 2268.94, "text": " so because these scales differ between the games,"}, {"start": 2268.94, "end": 2270.58, "text": " what it did, and this is again something"}, {"start": 2270.58, "end": 2273.02, "text": " that's Atari specific, so they are not completely"}, {"start": 2273.02, "end": 2276.24, "text": " agnostic to the setup, they are actually clipping it"}, {"start": 2276.24, "end": 2280.2599999999998, "text": " to plus one or minus one, if we get minus seven reward,"}, {"start": 2280.2599999999998, "end": 2281.92, "text": " that would get clipped to minus one,"}, {"start": 2281.92, "end": 2284.2999999999997, "text": " if we get plus three, that would get clipped to plus one,"}, {"start": 2284.2999999999997, "end": 2286.2999999999997, "text": " and that's additional trick they used"}, {"start": 2286.2999999999997, "end": 2288.8599999999997, "text": " to make it more stable and to be able to use"}, {"start": 2288.8599999999997, "end": 2291.8599999999997, "text": " the same set of hyperparams like the learning rate"}, {"start": 2291.86, "end": 2296.02, "text": " for every single one of these games, Atari games."}, {"start": 2296.02, "end": 2299.1800000000003, "text": " Again, one more detail, the epsilon was actually,"}, {"start": 2299.1800000000003, "end": 2301.9, "text": " the epsilon really, the epsilon was annealed linearly"}, {"start": 2301.9, "end": 2306.3, "text": " from one to zero one over the first million frames"}, {"start": 2306.3, "end": 2310.3, "text": " and fixed to 0.1 afterwards, so what that means,"}, {"start": 2311.54, "end": 2313.98, "text": " that means the following, so we have epsilon,"}, {"start": 2313.98, "end": 2318.36, "text": " we have the steps in our RL environment,"}, {"start": 2318.36, "end": 2322.46, "text": " and basically it starts with one and linearly annealed"}, {"start": 2322.46, "end": 2325.1800000000003, "text": " to zero one, and this is one million frames here,"}, {"start": 2325.1800000000003, "end": 2328.86, "text": " and that means we start off being completely random,"}, {"start": 2328.86, "end": 2331.6600000000003, "text": " our policy is completely random, so we'll be picking"}, {"start": 2331.6600000000003, "end": 2334.82, "text": " whatever state comes into the Q network,"}, {"start": 2334.82, "end": 2337.94, "text": " we pick the action without caring which is the max one,"}, {"start": 2337.94, "end": 2340.86, "text": " we just take one action, and that's how we behave,"}, {"start": 2340.86, "end": 2343.2200000000003, "text": " that's how we explore the environment initially,"}, {"start": 2343.2200000000003, "end": 2345.9, "text": " and that's an important concept in RL exploration"}, {"start": 2345.9, "end": 2348.86, "text": " versus exploitation trade-off, and here you can see"}, {"start": 2348.86, "end": 2352.62, "text": " usually the RL algorithm start exploring maximally"}, {"start": 2352.62, "end": 2354.9, "text": " to let it explore the environment and learn"}, {"start": 2354.9, "end": 2357.62, "text": " which states are better by random,"}, {"start": 2357.62, "end": 2360.34, "text": " and then start kind of being more greedy,"}, {"start": 2360.34, "end": 2362.48, "text": " being more deterministic about your actions"}, {"start": 2362.48, "end": 2367.26, "text": " and less sarcastic, and that's, you'll usually see policies"}, {"start": 2367.26, "end": 2370.7000000000003, "text": " like the schedules like this one,"}, {"start": 2370.7000000000003, "end": 2374.84, "text": " and then we'll end up having 0.1 epsilon"}, {"start": 2374.84, "end": 2378.1000000000004, "text": " throughout the rest of the training, that's what I did."}, {"start": 2378.1000000000004, "end": 2381.02, "text": " They also additionally use this frame skipping technique"}, {"start": 2381.02, "end": 2385.42, "text": " which means that, just a simple, again Atari specific thing,"}, {"start": 2385.42, "end": 2388.7000000000003, "text": " they just pick an action for, and then they just repeat"}, {"start": 2388.7000000000003, "end": 2390.5, "text": " the action for the next three steps,"}, {"start": 2391.42, "end": 2393.86, "text": " they're just sending the same action to the emulator,"}, {"start": 2393.86, "end": 2397.1800000000003, "text": " and only after the fourth frame do they actually"}, {"start": 2397.1800000000003, "end": 2400.38, "text": " pick the new action, here they say that they use K4,"}, {"start": 2400.38, "end": 2403.38, "text": " so they actually pick the action every four frames"}, {"start": 2403.38, "end": 2407.34, "text": " that comes from the emulator, except for the Space Invaders"}, {"start": 2407.34, "end": 2410.42, "text": " where they actually notice that the lasers are invisible"}, {"start": 2410.42, "end": 2414.42, "text": " if they take that period, so they actually had to use three,"}, {"start": 2414.42, "end": 2417.7000000000003, "text": " which is again, I think this is the only game specific"}, {"start": 2417.7000000000003, "end": 2422.1400000000003, "text": " detail they actually use, so just, yeah, it's a fun fact."}, {"start": 2422.1400000000003, "end": 2424.6800000000003, "text": " Here I'm not sure whether once they are doing"}, {"start": 2424.6800000000003, "end": 2426.58, "text": " those dummy actions where they're just repeating"}, {"start": 2426.58, "end": 2430.02, "text": " the last intelligent action, where they're actually"}, {"start": 2430.02, "end": 2431.98, "text": " feeding those frames into the state,"}, {"start": 2431.98, "end": 2434.82, "text": " into the circular buffer that has four slots,"}, {"start": 2434.82, "end": 2436.82, "text": " so I'm not sure if they're using these frames"}, {"start": 2436.82, "end": 2439.46, "text": " to fill that up, or they're only using the frames"}, {"start": 2439.46, "end": 2441.9, "text": " that got received from the environment"}, {"start": 2441.9, "end": 2444.18, "text": " when they produce an intelligent action."}, {"start": 2444.18, "end": 2446.58, "text": " So that's just something I'm confused about,"}, {"start": 2446.58, "end": 2450.02, "text": " maybe if you know, write it down in the comments,"}, {"start": 2450.02, "end": 2451.9, "text": " I haven't checked the original implementation,"}, {"start": 2451.9, "end": 2455.34, "text": " I did check some other GISTs and implementations of DQN,"}, {"start": 2455.34, "end": 2456.78, "text": " so I'm familiar how it works."}, {"start": 2458.7, "end": 2461.46, "text": " There is one thing I wanna mention here,"}, {"start": 2461.46, "end": 2463.18, "text": " and this nicely summarizes the difference"}, {"start": 2463.18, "end": 2465.26, "text": " between research and engineering,"}, {"start": 2465.26, "end": 2467.86, "text": " and that's that for this particular Atari game,"}, {"start": 2467.86, "end": 2470.56, "text": " they noticed this thing, so first encode a single frame,"}, {"start": 2470.56, "end": 2473.98, "text": " we take the maximum value for each pixel color value"}, {"start": 2473.98, "end": 2476.92, "text": " of the frame being encoded and the previous frame."}, {"start": 2476.92, "end": 2479.28, "text": " This was necessary to remove flickering"}, {"start": 2479.28, "end": 2482.3, "text": " that is present in games where some objects appear"}, {"start": 2482.3, "end": 2484.94, "text": " only in even frames, while other objects appear"}, {"start": 2484.94, "end": 2486.54, "text": " only in odd frames."}, {"start": 2486.54, "end": 2489.34, "text": " An artifact caused by the limited number of sprites"}, {"start": 2489.34, "end": 2494.02, "text": " in Atari 2600 that can display at once."}, {"start": 2494.02, "end": 2497.9, "text": " So this is totally not important for this research paper"}, {"start": 2497.9, "end": 2499.54, "text": " and for you understanding this paper,"}, {"start": 2499.54, "end": 2502.1000000000004, "text": " but it is important to understand"}, {"start": 2502.1000000000004, "end": 2505.6200000000003, "text": " that there are so many details that you actually understand"}, {"start": 2505.6200000000003, "end": 2507.58, "text": " when you start implementing the thing."}, {"start": 2507.58, "end": 2510.34, "text": " So reading research is really nice and everything,"}, {"start": 2510.34, "end": 2514.06, "text": " but until you start looking at the actual code"}, {"start": 2514.06, "end": 2517.0, "text": " and try to implement it, you probably first don't understand"}, {"start": 2517.0, "end": 2519.42, "text": " the actual theory, and secondly, you don't understand"}, {"start": 2519.42, "end": 2521.9, "text": " all of the pain points to actually make this work"}, {"start": 2521.9, "end": 2524.82, "text": " in a real world product."}, {"start": 2524.82, "end": 2526.14, "text": " So just something I want to mention."}, {"start": 2526.14, "end": 2530.38, "text": " And also, what I found useful is, for example,"}, {"start": 2530.38, "end": 2533.48, "text": " when I read this DQM paper the first time,"}, {"start": 2533.48, "end": 2537.42, "text": " I just found some gists and I went through the code"}, {"start": 2537.42, "end": 2539.6, "text": " and that made it much less abstract"}, {"start": 2539.6, "end": 2541.56, "text": " and clear how it works."}, {"start": 2541.56, "end": 2546.28, "text": " So I kinda suggest that you, aside from reading papers,"}, {"start": 2546.28, "end": 2549.94, "text": " maybe consult some code, and that's a good nice trade-off"}, {"start": 2549.94, "end": 2553.1000000000004, "text": " to understand the research better."}, {"start": 2553.1000000000004, "end": 2555.5, "text": " And that's somewhere like half the way"}, {"start": 2555.5, "end": 2558.38, "text": " between you actually implementing the project"}, {"start": 2558.38, "end": 2561.26, "text": " and you not seeing any code whatsoever."}, {"start": 2561.26, "end": 2563.0600000000004, "text": " So yeah, that was a small digression."}, {"start": 2563.0600000000004, "end": 2565.1400000000003, "text": " Hopefully it was useful for some of you."}, {"start": 2565.1400000000003, "end": 2567.6200000000003, "text": " Let me know if this was useful in the comments,"}, {"start": 2567.6200000000003, "end": 2570.3, "text": " things like this or whether this just distracts you."}, {"start": 2571.7200000000003, "end": 2572.78, "text": " Okay, let's continue."}, {"start": 2572.78, "end": 2577.78, "text": " Let us see how the agent progresses during the training."}, {"start": 2577.94, "end": 2580.78, "text": " Basically, here you can see that the rewards,"}, {"start": 2580.78, "end": 2583.1000000000004, "text": " so here we can see the training epochs,"}, {"start": 2583.1000000000004, "end": 2585.2200000000003, "text": " so and here we can see the average reward"}, {"start": 2585.2200000000003, "end": 2586.46, "text": " that the agent is receiving,"}, {"start": 2586.46, "end": 2590.02, "text": " and we can see on the breakout game an upward trend,"}, {"start": 2590.02, "end": 2593.1400000000003, "text": " so that means that the agent is learning better policies"}, {"start": 2593.1400000000003, "end": 2596.84, "text": " and better action values or Q values."}, {"start": 2597.86, "end": 2601.26, "text": " So basically, on the Sequest, we can see the same trend."}, {"start": 2601.26, "end": 2603.82, "text": " There is a lot of noise, but still the trend"}, {"start": 2603.82, "end": 2605.6600000000003, "text": " is kind of upward, so yeah."}, {"start": 2606.5200000000004, "end": 2609.28, "text": " A better metric they used is this,"}, {"start": 2609.28, "end": 2611.3, "text": " the average Q on breakout"}, {"start": 2611.3, "end": 2614.6200000000003, "text": " and the average Q on whatever game there may be."}, {"start": 2614.6200000000003, "end": 2615.9, "text": " And you can see that that one"}, {"start": 2615.9, "end": 2618.1400000000003, "text": " is pretty much monotonically increasing"}, {"start": 2618.1400000000003, "end": 2623.1400000000003, "text": " and has less noise than these ones here."}, {"start": 2623.2200000000003, "end": 2625.0600000000004, "text": " And let me just explain to you"}, {"start": 2625.0600000000004, "end": 2627.84, "text": " how they actually calculate that one."}, {"start": 2627.84, "end": 2631.0200000000004, "text": " So we collect a fixed set of states"}, {"start": 2631.02, "end": 2634.46, "text": " by running a random policy before training even starts,"}, {"start": 2634.46, "end": 2637.06, "text": " and they track the average of the maximum"}, {"start": 2637.06, "end": 2639.22, "text": " predicted Q values for these states."}, {"start": 2639.22, "end": 2641.42, "text": " So that looks the following."}, {"start": 2641.42, "end": 2643.52, "text": " Basically, before the training even starts,"}, {"start": 2643.52, "end": 2646.96, "text": " before the agent starts learning, they do the following."}, {"start": 2646.96, "end": 2651.96, "text": " So we can represent the environment and the game as an MDP,"}, {"start": 2652.58, "end": 2655.88, "text": " and I didn't explain quite what MDP is,"}, {"start": 2655.88, "end": 2659.58, "text": " but for now, you can imagine it as a bunch of states"}, {"start": 2659.58, "end": 2662.7599999999998, "text": " and you can transition and you can receive rewards,"}, {"start": 2662.7599999999998, "end": 2664.7, "text": " and yeah, that's the formalism."}, {"start": 2664.7, "end": 2668.66, "text": " But basically what they did is they took a couple of states,"}, {"start": 2668.66, "end": 2670.98, "text": " and those are those four frame tuples, remember?"}, {"start": 2670.98, "end": 2672.84, "text": " So they took a couple of these,"}, {"start": 2672.84, "end": 2675.38, "text": " and they just stored them into some memory,"}, {"start": 2675.38, "end": 2677.3199999999997, "text": " and basically later on,"}, {"start": 2677.3199999999997, "end": 2679.24, "text": " while the agent is actually learning,"}, {"start": 2679.24, "end": 2681.88, "text": " they just pass these specific values."}, {"start": 2681.88, "end": 2684.08, "text": " So let's call this one, let's call this two."}, {"start": 2684.08, "end": 2686.64, "text": " They'll just feed it through the CNN,"}, {"start": 2686.64, "end": 2691.64, "text": " and they'll find the max Q value for this state,"}, {"start": 2691.8599999999997, "end": 2693.2599999999998, "text": " max Q value for this state,"}, {"start": 2693.2599999999998, "end": 2695.8199999999997, "text": " and they're just gonna be accumulating these,"}, {"start": 2695.8199999999997, "end": 2697.42, "text": " like summing them up and then averaging"}, {"start": 2697.42, "end": 2698.62, "text": " by the number of states,"}, {"start": 2698.62, "end": 2700.8199999999997, "text": " i.e. they are gonna keep the average"}, {"start": 2700.8199999999997, "end": 2703.3799999999997, "text": " of the max Q values for these states."}, {"start": 2703.3799999999997, "end": 2705.4, "text": " And that's the metric they were using here,"}, {"start": 2705.4, "end": 2707.3799999999997, "text": " and it proved to be much more stable"}, {"start": 2707.3799999999997, "end": 2709.54, "text": " and better to keep track of the learning progress"}, {"start": 2709.54, "end": 2710.3799999999997, "text": " of the agent."}, {"start": 2711.94, "end": 2715.06, "text": " Okay, those are the curves."}, {"start": 2715.06, "end": 2719.14, "text": " Here, once you actually train the agent,"}, {"start": 2719.14, "end": 2720.94, "text": " you can see interesting behavior,"}, {"start": 2720.94, "end": 2722.5, "text": " and here you can see the following."}, {"start": 2722.5, "end": 2725.74, "text": " So here you can see that that's our ship"}, {"start": 2725.74, "end": 2727.42, "text": " that we're controlling, that's the agent."}, {"start": 2727.42, "end": 2729.2599999999998, "text": " The algorithm is controlling the ship,"}, {"start": 2729.2599999999998, "end": 2731.7, "text": " and once the enemy ship enters the screen,"}, {"start": 2731.7, "end": 2732.7, "text": " that's the point A,"}, {"start": 2732.7, "end": 2735.38, "text": " and you can see that the Q value increases,"}, {"start": 2735.38, "end": 2737.5, "text": " because we're expecting reward"}, {"start": 2737.5, "end": 2739.18, "text": " once we kill the enemy spaceship,"}, {"start": 2739.18, "end": 2741.38, "text": " we're gonna see an increase in score,"}, {"start": 2741.38, "end": 2744.86, "text": " and the Q value correctly anticipates"}, {"start": 2744.86, "end": 2748.3, "text": " that score increase, and then has a spike."}, {"start": 2748.3, "end": 2751.6200000000003, "text": " And then you can see once the torpedo is shot,"}, {"start": 2751.6200000000003, "end": 2754.3, "text": " and we are really close to killing the enemy ship,"}, {"start": 2754.3, "end": 2757.54, "text": " we're at point B, where we expect a huge reward,"}, {"start": 2757.54, "end": 2759.42, "text": " and once we actually kill the ship"}, {"start": 2759.42, "end": 2762.48, "text": " and we enter in this state here,"}, {"start": 2762.48, "end": 2766.58, "text": " the value drops, and it drops because it only expects"}, {"start": 2766.58, "end": 2768.1400000000003, "text": " the future rewards."}, {"start": 2768.1400000000003, "end": 2769.78, "text": " So we just received a huge reward,"}, {"start": 2769.78, "end": 2771.58, "text": " and that's why we dipped."}, {"start": 2771.58, "end": 2773.1800000000003, "text": " So you can see that it's really meaningful"}, {"start": 2773.1800000000003, "end": 2774.6600000000003, "text": " for this specific scenario,"}, {"start": 2774.66, "end": 2776.2599999999998, "text": " and it makes a lot of sense."}, {"start": 2777.8599999999997, "end": 2780.94, "text": " That was another interesting thing"}, {"start": 2780.94, "end": 2781.94, "text": " that I wanted to mention,"}, {"start": 2781.94, "end": 2784.1, "text": " and here is one additional detail."}, {"start": 2784.1, "end": 2786.7799999999997, "text": " So in addition to seeing relatively smooth improvements"}, {"start": 2786.7799999999997, "end": 2789.02, "text": " to predicted Q during training,"}, {"start": 2789.02, "end": 2791.66, "text": " we did not experience any divergence issues"}, {"start": 2791.66, "end": 2793.22, "text": " in any of the experiments,"}, {"start": 2793.22, "end": 2796.94, "text": " so despite lacking any theoretical convergence guarantees,"}, {"start": 2796.94, "end": 2799.18, "text": " the method is able to train the network"}, {"start": 2799.18, "end": 2801.14, "text": " with RL algorithm signal,"}, {"start": 2801.14, "end": 2804.14, "text": " and gradient descent in a stable manner."}, {"start": 2804.14, "end": 2807.22, "text": " So again, small discrepancy between the theory"}, {"start": 2807.22, "end": 2809.94, "text": " and the engineering or the practice."}, {"start": 2809.94, "end": 2811.58, "text": " Sometimes things just work,"}, {"start": 2811.58, "end": 2813.62, "text": " and later a couple of years down the road,"}, {"start": 2813.62, "end": 2816.8199999999997, "text": " somebody figures out why this was working,"}, {"start": 2816.8199999999997, "end": 2819.98, "text": " or yeah, but yeah, sometimes, a lot of times,"}, {"start": 2819.98, "end": 2824.06, "text": " the engineering and the technology is way in front"}, {"start": 2824.06, "end": 2827.62, "text": " of the actual research and theoretical understanding."}, {"start": 2827.62, "end": 2830.42, "text": " That's my honest opinion about this."}, {"start": 2830.42, "end": 2833.6, "text": " You can disagree, and I'd love to hear your comments on that."}, {"start": 2833.6, "end": 2834.44, "text": " Yeah."}, {"start": 2836.42, "end": 2839.38, "text": " So results are here."}, {"start": 2839.38, "end": 2844.38, "text": " DQN kinda destroyed every single other baseline."}, {"start": 2844.62, "end": 2845.74, "text": " So this is the random policy."}, {"start": 2845.74, "end": 2847.42, "text": " If you just play it random,"}, {"start": 2847.42, "end": 2848.7799999999997, "text": " if you play the game at random,"}, {"start": 2848.7799999999997, "end": 2850.58, "text": " these are the scores you get."}, {"start": 2850.58, "end": 2854.38, "text": " SARSA, it's an online algorithm similar to Q-learning."}, {"start": 2854.38, "end": 2855.94, "text": " I won't get into the details."}, {"start": 2855.94, "end": 2857.94, "text": " Contingency, again, very similar,"}, {"start": 2857.94, "end": 2861.02, "text": " and you can see usually Q-learning has better results,"}, {"start": 2861.02, "end": 2863.46, "text": " and DQN has much better results,"}, {"start": 2863.46, "end": 2864.82, "text": " and all of those baselines,"}, {"start": 2864.82, "end": 2867.18, "text": " and it's actually even better than humans in some games,"}, {"start": 2867.18, "end": 2870.48, "text": " like here on Breakout, Enduro, and Pong."}, {"start": 2870.48, "end": 2871.98, "text": " It's actually better than the human,"}, {"start": 2871.98, "end": 2874.2200000000003, "text": " and that's kinda interesting,"}, {"start": 2874.2200000000003, "end": 2877.98, "text": " and the scores here, how they got these are,"}, {"start": 2877.98, "end": 2880.2, "text": " so they just took some human,"}, {"start": 2881.1, "end": 2883.34, "text": " and that guy, that poor guy or girl,"}, {"start": 2883.34, "end": 2886.18, "text": " they were just playing the game for two hours,"}, {"start": 2886.18, "end": 2889.86, "text": " and once the two hours are done,"}, {"start": 2889.86, "end": 2892.08, "text": " they just take the scores that they achieved,"}, {"start": 2892.08, "end": 2894.8199999999997, "text": " they sort them, and they find the middle one,"}, {"start": 2894.8199999999997, "end": 2898.98, "text": " that's the median or the 50th percentile,"}, {"start": 2898.98, "end": 2901.98, "text": " and that's the score they publish here,"}, {"start": 2901.98, "end": 2903.38, "text": " and you can see that, yeah,"}, {"start": 2903.38, "end": 2906.18, "text": " in some cases, DQN achieved better results."}, {"start": 2906.18, "end": 2908.02, "text": " So one important thing to mention here"}, {"start": 2908.02, "end": 2910.86, "text": " is that in their subsequent paper"}, {"start": 2910.86, "end": 2913.34, "text": " that were published in Nature in 2015,"}, {"start": 2913.34, "end": 2916.2799999999997, "text": " they actually played on all the 57 Atari games,"}, {"start": 2916.2799999999997, "end": 2917.7799999999997, "text": " and they achieved impressive results"}, {"start": 2917.7799999999997, "end": 2919.8199999999997, "text": " where they were actually better than humans"}, {"start": 2919.82, "end": 2924.5800000000004, "text": " on 29 out of 57 games,"}, {"start": 2924.5800000000004, "end": 2927.5800000000004, "text": " and that's, yeah, quite impressive,"}, {"start": 2927.5800000000004, "end": 2929.7400000000002, "text": " especially back in 2015."}, {"start": 2929.7400000000002, "end": 2933.1200000000003, "text": " Now we have some improvements like Agent 57,"}, {"start": 2934.1800000000003, "end": 2935.7000000000003, "text": " and some other algorithms,"}, {"start": 2935.7000000000003, "end": 2938.1200000000003, "text": " and I'll be covering those in the subsequent videos,"}, {"start": 2938.1200000000003, "end": 2939.9, "text": " so yeah, stay tuned,"}, {"start": 2939.9, "end": 2942.1400000000003, "text": " but the interesting thing you can notice here"}, {"start": 2942.1400000000003, "end": 2946.1000000000004, "text": " is that all of the games that require fast reflexes,"}, {"start": 2946.1, "end": 2951.1, "text": " like boxing, like Pong, are much easier"}, {"start": 2951.22, "end": 2953.46, "text": " for our agents to learn how to play"}, {"start": 2953.46, "end": 2955.7, "text": " than some games like Montezuma's Revenge,"}, {"start": 2955.7, "end": 2957.58, "text": " it's a really famous game."}, {"start": 2957.58, "end": 2960.38, "text": " It's a tough one, you need to play it"}, {"start": 2960.38, "end": 2962.24, "text": " to understand why I'm saying this."}, {"start": 2962.24, "end": 2964.66, "text": " It requires a lot more strategy than Pong"}, {"start": 2964.66, "end": 2966.5, "text": " or Breakout or those other games,"}, {"start": 2966.5, "end": 2970.46, "text": " and that's why you can see we have actually zero score here,"}, {"start": 2970.46, "end": 2973.36, "text": " so the algorithm cannot, DQN cannot learn"}, {"start": 2973.36, "end": 2974.42, "text": " in this vanilla form,"}, {"start": 2974.42, "end": 2976.78, "text": " cannot learn to play this game at all."}, {"start": 2976.78, "end": 2978.9, "text": " So that was just some fun fact,"}, {"start": 2978.9, "end": 2980.1, "text": " and as I mentioned,"}, {"start": 2980.1, "end": 2982.94, "text": " so this Qbert, Sequest, and Space Invaders,"}, {"start": 2982.94, "end": 2985.1800000000003, "text": " so those are these three games,"}, {"start": 2985.1800000000003, "end": 2988.82, "text": " you can see that results are really poor"}, {"start": 2988.82, "end": 2990.82, "text": " compared to humans,"}, {"start": 2990.82, "end": 2993.1800000000003, "text": " and the reason is that they're challenging"}, {"start": 2993.1800000000003, "end": 2995.1, "text": " because they require us to find a strategy"}, {"start": 2995.1, "end": 2997.26, "text": " that extends over long time scales,"}, {"start": 2997.26, "end": 2999.46, "text": " and that's something that if you're familiar"}, {"start": 2999.46, "end": 3001.82, "text": " with any other field like NLP,"}, {"start": 3001.82, "end": 3004.06, "text": " when you're dealing with long sequences,"}, {"start": 3004.06, "end": 3007.18, "text": " you're gonna end up having problems,"}, {"start": 3007.18, "end": 3009.18, "text": " catastrophic forgetting whatever,"}, {"start": 3009.18, "end": 3011.02, "text": " the problems that RNN's had,"}, {"start": 3011.02, "end": 3013.9, "text": " and then LSTM's kind of solved, and Transformers,"}, {"start": 3013.9, "end": 3016.86, "text": " so yeah, that's the reason they,"}, {"start": 3016.86, "end": 3019.48, "text": " you can basically just by analyzing the game"}, {"start": 3019.48, "end": 3021.2999999999997, "text": " kind of get an intuition why the algorithm"}, {"start": 3021.2999999999997, "end": 3022.7799999999997, "text": " is failing on specific games."}, {"start": 3023.68, "end": 3024.74, "text": " And that's pretty much it,"}, {"start": 3024.74, "end": 3026.46, "text": " these are just some references,"}, {"start": 3026.46, "end": 3029.54, "text": " I think I've covered it pretty detailed."}, {"start": 3029.54, "end": 3032.06, "text": " Hopefully if you stuck with me until the end of the video,"}, {"start": 3032.06, "end": 3034.42, "text": " I'd love to hear your thoughts,"}, {"start": 3034.42, "end": 3036.94, "text": " did you like this one better than the last ones,"}, {"start": 3036.94, "end": 3040.98, "text": " and if you have any tips on how to improve this further,"}, {"start": 3040.98, "end": 3042.2999999999997, "text": " feel free to comment down below,"}, {"start": 3042.2999999999997, "end": 3044.7, "text": " I'll try to answer ASAP,"}, {"start": 3044.7, "end": 3047.14, "text": " so until next time, you know the drill,"}, {"start": 3047.14, "end": 3051.14, "text": " hit that bell icon, subscribe, and share the good word,"}, {"start": 3051.14, "end": 3053.04, "text": " and see you in the next video,"}, {"start": 3053.04, "end": 3054.9, "text": " until then, keep learning deep."}, {"start": 3054.9, "end": 3063.7400000000002, "text": " Yeah."}]