Information Bandwidth in Reinforcement Learning

The figures step through like slides. Use → or ▶, and step back with ←.

1. One bit per episode

For an outcome reward the one-bit count is exact, and the limit comes from the reward, not from policy gradient.

LoRA Without Regret finds that LoRA matches full fine-tuning for policy-gradient RL even at rank 1, and explains it by counting bits. A policy-gradient update depends on the reward only through a scalar advantage, so an episode with one final reward teaches about one bit. Their MATH run, 10,000 problems with 32 samples each, then has at most 320,000 bits to absorb, and a rank-1 adapter on Llama-3.1-8B has almost ten times as many parameters.

This post makes the count exact. It rests on one fact: the learner drew the response itself. From there the chain rule shows what sets the count (the reward), what can lower it (an update that collapses the reward to one number), and what cannot raise it (baselines and critics).

2. Every bit enters through the reward

Given the history, a response the learner sampled says nothing about the reward, so no update can learn more than the reward’s entropy.

For a language model the transitions are known: the state $s_t$ is the prompt and the tokens so far, the action $a_t$ is the next token, and taking it appends it. Only the reward is unknown. Put a prior on its parameter $\xi$, and let $\pi^\star$ be the optimal policy for $R_\xi$, with ties broken by a fixed rule. The prior is a modeling device, not a claim that algorithms are Bayesian: it makes “what the update tells us about $\pi^\star$” a mutual information, $I(u;\pi^\star\mid\mathcal H)$. The information bandwidth of an algorithm is the most one episode can teach it, $\sup_{\mathcal H} I(u;\pi^\star\mid\mathcal H)$.

Lemma. Let the update $u$ be any function of the response $\tau$, its rewards $\mathbf r$, the history $\mathcal H$, and randomness independent of $\xi$. Then

The steps are data processing, the chain rule, and $I\le H$. The middle term vanishes because the sampler that drew $\tau$, on-policy or not, is a function of $\mathcal H$, and its sampling noise does not depend on $\xi$: given the history, $\tau$ is independent of $\xi$, hence of $\pi^\star$.

Any algorithm that trains on its own samples computes its update this way: REINFORCE, GRPO, and PPO with its clipping, critic and several epochs per batch. Nothing in the lemma is specific to policy gradient; it holds for any learner trained on its own responses and their rewards, as long as the environment adds nothing to $\tau$. Algorithms differ only in how much of $H(\mathbf r\mid\tau,\mathcal H)$ their update keeps.

3. A pass/fail episode teaches at most one bit, often far less

With one outcome reward, an episode teaches at most h(p) ≤ 1 bit, where p is the pass rate the learner predicts.

For a reward $r\in\{0,1\}$ at the end, conditioning can only lower entropy, so

where $\bar p=P(r=1\mid\mathcal H)$ is the pass rate predicted from everything seen so far.

Applying the same bound to each reward in turn, a group of $n$ samples of one prompt teaches at most $n\,h(\bar p)$ bits. Prompts the model almost always or almost never solves teach almost nothing. Their groups are mostly all passes or all fails, which a group-mean baseline turns into a zero update and which the dynamic sampling of Yu et al. (2025) filters out.

Over a run, the weights $\theta_K$ after $K$ episodes are a function of the history and of randomness independent of $\xi$, so the chain rule adds up the episodes:

$K$ pass/fail episodes put at most $K$ bits about $\pi^\star$ into the weights, whatever the model size or compute. The 320,000 bits of the MATH run in section 1 are a bound, not an estimate.

4. With dense rewards, the advantage decides what gets through

One scalar advantage keeps at most log₂ B bits; per-token advantages keep the whole reward sequence.

With a reward $r_t$ at every token there is more to learn per episode, and the update can now lose some of it. Given $\tau$ and $\mathcal H$ the token scores $\psi_t$ are fixed, and the advantages only weight them:

The scalar form depends on $\mathbf r$ only through $\mathrm{Adv}=\sum_t r_t-b$, one number with at most $B$ values, so the lemma tightens to $I(u;\pi^\star\mid\mathcal H)\le H(\mathrm{Adv}\mid\tau,\mathcal H)\le\log_2 B$. Per-token advantages, whether returns-to-go, TD errors or GAE, are an invertible function of $\mathbf r$ given $(\tau,\mathcal H)$. When the token scores are linearly independent, the update keeps everything the rewards say about $\pi^\star$.

A sum forgets order: (+1, −1), (−1, +1) and (0, 0) all add up to zero. What that costs depends on the reward. For $T=1000$ tokens and no discount:

