🎯 Reinforcement Learning Basics

Before you start

Review probability and statistics for conditional expectation, calculus and optimization for gradients, and information theory for entropy and KL divergence. No prior RL algorithm is assumed.

After this chapter, you should be able to compute a return and Bellman backup, distinguish value learning from policy learning, explain what a baseline does, and calculate PPO's clipped surrogate for either advantage sign. The final sections connect these ideas to language-model training.

The problem: actions change tomorrow's data

A supervised model learns from provided examples. An RL policy chooses actions that influence both rewards and the observations it sees next. A robot choosing a route, a game player choosing a move, and a language model choosing a tool call all face delayed consequences. An immediate reward can favor an action that makes the eventual task fail.

A policy is a rule for choosing an action from the available state. A return adds rewards over the rest of an interaction. The learning objective is expected return under a specified start-state distribution and horizon; a reward function is a measurable proxy for the designer's goal, not the goal itself.

Worked example: take two now or four later

There are two nonterminal states, Start and Detour, plus a terminal state with value zero. At Start, Cash ends the episode with reward 2. Continue gives reward 0 and moves to Detour. At Detour, the only action ends the episode with reward 4. Let the discount factor be γ = 0.9.

Return from Cash:      2
Return from Continue:  0 + 0.9 × 4 = 3.6
V*(Detour) = 4
V*(Start) = max(2, 3.6) = 3.6

Now evaluate a policy that Continues with probability 0.25 and Cashes otherwise. Its expected value at Start is 0.25 × 3.6 + 0.75 × 2 = 2.4. Continue has advantage 3.6 − 2.4 = 1.2; Cash has advantage 2 − 2.4 = −0.4. The policy-weighted average advantage is zero: 0.25 × 1.2 + 0.75 × (−0.4) = 0.

A reward of 2 is positive, yet Cash has negative advantage because it is worse than the policy's average available outcome. Policy improvement depends on this comparison.

Notation and the state assumption

Symbol	Meaning
sₜ, aₜ, Rₜ₊₁	State, action, and reward following that action
P(s′ given s, a)	Distribution of the next state
π(a given s)	Policy's distribution over actions
γ	Discount factor; here between zero and one, inclusive for finite episodes
Gₜ	Return from time t
Vπ(s), Qπ(s, a)	Expected return from a state, or after a particular first action
Aπ(s, a)	Qπ(s, a) − Vπ(s), the advantage

A Markov decision process (MDP) assumes the state contains enough information that next-state and reward distributions depend only on the current state and action. Observations need not be Markov: a hidden robot velocity or missing conversation history can matter. Partial observability can require history, recurrent state, or a belief distribution. Calling an observation a state does not make the assumption true.

For an episode terminating at T, Gₜ = Σₖ₌₀^(T−t−1) γᵏ Rₜ₊ₖ₊₁. Finite episodes can use γ = 1. With bounded rewards, γ < 1 gives finite discounted returns in continuing tasks; average-reward formulations are another option. 1/(1−γ) describes the sum of discount weights, not a hard planning cutoff.

Bellman backups and value learning

The Bellman expectation equation separates the first reward from future return:

Vπ(s) = E over a~π and s′~P [R(s,a,s′) + γ Vπ(s′)].

For the optimal value, replace the action average with a maximum. Terminal continuation value is zero. In the worked example, the Bellman backup propagates the value 4 from Detour to the value 3.6 for Continue. A small gridworld makes this propagation visible:

Value iteration uses known transition/reward models to update a table. Q-learning instead uses sampled transitions:

Q(s,a) ← Q(s,a) + η [r + γ maxₐ′ Q(s′,a′) − Q(s,a)].

If Q(Start, Continue) is zero, the estimate at Detour is 4, and η = 0.5, the update is 0 + 0.5 × (0 + 0.9 × 4 − 0) = 1.8. This is a bootstrap estimate, not a complete sampled return. Tabular convergence requires sufficient state-action coverage and suitable decreasing step sizes, among other assumptions; neural Q-learning does not inherit an unconditional guarantee.

SARSA uses the next action actually sampled by the behavior policy instead of a maximum. DQN combines a neural Q-function with replay and a slowly changing target network. Maximizing Q is easy over a small discrete action set and harder over continuous or huge action spaces. Value-based control can still include stochastic exploration; it is not inherently forced to act deterministically.

Policy gradients and baselines

A policy network directly parameterizes πθ. For an undiscounted finite episode, the score-function estimator can be written:

∇J(θ) = E[Σₜ ∇θ log πθ(aₜ given sₜ) Gₜ].

REINFORCE estimates this expectation from sampled episodes. High-return actions get their log probabilities increased relative to alternatives. Discounted objectives require the corresponding discount weights or discounted state-visitation convention; dropping those silently changes the objective.

Subtracting an action-independent baseline b(sₜ) preserves the expected policy gradient under on-policy sampling, with the baseline treated as fixed in the actor gradient. This follows from Eₐ~π[∇ log π(a given s) b(s)] = b(s) ∇Σₐπ(a given s) = 0. A good baseline can reduce variance; an arbitrary one may increase it. Vπ(s) is a useful common choice, but the exact variance-minimizing scalar baseline also depends on gradient norms.

