Inventing Reinforcement Learning

Forget theory. We're going to play a game. The game is called CartPole — there's a cart on a track with a pole balanced on top. You can push the cart left or right. The goal: keep the pole from falling over as long as possible.

The twist? You play using Python code.

First, create a CartPole game. Run env.reset() — it gives you back 4 numbers. Print them. What do you think they mean?

The 4 numbers describe the world:

You have two possible actions: 0 = push left, 1 = push right.

Call env.step(action) with action 0 (push left) or 1 (push right). It returns 5 things. Print them all and figure out what each one means.

Write a loop that keeps taking random actions (0 or 1) until the game ends (terminated or truncated). Count how many steps you survived — that's your score. Run it a few times. What scores do you get?

Before writing any strategy, just think:

The pole is tilting to the RIGHT. Should you push the cart left or right to keep it balanced?

The pole is tilting to the LEFT. Which way should you push?

The pole is nearly vertical but moving (rotating) fast to the right. What should you do?

Random actions give terrible scores. You already have intuition about what to do — let's turn it into code.

In Exercise 1.3 you wrote a game loop. You'll be testing many different strategies in this chapter, so let's turn that loop into a reusable function.

Write play_game(policy_fn, env) that plays one full episode using policy_fn (a function that takes an observation and returns an action) and returns the total reward.

Then write evaluate(policy_fn, env, n=100) that plays n games and returns the average score.

Test them with a random policy: evaluate(lambda obs: np.random.choice([0, 1]), env).

Write a function my_policy(obs) that takes the 4 observation numbers and returns 0 (left) or 1 (right).

Use your intuition from the previous exercise: if the pole is tilting right (positive angle = obs[2] > 0), push right (return 1). Otherwise push left.

Evaluate it over 100 episodes. How much better is it than random?

Your angle-only policy probably scores around 40–60. Can you do better?

Try using the angular velocity (obs[3]) too. If the pole is tilting right AND the angular velocity is positive (falling faster to the right), it's more urgent to push right. Experiment with different rules. Can you consistently score above 200?

Optional stretch — skip this if you want to move on. You won't miss anything later.

Figure out all possible ways you can write the policy function to maximize the score. Try at least 3 different heuristics and record their average scores.

Some ideas to explore:

• Use all 4 observations, not just angle and angular velocity
• Try different combinations and multipliers
• Try non-linear rules (if-else chains, thresholds)

What's the highest average score you can achieve by hand-tuning?

You just played a game, wrote a strategy function, tested it, tweaked it, and repeated. Before we go further, give each piece a short name:

The game itself (CartPole) — what would you call the 'world' the player interacts with?

The 4 numbers you receive each step — what are they?

Push left / push right — what is this?

The number of steps survived (your score) — what is this?

Your function (my_policy) — what would you call it?

The process of playing → seeing the score → tweaking your function → replaying — what is this?

Here are the names computer scientists settled on:

This is the closest thing to how humans learn. You don't get a textbook — you try stuff, get feedback, and adapt. A child learning to walk, a dog learning tricks, you learning to drive — all reinforcement learning. That's life!

Map the RL terms to a real-life example: a child learning to ride a bicycle.

What is the environment?

What are the observations (state)?

What are the actions?

What are the rewards and penalties?

What is the policy?

Look at your best heuristic from Part 2. It probably looked something like: "if angle > 0, go right" or "if angle + 0.5 × angular_velocity > 0, go right." That's really just: multiply each observation by some number, add them up, and check the sign. Your action is a function of the observations.

Write a policy that computes score = w1 * obs[2] + w2 * obs[3] (angle and angular velocity). If score > 0, go right. Otherwise go left.

Try these weight combinations and record the average score for each:

• w1=1, w2=0
• w1=1, w2=1
• w1=1, w2=0.5
• w1=0.5, w2=1

Now use ALL 4 observations. Write weighted_policy(obs, weights) that computes:

