SESSION 1 | Multi-Agent Reinforcement Learning: Foundations and Modern Approaches | IIIA-CSIC Course

Thank you very much to everyone for coming to this course. It's really exciting for me to be here in Barcelona for the first time. I believe there are a lot of PhD students, and possibly other kinds of researchers here as well. Hands up if you're a PhD student. Almost everyone!

Hands up if you're not a PhD student. Okay, are you master's or undergraduate students or postdocs? What are you? Master’s? Okay, great! You're just interested? Okay, welcome! I think we have people online as well, right? How many people do we have online at the moment? Okay, and they can all hear and see me? It's all good? Alright, great! I just want to say, if you have trouble understanding me, just put your hand up and ask me to repeat. No problem at all! So, my name is Stefano Albrecht. I'm an Associate Professor at the University of Edinburgh in the School of Informatics, and I'm very happy to be here to teach you a little bit about multi-agent reinforcement learning, which is a really hot topic in AI and machine learning and something that we have worked on a lot. I’m first going to spend just a few minutes introducing the course to give you some background information, and then we’ll switch gears and get into the slides for the course.

Okay, let me first introduce my group. We are the Autonomous Agents Research Group in the School of Informatics. Here, you see a subset of the people. We have about 20 members, including postdocs and PhD students.

We are very much hardcore focused on deep reinforcement learning, multi-agent reinforcement learning, and more broadly speaking, machine learning algorithms for autonomous systems control and decision-making. That's what we do, basically. That's our daily business. We are housed in the School of Informatics, and I want to say that the School of Informatics is, by a wide margin, the largest computer science department in the entire country.

It has about 160 full-time professors. It's very large and has a long history, with a lot of research taking place. It is also historically one of the oldest AI institutes in the world. In 1963, there were only three AI labs in the world: at MIT, Stanford, and Edinburgh. A lot of the early work came from Edinburgh.

And it's also ranked by the UK government as the number one computer science department in the UK for research power and impact. So it's a very strong place. If any of you ever visit Edinburgh, it's a beautiful city, so feel free to reach out. We would be happy to show you around, introduce you to some people in my group, and give you a tour of our department. There is a website here that has many resources for PhD students and other researchers. I will say more about that in a moment.

Okay, so broadly speaking, we want to create autonomous agents that can accomplish tasks in complex dynamic environments. I'm showing you a few example applications that we're actively working on. On the left, there's an example of a warehousing application.

I'll show you some videos of this later. In the center, there is an example of self-driving technology. I was involved for a number of years with a company that was building self-driving vehicles, and our company was acquired by Bosch a couple of years ago. Now, we believe that with Bosch, we are Europe's largest Level Four self-driving team. Additionally, there are a few other example applications.

So, in all of these applications, what they have in common is that you have to develop highly sophisticated autonomous systems that can process constant streams of data and make safe and informed decisions. Another common element, which is the focus of what we're doing today, is that there is not just a single actor; there are multiple actors that coexist, and they have to interact in a useful and meaningful way to solve a task. This creates a multi-agent system. I mentioned the website earlier; the website has a lot of useful resources, and I want to take a minute to tell you about that. First, we have a blog, which you can find here.

There are a number of blog posts on the website that summarize all kinds of useful information. Many of these posts are in a summary or tutorial format, which introduce concepts in reinforcement learning within multi-agent systems. For example, in deep reinforcement learning, there are many subtle techniques and implementation tricks that are necessary to make it effective. Unfortunately, these details are often not explained in academic papers, but when you review the code, it's filled with useful insights. We decided to compile all of this information into a blog post. You can also find other blog posts about an online talk series that we organized at the Alan Turing Institute, which covers multi-agent environments. Additionally, we address common mistakes that were made in the early days of multi-agent reinforcement learning that have propagated within the research community. There are many really useful blog posts for you to explore. Another valuable resource I want to share with you is our code repository on GitHub.

We have many actively maintained code repositories with all kinds of algorithm implementations that you can use. However, perhaps the most important one, especially for today, is our Epymar codebase. This is a research prototype codebase for multi-agent reinforcement learning. It has a standardized interface and, I believe, around ten mature implementations of algorithms.

It has all kinds of environments you can plug and play, along with various configuration settings. If you want to quickly dive into multi-agent reinforcement learning and utilize a plug-and-play approach, this is a great starting point for you. We published this at NeurIPS a couple of years ago, and it has been embraced by the community. Many other papers are building on it or developing algorithms based on it.

So it's a good starting point. Perhaps the most important resource I want to share with you is this new book that we just finished writing and published with MIT Press. This is the first and only textbook ever to introduce the field of multi-agent reinforcement learning. It is published by MIT Press and is available on their website for free.

In fact, you can get the book PDF. You can also access all the slides that I will be using this week. Additionally, there is another code base that we released with the book, which is designed to be very easy to use. In contrast to Epyrmil, which I mentioned earlier and is quite sophisticated, this code base is much simpler: small, self-contained, and easy to read. That was the purpose of creating that code base.

So, if you're really new to this type of work, then this might be the best starting point. The book is designed to be self-contained. It has chapters on reinforcement learning, game theory, deep learning, deep single-agent reinforcement learning, and it extensively covers multi-agent reinforcement learning and engineering aspects. You can already pre-order the book at various retailers, like Amazon, and it will be released in print just a few days before Christmas. So, everyone, please go ahead and pre-order the book to support me in living a more luxurious life. Thank you!

Sure, here’s the text with correct capitalization and spelling: "Yeah, by the way, I have a question. We’re really happy with the design for the book cover. Does anyone have an idea what this might mean? This actually has a pretty cool meaning. The spiral you see there—don’t be shy, any hands up if you have any ideas about what that might mean? Yeah, okay, interesting, but no. But it’s an interesting idea, yes. Any other ideas? Anyone online who wants to know? Answer yes? Okay, I’ll tell you. So, this is an abstract graphical depiction of a mathematical process where two agents are repeatedly interacting, and in the process, they are learning to converge to a fixed point, which is in the center. In this case, it would be a national equilibrium. So, imagine the two agents play a game of rock, paper, scissors."

The two dots represent the two agents. The links between the two dots signify one interaction. Actions occur one at a time, and they keep repeating the interaction, spiraling into the center. In the center, there is a fixed point solution, which represents an actual equilibrium. In the context of Rock-Paper-Scissors, this means that everyone plays all actions uniformly at random. I think it's pretty cool; it's a beautifully summarized abstract depiction. Anyway, this is the book, and if you have the time, I recommend that you check out the chapters before the dates this week, so you can have an easier time following the lectures. Alternatively, you can revisit the chapters after the lectures to reinforce your understanding of the course material. Over the next few days, we will mostly be following the chapters in the book, for which you can find the slides on the book website. Some topics we will spend more time on, while others we will cover fairly quickly or skip altogether. This will create a dynamically paced course; sometimes we will linger on certain topics, and at other times, it will be quite fast-paced. However, you can always return to the book chapters and take your time to review them.

There will also be coding exercises. One of my co-authors, specifically for this course, has put together three very small coding exercises that should take no more than one, two, or three hours to complete on your own in the afternoon. The link to these exercises will be released on Slack. I believe everyone here should be on Slack, and there is a channel dedicated to coding exercises. Participation in these exercises is optional.

We're not going to discuss this much. We won't be grading anything, but it comes with files that explain step-by-step how to run some of these algorithms. It shows you how to get results, and you can get started and start experimenting. So it's completely up to you whether you want to do this. All right, just as a warm-up, I want to ask Ron: why do you want to learn about MARL, multi-agent reinforcement learning, and what do you want to do with it?

Hands up. I really would like to know from you why you actually care about this. Don't be shy, right? It's just an interesting way to start a conversation. I think we have a microphone there.

Yes, I am working on football analytics as an application for multiple agents on the soccer field. There are currently some advances using reinforcement learning and imitation learning, but I believe that multi-agent systems are a more applicable scenario in this context. How can we use multi-agent reinforcement learning for football analytics? By simulating the game in general, we can obtain more comprehensive results.

So we don't have a lot of counterfactual information right now from the data we have. Okay, you want to learn policies for your players to see what they would do in certain situations. Interesting.

Anyone else? Why do you care about Marl? What do you want to do? Hands up. Hi, so I'm working on automated negotiation.

And I think it could be one way to train agents to learn how to negotiate with each other. Or, vice versa, I think negotiation could actually help improve existing moral problems or solutions. If the agents can negotiate with each other on how to solve a problem, maybe in that way it could be beneficial. I've recently seen a lot of papers discussing morality in combination with negotiation, but I never knew much about morality.

I had to review those papers, so I realized I need to know more about this topic. Okay. If I could just ask, what university are you from? I'm from here, at this institute.

Okay, and you? Where? Oh, what's it called? Okay, I'm actually from Germany, but I can't tell what you're saying. Okay, okay, all right, who's up next? Who wants to come up here?

I'm a Ph.D. student working on formation control for multi-agent robotic systems. I'm implementing it using consensus-based algorithms, and I thought I would like to explore more reinforcement learning applications, especially for determining where the agents should be in a formation or for general task allocation. I've always been interested in this, so it was a perfect opportunity. Yes, I'm at the University of Manchester in the UK. Oh, okay! I think we're beginning to collaborate with some researchers in Manchester. Yes, exactly!

All right. Maybe one more. Who would like to share why they are interested in multi-agent reinforcement learning? What do you want to do with it? Okay, I'm going to use my volunteering algorithm. Hi! I work in the healthcare industry, and I came across an intriguing paper that discusses a counterfactual strategy for drug discovery. I think it would be interesting to learn more about multi-agent reinforcement learning, especially in relation to treatment strategies and regimen optimization. I just find the topic fascinating.

And which university are you from? I actually did my master's here at UB, but I'm just working now. Okay. Yeah. Nice.

All right. Great. Thank you. Yes, I think we might come back to this on other days as well to cover other people.

All right. Good. I think I'm going to switch to the actual slides for the book now, but before I do that, I just wanted to remind you to check out our research group website, which has a lot of useful resources. I wanted to mention this now rather than at the end to make sure I don't forget. After this, if you want to explore the field even further, there are a few more events coming up that I'm helping to organize.

In the UK, there's the Alan Turing Institute, which is the national AI and data science institute named after Alan Turing. We are organizing the second UK Multi-Agent Systems Symposium, which brings together various labs in the UK and Ireland that conduct multi-agent systems research. You would be welcome to attend if you happen to be in London at that time. There will be no attendance fee, so students are encouraged to come.

And then the second thing is I'm the program chair for a big reinforcement learning conference, which will be held in Dublin next year in June. Lots of prominent names in reinforcement learning, multi-agent reinforcement learning, robotics, and related fields will be there. Additionally, many individuals interested in cognitive science, psychology, and behavioral economics, who also care about reinforcement learning, will attend. This event brings these communities together. You can check out the website at rldm.org for more information.

Good. I think with that, I'm going to switch to the actual book slides. Let's see. Okay, so introduction. As I said, you can get all the slides online from the book website.

In fact, we're going to try to polish them even more. However, you can already access the current versions on the book's website. By the way, if you know any professors who are interested in reinforcement learning and multi-agent reinforcement learning and would like to teach, please inform them about this amazing book and the accompanying slides. They can use both the slides and the book for free in their teaching. We want to spread this resource as much as possible. So, I mentioned the book, which you can find on the website. Now, let's begin with a brief introduction to multi-agent systems: what they are, why we care about them, and what learning in multi-agent systems entails, along with some of the challenges involved. If there are any questions, please feel free to raise your hand, and we'll address your inquiries. Multi-agent reinforcement learning, or MARL, focuses on algorithms that seek to find optimal decision policies for two or more artificial agents that interact and coexist in a shared environment. In other words, the algorithms aim to learn policies for multiple agents that exist together in a common environment.

We use reinforcement learning; it's in the name. We want to interact and learn by observing what happens when we take certain actions, and we aim to improve over time. The goal is to learn these optimal policies. There are many exciting applications for multi-agent reinforcement learning. Here are just a few examples: computer games (which I will show you a video of in just a second), autonomous driving (which I was heavily involved in), robotic factories (we will also show a video of this), and automated trading (for example, on eBay, where you can have automated agents). On travel agency websites, you could have an automated agent that organizes your entire trip. Let me switch slides again because I have a few videos. So, who knows what this is? Can anyone see what kind of game this is? Yes, it's StarCraft II! This is just an example I wanted to show you. I'm going to explain what's happening here. There are two teams; this is a real computer game. StarCraft II is a super popular game with professional leagues where players can earn a living playing it, and it has a huge fan base.

We control the red team, which has a number of different units. There are marines that can shoot, bigger units armed with stronger guns, and flying units that can heal. Then there is the blue team, which we are trying to destroy.

And that is controlled by a built-in AI, basically. It looks like this: we use multi-agent reinforcement learning. The red team has first spread out to increase fire patterns. You can see that the healing unit is focusing on the high-energy assets to keep them alive for as long as possible.

You can see that our units have learned to concentrate fire on the central points and eliminate the high-energy assets of the opponent first. Basically, we learned to completely dominate the opponent very quickly. We did not tell our team anything about teamwork or strategies. We didn't instruct them to spread out, focus on fire patterns, or heal in a particular way. We left it to the algorithm, and the algorithm learned on its own how to develop these sophisticated teamwork strategies. So, it's a really cool thing if you think about it, right? It's this complicated game, and the algorithm figures out an effective way to do teamwork. This serves as a very basic example of a small task in multi-agent reinforcement learning, but you can actually scale this up and accomplish some pretty significant tasks. Now, who knows about AlphaStar? Who has heard about AlphaStar? Hands up. Okay, some people. AlphaStar was one of those big showcase projects from DeepMind, where they essentially played the entire game of StarCraft II—not just an isolated battle scene, but the whole thing from start to finish against professional players. This means you start with building some units, constructing your entire base, collecting resources, building your army, and working under conditions of partial observability when there's fog of war. You cannot see everything; you have to spread out, collect information, harass your opponent, and execute some pretty sophisticated attack maneuvers and strategies.

And basically, here's a video you can find; there are many videos on YouTube where they look at the replay. The moderators analyze what’s happening, and in this case, there’s a guy on YouTube who is explaining everything to you. I'm going to mute him and talk over his voice now. In this case, AlphaStar controls one of the races called Protoss, while the built-in AI controls the Zerg, who are these alien beings. Essentially, you start from zero.

You build your building, collect resources, and you play out this entire game, basically. It's really quite impressive if you see the kinds of maneuvers the Protoss player, the built-in multi-agent reinforcement learning approach, discovers. Basically, the way it's trained is through a league or population-based training method. So, you train a policy using deep learning for your own team.

And then basically, you repeatedly expose your own policy and your own team against a variety of opponents that you collect over time. This is known as population-based training. In that sense, you can grow and become better and better; you can identify weaknesses that you can then exploit, and you also identify your own weaknesses that you need to address. Additionally, you want to remain resilient against previous attacks that you've encountered, which is why you need to keep them in the pool as a type of memory. This allows you to train repeatedly and become really strong. Now, these concepts are applicable to computer games, but what can you do in reality? Here's an example of a warehousing application that we are actively building in my lab in collaboration with a very large warehouse automation company called Dematic. Dematic operates everywhere; they are a gigantic warehousing automation company.

They build these very high-density robot systems for warehousing operations. Basically, we want to use multi-agent reinforcement learning to see if we can optimize the operations of these systems. Here are a few snapshots from a high-fidelity simulator that we developed with our engineers. These represent real warehouses in different places in Europe: a small one, a medium-sized one, a large warehouse, and a disjoint one. The disjoint warehouse includes a cold compartment and a warm compartment, which need to be kept separate due to thermodynamics. In this system, there are several humans, referred to as "pickers" because their task is to pick items from the shelves. Additionally, there are Autonomous Guided Vehicles (AGVs), which are robots that coexist in the warehouse with the humans. The robots' task is to be in the right place at the right time to collect items from the pickers and return them to the packaging station.

We want to use multi-engine reinforcement learning to optimize the system's hackers. We train policies for both the robots and the humans. The policies are displayed to the humans on an iPad. For the robots, the information goes into their systems, allowing them to operate within the warehouse. Here’s an example of a real warehouse in Germany for a car parts manufacturer.

And basically, initially, you see that the agents are swarming out, and then the orders keep coming in—order, order, order. Imagine an Amazon warehouse with numerous requests and orders for different items. The various agents work through the warehouse to process all the different orders that keep coming in. This looks like a beehive to you.

