ReBeL - Combining Deep Reinforcement Learning and Search for Imperfect-Information Games (Explained)
deep learning machine learning arxiv explained neural networks ai artificial intelligence paper poker deep neural networks facebook facebook ai rebel holdem texas holdem rock paper scissors liars dice liar dice self play nash equilibrium alpha go alphazero zero sum policy cfr counterfactual regret minimization tree search monte carlo tree search mcts public belief state infostate value function supergradient strategy actor critic imperfect information
#ai #technology #poker

This paper does for Poker what AlphaZero has done for Chess & Go. The combination of Self-Play Reinforcement Learning and Tree Search has had tremendous success in perfect-information games, but transferring such techniques to imperfect information games is a hard problem. Not only does ReBeL solve this problem, but it provably converges to a Nash Equilibrium and delivers a superhuman Heads Up No-Limit Hold'em bot with very little domain knowledge.

OUTLINE:
0:00 - Intro & Overview
3:20 - Rock, Paper, and Double Scissor
10:00 - AlphaZero Tree Search
18:30 - Notation Setup: Infostates & Nash Equilibria
31:45 - One Card Poker: Introducing Belief Representations
45:00 - Solving Games in Belief Representation
55:20 - The ReBeL Algorithm
1:04:00 - Theory & Experiment Results
1:07:00 - Broader Impact
1:10:20 - High-Level Summary

Paper: https://arxiv.org/abs/2007.13544
Code: https://github.com/facebookresearch/rebel
Blog: https://ai.facebook.com/blog/rebel-a-general-game-playing-ai-bot-that-excels-at-poker-and-more/

ERRATA: As someone last video pointed out: This is not the best Poker algorithm, but the best one that uses very little expert knowledge.

Abstract:
The combination of deep reinforcement learning and search at both training and test time is a powerful paradigm that has led to a number of successes in single-agent settings and perfect-information games, best exemplified by AlphaZero. However, prior algorithms of this form cannot cope with imperfect-information games. This paper presents ReBeL, a general framework for self-play reinforcement learning and search that provably converges to a Nash equilibrium in any two-player zero-sum game. In the simpler setting of perfect-information games, ReBeL reduces to an algorithm similar to AlphaZero. Results in two different imperfect-information games show ReBeL converges to an approximate Nash equilibrium. We also show ReBeL achieves superhuman performance in heads-up no-limit Texas hold'em poker, while using far less domain knowledge than any prior poker AI.

Authors: Noam Brown, Anton Bakhtin, Adam Lerer, Qucheng Gong

Links:
YouTube: https://www.youtube.com/c/yannickilcher
Twitter: https://twitter.com/ykilcher
Discord: https://discord.gg/4H8xxDF
BitChute: https://www.bitchute.com/channel/yannic-kilcher
Minds: https://www.minds.com/ykilcher
Parler: https://parler.com/profile/YannicKilcher
LinkedIn: https://www.linkedin.com/in/yannic-kilcher-488534136/

If you want to support me, the best thing to do is to share out the content :)

