REINFORCE

REINFORCE is the simplest policy gradient algorithm. It uses complete episode returns to estimate the gradient.

Algorithm:

1. Run a full episode under $\pi_\theta$, collecting $(s_t, a_t, R_t)$
2. Compute returns: $G_t = \sum_{k=0}^{T-t} \gamma^k R_{t+k+1}$
3. Update: $\theta \leftarrow \theta + \alpha \sum_t \nabla_\theta \log\pi_\theta(a_t|s_t) \cdot G_t$

Intuition: actions followed by high returns get their probability increased; actions followed by low returns get decreased.

Problem: high variance. $G_t$ includes all future rewards, many of which are due to subsequent actions, not $a_t$. This noise makes learning slow.

Variance reduction with baseline:

• Subtracting baseline $b(s_t)$ doesn't change the expected gradient (provably)
• Best baseline ≈ $V(s_t)$ → the update becomes proportional to advantage $A(s,a) = G_t - V(s_t)$
• Learn $V$ with a separate network → this is Actor-Critic Methods

Limitations:

• Requires complete episodes (Monte Carlo)
• Even with a baseline, variance is still high compared to actor-critic
• On-policy: samples can't be reused (sample inefficient)

See also: Policy Gradient Theorem, Advantage Function, Actor-Critic Methods