It's like there’s no discernment logic, but he can perform a lot of analysis and understand that they are using some really sophisticated methods to coordinate essentially individual robots surfacing multiple humans at the same time. As a result, we recently opened a real prototype test facility in Germany, in a city called Dortmund, where we are actually building these real systems and transferring the trained policies into the real environment now. Dematic will also commercialize this as a product. Therefore, I think we can say this will be the world's first real industrial-scale application of multi-agent reinforcement learning.

So it's really nice, the result. Okay, this was just to show you a couple of videos for motivation. I'm going to try to go back to the other slide. Okay, back here.

So, just to get you excited about some cool things you can do! All right, what is a multi-agent system? I think we need to discuss this to ensure we're all on the same page. A multi-agent system is primarily defined by two things. First, there's the environment.

The environment is a physical space, such as a warehouse, or a software-defined environment, like eBay or a computer game. Essentially, there is a state that evolves over time, influenced by the actions of the agents that inhabit this environment. This brings us to the second point: the second part of the environment, or the multi-agent system, consists of these agents. The agents are virtual entities, essentially pieces of software, that receive information about the state of the environment. They can observe certain aspects using different modalities and choose specific actions to influence the state of the environment. For example, they can walk around, pick up objects, or shoot in a game like StarCraft. Importantly, these agents are goal-directed.

So they want to maximize what are called their rewards or returns. We'll discuss this throughout the week. Essentially, they're goal-oriented, which means they have defined goals and are choosing actions to achieve those goals. Here is a graphical depiction of multi-agent reinforcement learning. At the bottom, you have your environment, represented by a square.

And then there are these circles. The circles represent the different agents. Each agent is defined by certain actions they can take. They make observations from the environment and essentially take actions within it. Agents may possess different kinds of domain knowledge.

For example, they may have knowledge about the dynamics of the environment and other aspects. And, of course, as I mentioned, they have goals. Agents may also be able to communicate with one another by sending messages or symbols, basically. So, it's sort of a graphical description of a multi-agent system. Of course, you can build this in any way you see fit. I already showed you some applications that you can imagine represented in this manner. Here's a very basic example that you will see a lot in the book.

Basically, it’s a toy environment that you can use for basic training and experimentation. It’s simple enough for you to actually understand what’s going on. We call this a level-based foraging system: a 2D spatial environment, essentially a grid world. In this example, there are three agents, or black robots.

Okay, you see these black robots, which are agents, and they have various skill levels, represented by the numbers you see there. In this case, the skill levels are one, two, and one again. At the same time, there are these items shown as apples, and they also have different skill levels. The agent's goal is to collect these apples as quickly as possible. However, the interesting aspect here is that they may need to collaborate in order to achieve this.

The agents can only pick up an apple if they are all situated around the apple, and the sum of the agents' levels is at least as high as the apple's level. In this example, the agent on the left, who has a level of one, is unable to pick up the apple because their level is not sufficient. This implies that they lack the skill, capability, or capacity. On the other hand, the two agents on the right are collectively skilled enough because their levels add up to three, which matches the level of the apple, allowing them to collect it.

You can see what's happening. Sometimes they can do things on their own, and other times they may have to dynamically bond with one another on the fly in order to pick certain apples. Then they can disband again and continue doing their own thing. There's a very dynamic team formation aspect here as well, and in this case, they have certain actions.

The action space consists of moving up, down, left, or right in an attempt to collect items. There is also the option for no operation, or "no op." I believe there was a hand raised earlier. Yes, I will repeat the question: in this example, are the agents fixed, or can they enter and leave? In this example, and in fact throughout the entire book, we assume that there is a fixed number of agents. It does not change. So in this case, if there are three agents, there are three agents. However, there is a significant amount of research that explores open environments where agents can appear or disappear at any time.

So, my group has conducted a considerable amount of research in this area, which is really interesting. There are, of course, many realistic applications where you have to consider the possibility of agents disappearing. For example, asset loss in defense applications or, in the context of games, the arrival of reinforcements. Earlier, there was also a mention of soccer—football analysis—where players can disappear as well, which could affect teamwork strategies.

So, it's a very important question. However, we will keep things simple here. This is a basic example, and we will be using it a few times in the lecture; you will also see it frequently in the book. In fact, you can use this yourself if you utilize any of the code bases that I showed you earlier, such as Epymile.

You can play around with this. Okay, so we've talked about multi-agent systems. There’s this environment, and there are these agents. They have actions and observations, and so on. But what does it mean to learn in a multi-agent reinforcement learning environment?

And that's basically summarized here in this one slide. Okay, so this is a modification of the basic reinforcement learning loop that you may have seen already if you studied single-agent reinforcement learning with Sutton and Barto. It has just been extended to multiple agents. So, what's going on here? First, we have our environment at the bottom, which is shown as a square.

And then there are these agents: Agent One, Agent Two, and so on, until Agent N. We assume there is a fixed number of agents, denoted as N, so they do not change. Each agent chooses certain actions, and we call this the joint action—referring to all these actions taken together.

They have an effect on the state of the environment, causing changes. In return, the agents receive a new observation about the state of the environment, along with a reward. The observation may be limited to what they can perceive individually; they might not see everything and could only have their own local observation.

Their rewards could be an individual numerical value; it's just a scalar number that serves as a proxy for the goodness of what they've just done. In the simplest case, if they've done something good, they receive a positive reward. If they've done something bad, they receive a negative reward. However, the crucial point is that they don't actually care about just the immediate reward.

In reinforcement learning, it's all about maximizing the sum of your rewards over time. We call this the return. The sum of the rewards over time is the actual thing we are trying to optimize. Sometimes, it may be more important to sacrifice short-term rewards in order to create opportunities for long-term higher returns.

So, it's all about strategic decision-making. In this loop, you can see that it progresses in a circular manner: take action, something changes, new observations, new rewards, take action, and so on. Through this process, you continuously experience the environment over time.

You're collecting data about what’s happening over time. Time in the environment, along with this data and these experiences, will help you learn and improve your policy, allowing you to become better over time. That’s the reinforcement learning training loop, but designed for multiple agents. When there are multiple agents in the environment, I think this should be clear. Is this clear to everyone, or is it not clear to anyone? I believe it should be clear, right? So, it’s pretty straightforward. Okay, so why do we care about multi-agent reinforcement learning (MARL) in the first place? Why don’t we just say, “Okay, there are maybe these three robots, but I’m just going to use a single-agent reinforcement learning algorithm and train a centralized policy that controls everyone at the same time”?

You could do this, but it doesn't actually work in many applications. So, okay, first, let me tell you about this. There are two motivations I want to share with you. One is that it may not be feasible to implement a centralized single-agent approach. For example, if we go back to the level forging scenario that I showed you earlier with the three robots and the apples.

In this case, if there are three robots and they each have six actions, you will see that the joint action space grows exponentially with the number of agents: 6 to the power of 3, which equals 216. This already represents an action space that is quite challenging to handle, even for the strongest state-of-the-art single-agent algorithms. If you add one more agent, resulting in six to the power of four, it becomes completely unfeasible with existing single-agent algorithms. Therefore, we need a method to decompose the complexity of this control problem to make it more tractable. One solution could be to train three independent agents, with each agent responsible for controlling one of the three robots.

So, we have three robots, each represented by an agent. In this case, every agent only has to choose from six actions, rather than 216. Six actions are much more manageable. Now, we have three agents learning concurrently, and the added challenge, of course, is that they have to learn how to coordinate their actions. That's the new aspect that comes into play here.

But in terms of the actual action space, it's much more feasible now, right? It's just much smaller. And that's, in a way, if you think about it, that's an instantiation of this computer science paradigm, which is to divide and conquer. Hands up if you know divide and conquer. I think probably everyone learned about this.

It's the first thing you learn in computer science, right? This is an example of divide and conquer. We control a problem by breaking it into multiple action spaces. However, there are also much harder reasons for why we need multi-agent reinforcement learning. In many applications, there is a hard requirement, which is what I mean by "hard," to have decentralized decision-making. This means we need independent, decoupled policies that can be deployed locally on individual machines. There is no centralized entity able to coordinate them due to physical constraints, distances, or other feasibility aspects.

For example, in self-driving, it would not be practical to have a centralized entity that is relaying real-time actions constantly throughout the entire city. It would simply not be feasible. Hands up here again. Yeah, I think there's a microphone here. So, just to understand, you mentioned that there are all decoupled agents for each of the multi-agents, but the whole goal of multi-agent systems is to also take into account the actions of the other agents. If that is taken into account, won't it become similar to a single agent, like a large space of agents, or no? Because yes, they have to learn in the presence of each other. Some approaches work by ignoring the other agents, while others model the actions of the other agents. That’s basically what he is saying. However, in all of these cases, the fact still remains that when they choose an action, it's only one out of six actions, not one out of 216. This is a significant difference in terms of the branching factor, right?

Basically, it's a multi-agent system. They learn together, observe each other, and interact, but the focus is on reducing their own control spaces. Essentially, the output space is reduced, while the input space considers, of course, the actions of the other agents as well. It depends on the algorithm and how you model the observations of the agents.

But yes, ideally, it should be something like that. Yeah. Okay, moving on, the next thing I want to mention is that we talked about multi-agent systems and multi-agent reinforcement learning, and why we care about this. However, multi-agent reinforcement learning also comes with its own unique challenges. It’s not just straightforward to apply multi-agent reinforcement learning.

It does come with some pretty hard problems that have been around for decades now, and we're still not particularly close to solving some of these challenges. It's very important to be aware of them. The one that is probably mentioned most commonly when we talk about problems with multi-agent reinforcement learning is the idea that the environment becomes non-stationary from the perspective of individual agents. Every agent is learning; they're learning simultaneously, and that means, from the perspective of individual agents, things in the environment change because the policies of the other agents are part of the environment.

What they do affects the state of the environment, which in turn affects my rewards and my actions. However, if they keep changing, it means that the environment also keeps changing. These changes ensure that I converge neatly to a fixed point while the others are learning. Additionally, the others must also adapt to these fluctuations because I keep changing, and they have to track me as well.

Non-stationarity is a significant challenge, and extensive research has been devoted to addressing it. Additionally, there is an emerging set of questions regarding what it means to be optimal in a multi-agent system. In a single-agent reinforcement learning (RL) environment, we have a clear understanding of this: our goal is to learn a policy that maximizes the expected return across all states.

It's very straightforward. However, in multi-agent reinforcement learning, it is no longer clearly defined because my returns now depend on what the other agents are doing. We may have differences in terms of preferences, our individual reward functions, and desirable objectives. Consequently, there is a broad range of concepts known as solution concepts that define various types of solutions for a multi-agent system. Some of these concepts focus on fairness, others on welfare, while some address other aspects; there are quite a few different concepts to consider.

And there's not one right solution concept; it depends on your application. You have to choose a solution concept, and it can become really complicated to learn these things. Another challenge is what's called the multi-agent credit assignment problem. I'll show you this in a second.

But basically, the idea now is that the agents, when they observe what's going on in the environment, must also disentangle everyone's contribution to the rewards they have just received. So, was it my action that resulted in this reward, or was it this other person's action that caused it? I need to analyze these factors and make attributions as I learn.

It turns out that this is a really difficult problem. Scaling the number of agents is very important as well. We want to be able to realize applications where there are not just two or three agents, but perhaps tens or hundreds of agents. So, scaling is crucial. These topics are explored in the book.

And we will also explore them further in the upcoming lectures. I want to focus on two of them in a little more detail. The first one is the non-stationarity problem that I mentioned earlier. The idea is that multiple agents are learning, and the environment becomes non-stationary from the perspective of individual agents.

And that means we have this moving target problem. Every agent is optimizing against the changing policies of the other agents. So, let's look at this image that I'm showing you here. This is a depiction of an actual learning process in the rock-paper-scissors game that I showed you earlier. Does anyone not know what rock-paper-scissors is?

I think everyone knows what this is, so I’m going to assume everyone knows what rock-paper-scissors is. So, what does this show here? Here are two probability simplices. Each point in a simplex represents a fully specified probability distribution over three outcomes; in this case, the rock, paper, and scissors actions. If I start in the middle here, where, let’s say, if I start here, then that gives a probability of 0.5 to the paper action and 0.3 to the rock action. Sorry, I think maybe this should be 0.3 here; I need to revisit this. But basically, there’s an initial probability distribution, and what this line here shows is how these probabilities are evolving over time for the blue player and for the green player. You can see the probabilities keep changing. Okay, so there’s training time.

They train more and more. The same goes for the yellow guy up here. They are also training. They are playing this game repeatedly with one another.

In this particular algorithm we used, the participants converge very smoothly to the center point. This center point is actually the unique Nash equilibrium solution of the game, which occurs when everyone plays all three actions uniformly at random. That is the only unique Nash equilibrium that exists in this game. This serves as a concrete example of the book cover image I explained earlier, where there is a learning process and the participants beautifully converge to a center point that represents an actual solution. In this case, they have successfully managed the non-stationarity by adapting to one another. However, in many applications, if the algorithms are not well designed or if the problem is particularly difficult to learn, the outcome can be very chaotic. The participants may end up going in all kinds of directions and will never converge to anything, as they keep chasing each other and struggle to understand what is happening in the environment. Nonetheless, this example illustrates how they have effectively managed the non-stationarity.

But it could well be the case that it's just chaotic and they don't do this at all. Here's one slide description of the multi-agent credit assignment problem that I explained earlier. Let's go back to the level-based foraging example that I showed you earlier. This is the exact same scenario. Now, let's say there's a time step \( t \). All the agents perform their collect agent action—the same action—at the same time.

And then they all receive a shared reward, which is plus one. Okay, so basically, someone was able to collect an apple. In this case, these individuals were able to successfully collect an apple. As a result, let's say that everyone gets a plus one reward because they are a team.

They're working as a team, so now they each have to make individual decisions. They noticed that everyone took the collective action. They observed the state before and what it is now, and they realized that they received a plus one reward.

How do these different agents understand that the action of the guy on the left did not actually matter for the reward? It didn't achieve anything because the apple was too difficult to obtain. It was the two guys who performed the collecting action simultaneously who were able to receive the positive reward. Only by doing this action in this state, at this time, and at the same time were they able to achieve it.

It's difficult for an agent to disentangle these attributions if that's all they get to see, and they have to do this repeatedly over time. This is an example of a multi-edged career assignment problem. Now, let's move on to part one, which is a quick introduction to multi-agent systems and multi-agent reinforcement learning: why we care and what some of the challenges are.

In the next part, we will discuss some basics of reinforcement learning. This segment will be a bit more fast-paced. I will be skipping over certain topics, but I will ensure we cover some essential vocabulary.

But I want to ask, who has some basic background in single-agent tabular reinforcement learning? For example, if you've done a course at university or implemented your own projects, please raise your hand if you have a little bit of experience with reinforcement learning. Okay, uh, less than half. So I think we probably need to cover this. Some of you may recognize a lot of this material already, while others may find it new and perhaps a little fast-paced. However, do go back to the lecture and the course slides, as well as the book, and you can read this at your own pace as well. So, let's jump into the basics of reinforcement learning. Okay, this is how we like to describe it: Reinforcement learning, essentially, involves algorithms that learn solutions for sequential decision-making problems through repeated interactions with an environment.

Okay, so there are a few things that need to be defined in this description. First of all, there is the term "sequential decision problem." It refers to a process where we repeatedly take actions and then observe outcomes as part of a decision-making process. There are a number of different models you can use, but the most commonly used one is the MDP, or Markov Decision Process.

The decision process is essential, but there are many more complicated ones that you can use as well. In a reinforcement learning problem, the first thing you need to define is your decision process—your model of the world, essentially. How does the world work? Next, you need to define what it means to learn a solution.

What is a solution? The learning objective is pretty straightforward in single-agent reinforcement learning. In this scenario, there is only one agent; there are no multiple agents.

We're typically called to maximize the return or the discounted return with a specific discount factor in each state. And that's basically all there is to it. We want to learn a policy that can make choices so that over the longer term, we maximize the sum of the rewards. Essentially, that's the goal. We're learning a policy for a particular decision process to maximize this objective, which is to maximize the expected discounted returns.

Here's a graph description of the MDP model that I mentioned earlier, the Markov Decision Process. I'll tell you more about this in more detail in just a second, but let's focus on this graph for now. There are a few different elements here. First, there are the purple circles—or blue, whichever you prefer. These represent the states at different points in time.

Okay, state at time \( t-1 \), state at time \( t \), state at time \( t+1 \). This is the process that evolves over time. The state of the world changes over time. Then we have our actions, which are the red circles here. At each time step, in each particular state that we are in, we get to choose an action.

