Information Bandwidth in Reinforcement Learning

Step 6: Calculate Effective Bandwidth.

The role of the critic: The effective bandwidth depends on critic quality:

When the critic is well-trained, $V_\phi(s_t)$ approximates true expected rewards, and the TD errors become informative about $\xi$ throughout the trajectory.

Important caveat: The $O(T)$ bandwidth is an upper bound that requires a well-trained critic. In practice, especially early in training or without careful critic tuning, the effective bandwidth may be much lower. The TD errors at different timesteps may also be correlated (not providing independent information), further reducing the effective bandwidth below the theoretical maximum.

Correlation between TD errors: In practice, TD errors at successive timesteps are often correlated, particularly in long sequences. This correlation reduces the effective information rate compared to the $T \cdot O(1)$ upper bound.

Rigorous bound: Even with correlation, the information still scales as $O(T)$, but with a reduced constant. If $\delta_t = \rho \delta_{t-1} + \epsilon_t$ where innovations $\epsilon_t$ are independent with $H(\epsilon_t) = c$ bits, then:

where $f(\rho) < 1$ is a decreasing function of correlation strength. For example, with $\rho = 0.7$, the effective constant might be reduced by a factor of $2$- $5\times$ compared to independent observations.

This correlation arises because:

• Consecutive states share most tokens (only one token differs)
• Value estimates propagate through bootstrapping
• Policy changes affect multiple timesteps similarly

While the asymptotic scaling remains $O(T)$, the reduced constant factor partially explains why actor-critic methods for LLMs haven’t achieved the full theoretical improvement over policy gradient. Additionally, optimization difficulties in training the critic further reduce practical gains.

Summary:

Part 4: Synthesis and Implications

4.1 Unified Comparison for Token-Level MDPs

Key Insights:

1. Signal density determines bandwidth: Episode-level ( $O(1)$) vs. token-level ( $O(T)$) makes a $T\times$ difference

2. For language models with sparse rewards:

   • Policy gradient: $\sim 1$- $4$ bits per episode
   • Actor-critic: $\sim T$ bits per episode where $T$ is sequence length
   • If $T = 1000$ tokens, actor-critic has $250$- $1000\times$ more bandwidth

3. Token-level MDP clarifies everything: No need to assume unknown dynamics—transitions are deterministic concatenation

4.2 Why LoRA Works: Complete Explanation

Setup: Fine-tune a large language model using REINFORCE for $N$ episodes.

Prior: Pre-trained model gives us prior $p(\xi)$ over reward functions (implicitly, from pre-training on diverse text data).

Information Accumulation:

After $N$ episodes of policy gradient, total information gained:

Key insight: Each term $I(G_i; \pi^* | \{G_j\}_{j < i})$ represents the marginal information from episode $i$. This decreases as training progresses due to:

1. Redundancy: Later episodes may visit similar states and observe similar rewards
2. Saturation: As $\pi_\theta$ approaches $\pi^*$, less new information is gained
3. Correlation: Episodes generated by the same (or similar) policy are not independent

Bounding total information: We have two constraints:

1. Per-episode bound: Each return provides at most $O(1)$ bits about $\pi^*$
2. Total uncertainty bound: $I_{\text{total}} \leq H(\pi^*)$ (cannot learn more than initial uncertainty)

Practical regime: In early/mid training where $N \cdot O(1) < H(\pi^*)$, marginal information per episode remains roughly $O(1)$, giving:

where $c \in [1, 4]$ depends on reward distinguishability. As training saturates, marginal gains decrease.

However, we also have the constraint that we cannot learn more than the initial uncertainty:

Concrete numbers: With $c = 2$ bits per episode (4-level rewards):

• After $N = 1000$ episodes: $\approx 2000$ bits $\approx 250$ bytes
• After $N = 10000$ episodes: $\approx 20000$ bits $\approx 2.5$ KB

Important caveat: These are upper bounds on useful information. Actual information about $\pi^*$ may be less due to noise and redundancy in episodes.

