Exercises — REINFORCE algorithm

Answer: (b). Why (b): the log-derivative trick turns $\nabla p$ into $p\nabla \log p$, so the surviving factor is ${\nabla }_{\theta }\log {\pi }_{\theta }$ — the log, not the bare probability. That rules out (a). Why not (c): the weight is the return following $t$, $G_t$, not the single-step reward $r_t$. An action is credited with everything that comes after it, not just the immediate payoff.

Only ${\sum }_t{\nabla }_{\theta }\log {\pi }_{\theta }(a_t\mid s_t)$ survives. $\rho (s_0)$ (start-state distribution) and $P(s^{\prime }\mid s,a)$ (environment transitions) come from the world, not from $\theta$. Their gradient w.r.t. $\theta$ is exactly zero. This is precisely why REINFORCE is model-free.

Work backwards using $G_t=r_t+\gamma G_{t+1}$ (cheaper than re-summing each time).

• $G_3=r_3=4$.
• $G_2=r_2+0.5G_3=6+0.5(4)=8$.
• $G_1=r_1+0.5G_2=0+0.5(8)=4$.
• $G_0=r_0+0.5G_1=2+0.5(4)=4$.

Answers: $G_0=4,G_1=4,G_2=8,G_3=4$. Why backwards: each $G_t$ reuses the already-computed $G_{t+1}$, so the whole sweep is $O(T)$ instead of $O(T^2)$.

Write $\log {\pi }_{\theta }(R)={\theta }_R-\log (e^{{\theta }_L}+e^{{\theta }_R})$. Differentiate w.r.t. ${\theta }_R$: $\frac{\partial }{\partial {\theta }_R}[{\theta }_R-\log (e^{{\theta }_L}+e^{{\theta }_R})]=1-\frac{e^{{\theta }_R}}{e^{{\theta }_L}+e^{{\theta }_R}}=1-{\pi }_{\theta }(R).$ Why this shape is beautiful: if we sampled $R$ and got positive advantage, the update $\propto (1-\pi (R))$ pushes hardest when $\pi (R)$ is small (lots of room to grow) and gently when $\pi (R)$ is already near 1. Self-limiting, no manual clipping needed.

Update rule: ${\theta }_R\leftarrow {\theta }_R+\alpha {\nabla }_{{\theta }_R}\log {\pi }_{\theta }(R)\cdot G$. From L2.2, ${\nabla }_{{\theta }_R}\log \pi (R)=1-\pi (R)=1-0.5=0.5$. ${\theta }_R\leftarrow 0+0.1\times 0.5\times 1=\mathrm{0.05.}$ Answer: ${\theta }_R=0.05$ (and ${\theta }_L$ unchanged at $0$). New $\pi (R)=\frac{e^{0.05}}{e^0+e^{0.05}}\approx 0.5125$ — nudged up, exactly as the positive return demands.

