Notes

RL Bottoms Up

CS336 Lectures 15-17, OpenAI spinningup, relevant papers.

Terminology

A few of these will differ in meaning between general RL and Language Model RL.

  • Reward: a scalar signal from a single step
    • This is kinda simple to obtain from your environment, from an interaction, from another model, a heuristic, etc.
      • If you kill a monster, +10 points; a teammate, -20 points.
      • Passed the test cases (code)
      • Output with certain formatting
    • They can be defined however we want, deterministically, with an LM Judge, with a Reward Model.
  • Return: how good a trajectory τ\tau was, considering all the reward obtained from step t.
    • *LM RL = Reward almost always means the same as Return, and no one really uses the word “Return”
  • Expected Return: The average return to expect; definition of Expectation Math
    • In RL, you can’t easily predict the future rewards from a state.
  • at,sta_t, s_t = action at step t, state at step t
  • State = in general, RL comes from a snapshot of the environment; for LMs, it could refer to the tokens produced so far.
  • (at∣sta_t | s_t) = likelihood of an action at t, given state t, conditional probability
  • ∇θ\nabla_\theta = Parameter gradients
  • τ\tau = trajectory, the steps taken so far
  • Policy π\pi: Desired behavior for the model at∼π(⋅∣st).a_t \sim \pi(\cdot | s_t).,
    • This term is used in multiple confusing ways; it is good to differentiate between general RL and LLM RL
      • In general RL, the policy is the decision: when I see state s, take action a, so it is not the whole Agent itself, but part of the agent
      • In LM RL, the word “ agent “ is barely used, and usually the policy refers to the model itself. Also referred to as the Policy Model.
    • θ\theta: the policy/model parameters ≈ πθ\pi_\theta
  • Expected return: J(π)=∫τP(τ∣π)R(τ)=Eτ∼π[R(τ)].J(\pi) = \int_{\tau} P(\tau|\pi) R(\tau) = E_{\tau\sim \pi}[{R(\tau)}].
    • ∫\int is for a continuous space; on a discrete space, it would be ∑\sum
    • Expectation: R(τ)R({\tau}) is weighted by the probability of τ\tau given your current policy π\pi

Thus, the RL goal is to make a policy that maximizes the expected return of an agent when interacting with an environment. It can be written as π∗=arg⁡max⁡πJ(π)\pi^* = \arg\max_\pi J(\pi) ≈ find policy π, that maximizes the expected return JJ

  • Monte Carlo method = Estimate something by averaging over many random samples. Simulate and average. In RL: simulate a total future reward by sampling many times and taking averages.
  • Online RL: generate samples from your policy, get a reward, and move the weights
  • Offline RL: collect samples + rewards over steps > 1, and then fine-tune.
  • Surrogate Loss: Loss as a heuristic to move the gradients; in RL, the loss doesn't mean anything by itself, compared to pre-training, for example.

Value Functions

In RL (in most cases, e.g., PPO, not GRPO), you need to estimate the Expected Return for a state, or for a state-action pair; to do this, we use 2 types of value functions.

  • Notation:
    • * = optimal, π = policy
    • V = refers to a value function that relies only on state, Q = uses state+action pairs.
  • Vπ(s)V^{\pi}(s) = Expected Return, at state s, and after acting according to π.
  • Qπ(s,a)Q^{\pi}(s, a) = Expected Return, at state s, taking action a (which might not have come from π), after acting according to π
  • Optimal
    • V∗(s)V^*(s) = Expected return, at state s, and always act according to optimal π in env.
    • Q∗(s,a)Q^{*}(s, a) = Expected return, at state s, take action a, and then always act according to optimal π in env.

Creating a Value Function

