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

For each case, choose the most accurate model: ordinary bandit, contextual bandit, or Markov decision process (MDP).

1. For every independent request, a service chooses one of three models. Request features are known, one scalar score arrives after the response, and the choice does not affect later requests.

2. An agent opens web pages, extracts information, and decides which link to follow next.

3. Two fixed banners are rotated for an otherwise identical audience; only the click on the displayed banner is observed.

4. A dialogue system chooses an utterance, after which the user replies and changes the course of the conversation.

For every answer, name one assumption whose violation would change the model.

Select three correct statements.

1. A trajectory's pseudo-regret can be computed without knowing the true reward means.

2. The decomposition $R_T=\sum_a\Delta_a\mathbb{E}[N_a(T)]$ shows that an action with a small gap may be selected more often at a small immediate cost.

3. Sublinear regret means $R_T/T\to0$.

4. Logarithmic regret guarantees that an algorithm outperforms every other algorithm at every finite horizon.

5. Realized cumulative reward remains random under a fixed action sequence when rewards are noisy.

Select the two most accurate statements.

1. With fixed $\varepsilon>0$, ε-greedy continues to select suboptimal actions with positive frequency.

2. Optimistic initialization guarantees logarithmic regret in every non-stationary environment.

3. A constant step size can help under reward drift because it downweights old observations.

4. Pure greediness has linear regret on every individual run.

5. Any decaying $\varepsilon_t$ schedule automatically gives optimal regret.

An upper confidence bound (UCB) method is used in a stationary bandit; UCB1 is its classical variant.

Select three conditions or qualifications needed to read the UCB1 guarantee correctly.

1. Rewards are bounded; the standard theorem uses $[0,1]$.

2. Reward means remain unchanged over time.

3. The logarithmic bound is independent of action gaps $\Delta_a$.

4. Finite-horizon regret may remain substantial when two actions are nearly equal.

5. Any neural uncertainty score is automatically a UCB confidence bound.

6. The action set may change arbitrarily during learning while the classical UCB1 proof remains unchanged.

A Bernoulli action starts with a $\operatorname{Beta}(1,1)$ prior. After 8 successes and 2 failures, select three correct statements.

1. The posterior is $\operatorname{Beta}(9,3)$.

2. The algorithm always selects the largest posterior mean with no randomness.

3. On every round, it samples one plausible mean for every action.

4. A poorly observed action can be selected because its posterior is wide.

5. The 1933 publication date itself proves a modern logarithmic regret guarantee.

Select three correct statements.

1. If the prompt is context, a full response is one action, a scalar reward follows, and the episode ends, the external problem is a contextual bandit.

2. The whole-response abstraction implies that tokens cease to be sequential actions.

3. A multi-turn tool-using agent usually needs state that contains consequences of previous actions.

4. Choosing among several models for independent requests can be a contextual bandit.

5. Every Best-of-N procedure is automatically a multi-armed bandit.

Inverse propensity scoring (IPS) evaluates a target policy $\pi$ from logs generated by behavior policy $\mu$. Its self-normalized form is self-normalized inverse propensity scoring (SNIPS), while a doubly robust (DR) estimator combines reward predictions with propensity weights.

Select three correct statements.

1. Every pair $(x,a)$ with $\pi(a\mid x)>0$ requires $\mu(a\mid x)>0$.

2. Small behavior probabilities can produce large weights and high variance.

3. If behavior probabilities were not logged, they can always be reconstructed exactly from selected actions.

4. Self-normalized IPS is generally biased.

5. A doubly robust estimator creates an observed reward for an action that was never selected or modeled.

Item 6 refers to group relative policy optimization (GRPO). Select four correct statements.

1. Raising the temperature of a pure softmax with fixed logits flattens the distribution.

2. Temperature sampling from a frozen LLM updates the policy from reward by itself.

3. For independent candidates with the same success probability $p$, $1-(1-p)^N$ is the probability that the pool contains at least one success.

4. The finite-sample pass@$k$ estimator from $n$ candidates and $c$ successes is $1-\binom{n-c}{k}/\binom{n}{k}$.

5. Lower entropy always means a worse policy.

6. If all rewards in a GRPO group are equal, subtracting the group mean gives zero relative signal.

An action has been selected 4 times and its current estimate is $Q_4=0.35$. The fifth reward is $1$.

1. Compute $Q_5$ incrementally.

2. Find the sum of the first four rewards consistent with $Q_4$.

3. Verify the result with the direct mean of all five observations.

Three actions have means

Over $T=100$ rounds, expected selection counts are

1. Find $\mu^*$ and the gaps $\Delta_a$.

2. Compute expected regret.

3. How does regret change if 10 selections of action 2 are replaced by 10 selections of action 3?

At round $t=101$, two actions have estimates and counts

For

compute $I_1$ and $I_2$ to three decimals and state the selected action. Explain why the action with the lower sample mean may win.

Two Bernoulli actions use $\operatorname{Beta}(1,1)$ priors.

• action 1: 12 successes and 8 failures;
• action 2: 3 successes and 1 failure.

1. Write both posteriors.

2. Compute their means.

3. Which action has the larger posterior mean?

4. Why can Thompson sampling still select the other action?

The log contains:

1. Compute $w_i=\pi/\mu$.

2. Compute $\widehat V_{\mathrm{IPS}}=n^{-1}\sum_iw_ir_i$.

3. Compute $\widehat V_{\mathrm{SNIPS}}=\sum_iw_ir_i/\sum_iw_i$.

