Episode 28: Reinforcement Learning and Q-Learning

• Links to this episode: Spotify / Apple Podcasts

Unofficial, reviewed transcript. It may still contain mistakes; check the podcast when wording matters.

Speakers are labeled by first name where identified. Unidentified-speaker labels may refer to different people. Bracketed question marks indicate uncertain wording.

Transcript

[00:00:00]  Bruce: A warning for Theory of Anything podcast's audio listeners. This episode is mathematically really quite heavy. And the reason why is because I'm going into the theory of reinforcement learning, which requires me to go through the proofs and the mathematics to explain how it works, et cetera. So the audio version's gonna be a little bit harder to follow, and in fact, I cut out the proof in the middle, and I just explain it in the audio version. And you don't really get into it as far as if you go to the YouTube version where the visuals are available and it's easier to follow. But this episode in general may benefit from actually going to the YouTube channel and viewing it rather than just listening to it. But it should still be that you can get the gist of what we're talking about and how the theory works by being able to listen to the episode.

[00:00:50]  Bruce: All right, welcome to The Theory of Anything podcast. How's it going, guys?

[00:00:54]  Cameo: Great, Bruce, happy to be here.

[00:00:56]  Tracy: Yeah, going great.

[00:00:57]  Bruce: So today we're gonna talk about Reinforcement Learning. And both of you have seen this presentation at one point or another. But I, and I have to warn the people who listen to this podcast versus the ones that see it on YouTube, this one's got some important visuals. So if you really wanna understand what we're talking about, you're gonna have to go to the YouTube version so that you can watch the visuals. But I am gonna try to still describe things in such a way that even if you're listening to it, you can get the gist of the theory that is being explained. And I feel like this is a really important theory to understand based on future podcasts that we're gonna be doing and talking about, such as an upcoming podcast on animal intelligence. So understanding what we currently know about machine learning and reinforcement learning and how it differs from what animals do really ends up being kind of an important point.

[00:01:54]  Bruce: So I wanted to make sure that we did do an episode on reinforcement learning. We'll do one today and then we'll also do the AlphaGo one that we've been talking about doing so that we've kind of covered the material fairly well. But I feel like the mathematics and the theory and things like that, they're just an important part of trying to make sense of a lot of these other theories. So I feel like this is still an important topic. And so I've decided we're going to go ahead and we're going to do it, even though it may require some people going to the YouTube version. So reinforcement learning is a kind of machine learning. And if you can see the screen here from the recording, I've got a picture of Lee Sedol playing AlphaGo and this is, for those of you who've seen the movie, have you both seen AlphaGo the movie?

[00:02:46]  Cameo: Yes. Fantastic movie.

[00:02:49]  Bruce: You probably recognize that image right there. So you've got Lee Sedol, who's the world champion, who is playing AlphaGo. And then you've got one of the programmers from the AlphaGo team who is doing the moves that AlphaGo tells him to make. And the two of them play against each other. It's interesting. So Lee Sedol keeps trying to read the guy across from him and then remembers he doesn't know anything. And so he's trying to read his face, which is a natural part of playing Go. And he can't because the human he's playing against doesn't know what he's doing. It's actually the program that he's following that knows what it's doing. And so there's a lot of interesting things that kind of came out of this showdown between AlphaGo and Lee Sedol. And I highly recommend AlphaGo the movie. It's free on YouTube. AlphaGo utilizes Reinforcement Learning.

[00:03:44]  Bruce: And that was the big breakthrough that allowed AlphaGo to come into existence. So why is it that Reinforcement Learning was different than other types of machine learning, that it allowed us to finally make a professional level, world champion level go playing program? And we're gonna talk about that today. And it's very interesting how this theory relates to playing go. So just as a reminder, we covered some of this in our past episodes on artificial intelligence. There's roughly three kinds of machine learning. There's supervised learning, there's unsupervised learning, and there's reinforcement learning, which combines some of the attributes of the other two, but really it's kind of its own thing. So supervised learning, just real quick, imagine that we're trying to make a program that takes number of square feet, a number of bedrooms, and predicts the sales price for a house.

[00:04:49]  Bruce: So the features would be the square feet and the number of bedrooms, and the sales price is what we're trying to predict. So we take real values in real life, we feed in how many square feet there were, how many bedrooms there were, and what the actual sales price was. In this case, it's going to do a simple linear regression, where it tries to match a line to those points that exist. And the end result is that it can now make fairly good predictions. Whereas if you take a house that's for sale, that's never… Hasn't sold yet, and you say, this is the number of square feet and this is the number of bedrooms, it will give you a prediction. You should expect to sell it at this sales price, and it will be somewhat accurate. Now in real life, you'd never want to do this based on just square feet and number of bedrooms. The reason why I held it to two features was because otherwise it was more than two dimensions, and I wasn't able to show it on the screen.

[00:05:46]  Bruce: You'd probably want to put location in there, probably a whole bunch of other features in real life. But this should illustrate exactly how supervised learning works. The key points are that a human gives it correct values, and then it learns a model, and then that model can be used to predict future values. Okay. Unsupervised learning is different than that. You've just got a whole bunch of data points, and you say, like in this case, k-means cluster, you'd say, give me three clusters, and then it finds three clusters. So you can see the original data points, which are a big blob. And then you can say, give me three, you have to tell it how many clusters, unfortunately, but say, give it three clusters, and then it finds three reasonable clusters out of that data there. And then if you're trying to sell stuff, maybe these are clusters of customers that have similarities in how they purchase things and what their interests are or something like that.

[00:06:44]  Bruce: That might be valuable for a recommendation engine, for example. So in this case, the key thing is that there's nothing being input from a human. There's no input of what the correct answer is. It's just simply trying to find patterns in existing data as it is, without a human telling it what a correct answer is or even that there is a correct answer. Now, Reinforcement Learning, how does it differ from those other two more kind of popular kinds of machine learning? So the characteristics that really separate Reinforcement Learning from other kinds of machine learning is the existence of exploration, delayed rewards, and continuous learning. So similar to supervised learning, there are… The rewards for correct behavior work somewhat similar to giving a correct value to like in supervised learning, where we were giving the value of what the house actually sold for in our example.

[00:07:41]  Bruce: It's really kind of different, but you can see that there's something analogous about it. It's similar to what they call a loss function, where it's going to try to minimize how far off its predictions are from the correct values. It's similar to unsupervised learning, in that you have no correct result to work with. It just simply tries to learn to maximize the rewards that it's receiving. However, it's not… It's tempting at this point to say, it's like in between supervised and unsupervised learning. But there is actually a kind of machine learning called semi-supervised learning, which is literally in between supervised learning and unsupervised learning, where you give it a few data points from a human, and then it has to learn from data that doesn't have labels that a human put on it. So Reinforcement Learning isn't really in between the two.

[00:08:31]  Bruce: It's kind of its own thing. It just happens to have some characteristics similar to the other two, but it's kind of just its own thing. So why is it that Reinforcement Learning was able to beat the Go Master, the world Go champion, when other kinds of artificial intelligence failed to do so? So now this is an interesting thing, and I don't know how much you guys, I mean, like maybe I was just more into this when I was young, but I remember way back, probably as far back as the 90s, people were talking about, like on the news, you might come across something like this. They would talk about how we're very close to having an artificial intelligence algorithm that can beat the chess master, who at the time was Garry Kasparov. And they believed we were close. Right up to that point, we had never made a chess program that could beat a world champion in chess.

[00:09:30]  Bruce: But they felt they were close to it. And then a few years later, it happened. Deep Blue, IBM, they actually did create a program that could beat the world champion chess player.

[00:09:41]  Cameo: Yeah, I remember that well.

[00:09:43]  Bruce: Okay. And they used to always say, but Go, Go is some people call it Chinese chess, but they're really nothing similar between chess and Go. But it's the strategy game that's popular, been popular in China for, I don't know, centuries, maybe even millennia. I'm not sure how far back it goes. And they used to say, it would not be possible to make a program that can beat a Go master. To do that, they used to always say this, would require artificial general intelligence. I don't think that term existed back then. Would require true artificial intelligence, is what they used to say back then. Because it is not something that the existing chess-playing algorithms can do well. And there's no real hope of it ever scaling up what we're currently doing to be able to beat a world champion for Go. And so there was, and I heard this like multiple times on the news back then.

