Q-learning and TD learning optimize value functions — estimates of how good states or actions are. Williams’ REINFORCE took a different path: optimize the policy directly. This distinction still structures the field today.
The fundamental question
Can you compute the gradient of expected reward with respect to the policy parameters? The reward function is non-differentiable (you either win or lose, score or don’t), and it depends on the environment’s dynamics which you don’t model. It seems like you’d need the derivative of something you can’t differentiate.
The score function estimator (log-derivative trick) resolves this:
∇J(θ) = E_{τ~π_θ}[∇log π(a_t|s_t;θ) · R(τ)]
You don’t need to differentiate the reward. You only need to differentiate the log probability of taking each action under your policy — which you can compute exactly. The return R scales the gradient: actions that led to high return get their probability increased; actions that led to low return get their probability decreased.
Why this matters for connectionist systems
Q-learning required a discrete action space (the max operation). Policy gradient works for continuous actions — directly parameterizing a Gaussian over action space, for example. This made REINFORCE the foundation for:
- Continuous control (robotics, locomotion)
- Recurrent networks (policy over sequences)
- Stochastic policies that inherently require sampling
Modern algorithms like PPO (Proximal Policy Optimization) and SAC (Soft Actor-Critic) are direct descendants — they are policy gradient methods with variance reduction and constraint mechanisms.
The variance problem
REINFORCE is unbiased but has high variance. The return R for an entire episode fluctuates enormously. Practical fix: subtract a baseline b(s) from the return. Since E[∇log π · b] = 0, this doesn’t bias the gradient but dramatically reduces variance. The optimal baseline is the value function V(s) — and when you learn V(s) alongside the policy, you get Actor-Critic methods. The actor (policy) and critic (value function) co-train, the critic providing low-variance gradient estimates to the actor.
Relationship to Q-learning
| Value-based (Q-learning) | Policy gradient (REINFORCE) | |
|---|---|---|
| What’s learned | Q(s,a) function | π(a|s;θ) directly |
| Action space | Discrete (max operator) | Any (sample from π) |
| Policy | Implicit (greedy over Q) | Explicit parameterization |
| Variance | Low (bootstrapped) | High (Monte Carlo returns) |
| Bias | High (deadly triad) | Low (unbiased estimator) |
The synthesis — Actor-Critic — takes the policy gradient structure but uses Q-learning’s value function as the critic, getting lower variance without the deadly triad’s instability.