LoRA Capacity Analysis:

Rank- $r$ adapter for dimension- $d$ layer:

• Parameters: $2rd$ (two low-rank matrices)
• Storage capacity: $64rd$ bits (FP32 representation)

Example: $r = 8$, $d = 4096$ (typical for large LLMs):

• Parameters: $2 \times 8 \times 4096 = 65{,}536$
• Storage: $64 \times 8 \times 4096 = 2{,}097{,}152$ bits $= 256$ KB

Capacity comparison:

Why this comparison is meaningful: The LoRA parameters must encode the policy-relevant information learned through RL. While storage bits and information bits are different concepts, the argument remains valid: if LoRA can store $64rd$ bits and policy gradient provides only $\sim 2N$ bits of information, then LoRA’s representational capacity far exceeds the information bandwidth constraint.

Even for $N = 10{,}000$ episodes ( $\sim 20$ KB of information), LoRA still has $\sim 10\times$ excess capacity.

Why full fine-tuning is wasteful: A model with $M$ parameters has capacity $32M$ bits (FP32). For a 7B parameter model:

The model has 100 million times more capacity than policy gradient can fill!

4.3 Sample Complexity: An Information-Theoretic Perspective

Information-theoretic lower bound:

To reduce uncertainty about $\pi^*$ from prior entropy $H(\pi^*)$ to posterior entropy $\epsilon$:

Translating to sample complexity: If each episode provides $I_{\text{per-episode}}$ bits:

For different algorithms:

• Policy gradient: $I_{\text{per-episode}} = 1\text{-}4$ bits (with typical reward discretization) → $N_{\text{PG}} = \Omega(H(\pi^*)/c)$ where $c \in [1,4]$
• Actor-critic: $I_{\text{per-episode}} = O(T)$ → $N_{\text{AC}} = \Omega(H(\pi^*)/T)$

Important caveats:

1. Assumes information accumulates additively (ignores redundancy between episodes)
2. Real sample complexity depends on optimization dynamics (gradient descent may need more samples than information theory suggests)
3. Assumes perfect utilization of information (in practice, some information is “wasted”)
4. Actor-critic requires well-trained critic to achieve $O(T)$ bandwidth

Example (illustrative): If $H(\pi^*) \approx 10{,}000$ bits and $T = 1000$ tokens:

• Policy gradient: $\gtrsim 2{,}500$ to $10{,}000$ episodes
• Actor-critic: $\gtrsim 10$ to $1{,}000$ episodes (depending on critic quality)
• Gap: $10\times$ to $1000\times$ improvement possible

These are order-of-magnitude estimates that explain qualitative differences observed empirically, not rigorous sample complexity theorems.

4.4 Implications for LLM-RL

1. Dense vs. Sparse Rewards:

• Sparse (outcome-based): Reward only at sequence end → $O(1)$ bits/episode
• Dense (token-level): Reward at each token → $O(T)$ bits/episode
• Current limitation: Most LLM-RL uses sparse rewards (RLHF with binary preferences)
• Research opportunity: Develop methods for meaningful token-level reward signals

2. The Value-Based RL Gap:

Our analysis reveals that actor-critic methods should theoretically achieve $\sim T\times$ better sample efficiency than policy gradient. In traditional RL domains, PPO (actor-critic) requires $\sim 100\times$ fewer samples than REINFORCE.

However, for LLMs:

• Current state: No established training recipes for value function learning at scale
• Key challenges:
  • Value function training is unstable for large language models
  • Critic networks require careful initialization and hyperparameter tuning
  • Bootstrap error accumulation in long sequences ( $T \sim 1000$ tokens)
  • Computational overhead of maintaining and updating critics

Why this matters from an information-theoretic perspective:

• Current RLHF with policy gradient is limited to $O(1)$ bits/episode
• Successfully training critics could unlock $O(T) = O(1000)$ bits/episode
• This represents a $1000\times$ potential improvement in information bandwidth