[00:10:38]  Bruce: And they always talked about how it would require real intelligence to beat a, to be a Go champion. And it just isn't the same as chess. So let me explain why they thought that. Now, clearly the fact that now AlphaGo has beat the Go champion, that happened only, I don't know, a decade later or something, right? It wasn't a long time. They thought it would be like hundreds of years and we would have to create AGI first. Clearly that prediction turned out to be wrong. But why were they making that prediction? And for that matter, how is it that they knew that they were close to beating the World Chess Champion, but they didn't think that they were anywhere close to beating the World Go champion? Well, there's a really kind of a good reason, even though it turned out to be a false reason. And I think there's something interesting to learn from this.

[00:11:26]  Bruce: So the algorithm that beats, that plays chess is the minimax algorithm. And we talked about that in our artificial intelligence podcast episode. Basically, it just tries to play as many in its, you know, in the computer, it simulates out every possible move. Then it simulates out of each of those moves, what its opponent might do if it's trying to win. And then it simulates out from each of those what it might do back. And it just tries to look as far, as many moves forward as it can. Now, obviously, this would be an exponential growth. Okay, of different possible moves. So even with the most powerful imaginable computer, you can't look that many moves ahead. It's just an intractable problem. So like, if I were trying to program this, and you were just kind of doing a straight, naive way of doing it, you'd be lucky to get, say, five moves ahead.

[00:12:25]  Bruce: And a world champion can, in their mind, think more than five moves, five or more moves ahead. Now, the reason why a human can do this and a computer can't is because humans are awfully good at calling out things that don't matter, whereas the computer has to kind of go try everything. And that turned out to be one of the main things that they did to improve chess play, is they came up with algorithms that allowed the minimax algorithm to call out moves that weren't promising, so that it could start to look ahead, say, 13 moves or something like that, which now at this point, no human can look ahead that far. And so now it's going to be able to beat any human. And one of the main things that allows it to do that is not just intelligently calling things out, but just having a lot of memory. And so as computers got more powerful, they would throw more and more memory on there.

[00:13:17]  Bruce: They would be able to look forward further. Now keep in mind that this is exponential growth of moves. So even though Moore's Law is an exponential growth of power of a computer, you only end up with linear improvements. Against something like the minimax algorithm. Because it's an exponential problem and exponential growth of computer power. You get linear improvement. Does that make sense that that would be the case?

[00:13:39]  Cameo: Yeah, absolutely.

[00:13:40]  Bruce: So each new generation of computer can't go that much further than the previous one. In fact, maybe you'd have to double several times before you could even go one more move further with the minimax algorithm. The other thing that they did with Deep Blue is they had a really clever board evaluation algorithm that was hand coded by a human. So what's a board evaluation algorithm? Well, since you can't play the game all the way to its end, that's just exponentially impossible. What you do is you play forward a number of moves and then you evaluate the board for each of those moves and you say, okay, how good of a board position is this? And if you've got a good algorithm that tells you how good of a board position that is, then you don't have to go any further. You can say, oh, I just found a really good board, this is the best board position I've been able to find in my search, I'm gonna make the move that gets me towards that board position.

[00:14:31]  Bruce: So how might you go about coding a board evaluation algorithm for chess, do you think? Come up with a really bad one, just something that gives a feel for how it might be done.

[00:14:47]  Unidentified speaker: I don't even know if I can come up with a bad one, Bruce.

[00:14:51]  Bruce: Are either of you into chess at all?

[00:14:54]  Unidentified speaker: Not really.

[00:14:55]  Tracy: I'm not great.

[00:14:56]  Bruce: I'm not either. I'm not into chess. I remember, though, when I was a kid, I'd buy books on chess just because I thought it was a cool game. And one of the things they teach you is to count a number of points per piece. So a pawn's worth one point, and I can't remember exactly, but it's like a bishop and a knight is worth, I want to say, three points, and a rook is worth five points, and a queen is worth eight points. There's something along those lines, right? So you have to take eight pawns to make one queen be worth it. And it's kind of this rough heuristic that they use to try to evaluate if a move is worth it or not. Well, you could do something like that to evaluate a board, right? You could say, well, if I make these moves, the final board, I count the number of points for one side versus my side. I'm now ahead. That's the one I would want to make.

[00:15:52]  Bruce: Now, by itself, this would not be a particularly good board evaluation algorithm. It would probably work okay against an amateur. You would probably want to do more than that. You would probably want to have some way of, I don't know, evaluating the danger that your queen is in. I mean, I don't know exactly. One of the things is that to make this really work, there's a trade-off that takes place. You need your board evaluation algorithm to be really fast because if it's slow, you can't look ahead very many moves anymore because now you have to perform that board evaluation for every single possible move you consider. Having a quick and dirty board evaluation algorithm actually may outperform a really intelligent board evaluation algorithm. They have to come up with something that is both intelligent and fast. That's what they did for Deep Blue.

[00:16:43]  Bruce: They came up with, and I don't even know what it was, but it was something very clever that allowed them to evaluate boards well, while still being fast enough that it could look ahead 13, 20 moves on some search paths until it was just able to beat any human. And this is how you would do a chess program. Now, why would this not work for Go? There's a couple reasons why. One of them is that the number of possible moves in chess is much, much smaller than the number of possible moves in Go. So the branching factor, that's what they call it, for Go is much higher, and so it explodes exponentially much faster than it does for chess. If that were the only problem, I don't know if that would be a problem on its own. The second problem is that there's no really well-known board evaluation algorithm. So unlike chess, where you can count the number of points for the pieces or something like that, where there's well-known heuristics that exist that are easily computable, Go masters use their intuition.

[00:17:50]  Bruce: So they look at the move and then their intuition after playing hundreds or thousands or whatever games, they've built an intuition for this board position is better than this one, even if they can't explain all the time. It's often inexplicit knowledge. They can't explain why that board position is better. And the reason why that's necessary is because Go can switch really fast. Like you can have a good board position and then some other move can wreck it. And so it's unlike chess where you're clearly ahead or behind based on which pieces you have, there's just nothing like that in Go that you can hold on to. And so Go masters have to, it's basically just human intuition that you build up over time. And that was why they thought Go would require artificial general intelligence is because they thought how in the world do you program into a computer intuition?

[00:18:45]  Bruce: Is that even possible to program into a computer intuition?

[00:18:48]  Cameo: We don't even really know what intuition is, right? I mean, it's an interesting word because if you ask someone to describe intuition and what it means for us, we don't really know that.

[00:19:05]  Bruce: So how would you try to describe intuition? Take a stab at describing intuition.

[00:19:09]  Cameo: I would say it's a gut feeling that can't be validated by any facts.

[00:19:19]  Bruce: Okay, that's probably, I think a lot of people would agree with you on that. Do you have any difference of opinion there, Tracy?

[00:19:24]  Tracy: No, I actually think that was a great way to explain it. I would have to agree.

[00:19:28]  Bruce: So here's the big secret that I don't think people understood back in the 90s. Carlos Perez is an AI machine learning researcher that I'm connected to on Twitter, and we talk once in a while. He has a book called Artificial Intuition. His argument is that machine learning isn't artificial intelligence, it's artificial intuition. I think that's exactly accurate. Machine learning, as we learned from our past podcasts, we're not quite sure how it comes up with what it does. It creates this function, it's heuristics. It doesn't necessarily have a good explanation for how it does what it does, but it somehow figures out how to do a computation that can say recognize a face with some high degree of accuracy. Or for that matter, you can use it to build an artificial intuition for what is a good board position in Go. And that is what they did. So the difference between AlphaGo and Deep Blue, Deep Blue is what's known as artificial intelligence.

