Policy Gradient: REINFORCE

The idea: learn the policy, not a value table

An agent walks in a corridor of 7 cells. It starts at S = s2. The left end, s0, is an exit that pays +0.4; the right end, s6, is a goal that pays +1. Both end the episode. The agent can move ← or →, and future rewards are discounted by γ = 0.9 per move. Going right is 4 moves for 0.9³ × 1 = 0.73; going left is 2 moves for 0.9 × 0.4 = 0.36. An episode that has not ended after 12 moves is cut and pays 0.

A policy-gradient agent does not learn what each move is worth. It learns the policy itself: in every cell s one number θ(s), and the probability of going right is π(→|s) = σ(θ(s)) = 1 / (1 + e^−θ(s)). θ = 0 means 50/50; a large θ means almost always →. On the canvas each cell shows its two probabilities, darker blue for the more likely move.

REINFORCE: one episode, then one update

The algorithm is called REINFORCE (Williams, 1992). Press Run Episode:

1. Play the whole episode with the current policy. In each cell the agent draws a random u and goes → if u < π(→|s). Nothing is learned yet. The table fills one column per move.
2. Score every move with its return G_t = γ^T−1−t · R: the reward that came after it, discounted by how far away it was.
3. Push θ of the cell where the move was made:

θ(s_t) ← θ(s_t) + α · G_t · ∇ log π(a_t | s_t)

This is gradient ascent on J(θ), the expected return from S. The policy gradient theorem says that the average of G_t · ∇ log π(a_t|s_t) over episodes is exactly ∇J(θ), so each episode gives a noisy but unbiased step uphill. The agent never needs to know the rewards or the map. The chart shows J(θ) after each episode (blue, computed exactly for this small corridor) and the return G₀ of each episode (grey).

∇ log π: which way is "more likely"?

For two actions with π(→) = σ(θ), the gradient of the log-probability is simple:

action taken	∇θ log π(a|s)	effect of a positive push
→	1 − π(→|s)	θ goes up, → more likely
←	−π(→|s)	θ goes down, ← more likely

It always points toward the action taken, and it is large when that action was unlikely: a surprise that paid off moves the policy a lot, an action the policy already takes 99 % of the time barely moves it. With a softmax over many actions (or over a vocabulary of tokens) the rule is the same: one-hot of the action minus the probabilities, as in Softmax and Cross-Entropy.

Credit goes to the whole episode

In Demo 1: one episode reaches +1 the agent first steps ← to s1, then walks → all the way to the goal. Every move gets a positive return, including the detour: the first ← in s2 has G₀ = 0.59 and its Δθ = −0.30 makes ← more likely. The later → in s2 has G₂ = 0.73 and adds +0.36. Both land on θ(s2), which ends at +0.07: the better move wins, but only a little. REINFORCE cannot tell which move earned the reward; it learns that from many episodes, on average.

The problem with all-positive rewards, and the baseline

Here every reward is ≥ 0, so every action ever taken gets pushed up. In Demo 2 the agent goes ← ← to the +0.4 exit, and both ← moves become more likely: θ(s2) = −0.18, θ(s1) = −0.20. The worse exit gets reinforced simply because it paid something. Over 50 episodes (Demo 3) this can snowball: the more often the agent goes left, the more left gets reinforced, and the policy locks into the +0.4 exit with J = 0.36.

The fix is to subtract a baseline b that does not depend on the action, and push with the advantage A = G_t − b instead. The average step is still ∇J (the baseline term averages to 0), but its sign now says "better or worse than usual". A good baseline is a critic V(s): an estimate of the return from s, learned from the same episodes with V(s) ← V(s) + 0.3 · (G_t − V(s)). Choose baseline: critic V(s) and each cell also shows V.

In Demo 5, after 20 episodes with a critic, V(s2) = 0.65. The next episode goes ← ← to the +0.4 exit, G₀ = 0.36, so A = −0.29 and Δθ(s2) = +0.24: ← becomes less likely (red in the table). With the same random numbers as Demo 3, the critic version finds the +1 goal: J = 0.69 after 50 episodes (Demo 4), against 0.36 without a baseline.

50 episodes, α = 1, same seed	J(θ) at the end	π(→|S)
no baseline (Demo 3)	0.36	0.11
critic V(s) (Demo 4)	0.69	0.91

Step size α

A policy-gradient step changes behaviour, not just a number in a table, and the next episodes are sampled from the new policy. One large step on one lucky or unlucky episode can make the policy almost deterministic, and then it stops trying the other action. In Demo 6, α = 2 with no baseline: after a few early trips to the +0.4 exit, θ(s2) falls to −3.5 and J stays at 0.35. With the same seed and α = 1 the agent finds the +1 (J = 0.68). This is the problem that TRPO and PPO solve by limiting how far one update may move the policy.

Policy gradient vs Q-learning

	Q-learning	policy gradient (REINFORCE)
learns	Q(s, a), the value of each move	θ, the policy π(a|s) directly
acts by	argmax Q plus ε-greedy	sampling from π: exploration is built in
updates	after every move, from the next state's Q	after the episode, from the actual return
on/off-policy	off-policy	on-policy: old episodes go stale
actions	needs a max over a small set	works for huge or continuous action spaces
weakness	max can overestimate	high variance, needs a baseline

For a known model, Value Iteration computes the values without any sampling. The one-state version of this problem, with no corridor, is the Multi-Armed Bandit.

From here to actor-critic, PPO and RLHF

With a critic the agent has two parts: the actor (the policy θ) and the critic (V). Replace the full return G_t with a one-step estimate r + γV(s') and the update can happen after every move: that is actor-critic (A2C, A3C). PPO is an actor-critic with a clipped update so that the new policy stays close to the old one. In RLHF a chat model is the policy, each generated token is an action, a reward model scores the answer, and PPO pushes up the log-probabilities of tokens in answers with a positive advantage: the same rule as on this page. See RLHF vs DPO.

What the page leaves out

The γ^t factor of the textbook version of REINFORCE (dropped here, as most implementations do), reward-to-go vs full-episode returns, batches of episodes per update, entropy bonuses that keep exploring, neural-network policies with shared parameters across states, continuous actions with a Gaussian policy, generalized advantage estimation (GAE), the natural gradient, TRPO and the PPO clipped objective, and off-policy corrections with importance sampling.

References

Sutton & Barto, Reinforcement Learning: An Introduction (2nd ed.), ch. 13 Policy Gradient Methods

Williams (1992), Simple statistical gradient-following algorithms for connectionist reinforcement learning (REINFORCE)

OpenAI Spinning Up: Intro to Policy Optimization

Schulman et al. (2017), Proximal Policy Optimization Algorithms