REINFORCE — Sample Efficient Reinforcement Learning with REINFORCE

01 — Every symbol, explained

The vocabulary first

This is a theory paper, so the symbols matter more than usual. Every one used anywhere below is here. Click any of them — each gets a plain-English reading, a precise definition, why it exists, and a drawing.

\pi_\theta(a \mid s)

the policy

in plain words

A table of preferences. For each situation it holds a probability for every action — and those probabilities are what training changes.

precisely

A stationary stochastic policy, viewable as a vector in ℝ^{SA} on the probability simplex. Here S and A are finite, so the policy is a genuine table rather than a network.

why it is there

The whole analysis leans on the policy being a finite, explicitly parameterised object. That is what lets the authors say anything global about where optimisation ends up.

where it appears

1 of 17 — use the arrows, or click a symbol above.

If you read only one of these, read the score function. It is the identity that makes policy gradients possible at all: you cannot differentiate through the act of sampling, but you can weight the score of whatever you happened to sample by how well it turned out.

02 — The estimator

How you differentiate through a dice roll

You want the gradient of an expectation over trajectories you sample. You cannot differentiate the sampling itself — so instead you weight the score of whatever you happened to sample by how well it went.

the problem

The objective is an average over randomness

F(\pi_\theta) = \mathbb{E}\Big[\textstyle\sum_t \gamma^t r(s_t, a_t)\Big]

θ affects which trajectories you see, not the rewards along a given one. So the thing you want to differentiate is hidden inside the distribution you are sampling from.

the identity

Rewrite it as a weighted score

\nabla_\theta \pi_\theta = \pi_\theta \,\nabla_\theta \log \pi_\theta

Divide and multiply by π. Now the gradient of a probability is that probability times the gradient of its logarithm — and anything of the form “π times something” is an expectation you can estimate by sampling.

the estimator

Play once, weight, step

\widehat{\nabla} = \big(\hat Q - b\big)\,\nabla_\theta \log \pi_\theta(a\mid s)

The score says which way to push to favour the action you took. The return says how much you wanted to. That product, averaged, is the policy gradient.

Run it — one state, four actions, real arithmetic

0 episodes

the policy, right now

last return G

—

the true value plus noise — the agent only ever sees this

what to watch

The sampled action's score is positive and every other action's is negative, because probabilities must sum to one. Multiply by the return and the sampled action gets pushed up whenever the return was good — and down whenever it was bad, which without a baseline almost never happens, since returns here are always positive.

turn the baseline on

Now G − b is negative for below-average episodes, so bad draws actively push their action down instead of merely pushing it up less. The policy separates much faster, and the estimate is still unbiased.

\widehat{\nabla}_\theta = \big(\hat Q(s,a) - b(s)\big)\,\nabla_\theta \log \pi_\theta(a \mid s), \qquad \big[\nabla_\theta \log \pi_\theta\big]_i = \mathbb{1}[i = a] - \pi_\theta(i)

the full estimator used in the paper

\widehat{\nabla}_\theta L_{\lambda_l}(\theta_{l,k}) = \sum_{t=0}^{\lfloor \beta H \rfloor} \gamma^t \big(\hat Q^{l,k}(s_t, a_t) - b(s_t)\big)\nabla_\theta \log \pi_{\theta_{l,k}}(a_t \mid s_t)\; + \;\frac{\lambda_l}{SA}\sum_{s,a} \nabla_\theta \log \pi_{\theta_{l,k}}(a \mid s)

Three things are happening. The first sum is ordinary REINFORCE with a baseline. The upper limit ⌊βH⌋ throws away the tail of the episode, where the estimated Q-values are built from too few remaining rewards to trust. The second term is the gradient of the log-barrier, pushing every probability away from zero.

Why the returns have to be estimated

Q̂(s_t, a_t) is just the discounted sum of the rewards that actually followed, from t onward. It is an estimate of a true expected value you never observe — and for a step near the end of the episode there are hardly any rewards left to sum, which is exactly why the tail is cut.

biased but bounded

Truncating introduces bias. In exchange, every estimate is bounded — and the paper is explicit that this swap is the technical crux. Earlier proofs used state-action visitation estimators, which are unbiased but unbounded, and the analysis leaned on that unbiasedness. Here the analysis has to absorb the bias, and gets to exploit the bound instead.

03 — Variance

The cheapest improvement in reinforcement learning

Subtract any number that does not depend on the action you took. The gradient's average is unchanged; its spread can fall dramatically.

baseline b = 0.00

variance of the gradient estimate, as b moves