[00:20:37]  Bruce: There's no learning algorithms in Deep Blue. You can let Deep Blue play itself as many times as you want, and it will never get better at playing because all it's doing is a minimax algorithm with a clever human-built board evaluation algorithm. It never changes or updates or gets better at what it's doing. AlphaGo, its board evaluation algorithm wasn't coded by a human. It was machine learning, specifically reinforcement learning, and it simply developed exactly like a human intuition as to if I make this move, the board will look like this, and that's a better board position than if I made this move. And it doesn't have to, it's based on, we'll see how it works, but it's based on machine learning, and that's what machine learning does. It comes up with heuristics that work like this, which are very similar to the way people describe human intuition.

[00:21:33]  Bruce: In fact, I've wondered if human beings, when we talk about intuition, if we don't have something like machine learning algorithms that we utilize. That may not be true, by the way, but there seems to be something similar about the way we use our intuitions and the way machine learning works. We know there's still some really big differences too, like human intuition. You think about the number of games that a Go master plays to gain that intuition, and it's far fewer games than the billions of games that reinforcement learning has to play to get an equivalent intuition. So now we know humans also have explanatory knowledge, whereas machine learning doesn't. So undoubtedly there's a difference there, where what a human's doing is actually a combination of intuition and explanatory knowledge, where they can explain some things to themselves and some things they can't.

[00:22:26]  Bruce: So they can learn faster than a computer can because of that. And I'm not even sure what it is I just said. What I said is an accurate statement, but what is explanatory knowledge and how does it interact with intuition? No idea. That is a huge mystery at this point.

[00:22:43]  Cameo: Well, and you said something, you said humans use their intuition. I don't think that that's, you know, people don't think about, I'm going to use my intuition right now. If anything, it's kind of the opposite. The intuition happens and people decide whether or not to pay attention to it. Or whether they're going to revert back to only dealing with the observable or what we conceive of as being, you know, reality versus, oh my gosh, my stomach, my gut says I should do this contrary thing.

[00:23:20]  Bruce: Yes. By the way, have you guys ever heard of The Second Brain, the book, The Second Brain?

[00:23:25]  Cameo: No.

[00:23:26]  Bruce: I haven't read the book, but I had a friend who told me about it. It's a book I probably should read. People don't know this, but the digestive tract has almost as many neurons as the brain. So the digestive tract actually is a second brain of sorts. And so the idea that you go with your gut might be literally true in terms of how intuition...

[00:23:51]  Tracy: Oh, right, right. The second brain.

[00:23:54]  Cameo: That's certainly true when I'm hungry. That sounds like a potentially interesting topic for a future podcast.

[00:24:04]  Bruce: Yeah, we'll have to read that book and then talk about it. I should probably note it might also not be true. So it's... I would like to see what evidence that he comes up with and why he's making that argument, or if this is just one of those things where he's come up with something that's interesting, but there's no real truth to it, which happens all the time. But I just thought I'd throw that in there, just kind of an interesting side note. So this is what separates AlphaGo from Deep Blue. AlphaGo is machine learning. It learns. It learns by playing itself. Initially, it learned by looking at human games. So they would take champion human games and put it into AlphaGo, and it would learn from those games. They later got rid of that, and they just let it play itself so that it was learning from the ground up how to play Go well. And the final version of AlphaGo, the one that is used today that can beat anybody, it's the version that just plays itself.

[00:25:03]  Bruce: It doesn't even use input of human champion games anymore. And that machine learning component with the board evaluation algorithm with this artificial intuition that it uses, it is so good that AlphaGo can be changed to look ahead only one move, and it can play at professional levels. Probably couldn't beat the world champion that way, but it can play at professional levels because the board evaluation algorithm is just that good.

[00:25:32]  Cameo: Wow. That's pretty impressive.

[00:25:34]  Bruce: Yeah, it is. So, okay. So now, how is it that reinforcement learning is able to do this? So now we're going to talk about the actual theory. So to understand reinforcement learning, we have to talk about something called the Markov decision process. And now we really are going to be digging into just outright theory. This is the graduate level stuff that they taught me in school. Okay, so they first want to define what the Markov decision process is. So let me give you kind of just a quick layman's overview, and then we'll get into the specifics. The idea is that you take the state of the world and you don't look at its history. You just take the state of the world as it is now. And the theory of Markov decision processes is that you don't need any history to be able to tell what the next state of the world should be. Now, is this actually true?

[00:26:29]  Bruce: Well, we know that the laws of physics, at least the current way we think of the laws of physics, ignoring constructor theory for a moment, that the prevailing conception is that you've got these particles, they got an initial condition that they're going to be moving. If you knew every particle in the universe and you knew what its momentum and whatever is, then you would know what the next state of the universe is going to be. This is Laplace's demon. This is something that's very old in philosophy. So at least our current kind of Newtonian and even general relativity, the way we, or even quantum physics for that matter, the way we conceive physics today is actually as a Markov decision process. So that's at least somewhat promising as to why Markov decision processes might be valuable. Now in real life though, trying to take a problem, even if in principle every problem could be put into a Markov decision process, trying to actually do that in real life is hard.

[00:27:29]  Bruce: And there are many problems that would be very tough to solve as a Markov decision process as of today. If you think about it though, let's say that there was something important about your history that you wanted to track. What you can do is you can promote it to be part of the current state of the world. There's no reason why you can always do that [wording unclear]. So like if you need to know what was true three moves ago, you simply make part of your current state of the world a history from that piece of information from three moves ago also. So in some ways, this is why we suspect everything can be put into a Markov decision process, but it's just very difficult. It may even be intractable in many cases. But that's why it became of interest. Bellman, the famous Bellman, I don't know if you guys have heard of him or not, but his name comes up all over the place.

[00:28:21]  Bruce: He's the one who figured out a lot of these things and the theory on how to solve the Markov decision process. Markov is a famous scientist also from Russia. So the way they describe the Markov... So the key thing about the Markov decision process though is the Markov assumption, which is that you're only using the current state, none of the previous states. And then, so they would define that as S, which would be the states the agent can be in, and it would actually be the state of the whole world or at least the whole world as far as it understands the whole world. I'll explain the difference between those in a second. A is the set of actions the agent can take, and then at time T, the agent senses current state ST. So S is state and T would be the state at time T. Does that make sense? Nothing too fancy here yet, really, despite the notation.

[00:29:14]  Cameo: Yeah.

[00:29:15]  Bruce: And then the agent takes action AT, which would just be the action it takes at time step T. Okay. That represents the state of the world and what is the possible actions the agent can take. The environment then gives reward RT, which would be the reward at time T, in response, and then moves the agent to state ST plus one. So you're at time T, the state of the world is ST, you take action AT, you receive reward RT, and then suddenly the state of the world is now ST plus one, which just means the next time tick. For the sake of argument of making this a little more concrete, you're a robot, you've decided you're going to take action to move north. So the state of the world then gets updated to where the robot is now further north than it was before. Okay. Fairly simple, actually. The environment then could be thought of as containing two functions.

[00:30:15]  Bruce: One would be what we call the state transition function, and one would be what we call the reward function. So the state transition function, I've got a little, I don't know why they always use Greek characters, but we've got this little Greek character there. That's just the function. We could just call this state transition function instead. You pass to it two parameters, the state of the world at time t and the state of, and which action you're taking at time t, and it returns the new state of the world, whatever that is. Okay. And then you've got this other function, the reward function, where you pass to the reward function the state of the world at time t and the action you take at time t, the same two parameters, and it returns whatever reward the environment gives back to you. Okay. So for the sake of argument, we have the robot, it wants to move north, and when it does, it reaches its goal, so it is now in the goal state, and it receives the reward for being in the goal state.

[00:31:12]  Bruce: Does that make sense?

[00:31:14]  Cameo: Yeah, absolutely.

[00:31:15]  Unidentified speaker: Okay.