4. Compute the doubly robust (DR) estimate.

5. Which row contributes most to IPS variance, and why?

Two actions have scores $q=(0,1)$ and temperature $\tau=0.5$.

1. Compute $\pi^*(a)\propto\exp(q(a)/\tau)$.

2. If one independent candidate succeeds with probability $p=0.2$, find the chance of at least one success for $N=5$.

3. Find the smallest $N$ giving probability at least $0.9$.

4. For $n=10$, $c=2$, and $k=3$, compute the finite-sample pass@$k$ estimator.

5. Explain why parts 2 and 4 describe different statistical objects.

Implement:

import numpy as np

def pseudo_regret_curve(means: np.ndarray, actions: np.ndarray) -> np.ndarray:
    """Return cumulative pseudo-regret after each action."""
    ...

Requirements:

• means is a one-dimensional vector of means;
• actions is a one-dimensional integer vector;
• an invalid action index raises ValueError;
• the result has floating type and the same length as actions.

Check:

means = np.array([0.2, 0.5, 0.7])
actions = np.array([0, 2, 1])
# expected: [0.5, 0.5, 0.7]

Open checks:

np.testing.assert_allclose(
    pseudo_regret_curve([0.2, 0.5, 0.7], [0, 2, 1]),
    [0.5, 0.5, 0.7],
)

Implement:

import numpy as np

def run_epsilon_greedy(
    probabilities: np.ndarray,
    horizon: int,
    epsilon: float,
    seed: int,
) -> tuple[np.ndarray, np.ndarray]:
    """Return action and reward arrays."""
    ...

Rules:

• reward is rng.random() < probabilities[action];
• break greedy ties uniformly;
• update estimates as sample means;
• use np.random.default_rng(seed);
• decide whether to explore before sampling the reward.

Compare $\varepsilon=0$, $0.05$, and $0.2$ on one instance over at least 100 independent runs. Report mean pseudo-regret, not a conclusion from one seed.

Open checks:

actions, rewards = run_epsilon_greedy([0.1, 0.4, 0.6], 40, 0.1, 17)
assert actions.shape == (40,)
assert rewards.shape == (40,)
assert np.all((rewards == 0.0) | (rewards == 1.0))

Implement UCB1 for rewards in $[0,1]$:

import numpy as np

def run_ucb1(
    probabilities: np.ndarray,
    horizon: int,
    seed: int,
) -> tuple[np.ndarray, np.ndarray]:
    ...

Requirements:

1. select actions 0, 1, ..., K-1 on the first $K$ rounds;

2. then use $\widehat\mu_a+\sqrt{2\log t/N_a}$;

3. update sample means incrementally;

4. return action and reward arrays.

Verify that every action is selected at least once and cumulative pseudo-regret never decreases.

Open checks:

actions, rewards = run_ucb1([0.1, 0.4, 0.6], 3, 5)
assert np.array_equal(actions, [0, 1, 2])
assert rewards.shape == (3,)

Implement Beta–Bernoulli Thompson sampling:

import numpy as np

def run_thompson(
    probabilities: np.ndarray,
    horizon: int,
    seed: int,
    prior_alpha: float = 1.0,
    prior_beta: float = 1.0,
) -> tuple[np.ndarray, np.ndarray, np.ndarray, np.ndarray]:
    """Return actions, rewards, and final alpha/beta arrays."""
    ...

Increment alpha[action] after success and beta[action] after failure. Compare with UCB1 on several instances, including one with close means. Distinguish your empirical observation from a general guarantee.

Open checks:

actions, rewards, alpha, beta = run_thompson(
    [0.1, 0.4, 0.6], 10, 23
)
assert actions.shape == rewards.shape == (10,)
assert alpha.shape == beta.shape == (3,)
assert np.isclose((alpha + beta).sum(), 16.0)

Implement:

def ips_value(rewards, behavior_probs, target_probs) -> float:
    ...

def snips_value(rewards, behavior_probs, target_probs) -> float:
    ...

def doubly_robust_value(
    rewards,
    behavior_probs,
    target_probs,
    predictions_logged,
    predictions_target,
) -> float:
    ...

predictions_target[i] already contains $\sum_a\pi(a\mid x_i)\widehat r(x_i,a)$. Raise ValueError for non-positive behavior probabilities. Add an experiment where one propensity decreases from $0.5$ to $0.01$ and show how its IPS weight changes.

Open checks:

actual = ips_value(
    [1.0, 0.0, 1.0],
    [0.5, 0.25, 0.5],
    [1.0, 0.0, 0.5],
)
assert np.isclose(actual, 1.0)

Implement:

import numpy as np

def stable_softmax(logits, temperature=1.0) -> np.ndarray:
    ...

def categorical_entropy(probabilities) -> float:
    ...

def best_of_n_success(p: float, n: int) -> float:
    ...

def pass_at_k(n: int, c: int, k: int) -> float:
    ...

Requirements:

• softmax remains stable for large logits;
• entropy is in nats and uses $0\log0=0$;
• Best-of-N uses stable log1p/expm1 for small $p$ and large $N$;
• pass@$k$ uses $1-\binom{n-c}{k}/\binom{n}{k}$ or an equivalent stable product;
• invalid $n,c,k,p$ raise ValueError.

Verify that entropy rises for temperatures $0.5$, $1$, and $2$ with fixed logits, but do not infer anything about correctness or answer quality from that fact.

Open checks:

p = stable_softmax([1000.0, 1001.0])
assert np.isclose(p.sum(), 1.0)
assert np.all(p > 0.0)