weights[0]*obs[0] + weights[1]*obs[1] + weights[2]*obs[2] + weights[3]*obs[3]

Go right if positive, left otherwise. This is a dot product — np.dot(weights, obs) in numpy.

Try weights = [0, 0, 1, 0.5] (ignoring cart position and velocity). Then try [0.1, 0.5, 1, 0.5].

The numbers you've been manually tuning — w1, w2, w3, w4 — are called policy parameters. The function that maps observations to actions is the policy. The entire goal of reinforcement learning just became a concrete optimization problem:

Find the weights (policy parameters) that maximize the average reward.

But how? Trying them by hand is tedious. We need a strategy.

You need 4 good numbers. How hard can it be?

One idea: try ALL possible combinations of the 4 weights.

Each weight is a real number (like 0.37 or -1.2). How many possible values does a single weight have?

If you discretized each weight to 100 values (from -1 to 1 in steps of 0.02), how many combinations of 4 weights would you need to try?

Why is this approach impractical?

Think for a minute. What strategies can YOU think of for finding 4 good weight values without trying every combination? Write down at least 2 ideas before looking at hints.

Strategy 1?

Strategy 2?

Generate 100 random weight vectors (each weight between -1 and 1). Evaluate each one over 5 episodes. Print the best weights and their score.

Random search found a decent solution, but can we do better? Here's an idea:

1. Start with 100 random weight vectors
2. Evaluate all of them
3. Keep only the top 20

Now you have 20 good weight vectors. But you need 100 for the next round. How would you get from 20 back to 100? And then what? Design the rest of this algorithm yourself, implement it, and run it for 10 generations. Print the best score each generation.

What you just invented is called a Genetic Algorithm. See the analogy?

You found good policy parameters without any calculus — just random variation and selection. Evolution works!

Optional stretch — skip this if you want to move on. You won't miss anything later.

Can you think of ways to make the genetic algorithm better? Try implementing any of these ideas:

• Crossover: instead of just mutating one parent, combine two parents (e.g., take weights 0-1 from parent A and weights 2-3 from parent B)
• Adaptive mutation: start with large noise (±0.5) and reduce it each generation
• Elitism: always keep the single best individual unchanged
• Larger population or more generations

Try your ideas and see if they beat the basic version! If you invent something new, we want to hear about it.

Genetic algorithms work but feel brute-force. You might remember a more targeted approach: compute the gradient, move in the direction that improves the objective. Can we do that here?

Here's the idea: for each weight, nudge it slightly (+0.01), play a few games, nudge it the other way (-0.01), play again. The difference in scores tells you which direction improves that weight.

This is called finite differences — estimating the gradient by measuring the effect of small changes.

Take your best weights from the genetic algorithm (or start with [0, 0, 1, 0.5]). Estimate the gradient and update for 20 steps. Does the score improve?

Before moving on, make sure you understand what you just computed. Look at the gradient from one of your steps.

The gradient is a vector of 4 numbers — one per weight. If gradient[2] is large and positive, what does that tell you about weight 2?

If gradient[0] is close to zero, what does that mean?

In plain English, what is the gradient telling you? (No calculus needed — think about what you measured.)

The gradient approach probably gave erratic results — the score jumps around instead of steadily improving. Why?

If you play 10 games with the EXACT same weights, do you always get the same score? Why not?

If the score varies by ±30 between runs, and you're trying to detect a difference of 0.01 in one weight, can you reliably measure the gradient?

So the noise kills the gradient signal. But there's an even deeper problem.

When you push right at step 5, was it the right move? You won't know until the game ends — maybe at step 200. The total score doesn't tell you WHICH of your 200 individual actions were good and which were bad. This is called the credit assignment problem: how do you assign credit (or blame) to each action?

Let's tackle this problem step by step.

You played a game and scored 150 steps. At step 100, you pushed right.

Was pushing right at step 100 a good action? How would you know?

