What Policy Gradient Can Reach

Starting point. For a response $y$ to a prompt $x$, the model assigns probability $\pi_\theta(y\mid x)$; write $\mathrm{score}(y)=\nabla_\theta\log\pi_\theta(y\mid x)$. Responses are drawn by a sampler $\smu$, each with a learning signal $A$ (a reward or advantage), and each enters the update through its score centered under $\smu$, written $c(y)$: at every position, the drawn token’s logit gradient minus its average under $\smu$. The expected update and the sampler’s Fisher are

Centering makes $\mathbb{E}_{\smu}[c]=0$, so $G$ is a covariance (Part 1); on-policy, $c$ is the plain score and $G$ the policy gradient. Part 2 shows that a confident sampler concentrates $F^{\mu}$ on a few directions; this part asks how far $G$ can move one response.

1. A question that can be answered

Ask how much one update moves a response’s log-odds against another.

“Can reinforcement learning (RL) learn something new?” is too vague to prove anything about. A version that can be proved: for a response $y$ that the model rarely produces but the reward likes, how much can one update change its probability? The normalizer moves many responses at once, so the log-odds against a reference $y'$ isolates learning $y$ itself. Here $G$ is the expected update defined above, $\eta$ the size of a step along it, and $\mathrm{score}(y)$ the model’s score of the target. In the running example: after “She drank a cup of”, can matcha rise if the sampler never says it?

2. A response moves as far as it resembles the sampler’s outputs

One update moves a response only as far as its score resembles the scores of what the sampler draws.

The similarity $K(y,y'')$ says how much raising a sampled $y''$ raises $y$ along the way. Matcha is never sampled, but if its score shares directions with tea’s, rewarding tea lifts matcha too. A response whose score is orthogonal to the centered scores of everything the sampler draws gets $\mathrm{score}(y)^\top G=0$: to first order its log-probability does not move, however high its reward. With $v$ a coordinate vector it is the per-parameter cap $|G_i|\le\operatorname{std}_{\smu}(A)\sqrt{F^{\mu}_{ii}}$; here it holds in any direction.

3. One logit per response: growth in proportion to probability

On-policy, with one logit per response, a response grows at a rate proportional to its own probability.

The model. Fix a prompt with finitely many responses and give each response $y$ its own logit $z_y$: the parameters are the logits, and $\pi=\operatorname{softmax}(z)$. Sampling is on-policy ( $\smu=\pi$), the update is the expected gradient, and time $t$ is step size times number of steps, so the logits follow $dz/dt=G$. Write $r(y)$ for the reward, $\bar r=\mathbb{E}_\pi[r]$ for its mean, and $A(y)=r(y)-\bar r$ for the advantage. In these coordinates the score is $\mathrm{score}(u)=e_u-\pi$, with $e_u$ the indicator of $u$.

