RL for LLM3 / 13

Module 3. Bandits, exploration, and one-step decisions

Choose your answers and select “Check”. Numbers accept a decimal point, comma, or simple fraction. Answers and drafts are saved in this browser and shared between RU/EN.

Use the author’s worked answers to review open questions and code tasks yourself. Code does not run on this site.

Checked: 0 / 10 · Correct: 0

Question P01 · Why "pseudo"

single answer

Pseudo-regret $\bar R_T = \mathbb{E}\left[\sum_t (\mu^* - \mu_{A_t})\right]$ is not so named because it is fake. What does the prefix mean?

One correct option1That the quantity is approximated from a finite sample2That random rewards are replaced by their means: along a given trajectory the quantity carries no reward noise, which makes it convenient for a reproducible experiment3That the comparison is against the best observed arm rather than the optimal one4That the horizon

T

is unknown in advance

That the quantity is approximated from a finite sample

That random rewards are replaced by their means: along a given trajectory the quantity carries no reward noise, which makes it convenient for a reproducible experiment

That the comparison is against the best observed arm rather than the optimal one

That the horizon $T$ is unknown in advance

Answer and explanation

The correct option is That random rewards are replaced by their means: along a given trajectory the quantity carries no reward noise, which makes it convenient for a reproducible experiment.

Under stationary rewards expected regret equals expected pseudo-regret. The whole mechanism reduces to $R_T = \sum_a \Delta_a\,\mathbb{E}[N_a(T)]$ : the algorithm pays the gap each time it returns to a suboptimal arm.

Question P02 · Regret from gaps and pull counts

numeric answer · tolerance ±0.5

Three arms with gaps $\Delta = (0,\ 0.1,\ 0.3)$ were pulled on average $\mathbb{E}[N_a(T)] = (700,\ 200,\ 100)$ times.

What is the expected regret $R_T = \sum_a \Delta_a \mathbb{E}[N_a(T)]$ ?

Pseudo-regretAbsolute tolerance: ±0.000001

Answer and explanation

Answer: 50.

$0.1\cdot200 + 0.3\cdot100 = 20 + 30 = 50$ . The optimal arm with $\Delta = 0$ contributes no regret however often it is pulled.

Question P03 · The limits of the UCB1 guarantee

single answer

The UCB1 bound gives $R_T \le 8\log T \sum_{a:\Delta_a>0} 1/\Delta_a + \text{const}$ . What follows from it, and what does not?

One correct option1Logarithmic asymptotics promise small regret at any finite horizon2It is problem-dependent: a near-optimal arm has a small

\Delta_a

and needs many observations, so logarithmic asymptotics promise nothing about small regret at a finite horizon3The bound is gap-independent and therefore universal4The Lai–Robbins lower bound implies every algorithm has

\Omega(\log T)

regret on every instance

Logarithmic asymptotics promise small regret at any finite horizon

It is problem-dependent: a near-optimal arm has a small $\Delta_a$ and needs many observations, so logarithmic asymptotics promise nothing about small regret at a finite horizon

The bound is gap-independent and therefore universal

The Lai–Robbins lower bound implies every algorithm has $\Omega(\log T)$ regret on every instance

Answer and explanation

The correct option is It is problem-dependent: a near-optimal arm has a small $\Delta_a$ and needs many observations, so logarithmic asymptotics promise nothing about small regret at a finite horizon.

The last option is a standard miscitation: the lower bound is stated for particular parametric families and uniformly efficient strategies, not for every algorithm on every instance.

Question P04 · What transfers from UCB and Thompson

single answer

The module warns against porting bandit recipes to LLMs directly. Which transfer does it call useful?

One correct option1Ensemble spread can be used as posterior uncertainty2Token-distribution entropy serves as a confidence interval on a response's true utility3Exploration should depend on what the system does not yet know, not only on a fixed

\varepsilon

coin4A deterministic index maximum is always preferable to a random sample

Ensemble spread can be used as posterior uncertainty

Token-distribution entropy serves as a confidence interval on a response's true utility

Exploration should depend on what the system does not yet know, not only on a fixed $\varepsilon$ coin

A deterministic index maximum is always preferable to a random sample

Answer and explanation

The correct option is Exploration should depend on what the system does not yet know, not only on a fixed $\varepsilon$ coin.

The first two are exactly the transfers the module rejects: ensemble spread need not be posterior uncertainty, and entropy is not a confidence interval.

Question P05 · Conditions for IPS unbiasedness

multiple answers

Which conditions are needed for $\widehat V_{\mathrm{IPS}}$ to be unbiased? Select all that apply.

Select all correct options1Overlap: if

\pi(a\mid x) > 0

then

\mu(a\mid x) > 0

2The logged

p_i

match the real selection probabilities3Reward and context are recorded correctly4Given the context, action choice does not depend on an unrecorded factor that also drives the potential reward5The new policy

\pi

is deterministic

Overlap: if $\pi(a\mid x) > 0$ then $\Omega(\log T)$