An actor-critic learns a policy and a value estimate. A temporal-difference residual is δₜ = rₜ + γ V(sₜ₊₁) − V(sₜ). Generalized Advantage Estimation (GAE) combines residuals as Âₜ = Σₗ (γλ)ˡ δₜ₊ₗ. Smaller λ relies more on the critic; larger λ uses more sampled future rewards. At λ = 1, the sum telescopes to return minus V for a complete episode with correct terminal handling. Truncated rollouts retain a bootstrap term, so they are not automatically complete Monte Carlo estimates.

PPO: clipping an incentive, not a probability

PPO collects actions under πold, stores their log probabilities, estimates advantages, and optimizes a surrogate over the batch. Define the probability ratio ρₜ = πθ(aₜ given sₜ) / πold(aₜ given sₜ). For clipping parameter ε:

Lclip = E[min(ρₜ Âₜ, clip(ρₜ, 1−ε, 1+ε) Âₜ)].

This is an objective to maximize; implementations minimizing a loss negate it. With ε = 0.2:

Advantage	Ratio ρ	ρA	clipped ρ × A	min, the surrogate
+2	1.4	2.8	2.4	2.4
+2	0.6	1.2	1.6	1.2
−2	0.6	−1.2	−1.6	−1.6
−2	1.4	−2.8	−2.4	−2.8

For positive advantage, the sample stops rewarding increases above 1 + ε. For negative advantage, it stops rewarding decreases below 1 − ε. Moves in the unfavorable direction remain penalized. The ratio itself is not clipped or constrained. Shared parameters, other samples, additional losses, and repeated optimizer steps can move it outside the band. PPO clipping guarantees neither a maximum ratio change nor a KL bound.

TRPO instead formulates an average-KL-constrained surrogate and approximately solves it with additional optimization machinery. PPO is simpler to optimize, but is not the same constrained problem. Monitor measured KL, clip fraction, entropy, reward, and value error; learning-rate controls and KL-based early stopping are separate safeguards.

Data reuse and exploration

On-policy updates use data from the policy being optimized or a recent rollout policy with appropriate handling, as in PPO's limited batch reuse. Off-policy methods learn about a target policy using data from another behavior policy. Replay improves reuse but creates distribution and coverage issues; offline RL is the stricter setting where the fixed logged dataset cannot be augmented through new interaction. Neither family guarantees stability.

In a bandit, ε-greedy takes a random action with probability ε. A fixed positive ε keeps choosing known-suboptimal arms: with two arms whose mean rewards differ by Δ, forced uniform exploration alone incurs expected regret at least T ε Δ / 2 over T pulls. That is linear in T. UCB uses uncertainty bonuses and can achieve logarithmic regret in standard stationary stochastic-bandit settings with appropriate assumptions. Neither result says one strategy wins every finite run.

Use the bandit playground to compare sample paths and averages. Entropy bonuses preserve stochasticity without necessarily directing exploration toward useful uncertainty. Curiosity bonuses can help discover rare rewards but may chase irrelevant novelty.

Bridge to language-model RL

For token-level training, the state is a prompt plus generated prefix, the action is the next token, and termination is the end of the response. Tool use adds environment observations and action consequences. A terminal score may come from a learned preference reward model, executable tests, a formal checker, or a mixture.

A reference-policy KL penalty discourages drift while rewards drive adaptation; it does not make an imperfect reward safe to optimize. Verifiable-reward RL (RLVR) names the reward source, not a requirement to skip SFT, use binary rewards, or choose a particular optimizer. Tests can be incomplete and graders can contain bugs.

GRPO avoids a learned value critic by comparing a group of responses to the same prompt. A common response-level signal is Âᵢ = (Rᵢ − mean(R)) / (std(R) + εnum), where εnum prevents division by zero. For rewards [0, 1, 1, 0], mean and population standard deviation are both 0.5, giving approximately [-1, 1, 1, -1]. Equal rewards give zero group-relative signal; a separate KL or entropy term may still have a gradient.

The group-relative playground shows this normalization. A sample's own reward contributes to its group mean, and normalization changes weighting; this is not simply an arbitrary action-independent baseline with a blanket unbiasedness guarantee. Removing the critic saves its training state but group generation still costs compute. GRPO can use learned or verifiable rewards.

Optional: planning with a model

Model-based RL uses known or learned dynamics for planning. AlphaZero combines a policy/value network with Monte Carlo Tree Search in games with known rules. Search produces a stronger action-selection target, and self-play trains the network toward that target and observed outcomes. With learned dynamics, model error can compound. In language tasks, invalid steps, uncertain observations, and weak verifiers make the analogy to exact game search incomplete.

Check your understanding

With A = −3, ε = 0.2, and ρ = 0.7, calculate PPO's surrogate. Does it force ρ to become 0.8? For a two-arm bandit with ε = 0.1 and reward gap 0.4, what regret does forced exploration contribute over 1,000 pulls?

Solution

The two PPO terms are −2.1 and −2.4, so the surrogate is −2.4. That sample's objective is flat on this side; the policy ratio remains 0.7 and is not projected to 0.8. Forced uniform exploration chooses the inferior arm with probability 0.1/2, so it contributes 1,000 × 0.05 × 0.4 = 20 expected regret. Additional mistakes during exploitation can add more.

Continue learning

RLHF and DPO develops preference objectives, test-time compute studies search after training, and agentic AI turns tool policies into bounded, observable systems.

References

• Schulman et al., PPO: clipped and KL-penalty surrogate methods.
• Shao et al., DeepSeekMath: GRPO and group-relative policy optimization.
• Silver et al., AlphaZero: search, policy/value learning, and self-play.