REINFORCE

REINFORCE is the simplest thing you can do with the policy gradient theorem, and a great first algorithm to internalise. Run a whole episode under your current policy, watch the total return it earned, then for every action you took, nudge its log-probability up or down in proportion to that return. Good episodes make all their actions a little more likely; bad episodes make all theirs a little less likely.

Concretely, after sampling a trajectory you update θ by adding α times the return G_t times ∇_θ log π_θ(a_t|s_t), summed over time steps. Because G_t is a full Monte Carlo return — the actual rewards seen, not an estimate — REINFORCE is unbiased and needs no value model. The price is that it can only learn after an episode ends, and the return is a single very noisy number.

In its plain form REINFORCE is famously high-variance and slow, often needing many episodes to make steady progress. The standard fixes are immediate: subtract a baseline, use reward-to-go instead of the whole return, and eventually replace the Monte Carlo return with a learned critic — which is how you arrive at actor-critic methods.