Hey, I’m Jabril and welcome to Crash Course AI.

Say I want to get a cookie from a jar that’s on a tall shelf. There isn’t one “right way” to get the cookies.

Maybe I find a ladder, use a lasso, or build a complicated system of pulleys. These could all be brilliant or terrible ideas, but if something works, I get the sweet taste of victory... and I learn that doing that same thing could get me another cookie in the future. We learn lots of things by trial-and-error, and this kind of “learning by doing” to achieve complicated goals is called Reinforcement Learning.

INTRO So far, we’ve talked about two types of learning in Crash Course AI: Supervised Learning, where a teacher gives an AI answers to learn from, and Unsupervised Learning, where an AI tries to find patterns in the world. Reinforcement Learning is particularly useful for situations where we want to train AIs to have certain skills we don’t fully understand ourselves. For example, I’m pretty good at walking, but trying to explain the process of walking is kind of difficult.

What angle should your femur be relative to your foot? And should you move it with an average angular velocity of… yeah, never mind… its really difficult. With reinforcement learning, we can train AIs to perform complicated tasks.

But unlike other techniques, we only have to tell them at the very end of the task if they succeeded, and then ask them to tell us how they did it. (We’re going to focus on this general case, but sometimes this feedback could come earlier. So if we want an AI to learn to walk, we give them a reward if they’re both standing up and moving forward, and then figure out what steps they took to get to that point. The longer the AI stands up and moves forward, the longer it’s walking, and the more reward it gets.

So you can kind of see how the key to reinforcement learning is just trial-and-error, again and again. For humans, a reward might be a cookie or the joy of winning a board game. But for an AI system, a reward is just a small positive signal that basically tells it “good job” and “do that again”!

Google Deepmind got some pretty impressive results when they used reinforcement learning to teach virtual AI systems to walk, jump, and even duck under obstacles. It looks kinda silly, but works pretty well! Other researchers have even helped real life robots learn to walk.

So seeing the end result is pretty fun and can help us understand the goals of reinforcement learning. But to really understand how reinforcement learning works, we have to learn new language to talk about these AI and what they’re doing. Similar to previous episodes, we have an AI (or Agent) as our loyal subject that’s going to learn.

An agent makes predictions or performs Actions, like moving a tiny bit forward, or picking the next best move in a game. And it performs actions based on its current inputs, which we call the State. In supervised learning, after /each/ action, we would have a training label that tells our AI whether it did the right thing or not.

We can’t do that here with reinforcement learning, because we don’t know what the “right thing” actually is until it’s completely done with the task. This difference actually highlights one of the hardest parts of reinforcement learning called credit assignment. It’s hard to know which actions helped us get to the reward (and should get credit) and which actions slowed down our AI when we don’t pause to think after every action.

So the agent ends up interacting with its Environment for a while, whether that’s a game board, a virtual maze, or real life kitchen. And the agent takes many actions until it gets a Reward, which we give out when it wins a game or gets that cookie jar from that really tall shelf. Then, every time the agent wins (or succeeds at its task), we can look back on the actions it took and slowly figure out which game states were helpful and which weren’t.

During this reflection, we’re assigning Value to those different game states and deciding on a Policy for which actions work best. We need Values and Policies to get anything done in reinforcement learning. Let’s say I see some food in the kitchen: a box, a small bag, and a plate with a donut.

So my brain can assign each of these a value, a numerical yummy-ness value. The box probably has 6 donuts in it, the bag probably has 2, and the plate just has 1… so the values I assign are 6, 2, and 1. Now that I’ve assigned each of them a value, I can decide on a policy to plan what action to take!

The simplest policy is to go to the highest value (that box of possibly 6 donuts). But I can’t see inside of it, and that could be a box of bagels, so it’s high reward but high risk. Another policy could be low reward but low risk, going with the plate with 1 guaranteed delicious donut.

Personally, I’d pick a middle-ground policy, and go for the bag because I have a better chance of guessing that there are donuts inside than the box, and a value of 1 donut isn’t enough. That’s a lot of vocab, so let’s see these concepts in action to help us remember everything. Our example is going to focus on a mathematical framework that could be used with different underlying machine learning techniques.

Let’s say John-Green-bot wants to go to the charging station to recharge his batteries. In this example, John-Green-bot is a brand new Agent, and the room is the Environment he needs to learn about. From where he is now in the room, he has four possible Actions: moving up, down, left, or right.

And his State is a couple of different inputs: where he is, where he came from, and what he sees. For this example, we’ll assume John-Green-bot can see the whole room. So when he moves up (or any direction), his state changes.

But he doesn’t know yet if moving up was a good idea, because he hasn’t reached a goal. So go on, John-Green-bot... explore! He found the battery, so he got a Reward (that little plus one).

Now, we can look back at the path he took and give all the cells he walked through a Value -- specifically, a higher value for those near the goal, and lower for those farther away. These higher and lower values help with the trial-and-error of reinforcement learning, and they give our agent more information about better actions to take when he tries again! So if we put John-Green-bot back at the start, he’ll want to decide on a Policy that maximizes reward.

Since he already knows a path to the battery, he’ll walk along that path, and he’s guaranteed another +1. But that’s… too easy. And kind of boring if John-Green-bot just takes the same long and winding path every time.

So another important concept in reinforcement learning is the trade-off between exploitation and exploration. Now that John-Green-bot knows one way to get to the battery, he could just exploit this knowledge by always taking the same 10 actions. It’s not a terrible idea -- he knows he won’t get lost and he’ll definitely get a reward.

But this 10-action path is also pretty inefficient, and there are probably more efficient paths out there. So exploitation may not be the best strategy. It’s usually worth trying lots of different actions to see what happens, which is a strategy called exploration.

Every new path John-Green-bot takes will give him a bit more data about the best way to get a reward. So let’s let John-Green-bot explore for 100 actions, and after he completes a path, we’ll update the values of the cells he’s been to. Now we can look at all these new values!

During exploration, John-Green-bot found a short-cut, so now he knows a path that only takes 4 actions to get to the goal. This means our new policy (which always chooses the best value for the next action) will take John-Green-bot down this faster path to the target. That’s much better than before, but we paid a cost, because during those 100 actions of exploration, he took some paths that were even /more/ inefficient than the first 10-action try and only got a total of 6 points.

If John-Green-bot had just exploited his knowledge of the first path he took for those 100 actions, he could have made it to the battery 10 times and gotten 10 points. So you could say that exploration was a waste of time. BUT if we started a new competition between the new John-Green-bot (who knows a 4-action path) and his younger, more foolish self (who knows a 10-action path), over 100 actions, the new John-Green-bot would be able to get 25 points because his path is much faster.

His reinforcement learning helped! So should we explore more to try and find an even better path? Or should we just use exploitation right away to collect more points?

In many reinforcement learning problems, we need a balance of exploitation and exploration, and people are actively researching this trade-off. These kinds of problems can get even more complicated if we add different kinds of rewards, like a +1 battery and a +3 bigger battery. Or there could even be Negative Rewards that John-Green-Bot needs to learn to avoid, like this black hole.

If we let John-Green-Bot explore this new environment using reinforcement learning, sometimes he falls into the black hole. So the cells will end up having different values than the earlier environment, and there could be a different best policy. Plus, the whole environment could change in many of these problems.

If we have an AI in our car helping us drive home, the same road will have different people, bicycles, cars, and black holes on it every day. There might even be construction that completely reroutes us. This is where reinforcement learning problems get more fun, but much harder.

When John-Green-bot was learning how to navigate on that small grid, cells closer to the battery had higher values than those far away. But for many problems, we’ll want to use a value function to think about what we’ve done so far, and decide on the next move using math. For example, in this situation where an AI is helping us drive home, if we’re optimizing safety and we see the brake lights of the car in front of us, it’s probably time to slow down, but if we saw a bag of donuts in the street, we would want to stop.

So reinforcement learning is a powerful tool that’s been around for decades, but a lot of problems need a ton of data and a ton of time to solve. There have been really impressive results recently thanks to deep reinforcement learning on large-scale computing. These systems can explore massive environments and a huge number of states, leading to results like AIs learning to play games.

At the core of a lot of these problems are discrete symbols, like a command for forward or the squares on a game board, so how to reason and plan in these spaces is a key part of AI. Next week, we’ll dive into symbolic AI and how it’s a powerful tool for systems we use every day. See you then.

Crash Course Ai is produced in association with PBS Digital Studios. If you want to help keep Crash Course free for everyone, forever, you can join our community on Patreon. And if you want to learn other approaches to control robot behavior check out this video on Crash Course Computer Science.