LLM EngineeringHard

🎯 Reinforcement Learning Basics

MDPs, value functions, policy gradients, actor-critic, PPO, and the bridge to RLHF/GRPO for LLMs

Reinforcement Learning: From MDPs to RLHF

Reinforcement learning is the mathematical framework for an agent learning to act in an environment by trial and error, guided only by a scalar reward signal. Where supervised learning fits a function to labeled (x, y) pairs, RL learns a policy (a mapping from situations to actions) under the constraint that the agent's own actions determine the data it sees. Once obscure outside robotics and game-playing, RL became the engine behind ChatGPT (RLHF), AlphaGo, and the 2024-2025 reasoning revolution (DeepSeek-R1, o1, Claude with extended thinking).

The Markov Decision Process (MDP)

Every RL problem is formalized as an MDP, a 5-tuple (S, A, P, R, γ):

S: the set of states the agent can be in (board position in chess, joint angles of a robot, conversation context for an LLM)
A: the set of actions available (move a piece, apply torque, emit a token)
P(s' | s, a): transition dynamics, the probability of landing in s' after taking action a in state s
R(s, a) or R(s, a, s'): reward function, the scalar feedback signal
γ ∈ [0, 1): discount factor, how much to weight future vs immediate rewards

The Markov assumption: the future depends only on the current state, not the full history. This is rarely literally true (an LLM's "state" is just the context window, which loses old turns), but the MDP framing is the foundation regardless.

Episodic vs continuing tasks. Episodic tasks have a terminal state (a chess game ends; a robot task completes); continuing tasks run forever (a recommender, a thermostat). Discount factor γ matters more for continuing tasks; without γ < 1, infinite-horizon return diverges.

The agent's goal: maximize the expected discounted return G_t = Σ_{k=0}^∞ γ^k R_{t+k+1}.

Value Functions and the Bellman Equation

Two central objects:

State value V^π(s) = expected return starting in s and following policy π thereafter
Action value Q^π(s, a) = expected return after taking action a in state s, then following π

The Bellman equation is the recursive consistency relation that defines them:

V^π(s) = E_a~π [ R(s,a) + γ · E_{s'~P} [ V^π(s') ] ]

The optimal value functions V*, Q* satisfy the Bellman optimality equations (replace E_a with max_a). If you know Q*, you have the optimal policy: π*(s) = argmax_a Q*(s, a). Almost all of RL is some way of estimating Q*, V*, or π* without knowing P or R in closed form.

The classic way to see this is value iteration on a small gridworld: apply the Bellman optimality backup over and over and watch value spread outward from the goal, then read the optimal policy straight off the converged values.

Value iteration: how values fill a gridworld

Goal (+1)Pit (−1)WallCell shade = V(s); arrow = greedy action

The setup. An agent lives on a grid. One cell is the goal (+1), one is a pit (−1), and a wall blocks the middle. Each step costs a little (−0.04), so the agent wants the shortest safe path. At the start we only know the value of the two terminal cells — every empty cell is still blank (0). The task: figure out how good each cell is.

One Bellman backup. Value iteration sweeps every cell and sets V(s) ← max_a [ R + γ·V(s’) ]— the best action’s reward plus the discounted value of where it lands. After one sweep only the cells next to the goallight up: they’re the only ones that can already “see” a non-zero value to back up from.

Value propagates outward. Each further sweep lets cells back up the values their neighbours just learned, so the signal ripples out from the goal like a wavefront. Notice the cells around the pit stay low — routing through it costs you the −1, so their best achievable value is worse.

Convergence. Once a sweep barely changes any value, iteration has converged: V*is the true long-run value of every cell under optimal play. The gradient of shades now points steadily uphill toward the goal and away from the pit — the map of “how good is it to stand here.”

From values to a policy. The optimal policy falls straight out of V*: in each cell, take the action whose neighbour has the highest value — π*(s) = argmax_a Q*(s,a). The arrows trace safe paths to the goal that detour around both the wall and the pit. Knowing the values gives you the policy for free.

γ sets the horizon. Drop the discount to γ = 0.5 and distant reward barely registers: far-off cells fade toward zero because a goal many steps away is worth little today. The agent turns short-sighted. γ near 1 makes it far-sighted and patient — the single knob that decides how much the future counts.

Value-Based Methods

If you can learn Q*, you're done. Classical approaches:

Q-learning (Watkins, 1989): off-policy TD update Q(s,a) ← Q(s,a) + α [r + γ max_{a'} Q(s', a') − Q(s,a)]. Converges to Q* under mild conditions.
SARSA: on-policy variant that uses the action actually taken, not the max. More conservative; better when exploration carries real cost.
DQN (Mnih et al., 2013/2015): scale Q-learning to high-dim states (Atari pixels) with a deep neural Q-function plus two tricks, a replay buffer (decorrelate samples) and a target network (stabilize bootstrapping). The Atari breakthrough, superhuman play on dozens of games from raw pixels, kicked off the modern deep RL era.

Value-based methods struggle with continuous or high-dim action spaces (you can't enumerate max_a over real-valued robot torques) and learn deterministic policies, which can be brittle.

Policy Gradient Methods

Skip the value function: directly parameterize the policy π_θ(a | s) (a neural net) and follow the gradient of expected return with respect to θ. The policy gradient theorem gives:

∇_θ J(θ) = E_{s,a~π_θ} [ ∇_θ log π_θ(a|s) · Q^π(s,a) ]

REINFORCE (Williams, 1992) is the simplest instantiation: roll out an episode, weight each log-prob by the Monte Carlo return G_t from that step onward. Pure REINFORCE has notoriously high variance because returns sum noise over the whole trajectory.

Variance reduction with baselines. Subtract any state-dependent baseline b(s) from the return: the gradient remains unbiased but variance drops. The optimal baseline is V^π(s) itself, which leads naturally to actor-critic.

Actor-Critic

Combine the two families: a critic network estimates V (or Q), an actor network parameterizes π. Replace the Monte Carlo return with the advantage A(s,a) = Q(s,a) − V(s), how much better action a is than average. This dramatically reduces variance and enables online updates without waiting for episodes to finish. Generalized Advantage Estimation (GAE) smoothly interpolates between high-variance Monte Carlo and high-bias TD via a parameter λ ∈ [0, 1].

A2C/A3C (Mnih et al., 2016) demonstrated the modern actor-critic recipe at scale on Atari and Mujoco.

Trust-Region Methods: TRPO and PPO

Naive policy gradient ascent often catastrophically destroys the policy: a single bad step can collapse exploration and never recover. The fix is to constrain each update to stay near the old policy in KL divergence.

TRPO (Schulman et al., 2015) solves a constrained optimization: maximize the surrogate objective subject to KL(π_old || π_new) ≤ δ. Mathematically clean but requires conjugate gradient + line search per step, which is awkward to implement.

PPO (Schulman et al., 2017) replaces the hard KL constraint with a simple clipped surrogate:

L^CLIP(θ) = E [ min( r_t(θ) · A_t, clip(r_t(θ), 1−ε, 1+ε) · A_t ) ]

where r_t(θ) = π_θ(a_t|s_t) / π_old(a_t|s_t) is the importance ratio. The clip prevents the update from moving too far in either direction. PPO is dramatically simpler than TRPO, runs on standard SGD-style optimizers, and works well across continuous control, discrete games, and (most consequentially) language models. PPO became the default RL algorithm for InstructGPT, ChatGPT, and the entire first wave of RLHF.

How PPO's clip keeps updates in a trust region

Clipped surrogate vs importance ratio r (A = 1, ε = 0.2)

Unclipped r·AClipped surrogateTrust region [1−ε, 1+ε]Gradient = 0 (clipped)

The ratio r. PPO fine-tunes a policy one small step at a time. For a sampled action it forms the importance ratio r = π_new(a|s) / π_old(a|s)— how much the updated policy changed this action’s probability. At r = 1 nothing changed; above 1 the new policy likes the action more, below 1 less.

The unclipped objective r·A. Each ratio is weighted by the advantage A — how much better than average the action was. With A > 0 (a good action) the raw objective r·Ais the dashed line: it just keeps rising as r grows, so plain policy gradient would push the probability up without limit on a single lucky sample. That’s exactly the instability that wrecks naive updates.

Clipping a good action (A > 0). PPO caps the ratio to a trust region [1−ε, 1+ε] (green band). Once r passes 1+ε, the solid surrogate goes flat— the gradient drops to zero (red segment), so there’s no reward for shoving the probability even higher. One good sample can nudge the policy, not overhaul it.

Clipping a bad action (A < 0). Flip the advantage negative and the clip binds on the other side: as r drops below 1−ε the surrogate flattens again, so a single bad sample can’t collapse the action’s probability to zero. The trust region protects the policy in both directions.

Why the min(). The objective is min(r·A, clip(r,1−ε,1+ε)·A). The min makes the clip bite only in the direction that would over-update: it caps the upside for good actions and the downside for bad ones, but never stops the policy from correctinga move that went the wrong way. Below the band a good action still follows the live gradient — the clip isn’t a hard wall, it’s a one-sided brake.

ε is the leash length. Shrinking ε to 0.1 narrows the trust region, so the gradient dies sooner and each step is more conservative — this is PPO’s cheap, first-order stand-in for TRPO’s hard KL constraint, and why it became the default for RLHF. Drive it yourself in the playground →

Off-Policy vs On-Policy

On-policy (REINFORCE, A2C, PPO): updates the policy using data sampled from the current policy. Throws away data after each update (sample inefficient) but stable.
Off-policy (Q-learning, DQN, SAC): can reuse data from older policies via a replay buffer. Sample efficient but trickier to stabilize (importance sampling, distributional shift).

PPO is technically on-policy but does multiple epochs over the same batch, a pragmatic compromise.

Exploration vs Exploitation

The agent must try suboptimal actions to discover whether they're actually suboptimal. Classical strategies:

ε-greedy: with probability ε, take a random action; otherwise greedy. Simple, dumb, surprisingly competitive.
Entropy bonus: add β · H(π(·|s)) to the objective. Encourages stochastic policies, prevents premature collapse. Standard in PPO.
UCB (Upper Confidence Bound): pick actions optimistically via argmax_a [Q(s,a) + c · √(ln N(s) / N(s,a))]. Foundation of bandit theory and Monte Carlo Tree Search (AlphaGo).
Intrinsic motivation / curiosity: reward novelty (e.g., prediction error of a learned dynamics model) to explore in sparse-reward environments.

The multi-armed bandit is the cleanest sandbox for this tradeoff: several arms, unknown payoffs, and a fixed budget of pulls. Open the explore-vs-exploit playground to pit greedy, ε-greedy, and UCB against the same reward draws — greedy's regret climbs almost linearly once it commits to a lucky-looking arm, while ε-greedy and UCB bend toward flat because they keep checking.

Model-Based vs Model-Free

Model-free (everything above): learn V/Q/π directly from interaction, never explicitly model the environment.
Model-based: learn an approximate transition model P̂(s'|s,a) and plan with it (MuZero, Dreamer, MBPO). Far more sample-efficient when the model is accurate, but model errors compound during planning.

AlphaGo and AlphaZero combined a learned policy/value network with Monte Carlo Tree Search planning, a hybrid that beat the human world champion at Go in 2016, and re-derived superhuman chess and shogi from self-play alone in 2017.

Reward Hacking and Goodhart's Law

"When a measure becomes a target, it ceases to be a good measure." RL agents are pathologically literal optimizers: they will exploit any loophole in the reward function. Classic examples: a boat-racing agent that learns to loop endlessly collecting power-ups instead of finishing the race, a robot that learns to vibrate its sensor to maximize a "stand upright" reward, an LLM trained on thumbs-up that learns to be sycophantic rather than helpful.

This isn't an edge case. It is the default outcome whenever the proxy reward diverges from the true objective. Solutions: reward modeling from human comparisons (RLHF), constrained optimization (Constitutional AI), KL penalties against a reference policy (standard in all LLM RL), and verifiable rewards where possible (math problems either parse correctly or don't). The reward-hacking problem is the bridge from RL theory to AI alignment.

The Connection to LLMs

In 2017 PPO was just one of dozens of policy gradient variants. In 2022 InstructGPT and ChatGPT used PPO + a learned reward model to align GPT-3.5, and suddenly every frontier lab needed it. The standard recipe:

Pretrain an LLM on web text (next-token prediction).
Supervised fine-tune (SFT) on high-quality instruction-following demos.
Train a reward model R_φ on human-rated comparisons of model outputs.
Fine-tune the LLM with PPO against R_φ, plus a KL penalty against the SFT policy to prevent collapse, reward = R_φ(prompt, response) − β · KL(π_RL || π_SFT).

The "state" is the prompt + tokens-so-far; the "action" is the next token; the "trajectory" is the full generated response; the "return" is the reward model's score at the end.

GRPO (Group Relative Policy Optimization, DeepSeek 2024) emerged as PPO's successor for LLM RL. The key insight: instead of training a separate critic network (which doubles memory and is hard to train for language), sample G responses per prompt, use the group's mean reward as the baseline, and compute advantages within the group: A_i = (r_i − mean(r)) / std(r). This eliminates the critic entirely, halving memory, while remaining a valid variance-reduced policy gradient. GRPO powered DeepSeek-R1's RL-only training of reasoning capabilities and is now the default for open-source RL-on-LLM work (Qwen, Llama post-training, most reasoning fine-tunes).

Open the group-relative advantage playground to see this concretely: score a group of responses and watch each one's advantage A_i = (r_i − mean)/std — above-average responses get reinforced, below-average suppressed. Make every reward equal and the advantages collapse to zero: the group carries no signal and the gradient vanishes, which is exactly why GRPO pipelines skip all-correct and all-wrong groups.

RLVR (RL with Verifiable Rewards) is the 2024-2025 frontier: when the reward signal can be computed by a verifier (does the math answer parse and check? does the code pass unit tests? does the agent complete the task?) you sidestep reward modeling entirely and can scale RL almost arbitrarily. This is the engine behind o1, R1, and the reasoning model wave.

Beyond reward models. RLAIF (RL from AI Feedback, Anthropic) replaces human labelers with a constitution-guided LLM critic. Process Reward Models (PRMs) score intermediate reasoning steps rather than only the final answer, providing denser feedback for long chains of thought. Self-play and self-improvement loops (where the model generates its own training data, scored by a verifier or a separate critic) are an active research frontier, successors to the AlphaZero playbook.

Beyond LLMs: Where RL Lives

Game playing: TD-Gammon (1992), AlphaGo (2016), AlphaZero (2017), MuZero (2019), AlphaStar (StarCraft II), OpenAI Five (Dota 2)
Robotics: sim-to-real policy learning, dexterous manipulation (OpenAI's Rubik's cube hand), locomotion (ANYmal, Boston Dynamics RL controllers), most modern VLA (vision-language-action) policies use RL fine-tuning on top of behavior cloning
Recommender systems and advertising: contextual bandits and full RL for ranking, ad allocation, and inventory pacing at YouTube, Meta, Netflix, and most large ad platforms
Chip design: Google used RL for floorplanning on TPU v4 and beyond
Scientific discovery: RL for protein design, drug discovery, theorem proving (DeepMind's FunSearch, AlphaProof)

The field is far broader than LLM post-training, but for the foreseeable future, most of the compute and most of the industrial interest in RL is in language model alignment and reasoning.