In this state, t-1, we get to choose an action, a t-1, which depends on that state. Then, basically, depending on what state we were in and what action we've taken, we receive a reward, which is indicated by this green circle here. This reward occurs at that particular time step. You can see how the arrows mark the dependencies: the action depends on the state, and the reward depends on both the action and the state.

And then the next state in return depends on the previous state and the action that we've taken. Essentially, you go through this process repeatedly over time. Then, based on the next state, we get to choose an action again, which provides us with a reward, leading to the next state, and so on. That's basically how we navigate through this process. Primarily, it looks like this.

There are a number of components defined here. We have our state space \( S \), which is used to identify a number of states. There's also a set of terminal states that defines what it means to complete this task. For example, in level-based foraging, when all the apples have been collected, the task is finished. Then, there's a finite number of actions.

In the level-based foraging example, the actions are simply to walk up, down, left, or right, or to collect. Then there’s the reward function. In this case, there is only one agent, so there is only one reward function, which essentially maps the state-action pair and the next state to a reward. Most of the time, this is just a mapping from the current state and action to the reward.

And then there's a state transition function, which defines the probabilities with which we move from one state to another state given a particular action. Lastly, there's an initial state distribution, which defines what the first state is. You can simply say that there is always one particular state that we start in. That's a Markov Decision Process.

There are a few different assumptions you need to be aware of here, and it gets a little bit more technical. Again, you can go back to the book if you want to absorb this at your own pace. The first one is called the Markov property. That's where this term comes from: Markov Decision Process. The Markov property defines a type of stationarity, which means that the future states are independent of the past states and actions, given only the current state and the action that we are selecting.

So, if you know the current state and the current action, then the past doesn't matter anymore for the future. Basically, we can pick. If you know the current state and the current action, the past can be ignored.

That's what the Markov property means. Probabilistically, it looks like this: the probability of a particular successor state and a reward is independent of the entire past sequence, given only the current state and the current action. Another assumption in Markov Decision Processes is that we have full observability, which means that the agent can see everything. The agent gets to see the entire state of the MDP. In many practical applications, though, you would only see a little bit, right?

You only have your own perspective that you get to see. There may be many things that you do not get to see. However, in Markov decision processes, to keep it simple, we assume that we can observe the entire system. Additionally, we consider the environment to be stationary. This means that the dynamics of the environment—specifically, the transition probabilities and the reward function—will never change over time.

They will always be like they were from the start. Lastly, in reinforcement learning in particular, we assume that we do not know the whole Markov Decision Process (MDP). There will be many things in the MDP that we don't know, such as the action space, the transition function, the transition probabilities, or the reward function. By the way, you don't have to take photos; all the slides are available on the book's website, and you can access everything there. Okay, good. So, these are some basic assumptions. There are probably more that are worth mentioning, but I would say these four assumptions are the most important ones to be aware of. Here's an example of an MDP that we included in the book.

It's actually based on the reinforcement learning course I teach at the University of Edinburgh, and it's kind of neat, so we use it in the book as well. Let's say there's an MDP that is completely specified as a graph, similar to the nodes mentioned earlier, but this is a fully specified MDP. There is a start node, and we always begin in this start node.

Okay, in every node, there are different kinds of nodes, and we get to choose certain actions. For example, in the start node, we can go left or right. If we go left, there is a certain probability that we will arrive at this node, which is Site A, or there is a certain probability, \( p \), that we will arrive at a different node, which indicates that we have immobilized the robot. Essentially, you can imagine this as an example where you control a Mars rover; it has to navigate on Mars, and its goal is to reach the base node, the base station, essentially. It's very simple.

You could also just take your right action; there's a probability of 0.5 that you reach the base node, but there’s also the possibility of being destroyed, like falling down a cliff or something, right? Similarly, if you go left, there's a probability of 0.9 that you reach Side A, or a probability of 0.1 that you become immobile due to some kind of damage. Essentially, the idea is that you learn an optimal policy that determines, on average, the ideal sequence of actions to maximize the probability of reaching the base. In fact, it’s not actually about maximizing the probability of reaching the base.

In fact, it's not actually about maximizing the probability of getting there; it's about maximizing the returns, which is the sum of the rewards that we collect over time. Okay, this was just a basic MDP example for a toy problem: the Mars Rover. Right, so now we're getting into reinforcement learning. In an MDP like this, we have the MDP specified, which represents our world. This is, for example, a Mars Rover.

And now we want to learn in this environment. So we get to see this reinforcement learning loop that I showed you earlier, but just for a single agent. There's our environment, which is the Markov Decision Process (MDP). And there's an agent that exists in the environment, takes actions, changes the state of the environment, and then observes something new and receives a reward. You learn in this loop by collecting data over time, and you become better if you know how to learn.

There are two main categories of reinforcement learning algorithms that you learn about. One is value-based reinforcement learning. This is when you actually learn value functions that assign estimates of discounted expected returns to the individual actions you can take. Then, you derive a policy that uses that to choose optimal actions. In contrast, there is also policy-based reinforcement learning; these types of algorithms learn to optimize policy functions directly.

So, if you have a function for your policy, there will be certain parameters. For example, in deep learning, you have a deep network, and these are the parameters. You directly learn to modify the parameters rather than indirectly learning to estimate the values here. These are the two main categories that you will also still see in multi-agent reinforcement learning. Over the next few slides, I am going to explain a bit more technically what these returns are.

I'll provide you with some examples of these two classes of learning algorithms: value-based and policy-based. We'll keep it simple and skip over some details, ensuring you're familiar with these basic concepts before moving on to the next part. First, let's discuss discounted returns or expected discounted returns in reinforcement learning. Our goal is to learn a policy that maximizes the expected return. In this case, we use the lowercase "u" to denote a return. The return, as mentioned earlier, is simply the sum of rewards over time. It's important to keep in mind that if the Markov Decision Process (MDP) is non-terminating, meaning it continues indefinitely, there is a problem: the return may become infinite. This renders the problem undefined, making it unsolvable.

So, what we then do is add a discount factor, which is gamma here. Gamma essentially discounts the reward at each time point. By doing this, we create a geometric series that has a fixed point, and as a result, your return becomes defined. It is a finite number, guaranteed to be finite, even if the Markov Decision Process (MDP) goes on indefinitely. This is a useful technique we employ in reinforcement learning to ensure that the returns are finite.

There's also other motivation, which we described in the book. It's not just about the fact that Markov Decision Processes (MDPs) could be infinite; it's also about modeling termination probabilities. However, I'm just going to leave it at that for simplicity. Okay, so that's a discounted return, and basically we care about the expected discounted return. That's why there's an expectation here: because the environment is stochastic, the effects of our actions could also be stochastic. This means that sometimes they work, and sometimes they don't. In the Mars rover example that I showed you, there are probabilities that we go left or right, depending on the different actions. So, that's why we maximize the expected value of our return, because we cannot fully control the environment; there will always be these random effects. Now we get closer to the value-based approaches, where we can learn something called a state value function, denoted as \( V^\pi(s) \). This is the value \( V \) assigned to a particular state \( s \) under our current policy \( \pi \). Our policy \( \pi \) is what dictates the actions taken in different states, and it is defined as follows: The value \( V \) for a particular state \( s \) under a policy \( \pi \) reflects the expected return starting from state \( s \) and following policy \( \pi \) thereafter.

And it's defined like this: the value \( v \) for a particular state \( s \) under a policy \( \pi \) is simply the expected discounted return in that state, followed by moving forward from that point onward. By following that policy from that point onward in that state, you sum up those rewards; that gives you your return. The expectation of that is the value. It's as simple as that. Value is just the expected return.

You can actually define this recursively. If you write this out, you will see that the sum essentially involves the reward at time t, which is then discounted for the subsequent reward at time t plus 1, and so on. You can express this as a recursion where the return is defined as the immediate reward plus the discounted return for the next state. This is significant because many value-based approximations are, in fact, recursive. We'll explore this shortly. Essentially, the value at a particular state s is simply the expectation of this recursive definition—comprising the reward in the next time step plus the discounted return from the successor state.

Everything is clear so far, right? I think it's pretty straightforward. Okay, so now we get into one of the most important and central ideas in the entire world of reinforcement learning: the Bellman Optimality Equations. These are named after Richard Bellman, who was one of the first people to rigorously develop these concepts. He published a book in the 1950s, titled "Dynamic Programming," which is widely cited and very technical. In this book, he explains these ideas and even discusses games, which was far ahead of his time compared to many others. So basically, the Bellman Equation looks like this: If we start at the top here, this is just a copy and paste from the last slide, where we have the expected return defined as this recursion.

We can actually spell this out. First, let's break down the expectation here. We start in a particular state, where we have the option to choose from a set number of actions—let’s say six actions, similar to rock-paper-scissors or level-based forging. We will sum over the different possible actions we can take. Each action has a certain probability assigned to it based on our current policy, denoted as π. This probability reflects the likelihood of choosing that action given the particular state, s, that we are in. Next, we delve deeper into the sample by summing over the possible successor states, s'.