Pull $b(s)$ out (it doesn't depend on $a$) and convert the expectation to a sum, then run the log-derivative trick backwards: $b(s){\sum }_a{\pi }_{\theta }(a\mid s){\nabla }_{\theta }\log {\pi }_{\theta }(a\mid s)=b(s){\sum }_a{\nabla }_{\theta }{\pi }_{\theta }(a\mid s).$ Swap sum and gradient (finite sum, linear): $=b(s){\nabla }_{\theta }{\sum }_a{\pi }_{\theta }(a\mid s)=b(s){\nabla }_{\theta }(1)=b(s)\cdot 0=0.■$ The key fact: probabilities sum to $1$, a constant, whose gradient is $0$. This is the whole reason baselines are "free" — variance drops, bias stays zero. See figure.

• No baseline: weights are $+105$ and $+95$. Both positive — both log-probs pushed up. The learner must resolve which is better from a tiny $105$ vs $95$ difference riding on huge magnitudes → high variance, slow.
• With $b=100$: advantages are $A_A=+5$, $A_B=-5$. Now $A$ is pushed up, $B$ pushed down explicitly. The contrast is exposed; magnitudes are small and centered.

Why it works: the baseline removes the common-mode offset ($\approx 100$) that carried no information about which action was better. See figure.

Full return is $R(\tau )=15$. The naive estimator would multiply $\nabla \log \pi (a_1)$ by $15$; reward-to-go multiplies by $G_1=r_1+r_2=10$, dropping the $r_0=5$ earned before $a_1$. The past reward $r_0$ is a constant with respect to $a_1$'s distribution, so — by exactly the L3.1 argument with $b=r_0$ — its expected contribution to $\nabla \log \pi (a_1)$ is zero. Removing it changes nothing in expectation but shrinks the weight's variance. Answer: $G_1=10$; unbiased, lower variance. ✅

The second term has no $\mu$, so it drops. Differentiate the first w.r.t. $\mu$: ${\nabla }_{\mu }\log {\pi }_{\theta }(a\mid s)=\frac{a-\mu }{{\sigma }^2}.$ Interpretation of sign: if the sampled action $a$ was above the mean ($a>\mu$) and the advantage was positive, the update moves $\mu$ toward $a$ (upward) — "we liked doing more than average, so aim higher." If $a<\mu$, it pulls $\mu$ down. The magnitude $\propto (a-\mu )/{\sigma }^2$ scales the surprise by how tight the policy is.

$\mathcal{L}(\theta )=-{\sum }_{t=0}^T\log {\pi }_{\theta }(a_t\mid s_t)A_t.$ Why the sum: the gradient is a sum over timesteps, and $\nabla$ is linear, so summing the terms before differentiating gives the right total. Why $A_t$ is treated as a constant: in REINFORCE the advantage weight is a number computed from the rollout, not differentiated through — autograd sees it as a coefficient. Why the leading minus: optimizers minimize. We want to maximize $J$, i.e. ascend. Minimizing $-\sum \log \pi \cdot A$ = ascending $+\sum \log \pi \cdot A$. Drop the minus and you'd descend, making good actions less likely.

• Advantage of bootstrapping: using $r_t+\gamma \hat{V}(s_{t+1})$ instead of the full sampled $G_t$ dramatically lowers variance (one random reward + a learned estimate, versus a long noisy sum). It also allows online, per-step updates instead of waiting for the episode to end.
• Disadvantage: it introduces bias, because $\hat{V}$ is an imperfect estimate; the update is only as correct as the critic. REINFORCE's Monte-Carlo $G_t$ is unbiased but high-variance. This is the classic bias–variance trade-off of policy gradient methods.

1. Write expectation as an integral: $J=\int p_{\theta }(\tau )R(\tau )d\tau$. Tool: definition of expectation — a probability-weighted integral.
2. Push gradient inside: ${\nabla }_{\theta }J=\int {\nabla }_{\theta }{p}_{\theta }(\tau )R(\tau )d\tau$. Tool: linearity of the gradient; $R(\tau )$ is $\theta$-free (rewards come from the environment).
3. Log-derivative trick: ${\nabla }_{\theta }p=p{\nabla }_{\theta }\log p$. Why: converts $\nabla p$ into something that keeps the factor $p$, so the integral becomes an expectation again → samplable. Gives ${\nabla }_{\theta }J={\mathbb{E}}_{\tau }[{\nabla }_{\theta }\log p_{\theta }(\tau )R(\tau )]$.
4. Factor the trajectory probability: $p_{\theta }(\tau )=\rho (s_0){\prod }_t{\pi }_{\theta }(a_t\mid s_t)P(s_{t+1}\mid s_t,a_t)$; take log (product→sum), differentiate. Tool: $\log$ turns products into sums; environment terms $\rho ,P$ are $\theta$-free so vanish → ${\nabla }_{\theta }\log p_{\theta }(\tau )={\sum }_t{\nabla }_{\theta }\log {\pi }_{\theta }(a_t\mid s_t)$. This is where model-freeness appears.
5. Apply causality: an action at $t$ cannot influence rewards before $t$; those contribute zero in expectation (L3.1 argument), so replace $R(\tau )$ by the reward-to-go $G_t$ for each term. Result: ${\nabla }_{\theta }J={\mathbb{E}}_{\tau }[{\sum }_t{\nabla }_{\theta }\log {\pi }_{\theta }(a_t\mid s_t)G_t].■$

Baseline $b=\text{mean}(1,0)=0.5$. Advantages: $A_R=1-0.5=+0.5$, $A_L=0-0.5=-0.5$. Start $\pi (R)=\pi (L)=0.5$. Gradients (from L2.2 shapes):

• Sampled $R$: ${\nabla }_{{\theta }_R}\log \pi (R)=1-\pi (R)=0.5$; ${\nabla }_{{\theta }_L}\log \pi (R)=-\pi (L)=-0.5$.
• Sampled $L$: ${\nabla }_{{\theta }_L}\log \pi (L)=1-\pi (L)=0.5$; ${\nabla }_{{\theta }_R}\log \pi (L)=-\pi (R)=-0.5$.

Averaged gradient (weight each by its advantage, divide by $N=2$):

• $g_{{\theta }_R}=\frac{1}{2}[(0.5)(A_R)+(-0.5)(A_L)]=\frac{1}{2}[0.5(0.5)+(-0.5)(-0.5)]=\frac{1}{2}[0.25+0.25]=\mathrm{0.25.}$
• $g_{{\theta }_L}=\frac{1}{2}[(-0.5)(A_R)+(0.5)(A_L)]=\frac{1}{2}[(-0.5)(0.5)+(0.5)(-0.5)]=\frac{1}{2}[-0.25-0.25]=-\mathrm{0.25.}$

Update $\theta \leftarrow \theta +\alpha g$: ${\theta }_R=0+0.1(0.25)=0.025,{\theta }_L=0+0.1(-0.25)=-\mathrm{0.025.}$ Answer: ${\theta }_R=0.025$, ${\theta }_L=-0.025$. The rewarding action $R$ climbed, $L$ fell — and thanks to the baseline the two moved by equal and opposite amounts, cleanly separating the winner.

Which fact justifies dropping $P(s^{\prime }\mid s,a)$ from the gradient? ::: $P$ does not depend on $\theta$, so ${\nabla }_{\theta }\log P=0$ → model-free. What is the exponent inside the reward-to-go $G_t$? ::: ${\gamma }^{k-t}$ (relative to the current step, not absolute). What single property makes a baseline unbiased? ::: it must not depend on the action $a$. Why the leading minus sign in the loss? ::: optimizers minimize; minimizing $-J$ performs gradient ascent on $J$.