[00:31:16]  Bruce: All right. So that's the Markov decision process in a nutshell. So let's actually do a concrete example now. This is going to be helpful to have the YouTube version to see this. I'll try to describe it, though. So we've got a maze. I call it a maze, but it's not really a maze. What it really is, is it's a 3x3 grid with no walls at all, and you start in the lower left-hand corner, and your goal is to get to the upper right-hand corner. And so how would you get there? It's a 3x3? Well, one way, you might move up twice and then move to the right twice, or you might move to the right twice and then move up twice. Okay, that's all we're asking our robot to do, is to figure out that one of those two paths is the shortest path. It can even get to the goal a bit slower if it just wanders around until it happens to hit the goal, right, and then it would still receive the reward of 100.

[00:32:06]  Bruce: So any path to that goal will work, although as you'll see, we'll have a preference for how do we make it so that it finds the shortest path. So how many possible states are in this world? This is called a grid world. How many possible states are there in this world?

[00:32:24]  Cameo: 28.

[00:32:28]  Bruce: Okay, tell me how, so I actually want to hear your thinking. How would you go about counting states? And by the way, there's actually more than one possible correct answer. There's one answer that's particularly simple though. So describe your thinking on this. How would you come up with the number of states that this world has?

[00:32:48]  Cameo: You count the boxes?

[00:32:51]  Bruce: Okay, that is by far the simplest way to do it.

[00:32:54]  Tracy: Yeah, that's what I was thinking, just count the boxes.

[00:32:56]  Bruce: How many boxes are there?

[00:32:57]  Tracy: Except for start.

[00:32:58]  Bruce: Yeah, that's how you do it with eight is except for start. We would actually want to count start also. It would be nine. In fact, you may not count goal. So maybe it would be eight if you don't count goal, but it depends on how you implement it. How many actions are there possible for our agent here? And again, there's more than one possible correct answer here.

[00:33:16]  Tracy: It seems like it could be limitless because it can double back on itself forever before it gets to the goal. I'm thinking.

[00:33:22]  Bruce: Okay, let's make this a little simpler. If you're in any one given state, what are the possible actions?

[00:33:28]  Cameo: You could move forward or you can move back.

[00:33:31]  Bruce: Okay, so that's two. Seems like you're counting rotation. So there would have to be some way to rotate too. If you can move forward and back, correct? So that you can move up and to the left and to the right.

[00:33:43]  Cameo: Oh, that's a good point. You would need a step could be to turn one direction or turn the other direction.

[00:33:49]  Bruce: Let's simplify this for the sake of making it simpler. You don't need to rotate. You can just simply move from one square to one that's next to it. How many possible moves are there now?

[00:34:01]  Cameo: I don't know exactly what you mean by next.

[00:34:08]  Bruce: If you're at the start, how many squares are there next to you?

[00:34:11]  Cameo: There's two squares. Well, three squares if you count the… Two squares.

[00:34:18]  Bruce: Two that are directly next to you, and then a third one if you count the diagonal. Now, why is that though? There's only three possible moves, only two if we don't allow diagonal moves, but that's because the start square is at the bottom. Okay, let's say you were in the middle square. How many possible moves are there?

[00:34:39]  Cameo: One, two, three, four, and we're not counting the diagonal? Four.

[00:34:44]  Bruce: Do it both ways. Give me both answers since they're both good answers.

[00:34:48]  Cameo: Four if you don't count the diagonal, and eight if you do?

[00:34:52]  Bruce: Yeah. So for the sake of making this very simple, we're going to not count diagonals, although that could be legitimate. There's no reason why we shouldn't count the diagonals. It's just we're going to happen to program it that this agent only has four possible moves. So there's nine possible states, four possible moves. And in fact, we're going to make this even simpler. If you're in the start state, as you pointed out, if you don't count diagonals, there's only two possible moves. We're going to still allow it to move in the two illegal directions. It's just that the transition function is going to leave you in the start state. Okay? So you can move down from the start state, and you just wind up back in the start state again. Or you can move to the left in the start state, and you just wind back up in the start state again. Therefore, every single square has four possible moves.

[00:35:37]  Bruce: It just simplifies the programming. Does that make sense?

[00:35:40]  Cameo: Yeah, it does.

[00:35:41]  Bruce: Okay. So here is how we might do it. I didn't show the ones that go off the screen. Just imagine they're there. But here is the maze, and here are the four possible moves from each square. So this is our states and actions put into a graphical format now. You've got nine states, you've got four actions, and I'm showing you what it looks like on an actual grid world. How might you code that? Well, you could do something like this. You could create a table in memory, and it lists out every single combination of states and actions. So state one, go right. State two, go down. State, sorry, state one, go right. State one, go down. State two, go right. State two, go left, et cetera. You'd want to do all four. I had to fit this on the screen, so I cut out the ones that would just loop back to where you were starting. And then notice that I'm showing that if you're in state one and you go right, you wind up in a new state, state two.

[00:36:45]  Bruce: That's just a table. State equals one, action equals right, new state equals two. And this table represents the state transition function. It is the state transition function. Can you see that that is the case?

[00:36:58]  Cameo: Yes. Yeah.

[00:36:59]  Bruce: Okay. What would, so based on that, how might we make a very simple reward function? Remember that state three, the upper right-hand corner is the goal. What might a reward function look like? Use a table just like we did for the state transition function.

[00:37:15]  Cameo: This is a lot harder than I thought I was going to have to think today.

[00:37:19]  Tracy: I want to look at the formula again, so I can try to figure that out.

[00:37:25]  Bruce: The formula is very simple. You score 100 points if you make it to state three, otherwise you don't. All right, I'll give it to you. How about that?

[00:37:33]  Cameo: All right.

[00:37:34]  Bruce: So you just list the states, and if you're in state three, you get 100, otherwise you score zero. Does that make sense? Is that exactly equivalent to scoring 100 if you make it to state three?

[00:37:44]  Unidentified speaker: It would appear so.

[00:37:46]  Tracy: I guess I’m not getting if state three was… We are implying that it was still 100% based on the previous screen where it was saying state three is just arbitrarily 100.

[00:37:55]  Bruce: Yeah, that's the goal. You're trying to get from state seven, the bottom left-hand corner, to state three, the upper right-hand corner. So you score 100 by getting to state three. So this is the reward function. It's literally that simple. It just lists out nine states, and it says that for each state, you get a reward of zero except for state three, and you get a reward of 100. Now, in real life, this isn't the best way to do a reward function. You'd probably want to actually do this, where you do a reward of negative one for every state except for state three, and then that's 100. The reason why you'd want to do that is because you want it to feel a little bit of a penalty for not having arrived at the goal yet, so that it has natural incentive to try to find the quickest path to the goal. So in terms of just smart programming and making it so that the agent learns quicker, giving it a negative one reward for every other state except the goal state just makes sense because it's going to learn faster that way.

[00:38:58]  Bruce: For our purposes, though, that complicates the math, so I'm going to still use zero. Zero would still work in real life. It just would learn slower. But just wanted to kind of note that you'd probably want to actually have a slight negative penalty for any state that isn't the goal state. All right. How would you solve this problem? Well, what you really want is you want to create an optimal policy. So what is an optimal policy? Well, I've got a picture of what one looks like up on the screen. Basically, what this is, is it's the three by three grid, and no matter what state you're in, it tells you which direction to move so that it is the quickest way to the goal from that state. So whatever state you find yourself in, you always know what the best possible move is. Now, in this case, there's actually two best possible moves. It doesn't matter.

[00:39:50]  Bruce: We just want it to know at least one of the two most optimal moves. Okay. So can you see that that is an optimal policy? So it knows every single state in the world, and it knows exactly which is the best action in that state to try to get to the goal as quickly as possible.

[00:40:06]  Unidentified speaker: Yeah. Look at that. Yeah. Yeah.

[00:40:09]  Bruce: The way you would create this in real life is using something called dynamic programming. Now, it's interesting. Dynamic programming sounds like it's some sort of type of program, computer programming, but the term dynamic programming predates electronic computers. Back in the early days, a lot of people don't know this, but the term computer originally referred to a bunch of people, usually women, who would do computations. They would all stand around, they'd have note cards, and they would pass the note cards to each other, and they would have a rule that they're following, and they would do the computation based on the rule that they're following. They would do it very quickly, and then they would pass the card to the next person. And basically, it was a human computer. And this is how people did computer computations back before electronic computers existed.