The logged $p_i$ match the real selection probabilities

Reward and context are recorded correctly

Given the context, action choice does not depend on an unrecorded factor that also drives the potential reward

The new policy $\pi$ is deterministic

Answer and explanation

The correct options are:

Overlap: if $\pi(a\mid x) > 0$ then $\mu(a\mid x) > 0$
The logged $p_i$ match the real selection probabilities
Reward and context are recorded correctly
Given the context, action choice does not depend on an unrecorded factor that also drives the potential reward

The fourth condition is secured by proper randomization or a substantive assignment model — and is the easiest to violate in a real log.

Question P06 · IPS, SNIPS and the effective sample size

coding task

Specification: weights $w_i = \pi(a_i\mid x_i)/\mu(a_i\mid x_i)$ . $\widehat V_{\mathrm{IPS}} = \frac1n\sum_i w_i r_i$ ; $\widehat V_{\mathrm{SNIPS}} = \sum_i w_i r_i / \sum_i w_i$ ; Kish effective sample size $\mathrm{ESS} = (\sum_i w_i)^2/\sum_i w_i^2$ .

Input format: line 1 — the number of records $n$ ; then $n$ lines of r mu pi. Output format: lines 1–3 — IPS, SNIPS and ESS (4 decimals).

Starter code:

import numpy as np

def offline_estimates(rewards, behavior, target):
    """Return (ips, snips, ess)."""
    # YOUR CODE HERE
    raise NotImplementedError

if __name__ == "__main__":
    n = int(input())
    rows = [tuple(float(x) for x in input().split()) for _ in range(n)]
    r = [row[0] for row in rows]
    mu = [row[1] for row in rows]
    pi = [row[2] for row in rows]
    ips, snips, ess = offline_estimates(r, mu, pi)
    for value in (ips, snips, ess):
        print(f"{value:.4f}")

Open tests:

stdin	stdout
`3` ⏎ `1 0.2 0.6` ⏎ `0 0.5 0.1` ⏎ `1 0.3 0.3`	`1.3333` ⏎ `0.9524` ⏎ `1.7570`
`2` ⏎ `1 0.5 0.5` ⏎ `0 0.5 0.5`	`0.5000` ⏎ `0.5000` ⏎ `2.0000`

Your answer or notes

Answer and explanation

One correct implementation is:

import numpy as np

def offline_estimates(rewards, behavior, target):
    r = np.asarray(rewards, dtype=float)
    mu = np.asarray(behavior, dtype=float)
    pi = np.asarray(target, dtype=float)
    if not (r.ndim == mu.ndim == pi.ndim == 1 and r.shape == mu.shape == pi.shape):
        raise ValueError("inputs must be aligned one-dimensional arrays")
    if len(r) == 0 or np.any(mu <= 0.0) or np.any(pi < 0.0):
        raise ValueError("need non-empty data, mu > 0, and pi >= 0")
    w = pi / mu
    ips = float(np.mean(w * r))
    total = float(np.sum(w))
    if total <= 0.0:
        raise ValueError("the total weight must be positive")
    snips = float(np.sum(w * r) / total)
    denom = float(np.sum(w ** 2))
    ess = float(total ** 2 / denom) if denom > 0.0 else 0.0
    return ips, snips, ess

In the first test the weights are $\Delta_a$ . Thus IPS is $(3\cdot1+0.2\cdot0+1\cdot1)/3=4/3$ , SNIPS is $4/4.2\approx0.95238$ , and ESS is $4.2^2/(9+0.04+1)\approx1.757$ . The small ESS shows that three logged rows carry roughly the weighted information of fewer than two balanced observations.

In the first test ESS $\approx 1.76$ out of three records: one record with weight 3 carries almost the whole estimate. That is why IPS has high variance — and the same Kish quantity reappears in Module 12 for staleness control.

Question P07 · What double robustness does not give

single answer

The DR estimator stays consistent if at least one of the two models is correct. What can it still not do?

One correct option1Reduce variance relative to plain IPS2Create information where the log has no overlap: if the new policy picks an action the old one never showed in that context, the counterfactual reward is not determined by the log3Work without a behavior-probability model4Use a direct reward model

Reduce variance relative to plain IPS

Create information where the log has no overlap: if the new policy picks an action the old one never showed in that context, the counterfactual reward is not determined by the log

Work without a behavior-probability model

Use a direct reward model

Answer and explanation

The correct option is Create information where the log has no overlap: if the new policy picks an action the old one never showed in that context, the counterfactual reward is not determined by the log.

For LLMs this bites hard: the space of full responses is vast and exact overlap is unattainable. A model may extrapolate, but that is an added assumption, not a statistical fact.

Question P08 · Generation temperature versus training exploration

single answer

Why can raising the decoding temperature not be called exploration in the RL sense?

One correct option1Because temperature affects only the most likely token2Because temperature changes the candidate distribution without updating any quality estimate: training exploration means actions whose feedback changes the subsequent policy3Because temperature is always pinned to one during training4Because entropy does not increase with temperature

