==============================================================================================
RAHUL'S ML BLOG -- notes on machine learning, worked out by hand est. 2026
==============================================================================================
home | about | archive | glossary | contact
----------------------------------------------------------------------------------------------
CHAPTER 16 . POLICY GRADIENT -- learning the policy itself, not a worth
Propose and Grade: Actor-Critic by Pencil
============================================================================================
Every machine in this book so far learned a WORTH and then acted greedy on it. The
worth was always a middleman: you wanted a policy -- what to DO -- but you learned a
number and read the policy off it by grabbing the biggest. This post drops the
middleman and learns the policy straight.
A spot = one place in the world. A move = something you can do. A reward = a number
the world pays on a move. A policy = the rule that says which move to make. Three
cracks show in learn-a-worth-then-grab-the-biggest. Grabbing the biggest needs a max
over moves -- fine for a few buttons, a nightmare when the move is a real-numbered
dial (a steering angle has infinitely many settings to max over). The policy it
gives is all-or-nothing: a hair's change in two close worths flips the chosen move
from one to the other, a jolt. And sometimes the best policy is honestly MIXED --
"go left 70% of the time" -- which a grab-the-biggest rule can never say. So learn
the policy as its own thing, a set of knobs you can tune smoothly.
SO KEEP A PREFERENCE PER MOVE, AND SOFTMAX IT INTO CHANCES
Give every move at a spot a PREFERENCE -- a plain score, high means "lean toward
this move." Build it the linear tile way: lay two coarse shifted rulers over the
one-dial world (position on [0,1]), so a spot lights one tile per ruler; a
preference is the sum of that move's weights at the lit tiles. Here position 0.3
lights tiles A0 and B1. Three moves -- left, stay, right -- each with its own row
of weights:
move \ tile : A0 A1 B0 B1 B2
left : -1.0 ... 0.0 0.0 0.0
stay : 0.0 ... 0.0 1.0 0.0
right : 1.0 ... 0.0 1.0 0.0
At position 0.3 (lit tiles A0, B1) the three preferences are sums down those two
columns:
h(left ) = -1.0 + 0.0 = -1.0
h(stay ) = 0.0 + 1.0 = 1.0
h(right) = 1.0 + 1.0 = 2.0
Preferences are not chances -- they can be negative, and they do not add to 1. Turn
them into chances with a softmax: raise e (2.71828...) to each preference, then
divide each by the total, so all three are positive and sum to 1. Subtract the
biggest preference first (here 2.0) so the e's never blow up -- softmax reads only
the gaps between preferences, so the shift changes nothing:
shifted: h - 2.0 = [ -3 , -1 , 0 ]
e^(-3) = 0.0498 e^(-1) = 0.3679 e^(0) = 1.0
total = 0.0498 + 0.3679 + 1.0 = 1.4177
pi(left ) = 0.0498 / 1.4177 = 0.0351
pi(stay ) = 0.3679 / 1.4177 = 0.2595
pi(right) = 1.0 / 1.4177 = 0.7054 (check: 0.0351 + 0.2595 + 0.7054 = 1.0)
The biggest preference became the biggest chance, but the others kept a real slice.
The policy is now a smooth dial: shift a preference a hair and the chances slide a
hair -- no jolt.
Another spot, preferences h = [2, 0, 1]. Shift, lift by e, divide.
What are the three chances?
CHECK: shifted = [0, -2, -1]; e^0 = 1, e^(-2) = 0.1353, e^(-1) = 0.3679
total = 1 + 0.1353 + 0.3679 = 1.5032
pi = [ 1/1.5032 , 0.1353/1.5032 , 0.3679/1.5032 ]
= [ 0.665 , 0.090 , 0.245 ] (sums to 1.000)
WHICH YOU SAMPLE FROM, NOT ARGMAX
You do not grab the biggest chance. You ROLL. Lay the three chances end to end on a
0-to-1 line and drop a random number:
|---left---|--------stay--------|------------------right------------------|
0 0.0351 0.2946 1.0
roll r = 0.63 -> lands in right's slice [0.2946, 1.0) -> take RIGHT
Most rolls land in right (it owns 70% of the line), but stay and left still come up
sometimes. The wandering is built into the policy itself, not bolted on like the
epsilon of the value machines -- and it is exactly what the next nudge will tune.
BUT TO NUDGE A PREFERENCE YOU NEED A YARDSTICK -- A CRITIC
You took "right" and the world paid a reward. Should "right" become MORE likely
here? Only if it did better than you had any right to expect. A raw reward cannot
tell you that -- a +1 is great in a bad spot, lousy in a great one. So keep a second
learner, a CRITIC, that holds a WORTH per spot -- a baseline of how good this spot
already is. (The preference-keeper is the ACTOR; the worth-keeper is the CRITIC.
Actor proposes a move; critic grades how it went.)
The critic's worth is the same linear tile sum, its own row of weights at the lit
tiles:
tile : A0 A1 B0 B1 B2
critic: 0.2 0.3 0.0 -0.1 0.0
V(0.3) = critic[A0] + critic[B1] = 0.2 + (-0.1) = 0.1 (worth of the spot we left)
V(0.6) = critic[A1] + critic[B1] = 0.3 + (-0.1) = 0.2 (worth of the spot we landed on)
WHICH MEASURES "BETTER THAN EXPECTED": THE DIFFERENTIAL TD ERROR
The pendulum -- the standard toy here, a pole you swing up and balance -- never
ends. There is no goal to reach, no episode to finish; it just runs forever. With no
finish line there is nothing to discount toward, so you do not chase a discounted
pile. You chase the average reward PER STEP -- call your running guess of it R-bar
-- and you ask of each move: did it beat that average?
That gap is the differential TD error. Take the reward, subtract the average you
expected to earn this step, and add the change in worth from leaving to landing:
how wrong = reward - R-bar + V(landing) - V(left)
Worked, with reward = 1, R-bar = 0.5, and the two worths above:
how wrong = 1 - 0.5 + V(0.6) - V(0.3)
= 1 - 0.5 + 0.2 - 0.1
= 0.6
A positive 0.6: this step earned more than the running average and landed on a
slightly better spot than it left. Better than expected. That single number now
drives BOTH learners.
SO NUDGE BOTH: THE CRITIC TOWARD THE TRUTH, THE ACTOR TOWARD WHAT BEAT THE AVERAGE
Three nudges, all driven by the same how-wrong = 0.6. Sizes: 0.1 for each. Read old
worths for the how-wrong FIRST (above), THEN write -- a guess leaning on a guess,
the same read-then-write order as every one-sample nudge on this blog.
The average-reward guess crawls toward what it keeps seeing:
R-bar = 0.5 + 0.1 x 0.6 = 0.56
The critic crawls its worth for the spot you LEFT toward the how-wrong, on that
spot's lit tiles (A0, B1) -- the linear value nudge:
critic[A0] = 0.2 + 0.1 x 0.6 = 0.26
critic[B1] = -0.1 + 0.1 x 0.6 = -0.04
The actor is the new part. Make the move you TOOK more likely when how-wrong is
positive, and the moves you did NOT take less likely -- each in proportion to how
probable it already was. The nudge to move a's preference weight, on each lit tile,
is
actor[a][tile] += size x how-wrong x ( took-it? - pi(a) )
where "took-it?" is 1 for the move actually taken and 0 for the rest. That
(took-it? minus pi(a)) is the whole trick: the taken move gets (1 - its chance) --
a shove UP, biggest when it was UNlikely -- and every other move gets (0 - its
chance), a shove DOWN sized by its own odds. Worked on the lit tiles A0 and B1,
how-wrong 0.6, size 0.1, the chances from above:
right (taken): 0.1 x 0.6 x (1 - 0.7054) = 0.06 x 0.2946 = 0.0177 -> up
stay : 0.1 x 0.6 x (0 - 0.2595) = 0.06 x (-0.2595)= -0.0156 -> down
left : 0.1 x 0.6 x (0 - 0.0351) = 0.06 x (-0.0351)= -0.0021 -> down a hair
(Add the three shoves: 0.0177 - 0.0156 - 0.0021 = 0. Exactly zero, always --
because (took-it? - pi) sums to 1 - 1 = 0 across the moves. The actor never
creates preference out of thin air; it reshuffles it toward what worked.)
Add each to BOTH lit tiles of that move's row:
actor[right][A0]: 1.0 + 0.0177 = 1.0177 actor[right][B1]: 1.0 + 0.0177 = 1.0177
actor[stay ][A0]: 0.0 - 0.0156 = -0.0156 actor[stay ][B1]: 1.0 - 0.0156 = 0.9844
actor[left ][A0]:-1.0 - 0.0021 = -1.0021 actor[left ][B1]: 0.0 - 0.0021 = -0.0021
Re-read the preferences at 0.3 now and watch the policy lean toward right:
h(right) = 1.0177 + 1.0177 = 2.035 (was 2.0 -> up)
h(stay ) = -0.0156 + 0.9844 = 0.969 (was 1.0 -> down)
h(left ) = -1.0021 + -0.0021 = -1.004 (was -1.0 -> barely moved)
Softmax those and "right" now owns a little more of the 0-to-1 line than its old
0.7054. One good surprise made the move that caused it more likely -- and because
the shove is sized by (1 - pi), a move that was already near-certain barely moves,
while an unlikely move that pays off gets a big promotion. That is the actor
learning a policy directly.
The same spot, but a BAD step: how-wrong = -0.5 (the move came in
below the running average). Chances still [0.0351, 0.2595, 0.7054], right taken,
size 0.1. Compute the three shoves.
CHECK: right (taken): 0.1 x (-0.5) x (1 - 0.7054) = -0.05 x 0.2946 = -0.0147 -> DOWN
stay : 0.1 x (-0.5) x (0 - 0.2595) = +0.0130 -> up
left : 0.1 x (-0.5) x (0 - 0.0351) = +0.0018 -> up a hair
Every sign flipped: a below-average step demotes its cause and hands
the freed odds to the untried moves. (And the three still sum to 0.)
WHERE DID DILUTE GO? -- FOUR HABITS THE ENDLESS PENDULUM BROKE
"Where did dilute go? I kept trying to discount." The pendulum never ends, and a
discounted pile on an endless run blows up as the discount nears 1 -- a steady
reward of 1 per step is worth 1/(1-0.9) = 10, then 1/(1-0.99) = 100, then
unbounded. The differential error stays small forever: 1 - 0.5 + 0.2 - 0.1 = 0.6.
When the game never ends, grade each step against the AVERAGE step (subtract
R-bar) instead of fading a future that never arrives.
"The untaken moves did nothing -- why do their preferences move at all?" Add up
what actually moved: the three shoves were +0.0177, -0.0156, -0.0021, and they
sum to exactly 0, because (took-it? - pi) always does. Chances must keep summing
to 1, so pushing one move up IS pulling the others down; the formula just does it
in proportion to their odds. A policy is one pie. Nobody gets a bigger slice
unless someone gives some up.
"My winner was already at 0.7054 -- shouldn't winning make it grow just as fast
as ever?" The taken move's shove carries (1 - its chance): at chance 0.7054 the
factor is 0.2946; at chance 0.99 it would be 0.01 -- thirty times smaller for the
same good news. The promotion is sized by how SURPRISED the policy was to be
right. Near-certain moves have almost nothing left to learn from their own
success -- which is also what stops the policy slamming into all-or-nothing.
"R-bar is a third learner?! I set it once and left it." Suppose the true average
climbs to 1 while R-bar sits frozen at 0.5. Every step now reads
1 - 0.5 + (about 0) = +0.5 "better than expected" -- forever -- and every taken
move keeps getting promoted, good or not; the yardstick itself is lying by 0.5.
R-bar crawls too (R-bar += size x how-wrong), so "better than expected" keeps
meaning something as expectations rise.
SEAM. Pencil ends here; below, the same numbers in Python.
import math
size = 0.1
# preferences at 0.3 (lit tiles A0, B1)
wL_A0, wL_B1 = -1.0, 0.0
wS_A0, wS_B1 = 0.0, 1.0
wR_A0, wR_B1 = 1.0, 1.0
h_left = wL_A0 + wL_B1 # -1.0+0.0 = -1.0
h_stay = wS_A0 + wS_B1 # 0.0+1.0 = 1.0
h_right = wR_A0 + wR_B1 # 1.0+1.0 = 2.0
print(h_left, h_stay, h_right) # -1.0 1.0 2.0
# softmax: shift by max h=2.0
eL = math.exp(h_left - 2.0) # e^-3 = 0.0498
eS = math.exp(h_stay - 2.0) # e^-1 = 0.3679
eR = math.exp(h_right - 2.0) # e^0 = 1.0
tot = eL + eS + eR # 1.4177
pi_left = eL / tot # 0.0351
pi_stay = eS / tot # 0.2595
pi_right = eR / tot # 0.7054
print(round(eL,4), round(eS,4), round(tot,4)) # 0.0498 0.3679 1.4177
print(round(pi_left,4), round(pi_stay,4), round(pi_right,4)) # 0.0351 0.2595 0.7054
# YOUR TURN CHECK: h=[2,0,1] -> same gaps as [-3,-1,0] minus 2 everywhere
e0t = math.exp(2-2); e1t = math.exp(0-2); e2t = math.exp(1-2) # 1 0.1353 0.3679
tot2 = e0t+e1t+e2t # 1.5032
print(round(e0t/tot2,3), round(e1t/tot2,3), round(e2t/tot2,3)) # 0.665 0.090 0.245
# critic worths; differential TD error
V_03 = 0.2 + (-0.1) # 0.1
V_06 = 0.3 + (-0.1) # 0.2
how_wrong = 1 - 0.5 + V_06 - V_03 # 0.6
print(round(V_03,4), round(V_06,4), round(how_wrong,4)) # 0.1 0.2 0.6
# nudge critic and R-bar
R_bar_new = 0.5 + size*how_wrong # 0.56
critic_A0 = 0.2 + size*how_wrong # 0.26
critic_B1 = -0.1 + size*how_wrong # -0.04
print(R_bar_new, critic_A0, round(critic_B1,4)) # 0.56 0.26 -0.04
# actor shoves (took RIGHT, how_wrong=0.6)
shove_right = size*how_wrong*(1 - pi_right) # 0.06*0.2946 = 0.0177
shove_stay = size*how_wrong*(0 - pi_stay) # 0.06*(-0.2595) = -0.0156
shove_left = size*how_wrong*(0 - pi_left) # 0.06*(-0.0351) = -0.0021
print(round(shove_right,4), round(shove_stay,4), round(shove_left,4)) # 0.0177 -0.0156 -0.0021
print(round(shove_right+shove_stay+shove_left,8)) # 0.0 (always)
# new weights and preferences
wR_A0 += shove_right; wR_B1 += shove_right # 1.0177
wS_A0 += shove_stay; wS_B1 += shove_stay # -0.0156 0.9844
wL_A0 += shove_left; wL_B1 += shove_left # -1.0021 -0.0021
h_right_new = round(wR_A0 + wR_B1, 4) # 2.0354 ~ 2.035
h_stay_new = round(wS_A0 + wS_B1, 4) # 0.9688 ~ 0.969
h_left_new = round(wL_A0 + wL_B1, 4) # -1.0042 ~ -1.004
print(h_right_new, h_stay_new, h_left_new) # 2.0354 0.9688 -1.0042
# YOUR TURN: bad step how_wrong=-0.5, same chances
sb_right = size*(-0.5)*(1-pi_right) # -0.0147
sb_stay = size*(-0.5)*(0-pi_stay) # +0.0130
sb_left = size*(-0.5)*(0-pi_left) # +0.0018
print(round(sb_right,4), round(sb_stay,4), round(sb_left,4)) # -0.0147 0.013 0.0018
----------------------------------------------------------------------------------------------
CHAPTER 16 -- Policy Gradient:
[Propose and Grade: Actor-Critic by Pencil] (this post) -- the chapter closes here .
Next: Chapter 17 -- Wait for the Whole Trip: Monte Carlo by Pencil
<- Back to all posts
----------------------------------------------------------------------------------------------
home . source on GitHub
==============================================================================================