DeepMind x UCL RL Lecture Series - Introduction to Reinforcement Learning [1/13]

Hello and welcome to this course on reinforcement learning. My name is Harvan Husselt, and I'm a research scientist at DeepMind in London. Every year, we teach this course on reinforcement learning at UCL. This year, it's a little bit different because, due to the pandemic situation with COVID-19, we are pre-recording the lectures. So instead of talking from a lecture hall, I'm now talking to you from my home.

The topic, of course, as mentioned, is reinforcement learning. I will explain what that means, what those words mean, and we'll go into some depth in multiple lectures to explain different concepts and different algorithms that we can build. I'm not teaching this course by myself; some of the lectures will be taught by Diana Bursa, and some will be taught by Matteo Hessel. Today will be about introducing reinforcement learning.

There's also a really good book on this topic by Rich Sutton and Andy Barto, which I highly recommend. This book will also be used as background material for this course. If you go to the URL shown here on the slide, you can access a free copy of that book.

Just a little bit of admin before we get started: for students taking this for credit at UCL, there's a portal called Moodle, and we'll be using that to communicate with you. So please check that for updates and use the forum there for asking questions. If you do that, then if we answer these questions, other people can also benefit from that interaction. Multiple people might have the same question, or people might have a question but not even realize that they have that question. So then it's very useful if you ask it publicly on that forum.

In terms of grading, we will have assignments which will be graded. This year, there will not be an exam.

Now about this course specifically: what are we talking about? The main question for this first lecture, especially, is just the question: what is reinforcement learning? I'll explain it a little bit, and then we'll go into a lot of depth into different subtopics of this question.

In order to understand what reinforcement is, it's actually useful to first ask the question: what is artificial intelligence, and how are these two related? It turns out these are closely related. To understand at least what I mean when I say artificial intelligence, I'm going to pop up a level, and we're going to turn first to the Industrial Revolution.

This is a period in time that started a couple of hundred years ago. One could argue this is all about automating repeated physical solutions or manual solutions, if you will. So think, for instance, of a steam train or a steamboat and how this replaced the manual labor of pulling a cart by yourself or using, for instance, animal labor, horses, to draw those carts.

Now, of course, some of that still happens; we still have manual labor, but we replaced a lot of that with machines. This led to the machine age, where we started replacing more and more things with machines. In addition to that, we also came up with new things that we could solve with machines. Even things that we weren't doing before, we could now make machines that could do those things for us.

Of course, this led to huge productivity increases worldwide, and it also fed into a new stage you could argue comes after this, which you could call the digital revolution. One way to interpret this is to say the digital revolution was all about automating repeated mental solutions. A classic example here would be a calculator.

We know how to add two numbers together; we know how to multiply two numbers together. In fact, we know that precisely enough that we can write a program and implement that on a machine, on a computer, if you will, and then automate that process in such a way that it's very fast and very precise. Therefore, we replace the slower mental calculations that we had to do before.

Now, this of course also led to a lot of productivity increase. But both of these phases have something in common, which is that we first had to come up with the solutions. Now, I'm going to argue that there's a next thing that you can think of, which is already ongoing, and that would be to allow machines to find solutions themselves. This you could call the domain of artificial intelligence.

Now, this has huge potential upside because if you are able to find machines that can learn for themselves to find solutions, then this takes away the responsibility on us to find a solution in advance and then to automate it. Instead, all that we need to do is specify a problem and a goal and then have the machine figure out how to solve this.

As we'll see later, this will often involve interacting; you have to have some data to find the solution, and this means that there's a process of learning. So here we already bump into this term learning, which I'll get into much more in depth.

In addition, this requires you to autonomously make decisions. I'm putting these terms basically up front and center: learning, autonomy, and decisions. These are all quite central to this generic problem of trying to find solutions.

Of course, we're not the first to talk about artificial intelligence. This has been a topic of investigation for many decades now. There's this wonderful paper by Alan Turing from 1950 called "Computing Machinery and Intelligence." The very first sentence of that paper reads, "I propose to consider the question: Can machines think?"

Now, I recommend you read this paper; it's wonderfully written, it's very accessible, and it has lots of really interesting thoughts. But there's one paragraph that I want to highlight specifically, and I'll read that to you now.

So Alan Turing writes, "In the process of trying to imitate an adult human mind, we are bound to think a good deal about the process which has brought it to the state that it is in. We may notice three components: the initial state of the mind, say at birth; the education to which it has been subjected; and other experience not to be described as education to which it has been subjected. Instead of trying to produce a program to simulate the adult mind, why not rather try to produce one which simulates the child's? If this were then subjected to an appropriate course of education, one would obtain the adult brain. Presumably, the child brain is something like a notebook as one buys it from the stationers: rather little mechanism and lots of blank sheets. Mechanism and writing are, from our point of view, almost synonymous. Our hope is that there is so little mechanism in the child brain that something like it can be easily programmed."

So what is Turing talking about here? He's essentially talking about learning. He's essentially conjecturing that trying to write the program which constitutes an adult mind might be quite complicated, which makes sense because we're subjected to a lot of experience throughout our lives.

This means we learn a lot. You can think of these as being rules or pattern matching that we learn how to do, skills that we acquire. Enumerating all of that, describing that all of that clearly enough and cleanly enough that you have something with the same capability as an adult mind, he's conjecturing that that might actually be quite tricky.

Maybe it's easier to actually write a program that can itself learn in the same way, maybe that we do, or maybe in a similar way, or maybe in a slightly different way. But it can learn by interacting with the world, by, in his words, subjecting itself to education, maybe to find similar solutions as the adult mind has. He's conjecturing that maybe this is easier.

Now, this is a really interesting thought, and it's really interesting to think about this a little bit. So maybe this is a good time for you also to pause the video and ponder this a little bit, whether you agree with this conjecture that indeed maybe it might be easier to write a program that can learn than it is to write a program that has the same capabilities as the program that can learn will achieve over time.

So what is artificial intelligence? Well, one way to define it would be that the goal would be to be able to learn to make decisions to achieve goals. This is not the only possible definition of artificial intelligence, and other people have proposed sometimes slightly different versions or vastly different versions. I'm not going to argue that this is the best definition of artificial intelligence; maybe there are different types of artificial intelligence that we could consider.

But this is the one that is central to us, so we're going to basically ask this question: how could we build something that is able to learn to make decisions to achieve goals? That is our central question. Note that learning, decisions, and goals are all very central concepts in this, and we'll get into a little bit more detail about what I mean with all of them.

So this brings us to the question: what is reinforcement learning? This is related to the experience that Alan Turing was also talking about because we know that people and animals learn by interacting with our environment. This differs from certain other types of learning, and that's good to appreciate.

First of all, it's active rather than passive, and we'll get back to that extensively in the next lecture. What this means is that you are subjected to some data or experience, if you will, but the experience is not fully out of your control. The actions that you take might influence the experience that you get.

In addition to that, interactions might be sequential. Future interactions might depend on earlier ones. If you do something, this might change the world in such a way that later other things are possible or impossible. We are also goal-directed; we don't just randomly meander. We do things with a purpose.

This is also at large but also at small scale. I might have a goal to pick up a glass, for instance. That is a small thing, perhaps, but you could think of this as being a directed action where I pick up that glass. Of course, this consists of many small little micro-actions of me sending signals to my muscles to actually execute that.

Also, we can learn without examples of optimal behavior, and this one's interesting. It's good to think about that a little bit and to appreciate what I mean when I say that because obviously, we are subjected to education as engineering courses. So we do get examples of what we want or behavior that other people want us to do, and we try to follow those examples in many cases.

But what I mean here is something a little bit different. I mean that when you do pick up a cup, maybe somebody showed you at some point, "Oh, it's useful to pick up a cup." Or you could think of it that way. Maybe that's not the greatest example of that, but somebody taught you how to write or taught you how to do math.

But nobody actually told you exactly how to steer your muscles in such a way as to move your arm to pick up a pen or to pick up a cup. Things like this. So clearly, we still learn some sort of behavior there. We learn to control our muscles, but not in a way that somebody tells you exactly, "Oh, this is how you should have moved your muscle," and now you just replicate.