Because temperature affects only the most likely token

Because temperature changes the candidate distribution without updating any quality estimate: training exploration means actions whose feedback changes the subsequent policy

Because temperature is always pinned to one during training

Because entropy does not increase with temperature

Answer and explanation

The correct option is Because temperature changes the candidate distribution without updating any quality estimate: training exploration means actions whose feedback changes the subsequent policy.

Two neighbouring caveats on the same step: during training the logits themselves change, and after top-k, top-p and bans the resulting distribution is no longer a single temperature curve — a token zeroed by a filter cannot be restored by raising temperature.

Question P09 · How many candidates Best-of-N needs

numeric answer · tolerance ±0.5

Each independent candidate succeeds with probability $p = 0.15$ , and the verifier detects success without error.

What is the minimum number of candidates for a success probability of at least $0.95$ ?

Number of candidates NAbsolute tolerance: ±0

Answer and explanation

Answer: 19.

$0.1\cdot200 + 0.3\cdot100 = 20 + 30 = 50$ , hence $19$ . Verified with minimum_samples_for_target. The assumptions are strong: independence, identical $p$ , a perfect verifier and cost outside the objective.

Question P10 · Why Best-of-N is not a bandit

single answer

Why is ordinary Best-of-N with a frozen LLM not a standard online multi-armed bandit?

One correct option1Because the number of candidates is finite2Because there is no finite set of unknown arms whose estimates are refined across rounds: this is repeated sampling from one policy plus selection by a verifier3Because the reward is binary4Because the model parameters are frozen and bandits require learning

Because the number of candidates is finite

Because there is no finite set of unknown arms whose estimates are refined across rounds: this is repeated sampling from one policy plus selection by a verifier

Because the reward is binary

Because the model parameters are frozen and bandits require learning

Answer and explanation

The correct option is Because there is no finite set of unknown arms whose estimates are refined across rounds: this is repeated sampling from one policy plus selection by a verifier.

A bandit problem appears when the system repeatedly chooses among several models, prompt variants, temperatures or routes and updates those choices from feedback.

Question P11 · The unbiased pass@k estimator

coding task

Specification: a task produced $n$ programs of which $c$ passed the tests, $n \ge k$ . The finite-sample estimator is $\widehat{\operatorname{pass@}k} = 1 - \binom{n-c}{k}\big/\binom{n}{k}$ , with $\binom{m}{k} = 0$ for $m < k$ .

Input format: one line — $n$ , $c$ , $k$ . Output format: one line — the estimate (6 decimals).

Starter code:

from math import comb

def pass_at_k(n: int, c: int, k: int) -> float:
    # YOUR CODE HERE
    raise NotImplementedError

if __name__ == "__main__":
    n, c, k = (int(x) for x in input().split())
    print(f"{pass_at_k(n, c, k):.6f}")

Open tests:

stdin	stdout
`10 3 4`	`0.833333`
`8 2 2`	`0.464286`
`5 0 3`	`0.000000`
`6 6 2`	`1.000000`

Your answer or notes

Answer and explanation

One correct implementation is:

from math import comb

def pass_at_k(n: int, c: int, k: int) -> float:
    if n < 1 or not 0 <= c <= n or not 1 <= k <= n:
        raise ValueError("need n >= 1, 0 <= c <= n, and 1 <= k <= n")
    failures = n - c
    if failures < k:
        return 1.0
    return 1.0 - comb(failures, k) / comb(n, k)

The formula is the probability that a size- $\Delta_a$ subset drawn without replacement from the observed $n$ programs contains at least one of the $c$ successes. For $\Omega(\log T)$ , the probability of drawing only failures is $\binom{7}{4}/\binom{10}{4}=1/6$ , so the estimate is $5/6\approx0.833333$ .

Plugging $\widehat p = c/n$ into $1-(1-\widehat p)^k$ would give $1-0.7^4 = 0.7599$ on the first test — noticeably lower. The combinatorial formula is the probability that a random size- $k$ subset drawn without replacement contains at least one success.

Question P12 · Entropy collapse: observation or theorem

single answer

A 2026 preprint reports a substantial entropy drop across several RLVR configurations on mathematics. How does the course ask you to read that?

One correct option1As proof that any GRPO run collapses entropy2As a primary empirical report from one specific paper, not proof that group-relative optimization must collapse entropy3As an artifact of the chosen optimizer, removable by changing the learning rate4As a theoretical consequence of PPO clipping

As proof that any GRPO run collapses entropy

As a primary empirical report from one specific paper, not proof that group-relative optimization must collapse entropy

As an artifact of the chosen optimizer, removable by changing the learning rate

As a theoretical consequence of PPO clipping

Answer and explanation

The correct option is As a primary empirical report from one specific paper, not proof that group-relative optimization must collapse entropy.

A falling mean entropy is not itself an error: a successful policy often should grow more confident. The problem is diversity vanishing before the solution space has been explored, or concentration driven by an update pathology.