REINFORCE algorithm

WHAT are we optimizing?

WHY a policy directly? In continuous or huge action spaces, taking $\arg\max_a Q(s,a)$ is hard. A parameterized policy handles stochasticity, continuous actions, and gives smooth optimization.

HOW: deriving the Policy Gradient from scratch

We want $\nabla_\theta J(\theta)$. The trouble: the expectation is over a distribution that depends on $\theta$. We can't just push the gradient inside — so we use the log-derivative trick.

Step 1 — Write the expectation as an integral over trajectories. $J(\theta) = \int p_\theta(\tau)\, R(\tau)\, d\tau$ Why? An expectation is just a probability-weighted sum/integral of the quantity.

Step 2 — Differentiate; gradient moves inside the integral (linear operator). $\nabla_\theta J = \int \nabla_\theta p_\theta(\tau)\, R(\tau)\, d\tau$ Why? $R(\tau)$ doesn't depend on $\theta$ (rewards come from the environment), only $p_\theta(\tau)$ does.

Step 3 — The log-derivative trick. Note the identity $\nabla_\theta p_\theta(\tau) = p_\theta(\tau)\, \nabla_\theta \log p_\theta(\tau)$ Why? Because $\nabla_\theta \log p = \frac{\nabla_\theta p}{p}$ — just the chain rule on $\log$. Multiply both sides by $p$.

Substitute: $\nabla_\theta J = \int p_\theta(\tau)\, \nabla_\theta \log p_\theta(\tau)\, R(\tau)\, d\tau = \mathbb{E}_{\tau}\big[\nabla_\theta \log p_\theta(\tau)\, R(\tau)\big]$ Why this matters: it turned a gradient-of-an-expectation into an expectation of a gradient, which we can estimate by sampling trajectories (Monte Carlo).

Step 4 — Expand $\log p_\theta(\tau)$. The trajectory probability is $p_\theta(\tau) = \rho(s_0)\prod_{t=0}^{T} \pi_\theta(a_t\mid s_t)\, P(s_{t+1}\mid s_t,a_t)$ Take log (product → sum): $\log p_\theta(\tau) = \log\rho(s_0) + \sum_t \log\pi_\theta(a_t\mid s_t) + \sum_t \log P(s_{t+1}\mid s_t,a_t)$ Now differentiate w.r.t. $\theta$. The environment terms $\rho$ and $P$ do not depend on $\theta$, so their gradients vanish! $\nabla_\theta \log p_\theta(\tau) = \sum_{t=0}^{T} \nabla_\theta \log \pi_\theta(a_t\mid s_t)$ Why this is huge: We get the gradient without knowing the transition model $P$ — REINFORCE is model-free.

Why $G_t$ (reward-to-go) instead of full $R(\tau)$? The action at time $t$ can only affect future rewards. Rewards earned before $t$ are noise as far as $a_t$'s credit is concerned. Dropping them keeps the estimator unbiased but lowers variance. This is causality.

The baseline: variance reduction

$\nabla_\theta J = \mathbb{E}\!\left[\sum_t \nabla_\theta \log\pi_\theta(a_t\mid s_t)\,\big(G_t - b(s_t)\big)\right]$

Why is this still unbiased? For any baseline that doesn't depend on the action: $\mathbb{E}_{a\sim\pi}\big[\nabla_\theta \log\pi_\theta(a\mid s)\,b(s)\big] = b(s)\sum_a \nabla_\theta \pi_\theta(a\mid s) = b(s)\,\nabla_\theta \underbrace{\sum_a \pi_\theta(a\mid s)}_{=1} = b(s)\cdot 0 = 0$ So the baseline changes variance but adds zero bias. A common choice: $b(s_t) = \hat V(s_t)$, giving the advantage $A_t = G_t - \hat V(s_t)$.

The Algorithm (Monte Carlo, episodic)

Initialize θ (policy network), optional value net for baseline
repeat:
    Sample an episode τ = (s0,a0,r0,...,sT) using π_θ
    for t = 0 ... T:
        G_t = Σ_{k=t..T} γ^{k-t} r_k          # reward-to-go
        A_t = G_t - b(s_t)                     # optional baseline
    Loss  = - Σ_t log π_θ(a_t|s_t) * A_t       # minus: grad ASCENT
    θ ← θ + α ∇_θ ( -Loss )                    # via autograd + optimizer
until converged

Why the minus sign? Optimizers minimize. We want to maximize $J$, so we minimize $-J$.

Worked Examples

Common Mistakes (Steel-manned)

Active Recall

Flashcards

Connections

• Policy Gradient Methods — REINFORCE is the foundational instance.
• Actor-Critic Methods — replaces Monte-Carlo $G_t$ with a learned critic (baseline + bootstrapping).
• Advantage Function — $A_t=G_t-V(s_t)$ used as the weighting.
• Value Function V(s) — a natural baseline choice.
• Monte Carlo Methods — REINFORCE returns are full-episode MC estimates.
• Log-Derivative Trick — the core mathematical identity.
• Softmax Policy / Gaussian Policy — common parameterizations of $\pi_\theta$.
• Variance Reduction in RL — baselines, reward-to-go, control variates.

Concept Map

Hinglish (regional understanding)