Stanford's Gammelli Details How Deep Q-Networks Tame Moving Targets

斯坦福Gammelli解析Deep Q-Networks如何应对移动目标 在强化学习中，除非通过经验回放与解耦的目标网络消除时间数据相关性及非平稳的贝尔曼回归目标，否则神经网络价值逼近将会崩溃。 Daniele Gammelli博士深入探讨了基于价值的无模型强化学习，从广义策略迭代中蒙特卡洛评估向时序差分（TD）控制的转变讲起。他对比了同策略SARSA与异策略Q-learning，并在Windy Gridworld和Cliff Walking等基准环境中展示了它们各自不同的安全裕度与训练动态。随后，讲座通过将价值函数逼近构建为监督回归目标来应对维度灾难。最后，讲座探讨了深度Q网络（DQN），阐明了经验回放与解耦的目标网络如何解决轨迹数据的相关性以及训练目标移动的问题。 时序差分学习将蒙特卡洛方法的采样机制与动态规划的自举原理相结合，无需终止状态即可实现在线无模型控制。 (2:52) SARSA与Q-learning在策略对齐方式上存在差异：SARSA属于同策略方法，通过评估其实际的探索性行为策略运行；而Q-learning属于异策略方法，通过向最优贪婪目标策略自举运行。 (25:42) 组合状态空间（例如围棋约10^170种状态布局）因内存限制和缺乏泛化能力会导致表格型强化学习失效，从而必须采用参数化函数逼近器。 (45:57) 深度Q网络通过利用经验回放消除转移样本间的相关性，并利用目标网络稳定非平稳贝尔曼目标，解决了强化学习中在线神经网络回归的两个主要失效模式。 (68:15)

Dr. Daniele Gammelli frames value-based reinforcement learning as a systematic evolution from exact dynamic programming to model-free sampling and deep function approximation. The lecture establishes how temporal difference learning resolves horizon and variance bottlenecks, contrasts the behavioral implications of on-policy versus off-policy control, and details the algorithmic stabilization techniques required to train deep Q-networks. Sampling and Bootstrapping: DP to TD (2:52) Exact dynamic programming relies on Bellman's principle of optimality to collapse infinite horizons into single-step calculations, but it strictly requires complete knowledge of transition dynamics. When transitions cannot be computed analytically, Monte Carlo methods bypass model requirements by sampling complete trajectories to terminal states; however, this episodic requirement introduces high variance and fails on continuing or cyclic tasks where episodes never terminate. Temporal difference (TD) learning bridges these paradigms by combining Monte Carlo sampling with dynamic programming bootstrapping, updating value estimates incrementally after a single transition target. On-Policy Versus Off-Policy: SARSA and Q-Learning Within Generalized Policy Iteration, SARSA and Q-learning implement TD control through fundamentally different policy couplings. SARSA operates strictly on-policy by using the transition quintuple $(S_t, A_t, R_{t+1}, S_{t+1}, A_{t+1})$ to update action-values against the same exploratory $\epsilon$-greedy policy executing the behavior. In contrast, Q-learning is off-policy: it allows an agent to gather transitions under an exploratory behavior policy $\mu$ while evaluating a deterministic greedy target policy using the Bellman optimality operator, collapsing successor evaluation into a direct maximum over actions. This structural divide yields divergent behaviors in the Cliff Walking benchmark. Under a fixed exploration rate $\epsilon$, SARSA internalizes its ongoing behavioral stochasticity and converges to a risk-averse path far from the cliff edge to avoid catastrophic $-100$ penalties. Q-learning evaluates the optimal deterministic path hugging the precipice. While Q-learning logs lower cumulative reward during online training due to occasional random exploratory falls, its underlying target policy provably converges to the true optimal return. Function Approximation for High-Dimensional State Spaces (45:57) Tabular representations fail in vast state spaces—such as the game of Go with approximately $10^{170}$ legal configurations—due to computer memory limits and the inability to generalize to unvisited states. Parametric function approximation replaces lookup tables with models parameterized by weights $\theta$, enabling spatial generalization across topologically related states. For discrete action spaces, Dr. Gammelli highlights an architecture that takes a state as input and outputs a vector of Q-values across all discrete actions, allowing greedy policy selection in a single forward pass rather than querying the network once per action. Value approximation adapts to supervised mean squared error regression, but replacing the unknown true policy value with empirical targets introduces unique challenges. In Fitted Q-Iteration, using one-step bootstrapped TD targets creates a non-stationary regression problem because the optimization target shifts whenever the parameters $\theta$ update. Stabilizing Deep Q-Networks: Replay and Target Decoupling (68:15) Deep Q-Networks (DQN) process high-dimensional inputs, such as raw Atari video frames, through convolutional neural networks to output action values, but standard gradient descent destabilizes when applied to online reinforcement learning. Continuous environment interactions produce sequential transitions that violate the independent and identically distributed (IID) data assumption of statistical learning, while computing TD targets from actively updating weights leads to moving-target feedback loops and policy divergence. DQN stabilizes training through two core innovations. Experience replay stores transitions in a large memory buffer and samples mini-batches uniformly at random, breaking temporal correlations to mimic an IID data-generating process. Decoupled target networks maintain a separate parameter set $\phi$ to hold the TD target stationary. These target weights are updated either through periodic hard updates matching the online network every $C$ steps, or through smooth Polyak averaging maintaining an exponential moving average ($\phi \leftarrow \tau \theta + (1 - \tau) \phi$ with $\tau \ll 1$). The presentation concludes that value-based methods successfully scale from small tabular tasks to complex environments by combining bootstrapping, off-policy targets, and stability mechanisms. Dr. Gammelli notes that upcoming lectures shift the course focus from value-based algorithms toward model-free policy optimization and model-based optimal control frameworks.

[6:31] Dr. Daniele Gammelli: carve out a better policy out of it [20:03] Dr. Daniele Gammelli: the magic of the TD backup start to happen [20:03] Dr. Daniele Gammelli: positivity and the goodness of our decisions [39:52] Dr. Daniele Gammelli: learning the best version of its kind of exploratory policy [53:30] Dr. Daniele Gammelli: n queries where n could be very high [53:30] Dr. Daniele Gammelli: creativity is king [58:31] Dr. Daniele Gammelli: kind of a chicken and egg... problem because we're saying we want to minimize the error between our prediction and our true value function, but we don't have the true value function [58:31] Dr. Daniele Gammelli: one of the key engineering breakthroughs