So that is what I mean when I say we learn without examples. Nobody gives you exactly the low-level actions that are required to execute that thing that you want to execute. This actually maybe constitutes most of the learning that we do. Most of the learning that we do is actually of that form where maybe we do interpret something that we see in some sense as an example, but maybe typically at a much higher level of abstraction.

In order to actually fill in that example, in order to execute what we want to mimic, this might still require us to learn skills in a much more autonomous way without clear examples. So one way to think about this is that you can think of this as optimizing some reward signal. We want to achieve something, and by achieving it, we feel in some sense satisfaction or happiness, and this is what steers our behavior.

We notice that some things are more pleasing than other things. So this brings us to a very central picture that I'm going to show multiple times during this course, which is the interaction loop. One can perceive this as being basically the setting that we find ourselves in.

This is something to keep in mind: that we are basically considering an agent interacting with an environment. Here, I drew them separately, but you could also think of the agent as basically being inside that environment. There's a huge world out there; the agent lives somewhere in that world.

Now, this could be quite concrete. For instance, the agent could be a robot, and the environment could be the real world. It could also be much more abstract. For instance, the environment could be some abstract game, or it could be a virtual environment; it could be the internet, and the agent could be some program that tries to interact with that environment instead.

So it's quite a flexible framework. We basically say that the agent then executes actions and observes the environment. This is typically drawn in such a way as I did here, where the actions go from the agent into the environment, and the observations go from the environment into the agent.

But of course, you could also think of the observation as being something that the agent pulls in. In fact, the observation typically depends on the agent because the agent will have some sort of sensory motor stream that is defined by its interface. For instance, the agent could have a camera, and that defines which observations it gets.

So the main purpose of this course is then to go basically inside that agent and figure out how we could build learning algorithms that can help that agent learn to interact better. And what does better mean here? Well, the agent is going to try to optimize some reward signal. This is how we're going to specify the goal.

The goal is not to optimize the immediate reward, so we're not just interested in taking an action and then forgetting about everything that might happen after. No, we're actually interested in optimizing the sum of rewards into the future. I'll explain it a little bit more clearly in a moment, but it's good to appreciate that there must be some goal to this, right? If there's no goal specified, then it's unclear what we're actually optimizing, and it's unclear what the agent will actually learn to do.

So we need some way, some mechanism, to specify that goal. In many cases, when people show versions of this interaction loop when talking about reinforcement learning, they put these rewards next to the observation, and that's one useful way to think about this: that you take an action, and then the environment gives you an observation and a reward.

But sometimes it's a bit more natural to think of the reward as being internal to the agent. So you could also think of the reward signal as being some sort of a preference function over these observations or over sequences of observations that the agent receives. The agent just observes the world and feels happier or less happy about what it sees and then tries to optimize its behavior in such a way that it achieves more of these rewards.

So this is why I didn't put the reward in the figure because sometimes it's easier to think of it as just coming from the environment through the external to the agent. Sometimes it's easier to think of it as being, in some sense, part of the agent. But it should still be there, and it should be clearly specified because otherwise, it's unclear what the goal of this whole system would be.

This reward function is quite central, so it's good to stop and think about why this is a good way to specify a goal. This is formulated in this reward hypothesis that we see on the slide, which states that any goal can be formalized as the outcome of maximizing a cumulative reward.

Now, I want to encourage you to think about that and think about it critically and try to see if you can maybe even break it in some sense. So breaking it would mean coming up with a counterexample of a goal that you cannot specify by maximizing the cumulative reward. Feel free to pause the video and think about this for a bit.

I've not been able to come up with examples myself, and maybe this is somewhat even trivially true in some sense because you could think of a reward signal that basically just checks whether you've achieved that goal that we want to specify. Then whenever you've achieved the goal, the reward signal becomes one, and before that, it's zero.

Then optimizing this cumulative reward would clearly correspond to maximizing or achieving that goal. It doesn't mean it's easy to specify that; sometimes it's hard to specify your goal precisely, or sometimes it's hard to specify a reward that is easy to optimize, which is a completely different problem. But that's not under this reward hypothesis; this just states that there must exist a reward.

Indeed, sometimes there are many different ways to specify the same goal. For instance, instead of saying you get a reward of plus one whenever you achieve the goal and zero before that, you could also say, "Let me give you a reward of minus one," in some sense a penalty on every step before you've achieved the goal, and then zero rewards after you've achieved it.

Then you could think of the agent as maximizing this cumulative reward as, in some sense, minimizing these penalties, which would also then maybe lead to the behavior of achieving the goal as quickly as possible because minimizing the number of -1 rewards, the number of steps until you've achieved the goal, will then become relevant.

So we see that a goal could also include not just that it happens but also when it happens if we specify it in this way. So it's quite a flexible framework, and it seems to be a useful one that we can also use to create concrete algorithms that work rather well.

So some examples, some concrete examples of what reinforcement learning problems could then exist. Here's a list including flying a helicopter, managing an investment portfolio, controlling a power station, making a robot walk, or playing video or board games. All of these examples were picked because they have actually been used, and reinforcement has been applied to them successfully.

For instance, we could have a reward function for the helicopter that is related to airtime or inverse distance to some goal. Or to pick, for instance, the video games or board games, you could think of a reward function that just looks at whether you win or not. So think of the game of chess, for instance. You could have a reward function that gives you plus one whenever you win, minus one whenever you lose.

If the goal isn't to learn via interaction, these are all reinforcement learning problems. This is irrespective of which solution you use, and I put that on the slide because sometimes people conflate the current set of algorithms that we have in reinforcement learning to solve these types of problems with the field of reinforcement learning.

But it's good to separate that out and to appreciate that there's a reinforcement learning problem, and then there's a set of current solutions that people have considered to solve these problems. That set of solutions might be under a lot of development; they might change over time. But it's first good to think about and appreciate whether we agree with the goal, with the problem statement.

If we agree with the problem statement, then we can think flexibly about the solutions. We don't have to be dogmatic about that, and we can think about new solutions that achieve the same goal. So it's good to separate that out, and I would argue that if you're doing any of these problems where there is a reward function, errors, or sequential interaction, then you're doing reinforcement learning, whether or not you call your algorithm reinforcement learning algorithms.

In each of these problems that I specified, these reinforcement learning problems, there might actually be two distinct reasons to learn. The first one, maybe obviously, is to find solutions. So going back to the example of the helicopter, for instance, you might want to find a policy of behavior for this helicopter so that it flies to a goal as quickly as possible.

But maybe in order to optimize its cumulative reward, it also sometimes has to do some more complicated things, such as first go somewhere else to refuel because otherwise, it won't even reach the goal. But in the end, you might have some learning process, and you might find a solution.

Two examples here to make that concrete: you could think of a program that plays chess really well; that might be something you desire. Or you might want a manufacturing robot with a specific purpose, and then reinforcement could potentially be used to solve these problems and then to deploy that solution.

Now, a subtly different but importantly different thing that you might want is a system that can adapt online, and the purpose for this would be to deal with unforeseen circumstances. So to take the same two examples and contrast how this is different: in the chess program, for instance, you might not want a chess program that displays maybe the most optimal form of chess that you can find, but instead, you might want to find a program that learns to adapt to you.

Now, why would you do that? Well, for instance, you might want a program that doesn't win too often because then maybe your enjoyment is less. So instead of optimizing the number of times it wins, maybe it actually wants to optimize so that the number of times it wins is maybe like roughly half of the time or something like that.

Or maybe it wants to optimize how often or how long you play it because maybe that's a good proxy for how much you enjoy playing it. Similarly, you can think of a robot that can learn to navigate unknown terrains. Maybe you can pre-train this manufacturing robot from the first example because you have a very good simulator for the setting that it might be in.

But in other cases, maybe you don't have a very good simulator, or maybe you do have good simulators for different types of terrains that the robot might encounter, but you do not know yet exactly what the terrain will look like where it will be deployed. There might be unknown unknowns; there might be things that you haven't foreseen.

In those cases, obviously, it's quite useful if you can continue to adapt, if you can continue to learn. We do that as well; we continue to learn throughout our lifetimes. So that's a different purpose, but fortunately, reinforcement learning can provide algorithms for both those cases.