If you want to support me financially (completely optional and voluntary, but a lot of people have asked for this):
SubscribeStar: https://www.subscribestar.com/yannickilcher
Patreon: https://www.patreon.com/yannickilcher
Bitcoin (BTC): bc1q49lsw3q325tr58ygf8sudx2dqfguclvngvy2cq
Ethereum (ETH): 0x7ad3513E3B8f66799f507Aa7874b1B0eBC7F85e2
Litecoin (LTC): LQW2TRyKYetVC8WjFkhpPhtpbDM4Vw7r9m
Monero (XMR): 4ACL8AGrEo5hAir8A9CeVrW8pEauWvnp1WnSDZxW7tziCDLhZAGsgzhRQABDnFy8yuM9fWJDviJPHKRjV4FWt19CJZN9D4n
 Hi there. Take a look at this variant of the game Rock Paper Scissors. It's like usual Rock Paper Scissors, except with the added complexity that when either player chooses scissors, then the rewards and the losses are doubled. So for example, you see right here, player one chooses rock and player two chooses scissors. So both the reward for player one and the loss for player two are double the size. Now, you might know that in original Rock Paper Scissors, the optimal strategy is to play one third of each of the three choices at any time. So you basically take a fair three sided coin dice. Does that exist? I'm not sure. And you throw it and whatever side is up, that's what you play. However, here, since one of the options is different, the sort of optimal strategy shifts. And interestingly, it shifts as follows. What you want to do is you want to play rock and paper, both with a 0.4 probability and you want to play scissors with only 0.2 probability. That is pretty interesting. You might intuitively conclude that you want to go more where there are more rewards to be had. But of course, also you lose more. So you might also conclude, well, it doesn't make a difference ultimately. But why does the why does the sort of optimal strategy shift such that you want to decrease your likelihood of playing scissors? Let's just quickly analyze this game before we jump into the paper, because this game is sort of a microcosm of what the paper of today is about. So the paper of today is called Combining Deep Reinforcement Learning and Search for Imperfect Information Games by Noam Brown, Anton Bakhtin, Adam Lehrer and Qi Chenggong of Facebook AI Research. So this paper brings basically what AlphaGo or AlphaZero has done for perfect information games. It brings this to the domain of imperfect information games. And we'll see what the difficulties are in this and what can be done to solve it. And not only do they have an algorithm, but they have interesting theoretical results that under some conditions, namely under the condition that neural networks do something useful, will actually converge to Nash equilibrium in these games. So that is pretty cool. So practical and theoretical paper right here. As always, if you like content like this, don't hesitate to share it out and tell me what you think in the comments. This is not my field, so I might get quite a bit of stuff wrong right here. Also, if you haven't seen the Negranu Poker Challenge, so I think it's the last video I did, be sure to check that out just to see how you have to think about situations like this. All right, let's get back to this rock, paper, scissors example right here. Interestingly to note is that these dashed lines here means that player two cannot decide which of these states they're in. So player two doesn't know what states are in. For player two, this is all basically the same state. It would be really easy, right? If player one plays first and then player two sees what player one does, and then they just act like they always win. However, player two doesn't, so they have to sort of decide what to do, independent of which state they're in. Especially this is a symmetric game, right? This is a two player game, because it has two players. It's zero sum, because whenever one player wins a reward, the other player loses the same reward. And it is also, that makes it symmetric. So both players play at the same time, though that is not necessary in general. But here it's the case. All right, so this means in this particular case, whatever strategy player one has, player two must have as well. So we'll just do the analysis for player one. So let's say you deviate from this optimal strategy, right? We claim that this here is the optimal strategy, playing 20% of scissors. Let's say player one doesn't believe it. Player one deviates from it and says, nah, there is so much reward there. I'm going to get some more of that. So they up this, right? They up this to like, let's say, point, I don't know, point three, three, like doing the classic one third or even higher, right? They up this, go more scissors, okay? And they probably want to take this mass because they have to take it from somewhere. They probably want to take this from rock and paper. Let's say they just take it equally from rock and paper towards scissors to up the, to up the probability that they play scissors. So from paper and from rock, they go towards scissors. Now, player two observes this, right? They can just play against player one for a while. Or what we're going to assume is that everyone announces their strategy publicly. It's the same thing. You can just observe someone for a while or they can just announce their strategy. It's, we'll treat this equally. So player two observes player one playing scissors too often. So player two knows they are very often in this situation right here in this right state. They can't directly observe, but they infer I must be very often in this right, right most state where player one chooses scissors. And therefore you see player two's payoffs. It's zero here, minus two here and two here. So they'll say, well, I also have this optimal strategy of point four, point four, point two. What I can do is I can simply, knowing that I'm a lot in this state, I can simply take some mass from paper and put it on rock. So I play rock way more often and I reduce the amount I play paper, right? Scissors doesn't matter, but now I lose two less often and I win two much more often. And player one in turn loses two much more often and wins much less often. So player one wanted to get more reward, but they're sort of being punished by player two for playing this too often. Now you can say, well, player one can do the same thing knowing that player two plays rock too often now. They've taken away mass from paper towards rock. Knowing that player two has taken rock, player one knows that either they're here or they're here, right? And in this case, player one can say, all right, you play rock too often. Obviously, if I play scissors, then I'm going to lose, but I've already decided I want to play scissors much more. So they're trying to make it up right here. So what they can do in this case is they can say, when I play paper, I win one. Instead of if I play rock too, I win zero. So I know player two is playing rock way more often than they should. So I'm going to punish player two by playing paper more often. So let's erase this arrow. Let's say we play scissors. Sorry, we play scissors. No, let's not erase this. We play scissors by moving from rock and we also move from rock to paper. Like we're almost never playing rock. We're just playing scissors more often because that's what we started with. And we're playing also now paper more often. So now we basically do the same thing that player two did to us. We are upping the likelihood of this thing happening and decreasing the likelihood of this thing happening. So now we can say, haha, now I also I play paper more often. Now I also win more often here and you lose more often. But you see, because the rewards are doubled over here, the fact that player two can achieve this is much more meaningful than the fact that player one can achieve this. OK, and that's why player one will be punished harder for deviating here. So that's sort of how you reason about these strategies. So if player one will play this point to too often, they will be punished harder than player two for deviating in response to that. And the same counts for the symmetric part. This is a very important concept right here. Namely, you can see player two strategy depends on player one strategy, even though you could conceptualize this game of player one plays a move and then they play a move, but they don't show it yet. Right. They play a move. They take like a picture of their hands doing rock, paper, scissors, and they just don't show the picture yet. And then player two plays a move. So now we're basically back in. We're in this game where it's sequential in nature. And usually in a sequential game, you can just do a sub game analysis. So you can just say, OK, and do a sub game analysis. But the sub game analysis depends on the strategy of player one because you don't know the situation. This is different than a full information game. And this is illustrated right here. So they say usually what something like AlphaZero does is your game starts here. Right. And then you have two actions to take. You maybe take this action. OK. Now your opponent has two action. Maybe they take this action. All right. And now you have two actions again. Which one do you take? What something like deep Q learning or actor critic learning would do is they would simply put a neural network here. They would look at this state. And they would simply tell you which action to pick. Like this action right here. Sounds good to the neural network. In contrast to that, AlphaZero, if I draw the same situation right here, AlphaZero, what it will do is it will say, well, I could do this or I could do this. If I do the left thing, then I'm going to have my opponent's going to have two options. They could do this or they could do that if they do the left thing again. And so you get the idea. It sort of goes down the tree and it does this over here. Right. Sorry. This should be so it goes down the tree. I'm stupid. And it evaluates. It kind of calculates ahead. It uses its internal simulator to look ahead. And it could technically do this until it reaches the end. And then it would know if it reaches the end state every time here, it wouldn't know. It could simply backwards calculate which one is the best option for me to do right now. However, this game is often very, very deep. So the tree, the depth here is often so deep that you can't solve the whole game. So what Alpha Zero does instead is it says, I'm not going to play until the end. I'm going to play a certain amount ahead. Right. I'm going to think some limited depth ahead. And I know Alpha Zero does this adaptively. But bear with me. I'm going to think some limited depth D ahead. So here in this case, D is equal to two because we think two layers ahead. And then at the end, I'm going to replace everything that comes after with a single value that indicates how good this is for me. OK. So and this thing right here is very hard to get. Of course, if you knew how good anything is for you, then you have solved the game. But Alpha Zero at this point, the neural network comes in. Right. It this is a neural network. It's a black box. So it simply asks for each one of these states. How valuable do you think that is? OK. How valuable do you think that is? OK. And so on. So it asks for each state, the neural network, how valuable that particular node is. And then it does the same backwards calculation. So we've sort of substituted going to the end of the game by the neural network. But it is still more powerful than asking the neural network at the very beginning, like we do here. The power comes from combining the learning. This is this is the learning. And the search. This here is the search. Right. So this is what Alpha Zero does. And this is what this paper does for imperfect information games. So imperfect information games is when you don't know a particular thing about the game at any point. So there is hidden information like in poker. And the problem is right here, if you do the same thing for this game right here and you look from player one's perspective and you say, OK, this game is very deep. Actually, it's just too deep. Right. But let's assume that's too deep for you. And you want to replace. You want to say, OK, I'm just going to look ahead. D equals one. That's all I can afford. I go ahead. And at the end, I'm going to ask my neural network what the value here is. And the neural network will tell you accurately that the value at each of these nodes is zero. So the average value, if you can see right here, the average value of each of these nodes is zero, depending, of course, on how player two acts. But in this case, it's zero. So as player one, this information will not lead you to the correct optimal conclusion, the correct optimal conclusion being this point four point four point two. Player one, like it's indifferent. Any strategy could work here. Right. If there is some regularization, it'll probably come to the point, the one third, one third, one third. So if it means all the values are equal, it might conclude it's probably best if I distribute my actions or something. So you can see the problem right here. And the problem is that this value right here, it depends on the strategy of player one. And this is something that AlphaZero has no concept on. AlphaZero, the value of a node only ever depends on what comes downstream. In imperfect information game, the value of a node also depends on what has happened upstream. So on the strategy of the upstream events. And that is, as I said, that is that is quite important. Also for AlphaZero, once I have evaluated a game tree and determined the value of a node like this, I can evaluate the same game tree again. And the value is going to be the same. But for the same reason, because the value depends on the value of this node right here, depending on upstream. If I change my strategy. So if here I determine either action one or action two with a certain probability, if this search process results in a result that tells me this is how often you should pick action one, and that's different from what I searched with, right, then all of these values down here are going to change. And I can basically search again. So these are the problems of imperfect information games that we're going to tackle. So you see this poker thing is sort of a microcosm. And this was already half of the paper if you understood why exactly searching using kind of a value estimator with this combined with this tree search is a problem in imperfect information games. So let's quickly go through the abstract. Then we're going to have to define a few terms. And then we can go into this algorithm. The algorithm is called Rebel. It's a general framework for self play reinforcement learning and search that provably converges to a Nash equilibrium in any two player zero sum game. It says that in the simpler setting of perfect information games, Rebel reduces to an algorithm similar to Alpha zero. And they say we also show Rebel achieves superhuman performance in heads up, no limit Texas Hold'em poker while using far less domain knowledge than any prior poker AI. So last video, I've had a comment, which is correct, that is not the best Hold'em AI out there, as far as I can tell. However, it is a very performant one that uses very little domain knowledge of poker. So it like Alpha zero removed basically all domain knowledge out of the games it played. This bot right here, I think the domain knowledge is to the extent of it is given a limited set of bet sizes, even though it's kind of no limit Hold'em where you can bet whatever you want. It's given sort of a limited bet, limited size of bet sizes, like half the pot, full pot, two times the pot and so on. In order to make the actions discrete, I think that's just easier for this algorithm. But in any case, the algorithm is applicable pretty much anywhere where you have a two player zero sum in perfect information game or perfect information. OK, so let's shortly go over a little bit of background. So we're going to need some terms right here. The first term we're going to need is what's called a world state. So a world state is the state of the world. I know easy, easy, but it's quite important that to see that in poker, what is the world state? So in heads up, no limit Hold'em, there are your cards, you get two, your opponent gets two cards, right? And then there are board cards like at the end there are five, but maybe there are only three or there are none yet. It depends on the state of the game. So the board cards, you know, this is maybe an ace, a king, an eight. You know your two whole cards, which is maybe an ace and an ace, but you don't know your opponent's cards. We're also going to assume that the actions are always public for the purposes of this video. They don't not necessarily for rebel the algorithm, but for us, let's just say the actions are all public. So the world state is the fixed entire state of the world. So the world state would include the your cards, the public cards and your opponent's cards. So the world state is sort of like a super user can look at all of the cards. That's the world state. No one knows the full world state, but it still exists. What we also need is so there's a concept of actions. There is an action space, which in poker is something like you can bet, you can raise and so on. So these are your classic actions and there is a transition function like in classic reinforcement learning. So the transition function depends on the world state and the action and it gives you the next world state. And after an action, each agent receives a reward that is also a function of the world state and the action. So important to note that this is the reward you receive, but you don't know the you maybe know the function, but you don't know the world state. So you can't explicitly sort of predict your reward. You can maybe predict the distribution. All right. The next concepts are the concepts of observation. Since we are in an imperfect information game, an observation and the world state, these are not the same thing. Like in chess, you need to look at the board and that's all there is. That's all there is to know. So the world state and the observation are the same thing. Here there is the concept of private and public observations. So public observation is like is what everyone knows in each step, whereas private observations are things that are just revealed to you personally. In poker, the private observation is simply your two whole cards and the public observation is the middle cards. So this is the public observation and this is your private observation. So the private observation is different for each player while the public observation is the same. I guess you could model the public observation as simply another player that doesn't get any whole cards. But you know, that's a question of semantics. All right. The observations can also include the actions that happened so far just for completeness. If you like, you can get information about hidden actions and so on. There's lots of mathematical freedom here, but just the concept is you have private observations to each player individually and then public observations. The subscript I here always denotes a individual player while you see there is no such subscript in the public observations. All right. The next concept is a history and a history is pretty much what you think. A history or a trajectory is a finite sequence of legal actions and world states denoted by this. So you can see it's simply the history of world states and actions that happened. Again, no one knows the history fully, but it's still it is still the case. And I know I know you can I don't know quantum mechanics, many worlds theorem, blah, blah, blah. We'll just assume that whatever you don't know these these are fixed cards. They're actually there. They have a value even though no one has looked at them yet. So the world state is is defined even if you don't know it. So the first real interesting concept here is called an info state. OK, so the info state is like the world state or like the history, but it's conditioned on what an individual player knows. OK, the info state also called an action observation history for agent I is a sequence of an agent's observations and actions. So you can see it's very much like a history, except that it doesn't have the world states. So usually there would be the world state here. You said no, there is the observation for player I at each of the time steps. OK, and these observations, they include public and private observations and along with the actions. But we'll say the actions are public anyway. So an info state is basically the history as it looks to player I. OK, that's an info state in our original game. We said that player two can't distinguish between the three nodes. So if you look at the three nodes individually like this node one node two node three, these are three different world states with three different histories. And to player two, they're simply the same info state because all it all player two knows is that player one has taken some action. It doesn't know which action. So the observation that player two has is exactly the same. Therefore, it can't distinguish. So you can see that the info state is sort of the correct abstraction that we're going to look at here in, you know, in turn for if you look for player one, it looks different, even though for player one, it's also three different world states. It is also three different info states, OK, because player one knows which action they have taken. So player one can decide which of these three states player two is in. So player one is to player one. This corresponds to three different info states. So the info states is always conditioned on a player and it is the sort of unit that we'll look at here. All right. So the info state briefly, it includes the observations and actions for a given player. And the observations include the private and the public observations. The unique info state corresponding to a history for agent i is denoted by this. The set of histories that corresponds to some info state is denoted by large H. So as we said, if you have an info state, there are many different histories that could have led to the info state. OK, so there are many different like there may be for player two. It looks like three different histories that could have happened lead to the same info state. OK, that's but any given history determined fully determines the info state. If I tell you what happened, you can give me the info state for each player. You can say, ah, player one played rocks. Therefore, player two is in that info state and player one is in that info state. So that's why there is a unique info state for each history. But there is a set of histories for each info state. So the last last concept from here is a policy. A policy is again what you think it is. So it is something usually it's something that maps from an observation to an action or from a history to an action or from a world state to an action. But here it is a function necessarily that maps from an info state to a probability distribution over actions. So two things important here. The input to the policy is an info state since the players, they can't distinguish between the world states as long as they correspond to the same info state. Therefore, their policy necessarily must be taking an info state as an input. So player two's policy cannot depend on what player one did because it can't distinguish. It can depend on the strategy of player one, but not on the concrete action. The second thing is that we map to a probability distribution over actions. This is usually the case in in RL if you frame it as a general principle. However, here it's going to be quite important that this is always a probability distribution. Very often in these games, your strategy is probabilistic. So there is no single best move in rock, paper, scissors. But the best thing to do, the best strategy is to play each move with a one third probability or the modified version at the beginning. But it's important to see that a policy will output a probability distribution. And I will also call this the strategy of a player. So the strategy is going to be the policy. And I like to call it a strategy because it's sort of it's a kind of a plan what you would do in each situation. And we're going to see that that is going to be a central theme lifting in solving these games right here using rebel. So policy profile is simply a tuple of policies. So it's simply the policies of all players. That's the policy profile. If you combine the policy profile with some with some info state or some history, you can calculate the expected value. So the expected value for a given history, given that the players play policy pro players play policy profile pie. So this is all players play their strategies in history H. And we're going to look at player I and its value. So we can calculate the expected value of some policies. So I can I can given this function V, I can input. OK, here's what happened. And here's how everyone's strategy now tell me in expectation what the first player is going to net from this. OK, solving the value function is pretty much equivalent to solving the game. So if you if you give me a good value function, I can solve the game by simply choosing the next action that gives me the best value function. But there's a difficulty. We said, OK, we know pie strategies are public, but we don't know what history we're in. Right. So even if you had the perfect value function, I don't know what to input. So this is going to be a problem. All right. The last thing is a Nash equilibrium. You might know this term. A Nash equilibrium is a policy profile such that no agent can achieve a higher expected value by switching to a different policy. Our goal here is going to be to find a Nash equilibrium strategy for these games. And the rebel algorithm is going to provably converge to a Nash equilibrium. All right. So, OK, there's also the concept of a sub game. A sub game is defined by a root history. It's simply if you're in a it's simply a game that starts at some intermediate state. That's a sub game. OK. Alpha zero, for example, constructs sub games. In fact, it constructs these depth limited sub games because you only solve up to a certain depth. And at that point, you sort of ask your value estimator what the value is. This is different in different things. Like you can also do this this kind of Monte Carlo estimation where you just play one trace to the end and so on. But the notion is we iteratively construct these depth limited sub games. That means we play for a certain depth and then we evaluate at that depth. And the question is, how are we going to evaluate? OK, so this is all sort of the build up. So we've built up that we can't deal with world states like in classic games. We need to deal with info states. And now with info states, we have a problem. Namely, we can't use the Alpha Zero algorithm again because it will result in the thing on the right. Because if we simply ask our value estimator, our value estimator, even if it's perfect, it won't lead us to the correct strategy because the value estimator here is the wrong tool. If we don't know all of the information because of this fact that the value of a node doesn't only depend on the downstream actions, but also depends on the upstream strategies. So in an info state, we can't distinguish where we are. And that means our value estimations are going to be rather useless if we just apply this algorithm straightforward. So we need a way to transform a game where we don't know everything to a game where we do know everything. It sounds a bit weird, but that's exactly what we're going to do right here. So we're going to go from world states to public belief states. And the world states are sort of what we would like to have, but don't know. The public belief states, those are going to be things that everyone knows. So if we go from world states to public belief states, we're going to be in a situation again where everyone knows everything. And therefore, it is a perfect information game. It's going to be a different game. But if we find the solution to this different game, we're going to end up with the solution to this to the original game. For that, they ask you to imagine the following game. Consider a game in which one of 52 cards is privately dealt to each player's. So you get a card, your opponent gets a card, one card. 52, for those of you maybe in different parts of the world, that's the number of cards in a standard card deck for like poker and blackjack and so on. I know different countries have different things. Like in Switzerland, you'll very often find 36 cards to a deck. But just that's why, because 52 appears like a bit of a weird number in any case. On each turn, a player chooses between three actions, fold, call or raise. So these are the sort of standard poker actions. You can either throw away your card if you don't like it. You can match the bet of your opponent or you can put in some money or some more money yourself. And at the end, I'm going to guess. Yeah, here, eventually the game ends and players receive a reward. So let's say whoever has the higher card wins all the money in the middle. Now consider a modification of this game in which the players cannot see their private cards. Instead, their cards are seen by a referee. On the player's turn, they announce the probability they would take each action with each possible private card. The referee then samples an action and the players on the player's behalf from the announced probability distribution for the players true private card. This is this is weird. So usually you'd look at your card like I have an ace. OK, and then you come up with a with a sort of strategy. You come up with a policy. You want to say I'm going to raise with probability. Ace is pretty good. So I'm going to raise with a probability point seven. I'm going to call with a probability of point two. And I'm going to fold with a probability of point one. So this here, this would be an appropriate policy, let's say, for getting an ace at the beginning. Maybe this goes back and forth a bit and you might change because you might change your belief. You don't know what your opponent has. Now the game changes, namely, the game is going to be your opponent gets a card and you get a card and you don't get to look at even your card. So now you don't know your opponent's card and you don't know your card. But what you can do is you can announce to the referee, you can say, OK, referee, I am going to do this. If I have an ace, I'm going to raise with point seven, call with point two and fold with point one. If I have a king, I'm going to. OK, I need a bit more space. If I have a king, I'm going to raise with point six. I'm going to call with point three and I'm going to fold with point one and so on until if I have a two, I'm going to raise with probability zero. I'm going to call with probability point one. I'm going to fold almost all of it. OK, so you get to announce your entire strategy to the referee. The referee, who is a super user or I don't know, God. So or I don't know, choose your favorite deity, sees everything, sees all the cards. The referee will input will take this entire table that you give it as input. It will go look at your card. It will see, ah, it's a king or it's an ace, and it will then choose the appropriate sub table here for you. And then it will sample an action from that. So instead of you looking and just producing this table, you produce all the tables for all the things that you could have. And then the referee does the same thing for you. OK, and so does your opponent. And you simply do this. So now you see it's a bit of a different game. The the namely the actions are different. So the action is no longer that you produce or sort of policy is no longer. You simply look at what you have and you determine the probabilities. Now the policy is you spout out this table for all the things you could have. And in each case, for all the things you could do. The important thing is so they say, OK, when the game starts, each player's belief distribution about their private card is uniform random and also about the opponent's private card. Right. However, after each action by the referee, players can update their belief distribution about which card they are holding the base rule. Likewise, players can update their belief distribution about the opponent's private card through the same operation. So it's important to note that this already happened before. So even if in the original game, you would update your belief about the opponent's private card according to base rule or whatever you rule you want. You simply try to infer what they have. Now, the difference is you also have to infer what you have, depending on what actions the referee does. So you sort of treat yourself like a player, like a different player, like an opponent player that you don't know the private cards of. Thus, the probability that each player is holding each private card is common knowledge among all players at all times in this game. So that makes it such that you don't know your opponent's card. You don't know your card. You have to use sort of the same algorithm to determine what everyone has. So that means that all the knowledge is shared. No one knows the true private cards, but everyone knows the same things. So if no one knows, then everyone knows the same. It's a bit like probability socialism. No one has anything. Everyone's equal. Sorry, that was a slight right there. So the important thing, they say, the critical insight is that these two games are strategically identical. And that's very surprising. But if you think a bit about it, it becomes clear that your strategy up here is the same as down here. You simply don't fully announce it every time explicitly. But we said anyway that policies are public. Therefore, this game here is equivalent to this game. These are the same games. But the latter contains no private information. And is instead a continuous state and action space. Perfect information game. While players do not announce their action probabilities for each possible card in the first game, we assume that all players policies are common knowledge. And therefore, the probability that a player would choose each action for each possible card is indeed known by all players. OK, so. And this you can even lift the restriction that you know or don't know the opponent's strategy. So you don't actually need to know it, but we'll simply assume that everyone knows everyone's strategy. They just don't know their their private cards. So this is a new game that we've constructed where it's a bit different, right? There are different states and different actions. So the states that we deal with in this game, let's quickly analyze this. So what's. So we have state and action in the in game one. The state is an info state. So this is an info state and the action is going to be a probability distribution over actions. So P of each of the actions in this game down here, we have different states and different actions. Now, the states we're going to get to in a minute. But what's the action? The action is to send a table of all these probability distributions in each case, like in case I have this, in case I have this, so that's going to be the action. The action is going to be to send this entire table to the referee. Now, what are the states? This is this next section. We refer to the first game as the discrete representation. That's the top game and the second game as the belief representation. An example above a history in the belief representation, which we refer to as a public belief state, is described by a sequence of public observations and one hundred and four probabilities, the probability that each player holds each of the 52 possible private cards. OK, so this is going to be the state is going to be called a public belief state. And it's described by the sequence of public observations and one hundred and four probabilities. So the probabilities that probability that you have an ace, you have a king, you have a queen and so on, like the distribution over your cards and the distribution of your opponent's cards. So it's simply the info. It's like an info state of someone that just observes the game. That is going to be the public belief state. OK, likewise, an action is described by one hundred and fifty six probabilities, one per discrete action per private card. In general terms, the PBS is described by a joint probability distribution over the agents possible info states. You see, it's a it's a distribution over info states. So the state is a distribution for each info state or they also call this a public belief state. So now we've gone from a game that is imperfect information to a game that is perfect information. OK, this is this is this has unknowns like many like, oh, this is different for each player. But here all the information is known and these two games are equivalent. It's just that you can see already the problem like the states are way bigger because it's a distribution over each state that could be. And the actions are also way bigger, namely, it's an one policy for each state that you could be in. So these are massive amounts. But in theory, that makes no difference. So they say, since any imperfect information game can be viewed as a perfect information game consisting of public belief representations or public belief states, in theory, we could approximate a solution of any two player zero sum imperfect information game by running a perfect information or L plus search algorithm on a discretization of the belief representation. OK, so nothing stops you from simply taking this and running AlphaZero on this new thing on this new thing with the states being public belief states and the actions being descending around of these giant tables. You might have to discretize it as it says, but that's feasible. So you can think of constructing this game tree, but each node here is going to be a public belief state. Instead of a world state like an AlphaZero or like an info state, like we started these imperfect information games with. And then you can construct your tree down here and then, you know, but this is infeasible because these public belief states are just too large and the actions are also too large. There are so many actions. These are super high dimensional. So this is not feasible. And we're going to so they have to find a way to do this thing. But to to sort of do it in the domain of the original game. And that's the I feel that's the entire trick of this rebel paper is to take this idea. Let's do this search over the public belief states. But somehow this this thing down here, because what we need is we need the values of these. Right. If we figure out the value of this public belief state and the value of this one, right. This is of beta one. This is of beta two. Then we would know which action to take. And an action is this huge thing. But if we knew the values of these, we would know which action to take. However, this is not feasible. So we need to find a way to figure out these values using the original formulation of the game. And that's what they do in the exact next section right here. So they go on saying, however, as shown in the example above, belief representation can be very high dimensional. So conducting search is as is done in perfect information games would be intractable. They say, fortunately, in two players, zero sum games, these high dimensional belief representations are convex optimization problems. Rebel leverages this fact via conducting search via an iterative gradient ascent like algorithm. So I don't know what this sentence means that the belief representations are convex optimization problems. Maybe this is misformulated or I'm just not understanding it well enough. In general, this section here is a bit of a mystery to me. But I can sort of tell you what what I understand of it. OK, so they say rebels search algorithm operates on super gradients of the P B as value function at the leaf nodes rather than on P B S values directly. This is the first indication we don't want to work. We want to construct this search tree and at the leaf nodes, we need value functions right like in Alpha zero. Now, since we operate on public belief states, we would need value functions of public belief states. However, rebel finds a way to not do that. Specifically, the search algorithms require the values of info states for P B S. OK, so they find a way to connect the values of info states to the values of public belief states. And just as a reminder, an info state is a state that as it looks to one player that could have many different histories, a public belief state has all the info states that could lead to the public observation. So all the info states that you could be in right with all their histories here, basically a distribution over all these info states. That entire thing is one public belief state. Now, they are going to say we can determine the value of a public belief state. So the value of this is going to be equal to and we can somehow approximate this with the values of these things here. We somehow don't need the value of the entire public belief state. We connect this to the values of the individual info states. And that's I mean, that's done fairly easily because you simply sum over. So you can say the value of a given info state condition that you're in public belief state beta is simply going to be kind of the expectation over all the histories that could lead to this info state multiplied by the value of each history. Like you can have the value of a history given some policy and therefore you can approximate the value at a given info state. And this theorem one here is where they connect the value of a public belief state to the value of an info state. So they say for any public belief state, for the beliefs of player one and player two info states respectively, and any policy pi star that is a Nash equilibrium of the sub game rooted at beta. So now we root sub games at public belief states. This thing holds right here. So as you can see, this connects the value of the public belief states. This is what we sort of need in order for the search algorithm to work. It connects it to the value of an info of info states and info states are way lower dimensional than public belief states. So it connects it connects the value of this right here to the value of let's say this. Okay, this this might be an info state here s and the value it connects the value of the global public belief state to the value of this particular info state. And it does so via this term right here. So this term right here, this is just the unit vector in the direction of that particular info state. And this here is a super gradient of an extension of the value function to unnormalized belief distributions. As I understand it, this G is the gradient with respect to probably beta one if we care about s one to V one of beta, something like this. As I said, this is where I don't 100% see through it. But what I understand is that this connects the value of the public belief state this thing to the value of the individual info states that are part of this public belief state. So we don't need a value function for public belief states. We can simply get away with learning a value function for the individual info states. And that's what they do. So the only the learned part here in this algorithm. This is the first time we see like a neural network. Since rebel search algorithm uses info state values, rather than learn a PBS value function rebel instead learns an info state value function. So we're going to input a public belief state. Yes. And we're going to get value for each info state. We're going to get a value here. So we'll simply learn a value function as sort of a vector output. You could also input the public belief state and the info state and get out a single number. I guess that would turn out to be the same thing. Okay, so the info state value function directly approximates for each info state, the average of the sampled values produced by rebel at beta. So we're going to learn this in a sort of bootstrap fashion, like like Alpha Zero does it a bit like temporal difference learning. So what we're going to do in this algorithm is we're going to start out, then we're going to construct this sort of this sub tree. And we're going to do this in the discrete representation of the game. Now, that's the genius of the rebel algorithm. We're going to sort of evaluate these things in the discrete representation in the info state representation. And then we're going to be able to use what we find right here in order to determine the value of the next actions to take as far as I can tell. Okay, so that there is only one thing left to do. Right. We need to know how does how does this step here work? So we we said we want to do this tree search over the public belief states, but we can't. It's too cumbersome. Therefore, we can now we can evaluate values of a public belief state. But we still need to do to determine the policies. And that's where the self play reinforcement learning comes in. So bear with me for one second. This is going to kind of snap together all that we've looked at so far. In this section, we describe rebel and prove that it approximates a Nash equilibrium at the start of the game. A depth limited sub game rooted at the initial public belief state is generated. This sub game is solved by running T iterations of an iterative equilibrium finding algorithm in the discrete representation of the game, but using the learned value network to approximate leaf values on every iteration. Okay, so it might seem a bit a bit complicated, but we're going to do is we're going to here is what I think happens. And this is a bit unclear to me. We're going to take a any public beliefs that we find ourselves in. They call they tell the beginning of the game, but any any public belief state. Okay, so the public belief state is maybe here and it contains many different info states. Now, what I think happens here is that they may be sampling one of the info states. I don't know, or they may input the public belief states at the beginning. This is unclear to me, but then they're going to solve the game in the discrete representation. So they're going to use a classic solver to solve the game up to a limited depth. Okay, so this limited depth is going to be sort of D steps in into the future. This is going to be in the classic representation. So classic states and classic actions. Now, the solver that they use for this is counterfactual regret minimization. This is a solver that works with info states. Okay, so you can actually use CFR to solve poker. However, you can't solve all of poker because the game is too big. Right. So but you can solve a sub game provided that you have good value estimates here at the end. So that since they use CFR, that leads me to believe they don't use the entire public belief state as an input to CFR. But they either maybe sample an info state or they actually sample one particular history that happened. That is unclear to me. However, what they do is they they do this. They solve the sub game using CFR. And then out of that, they get a strategy. Okay, so here you ask your solver, what should I do? Given, you know, given my estimates of the values right here and the CFR will say, I know what you should do. Here is a strategy. Here is a policy that you should do. Now, if this were AlphaZero, if this were fully observable, then you would be done. Right. You'd say, okay, I'm done. Cool. That's what I'm going to do. However, what we saw above is that your values right here, your values down here, they are dependent on what comes before you. Specifically, they are dependent on this strategy. Okay. Now, CFR needs sort of an initial strategy. And it outputs a best strategy for the given values. But now that you have another strategy, these values here, they are no longer valid. And you computed the strategy with the values. So what you're going to do is you're going to plug in. You're going to use this thing to compute new values. Okay. More values. You're going to construct another or the same sub game with new values and then use CFR again to solve that. And that will give you the next policy for these values. But then the values change again and so on. Now, this is going to converge eventually. But you're going to have to run a couple of iterations of this for this to converge. In fact, I believe it's the running average or the average that's going to converge. But you're going to solve a number of these sub games, okay, until you reach the actual best strategy. And you're going to do that down the game tree. So from this thing, you're going to construct sub game. You're going to construct one, two, three, updating the values, solving it. And then once you have it, you sample some state in between. From that, you're going to solve the sub game again, one time, two time, three time, and so on until convergence and so on. So this multiple solving of the same sub game, that's what we have to do. So it is the price we have to pay for solving the game in the discrete representation because we can't solve it in the belief representation because it's too big. There, we would only have to solve it once. But here we have to solve it multiple times. So this is the entire algorithm right here. You can see while the while we're not in a terminal state, we're going to construct a sub game and initialize some some policy. And then for each step, we're going to do first. Sorry, we also set the leaf values. So this setting of leaf values, that's simply forwarding. Like if I know the policy, I can go set the leaf values using my neural network. Right. My neural network can tell me what the value at each of the leaf nodes are. That's what we train it for. So in the set leaf values, there is a neural network. You see this by the fact that there are parameters right here. And then we're going to do repeatedly the following two things. Update policy. So this here is where we use the solver CFR. So we determine the best policy given the current value estimations. And then we're going to set new values given the policy. So see CFR, it will take in the last policy and it will output the next policy. And set leaf values will in will take in these parameters, which meaning this here, that's going to be some kind of MLP or neural network. And we're going to do this. Then we're going to loop back again and do the same thing. Solve the game, set new values, solve the game, set new values, solve the game, set new values. Eventually, by aggregating all of this information, we are going to be able to compute the expected value. And that's going to be the value of the public belief state altogether. And as we said, if we know the value, we can sort of take the best action. In fact, here, I believe that the policy that comes out, this average policy is the Nash equilibrium. And we can simply sample an action from that. All right. That's what they describe here. They use we describe rebel assuming the counterfactual regret minimization decomposition CFR algorithm is used. This is a depth limited version of CFR. That's an entire research direction by itself. Right here. Counterfactual regret minimization is simply used as sort of the inner solver, kind of a helper function to call. And that thing by itself is an entire, entire algorithm. It's like a very complicated algorithm. OK. On each iteration, CFR determines a policy profile in the sub game. Next, the value of every discrete representation leaf node is set to this. And this is this is the neural network. Right. So we're going to use the neural network to set the leaf node values of the discrete representation. OK. This means that the value of a leaf node during search is conditional on the policy. Thus, the leaf node value change every iteration. Given pi and the leaf node values, each info state has a well defined values. This vector of values is stored. And next, CFRD chooses a new policy profile in the process repeats for T iterations. All right. That's the rebel algorithm. And they also describe how they actually sample data for learning with the exploration. And they also show that running algorithm one with T iterations of CFR in each sub game will produce a value approximator that has an error of at most this for any PBS that could be encountered during play. So they're going to say that the value approximator, given that it is sort of idealized, will actually converge to a good value approximator. If you sample it, depending on how many iterations of CFR you do. But you can see that the more iterations you do, the better of an approximation you get. And if you have a good value estimator, as we already said, you basically have solved the game. The last thing is that they determine now what do we do at test time? You might not have thought of this. This seems sort of obvious if you know alpha zero, but they determine that at inference time, you can simply run the same algorithm, except you don't want to produce training data from it. You don't want to learn anything. You simply want to run this algorithm too. If you run that algorithm at test time, that will actually give you a Nash equilibrium. So that's theorem three right here. If algorithm one runs a test time with no off policy exploration, value network with error at most, this and this, and was trained as described in theorem two, with t iterations of that, then the algorithm plays this kind of approximation Nash equilibrium, where C1 and C2 are game specific constants. So you can see right here that the Nash equilibrium is going to be perfect depending on how many iterations you do. And depending on, I believe, how accurate your neural network is. Yes, your value network error. If you make that smaller, your Nash equilibrium is going to be better. Pretty, pretty cool. So that was the algorithm. They do a bunch of experiments where they see what kind of network they use, if they use the value net or not, if they use self play or not. And they can also introduce a policy net, I believe, for initializing or searching more effectively. They compare against previous things like DeepStack, Libratus and so on. They do beat top humans, as you can see. Poker has been for a long time kind of an not so solved game by machine learning. But this area has been over for a while right now. And they do release the code of, I believe, of the Liar's Dice. So they have the code released for Rebel and the implementation for Liar's Dice, but not for Poker, because that's what they discuss in the broader impact statement. So let's quickly look at broader impact. Then we're done. So just to say I love this broader impact statement. It is, it describes like it praises the paper. So it's kind of more advertisement for the paper. It does almost like no harm to the paper itself, to its reputation. It is actually accurate. So this broader impact statement actually makes tangible predictions and it doesn't go beyond the or it mostly doesn't go beyond the tangible things you can say about this algorithm. And it actually has as a conclusion an action that they take. So and further, it is nothing like what the original specification of broader impact statement says. And that makes me happy. So good job on this one. We believe Rebel is a major step towards general algorithm finding algorithm, yada, yada, yada. So they say if this is this is good because many things are sort of these kind of games. If you can extend it to multi-agent and so on. So this is the technology good section. But then the bad section is interesting. The most immediate risk posed by this work is its potential for cheating in recreational games such as poker. While they are algorithm already exist, they say why they are better. Why this particular algorithm could be used for cheating where the others can't be done so easily. By the way, this algorithm by nature of performing the searches over and over again, it needs a lot of compute. Like it needs a lot of compute. The learning isn't the problem. The problem is performing these searches over and over and over again. Yeah, so it's not super easy to replicate. Like don't don't try this at home. However, if they were to release the pre-trained network, that would make it easy. And they also say if they release the code, that would maybe make it easier to cheat. If you can simply run maybe, you know, you don't have the hardware, but given made massive poker winnings, who knows? Retraining the algorithms to account for arbitrary cheat size requires more computation as feasible in real time. That's about the other algorithms. However, Rebel can compute a policy for arbitrary stack size and arbitrary bet size in seconds. So that's at inference time. Partly for this reason, we have decided to not to release the code for poker. We instead open source our implementation for Liar's Dice, a recreational game that is not played competitively by humans. OK, so it's a concrete prediction of the impact of this work. It has a concrete action to kind of its conclusion. And it doesn't dabble in who knows if we now solve these two player imperfect information games, then surely in the future bombs will fly and stuff like this. Yeah, good job on this again. All right. So this was the overview of the paper. We started with the notion of info states and info states are kind of like states in classic reinforcement learning. And we determined that we can't really use the sort of Alpha Zero way of doing things because the value of info states not only depends on downstream things, but also on upstream things. And the values here, yeah, that makes the values at the end of the tree not constant. And that means we can't really use that as we saw in this poker thing. Then we converted the game from an info state representation to a public belief state representation, where now it's sort of it's again a everyone knows everything game. Therefore, we could use the Alpha Zero way of doing things. However, since these states and the actions are so large because it consists of these giant tables of numbers, we can't use the Alpha Zero for computational reasons. Luckily, they find a way to connect the value function of public belief states to the value functions of info states, and therefore we can use a solver in the classic in the discrete representation to approximate or to to to use in this search procedure. As long as we run it multiple times and sort of keep updating its values. By doing that, we can use this in this self play, simply iteratively doing this in each step. And we can use bootstrapping and play as we said self play between two agents, and that will provably converge to a good value function and to a Nash equilibrium. All right, that was the paper. Thanks for listening. I'll see you next time. Bye bye.
 Hi there. Take a look at this variant of the game Rock Paper Scissors. It's like usual Rock Paper Scissors, except with the added complexity that when either player chooses scissors, then the rewards and the losses are doubled.
 So for example, you see right here, player one chooses rock and player two chooses scissors. So both the reward for player one and the loss for player two are double the size.
 Now, you might know that in original Rock Paper Scissors, the optimal strategy is to play one third of each of the three choices at any time. So you basically take a fair three sided coin dice. Does that exist? I'm not sure.
 And you throw it and whatever side is up, that's what you play. However, here, since one of the options is different, the sort of optimal strategy shifts. And interestingly, it shifts as follows.
 What you want to do is you want to play rock and paper, both with a 0.4 probability and you want to play scissors with only 0.2 probability.
 That is pretty interesting. You might intuitively conclude that you want to go more where there are more rewards to be had.
 But of course, also you lose more. So you might also conclude, well, it doesn't make a difference ultimately.
 But why does the why does the sort of optimal strategy shift such that you want to decrease your likelihood of playing scissors?
 Let's just quickly analyze this game before we jump into the paper, because this game is sort of a microcosm of what the paper of today is about.
 So the paper of today is called Combining Deep Reinforcement Learning and Search for Imperfect Information Games by Noam Brown, Anton Bakhtin, Adam Lehrer and Qi Chenggong of Facebook AI Research.
 So this paper brings basically what AlphaGo or AlphaZero has done for perfect information games.
 It brings this to the domain of imperfect information games.
 And we'll see what the difficulties are in this and what can be done to solve it.
 And not only do they have an algorithm, but they have interesting theoretical results that under some conditions,
 namely under the condition that neural networks do something useful, will actually converge to Nash equilibrium in these games.
 So that is pretty cool. So practical and theoretical paper right here.
 As always, if you like content like this, don't hesitate to share it out and tell me what you think in the comments.
 This is not my field, so I might get quite a bit of stuff wrong right here.
 Also, if you haven't seen the Negranu Poker Challenge, so I think it's the last video I did,
 be sure to check that out just to see how you have to think about situations like this.
 All right, let's get back to this rock, paper, scissors example right here.
 Interestingly to note is that these dashed lines here means that player two cannot decide which of these states they're in.
 So player two doesn't know what states are in. For player two, this is all basically the same state.
 It would be really easy, right? If player one plays first and then player two sees what player one does,
 and then they just act like they always win.
 However, player two doesn't, so they have to sort of decide what to do, independent of which state they're in.
 Especially this is a symmetric game, right? This is a two player game, because it has two players.
 It's zero sum, because whenever one player wins a reward, the other player loses the same reward.
 And it is also, that makes it symmetric. So both players play at the same time, though that is not necessary in general.
 But here it's the case. All right, so this means in this particular case, whatever strategy player one has,
 player two must have as well. So we'll just do the analysis for player one.
 So let's say you deviate from this optimal strategy, right? We claim that this here is the optimal strategy, playing 20% of scissors.
 Let's say player one doesn't believe it. Player one deviates from it and says, nah, there is so much reward there.
 I'm going to get some more of that. So they up this, right? They up this to like, let's say, point, I don't know,
 point three, three, like doing the classic one third or even higher, right? They up this, go more scissors, okay?
 And they probably want to take this mass because they have to take it from somewhere.
 They probably want to take this from rock and paper. Let's say they just take it equally from rock and paper towards scissors to up the,
 to up the probability that they play scissors. So from paper and from rock, they go towards scissors.
 Now, player two observes this, right? They can just play against player one for a while.
 Or what we're going to assume is that everyone announces their strategy publicly.
 It's the same thing. You can just observe someone for a while or they can just announce their strategy.
 It's, we'll treat this equally. So player two observes player one playing scissors too often.
 So player two knows they are very often in this situation right here in this right state.
 They can't directly observe, but they infer I must be very often in this right, right most state where player one chooses scissors.
 And therefore you see player two's payoffs. It's zero here, minus two here and two here.
 So they'll say, well, I also have this optimal strategy of point four, point four, point two.
 What I can do is I can simply, knowing that I'm a lot in this state, I can simply take some mass from paper and put it on rock.
 So I play rock way more often and I reduce the amount I play paper, right?
 Scissors doesn't matter, but now I lose two less often and I win two much more often.
 And player one in turn loses two much more often and wins much less often.
 So player one wanted to get more reward, but they're sort of being punished by player two for playing this too often.
 Now you can say, well, player one can do the same thing knowing that player two plays rock too often now.
 They've taken away mass from paper towards rock. Knowing that player two has taken rock,
 player one knows that either they're here or they're here, right?
 And in this case, player one can say, all right, you play rock too often.
 Obviously, if I play scissors, then I'm going to lose, but I've already decided I want to play scissors much more.
 So they're trying to make it up right here. So what they can do in this case is they can say, when I play paper, I win one.
 Instead of if I play rock too, I win zero. So I know player two is playing rock way more often than they should.
 So I'm going to punish player two by playing paper more often. So let's erase this arrow.
 Let's say we play scissors. Sorry, we play scissors. No, let's not erase this.
 We play scissors by moving from rock and we also move from rock to paper. Like we're almost never playing rock.
 We're just playing scissors more often because that's what we started with. And we're playing also now paper more often.
 So now we basically do the same thing that player two did to us.
 We are upping the likelihood of this thing happening and decreasing the likelihood of this thing happening.
 So now we can say, haha, now I also I play paper more often.
 Now I also win more often here and you lose more often. But you see, because the rewards are doubled over here,
 the fact that player two can achieve this is much more meaningful than the fact that player one can achieve this.
 OK, and that's why player one will be punished harder for deviating here.
 So that's sort of how you reason about these strategies. So if player one will play this point to too often,
 they will be punished harder than player two for deviating in response to that.
 And the same counts for the symmetric part. This is a very important concept right here.
 Namely, you can see player two strategy depends on player one strategy,
 even though you could conceptualize this game of player one plays a move and then they play a move,
 but they don't show it yet. Right. They play a move.
 They take like a picture of their hands doing rock, paper, scissors, and they just don't show the picture yet.
 And then player two plays a move. So now we're basically back in.
 We're in this game where it's sequential in nature.
 And usually in a sequential game, you can just do a sub game analysis.
 So you can just say, OK, and do a sub game analysis.
 But the sub game analysis depends on the strategy of player one because you don't know the situation.
 This is different than a full information game. And this is illustrated right here.
 So they say usually what something like AlphaZero does is
 your game starts here. Right. And then you have two actions to take.
 You maybe take this action. OK. Now your opponent has two action.
 Maybe they take this action. All right. And now you have two actions again.
 Which one do you take? What something like deep Q learning or actor critic learning would do is
 they would simply put a neural network here. They would look at this state.
 And they would simply tell you which action to pick. Like this action right here.
 Sounds good to the neural network. In contrast to that, AlphaZero,
 if I draw the same situation right here, AlphaZero, what it will do is it will say,
 well, I could do this or I could do this. If I do the left thing, then I'm going to have my opponent's going to have two options.
 They could do this or they could do that if they do the left thing again.
 And so you get the idea. It sort of goes down the tree and it does this over here. Right.
 Sorry. This should be so it goes down the tree. I'm stupid.
 And it evaluates. It kind of calculates ahead. It uses its internal simulator to look ahead.
 And it could technically do this until it reaches the end.
 And then it would know if it reaches the end state every time here, it wouldn't know.
 It could simply backwards calculate which one is the best option for me to do right now.
 However, this game is often very, very deep. So the tree, the depth here is often so deep that you can't solve the whole game.
 So what Alpha Zero does instead is it says, I'm not going to play until the end. I'm going to play a certain amount ahead. Right.
 I'm going to think some limited depth ahead. And I know Alpha Zero does this adaptively. But bear with me.
 I'm going to think some limited depth D ahead. So here in this case, D is equal to two because we think two layers ahead.
 And then at the end, I'm going to replace everything that comes after with a single value that indicates how good this is for me.
 OK. So and this thing right here is very hard to get. Of course, if you knew how good anything is for you, then you have solved the game.
 But Alpha Zero at this point, the neural network comes in. Right.
 It this is a neural network. It's a black box. So it simply asks for each one of these states.
 How valuable do you think that is? OK. How valuable do you think that is? OK. And so on.
 So it asks for each state, the neural network, how valuable that particular node is.
 And then it does the same backwards calculation. So we've sort of substituted going to the end of the game by the neural network.
 But it is still more powerful than asking the neural network at the very beginning, like we do here.
 The power comes from combining the learning. This is this is the learning. And the search.
 This here is the search. Right. So this is what Alpha Zero does.
 And this is what this paper does for imperfect information games.
 So imperfect information games is when you don't know a particular thing about the game at any point.
 So there is hidden information like in poker. And the problem is right here,
 if you do the same thing for this game right here and you look from player one's perspective and you say,
 OK, this game is very deep. Actually, it's just too deep. Right.
 But let's assume that's too deep for you. And you want to replace.
 You want to say, OK, I'm just going to look ahead. D equals one.
 That's all I can afford. I go ahead. And at the end, I'm going to ask my neural network what the value here is.
 And the neural network will tell you accurately that the value at each of these nodes is zero.
 So the average value, if you can see right here, the average value of each of these nodes is zero,
 depending, of course, on how player two acts. But in this case, it's zero.
 So as player one, this information will not lead you to the correct optimal conclusion,
 the correct optimal conclusion being this point four point four point two.
 Player one, like it's indifferent. Any strategy could work here. Right.
 If there is some regularization, it'll probably come to the point, the one third, one third, one third.
 So if it means all the values are equal, it might conclude it's probably best if I distribute my actions or something.
 So you can see the problem right here. And the problem is that this value right here,
 it depends on the strategy of player one.
 And this is something that AlphaZero has no concept on.
 AlphaZero, the value of a node only ever depends on what comes downstream.
 In imperfect information game, the value of a node also depends on what has happened upstream.
 So on the strategy of the upstream events. And that is, as I said, that is that is quite important.
 Also for AlphaZero, once I have evaluated a game tree and determined the value of a node like this,
 I can evaluate the same game tree again. And the value is going to be the same.
 But for the same reason, because the value depends on the value of this node right here, depending on upstream.
 If I change my strategy. So if here I determine either action one or action two with a certain probability,
 if this search process results in a result that tells me this is how often you should pick action one,
 and that's different from what I searched with, right, then all of these values down here are going to change.
 And I can basically search again. So these are the problems of imperfect information games that we're going to tackle.
 So you see this poker thing is sort of a microcosm.
 And this was already half of the paper if you understood why exactly searching using kind of a value estimator
 with this combined with this tree search is a problem in imperfect information games.
 So let's quickly go through the abstract. Then we're going to have to define a few terms.
 And then we can go into this algorithm. The algorithm is called Rebel.
 It's a general framework for self play reinforcement learning and search that provably converges to a Nash equilibrium in any two player zero sum game.
 It says that in the simpler setting of perfect information games, Rebel reduces to an algorithm similar to Alpha zero.
 And they say we also show Rebel achieves superhuman performance in heads up,
 no limit Texas Hold'em poker while using far less domain knowledge than any prior poker AI.
 So last video, I've had a comment, which is correct, that is not the best Hold'em AI out there, as far as I can tell.
 However, it is a very performant one that uses very little domain knowledge of poker.
 So it like Alpha zero removed basically all domain knowledge out of the games it played.
 This bot right here, I think the domain knowledge is to the extent of it is given a limited set of bet sizes,
 even though it's kind of no limit Hold'em where you can bet whatever you want.
 It's given sort of a limited bet, limited size of bet sizes, like half the pot, full pot, two times the pot and so on.
 In order to make the actions discrete, I think that's just easier for this algorithm.
 But in any case, the algorithm is applicable pretty much anywhere where you have a two player zero sum in perfect information game or perfect information.
 OK, so let's shortly go over a little bit of background.
 So we're going to need some terms right here.
 The first term we're going to need is what's called a world state.
 So a world state is the state of the world.
 I know easy, easy, but it's quite important that to see that in poker, what is the world state?
 So in heads up, no limit Hold'em, there are your cards, you get two, your opponent gets two cards, right?
 And then there are board cards like at the end there are five, but maybe there are only three or there are none yet.
 It depends on the state of the game.
 So the board cards, you know, this is maybe an ace, a king, an eight.
 You know your two whole cards, which is maybe an ace and an ace, but you don't know your opponent's cards.
 We're also going to assume that the actions are always public for the purposes of this video.
 They don't not necessarily for rebel the algorithm, but for us, let's just say the actions are all public.
 So the world state is the fixed entire state of the world.
 So the world state would include the your cards, the public cards and your opponent's cards.
 So the world state is sort of like a super user can look at all of the cards.
 That's the world state. No one knows the full world state, but it still exists.
 What we also need is so there's a concept of actions.
 There is an action space, which in poker is something like you can bet, you can raise and so on.
 So these are your classic actions and there is a transition function like in classic reinforcement learning.
 So the transition function depends on the world state and the action and it gives you the next world state.
 And after an action, each agent receives a reward that is also a function of the world state and the action.
 So important to note that this is the reward you receive, but you don't know the you maybe know the function,
 but you don't know the world state. So you can't explicitly sort of predict your reward.
 You can maybe predict the distribution. All right.
 The next concepts are the concepts of observation.
 Since we are in an imperfect information game, an observation and the world state, these are not the same thing.
 Like in chess, you need to look at the board and that's all there is.
 That's all there is to know. So the world state and the observation are the same thing.
 Here there is the concept of private and public observations.
 So public observation is like is what everyone knows in each step,
 whereas private observations are things that are just revealed to you personally.
 In poker, the private observation is simply your two whole cards and the public observation is the middle cards.
 So this is the public observation and this is your private observation.
 So the private observation is different for each player while the public observation is the same.
 I guess you could model the public observation as simply another player that doesn't get any whole cards.
 But you know, that's a question of semantics.
 All right. The observations can also include the actions that happened so far just for completeness.
 If you like, you can get information about hidden actions and so on.
 There's lots of mathematical freedom here, but just the concept is you have private observations to each player individually and then public observations.
 The subscript I here always denotes a individual player while you see there is no such subscript in the public observations.
 All right. The next concept is a history and a history is pretty much what you think.
 A history or a trajectory is a finite sequence of legal actions and world states denoted by this.
 So you can see it's simply the history of world states and actions that happened.
 Again, no one knows the history fully, but it's still it is still the case.
 And I know I know you can I don't know quantum mechanics, many worlds theorem, blah, blah, blah.
 We'll just assume that whatever you don't know these these are fixed cards.
 They're actually there. They have a value even though no one has looked at them yet.
 So the world state is is defined even if you don't know it.
 So the first real interesting concept here is called an info state.
 OK, so the info state is like the world state or like the history, but it's conditioned on what an individual player knows.
 OK, the info state also called an action observation history for agent I is a sequence of an agent's observations and actions.
 So you can see it's very much like a history, except that it doesn't have the world states.
 So usually there would be the world state here.
 You said no, there is the observation for player I at each of the time steps.
 OK, and these observations, they include public and private observations and along with the actions.
 But we'll say the actions are public anyway.
 So an info state is basically the history as it looks to player I.
 OK, that's an info state in our original game.
 We said that player two can't distinguish between the three nodes.
 So if you look at the three nodes individually like this node one node two node three,
 these are three different world states with three different histories.
 And to player two, they're simply the same info state because all it all player two knows is that player one has taken some action.
 It doesn't know which action.
 So the observation that player two has is exactly the same.
 Therefore, it can't distinguish.
 So you can see that the info state is sort of the correct abstraction that we're going to look at here in, you know, in turn for if you look for player one,
 it looks different, even though for player one, it's also three different world states.
 It is also three different info states, OK, because player one knows which action they have taken.
 So player one can decide which of these three states player two is in.
 So player one is to player one.
 This corresponds to three different info states.
 So the info states is always conditioned on a player and it is the sort of unit that we'll look at here.
 All right. So the info state briefly, it includes the observations and actions for a given player.
 And the observations include the private and the public observations.
 The unique info state corresponding to a history for agent i is denoted by this.
 The set of histories that corresponds to some info state is denoted by large H.
 So as we said, if you have an info state, there are many different histories that could have led to the info state.
 OK, so there are many different like there may be for player two.
 It looks like three different histories that could have happened lead to the same info state.
 OK, that's but any given history determined fully determines the info state.
 If I tell you what happened, you can give me the info state for each player.
 You can say, ah, player one played rocks.
 Therefore, player two is in that info state and player one is in that info state.
 So that's why there is a unique info state for each history.
 But there is a set of histories for each info state.
 So the last last concept from here is a policy.
 A policy is again what you think it is.
 So it is something usually it's something that maps from an observation to an action or from a history to an action or from a world state to an action.
 But here it is a function necessarily that maps from an info state to a probability distribution over actions.
 So two things important here.
 The input to the policy is an info state since the players, they can't distinguish between the world states as long as they correspond to the same info state.
 Therefore, their policy necessarily must be taking an info state as an input.
 So player two's policy cannot depend on what player one did because it can't distinguish.
 It can depend on the strategy of player one, but not on the concrete action.
 The second thing is that we map to a probability distribution over actions.
 This is usually the case in in RL if you frame it as a general principle.
 However, here it's going to be quite important that this is always a probability distribution.
 Very often in these games, your strategy is probabilistic.
 So there is no single best move in rock, paper, scissors.
 But the best thing to do, the best strategy is to play each move with a one third probability or the modified version at the beginning.
 But it's important to see that a policy will output a probability distribution.
 And I will also call this the strategy of a player.
 So the strategy is going to be the policy.
 And I like to call it a strategy because it's sort of it's a kind of a plan what you would do in each situation.
 And we're going to see that that is going to be a central theme lifting in solving these games right here using rebel.
 So policy profile is simply a tuple of policies.
 So it's simply the policies of all players.
 That's the policy profile.
 If you combine the policy profile with some with some info state or some history, you can calculate the expected value.
 So the expected value for a given history, given that the players play policy pro players play policy profile pie.
 So this is all players play their strategies in history H.
 And we're going to look at player I and its value.
 So we can calculate the expected value of some policies.
 So I can I can given this function V, I can input.
 OK, here's what happened.
 And here's how everyone's strategy now tell me in expectation what the first player is going to net from this.
 OK, solving the value function is pretty much equivalent to solving the game.
 So if you if you give me a good value function, I can solve the game by simply choosing the next action that gives me the best value function.
 But there's a difficulty.
 We said, OK, we know pie strategies are public, but we don't know what history we're in.
 Right. So even if you had the perfect value function, I don't know what to input.
 So this is going to be a problem.
 All right.
 The last thing is a Nash equilibrium.
 You might know this term.
 A Nash equilibrium is a policy profile such that no agent can achieve a higher expected value by switching to a different policy.
 Our goal here is going to be to find a Nash equilibrium strategy for these games.
 And the rebel algorithm is going to provably converge to a Nash equilibrium.
 All right.
 So, OK, there's also the concept of a sub game.
 A sub game is defined by a root history.
 It's simply if you're in a it's simply a game that starts at some intermediate state.
 That's a sub game.
 OK.
 Alpha zero, for example, constructs sub games.
 In fact, it constructs these depth limited sub games because you only solve up to a certain depth.
 And at that point, you sort of ask your value estimator what the value is.
 This is different in different things.
 Like you can also do this this kind of Monte Carlo estimation where you just play one trace to the end and so on.
 But the notion is we iteratively construct these depth limited sub games.
 That means we play for a certain depth and then we evaluate at that depth.
 And the question is, how are we going to evaluate?
 OK, so this is all sort of the build up.
 So we've built up that we can't deal with world states like in classic games.
 We need to deal with info states.
 And now with info states, we have a problem.
 Namely, we can't use the Alpha Zero algorithm again because it will result in the thing on the right.
 Because if we simply ask our value estimator, our value estimator, even if it's perfect,
 it won't lead us to the correct strategy because the value estimator here is the wrong tool.
 If we don't know all of the information because of this fact that the value of a node doesn't only depend on the downstream actions,
 but also depends on the upstream strategies.
 So in an info state, we can't distinguish where we are.
 And that means our value estimations are going to be rather useless if we just apply this algorithm straightforward.
 So we need a way to transform a game where we don't know everything to a game where we do know everything.
 It sounds a bit weird, but that's exactly what we're going to do right here.
 So we're going to go from world states to public belief states.
 And the world states are sort of what we would like to have, but don't know.
 The public belief states, those are going to be things that everyone knows.
 So if we go from world states to public belief states, we're going to be in a situation again where everyone knows everything.
 And therefore, it is a perfect information game.
 It's going to be a different game. But if we find the solution to this different game, we're going to end up with the solution to this to the original game.
 For that, they ask you to imagine the following game.
 Consider a game in which one of 52 cards is privately dealt to each player's.
 So you get a card, your opponent gets a card, one card.
 52, for those of you maybe in different parts of the world, that's the number of cards in a standard card deck for like poker and blackjack and so on.
 I know different countries have different things.
 Like in Switzerland, you'll very often find 36 cards to a deck.
 But just that's why, because 52 appears like a bit of a weird number in any case.
 On each turn, a player chooses between three actions, fold, call or raise.
 So these are the sort of standard poker actions. You can either throw away your card if you don't like it.
 You can match the bet of your opponent or you can put in some money or some more money yourself.
 And at the end, I'm going to guess. Yeah, here, eventually the game ends and players receive a reward.
 So let's say whoever has the higher card wins all the money in the middle.
 Now consider a modification of this game in which the players cannot see their private cards.
 Instead, their cards are seen by a referee. On the player's turn, they announce the probability they would take each action with each possible private card.
 The referee then samples an action and the players on the player's behalf from the announced probability distribution for the players true private card.
 This is this is weird. So usually you'd look at your card like I have an ace.
 OK, and then you come up with a with a sort of strategy. You come up with a policy.
 You want to say I'm going to raise with probability. Ace is pretty good.
 So I'm going to raise with a probability point seven. I'm going to call with a probability of point two.
 And I'm going to fold with a probability of point one.
 So this here, this would be an appropriate policy, let's say, for getting an ace at the beginning.
 Maybe this goes back and forth a bit and you might change because you might change your belief. You don't know what your opponent has.
 Now the game changes, namely, the game is going to be your opponent gets a card and you get a card and you don't get to look at even your card.
 So now you don't know your opponent's card and you don't know your card.
 But what you can do is you can announce to the referee, you can say, OK, referee, I am going to do this.
 If I have an ace, I'm going to raise with point seven, call with point two and fold with point one.
 If I have a king, I'm going to. OK, I need a bit more space.
 If I have a king, I'm going to raise with point six. I'm going to call with point three and I'm going to fold with point one and so on until if I have a two, I'm going to raise with probability zero.
 I'm going to call with probability point one. I'm going to fold almost all of it.
 OK, so you get to announce your entire strategy to the referee.
 The referee, who is a super user or I don't know, God.
 So or I don't know, choose your favorite deity, sees everything, sees all the cards.
 The referee will input will take this entire table that you give it as input.
 It will go look at your card.
 It will see, ah, it's a king or it's an ace, and it will then choose the appropriate sub table here for you.
 And then it will sample an action from that.
 So instead of you looking and just producing this table, you produce all the tables for all the things that you could have.
 And then the referee does the same thing for you.
 OK, and so does your opponent.
 And you simply do this.
 So now you see it's a bit of a different game.
 The the namely the actions are different.
 So the action is no longer that you produce or sort of policy is no longer.
 You simply look at what you have and you determine the probabilities.
 Now the policy is you spout out this table for all the things you could have.
 And in each case, for all the things you could do.
 The important thing is so they say, OK, when the game starts, each player's belief distribution about their private card is uniform random and also about the opponent's private card.
 Right. However, after each action by the referee, players can update their belief distribution about which card they are holding the base rule.
 Likewise, players can update their belief distribution about the opponent's private card through the same operation.
 So it's important to note that this already happened before.
 So even if in the original game, you would update your belief about the opponent's private card according to base rule or whatever you rule you want.
 You simply try to infer what they have.
 Now, the difference is you also have to infer what you have, depending on what actions the referee does.
 So you sort of treat yourself like a player, like a different player, like an opponent player that you don't know the private cards of.
 Thus, the probability that each player is holding each private card is common knowledge among all players at all times in this game.
 So that makes it such that you don't know your opponent's card. You don't know your card.
 You have to use sort of the same algorithm to determine what everyone has.
 So that means that all the knowledge is shared.
 No one knows the true private cards, but everyone knows the same things.
 So if no one knows, then everyone knows the same.
 It's a bit like probability socialism. No one has anything. Everyone's equal.
 Sorry, that was a slight right there.
 So the important thing, they say, the critical insight is that these two games are strategically identical.
 And that's very surprising. But if you think a bit about it, it becomes clear that your strategy up here is the same as down here.
 You simply don't fully announce it every time explicitly.
 But we said anyway that policies are public. Therefore, this game here is equivalent to this game.
 These are the same games. But the latter contains no private information.
 And is instead a continuous state and action space. Perfect information game.
 While players do not announce their action probabilities for each possible card in the first game,
 we assume that all players policies are common knowledge.
 And therefore, the probability that a player would choose each action for each possible card is indeed known by all players.
 OK, so. And this you can even lift the restriction that you know or don't know the opponent's strategy.
 So you don't actually need to know it, but we'll simply assume that everyone knows everyone's strategy.
 They just don't know their their private cards.
 So this is a new game that we've constructed where it's a bit different, right?
 There are different states and different actions. So the states that we deal with in this game, let's quickly analyze this.
 So what's. So we have state and action in the in game one.
 The state is an info state. So this is an info state and the action is going to be a probability distribution over actions.
 So P of each of the actions in this game down here, we have different states and different actions.
 Now, the states we're going to get to in a minute. But what's the action?
 The action is to send a table of all these probability distributions in each case, like in case I have this, in case I have this,
 so that's going to be the action. The action is going to be to send this entire table to the referee.
 Now, what are the states? This is this next section.
 We refer to the first game as the discrete representation.
 That's the top game and the second game as the belief representation.
 An example above a history in the belief representation, which we refer to as a public belief state,
 is described by a sequence of public observations and one hundred and four probabilities,
 the probability that each player holds each of the 52 possible private cards.
 OK, so this is going to be the state is going to be called a public belief state.
 And it's described by the sequence of public observations and one hundred and four probabilities.
 So the probabilities that probability that you have an ace, you have a king, you have a queen and so on,
 like the distribution over your cards and the distribution of your opponent's cards.
 So it's simply the info. It's like an info state of someone that just observes the game.
 That is going to be the public belief state.
 OK, likewise, an action is described by one hundred and fifty six probabilities,
 one per discrete action per private card.
 In general terms, the PBS is described by a joint probability distribution over the agents possible info states.
 You see, it's a it's a distribution over info states.
 So the state is a distribution for each info state or they also call this a public belief state.
 So now we've gone from a game that is imperfect information to a game that is perfect information.
 OK, this is this is this has unknowns like many like, oh, this is different for each player.
 But here all the information is known and these two games are equivalent.
 It's just that you can see already the problem like the states are way bigger
 because it's a distribution over each state that could be.
 And the actions are also way bigger, namely, it's an one policy for each state that you could be in.
 So these are massive amounts. But in theory, that makes no difference.
 So they say, since any imperfect information game can be viewed as a perfect information game
 consisting of public belief representations or public belief states, in theory, we could approximate a solution of any two player zero sum imperfect information game
 by running a perfect information or L plus search algorithm on a discretization of the belief representation.
 OK, so nothing stops you from simply taking this and running AlphaZero on this new thing on this new thing with the states being public belief states
 and the actions being descending around of these giant tables.
 You might have to discretize it as it says, but that's feasible.
 So you can think of constructing this game tree, but each node here is going to be a public belief state.
 Instead of a world state like an AlphaZero or like an info state, like we started these imperfect information games with.
 And then you can construct your tree down here and then, you know,
 but this is infeasible because these public belief states are just too large and the actions are also too large.
 There are so many actions. These are super high dimensional. So this is not feasible.
 And we're going to so they have to find a way to do this thing.
 But to to sort of do it in the domain of the original game.
 And that's the I feel that's the entire trick of this rebel paper is to take this idea.
 Let's do this search over the public belief states.
 But somehow this this thing down here, because what we need is we need the values of these.
 Right. If we figure out the value of this public belief state and the value of this one, right.
 This is of beta one. This is of beta two.
 Then we would know which action to take.
 And an action is this huge thing.
 But if we knew the values of these, we would know which action to take.
 However, this is not feasible.
 So we need to find a way to figure out these values using the original formulation of the game.
 And that's what they do in the exact next section right here.
 So they go on saying, however, as shown in the example above, belief representation can be very high dimensional.
 So conducting search is as is done in perfect information games would be intractable.
 They say, fortunately, in two players, zero sum games, these high dimensional belief representations are convex optimization problems.
 Rebel leverages this fact via conducting search via an iterative gradient ascent like algorithm.
 So I don't know what this sentence means that the belief representations are convex optimization problems.
 Maybe this is misformulated or I'm just not understanding it well enough.
 In general, this section here is a bit of a mystery to me.
 But I can sort of tell you what what I understand of it.
 OK, so they say rebels search algorithm operates on super gradients of the P B as value function at the leaf nodes rather than on P B S values directly.
 This is the first indication we don't want to work.
 We want to construct this search tree and at the leaf nodes, we need value functions right like in Alpha zero.
 Now, since we operate on public belief states, we would need value functions of public belief states.
 However, rebel finds a way to not do that.
 Specifically, the search algorithms require the values of info states for P B S.
 OK, so they find a way to connect the values of info states to the values of public belief states.
 And just as a reminder, an info state is a state that as it looks to one player that could have many different histories,
 a public belief state has all the info states that could lead to the public observation.
 So all the info states that you could be in right with all their histories here, basically a distribution over all these info states.
 That entire thing is one public belief state.
 Now, they are going to say we can determine the value of a public belief state.
 So the value of this is going to be equal to and we can somehow approximate this with the values of these things here.
 We somehow don't need the value of the entire public belief state.
 We connect this to the values of the individual info states.
 And that's I mean, that's done fairly easily because you simply sum over.
 So you can say the value of a given info state condition that you're in public belief state beta is simply going to be kind of the expectation over all the histories
 that could lead to this info state multiplied by the value of each history.
 Like you can have the value of a history given some policy and therefore you can approximate the value at a given info state.
 And this theorem one here is where they connect the value of a public belief state to the value of an info state.
 So they say for any public belief state, for the beliefs of player one and player two info states respectively,
 and any policy pi star that is a Nash equilibrium of the sub game rooted at beta.
 So now we root sub games at public belief states.
 This thing holds right here.
 So as you can see, this connects the value of the public belief states.
 This is what we sort of need in order for the search algorithm to work.
 It connects it to the value of an info of info states and info states are way lower dimensional than public belief states.
 So it connects it connects the value of this right here to the value of let's say this.
 Okay, this this might be an info state here s and the value it connects the value of the global public belief state to the value of this particular info state.
 And it does so via this term right here.
 So this term right here, this is just the unit vector in the direction of that particular info state.
 And this here is a super gradient of an extension of the value function to unnormalized belief distributions.
 As I understand it, this G is the gradient with respect to probably beta one if we care about s one to V one of beta, something like this.
 As I said, this is where I don't 100% see through it.
 But what I understand is that this connects the value of the public belief state this thing to the value of the individual info states that are part of this public belief state.
 So we don't need a value function for public belief states.
 We can simply get away with learning a value function for the individual info states.
 And that's what they do.
 So the only the learned part here in this algorithm.
 This is the first time we see like a neural network.
 Since rebel search algorithm uses info state values, rather than learn a PBS value function rebel instead learns an info state value function.
 So we're going to input a public belief state.
 Yes.
 And we're going to get value for each info state.
 We're going to get a value here.
 So we'll simply learn a value function as sort of a vector output.
 You could also input the public belief state and the info state and get out a single number.
 I guess that would turn out to be the same thing.
 Okay, so the info state value function directly approximates for each info state, the average of the sampled values produced by rebel at beta.
 So we're going to learn this in a sort of bootstrap fashion, like like Alpha Zero does it a bit like temporal difference learning.
 So what we're going to do in this algorithm is we're going to start out, then we're going to construct this sort of this sub tree.
 And we're going to do this in the discrete representation of the game.
 Now, that's the genius of the rebel algorithm.
 We're going to sort of evaluate these things in the discrete representation in the info state representation.
 And then we're going to be able to use what we find right here in order to determine the value of the next actions to take as far as I can tell.
 Okay, so that there is only one thing left to do.
 Right.
 We need to know how does how does this step here work?
 So we we said we want to do this tree search over the public belief states, but we can't.
 It's too cumbersome.
 Therefore, we can now we can evaluate values of a public belief state.
 But we still need to do to determine the policies.
 And that's where the self play reinforcement learning comes in.
 So bear with me for one second.
 This is going to kind of snap together all that we've looked at so far.
 In this section, we describe rebel and prove that it approximates a Nash equilibrium at the start of the game.
 A depth limited sub game rooted at the initial public belief state is generated.
 This sub game is solved by running T iterations of an iterative equilibrium finding algorithm in the discrete representation of the game, but using the learned value network to approximate leaf values on every iteration.
 Okay, so it might seem a bit a bit complicated, but we're going to do is we're going to here is what I think happens.
 And this is a bit unclear to me.
 We're going to take a any public beliefs that we find ourselves in.
 They call they tell the beginning of the game, but any any public belief state.
 Okay, so the public belief state is maybe here and it contains many different info states.
 Now, what I think happens here is that they may be sampling one of the info states.
 I don't know, or they may input the public belief states at the beginning.
 This is unclear to me, but then they're going to solve the game in the discrete representation.
 So they're going to use a classic solver to solve the game up to a limited depth.
 Okay, so this limited depth is going to be sort of D steps in into the future.
 This is going to be in the classic representation.
 So classic states and classic actions.
 Now, the solver that they use for this is counterfactual regret minimization.
 This is a solver that works with info states.
 Okay, so you can actually use CFR to solve poker.
 However, you can't solve all of poker because the game is too big.
 Right.
 So but you can solve a sub game provided that you have good value estimates here at the end.
 So that since they use CFR, that leads me to believe they don't use the entire public belief state as an input to CFR.
 But they either maybe sample an info state or they actually sample one particular history that happened.
 That is unclear to me.
 However, what they do is they they do this.
 They solve the sub game using CFR.
 And then out of that, they get a strategy.
 Okay, so here you ask your solver, what should I do?
 Given, you know, given my estimates of the values right here and the CFR will say, I know what you should do.
 Here is a strategy.
 Here is a policy that you should do.
 Now, if this were AlphaZero, if this were fully observable, then you would be done.
 Right. You'd say, okay, I'm done.
 Cool.
 That's what I'm going to do.
 However, what we saw above is that your values right here, your values down here, they are dependent on what comes before you.
 Specifically, they are dependent on this strategy.
 Okay.
 Now, CFR needs sort of an initial strategy.
 And it outputs a best strategy for the given values.
 But now that you have another strategy, these values here, they are no longer valid.
 And you computed the strategy with the values.
 So what you're going to do is you're going to plug in.
 You're going to use this thing to compute new values.
 Okay. More values.
 You're going to construct another or the same sub game with new values and then use CFR again to solve that.
 And that will give you the next policy for these values.
 But then the values change again and so on.
 Now, this is going to converge eventually.
 But you're going to have to run a couple of iterations of this for this to converge.
 In fact, I believe it's the running average or the average that's going to converge.
 But you're going to solve a number of these sub games, okay, until you reach the actual best strategy.
 And you're going to do that down the game tree.
 So from this thing, you're going to construct sub game.
 You're going to construct one, two, three, updating the values, solving it.
 And then once you have it, you sample some state in between.
 From that, you're going to solve the sub game again, one time, two time, three time, and so on until convergence and so on.
 So this multiple solving of the same sub game, that's what we have to do.
 So it is the price we have to pay for solving the game in the discrete representation because we can't solve it in the belief representation because it's too big.
 There, we would only have to solve it once.
 But here we have to solve it multiple times.
 So this is the entire algorithm right here.
 You can see while the while we're not in a terminal state, we're going to construct a sub game and initialize some some policy.
 And then for each step, we're going to do first.
 Sorry, we also set the leaf values.
 So this setting of leaf values, that's simply forwarding.
 Like if I know the policy, I can go set the leaf values using my neural network.
 Right. My neural network can tell me what the value at each of the leaf nodes are.
 That's what we train it for.
 So in the set leaf values, there is a neural network.
 You see this by the fact that there are parameters right here.
 And then we're going to do repeatedly the following two things.
 Update policy.
 So this here is where we use the solver CFR.
 So we determine the best policy given the current value estimations.
 And then we're going to set new values given the policy.
 So see CFR, it will take in the last policy and it will output the next policy.
 And set leaf values will in will take in these parameters, which meaning this here,
 that's going to be some kind of MLP or neural network.
 And we're going to do this.
 Then we're going to loop back again and do the same thing.
 Solve the game, set new values, solve the game, set new values, solve the game, set new values.
 Eventually, by aggregating all of this information, we are going to be able to compute the expected value.
 And that's going to be the value of the public belief state altogether.
 And as we said, if we know the value, we can sort of take the best action.
 In fact, here, I believe that the policy that comes out, this average policy is the Nash equilibrium.
 And we can simply sample an action from that.
 All right.
 That's what they describe here.
 They use we describe rebel assuming the counterfactual regret minimization decomposition CFR algorithm is used.
 This is a depth limited version of CFR.
 That's an entire research direction by itself.
 Right here.
 Counterfactual regret minimization is simply used as sort of the inner solver, kind of a helper function to call.
 And that thing by itself is an entire, entire algorithm.
 It's like a very complicated algorithm.
 OK.
 On each iteration, CFR determines a policy profile in the sub game.
 Next, the value of every discrete representation leaf node is set to this.
 And this is this is the neural network.
 Right. So we're going to use the neural network to set the leaf node values of the discrete representation.
 OK.
 This means that the value of a leaf node during search is conditional on the policy.
 Thus, the leaf node value change every iteration.
 Given pi and the leaf node values, each info state has a well defined values.
 This vector of values is stored.
 And next, CFRD chooses a new policy profile in the process repeats for T iterations.
 All right. That's the rebel algorithm.
 And they also describe how they actually sample data for learning with the exploration.
 And they also show that running algorithm one with T iterations of CFR in each sub game will produce a value approximator that has an error of at most this for any PBS that could be encountered during play.
 So they're going to say that the value approximator, given that it is sort of idealized, will actually converge to a good value approximator.
 If you sample it, depending on how many iterations of CFR you do.
 But you can see that the more iterations you do, the better of an approximation you get.
 And if you have a good value estimator, as we already said, you basically have solved the game.
 The last thing is that they determine now what do we do at test time?
 You might not have thought of this.
 This seems sort of obvious if you know alpha zero, but they determine that at inference time, you can simply run the same algorithm, except you don't want to produce training data from it.
 You don't want to learn anything.
 You simply want to run this algorithm too.
 If you run that algorithm at test time, that will actually give you a Nash equilibrium.
 So that's theorem three right here.
 If algorithm one runs a test time with no off policy exploration, value network with error at most, this and this, and was trained as described in theorem two, with t iterations of that,
 then the algorithm plays this kind of approximation Nash equilibrium, where C1 and C2 are game specific constants.
 So you can see right here that the Nash equilibrium is going to be perfect depending on how many iterations you do.
 And depending on, I believe, how accurate your neural network is.
 Yes, your value network error.
 If you make that smaller, your Nash equilibrium is going to be better.
 Pretty, pretty cool.
 So that was the algorithm.
 They do a bunch of experiments where they see what kind of network they use, if they use the value net or not, if they use self play or not.
 And they can also introduce a policy net, I believe, for initializing or searching more effectively.
 They compare against previous things like DeepStack, Libratus and so on.
 They do beat top humans, as you can see.
 Poker has been for a long time kind of an not so solved game by machine learning.
 But this area has been over for a while right now.
 And they do release the code of, I believe, of the Liar's Dice.
 So they have the code released for Rebel and the implementation for Liar's Dice, but not for Poker, because that's what they discuss in the broader impact statement.
 So let's quickly look at broader impact.
 Then we're done.
 So just to say I love this broader impact statement.
 It is, it describes like it praises the paper.
 So it's kind of more advertisement for the paper.
 It does almost like no harm to the paper itself, to its reputation.
 It is actually accurate.
 So this broader impact statement actually makes tangible predictions and it doesn't go beyond the or it mostly doesn't go beyond the tangible things you can say about this algorithm.
 And it actually has as a conclusion an action that they take.
 So and further, it is nothing like what the original specification of broader impact statement says.
 And that makes me happy.
 So good job on this one.
 We believe Rebel is a major step towards general algorithm finding algorithm, yada, yada, yada.
 So they say if this is this is good because many things are sort of these kind of games.
 If you can extend it to multi-agent and so on.
 So this is the technology good section.
 But then the bad section is interesting.
 The most immediate risk posed by this work is its potential for cheating in recreational games such as poker.
 While they are algorithm already exist, they say why they are better.
 Why this particular algorithm could be used for cheating where the others can't be done so easily.
 By the way, this algorithm by nature of performing the searches over and over again, it needs a lot of compute.
 Like it needs a lot of compute.
 The learning isn't the problem.
 The problem is performing these searches over and over and over again.
 Yeah, so it's not super easy to replicate.
 Like don't don't try this at home.
 However, if they were to release the pre-trained network, that would make it easy.
 And they also say if they release the code, that would maybe make it easier to cheat.
 If you can simply run maybe, you know, you don't have the hardware, but given made massive poker winnings, who knows?
 Retraining the algorithms to account for arbitrary cheat size requires more computation as feasible in real time.
 That's about the other algorithms.
 However, Rebel can compute a policy for arbitrary stack size and arbitrary bet size in seconds.
 So that's at inference time.
 Partly for this reason, we have decided to not to release the code for poker.
 We instead open source our implementation for Liar's Dice, a recreational game that is not played competitively by humans.
 OK, so it's a concrete prediction of the impact of this work.
 It has a concrete action to kind of its conclusion.
 And it doesn't dabble in who knows if we now solve these two player imperfect information games, then surely in the future bombs will fly and stuff like this.
 Yeah, good job on this again.
 All right. So this was the overview of the paper.
 We started with the notion of info states and info states are kind of like states in classic reinforcement learning.
 And we determined that we can't really use the sort of Alpha Zero way of doing things because the value of info states not only depends on downstream things, but also on upstream things.
 And the values here, yeah, that makes the values at the end of the tree not constant.
 And that means we can't really use that as we saw in this poker thing.
 Then we converted the game from an info state representation to a public belief state representation, where now it's sort of it's again a everyone knows everything game.
 Therefore, we could use the Alpha Zero way of doing things.
 However, since these states and the actions are so large because it consists of these giant tables of numbers, we can't use the Alpha Zero for computational reasons.
 Luckily, they find a way to connect the value function of public belief states to the value functions of info states, and therefore we can use a solver in the classic in the discrete representation to approximate or to to to use in this search procedure.
 As long as we run it multiple times and sort of keep updating its values.
 By doing that, we can use this in this self play, simply iteratively doing this in each step.
 And we can use bootstrapping and play as we said self play between two agents, and that will provably converge to a good value function and to a Nash equilibrium.
 All right, that was the paper. Thanks for listening. I'll see you next time. Bye bye.