Reinforcement Learning Foundations for LLM Alignment

Part 1 of 5: The Mathematical Foundations

Updated 31 Oct 2026: Added a notation section used across the series, the policy-gradient derivation, the exact optimal baseline, and a short importance-sampling section. Rewrote the on-/off-policy discussion. Fixed the transition probabilities in two tables, which rendered wrong. Clarified when the Monte Carlo advantage is unbiased, and added a stop-gradient to the A2C pseudocode. Series labels now count five parts.

TL;DR: Before understanding PPO, GRPO, or any modern LLM alignment algorithm, you need solid RL foundations. This article covers MDPs, policy gradients, the variance problem, value functions, Bellman equations, and advantage estimation—all through the lens of language model fine-tuning. By the end, you’ll understand why these algorithms are designed the way they are.

Reading time: ~35 minutes

Why RL for Language Models?

You’ve trained a language model on terabytes of text. It can complete sentences, answer questions, even write code. But it also happily generates harmful content, confidently states falsehoods, and ignores user preferences. Supervised fine-tuning on curated examples helps, but you can’t enumerate every possible good response.

What you need is a way to optimize for “goodness” directly—to tell the model “responses like this are better than responses like that” and have it learn the pattern. This is exactly what reinforcement learning provides.

The insight behind RLHF (Reinforcement Learning from Human Feedback) is powerful: instead of showing the model correct outputs, we show it a reward signal indicating how good its outputs are. The model then learns to maximize this reward.

But RL for LLMs isn’t straightforward. The action space is enormous (vocabulary size per token), episodes are variable length, rewards are sparse (often only at generation end), and we need stable training for billion-parameter models.

Understanding the foundations deeply will help you see why algorithms like PPO and GRPO make specific design choices—and when those choices might not be right for your problem.

Table of Contents

1. Notation
2. The MDP Framework
3. Policies and the Objective
4. Policy Gradients: Learning Without a Model
5. The Variance Problem
6. Value Functions and Bellman Equations
7. Advantage Functions: The Key Insight
8. Actor-Critic Methods
9. From General RL to LLM Fine-Tuning
10. Key Takeaways

Notation

The same symbols are used in all five parts of the series. Later parts link back here.

The MDP Framework

Reinforcement learning formalizes sequential decision-making through Markov Decision Processes (MDPs). Understanding this framework precisely will help you see how LLM generation maps onto RL concepts.

Definition

An MDP is defined by the tuple $(\mathcal{S}, \mathcal{A}, P, R, \gamma)$:

The Markov Property

The “Markov” in MDP refers to the Markov property: the future depends only on the current state, not on how we got there.

This is crucial for tractability—we don’t need to remember the entire history, just the current state.

The Agent-Environment Loop

At each timestep $t$:

1. Agent observes state $s_t$
2. Agent selects action $a_t$ according to its policy
3. Environment transitions to $s_{t+1} \sim P(\cdot | s_t, a_t)$
4. Agent receives reward $r_t = R(s_t, a_t, s_{t+1})$
5. Repeat until terminal state or horizon

LLM Generation as an MDP

For language model fine-tuning, we can map concepts as follows:

The state space is enormous (all possible token sequences up to context length), and the action space is the vocabulary size (typically 32K-128K tokens). This scale motivates many of the algorithmic choices we’ll see.

Key Insight: The Markov property technically holds for LLM generation—the next token distribution depends only on the current sequence, not on how we generated it. However, the state itself encodes the full history, so we’re not actually discarding information.

Policies and the Objective

What is a Policy?

A policy $\pi$ maps states to actions. It can be:

• Deterministic: $a = \pi(s)$ — always the same action in state $s$
• Stochastic: $a \sim \pi(a|s)$ — a probability distribution over actions

For LLMs, the policy is inherently stochastic: $\pi_\theta(o_t | s_t) = \pi_\theta(o_t | q, o_{<t})$ is the probability of token $o_t$ given the context. The parameters $\theta$ are the model weights.

The Return

The return $G_t$ is the cumulative (discounted) reward from time $t$ onwards:

The discount factor $\gamma$ serves multiple purposes:

• Mathematical: Ensures the sum converges for infinite horizons
• Practical: Encodes preference for immediate vs. delayed rewards
• LLM setting: Often $\gamma = 1$ since episodes are finite

The RL Objective

The goal of RL is to find a policy that maximizes expected return:

where $\tau = (s_0, a_0, r_0, s_1, a_1, r_1, \ldots)$ is a trajectory sampled by following policy $\pi_\theta$.

The expectation is over:

• Initial state distribution $s_0 \sim \rho_0$
• Actions from policy $a_t \sim \pi_\theta(a|s_t)$
• Transitions from dynamics $s_{t+1} \sim P(s'|s_t, a_t)$

For LLMs Specifically

In the LLM setting, the objective simplifies to:

where:

• $q$ is a prompt from the prompt distribution $P(Q)$
• $o = (o_1, \ldots, o_T)$ is a complete response sampled from the model
• $R(q, o)$ is the reward (from a reward model, or a programmatic verifier)

With sparse rewards (only at episode end), there’s no discounting to worry about within an episode.

There is a consequence worth noticing now. With $\gamma = 1$ and a single terminal reward, the reward-to-go is the same for every token: $G_t = R(q, o)$ for all $t$. Every token in a response gets identical credit. That is where GRPO’s uniform per-response advantage in Part 3 comes from.

Policy Gradients: Learning Without a Model

How do we optimize $J(\theta)$? We can’t compute it analytically—it requires integrating over all possible trajectories. But we can estimate its gradient and use gradient ascent.

The Policy Gradient Theorem

The policy gradient theorem (Sutton et al., 1999) provides a remarkable result: we can estimate $\nabla_\theta J(\theta)$ using only samples, without knowing the transition dynamics $P$.

We don’t know $Q^{\pi_\theta}$, but we can sample it. The reward-to-go $G_t$ has expectation $Q^{\pi_\theta}(s_t, a_t)$ given $(s_t, a_t)$, so it is an unbiased stand-in. And only rewards from $t$ onwards belong in the weight: an action can’t affect rewards that came before it, so those terms have zero expectation and drop out. That gives the form we actually compute:

Let’s unpack this:

• $\nabla_\theta \log \pi_\theta(a_t|s_t)$ is the score function—the direction that increases the probability of action $a_t$
• $G_t$ is the return from time $t$—how good the outcome was
• The product says: “increase probability of actions that led to high returns”

Intuition: Credit Assignment

The gradient has an elegant interpretation:

1. Sample a trajectory by running the policy
2. For each action taken, compute how much total reward followed
3. If reward was high, increase that action’s probability
4. If reward was low, decrease that action’s probability

This is the core of policy gradient methods: reinforce good actions, discourage bad ones.

The REINFORCE Algorithm

The simplest policy gradient algorithm is REINFORCE (Williams, 1992):

Algorithm: REINFORCE

For each episode:
    1. Sample trajectory τ = (s₀, a₀, r₀, ..., s_T, a_T, r_T) using π_θ
    
    2. For t = 0 to T:
        Compute return: G_t = Σₖ γᵏ r_{t+k}
    
    3. Compute gradient estimate:
        ∇̂ = Σₜ ∇_θ log π_θ(aₜ|sₜ) · Gₜ
    
    4. Update: θ ← θ + α∇̂

Why This Works: The Log-Derivative Trick

The derivation uses the log-derivative trick:

This converts a gradient of a probability into an expectation we can sample:

For whole trajectories, apply the same trick to the trajectory probability $p_\theta(\tau)$, then expand its log:

The initial-state term $\rho_0$ and the dynamics term $P$ don’t depend on $\theta$, so their gradients are zero and they drop out. Only the policy’s own log-probabilities remain. That last line is the whole reason no model of $P$ is needed.

Key Insight: Policy gradients are model-free—we don’t need to know $P(s'|s,a)$. We only need to sample from the environment and observe rewards. This is crucial for LLMs where the “environment” is just string concatenation.

The Variance Problem

REINFORCE is elegant but has a critical flaw: high variance. The gradient estimates are so noisy that learning is impractically slow.

Sources of Variance

Consider what affects the gradient estimate $\nabla_\theta \log \pi_\theta(a_t|s_t) \cdot G_t$:

1. Stochastic policy: Different action samples give different gradients
2. Stochastic transitions: Same action can lead to different states
3. Long horizons: $G_t$ includes all future rewards, accumulating randomness
4. Sparse rewards: Most of the signal comes from rare events

A Concrete Example

Suppose you’re training an LLM to solve math problems. The reward is +1 for correct, 0 for incorrect.

Episode 1: Model generates a correct solution. Every token gets gradient proportional to +1.

Episode 2: Model generates an incorrect solution. Every token gets gradient proportional to 0.

Problem 1 — failures teach nothing. With 0/1 rewards and no baseline, every wrong answer gives exactly zero gradient. The model never learns from its failures, only from its successes. A baseline turns them into negative signal: subtract the current success rate, say $b = 0.3$, and a wrong answer now carries $0 - 0.3 = -0.3$, which pushes its tokens down.

Problem 2 — credit is smeared. In episode 1, all tokens get positive reinforcement—including lucky guesses, unnecessary steps, and tokens that happened to work but weren’t essential. The gradient doesn’t distinguish “this token was crucial” from “this token was irrelevant.”

Variance Reduction with Baselines

A key insight: we can subtract any baseline $b(s_t)$ that doesn’t depend on actions without changing the expected gradient:

Why doesn’t this change the expectation?

The baseline can be anything that doesn’t depend on the action—but choosing it well dramatically reduces variance.

Optimal Baseline

Every action-independent baseline leaves the gradient unbiased; they differ only in variance. The baseline that actually minimizes variance (per state, for a single-step estimator) is a weighted average of the return:

Returns from actions with large score-function norms count more. Nobody computes this in practice. Drop the weights and you get the practical approximation, the expected return from state $s_t$:

This is the value function, which we’ll explore next. It is near-optimal and learnable, not the exact minimizer.

Intuition: Relative Performance

With a good baseline, the gradient update becomes:

This says:

• If $G_t > V(s_t)$: Action was better than expected → increase probability
• If $G_t < V(s_t)$: Action was worse than expected → decrease probability
• If $G_t = V(s_t)$: Action was exactly as expected → no change

This relative signal is far more informative than absolute returns.

Key Insight: The baseline transforms absolute returns into relative performance measures. This is the foundation of advantage-based methods—and explains why GRPO’s group normalization works.

Value Functions and Bellman Equations

To use $V(s)$ as a baseline, we need to estimate it. Value functions are central to RL and worth understanding deeply.

State Value Function

The state value function $V^\pi(s)$ is the expected return starting from state $s$ and following policy $\pi$:

This answers: “How good is it to be in state $s$?”

Action Value Function

The action value function (or Q-function) $Q^\pi(s, a)$ is the expected return starting from state $s$, taking action $a$, then following policy $\pi$:

This answers: “How good is it to take action $a$ in state $s$?”

Relationship Between V and Q

The value function is the expected Q-value under the policy:

The Bellman Equation

Value functions satisfy a recursive relationship called the Bellman equation:

This says: “The value of a state equals the expected immediate reward plus the discounted value of the next state.”

For Q-functions:

Why Bellman Equations Matter

The Bellman equation enables bootstrapping: we can estimate $V(s)$ using our current estimate of $V(s')$, without waiting for the episode to end.

Monte Carlo: Wait for episode end, compute $G_t = \sum_k \gamma^k r_{t+k}$, update $V(s_t) \leftarrow V(s_t) + \alpha(G_t - V(s_t))$

Temporal Difference (TD): After one step, update using $V(s_t) \leftarrow V(s_t) + \alpha(r_t + \gamma V(s_{t+1}) - V(s_t))$

TD learning has lower variance (one-step update vs. full episode) but introduces bias (using an estimate $V(s_{t+1})$ instead of the true expected return).

TD Error

The TD error is the difference between our estimate and the bootstrapped target:

If our value function is accurate, $\mathbb{E}[\delta_t] = 0$. The TD error measures how “surprised” we are by what happened.

Key Insight: Bellman equations let us learn value functions incrementally, updating after each step rather than waiting for episodes to complete. In principle this is valuable for long episodes like LLM generation. In practice, with a terminal-only reward, $V$ at intermediate tokens is hard to learn: every target is bootstrapped from another estimate until the last token. That is why Part 2 recommends a high GAE $\lambda$, which leans on observed returns more than on $V$.

Advantage Functions: The Key Insight

The advantage function combines V and Q to measure how much better an action is than average:

Interpretation

• $A(s, a) > 0$: Action $a$ is better than the average action in state $s$
• $A(s, a) < 0$: Action $a$ is worse than average
• $A(s, a) = 0$: Action $a$ is exactly average

The advantage answers the crucial question: “Is this action better or worse than what I’d typically do?”

Why Advantages for Policy Gradients?

Using advantages in the policy gradient gives:

This is a good choice for variance reduction, though not a provably optimal one:

1. Advantages are centred by construction, $\mathbb{E}_a[A(s, a)] = 0$, so they act as a baseline-corrected signal. The baseline is $V$, which is near-optimal (see above), not the exact minimizer.
2. The signal focuses on relative action quality
3. It separates “was the action good?” from “was the state good?”

Estimating Advantages

We rarely know $A^\pi$ exactly. Common estimators:

1. Monte Carlo Advantage: $\hat{A}_t = G_t - V(s_t)$ Use actual returns minus estimated value. In the policy gradient this gives an unbiased gradient for any $V$, because a baseline never adds bias. As an estimate of $A^\pi$ itself, it is unbiased only when $V = V^\pi$. High variance either way.

2. TD Advantage: $\hat{A}_t = r_t + \gamma V(s_{t+1}) - V(s_t) = \delta_t$ One-step TD error. Low variance but biased.

3. Generalized Advantage Estimation (GAE): $\hat{A}_t^{\text{GAE}(\gamma, \lambda)} = \sum_{k=0}^{\infty} (\gamma\lambda)^k \delta_{t+k}$ Interpolates between MC ($\lambda=1$) and TD ($\lambda=0$). We’ll explore GAE deeply in Part 2.

Properties of Good Advantage Estimators

There’s typically a bias-variance tradeoff: lower variance estimators introduce more bias (by relying on learned value functions).

Key Insight: The advantage function is the “right” quantity for policy gradients. It tells us exactly what we want to know: was this action better or worse than average? All modern policy optimization methods (PPO, GRPO, etc.) are fundamentally about estimating advantages well.

Actor-Critic Methods

Actor-critic methods combine policy gradients (the “actor”) with learned value functions (the “critic”). This architecture underlies PPO and most modern RL algorithms.

The Two Components

Actor: The policy $\pi_\theta(a|s)$ that selects actions

• Parametrized by $\theta$
• Optimized via policy gradients
• Goal: maximize expected return

Critic: The value function $V_\psi(s)$ or $Q_\psi(s, a)$

• Parametrized by $\psi$
• Optimized via Bellman equation (TD learning)
• Goal: accurately estimate expected returns

Why Two Networks?

Each component benefits the other:

1. Critic helps actor: Provides baseline/advantage estimates for lower-variance policy gradients
2. Actor helps critic: Generates on-policy data for value function training

The A2C Algorithm

Advantage Actor-Critic (A2C) is a foundational actor-critic algorithm:

Algorithm: A2C

For each batch of experience:
    1. Collect trajectories using current policy π_θ
    
    2. Compute advantages:
        For each timestep t:
            δ_t = r_t + γV_ψ(s_{t+1}) - V_ψ(s_t)  # TD error
            (Or use GAE for multi-step advantages)
    
    3. Update critic (minimize value loss):
        L_critic = Σ_t (V_ψ(s_t) - G_t)²  # Or TD targets
        ψ ← ψ - α_critic ∇_ψ L_critic
    
    4. Update actor (maximize policy objective):
        L_actor = Σ_t log π_θ(a_t|s_t) · stop_grad(Â_t)   # Â_t.detach() in PyTorch
        θ ← θ + α_actor ∇_θ L_actor
        # Â_t is a fixed weight here. Without the stop-gradient, the actor
        # loss would also backpropagate into the critic through V_ψ.

On-Policy vs. Off-Policy

On-policy methods (A2C, PPO, GRPO) learn from data sampled by the current policy, or one very close to it:

• Samples from $\pi_\theta$ are used to update $\pi_\theta$
• Data goes stale as the policy moves, and is discarded after a few updates
• PPO and GRPO stretch each batch over several gradient steps, correcting for the small drift with importance ratios (next section)

Off-policy methods like DQN and SAC learn from a replay buffer of data collected by older policies. They learn a Q-function from bootstrapped targets, so they need no importance weights. Policy-gradient methods are different: their gradient is an expectation under the current policy, so they correct for slightly stale data with importance ratios — the tool Part 2 builds on.

LLM fine-tuning uses on-policy methods mainly for stability: policy-gradient estimates assume data from (close to) the current policy, and stale samples bias the update. Generation is the most expensive step, which is why PPO reuses each batch for several epochs with importance ratios rather than throwing it away after one step.

Importance Sampling: Reusing a Batch

Suppose a batch was sampled by $\pi_{\theta_{\text{old}}}$, and we have since taken a gradient step, so we now want the gradient under $\pi_\theta$. Importance sampling rewrites an expectation under one distribution as an expectation under another:

The ratio $\rho = \pi_\theta / \pi_{\theta_{\text{old}}}$ reweights old samples so they count as if the current policy had drawn them. That is what lets PPO take several gradient steps on one batch of generations.

The catch: as $\pi_\theta$ drifts from $\pi_{\theta_{\text{old}}}$, the ratios spread out and the estimate’s variance grows. Per-token ratios also ignore that the states visited would change too. Both are reasons to keep $\rho$ near 1, and Part 2’s clipped objective is one way to do that.

Challenges in Actor-Critic

1. Training instability: Actor and critic must improve together; if one diverges, both fail
2. Sample efficiency: On-policy methods need fresh samples after each update
3. Hyperparameter sensitivity: Learning rates, advantage estimation, entropy bonuses all interact
4. Scale: For LLMs, the critic is another massive network to train

Key Insight: Actor-critic methods are powerful but complex. The critic provides essential variance reduction, but at the cost of a second model (for LLMs usually the same size as the policy, though it can be smaller) and potential instability. This motivates GRPO’s approach of eliminating the critic entirely.

From General RL to LLM Fine-Tuning

Let’s map everything we’ve learned to the specific setting of language model alignment.

The LLM-RL Correspondence

Unique Challenges for LLMs

1. Enormous Action Space

Vocabulary sizes of 32K-128K tokens mean:

• Can’t enumerate all actions
• Must use function approximation (the LLM itself)
• Exploration is implicit in stochastic sampling

2. Sparse Rewards

Typically, reward comes only at generation end:

• $r_t = 0$ for $t < T$
• $r_T = R(q, o)$ — the reward model score

This makes credit assignment hard: which tokens were responsible for the reward?

3. Variable-Length Episodes

Generations can be 10 tokens or 1000 tokens:

• Can’t use fixed-horizon methods
• Must handle EOS token properly
• Padding and masking complexities

4. The Reference Model Constraint

Unlike standard RL, we don’t want to maximize reward unconditionally. We want to improve while staying close to a reference model:

This prevents:

• Reward hacking: Finding exploits in the reward model
• Mode collapse: Generating the same high-reward response always
• Capability loss: Forgetting useful behaviors from pretraining

5. Scale

Training billion-parameter models requires:

• Massive memory for model weights, gradients, optimizer states
• Distributed training across many GPUs
• Careful numerical stability

The RLHF Pipeline

The reward doesn’t have to be a learned model. For maths and code it is often a programmatic verifier: check the final answer, run the unit tests. This is RL with verifiable rewards (RLVR), and Parts 3 and 5 lean on it.

What’s Coming Next

With these foundations, we’re ready to understand PPO (Part 2):

• How clipping provides stable updates
• How GAE estimates advantages
• Why it requires four models
• And why that’s a problem

Then GRPO (Part 3) will show how to eliminate the critic by clever use of group statistics.

Then GDPO (Part 4) will address multi-reward settings where GRPO falls short.

Finally, the GRPO family map (Part 5) lays out the handful of design axes that DAPO, Dr. GRPO, GSPO and the rest vary along.

Key Takeaways

The MDP Framework

• RL formalizes sequential decisions as states, actions, rewards
• Markov property: future depends only on current state
• LLM generation maps naturally to this framework

Policy Gradients

• We can optimize expected reward using gradient ascent
• The policy gradient theorem enables learning without knowing dynamics
• REINFORCE is simple but high-variance

The Variance Problem

• Raw policy gradients are too noisy for practical use
• Baselines reduce variance without changing expected gradient
• The value function is a near-optimal, practical baseline (the exact minimizer weights returns by score-function norm)

Value Functions

• $V(s)$ = expected return from state $s$
• $Q(s,a)$ = expected return from state $s$ taking action $a$
• Bellman equations enable bootstrapped learning

Advantage Functions

• $A(s,a) = Q(s,a) - V(s)$ measures relative action quality
• Advantages are centered: $\mathbb{E}_a[A(s,a)] = 0$
• This is the key quantity for policy optimization

Actor-Critic

• Actor (policy) + Critic (value function) work together
• Critic provides variance reduction for actor updates
• Adds a second model, usually the same size as the policy for LLMs, though it can be smaller

LLM-Specific Considerations

• Sparse rewards make credit assignment hard
• Reference model constraint prevents reward hacking
• Scale demands memory-efficient algorithms

What’s Next

In Part 2: PPO for Language Models, we’ll see how Proximal Policy Optimization addresses many challenges:

• Trust regions for stable updates
• GAE for flexible advantage estimation
• Clipping for simplicity

But we’ll also see PPO’s costs: the four-model architecture that strains GPU memory, and the complexity that makes implementation tricky. This sets the stage for GRPO’s elegant simplification.

Exercises

All three fit in one script on a toy problem: a 10-armed bandit with Bernoulli rewards and a softmax policy. Run each for a few hundred steps, and at a fixed policy, estimate the gradient from many independent batches and plot its variance.

1. REINFORCE. Implement the plain estimator $\nabla \log \pi(a) \cdot r$. Note how often the gradient is exactly zero when rewards are 0/1.
2. REINFORCE with a baseline. Subtract a running mean of the reward. The gradient’s expectation should not change; its variance should drop.
3. Actor-critic. Make it a short-horizon MDP (say, three steps), learn $V_\psi$ with TD, and use $r_t + \gamma V_\psi(s_{t+1}) - V_\psi(s_t)$ as the advantage, detached. Compare variance and bias against the first two.

Further Reading

Courses and tutorials:

• OpenAI Spinning Up: Intro to Policy Optimization — the policy-gradient derivation, step by step
• Sergey Levine, CS285 Deep Reinforcement Learning — the policy-gradient and actor-critic lectures

Foundational Papers:

• Policy Gradient Methods for Reinforcement Learning with Function Approximation (Sutton et al., 1999)
• Simple Statistical Gradient-Following Algorithms for Connectionist Reinforcement Learning (Williams, 1992 — REINFORCE)

Textbooks:

• Reinforcement Learning: An Introduction (Sutton & Barto, 2018) — The definitive reference
• Deep Reinforcement Learning (Foundations and Trends survey)

LLM-Specific:

• Training language models to follow instructions with human feedback (InstructGPT, Ouyang et al., 2022)
• Learning to summarize from human feedback (Stiennon et al., 2020)

@misc{sousa2026rlfoundations,
  title={{Reinforcement Learning Foundations for LLM Alignment}},
  author={Sousa, Vitor},
  year={2026},
  howpublished={\url{https://www.vitorsousa.com/blog/rl-foundations/}},
  url={https://www.vitorsousa.com/blog/rl-foundations/}
}