Remember these are estimators, not true values. We can create these in 2 different ways:

  1. Direct Monte Carlo sampling

    • Getting a bunch of trajectories and computing the rewards backward.
      • High variance = each τ\tau can give different returns due to stochasticity; rewards come much later than the action as well. We do rollouts first, then rewards; hard to attribute credit properly.
      • Unbiased cause it's a true value, not an estimate
    • GtG_t , Gt=∑t’=tTγt’−trt’G_t = \sum_{t’=t}^T \gamma^{t’-t} r_{t’}: In general, when we see GtG_t, we are referring to Q(s,a)Q(s, a), but GtG_t is an approximation to the true expected return we can't observe (Q), but notations usually interchange them
  2. Using the Monte Carlo rollouts to train a neural network as an estimator Vϕ(st)V_\phi(s_t) using MSE min⁡ϕ∑t(Vϕ(st)−Gt)2\min_\phi \sum_t \left( V_\phi(s_t) - G_t \right)^2

    • Predictions will fluctuate less than individual rollout returns, but have approximation errors.
    • As the policy improves, the Expected Return from a state changes; thus, the critic must keep training
  • Bias-Variance tradeoff = statistical estimation of a true quantity (e.g. gradient, return, value func), can be wrong in 2 ways

    • Bias: avg estimate is far from the truth
    • Variance: random error, variation across samples
    • You can reduce one at the cost of the other
  • Bootstrapping:

    • Using an estimate as the learning objective of another model. Relates to the 2nd way of creating Value functions. GAE is an example of this.
    • Some people use this term to refer to RL self-training.
    • Discounts: when we estimate future rewards after taking a step, this generally has a multiplier in [0, 1), which means we take less relevance from a step farther in the future.

For general RL, we have 2 methods for optimizing policies: gradient-based and non-gradient-based; for LM RL, we’ll focus only on gradient-based ones.

Building RL Bottoms Up

1. REINFORCE / Vanilla,1992

∇θJ(θ)=Et[∇θlog⁡πθ(at∣st)⋅Gt]\nabla_\theta J(\theta) = \mathbb{E}_t\left[ \nabla_\theta \log \pi_\theta(a_t | s_t) \cdot G_t \right] = The objective is to find the gradient ∇θ\nabla_\theta of J(θ)J(\theta) in the direction that increases the Expected return.

Let’s say you have nn prompts, and for prompt_0, you sample and get 100100 tokens that receive a return of Gt=1.0G_t= 1.0. You’d get the logproblogprob of every token selected in that rollout, compute the gradient, multiply it by GtG_t, and then average these gradients.

Using GtG_t has 3 issues:

  1. Each token is equally weighted, as we only have our rollout return. (high variance)
  2. 0 returns don’t get pushed down
  3. A bad sample that still gets a >= 0 reward will still be pushed up, and we want the opposite.

The solution is to use a baseline (Value function Type 2). The average expected return of all other actions that could've been taken at step t under the current policy. b(st)=Vπ(st)b(s_t) = V^\pi(s_t)

After this fix, at every token, we use V(s)V_{(s)} to estimate the return at that token, which allows us at the end to weight each token separately. Once the rollout completes, we train V(s)V_{(s)}.

Thus, REINFORCE becomes ∇θJ(θ)=Et[∇θlog⁡πθ(at∣st)⋅At]\nabla_\theta J(\theta) = \mathbb{E}_t\left[ \nabla_\theta \log \pi_\theta(a_t | s_t) \cdot A_t \right], where A^t=Gt−b(st)\hat{A}_t = G_t - b(s_t). The advantage then means “how much better/worse action ata_t was when compared to other actions at sts_t on average”.

read more

2. TRPO, 2015

REINFORCE is not constrained. It can take large policy updates, so it’s still unstable even if we controlled for variance via the baseline trick. So in TRPO, we add a couple of things:

  1. An Importance Ratio: You want to get more signal per batch of prompts; thus, you take multiple steps instead of 1. But if you want to do that, you 1) save the per-sample token probabilities you got before the last update. 2) weight them against the current policy token probs. If the new policy likes a token more than the old one, that sample counts more.
  2. KL constraint to keep π changes from moving too far from the current π, keeping updates within a safe zone.

L(θ)=Et[πθ(at∣st)πθold(at∣st) A^t]L(\theta) = \mathbb{E}_t\left[\frac{\pi_\theta(a_t|s_t)}{\pi_{\theta_{old}}(a_t|s_t)}\,\hat A_t\right], under a KL constraint Et[KL(πθold(⋅∣st) ∥ πθ(⋅∣st))]≤δ\mathbb{E}_t\Big[\mathrm{KL}\big(\pi_{\theta_{old}}(\cdot|s_t)\,\|\,\pi_\theta(\cdot|s_t)\big)\Big] \le \delta