It's still good to keep in mind that these are actually different goals, and sometimes that becomes important. Note that the second point about adaptive algorithms to be able to adapt online is not just about generalizing. It's not about finding a solution similar to in the first category, but one solution that is very general in some sense.

Now, it's really about unknown unknowns. It's really about what if the environment changes? What if, for instance, you have a robot, and it gets deployed, and at some point, there's wear and tear, and you haven't foreseen this? There was no way to know exactly what would happen, and all of a sudden, the robot has to deal with this somehow.

Then if it can't adapt online, then it's really hard to find a solution that is generic enough, general enough that can deal with that. Indeed, there are other reasons why it might be useful to learn online because it might be easier to have a smaller program that continues to track the world around it than it is to try to find this one humongous solution that can deal with all of the unforeseen circumstances that you could possibly come up with.

So these are really different settings. Okay, so now we finally are ready basically to answer this question: what is reinforcement learning? I'm going to say that basically reinforcement learning is the science and framework of learning to make decisions from interaction.

So reinforcement learning is not a set of algorithms, also not a set of problems. Sometimes in shorthand, we say reinforcement planning when referring to the algorithms, but maybe it's better to say reinforcement learning problems or reinforcement learning algorithms, especially if we want to specify those two different parts of it.

Then reinforcement learning itself could just be the science and the framework around all of that. This has some interesting properties; it requires us to think about time and consequences of actions. This is a little bit different from many other types of learning, from, for instance, other types of machine learning, where oftentimes you are given a dataset, and for instance, you want to find a classifier or something of the form, and then maybe there are no long-term consequences.

You basically just specify that your goal is to minimize the errors that the system makes. Now, in reinforcement learning, we would argue that maybe you want to consider the whole of the system. So maybe you don't just want to consider the classifier, but you also want to consider the consequences of classifying something wrong, and that might be taken into account if you consider the whole framework.

This makes it more challenging, and it also means we have to actively gather experience because these actions will change the data that we see. We might want to predict the future, so not just on one step thing. So unlike a classifier, where you just get an input and you're only interested in the input for that or the output for that specific input, we might actually want to consider future steps further into the future, which is an interesting and tricky subject.

In addition, this is a more typical thing that happens in machine learning: we have to deal with uncertainty somehow. Now, the benefit of this is that there's huge potential scope, but you might have also realized that this is also a very complicated or difficult question in general: how to solve this very generic problem.

But the upside is huge. If we are able to find good generic algorithms that can deal with this very generic setting, then maybe we can apply this to many different problems successfully. Indeed, one way to think about reinforcement learning is that it's a formalization of the AI problem, as I defined it earlier.

So it's good to appreciate the ambition here that reinforcement learning is quite an ambitious endeavor. That doesn't mean that, of course, it sits on an island. In fact, we will see during this course that current-day reinforcement learning is very synergetic with deep learning, which is all about training deep neural networks. Indeed, this seems to be a very suitable component for a full AI problem.

So the reinforcement learning description is just about formalizing the problem. That doesn't mean that we don't need solutions from all sorts of subparts of machinery.

Okay, now I'm going to show you an example. What we see here is an Atari game. This is an old video game from the 1980s called Beam Rider, and the agent that is playing this game has learned to play it by itself. Its observations were the pixels, as you also see them on the screen.

Here's a different Atari game with different pixels, and in each of these cases, the actions that the agents would take are the motor controls, which are basically just the joystick inputs for the Atari games. This means the agent could press up, down, left, right, or diagonally, and it will press a fire button. Then the agent just had to deal with that input-output stream.

So it just gets these observations, these pixels from the screen, and it outputs these joystick controls. We see that they did relatively well learning to play each of these different games, even though they're quite different.

So here's a racing game, Enduro, and it's good to appreciate that the agent is not even told what it's controlling, right? It just gets these pixels. So it's not told, "Oh, there's this thing at the bottom here which is kind of meant to be a racing car, and your goal is to pass these other cars."

Now instead, you just get these pixels, you get your motor controls, and you get a reward signal. Now, in these games, the reward signal was defined as the difference in score on every time step. On a lot of time steps, this difference in score is zero; that's fine. But on other time steps, it will be positive, and the agent tries to maximize the summation of that over time.

So it wants to take actions that will lead it to good rewards later on. Now, the most important thing to take away from this is that we have used a learning system to find these solutions, but we didn't need to know anything about these games ourselves. There was nothing put into the agent in terms of strategy or even in terms of prior knowledge on what you're controlling on the screen.

So the agent, when it started playing Space Invaders, did not know that it was going to control this thing at the bottom which is shooting or that it was controlling one of these boxes in this example. That is the benefit of having a generic learning algorithm. In this case, this algorithm is called DQN, and we'll discuss it later in the course as well.

Okay, so now I'll go back to the slides. Now I've given you a couple of examples; I've shown you these Atari games, and now is a good time to start formalizing things a little bit more completely so that we know a little bit more about what's happening.

In future lectures, of course, we will make this much more clear and rigorous. For now, we're going to give you kind of like a high-level overview of what happens here: what is this reinforcement learning problem, what's inside that agent, and how could this work?

So we're going to go back to this interaction loop, and we're going to introduce a little bit of notation where we basically say that every time step t, we receive some observation O_t and some reward R_t. As I mentioned, the reward could also be thought of as being inside the agent; maybe it's some function of the observations, or you could think of this as coming with the observations from the environment.

Then the agent executes some action. The action can be based on this observation O_t in terms of our sequence of interactions, and then the environment receives that action and emits a new observation. Or we could think of the agent as pulling in a new observation and a next reward.

Note that we increment the time step after taking the action, so we say that the action is emitted at time step t, and then the next observation is received at time step t plus one. That's just convention; this is where we increment the time index.

You can actually extend reinforcement learning to continuous time as well rather than having these discrete time steps, but we won't cover that in this course. The extensions are, in some sense, not too difficult, so it's good to have that in mind, but there are some subtleties that one would have to consider.

So the reward here is a scalar feedback signal; it's just a number. It can be positive; it can be negative. A negative reward you could call a penalty, but we just call that a negative reward just to have this one word that refers to the feedback signal.

Just to recall, I put the reward hypothesis on the slide again, where we state that any goal can be formalized as the outcome of maximizing a cumulative reward. This instantaneous reward indicates how well the agent is doing at that time step t, and this helps define the goal of the agent.

The cumulative reward is the accumulation or the sum of these rewards over time. It's useful to also devote a letter to that, which we'll call G. So roughly speaking, you can think of G as kind of specifying the goal, but we'll use the term return to refer to this.

So the return is just shorthand for the cumulative reward or the sum of rewards into the future. Note that the return is only about the future, right? So this is at some time step t. This is useful to determine which action to take because your actions cannot influence the past; they can only influence the future.

So when we define the return, the return is defined as all of the future rewards summed together, but the past rewards are in the past, and we can't change them anymore. Then we can't maybe always hope to optimize the return itself, so instead, we're going to define the expected return, which we'll call a value.

So the value at time s would simply be the expectation of the return, so that's the sum of the rewards going into the future conditioned on the fact that you're in that state s. I haven't defined what a state is yet, but for simplicity, you could now think of this as just being your observation, but I'll talk more about that in a moment.

So this value does depend on the actions the agent takes, and I will also make that a little bit more clear in the notation later on. So it's good to know that the expectation depends on the dynamics of the world but also the policy that the agent is following.

Then the goal is to maximize the values. We want to pick actions such that this value becomes large. One way to think about that is that rewards and values together define the utility of states and actions.

There's no supervised feedback, so we're not saying this action is correct, that action is wrong. Instead, we're saying this sequence of actions has this value, that sequence of actions has that value, and then maybe pick the one that has the highest value. Conveniently, this is used in many algorithms.

The rewards, sorry, the returns and the values can be defined recursively. So the return at time sub t can be thought of as simply the first reward plus the return from that time step t plus one. Similarly, the value can be defined recursively.

So the value at some time, sorry, the value at some state s is the expected first reward you get after being in that state and then the value of the state you expect to be in after being in that state.

So the goal is maximizing value by taking actions, and actions might have long-term consequences. This is captured in this value function because the value is defined as the expected return, where the return sums the rewards into the future.

