AI · 13 Artificial Intelligence

Learning by Reward: Reinforcement Learning

Learning by Reward: Reinforcement Learning

On slippery ice, a random agent reaches the goal 18 times in 1,000. After 10,000 tries of Q-learning: 7,384 goals in 10,000 test games (73.8%), with moves that look wrong. Rewards, return and discount, Bellman's equation, a real Q-learning update by hand, explore vs exploit, policy gradients, DQN, AlphaGo's move 37, self-play, and an agent that games its reward. Every number is real output from code you can run.

Chapters

Cheat sheet

Code

Try it yourself (pip install gymnasium numpy; runs in seconds)
import gymnasium as gym
import numpy as np

env = gym.make("FrozenLake-v1") # 4 x 4 slippery ice, reward 1 only at the goal
env.reset(seed=0)
rng = np.random.default_rng(0)
Q = np.zeros((16, 4)) # a score per tile and move: left, down, right, up
alpha, gamma, epsilon = 0.1, 0.99, 1.0

wins = 0
for episode in range(1, 10_001):
state, _ = env.reset()
done = False
while not done:
if rng.binomial(1, epsilon): # explore
action = rng.integers(4)
else: # exploit
action = Q[state].argmax()
next_state, reward, ended, out_of_time, _ = env.step(action)
target = reward + gamma * Q[next_state].max()
Q[state, action] += alpha * (target - Q[state, action])
state, done = next_state, ended or out_of_time
wins += reward
epsilon = max(0.01, epsilon * 0.999) # explore less and less
if episode % 2000 == 0:
print(f"episodes {episode - 1999:,}-{episode:,}: reached the goal {wins / 2000:.1%}")
wins = 0

tiles = env.unwrapped.desc.astype(str)
moves = np.array(list("LDRU"))[Q.argmax(axis=1)].reshape(4, 4)
print("best move per tile:", *[" ".join(row) for row in np.where(np.isin(tiles, ["H", "G"]), tiles, moves)], sep="\n ")
print("best score per tile:", *[" ".join(f"{v:.2f}" for v in row) for row in Q.max(axis=1).reshape(4, 4)], sep="\n ")

goals = 0
for game in range(10_000): # no exploring now: always the best move
state, _ = env.reset()
done = False
while not done:
state, reward, ended, out_of_time, _ = env.step(Q[state].argmax())
done = ended or out_of_time
goals += reward
print(f"greedy policy: reached the goal in {goals:,.0f} of 10,000 games")

What we got: 13.5% goals in episodes 1-2,000, 70.0% by 4,001-6,000; moves L U U U / L H L H / U D L H / H R D G, the best possible on every ice tile; 7,384 of 10,000 test games.

Sources

Transcript

Last episode ended with a little agent on a four-by-four grid. Here it is for real: a frozen lake. Reach the goal, and you get one point. Fall in a hole, and you get nothing. And the ice is slippery: press right, and you only go right one time in three.

Moving at random, it reaches the goal eighteen times in a thousand. After ten thousand tries, it reaches it seventy-four percent of the time, with some moves that look plain wrong. That's a classic interview question: how does an agent learn from rewards alone, and why must it explore?

This is Just Known. From unknown, to known. Episode thirteen: learning by reward, with reinforcement learning. Reinforcement learning has two parts: an agent, and an environment. At each step, the agent sees a state, here, which of the sixteen tiles it's on.

It picks an action: left, down, right or up. The environment answers with a new state, and a reward. As episode two put it, there are no right answers to copy, just a score. Here, the only reward is one point at the goal, and every other move pays zero. So the agent can't tell a good move from a bad one until, many moves later, it reaches the goal, or doesn't.

What the agent maximizes isn't the next reward, but the return: the sum of the rewards still to come. Usually, it's discounted: each step further away counts a little less, by a factor called gamma. With gamma at zero point nine nine, a point ten moves away is worth zero point nine one now. With gamma at zero point nine, it's worth zero point three nine. A low gamma makes an agent short-sighted.

And when the point finally arrives, which of the moves before it earned it? That's the credit assignment problem. The agent's strategy is called a policy: which move to make on each tile. And the value of a tile is the return you can expect from there, playing well. Richard Bellman's equation, from his nineteen fifty-seven book on dynamic programming, ties them together: a tile's value is what the best move pays on average, the reward plus the discounted value of wherever you land.

Next to the goal, pressing down is worth zero point eight six. Knowing the slip odds, you can solve these equations by sweeping through them until they settle. On this ice, the best possible policy reaches the goal seventy-four percent of the time within a hundred moves. But our agent doesn't know those slip odds. It has to learn from experience.

That's model-free learning, and the classic method is Q-learning, from Chris Watkins's PhD thesis in nineteen eighty-nine. Instead of one value per tile, it keeps a Q-value for every tile and move: sixty-four numbers, all starting at zero. After each move, it updates one of them. The target is the reward it just got, plus gamma times the best Q-value where it landed. Then it moves the old value a small step toward that target, a tenth of the way.

Here's a real update from our run. In episode one hundred two, the agent finally gets lucky. On the tile next to the goal, it presses up, slips sideways, and lands on the goal. Reward: one. The target is one, so that Q-value moves from zero to zero point one.

Forty-nine episodes later, from the tile above, it slips down onto that same tile. No reward this time, but the landing tile is now worth something. The target is zero point nine nine times zero point one. So value flows backward, one tile at a time, from the goal toward the start. Which move should it make while it learns?