The KL has a few issues that result in second derivatives, which makes it very expensive. Fixed later by PPO.

3. Generalized Advantage Estimator (GAE), 2016

The idea is that if your Value Function V(s)V_{(s)} at token 40 has a 0.7 expected return, but at token 41 is 0.10.1, your TD error is −0.6-0.6, how do you weight these drops or sudden increases to weight a token correctly, which in theory controls bias variance with a lambda factor.

Before, the advantage was: A^t=Gt−V(st)\hat A_t = G_t - V(s_t). That's the real return minus the critic's guess. With GAE, it becomes a weighted sum of TD errors: A^t=∑l=0T−t(γλ)l δt+l,δt=rt+γV(st+1)−V(st)\hat A_t = \sum_{l=0}^{T-t} (\gamma\lambda)^l\,\delta_{t+l}, \qquad \delta_t = r_t + \gamma V(s_{t+1}) - V(s_t)

4. PPO, 2017

https://arxiv.org/pdf/1707.06347

How do you keep updates constrained without the KL constraint in TRPO, as it’s computationally expensive? PPO solves this with clipping or a KL penalty instead of a KL constraint.

LPPO(θ)=Et[min⁡(rt(θ) A^t, clip(rt(θ),1−ϵ,1+ϵ)⋅A^t)]L_{\text{PPO}}(\theta) = \mathbb{E}_t \left[ \min\left( r_t(\theta) \, \hat{A}_t, \ \text{clip}\big(r_t(\theta), 1 - \epsilon, 1 + \epsilon\big) \cdot \hat{A}_t \right) \right], where rt(θ)=πθ(at∣st)πθold(at∣st)r_t(\theta) = \frac{\pi_\theta(a_t|s_t)}{\pi_{\theta_{\text{old}}}(a_t|s_t)} = ratio (same as TRPO), where ϵ\epsilon = is a hyperparameter, usually 0.2. (if rt(θ)r_t(\theta) is between the clipping threshold 1−ϵ1-\epsilon, 1+ϵ1+\epsilon, it will behave the same as TRPO).

The alternative KL version: LPPO-KL(θ)=Et[rt(θ) A^t  −  β⋅KL ⁣[πold(⋅∣st) ∥ πθ(⋅∣st)]]L_{\text{PPO-KL}}(\theta) = \mathbb{E}_t \left[ r_t(\theta) \, \hat{A}_t \;-\; \beta \cdot \mathrm{KL}\!\left[ \pi_{\text{old}}(\cdot \mid s_t) \,\|\, \pi_{\theta}(\cdot \mid s_t) \right] \right], where β\beta is an hp controlling KL penalty; sometimes it’s a learned value.

Choosing KL vs Clipping?

5. RLHF 2020

Optimize for Human Preferences using RL. Summarize from Human Feedback (first RLHF paper), InstructGPT coined the term, first generalized attempt on preferences. Reinforcement Learning from Human Feedback and LLM Post-Training

State = tokens seen. Environment = context. Reward Model rewards, not the environment.

Relevant concept: Bradley-Terry Model

  • Probabilistic model for pairwise comparisons
  • How likely one item is preferred over another
  • P(A≻B)=eβAeβA+eβB=σ(βA−βB)P(A \succ B) = \frac{e^{\beta_A}}{e^{\beta_A} + e^{\beta_B}} = \sigma(\beta_A - \beta_B)
  • logistic function/sigmoid over the value of their scores, logit to probability
  • The sigmoid of the difference between two scores gives the probability that one option is chosen over the other.

