Stanford AA203 Optimal and Learning-Based Control | Spring 2026 | Lecture 16: Fundamentals of RL

斯坦福 AA203 最优与基于学习的控制 | 2026年春季 | 第16讲：强化学习基础 Gammelli 博士从模仿学习过渡到强化学习，探讨智能体如何通过经验交互而非显式转移模型或演示来优化控制策略。在阐明策略迭代和价值迭代等精确动态规划方法的局限性后，本讲座介绍了通过蒙特卡洛和时序差分（TD）学习实现的无模型策略评估，并对比了它们的偏差-方差权衡及回溯机制。随后，讨论延伸至结合 ε-贪婪探索、使用动作价值函数（$Q$ 表）的广义策略迭代，展示了智能体如何在模拟的二十一点任务中从零开始学习最优策略。最后，Gammelli 博士提出了一个通用的三阶段架构——样本生成、估计/建模以及策略改进，该架构构成了所有现代强化学习算法的基础。 强化学习通过直接的环境交互实现自主策略探索，从而解决了模仿学习受限于演示者质量的核心性能瓶颈。 (0:06) 尽管蒙特卡洛方法利用经验回报提供了无偏的状态价值估计，但其方差较大，且由于需要完整的轨迹结束，严格受限于幕式任务。 (20:39) 时序差分（TD）学习通过将经验采样与自举相结合，架起了动态规划与蒙特卡洛之间的桥梁，虽引入了估计偏差，但实现了更低的方差以及在非终止环境中的在线学习。 (41:59) 无模型广义策略迭代需要评估动作价值函数 Q(x, u) 而非状态价值 V(x)，从而在无需解析转移状态动态的情况下实现贪婪策略改进。 (60:05)

Dr. Daniele Gammelli frames reinforcement learning as a necessary transition from demonstration- and model-dependent control to autonomous trial-and-error interaction, resolving the limitations of exact dynamic programming by sampling empirical experience and balancing the statistical trade-offs of value estimation. Moving Beyond Exact Transition Models (18:53) Exact dynamic programming methods such as policy iteration and value iteration solve Markov Decision Processes by enforcing Bellman equations across state and action spaces. However, Dr. Gammelli emphasizes that both policy evaluation and greedy policy improvement fundamentally rely on explicit, analytical access to the environment's transition probability distribution, denoted as P(x_{t+1} | x_t, u_t). When an agent operates in real-world systems where the underlying dynamics are unknown, standard dynamic programming equations cannot evaluate expectations over future states. To overcome this reliance on analytical models, reinforcement learning shifts toward model-free methods that substitute explicit transition matrices with empirical interactions collected from the environment. Beyond model dependence, exact tabular methods face severe memory and computational bottlenecks from enumerating discrete state-action pairs, necessitating sample-based approximations and function approximators to handle high-dimensional environments. Statistical Trade-Offs in Value Estimation Model-free value estimation divides into Monte Carlo methods and Temporal Difference (TD) learning, which occupy distinct locations along the dimensions of backup width and backup depth. Monte Carlo methods evaluate states by executing complete trajectory rollouts to episodic termination, estimating state values from empirical returns. While this sample average is an unbiased estimator of expected return, it suffers from high variance caused by compounding stochasticity across transitions, actions, and rewards over long trajectories. Additionally, its reliance on terminal returns restricts standard Monte Carlo methods strictly to episodic tasks. In contrast, one-step TD learning updates estimates immediately after a single transition by bootstrapping—updating its current value toward an estimated target composed of the immediate reward plus the discounted value of the successor state. Although using an imperfect value estimate introduces systematic bias into the TD target, it isolates environmental noise to a single transition step, achieving substantially lower variance and permitting online learning in continuing, non-terminating tasks. Action-Value Optimization and Exploration Dilemmas (60:05) Operationalizing model-free control within Generalized Policy Iteration requires replacing state-value functions V(x) with action-value functions Q(x, u). When evaluating state values alone, extracting a greedy policy requires computing an expectation over next-state distributions, which reintroduces the need for an explicit transition model. Evaluating Q(x, u) removes this barrier, enabling direct greedy improvement via an argmax over candidate inputs without consulting transition dynamics. However, deterministic greedy improvement over empirical Q-values triggers the exploration-exploitation dilemma. As illustrated by a two-door decision problem, an agent that receives an initial zero reward from one action and a positive reward from another will deterministically abandon the first, permanently ignoring it even if its true expected value is superior. Implementing an epsilon-greedy strategy—selecting the greedy action with probability 1 - epsilon and a uniform random action with probability epsilon—ensures continuous exploration across the state-action space. In a blackjack simulation, this combined architecture converges from scratch to an optimal policy without prior heuristics or transition models. A Universal Three-Stage Algorithmic Architecture (70:40) Dr. Gammelli unifies reinforcement learning algorithms into a shared three-stage conceptual cycle rather than isolated techniques. The first module involves generating empirical trajectory samples through environmental interaction. The second module processes those samples to either approximate value functions (in model-free methods) or fit surrogate transition dynamics and reward models (in model-based approaches). The third module executes policy improvement based on the updated estimates. Depending on the algorithmic family, this improvement manifests as a greedy operator across action-value tables or as analytical gradient ascent steps targeting parameterized policies. Dr. Gammelli highlights that this recurring three-part abstraction forms the core architecture underpinning both tabular algorithms and advanced deep reinforcement learning frameworks. While tabular Monte Carlo and Temporal Difference methods provide rigorous convergence guarantees for finite environments, their dependence on discrete lookup tables renders them impractical for high-dimensional and continuous control tasks. Resolving these memory and scalability bottlenecks requires replacing discrete tables with parametric function approximators, such as neural networks.

[0:06] Dr. Daniele Gammelli: learning from demonstrations [0:06] Dr. Daniele Gammelli: learn from interactions [11:36] Dr. Daniele Gammelli: So here, nothing too fancy. I just basically formalized what we are writing the Bellman expectation equation. [38:47] Dr. Daniele Gammelli: guess towards a guess [53:11] Dr. Daniele Gammelli: there are just many more possible futures [54:18] Dr. Daniele Gammelli: really drive this message home [57:11] Dr. Daniele Gammelli: our guess towards a guess [66:34] Dr. Daniele Gammelli: becoming experts at blackjack [66:34] Dr. Daniele Gammelli: I'm definitely not advising you to try this strategy if you go in because who knows.