[0:05] OK, and so getting to this week's end today's [0:10] lecture, so from a user roadmap, over the last few weeks, [0:14] we started looking at modern ways [0:16] to approach learning-based control. [0:18] We started from imitation learning where the idea there [0:21] was to learn to mimic the behavior of an expert. [0:25] And then last week we started to introduce [0:26] reinforcement learning, which is this idea of learning [0:29] through trial and error. [0:30] And specifically, we introduce some foundational [0:33] learning mechanisms to do so. [0:35] And starting today and for the next lectures, for the remaining [0:39] lectures of this class, we'll be looking [0:41] at specific categories of algorithms, [0:43] today starting from value based methods [0:45] that belong to the category of model-free reinforcement [0:48] learning methods. [0:51] So briefly mention a couple of amazing references. [0:54] Of course, you all know probably Sutton and Barto's textbooks [0:57] on reinforcement learning but also discourse [1:00] by David Silver, which is great. [1:02] And also some of the slides today [1:04] are indeed inspired by that course. [1:08] So to briefly pick up what we were saying last week, [1:14] so remember that in previous lectures, [1:16] we basically started to make the distinction between what [1:20] we refer to as prediction, whereby given a policy that [1:24] was given to us we wanted to estimate [1:27] the value for that policy and control, whereby the goal which [1:32] is actually what we deeply care about, [1:34] is to learn the policy that optimizes [1:36] some measure of performance. [1:38] And specifically, we started looking at algorithms motivated [1:43] by dynamic programming, which we refer [1:45] to as exact methods, specifically policy iteration [1:48] and value iterations as ways to solve Markov decision [1:52] processes, which is indeed the mathematical formalism we [1:56] are using also for reinforcement training. [1:59] And we also highlighted how these models, [2:02] despite being great at solving Markov decision processes, [2:05] had one main limitation, which is the one that in order [2:08] to use them, we assumed we have a perfect knowledge [2:11] of the system dynamics. [2:12] Specifically, we have knowledge of the transition function, [2:16] t, which is the probability of going in state xt plus 1 [2:19] given in state xt given action, ut. [2:24] And so, basically, last time last week [2:27] we started to introduce two really fundamental learning [2:31] paradigms to which really encompass [2:33] this idea of reinforcement learning [2:35] which is learning from interaction. [2:36] So we don't have access to a dynamical model. [2:39] We want to learn without it through interactions [2:42] from the environment. [2:43] And we saw specifically Monte Carlo learning [2:45] and temporal difference learning as two key instantiations [2:48] of these learning paradigms. [2:52] We started building out, even visually, [2:55] a mental map of different approaches [2:57] to learning from interaction, whereby [2:59] we were looking at these diagrams which essentially [3:03] represent rollouts in our environments. [3:05] So if you recall, in these diagrams, [3:07] white nodes represent states and black nodes [3:10] represent possible actions that we could [3:11] take in that specific state. [3:13] And so these basically visualize this idea [3:17] of the possible futures that we could have in our environment. [3:20] And ideally, when we look at estimating [3:22] the value of a state given a policy, [3:26] we are potentially ultimately interested [3:28] in estimating the expected value of all the leaves [3:32] in our possible rollouts. [3:33] So this is the actual quantity that we're [3:35] interested in estimating. [3:37] Of course, one way assuming we have infinite compute [3:41] would be to just simulate our environment infinitely [3:45] many times forward, collect the actual expectations of all [3:49] of our leaf nodes, and estimate the values like this. [3:53] But then we saw how dynamic programming gave us [3:56] through the principle of optimality [3:57] gave us a practical way of approximating and calculating, [4:01] actually, these values through basically a one step calculation [4:08] whereby the value of a given state [4:11] was essentially defined as the expectation of the reward [4:15] that we observe in the one step transition [4:17] plus the discounted future value at our next state. [4:21] The catch here is that to compute those expectations [4:24] exactly, we needed the knowledge of the transition function [4:27] or our dynamics. [4:29] And so this is where Monte Carlo and temporal difference learning [4:31] came in place, whereby we used sampling, that is, [4:35] we simulated some rollouts in our environment. [4:38] And in Monte Carlo, we update our guess of our value function [4:43] by taking a step in the direction of the return, gt, [4:48] where we calculate this gt simply [4:50] by having a rollout in our environment [4:53] until we reach a terminal state and summing up [4:56] all of the rewards that we observed in this rollout. [5:00] In td, on the other hand, we define the target [5:06] by basically getting leveraging ideas from both Monte Carlo, [5:10] that is, the sampling and dynamic programming, [5:12] that is the bootstrapping, by defining [5:14] the target as this one step estimate of the final return. [5:21] And so we saw how compared to dynamic programming, which [5:25] has no need to sample because we have the underlying dynamics, [5:28] Monte Carlo and temporal difference learning both sample [5:31] because we do have interactions in our environment. [5:34] And we saw how TD and dynamic programming [5:39] bootstrap because they guess towards another guess, which [5:42] is our estimate at the next time step, t plus 1. [5:46] Well, Monte Carlo does not bootstrap because it actually [5:48] rolls out until the end of the episode. [5:53] Of course, we introduced everything [5:56] in this slide for the purpose of estimating value functions [5:58] or state value functions, v. But everything that we just said [6:01] holds equally for state action value functions or Q functions. [6:07] For control-- yes. [6:10] In Monte Carlo you always have to go to a terminal state [6:13] or is there any where you go and you take five steps [6:16] and then reevaluate? [6:17] For Monte Carlo, you always need to reach a terminal state, which [6:20] is indeed, if you wish, one of the limitations of Monte Carlo. [6:23] But we discussed trade offs between bias and variance [6:26] of these estimators. [6:31] But so this is great for the purpose of prediction. [6:34] That is estimating values given a policy. [6:36] But what we actually care about is [6:38] finding those optimal policies themselves. [6:40] So we care about control. [6:42] And so we discussed a general paradigm [6:45] for control, which is one of generalized policy [6:50] iteration, whereby the main idea here [6:53] is that we are alternating between two different processes. [6:56] So we're given a arbitrarily initialized value [6:59] function and a policy. [7:01] And we alternate between policy evaluation step. [7:04] That is, given the policy, we estimate the value function [7:07] of that policy and a policy improvement step, [7:10] which, given the updated value function, [7:13] kind of uses it to carve out a better policy out of it. [7:17] And by iterating through these two processes, [7:19] we hopefully converge to the optimal value [7:21] function and associated policy. [7:24] Specifically, we saw kind of a v0 version of a working control [7:29] algorithm, which we refer to as Monte Carlo control, which [7:33] is basically alternating between two specific instantiations [7:36] of the policy evaluation process and the policy improvement [7:40] process. [7:41] For policy evaluation, we are essentially using a Monte Carlo [7:45] estimate of a Q function. [7:48] Well, for policy improvement, we assume [7:50] to do an epsilon greedy policy, if you recall. [7:53] So again, we saw this general formalism. [7:56] And then we had a v0 RL algorithm [7:59] which we denoted as Monte Carlo control where [8:01] we had two specific instantiations of policy [8:04] evaluation and policy improvement. [8:11] So today what we will essentially be doing [8:14] is we'll be building on top of these concepts [8:17] by, first of all, introducing two very popular algorithms [8:23] like falling between the family of value-based methods, which [8:25] is Sarsa and Q-learning. [8:28] We'll use the discussion on these two algorithms [8:30] to deep dive and explore it a bit more [8:33] in depth the difference between on-policy and off-policy [8:35] algorithms. [8:36] We'll see more shortly. [8:39] And then we'll introduce value function approximation as a way [8:42] to scale these algorithms to higher dimensional state [8:45] and action spaces. [8:47] And we'll conclude with a brief mentions [8:50] to some deep reinforcement learning [8:52] methods and applications. [8:58] All good with the plan? [9:01] Nice. [9:03] OK, so we basically discussed Monte Carlo and TD learning. [9:09] And last week we mentioned how temporal difference learning [9:13] essentially has, if you wish, several advantages over Monte [9:16] Carlo learning to some extent. [9:19] The first one is that we saw how TD learning is a lower variance [9:23] estimate of the ground truth return. [9:26] So remember that we were making this even visual distinction [9:29] whereby assuming we have a rollout in our environment [9:34] until we reach some terminal state at time t. [9:42] In Monte Carlo, to estimate the expected return for our policy, [9:47] we would essentially be rolling out the entire episode [9:52] until we are able to compute our target return, gt, [9:56] which is simply the discounted sum of all the rewards [10:01] that we observed over time. [10:06] And we saw how this target, which in Monte Carlo [10:09] is simply the return. [10:10] For TD, we basically used the kind of a dynamic programming [10:16] estimate whereby our target becomes [10:20] the instantaneous reward plus the discounted future value. [10:26] And we last time we basically highlighted the fact [10:28] that by looking at the amount of stochasticity that is involved, [10:33] TD learning is a lower variance estimator because it simply put, [10:36] we're sampling only once while in Monte Carlo in order [10:39] to estimate all the way down here in our episode [10:42] we would have to account for the added stochasticity that [10:46] comes by sampling in our environment [10:49] further along the way, essentially. [10:53] Not only that, we also discussed that since in TD learning we [10:56] are working with one step updates, [10:59] we can use this update online. [11:02] That is, as we progress in our rollout, [11:05] we could keep updating our estimates of the value function. [11:08] And because we don't need a terminal episode, [11:13] we can work with incomplete sequences, essentially. [11:17] So long story short, we have a number of advantages [11:22] from TD learning. [11:23] So kind of a natural idea would be, [11:27] why don't we just replace in our Monte Carlo control algorithm? [11:32] That is our v0 RL algorithm TD learning where we previously [11:37] had Monte Carlo learning of our Q function. [11:45] And basically, this is essentially [11:48] the step that leads us from our Monte Carlo control algorithm [11:51] to what is known as Sarsa. [11:54] So let us look a little bit more closely [11:57] at what it means to update action value functions or Q [12:00] functions within this algorithm known as Sarsa. [12:04] So specifically, we referred before [12:06] to the temporal difference backup [12:08] as updating our guess of our value function [12:11] by taking a step towards the TD target. [12:16] Of course, this holds for value functions, v, but equally for Q [12:21] functions in the same way. [12:24] Of course, the moment we want to define this TD backup for Q [12:28] functions, we need a few specific elements, [12:32] which are essentially we need the current state and control, [12:37] xt and ut. [12:39] We need the reward that are obtained from those by taking [12:42] that control on that state. [12:44] And then we need the future state, xt, [12:46] and the future control that we take at t plus 1. [12:54] But once we have this, this is essentially [12:56] what defines the Q function update in this algorithm. [13:04] So specifically, now just a note on notation, [13:07] in reinforcement learning literature, [13:10] this quintuple of events is usually [13:13] expressed with states represented as S [13:16] and actions represented as A. And so [13:18] if you take this quintuple of events, [13:20] which are the ones that we need in order to define this update, [13:23] this literally spells out Sarsa. [13:24] And so this is also where the name of the algorithm [13:26] comes from. [13:28] But again, kind of simply put, at a high level, what [13:31] we're doing is that now we took our Monte Carlo control [13:35] algorithm. [13:36] We replaced Monte Carlo evaluation of the Q function [13:40] with TD updates of the Q function. [13:45] And we're doing this at every time step [13:47] because this is something that TD allows us to do. [13:56] And so indeed, you see that the step from what we're [13:58] doing to arguably one of the most famous algorithms [14:02] out there, Sarsa, is indeed pretty small. [14:04] And so I think it's useful to go through pseudocode to really [14:10] ground our intuition. [14:12] And so this is, if you wish, how Sarsa is loosely defined. [14:17] So we initialize a Q function. [14:19] Again, this could be all zeros at the beginning. [14:24] And we start our learning loop. [14:27] So we are initially initialized in our environment [14:30] at some state, xt. [14:32] At that state xt, we choose an action [14:35] according to our greedy policy or epsilon greedy policy. [14:39] So remember that we discussed our policy, pi. [14:45] If we choose an epsilon greedy policy, [14:47] is something that for with probability epsilon, [14:50] we'll choose a random action. [14:54] And with probability 1 minus epsilon, [14:56] we'll instead choose the argmax over u of our Q function. [15:08] So we are in a given state. [15:09] We act according to our epsilon greedy policy [15:12] and pick an action, u. [15:14] This will lead us into-- will basically give us [15:17] a reward for that action and next state [15:21] from which we repeat the selection of our control, ut [15:25] plus 1 according to our epsilon greedy policy. [15:27] And now we basically collected all of our five elements [15:31] that we need for our update. [15:34] So we have the initial state and control, xt, ut, [15:38] we have the reward associated with this control, [15:41] and the following xt plus 1, ut plus 1. [15:45] And so here we just simply compute this update rule [15:48] that we defined previously, which [15:51] is nothing else than the TD backup for Q functions. [16:00] Of course, here the clock ticks and we [16:01] can repeat until we converge. [16:11] Any questions here? [16:12] Does it make sense? [16:23] Yes. [16:24] [INAUDIBLE]? [16:28] Yes, TD. [16:28] So here we're using TD version of our update [16:33] for the Q functions, where we are updating our value [16:36] functions according to basically one step look ahead, [16:40] you might say. [16:41] So we're taking one step in our environment. [16:43] And as we were showing here in our pictorial diagrams, [16:46] we're essentially using only this one step update [16:49] to update our values. [16:58] So let's dig a little bit deeper. [17:01] And let's build some intuition into what [17:04] we're actually doing here. [17:05] And what are the results from the perspective of the policy [17:08] that we actually learned? [17:10] And so let's go through this. [17:12] What I'm referring here as a windy gridworld example. [17:15] So here we are in a gridworld where [17:17] the goal is, as usual, to go from a starting cell [17:20] to a goal cell. [17:23] The policy or the action space is basically [17:27] the four cardinal directions. [17:30] And in this grid world, the catch [17:32] is that we assume we have some kind of fictitious wind [17:35] that is coming from below, which basically pushes the agent, x [17:43] cells up depending where x is the value encoded here [17:47] below each of these columns. [17:49] So, for example, if we were in this column [17:51] here in the third one, we would have no wind. [17:54] If we were in the fourth, we will [17:56] be pushed one up, and so forth. [18:00] As usual, the goal that we want to solve [18:01] is to basically come up with the policy that [18:04] reaches the goal in the minimum time possible, [18:07] and we encode a minimum time through a stage wise reward that [18:11] is negative 1 for every time our clock ticks, essentially, [18:17] and we have some specific hyperparameters. [18:20] Epsilon refers to our epsilon greedy policy. [18:23] Alpha is a step size of our update, [18:25] and we pick a gamma of 1. [18:28] So now even just by eyeballing this example, [18:34] how would you describe the optimal policy here? [18:41] Yeah. [18:43] The bottom part of the thing before you [18:45] move to the right [INAUDIBLE]. [18:49] This is a good intuition. [18:51] It's actually not correct in this case. [18:54] Can anyone spot why? [18:57] Yeah. [18:58] You can't move over and up in the same grid. [19:01] So you can go all the way to bottom, [19:02] but to push you over g by the time you get there. [19:06] Yeah, exactly. [19:06] Because if you look closely at the intensity of the window [19:10] here, if you're way all the way to the bottom here, [19:12] you'll basically go up here. [19:14] Then you take one step and you go up again. [19:16] You take one step, and you go up again. [19:18] And then here we're taking two steps. [19:20] So you won't be able to reach. [19:22] So actually, it turns out that the optimal thing to do [19:24] would be to just push yourself to the ceiling and then go back. [19:29] So here go back here and then ultimately go to your goal. [19:37] So here's where I ask you to do a leap of faith. [19:40] But if you actually implement this [19:41] in practice, what you will see is [19:43] something that looks very similar to what is here [19:46] on the slide, whereby the first of all, Sarsa [19:50] indeed does converge to the optimal policy, which is [19:53] similar to how we described it. [19:57] And by looking at the training dynamics, [20:00] we will see something similar to this plot on the slide. [20:03] Specifically, this plot is showing on the x-axis the time [20:06] steps of interactions with the environment, [20:09] so literally how many time steps we are [20:10] observing in our environment. [20:12] And on the y-axis, we have the number of successful episodes, [20:18] meaning how many times do we actually reach the goal? [20:21] So you will see that initially our Q function [20:24] is, and therefore our policy, is randomly initialized. [20:27] So we'll basically be succeeding 0 times. [20:30] So we never reach the goal until at some point, [20:34] even just by random exploration, we will reach the goal. [20:38] And here's where the magic of the TD backup [20:43] start to happen because through those backups, [20:45] we're basically starting to back propagate basically positivity [20:51] and the goodness of our decisions all the way [20:53] back to the starting point. [20:55] And so you will see that over time the performance [20:58] of the policy improves. [21:01] Does the graphs here make sense? [21:09] Now, would you say that-- [21:11] within this environment, would you [21:15] say that Monte Carlo methods would also easily apply? [21:21] And in either case, why do you think so? [21:26] This is a more subtle question, but I think [21:28] it's a good one to think about. [21:31] Yes. [21:32] It wouldn't be the case because you would try out [21:34] a bunch of different combinations [21:35] and you only terminate if once you reach your goal. [21:38] So the goal is that you spend a lot of downtime, [21:40] just kind of wander around until eventually it lands on the goal? [21:44] Yeah, yeah. [21:45] I would say this is definitely the right intuition [21:48] because in Monte Carlo methods, remember we [21:51] require terminating episodes. [21:54] Well, in this case, terminating episodes [21:55] is only when we reach the goal. [21:57] So we might be lucky in the sense [22:00] that we end up into some random exploration that [22:05] does reach the goal. [22:06] But in the general case, it is not [22:07] guaranteed that we'll be able to do so. [22:10] So I think a nice counterexample to think about [22:15] is say that in our grid world example, [22:23] we have a situation whereby for some behavior of our learning [22:29] dynamics, we converge to a temporary policy that [22:33] is something like this, something where we have a circle [22:40] loop in our policy. [22:42] Then in Monte Carlo, this will essentially [22:46] never update the Q function. [22:47] And it will be stuck in this loop. [22:49] On the other hand, if we are in the same situation [22:53] with TD learning, TD learning allows us to update online. [22:58] So at each step, we are actually updating the values over [23:01] in our Q function. [23:03] And so this means that if we were [23:04] to be stuck in this circle loops, at some point, [23:07] we are basically accruing negative rewards over time. [23:12] And so this would mean that these specific behaviors [23:15] at some point will be actually worse than doing something else. [23:31] Indeed, and so it's exactly as we said in the sense [23:34] that termination is not guaranteed for all policies [23:36] here, and therefore kind of success of MC, [23:39] Monte Carlo learning, is not guaranteed as well. [23:44] So we now introduce, if you wish, [23:49] one of the first complete reinforcement [23:52] learning algorithms, namely Sarsa. [23:54] Let's use Sarsa as a kind of grounding algorithm [23:59] to start discussing the differences [24:01] between on-policy and off-policy learning. [24:04] So we mentioned it briefly before, [24:06] but let us briefly revisit also the definitions of what [24:09] we mean by on-policy and off-policy learning. [24:12] We'll dig more later on this. [24:14] But this is at a high level how I [24:16] would describe on-policy and off-policy learning. [24:19] So for on-policy, we mean that we [24:22] are interested in evaluating or improving [24:25] the policy that is currently used to make decisions [24:28] in the environment. [24:30] On the other hand, for off-policy, [24:32] we are interested in evaluating or improving [24:35] a policy that might be different from the one that [24:38] is used to generate data, that is the one that is actively [24:41] interacting with the environment. [24:44] Again, we'll formalize this a little bit shortly. [24:46] But I think this is intuitively the main difference. [24:51] Now, with these two kind of loose definitions, [24:56] in which of these two buckets would you place Sarsa? [25:00] And again, here, why would you do that? [25:11] It's also your policy because you're [INAUDIBLE]. [25:19] So we are modifying it. [25:23] But I would argue that we are modifying [25:26] the policy that is actively being used in the environment. [25:30] So I'm giving away the answer a little bit. [25:33] But in this case and in general, Sarsa [25:36] is to be considered an on policy algorithm [25:39] because if you look at the pseudocode a little bit more [25:42] closely, we are defining our policy [25:44] as the epsilon greedy policy. [25:46] And we are indeed improving this same epsilon greedy policy. [25:50] So the policy will change over time, and you're correct. [25:54] But we are indeed going to be improving [25:57] the same policy that is being used to interact [26:00] with the environment. [26:08] So yeah, Sarsa is indeed a non-policy algorithm. [26:11] But so let us now dig a little bit deeper [26:14] into off-policy learning. [26:17] How do we define it slightly more formally? [26:20] And also why do we ultimately care about off-policy learning? [26:23] So, in general, off-policy learning [26:27] can be seen as the mechanism through which we want [26:31] to evaluate a target policy pi. [26:35] That is, we want to compute the associated value functions [26:40] for this target policy pi while following a behavior policy, mu, [26:45] that is a different policy. [26:46] Specifically, the data we'll use to define our update equations [26:52] will basically be sampled by interactions [26:55] in the environment that are collected by following [26:58] the behavior policy, mu. [27:01] So the data here is obtained by observing a different policy. [27:08] So why would being able to do something like this be useful? [27:14] So, first of all, in some cases, for example, robotics to be one, [27:23] we might not have the luxury of actually [27:26] interact with the real world or with the environment infinitely [27:30] many times. [27:31] Maybe in some cases, we can only learn [27:33] through either observations of humans or other agents [27:37] doing things. [27:38] And therefore having this framework whereby [27:42] we are able to evaluate and learn about a different policy [27:47] from the one that is the one that generated the observations [27:51] is actually a nice thing to have. [27:55] Kind of a second reason is that so far, so [27:58] remember our generalized policy iteration scheme, [28:02] we described these alternating processes where we are gradually [28:06] improving our policy over time. [28:08] And so if you see this now a little bit more holistically [28:12] in the environment, we are generating data [28:15] according to changing and hopefully sequentially improving [28:22] policies, versions of the same policy. [28:24] And so far, we are basically saying [28:27] that we have some interactions with the environment, [28:31] and we only use the most recent versions of those interactions [28:35] to update our values. [28:36] So all of the previous data that was generated [28:39] from the previous versions of my policy [28:41] we were basically throwing it away. [28:43] And so I hope it's pretty evident [28:47] that this might be wasteful. [28:50] So maybe there is some information [28:51] to be gained from previous data. [28:57] And lastly, so this is slightly more subtle point, [29:01] but also I think the reason why off-policy methods are also [29:04] best known for, and it is because by decoupling, [29:10] if you wish the behavior policy from the target policy, [29:13] we're essentially able to posit the problem where [29:16] we want to learn about the optimal policy that [29:20] is likely to be an exploiting policy, [29:24] typically deterministic from the exploratory policy which [29:29] is the one that is maybe a little bit more random [29:31] and free of exploring our environment. [29:37] So I think these are all great reasons for which off policy [29:40] learning is actually very important. [29:47] So now let's look back at what we were doing for Sarsa where [29:51] we were basically updating our Q functions in an on-policy way. [29:55] And let's see how we could modify [29:58] what we're doing in Sarsa in order to basically follow [30:01] this off policy paradigm. [30:04] So remember that in Sarsa we were using behavior policy, mu. [30:08] So here we're already using the new notation [30:11] to generate our quintuple of events. [30:15] Specifically, the state and control [30:18] at time t, the reward and the next state, and then we're [30:22] also using it to generate the next control. [30:27] However, now let's consider an alternative successor action, [30:31] ut plus 1 prime, which is generated from our target [30:35] policy. [30:36] If we were to use now this quintuple of events [30:40] in defining the update, this was essentially [30:43] represent a way in which we are updating [30:47] our Q function, Q, towards the value of the alternative action. [30:52] So if you look a little bit more closely [30:54] at what we're saying here, is that we're updating our Q [30:58] function for xt, ut by taking a step in the direction of the TD [31:05] target defined by the value of the alternate action, [31:11] ut prime, t plus 1 prime. [31:20] Now, basically, the formalization of this, [31:23] so how do we-- if we want to now instantiate [31:26] this idea into a working algorithm, [31:29] this would directly lead us into defining Q-learning. [31:33] So specifically, in Q-learning, we [31:37] would define the target policy, pi, as the greedy policy [31:42] with respect to Q. Again, the target policy [31:45] is the policy we wish to learn. [31:47] And we are interested in learning the optimal policy. [31:50] So we want to learn the greedy policy with respect to Q. [31:53] So the target policy for us is the argmax over Q. [31:58] And we define the behavior policy to be [32:02] the epsilon greedy policy. [32:04] So in this case, we are acting in some cases [32:08] randomly with respect to our Q function. [32:11] But you see how we are formally defining these two [32:13] different policies, the one that we [32:15] use to interact with the environment and the one we [32:18] actually care about learning. [32:25] So by basically looking at the TD target in this case, [32:30] so remember that in the previous slide, [32:33] we basically said that in this formalism where [32:35] we have a behavior policy and a target [32:37] policy, the update and specifically the TD target [32:41] essentially looks at the reward plus the discounted value [32:45] Q function evaluated in the alternative action, [32:49] ut plus 1 prime. [32:51] So if we just take this same TD target, which is basically [32:55] this term over here, and apply our definition of how we compute [33:01] the alternative actions according to our target policy, [33:05] we only would modify this term inside the Q function, [33:10] namely the argmax over our Q function. [33:15] And by just doing some algebraic manipulations, [33:19] we would basically get that this is [33:21] equivalent to defining TD target as the reward [33:26] plus the discounted maximum Q value [33:30] where the maximum is taken under the action, u. [33:35] So here we're evaluating the Q value [33:40] under the argmax where the control is taken [33:44] under the argmax over Q. And so this means [33:46] that the overall value will be maximized because we're taking u [33:50] in order to maximize Q. And so this can just be rewritten [33:53] as the max over Q. All of this to say [33:58] is that by following this formalism, we basically redefine [34:03] our TD target in this way over here, [34:09] meaning we're just replacing our TD target by defining it [34:15] according to the alternative successor action, in this case, [34:20] the alternative successor action is the argmax policy. [34:24] And so this is what it leads to, essentially. [34:32] Any questions here? [34:41] And so basically, now if you put this together [34:44] into a working algorithm, you would basically [34:47] get what is referred to as Q-learning, exactly. [34:50] So again, we initialize our policy. [34:55] We start our learning loop whereby we are [34:58] initialized in some state, xt. [35:01] We basically choose our control, ut, in this state xt [35:07] according to an epsilon greedy policy, [35:09] this is our behavior policy, which we chose. [35:13] And we observe the reward and the next state [35:17] according to this control. [35:20] Now, we basically have all of our elements [35:22] in order to define the update which we [35:24] derived in the previous slide. [35:26] And so we can just repeat over time until we converge. [35:32] Yes. [35:35] The behavior policy only generates the first-- oh, sorry. [35:41] Behavior policy generates the first four, right, of the-- [35:45] OK. [35:46] Oh, yes, yes. [35:48] Just to make-- [35:50] Yeah, so in this case, we are using the behavior policy [35:52] in our environment, specifically this generates the first four. [35:56] And then we are kind of fictitiously assuming [35:59] that we would take this action over here. [36:04] Yeah. [36:05] Sorry, what does this new part-- what [36:08] does this new part [INAUDIBLE]? [36:13] So here we're defining two different policies. [36:16] One is our behavioral policy which [36:17] interacts with the environment. [36:19] And one is a target policy which is [36:21] the one we care about learning, essentially. [36:24] So in this case, this ut plus 1 prime [36:27] is sampled from this target policy. [36:30] So here this is in general terms. [36:33] So we are arbitrarily talking about behavioral policy mu [36:36] and target policy pi. [36:38] But in specifically when we look at Q-learning, [36:41] the target policy is the greedy policy, so taking the argmax. [36:47] And the behavior policy is the epsilon greedy policy. [36:49] So we randomly act-- [36:52] we react randomly epsilon percent of the time. [36:58] So putting this together, we indeed [37:01] follow the epsilon greedy policy in our environment. [37:03] But then in our updates, we are basically [37:08] updating our Q functions towards the value of the successor [37:12] action. [37:15] Does this clarify? [37:24] So there is some, of course, there's [37:25] theory that have been developed for all of these algorithms, [37:28] Sarsa included. [37:30] I thought it would have been nice to just mention [37:32] the fact that it can be proven that under some regularity [37:38] assumptions, Q-learning does, indeed, [37:41] converge to the optimal action value function. [37:44] And therefore, this process essentially [37:46] leads to learning the optimal policy accordingly. [37:52] So I think that basically these differences [37:58] and these discussions that we're doing between behavior policies [38:02] and target policies can be a little bit confusing at first. [38:06] So let's try to build some intuition by looking [38:12] at the difference in a simple environment between what we did [38:15] before with Sarsa and what we're doing right now with Q-learning. [38:21] So let's look at this modified version of the gridworld, [38:25] whereby again, we want to go from a start position [38:28] to a goal position. [38:30] No wind in this case, so no disturbance. [38:33] But now we are assuming we have this, basically [38:35] failure region, which is the cliff over here, [38:39] which is basically something extremely [38:41] negative for our agent. [38:42] So the reward here is, again, encoding minimal time, so [38:46] negative 1 at all time steps. [38:48] But if you do end up falling in the cliff, then you're doomed. [38:52] So negative 100, specifically, and with the specific choice [38:56] of hyperparameters. [38:59] So as a spoiler, if you wish, here we [39:04] are comparing the policies that we [39:08] would be converging if we followed Sarsa [39:12] in blue or Q-learning in red. [39:19] However, if you look at the kind of training dynamics over here, [39:25] you would basically, again, here we're looking at on the x-axis [39:28] the episodes, and on the y-axis we're [39:32] now looking at the sum of rewards [39:34] that we accrue over episodes. [39:37] And from here, you would actually [39:38] say that Sarsa is indeed performing better [39:41] than Q-learning. [39:43] So the catch here is that if you think back [39:49] at our discussion on-policy and off-policy algorithms, [39:52] Sarsa being an on-policy algorithm [39:55] is essentially learning the best version [39:58] of its kind of exploratory policy, if you wish. [40:03] So Sarsa, as we defined it, we were following [40:07] this epsilon greedy policy. [40:09] And so Sarsa indeed converges to the optimal epsilon [40:12] greedy policy. [40:14] On the other hand, Q-learning, because we [40:17] are kind of detaching our behavior [40:19] from the target of learning converges to the optimal policy, [40:24] pi star. [40:26] So this is, if you wish, by induction a property of one [40:30] being on-policy and one being off-policy. [40:34] Now, why would this explain this behavior over here? [40:38] The reason is that in our environment, [40:42] remember that both algorithms act epsilon greedily. [40:46] So if you act according to the read policy [40:52] and you're epsilon greedy, then sometimes you [40:55] will actually be doing some random things [40:57] and fall in the cliff. [40:59] And so this is why Q-learning when [41:02] we log what we're doing over training, we have a lower score. [41:07] On the other hand, Sarsa, because in order [41:10] to account for this uncertainty of epsilon [41:12] greediness kind of converge to the optimal epsilon [41:16] greedy policy, which in this case, [41:17] is a safer one that basically will travel more [41:21] closer to the ceiling. [41:24] Is it generally the case that Sarsa will [41:26] converge to a safer policy? [41:30] So I would say this is specific, of course, [41:33] to this specific choice of hyperparameters [41:36] and how we are discussing it. [41:38] In general, of course, you can modify the algorithm of Sarsa, [41:42] for example, by having a decay schedule of your epsilon [41:45] greediness and then you can also converge to the optimal policy. [41:51] So I mentioned theory for Q-learning [41:53] that this converges to the optimal policy. [41:55] There is theory that developed also for Sarsa in the fact [41:59] that according to indeed some specific choice [42:03] of your epsilon decay strategy or more generally [42:09] some specific property of your randomness in your policy [42:12] and some conditions on your step size, [42:14] Sarsa also converges to the optimal policy. [42:17] Yeah. [42:21] But why does [INAUDIBLE] achieve really [42:26] converge on lower reward despite taking a shorter path? [42:32] And why does the-- [42:33] I mean, both are not passing through the cliffs. [42:35] So why does [INAUDIBLE]? [42:38] No, I think it's worth looking at this closely and making [42:41] sure we're all on the same page. [42:43] So here we're just visually depicting [42:47] the optimal strategies that both algorithms converge to. [42:53] So we learn some Q functions. [42:55] And if we act greedily with respect to those Q functions, [42:57] this is how the two algorithms would behave. [43:00] Now, at training time, we're not acting greedily [43:03] with respect to those Q functions, [43:05] but we're acting epsilon greedily. [43:07] So with some epsilon percent, we're doing some random action. [43:14] If you consider the fact that Q-learning is actually [43:19] going closer to the cliff, in some epsilon [43:22] percent of the time, we would be landing in the cliff. [43:25] And so this is giving it some negative reward during training. [43:30] So these logs are measuring the performance of the epsilon [43:35] greedy application of the 2Q functions that we're learning. [43:41] Also, is the reward negative one the first step taken? [43:45] Or it's just the rewarding [INAUDIBLE]? [43:49] You mean what is being tracked here? [43:51] That reward negative one. [43:54] Here we are assuming that for every time [43:56] step in our environment, whatever we do, it's minus 1 [43:59] until we reach the goal. [44:00] And then if we fall in the cliff, we get negative 100. [44:03] And it terminates and we are spawned back to the start. [44:07] So even though during the training [44:10] the sum of the rewards and the episodes [44:13] is lower for Q-learning, because the more often your [INAUDIBLE], [44:21] the actual fact that it converges to is, [44:26] I guess, higher in reward than the blue curve. [44:29] Yeah, this is very important. [44:30] Does it make sense why? [44:31] These two paths are visualizing-- [44:35] forget what happens during training. [44:37] Training is done, and we converge to two different Q [44:40] functions. [44:41] This path is visualizing being greedy, so argmax [44:45] over those Q functions. [44:47] And this is what you would do. [44:49] Now, here what we're saying is during training time, [44:55] so before doing this visualization, what [44:57] you would see is this basically this plot over here. [45:02] Why would you see this difference? [45:03] Is because at training time, you're [45:05] not acting greedily with respect to your Q function, [45:08] but you're acting epsilon greedily. [45:18] Oh, sorry, yeah. [45:20] Do you do the epsilon decay [INAUDIBLE]? [45:24] No, so here is just fixed hyperparameters. [45:27] And if you did have [INAUDIBLE]? [45:32] Yeah, so Sarsa would converge to the optimal policy as well. [45:35] OK. [45:36] Yeah. [45:44] OK, any other questions on what we discussed so far before we [45:49] move on to function approximation? [45:55] OK, great. [45:57] So until now, we discussed algorithms [46:02] that were basically deployed on these smaller [46:05] scale, toy-like worlds. [46:09] On the other hand, I'm sure most of you or some of you, at least, [46:14] might have heard about the great successes of reinforcement [46:18] training both in the realm of games, [46:20] for example, AlphaGo and the successes in Go, [46:24] one of the peaks of the successes, at least with respect [46:27] to games. [46:29] But these are all environments where [46:31] if you think about the state space, [46:34] these are incredibly large and incredibly high dimensional. [46:38] So, for example, in the game of Go, [46:40] you could have 10 to the power of 170 different configurations [46:44] of the board, which is, I think, more [46:46] than the atoms in the universe or something like that. [46:48] So this is an incredibly high number. [46:51] And you could argue that games are actually among the easier [46:55] things to solve compared to having things deployed [46:59] in the real world where things that could happen [47:01] are much more high dimensional, even. [47:07] And so the question is, how can we [47:09] scale what we're saying with this model free reinforcement [47:15] learning approaches to these more high dimensional systems? [47:21] And the culprit here in scaling will essentially [47:24] be to move away from our tabular expression of value functions. [47:32] Again, remember that we are essentially in everything [47:36] that we did so far, we were assuming [47:38] that the value functions or Q functions equally [47:44] were essentially represented as lookup tables. [47:48] So essentially, for each value of our state or state action [47:53] pair, we would have a specific entry [47:55] which represents the value of that state or state action pair. [48:00] On the other hand, and this is, of course, problematic, [48:04] as I'm sure you can imagine, for two main reasons. [48:07] The first one is memory. [48:09] So if you have 10 to the power of 170 states, [48:13] then even just storing this is an issue. [48:16] But then from the perspective of learning, [48:18] there is a clear curse of dimensionality issue [48:20] that comes up because to update values in our lookup tables, [48:26] we have to visit those entries in the lookup table. [48:30] And so you can imagine how this becomes problematic. [48:35] So this is where value function approximation comes into play. [48:41] And this is because-- and basically, where the main idea [48:44] is that rather than defining these Lookup tables, [48:47] we want to define a parametric function [48:50] with some parameters, theta, that basically [48:52] approximates our values. [48:55] So we will be moving from these tabular representations [48:58] to something where the value function is basically [49:01] a parametric function, parameters theta, that [49:04] in this case, maps from states to a real value. [49:11] And you can imagine something very similar for the Q function. [49:14] Again, it's just a function that basically maps from states [49:25] and controls to real values. [49:32] So first of all, how does this idea address these two issues? [49:37] First of all, we are compressing, [49:42] or if you wish, amortizing the memory storage [49:45] cost in storing only the parameters. [49:49] So we're not storing one value for each state action pair, [49:52] but we're only storing the values of our parameters. [49:56] And also in terms of addressing the curse of dimensionality, [50:00] to some extent, we can hope that these value approximations [50:05] can generalize across states and state action pairs. [50:09] So far, even in our gridworld examples, [50:14] we were assuming that we had a goal state, g, and that even [50:22] very nearby states, if we wish to estimate [50:27] the value of this nearby state to the goal, [50:29] we would have to visit this state. [50:31] On the other hand, you can probably [50:33] hope that in the general case, as long [50:36] as your representation of your environment is correct, [50:39] this kind of knowing something about the goal state [50:41] could also inform your estimate of the value close [50:45] by the goal state. [50:46] And so this is something that we can [50:49] hope to have when we look at function approximation. [50:59] How does function approximation look in practice [51:02] for value functions? [51:05] Here is where there could be many different ways [51:08] of instantiating value functions through function approximation. [51:13] At the high level, I think most implementations [51:15] pick between one of these three representations. [51:20] In general, we are assuming that we have a black box that [51:23] basically represents our function approximation [51:26] with some parameters, theta. [51:28] But, in general, we could have these three main classes. [51:31] The first one is if you're estimating value state value [51:34] functions, v, it will be something [51:36] that takes as input as state x, does some computation, [51:40] and then spits out a value for that state. [51:44] Similarly, the Q function could be something [51:47] that takes as input a state and a control [51:49] and spits out the specific Q function for that state [51:52] and control pair. [51:54] Or another interpretation of this second approach [52:00] would be something that we still want to estimate the Q function. [52:04] But now we take as input only the state. [52:06] And rather than generating one output, [52:09] we would be generating multiple outputs one [52:13] for each possible control in that state. [52:19] Can you imagine why-- [52:20] I'm not saying this is better in general, [52:22] but can you imagine why this might be desirable [52:24] compared to the second one? [52:26] Yeah. [52:27] [INAUDIBLE] in your function, or maybe even you put inputs, [52:34] then you could define the function [52:38] in terms of new [INAUDIBLE]. [52:42] So I think your intuition is correct. [52:45] Now doing this for continuous action spaces [52:49] is challenging depending on discretization. [52:52] But I would not go for this when you have a continuous control [52:55] space. [52:56] But I think you're correct in the sense [52:57] that this could lead to some simplification in how [53:01] you represent Q. But can you-- [53:04] so assume both x and u are discrete in our case. [53:10] Can you think of a reason why? [53:12] Yeah. [53:13] [INAUDIBLE] you might want to have [53:15] multiple [INAUDIBLE] functions. [53:17] Like if you were to drive your car somewhere [53:20] where distance in car versus cost of gas [INAUDIBLE]. [53:27] I would argue probably not. [53:30] No, at least at face value. [53:31] Because remember that we will be posting [53:34] this as a regression problem. [53:36] So either here you are assuming that you have different target Q [53:43] functions that you're willing to wanting to estimate, [53:45] and then maybe indeed this could be helpful. [53:48] But let's assume for now that we have [53:50] one value function of one policy that we wish to estimate. [53:54] But I think yours is a good intuition but not what [53:56] I was looking here right now. [53:58] I mean, what's this probe one specific state and then [54:02] we can take the argmax over all the Qs that output to get the-- [54:06] Yes, exactly, exactly. [54:08] So I think these are all great points. [54:10] But here I was more thinking about, indeed, [54:12] more of a computational aspect, if you wish. [54:15] So remember that we are defining our policy generally, [54:19] or at least a greedy policy once we have learned the Q function [54:22] as an argmax over u. [54:24] Now, say that we have, again, u is discrete, [54:28] so we have a finite number of u we want to iterate over. [54:31] If we had now a function approximation for our Q [54:37] function, this becomes an optimization problem, [54:40] if you wish. [54:41] So before it was just basically looking up in a table. [54:45] Now, it's an optimization problem. [54:47] So if our Q function is something that given [54:52] a state only gives us the value of-- [54:55] given a state and a control gives us one value, [54:57] we would have to do n queries where n could be very high. [55:03] On the other hand, if Q is an object that given [55:06] an x gives us all the values of u of qxu for all u, [55:12] then this becomes again a kind of a lookup [55:15] in a finite number of elements, if that makes sense, [55:18] with only one call. [55:23] Again, I'm not saying this is the best way for going for it, [55:25] but these are kind of insights behind these choices. [55:36] And then not only is there, of course, [55:38] flexibility in how you define these functional approximations [55:41] at a high level, but also within the Black box creativity [55:48] is king here. [55:49] So in some sense, you could go with something very simple, [55:53] such as a linear model or something very complex, [55:55] such as an extremely deep neural network. [55:58] But the high level understanding remains the same. [56:05] So I hope I have convinced you about the benefits of value [56:09] functions approximations. [56:11] How do we instantiate what we've been saying so far in terms [56:16] of Monte Carlo learning and TD learning [56:19] when we have value functions where [56:22] we have parametric functions that [56:24] represent our value functions? [56:29] So remember that now what we want to do [56:31] is essentially learn the parameters, theta, of our value [56:37] function approximators. [56:38] That is, we want to minimize the error between the estimated [56:42] value, for example, v theta of x. [56:47] So the error we want to minimize this error between v theta of x [56:50] and the true value v pi of x. [56:54] Seeing this from a regression perspective, [56:57] this would mean potentially positing [56:59] this objective function, j, or cost function j. [57:03] And we want to minimize the expected value of this error. [57:08] So we want to minimize the mean squared error, for example. [57:14] How do we solve this? [57:15] We have done this multiple times, for example, [57:17] by taking a gradient descent. [57:20] So where we want to define essentially some delta, [57:28] some displacement in our parameters of our function [57:31] approximators, which goes in the direction [57:34] of the negative gradient. [57:36] Now, if we were to pick this choice of displacement, [57:43] delta t, what we would basically get [57:46] doing some math is something such as we [57:49] are basically taking one step where [57:51] we choose some step size, alpha, in the direction of basically [57:58] our negative gradient multiplied by this error over here. [58:06] And I definitely suggest you to basically go [58:08] through the derivation of how we go from here to here. [58:11] But this is not very insightful. [58:13] It's just basically applying gradient descent, [58:15] stochastic gradient descent to this objective. [58:18] But at a high level, it's important to basically fix [58:21] in your mind that the form of our updates in our parameters [58:25] is something that looks like this. [58:31] Now, how we described it so far, it's [58:33] kind of a chicken and egg in an egg problem [58:35] because we're saying we want to minimize [58:37] the error between our prediction and our true value function, [58:42] but we don't have the true value function. [58:44] And so in practice, what we do here [58:49] is we basically leverage everything [58:51] that we said so far when we talked about TD targets [58:56] and Monte Carlo targets in order to define [58:59] what is our target for regression, essentially. [59:02] So similarly to how we did in tabular methods, [59:06] we would have a version of the Monte Carlo update [59:09] where now we are taking we're updating [59:11] the parameters of our function in the direction of minimizing [59:15] the prediction error or this prediction error is [59:18] between our prediction and the ground truth [59:21] return estimated as we were doing through Monte Carlo. [59:26] And in TD learning, what we would get is the same thing. [59:29] But now, instead of pointing at the observed return, [59:34] we're basically pointing at the TD target [59:37] where we're using our estimate of future values as well. [59:48] OK, so what are we really saying here? [59:52] So we are basically saying two different versions [59:58] of a very similar intuition. [60:00] So we said in the tabular dimension [60:03] where value functions are lookup tables, [60:07] we were using interactions with our environment [60:10] to estimate either our return, simply the sum [60:15] of all the rewards that we saw or a TD target. [60:19] So the immediate reward plus the estimated future value, [60:25] in the tabular case, we were then simply using these two [60:30] quantities to update individual entries in our lookup table [60:35] according to our update equations. [60:42] When we're looking at function approximation, [60:45] at the high level, we're doing exactly the same thing. [60:47] But now, instead of updating entries in lookup tables, [60:51] we're using those same quantities. [60:54] The return, gt, and the TD target, [60:59] to basically define input output pairs for our regression [61:06] problem. [61:07] And so this means that we will be [61:10] able to define some updates to our parameters, theta, [61:14] in a very similar way. [61:16] Does this make sense? [61:19] Any questions here? [61:31] [INAUDIBLE] [61:41] Yes, so this is a great intuition because indeed, [61:47] as you say, the quality of my target evolves over time [61:52] the more this is getting better. [61:53] And so you are actually pointing at, [61:56] I would say, one of the key engineering breakthroughs, [62:01] if you wish, that enabled deep reinforcement [62:04] learning to actually work in practice, [62:06] basically stabilizing learning exactly for this reason. [62:10] And I think we'll mention it in a couple of slides. [62:13] Yeah, but this is a great intuition. [62:23] Of course, again, here we mentioned everything [62:27] in looking at state value functions. [62:31] But everything holds exactly the same [62:33] when we look at Q functions. [62:35] So again, the underlying regression problem [62:38] that we would like to solve is basically [62:41] minimizing the error between the predicted Q function [62:45] and the ground truth Q function, which [62:49] leads to defining a specific update in parameter space. [62:52] We are, of course, not able to observe the ground truth [62:56] Q function, and so we define the target of our regression [63:02] either through Monte Carlo or TD learning. [63:04] In this case, if we were to use a TD target, [63:07] we would get what is referred to in literature as fitted Q [63:11] iteration. [63:16] And so, indeed, implementing this [63:21] in within our generalized policy iteration scheme [63:27] could look like something where at the policy evaluation stage, [63:31] we basically approximate the Q function of our policy [63:35] by using these update equations in parameter space [63:39] that we just defined. [63:40] Namely, we interact with the environment, collect some data, [63:44] and fit that data, fit the Q function that better [63:47] estimates those TD targets. [63:49] And so this is what policy evaluation looks like for us. [63:52] And then we use the updated Q function [63:56] to basically define our epsilon greedy policy improvement step. [64:01] Again, I hope that even through the repetition [64:06] of very similar versions of those same algorithms, [64:08] you're starting to see how different RL algorithms are all [64:11] built around different instantiations of Monte Carlo [64:14] learning and TD learning and basically [64:16] swapping or mixing different elements in those updates. [64:21] But this would, indeed, be a working reinforcement [64:25] learning algorithm with value function approximation. [64:33] How does this look like in our reinforcement learning skeleton? [64:36] Remember that last time we were starting [64:38] to introduce this bird's eye view on basically [64:42] all reinforcement learning algorithms out [64:43] there defined as a first stage where [64:47] we generate samples, a second stage where we either [64:50] fit a model of our dynamics or estimate some return, [64:53] and use this to improve the policy. [64:55] Indeed, if we look at fitted Q-learning, which [64:58] is what we just described, we would run the policy [65:02] and observe our usual transitions. [65:06] We would then use this data to define [65:09] a target for our Q function regression problem, if you wish. [65:16] Specifically, here we're using the TD target. [65:19] And then use this to basically update [65:23] our estimate of the Q function. [65:26] And then we use the newly learned Q function [65:29] to improve the policy according to an argmax policy improvement. [65:38] Any questions here? [65:46] So then the last thing that I wanted to discuss today [65:50] relates with basically taking these ideas [65:53] but now looking at modern instantiations of these ideas, [65:57] specifically in the field of deep reinforcement [65:59] learning, that is, using deep neural networks [66:02] within the same algorithms that we just discussed today. [66:06] And one of, I would say, groundbreaking results, [66:11] I think this dates back to roughly 2014, [66:14] is known as Deep Q-Networks or DQN for short. [66:19] And we saw this, I think, a couple [66:22] of times before we saw these videos of these Atari games. [66:25] But the point here is that, indeed, [66:27] the goal of where these algorithms were developed [66:30] was solving basically learn how to play [66:33] optimally different versions of the Atari family of games. [66:37] Specifically, the interesting side of this [66:39] is that we're basically using deep neural network specifically [66:43] at the time, convolutional neural networks, [66:45] to learn how to control these games directly from images. [66:49] And so this is where the power of if you wish, [66:51] deep learning and reinforcement learning [66:52] was starting to be combined. [66:54] And at a high level, the architecture of these methods [67:00] looked something like we have raw images of our environment, [67:05] which we are processing through multiple layers [67:07] of convolutional neural networks. [67:10] And then we're outputting here, at least [67:12] in the original instantiation, one value [67:17] for each of the possible actions that we could do in this state. [67:20] So if you wish, the image for us is a proxy or observation [67:24] of what the state x is. [67:26] And so we have the state coming in in the form of an image. [67:30] And we have the Q value for all of the u [67:33] of our controls in this state. [67:35] So if you remember from our three different categories [67:38] of value function approximation, this would be the third one. [67:46] So in some way, this work, indeed, used deep neural nets [67:50] to represent our Q functions. [67:52] And as we'll see in the next slide, [67:54] this introduced a number of tricks that basically helped [67:58] to stabilize learning when we look at deep neural networks, [68:02] exactly as your colleague was assuming before. [68:08] Is this picture clear, more or less [68:09] what the algorithm is doing? [68:15] So let's look more specifically at these two solutions that [68:22] were I would say extremely important for actually [68:26] the success of these methods. [68:28] And we're specifically talking about experience replay [68:32] and what is known as using fixed Q targets. [68:37] So indeed, these two ideas turned out [68:38] to be extremely important to stabilize training [68:43] because they basically addressed two main issues. [68:46] The first one is that right now, if we [68:51] are looking at function approximation of our Q [68:55] functions, we basically have this inner loop, [68:58] which is basically regression of our Q function. [69:03] So as we explore in our environment, [69:06] we basically are iteratively fitting the estimates of our Q [69:10] function to the targets that we are observing. [69:13] However, in this case, because we [69:16] are active agents in our environment, [69:19] kind of samples over time in our rollouts [69:22] are highly correlated with each other. [69:25] And this is, of course, very bad from our perspective [69:31] of regression and supervised learning [69:34] because we know that statistical learning theory usually [69:38] assumes that data is IID from a target distribution. [69:43] And so the one big issue is that because we are now [69:46] in an interactive engagement with our environment, [69:52] the targets and the samples that we [69:54] observe are highly correlated with each other. [69:57] The second problem is, indeed, what your colleague [70:00] was referring to, which is that the target that we are aiming [70:03] towards that we are regressing towards to [70:06] is, indeed, a moving target. [70:07] Because as we update the parameters theta, [70:10] then the target of our regression also changes. [70:13] And so this creates some problems in terms of stability. [70:18] So let us look at how these two issues were solved in practice. [70:24] So at the very high level, I would [70:25] say the learning loop of DQN goes as follows. [70:31] So as usual, we are in a specific state, xt, [70:34] and we take an action ut according [70:36] to the epsilon greedy policy. [70:37] Again, the policy initially might be a randomly initialized [70:41] neural net. [70:43] As we are doing classically in Q-learning, [70:47] we store this transition of xt, ut reward and next state. [70:53] And we store it in a replay memory calligraphic t. [70:59] Now, so here is where the solution to the first problem [71:03] actually comes in place, which is arguably very simple, [71:06] but it's essentially saying that we [71:07] know that the problem that we want to fix [71:10] is that data and individual transitions [71:13] are highly correlated between each other. [71:16] So let's decorrelate transitions by storing them in a buffer. [71:21] And then rather than using only the most immediate transitions, [71:25] let us subsample these individual transitions [71:28] from that buffer. [71:33] Assuming the buffer is large enough, [71:35] then this would-- the more the buffer grows, [71:38] the more the individual transitions are decorrelated [71:43] with each other. [71:45] So what we're saying is that if we [71:49] were to look at a single rollout, [71:53] we would generally observe a situation where [71:57] we have xt, ut and the associated reward, [72:01] and we have the next state xt plus 1, which [72:03] gives us the first transition. [72:13] And so we could use this to make one update in our algorithm. [72:17] But then as we move along in our episode, [72:20] we would basically be observing some new transitions [72:29] which are highly correlated with the previous one. [72:32] And so if we were to take these transitions online and [72:37] sequentially, this would be highly [72:38] correlated with each other. [72:39] What we're saying, at least with this experience replay idea, [72:43] is that rather than using these transitions directly, [72:46] we observe them, store them in a buffer, which is something [72:52] that it's just a large data set of transitions, something [72:57] that is a collection of these transitions-- [73:05] and xt plus 1. [73:08] And by sampling from this buffer, [73:09] we are basically decorrelating the transitions [73:12] that we use to fit our networks. [73:17] So again, very simple idea, but I [73:18] think quite powerful in accomplishing [73:21] what I was trying to do. [73:24] Now, the second trick entails stabilizing this moving target [73:30] issue that we were highlighting before. [73:32] And the idea here is to basically leverage [73:36] two copies of the same value function network. [73:40] So instead of having a single network, Q theta, [73:44] we're basically working with two different networks, Q theta [73:47] and Q phi. [73:50] So we have two copies of the parameters. [73:54] The point in this solution is essentially [74:02] that we will have one copy of the parameters [74:09] that we are updating over time and one copy that is basically [74:13] a delayed version of that function that we're updating. [74:18] So we start with some randomly initialized to the same thing [74:24] policy, so two copies of the same initialized network. [74:28] Now, imagine that we have this is like a time axis [74:31] overtraining. [74:33] We would have a phase where we are initially updating theta. [74:43] And we are updating theta on fixed phi. [74:47] So over here phi is actually fixed. [74:53] Now, phi could be horribly bad at estimating [74:58] the values at the beginning. [75:00] But from the perspective of stability of the target, [75:03] this is actually stable because it's consistent over time. [75:08] Of course, over time it will be defining some regular cadence [75:14] where we are basically updating the parameters, phi, [75:20] to the potentially most recent version of theta. [75:25] And so we repeat this. [75:27] So then we have a new phase where we are updating theta. [75:31] But now towards a slightly better version [75:33] of the target network. [75:35] Again, phi here remains fixed. [75:40] And then we repeat over time. [75:42] So you see that, in general, we basically [75:44] instantiate this delayed version of the same Q-network which [75:48] stabilizes the target through this kind of delayed update. [75:57] Of course, different versions vary [75:59] of the algorithm vary in how this update is done. [76:03] This is a very deterministic way of updating the target policy, [76:10] Q phi. [76:12] It's been shown that this specific version is probably [76:17] not the best choice because there could [76:19] be a jump, a too harsh jump in updating [76:22] the parameters of our target phi. [76:24] So I would say probably right now [76:26] the most popular version is referred to as Polyak averaging, [76:30] where it's basically a moving average of the parameters. [76:33] So if you wish exact same intuitions apply. [76:36] But the update of our target network, Q phi [76:39] is not done in a so kind of harsh step fashion way. [76:44] But phi will be a moving average of previous versions of theta. [76:52] But this is exactly the idea. [76:54] And so you see that I would say these two contributions were [76:59] basically key in making deep reinforcement learning [77:03] algorithms work in practice. [77:09] Does this make sense? [77:09] Any questions here? [77:17] So this wraps up, concludes our discussion [77:21] of value based methods. [77:23] Next week we'll be discussing policy optimization based [77:26] methods, again, model free. [77:28] And then we'll move for our last lecture [77:30] on model-based reinforcement learning methods. [77:33] See you next week.