5.1 Training a Reward Model

  1. Collect samples from πθ\pi_\theta. Take a prompt and sample nn outputs.

  2. Get humans to label pairs of these samples. Use pairwise comparisons: labels 1/0 indicate which output is best.

  3. Train the RMRM.

    Architecture

    • Take the SFT model and add a linear head that outputs a scalar—a single neuron.
    • Pass each sample individually through the model to get its scalar reward.
    • The binary preference data creates a model that outputs a scalar in [0,1][0,1], because binary results are not differentiable.

    Loss: Bradley–Terry pairwise comparisons

    • If sample aa is labeled 1 and sample bb is labeled 0, use -log(sigmoid(x)), where x=a−bx = a-b.
    • For the reverse preference, use x=b−ax = b-a.
    • sigmoid(x) represents the Bradley–Terry preference probability.
    • Minimizing -log(sigmoid(x)) performs maximum likelihood estimation (MLE). With binary preference labels, this becomes binary cross-entropy loss.
    • We use the negative log because deep learning frameworks minimize losses; minimizing negative log-likelihood maximizes likelihood.
    • Then we do backprop.
  4. Prepare the value head. This is again the same policy, but with a different MLP head that outputs a single scalar. We share the policy’s hidden parameters in real time and only update the value head here.

5.2 Optimizing via PPO

  • Input prompts, get responses, logprobs, compute rewards read more
  • Compute the advantages. Here we use our rollouts/completions GtG_t (returns), and with those we can train our V(t)V(t); we can do advantage with or without GAE
  • Compute the loss using PPO
  • Backprop gradients from the loss, backprop V(t)V(t) using MSELoss from GtG_t
  • repeat

The 37 Implementation Details of Proximal Policy Optimization · The ICLR Blog Track. Secrets of RLHF in Large Language Models. RewardBench.

6. DPO, 2022

Direct Preference Optimization. Paper: 2305. Video Explanation by: Umar Jamil. Make the preferred response more likely and the non-preferred one less likely. (Penalize the model if the preferred response doesn’t have significantly higher log-probability than the rejected one.)

Here because it builds on RLHF, but it’s not real RL: no value model, no RM; you can optimize π using pairwise comparisons, even with 1s and 0s; this isn’t differentiable (you can’t backprop through it) under the Bradley-Terry model. And this decision can be optimized using Maximum Likelihood Estimation (MLE Loss)

LDPO(θ)=−log⁡σ(β[Δlog⁡πθ−Δlog⁡πref])L_{\text{DPO}}(\theta) = -\log \sigma \left( \beta \left[ \Delta \log \pi_{\theta} - \Delta \log \pi_{\text{ref}} \right] \right), where Δlog⁡πθ=log⁡πθ(yw∣x)−log⁡πθ(yl∣x)\Delta \log \pi_{\theta} = \log \pi_{\theta}(y_w \mid x) - \log \pi_{\theta}(y_l \mid x) = logπθlog{π_\theta} is the log probability of given prompt x, the model outputs ywy_w = preferred, yly_l = not preferred. where β\beta is just a temperature scaling hyperparameter [0.1, 1.0], and πrefπ_{ref} is the frozen model before DPO training starts.

6.1 From DPO to PPO

(Derivation is not clear)

  • It seems that they found that the RM in PPO was using Bradley-Terry comparisons + MLE, and that this was learning to assign higher values to preferred responses
  • And the assumption was: The RM is just the log-likelihood ratio between the current policy and a frozen reference policy.
  • Plug that into Bradley-Terry, then into MLE, and done!
  • No online RL rollouts, no RM, offline supervised fine-tuning over pref data.

6.2 PPO vs DPO

Paper: 2406. Start with DPO; when it saturates, do RLHF and scale beyond labeled data. DPO is way easier and more stable. If you have many unlabeled prompts and want to train a reward model, consider RLHF unless you can pull the ops layer.

Comparison of PPO and DPO performance

6.3 DPO variants

SimPO and Length-Normalized DPO; check Tulu 3 for some ablations of this.

7. GRPO, 2024

DeepSeekMath. Group Relative Policy Optimization. GRPO = PPO with a simpler way to compute Advantage, no value model. What if, instead of using a V(t)V(t), we use a grouped relative reward? A^i=ri−mean(r)std(r)\hat{A}_i = \frac{r_i - \text{mean}(r)}{\text{std}(r)}. Everything else is the same as in PPO.