What are the possible successor states that could arise after that? We need to sum over those. We assign probabilities to the different successor states using the state transition probability function that we defined. Then, we multiply this by the immediate reward we receive from making the transition from state \( s \) to state \( s' \) given a particular action. We add to that the discounted expected return of the reward in the successor state.

Keep going forward with this clicker; sorry about that. Essentially, the last step at the end here, this expectation, if you look closely, is just another application of our value function and the successor state. Now we have a closed-form recursive definition of this entire expected return, right? This function that we care about can be expressed using sums analytically, exactly as shown here. In fact, this defines a linear equation system that you can solve with Gaussian elimination and other classical approaches you learned about in your first year of university or something similar.

So, it's beautiful, right? If you think about it, this is a nice analytical closed-form solution that you can solve exactly to a fixed point with existing approaches like Gaussian elimination. But, of course, here we don't want to use Gaussian elimination; we want to use reinforcement learning. So, it's a different way to solve this. Another idea is that, rather than attributing values to states, you can also attribute values to combinations of states and actions.

That's the other concept that you often see: Q. In fact, probably the most famous reinforcement learning algorithm is called Q-learning. Everyone knows what Q-learning is; it's the first thing you learn. It is named Q-learning because it learns this Q function. It learns to assign values to states and actions. You'll see Q-learning in just a second, but basically, it's very similarly defined.

Rather than just having a function \( v \) for states, we now have a function \( q \) for combinations of states and actions. This function represents the expected return given the current state and the execution of a particular action in that state, followed by adhering to our policy \( \pi \) in subsequent states. The definition is almost the same, except that we add the component for the specific action we intend to execute. As before, we can express this as a Bellman equation. We outline this by calculating the sums of the rewards and the transitions of our successor states. In the end, we rewrite it in closed form, but I just realized that there is an error in the slides. It should be \( v \) instead of \( q \). I need to note this down to ensure I remember to fix it.

Slide 22: Okay, yes. Sorry about that. I'll fix it first thing later. Yes?

Oh, you're right. Go back to this. Yeah, this is actually a copy and paste issue; that's why it's incorrect. It's copied from the function definition. Thanks for letting me know. I need to address this copy and paste mistake. But I think you can kind of close the loop there mentally yourself.

I'll fix this later when I get home. By the way, if you all happen to look at the slides and find anything else that doesn’t make sense or any typos, please let me know because we’re still polishing the slides. We want to make them as good as possible. Alright, so we have the value function, which assigns a value to a particular state and action; this is the Q-function. Now we can have a policy that acts greedily with respect to the value function, and that’s essentially what we’re trying to learn. We want to learn an optimal value function that assigns the optimal expected returns to different states. Then we just want a policy that is greedy with respect to a particular value function, which means that in any given state, we choose the action that maximizes the expected return based on our value assignments. So, looking at the bottom here, if we have the Q-function in a particular state S, our function π assigns maximum probability to the action that has the highest Q-value in that specific state.

And if it involves more than one action, which could be the case, then you can have arbitrary probability assignments, or you can simply select one of those and assign all probability to that. However, the values for the optimal Q-function will always be unique, and we'll see this shortly. Now, regarding the greedy policy with respect to a Q-function: we say that a greedy policy with respect to your value function is optimal only when using the optimal value function. The interesting aspect of Markov Decision Processes (MDPs) is that there is always a unique, singular optimal state or Q-value function. However, there may be multiple optimal policies. For example, if you have a state where multiple actions have the maximum Q-value, you can choose any of those actions. This possibility creates an infinite variety of policies. Nevertheless, every MDP is always uniquely solved with one optimal Q-function, which makes them particularly interesting as a mathematical object that we can actually solve. Thus, we arrive at the optimal value function.

And that makes them really interesting in terms of a mathematical object that we can actually solve. The optimal value function for a Markov Decision Process (MDP) is defined like this: we use an asterisk (*) to denote optimality. Thus, we replace the policy (π) here with an asterisk, which indicates that under an optimal policy, the value of that particular state is the same as the maximum value that can be achieved in that state. That is what the maximizer encompasses.

Any policy that maximizes the value in that particular state is important. Remember, the value is the expected discounted return. Similarly, for the Q function, Q* is the optimal Q function, which is also unique. In this case, it is a policy that maximizes the Q function after taking action A in that state. Therefore, the optimal policy, denoted as π*, always chooses the action that yields the maximum value in that particular state, based on the unique optimal Q function Q*. That's basically it.

That's the object mathematically defined that we're trying to learn in a given Markov Decision Process (MDP). This π* (pi star) is what we're trying to learn. Reinforcement learning is essentially a way to learn this π* over time by repeatedly interacting with the environment. All right, so now we've looked at value functions, V values, and Q values. V values assign values to states.

V values assign values to states, while Q values assign values to actions and states. Now, we are going to look at some algorithms that try to learn these value functions, whether it's Q or V. The first thing you typically learn when you get into reinforcement learning is what is called dynamic programming. Dynamic programming is a concept that Richard Bellman developed before reinforcement learning emerged.

But reinforcement learning relies heavily on the ideas that were developed in dynamic programming. Okay, so what is dynamic programming? Dynamic programming, or DP, is a family of algorithms used to compute optimal value functions and optimal policies in Markov Decision Processes (MDPs). The key points I want to emphasize here are V* and Q*. These are the values we are trying to learn through dynamic programming. Once we have V* or Q*, we can derive optimal policies from those optimal value functions by greedily selecting actions based on V or Q. In dynamic programming, we assume that we have complete knowledge of the MDP. If you remember how an MDP is defined, we have the state space, the action space, the state transition probabilities, the reward function, and so on.

Everything there is to know, we know about the MDP. That's the assumption in dynamic programming. Essentially, the way it works is that, given this complete knowledge, we use concepts like the Bellman equation in an operational way to find these optimal value functions, essentially by iterating and repeatedly applying these Bellman equations. So here's the starting point: this is probably the most well-known type of dynamic programming algorithm that you will learn about.

It is called Policy Iteration. Policy Iteration is a dynamic programming algorithm that alternates between two steps. The first step is Policy Evaluation. This is when we compute a value function for a particular current policy, π. So, we have a current function π that assigns probabilities to actions and states.

Anything that you give to me. We want to approximate this associated value function for that particular policy function, π. In the policy evaluation step, we say "evaluate" because the value is the thing that we want to learn from a particular policy. Once we have completed the policy evaluation, the next step is policy improvement. This is when we use our estimate of the value function to make certain improvements to the current policy we have. Typically, this means that we modify the policy with respect to the value function we just computed. Sequentially, it looks like this.

If it's a well-defined algorithm, which these algorithms are, then in the process, we start with an initial policy, π₀. Then we learn the associated value function for that particular policy, π₀. We make an update to the policy. It's now π₁.

We learn the value function for that particular policy, π₁. Then, we make an update based on that, and we continue this process. We repeatedly apply these updates until we eventually converge to the optimal unique value function, V*. From that, we can derive the optimal policy, π*. This is essentially how we can envision the process working over time.

In practice, we would typically terminate this learning ahead of time. For example, if there’s a threshold for changes that have occurred, and only very minor changes are detected in one iteration, then we can go ahead and terminate the process. That’s typically how it’s done in practice. Now, let’s look at some pseudocode. This is a complete pseudocode for a policy iteration algorithm.

And I'm going to walk you through this step by step. Okay, so first we initialize the policy randomly. Let's say that initially, the policy gives a uniform probability to all the actions that we have. Okay? Then, we also initialize the value arbitrarily.

For example, that could just be 0 initially. The whole value function could be 0, and the policy could initially just be random. Okay, that's just how we start. Then, we repeat our learning. First, we perform policy evaluation as the first step.

Here, we achieve this by repeatedly applying the function we discussed earlier, which is the Bellman equation for the value function. It turns out that we can apply this process repeatedly to successively learn the value function \( V^* \). We continue this until we converge for all the states we are in. Convergence could mean that there are no changes in the estimates or just a small delta. After that, we move into the policy improvement step. We have just estimated a specific value function \( V \), and we use that to enhance our policy. Now, how does this work in the pseudocode? First, we define a boolean variable here, which is set to true.

Is the policy stable? Yes or no. Let's say yes initially. Then we iterate over all the possible states that we're in. We choose an action from the current policy and then we observe what the policy would do greedily with respect to the value function that we've just computed.

And if those things differ, then we need to change the policies, which are not stable. We need to adjust them to address the new greedy actions. So, the policies are no longer stable; things have changed. Hold on a second. Is there a typo here? Ah, no, it makes sense.

Check it out. So that's basically, in a nutshell, the policy iteration algorithm, where we have these two steps: policy evaluation and policy improvement. Over time, as we repeat those steps, we converge to the unique optimal value function. From that, you can extract your policy. Okay, there's one more algorithm in dynamic programming that I'm going to show you, and then I'll leave it at that.

That's as much as I'm going to tell you. This is value iteration, which is an even simpler algorithm. Value iteration just uses one particular equation. So rather than going through the whole steps that you just saw with policy evaluation and policy iteration, we're going to use this one equation. This is essentially an application of the Bellman optimality equation, where we successfully learn a value function from case k to k plus one and k plus two, and so on, by choosing the maximizing action over the current expected return equation that you saw earlier.

So we've repeatedly applied this function over the entire state space, which is already defined and provides, in the limits, the unique key values. State values are a result of this process, making it a very simple dynamic programming algorithm. It only requires three or four lines of code to implement, as shown in this pseudo code. However, I'm going to skip over that, as you have already seen the other pseudo code. Now, that's dynamic programming, but no one uses it in real applications, right? It doesn't scale. We cannot iterate over the entire state space; it's impossible. We have environments with billions of states.

And also, it's not practical. We cannot assume that we have all this knowledge. In practice, we don't know the transition function or all the state spaces. Furthermore, we may not even be able to enumerate over the entire action space.

Now we are going to move into reinforcement learning. Reinforcement learning tries to learn value functions and policies by experiencing the environment, trying actions, observing the outcomes of those actions, and learning from these experiences over time. The main idea, and perhaps the single most important concept that defines the entire field of reinforcement learning, is temporal difference learning (TD learning). Almost all reinforcement learning algorithms, including those used in deep learning, belong to this temporal difference learning family. Additionally, temporal difference learning itself relies on dynamic programming concepts.

In the book, it is explained in more detail, but I wanted to clarify the connection and highlight the important differences. Temporal Difference (TD) Learning is a family of reinforcement learning algorithms that learn optimal policies and value functions based on data collected in the environment by trying out actions. This involves a trial-and-error process where we attempt actions and observe the outcomes, which can sometimes be positive and sometimes not so positive. A key aspect of Dynamic Temporal Difference Learning is that we do not assume we know these elements in advance.

We do not know the full Markov Decision Process (MDP). Instead, we try out actions and observe the outcomes. So it is more practical in a sense, right? Now, what is a temporal difference learning update? Again, our main mathematical objective that we are trying to learn is this value function \( V \), which assigns a value to a particular state.

But now we're doing this by learning and trying out actions in the environment. Basically, the main update rule that you observe in these temporal difference learning algorithms is a version of this. In short, we update the estimate for a current state value by using the current estimate we have, but we adjust it a little bit. In fact, we adjust it using this learning parameter called alpha.

This could be a small number. In practice, this would typically be a very small number. Additionally, over time, you would usually decrease this value so that it becomes smaller and smaller. This is related to learning stability. Essentially, there is an important aspect that can be instantiated in several different ways. I will show you just two examples of how to instantiate this in the slides here, but there are many more ways to do this. Similarly, if instead of learning the state value functions, you learn the state action value functions, known as the Q function, it looks very similar. Oh, I think I forgot the key here.

I need to make a note of that. So, line 31. Okay, yeah, there's a queue missing here. There should be just a queue here. Yes, it's similar to the one above.

You need to adjust your current estimate by moving a little bit towards a new estimate, which is defined by alpha and the character here. Okay, so this is almost the same as above, except that it's for a particular action and state combination. We call this the update target because we're moving towards that target, defined by the step size, which is alpha or the learning rate. "Step size" and "learning rate" are two common terms for it. Right, so the first algorithm that we are going to look at is SARSA.

This is one of the most basic algorithms you learn about. SARSA is called SARSA because the letters S-A-R-S-A correspond to an experience: the current State, the Action that we take, the Reward that we get, the next State that we observe, and the next Action that we perform in that state. SARSA. That's where the name comes from. It doesn't have any other deeper meaning, basically.

But in this case, here's the experience triple that I just told you about, which makes up this name, Sarsa. And here, the update target looks like this: it's the immediate reward that we receive after executing that action in that particular state. Then we add to that a discounted key value for the next action that we take in the next state. This defines the entire update rule for this algorithm. Essentially, if you take this definition of the update target and go back to this slide here and plug it in, then that's already your full definition of the Sarsa learning algorithm. Okay? That's basically the entire algorithm, and you can already go ahead and implement that and learn your value functions. So, if you look at this, it resembles the Bellman equation that we saw earlier.

We defined \( v \) or \( q \) by expressing these different sums over the actions and over the successor states. In this case, it's the closed-form Bellman equation for the state-action values, or the \( q \) function. If you look at the red blocks here, there is a correspondence to what we have above. The immediate reward is represented as \( r_t \). We also considered the discounted \( q \) function for the successor state, along with the successor action that we select under our current policy.

This is the thing up here. It shows the connection between temporal difference learning and dynamic programming. Down here is a classical dynamic programming approach, which is a closed form and requires us to perform complete sums over all actions and all successor states. Additionally, we need to know the dynamics. Instead, up here, we apply this only once for one particular state-action combination, one specific reward that we received, and one particular successor state's response.

This is our experience tuple, and it's basically a stochastic approximation that samples this learning update just once using our experiences. As you can see, it is derived nicely from the dynamic programming family, but it does not require us to have all this knowledge, nor does it require us to perform all the sums down here, which are very difficult to compute in practice. Ultimately, the update rule for the algorithm becomes this: you can plug in the update target here, and you can detail it out, so it looks like this.

This thing here is called the update target. The whole thing is referred to as the TD error because it's the difference between the new estimate and the old estimate, in terms of terminology. Another important piece of terminology that you often see in reinforcement learning, which you need to be aware of, is bootstrapping. Hands up if you know what bootstrapping is. Okay, what bootstrapping is… Alright, bootstrapping samples from the actual state and action and uses it to reinforce the Q-function that we have. We sample and update it, but it's not quite accurate—kind of getting there but not quite. Let me explain.

You're kind of getting there, but not quite. Let me explain. I think you're on the right track. Bootstrapping is actually simpler. Bootstrapping refers to a statistical concept that goes beyond just reinforcement learning; it applies to the entire field of statistics. It means making estimates—statistical estimates—by using other estimates. That's all there is to it.

So we are bootstrapping off of existing estimates that come from other parts of the environment to make estimates here. The way it is shown here is that we have our old estimate that we're trying to update. We use our old estimate along with other estimates from different areas for these various states. This method is called bootstrapping. It is very important because you see this concept a lot in reinforcement learning; bootstrapping is one of the core ideas. Here’s everything spelled out as pseudocode. I think I’m going to leave this here because there’s another piece of pseudocode that I will get to in just a second. There’s also a piece of mathematics that demonstrates that this learning algorithm is actually well-defined in the sense that, under certain statistical assumptions, you have an algorithm that, in the limit, will learn the optimal unique value functions and, essentially, the optimal policy function.

So, basically, there are two assumptions you need to consider. One is that all state-action pairs are explored infinitely many times in the environment. There are ways to ensure this theoretically by assigning non-zero probabilities to all actions. The second assumption involves standard stochastic approximation conditions, which essentially comprise two conditions. This means that the learning rate will change over time to prevent the updates from being overwhelming.

It's basically a geometric series, which is defined by the second part here. But it's a bit technical. I'm going to leave it at that. Just keep in mind that there are certain assumptions. Under these assumptions, these algorithms have a beautiful piece of theory that shows that, in the limit, they converge to these optimal value functions.

Purely through this process of trying out actions and learning over time what is happening, I mentioned earlier that there is an assumption we need to explore all states and actions infinitely many times. However, the problem arises if you have a fully greedy policy; you always choose one action—the greedy action. This would violate the convergence condition.

Instead, we need to have probabilities that are never zero. We need to have a policy that always assigns a non-zero probability to all the available actions. This is called an absolute greedy policy. Rather than giving all the probability to the action with the maximum value, we introduce a parameter called epsilon, which is between zero and one. This parameter defines the probability with which we choose a uniform random action instead of the greedy action. As a result, there will always be a probability assigned to all the actions.

And basically, it's summarized here. I'm going to move on to the next part now. This is probably the single most important learning algorithm in the entire field of reinforcement learning, and a lot of new algorithms still refer to this because the ideas are very closely related. So, it's called Q-learning.

And in fact, Chris Watkins and Peter Dejan. Peter Dejan also completed his PhD at our school at that time. In fact, quite a few notable individuals have ties to our institution. For example, who knows Jeff Hinton? Jeff Hinton recently received the Turing Award for his backpropagation algorithm, which drives much of deep learning. Jeff Hinton also completed his PhD at our school, along with some other notable figures.

So, there's a lot of history in that area, but basically, that's just a tangent. Q-learning is a very popular temporal difference (TD) learning algorithm, and it's even simpler than what I just showed you. The difference is that we're now essentially using the Bellman optimality equation. You're going to see this in a second. There is a maximum operator, and we learn the optimal state-action value function directly.

So, how does it look? We're returning to the idea that we need to define an update target. This is the concept that you saw earlier, and now it looks like this. It's even simpler than what we had before. The update target is defined as the immediate reward, \( r_t \), plus applying one discounting over the maximizer action and the Q function for the successor state.

So we've taken the maximum action, a prime, in the successor state at t plus one. This defines the entire update target: the reward plus gamma times the maximizer in the Q-function for the successor function. Again, we take that whole update target, plug it into the update rule, and that gives us the entire Q-learning update rule, which looks like this. This provides us with the complete Q-learning update rule.

This is a one line that defines the entire Q-learning algorithm. The difference compared to SARSA is that we have a maximizer here, making it non-linear. Additionally, we no longer need to sample our actions in the successor state, allowing us to use fewer experiences. All right, let's go through this pseudocode.

And that's the last pseudocode I'm going to go through with you for this part of the lecture. So, Q-learning, let's see how this works in practice by going through it step by step. First, we need to initialize the Q function. For every state and action that we can combine, let's just say we give it a value of zero, but it could, in fact, be arbitrary.

Let's say it's just zero for simplicity. In fact, the only thing that cannot be arbitrary is if there are terminal states, but that's not shown here. So, for simplicity, let's just say zero. Then we're going to engage in our learning. We will conduct multiple episodes.

Each episode starts at time zero and then resets the Markov Decision Process (MDP). This serves as our initial state. That is how every episode begins. Then we have our time steps, which are indexed as zero, one, two, and so on until five, and continue until you either terminate or exhaust your time step budget.

At every time step \( t \), we observe the current state \( s \). Remember that in Markov Decision Processes (MDPs), we assume that we observe the full state, so we know what the current state \( s \) is. We implement an epsilon-greedy policy, meaning that with probability \( \epsilon \), we choose a random action. We need to select this probability \( \epsilon \); for example, it could be 0.05, representing a 5% chance. Otherwise, we choose the greedy action, which is the one that maximizes the current key value for that particular state.

Okay? Those two lines here define our policy. Then we apply the particular action that we just sampled. We observe the rewards we receive after executing that action, and then we observe the resulting state, S plus one.

Sure! Here’s the text reformatted with correct capitalization and spelling: "Okay. Now, with this experience and the data that we have here—the current state, the action that we picked, the reward, and the successor state—that's all we need to apply the Q-learning update rule that we discussed earlier in the slide. We update our value estimate at this particular state with this particular action by modifying the current estimate, moving it by alpha in the direction of the TD error or this particular TD update. Is this clear for everyone, or are there any questions?"

It's a pretty straightforward small algorithm, right? Any questions there? So this is basically applicable to discrete states, correct? Yes.

Because in our example, we defined finite Markov Decision Processes (MDPs) where everything is discrete and finite. Do you have any other questions, or is it clear for everyone? The pseudo code is pretty straightforward, right?

You can imagine how to write this down in your Python script; it's just a few lines of code. The nice thing is that, under the assumptions I showed you earlier, you visit your actions infinitely many times, at least in theory. You also have your stochastic approximation conditions, which is a condition on the alpha value. This algorithm is guaranteed, in the limit, to learn the optimal unique value function of the Markov Decision Process (MDP). Once you have that, you also know what the optimal policy is, which is simply the policy that always selects the action with the maximum value in any given state.

That's it, right? That's very simple, but very neat. Okay, so last slide, I think for this part of the lecture, there’s now this question of how to evaluate algorithms. Okay, so you implement your MDP, for example, the master MDP that I showed you earlier. There are the states and the probabilities for how the states change and so on. Then you implement the algorithm, Q-learning, for example. You just saw the pseudocode. Okay, you initialize, you run through your learning episodes, you collect the data, you apply your update rules, and you want to see what's going on. You want to plot some results and evaluate whether or not we learned something. So there are a few things you can do, but this is basically the most common way to do this.

Evaluation plots show a variety of different algorithms. For simplicity, let's focus on this one for now. First, let’s examine the axes. On the x-axis, you have your environment time steps. You start at zero and then proceed to 100, 200, 300, and 400 time steps.

This is the number of time steps \( t \) that you accumulate over time. In fact, some people would plot the episodes here, but I think we should all be plotting the environment time steps. That's actually the standard now in deep reinforcement learning because different episodes may have different lengths. Sometimes an episode may finish earlier, and sometimes an episode may be longer.

And then, if you plot your episodes here, it may not accurately reflect the actual amount of training data. Therefore, showing the actual training timestamps across episodes—there could be many episodes here—is the most appropriate way to represent your training data. In this case, with 500, you have 500 experience tuples. This is your amount of training data. So, again, in this case, with 500, you have 500 experience tuples.

This is the amount of training time. Then we have our y-axis, which represents the evaluation returns. Returns, as you already know, refer to the sum of the rewards that you accumulate in an episode. In fact, we call this something specific here.

We call this evaluation return. The reason we refer to it as such is that there is also a term called training returns. Training returns are the returns you obtain during the episodes as you execute these pseudo-codes. In this case, we still have our epsilon-greedy policy. However, after training, you have your unique value function that you have learned. At this point, you do not want to use randomization anymore because it is unnecessary; you no longer need to learn or collect data. This is no longer needed, which is what evaluation returns signify. When we evaluate the actual policy that we ultimately deploy, it involves no randomization, and it reflects the actual discounted returns that you would obtain.

We can see here two algorithms: the orange line represents Q-learning, while the blue line refers to SARSA. For this simple example with the Master Rover, you can observe that both algorithms quickly learn to derive the optimal unique value function and, correspondingly, the optimal actions. The horizontal dashed line serves as a comparison, indicating the actual unique value of the initial state, which is 4.1. As a result, it is evident that we successfully learn a policy that executes the optimal sequence of actions in the initial state, as we overlap with this horizontal dashed line.

Here are a few more plots. You can see down here, for example, in the lower left, we only show lines for Q-learning, but we use different learning rates, specifically different values for alpha. For instance, alpha values of 0.01, 0.03, and so on. You can observe that the different rates have a significant impact on the actual ability to learn the optimal policy. For example, it turns out that if you use a learning value of what is it?

Yes, one over the k, I think, is the episode number. I need to check this again. But basically, it decreases over time. That essentially implements the stochastic conditions that I showed you earlier. We learn very quickly.

But if we use instead a learning rate of, say, the blue line, which is just a constant 0.01, you see that the learning is much less efficient. In fact, we're actually plateauing here. We will never reach the dashed line at the top. So you can see that having a constant learning rate is actually violating the condition, and in this case, the constant was essentially too small.

It was not able to actually collect enough data to convert to the optimal lineup here. What this means for you is that this hyperparameter, or the learning rate, is a very important part of this learning algorithm and needs to be tuned very carefully. This is still a problem in reinforcement learning. These are some of the simplest, oldest, and most basic concepts. It was already a problem then.

Today, in the most sophisticated, state-of-the-art deep reinforcement learning algorithms, we encounter the same fundamental problem: we need to thoroughly tune hyperparameters. However, tuning has become much more challenging due to the scale of our networks and the complexity of the problems we are addressing. Additionally, running these learning algorithms is quite expensive. As a result, tuning hyperparameters—along with various other parameters—becomes one of the more enigmatic aspects of reinforcement learning, particularly if one aims to make it practical. It is evident that there are certain elements in reinforcement learning that remain implicitly challenging. Even after decades of research, we still find ourselves experimenting with different alpha values to determine the best option. We are still in this phase of trial and error. That concludes this part of the lecture. We have provided an introduction to multi-agent systems and multi-agent reinforcement learning. Additionally, we have discussed some single-agent fundamentals in reinforcement learning, such as Markov decision processes, value functions, dynamic programming, and temporal difference learning techniques like SARSA and Q-learning.

And I think we're going to take a break from here. We're going to do some questions and then take a break. In the next part of today's lecture, we're going to be discussing games, which is our first step into the multi-agent topic. But before we go into the break, I just want to see if there are any questions, either here or online, about any of the topics we've covered so far. Any questions?

So don't be shy, right? Any questions you have? First question there, yes. I think we have microphones. For the example of multi-agent reinforcement learning that you showed, you were using a single reward that some agents needed to disentangle.

I imagine there are certain situations where agents would have different reward functions. So I assume that's not the only case, and there are vectors of rewards. I guess. Absolutely, yes. That was just what's called a common reward.

There's only one reward; everyone has the same thing. That's already kind of difficult for the reason I showed you. However, in many really interesting applications, as you mentioned, that would not be the case. In fact, that's what we're going to be discussing in the next part of the lecture: how you can define these games and how agents may have different reward functions. Sometimes, these reward functions might be a little bit similar.

Sometimes, they might be completely opposed. For example, if they're playing a game of chess, you're my enemy, right? Essentially, those reward functions are completely opposed. This makes it really tricky to define what optimality is.

So, it's really rich in space. Regarding the reward, yes, the credit assignment problem exists even in a competitive setting. Yes, definitely; this does not affect that problem. In fact, there are actually two types of credit assignment problems. The first credit assignment problem, before we even consider multi-agent scenarios, is inherited from the single-agent reinforcement learning (RL) problem, and it's called temporal credit assignment. Temporal credit assignment refers to the situation where, for instance, I take a sequence of actions—action, action, action, action, action—and then I observe certain rewards at the end.

Now the question is: which of these past actions were actually important? Which of these past actions were needed in order to achieve the reward that I just received, and which of them were not necessary? This is temporal credit assignment over time. Temporal. And now this concept also exists in multi-agent reinforcement learning.

And now we also have the lateral version of this, which addresses whose actions contributed to the reward. Not just which past actions, but actually whose actions they are. Because we have all taken these actions simultaneously, and some of them may have an impact on the actual rewards that the agents receive. However, whether or not we are in opposition or how these rewards are defined does not affect the existence of this problem. The problem always exists.

It sometimes can be more pronounced than at other times. For example, in the earlier case where there's only a +1 reward that everyone receives, it becomes really tricky for agents to disentangle the contributions of individual agents' actions. However, this complexity still exists even if one agent receives a +1 and the other agent receives a zero. For the agent that received a zero, it remains unclear why it got a zero instead of a one, correct? It still has to learn that it received a zero not because of the other agent's action, but because of its own action. So, this issue still persists. Thank you! I think there’s more to discuss here. Yes, just on slide 15, I had a question. Would you like me to go back to slide 15?

Sure! Here's the text reformatted with correct capitalization and spelling: "Yeah, okay. It's so rough. I was just curious why there is an arrow going back from the state at the current time point to the reward at the previous time point. What’s the dependency? Maybe let's look at this one."

We're only concerned about the graph, right? So which arrow are we talking about? There's an arrow from state \( s_t \) going back to \( r_{t-1} \). So, is the reward in the previous time point? Yes, because the most general definition of the reward function is actually a mapping from the current state and action to the successor state.

And in fact, in many practices and applications, the mapping really is just this arrow, and the other errors basically depend on what current state you ended up in. This is the most general way to define a reward function, but in practice, you may end up having a reward function that only depends on this or only depends on these two things. However, the most general one basically allows you to represent any of these kinds of definitions that you can come up with, including any of these subsets. Does that answer your question? I am a bit confused, though. How does it affect the reward at the previous time point and the current state?

Because that's just terminology. Basically, this is the state we're in now, and we're using \( r_{t-1} \) for the reward we received when entering the state. It's simply a matter of terminology. In contrast, for example, the book on reinforcement learning by Richard Sutton, which has been used for a long time, actually employs different terminology, where this is referred to as \( r_t \), not \( r_{t-1} \). However, for various theoretical reasons, we decided to adopt this terminology.

Terminology. Does that clear things up? It's just a notation aspect, I think. Basically, it just means this is the reward that we receive once we move into the current state, \( s_t \). If it makes it easier for you mentally, you can simply change the notation here and use a different notation, \( r_t \).

Maybe then it looks more logical to you. But there are other reasons why we haven't done that, which are explained in the book, basically. Okay, I see. And a second question: what would be a situation where Q-learning would be preferred over SARSA?

One is SARSA; there are some things that we haven't covered here. I didn't tell you the whole story, but there's more to it. There's an idea called off-policy and on-policy reinforcement learning. SARSA is an on-policy reinforcement learning algorithm because it always uses only data from the current policy it is executing.

Q-learning is an off-policy algorithm because, in the learning update that you saw, we have a max operator. This means that in the targets it's computing, it essentially uses an estimate for the maximum action in the subsequent state, which is never actually executed. That's why it's called off-policy. The reason I mentioned this is that off-policy and on-policy algorithms have different trade-offs. For example, Q-learning tends to be much more efficient than SARSA because of its off-policy nature. SARSA, on the other hand, tends to be more stable than Q-learning because its on-policy nature makes certain theoretical properties easier to satisfy. Therefore, there are specific theoretical reasons why you might prefer one algorithm over the other.

But in practice, off-policy algorithms tend to be much more efficient. In fact, today's state-of-the-art green phosphor-moyering algorithms are primarily off-policy algorithms for this reason. This means that you can reuse a lot of data that does not come from the current policy. Thank you. More questions?

So you said that there is only one optimal Q* value, but there can be different policies that can lead to this Q*. Does that mean that all these different policies that can lead to Q* are optimal policies? Yes. Let me give you an example. Let's say we're in a current state where we have three actions available. If the optimal, unique Q-value function gives a value of 5 to two actions and a value of 0 to the other action, then we know that the action with a value of 0 is never going to be taken; it is not optimal. The other two actions have the same value, though, under the optimal value function, which could be the case. Therefore, any policy that assigns arbitrary probabilities only to those two actions is also an optimal policy.

It doesn't matter how it's assigning probabilities to any one of these two actions that have the same value. Because the probability spectrum is infinite, it means that we have infinitely many optimal policies. Therefore, any one of these assignments of probabilities, as long as it's only on these value actions that have the same maximum value, is also an optimal policy. This is a simple example that shows that there can be infinitely many optimal policies, but only ever one unique optimal value function. When we're discussing the algorithms to find the optimum policy for maximizing the evaluation return, after that simulation, if I want to deploy these policies onto an actual system, how much discrepancy should I expect when implementing them in a real operating system?

Because, when you explain the Markov Decision Process (MDP), there are many assumptions. However, these are just assumptions. In a real scenario, you will encounter various differences, so how would I then determine my expectations regarding performance? That's a good question. Let's break this down into parts. If the MDP we are solving here is an accurate model of the real world—let's say it perfectly describes reality—then the evaluation returns precisely reflect what you can expect if you take the policy at any specific point in time. For instance, if I stop training at a certain point and apply the policy from that moment in the MDP, this will yield the average returns I can expect to see. If I take the policy from a different point in time, that will give me an exact expectation as well. It's important to note that these evaluation returns are based on the greedy policy, which is different from what we use during training. During training, we incorporate randomization to explore different areas. However, after training, we remove that element.

There's no randomization anymore. We only do the greedy stuff, and that's exactly how you would execute it in the environment. That's the first part of your question. However, I think what you may be getting at is, what if the Markov Decision Process (MDP) is wrong?

What if the MDP is not quite doing what the real world is doing? That is a very good question, and it is exactly the reason why we care about reinforcement learning and not about dynamic programming. Dynamic programming requires the model. Even if we had the model and could write it down, we would still need to perform all the calculations and handle all the expensive computations.

There could always be the problem you’re describing, where the model might not reflect the real environment. However, with reinforcement learning, I can apply it directly in the real world where there is no model—just the real world. Therefore, there isn't this discrepancy, right? You can learn directly from the data in the real world.

In that case, there could still be problems with assumptions in reinforcement learning. For example, reinforcement learning assumes that there is a Markov assumption, even if it is actually using the real model. It still assumes that whatever the real model is, the real world is Markov. That could already be a problem, right? If that's the case, then there could be instability in the learning process and other related issues.

But that's one of the beautiful things about reinforcement learning. The fact that I can throw it at any problem, there can be any non-linearities, it could be high-dimensional, and there could be lots of things that I'm not even aware of, right? Lots of noise, lots of factors that are hard to specify, and many coupled equations. I don't care. I just throw it at this problem.

As long as certain assumptions are satisfied, such as the Markov property, I have a guarantee that the algorithm will still learn an optimal solution. That's one of the nice things about reinforcement learning. It's really effective. For example, as I mentioned earlier, if I can elaborate a bit more, remember I showed you the warehousing example that we're building. Warehousing is actually quite a complicated problem.

There are very complicated time-dependent dynamics in the order profiles as the orders keep coming in; they change over time. Additionally, your machines have vehicle models that exhibit non-linear dynamics. Writing down everything in a warehouse like this would be impossible. I could not document the details, compute any of the information, and even if I could, it would not match reality. However, we didn't have to.

We didn't have to write down any of the information. We just trained in the real world, essentially. We also have an extremely high-fidelity simulator that is trained with data from the real world. That's why we're using reinforcement learning in cases where classical approaches, which assume all this knowledge or are not able to learn directly from the real world, would fail.

Yeah. Perfect. Thank you so much. Thank you. Is there a question up here?

Online questions? Sure, yeah. Okay. I'm not sure, but I think that in some of the slides I saw that for applying dynamic programming and these, can I say, pre-reinforcement learning algorithms, we have to assume that we have knowledge of the whole environment and stuff.

For POMDPs, there's an approach using reinforcement learning, or possibly deep reinforcement learning. They cannot be approached using dynamic programming or other partially observed MDPs. First, I want to ensure everyone understands the question. I discussed programming and these other partially observed MDPs.

Yes, I should clarify for everyone to understand the question. I presented Markov Decision Processes (MDPs) and explained that there is one key assumption: we have complete visibility of the environment. The current question refers to Partially Observable Markov Decision Processes (POMDPs), which are a more complex model. In POMDPs, we only observe certain aspects of the world, rather than having full visibility. This model is a bit more realistic.

And now the question is, can we still use dynamic programming in this kind of model? Or can it be approached through reinforcement learning and deep reinforcement learning? Oh, yes, for sure. Or policy gradients? Yes, definitely.

First of all, dynamic programming algorithms also exist for Partially Observable Markov Decision Processes (POMDPs), and they are very sophisticated. Everything we do in reinforcement learning is under partial observability now, so we definitely tackle these cases. Would you say that, at the state of the art, we have been conducting more research in POMDPs than in Markov Decision Processes (MDPs)? I mean, if I look at the papers that come out, I still see many that assume full observability if they address other kinds of problems.

Many papers focus on partial observability. Almost all the work coming out of our lab involves partial observability because it is more realistic and more complex. Yes, I would like to specialize in robotics. Would you say that Poem Devis is more in the robotics world? It depends.

So I would say that if you have a highly controlled environment where you have your proprioception and very reliable sensing, then it's quite close to full observability. To be honest, you can treat it as such. We've done that as well, and that's probably what you should do to keep things simple. However, there are many robotics applications where you have intrinsic partial observability. For example, self-driving is a business that I was involved in.

When you have self-driving vehicles, one of the biggest problems we have had to deal with is occlusion. Occlusion means that there are cars nearby, and because of these cars, I cannot see what is in front of them. Or there might be someone parked in a spot, and because someone is parked there, I want to get out, but I cannot see the traffic coming. This makes it very challenging for a control system to manage the situation effectively. These kinds of occlusions are critical, but they can be addressed using various inference and reinforcement learning techniques. Yes, I think we want to take some online questions now. Okay, this question comes from the beginning when you were discussing single agent versus multiple agent systems.

They were talking about how you mentioned that a dimension of 216 represents too large an action space. They were asking what would constitute a large yet tractable action space with current reinforcement learning algorithms. I'm trying to get back to that slide. Which one was it? Ah, yes, this one, right?

Yeah, so the question is: what is actually a tractable action space? That's an interesting question. I suppose someone should go ahead and try to figure this out.

The answer to this question, I guess, changes every year because things get better. So, what's a tractable action space? It's not just about the action space; it depends on the dimensionality of your observation vector as well. Sometimes, you have a problem where observations are very small.

Sometimes, you encounter a problem where you have an extremely high-dimensional observation vector. For example, let's say I have a robot that can see a camera feed. It's a very high-dimensional observation, and it changes very quickly.

And depending on how you define the observations, that could already be a significant factor in determining whether or not a problem is feasible before you even discuss the action space. So, the answer to this question is broader than just the action space. However, this example is already enough to demonstrate that, regardless of the problem or observation space, even if it's a very simple observation space, the action space is already very hard to deal with for existing approaches. I hope that people online can hear me okay. Did the person hear the answer clearly? Yes, I think she did. This is an interesting question, and I want to turn it back to the person who asked the question. If that person has any estimates based on their experience that they would like to share, I would be interested to know what they consider to be the borderline between feasible and not feasible. Or, perhaps people can participate in a little online guessing game and share their experiences regarding what they've been able to accomplish and what was too difficult for them. It would be fascinating if those with experience using Deep Reinforcement Learning could share their insights on Slack.

What were they able to do, and when did they hit a wall in terms of scaling? Okay, let's take some more online questions. That one is from slide 40, and they were asking about the type of smoothing in the plots of the training curves. Slide 40? Yes.

Okay. Is it a smoothing in the time dimension or a variation across different seeds? Could you please repeat the question? What does the smoothing on the back of the plot refer to?

What's the smoothing? The smoothing colors, I guess. It's kind of brownish. Oh, you mean the shaded areas? Yeah.

The shading, yes. This can vary across different plots. Most of the time, it represents the standard deviation or the variance of your evaluation returns. To explain this, let's say we are at training step 100 at this point, and we're aiming to reach the purple line here. If we take the policy from this point after 100 training time steps, then we should expect to see the evaluation returns at this specific point.

But because the environment can have noise effects, there are stochastic effects; sometimes actions lead to one outcome, and sometimes to another. These are the probabilities that we cannot control. That's why there is variation in the returns that we realize, represented by the shaded area. If the shaded area is very high, like in the earlier days of training, it indicates that the policy can be quite inconsistent regarding the returns that you achieve.

And that's because initially, the policy will not be optimal. It will assign probabilities to actions that do not lead to good outcomes. However, as you get closer to the optimal policy, you will notice that there is still some residual stochastic effect present, but it is much smaller, as indicated by the shaded area, compared to the earlier stages. This change occurs because we have now converged to the optimal value function, where the only remaining random effects are due to the stochasticity in the environment that we can no longer control. So, essentially, that's what it means. Is that clear for the person online? I think so. Okay.

Okay, another question is, do all actions have to be simple actions, or can you have a more complex action space? For example, can each action be another subroutine? And if they can, can you have combinations of both simple and complex actions? Yes, absolutely. One idea that I think is worth mentioning is called hierarchical reinforcement learning.

Hierarchical reinforcement learning means that your actions are now decomposed into a hierarchy. For example, one action could be something like "clean the kitchen." Although "clean the kitchen" sounds like a single action, it can actually be decomposed into a hierarchy of actions, which includes moving to the kitchen, picking up the cleaning supplies, and cleaning objects A, B, C, and D. The sequence of these actions collectively makes up the abstract action of "clean the kitchen." So, you have this hierarchy, which results in a much more complex composed action.

In fact, it can be even more complicated with the hierarchy. You have this hierarchy, and in this case, it is a much more complex composed action. You can expand the hierarchy and say that "clean kitchen" is associated with "move to kitchen." The action of moving to the kitchen itself is a hierarchical action that can be decomposed into actions such as "turn around," "accelerate," and "turn around again," for example.

So you can imagine how actions can be much more complicated and complex, and there are many algorithms that have been designed to deal with these kinds of complex actions. Another example is that actions can be parameterized. For instance, let's say we're playing soccer or football. One action could be kicking the ball, but typically, there would be a parameter like kicking the ball with a certain strength.

How hard do you want to kick the ball? Kicking the ball would be a discrete action, but there could be a continuous parameter that determines just how hard to kick the ball. For example, it could be a value between 0 and 1. There are algorithms designed to handle these types of composed actions; however, here, we kept it very simple.

There was none of this. Okay, I think let's move on. We're going into the break now because we still have the second part of the lecture. Please relax a little bit, and if you have more questions, feel free to come to me; I'm happy to chat. Otherwise, I'll see you at 12:15. Thank you. Okay, good to go! Alright, welcome back everyone after the break. I hope you found the first part interesting. We talked about the basic ideas of multi-agent systems and learning in multi-agent systems.

Why do we care about this? Then we went through some very basic ideas in single-agent reinforcement learning, without any deep learning components. This was our first foray into reinforcement learning. Now, I'm going to move into the multi-agent aspect by discussing the first piece of this bigger puzzle, which is games.

We're going to be talking about how to represent the world—nothing else. We're not going to discuss how to learn in that context, nor will we talk about how to evaluate in that space. We will solely focus on these different models for representing the world.

Okay, so the first point that I think we need to be really clear about is this: as I mentioned earlier, you can find all the slides online if you visit the book's website. Therefore, there is no need to make copies of the slides here. There will be two parts to this lecture.

First, there are, in fact, three parts to the game models. This is the most important part. Then, we will discuss some other topics, such as how to model communication and the assumptions in some of these game models. Remember that in Markov Decision Processes (MDPs), there were certain assumptions. Similarly, there are certain assumptions here that you need to be aware of as well.

Okay, let's get into it. As before, raise your hand if you have any questions or if anything is unclear. If there's an important question online, feel free to interrupt me as well, okay? There is a hierarchy of game models, and this is a one-slide graphical description of these different game models and how they relate to one another.

Let's go through this. We will delve into some of these models in more detail in the slides. You can see there’s a nice diagram here. The first thing you should recognize is the Markov Decision Process. This is the concept that you just learned about.

There's only one agent, and there are multiple states that we sort of go through. Right? So, the environment has states, and each state changes. That's the Markov Decision Process (MDP). The easiest kind of game model, when we have multiple agents, is the repeated normal form game or the normal form game and then the repeated version of that.

In this case, we have just one state, but we have multiple agents in the repeated normal form game, or the normal form game followed by the repeated version of that. Here, you can see that the numbers are inverted. In a Markov Decision Process (MDP), there is one agent in 'M' states. Now, we have 'N' agents and one state.

There's only one state, or essentially, there's no state. Nothing in the environment changes, but there are multiple agents who repeatedly play a game. For example, rock, paper, scissors would be an example of that. Then, there is the broader category of games known as stochastic games. Stochastic games generalize both the Markov decision process and the repeated normal form game.

Now we have \( n \) agents and \( m \) states. There are multiple agents and multiple states, but they are still fully observed. An even larger class of problems, which gets really complicated, is the partially observable stochastic game. In this case, we still have \( n \) agents and \( m \) states, but they are only partially observed. Each of the \( n \) agents may have their own reward function and preferences, and they can only see their own part of the environment, which may differ from what the other agents are seeing.

It's quite complicated, right, if you think about it? They are learning in these games. In this lecture, we're only going to talk about these models, not about learning, algorithms, and so on. We're not even going to discuss what it means to solve these things—that's for tomorrow.

For the rest of the lecture today, we're only going to be talking about these formal frameworks. It's very easy. Okay, so let's start with the absolute simplest type of multi-agent model that exists, basically, that you can do. It's called a normal-form game. Let's talk about where this name comes from.

It's inherited from the game theory literature, where much of this work originates. I really don't know why it's called "normal form," but that's what it's called. Let's just go with it, basically. In fact, many people refer to them as matrix games because, if there are just two players, you can represent it as a matrix. However, the general term is "normal form game."

It defines a single interaction between two or more agents. Let's just say two for simplicity. It essentially provides a simple kernel for all the other more complex models that you will see later, so this is a good starting point. How is it defined? Okay, let's go through this step by step. First, it is defined as a three-tuple. There is the set of agents, denoted as \(I\), called \(I\) because \(i\) is used for indexing. We use these indices in the actions and so on for the agents and their rewards. Okay, so there is a fixed number of agents, and returning to the question we had earlier, this number of agents does not change.

Which, over time, is fixed. Then, for every agent in that set of agents, we typically use \(i\) or \(j\) to refer to the agents. Most of the time, we use \(i\). There is a finite set of actions that an agent can choose from. For example, in rock, paper, scissors, there are three options: rock, paper, and scissors.

Every agent has its own reward function. In this case, a reward function is defined as a mapping from the combination of actions of all the individual agents into a scalar. The key difference between our previous understanding and the current one is that the reward function is not solely based on the agent's own action; instead, an agent's reward can now be influenced by the actions of all agents. This collective influence is referred to as a joint action. The Cartesian product of the different action spaces is known as the joint action space. This is perhaps the most important aspect of the definition of a normal form game: the presence of individual reward functions for each agent and the fact that these reward functions are affected by the actions of all agents.

Okay, that's probably the single most important thing. Was there a question here? No, it was just that something happened. Okay, so in a normal form game, there are no time steps or states. Earlier, I said there is just one state, but the fact that there's just one state that never changes means the same as if there is basically no state at all.

Agents choose an action based on observer rewards, and it procedurally works like this: In the first step, every agent samples an action from its policy. As I mentioned earlier, we will use index \( i \) to refer to agent \( i \). Each agent \( i \) selects an action from its action space using probabilities defined by its policy \( \pi_i \). The resulting actions from all the agents taken together are referred to as a joint action, which is represented as a tuple. This joint action is then executed, leading to an individual reward for each agent, defined by their respective reward functions. Consequently, agent \( i \) receives a reward \( r_i \), which is determined by applying its reward function to the joint action selected by the collective agents. This is essentially how a run-off in a normal form game works. There are different classes of games, and this framework applies to all the games we will be examining.

The most basic class that was studied in the early days is called the zero-sum game. It is referred to as a zero-sum game because the sum of the agents' rewards is always zero. Formally, it is defined as follows: if we sum the rewards that all the agents receive for a given joint action, the total will be zero. This concept can also be generalized to what is known as a constant-sum game. However, constant-sum games can always be mapped into a zero-sum game, as it merely involves a constant number that shifts.

Okay. Some games. What's an example? An example is rock, paper, scissors. If I win, you lose.

If you win, I lose. And if there's a draw, then we have the same outcome, which is also zero. Okay. Another game, another example is chess. Okay.

Win, lose. These kinds of win-lose games are typically zero-sum games. The next class is a common reward game. In a common reward game, all the agents have the same reward function. They always receive the same reward.

You saw the earlier example that I showed you in level-based forging, where they picked an action and then everyone received a plus one reward. You remember that, right? That was a common reward game. Again, you can also have this as a normal form game. The most general class is the general sum game.

There are no restrictions on the relationship between the reward functions here. Basically, anything that is not a zero-sum game or a common reward game is considered a general sum game. It is called "general" because there are no defined relationships between the rewards—none that are documented, anyway. Here are some examples of what is referred to as a matrix game.

We call them matrix games because if there are only two players, we can represent the reward functions as a matrix. It looks like this: for example, rock, paper, scissors is a game that I keep mentioning. We can write this down as a matrix where there are three actions for the two players. For the row player, there is rock, paper, or scissors, and for the column player, there is also rock, paper, or scissors.

Let's say they pick a particular combination of actions. For example, the row player—let's say Player 1—picks action R for rock. And let's say the column player, Player 2, picks action P for paper. Then, because paper beats rock, Player 1 receives a reward of -1, and Player 2 receives a reward of +1. It works the same way for the other entries here.

If both of them pick the same action, such as "rock," then there's a draw, and they both get zero. It's straightforward, right? That's why we call it a matrix game. There are a few more examples here. For example, the coordination game is a common reward game, and that's why there's only one number in each cell. Both players receive the same number, which is called coordination because they need to pick the same action. If they both choose "A," then they get 10; if they both choose "B," then they also get 10. However, if they miscoordinate their actions, meaning they choose different actions—either "B, A" or "A, B"—then they get zero. Okay, that's a common example. Lastly, there is the prisoner's dilemma.

This is probably the most famous and widely studied game in game theory. It models a situation where there are two people who are in prison. They cannot talk to each other, but they are interrogated by the police. Each of them has two options: they can either cooperate or defect.

Cooperating means that they stick together; they don't inform on each other. Defecting means they will say, "It wasn't me; it was this other guy." Essentially, if both players cooperate, they each receive one year in prison. However, if Player One defects while Player Two cooperates, Player One goes free, and Player Two receives five years in prison. This illustrates that it's not a zero-sum game; it's also not a common reward game. Instead, it's known as a social dilemma. What should they do in this kind of situation? It's interesting, right?

What is the right way to play this game? There are many different answers to that. In fact, it turns out that most of the time, the algorithms would learn to defect. "Defect, defect" is actually the unique Nash equilibrium in this game. While this is theoretically interesting, it is not practically favorable; it means that everyone is very selfish and always turns on the other player. It's difficult for algorithms to escape from this outcome due to various properties. We have zero-sum games, common reward games, and general-sum games. So, that was the normal form game. Of course, you can repeat it, which leads us into the realm of learning. To learn, you need to repeat experiences and collect data. A repeated normal form game is essentially the same concept; we have a normal form game defined, for example, as a matrix, and we just repeat it over and over again—whether for a hundred times or infinitely many. If you visualize this as a graph, there is only one state, which is defined by this reward function here. If the agents choose actions such as row 2, column 1, they receive a reward of 2, 2. So, player 1, or agent 1, gets a reward of 2, and the same applies for agent 2.

But if they pick, for example, Action 1 or Action 2, then Agent 1 gets 0, and Agent 2 gets 1. And it continues like this. That's why the probability of returning to this state is 1. This is what a repeated game is: it involves repeating the same normophone game over and over, for a fixed number of time steps or indefinitely.

And now the important thing is the difference is that the policy can now actually be conditioned not just on nothing, which was the case in normal form games, but actually they can be conditioned on the history of the joint action that they executed in the past. So the history is this \( H_t \), and it means it's all the joint actions that were executed from time step zero until the most recent time step. This is what they have seen so far that happened in the game. Sophisticated strategies can be conditioned on that. For example, there's a famous strategy called "Tit for Tat," which is used in the Prisoners' Dilemma. Basically, it's a strategy that is conditioned on the most recent joint action and it essentially copies your last action. So if you defected most recently, I'm going to defect.

If you cooperated most recently, I'm going to cooperate again. "Tit for tat" is an extremely simple strategy that turns out to be a really effective approach for a prisoner's dilemma. Anyway, the interesting aspect is that we repeat this interaction, and policies can be conditioned on the entire history, though they don’t have to be. For example, tit for tat is conditioned only on the most recent joint action. Okay, so that's it.

That's normal form games and repeated normal form games. The simplest concepts we are starting with for game models. Next, let's move into a more complex setting, which is the stochastic game. Stochastic games are called that way because Shapley, who wrote the paper "Stochastic Games" in 1953, received the Nobel Prize in Economics for a significant body of work, including contributions to game theory. They are called stochastic because there are now stochastic outcomes for the different actions that can be selected, similarly to a Markov Decision Process (MDP).

The generalization is that we now have both scenarios represented. We have Markov Decision Processes (MDPs) as a special case, where there is only one agent but multiple states. We also have repeated normal-form games as a special case, where there is one agent but only one state. Additionally, there are many more games that involve multiple agents and multiple states. The concept of a defined stochastic game introduces the notion of states, which can change over time.

And it's defined by these six elements, which look like this. First, again, there's a finite set of agents, which is the set I. Then there's a finite set of states. It looks very similar to what we saw in the MDPs. As we saw with the MDPs as well, there's a subset of states, which are the terminal states.

This is when the game fails—when it finishes. When we reach one of these games, one of these states, then we complete the game. For example, in the lever-based foraging scenario, a terminal state would be one where all the apples are gone. At that point, it becomes a terminal state.

And now, in addition to that, we also define, similarly to normal form games, individual action spaces for the different agents. The agents have their own reward functions, as before, but now the reward function is a little bit more complicated. The reward function for agent \( i \) is defined as a mapping from the previous state and action that we took, and the new state that we arrive in, over a scalar. This looks very much like the reward function definition for Markov Decision Processes (MDPs), except for the difference that the action \( a \) in this case is now the joint action space, which includes the actions of all the agents, and not just one agent. Similarly to normal form games, every agent's rewards—specifically, the reward for agent \( i \)—are affected by the actions of all the agents.

Okay. Lastly, like in Markov Decision Processes (MDPs), there is a state transition function that defines the probabilities of reaching particular successor states when a joint action is executed in a state. Again, this is defined over the joint actions, so every agent's actions can impact these probabilities. Additionally, there is an initial state distribution, as we had before, similar to MDPs.

It looks very similar to both Markov Decision Processes (MDPs). You can recognize certain elements, such as the position function and the initial state distribution, and so on. It also resembles normal-form games because you can identify the individual reward functions defined over the joint actions. Additionally, there is the number of agents involved, so you can see how they all represent special cases.

We can write this down. Here’s an example presented as a graph. We can say that every state can actually be viewed as a non-repeated normal form game. A non-repeated normal form game means that there is only one instance in which we conduct the normal form game. In this example, let’s consider three states: S1, S2, and S3.

And every state is defined by a matrix game for the two agents, which is shown inside the states here. You can see that every state can have a different matrix game to define the rewards in that state. There will be an initial state; let's say s1 is the initial state. If we go through this example, initially, if the agents pick s1 and both select action 2, then the reward for them is 1-1. This corresponds to the cell in the lower right.

And then there's a probability with which we enter successful states. If we choose the joint action of 2-2, then with a probability of 0.5, we will return to the same state, or with the other probability of 0.5, we will move into state s2. In state s2, we have a different reward function. Again, let's say if we choose the joint actions of 1, 2, 1, 2, then they receive rewards of 0 and 4, and they will move into successor states. With a probability of 0.8, they will return to the s1 state, or with a probability of 0.2, they will move into the s3 state, and so on.

So you can see, it's a small, nice example to understand how to write down a stochastic game. Of course, I'm only showing a subset of these arrows. I'm only showing you these arrows for some of the joint actions. But in every state, the player can execute any one of these four possible joint actions, right? A combination of actions for both players, both agents.

By the way, you sometimes hear me switch between "agent" and "player." It's just because, in my head, there's a lot of game theory literature, and in game theory, they refer to it as "player," not "agent." So sometimes I accidentally say "player," but for us, it means the same thing. "Agent" and "player" are synonymous, okay? In fact, in the book, to help people from both of these communities communicate with each other, I added a section at the end of Chapter Three that serves as a dictionary for game theory and reinforcement learning.

Because we use a lot of terminology, but often this terminology means the same thing, like "player" and "agent," I added a dictionary that you can use to make your life a bit easier. All right, so let's look at this stochastic game as a process and go through it step by step. First, we have an initial state, which is sampled from the initial state distribution. Then, at every time step, at this constant step t, every agent observes the current state.

Like in the Markov Decision Process (MDP), we're assuming we get to observe the full system. Each agent then chooses an action from its action space with a probability defined by its policy, which is conditioned on the history. I think I missed the index here; I need to make a note about that. I believe the index missing on the policy should be π (pi). So, this will be fixed later today. In this setup, you can see that the policy is now conditioned on the state-action history, which includes all past states and all past joint actions that were executed. Since every agent can observe everything, they can also condition their decision-making on the entire past. Then, given the current state and the joint action selected by the agents, they can proceed accordingly.

We're going to move into a successor state for \( S_{t+1} \) with a probability defined by the state transition probabilities here. Lastly, every agent receives a reward, which is defined by its reward function. The reward function is a mapping from the state and joint action to the successor state. As I mentioned earlier, I think there was a question here. Most of the time, this is defined based either on the actual state that we ended up in or just on the action that we executed in a particular state.

But this is the most general way to write it down. In the book, in Chapter Two, there's actually a section at the end where I formally show, theoretically, that the substates are still equivalent to this more general version, if you're curious. Then, these steps are repeated until we reach a terminal state. For example, this could happen when all the apples have been collected or when we reach a maximum number of time steps. Let's look at the level-based forging example.

This is the thing that I introduced earlier to give you a basic example of a stochastic game. How do we write this down as a stochastic game? In this case, let's start with the states. First, we have states which are in the set S, and they're basically just a vector of x, y coordinates or positions for the different agents and the different items. For example, every agent and item has an x, y coordinate.

Then there is a binary flag for each item, which is zero if it has been collected and one if it has not been collected and still exists. You might also want to add elements in that vector to represent the different levels if they are not constant. So, that is the state; the state is just a vector that has the coordinates and the levels, and so on. What's the next thing we need to define? Then we need to define the actions. In this case, there are just four directions: up, down, left, and right. There's a collect action that you can attempt, and then there's a no operation action, which means nothing is done for that agent. The next thing we need to define is the state transition probabilities.

In this case, it's deterministic. For example, if this agent here picks the action to go up, then for sure in the next state, it will end up here. So, there's no probabilistic or stochastic effect in this scenario. Lastly, we need to define the reward function. In this case, let's say it could be a common reward, which means that everyone receives a reward of plus one if anyone picks an item. Alternatively, it could be a different setting where we have a general sum, and only the agent that actually picks up an item receives the plus one reward, while the others receive a zero reward.

So, you can see how you can model this in different ways, but I think this is a neat, simple example that shows you how you can actually write down an example like LBF as a stochastic game. Does this make sense to everyone? Do you feel it makes sense? Are there any questions about this part? I think it's clear, right?

Okay, going back to this. The next thing, oh, I think you cannot actually see the color here. This was, I think, supposed to be blue up here, but I'm going to have to go back and change the colors. Oh, you can see it on the sides. Okay, it's just a projector. Great!

Thanks. Yes, so now we're going to move on to the last section, which is the partially observable stochastic game—the most complicated, largest, and most complex model that we're examining in the book. In fact, there are even more complex models that we don't cover here, but we will focus on this one because it's all we really need for most applications. As the name suggests, partially observable stochastic games are an extension of stochastic games, incorporating the element of partial observability.

In stochastic games, the agents can see everything, but in a partially observable stochastic game, each agent has its own local observations. Essentially, that is what it means. Partially observable stochastic games are important for applications such as self-driving vehicles, where each vehicle can only observe its own local environment, make estimates, and so on, but cannot see what other vehicles are observing. Particularly, if there is occlusion, then an agent cannot see things that are behind other vehicles. This results in very limited observability.

Or if you can think about strategic games like poker and card games, where there's hidden information. I have my own cards in my hand that you don't get to see. You only get to see what's public on the table, basically. So, there's public information and there's private information. I have my own cards in my hand that you don't get to see.

You only get to see what's public on the table, basically. So, there's public information and there's private information, right? This partial visibility is very important to represent in these cases. Alright, so let's look at this graph again as an example. A partially observable stochastic game is defined almost in the same way as a stochastic game.

You see all the same elements here, except there are now two new things, which are highlighted in orange. Every agent now also has an observation set. These are the things that can be observed: the observation vectors. Additionally, there is an observation function that defines the probabilities with which you get to observe these different elements in a particular state, and so on. So, that's defined here. For every agent \(i\), we define an additional observation set and an observation function that provides probabilities for observing these different observations. For example, in a self-driving scenario, you might have noisy observations. If I have estimates about the locations of the other vehicles, these estimates might be noisy; in other words, they might not be completely accurate and could be slightly off the mark. This noisy element is represented by this probability distribution.

It could be, for example, Gaussian covariance, and then your estimate isn't exactly centered. Alternatively, you might have observations where the full state is defined by everyone's locations and all the apples and agents, similar to level-based foraging. However, the observation might only include the location for one agent—in this case, ourselves—and perhaps only the locations of the apples that are within a vicinity, such as a three-by-three square. I'm just making up examples to illustrate what partial visibility could be, and you can represent all of that here.

Here, this is the same graph that we saw earlier. I'm just showing this dashed line here because it represents that the agents do not directly see the state anymore. Instead, they receive an observation that depends on the state but does not tell them exactly what the state is. That's somewhat difficult to illustrate on the graph, so we just use the dashed line to explain what that's supposed to represent. Again, the process is very similar to before. We start with an initial state, and then every agent receives an observation. There will be an initial observation, and subsequently, there will be observations sampled using the observation probabilities. These probabilities depend on the state we are in and the previous joint action. The agents may not observe the actions of the other agents; they may be completely unobserved.

And then every agent chooses an action \( a_i \) at the particular time \( t \), which is based on its policy \( \pi_i \). However, now the policy is conditioned on the full history of observations that the agent has made from time step zero to the current time step. The agents then pick their actions, resulting in a new joint action. This joint action, in turn, affects the state of the environment just as it did before. Additionally, just like it was before, every agent receives a reward as well.

And this is done until we reach a terminal state or we have reached a maximum number of time steps. So, the only thing that's new here is these two steps where the observations are sampled, and then the agents get to condition on the sequence of observations that they observed in the past. But other than that, it's the same. Okay, here's again an example, but I think the colors are not ideal again. I think you can see this on the slide, but not here.

To create a shaded area that illustrates what is visible and what is not. If you look at the slides, you can see a gray area here. This represents that this agent can only see this apple and this apple, but not the apples outside the visibility region. Similarly, this agent can only observe that apple, but not the others. In this case, we are modeling limited visibility.

And this is also important because what they see really is what they need to be doing. We're going to talk about this in just a second here. Yes, in fact, here. There’s an important point to note: something that didn't exist in the fully observable case is that the limited observations we make mean we do not know the actual true state of the environment. This indicates that it may not be optimal to make choices based solely on the current state we are in.

What we really need to do is make an estimate of the real state based on the observations we've received over time. So, what do I mean by that? Let's say we're in this particular situation that we're seeing here. We'll focus only on the agent on the left. It has an observability region, which you cannot see, but it is supposed to be gray.

You can see this in the slides if you look on your computer. The optimal action for this agent is to go left because its level is level one. The other apples that it sees are level two, which don't make sense. The closest level one apple is the one on the left.

But it doesn't know that the apple is there because it's not in the visibility region, so it doesn't know what the optimal action is. If it only conditions on what it's seeing right now, it wouldn't know what to do. At the very least, it would know that it's not supposed to be collecting these apples here. However, if it did move around this area previously and saw this level one apple on the left, for instance, down here, it should have some sort of memory functionality to remember that, in fact, there is an apple here that it saw previously. Right? So it needs to remember that, okay, there is this thing here.

Maybe I need to move from the left, even though I don't see this right now, because I previously saw that there was something there. The mathematical vehicle to do this is called the belief state. A belief state is a distribution over the possible states in the environment, which is referred to as 'b' for belief state. Essentially, this is computed using something called Bayesian theory or Bayes' Law. Hands up if you know about Bayesian theory!

Bayesian probabilities. Surprisingly, only a small percentage of people—less than half—are familiar with it. It's one of the most important concepts to understand when it comes to machine learning: Bayesian probability. If you don't know about Bayesian statistics or Bayesian probability, you should learn about it today. Essentially, go home and study Bayesian probability.

You need to know about this because a lot of the mathematical background in machine learning is based on Bayesian theory. Thomas Bayes and probability are essential concepts in this field. Thomas Bayes himself has an interesting background; he was actually a reverend, a priest.

And he apparently invented Bayesian calculus to prove the existence of God. I don't know how well that worked out for him, but it turns out it worked really well for machine learning. Thomas Bayes was also at Edinburgh, specifically at Edinburgh University, where he actually studied medicine. Anyway, that's described in the book, but basically, it looks like this.

Let's say, for simplicity, there's just a single agent to keep the mathematics a bit easier. There are no multiple agents, just one single agent, but there is still partial observability. Initially, let's assume we know the distribution of states—magically, we just know that. So, that's our initial belief state. Then, we proceed with the update process.

After taking a particular action, we make a specific observation. Assuming that we know the observation probabilities and the state transition probabilities, we can apply this update. Our Bayesian posterior over the state space will be updated to be proportional to this calculation, which essentially sums over all the states we could be in and multiplies by the probability of the successful state when observing that state, as well as the probability of observing that particular observation in that set. This is represented by the proportional symbol, which indicates that you can convert this into an equation by adding a denominator that accounts for all successor states. This process is based on probability and is quite straightforward.

But the reason I'm showing this here is because this type of inference is typically infeasible, not just in multi-agent reinforcement learning, but also in partially observable Markov decision processes (POMDPs). You mentioned POMDPs earlier. This type of computation is a standard process in POMDPs, but no one does it because it's not feasible computationally. In practice, you would lose other kinds of inference techniques. For example, deep learning can be trained to infer states implicitly through sequences of observations.

That's why deep learning is also useful for these kinds of applications. The other reason we do not use this in reinforcement learning, including in multi-agent learning, is that we do not actually know these ingredients. We don't know the state transition probabilities or the observation probabilities. Hence, we cannot compute this analytically.

But I wanted to show you this because it is important. In any case where you have partial observability, you need to maintain some sort of memory functionality in order to recover. Information that you observed in the past may be relevant for making optimal decisions. In Partially Observable Markov Decision Processes (POMDPs), which is the version when there's only a single agent, the optimal policy is actually defined over the belief states, not over individual observations. This is called a sufficient statistic; it summarizes all the information you observed in the past. However, practically in reinforcement learning, we cannot achieve this because we do not know these pieces of information. Even if we did know these things, to be honest, we would still not be able to compute these marginals as it might involve billions of states, making it impossible to sum over them. So, those were the models we discussed. We started with normal form games, which involve one interaction but with multiple agents in just one state. Then we moved on to repeated normal form games, where we repeat the same scenario over and over again. The next general class is stochastic games.

We now have \( m \) agents and \( n \) states, which includes Markov Decision Processes (MDPs) and normal-form games. We also looked at partially observable stochastic games, which is the case where we know that agents have individual observations. In my view, those are probably the most important models you need to know about if you want to learn about multi-agent reinforcement learning. That's all we cover in the book.

In the book, these things are described in a good amount of detail. For the rest of this lecture, before we wrap up, I just want to talk a little bit more about some communication and assumptions, because I think a lot of people are interested in this. First, communication. In many cases, and applications, you can imagine that the agents can actually talk with each other. They can send messages; they can say, “uh,” or “um.” They can send symbols like "abc," and these symbols can mean something. Alternatively, they can send proper messages as text. If these agents are equipped with some sort of LLM functionality, they can send whole sentences to one another and interpret those. So, we can use these existing games as they are to model these communication actions. The way you can look at this is that communication is just a type of action.

We don't change anything about the model; it's just a type of action. It just happens that this communication action doesn't alter anything in the environment. It can be observed, and there can be noise and corruption, but it doesn't change the physical state of the environment. Because it can be observed, the action, it's similar to communication, right? So they are sending each other these signals.

We can view communication as a type of action that other agents can observe without affecting the state of the environment. The cool thing about multi-agent reinforcement learning is that the agents can actually learn to attach meaning to these communication messages. One of the fascinating aspects of multi-agent reinforcement learning is this idea that the agents learn together to develop a language. They create a specific way of attaching meaning to different symbols that makes sense for them, even if it doesn't make sense to us. However, this system of meaning might be quite effective for them in terms of solving the task. So, how do we accomplish this?

For example, we described this in the book. You can say that the action is just a slightly more complex composition of two components. One is a physical action, denoted as x, and the other is a message, represented as m. Essentially, it's just a concatenation of these two elements. However, it doesn't alter anything about the models. In m, there could be multiple messages, allowing you to choose from different words, letters, symbols, and so on.

Every action is essentially a combination of a physical action and a communication action. Agents observe the current state, as they did before, in a stochastic game. If they observe each other's actions, that includes the communication action; they can perceive the message from the other action sent. In a partially observable stochastic game, it is modeled in a similar way.

We can say that the observation now includes some kind of information about the state, but it can also include the messages, in this case from the other agents. Because of the observation probabilities, we can even model things like noisy messages. If there is a noisy communication channel or a loss of messages, we can model that these things could be empty as well, under certain probabilities. Therefore, you can be quite creative with how you model this. That's all I wanted to say about communication.

The last couple of slides, and then we finish for today, are about assumptions in games because I think it's important to be aware of them. First of all, a lot of this work comes from game theory. Game theory is much older than reinforcement learning, and it has its own conventions and assumptions. Some of these assumptions make sense, while others may not make as much sense, but it's crucial to be aware of them. If we do not share the same assumptions when we communicate, we may not be discussing the same concepts. The first thing we need to clarify when we talk with each other is what the actual settings and assumptions are. This is very important. In game theory, we typically assume that all agents know all the components of the game.

It's called complete knowledge, a default assumption in game theory. For example, in a stochastic game, players know all the action spaces, all the state spaces, the probabilities of the state transitions, and so on. They understand the complete definition of the stochastic game, including the reward functions as well. They even know what your preferences are and what your reward function is.

So, by extension, I know what rewards you're getting. Okay. The reward function is such that, by extension, I know what rewards you're receiving. That's the typical assumption in game three.

But now let's look at the Marl assumptions. In Marl, we typically have limited knowledge. This is similar to what I mentioned earlier regarding single-agent error compared to dynamic programming, which is what we assume in temporal difference learning. Most commonly, we do not assume that we have knowledge of the transition function, and we also typically do not have knowledge of the other agent's reward functions.

We may, at best, know our own reward function; however, it is also possible that we may not even know our own reward function. We may only experience our rewards as we try things in the environment. Additionally, certain agents may know things about the game that we do not. Knowledge can be mutual, meaning everyone knows everyone else's reward functions, or it might be asymmetric; you may only know your own reward function while being unaware of mine. There may also be aspects of the state space that you understand, but I do not, and so on.

So, you know, in realistic applications, it could be that the agents have different domain knowledge. This also relates back to the earlier question. We typically assume that the agents are fixed in number, but there is research, including from our lab, where we have this open multi-agent system. In this system, there can be a dynamic number of agents; they can come and go.

And lastly, I think this is the last slide. This is the dictionary that I showed you earlier. I think this is quite useful.

When we first announced the book more than a year ago, one of the initial reactions on Twitter was surprising. People began to copy the dictionary and share it extensively with their friends. It received a lot of attention. For us, it was unexpected that this became one of the most significant takeaways for some individuals, as there seemed to be a frustration regarding the misalignment in language. Finally, here was a table that brought it all together. Overall, it is quite straightforward.

In reinforcement learning, we often use the term "environment." In Game Theory, we refer to it as a "game." "Game" is also the term we used previously. An agent and a player are essentially the same thing; in reinforcement learning, we call it a "reward," while in game theory, it is typically referred to as "payoff" or "utility." Then we have "policy," which is often called "strategy." A deterministic policy is what we would call it, whereas they would refer to it as a "pure strategy." So, you see there are different terms, but they all mean the same thing. We just need to be aware of these differences, and then we can communicate effectively. That's all we really need to do. However, in the book and the lectures, we will be sticking with the terminology from reinforcement learning, because ultimately, that is what we care about and what we will focus on.

Okay, I think that's it. So we covered the game models. We discussed some basic concepts about communication and assumptions in games. Tomorrow, we will be moving into solution concepts for games. What does it even mean to solve these games?

We haven't even talked about this, right? I haven't mentioned what it means to solve any of these games yet. In fact, there are many different solution concepts.

And the other thing we're going to cover, I think, tomorrow as well, is some basic, very first ideas for how to do reinforcement learning in these kinds of games. That's what we'll be doing tomorrow. The last thing I want to say is to take your time to go through the book sections and the slides. If you have time, you could already look at the chapter for tomorrow if you want to make it a bit easier for yourself. Starting later today, I'll be posting the link to the recording exercises on Slack.

This will direct you to a README file that provides straightforward, step-by-step instructions on how to run some of these algorithms, particularly in the context of level-based foraging. This is optional, and you can complete it at your own pace; it shouldn't take more than one or two hours. One thing I want to mention is that I can actually show you the link I have. It's available here. I will be posting this link, which provides exercises for the Barcelona Summer School, starting from tomorrow. Day one, in terms of the coding exercises, is scheduled for tomorrow. The document outlines all the necessary steps you can follow, including instructions on how to use the code and run these algorithms. Additionally, there are some very basic exercises that will help you evaluate these algorithms and obtain some initial results.

So it's really not a lot, but it's meant to give you something to start with, to play with, right? Then you can go from there and just experiment basically, doing more things on your own. Yes, with that, I think let's wrap up for today and check if there are any more questions. Yes, in these examples, we essentially had an environment with discrete time steps. Will we be looking at continuous time and asynchronous actions, or do we always assume that it can be approximated by discrete steps and maybe some default actions? That's a very good question. The vast majority of the literature is like that.

Discrete time steps that you can implement in some sense. Personally, I'm only aware of very little research in reinforcement learning that explores the idea of continuity, where there isn't a discrete delta t, basically. Just last year, I gave a talk in Canada at the University of Alberta, and Rich Sutton, one of the grandfathers of reinforcement learning, authored a book in this area. They had one paper on this topic, and that was the first paper I ever encountered.

It tells me that there is probably very little. But then, to be honest, in practice, it's not really a big deal. In the applications we are building in robotics and so on, there are ways to handle this. One option is to have a very high frequency in the action space. For instance, in self-driving, you can have a very high frequency in the action space.

You're looking at a minimum of 10 hertz, which means 10 decisions per second. This gives you 100 milliseconds between each decision, which is quite low already. Typically, 20 or 30 hertz would be better. What I want to emphasize is that if you execute, for example, at 10 hertz certain times a second, it means that the information you collect between these delta times can still be accumulated in a filter.

It's called a filter, basically, that provides a status estimate. You're losing information in between, but the system can still maintain this information. If the frequency is high enough—like 10, 20, or even 100 hertz—then you're so close to real time that it almost doesn't matter anymore. For example, it has been found that professional human players are extremely skilled at their jobs, such as professional human players in StarCraft.

They are, I think, working with a framework of typically a frame rate between 30 and 60 frames per second. So that's what humans do. Normally speaking, they operate in real time, not in discrete time steps. The brain is wired in a way that there isn't more capacity than that. If robots can operate at even 100 hertz, then that's already more than what humans do.

And then, you know, looking at other examples, high-frequency trading in financial systems requires much more than that, right? So 10 hertz would not be enough for them. Okay, but I hope that answers the question. Also, in these high-frequency cases, I guess we don't need to actually have active actions from all possible agents. We can include some no-ops, for instance, to fill the joint action.

Oh, yeah, that's interesting. So your question now is, if there is a delta t, but in reality, these agents might not always be making the decision exactly at this time step. It could be that for one agent, it’s time to make a decision, but the other agents are not there yet, or whatever, right? Then, yeah, how do you deal with that? I think there are a few ways of addressing that.

You can say there could be a no-op, which is what you just mentioned, or there are protocols where we always wait for everyone to be ready to make a decision. In such cases, there needs to be a central coordinator who announces that it's decision time and then broadcasts this to everyone, waiting for all parties to make their decisions. That's one protocol to handle this situation. Another way to approach this is that if I do not have any components in my system that explicitly rely on having information about your actions, and if everything in the system that I can observe is purely based on my sensing network—rather than being dependent on knowing your actions—then I don't care when you make a decision.

I just get to see whatever I see in my camera, for example. So it's different in that sense. It's only important if your particular algorithm has a discrete component that explicitly represents the other person's actions, which probably is not a good idea for deployment anyway.

But there are many more ideas, and they can be quite creative. So, you know, we can discuss that further. Thank you. This is an online question. They are asking, when you mention communication with your agents, how do we currently accomplish this in the real world, specifically in multi-agent deep reinforcement learning and multi-robot warehouse systems?

Is there any communication protocol? How is it accomplished? How advanced are we in terms of learning communication protocols in the real world? Okay, so we don't actually do that.

In our warehousing application, we don't learn communication protocols in that way. There's a different system where a manager agent learns to dynamically allocate tasks to the worker agents, which consist of both humans and robots. The robots, in turn, learn to perform those actions. So, they are learning simultaneously: the manager learns how to assign tasks, while the worker agents learn how to execute them. However, there is no communication in the sense of verbal conversation.

I think this research in learning communication protocols is still not very advanced, to be honest. That's because it's not easy. Learning to attach meaning to symbols is an entire research area, even outside of multi-agent reinforcement learning. We have collaborated with individuals who are not focused on reinforcement learning or machine learning but study languages. They engage in what are called language and reference games, which essentially examine how agents attach meaning to symbols over time.

But it's not really about reinforcement learning or solving tasks. It's purely about the idea of merging a language together. Even there, I can see that it's still a very difficult process to converge robustly to a shared language. There's a lot of complexity involved, and there are many issues that arise when you observe things locally.

I think that if there are PhDs here and you are really interested in communication, particularly in multi-agent reinforcement learning, it’s probably a significant opportunity space for you. I have seen some papers, and there are still papers coming out today that attempt to develop multi-agent reinforcement learning for communication. However, every time I see these papers, I think they are not very scalable or advanced yet. Therefore, I believe there is likely a lot of opportunity for you if you are interested in this area, including those of you online. There is another question about whether multi-agent reinforcement learning (MARL) is currently applicable in the stock market prediction space, given that there are too many agents and it is a very dynamic environment for it to have a substantial application. I’m not really a finance expert, but I am aware of some companies that are trying to do this and I have spoken with them as well. My short answer is that I don't know—I haven’t really explored this application in depth. However, I can already identify some problems with it.

One problem with trading is that there could be situations where you have many agents—hundreds of them. However, a lot of the algorithms currently used in multi-agent reinforcement learning are not designed to scale to hundreds of agents; they typically scale to only tens of agents. I believe there is still a lot of work to be done in terms of scaling these algorithms to accommodate hundreds of agents.

I think there's still a lot of work to be done in terms of scaling to hundreds of agents. It’s not clear yet what the right philosophy is to achieve that. Mean field games make certain abstractions to facilitate scalability, but they have other limitations as a consequence. Although I'm not very familiar with this application, I would expect that there are certain limitations in multi-agent reinforcement learning regarding scaling to these applications. Do you have any more questions about this? Yes. Is it always a kind of decentralized approach with agents, or can we also consider a central agent that receives communication from other agents and then commands the different agents? Yes, that's a possibility.

So tomorrow, we're going to be talking about the idea of a central learner, which is like this. It's similar to what I mentioned earlier when I provided the example in level-based foraging and how we were going to decompose the problem. If we have a centralized agent, we encounter an exponential action space; 216 was the example, right? That would be very hard to manage, so centralized learners are typically not feasible for that reason. However, there are ideas in between. For example, in the warehousing application, we have something akin to a centralized agent, which is the manager agent. The manager agent is responsible for allocating tasks to the individual worker agents. It's like a central component that coordinates them: “You do this, you do that, you do this,” and I’m trying to coordinate you.

But I'm not actually telling them exactly how to do this. They still have to learn how to do these things, which basically makes it feasible. However, if I had a manager agent that instructed everyone exactly—saying, "You do this, and you do that, and this is exactly how you do everything"—then we would encounter the same problem of feasibility. It would lead to an overwhelmingly large action space. An example of a more balanced approach would involve decentralized worker agents, while still having a high-level centralized entity that possesses more information and makes decisions at a higher level, thereby keeping the process feasible.

So, you can see that multi-agent reinforcement learning really gives you a lot of flexibility in terms of shaping these configurations of agents in their action spaces. Whatever configuration you come up with, you can still use existing multi-agent reinforcement learning algorithms to optimize the policies for these different setups, which I think is really cool. Another question related to this: for example, if we assume we have infinite compute and everything else, is there any study that shows that a completely decentralized option can achieve the same efficiency as a centralized one? Even without that limit case, my experience is that decentralized cases tend to be more efficient than centralized cases. This is because they face a much smaller space, but they do have other problems. For example, they might exhibit chaotic behavior, which means they don't converge to an interesting fixed point. This will not be the case with a centralized approach if it’s based on a well-defined single-agent reinforcement learning algorithm like Q-learning. If those assumptions are upheld, we know that it's guaranteed to converge to the optimal Q function over the joint action space. However, because there's a very large search space—216 actions in this example and a time step of 260—there is a huge branching factor, making it very inefficient and very slow to achieve optimality. On the other hand, multiple decentralized learners typically learn much faster to fill in the values in these much smaller value functions. However, they may not coordinate well, and that introduces a different kind of problem. In this sense, if you're asking about efficiency, I would expect that practically, decentralized approaches would be more efficient, but they might face challenges in converging to the actual optimal solution. Does that make sense? Okay, thank you. I have another question here. I was going to ask something similar regarding the decentralized and centralized approaches. I’ve read a lot in the literature about the concept of centralized training and decentralized operation.

I don't know if this is the most popular approach or something like that. You mentioned that you can train in a decentralized manner. If so, it's kind of a question within a question. I'm not sure if you covered this in the earlier part of the lecture since I arrived a little late. What would be the difference with swarm intelligence?

And if swarm intelligence is like a kind of research that is falling behind because of multi-agent reinforcement learning, or is it imperturbable? Yeah, okay. A lot of questions. So, I think swarm intelligence; I'm not so familiar with their latest techniques, but I know some high-level outlines. In swarm literature, we typically look at hundreds or thousands of agents.

Due to the need to scale significantly to accommodate many agents, we typically do not have the capacity to run individual reinforcement learning processes on hundreds or thousands of agents in that manner. Instead, researchers often employ highly simplified, usually heuristics-based approaches that are hardcoded into FPGAs, which can be executed locally on these systems. Therefore, these methods are usually not learning-based; if they are, they do not scale to such a large number of agents. This is consistent with the papers I have reviewed, which indicate that they do not generally utilize multi-agent reinforcement learning. Rather, they tend to use much simpler approaches to achieve the necessary scaling.

That's typically the trade-off, right? Here, we still have quite a bit of computation that needs to be done to implement this type of trade-off. So even though I'm not part of this community, I do come across papers sometimes. As far as I'm aware, this community tends to use highly simplified approaches just to achieve scalability. With these simplified approaches, they want to see if they can still observe interesting emergent behavior when everyone operates in this manner.

For example, one subarea of literature is called flocking, which means that if you have hundreds of agents, like drones, and you can insert some agents that you can control, you can manipulate the whole flock to perform certain maneuvers. This is typically done using very simple approaches. So that was the last question, I think. The first question was about centralized training and decentralized execution. Yes, I'll be talking about this not tomorrow, but the day after tomorrow. It's a very important paradigm, as it aims to combine the benefits of both ideas.

Centralized training means that we have an opportunity to train everything in one place. For example, we can simulate the environment, control all the information, and facilitate complete communication without limitations imposed by the real world. We can train them centrally, which may provide a better environment for them to learn useful things together, as they can share a lot of information. However, we are training models that can be executed completely independently after training. So, centralized training with decentralized execution is where the name comes from. This approach is useful because it often allows us to share a great deal of information during training.

That could be because everything is trained in one place. We are not constrained by hard physical limitations, for example, if everyone is in the same lab. However, if we can train the model so that post-training, we can then execute it locally, that might satisfy the requirements of the actual application. One direct example I can give you is something like self-driving technology. You can imagine training self-driving policies in a large simulator; CARLA is one of the most popular simulators for that purpose.

And you can train policies for tens of vehicles. Because they are all trained in simulation, they can share a lot of information, which could be useful. However, in reality, they cannot share all this information. Still, we can train those policies so that they can be executed in a fully localized way after training.

And that's kind of the interesting aspect, like the beauty of centralized training with decentralized execution. You're trying to do it in a way that can be executed locally. But what's even nicer, in theory, would be decentralized training and decentralized execution, right? Because then you can do everything on the actual deployed system. You do not have to share privileged information during training. It turns out that before the deep learning phase of multi-agent reinforcement learning, there was work that emerged in the early nineties that focused on decentralized training and decentralized execution. They did not have this concept of centralized training and decentralized execution.

This only came later when the deep learning concepts emerged. The early algorithms discussed in Chapter Six of the book contained many theoretical claims. They were designed for decentralized training, but they do not scale to the interesting applications that we care about. This relates back to the question we had earlier about centralized and decentralized efficiency. There are many early algorithms in multi-agent reinforcement learning that have strong guarantees in the limit for learning particular solutions, such as a Nash equilibrium.

But they typically do not make claims about finite-time efficiency. It's only ever in the limit. In fact, the same applies to single-agent reinforcement learning. Almost all the literature only makes claims about limit performance, but not about finite-time bounds, essentially. So, it's challenging.

This question you asked, when I gave you this answer, was just my empirical response. However, theoretically, there's very little in terms of finite time bounds that would actually compare the efficiency of these learning processes. Another question arises: if it is decentralized training, would it achieve the same level of interactions as centralized training? That's one of the goals of multi-agent reinforcement learning, right? To have interactions between the agents.

Yes. What do you mean by the same level of interaction? Essentially, what I’m asking is if they are decentralized and decoupled, how do they interact with each other? How do they account for the action space of the other?

Agents can still do that, right? Even in a decentralized case, they can represent other agents and choose actions. They don't have to, but they could. I think maybe this isn't the right question. The real question is whether they can still learn the same solution concepts as centralized approaches, because that's what matters in the end. We want to learn an optimal rule, for example, which I'll tell you about tomorrow. It doesn't matter how interactive that is or whatever that concept even means. The only thing we care about is that we learn a well-defined solution that satisfies certain properties. For example, in a Nash equilibrium, it means that everyone's policy is mutually optimal with respect to the other policies.

So, that's a hard, concrete mathematical set of properties that we want to satisfy. The real question is: do the decentralized learners provide us with a guarantee to learn these concepts? Yes, there are many algorithms that have these kinds of guarantees, except for the more recent deep learning-based approaches, where most algorithms lack hard guarantees due to the empirical nature of this work and the nonlinearities in functional approximation, which makes any theoretical analysis difficult. Does that make sense? I'm trying to shape your question to focus more on the end point of the learning.

I think your question was more about the extent of interaction during the learning process. However, what really matters is the solution they learn. The solution essentially defines what we care about, and it is also a result of the training process. Yes, that's correct. But during training, anything can happen, right?

I don't really care what they do in training. What I care about is that they give me this thing at the end, which is, for example, a Nash equilibrium. And, you know, different algorithms may do it in different ways, but as long as they give me the correct answer, which is a Nash equilibrium, for example, then, you know, that's what I wanted. Whether it's centralized or decentralized training at that point doesn't matter anymore. I just have my Nash equilibrium then, basically.

That's the result of the learning I wanted to achieve. I think this will become clearer tomorrow when we discuss the solution concepts, which we haven't talked about today. Thanks to everyone. Are there any more questions, or should we wrap up? I think we're probably good to wrap up. Is there anything online we'd like to address quickly? One person is asking if you could please elaborate further on the limitations of mean field games. Oh, okay, interesting. It seems someone online is knowledgeable about this. Mean field games, as the name suggests, take population averages into account and reason about the policies based on what the population average is doing. This means I no longer care about differences in policies between individual members of the population, allowing for significant scaling. However, the drawback is that I have a homogeneous population where everyone uses basically the same policy. In many applications, that's not what I want. I want individuals to have different policies because teamwork necessitates that they have varied roles in the team; they complement each other's actions and so on, instead of reasoning over population averages and aggregates. That's my short answer.

In a nutshell, what are the different types of multi-agent systems, excluding swarm and MARL, that we have already discussed? There are various types of multi-agent systems. However, I'm not sure I understand the question.

There are multi-agent systems where there is always an environment and multiple agents. These agents have different observability, report functions, actions, and so on. I'm not sure what is meant by "types." Different types of algorithms, perhaps? Okay, I see.

Yeah, I guess there are different categories of algorithms. For example, tomorrow we're going to be learning about independent learning and central learning. After that, we're going to be learning about things like decentralized training with decentralized execution. These are broader categories, and many algorithms exist in these areas. Additionally, you can further refine these categorizations.

Different algorithms have different assumptions regarding what they can observe and what they do not need to observe, as well as what they need to know about the game and what they do not need to know. They also have varying assumptions about the rewards. Do we have common rewards or zero-sum rewards, and so on? Therefore, the categorizations that I showed you earlier, such as the different classes of games, also apply to the algorithms in some sense. This is because different algorithms are sometimes designed for specific classes of games, like zero-sum games and common reward games. I’m not sure if that answers your question, but let’s say that’s my response for now.

Like zero-sum games and common reward games, and so on. I guess I'm not sure if that was the question, but let's say that's my answer for now. Okay. All right. Then I guess we're good to wrap up, right?

One more question there, okay. It makes learning more efficient when we have a huge action space. I would say it can, yes. Whenever it's not chaotic and an optimal solution is possible to find. I'm guessing maybe it also has to do with the return design or the way we can decouple that as well?

Sure. Because maybe in one single reinforcement learning scenario, we have a Pareto front we want to optimize, and we have to design a very complex reward function. I don't know if multi-agent reinforcement learning can ease that by having multiple agents. Yes. So, I think the things you just mentioned will be discussed tomorrow when we talk about solution concepts.

So maybe the answer is two points. For this right here, I think everyone's already a little bit tired. Let's bring the question back up tomorrow because we have the background to talk about this kind of question. Okay, so we'll come back to your question tomorrow. Does that sound good? Alright then, thank you everyone, and I'll see you tomorrow.