One way to think about this is that actual rewards associated with certain actions can be delayed. What I mean with that is you might pick an action that might have consequences later on that are important to keep in mind but that do not show up immediately in the reward that you get immediately after taking that action.

This also means that sometimes it's better to sacrifice immediate reward to gain more long-term reward, and I'll talk more about that in the next lecture. Some examples of this might be one that I mentioned before today: refueling a helicopter might be an important action to take even if it takes you slightly farther away from where you want to go.

So this could be formalized in such a way that the rewards for that are low or even negative for the act of refueling, but the sum of rewards over time might be higher because eventually, you get closer to your goal than if you wouldn't refuel. Or to pick the last example, learning a new skill might be something that is costly and time-consuming at first, might not be hugely enjoyable, but maybe in the long term, it will yield you more benefits.

Therefore, you learn this new skill to maximize your value rather than the instantaneous reward. For instance, maybe that's why you're following this course.

Just in terms of terminology, we call a mapping from states to actions a policy. This is just shorthand, in some sense, for an action selection policy. It's also possible to define values on not just states but on actions, so these are typically denoted with the letter Q for historical reasons.

So we have the letter V to denote the value function of states, and we have the letter Q to denote the value function of states and actions. This is simply defined as the expected return conditioned on being in that state and then taking that action A.

So instead of considering some sort of a policy which immediately could pick a different action in state S, we're saying, "No, no, we're in state S, and we're considering taking this first action A." Now, this total expectation will then, of course, still depend on the future actions that you take, so this still depends on some policy that we have to define for the future actions, but we're just pinning down the first action and conditioning the expectation on that.

We'll talk much more in depth about this in lectures three, four, five, and six. So now we can basically summarize the course concepts before we continue.

We said that the reinforcement learning formalism includes an environment, which basically defines the dynamics of the problem. It includes a reward signal, which specifies the goal, and sometimes this is taken to be part of the environment, but it's good to basically list it separately.

Then it contains an agent. Now, this agent might contain different parts, and most of this course will essentially be about what's in the agent, what should be in the agent, how could we build learning algorithms that work well, and some of the parts are listed here.

So the agent will contain some agent state; this is just the internal state of the agent. It will contain some policy, and it could contain a value function estimate, so a prediction of the value, or a model, which might be a prediction of the dynamics of the world.

I put question marks there because these are, in some sense, more optional than the first two. The agent must have some internal state; this could be a very simplistic state. It could be a null state, or your agency could simply be the immediate observation that you've received right now.

But it could be a more complicated state, and it must have some policy. It must select actions in some way. Again, this policy could be particularly simple; it could be a random policy that just selects actions completely uniformly at random. But there must be some policy.

The value function and the model are more optional in the sense that they're not essential parts, but they are very common parts, and I will discuss them a little bit in the remainder of this lecture.

So now it's time to go into the agent, and we'll start with the agent state. This is one way to depict the internals of the agent. So now we're inside the agent, and in this schematic here on the right-hand side, time increments as we go to the right.

We see inside the agent from the view inside the agent: on every time step, there's an observation that comes in, and then there's some internal state of the agent. From the state of the agent, the agent might make predictions, and it should define some policy somehow, and then the action gets selected by this policy.

I could have basically drawn another arrow going from the policy into the action, which would then go back into the environment, but we're focusing here on that state component. The state here basically refers to everything that the agent takes along with it from one time to the next.

So if there are things that are not taken along, for instance, the policy at the instantaneous policy at the time step might not be taken along, the predictions might not be taken along, or they could be. In that case, they could just be part of the state, but there might be other things in the state as well.

There might be some memory in the state; there might be learned components in the state. Everything that you take along with you from one time to the next we could call the agent state. We can also talk about the environment states, which is the other side of that coin.

In many cases, the environment will have some really complicated internal states. For instance, in the example where the agent is a robot and the environment is the real world, then the state of the environment is basically just the state of all of the physical quantities of the world, all of the atoms, all of the quantum mechanics of the world. That's the environment state.

Of course, in many smaller examples, if it's a virtual environment, it could be much smaller, but it could still be quite complicated. This also means it's usually invisible to the agent. It's very rarely really large, and it's not part of the observation stream per se. Even if it would be visible, it might contain lots of irrelevant information, and it might just be simply too large to process.

But actually, the first one is more interesting; it's usually just invisible to the agent. We can only see a sub-slice of it. We can see a small part of it via our observation stream. An important concept to keep in mind then is that we can also formulate the whole interaction sequence into something that we could call the history of the agent.

This is simply everything that the agent could have observed so far. So that includes the observation from the environment, but also the actions that the agent took and the rewards that it received. So this is really just taking that interface and storing everything that happens on the interface level, and we could call that the history of the agent.

For instance, it could be the full sensory motor stream of the robot. Now we can say that the history is the only thing that can be used to construct the agent state in some sense, apart from whatever prior knowledge you put in all the way at the beginning. But let's just set that aside for a moment.

Everything else must be a function of your history. There's nothing else; essentially, the agent has no additional information apart from its sensory motor stream. So that's what you should be using to construct your agent state.

Then a special case is when the agent can see the full environment state, so that the observation is the full environment state, and this is called full observability. I mentioned before already this is a very special case; this is not the common case at all, but it's a useful one, and sometimes it's used, for instance, in theoretical statements just because it's easier to reason about in some cases.

In that case, the agent state can just be the observation, right? We don't need to worry about this whole interaction stream; we can just observe whatever the environment state is, and then this should be sufficient in order to basically tell where you are. You don't need additional memory; you don't need anything else; you just need the environment state as your state.

Now, in addition to that, there could be the learnable parts of the agent, right? The agent might have some parameters that it's learning, and you could also consider that to be part of the agent state. In this case, I'm actually not considering that to be part of the agent state; that's something that we also have; that's also part of the agent, but let's just set that aside and call that the agent's mind essentially separate from its state in this sense.

So in the fully observable case, you can just look at your observation; you could say, "Oh, that tells me everything I need to know about the environment," so I don't need to log any of the previous interactions.

This leads us to an important concept in reinforcement learning, which is the Markov property. This has been used to formulate essentially the reinforcement problem and also precursors to this. Importantly, a Markov decision process is essentially a very useful mathematical framework that allows us to reason about algorithms that can be used to solve these decision problems.

The Markov property itself states that a process is Markovian, or a state is Markovian for this process, if the probability of a reward and a subsequent state doesn't change if we add more history. That's what the equation on the slide means.

So we can see the probability of a reward and a state; you should interpret this as the probability of those occurring on time step t plus one. We say that the probability of this happening conditioned on state S_t is equal to conditions on the full history up to time t. That means if this is true, that the state contains all the means you need to know, so we don't need to store anything else from the history.

It doesn't mean that the state contains everything; it just means that adding more history doesn't help. For instance, if your observations are particularly uninformative, then adding more uninformative observations might not help, so that might lead to a Markovian state.

But it doesn't mean that you can observe the full environment state. However, if you can observe the full environment states, then you're also Markovian. So once the state is known, the history might be thrown away if you have this Markov property.

Of course, this sounds very useful because the state itself might be a lot smaller than the full history. So as an example, the full agent and environment state is Markov, but it might be really, really large because, as I mentioned, the environment state might be humongous; it might be the real world.

Also, the full history is Markov, which you can kind of clearly read from this equation because if you put H_t on the left-hand side where it says S_t, then obviously this is true. But the problem with that is that that state keeps growing.

So if we want to use the full history as our agent state, then the amount of memory that we're using inside the agent's head keeps growing linearly over time, and sometimes that also becomes too large, or actually oftentimes it also becomes too large.

So typically, the agent state is some compression of the history. Whether it, instead of the Markov property, is actually maybe not even the most important question, but it's an interesting thing to keep in mind.

So note here that we use S_t to denote the agent states, not the environment states, and we'll use that convention basically throughout, where sometimes, as a special case, these will be the same because the environment state might be fully observable. But in general, we will not assume that, and then whenever you say states, this is basically the state on the side of the agent, and that's specified differently.

Now, I said that full observable cases are very rare, so we should talk about the complement of that, which is the partial observable case. In this case, the observations are not assumed to be Markovian, and I'll give you a couple of examples.

