How does REINFORCE turn sampled episode returns into a gradient on the policy's parameters?

## The objective and why it resists direct differentiation The agent wants to maximise expected return: `J(theta) = E over trajectories tau drawn from pi_theta [ R(tau) ]` The awkwardness is that `theta` does not appear inside `R`. It appears in the *distribution you are averaging over*. Change the policy parameters and you do not change what any given trajectory pays; you change which trajectories you tend to see. Ordinary supervised learning never has this problem, because there the parameters sit inside the loss and the data distribution is fixed. ## The score-function (likelihood-ratio) trick Write the expectation as an integral and differentiate: `grad J = grad integral p_theta(tau) R(tau) dtau = integral grad p_theta(tau) * R(tau) dtau` Now use the identity `grad p = p * grad log p`, which is just the chain rule on the logarithm rearranged. Substituting turns the integral back into an expectation: `grad J = E over tau from pi_theta [ R(tau) * grad log p_theta(tau) ]` That quantity `grad log p_theta(tau)` is the **score function**. The whole method is named after it, and the estimator is also called the likelihood-ratio gradient estimator. Its value is that the right-hand side is an expectation you can estimate by sampling: roll out episodes, evaluate the bracket on each, average. ## Why the environment drops out The probability of a whole trajectory factorises: `p_theta(tau) = p(s_0) * product over t of [ P(s_{t+1} | s_t, a_t) * pi_theta(a_t | s_t) ]` Taking the log turns products into sums: `log p_theta(tau) = log p(s_0) + sum_t log P(s_{t+1} | s_t, a_t) + sum_t log pi_theta(a_t | s_t)` The initial-state distribution and the transition probabilities are properties of the environment; they do not contain `theta`, so they differentiate to zero. What survives is `grad log p_theta(tau) = sum over t of grad log pi_theta(a_t | s_t)` This is the reason REINFORCE is **model-free**: you never need to know, estimate or differentiate the environment's dynamics. You only need to be able to compute the gradient of your own policy's log-probability for the action you actually took. ## The reward is never differentiated Notice where `R(tau)` sits: outside the gradient, as a plain scalar weight. Nothing requires it to be differentiable, continuous, or even expressible in closed form. It can be the output of a discrete-event simulator. That is what makes the estimator usable on objectives that gradient-based optimisation normally cannot touch, for instance a nurse-shift scheduler scored by a simulator that adds up shift coverage and a staff-satisfaction penalty: the score is a step-shaped function of a combinatorial assignment with no derivative anywhere, but the *policy* that emits the assignment is a smooth parameterised distribution, and that is the only thing being differentiated. ## Credit assignment: from R(tau) to reward-to-go The raw derivation multiplies every step's score by the whole episode's return. You can do better without losing unbiasedness. An action at time t cannot influence rewards collected before t, and the expected contribution of those earlier rewards to the estimator is exactly zero. Dropping them gives the standard form: `grad J = E[ sum over t of G_t * grad log pi_theta(a_t | s_t) ]`, with `G_t = r_t + gamma*r_{t+1} + gamma^2*r_{t+2} + ...` Same expectation, less noise, because you have removed a term that was pure variance. This is called the **reward-to-go** form and it is what practical REINFORCE uses. ## The algorithm, end to end 1. Run one or more complete episodes with the current policy, recording states, actions and rewards. 2. For each timestep, compute the return from that step onward, `G_t`. 3. For each timestep, compute the score `grad log pi_theta(a_t | s_t)` for the action that was actually taken. 4. Accumulate `sum_t G_t * score_t` over the batch, average, and take an ascent step: `theta <- theta + lr * (that average)`. 5. Throw the batch away and go back to step 1. Step 1 requires *complete* episodes, because `G_t` is a Monte-Carlo return: nothing is bootstrapped, so nothing can be computed until the episode ends. That makes plain REINFORCE unsuitable for continuing tasks without truncation. ## The intuition to keep The update is credit assignment by association: whatever you did in an episode that turned out well, do more of it; the size of the nudge is proportional to how well it turned out. Nothing in the estimator knows *why* the return was high or which specific action deserved it. Averaged over enough episodes, actions that genuinely raise return appear more often in high-return trajectories, and the average points uphill. "Enough episodes" is doing heavy lifting in that sentence, which is why variance reduction is the next thing anyone learns about this estimator.