Reinforcement Learning Fundamentals

For NAO + anyone who keeps seeing "PPO", "GRPO", "RLVR", "reward model" in the post-training papers and wants the actual machinery underneath. Every modern reasoning model — o1, DeepSeek-R1, the "thinking" models — is trained with an algorithm that is, at its core, a 1990s reinforcement-learning idea wearing an LLM as its policy network. This article is the ground floor. If you understand the five things here — MDPs, value functions, the Bellman equation, the policy gradient, and PPO's clipped objective — then [[rlhf-and-alignment]], [[rlvr]], and [[grpo]] stop being magic and become "oh, it's that, but the environment is a math problem and the reward is a unit test."

What it is (intuition first)

Supervised learning hands the model the right answer for every input: "this image is a cat, that one is a dog." Reinforcement learning (RL) does not. In RL, an agent is dropped into an environment, takes actions, and gets back only a scalar reward — a number saying "that was good" or "that was bad," often arriving long after the action that caused it. Nobody tells the agent what the correct action was. It has to figure that out from the consequences.

Think of training a dog. You don't hand it a textbook of "sit when I say sit." You wait, it does something, and occasionally a treat appears. The dog's whole problem is credit assignment: of all the things I just did, which one earned the treat? And exploration vs exploitation: do I keep doing the thing that worked, or try something new that might work better?

That is the entire field. Three hard problems hide inside it:

1. Delayed reward. A chess move that loses the game might have been the move 20 turns ago. The reward (you lost) is far from the cause.
2. No supervisor. There's no label "the right move here was Nf3." There's only outcomes. The agent must invent its own targets.
3. Your data depends on your behavior. A supervised dataset is fixed. In RL, the actions you take determine which states you see next, so a bad policy only ever sees bad situations and never learns its way out. The data distribution is non-stationary and self-inflicted.

The reason every LLM person now needs this: post-training an LLM is an RL problem. The "agent" is the model. The "action" is emitting the next token (or a whole answer). The "reward" is a human preference ([[rlhf-and-alignment]]) or a verifier like a unit test or a math checker ([[rlvr]]). The algorithms below are literally what runs.

Why it matters

• It is the post-training engine of every frontier model. RLHF ([[rlhf-and-alignment]]) turned GPT-3 into ChatGPT. RLVR ([[rlvr]]) turned base models into reasoners. Both are PPO-family RL with a language model as the policy. You cannot read a 2025–2026 model card without it.
• It handles problems supervised learning structurally cannot. When the "right answer" is unknown or there are many right answers (a good essay, a winning game, a passing patch), but you can score an outcome, RL is the tool.
• It is the bridge to agency. Single-turn RL gives you a better chatbot. Multi-turn RL over tool calls and long trajectories gives you a coding agent ([[agentic-rl-long-horizon-coding]]) — the "Alice can code" mission.
• The vocabulary is load-bearing. "Advantage," "baseline," "KL penalty," "on-policy," "clipped ratio," "credit assignment" — these come straight from the fundamentals here and are used unchanged in [[grpo]] and [[process-outcome-rewards]].

How it works (real mechanics, formulas, pseudocode)

1. The Markov Decision Process (MDP)

The formal container for an RL problem is an MDP — a 5-tuple ⟨S, A, R, P, ρ₀⟩ (OpenAI Spinning Up, Sutton & Barto):