[0:06] OK, so starting from your roadmap, [0:10] last Monday we started talking about more modern approaches [0:15] to learning based control. [0:18] Specifically, we looked at imitation learning [0:20] as our specific paradigm of interest where loosely speaking, [0:24] we pitched imitation learning as this idea of wanting [0:27] to learn from demonstrations. [0:29] And so we saw different types of ways of doing this, specifically [0:32] behavioral cloning and inverse reinforcement learning, where [0:35] the idea there is that we want to directly learn a policy that [0:38] represents or mimics and approximates [0:40] the behavior of our expert. [0:41] Or do we want to learn the objective that [0:43] is, the underlying reward function [0:44] that the expert is optimizing? [0:47] However, we also recognized how imitation learning techniques [0:50] at their core are essentially capped in terms of performance [0:55] by the performance of the expert demonstrations. [0:57] And so for today and for the rest of this class, [1:00] we move towards reinforcement learning, [1:03] which, on the other hand, is this idea of wanting [1:05] to learn from interactions. [1:08] As a basic paradigm to learn through trial and error [1:13] and discover solutions for optimal control problems. [1:17] So today and for the next two classes, [1:21] we'll be looking at model free reinforcement learning, [1:23] and then we'll be looking at model-based reinforcement [1:26] learning. [1:28] And specifically, for today, we'll [1:30] start with a brief recap of reinforcement [1:32] learning problem setting. [1:34] And we'll dive a little bit deeper [1:35] into what I'm referring to here as exact methods. [1:37] So if you recall in our lectures on dynamic programming, [1:41] we discussed value iteration and policy iteration [1:44] as ways of solving Markov decision processes. [1:46] And so we'll look a little bit more [1:48] closely on those that is methods that leverage [1:52] dynamic programming for computing solutions. [1:55] The reason why I refer to them as exact methods [1:58] is because implicitly, these methods, that [2:01] is value iteration and policy iteration, [2:03] were leveraging the fact that we knew the underlying [2:05] dynamics of our system, which is something [2:09] that on the other hand, we assume [2:11] we won't have throughout reinforcement learning. [2:13] And this is where learning from interaction will come in place. [2:17] And so from that, we'll then leverage and build [2:20] upon those techniques to introduce two, I would say, [2:23] really fundamental kind of approaches [2:25] for model free learning, that is model [2:27] learning from interactions. [2:30] Specifically, we'll look at Monte Carlo learning [2:32] and temporal difference learning. [2:34] And then we will wrap up the discussion [2:36] with some kind of concluding remarks [2:38] and as a segue into the next few lectures we'll [2:41] be diving more closely into specific algorithms, both model [2:44] free and model based. [2:48] And so starting from our problem setting, [2:52] we introduced in the past this idea of a Markov Decision [2:57] Process, which were ultimately an MDP, [2:59] is represented by a tuple of elements here defined [3:03] by the calligraphic m. [3:04] Loosely speaking, we have an action and a state space [3:07] which represent the possible set of states and actions [3:09] our agent could either be in or could enact. [3:13] We have a transition function, which [3:15] is represented in the RL literature, [3:17] usually as a distribution over next states given [3:19] states and controls. [3:21] We have a reward function which maps states and controls [3:23] to a scalar measure of success, and we [3:25] have a discount factor, which is just a scalar between 0 and 1. [3:28] We discussed how this is both useful from an intuitive [3:32] standpoint, it kind of trades off [3:34] long term reward with respect to short term reward, [3:37] but also as a mathematical object [3:38] that enables an infinite sum to become tractable. [3:43] Where does this infinite sum come in place? [3:46] It comes in place from the overall goal [3:48] that we want to maximize in when we talk about Markov decision [3:53] processes. [3:54] That is, we want to find the optimal policy, pi star, that [3:57] maximizes the expected cumulative discounted [4:00] reward over time. [4:04] And to solve these problems, last time, [4:06] we introduced the concepts of value functions [4:09] and Bellman equations. [4:10] Specifically, we introduced the state value function represented [4:14] as v as essentially an element that encodes the expected reward [4:20] that we can expect to have starting from some state, xt, [4:23] and then following a given policy, pi. [4:26] So the value function is an object that depends on policy. [4:31] And we saw how these value functions [4:34] satisfy some fixed point equations, namely [4:37] the Bellman equations. [4:39] And so we discussed the Bellman optimality equation, which [4:43] relates with the optimal value function, [4:45] v star, which essentially says that the optimal value [4:48] function, v star, at some state xt, [4:50] is essentially equal to the maximization over controls, [4:54] u, ut, of the sum of the instantaneous reward [4:57] plus the expected value at the next state, [5:03] xt plus 1, where the expectation is essentially averaging out [5:06] over possible next states. [5:09] We saw how this is a property of the optimal value function, [5:12] but we discussed this how a similar fixed point [5:15] equation holds also for any policy, pi, [5:18] where very similarly, this fixed point equation, that [5:21] is the Bellman expectation equations [5:23] is defined as we introduce also a couple of weeks back. [5:30] We did a very similar discussion for the Q function, [5:34] that is, essentially a measure to represent [5:37] our expected future reward starting from some state, xt, [5:41] taking an action, ut, and then following a given policy, pi. [5:45] Again, very similarly, here we have some fixed point equations [5:48] which these concept satisfy, which are namely [5:52] the Bellman optimality equation and expectation [5:54] equation for the Q function, respectively. [5:58] Why did we introduce the Q function? [6:00] We introduced it because from the control, [6:02] from the perspective of developing an optimal policy, [6:06] this is a pretty useful in practice [6:09] because it allows us to define a policy implicitly through the Q [6:14] function as the argmax over u of the Q function [6:19] defined on some state, x. [6:22] And so very practically, at least [6:24] from the perspective of tabular methods, [6:27] that is the one we'll be looking at today, [6:29] so where we don't discuss function approximation, [6:31] I think it's useful to visualize value functions, [6:34] both state value functions and Q functions as just lookup tables. [6:39] So the value function, v of x, you can namely visualize it [6:43] as the value for any specific state x1 to xn, assuming we [6:50] have n possible states. [6:52] And very similarly for the Q function [6:55] this would then be a matrix representing possible Q values [7:00] for all states and all controls. [7:09] OK, so we said how these were essentially interesting [7:11] properties that derived from this infinite horizon Markov [7:15] decision process problem setting. [7:18] And we then operationalize these concepts [7:21] into practical algorithms specifically [7:23] through, as we were saying before, [7:26] value iteration and policy iteration. [7:28] And in these algorithms, they essentially [7:30] boil down, if you remember, as mechanisms where we iteratively [7:37] enforce these fixed points equations until convergence. [7:41] So in value iteration, we recursively [7:44] enforce the Bellman optimality equation [7:47] until we converge to the optimal value function. [7:50] And for policy iteration, we alternate it [7:53] between step, which we call the policy evaluation step. [7:57] That is, the application of the Bellman expectation [7:59] equation that we are trying to estimate [8:01] the value of a given policy. [8:03] And then we had the policy improvement step [8:05] which turned out to be a greedy policy improvement, in our case. [8:09] So long story short, we have seen all of these objects [8:12] before. [8:12] And in the past, we derived actionable algorithms [8:16] to solve Markov decision processes by basically enforcing [8:21] these Bellman equations. [8:22] But in order to do this, we always [8:24] leveraged the knowledge of the dynamics function. [8:33] So looking a little bit more closely at policy iteration, [8:36] because this will be a concept we'll be building on today, [8:40] if you recall, policy iteration is essentially [8:42] an iterative algorithm where we are given an initial policy, pi. [8:46] And for every iteration, k, that ranges from 1 [8:49] until some convergence or termination criteria is met. [8:53] We're basically alternating between these two processes [8:56] which visually we could visualize here on this slide. [8:59] We have a given initial guess for our value function [9:02] and a given initial policy. [9:04] And we alternate between the policy evaluation [9:06] step, which basically evaluates the value [9:09] function for that policy. [9:11] And then we have a policy improvement step, [9:13] which, on the other hand, uses the most recent estimate [9:17] of the value function to derive a better policy from that. [9:24] How did these two processes look in practice? [9:27] For the policy evaluation step, we recursively [9:29] enforced the Bellman expectation equation as we defined before. [9:34] And for the policy improvement step, [9:35] we were basically taking the argmax over u. [9:41] Yeah, so note again that in both of these formulations, [9:45] we're leveraging the fact that we [9:46] have the knowledge of the dynamics function. [9:53] So more concretely, let us look at how [9:56] this looks from an implementation [9:58] perspective in practice. [10:00] Let's consider this gridworld example [10:02] where we have this basically 16 dimensional world where [10:08] we could be in either of these grid cells. [10:11] We have 14 non-terminal states, that is the white cells. [10:16] And we have two terminal states or goal [10:17] states that we want to reach. [10:19] So loosely speaking, the goal here [10:21] is will be spawned in any of these cells. [10:25] And the goal is to get to the goal terminal cells [10:28] as fast as possible. [10:31] How do we encode this objective of getting to the goal point [10:34] as fast as possible? [10:35] An idea could be to just fix the reward to be minus 1 [10:39] or any negative number until we reach the terminal cell. [10:46] In this case, we're assuming we can [10:48] take these four possible controls so the four [10:51] cardinal directions. [10:52] And if we take some of our controls [10:54] that would lead us out of this grid cell, [10:56] we just stay where we are. [10:57] We're doing this assumption. [11:00] And for simplicity of calculation, [11:01] we're assuming that we have an undiscounted MDP where [11:04] gamma is equal to 1. [11:08] So, in practice, let us take a first step in the policy [11:12] iteration algorithm. [11:13] So we say that we have a given initial policy. [11:17] And for now, for simplicity, since we [11:18] have potentially no clue about what a good policy is, [11:21] we just assume that our policy is a random policy. [11:24] So in all states, we just take a random action [11:26] with equal probability. [11:28] Again, we have potentially no clue [11:30] of how to initialize the value function. [11:32] So we might just initialize it as all zeros. [11:36] So here on the left column you're [11:39] basically seeing different iterations [11:42] of the policy evaluation step. [11:46] So we are enforcing the Bellman expectation equations at k [11:50] equals 1, k equals 2, until we converge. [11:56] So concretely, say we are at this grid cell over here. [12:00] So the coordinate 2, 2 what we're doing [12:05] is that we are updating the value [12:10] at that specific state as the current estimate of our value [12:20] function. [12:22] So the reward plus the expected future values in the next states [12:32] that we would expect to be in. [12:34] So more formally, we have this negative 1, which is just [12:37] the reward of taking one step. [12:40] And then we have the expectation of all possible next states, [12:43] which in our case, are equally distributed around the four [12:47] possible neighboring states. [12:49] So we'll be looking at xt plus 1 in 1, 2 to 1, 3, 2 and 2, 3. [13:06] So we are looking at wanting to update this cell over here. [13:11] So the reward of taking any move is minus 1. [13:15] And then we have to take the expected value of the next state [13:21] that we land in, which is in our case one of these four states. [13:26] And when we take the expectation under our transition dynamics, [13:30] there is the probability of being [13:31] xt plus 1 given xt and the action that we [13:36] would take in xt times the previous estimate of the value [13:42] function. [13:43] So this is v1, if you wish, and this would be v0 in that state. [13:52] So here, nothing too fancy. [13:54] I just basically formalized what we are writing the Bellman [13:58] expectation equation. [13:59] Yes. [14:00] Is it kind of just convention that k [14:02] equals 0 you have all zeros rather than just initializing [14:06] with the value or rather with the reward for each state? [14:11] That's just a choice. [14:12] So if you have knowledge in general, knowledge [14:14] in your problem that you wish to encode as a starting point, [14:18] then it's definitely a good idea to do so because it just speeds [14:21] up the convergence. [14:22] But in this case, we just assume we have no knowledge whatsoever. [14:25] And we start from all zeros. [14:27] So in this case, well, we know that our previous guess [14:30] was all zeros. [14:31] So this is always 0. [14:33] In theory, we would know that this is equally distributed [14:37] across our four steps. [14:38] So this would be always 0.25. [14:41] But, in general, since we have a 0 term here, this cancels out. [14:44] And so for all the grid cells in k equals 1, [14:46] we would actually get minus 1. [14:50] And you can then imagine that if we repeat this process [14:53] across iterations, we basically get an evolving surface [14:57] of our value function. [15:02] And if we do this until convergence, [15:04] we would then get something that looks like this. [15:07] So at this point in our algorithm, essentially, [15:10] we have taken, again, visualizing it here [15:13] in our sketch, we basically took one step [15:15] in the policy evaluation step. [15:17] So we concluded a full policy evaluation [15:20] step where given a policy, we estimated the value [15:23] for that policy. [15:27] What is the next step then here according to the policy [15:34] iteration algorithm? [15:37] Yes. [15:37] We want to use those expected values [15:40] to derive a different policy. [15:43] Yeah, exactly. [15:44] So we want to then take basically [15:47] do this step, which is the policy improvement step. [15:49] How did we define it so far? [15:51] We basically take this argmax over this quantity over here [15:58] which essentially means that the theta we converge to this value [16:05] function over here the policy that maximizes this value [16:08] function, since the reward is always minus 1, [16:12] no matter what we do, the policy will basically converge [16:16] to taking the action, u, which leads to the best, [16:22] the state with the best value function value. [16:25] So from here, we could immediately even [16:28] visually see that in each of these grid cells, [16:30] we're basically the policy that we [16:32] get from that policy improvement step essentially [16:34] would be pointing towards the state with the neighboring state [16:38] with the best value function, which [16:42] is exactly what we get here. [16:44] So this would be the visualization of the policy [16:47] that we get out of the policy improvement [16:48] step from this value function, which we estimated before. [16:58] Now, of course, if you, in general, we [17:04] run a full policy evaluation step until convergence [17:07] in this case, but you can always hypothesize doing the policy [17:11] improvement step at intermediate steps in our policy evaluation [17:14] iterations. [17:15] In this case, since this is a very simple problem, [17:18] you would actually get the optimal policy [17:20] even if you stopped before convergence. [17:23] But this is not guaranteed to be the case, in general. [17:28] For example, here if we stopped immediately and did the policy [17:32] improvement step here, we would get [17:33] a policy that is still slightly better from the original one [17:37] because we do get some nice behavior here [17:39] where we're not random anymore, but still not there yet. [17:43] Yes. [17:44] Is not having-- is a stationary policy enough of a signal [17:51] to say that you've converged? [17:53] Or is it possible that between iterations you [17:54] could have a policy not change? [17:56] But if you continued and the value function [17:58] continues changing then you might update the policy [18:00] later on? [18:01] Yeah, so in general, I guess the question [18:03] is, how do you define termination criterion [18:05] for this case? [18:06] So, in general, for these tabular settings where [18:09] we can actually enumerate all the possible value functions, [18:13] so values for each states and each state action pairs. [18:16] This is proven to converge. [18:18] So there is no-- [18:20] if you run this long enough, you will be converging. [18:23] In general, there are different types of termination criteria [18:26] you could come up with. [18:27] Some could be like delta based. [18:30] So depending on how much it changes across iterations [18:32] and there is no real one best rule for doing that, [18:37] if makes sense. [18:38] So to answer to your question, in this case, [18:40] as long as you run it long enough, [18:42] you will be converging to the optimal value [18:44] function and policy. [18:53] And so you will notice also running through this example [18:57] that all of these formulations, in this case, [19:00] we looked at policy iteration. [19:01] But the same thing holds for value iteration. [19:04] All of these formulations require a model of the MDP. [19:07] So we use the transition dynamics [19:08] to update our quantities. [19:13] In general, to solve unknown MDPs, [19:15] that is MDPs where we don't have access to the ground truth [19:20] transition dynamics, we'll use interactions [19:23] with the environment to replace this knowledge. [19:26] And so more generally speaking, the main limitations [19:31] of these exact methods, such as policy and value iterations [19:36] are mainly two. [19:37] The first one is that the update equations require access [19:40] to the dynamics, and we'll use sampling-based approximations [19:44] to basically solve and address this challenge. [19:49] And we'll see this more shortly. [19:51] And the other one is that iteration over [19:54] and storage of all of the states and actions [19:57] and the values for the states and actions [19:59] can require an extreme kind of a large memory effort. [20:03] And also it could just lead to very long far away convergence [20:08] for these algorithms. [20:09] And so whenever we have a very large state action space [20:13] we'll see how function approximation [20:14] could come in handy. [20:16] Today we'll be mostly looking at sampling based approximations. [20:19] But starting from next week, we'll [20:22] also be looking at function approximation. [20:28] Any questions here before we get started [20:31] with the first algorithms? [20:39] So let's start from Monte Carlo learning. [20:43] And the idea of Monte Carlo is actually extremely simple. [20:47] So we are saying that we are interested in estimating [20:57] these values for value functions in general. [21:01] And we want to do this using samples. [21:06] What do we mean with samples in our case? [21:08] So we have an environment which we assume we can interact with. [21:12] And interactions, essentially, means collecting rollouts. [21:15] So we will be releasing our policy in the environment [21:19] and collecting the rollouts that we get from the environment. [21:22] So this means collecting a sequence of states and controls [21:26] over time until we reach some termination criteria here. [21:32] Now, in principle, what we are interested in when we talk about [21:37] in this case, for example, the value of state x1 [21:41] would be to basically approximate the expected future [21:47] rewards that we would expect to have if we were able to simulate [21:53] infinitely many scenarios. [21:54] I'm interested in the ground truth expectation of this value [21:58] function. [22:00] To do this, so far, we've leveraged knowledge [22:03] of the transition dynamics. [22:05] But, in general, this is not possible. [22:07] So we want to do this through sampling. [22:09] And this means that in Monte Carlo, what we do [22:12] is that we basically want to approximate this expected value [22:19] function or expected future reward through the return. [22:22] The return for us, let's remember, [22:24] that it's just the-- or at least the return of a trajectory [22:27] in this case, at time t, is just the sum of all the rewards [22:31] that we observed from time t onwards. [22:43] Again, simply put, the return starting from x1 [22:46] would just be having our trajectory [22:49] evaluating all of the rewards that we got over time [22:52] and summing them up. [22:58] And the idea is that if we were to repeat this multiple times, [23:01] so we don't have only one trajectory, [23:04] but we have multiple, we would be essentially [23:06] able to approximate this ground truth expectation that we're [23:10] interested in through the mean, the empirical mean, essentially. [23:20] Does this make sense? [23:31] And so because of this, essentially, Monte Carlo methods [23:35] are methods that directly learn from episodes of experience. [23:39] And it is model free. [23:40] So there is no knowledge of the transitions [23:42] that we're using here. [23:44] We're just using interactions or samples from our environment [23:47] to approximate these values. [23:52] One caveat, of course, which is also a pretty important one, [23:55] is that because of how we define the return, which is literally [24:00] the sum of all the rewards that we observe [24:02] throughout our trajectory, Monte Carlo methods apply only [24:07] to episodic MDPs. [24:09] So there needs to be a termination [24:11] of our episode at some point simply because otherwise, we [24:14] would be continuing to summing up rewards forever, essentially. [24:23] So how do we use this in practice? [24:26] Kind of an immediate thought there [24:28] would be to use Monte Carlo methods for learning the state [24:32] value function, v. So recall that we defined [24:36] the return as just the discounted sum of future rewards [24:40] from given a trajectory. [24:43] In principle, we are interested in approximating [24:46] this expectation here, which is just our value function. [24:49] So, for us, the value function is the expected future reward [24:53] that I expect to have starting in xt following a policy, pi. [24:58] And if you look at this inner term here, [25:00] this is nothing else than the return itself. [25:04] So of the value function is actually the expectation [25:11] of the return given state xt. [25:21] And so with Monte Carlo methods, we essentially or specifically [25:24] with Monte Carlo policy evaluation what [25:27] we would be doing is that we use the empirical mean [25:30] to estimate this expectation instead of computing [25:34] exactly this expectation through the knowledge of the dynamics. [25:51] In practice, you could have two variants of Monte Carlo methods. [25:57] The first is referred to as first visit Monte Carlo, where [26:02] in order to evaluate the value function at a given state, [26:06] we would be essentially computing these means, [26:09] these mean returns. [26:11] Only the first time we visit a specific state in an episode. [26:16] So, in practice, once we visit a specific state, x, [26:21] we would be incrementing the counter of how many times [26:24] we visited that state x. [26:26] We would be incrementing the total return. [26:29] So that is all the returns that we ever [26:30] saw when visiting that state and then just taking the mean. [26:37] And, in general, the assuming we have the more samples [26:43] of this trajectory we would have. [26:44] So with n going to infinity, we would [26:47] be converging to the ground. [26:49] Truth expectation. [26:55] The other approach is the every visit approach, [26:58] where now we account explicitly for the situation [27:01] where maybe within our rollout, for some reason, [27:06] we are maybe visiting state x1 again. [27:09] So we are maybe taking some detour, [27:13] and we end up in the starting state again. [27:15] In the first visit, we would basically be ignoring the return [27:19] from the second visit onwards. [27:21] In the every visit, we just consider [27:23] these two as independent visits and update the mean regardless. [27:29] Again, this is just a kind of technicality when you look [27:32] at implementation, but the overall idea is that we want [27:34] to approximate these expected future rewards because we cannot [27:40] compute these expectations exactly, [27:42] we approximate them through an empirical mean. [27:52] [INAUDIBLE] revisit the same state over and over again to do [27:54] different trajectories, wouldn't it be-- [27:58] I don't know if unfair is the right word, [27:59] but to exclude that from your database [28:02] with the first visit mentality rather than doing [28:06] the every visit mentality? [28:08] Yes, I think it's a valid point, especially [28:10] if you have these maybe degenerate cases where [28:13] the policy is visiting the state over and over. [28:17] I would say in general, this probably [28:19] boils down to you want to have sufficient exploration. [28:24] So you want a policy that basically explores your state [28:28] action space well enough for these tools [28:32] to be efficient and effective in practice. [28:36] But yes, so when you have these cases, [28:38] it is a valid discussion to consider like, [28:42] should I go for an every visit example or a first visit case? [28:45] Maybe in that case, the first visit is what you want. [28:51] If you're saying this will be used [INAUDIBLE], [28:54] site an example like in practice. [28:57] [INAUDIBLE] if you're not able to run this and collect [29:00] this data on simulation based on some model that you have, [29:04] it would be difficult in practice [29:05] to set up some experiment and collect all this data. [29:10] Yes, this is a good question because in general, [29:12] so here, when we talk about model free, we refer to the fact [29:15] that we're not leveraging a known model of the dynamics [29:19] within our calculations. [29:21] Now, you could indirectly use it by having interactions [29:26] with the simulator. [29:28] But, in general, here this is agnostic to any kind [29:33] of environment and reality we are interacting with. [29:36] So by model free here, we just mean [29:38] that we are modifying all of our update equations, [29:43] saying the policy iteration case to avoid [29:46] using an analytical expression of the transition dynamics. [29:51] So in practice, I would say leveraging a simulator here [29:55] would be a concrete example of using this. [29:58] So we have some simulator that simulates our environment, [30:02] say a driving simulator. [30:03] And then we want to use these tools to estimate a value [30:07] function within that simulated world. [30:10] But we're doing this without leveraging [30:12] the potentially extremely complex model that [30:14] runs under the hood in the simulation, if that makes sense. [30:21] Yes, does it clarify? [30:26] Yeah, so bottom line is model 3 here just refers to the fact [30:28] that we're not using the transition dynamics. [30:37] So let's look at an example. [30:42] So here consider the game of blackjack, which we're probably [30:46] most of us are familiar with. [30:47] But in general, here we are assuming [30:49] that we have a state where we are dealt two cards. [30:56] We're playing against a dealer that also has two cards. [30:59] The state for us is that we are considering the current sum [31:03] of the two cards that we have in hand that ranges from 12 to 21. [31:08] We're also specifically recognizing [31:12] if the dealer's showing card. [31:16] So we have visibility of one of the two cards of the dealer, [31:19] so from ace to 10. [31:21] And we are specifically having a flag if we have a usable ace [31:25] or not. [31:25] So we have an ace in hand or not? [31:29] In this case, of course, the goal [31:31] is to beat some of the dealer essentially having the hand [31:38] that reaches closer to 21. [31:41] The way we do this is by-- [31:44] so we have two possible actions. [31:45] So at any point in time, either we [31:47] stand so we stop receiving cards and the game terminates [31:51] or we hit, that is, we ask for another card [31:54] without replacement. [31:57] In this case, the reward for us is that when we stand. [32:00] So where the game terminates, we get a plus 1 reward [32:04] if some of the cards essentially beats one of the dealer, [32:08] we have 0. [32:09] If we have a tie, and we have a negative reward [32:12] if we lose against the dealer for the hit, [32:17] when we actually ask for another card, [32:20] we get a negative reward if we go above 21 [32:23] where the game terminates and we get 0 otherwise. [32:29] So we, in general, we are assuming that we automatically [32:34] hit if our sum of cards is below 12. [32:37] This is the only assumption that we have on the transitions. [32:40] So in this case, we want to consider a given policy. [32:43] So we are given to us this policy which basically stands [32:46] if the sum is greater or equal than 20 [32:48] and always hits otherwise. [32:50] And so the goal here is let's now take [32:52] this environment with these rules [32:54] and basically run policy evaluation through Monte Carlo [32:58] sampling in this environment. [33:03] Is this setting clear? [33:05] Nice. [33:06] So we'll be blackjack experts after this, I guess. [33:10] So what we're looking at here is assume we are running policy [33:15] evaluation for 10,000 episodes or 500,000 episodes. [33:21] So again, here what we're saying this [33:23] would be one episode of interaction. [33:26] We're assuming we are playing 10,000 and 500,000 games with [33:31] the dealer. [33:32] And these three dimensional landscapes [33:36] are essentially a visualization of the value function. [33:40] So here, specifically, we have two axes. [33:42] One axis is looking at the dealer showing card that [33:47] ranges from an ace to a 10. [33:49] We have a player sum, so the sum that we [33:52] have in hand from 12 to 21. [33:54] And we have the surface kind of differentiated [33:59] between when we have a usable ace [34:01] and when we don't have a usable ace. [34:03] So this is just our state space if you remember those three [34:06] bullet points. [34:08] So what we see is, first of all, you see a difference between [34:13] the column that relates with the 10,000 episodes and the 500,000 [34:17] episodes in terms of noise. [34:19] So these estimates are definitely [34:22] more noisy than the ones where we have more episodes. [34:28] Again, the reality is that here we [34:30] are approximating these expectations [34:32] through empirical means. [34:33] And so the more episodes we have, [34:35] the more we are converging to the ground truth solution. [34:41] And to basically maybe understand [34:45] to get your understanding here, let us look at some questions [34:48] and have some questions for you. [34:50] So consider specifically the diagrams on the right. [34:54] So why does the estimated value function [34:58] jump up for the last two rows here in the back? [35:03] Yeah? [35:04] Because those are the only thing [INAUDIBLE] 20 and 21, [35:09] we always hit until we get there either most [35:11] of the time we're in a bust. [35:13] But if we do get there, we're probably [35:14] going to win [INAUDIBLE]. [35:17] Yeah, exactly. [35:18] So we're playing a game with our policy that is given to us, [35:21] where we only stand if we are 20, 21. [35:24] And if we do, that's a pretty good hand so we likely win. [35:29] So exactly correct. [35:31] And another question would be, why does the value function [35:35] drop off for the whole last row on the left on the other hand? [35:45] When the dealer has an ace, so they're [35:48] likely to have a 10 to get one. [35:50] Exactly. [35:51] So also just having an ace is a good hand. [35:56] So you can use this in different ways. [35:58] And so that's on average is something where [36:00] the dealer is well positioned. [36:03] So, in general, of course you see how the bottom line here [36:07] is that in policy evaluation, we basically [36:12] had no information whatsoever on how the game works [36:17] or any dynamics of this game. [36:19] We basically leveraged simulation, if you wish, [36:22] or interactions with the environment [36:24] to estimate future values of all the states. [36:29] And what we get is through this interaction, [36:32] a complete representation of the value of every possible state [36:37] that we could find ourselves in this game. [36:39] And so given this policy that is given to us, [36:42] we have exactly characterized its efficacy [36:47] in all different states, if that make sense. [36:50] And this value function is, to some extent, [36:54] interpretable because we can more or less understand it [36:57] and it's reasonable. [37:04] As a just note, in general, we're [37:10] talking about in Monte Carlo. [37:12] We're leveraging empirical means to approximate expectations. [37:16] Of course, these episodes will be coming in incrementally. [37:21] And so it doesn't make sense to recompute the means from scratch [37:25] or store all the possible rewards that we ever observed. [37:29] But, in practice, we often compute the means incrementally. [37:33] And so we know that this is a standard result that we [37:36] can compute the mean for a given realization, x, [37:43] incrementally through this equation over here, [37:47] where we're essentially updating the mean [37:50] as the previous estimate plus basically [37:54] a step in the direction of the new observation. [38:00] So this is, in general, for incremental means. [38:03] Of course, for us, the mean that we're interested in computing [38:07] is the expected return, the mean return, [38:09] which for us, is our estimate of the value. [38:12] And so we'll be updating our value, [38:16] our estimate for the value function as the previous guess [38:20] plus basically a step in the direction of the new return [38:24] that we have observed. [38:30] So this is the exact formulation for the incremental mean. [38:33] In practice, we will often see this expressed very similarly [38:38] to what you would see a gradient descent step update rule where [38:43] we could have a varying alpha, basically [38:47] a scalar that changes how big of a step [38:49] we're taking in the direction of the update. [39:00] Any questions on Monte Carlo before we move to TD learning? [39:09] So Monte Carlo is one, I would say, [39:13] really fundamental strategy for model free learning. [39:16] TD learning is, I would say, the other bigger player [39:19] in when we talk about model free learning techniques. [39:23] And specifically, at a high level, [39:25] TD learning is a combination of Monte Carlo [39:28] and dynamic programming approaches. [39:31] So like Monte Carlo, TD learning is model free, [39:35] so there is no knowledge of the transition dynamics in our MDP. [39:41] And TD learning also learns from experience. [39:43] So we are replacing this knowledge [39:45] through interactions with the environment. [39:50] On the other hand, different kind [39:52] of differing from Monte Carlo but similarly [39:55] to dynamic programming, temporal difference [39:58] learning update estimates of, for example, values [40:03] based in part on other learned estimates. [40:06] Essentially, we can update our guess towards a guess [40:10] without waiting for the final outcome in our episodes. [40:15] More formally, it is denoted as temporal difference learning [40:21] and dynamic programming bootstrap. [40:24] So remember how in dynamic programming, [40:30] we were essentially saying that we [40:32] could have a recursive function where the value function for us [40:39] would be at a state xt would be equal to the immediate return, [40:44] a reward that we see at xt plus a discounted future value [40:50] at the next state, xt. [40:54] Now, in TD learning, since we cannot compute these [41:00] expectations exactly, because in order to do this, [41:03] we would have to have knowledge of our transition dynamics. [41:06] We use samples to approximate this expectation. [41:10] So in Monte Carlo, we were using the full trajectory [41:13] to directly estimate the return. [41:17] In TD, we are only interested in the one step update [41:22] where we will be updating the value of x1 [41:28] basically in the direction of the immediate reward [41:34] that we see, R1 plus the discounted value at x2, [41:41] in this case. [41:43] So we'll be using the same property [41:45] that we can use our current estimate for the value function [41:49] to basically approximate all future rewards [41:53] that we would have observed going forward with the episode. [41:59] So more concretely, let us look at the specific definition. [42:02] In Monte Carlo, we said that we want [42:06] to update our value estimate towards the actual return, GT. [42:11] Specifically, we take a step alpha [42:14] in the direction of the return. [42:18] In temporal difference learning, we [42:20] update the value towards the estimated return [42:24] where this estimate is taken using basically [42:27] dynamic programming ideas, where we [42:29] take the immediate reward plus the discounted [42:32] future estimate of our value. [42:38] And so, specifically, we take a step [42:40] in the direction of this target over here in red. [42:44] So, in general, the reward plus the discounted future value [42:49] is referred to as the TD target. [42:52] And the difference between our guess and this TD target [42:57] is known as the TD error. [43:03] So, in general, you see how temporal difference methods [43:05] combine the sampling of Monte Carlo [43:08] because we're only leveraging interactions [43:10] with the environment to estimate our values [43:12] with the bootstrapping of dynamic programming [43:14] because we're updating a guess towards a guess. [43:22] Yes. [43:24] For the first one, the GT, does that mean [43:26] you have to run a bunch of rollouts at each update step [43:29] to figure out what the actual return would be? [43:32] So here this is independent of how many rollouts you do. [43:36] So here we're saying that we want [43:38] to approximate the actual return. [43:44] So that is the sum of all future rewards through sampling. [43:47] Specifically, here we could take one sample [43:50] of the return, which just means summing all the rewards that we [43:55] see over time. [43:58] Visually, we want to approximate this ground truth expectation [44:02] over here. [44:03] And we could do this by just evaluating the empirical returns [44:08] that we observe over time and taking a mean. [44:12] Now, GT is just the definition of the return. [44:16] And so for us, assuming we have one sample, [44:19] this would be a one sample estimate [44:21] of the actual expectation. [44:23] In temporal difference learning, instead of [44:26] looking at the final return here, [44:29] we actually look at the one step estimate [44:32] of that return where this estimate is just [44:35] the instantaneous reward, R1, plus the discounted [44:39] guess of the value here. [44:42] So, in other words, our guess here [44:44] is just a mechanism to avoid having [44:46] to run through the entire episode [44:48] but approximating what this rest of the return [44:51] would be at time 2, in this case. [44:55] Does this clarify? [45:04] [INAUDIBLE] [45:14] So, in general, so the interaction [45:16] will always be for full rollouts. [45:21] So we'll be having full interactions [45:24] with our environment. [45:25] But then this is changing how we update our value estimates. [45:29] In the Monte Carlo case, we update our value estimates [45:33] looking basically one episode at a time the full episode. [45:37] In TD learning, we can actually update our value estimates [45:41] more often, because this would basically [45:43] be only one update, if that makes sense, [45:47] because we only have one return. [45:49] Here, we can update our value function [45:53] before the episode finishes, potentially, because we just [45:56] use our guess to do so. [45:59] [INAUDIBLE] [46:00] Potentially, potentially. [46:08] Yeah, so looking at differences more closely, [46:13] we mentioned how Monte Carlo learning essentially [46:16] requires episodic MDPs because we need to reach that terminal [46:19] state at the end. [46:21] On the other hand, in TD learning, because we are only [46:24] using our own guess to estimate the values, [46:28] TD learning can learn before the final outcome, essentially. [46:33] And so TD learning can potentially [46:34] learn online after every step. [46:36] But Monte Carlo must wait until the end of the episode [46:39] to collect those returns. [46:44] And so, indeed, TD learning can learn without the final outcome [46:48] and so can learn from potentially incomplete sequences [46:53] and can potentially work in continuing or non-terminating [46:56] environments. [46:57] But, on the other hand, Monte Carlo [46:59] requires this determination. [47:11] Does this make sense? [47:17] So I would say, really, Monte Carlo learning and TD [47:20] learning are the fundamental mechanism through which we [47:25] estimate quantities of interest. [47:28] Most of the times, these are values and value functions. [47:31] And that these are really the foundations over which [47:36] all other kind of reinforcement learning algorithms [47:38] are built on. [47:40] Either if these are estimated are kind of value-based methods [47:43] or policy optimization methods we will [47:45] see actor-critic, and so forth. [47:47] All of these tools essentially rely on some approximation [47:51] of value functions. [47:53] And when we don't have a knowledge of the transition, [47:55] then we have to resort to interactions [47:58] with the environment and leverage tools similar to Monte [48:02] Carlo and TD learning to do so. [48:09] [INAUDIBLE] [48:17] How could that working out for environments like-- the way I'm [48:20] understanding is that do not recursively [48:22] go back from the final state to understand [48:25] the value of that final state and work backwards to, say, [48:28] that's [INAUDIBLE]. [48:31] I think I'm misunderstanding how you would do that [INAUDIBLE]. [48:36] No, I think you have the right intuition because basically, [48:39] what you're saying is, I get that the point that we're [48:43] updating our guests towards our next guests [48:45] and how this could mechanically work online at each step, [48:49] even without relying on the final step, [48:51] but you're saying at the end of the day, [48:53] we need to ground some of our estimates on an actual value. [48:58] And I think this is correct. [48:59] And this is exactly where the discount factor comes into play [49:03] because if you take the extreme version where the final, [49:09] we are at step 500,000 in the future, [49:12] then here the future values will essentially be very close to 0. [49:16] And so we will have a way to estimate these value [49:20] functions that are not exploding to infinity, [49:23] if that makes sense. [49:30] OK, so we're basically saying we're [49:32] interested in estimating values and value functions. [49:36] We introduced these two ways of doing so, [49:38] Monte Carlo and TD learning, which are essentially [49:42] estimators of a quantity that we're [49:44] interested in approximating. [49:46] That is the expected future reward or the cost to go, [49:50] the reward to go, in this case. [49:52] So let us look at properties of these two estimators. [49:56] So specifically, the bias and variance [49:59] of these two estimators. [50:01] So let us take Monte Carlo to start. [50:07] So we're interested in estimating [50:09] the true value of our policy. [50:13] And we're saying that in order to do so, [50:15] we want to use the return, which is just [50:17] the sum, the discounted sum of all the rewards [50:20] that we observed. [50:21] Now, of course, this return is an unbiased estimate [50:25] of the ground truth value. [50:28] Again, using an extreme example, if the expectation that we're [50:35] actually interested in would be the expectation [50:38] over all possible future evolutions [50:40] or episodes in our environment. [50:43] And the return is just a sample from this. [50:48] If we take an infinite amount of interactions and episodes [50:52] with our environment, we would be converging to the ground [50:56] truth expectation. [50:58] So in this sense, this estimator is actually [51:00] an unbiased estimate. [51:04] In principle, the true TD target that [51:09] is for temporal difference learning, [51:11] is also an unbiased estimator of the actual value. [51:16] But this is only if we assume we already know what the true value [51:19] function is. [51:21] So here we're saying we're using this value [51:24] function at the next step to basically approximate [51:28] the future reward. [51:30] And if the value function is exact, [51:33] then this would actually be an exact characterization [51:36] of the expected reward to go. [51:38] But, in reality, we won't be using the exact, [51:41] the true value function, basically, [51:43] just for the purpose of learning is trying [51:46] to estimate the value function. [51:47] And so we will actually be using an estimate. [51:49] Kind of a v hat for our value. [51:52] And so since this estimate won't be exact, [51:56] we're introducing some bias. [52:05] Does this make sense? [52:14] OK, and how about variance? [52:17] So, in general, the TD target is a much lower variance estimator [52:26] than the return. [52:29] And this is because the return depends [52:31] on a full sequence of random actions, transitions, [52:35] and the reward realizations. [52:38] On the other hand, the TD error kind of only [52:41] depends on one kind of sample of basically stochasticity [52:46] of a random action transition and reward. [52:49] So here we're saying that in order [52:52] to approximate the future reward to go, [52:54] we are either approximating through the return [52:57] that we evaluate here or we approximate it [53:00] through the TD target. [53:05] So basically, in this case, r1 plus v x1. [53:11] So in the former case, in order to compute the return GT, [53:19] we're basically sampling multiple times [53:22] over the episode where sampling means [53:25] we have potentially unknown kind of stochastic transition [53:29] dynamics that we are repeatedly sampling from. [53:35] We have potentially stochastic policy [53:41] that we're potentially sampling from. [53:43] And the reward itself might be stochastic reward. [53:46] On the other hand, in the TD for the TD error for the TD target, [53:51] we're doing the same sampling but only once. [53:55] And so in this sense, the return as an estimate of the true value [54:00] is actually a much higher variance estimator [54:03] because there are just many more possible futures [54:07] that we are kind of taking into consideration here. [54:18] So let's really drive this message home. [54:23] And I think it's useful to visualize this [54:25] through these sort of tree-like diagrams. [54:29] And specifically, let us look at Monte Carlo first. [54:33] So we basically introduced what is often [54:36] referred to as Monte Carlo backup, [54:38] meaning the update equation that we use for our value estimates [54:42] according to Monte Carlo learning. [54:45] And we defined this as updating our guess of the value function [54:49] by taking a step in the direction of the return. [54:53] What does this mean visually? [54:55] In this diagram, white nodes here [54:59] represent states and black nodes represent actions. [55:04] And t represents a terminal state. [55:07] So that is where the episode terminates. [55:09] And so you see how potentially in state xt [55:12] we could be taking two possible actions. [55:15] And depending on the action that we take, [55:17] we could land on potentially two different states. [55:22] In a Monte Carlo backup, this essentially [55:24] means that in this possible tree of all kind of futures [55:30] that we could observe in our environment, [55:32] we approximate the ground truth expectation of the values [55:36] by essentially taking a full episode of interactions [55:39] with the environment until we reach a terminal condition [55:42] and using the return that we observe over [55:44] here to update our guess. [55:51] Differently, in TD learning, we defined our update [55:55] as taking a step in the direction [55:57] of the immediate reward plus a guess of our future values. [56:04] And so this visually means that rather [56:06] than having to take a full episode of interaction [56:08] until reaching a terminal state, we only [56:10] look at the one step transition, if that makes sense. [56:19] On the other extreme kind of positioning this with respect [56:23] to what we saw with dynamic programming, [56:25] in dynamic programming, we were essentially [56:27] able to evaluate exactly these expectations through the use [56:31] of the transition dynamics. [56:33] And so we weren't really defining [56:35] these estimates of these expectations because we could [56:38] actually compute the exact expectation by basically [56:45] computing this expectation analytically [56:48] through the knowledge of the dynamics. [56:59] Any questions here? [57:11] So we've seen now how we introduced these two [57:19] basic techniques. [57:20] So we discussed sampling as essentially our mechanism [57:26] to approximate expectations through interactions [57:28] with the environment. [57:30] And we saw how both Monte Carlo and TD learning sample. [57:35] And this is because they're model free algorithms. [57:37] So we assume we don't have knowledge of the dynamics. [57:39] On the other hand, dynamic programming [57:40] does not sample because there we assume we [57:42] have knowledge of the dynamics. [57:44] And we could compute those expectations exactly. [57:48] We then discussed also bootstrapping [57:49] where the idea is to basically update [57:53] our guess towards a guess. [57:55] And we saw how both TD learning and dynamic programming [57:59] were using this idea while Monte Carlo did not. [58:04] And so, really, what we're doing today [58:07] is basically constructing or paving [58:13] a unifying view of all possible reinforcement [58:17] learning algorithms depending on these two axes. [58:20] And specifically, thinking about these trees [58:24] that we were observing before, different algorithms [58:27] fall on a spectrum depending on the width of the backup. [58:31] So we discussed algorithms that look [58:33] at the full width of the backup that [58:36] is dynamic programming or intuitively also [58:39] exhaustive search. [58:41] We could just sample infinitely until we explore the full tree. [58:46] Or, on the other hand, algorithms [58:48] that only sample use at the extreme one sample [58:54] from the environment. [58:55] And so we looked at temporal difference learning [58:58] and Monte Carlo learning. [59:00] Similarly, we looked at the height of the backup that [59:03] is through on one extreme Monte Carlo and exhaustive search [59:08] require reaching the end, so a terminal state [59:11] in order to update their values and TD learning [59:15] and dynamic programming instead relied only on a one step update [59:20] because they could use bootstrapping [59:22] to approximate their values. [59:26] Of course, these are just four extremes of a spectrum, [59:29] and you could envision algorithms laying somewhere [59:32] in between, right. [59:33] So, for example, you could assume rather than updating [59:38] your TD target after one step, you [59:41] might assume that you want to do four steps of experience [59:44] and then use the value function after four steps of experience. [59:49] And there are pros and cons when doing so. [60:05] OK, so let's now build towards if you want a first working [60:10] version of a reinforcement learning algorithm [60:14] using these tools. [60:15] So, in previous lectures, we introduced policy iteration [60:18] and also earlier today. [60:20] And we essentially discussed how this [60:23] is an algorithm that implements two interactive processes. [60:28] We have policy evaluation on one hand, [60:31] which given a policy estimates the value for that policy. [60:34] And then we have policy improvement, [60:36] where given a new estimate of the value function [60:39] we used it to improve the current policy. [60:42] In general, we will use the term generalized policy iteration [60:47] to refer to this general idea of an algorithm skeleton [60:51] or structure, whereby we will be iterating between these two [60:55] processes regardless of how these two processes are actually [61:01] specifically defined. [61:03] In policy iteration, we saw how the policy evaluation scheme, [61:07] the policy evaluation step was essentially iterative [61:12] enforcement of the Bellman expectation equation. [61:16] And for the policy improvement step [61:18] we used a greedy policy improvement. [61:20] So we were taking the argmax over the quantity defined [61:24] by the new value function. [61:27] But this is a general formalism. [61:29] And you will see how many algorithms actually [61:31] apply this skeleton. [61:38] So we mentioned how policy iteration specifically [61:42] required knowledge of the dynamics [61:44] in both of these processes. [61:47] So we use the knowledge of the dynamics [61:49] to perform policy evaluation through the Bellman expectation [61:52] equation. [61:53] And we use the knowledge of the dynamics [61:55] to improve the policy in our greedy improvement step. [62:00] So can we make this actionable through everything [62:04] that we learned today? [62:06] So the first thing that you might think of [62:08] is, can we replace the analytical policy Bellman [62:13] expectation equation through Monte Carlo policy evaluation [62:17] of the value function? [62:18] So the first step is we were given a policy, [62:20] and we want to estimate the value for that policy. [62:23] Can we do this through Monte Carlo policy evaluation, which [62:26] is what we've done today and potentially leave unchanged [62:32] the greedy policy improvement? [62:35] And the answer is that, well, yes, in the sense [62:38] that Monte Carlo policy evaluation will work, [62:40] and this is exactly what we've been doing today [62:42] in both in the Monte Carlo learning section. [62:46] But then the greedy policy improvement, as we said before, [62:49] relied on this knowledge of the transition dynamics [62:53] to update our policy, to take this argmax. [62:55] So this will not cut it in a way. [62:59] So kind of one thing is that we discussed [63:02] before how the Q function is a nice object in order to-- [63:08] and a convenient object in order to define a policy implicitly. [63:12] So let us just replace the value function, v, [63:15] with the Q function. [63:22] So now we're looking at a version of policy iteration [63:25] where we are doing Monte Carlo policy evaluation of the Q [63:29] function and then potentially greedy improvement. [63:33] So will this work? [63:37] What do you think? [63:38] Well, there is a spoiler on the slides, of course. [63:41] What do you think and why? [63:51] Well, the point is that it won't, in general. [63:55] And the idea is that here it kind of touches on, I would say, [63:59] a really fundamental issue and challenge [64:02] in reinforcement learning, which is one of exploration. [64:05] So the trade off between exploitation and exploration. [64:09] So let us look at this from the perspective of a simple example. [64:15] So say we have two doors and we need [64:19] to pick among these two doors and each of these two doors [64:22] will give us a specific reward. [64:25] This is in a way stateless environment [64:27] because we are always in the same state. [64:29] So we have nothing that conditions us [64:31] in picking the two doors. [64:33] But now say that we have no information [64:35] of the quality of the two doors and that we, first of all, [64:39] so we initialize our Q function randomly and then also randomly, [64:44] we basically pick the left door as our first interaction, [64:48] and we get a reward of 0. [64:50] So we basically update the value of our Q function as 0. [64:56] Now, we similarly execute in our environment, [65:01] and we pick the right door and we observe a reward of 1 [65:04] in this case. [65:04] So we update the value of the Q. Now, note that in general, [65:09] right now, the policy that we are executing in the environment [65:12] is a deterministic policy. [65:14] It is the argmax over the Q function. [65:17] So since we have basically created a situation [65:21] where the right choice is basically [65:24] dominating the left door, here and basically forever [65:29] we will always be choosing the right door. [65:32] And so this is potentially at loss of a better reward [65:37] that we might have had on the left door. [65:42] And so the problem here is once we estimate Q functions or state [65:48] action values through samples, then [65:51] we need to visit every state action pair in order [65:53] to approximate those values. [65:59] And deterministic policies do not allow for this exploration. [66:03] So a simple but effective trick and strategy [66:06] is to basically introduce some randomness [66:10] in how we explore the environment [66:12] and how we take decisions. [66:13] And a simple strategy is one of epsilon-greedy exploration. [66:17] Specifically, with some probability epsilon, [66:23] 1 minus epsilon, we will be consistent with how [66:26] we pick the action so far. [66:28] So we will just take the argmax over Q. [66:31] On the other hand, with some small probability epsilon, [66:34] we will be acting random. [66:36] So we'll just pick a random actions [66:38] from our possible action space. [66:42] This is a very simple trick but fundamentally, this [66:45] ensures that all actions are tried with non-zero probability. [66:50] And so this, on the long run, ensures that we [66:52] are visiting and exploring. [66:54] And that is having a nice coverage of our entire state [66:58] action space. [67:04] And so if you wish this builds and leads us [67:08] to a first working version of a reinforcement learning [67:12] algorithm. [67:13] That is something where we have Monte Carlo policy [67:15] evaluation of a Q function and then an epsilon greedy policy [67:19] improvement. [67:24] So since the goal for today is becoming experts at blackjack, [67:28] let's look at how the policy that we would [67:31] get if we run this in practice on the same environment [67:34] that we had before. [67:35] So now before we were focusing on policy evaluation. [67:39] So we were given a specific policy [67:41] that was standing if the sum of cards was 20 or above. [67:48] Now, we're actually doing the full problem [67:50] where we actually want to derive an optimal policy for the task. [67:56] And so here if you trust me, that by running exactly [67:59] the algorithm that we discussed so far, [68:02] we would basically be converging to this policy over here, [68:07] whereby we have a specific rule that we can also inspect where [68:12] depending on if we have a usable ace or not, [68:16] and the sum of the cards and the dealer's showing card, [68:19] we have an explicit rule of whether to stick or stand [68:23] or hit. [68:27] A note maybe intuitively that if we don't have a usable ace, [68:32] we're actually more conservative here. [68:35] So, of course, we can go into the details. [68:37] And I'm definitely not advising you to try this strategy if you [68:40] go in because who knows. [68:41] But this is the idea. [68:43] Again, we gave no clue, no intuition [68:46] whatsoever to the environment on how to behave. [68:49] And through this interaction, we derived both an optimal policy [68:53] and its respective value function. [69:02] OK, so to recap what we've been discussing so far, [69:07] so we started from exact methods for solving Markov decision [69:12] processes, namely policy iteration and value iteration. [69:17] And we said and recognized that these have some limitations. [69:21] Specifically, today we looked at the first of these two, [69:24] which is the one that in both the update equations [69:29] and of our estimates for the value function, that [69:34] is the Bellman equations. [69:36] And in the greedy policy improvement steps, [69:40] we were using implicitly our knowledge [69:42] of the transition dynamics. [69:44] And so, today, we focus on these two main classes [69:47] of methods and families of methods, MC learning [69:50] and TD learning to address this through interaction. [69:57] And so, indeed, so we introduced MC learning and TD learning [70:00] as examples of a spectrum, where depending on the height [70:06] or width of the backup, we could derive different algorithms [70:11] all under the kind of shared goal of solving [70:14] unknown MDPs through learning. [70:18] We did not discuss how we could deal with high dimensional state [70:21] action spaces, but we'll do this in the coming lectures. [70:27] Any questions here before I spend a few minutes [70:30] on some concluding remarks? [70:40] So if you recall, last week we were [70:42] looking at this taxonomy of reinforcement learning [70:44] algorithms. [70:48] Starting next week, we'll be looking at, in order, [70:52] we'll be looking at value based methods next Monday. [70:55] We'll then be looking at policy optimization and next Wednesday. [70:58] And then we'll be looking at model based algorithms. [71:02] Well, not next Monday because that's a holiday but next time. [71:06] And then we'll be looking at model based algorithms. [71:10] In general, I think it is really valuable [71:16] to see all of these algorithms as different instantiations [71:20] of a common, shared skeleton of our reinforcement [71:23] learning algorithm. [71:25] And specifically, this skeleton has three main processes [71:28] going on. [71:30] The first one is that all algorithms [71:32] will have some way of generating samples [71:35] because we want to learn from interaction. [71:37] And as we saw today, interaction for us [71:39] essentially means sampling episodes [71:43] from interactions with the environment, where the goal here [71:47] will be essentially to collect these trajectories [71:50] or episodes of interactions, tau, [71:53] and use these quantities to basically do something with it. [71:57] Specifically, we'll use these samples [72:00] from the environment to either fit a model [72:03] or estimate a return or a value. [72:06] So today we discussed extensively [72:08] how we might be interested in estimating value functions or Q [72:12] functions. [72:14] But, in general, we might also see [72:15] how we could use these trajectories to estimate [72:19] a learned model of our dynamics in model free RL. [72:23] Bottom line is we will have some interactions [72:25] with our environment, and we'll be doing something [72:27] with that interaction, which is, loosely [72:29] speaking either estimating some values [72:31] or fitting some model of our dynamics. [72:36] And then we'll use these computations [72:39] that we do in the second block to improve the policy. [72:42] Today, we saw how we are basically [72:44] using an epsilon greedy or greedy policy improvement step. [72:48] But we will see different ways of improving the policy. [72:53] For example, we'll see how in policy optimization algorithms [72:57] we will be taking gradient steps with respect [73:02] to some parameters, theta, which might represent [73:05] a parametric policy that we're defining in order [73:09] to optimize the RL objective directly, [73:12] that is maximized estimated return. [73:14] But we'll see this more next week. [73:20] But bottom line is I think this is a very useful mental model [73:24] to use when approaching different RL [73:27] algorithms because this is really [73:28] a kind of other core of what most of these are doing. [73:37] So if there are no more questions, [73:40] I'll see you next time with value-based reinforcement [73:43] learning. [73:44] Thank you.