Reinforcement Learning II: TD, Q-Learning, Policy Gradients, DQN and PPO

Imagine learning to play chess, but you only find out whether you were good after the entire game, and only by a single win or loss. That is painfully slow. Humans learn from every move, and so can an agent. In the last lesson we met Markov decision processes, Bellman equations, dynamic programming and Monte Carlo. Today we build the algorithms that actually power modern reinforcement learning.

• Lesson 60
• Learn from every step

Here is the plan. First, temporal difference learning, which updates after every step. Then SARSA and Q-learning on a cliff. Then exploration, deep Q-networks, and policy gradients, including a full derivation of REINFORCE. We finish with actor-critic, PPO, reward design, and a CartPole demo. We will not re-derive the Bellman equations, so recall lesson 59 if you need them.

• TD and Q-learning
• Policy gradients
• Deep RL and PPO

Monte Carlo waits until an episode ends, then uses the full return G as the target for every visited state. Suppose the rewards are 1, 0, 0, and 5, with discount gamma equal to 0.9. The return is 1 plus 0.9 cubed times 5, which is 1 plus 3.645, giving 4.645. That number depends on every random event along the way, so it is unbiased but very noisy, and we must wait for the end.

• Wait for full return
• High variance

Temporal difference learning takes a shortcut. Instead of waiting for the true return, it uses the reward just received plus the discounted current estimate of the next state: r plus gamma times V of s prime. This is called bootstrapping, because we update a guess using another guess. It is justified by the Bellman equation you already know, which says the value equals the expected reward plus discounted next value.