[00:41:06]  Bruce: And these women would get really good at it, and they could very quickly pass the cards from each other, do their computation. Each of them does one simple computation. They pass the card to the next person, and they could perform all sorts of computations quite quickly by doing that. And you would end up with basically a program where you set up each of the women to have the one step they need to do. Maybe it's like an if-then statement or something like that. Each of them would perform that statement, and they would do it very quickly, and you'd end up with the result you needed at the very end. And that's where the term computer comes from, is from these women who were computers. And when they started to invent the digital computer, the electronic computer, it was an analogy to what these women did, that now you have this device, this machine, that can perform the same types of computations that these women could.

[00:41:59]  Bruce: So they started calling them electronic computers or digital computers, until eventually the term only meant that, because there was no longer needs for this profession anymore. It disappeared. And once that disappeared, the term came to mean only the electronic type of computer. The term dynamic programming comes from the era prior to the electronic computer. So the programming involved would be with these human female computers that they would use. Does that make sense?

[00:42:27]  Unidentified speaker: Yeah. Yeah, it does.

[00:42:30]  Bruce: By the way, Hidden Figures, the movie, I believe that's what they were actually were. The women in that movie were the computers. And they show kind of the introductory of electronic computer. And they would then become the programmers of electronic computer. It's kind of a cool movie, by the way, for anyone that's interested in that. So dynamic programming then, without getting into, I'm not going to describe to you exactly what dynamic programming is. Basically, what it is, is a technique. It's a general technique that allows you to take one big problem and split it up into a bunch of little problems. The Fibonacci numbers is an example of dynamic programming. If I want to solve for what's the fifth Fibonacci number, this is from a past podcast, then I solve first for what the first two Fibonacci numbers are, which is just axiomatically given, and then I solve for what the third one is, and then the fourth one is, and then the fifth one is.

[00:43:28]  Bruce: And I save off what the answer is for all the previous ones so that I've got it in memory, and I've got that available to when I get to the fifth one. That's a very basic sort of dynamic programming. In this case, you would basically do that sort of iterative process. You would create one policy after another, and then you would try to improve it until you couldn't improve it anymore. There's actually something called policy iteration, something called value iteration. They get the same result, but they do it in slightly different ways. Both of those are types of dynamic programming, and the end result of either is ultimately an optimal policy. Now, to be able to do dynamic programming, though, to solve the Markov decision process, you have to know the reward function and the state transition function, which in this case we do because I just showed you what they look like for this grid world.

[00:44:18]  Bruce: If you have that state function and that reward function, you simply use them to do dynamic programming to solve the Markov decision process, and the net result is an optimal policy, exactly like what you see on the screen. Now your agent knows exactly what to do in every possible state it might find itself in, and it always makes the optimal move. Does that make sense?

[00:44:38]  Unidentified speaker: Yes.

[00:44:39]  Bruce: Now, the optimal policy would be based on a value function, which I now show on the screen. It's the same three by three world, but what we're doing is we're assigning a value to each state. Basically, the goal state is 100 still, and every state next to the goal state is a discounted version of it. So 90 points for being on one of the two squares that's right next to the goal state, and then a square that's next to one of those squares is then a little less than that. So 81 for each of those. You can see I'm taking 90 percent each time, right? Until finally you get back to the start state, which gets the lowest value, it's 65.61, okay? Because you've taken 90 percent, 90 percent, 90 percent. And that is what the value function looks like, okay? And basically, dynamic programming, if you're doing value iteration, it solves for that and then it creates a policy out of it.

[00:45:38]  Bruce: The other way would be policy iteration, you would work directly with the policy, but it's basically the same thing. How might you translate between the value function and the optimal policy, the optimal value function and the optimal policy? It's fairly simple. There's nothing magic about this. What would be a very simple way of doing that?

[00:45:59]  Cameo: I have no idea.

[00:46:01]  Bruce: Basically, you just move towards the state that you're next to that's higher than you. If I'm in the middle square on the top row, so my value is 90, my arrow in my policy would be the one that moves to a square that's higher than me. Which one is that?

[00:46:21]  Tracy: The 100.

[00:46:22]  Bruce: That's right. Notice that if you put an arrow from the 90 to the 100, it's exactly the same as the arrow in the optimal policy. That's true for all of them. Look at every single one of these. Imagine yourself in that square, and then put an arrow that goes to one of the squares that's higher than it, and it will exactly match the optimal policy that I drew. As I mentioned, some of these could have a second optimal policy that's just as optimal. You just have to pick one of them. Can you see how to translate between the two?

[00:46:50]  Tracy: If you mean like 81 should have, to me, two arrows, one up and one right, because the next nearest values are both 90. But you just have to pick one. Whatever direction it goes.

[00:47:02]  Bruce: You just have to pick one. So I picked up, but I could just as well have picked to the right. So let's do an example. Take a look at the lower right-hand corner. What's the value in the lower right-hand corner?

[00:47:16]  Tracy: 81.

[00:47:17]  Bruce: Okay. Where would you draw the arrow to? Would you draw it to this? We're not allowing diagonals, so there's only two squares next to it. There's the one above it and the one to the right of it. Which direction would you draw the arrow in the optimal policy?

[00:47:33]  Tracy: Upwards to the box above it—the value is 90.

[00:47:36]  Bruce: That's right. Now, you can do that for every single one of those squares. Every single one of those squares, all you have to do is check each square next to it and then draw the arrow towards whichever one is the largest. And if you have two that are the same, then you just draw it to one of them. You just pick one. Does that make sense?

[00:47:51]  Cameo: Yes.

[00:47:53]  Bruce: Here's the problem though. So this is easy so far. And if we know the state transition function, then we know we can use dynamic programming to solve for an optimal policy, and then our agent will be able to perform optimally. What if we don't know the transition function? Or for that matter, what if we don't know the reward function? Now, in this grid world, I made the world myself. I came up with the grid. I came up with what the states are. I came up with what the actions were. So of course I know what the transition function and the reward function are. But in real life, if I'm trying to, let's say, make a stock buying program, I don't know what the transition function is. The world contains a transition function, but I don't have any idea what it is. For that matter, I may know what the rewards are. So for a stock buying program, I know I want to make more money and I don't want to lose money.

[00:48:45]  Bruce: So I don't know what the reward function is. I don't know if I make this purchase what my reward is going to be, but after I do it, I can look at how much money did I make or lose. I can know what the reward was for that move, for that action. But I don't have any idea what the transition function is. What actually causes the stock market to go up or down? Nobody knows, right? So if reinforcement learning had to use dynamic programming, then it would require that you could only use it on Markov decision processes, where we happened to know the state transition function and the reward function, which is basically never except in little toy problems like this that I'm demonstrating. This would make Markov decision process, solving for a Markov decision process, not particularly useful. So what we really need is we need some way to solve the Markov decision process where we don't know what the state transition function is or what the reward function is.

[00:49:50]  Bruce: Now, when I originally gave this presentation, I did a little aside about David Deutsch. Since people listening to this podcast are going to know way more than this, I can just summarize this really quickly. Basically, because the real world is computable, as per if you've listened to the podcasts on Church-Turing thesis, the Turing principle, the whole world is computable. So we basically know from that theory that everything has a state transition function. Everything has a reward function. We just don't know what they are, but they exist. And that all came from Alan Turing. Based on that, we have this idea of the Turing principle, all of reality can be simulated on a universal computer. Because we know that it must exist, there must be some way to actually solve this problem. Just how do we do it? Well, this is where the clever stuff comes in.

[00:50:48]  Bruce: Now, right here...

[00:50:49]  Tracy: I need a second cup of coffee for this.

[00:50:54]  Bruce: Right here, I've written out the mathematics. So this probably makes no sense to you. It looks like Greek.

[00:50:59]  Cameo: This math hurts my brain just even more.