Component $y$ of a sampled score is $1-\pi(y)$ when $y$ itself is drawn, which happens with probability $\pi(y)$, and only $-\pi(y)$ otherwise, so every push on $z_y$ carries a factor $\pi(y)$. A log-probability, $\log\pi(y)=z_y-\log\sum_u e^{z_u}$, also moves with the normalizer, which shifts every log-probability by the same amount; the log-odds cancel it. For two rare responses both rates are small, as the bound of section 2 says: with the on-policy Fisher in logits, $F^{\mu}=\operatorname{diag}(\pi)-\pi\pi^\top$, and $v=e_y-e_{y'}$,

A rare rewarded response. Let a target $y^\star$ start at probability $\varepsilon$ with reward $\Delta$, the reward gap, while every other response earns 0. Write $p=\pi(y^\star)$. Then $\bar r=p\Delta$, $A(y^\star)=\Delta(1-p)$, and every other response has $A(u)=-p\Delta$:

How long $p$ takes to reach one half depends on where the competing probability sits:

• One dominant competitor. Its logit falls as fast as the target’s rises, so the log-odds between them grow at $2\Delta p(1-p)$ and the time is about $1/(2\varepsilon\Delta)$. The figures use this case.
• Many small competitors. Each competitor’s logit barely moves, only the target’s does, and the time is about $1/(\varepsilon\Delta)$.

Either way the time grows like $1/\varepsilon$: most of it is spent near the start, where the growth rate is proportional to $p$ itself. This matches the theory of softmax policy gradient, whose rate depends on how much probability the optimal action keeps (Mei et al., 2020), and which can take exponential time in the worst case (Li et al., 2021).

4. A demonstration injects probability directly

A demonstration pushes a response at a rate that does not shrink with its probability.

In any model, imitating a response $y^\star$ moves the parameters along its own score:

In the one-logit model of section 3 the step is $e_{y^\star}-\pi$, again with $p=\pi(y^\star)$:

The target’s logit rises at nearly 1 however small $p$ is. With one dominant competitor the log-odds grow at $2(1-p)$, and reaching one half takes $\tfrac12(1-\ell_0-e^{\ell_0})\approx\tfrac12\log(1/\varepsilon)$, with $\ell_0$ the starting log-odds; with many small competitors it takes twice that, about $\log(1/\varepsilon)$. From $\varepsilon=0.01$ these are 2.8 and 5.6; from $\varepsilon=0.001$, 4.0 and 7.9. The expression $1-2p+\sum_y\pi(y)^2$ is the squared logit update of Logit Dynamics for a chosen action; in the output layer, the row of $y^\star$ receives $1-p$ times the last hidden state (Part 2).

Policy gradient is a demonstration scaled by probability. On-policy, in any model,

since only $y^\star$ is rewarded. Policy gradient takes the demonstration’s step shrunk by $p\Delta$. At equal step size and $\Delta=1$, that factor is the whole difference: $1/\varepsilon$ against $\log(1/\varepsilon)$, in either case of section 3. Supervised fine-tuning can inject mass into a response the sampler never produces. Policy gradient can only amplify what it already reaches through similarity.

5. Limits of the bound

The bound covers one first-order step of one estimator, and leaves room for policy gradient to learn new behavior.

• Shared structure. In a network the similarity $K$ has off-diagonal entries, so a response never sampled moves with the rewarded samples it resembles (section 2): new solutions recombined from existing pieces are within reach.
• Many steps. The Fisher drifts. In Zhang, Mukherjee & Peng (2026), the initial high-Fisher set keeps 70–78% of its coordinates through 1,000 steps, well above chance, and the mean Fisher of the initial low-Fisher set rises by 15–17%. Directions that were invisible can open; a multi-step bound would need control over that drift, and none exists yet.
• First order. Large steps and strong nonlinearity add higher-order terms.
• Which estimator, and which sampler. With full importance weighting (each sampled response weighted by $\pi_\theta/\smu$), the expected update is the on-policy gradient, bounded by the model’s own Fisher whatever the sampler, so changing the sampler leaves the reach of a single step unchanged. With the score centered under the sampler, the update is $\operatorname{Cov}_{\smu}(A,c)$, bounded by $F^{\mu}$: a different sampler (a higher temperature, an exploration bonus, or posterior sampling as in Exploration at Scale) changes which directions are visible. Value-based temporal-difference learning has no score weighting, so the bound does not apply to it.
• Sparse can be substantial. A new capability can live in a few parameters.

6. What to measure

Whether policy gradient can learn a behavior depends on score similarity as well as on probability.

The debate over whether RL extends a base model’s abilities usually looks at probability: at large k, the base model’s pass@k, the chance that one of k samples is correct, can exceed that of the RL-trained model (Yue et al., 2025). The bound points to $v^\top F^{\mu}v$ from section 2, the overlap between the target behavior’s score and what the sampler produces. Among equally unlikely responses, those that share structure with high-reward samples can be amplified and isolated ones cannot. Policy gradient is similarity-driven amplification. Whether it yields new capabilities depends on how new behavior connects, through shared parameters, to what the sampler already generates, and on which sampler is used.

Choosing the sampler is the exploration problem, which Exploration at Scale treats on its own terms.

Next. Part 4 follows the competing tokens into hidden space: the directions that cap each parameter also bound the rank of the whole update, and a LoRA of that rank carries it.

References

• J. Mei, C. Xiao, C. Szepesvári, D. Schuurmans. On the Global Convergence Rates of Softmax Policy Gradient Methods. ICML 2020.
• G. Li, Y. Wei, Y. Chi, Y. Chen. Softmax Policy Gradient Methods Can Take Exponential Time to Converge. COLT 2021.
• Y. Yue, Z. Chen, R. Lu, et al. Does Reinforcement Learning Really Incentivize Reasoning Capacity in LLMs Beyond the Base Model? 2025.
• Y. Li. Logit Dynamics in Softmax Policy Gradient Methods. arXiv, 2025.
• Y. Zhang, S. Mukherjee, H. Peng. Understanding LLM Parameter Update Sparsity through the Lens of Fisher. arXiv, 2026.
• Y. Li, J. Xu, B. Wang, Z.-Q. Luo. Scalable Exploration via Ensemble++. NeurIPS 2025.

Citation

@online{li-2026-what-policy-gradient-can-reach,
  title  = {What Policy Gradient Can Reach},
  author = {Li, Yingru},
  year   = {2026},
  month  = oct,
  url    = {https://richardli.xyz/post/what-policy-gradient-can-reach/}
}