• Target = r + γV(s')
• Guess from a guess

The TD zero update is: V of s becomes V of s plus alpha times delta, where delta, the TD error, equals r plus gamma V of s prime, minus V of s. Alpha is the learning rate. Delta measures surprise: how far reality, as seen one step later, differs from what we predicted. If delta is zero, our prediction was perfect and nothing changes.

• V(s) ← V(s) + α·δ
• δ = target − V(s)

Let us compute one. Say V of s is 0.5, we receive reward 1, and the next state has value 2.0. Gamma is 0.9 and alpha is 0.1. The target is 1 plus 0.9 times 2.0, which is 2.8. Delta is 2.8 minus 0.5, so 2.3. The new value is 0.5 plus 0.1 times 2.3, which is 0.73. We moved one tenth of the way toward the target.

• V(s)=0.5, V(s')=2.0
• r=1, γ=0.9, α=0.1
• New V(s)=0.73

Here is the key contrast. Monte Carlo targets are unbiased, since they are real returns, but they sum many random steps, so variance is high. TD targets involve only one random reward and one transition, so variance is low, but they are biased, because they lean on an imperfect estimate of the next state. As estimates improve, the bias fades. In practice TD often learns faster, and it works in tasks that never end.

• MC: unbiased, high variance
• TD: biased, low variance

Two classic mistakes. First, at a terminal state there is no next value, so the target must be just the reward, not reward plus gamma times some leftover number. Second, a large alpha makes estimates jump around with every noisy sample, while a tiny alpha learns glacially. Start small, like 0.1 or less, and watch your TD errors shrink over time.

• Forgetting terminal states
• Learning rate too large

V of s tells us how good a state is, but to act we need a model of the world to see where actions lead. The fix is to learn Q of s and a directly, the value of taking action a in state s. Then the greedy policy is simply the action with the largest Q. No model of the environment required, which is exactly what makes these methods model-free.

• Q(s,a) needs no model
• Pick action by argmax

Both algorithms use the same TD pattern but different targets. SARSA, named after state, action, reward, state, action, uses the Q value of the action it really takes next. Q-learning uses the maximum Q over all next actions, whatever it actually does. SARSA is on-policy: it evaluates the policy it follows. Q-learning is off-policy: it learns about the greedy policy while behaving differently.

• SARSA uses actual next action
• Q-learning uses max

Numbers make this concrete. Q of s and a is 2, reward is minus 1, gamma is 0.9, alpha is 0.5. In the next state the two actions have Q values 4 and 1, and exploration happens to pick the second one. Q-learning's target is minus 1 plus 0.9 times 4, which is 2.6, so the new Q is 2 plus 0.5 times 0.6, giving 2.3. SARSA's target is minus 1 plus 0.9 times 1, which is minus 0.1, so the new Q is 2 plus 0.5 times minus 2.1, giving 0.95.

• Q(s,a)=2, r=−1
• Next Q: 4 and 1
• Q-learning 2.3, SARSA 0.95

The classic test is cliff walking. A grid with four rows and twelve columns, start at the bottom left, goal at the bottom right, and the bottom row between them is a cliff. Each step costs minus 1. Stepping on the cliff costs minus 100 and sends you back to the start. The shortest path hugs the cliff edge. The safe path runs along the top.

• 4 by 12 grid
• Step = −1, cliff = −100

Here is the surprise. Q-learning learns the optimal edge path, because its target assumes greedy behaviour next. But while training with epsilon-greedy, the agent sometimes takes a random step and falls off the cliff, so its online reward is worse. SARSA accounts for its own exploration in its targets, so it learns the longer, safer route and earns better reward during training. Neither is wrong; they answer different questions.

• Q-learning: edge path
• SARSA: safe path

In Python this is a short loop. Keep a table of Q values, initialised to zero. For each episode, reset to the start, choose an action with epsilon-greedy, step the environment, then update the table with the target. Swap one line to switch algorithms: for Q-learning use the max over the next row of the table, for SARSA use the entry of the next action you will actually take. Remember to zero the future term at terminal states.

• Table Q[state][action]
• Update after each step

Every agent faces a dilemma. Exploit: choose the best action you know so far. Explore: try something uncertain, which might be better. Think of choosing a restaurant. Always going to your favourite is safe, but you might miss a better one. Always trying new places wastes dinners. Learning algorithms must balance both, and the balance should shift as knowledge grows.

• Exploit what you know
• Explore what you don't

The simplest strategy is epsilon-greedy. With probability epsilon pick a random action, otherwise pick the greedy one. With four actions and epsilon 0.1, the greedy action has probability 0.9 plus 0.1 over 4, which is 0.925, and each other action gets 0.025. Early on we want more exploration, so we decay epsilon, for example multiply by 0.995 each episode, down to a floor like 0.05. After 100 episodes epsilon is about 0.6.

• Random with probability ε
• Greedy otherwise
• ε decays over time

Bandits are the one-state version of this problem, and they offer a smarter rule: upper confidence bound. Score each arm as its average reward plus a bonus, c times the square root of log t over N, where N counts how often that arm was tried. At time 100 with c equal to 1, arm A has mean 0.6 after 60 pulls, so its score is 0.6 plus 0.277, or 0.877. Arm B has mean 0.5 after only 10 pulls, so 0.5 plus 0.679, or 1.179. UCB tries arm B, because uncertainty deserves a look.

• Optimism under uncertainty
• Q + c·√(ln t / N)

A Q table works for a grid with 48 cells. It cannot work for a game screen with millions of possible pixel combinations, or a robot with continuous joint angles. We need function approximation: replace the table with a function Q of s, a, and parameters theta, usually a neural network. Similar states then share knowledge, so what we learn in one place generalises to others.

• Too many states
• Generalize with a network

Training becomes regression. The target y is reward plus gamma times the max over next actions of Q. The loss is the squared difference between y and our network's output for the action taken. Say reward is 1, gamma is 0.99, the best next Q is 10, so y is 10.9. If the network currently says 9.5, the error is 1.4 and the loss is 1.96. Gradient descent, from lesson 11, nudges theta to shrink that error.

• Target y = r + γ max Q(s',a')
• Loss = (y − Q(s,a))²

Naively combining a network with Q-learning is unstable for two reasons. Consecutive frames are nearly identical, so training data is highly correlated, unlike the independent samples that gradient descent expects. And the target uses the same network we are updating, so every step moves the goalposts, like chasing your own shadow. Two ideas from the DQN work fix these problems.

• Correlated samples
• Moving targets

First, the replay buffer. Store every transition, state, action, reward, next state, and done flag, in a large memory, then train on random mini-batches, say 32 at a time. This breaks correlation and reuses data. Second, the target network: a frozen copy of the Q network used only to compute targets, refreshed every few thousand steps, or blended slowly. The targets now hold still long enough for learning to make progress.

• Store transitions, sample batches
• Freeze a copy of the network

Value methods learn Q and then act greedily. Policy gradient methods skip that step: a network outputs the probabilities of actions directly, pi of a given s with parameters theta. This handles continuous actions naturally and allows stochastic policies. Our goal is to maximise J of theta, the expected return when following the policy. We want its gradient, so we can climb.

• π(a|s;θ) as a network
• Maximize expected return J(θ)

Here is the central derivation. J of theta is the sum over trajectories tau of probability p of tau times return R of tau. Differentiate: the gradient of the sum is the sum of gradient of p times R. Now use the identity gradient of p equals p times gradient of log p, which follows from the chain rule since the derivative of log p is one over p. The sum becomes p times gradient log p times R, which is an expectation we can estimate by sampling.

• ∇p = p·∇log p
• Turns sums into expectations

The log probability of a trajectory is a sum of log policy terms plus log terms for the environment's dynamics. The dynamics do not depend on theta, so their gradient is zero and they vanish. That is a beautiful result: we never need a model of the world. We get REINFORCE: run episodes, and for each step push up the log probability of the action taken, weighted by the return that followed. Good outcomes make their actions more likely; bad outcomes make them less likely.

• Dynamics terms vanish
• ∇J = E[Σ ∇log π(aₜ|sₜ)·G]

REINFORCE has a flaw: if every return is positive, every action sampled is pushed up, and the signal is buried in noise. The fix is a baseline: subtract a number b of s from the return. This does not bias the gradient, because the expected gradient of log pi is zero, but it cuts variance. Example: two actions have probabilities 0.7 and 0.3, return is 10, baseline is 6, so the advantage is 4. For a softmax, the gradient of log pi with respect to the chosen logit is 1 minus its probability, here 0.7 for the rare action, so the push is 2.8 times the learning rate.

• Subtract b(s) from G
• Advantage A = G − b
• No bias added

What baseline should we use? Learn it. The critic is a value network estimating V of s, trained with TD. The actor is the policy. Instead of waiting for the full return, the actor uses the TD error as its advantage estimate: r plus gamma V of s prime minus V of s. This is exactly the delta from the start of this lesson. We get updates on every step, with far lower variance than REINFORCE.

• Actor: policy
• Critic: V(s)
• δ replaces G

Policy gradients have another danger. One overly large update can wreck the policy, and since future data comes from the policy itself, recovery may be impossible. Supervised learning has a fixed dataset, but here a bad step ruins the dataset too. We want to improve the policy while keeping each new policy close to the old one.

• Bad update ruins data
• Need a trust region

Proximal policy optimisation does this with a simple trick. Compute the ratio of new to old probability of the action. Multiply by the advantage, but also compute a version with the ratio clipped to between 0.8 and 1.2, and take the minimum. With ratio 1.5 and advantage 2, the plain term is 3, the clipped one is 2.4, so we use 2.4 and the incentive to push further disappears. With advantage minus 2, the plain term is minus 3 and clipped is minus 2.4; the minimum is minus 3, so harmful moves are still penalised.

• Ratio = π_new / π_old
• Clip to [0.8, 1.2]
• Take the minimum

A PPO iteration collects a batch of experience from the current policy, estimates advantages, then runs several epochs of mini-batch updates on the clipped objective, safely reusing the same data. The total loss adds a value-function loss for the critic and a small entropy bonus to keep the policy from becoming deterministic too early. PPO is popular because it is simple, fairly stable, and works across many tasks, including fine-tuning language models from human feedback.

• Collect rollouts
• Several epochs per batch
• Value loss + entropy bonus

An agent optimises the reward you wrote, not the goal you had in mind. This is reward hacking. A well-known example is a boat-racing game where an agent circled to collect bonus targets instead of finishing the race, scoring points while ignoring the course. Similar surprises appear whenever the reward is a proxy. Design rewards that match the true goal, add penalties for unwanted side effects, and watch the behaviour, not just the score.

• Agents optimize what you write
• Not what you meant

Reinforcement learning results are notoriously noisy. A single training run can look brilliant or terrible depending on the random seed alone. So run several seeds and report the average with its spread. Evaluate the greedy policy separately, with exploration turned off, because training reward includes random actions. Keep hyperparameters honest, and test on varied conditions, since an agent can overfit to one particular environment.

• Many seeds
• Evaluate without exploration
• Report spread

Now the demo. In CartPole, a pole is hinged on a cart. The state is four numbers: cart position, cart velocity, pole angle, and pole angular velocity. There are two actions, push left or push right. You get plus 1 for every step the pole stays up, and the episode ends if it tips too far or the cart leaves the track. In the standard Gymnasium version, episodes are capped at 500 steps.

• 4 state numbers
• 2 actions
• +1 per step balanced

I will not quote a score here that I did not measure, so run the accompanying script yourself and compare. The pattern to expect with a small DQN or a policy gradient agent is consistent. Early episodes are short, as the pole tips within a few dozen steps. Over training, episode length rises, though not smoothly: curves are noisy, can collapse after improving, and differ between seeds. Plot several seeds, and evaluate with exploration off.

• Early: pole falls fast
• Later: longer episodes
• Noisy curves, vary by seed

When your agent does not learn, check the basics first. Are shapes correct, and is the done flag used to cut off the future term? Does the Q value magnitude explode? Is epsilon decaying too fast, so the agent stops exploring early? Is the learning rate too high, or the target network updated too often? Fix one thing at a time, and always test your code on an easy problem before a hard one.

• Check shapes and done flags
• Watch loss and Q magnitude
• Try a smaller learning rate

Let us recap. TD learning updates from one step using a bootstrapped target, trading a little bias for much lower variance than Monte Carlo. SARSA is on-policy and Q-learning is off-policy, which is why they take different paths on the cliff. Exploration needs epsilon decay or confidence bonuses. DQN adds a replay buffer and target network. Policy gradients use the log-derivative trick, baselines, critics, and PPO's clipping. And rewards must be designed and evaluated with great care.

• TD, SARSA, Q-learning
• DQN, REINFORCE, PPO

That completes our two-part tour of reinforcement learning. In lesson 61 we turn to probabilistic machine learning: maximum a posteriori estimation, Bayesian inference, and Gaussian processes, where uncertainty becomes a first-class citizen.

• Lesson 61
• MAP, Bayes, Gaussian processes
• Subscribe