[00:51:03]  Bruce: So I'm actually going to take the time to take you through the mathematics. And I don't really expect you to understand it exactly. I'm trying to just get you to get the gist of it. Roger Penrose, one of my favorite authors, he talks about... He's a world-class physics-mathematic person, right? And he talks about how when he reads math formulas in papers and such, he doesn't know what they mean either. And he just tries to get the gist of... initially just get the gist of what they mean. It's a lot easier to get the gist than it is to understand exactly what it's saying. But the gist is beautiful. There's like this beautiful theorem that I'm going to try to go through here. And if anyone's like later on, maybe someone in the OMSCS program is using this, this will explain how reinforcement learning actually works and why it works. Okay. So let me kind of take you through each of these parts.

[00:51:56]  Bruce: So let's start with the value reward and transition functions. So the reward function is the actual rewards. We already know how to do that. The value function is what I already showed you. It's the same grid. The reward function is the grid with 100 on the goal state, which is state three, and everything else is zero. And the value function is the discounted value of being close to the goal. So the upper right-hand corner is 100 because it's the goal. The two next to it are 90. The two next to the 90s… The three next to the 90s are 81s. The two next to the 81s are 72.9s. The start state, which is the furthest away from the goal, is 65.61. That's just 90% off each time, taking a discount. If you're familiar with economics, you already understand the idea of net present value and the idea of discounting value that's in the future. Having a million dollars today is very different than having a million dollars 10 years from now.

[00:52:55]  Bruce: So they do a net present value to say, how much is a million dollars in the future worth today? And you do a discount factor. It's the exact same idea. So the transition function is just a list of what actions move from one state to another. The Q function, I've got to define the Q function. Q function is like a combination of the states and the actions. So the only real difference here is that instead of assigning the value to the goal of 100, I'm going to assign a value of 100 to the move that moves you into the goal state. So can you see, if you can see the screen for those who are doing the YouTube version, you can see that the two squares next to the goal state, they have an arrow that goes to the goal state. That arrow is now worth 100 instead of being in the state, state 3. Taking the action to get you to state 3 gives you the 100 instead.

[00:53:49]  Bruce: Do you see the difference there? It's basically the same thing. By doing that, the Q function looks slightly different. I'm now going to call state 3 the upper right-hand corner goal. I'm going to assign a value of 100 to the move that comes in. Then I can take an optimal value function. You basically just say, take the max. I've got a bunch of arrows which are actions I can take from that state. Take whichever action gives me the highest value, so it assigns a 100 for being next to the goal state in this case. There's no real difference. Mathematically, it works out to be exactly the same as the way we were doing it before. It's just a little bit easier to calculate by having it put into the Q function where we're keeping track of states and actions together. Does that make sense? That's what a Q function is and what an optimal value function is.

[00:54:40]  Bruce: Finally, we have the optimal policy which can be attained from the optimal value function based on the way we just talked about. Now we can get into the actual proof. In the audio version of this podcast, I cut out the proof that then followed. If you really are interested in this subject, you may want to visit our YouTube channel where you can find the proof in full and it's written out and it should be a lot easier to understand than if I just give you the audio version of it. Let me explain the basics though of what it is I went over. There's a series of equations, most of which are just kind of patently obvious. They simply define things. They define what a value function is. They define what a policy is. In fairly intuitive ways, when you take them all together and then use those functions to substitute in with each other, you end up with something called the Q function, defined in terms of itself.

[00:55:34]  Bruce: The idea is that a Q function, it's a value for a state and an action inside your world. And it defines it in terms of the reward that you receive and then a discount of all future Q values that come from that state that you've then moved into, discounted by the number of states it is away from you. And it does that in terms of the Q function itself. By putting this together into a Q function that's recursively defined in terms of itself, it actually sets us up so that we're able to create a function that, you know, program it in Python or something like that. You can set it up so that the agent, the robot, or whatever it is that you're trying to train, that it simply takes rewards from the real world and then it converges those rewards. It uses that to slowly converge to the correct Q function, which is a table of states and actions, the various states that exist in the world and the actions that you can take from each state.

[00:56:36]  Bruce: Now, by doing this, it will actually, over time, in fact, at infinity, it will converge exactly to the right values. This can be proven mathematically. In real life, you never go to infinity, but you can get to the point where the Q values you come up with are fairly close to what they would be if you were doing dynamic programming that gives you an exact answer. Dynamic programming, though, required you to have the transition function and required you to have the reward function. In this case, you don't need either of those. So by defining it in this way, you're getting rid of the need to have the transition function or the reward function. Now, of course, the whole goal, it was to get rid of the transition function and the reward function, because in the real world, we never know what those are. And because we don't know what those are, we can't use dynamic programming to solve a Markov decision process.

[00:57:25]  Bruce: By moving to Q learning, since we got rid of those functions and we can approximate it in a different way, we're now able to essentially solve these problems without having to know what the transition function and the reward function of the world are. And what you come up with ultimately then is this approximation of the Q table that you need. And once you have that, it's very easy to convert that into a policy for your agent that tells it for every single state, here's the correct action to take. This is basically how reinforcement learning works. And this is how AlphaGo works. This is how anything that deals with reinforcement learning works. The rewards simply perpetuate out from the goal state, let's say a win in AlphaGo, until it figures out which board states are the most likely to lead to a win in the future. So this is what I went through mathematically, showed how it worked.

[00:58:22]  Bruce: The end result then is exactly what we wanted. It's a general purpose learner that once you give it the states and you give it, set up the agent to pick up the rewards and you define what the rewards are that come from the real world, it will then just simply converge towards the right function that it needs. Now back to the rest of the program. This is the beautiful thing about it. It doesn't matter if you don't quite get it.

[00:58:48]  Cameo: That's good then.

[00:58:52]  Tracy: Thank you for saying that.

[00:58:54]  Bruce: The important thing here is that we no longer have to know the transition function. It is possible to approximate the Q function without ever knowing the transition function or the reward function. So long as you can receive rewards in real life, and so long as you do these iterative updates that I talked about where you simply throw a little extra value, you slowly move towards… You take the old value and you basically, the easiest way to explain this would be whatever state you're in, in the Q function. So you're in the Q function in state S and you're taking action A. You know based on your current Q function that the best action leads to some other action. So you're looking one move ahead and you're doing a discount on one move ahead. And then you're throwing on whatever the reward is. You simply do 20% of the reward, 80% of what it used to… What the value used to be, and you assign that to the new one.

[00:59:55]  Bruce: What's going to happen is it's going to start perpetuating out. The values in the Q table will slowly spread out from the goal until they hit the start state. I'll show you an actual example of this now. I'm just kind of trying to show that how all of these are really kind of the same thing done in different formats, right? So you can see where the reds and the greens and the purples match. Now remember that you care, what we care about is not the Q function, it's the optimal policy. But you can get the, from the Q function, you can get an optimal policy using the techniques that we've already talked about. So if we can get, if we can iteratively come up with the Q function, we can then use that to convert to the optimal policy and we're done, right? The end result of this is that we now have a tractable way to just use natural rewards to find an optimal policy.

[01:00:41]  Bruce: And remember everything under the Turing Principle is a function. So theoretically, this is a general learning algorithm. Now, you got to be careful, we're not talking about AGI, but theoretically, this is an algorithm that can learn any real world function so long as you can figure out how to define it in terms of a Markov decision process and you can define rewards, then this algorithm will work on it. It may not work well, may not be tractable, there's a lot of caveats there. Now, this is why people got so excited about reinforcement learning, even though it really isn't the most useful technique at this point. There was a guy who was a researcher in reinforcement learning, and he said, people always ask me if reinforcement learning would be an appropriate approach for their current problem. And he says, I always answer, no, it's not. And I know there's a 70% chance I'm right, because our level of understanding of reinforcement learning is still so primitive that it doesn't work as well as just regular supervised learning, for the most part.