So for instance, a robot with a camera which is not told its absolute location would not have Markovian observations because at some point, it might be staring at a wall, and it might not be able to tell where it is. It might not be able to tell what's behind it or behind the wall; it can maybe just see the wall, and then this observation will not be Markovian because the probability of something happening might depend on things that it has seen before but it doesn't see right now.

It may have just turned around, and there might be information about what's behind it which should influence the probability of what happens next, but it can't see this from its observations per se. Similarly, a poker-playing agent only observes public cards and its own cards; it doesn't observe the cards from the other players, but obviously, these are important for its future rewards.

So part of the environment state is then hidden to the agent. So now using the observation S_t would not be Markovian. That doesn't mean it's necessarily a bad idea, but it means it can be a bad idea because you're ignoring some information that might be contained in your past observations.

This is then called a partially observable Markov decision process, or POMDP for short, and it's basically just an extension of the Markov decision processes, which we'll define more rigorously in future lectures. It's good to keep in mind that this is basically the common case.

Note that the environment state itself could still be Markov; it's just that the agent can't see it and therefore can't know it. In addition, we might still be able to construct a Markov agent state. The example I gave in the previous slide is you could always take your full history, and that would be Markovian.

The problem with that is just it's too large, but maybe there are smaller agent states we can construct which still hold enough information to be Markovian. So the agent state is an important concept, and it must depend on this information that you've seen before, right? This must depend on this interaction stream, and the agent actions then depend on the state, and it's some function of history.

So the examples that I gave were like the states could be the observation; it could be your full history. But more generally, you can also write this recursively, where the state at your next time step t plus one is some function of your previous state, the action that you've taken, the reward you've seen, and the observation that you see.

So we're taking one step in this interaction loop, and we're basically saying we're going to update the state to be aware of this new time step. Clearly, if we're concatenating the action, reward, and observation, then S_t plus one could just be your full history if S_t is your full history up to time step t.

So the full history is contained within this formulation. Also, quite clearly, the special case of just looking at the observations contains this formulation, and this is a more flexible way to think about it. U is the state update function.

Now, as I mentioned, it's often useful to consider the agent's state to be much smaller than the environment state. In addition, you also typically want it to be much smaller than the full history. So we want this agent update function to give us some compression of the full history, maybe recursively, and maybe the state actually stays the same size, right?

So S_t could be of a certain size; we see new action, reward, and observation, and we condense all of the information together into something that is the same size as S_t. Here's an example just to make that a little bit more concrete.

Let's consider a maze, and let's say that the full state of the environment in a maze is this layout, and in addition, it's where you are in the maze, and that would define the full environment state. But let's say that the agent can't observe all of that; it can't observe its location in the maze.

Instead, maybe it can only see this little three by three around itself. In this case, the agent would be in the center of this three by three block, and what it can see is exactly the pixels around it, the cells around it. So it can see, for instance, that above it, it's empty; to the left and the right, there's a wall; and below it, it's empty.

So it could walk up; it could walk down. Also, it can look slightly around the corner where it can see that if it goes up and then right, there's also an empty spot. But if it goes up and left, it would bump into a wall, and that's all that it can see.

Now, this observation is not Markovian because if we look at a different location, these observations are actually indistinguishable. So if we would just use the observation in this case, then the agent won't be able to tell where it is.

We can also talk about why that might be problematic. So let's say that the agent starts in the top right corner, and let's say that the goal for the agent is to go to the top left corner. Then if you consider the shortest path in the state that we see, the observation that we see in the top right here, the optimal action would be the step down because that's in the direction of the goal.

Because we have to go via the bottom of this maze in order to reach the top left corner. However, if you then look at the left observation, in that observation, the optimal action would be to go up. But if the agent can't distinguish between these two, if it would be using the observation as its full agent state and its action selection policy must depend on only that observation, then it's unclear what it should be doing.

In the top right, it should be going down; in the left, it should be going up. But there's no single policy, a single function of this observation that will do the right thing in both cases. This is why it can be problematic to not have a Markovian state observation.

So now I actually want you to think about for a second. So feel free to pause the video here and think about how you might be able to construct a Markovian agent state for this specific problem and maybe for any reward sequence. So feel free to pause the video, and then I'll talk about this a little bit more.

So one thing that you may have come up with is, "Well, maybe we can use that thing that you said where you can use the full history." Yes, the full history would be Markovian; it would be rather large. So I think many of you will have kind of discounted that as being not the most pleasant or feasible solution.

So maybe we could do something that's a little bit in that direction but not quite the same. So let's say we consider storing not just the observation that we see right now but also the previous observation. Would that work well? It kind of depends, actually. It depends on the policy and whether the state transitions here in the real world are completely deterministic.

So if you go down, you really go down, or whether there is some noise in there where sometimes when you press down, you actually go up. Because note that if you look at both of these observations that are highlighted right now, if you step down one step, the observation is still the same.

So if you would come from this situation below where we currently are, and you would just concatenate these two observations, that would not be sufficient to be able to tell where you are. So just concatenating two observations is not necessarily Markovian in this environment.

However, it can be sufficient if your policy never does that same action in the left state. Then the ordering of the observations is enough to distinguish the left from the top right. But in general, for any policy, for instance, for a uniformly random policy, just concatenating two observations is not sufficient in order to get a Markovian state in this case.

Okay, so in general, what I'm doing there is basically trying to construct a suitable state representation to deal with the partial observability in the maze. As examples, I mentioned using just the observation might be enough; using the full history might be too large.

But generically, you can think of some update function, and then the question is how do we pick that update function? That's actually what we were doing just now; we were trying to hand-pick a function U that updates the state in such a way to take into account the stream of observations.

The example that I gave where I just concatenate two observations would be where you just keep track of this buffer, and whenever you see a new observation, it basically replaces the oldest observation with a new one, with a newer one, and then adds the newest one on top. So you have like a two-observation buffer in that case.

Excuse me. So this is a generic update. You can do other things there as well, of course, but it's good to note that constructing a full Markovian agent state might not be feasible. Your observation might be really complicated, and it might be really hard to construct a full Markovian agent state.

Instead of trying to always shoot for complete Markovianness, maybe that's not necessary. Maybe it's more important that we allow good policies and good value predictions, and sometimes that's easier. Sometimes going for optimal is really, really hard, but going for very good is substantially easier, and that's something more generally that we'll keep in mind when we want to deal with messy, big, real-world problems where optimality might be out of reach.

Okay, now we're going to continue our journey inside the agent, and we're going to go to the next bits, which are the policy, the value function, and the model, starting with the policy. So we covered the agent state; now we're going into policy and then immediately into the value function and the model.

The policy is simply something that defines the agent's behavior. It's not a very complicated construct; it's a mapping from agent state to actions. For instance, we can write this like this for a deterministic policy. It could be considered simply a function that takes a state as input and outputs an action.

Now, actually, it will be more common and often more useful to think of stochastic policies, where instead, π means the probability of an action given a state. π is just conventional notation for policies; we often use π to denote a policy, and the stochastic policies in some more general case.

So typically, we consider this a probability distribution of actions, and that's basically it in terms of policies. Of course, we're going to say a lot more about how to optimize these policies, how to represent them, how to optimize them, and so on. But in terms of definitions, all that you need to remember is that π denotes the probability of an action given a state.

Then we can move on to value functions and value estimates. What I have here on the slide is a version of the value function as I defined it earlier, and I want to mention a couple of things about this. First of all, it's good to appreciate that this is the definition of the value. Later, we'll talk about how to approximate that; this is just defining it.

I've extended it in two different ways from the previous definition that I had. First, I made it very explicit now that the value function depends on the policy. The way to reason about this is if I have this conditioning on π, it means that I could write this long form to say that every action at subsequent time steps is selected according to this policy π.

So note that we're not conditioning on a sequence of actions; we're conditioning on a function that is allowed to look at the states that we encounter and then pick an action, which is slightly different. The other thing that we've done now on this slide is introduce a discount factor. This is a somewhat orthogonal thing, but I thought I should include it here so that we have the generic form of a value function, which conditions on the policy and includes potentially this discount factor, which is a very common construct in reinforcement learning.