the 400 individual estimates, for the best action

dashed line = the average, which barely moves. the spread is what changes.

variance

0.1474

noisy — the estimate jumps around between episodes

mean estimate

+0.0980

essentially unchanged by b — which is the whole point. The baseline is free.

why it is free

Because the scores sum to zero across actions, subtracting anything that does not depend on the action adds a term whose expectation is exactly zero. The mean survives; only the spread changes.

in this paper

The requirement is only that b(s) be independent of the sampled trajectory, and bounded by some B. b = 0 recovers the plain estimator. Nothing forces you to choose well — but choosing badly costs you sample efficiency, not correctness.

\mathbb{E}\big[b(s)\,\nabla_\theta \log \pi_\theta(a \mid s)\big] = b(s)\sum_a \pi_\theta(a\mid s)\,\nabla_\theta \log \pi_\theta(a\mid s) = b(s)\,\nabla_\theta\!\!\sum_a \pi_\theta(a \mid s) = b(s)\,\nabla_\theta 1 = 0

Read left to right: the baseline term factors out, the remaining sum is the gradient of a quantity that is always one, and the gradient of a constant is zero. That single line is why baselines are the first thing anyone adds to REINFORCE.

Why variance is the enemy here

With one trajectory per update there is no averaging to smooth the estimate. A noisy gradient means steps that partly cancel, so progress is slow and erratic even when the direction is right on average.

Why it costs nothing

Scores sum to zero across actions, so a term that does not depend on the action contributes exactly zero in expectation. You get the variance reduction for free, with no bias introduced.

What the paper requires

Only that b(s) be independent of the sampled trajectory and bounded by some B. The results hold for any such choice, including the adaptive reinforcement baseline and b = 0.

A subtlety worth noticing. Without a baseline, when every return is positive, every update pushes the sampled action's probability up — bad actions simply get pushed up less than good ones. The policy still learns, because probabilities must sum to one, but it learns by a slower and noisier route than it needs to.

04 — The gap

Theory needed an infinite batch. Practice never had one.

Before this paper, every global convergence result for vanilla policy gradients required the number of trajectories per update to grow without bound — or settled for convergence only to within a floor set by the batch size.

what the proofs assumed

Batch size M → ∞, so the gradient estimate's error vanishes and the analysis splits cleanly into deterministic ascent plus a shrinking error term.

what people actually run

One trajectory, or a fixed handful. The same cost per update, forever — and empirically it works fine.

the residual floor, and its removal

Earlier fixed-batch results guaranteed convergence only to within Θ(1/M^p) of the optimum — a floor you could lower by paying for a bigger batch, but never reach. This paper removes it.

Four things that changed

Batch size per updatemust diverge to infinity→a single trajectory, or any fixed size

A diverging batch makes the gradient estimate's error vanish, which lets the analysis split into clean deterministic ascent plus a shrinking error term. With a fixed batch that decoupling is simply unavailable.

Gradient estimatorstate-action visitation measure→the REINFORCE estimator

The visitation-measure estimator is unbiased but unbounded; REINFORCE is biased but bounded. The proof has to absorb the bias and, in return, gets to lean on the boundedness.

Residual errora non-vanishing Θ(1/M^p) term→removed

Earlier results only guaranteed convergence to within a floor set by the batch size M. Here the floor is gone entirely.

Mode of convergencein expectation→almost surely, and with high probability

A statement about the average over hypothetical repeats is weaker than a statement about the run you actually performed.

05 — How the proof works

Three tools, and what each one costs

None of these change the algorithm anyone runs. They are the scaffolding that makes a statement about it possible.

what it is

Add λ·(average log probability) to the objective.

L_\lambda(\theta) = F(\pi_\theta) + \lambda R(\theta)

R(\theta) = \tfrac{1}{SA}\textstyle\sum_{s,a} \log \pi_\theta(s,a)

why it is needed

Under softmax, probabilities can approach zero and the optimisation can stall on a plateau where the gradient has vanished but the policy is still bad. The barrier makes that region infinitely expensive, so it cannot be reached.

what it costs

It changes what you are optimising. Hence the phases, which shrink λ toward zero so the surrogate converges back to the real objective.

how they fit together

Inside a phase, λ is fixed, so you are doing ordinary stochastic ascent on a smooth regularised objective. Split that phase's episodes into those where the gradient is still large and those where it is not: on the second group a known result bounds the sub-optimality directly, and the first group must be small because each such episode makes measurable progress. That gives a bound per phase. The doubling trick then stitches the phases together into a single bound that holds at any episode count, with λ decaying so the surrogate converges back to the objective you actually wanted.