• S — set of states (the world description the agent sees).
• A — set of actions.
• R — reward function, r_t = R(s_t, a_t, s_{t+1}).
• P — transition dynamics, P(s' | s, a) = probability of landing in s'.
• ρ₀ — distribution over starting states.

The word Markov is the key assumption: the next state depends only on the current state and action, not the full history. The present screens off the past.

The agent acts via a policy π. It can be deterministic — a = μ(s) — or, the usual case, stochastic: π(a | s) is a probability distribution over actions. An episode produces a trajectory τ = (s₀, a₀, s₁, a₁, …).

The thing we want to maximize is the return — cumulative reward, almost always discounted so that nearer rewards count more and infinite sums stay finite:

R(τ) = Σ_{t=0}^{∞} γ^t r_t        with discount  γ ∈ (0, 1)

The RL objective is to find the policy maximizing expected return:

J(π) = E_{τ ~ π}[ R(τ) ]          π* = arg max_π J(π)

2. Value functions — "how good is this situation?"

We rarely optimize J(π) blind. We estimate value functions that summarize expected future return (Spinning Up's four-function table):

Two relationships you must internalize:

V^π(s) = E_{a ~ π}[ Q^π(s, a) ]          (value = average Q over your policy)
V*(s)  = max_a  Q*(s, a)                  (optimal value = best action's Q)

The single most useful derived quantity is the advantage:

A^π(s, a) = Q^π(s, a) − V^π(s)

It answers: how much better is action `a` than the average action in this state? Positive advantage → do more of this. Negative → do less. Subtracting V^π(s) (a baseline) doesn't change which action is best but dramatically reduces noise. This trick reappears verbatim as the entire idea of [[grpo]].

3. The Bellman equation — the recursion that makes it tractable

Value functions obey a self-consistency recursion. The value of now equals the immediate reward plus the discounted value of next (Spinning Up):

V^π(s)   = E[ r(s,a) + γ V^π(s') ]
Q^π(s,a) = E[ r(s,a) + γ E_{a'~π}[ Q^π(s', a') ] ]

And the Bellman optimality equations, where you act greedily:

V*(s)   = max_a  E[ r(s,a) + γ V*(s') ]
Q*(s,a) = E[ r(s,a) + γ max_{a'} Q*(s', a') ]

This recursion is the foundation of every value-based method. It lets you learn a value not from full episodes but from single transitions, by bootstrapping: estimating a value partly from another (current) estimate.

4. Q-learning — the canonical value-based method

Q-learning (Watkins 1989; Sutton & Barto ch. 6) learns Q* directly from experience, without a model of the environment, and off-policy (it learns about the greedy policy while behaving more exploratorily, e.g. ε-greedy). The update applies the Bellman-optimality recursion as a moving target:

Q(s,a) ← Q(s,a) + α [ r + γ max_{a'} Q(s', a') − Q(s,a) ]
                       └──────────── TD error δ ────────────┘

• α is the learning rate.
• The bracketed term is the temporal-difference (TD) error δ — the gap between the bootstrapped target r + γ max Q(s',a') and the current estimate.
• max_{a'} over the next state's actions is what makes it learn the optimal policy regardless of how it actually behaved → off-policy.

Once Q is good, act greedily: a = arg max_a Q(s,a). Deep Q-Networks (DQN) replace the table with a neural net and were what cracked Atari from pixels. Q-learning is foundational, but it struggles with continuous/huge action spaces (that max_a becomes intractable) — which is exactly why LLM post-training uses policy methods instead, since the action space is "every possible token."

5. Policy gradients & REINFORCE — optimize the policy directly

Instead of learning values and acting greedily, policy-gradient methods parameterize the policy π_θ(a|s) (the LLM!) and push θ straight up the return gradient. The policy gradient theorem (Sutton et al. 1999) gives the remarkable result that you can do this without differentiating through the environment's dynamics or state distribution:

∇_θ J(θ) = E_{τ ~ π_θ}[ Σ_t  ∇_θ log π_θ(a_t | s_t) · Ψ_t ]

where Ψ_t is some measure of "how good a_t was." The intuition is pure behaviorism: increase the log-probability of actions that led to high return, decrease it for low return. The ∇ log π factor is the "knob to turn up this action"; Ψ_t is "by how much, and in which direction."

REINFORCE (Williams 1992) is the simplest choice: Ψ_t = the return:

# REINFORCE — vanilla policy gradient (one update)
trajectories = sample(policy_pi_theta)              # roll out the current policy
for tau in trajectories:
    R = discounted_return(tau)                      # one number for the episode
    for (s_t, a_t) in tau:
        # gradient ascent: push up log-prob of taken actions, scaled by return
        loss += -log_prob(pi_theta, a_t, s_t) * R   # (minus → ascent via SGD)
theta = theta - lr * grad(loss)

Raw REINFORCE works but is extremely high-variance (the return is noisy). The fixes, in order, are the lineage that leads straight to PPO:

1. Subtract a baseline. Replace return R with advantage A_t = Q − V. The baseline V doesn't bias the gradient but slashes variance. A policy net + a value net = actor-critic.
2. Estimate the advantage well. Generalized Advantage Estimation (GAE) (Schulman et al. 2015) blends short- and long-horizon TD residuals with a knob λ:

   δ_t = r_t + γ V(s_{t+1}) − V(s_t)                 # one-step TD residual
   Â_t^GAE(γ,λ) = Σ_{l=0}^{∞} (γλ)^l · δ_{t+l}       # exponentially-weighted sum

λ=0 → Â_t = δ_t (low variance, high bias, pure bootstrap). λ=1 → Monte-Carlo advantage (high variance, low bias). Typical λ ≈ 0.95 tunes the bias–variance tradeoff. (Formula per the GAE paper, arXiv:1506.02438; we state it from the canonical form — the PDF stream would not parse in this pass, see caveats.)

6. PPO — the workhorse (and the actual RLHF/RLVR algorithm)

The danger with raw policy gradients: one big batch can push θ so far that the policy collapses, and because the data is on-policy, a wrecked policy collects only garbage data and never recovers. TRPO fixed this with a hard trust-region constraint but is painful to implement.

Proximal Policy Optimization (PPO) (Schulman et al. 2017, arXiv:1707.06347) gets the same "don't move too far" guarantee with a dead-simple trick. Define the probability ratio between new and old policy:

r_t(θ) = π_θ(a_t | s_t) / π_{θ_old}(a_t | s_t)

Then optimize the clipped surrogate objective (quoted from the paper):

L^CLIP(θ) = Ê_t[ min( r_t(θ) Â_t ,  clip(r_t(θ), 1−ε, 1+ε) Â_t ) ]

with ε = 0.2 typically (ratios clipped to [0.8, 1.2]). The mechanism:

• If advantage Â_t > 0 (good action), the objective lets you raise r_t — but the clip caps the gain at 1+ε, so there's no reward for moving the policy further than that. No incentive to overshoot.
• If Â_t < 0 (bad action), it lets you push r_t down, capped at 1−ε.
• The outer min makes the clip a pessimistic lower bound, so the update is conservative. That single min(…, clip(…)) is the whole trust region.

Because the objective is well-behaved over a region, you can run multiple epochs of minibatch SGD over the same batch of trajectories — far better sample efficiency than one-shot REINFORCE. The full loss adds a value-function loss and an entropy bonus (from the paper):

L^{CLIP+VF+S}(θ) = Ê_t[ L^CLIP(θ) − c₁ L^VF(θ) + c₂ S[π_θ](s_t) ]

L^VF trains the critic (the value net); S is an entropy bonus keeping the policy exploratory; c₁, c₂ weight them.

# PPO (Algorithm 1, paper) — actor-critic, on-policy
for iteration in range(N):
    trajectories = run_policy(pi_theta_old, T_steps)        # collect on-policy data
    advantages   = gae(trajectories, value_net, gamma, lam) # Â_t via GAE
    for epoch in range(K):                                  # reuse the batch K times
        for minibatch in shuffle(trajectories):
            ratio = pi_theta(a, s) / pi_theta_old(a, s)
            clipped = clip(ratio, 1 - eps, 1 + eps)
            L_clip  = mean(min(ratio * A, clipped * A))     # the trust region
            L_vf    = mean((value_net(s) - return_target)**2)
            L_ent   = mean(entropy(pi_theta(s)))
            loss    = -(L_clip - c1 * L_vf + c2 * L_ent)    # minus → ascent
            theta   = adam_step(theta, grad(loss))
    theta_old = theta                                       # refresh reference

This pseudocode, almost unchanged, is what runs in RLHF and RLVR. Swap the environment for "an LLM emitting tokens," swap the reward for "a reward model ([[rlhf-and-alignment]]) or a verifier ([[rlvr]])," add a KL-to-reference penalty to keep the model near its starting point, and you have the standard LLM-alignment training loop. [[grpo]] then deletes the value net (c₁ L^VF term and the critic) and replaces Â_t with the normalized reward of a group of sampled answers — PPO with the expensive half removed.

Key ideas & tradeoffs

• Value-based (Q-learning) vs policy-based (REINFORCE/PPO). Value methods learn "how good is each action" then act greedily — great for small discrete action spaces, sample-efficient, off-policy. Policy methods optimize the policy directly — they handle huge/continuous action spaces (every token!) and stochastic policies naturally, at the cost of being on-policy and higher-variance. LLMs use policy methods because the action space is the vocabulary.
• On-policy vs off-policy. Off-policy (Q-learning) can learn from any data, including old replay buffers — sample-efficient but can be unstable. On-policy (PPO) must collect fresh data with the current policy every iteration — stable, but you "throw away" data after a few epochs. PPO's clip is precisely what lets it squeeze several epochs out of each on-policy batch.
• Bias–variance is the eternal knob. Monte-Carlo returns: unbiased, noisy. Bootstrapped TD: low-variance, biased. GAE's λ and the discount γ are how you dial between them. Every RL system is a point on this tradeoff.
• The baseline / advantage is the highest-leverage idea. Subtracting a state-dependent baseline is variance reduction for free. It is why actor-critic beats vanilla REINFORCE, and the entire conceptual basis of [[grpo]]'s group-relative trick.
• Credit assignment is the unsolved hard part. Discounting + GAE are heuristics for "which action earned the reward." Over long horizons (a 20-step coding session) they get weak — which is the whole research frontier of [[agentic-rl-long-horizon-coding]] and [[process-outcome-rewards]].

Honest caveats

• RL is notoriously brittle. Reproducibility is a known sore spot: performance can swing wildly with random seeds, reward scaling, network initialization, and implementation details that the papers barely mention. The implementation often matters more than the algorithm. Treat any single RL benchmark number with suspicion.
• PPO is a bag of tricks, not just the clip. The clipped objective is the headline, but working PPO depends on advantage normalization, reward/observation scaling, value-loss clipping, learning-rate annealing, and careful entropy tuning. "Implement PPO from the paper" rarely works first try; the community knows it as "the 37 implementation details."
• `γ` and `λ` are not innocent. They silently define what problem you are solving (how much the future matters). Choosing them is modeling, not a detail.
• Sample efficiency is bad. On-policy RL throws away data and needs enormous interaction. This is fine when the "environment" is a cheap verifier; it's brutal when each rollout is expensive.
• Reward is the whole game and easy to get wrong. Agents ruthlessly exploit any gap between your reward and your true intent (reward hacking). In LLM RL this is acute — a model will learn to please a flawed reward model rather than be correct. See the alignment caveats in [[rlhf-and-alignment]] and the verifiable-reward motivation in [[rlvr]].
• Source-fetch honesty: the PPO clipped objective, ratio, ε=0.2, and combined loss above are quoted from the paper PDF (arXiv:1707.06347); the MDP/value/Bellman formulas are from OpenAI Spinning Up. The GAE estimator is stated from its canonical form — the arXiv:1506.02438 PDF returned a compressed stream our fetcher could not parse, so we did not re-quote it verbatim; verify against the paper if precision matters.

How it connects to OpenAlice + the Academy ladder

This article is the floor of the post-training wing of the library. Read it first, then climb:

1. [[reinforcement-learning-fundamentals]] (you are here) — MDPs, value, policy, Q-learning, REINFORCE, PPO. The vocabulary and the loop.
2. [[rlhf-and-alignment]] — make the LLM the policy, make a learned reward model the reward, add a KL-to-reference penalty: that's RLHF. Also covers DPO (RL's objective without the RL loop).
3. [[rlvr]] — replace the fragile reward model with a verifier (unit test, math checker). Reward 1/0, run PPO/[[grpo]]. This is how o1 / DeepSeek-R1 were made to reason.
4. [[grpo]] — PPO minus the critic; the group of sampled answers is the baseline. The advantage trick from §2 of this article, taken to its logical end. Pairs with [[process-outcome-rewards]] on how the reward is graded.
5. [[self-play-and-verifier-driven-training]] and [[agentic-rl-long-horizon-coding]] — multi-turn, long-horizon RL where the credit-assignment problem from this article gets genuinely hard. The "Alice can code" frontier.

For OpenAlice specifically: the M13 knowledge-compressor and the lab's research rig ([[autoresearch]]) lean on exactly this stack — RLVR/GRPO over verifiable tasks is the training mechanism behind the reasoning and coding capability the org is building toward. When you read an Atlas board task that mentions "reward," "advantage," "rollout," or "KL penalty," it traces back to the five ideas on this page. Foundations adjacent: [[attention-and-transformers]] and [[llm-from-scratch]] build the policy network; this article trains it.