How Modern AI Models Work · Course book
Chapter 3: Learning From Reward
Most machine learning needs examples labelled with the right answer. Reinforcement learning needs none. A program tries things, is told only how well it did, and gradually works out what to do. It is how programs have learned to play games better than people and how robots learn to walk. Building such a system with no libraries, in a low-level language like C, forces every hidden part into view. This chapter explains those parts: the learning loop, the meaning of reward over time, the automatic calculus that makes training possible, and the rule that turns experience into improvement.
The loop: agent, environment and reward
Reinforcement learning has two characters. The agent is the learner that makes decisions. The environment is everything else: the game or world the agent acts in. They take turns in a loop, shown in Figure 3.1.
At every step the agent receives the state, a description of the current situation. It picks an action. The environment responds with a new state and a reward, a single number saying how good that outcome was. The agent's sole aim is to collect as much reward as possible over time.
Take the game of Snake, a common first project. The snake moves around a grid eating food and growing longer, and the game ends if it hits a wall or itself. The pieces map across neatly.
| Term | Meaning | In a game of Snake |
|---|---|---|
| Agent | The learner and decision-maker | The program controlling the snake |
| Environment | The world the agent acts in | The grid, the food and the rules |
| State | What the agent is told about the situation | Numbers such as: is there danger ahead, left or right, and in which direction is the food? |
| Action | A choice available to the agent | Go straight, turn left or turn right |
| Reward | A number scoring the outcome of a step | For example +10 for eating food, -10 for a collision, 0 otherwise |
| Policy | The agent's rule for choosing actions | A small neural network: state in, a probability for each action out |
| Episode | One complete run from start to finish | One game, until the snake dies |
Two design decisions here are made by a person and matter greatly. The first is state encoding: turning the game into a short list of numbers. Too little information and the agent cannot learn; too much and learning is slow. The second is the reward scheme. The agent pursues exactly what is rewarded, not what was intended, so a careless scheme produces surprising behaviour, such as a snake that circles for ever to avoid dying.
Reward now or reward later
The difficulty at the heart of the subject is delay. The snake is rewarded when it eats, but the moves that mattered were the earlier ones that brought it there. How should credit for a reward be shared among the steps leading up to it?
The standard answer is the return: for each step, the total reward that follows it, with later rewards counted for less. A discount factor, written with the Greek letter gamma and set a little below 1, is applied once for every step of delay. With gamma at 0.9, a reward one step away counts for 0.9 of its value, two steps away for 0.9 × 0.9 = 0.81, and so on.
Suppose an episode has three steps with rewards 0, 0 and 10: the snake eats on the third step. The returns are worked out from the end backwards, each one being that step's reward plus 0.9 times the return of the step after.
- Step 3: the return is 10.
- Step 2: the return is 0 + 0.9 × 10 = 9.
- Step 1: the return is 0 + 0.9 × 9 = 8.1.
Every step leading to the food receives credit, a little less the further back it lies.
The discount factor sets how far-sighted the agent is. Near 1, it plans far ahead; lower, and it cares mostly about the next few steps.
The machinery underneath: automatic differentiation
The policy is a neural network, and training a network means adjusting its weights. To adjust them we must know, for every weight, how the final result would change if that weight were nudged. That quantity is a gradient. Frameworks compute gradients behind the scenes; built by hand, the mechanism turns out to be simple.
Every calculation, however large, is a chain of elementary operations such as addition and multiplication. Record them as they happen and you have a computational graph. Take z = x × y + x, with x = 2 and y = 3.
Forward pass. Compute step by step, remembering each intermediate result. First a = x × y = 6. Then z = a + x = 8.
Backward pass. Walk the chain in reverse, asking at each operation how its output responds to its inputs. Only two local rules are needed. For an addition, each input passes the gradient through unchanged. For a multiplication, each input receives the gradient multiplied by the other input.
- Start with a gradient of 1 at z.
- The addition z = a + x passes 1 to a and 1 to x.
- The multiplication a = x × y passes 1 × y = 3 to x and 1 × x = 2 to y.
- x was used twice, so its contributions add: 1 + 3 = 4. The gradient for y is 2.
Check it. Raise x from 2 to 2.01: z becomes 2.01 × 3 + 2.01 = 8.04, an increase of 0.04, which is 4 times the nudge of 0.01. This procedure is automatic differentiation, and it is exactly backpropagation. A network with millions of weights is handled the same way, only with a longer chain.
| Building block | What it must do | What makes it hard in C |
|---|---|---|
| Matrix structure | Hold a grid of numbers with its dimensions | Memory must be requested and released by hand |
| Operations | Multiply and add matrices; apply functions such as ReLU and softmax | Each needs a matching rule for the backward pass |
| Graph recording | Remember every operation and its inputs during the forward pass | The graph is rebuilt on every step and must be freed afterwards |
| Backward pass | Visit operations in reverse and accumulate gradients | Getting the order right when a value is used more than once |
| Environment | Run the game: states, moves, collisions, rewards | Ordinary game programming, but it must be fast |
| Training loop | Play, compute returns, update the weights, repeat | Keeping thousands of episodes from leaking memory |
In a language like Python, memory is reclaimed automatically. In C, every block requested must be released by the programmer. Training runs the forward and backward passes millions of times, so a tiny leak in each would exhaust the machine. A common solution is to take one large block of memory in advance, hand out pieces of it during a step and reset the whole block at the end of the step, an arrangement often called an arena.
From scores to choices
The policy network ends by producing one raw score for each action. Two small functions deserve a note because they appear in almost every network.
ReLU is applied between layers. It replaces negative numbers with zero and leaves positive numbers alone, so -2 becomes 0 and 3 stays 3. Without some such step, a stack of layers would collapse into the equivalent of a single layer.
Softmax turns the final scores into probabilities by raising e to the power of each score and dividing by the total. Written naively, it can fail. With scores of 1000, 999 and 998, the value of e1000 is too large for a computer's ordinary number format, and the result is an error. The remedy is to subtract the largest score from all of them first, giving 0, -1 and -2. Now the powers are 1, 0.368 and 0.135, which total 1.503, and the probabilities are 0.665, 0.245 and 0.090. The answer is identical to what the true calculation would give, because subtracting the same amount from every score does not change the ratios. This is the numerically stable form.
The agent then chooses its action at random according to those probabilities. The randomness is deliberate. An agent that always took its current favourite would never discover that another action is better. Trying uncertain options is called exploration; using what is already known is exploitation, and learning needs both.
Learning from experience: the policy gradient
All the pieces now combine into a training method called the policy gradient. Its idea fits in a sentence: make the actions that turned out well more likely, and those that turned out badly less likely.
- Play. Let the agent play using its current policy, recording every state, action and reward. Such a recorded run is called a rollout, and the records are kept in a buffer.
- Score. Compute the discounted return for every step, as in the worked example.
- Compare. Subtract a baseline, a typical return such as the average, to give the advantage. A step with a return of 8.1 against a baseline of 5 has an advantage of +3.1: better than usual. One with a return of 2 has an advantage of -3: worse than usual.
- Update. Use the backward pass to find how each weight affects the probability of the action taken, then shift the weights to raise that probability where the advantage is positive and lower it where the advantage is negative, in proportion to its size.
- Repeat for thousands of episodes.
The baseline matters more than it appears. If every return in a game is positive, then without a baseline every action would be encouraged and only the size of the encouragement would differ, which makes learning slow and erratic. Measuring against the average turns the signal into a clear "better than expected" or "worse than expected".
At first the snake moves at random and dies almost at once. Occasionally it stumbles into food, and those moves are reinforced. Over many games the lucky accidents accumulate into a strategy. Nobody ever tells the agent the rules; it infers them from consequences alone.
Check your understanding
- In reinforcement learning, what is the difference between a state, an action and a reward?
- An episode has rewards 0, 0, 0 and 10, and the discount factor is 0.9. What is the return at the first step? (Answer: working backwards, 10, then 9, then 8.1, then 7.29.)
- For z = x × y + x with x = 5 and y = 2, what are z and the gradients for x and y? (Answer: z = 15; the gradient for x is 1 + y = 3; the gradient for y is x = 5.)
- Why is the largest score subtracted before computing softmax, and why does this leave the answer unchanged?
- A step has a return of 4 and the baseline is 6. What is the advantage, and will the action become more or less likely? (Answer: -2, so less likely.)
- Why does the agent pick actions at random according to their probabilities instead of always taking the most probable one?
This course book is available to read online only at tech-academy.chrysolites.org.