[01:01:48]  Bruce: It's much easier to define problems and solutions to problems in terms of supervised learning than in terms of reinforcement learning. The difference is that reinforcement learning can be applied to any problem, and supervised learning really can't. It always requires that you have a human that has labeled things, whereas this gets away from that. Because of that, you've got like this Antonio Gulli from Deep Learning with Keras, where he says reinforcement learning seems to be a general learning algorithm that can be applied to a variety of environments. It may even be the first step to a general artificial intelligence. Well, I don't agree it's a first step to general artificial intelligence, but it is very exciting. It is a general purpose machine learning algorithm. It's the only one we really know about. And the reason why it works is because of everything I just showed you mathematically, the fact that we can drop this transition function out and we can estimate the Q values and then from there make an optimal policy.

[01:02:44]  Bruce: So this is a very exciting area for research, regardless of whether it's really a path to artificial general intelligence or not. Since machine learning is about modeling reality's hidden functions, we now have a general way to do that. So now let's talk about how this is going to work in real life. We're actually almost done, but I want to make sure we get in this real life example. Sorry, it'll make a little bit more sense if I show you how the values slowly perpetuate outwards. So we've defined our state transition function, which you can see here… We have a reward function. We've got our Q-learning algorithm, which we implement using code something like this. You don't need to follow what the code is, but I put this code in terms of Python, where I basically take 20% of one value, 80% of what it used to be, and then you're slowly converging towards it.

[01:03:37]  Bruce: And we've got our states and actions, which is defined as this grid here. So let's start with our little robot here that exists inside of this grid world. And it starts in the start state, and we want it to find the goal. So it's going to, since it's Q table that it's using initially starts off with all zeros, it's basically just making random moves. So it moves all over the place, and just by chance, it happens to make it to state two, which is a state right next to the goal state. So, and then by chance, it happens to move into the goal state. So I'm going to go back one. Up to this point, that formula I've been using, because the Q values are all zero, they always return zero. So I'm doing the mathematics here, you can see, but it's updating zero with zero. Nothing's getting updated because we haven't reached the goal state yet. By chance, we now hit the goal state, okay?

[01:04:31]  Bruce: And we receive a reward of 100. How does the math work? So following the formula that I've listed out, you take 80% of the current Q value, which is 80% of zero, and you take 20% of the reward plus the Q value one forward into the future, which in this case is also zero. So what you're really going to end up with is 20% of the reward. So we work the math, and what we end up with is the Q value for state two taking right is going to now equal to 20. So right now, Q value for two right is zero. It's going to be updated to 20. Now let's say we do another run. So you got to let this robot run a whole bunch of times for this algorithm to work. And it somehow just happens to wind up in state one at some point, and it happens to move into state two. So again, we run the formula. You take 80% of the old value. Basically, just running these numbers here doesn't really matter too much.

[01:05:31]  Bruce: What you're going to end up with is 90% of the 20 that's in state two. So 3.6. We update our Q table to have a 3.6 at state one if you take a right. You can see how... Now remember, think about this in terms of the value function. The value function is just the largest action in that state. So this state one now has a value function of 3.6, and this state two now has a value function of 20. You can see how the rewards from state three are starting to spread into our little maze. Does that make sense? And even if you don't follow the math, does that make sense how it spreads and why it spreads?

[01:06:08]  Unidentified speaker: Yeah.

[01:06:09]  Tracy: Yeah, it makes sense why it spreads.

[01:06:11]  Bruce: This is reinforcement learning. Reinforcement learning is nothing but this. You're counting on the fact that as you explore that maze around and as it starts to find the rewards, that the rewards are going to, based on the formulas that we've been playing with, that they're going to naturally always expand outward from the reward states, from the goal state, until eventually it reaches our start state. In which case, at that point, we now know what the right moves are.

[01:06:45]  Tracy: Do you see that natural spread as intuition of some kind?

[01:06:49]  Bruce: Well, you'll see. You'll see. So, not yet. It's kind of like that. Our robot's now in state two. It happens to move into the... When it's in state two, it now knows that the goal stays to the right because it found it from state two last time. So it now knows, pick the move to the right. It doesn't have to make a random move anymore. It gets a score of 100. We run the math again, and the math works out like this. It now updates from 20 in state two move right to 36 in state two move right. It's now increased. It now has a better understanding that if I'm in state two and I take the right move, that's more value than 20. It's got to be something higher than 20. It moves it to 36. It will literally, if you run this enough times, it will literally converge to exactly the values where 100 in state two and 100 in state six so that it knows, oh, if I'm in state two or state six, I need to move to the right to get into the goal state or if I'm in state six, move up to get into the goal state.

[01:07:58]  Bruce: It will converge towards the correct Q values over time. So now it won't ever… There's no guarantee it will find the exact right ones. The guarantee only exists at infinity, right? If you run this enough times, I haven't talked about Explore-Exploit yet. I'll explain that in just a second. But if you do Explore-Exploit and you run this an infinite number of times, mathematically it's guaranteed to converge to the right Q values. Now obviously you don't ever actually do anything an infinite number of times. But as it turns out, if you just do this a whole bunch of times, it will converge to something close to the correct Q values. Okay, does that make sense? Do you follow what I'm saying there?

[01:08:41]  Cameo: Yes.

[01:08:42]  Bruce: So this is an example where they're not quite right. I'm kind of throwing values in there. They're close to right, but they're not quite right. But those values, as they converge towards the correct Q values, they'll be good enough to make a near optimal policy. Now there is one problem though that we still have to overcome. This is the Explore Exploit trade-off. Since we're originally just moving that robot randomly, since the Q values all start off as zero, it's possible the robot, like in a worst case scenario, we could imagine a robot that happens to move from the start state to here to here, and it makes like an S. It takes the longest possible path to the goal state. And let's just say by chance, it keeps doing that. What would happen is that the Q values would spread out from the goal, but they would follow only the path that the robot had followed.

[01:09:32]  Bruce: So the values would spread, and you'd end up with a very non-optimal policy. The robot would always follow exactly the path it followed before, this long winding S path. So how do you keep that from happening? Okay, well, basically what you do is you don't follow your optimal policy, your current approximation of the optimal policy every single time. Some percentage of the time, you just take a random move. And by doing that, it gives it a chance to explore if there's a shorter path. And again, at infinity, it will eventually try every single possible action, and it will eventually converge to the correct Q values. So that's why you have to have the Explore Exploit trade-off. You can't do without it. The guarantees of converging to the correct Q values only happen if you also make random moves every so often during the training phase. What you would typically do, though, is you would, they call this ε-greedy, ε-greedy.

[01:10:35]  Bruce: So basically, you always take the best move, except some epsilon e, that's the e, epsilon greedy, epsilon value, and you would decay that. So maybe initially you tell it, the epsilon is 90 percent, so 90 percent of the time you make a random move. Then maybe on the next generation, you make it 89 percent of the time, a random move. And then you just let it keep decaying, until finally after thousands of generations, maybe you're only making a random move 0.01 percent of the time. That's still sufficient. If you're decaying the occurrences of random moves, the robot will learn an optimal policy or something close to an optimal policy, and yet it will always have a little bit of a chance of making a random move, and so it can continue to improve things. By the way, this is Popperian, right? It's fallibilism. It's the fact that since there's no guarantee it'll find an optimal policy, you have to always be open to there might be an improvement.

[01:11:37]  Bruce: That's the random explore-exploit trade-off. And at infinity, yes, it's guaranteed to get an optimal policy. That's exactly equivalent to David Deutsch's, all problems are soluble. It's a soluble problem, but only at infinity. And as long as you have an infinite horizon, you can continue to make improvements, but it will always require some diversity of thought. It will always require trying things different than what our current best theories say. And there's a very cool, critical rationalist explanation for exactly what we're seeing here in reinforcement learning. All right, any questions about this? I don't want to move on unless this makes at least a little bit of sense.

[01:12:21]  Tracy: It makes a little bit of sense.

[01:12:22]  Cameo: It does make a little bit of sense.

