Module 1. Introduction: Reinforcement Learning for LLMs

Answer: A-3, B-1, C-5, D-2, E-4.

• A state describes the current situation: a cell, or a prompt plus prefix.
• A policy specifies the choice rule: a direction rule or a token distribution.
• An action is one choice that was actually taken.
• The environment determines transitions and external consequences.
• A reward is scalar feedback after a transition or episode.

The key boundary is between a policy and an action: a distribution is not the same object as one sample from it.

Answer: 2.

$\pi_\theta(\cdot\mid s)$ denotes the full probability distribution over available actions. A concrete $a$ is selected from that distribution. Reward then evaluates a consequence; it is neither the action nor its probability.

Option 4 is false because stochastic does not mean uniform. A policy may assign probabilities $0.9$ and $0.1$ to two actions.

Answer: A-2, B-3, C-4, D-1.

In the token-level formulation,

This is an exact correspondence at the level of the mathematical action-selection model. It does not determine how the weights $\theta$ were obtained: next-token pretraining, supervised learning, and RL can all produce a model that defines a token distribution.

Answers: 1 and 3.

Reward $r_{t+1}$ is local to one transition. Return

aggregates future rewards. When $\gamma=0$, only the immediate term $r_{t+1}$ remains.

Option 2 is true only in special tasks with a single nonzero terminal reward and $\gamma=1$. Option 4 is false: when $\gamma=1$, return is the ordinary sum of rewards, and different episodes can have different sums.

Answer: 3.

During online collection, the current policy participates in creating the next dataset. After an update, action frequencies, visited states, and observed outcomes change. Reward normally reports the result of the selected action or trajectory, not a full set of counterfactual outcomes for every alternative.

The other options are false: RL can use gradient descent and demonstrations, and scalar-valued loss alone does not create a decision-making problem.

Answer: A-3, B-4, C-2, D-1.

• Supervised fine-tuning (SFT) maximizes demonstration likelihood.
• Direct preference optimization (DPO) uses fixed pairs and a pairwise loss relative to a reference policy.
• Reinforcement learning from human feedback (RLHF), implemented here with proximal policy optimization (PPO), collects rollouts and updates the policy; a typical PPO-RLHF system also uses a reward model and critic.
• Best-of-N selects a candidate at inference time and does not by itself change parameters.

1. Contextual bandit. The complete response is collapsed into one action followed by one terminal reward.

2. Finite token-level Markov decision process (MDP). The state is the full prefix and the action is the next token.

3. Partially observable Markov decision process (POMDP) or semi-Markov decision process (semi-MDP). External state is hidden and macro-actions can have unequal duration.

No abstraction is permanently “the true one.” The appropriate choice depends on which mechanism must be explicit in a particular derivation.

Answers: 1 and 3.