06 — The algorithm

The same update, twice

On the left, REINFORCE as anyone writes it. On the right, the version the proof is about. The update rule is byte-for-byte identical — everything added is scaffolding around it.

policy gradient, single trajectory

line 1

The plain version, before any of the machinery. This is REINFORCE as almost everyone writes it.

what is active

PostProcess, in full

\hat\pi = \epsilon_{pp}\mathbf{1} + (1 - A\epsilon_{pp})\pi_\theta

Mix the current policy with the uniform one. Every action then has probability at least ε_pp, which keeps the log-barrier bounded so the next phase's analysis is valid. It is a small nudge, applied only at phase boundaries.

Compare the two update lines. They are the same: take a step along the estimated gradient of the regularised objective. Everything the phased version adds — fixed λ per phase, doubling lengths, a probability floor restored at each boundary — exists so the proof can proceed, not so the algorithm can work better.

07 — What was proved

Three statements, and what each one means

Read these carefully — the strength is in the qualifiers. Anytime, high-probability, almost sure.

Anytime sub-linear high-probability regret

\begin{aligned}\mathrm{regret}(N) \le\;& d_1 (N+c)^{d_2}\big(\log(N/\delta)\big)^{d_3} \\[2pt] &+\, d_4 (\log N)^{d_5}\end{aligned}

With probability at least 1 − δ, total regret grows slower than the number of episodes — so the average regret per episode shrinks toward zero. It holds at every N, not only at a horizon fixed in advance.

Almost-sure global convergence of the average regret

\lim_{N \to \infty} \frac{\mathrm{regret}(N)}{N+1} = 0 \quad \text{almost surely}

Not just in expectation, and not just with high probability — on essentially every run. This is stronger than the expected-convergence results that dominate the literature.

An explicit asymptotic rate

O\!\left(\frac{S^2 A^2}{(1-\gamma)^7}\left\lVert \frac{d^{\pi^\star}_\rho}{\rho}\right\rVert_\infty^{5}\right)

Polynomial in the size of the problem — not exponential. That is what 'sample efficient' means here: the cost grows manageably with the number of states and actions, even if the constants are large.

what sub-linear regret looks like

Total regret keeps rising — you never stop paying for imperfect play. But it rises more slowly than the episode count, so the average cost per episode goes to zero. Phase lengths roughly double, so later phases are much longer than early ones.

regret, defined

\mathrm{regret}(N) = \sum_{n=0}^{N} \Big(F^\star - \hat F^{l,k}(\pi_{\theta_{l,k}})\Big)

Every episode contributes the gap between the best achievable value and what your policy was worth at that moment. It charges you for the whole learning curve, not just the destination — which is why it is a stricter demand than “does it eventually converge”.

why “almost surely” is the strong one

A result in expectation says: average over infinitely many hypothetical repeats of the experiment, and the average behaves. That is compatible with the single run you actually performed misbehaving forever.

Almost-sure convergence says: with probability one, this run's average regret goes to zero. The paper notes that these stronger modes are not what dominates the vanilla policy-gradient literature.

08 — What it does not say

Read the constants before you get excited

The authors are unusually direct about the boundaries of the result. This section is their caveats, not editorial ones.

The constants are enormous

A 1/(1−γ)⁷ factor and a fifth power of the distribution-mismatch coefficient. The result establishes that the cost is polynomial, not that it is small. Nobody should read these bounds as practical sample-complexity estimates.

Finite states and actions, tabular softmax

The analysis assumes S and A are finite and the policy is a softmax over a parameter per state-action pair. Function approximation — which is what every practical use of REINFORCE relies on — is outside the setting.

The initial distribution must cover everything

ρ is assumed component-wise positive, and the distribution-mismatch coefficient ‖d^{π*}_ρ/ρ‖_∞ appears in the rate. If the start distribution neglects states the optimal policy needs, the bound degrades.

This is analysis, not a better algorithm

The authors are explicit that the goal is to understand an algorithm people already use, with little or no modification — not to tweak it toward near-optimal bounds. The paper ends by saying the picture is incomplete and listing open questions.

the claim, stated exactly

For episodic reinforcement learning over a finite MDP, with a softmax policy and a log-barrier regulariser, REINFORCE run with a single trajectory per update — or any fixed batch size — achieves sub-linear regret with high probability at every episode count, and its average regret converges to zero almost surely, at a rate polynomial in the size of the problem. It is a statement about why a method people already use is sound, not a proposal to change it.

One episodeat a time,and it still converges