One way to think about that is that the discount factor helps determine the goal in addition to the reward function. For instance, if you consider a reward function to be plus one on every time step, then it could be infinitely large. Alternatively, if you think of a maze where the reward is zero on every time step until you reach the goal, then the value function for a uniformly random policy would be, sorry, if it's zero every time step and one when you reach the goal, then any policy that eventually reaches the goal gets a value of one.

So then we can't distinguish between getting there quickly. So sometimes discount factors are used to define goals in the sense, "Oh, maybe it's better to look at the near-term rewards a little bit more unless it's a long-term reward."

So this allows us to trade off the importance of immediate versus long-term rewards. To look at the extremes, to make it a bit more concrete, you can consider a discount factor of zero. If you plug that into the definition of the value as it's written on the slide, there you see that then the value function just becomes the immediate reward.

All of the other rewards are canceled out because they're multiplied with the zero discount. So that means if your discount factor is small, or in a special case if it's zero, then you only care about the near-term future. If you don't want to optimize your policy, then the policy would also be a myopic policy, a short-sighted policy, which only cares about immediate reward.

Conversely, the other extreme would be when the discount factor is one. This is sometimes called the undiscounted case because then the discounts basically disappear from the value definition. We get the definition that we had before, where all rewards are equally important, not just the first one, but the second one also is equally important, the first one.

That also means that you no longer care in which order you receive these rewards, and sometimes it's useful to have a discount factor that is in between these two extremes in order to define the problem that you actually want to be solving.

Now, as I mentioned, the value depends on the policy, and then ultimately we want to optimize these. So we want to be able to reason about how we can pick different policies, and we can now do that because the value function can be used to evaluate the desirability of states.

Also, we can compare different policies on the same state. We can say one value might have a different, sorry, one policy might have a higher value than a different policy, and then we can maybe talk about the desirability of different policies. Ultimately, we can also then use this to select between actions.

So we could do so. Now, here we've defined the value function as a function of a policy, but then if we have a value function or estimated value function, we can then maybe use that to determine a new policy.

So this will be talked about in a lot more depth in future lectures, but you can think of this as kind of being an incremental learning system where you first estimate the value of a policy, and then you improve your policy by picking better policies according to these values.

That's indeed a relevant algorithm idea that we'll get back to later. As I mentioned before, the value functions and returns have recursive forms. So the return now has its discount factor in the more general case, and the value function is also recursive, where, again, as I mentioned before, the value of a state can be defined as the expected value of the immediate reward plus now the discounted value at the future state for that same policy.

Here, the notation A tilde π just means that A is sampled according to the probability distribution π, and we'll just use that same notation even if the probability distribution is just deterministic for simplicity. This is called a Bellman equation; it was first described by Richard Bellman in the 1950s, and it's useful because you can turn it into algorithms.

These equations are heavily exploited, and a similar equation can be written down for the optimal value, which is really interesting. So note that the equation above is conditioned on some policies, so we have some policy, and we can then determine its value.

It turns out we can also write down an equation for the optimal value that you can have, so there is no higher value that you can get in this setting. This turned out to adhere to this recursion that is written on the slide, where V star, the optimal value of state S, is equal to the maximization over actions of the expected reward plus discounted next value conditioned on that state and action.

Importantly, this does not depend on any policy; it just depends on the state. This recursion is useful; it defines recursively the optimal value because know that V star is on the left-hand side and the right-hand side, but we can use this to construct algorithms that can then learn to approximate V star in the future.

In future lectures, we will heavily exploit these equations, and we'll use them to create concrete algorithms. In particular, of course, we often need to approximate them. So the previous slide just defines the value of a certain policy, and it defines the optimal value. It doesn't tell you how to get them, and in practice, you can't actually get them exactly, and we'll have to approximate them somehow.

We will discuss several algorithms to learn these efficiently, and the goal of this would be that if you have an accurate value function, then we can behave optimally. I mean, if we have a fully accurate value function, because then you can just look at the value function.

We could define a similar equation that we had on the previous slide for state-action values rather than just for state values, and then the optimal policy could just be picking the optimal action according to those values. So if we have a fully accurate value function, we can use that to construct an optimal policy.

This is why these value functions are important, but if we have a suitable approximation, which might not be optimal, we might not be perfect, it might still be possible to behave very well even in interactively large domains. This is kind of the promise for these approximations that we don't need to find the precise optimal value.

In many cases, it might be good enough to get close, and then the resulting policies might also perform very well.

Okay, so the final component inside the agent will be a potential model. This is an optional component, similar to how the value functions are optional, although they are very common. A model here refers to a dynamics model of the environment.

The term is sometimes used more generally for other things as well in artificial intelligence or machine learning, but in reinforcement, we typically, when we say we have a model, we typically mean a model of the world in some sense. So that means the model predicts what the environment will do next.

For instance, we could have a model P, which predicts the next state, where maybe if you give it inputs as inputs a state, an action, and a next state, the output of this thing is an approximation to the actual probability of seeing that next state after observing this previous state and action.

For simplicity, it might be good to keep in mind a specific agent state where, for instance, these agents could be your observation. Then this would be the probability of the next observation given the previous observation and the previous action, and we could try to model that. We could try to approximate this, and then in addition, we could also approximate the reward function, which could be, for instance, conditioned on state and action, where this would just be the expected reward given that you are in that state and taking that action A.

A model doesn't immediately give us a good policy. Like for value functions, we can actually just kind of read off a policy if we have state-action value functions. We can pick actions according to these values. For a model, we don't immediately have that; we would still need to conduct some sort of a planning mechanism.

We'll talk about specific algorithms that can be used in addition to, like, sorry, on top of a model in order to extract a policy. But it's good to keep that in mind in general that the model would still require additional computation in order to extract a good policy.

In addition to the expectation above for instance for the reward, we consider the expected reward; we could also consider a stochastic model or an expectation model for the state. So the state's model here in particular, this would be an example of a distribution model where we try to actually grasp the full distribution of the next state given the current state in action.

You could also instead try to approximate the expected next state, or you could try to find a model that just outputs a plausible next state or maybe randomly gives you one of the states that could happen. These are all choices, design choices, and it's not 100% clear in general yet what the best choices are.

Now I'll go through an example to talk about all of these agent components a little bit. It's just a very simple example; we'll see much more extensive examples in later lectures. In particular, we're going to consider this maze.

So we'll start at the left, and the goal is at the right, and we define a certain reward function which gives you a minus one per time step. That means that the optimal thing to do is to go to the goal as quickly as possible because then you'll have the lowest number of minus ones.

Then the actions will be up, down, left, and right, or north, east, south, and west if you prefer. The agent location is the state. Let's say that this is fully observable, so you can basically just tell where you are. Maybe you could think of this as x, y coordinates, which are easily shown to be Markovian in this setting.

So here's an example which shows a policy, and in fact, it shows the optimal policy. In every state, we see an arrow; this arrow depicts which action to take. So for instance, in the leftmost state, the arrow points right, so we say that in the leftmost state, the policy now will take the action right.

This policy is a deterministic policy that indeed gives us the shortest path to the goal, and it will be an optimal policy. You could also consider a stochastic policy, which might select multiple actions with non-zero probability.

Here is the value of that policy on the previous slide, which happens to also be the optimal value function, which, as you can see, increments every time you step away from the goal. This is because the value function is defined as the expected sum of rewards until the indefinite future, but if the episode ends at the goal, then the rewards stop there.

So if you're one step away from the goal, the value will just be minus one for that optimal policy. If you're two steps away, it will be -2, and so on. This is a model, and specifically, this is an inaccurate model because note that all of a sudden, a part of the maze went missing.

So in this case, the numbers inside the squares are the rewards. So these are models as just, "Oh, we've learned the reward is basically minus one everywhere." Maybe this is very quick and easy to learn, and the dynamics model was learned by simply interacting with the environments.

But it turns out maybe we haven't actually gone to that portion there in the left corner, left bottom corner, and therefore the model is inaccurate and wrong there. If you then would use this model's plan, it would still come up with the optimal solution for the other states that this can see, but it might not have any solutions for the states it hasn't seen.

