The Evolution of RL · Part 1 of 5

One Goal, and the Most Direct Way to Chase It

Every algorithm in this series is chasing the same objective. The first honest attempt at it works — and is almost unusable.

Series: Nobody Invented PPO From Scratch · ~6 min read

OBJECTIVE→REINFORCE→BASELINE→ACTOR-CRITIC→TRPO→PPO→GRPO

The one goal everything shares

Every algorithm in this series is trying to do exactly one thing: find a policy — a strategy for choosing actions — that collects as much reward as possible over time.

We write the policy as $\pi_\theta(a\mid s)$: given a state $s$, it gives the probability of taking action $a$. The loop it lives in is the most famous diagram in RL:

The agent acts; the world answers with a new state and a reward. Round and round, forever. Everything in RL is about making the blue dot smarter.

THE CAST OF SYMBOLS — EVERYTHING THIS TUTORIAL USES

$s$the state: everything the agent can see about the world right now
$a$an action the agent can take
$\pi_\theta(a\mid s)$the policy: the probability of picking action $a$ in state $s$. The subscript $\theta$ is the neural-network weights that define it — training means changing $\theta$
$r$the reward received after a single step
$\gamma$the discount factor (≈0.99): how much tomorrow's reward counts compared to today's
$R$the return: total discounted reward collected over one episode
$V(s)$the value function: expected return starting from $s$ — arrives in Part 2
$A(s,a)$the advantage: how much better action $a$ is than typical from $s$ — also Part 2
$\lambda,\ \varepsilon$two knobs you'll meet later: the GAE dial (Part 3) and the PPO clip width (Part 5)

The thing we want to maximize is the expected return — total reward, with future rewards discounted so that reward now counts a bit more than reward later:

$$J(\theta)\;=\;\mathbb{E}\big[\,r_0+\gamma r_1+\gamma^2 r_2+\cdots\big]$$

Here $\theta$ is the parameters of our policy (the weights of a neural network) and $\gamma$ is the discount factor — some number like 0.99. It's worth feeling what $\gamma$ does, because it's the knob that defines how far-sighted your agent is:

discount γ γ = 0.90

How much a reward t steps in the future is worth today: γ^t. Drag the slider. Low γ = live for the moment; γ near 1 = plan far ahead.

That's it. That's the whole objective, and it never changes for the rest of this series. Everything that follows — REINFORCE, actor-critic, TRPO, PPO — is a series of increasingly clever answers to one question: how do we compute a gradient of this thing and follow it without blowing up?

Attempt 1: REINFORCE — just follow the reward

The most direct idea possible: run the policy, watch what happens, and make good outcomes more likely.

Concretely: play out a full episode, add up the total reward $R$, then nudge the network to increase the probability of every action you took, scaled by $R$. Good episode? All its actions get reinforced. Bad one? Suppressed.

$$\nabla_\theta J\;\approx\;\sum_t \nabla_\theta \log \pi_\theta(a_t\mid s_t)\cdot R$$

That's REINFORCE (Williams, 1992). It's beautiful because it's legitimate — this really is an unbiased estimate of the true gradient of $J$. Sample enough episodes and, on average, you're pointing in the right direction.

The problem: the variance is horrendous. "On average correct" hides how wild each individual estimate is:

Each gray arrow is the gradient estimated from a single episode. The green arrow is their average, which slowly finds the true direction (blue, dashed). Individually, the estimates point almost anywhere.

Two things make it this noisy in practice:

1. Credit is assigned collectively. If the episode scored well, every action gets praised — including the terrible ones that happened to occur in a good episode. The signal for "which specific action was good" is buried under the noise of "how the whole episode went."

2. The scale of $R$ is arbitrary. Suppose every episode in your game scores between +90 and +100. Then even your worst episodes get a big positive $R$, and every action ever taken gets pushed up. The gradient spends most of its energy encoding "rewards here are large" rather than "this action was better than that one."

REINFORCE works — it just needs an enormous number of episodes to average the noise away. So the next step in the story isn't a new algorithm at all. It's a fix to this one.

THE PROBLEM WE LEAVE WITH

The gradient is honest but drowning in noise, and a +95 episode looks "good" even when it was our worst. We need a way to ask a sharper question than "was this episode good?"

SERIES← All parts NEXT · PART 2Baselines & the Advantage →