Policy gradient methods (REINFORCE)

Back to the three-armed bandit — but instead of a Q-table, there's a preference number for each arm, run through a softmax to get a probability of picking it. Step through five pulls and watch the bars themselves shift: an arm that pays off gets more likely to be picked next time, one that doesn't gets less so.

With preferences $\theta$ and policy $\pi_\theta(a) = \text{softmax}(\theta)_a$, the REINFORCE update after taking action $a$ and observing return $G$ is:

• $\theta_i$ — the preference parameter for action $i$, before being run through softmax.
• $\pi_\theta(i)$ — the current policy's probability of picking action $i$: softmax of the preferences.
• $a$ — the action that was actually taken.
• $\mathbb{1}[i{=}a]$ — equals $1$ if $i$ is the action actually taken, $0$ otherwise.
• $G$ — the return observed for that action.
• $\alpha$ — the learning rate controlling the update size.

1. Same shape as the softmax cross-entropy gradient

   $\big(\mathbb{1}[i{=}a] - \pi_\theta(i)\big)$ is exactly the softmax cross-entropy gradient from Part II, indicator minus predicted probability.

2. But scaled by the return, not by 1

   Cross-entropy always scales by $1$ (the true label is certain), while REINFORCE scales by $G$, whatever return that action happened to earn.

3. What that scaling does

   A big positive return pushes hard toward that action; a return of exactly zero pushes not at all.

Compare the very first policy to the one after five pulls. Nothing here ever built or consulted a value table — the probabilities shifted directly, one gradient step at a time, purely from the returns each pull happened to produce.

Starting from $\theta=(0,0,0)$ — a uniform policy — with $\alpha=0.5$:

1. First pull: arm A, reward 1

   $\pi = (\frac13,\frac13,\frac13)$ before the update. Each preference updates by $\alpha(\mathbb{1}[i{=}A]-\pi_i)(1)$:

   • $\theta_A \leftarrow 0 + 0.5(1-\frac13)(1) = \frac13$
   • $\theta_B \leftarrow 0 + 0.5(0-\frac13)(1) = -\frac16$
   • $\theta_C \leftarrow 0 + 0.5(0-\frac13)(1) = -\frac16$

   B and C both drop, pushed down even though they weren't pulled, simply for not being the chosen action.

2. A reward of exactly zero changes nothing

   Pulling arm C next happens to pay $0$. Since the update scales by the return, multiplying by $0$ zeroes out every single term — $\theta$ comes out of that step completely unchanged, regardless of which arm was pulled.

3. After all five pulls

   Pulls 3 and 5 both pay $0$, so (per the previous step) they leave $\theta$ unchanged. Only pulls 2 and 4 (both pulling B, both paying $1$) move the parameters:

   • After pull 2: $\pi\approx(0.452,0.274,0.274)$ from $\theta=(\frac13,-\frac16,-\frac16)$, giving $\theta \approx (0.107, 0.196, -0.304)$
   • After pull 4: $\pi\approx(0.363,0.397,0.240)$ from that $\theta$, giving $\theta \approx (-0.074, 0.498, -0.424)$

   $\theta_B \approx 0.498$, clearly ahead of $\theta_A \approx -0.074$ and $\theta_C \approx -0.424$ — the policy now assigns arm B more than half its probability mass, without ever computing a single $Q(s,a)$.