DPO uses fixed data, so offline is appropriate as an engineering description of data access. A typical DPO problem, however, is not built from transitions $(s,a,r,s')$, does not perform Bellman backups, and does not reproduce the classical value-extrapolation problem in the same form as offline RL.

A concise accurate description is: DPO is direct offline preference optimization derived from a Kullback–Leibler-regularized human-feedback formulation.

Answer: 2.

In PPO, a snapshot $\pi_{\text{old}}$ usually generates the rollouts. One batch may then be processed for several minibatch epochs. The ratio

enters a clipped surrogate objective. Clipping removes the incentive for some further ratio changes but does not enforce a hard bound on actual ratios or KL. This is a near/on-policy protocol, not a promise that every sample is used once. Clipping reduces the risk of an excessively large step, but it does not turn arbitrarily stale data into strictly on-policy data.

Answer: 2.

Reinforcement learning with verifiable rewards (RLVR) describes the source of feedback: correctness can be checked by code, tests, an exact-answer rule, or another automatic procedure.

Group relative policy optimization (GRPO) describes a way to form relative advantages from a group of rollouts and update the policy. GRPO is often used in RLVR, but the terms are not identical: one reward regime allows multiple algorithms, and GRPO can consume other scalar feedback.

Answer: 3 — Best-of-N / inference-time selection.

The model parameters are frozen, so the system performs candidate search and selection rather than policy training. A training loop appears when the scores or selected responses are used to change $\theta$, for example through a supervised update, preference optimization, or a policy-gradient update on collected rollouts.

Answers: 1 and 3.

For a pure temperature policy with fixed logits,

This statement does not automatically extend to a complete decoding pipeline with top-$p$, top-$k$, penalties, or hidden transformations.

Kullback–Leibler divergence (KL) measures distributional change relative to a reference policy. It can constrain drift, but it does not prove that the reward model measures the intended property or that a proxy objective matches the true objective.

A backward-recursion check gives

In a standard model-free formulation, the factors that depend on $\theta$ are

The initial distribution $\rho_0$, environment dynamics $P$, and reward rule $P_R$ are treated as fixed with respect to the policy parameters. Updating $\theta$ changes action probabilities, which changes subsequent transitions, visited states, and therefore the entire distribution $p_\theta(\tau)$. If the environment or reward model is updated at the same time, its parameters must be written separately; that is a broader nonstationary system.

For an LLM, the same statement means that an updated model generates a different response distribution; in an agentic system, different actions can also lead to different external states.

Over two steps from the center, four equally likely outcomes exist:

• left, left — absorption at 0;
• right, right — absorption at 4;
• left, right and right, left — return to 2.

The probability of surviving one two-step block is $1/2$. Avoiding both terminals for 20 actions requires surviving ten blocks:

By symmetry, the probabilities of terminating on the left and right are equal. Hence

The value $0.5$ belongs to the version without a time limit. It is useful intuition but not the exact baseline for the executed protocol.

The autoregressive probability of the complete response is the product of the conditional probabilities:

Its natural logarithm is

Separately,

Therefore,

One final reward evaluates the whole response but does not identify which of the three token choices was useful or harmful. That is the credit-assignment problem.

from __future__ import annotations

import math
import numpy as np


def discounted_return(rewards: list[float], gamma: float) -> float:
    values = np.asarray(rewards, dtype=np.float64)
    if values.ndim != 1 or values.size == 0:
        raise ValueError("rewards must be a non-empty 1D sequence")
    if not np.isfinite(values).all():
        raise ValueError("rewards must be finite")
    if not math.isfinite(gamma) or not 0.0 <= gamma <= 1.0:
        raise ValueError("gamma must lie in [0, 1]")

    result = 0.0
    for reward in values[::-1]:
        result = float(reward) + gamma * result
    return float(result)

The backward recurrence avoids explicitly computing powers and makes one pass: $O(T)$ time and $O(1)$ additional memory.

import math
import numpy as np


def softmax_with_temperature(
    logits: np.ndarray,
    temperature: float,
) -> np.ndarray:
    z = np.asarray(logits, dtype=np.float64)
    if z.ndim != 1 or z.size == 0:
        raise ValueError("logits must be a non-empty 1D array")
    if not np.isfinite(z).all():
        raise ValueError("logits must be finite")
    if not math.isfinite(temperature) or temperature <= 0.0:
        raise ValueError("temperature must be finite and positive")

    scaled = z / temperature
    scaled -= scaled.max()
    weights = np.exp(scaled)
    return weights / weights.sum()

Subtracting the maximum uses softmax shift invariance and prevents overflow. The common multiplicative factor cancels between numerator and denominator, so probabilities are unchanged.

import math
import numpy as np

def softmax_with_temperature(logits: np.ndarray, temperature: float) -> np.ndarray:
    z = np.asarray(logits, dtype=np.float64)
    if z.ndim != 1 or z.size == 0 or not np.isfinite(z).all():
        raise ValueError("logits must be a non-empty finite 1D array")
    if not math.isfinite(temperature) or temperature <= 0.0:
        raise ValueError("temperature must be finite and positive")
    scaled = z / temperature
    shifted = scaled - np.max(scaled)
    weights = np.exp(shifted)
    return weights / weights.sum()


def categorical_entropy(probabilities: np.ndarray) -> float:
    p = np.asarray(probabilities, dtype=np.float64)
    if p.ndim != 1 or p.size == 0 or not np.isfinite(p).all():
        raise ValueError("probabilities must be a non-empty finite 1D array")
    if np.any(p < 0.0):
        raise ValueError("probabilities must be non-negative")
    if not math.isclose(float(p.sum()), 1.0, rel_tol=1e-10, abs_tol=1e-12):
        raise ValueError("probabilities must sum to 1")

    positive = p > 0.0
    return float(-np.sum(p[positive] * np.log(p[positive])))


def policy_entropy(logits: np.ndarray, temperature: float) -> float:
    return categorical_entropy(softmax_with_temperature(logits, temperature))

To reproduce the table:

logits = np.array([2.0, 1.0, 0.0, -1.0])
for temperature in [0.25, 0.5, 1.0, 2.0, 4.0, 10.0]:
    print(temperature, f"{policy_entropy(logits, temperature):.6f}")

The output is 0.093113, 0.455429, 0.947537, 1.245050, 1.348243, 1.380071.

import numpy as np


def run_corridor_episode(
    rng: np.random.Generator,
    *,
    max_steps: int = 20,
) -> float:
    if not isinstance(max_steps, int) or isinstance(max_steps, bool) or max_steps <= 0:
        raise ValueError("max_steps must be a positive integer")

    state = 2
    for _ in range(max_steps):
        action = int(rng.integers(0, 2))
        state += -1 if action == 0 else 1
        if state == 0:
            return 0.0
        if state == 4:
            return 1.0
    return 0.0


def estimate_corridor_value(
    n_episodes: int,
    *,
    seed: int = 7,
    max_steps: int = 20,
) -> float:
    if not isinstance(n_episodes, int) or isinstance(n_episodes, bool) or n_episodes <= 0:
        raise ValueError("n_episodes must be a positive integer")

    rng = np.random.default_rng(seed)
    returns = [run_corridor_episode(rng, max_steps=max_steps) for _ in range(n_episodes)]
    return float(np.mean(returns))

Verified values:

N=1000,  seed=7,  max_steps=20 -> 0.494
N=20000, seed=23, max_steps=20 -> 0.4933
exact finite-horizon value       -> 0.49951171875

Without a step limit, corridor symmetry gives probability 0.5 for the right terminal. With a 20-step limit, some trajectories reach neither boundary and receive reward 0.0. To survive each pair of steps, the process must return from state 1 or 3 to state 2, which happens with probability 1/2. The probability of remaining nonterminal through ten such pairs is therefore $2^{-10}=1/1024$. Symmetry splits the remaining probability equally between the left and right terminals, so the exact probability of the right terminal is

A random estimate need not match the exact value in every run. It should behave according to Bernoulli variance, with typical error decreasing approximately as $1/\sqrt{N}$.