1G∑i=1G1∣oi∣∑t=1∣oi∣[min⁡(πθ(oi,t∣q,oi,<t)πθold(oi,t∣q,oi,<t) A^i,t, clip(πθ(oi,t∣q,oi,<t)πθold(oi,t∣q,oi,<t),1−ϵ,1+ϵ)A^i,t)−β DKL ⁣[πθ ∥ πref]]\frac{1}{G} \sum_{i=1}^{G} \frac{1}{|o_i|} \sum_{t=1}^{|o_i|} \left[ \min \left( \frac{\pi_\theta(o_{i,t} \mid q, o_{i,<t})}{\pi_{\theta_{\text{old}}}(o_{i,t} \mid q, o_{i,<t})} \, \hat{A}_{i,t}, \ \text{clip} \left( \frac{\pi_\theta(o_{i,t} \mid q, o_{i,<t})}{\pi_{\theta_{\text{old}}}(o_{i,t} \mid q, o_{i,<t})}, 1 - \epsilon, 1 + \epsilon \right) \hat{A}_{i,t} \right) - \beta \, D_{\text{KL}}\!\left[ \pi_\theta \,\|\, \pi_{\text{ref}} \right] \right]

Group relative policy optimization

Many variants have been created in the past 2 years that remove some terms, increase rollouts per group, filter them, use new constants, or clip differently, but the key idea of relative advantages via groups remains the same.

7.1 DR GRPO, 2025

Paper: 2503. Removed the division by std(r){\text{std}(r)}; when the std(r)std(r) is too small, you don’t want an exploded advantage (larger gradients). When is standard deviation small? When the problem is too easy or hard. It also removes division by the output length, so when problems are hard and models can’t solve them, they aren’t incentivized to output long texts to minimize the loss.

A custom implementation can be found in CS336 Assignment 05 and here

7.2 DAPO, 05/2025

Paper: 2503. Decoupled Clip and Dynamic sAmpling Policy Optimization (DAPO). JDAPO(θ)=E(q,a)∼D,{oi}i=1G∼πθold(⋅∣q)[1∑i=1G∣oi∣∑i=1G∑t=1∣oi∣min⁡(ri,t(θ)A^i,t, clip(ri,t(θ),1−ϵlow,1+ϵhigh)A^i,t)]\mathcal{J}_{\text{DAPO}}(\theta) = \mathbb{E}_{(q,a)\sim\mathcal{D}, \{o_i\}_{i=1}^G \sim \pi_{\theta_{\text{old}}}(\cdot|q)} \left[ \frac{1}{\sum_{i=1}^G |o_i|} \sum_{i=1}^G \sum_{t=1}^{|o_i|} \min\left( r_{i,t}(\theta)\hat{A}_{i,t}, \ \text{clip}\left(r_{i,t}(\theta), 1 - \epsilon_{\text{low}}, 1 + \epsilon_{\text{high}}\right) \hat{A}_{i,t} \right) \right] , where s.t.0<∣{oi ∣ is_equivalent(a,oi)}∣<G\text{s.t.} \quad 0 < \left| \left\{ o_i \ \big| \ \text{is\_equivalent}(a, o_i) \right\} \right| < G, and where, ri,t(θ)=πθ(oi,t∣q,oi,<t)πθold(oi,t∣q,oi,<t)r_{i,t}(\theta) = \frac{\pi_\theta(o_{i,t} \mid q, o_{i,<t})}{\pi_{\theta_{\text{old}}}(o_{i,t} \mid q, o_{i,<t})}, A^i,t=Ri−mean({Rj}j=1G)std({Rj}j=1G)\hat{A}_{i,t} = \frac{R_i - \text{mean}(\{R_j\}_{j=1}^G)}{\text{std}(\{R_j\}_{j=1}^G)}