Which reward is more relevant to the action at step 100 — the reward at step 101 or the reward at step 150?

If you got a reward of 1 at each step, how would you assign 'credit' to the action at step 100? Should nearby rewards count more than distant ones?

You agreed that nearby rewards should count more than distant ones. Now design a formula.

Suppose you played 5 steps and got rewards [1, 1, 1, 1, 1]. You want to compute a "total credit" for the action at step 0.

If you just sum all future rewards equally, what's the credit for step 0? (1+1+1+1+1 = 5). What's the problem with this?

What if each future reward was worth a little LESS than the one before it — say 99% as much? Step 0's own reward counts fully (×1), step 1's reward counts ×0.99, step 2's counts ×0.99², etc. What would the credit for step 0 be?

What should the credit for the LAST step (step 4) be? It has no future rewards.

What would you call that 0.99 multiplier?

Write compute_discounted_rewards(rewards, gamma=0.99) that implements the credit system you just designed. It takes a list of rewards (one per step) and returns the discounted return for each step.

Play a game, compute discounted rewards, and look at the values. Run the code below. What do you notice about the numbers — are any of them negative?

All the credits are positive, so every action looks good. But some were clearly better than others.

How would you fix this so that above-average actions get POSITIVE credit and below-average actions get NEGATIVE credit? Write a function that does this and apply it to the discounted rewards.

So far you've been hand-tuning weights or using evolution. But there's something unsatisfying — you're searching OUTSIDE the game. You try weights, play a full game, check the score, try new weights. What if the model could learn FROM each game it plays?

Your current policy is deterministic: if weights @ obs > 0, always go right. Always. Every single time.

If the policy always makes the same decision in the same state, can it ever discover that the OTHER action might have been better?

What if instead of 'always go right when score > 0', the model said 'go right with 70% probability'? Sometimes it would go left — accidentally. What could you learn from those accidents?

If an accidental action leads to a HIGHER reward than usual, what should the model do next time?

You want to convert your weighted_policy from a hard yes/no decision into a probability. Instead of "go right if weights @ obs > 0", output a PROBABILITY of going right — a number between 0 and 1.

Your current policy computes z = weights @ obs, which can be any number (positive, negative, large, small). You need a function that takes z and outputs a value between 0 and 1.

When z is large and positive (strong signal for 'right'), the probability should be close to what?

When z is large and negative (strong signal for 'left'), the probability should be close to what?

When z = 0 (no signal either way), the probability should be what?

Can you think of a formula that maps any number to the range (0, 1) with these properties? Hint: think about what happens to $\frac{1}{1 + \text{something}}$ when that 'something' is very large vs. very small.

Now use the sigmoid to build a probabilistic policy. Write:

• prob_right(obs, weights) — returns sigmoid(weights @ obs)
• sample_action(obs, weights) — samples an action from the probability

Test with weights = np.zeros(4). What probability do you get? Why?

Your model outputs a probability and samples an action. After the game, you have discounted rewards telling you which actions were good (positive) and which were bad (negative).

If action = 'go right' and the discounted reward was POSITIVE (good action), should the model make 'go right' MORE or LESS likely next time?

If action = 'go right' and the discounted reward was NEGATIVE (bad action), what should happen?

You want to INCREASE reward. If you had a gradient (the direction that increases probability of the chosen action), what should you do — move WITH the gradient or AGAINST it?

To compute a gradient, you need a single number that measures how likely the chosen action was. The probability $p$ does that. But across many steps, probabilities multiply ($p_1 \times p_2 \times ...$), which is awkward for optimization. What mathematical function turns products into sums?

You need the gradient — the direction to push the weights to make the chosen action more likely. Instead of deriving it with calculus, let's measure it using finite differences (the same trick from Exercise 6.1).

Write a function estimate_log_prob_gradient(obs, action, weights, eps=0.001) that:

1. For each weight $i$, nudge it by $+\epsilon$ and $-\epsilon$
2. Compute $\log(p)$ each time (where $p$ is the probability of the chosen action)
3. Gradient$[i] \approx (\log p_{+} - \log p_{-}) / (2\epsilon)$

Then compare your numerical gradient to this formula (which comes from calculus):

• If action = 1 (went right): gradient $= (1-p) \times \text{obs}$
• If action = 0 (went left): gradient $= -p \times \text{obs}$

Do the numbers match?

The gradient formulas are:

• Action = 1 (went right): gradient $= (1-p) \times \text{obs}$
• Action = 0 (went left): gradient $= -p \times \text{obs}$

You verified these numerically — they tell you which direction to push the weights to make the chosen action more likely. Multiply by the reward signal and you have a learning rule: reinforce good actions, suppress bad ones.

From here on we'll use the analytical formulas (they're faster than finite differences and give the same answer).

Write play_episode(env, weights) that plays one full game using the probabilistic policy and records everything that happens:

1. At each step, compute the probability with prob_right
2. Sample an action from the probability
3. Compute the gradient for that action
4. Record: observation, action, reward, and gradient

Return all four lists. Test it — play one episode and print the number of steps and the total reward.

Now write reinforce_update(env, weights, lr=0.01) that uses play_episode to learn from one game:

1. Play an episode and get the recorded gradients and rewards
2. Compute discounted rewards (your compute_discounted_rewards)
3. Normalize them (your normalize function)
4. Multiply each step's gradient by its normalized reward
5. Sum all the weighted gradients
6. Update: weights += lr * total_gradient (gradient ASCENT!)

Return (weights, total_score).

Run the REINFORCE update in a loop for 1000 episodes. Record the score each episode and plot it. Does the agent learn to balance the pole?

After training, evaluate the final policy over 100 fresh episodes with evaluate() and compare to the random baseline (~20).

You just invented the REINFORCE algorithm (Williams, 1992)! Look at what happened:

• The model started knowing nothing (all weights = 0, coin-flip decisions)
• It played games, making random choices
• Good accidents (high reward) → gradient got amplified → model repeats those choices
• Bad accidents (low reward) → gradient got reversed → model avoids those choices
• Over hundreds of games, the model converged on a good policy

No one told the model the rules of physics. It learned entirely from its own experience — just like you did in Part 1, but automatically.

REINFORCE works, but notice something: it has to finish the ENTIRE game before it can learn anything. It plays 200 steps, then looks back and assigns credit. Can we do better?

Think about two situations mid-game:

The pole is nearly vertical, barely moving. How many more steps do you think you'll survive? What's your expected future reward from here?

The pole is nearly horizontal, falling fast. Expected future reward?

You just made an intuitive prediction about future reward based on the state. If a MODEL could make this prediction, why would that be useful for learning?

Build a simple linear model: given a state (observation), predict the total future reward.

$$V(\text{obs}) = \mathbf{v} \cdot \text{obs}$$

This is linear regression — input = observation (4 numbers), target = actual discounted return at that step, loss = $(V(\text{obs}) - \text{target})^2$.

To train it: play 200 episodes using your trained REINFORCE policy (the weights from Exercise 7.5), compute actual discounted rewards with compute_discounted_rewards, and update the value weights to reduce the squared error.

Your value model works — but it still needs compute_discounted_rewards, which requires the FULL list of rewards from a completed episode.

Can you think of a way to estimate the discounted return at step t WITHOUT finishing the game?

You have: the reward at step t, and the value model's prediction for the NEXT state. The discounted return at step t is: reward[t] + gamma × (discounted return at step t+1). But the discounted return at step t+1 is approximately... what?

So the discounted return at step t is approximately: reward[t] + gamma × V(next_state). Does this require finishing the game?

Implement the idea you just derived. At each step, compute:

• target = reward + gamma * V(next_state) (your estimate of the true return)
• error = target - V(current_state) (how wrong the value model was)
• Update: value_weights += lr * error * obs

Write td_update(obs, reward, next_obs, done, value_weights). When the game is done, V(next_state) = 0 (no future rewards).

Look at the error from td_update: error = reward + gamma * V(next_state) - V(current_state).

If the error is positive, it means: what you actually got (reward + predicted future) is MORE than what you expected (V(current)). Was the action that got you here good or bad?

If the error is negative, was the action good or bad?

Compare this error to the normalized discounted rewards from REINFORCE. Which gives a more specific signal about whether an action was good?

You trained the value model on 200 episodes in Exercise 8.2. Now let's see how its advantage signal compares to the normalized discounted rewards from REINFORCE.

Play an episode using your REINFORCE policy (weights from Exercise 7.5) and compute both:

1. The normalized discounted rewards (REINFORCE's signal)
2. The TD errors from your trained value model (advantages)

Print the standard deviation of each. Which is more stable?

You just invented several things at once:

• A model that predicts future reward from a state = the value function (or critic)
• Training it step-by-step using reward + gamma × V(next_state) = Temporal Difference (TD) learning
• The error reward + gamma × V(next) - V(current) = the advantage (or TD error)

The value model doesn't pick actions — it just evaluates states. That's why it's called the critic: it watches the policy play and judges how well it's doing.

A related approach called DQN (Deep Q-Network) uses a neural network to predict the value of each action rather than each state — but the core idea of TD learning is what you built here.

You now have two models:

1. The actor (REINFORCE policy from Part 7) — picks actions
2. The critic (value model from Part 8) — evaluates states

What if you used BOTH together? The critic tells the actor how good its actions are (via advantages), and the actor uses that feedback to improve. The critic learns alongside the actor, getting better at evaluating states as the actor gets better at playing.

Think about how to combine the actor and critic:

In REINFORCE, you multiplied gradients by normalized discounted rewards. But you now have a better signal — the advantage (TD error). What should you multiply the gradients by instead?

Both models learn at the same time. What does the actor learn from? What does the critic learn from?

REINFORCE waits until the end of the episode. With a critic providing advantages at each step, do you still need to wait?

Before writing the full training loop, let's trace through ONE step of the combined update by hand. Use the code below to set up a single step, then compute and print each piece:

1. The actor's probability and sampled action
2. The critic's predicted value for the current AND next state
3. The TD error (advantage)
4. The actor's gradient
5. The updated actor weights and critic weights

This is the same math from Parts 7 and 8 — you're just combining them.

Wrap the logic from Ex 9.2 into a reusable function:

Write actor_critic_train(env, n_episodes=2000, actor_lr=0.01, critic_lr=0.005, gamma=0.99) that:

1. Initializes actor and critic weights to zeros
2. For each episode, runs the combined update at each step
3. Records the score each episode
4. Returns (actor_weights, critic_weights, scores)

Train for 2000 episodes, plot the scores, and evaluate the final policy.

You've built several approaches. Let's see three of them side by side — the ones that produce a score each episode, so we can plot learning curves:

1. Random — baseline (random actions, no learning)
2. REINFORCE — 1000 episodes of policy gradient
3. Actor-Critic — 1000 episodes of combined learning

Plot them together. Which learns fastest? Which achieves the highest score?

Look at how far you came:

1. You played CartPole with random actions (scored ~20)
2. You hand-coded a heuristic (scored ~60)
3. You evolved weights with a genetic algorithm (scored ~200+)
4. You tried gradient estimation (learned why it's noisy)
5. You invented discounted rewards (credit assignment)
6. You invented REINFORCE (policy gradient)
7. You invented a value function (the critic)
8. You combined them into Actor-Critic

Every single one of these is a real algorithm used in production. The only difference between yours and DeepMind's is scale — they use massive neural networks, millions of episodes, and GPU clusters. The ideas are identical.