If it always picks the best move so far, it never learns anything. At the start, every Q-value is zero, so it always takes the first move, left. And pressing left never moves you right. In ten thousand episodes, it doesn't reach the goal once. Break the ties at random, and it stumbles onto the goal in episode fifty-six, then sticks with that clumsy route: three percent.

That's exploration versus exploitation. The usual fix is epsilon-greedy: with probability epsilon, make a random move. Ours starts at one, all random, and shrinks after every episode, down to one percent. Here's the learning curve. In the first two thousand episodes, still exploring a lot, it reaches the goal thirteen percent of the time.

From episode four thousand on, about seventy. Switch off exploring and test it: seven thousand three hundred eighty-four goals in ten thousand games. It matches the best possible policy, move for move. And look at those moves. On this tile, with a hole to its right, it presses left, into the wall.

Then it stays put or slips up or down, but never into the hole. Here, beside another hole, it presses away from it. On slippery ice, the safe way forward is often sideways. Q-learning learns values, then picks the best move. Policy-gradient methods learn the policy itself: a probability for each move on each tile.

The simplest is Reinforce, from Ronald Williams in nineteen ninety-two. After a winning episode, it nudges up the probability of every move it made: episode ten's blame flowing backward, and episode three's gradient, climbing toward more reward. On the tile beside the hole, pressing left starts at a quarter, and passes ninety percent within three thousand episodes. But overall it learned more slowly: after twenty thousand episodes, it reached the goal just over half the time. Many systems combine both: an actor that picks moves, and a critic that values them.

A table works for sixteen tiles. But an Atari screen is two hundred ten by one hundred sixty pixels, in a hundred twenty-eight colors: the number of possible screens has over seventy thousand digits. So DeepMind replaced the table with episode twelve's convolutional network. It reads the screen, and outputs a Q-value for each joystick move. Two tricks kept it stable: experience replay, learning from a shuffled memory of past moves, and a target network, a copy that's updated only now and then.

In twenty fifteen, seeing just the pixels and the score, with the same design and settings for all forty-nine games, it played at a level comparable to a professional human games tester. Go was harder still. DeepMind's AlphaGo used two of episode nine's networks: a policy network, to suggest promising moves, and a value network, to judge who's winning. As episode two said, it learned from human expert games first, then got stronger by playing against itself, and searched ahead before every move. In October twenty fifteen, it beat the European champion, Fan Hui, five games to zero.

In March twenty sixteen, in Seoul, it beat Lee Sedol, one of the world's best players, four games to one. In game two came move thirty-seven. One commentator double-checked his screens, to see if there had been a mistake. By AlphaGo's own estimate, a human would play that move about one time in ten thousand, and it helped win the game. In game four, Lee Sedol answered with move seventy-eight, just as unlikely, and won.

In twenty seventeen, AlphaGo Zero skipped human games entirely. It learned only by playing itself, and after three days, it beat the version that beat Lee Sedol, a hundred games to zero. We tried self-play on tic-tac-toe. After a hundred thousand games against itself, our little learner drew every game against a perfect player. Now, what can go wrong.

An agent optimizes exactly the reward you give it, not the one you meant. In twenty sixteen, OpenAI showed an agent in a boat-racing game that paid points for hitting targets along the course. It found a lagoon, and went round and round, hitting the same three targets as they came back. It caught fire, crashed, went the wrong way, and still scored about twenty percent more than human players. We built a tiny made-up track.

Targets pay one point, the finish pays ten. Our Q-learner found the lagoon and circled it: thirty-six points in a hundred moves, and it never finished. Pay only for finishing, and it races straight to the line. As episode six warned: optimize the wrong score, and you get exactly that. You can run this yourself: about forty lines of Python, with Gymnasium and NumPy, in a few seconds on a laptop.

The code is in the description. It makes the lake, trains a Q-table for ten thousand episodes, and prints the learning curve, the best move and score for every tile, and the result of ten thousand test games. A second script has everything else in this episode, including the boat. Interview corner. What's the difference between reward, return and value?

How does Q-learning update its table? And why does the agent have to explore? Pause here, and try answering in thirty seconds.

Here's a strong answer. A reward is what one step pays. The return is the sum of the rewards to come, discounted by gamma. A state's value is the return you expect from there, and a Q-value is the same for a state and a move. Q-learning moves each Q-value toward the reward plus gamma times the best Q-value of the next state, by a small learning rate.

And the agent must explore, or a move it never tries can never prove its worth. Epsilon-greedy explores at random, less and less over time. To stand out, say that Q-learning is off-policy: it learns the best policy's values, whatever moves it makes. Ours moved completely at random for ten thousand episodes, reached the goal about one percent of the time, and still learned the best policy. Sarsa, by contrast, is on-policy.

Let's recap. In reinforcement learning, an agent acts, and learns from rewards, by trial and error. It aims for the discounted return, and values say how much return to expect. Q-learning learns them from experience, one update at a time, and has to explore to learn at all. Policy gradients learn the moves directly.

Networks replaced the tables, and self-play helped AlphaGo beat one of the world's best players. But an agent chases the reward you wrote, not the one you meant. We'll see in episode seventeen how reinforcement learning from human feedback helped turn a language model into a chatbot. Next, a new act begins: language. That's episode fourteen: words as numbers, with tokens and embeddings.

This is Just Known. From unknown, to known.

Note: one run on our laptop's CPU, fixed seeds. The race track is made up; CoastRunners is described from OpenAI's 2016 post. Pictures marked "illustration", like the Go boards, aren't real positions or data.
Narration voice generated with Google Gemini text-to-speech.