It claims that GRPO suffers from entropy collapse, reward noise, and instability, so it adds the following changes:

  1. Clip higher = clipping ϵ\epsilon to 1 - 0.2 and 1 + 0.28. Suggests making the upper bound higher to allow for better exploration
  2. Dynamic Sampling = if all rollouts are correct, GRPO has a zero advantage, no gradient update, increased noise sensitivity, degrading sample efficiency. It suggests sampling more and filtering out prompts with accuracy equal to 1 or 0, and not training on them until there’s some signal. Restores the /std division.
  3. Token Level Policy Loss = contrary to 7.1 DR GRPO, longer responses should affect the gradient more, either positively or negatively. The overall loss should be computed per token, not avg per sample
  4. Overlong Reward Shaping = if rollouts get truncated, adds a reward penalty, and masks the loss for these samples.

DAPO training results

7.3 Other Methods

REINFORCE++ claims that because GRPO estimates advantages independently for responses to each prompt, which can lead to overfitting on simpler prompts and vulnerability to reward hacking and may be biased, it computes a batch advantage normalization z-score instead of per group of rollouts.

GSPO defines the importance ratio based on sequence likelihood and performs sequence-level clipping, rewarding, and optimization; adds MoE stability, restores length normalization

GFPO promotes shorter CoT and still allows for exploration of harder questions that require longer CoT. Over-samples and filters responses to train by 1) response length 2) token efficiency ≈ reward per token ratio, restores other terms, and changes normalization parameters.

LitePPO, …


FAQ and some Facts

  • The model learns during pre-training and a bit during SFT (CoT and style), not during RL. In RL, you are guiding the distribution: do this x instead of y (like the fact that in most cases you need SFT CoT tokens before RL, cause the CoT doesn’t exist if you do RL alone)
  • RL is very sample-inefficient to bootstrap; that’s why robotics only started working recently with pre-training.
  • As ridiculous as the case of random rewards still improving on Math.
  • Large batch sizes are generally needed; why?
  • RLVR = Reinforcement learning with verifiable rewards, asks “Can I get my reward from a deterministic setup?”
  • Reasoning vs Preference RL = If something is non-deterministic and you can’t create an LM judge for it (very unlikely), you’d be in a realm of preference data, and your training would look more like RLHF/PPO, but if you could verify it deterministically, you can teach preferences or even Instruction Following.
  • Rewards: they could be sparse and rare; if so, it will be hard to train on them. You need some signal, a minimal pass rate, to move the distribution in that direction.
  • Reward Models scaling laws. Generally used for preference data, cause RLHF is when we do PPO; if evaluating process/intermediary steps (Process Reward Models), they usually underperform.
  • Agentic RL = teaching JSON outputs/formatting, teaching tool calling to achieve a task. You could do PRMs, but no one does?
  • RL libraries: tinker/verl.
  • RL can be faster if you are doing LoRA, way way faster.
  • Some RL empirical intuition from 2508.
    • Group-level norm is robust across different reward settings.
    • Batch-level norm is best when rewards are large-scale, numerous, or high-variance, e.g., long-horizon summed rewards.
    • Removing std when it is close to 0 (meaning an easy or hard dataset) is better.
    • µ mean at local group level and std at batch/global is more robust; batch std is rarely tiny.
    • If the -base model has strong reasoning ability, clip higher to allow for better exploration.
    • DAPO clip higher ϵ=0.28\epsilon=0.28 value is optimal. And smaller models <= 4B in this case benefit w/ higher e.g. 0.320.32.
    • Token-level loss is best on base models, with limited improvement on instruct; do token-level loss.
    • Overlong filtering helps clarity in medium, short-length reasoning tasks, limited improvement on long-tail reasoning.
  • RLs razor
    • The degree of catastrophic forgetting is determined by the KL divergence between the frozen policy and the policy after RL
    • On-policy RL biases towards minimizing KL divergence.
    • Degree of forgetting for a new task τ\tau : Ex∼τ[KL(π0 ∥ π)]\mathbb{E}_{x \sim \tau} \left[ \mathrm{KL} \left( \pi_0 \,\|\, \pi \right) \right], shuold log and minimize?
    • Reasons:
      • RL does sampling/groups, which means relative updates
      • RL does negative rewards, pushes prob distribution away from it.
        • SFT doesn't have this; could we add it?
      • ofc, on-policy > off-policy, cause you are always very close to the previous distribution.