It's just an example, of course; it's unrealistic to have an accurate value function but an inaccurate model in this way specifically. But it's just an example to say, "Oh yeah, your model doesn't have to be perfect if you learn it; it could be imperfect." The same, of course, holds for the policy and value function; these could also be imperfect.

Okay, now finally, before we reach the end of this lecture, I'm going to talk about some different agent categories. In particular, this is basically a categorization; it's good to have this terminology in mind, which refers to which part of the agent are used or not used.

A value-based agent is a very common version of an agent, and in this agent, we'll learn a value function, but there's not explicitly a policy separately. Instead, the policy is based on the value function. This agent that I showed earlier that was playing Atari games is actually of this form, where this agent learns state-action value functions and then picks the highest-rated action in every state with a high probability.

Conversely, you can think of a policy-based agent, which has an explicit notion of a policy but doesn't have a value function. I haven't yet told you any algorithms how you could learn such a policy if you're not learning values, but we'll actually see an example of that in the next lecture.

Then there's the terminology actor-critic. The term actor-critic refers to an agent which both has an explicit representation of a policy and an explicit representation of a value function. These are called actor-critics because the actor refers to the policy part; there's some part of the agent that acts, and the value function is then typically used to update that policy in some way.

So this is interpreted as a critic that critiques the actions that the policy takes and helps it select better policies over time. Now, all of these agents could be model-free, which means they could have a policy and/or a value function, but they don't have an explicit model of the environment.

So note in particular that a value function can, of course, also be considered some model of some part of the environment; it's a model of the cumulative expected rewards. But we're not calling them a model in reinforcement learning parlance typically.

So instead, if you just have a value function, we tend to call this model-free. I'm saying that not because it's a great definition or a great division between agents, but because it's a very common one. So if you read papers and they say something about model-free reinforcement learning, this is what they mean: there's no explicit dynamics model.

Conversely, a model-based agent could still ultimately, oh sorry, could still optionally have an explicit policy and/or a value function, but it does in any case have a model. Some model-based agents only have a model and then have to plan in order to extract their policy. Other model-based agents have a model, but in addition to that, have an explicit policy and, for instance, use the model to sometimes just incrementally improve the value function or policy.

So now finally, we're going to talk about some subproblems of the RL problem. Prediction is about evaluating the future. For instance, learning a value function, you could call a prediction problem, and this is indeed often the terminology that is used. Typically, when we say prediction, we mean for a given policy.

So you could think about predicting the value of the uniformly random policy, for instance, or of a policy that always goes left or something of the form. Conversely, control is about optimizing the future, finding the best policy.

So it's good to note that this terminology is used quite frequently in papers, so it's good to have that in mind. Often, of course, these are quite related because if we have good predictions, then we can use that to pick new policies. In fact, the definition of the optimal policy π star is the arc max of policies over these value functions.

By definition, the value function defines which policies are the ranking on policies, essentially your preference on policies. That doesn't mean that you need to have these value functions per se in order to learn policies, but it just shows how strongly related the problems of prediction and control are.

In addition, there's an interesting question that I encourage you to ponder a little bit, which is that this is something that Rich Sutton often says: that in one way or the other, prediction is maybe a very good form of knowledge. In particular, if we could predict everything, it's unclear that we need additional types of knowledge.

I want you to ponder that and think about whether you agree with this or not. So if you could predict everything, is there anything else that we need? Feel free to pause the video and think about that for a second.

I'm going to give you one suggestion. So indeed, if you can't predict everything about the world, this gives you a lot of knowledge. It might not immediately tell you how to do things, so maybe it's sometimes useful, similar to these policies and value functions.

Sometimes it can be useful, especially if we're approximating, so we can't predict everything perfectly. It can be useful to separately store predictions and separately store policies, or you could think of these as them being skills in some sense.

But indeed, predictions are a very rich form of knowledge, and many things can be phrased as a predictive problem, even if they're not immediately clearly a predictive problem if you first think about them.

As I've referred to when I was talking about models, there's two different parts to the reinforcement learning problem. One is about learning, and this is the common setting which we assume where the environment is initially unknown, and the agent interacts with the environment.

Someone has to learn, whether it's learning a value function, a policy, or a model. All of that could be put under the header of learning. Then separately, we could talk about planning.

So planning is a common term in artificial intelligence research, and planning is typically about when you have a model. So let's say the model of the environment is just given to you, and then the agent somehow figures out how best to optimize that problem; that would be planning.

So that means you're using some compute to infer from the statement of the problem, from the model that's given, what the best thing to be done is. Now, importantly, the model doesn't have to be given, but it could also be learned.

But then it's good to keep in mind that the model might be slightly inaccurate. So if you plan exhaustively in a learned model, you might find a certain policy, but it's unclear that this policy is actually optimal in the true world because the model might not be completely accurate.

Indeed, the planning might latch on to certain inaccuracies in the model and hence might find solutions that are actually not that suitable for the real world because, for instance, the model might have a hole in the wall somewhere that is not actually there, and then the shortest path might take the agent through that hole, which isn't actually there, and the policy might not be great that you get from there.

But we can think of planning more generally as some sort of an internal computation process. So then learning refers to absorbing new experiences from this interaction loop, and planning is something that sits internally inside the agent's head; it's a purely computational process.

Indeed, I personally like to define planning as any computational process that helps you improve your policies or predictions or other things inside the agent without looking at new experience. Learning is the part that looks at new experience; that takes in your experience and somehow condenses that, and planning is the part that does the additional compute that maybe turns in a model that you've learned into a new policy.

It's important also to know that all of these components that we've talked about so far can be represented as functions. We could have policies that map states to actions or to probabilities over actions, value functions that map states to expected rewards or indeed also to probabilities of these.

We have models that map states to states or state actions to states, and we could have rewards that map states to rewards again or distributions over these. We have a state update function that takes a state and an observation and potentially an action and a reward and maps it to a subsequent state. All of these are functions, and that's important because we have...

Very good tools to learn functions. Specifically, these days, neural networks are very popular and successful. The field of researching how to train neural networks is called deep learning.

Indeed, in reinforcement learning, we can use these deep learning techniques to learn each of these functions, and this has been done with great success. It is good to take a little bit of care when we do so because we do often violate assumptions from, say, supervised learning.

For instance, the data coming at us might be correlated. Think of a robot operating in a room; it might spend some substantial time in that room. If you look at the data coming into the agent, it might be correlated over time. Then, sometime later, it might go somewhere else, and this might be less correlated.

But there might be, in the near term, quite some strong correlations in the data, which are sometimes assumed not to be there when you do supervised learning. In addition, the problem is often assumed to be stationary in supervised learning, in many supervised learning problems—not in all, of course.

But in reinforcement learning, we're often interested in non-stationary things. Think, for instance, of a value function. As I mentioned, the value function is typically conditioned on a policy. But if we're doing control, if we're trying to optimize our policy, the policy keeps on changing.

That means that the relevant value functions may also keep on changing over time because we want to keep track of the value of the current policy. If the policy keeps on changing, that means that the value function also needs to change.

So this is what I mean when I say we often violate assumptions from supervised learning. That's not necessarily a huge problem, but it does mean that whenever we want to use some sort of deep learning technique, sometimes they don't work out of the box.

Deep learning is an important tool for us when we want to apply reinforcement learning to big problems. But deep reinforcement learning, which is basically a research field at the merger of deep learning and reinforcement learning, or how to use deep learning in reinforcement learning, is a very rich and active research field.

You can't just plug in deep learning and then hope that everything will immediately work. That works up to a point, but there are lots of reasons to be done exactly at that intersection of deep learning and deep reinforcement learning. We'll talk much more about that later in this course.

Okay, now that brings us to the final examples. I talked about Atari; let's make it a little bit more specific now. What was happening in the Atari game that I showed you?

You can think of the observations as the pixels, as I mentioned at that time point. The output is the action, which is the joystick controls, and the input is the reward. Here on the slide, it actually shows the score, but the actual reward was the difference in score on every time step.

Note that the rules of the game are unknown, and you learn directly from interactive gameplay. So you pick actions on the joystick, you see pixels and scores, and this is a well-defined reinforcement learning problem. We have algorithms that can learn to deal well with this.

As a different example, here's a schematic example—a little bit more of an illustrative example—and this is easier to reason through. This is why we sometimes use these much smaller examples, and oftentimes the conclusions still transfer.

