The Captain's Bowling Change
An IPL captain walks out for the toss holding a policy, not a plan. She does not know in advance that she will bring on the pacer in the 4th over and the mystery spinner in the 11th — she carries a set of tendencies, shaped by experience, that assign a probability to each bowling choice given the match situation: powerplay or middle overs, required run rate, which batter is on strike. Formally, she is running a stochastic policy π(a|s) — a probability distribution over actions a (which bowler, which field), conditioned on the state s (overs bowled, score, wickets, batter matchup).
The reward for any single bowling change is almost impossible to isolate. A wicket in over 7 might result from three overs of pressure built earlier, or from pure variance. The only reward signal she can trust without ambiguity arrives at the very end: win or loss. This is the reinforcement learning setting that policy gradient methods were built for — an agent acting under a parameterized stochastic policy, receiving a delayed, aggregate reward at the end of an episode, with no reliable per-action label to imitate. There is no dataset of "correct" bowling changes to run supervised learning against. The only teacher is the final scoreline, replayed across many matches (episodes) until the policy shifts toward the choices that, on average, preceded wins.
This is exactly the problem REINFORCE — the first practical policy gradient algorithm, published by Ronald Williams in 1992 — was designed to solve: how do you adjust the parameters of a stochastic policy using only the total return of complete episodes, with no value function, no model of the environment, and no per-step ground truth?
Why Not Just Learn a Value Function?
Value-based methods like Q-learning learn Q(s,a), the expected return of each action, and act by taking argmax over actions. That works cleanly when the action set is small and discrete and when a deterministic policy is actually optimal. But the captain's problem resists this on two fronts. First, a deterministic "always bowl the death-overs specialist at over 17" policy is exploitable — a good opposition batting lineup adapts once the pattern is read, so the game-theoretically optimal policy is often genuinely stochastic (mix your bowling changes so batters cannot pre-plan against a predictable pattern). Value-based methods with argmax action selection cannot represent a policy that assigns 60% probability to bowler X and 40% to bowler Y at the optimum — they collapse to a single best action. Second, policy gradient methods parameterize and optimize the policy directly: π_θ(a|s), with θ a vector of learnable weights. There is no intermediate value table to maintain and no argmax to compute at decision time — you sample directly from π_θ. This is the defining shift: instead of learning "how good is this action" and deriving a policy from it, you climb the gradient of expected return with respect to the policy's own parameters.
Setting Up the Objective
Consider an episodic MDP. A trajectory τ = (s₀, a₀, r₁, s₁, a₁, r₂, …, s_{T−1}, a_{T−1}, r_T) is generated by repeatedly sampling an action from π_θ(a|s) and letting the environment respond. Define the trajectory return G(τ) = Σ_{t=1}^{T} γ^{t−1} r_t (discount γ ∈ (0,1], set to 1 for a short episodic task like a single match). The objective we want to maximize is the expected return under the current policy:
J(θ) = E_{τ ~ π_θ} [ G(τ) ]
Policy gradient methods perform gradient ascent directly on this objective: θ ← θ + α ∇_θ J(θ). Everything about REINFORCE follows from finding a way to estimate ∇_θ J(θ) using only samples — trajectories the agent actually experiences — since J(θ) itself is an expectation over an unknown environment and cannot be differentiated in closed form.
Deriving the Policy Gradient: the Log-Derivative Trick
Write J(θ) as a sum over all possible trajectories, weighted by their probability under the policy: J(θ) = Σ_τ P(τ;θ) G(τ). Differentiating with respect to θ:
∇_θ J(θ) = Σ_τ ∇_θ P(τ;θ) · G(τ)
The gradient of a probability is awkward to sample from directly, but a standard identity fixes this. Since ∇_θ P(τ;θ) = P(τ;θ) · [∇_θ P(τ;θ) / P(τ;θ)] = P(τ;θ) · ∇_θ log P(τ;θ), substituting gives:
∇_θ J(θ) = Σ_τ P(τ;θ) · ∇_θ log P(τ;θ) · G(τ) = E_{τ~π_θ}[ ∇_θ log P(τ;θ) · G(τ) ]
This is now an expectation, which can be estimated by sampling trajectories and averaging — exactly what an RL agent can do by just playing episodes. The remaining question is what ∇_θ log P(τ;θ) actually equals. The trajectory probability factors into environment dynamics and policy choices:
P(τ;θ) = P(s₀) · Π_{t=0}^{T−1} P(s_{t+1}|s_t,a_t) · π_θ(a_t|s_t)
Taking the log turns this product into a sum, and the environment's transition probabilities P(s_{t+1}|s_t,a_t) do not depend on θ at all — the captain's policy has no influence on how a bowler's delivery actually plays out physically. So when we differentiate log P(τ;θ) with respect to θ, every transition term vanishes and only the policy terms survive:
∇_θ log P(τ;θ) = Σ_{t=0}^{T−1} ∇_θ log π_θ(a_t|s_t)
This is the crucial simplification: the gradient of a trajectory's log-probability depends only on the agent's own policy, never on the environment's dynamics, which is precisely why REINFORCE is model-free — it needs no knowledge of P(s'|s,a) to compute an unbiased gradient estimate. Substituting back gives the policy gradient theorem in its basic form:
∇_θ J(θ) = E_τ [ ( Σ_{t=0}^{T−1} ∇_θ log π_θ(a_t|s_t) ) · G(τ) ]
From Whole-Episode Return to Return-to-Go: the Causality Trick
The formula above multiplies every timestep's score-function gradient by the entire episode's return G(τ), including rewards earned before that timestep even happened. Intuitively this is wasteful: the reward the captain's team scored in over 3 cannot possibly have been caused by the bowling change she makes in over 11, so it shouldn't influence the gradient signal for that later decision. This intuition can be made exact. Expand G(τ) = Σ_{k=1}^{T} r_k and distribute it across the sum over t. For any reward r_k occurring strictly before action a_t was chosen (k ≤ t), the term E[∇_θ log π_θ(a_t|s_t) · r_k] evaluates to zero in expectation, because r_k is fixed by the time a_t is sampled and E_{a_t~π_θ}[∇_θ log π_θ(a_t|s_t)] = 0 for any fixed s_t (a standard property of the score function of any normalized probability distribution — it always integrates to zero). Only rewards from timestep t onward carry a genuine causal dependency on a_t. Discarding the zero-expectation past-reward terms — which also strictly reduces variance, since they added noise without adding signal — leaves the return-to-go G_t = Σ_{k=t+1}^{T} γ^{k−t−1} r_k in place of the full-episode G(τ):
∇_θ J(θ) = E_τ [ Σ_{t=0}^{T−1} ∇_θ log π_θ(a_t|s_t) · G_t ]
This is the working form of the REINFORCE gradient: at every timestep, credit that action's log-probability gradient using only the reward that followed it, never the reward that preceded it.
The REINFORCE Algorithm
Williams named it as a backronym: REward Increment = Nonnegative Factor × Offset Reinforcement × Characteristic Eligibility. The "characteristic eligibility" is exactly ∇_θ log π_θ(a_t|s_t) — how much nudging θ in a given direction would have made the action actually taken more or less likely. The algorithm loops over full episodes:
Initialize policy parameters θ (e.g. random small weights)
repeat forever:
Generate one episode s0, a0, r1, s1, a1, r2, ..., sT
following the current policy at ~ π_θ(·|st)
for t = 0, 1, ..., T-1:
Gt = sum of rk for k = t+1 to T (discounted by γ^(k-t-1))
θ ← θ + α · Gt · ∇θ log π_θ(at|st)
Three properties fall directly out of the derivation. First, it is on-policy — the trajectory must be sampled from the current π_θ, because the derivation's expectation is taken over π_θ; an old episode from a stale policy would bias the estimate. Second, it is a Monte Carlo method — G_t is the actual observed sum of future rewards, not a bootstrapped estimate, so the agent must wait for the episode to terminate before it can compute a single update. This is why REINFORCE only applies cleanly to episodic tasks (a match has a final score; a continuously running system without natural episode boundaries needs bootstrapped methods instead). Third, because G_t is a sample of a random variable that itself depends on every action taken for the rest of the episode, the gradient estimate carries high variance — one lucky wicket late in the innings inflates the credit assigned to an early, unrelated bowling change that happened to precede it in that one trajectory.
Worked Example: Two Overs, One Update
Take a deliberately small slice of the captain's problem — two decision points, two bowler choices each — so every number can be traced by hand. State s₀ is the powerplay; the captain chooses between bowler A (pace) and bowler B (spin) using a tabular softmax policy with parameters θ(s₀) = [θ_A0, θ_B0]. State s₁ is the middle overs, reached regardless of the first choice, with its own independent parameters θ(s₁) = [θ_A1, θ_B1]. For a two-action softmax, π(A|s) = e^{θ_A} / (e^{θ_A} + e^{θ_B}).
Initialize all four parameters to 0, so both states start at 50/50: π(A|s₀) = π(B|s₀) = π(A|s₁) = π(B|s₁) = 0.5 — the captain has no prior lean either way. One episode is sampled: at s₀ the policy happens to sample a₀ = A (pacer), which yields r₁ = 0 (no wicket, no boundary — a quiet over). At s₁ the policy samples a₁ = B (spinner), which yields r₂ = +1 (the wicket that ultimately secures the win). With γ = 1, the returns-to-go are G₀ = r₁ + r₂ = 0 + 1 = 1 and G₁ = r₂ = 1.
The softmax score function has a clean closed form worth deriving once: log π(a|s) = θ_a − log Σ_b e^{θ_b}, so ∂/∂θ_c log π(a|s) = 1{c=a} − π(c|s). For the taken action, the gradient with respect to its own logit is (1 − π(a|s)); for every other action it is (−π(other|s)). At t=0, action A was taken with π(A|s₀)=0.5, so ∇_{θ_A0} log π(A|s₀) = 1 − 0.5 = 0.5 and ∇_{θ_B0} log π(A|s₀) = −0.5. At t=1, action B was taken with π(B|s₁)=0.5, so ∇_{θ_B1} log π(B|s₁) = 0.5 and ∇_{θ_A1} log π(B|s₁) = −0.5.
With learning rate α = 0.1, the REINFORCE update θ ← θ + α · G_t · ∇θ log π(a_t|s_t) gives:
θ_A0 = 0 + 0.1 · 1 · ( 0.5) = 0.05
θ_B0 = 0 + 0.1 · 1 · (-0.5) = -0.05
θ_A1 = 0 + 0.1 · 1 · (-0.5) = -0.05
θ_B1 = 0 + 0.1 · 1 · ( 0.5) = 0.05
Recomputing the softmax with these updated logits (verified numerically): π(A|s₀) = e^0.05/(e^0.05+e^{-0.05}) = 0.52498, π(B|s₀) = 0.47502; and π(A|s₁) = 0.47502, π(B|s₁) = 0.52498. Both shifts make sense and both are informative. The probability of choosing the pacer in the powerplay rose slightly, even though the pacer's own over produced zero reward — because it was part of a trajectory that ultimately won, and REINFORCE has no way (yet) to separate "genuinely useful" from "merely present when something good happened." The probability of choosing the spinner in the middle overs also rose, and here the credit is directly earned — that action was immediately followed by the reward. This is the core credit-assignment behavior of REINFORCE: every action along a winning trajectory gets reinforced by the return that follows it, in proportion to how much that action's own probability could be nudged.
The REINFORCE Update Loop
The Variance Problem and the Baseline Trick
The worked example used a single episode to keep the arithmetic traceable, but a single episode is a noisy witness. If, in a different match, the same pace-then-spin sequence had been followed by a loss, G₀ and G₁ would both have been negative, and the exact same actions would have been punished instead of rewarded — even though nothing about how the actions were chosen changed. Because G_t is a Monte Carlo sample of a return that depends on every random event for the rest of the episode (fielding luck, a dropped catch, a random umpiring decision), the gradient estimate has high variance, and REINFORCE typically needs many episodes averaged together (or a very small α) before the noise cancels out and a genuine signal emerges.
A standard fix subtracts a baseline b(s_t) from the return before scaling the gradient: θ ← θ + α · (G_t − b(s_t)) · ∇_θ log π(a_t|s_t). Because E_{a_t~π_θ}[∇_θ log π(a_t|s_t)] = 0 for any fixed s_t, subtracting anything that does not depend on the action taken changes the variance of the estimator but does not change its expectation — the update stays unbiased as long as b depends only on the state, never on the action. A common choice is an estimate of the state's average return, V(s_t), often learned by a separate small network; the term (G_t − V(s_t)) is exactly the advantage — how much better this particular action's outcome was than what was typically expected from this state — which is the seed idea behind actor-critic methods that extend REINFORCE.
Common Misconception
The mistake nearly every student makes on first contact with this formula is reading θ ← θ + α · G_t · ∇log π(a_t|s_t) as if G_t were the immediate reward r_t, the way a supervised loss uses a single immediate label. It is not. G_t is the return-to-go — the sum of all rewards from timestep t through the end of the episode. In the worked example, θ_A0 was updated using G₀ = 1, the total of both r₁ = 0 and r₂ = 1, even though bowler A's own over produced zero reward on its own. If REINFORCE used only r_t, the pace bowler's action at t=0 would never be reinforced at all (its immediate reward was 0), and the algorithm would be blind to any action whose payoff arrives later in the episode — which describes nearly every meaningful decision in an MDP with delayed reward. The whole reason REINFORCE works as a credit-assignment mechanism is precisely that it looks forward from each action to everything that followed it, not sideways at what that single step alone produced.
Active Recall
Attempt each question before reading its answer.
- In the REINFORCE update, why is the return-to-go G_t used instead of the immediate reward r_t?
- A softmax policy has two actions with logits θ_A = 1, θ_B = 3. Compute π(A|s), and compute ∇_{θ_A} log π(A|s) and ∇_{θ_B} log π(A|s) for the case where action A is the one taken.
- Why is REINFORCE classified as a Monte Carlo method, and what constraint does this place on the kind of tasks it can be applied to?
- If a state-dependent baseline b(s) is subtracted from G_t in the update rule, why does the gradient estimator remain unbiased, and what property must b(s) satisfy for this to hold?
- Why does REINFORCE typically require many more episodes to converge than a comparable supervised-learning gradient step requires labeled examples?
- Redo the worked example with one change: at s₁ the policy samples a₁ = A instead of B (both starting from θ_A1 = θ_B1 = 0), with r₂ = +1 still. Using α = 0.1, compute the new θ_A1, θ_B1 and the resulting π(A|s₁), π(B|s₁).
Answers
1. Rewards earned before timestep t are already fixed by the time a_t is sampled — they cannot causally depend on a_t — so their expected contribution to the gradient is zero and including them only adds variance without adding signal. Only rewards from t onward could plausibly have been influenced by a_t, so return-to-go is both the causally correct and lower-variance choice; discarding future information (using only r_t) would make the algorithm blind to any action whose payoff is delayed.
2. π(A|s) = e¹/(e¹+e³) = 2.71828/22.80338 ≈ 0.1192, so π(B|s) ≈ 0.8808. Since A is the action taken: ∇_{θ_A} log π(A|s) = 1 − π(A) = 1 − 0.1192 = 0.8808. ∇_{θ_B} log π(A|s) = −π(B) = −0.8808. (Note the low-probability action, once taken, produces a large gradient magnitude — a rare choice that still gets sampled pulls its own logit up sharply if it turns out to be followed by a positive return.)
3. It is Monte Carlo because G_t is computed from the actual, fully observed sequence of rewards for the rest of the episode rather than from a bootstrapped estimate (as TD methods use). This means an update cannot be computed until the episode has terminated — REINFORCE therefore requires episodic tasks with a well-defined end (a match, a game, a fixed-horizon task), and cannot directly update online during an episode or handle a continuing task with no terminal state.
4. The unbiasedness follows because E_{a_t~π_θ}[∇_θ log π(a_t|s_t)] = 0 for any distribution that is properly normalized (the score function of any probability distribution integrates to zero over its own sample space). Subtracting a term b(s_t) that does not depend on a_t therefore subtracts E[b(s_t)·∇_θ log π(a_t|s_t)] = b(s_t)·E[∇_θ log π(a_t|s_t)] = 0 from the expected gradient — it changes nothing in expectation. The required property is that b depends only on the state, never on the action taken; a baseline that used a_t (e.g., subtracting the reward of whichever action happened to be sampled) would introduce bias.
5. A supervised gradient step uses a label that is deterministic and directly tied to that one input. A REINFORCE gradient step uses G_t, a random variable whose value depends on every stochastic event for the rest of that one sampled episode — a different random seed on the same policy can produce a wildly different G_t for the identical action. Averaging over many episodes is what suppresses this episode-to-episode noise into a usable gradient direction, so more samples are needed to reach the same signal-to-noise ratio a fixed supervised label gives for free.
6. π(A|s₁) = π(B|s₁) = 0.5 initially. Action A is taken, so ∇_{θ_A1} log π(A|s₁) = 1 − 0.5 = 0.5 and ∇_{θ_B1} log π(A|s₁) = −0.5. With G₁ = 1 and α = 0.1: θ_A1 = 0 + 0.1(1)(0.5) = 0.05, θ_B1 = 0 + 0.1(1)(−0.5) = −0.05. Recomputing the softmax: π(A|s₁) = e^0.05/(e^0.05+e^{-0.05}) ≈ 0.52498, π(B|s₁) ≈ 0.47502. Because the same action (A) was rewarded twice as likely this time — first by the spin-bowler version of the episode, now by choosing A itself in the middle overs — the probability of A at s₁ rises in exactly the same way B's did in the original example: whichever action was actually sampled and followed by positive return gets its own probability increased, regardless of which specific action label it carries.
Think About It
Think about this: How would you explain policy gradient methods: reinforce algorithm to a friend who has never seen a computer? What real-world analogy would you use? Imagine you had to build a system using these concepts — what would be your first step? Try this: before moving on, write down three things you learned and one question you still have.
Practice Exercises
Now it is time to practice! Complete these challenges to solidify your understanding:
- Exercise 1: Write a short program that demonstrates the core concept from this chapter. Test it with at least 3 different inputs.
- Exercise 2: Find a real-world example where policy gradient methods: reinforce algorithm is used in an Indian company (like TCS, Infosys, Flipkart, or ISRO). Write a paragraph explaining the connection.
- Exercise 3: Create a mind-map connecting policy gradient methods: reinforce algorithm to at least 3 other topics you have studied.
Key Takeaways — Summary and Recap
Let us recap what we covered: the core ideas behind policy gradient methods: reinforce algorithm, how they connect to real-world applications, and why they matter for your journey in computer science. Remember these key points as you move forward. For competitive exam preparation (CBSE, JEE, BITSAT), focus on understanding the WHY behind each concept, not just the WHAT.