[01:12:25]  Bruce: So here is a grid world I actually ran. You've got the ones are walls, the two is the start state, the three is the goal state, the fives are pits that you fall into and you lose. I ran reinforcement learning on it. And you can see that this is the optimal policy it came up with. Imagine these little signs as arrows, okay? And you can see the pits and you can see the walls. Now, look at this carefully. And this is pretty close to an optimal policy. So this is the start state. It's going to try to move you this way, this way, up here. It's trying to stay away. It's not taking the fastest path to the goal state because it's trying to stay away from the pits. By the way, there's a random chance you won't move in the direction you're trying to. So if it was deterministic, it would just simply go here and go straight to the goal state. But because that gives you a chance of losing the game, instead, it comes up with a policy where it moves you around the walls this way and then takes you to the goal state, so that it never even gets close to the pits.

[01:13:26]  Bruce: That's exactly what you would expect it to come up with. Now, you can see that it's not quite optimal. Notice how that state right there is going down, and then it goes up. It's not very useful. There's not much chance you'll ever get to that state. And that's exactly why it has a non-optimal policy at that state, is because it didn't get to explore that state out very much. Because it normally just followed the optimal policy and it just had no need to go there. So it might be off slightly, but it's getting really dang close to the optimal policy. Now, here's a real-life example of stock trading. So I've got stock that I'm doing. I've got my portfolio. I've got a benchmark and an attempt to do manual trades that didn't work that well. Basically, I ran this through the exact same reinforcement learning algorithm that I just used for that grid world.

[01:14:22]  Bruce: The only thing that changed was I had to change what the state of the world looked like. And it came up with a bunch of trades, and those trades made it so that it made a whole bunch of money. That's basically what I'm showing here. You can see it's trading all the time, though. How do you actually do that? Well, I have to come up with some way to represent the state of the world into discrete Q values. The way I would do that is maybe I'd use a signal like a Bollinger band, and I would turn it into a discrete signal instead. And my state of the world would be based on what these discrete signals for the Bollinger bands are. How well this would work in real life, it really wouldn't work that well. But this gives you a feel for how you would actually translate the world into a set of discrete states that can then be used for Q values. Final result of this, now using something in the future that wasn't part of the training set, it still returned pretty good results.

[01:15:14]  Bruce: I did find though that it only really returned good results if the future and the past were similar. So in this case, I was using JP Morgan right after the crash in 2008. Its future and its past were very similar. So it came up with a fairly good policy on when to buy and sell. I tried it on Microsoft where it crashed huge 2008, and then it just took off. So it still made money when I did that, but you could make more money by just buying Microsoft and holding it. So it's not going to give you great results if the future and the past don't happen to match. And there's no guarantee the future and the past will match. But if they do, it will come up with a policy that works better than probably anything that you can come up with. This is where it becomes like intuition, Tracy, where it seems like it's intuitively knowing when to buy and sell.

[01:16:07]  Bruce: But what it's really doing is treating the world as a MDP, as a Markov decision process. And then it's letting those values perpetuate backwards until it finds what are the good times to buy and sell based on this Bollinger Band signal. And then it ends up making money based on that. If it turns out that the world has changed and those signals are no longer valid, then it's going to not make money. And that's just kind of the way Reinforcement Learning works. All right, that's it. We're actually done. I think I would add one more thing. All of this assumes that we're dealing with a discrete world. The real world isn't discrete. So there's something really cool you can do with Reinforcement Learning, where you add a neural net to replace the Q table. So basically you say instead of using a Q table, which has to be discrete, you say I'm going to use a neural net as a replacement for my Q table function.

[01:17:00]  Bruce: And it's going to approximate a continuous Q table, whatever that is, and it will do it. It will actually approximate a continuous Q table using a neural net. And that's what they call deep reinforcement learning. And that's what AlphaGo actually used, because the state of the world for a Go board is so large, you couldn't hold it in memory. So they approximate it using a neural net instead. And neural nets are artificial intuition. The net result is that they use reinforcement learning of playing lots and lots of games and it continues to refine its neural net as a substitute for the Q table. And it will slowly converge to something that has really strong intuitions as to this is a good move. The reason why this works so well for something like AlphaGo though, is because it's a game and you can let it play itself billions of times until the reinforcement learning algorithm perpetuates outwards and it comes up with really good values.

[01:18:00]  Bruce: And this is really the main thing that we have to understand, is that while this is our single best general purpose problem solving algorithm in machine learning, it still requires billions of examples and it still requires that you actually still define what the states of the world are. It doesn't learn the states on its own. So it still needs this giant injection of knowledge from a human that can say, well, the problem I'm solving, I'm going to use Bollinger bands to represent my world. I'm going to, here's how I'm going to do it. You still need this giant injection of knowledge. And that's the way AlphaGo works, by the way. They often kind of pitch AlphaGo as it learned how to play Go from scratch. It's not really true. It still had to come up with, the humans had to still come up with valid states that it could learn from that represented true knowledge about how Go was played.

[01:18:54]  Bruce: So there was still this injection of knowledge coming from the human. It learned a lot on its own, and the end result is that it could play better than any human had ever played. So clearly it's got some sort of knowledge that no human being has. And yet it's still this interesting mix of human knowledge and knowledge generated by the machine learning algorithm. And it's hard to really tease apart those two well. All right, any questions about this? We really are done now.

[01:19:22]  Cameo: No, no, it's a great topic. It also reminds me why I'm not a mathematician.

[01:19:32]  Tracy: I'm with you.

[01:19:34]  Bruce: Do your heads both hurt at this point?

[01:19:36]  Cameo: Yeah, yeah, I'm going to go take a nap.

[01:19:40]  Bruce: So when we talk about animal intelligence in the future, one of the key things I want to get across is that animals don't require any sort of state, world state knowledge injected into their heads to be able to learn how to do something. And they can learn from a few thousand examples instead of a few billion examples. So animals like this is something that David Deutsch often talks about. He talks about like behavior parsing. We'll talk about that in a future thing. He points out that apes—gorillas— when they have to learn memes, they have to watch each other thousands of times or hundreds of times really, not thousands, but hundreds of times before they can learn the movements and what they need to do from another gorilla. Or with a human, because humans can explain things. They can watch a person a couple times, get an explanation for what the purpose is, and then they can now perform these actions.

[01:20:36]  Bruce: So he points out how much faster humans learn than gorillas, because humans have real full understanding, and even the primates closest to us don't, right? The thing that he's missing there, that's all true. The thing he's missing there is that our best algorithms don't even come close to how fast an ape can learn.

[01:21:00]  Cameo: Sure.

[01:21:01]  Bruce: And so animals are like this in-between state. And I don't know if that's meaningful or if it's not, but animals are more general purpose learners than any sort of machine learning that exists. And they learn faster than any machine learning that exists, even our best general purpose machine learning algorithm, which is reinforcement learning. And I think that's significant. I don't know exactly how significant, but I think that that is a very interesting thing that animal intelligence seems to exist between our current knowledge about machine learning, but quite a bit shy of what humans are capable of.

[01:21:39]  Cameo: Interesting.

[01:21:40]  Bruce: All right. Thank you guys.

[01:21:42]  Cameo: Thank you, Bruce.

[01:21:43]  Tracy: Thank you.

[01:21:45]  Unidentified speaker: All right.

[01:21:45]  Bruce: Bye-bye. The Theory of Anything podcast could use your help. We have a small but loyal audience, and we'd like to get the word out about the podcast to others so others can enjoy it as well. To the best of our knowledge, we're the only podcast that covers all four strands of David Deutsch's philosophy as well as other interesting subjects. If you're enjoying this podcast, please give us a five-star rating on Apple podcasts. This can usually be done right inside your podcast player. Or you can Google The Theory of Anything podcast Apple or something like that. Some players have their own rating system and giving us a five-star rating on any rating system would be helpful. If you enjoy a particular episode, please consider tweeting about us or linking to us on Facebook or other social media to help get the word out. If you are interested in financially supporting the podcast, we have two ways to do that.

[01:22:38]  Bruce: The first is via our podcast host site, Anchor. Just go to anchor.fm slash four dash strands, F-O-U-R dash S-T-R-A-N-D-S. There's a support button available that allows you to do reoccurring donations. If you wanna make a one-time donation, go to our blog, which is fourstrands.org. There is a donation button there that uses PayPal. Thank you.