The entire example is an example of a rich, messy, hard problem in some sense, right? This would be an example of a very small-scale, illustrative problem. We do this because we can often learn something from these smaller problems that we can apply to these much harder-to-understand, difficult big problems.

In this specific example, which is from the Susan Lombardo book, it's basically a grid world without any walls, although there might be walls at the edges essentially, but not any walls inside the 5x5 grid.

There's a reward function defined as -1 when bumping into a wall, zero on most steps, but if you take any action from state A, the state that is labeled with A, you get a plus 10 reward and you transition to A prime.

So even if you press, say, up from state A, you still find yourself in A prime and you get plus 10. Similarly, from state B, you would transition to state B prime and you get plus five.

Now we can ask several different questions about this setting, and there might be reasons why we might be interested in these different questions. A first question could be a prediction question, which is, for instance, what is the value of the uniform random policy that selects all of the actions uniformly at random?

That's depicted here on the right-hand side in figure B. What we see here is that this is quite a complicated construct, right? I wouldn't have been able to tell you just immediately, just by looking at the problem, what the value function is for the optimal—sorry, for the uniformly random policy.

But we can use reinforcement learning algorithms, which we'll talk about in future lectures, to infer this and to figure out what that value is. It turns out, just to look at this a little bit more in detail, that of course the value of state A is quite high because from this state you often get a high reward.

But it's lower than 10 because the rewards after this first reward of 10 are negative. You see that the value of state A prime is actually -1.3. Sorry, I didn't say, but there's a discount factor here as well, 0.9, which means that this is why the value of state A is 8.8 and the value of state A prime is 1.3.

The difference between them is not quite 10, right? From state B, you often get a -1 because you often find yourself bumping into the wall. You don't get a -1, but then you might get a -1 on the next time.

So because you might have walked left to the corner, it's quite a complicated thing because of the discount factor and the dynamics of the world. But we can see that state A is desirable, state B is somewhat desirable, and states in the bottom left are quite undesirable.

But you might actually be more interested in, okay, but what's the optimal thing to be doing? To me, that's not immediately obvious, right? Should you be going to state A and then looping to A prime and get this plus 10 every time? You could, but it takes you a couple of steps in between each two times you do that transition.

You could also go to state B and go to B prime, and then you can get these transitions more often. Now, it turns out we could also figure out what the optimal value function is for this problem and what the optimal policy is.

If you look at the optimal value, they're all positive now because you never have to bump into a wall anymore. The optimal policy doesn't bump into walls, so even the bottom left corner now has positive values.

In fact, the lowest positive values are in the bottom right corner now because from there it takes you a long time to get to the best possible state you can. It turns out the best state you can be in is state A, looping with these plus 10 rewards, is apparently more beneficial than looping with these plus 5 rewards.

Even though the difference in distance on these plus fives is smaller, you can get more plus fives in a row very quickly by going from B to B prime every time. But going from A to A prime is apparently more profitable in the long term.

We can see this in figure C here as well, where the optimal policy is depicted. We see that if you're in almost any state, what you should be doing is moving to state A. This will transition you all the way to the bottom to A prime, and from there you'll just move straight up again to state A and repeat.

Conversely, if you're in state B prime, if you just look at where B prime is in this, you would either go up or left. It doesn't actually matter which one; they're equally good. But if you go up, you would then move left.

So you wouldn't move into state B; instead, you would move left and then move up or left again in order to get to state A. There's only one state that would move into B, which is the top right corner because from the top right, going around state B and then going all the way to A would take so long that it's actually more beneficial to jump into state B, which will transition you to B prime.

Then from there, you'll go to state A and then loop indefinitely. This is quite subtle. I wouldn't have been able to tell you just from looking at the problem that this would be the optimal policy.

But fortunately, we have learning and planning algorithms that can sort that out for us, and they can find this optimal solution without us having to find it. So popping up in this course, we will discuss how to learn by interaction.

We didn't really discuss it in this lecture; in this lecture, we just talked about the concepts and the terminology and things like that. But we haven't really given you algorithms yet. We will do that in the subsequent lectures, and the focus will be on understanding the core principles and learning algorithms.

So it's less about what the current state of the art is. We'll touch upon that a little bit for sure, but it's less about specific algorithms that people happen to use right now and then going all the way to the depth of those.

We will do that for some algorithms, but it's much more important to understand the core principles and learning algorithms because the algorithms that are currently safe will change next year. There will be new algorithms, and if you understand the core principles, then you can understand these new algorithms, and maybe you could even invent your own algorithms.

Topics include exploration in the next lecture and something called bandits, which is basically one-step Markov decision processes. We will talk more about what Markov decision processes actually are, like how they are mathematically defined and what we can say about them.

We will also talk about how to plan in those with dynamic programming. This will be the lectures after the next lecture, and this user will be given by Diana. Then we will use that to go into model-free prediction and control algorithms.

You may have heard of an algorithm called Q-learning, or I mentioned earlier in this lecture an algorithm called DQN. DQN is short for Deep Q Network. Q, as I mentioned, is often used to refer to state-action values.

Q-learning is an algorithm that can learn state-action values, and then the DQN algorithm is an algorithm that uses Q-learning in combination with deep neural networks to learn these entire games. This falls under model-free prediction and control because no explicit model of the environment is learned in that algorithm.

We will also talk about policy gradient methods. We, in fact, already touch upon them in the next lecture, but we'll talk about them more later. These are methods that can be used to learn policies directly without necessarily using a value function.

But we also discuss actor-critic algorithms, in which you have both an explicit policy network or function and an explicit value function. This brings us also to deep reinforcement learning because, as I mentioned, these functions are often represented these days with deep neural networks.

That's not the only choice; they could also be linear or it could be something else. But it's a popular choice for a reason, and it works really well. We'll discuss that at some length later in this course.

We will also talk about how to integrate learning and planning. I talked a little bit about planning being an internal computation process and then learning meaning the process that takes new experience and learns from that.

Of course, we could have both of those happening at the same time in an agent, and then we want them to play nicely together. There will be much more; there will be other topics that we'll touch upon when we go through all of this.

Okay, now finally, I want to show you one final example of a reinforcement learning problem. Again, what we'll see here is a little bit more of a complicated example.

So what we'll see is a system that was learned to control the body. You can see the body already here on the still. I'll press play in a moment, and what will happen is that there's an algorithm that controls the forces of these body parts.

This agent specifically can run right, and it had to learn itself how to move its limbs in such a way as to produce forward motion. The reward was a very simple one: the reward was just go in that one direction, and you'll get plus one, or you get a positive reward basically proportional to how fast you go in that direction.

So it really wants to go really fast in one direction. It was not told how to do that. So at first, when it starts moving, it doesn't know how to control its limbs. It just knows that it perceives the world in some sense by sensors, which I won't go into that much depth; it's not too important here.

But the point is it doesn't know how to move its limbs; it has to figure that out by itself. It just notices that when it moves in certain ways, it gets more reward. In other ways of doing that, you get the following behavior with simplified vision, as it says on the slide, and proprioception, which means it can feel essentially where its own limbs are in some sense.

Then it can traverse through this very complicated domain, and it can learn how to jump over things and how to maybe even climb in some sense just because it wants to go to the right. Not everything is easy, but it does manage to get there.

Now interestingly, by using this setting, by just having a simple reward, you can traverse different types of domains. You can learn to traverse different types of terrains and do this in very non-trivial ways.

It would be very hard to specify a policy by hand that does this. In fact, because we have a learning system, it's not just that we don't have to specify a thing by hand, but we can also apply the exact same learning system to different body types.

This was learned with the exact same system that was used for this other thing, and you can use this in two dimensions or you can use it in three dimensions. In each of these cases, the agent can learn by interaction how to actually scale these obstacles.

The reward is particularly simple; we didn't have to think about how to move the limbs in order to do that. We can just have the learning system come up with that, and that's the important point here. You can apply some more difficult terrains, you can apply this to different body types, and you can get quite non-trivial behavior in doing so.

Okay, so that brings us to the end of this lecture. Thank you for paying attention, and we'll see you in the next lecture, which will be on the topic of exploration.