3. Research Directions: Value-Based RL for LLMs:

From our information-theoretic analysis, developing effective value-based methods for LLMs is the highest-leverage research direction:

a) Stable Critic Training:

• Challenge: Value function learning at LLM scale
• Information perspective: Each successful critic update should provide $O(1)$ bits about $\xi$ per token
• Research questions:
  • What architectures enable stable value learning?
  • How to handle long-horizon credit assignment ( $T \sim 1000$)?
  • Can we leverage pre-trained representations?

b) Alternative Value Representations:

• Approach: Instead of learning $V_\phi(s_t)$, learn compressed value representations
• Information perspective: The critic need only capture $O(T)$ bits about expected rewards
• Concrete ideas:
  • Low-rank value functions
  • Hierarchical value decomposition
  • Outcome-conditioned value models

c) Hybrid Approaches:

• Monte Carlo + TD: Use sparse rewards but dense value targets
• Model-based value learning: Use reward models to generate dense pseudo-rewards
• Information gain: Even partial value information could provide $O(T/k)$ bits for some $k < T$

4. LoRA Rank Selection (For Current Policy Gradient Methods):

Given that we currently use policy gradient with $O(1)$ bits/episode:

Information accumulated in $N$ episodes: $\sim N \cdot 2$ bits (with 4-bin returns)

Choose rank $r$ such that: $64rd \geq 2N$

For $d = 4096$, $N = 1000$: $r \geq 1$ is sufficient!

In practice, $r = 8$ or $r = 16$ provides ample margin.

5. Multi-Task Learning: If fine-tuning on $K$ tasks simultaneously, information accumulation scales:

This explains why multi-task RL may benefit from higher-rank adapters.

4.5 Scope and Applicability

4.5.1 When This Analysis Applies

This information-theoretic framework is most applicable when:

1. Stationary reward functions: The analysis assumes $\xi$ is fixed. For continually evolving preferences or non-stationary objectives, the effective bandwidth must also account for tracking a moving target.

2. Pure policy learning: We focus on learning which policy is optimal, not exploration. Information-directed sampling or active learning would have different bandwidth properties.

3. Known dynamics: For token-level MDPs with deterministic transitions. Agentic settings with unknown stochastic dynamics require additional bandwidth for learning transition models (see Section 4.7).

4. Optimization is not the bottleneck: We measure information provided to the learning algorithm, not whether gradient descent can utilize it effectively. Poor optimization can waste available bandwidth.

This analysis may not directly apply to:

1. Partial observability: If the agent cannot observe the full state, additional bandwidth is needed to infer hidden information.

2. Exploration-exploitation settings: The framework assumes we’re learning from a fixed policy distribution, not actively exploring to gain information.

3. Multi-task or continual learning: Interference between tasks and catastrophic forgetting introduce additional constraints beyond information bandwidth.

4. Adversarial or strategic environments: When the environment responds to the policy, game-theoretic considerations matter beyond pure information flow.

4.6 Fundamental Trade-offs

1. Signal Density vs. Computational Cost

• Dense signals: $O(T)$ bandwidth but requires critic, more computation per step
• Sparse signals: $O(1)$ bandwidth but simpler algorithm, less computation
• Trade-off: Sample efficiency vs. computational efficiency

2. Prior Strength vs. Learning Speed

• Strong prior (good pre-training): Low $H(\pi^* | \text{prior})$, fast fine-tuning
• Weak prior: High $H(\pi^* | \text{prior})$, slow fine-tuning
• Recommendation: Invest in high-quality pre-training for faster RL fine-tuning

3. Adapter Capacity vs. Catastrophic Forgetting

• Low-rank adapters: Limited capacity, preserves pre-training
• Full fine-tuning: High capacity, risks forgetting
• Insight: Policy gradient’s low bandwidth naturally matches low-rank adapters, avoiding forgetting

Part 5: Conclusion

Main Results

We established a rigorous information-theoretic framework for RL in autoregressive generation:

1. Token-Level MDP Formulation

• States: Token sequences $s = (x_1, \ldots, x_t)$
• Actions: Next token $a = x_{t+1}$
• Transitions: Deterministic concatenation (known)
• Rewards: Parameterized by unknown $\xi$

2. Bayesian Framework Makes $I(S; \pi^*)$ Well-Defined

• Prior $p(\xi)$ over reward parameters
• Induces distribution over optimal policies $p(\pi^*)$
• Both $S$ and $\pi^*$ are random variables

3. Rigorous Information Bandwidth Results

• Policy gradient: $\mathcal{B}_{\text{effective}} = 1\text{-}4$ bits per episode (depending on reward distinguishability)
• Actor-critic: $\mathcal{B}_{\text{effective}} = O(T)$ bits per episode (upper bound requiring well-trained critic)
• Difference: $T\times$ where $T$ is sequence length ( $\sim 100$- $1000\times$ theoretical, less in practice due to TD error correlation)

4. LoRA Explained

• Policy gradient accumulates $O(N)$ bits over $N$ episodes
• LoRA capacity: $64rd$ bits ( $\sim 100{,}000\times$ more than needed)
• Perfect match between limited information and limited capacity

5. Sample Complexity Predictions

• Policy gradient: $\Omega(H(\pi^*))$ episodes
• Actor-critic: $\Omega(H(\pi^*)/T)$ episodes
• Explains $100$- $1000\times$ empirical differences

Open Questions

Our rigorous information-theoretic framework reveals fundamental bottlenecks and opportunities in RL for LLMs:

1. The Value Function Challenge (Highest Priority):

How can we develop stable, scalable methods for training value functions on LLMs?

• Information gain: Could unlock $\sim 1000\times$ improvement (from $O(1)$ to $O(1000)$ bits/episode)
• Key obstacles: Training stability, long-horizon credit assignment, computational overhead
• Promising directions: Low-rank critics, hierarchical decomposition, better initialization

2. Token-Level Reward Design:

Can we design meaningful dense reward signals without human annotation at every token?

• Current: Sparse outcome-based rewards ( $O(1)$ bits/episode)
• Potential: Token-level rewards ( $O(T)$ bits/episode)
• Approaches: Automated reward shaping, proxy signals, model-based pseudo-rewards

3. Information-Efficient Exploration:

How should we design exploration strategies to maximize $I(S; \pi^*)$ per token?

• Traditional RL uses entropy bonuses, but these don’t target information about $\xi$
• Information-directed sampling: Choose actions to maximize expected information gain about reward function

4. Multi-Objective RL:

How does information bandwidth extend to multiple reward functions $\{\xi_i\}_{i=1}^K$?

• Does learning about one objective help with others?
• How should we allocate limited bandwidth across objectives?

5. Continual Learning Dynamics:

As policy updates, the trajectory distribution $p(\tau | \pi_\theta, \xi)$ changes. How does this affect:

• Information accumulation rate over training?
• The relationship between bandwidth and convergence speed?
• Optimal learning rate schedules from an information perspective?

Practical Recommendations

For practitioners fine-tuning LLMs with RL:

Current Best Practices (Policy Gradient Era):

1. Use LoRA with small rank ( $r = 8$ to $16$) for policy gradient—our analysis shows full fine-tuning is wasteful given $O(1)$ bits/episode

2. Expect slow convergence: With $O(1)$ bits/episode, budget for thousands of episodes

3. Invest in pre-training quality to reduce $H(\pi^* | \text{prior})$ and speed up RL fine-tuning

4. For multi-task learning, scale LoRA rank proportionally to number of tasks ( $I_{\text{total}} = N \cdot O(K)$)

The $1000\times$ Opportunity:

Our analysis reveals a massive opportunity: successfully training value functions for LLMs could improve sample efficiency by $\sim 1000\times$ (from $O(1)$ to $O(T)$ bits/episode where $T \sim 1000$).

Priority Research Directions:

1. Develop stable critic training methods for LLMs

   • Low-rank value functions
   • Better initialization strategies
   • Hierarchical value decomposition

2. Design meaningful token-level rewards (currently most methods use sparse, outcome-based rewards)

3. Explore hybrid approaches that partially capture $O(T)$ bandwidth:

   • Monte Carlo + TD methods
   • Model-based value learning with reward models
   • Outcome-conditioned value estimation

4.7 Extension to Agentic RL and Model-Based Methods

Note on Reasoning RL: Our analysis focused on autoregressive token generation where transitions are deterministic and known (token concatenation). However, for agentic RL settings where language models interact with external environments (e.g., tool use, code execution, web browsing), the picture changes significantly.

Model-Based RL in Agentic Settings:

When transitions are not deterministic or known:

• Learning Signal: $\{S_t = (s_{t+1}, r_t)\}_{t=0}^{T-1}$ now contains information about both dynamics and rewards
• Potential Bandwidth: $O(T \log |\mathcal{S}|)$ bits per episode (observing next states provides $\log |\mathcal{S}|$ bits each step)
• Effective Bandwidth: Can be much higher than actor-critic when dynamics are unknown

Key Distinction:

• Token-level MDP (this analysis): Transitions known → model-based ≈ actor-critic
• Agentic RL: Transitions unknown → model-based has information advantage

Information Allocation: In agentic settings, the agent may learn both:

1. $P(s' | s, a)$: Transition dynamics (how the environment responds)
2. $R_\xi(s)$: Reward function (what the user wants)

Model-based methods can learn both simultaneously, potentially achieving higher total information bandwidth. However, in pure reasoning RL (e.g., chain-of-thought, internal planning), transitions remain deterministic and our analysis applies directly.

Appendix: Scope and Limitations

What this analysis rigorously establishes:

1. ✅ Policy gradient uses scalar signals with $O(1)$ bit capacity per episode
2. ✅ Actor-critic uses token-level signals with $O(T)$ bit capacity per episode
3. ✅ The qualitative conclusion: dense signals provide $T\times$ more information bandwidth
4. ✅ LoRA’s storage capacity vastly exceeds information provided by policy gradient

What requires additional assumptions:

1. ⚠️ Exact sample complexity bounds (requires analysis of optimization dynamics)
2. ⚠️ Linear accumulation of information (assumes limited redundancy across episodes)
3. ⚠️ Actor-critic achieving $O(T)$ bandwidth (requires well-trained critic)
4. ⚠️ Reward distinguishability (assumes $O(1)$ effective precision)

What remains qualitative:

1. 📊 Specific constants (exact bits per distinguishable reward level)
2. 📊 Saturation dynamics (when marginal information gain decreases)
3. 📊 Relationship between storage bits and representational capacity in neural networks

Perspective: This analysis provides an information-theoretic lens for understanding RL efficiency in LLM fine-tuning. The mathematical framework is rigorous, but translating information-theoretic bounds to concrete sample complexity requires additional assumptions about optimization and learning dynamics. The value lies in the qualitative insights and order-of-magnitude comparisons, which align well with empirical observations and provide intuition for why certain methods work.

Further Reading

• Russo & Van Roy (2014), “Learning to Optimize via Information-Directed Sampling”
• Ouyang et al. (2022), “Training language models to follow instructions with human feedback” (InstructGPT)
• Hu et al. (2021), “LoRA: Low-Rank Adaptation of Large Language Models”
• Cover & Thomas (2006), “Elements of Information Theory”

Citation

If you found this post useful in your research, please consider citing it:

@article{li2025information,
  title   = {Information Bandwidth in Reinforcement Learning: Understanding Why Policy Gradient Learns 1 Bit Per Episode},
  author  = {Li, Yingru},
  journal = {Richard Li's Blog},
  year    = {2025},
  month   = {October},
  url     = {https://richardli.xyz/post/information-bandwidth-rl/}
}

Did you find this post helpful? Consider sharing it 🙌