The scalar ceiling grows like $\log T$, the per-token ceiling like $T$. With one outcome reward there is nothing to forget, and the two forms are equal. With $B_r$ values per reward, the dense ceiling is reached only if every reward is uniform and unpredictable from the earlier ones,

so a dense reward whose steps are predictable from one another teaches little more than a single reward.

5. What changes the bandwidth, and what does not

Baselines and critics move bits around without adding any. More bits come only from the reward, the sampler, or someone else’s data.

• Baselines, critics and per-token credit. A baseline computed from the history, or from the other rewards in a group, only reshuffles bits the group already has. A critic is trained on earlier episodes, so what it knows is already in $\mathcal H$. Neither adds a bit. What they change is the noise that comes with the bits, and so how many episodes an optimizer needs to use them; the Optimal Token Baseline is the variance-optimal choice.
• A denser reward. A process reward that scores each of $m$ steps raises the ceiling to as much as $m\log_2 B_r$ bits, but only with per-token advantages, and only as far as its scores are unpredictable from one another.
• The sampler. $H(\mathbf r\mid\tau,\mathcal H)$ depends on which response is drawn, so a sampler that goes where the outcome is uncertain gets more bits per episode. Information-directed sampling (Russo & Van Roy, 2018) picks samples by trading this information against regret. Thompson sampling sends the learner where plausible models disagree, which is where outcomes are uncertain, and Exploration at Scale makes it affordable for deep networks.
• Someone else’s responses. The lemma rests on one fact: the learner drew $\tau$ itself. A demonstration is drawn by someone else, so the response itself carries information, up to $T\log_2\lvert\mathcal V\rvert$ bits for a vocabulary $\mathcal V$. This is why SFT can teach far more per episode, and why it lifts rare responses that policy gradient raises only slowly (What Policy Gradient Can Reach).

Few bits explain why an RL update carries little. Which coordinates it moves is a separate question, the subject of Why Post-Training Is Sparse.

6. Scope

• The bound is on capacity, not rate: what an episode can teach, not what an optimizer extracts from it.
• For a continuous reward, stop one step early: the bound is $I(\mathbf r;\pi^\star\mid\tau,\mathcal H)$, which stays finite when the reward is noisy.
• In a multi-turn agent, tool outputs and user replies inside $\tau$ come from the environment, not from the learner. They can carry information too, and the bound gains a term for what they reveal.
• Nothing here is measured in a real run.

References

• J. Schulman and Thinking Machines Lab. LoRA Without Regret. Thinking Machines Lab: Connectionism, 2025.
• E. J. Hu, Y. Shen, P. Wallis, et al. LoRA: Low-Rank Adaptation of Large Language Models. ICLR 2022.
• R. S. Sutton, D. McAllester, S. Singh, Y. Mansour. Policy Gradient Methods for Reinforcement Learning with Function Approximation. NeurIPS 1999.
• V. R. Konda, J. N. Tsitsiklis. Actor-Critic Algorithms. NeurIPS 1999.
• J. Schulman, P. Moritz, S. Levine, M. Jordan, P. Abbeel. High-Dimensional Continuous Control Using Generalized Advantage Estimation. ICLR 2016.
• J. Schulman, F. Wolski, P. Dhariwal, A. Radford, O. Klimov. Proximal Policy Optimization Algorithms. arXiv, 2017.
• Z. Shao, P. Wang, Q. Zhu, et al. DeepSeekMath: Pushing the Limits of Mathematical Reasoning in Open Language Models. arXiv, 2024.
• Q. Yu, Z. Zhang, R. Zhu, et al. DAPO: An Open-Source LLM Reinforcement Learning System at Scale. arXiv, 2025.
• D. Russo, B. Van Roy. Learning to Optimize via Information-Directed Sampling. Operations Research, 2018.
• T. M. Cover, J. A. Thomas. Elements of Information Theory, 2nd ed. Wiley, 2006.

Acknowledgements

I thank @mgostIH for pointing out that REINFORCE with per-token returns $G_t-b$ keeps the reward sequence, since each $r_t$ can be read off two consecutive returns. The first version of this post analyzed only the scalar advantage and TD errors.

Citation

@article{li2025information,
  title   = {Information Bandwidth in Reinforcement Learning},
  author  = {Li, Yingru},
  journal = {Richard Li's Blog},
  year    = {2025},
  url     = {https://richardli.xyz/post/information-bandwidth-rl/}
}

First posted October 2025; revised November 2025 and October 2026.