Multi-armed bandit

Overview

A multi-armed bandit is a sequence of choices among K arms. Each arm has an unknown mean payoff mu_i and variance sigma_i^2, and the learner sees a payoff only after pulling that arm 2605.00488 §2. The usual goal is cumulative reward, which favours pulling the best-looking arm most of the time. A second goal is to estimate every arm's mean accurately, which favours balanced sampling. Known results already show that low regret and best-arm identification cannot both be optimal 2605.00488 §1.

The design choice this page covers is how to combine the two goals. The compiled paper writes the combined score as w * reward - (1 - w) * error, where w in (0, 1) sets the balance and the error term is a scaled sum of per-arm standard-deviation terms 2605.00488 §2, eq. 3-4.

Two papers with cards use this slug. The first proposes a learner for the combined objective. The second does not propose a learner: it gives a language model a two-armed bandit and reads off its exploration behaviour 2206.14576 §Results / Information search. The variants below are grouped by that difference.

Variants

Reward-error trade-off with forced sampling (ForcingBalance)

The method first forces each arm to be pulled at least eta * sqrt(t) times. When no arm is below that floor, it estimates the means and standard deviations and solves for the allocation that maximises the combined score. It then pulls the arm furthest below its target share 2605.00488 §3. The authors call it an adaptation of the forcing idea in GAFS of Antos et al. 2605.00488 §3. Its reported regret is bounded in three phases, with an asymptotic rate of n^(-1/2); the authors state this bound and its constants 2605.00488 §4, thm. 1. Card: Trading off rewards and errors in multi-armed bandits.

Comparators in the same paper

The paper compares against three baselines. None of them has a card here, so they are named only:

• UCB, which chases reward and gets the highest reward in the paper's educational table, but estimates poorly 2605.00488 §5.2.
• GAFS, adapted to minimise error, which is accurate but collects less reward 2605.00488 §5.2.
• Uniform sampling, which the paper reports as close to GAFS on error 2605.00488 §5.2.

The paper also reports that a naive optimistic bound on the combined score fails at small w, because it starves arms with wide confidence intervals 2605.00488 §3, app. C.

Bandit probe for a language model (horizon task)

This variant has no learning rule to implement. A language model is the decision-maker, and the bandit is a behavioural test. The task is two-armed: four forced trials, then one or six free choices. The forced trials show either equal or unequal information about the two arms [arxiv:2206.14576 §Results / Information search]. The paper names two kinds of exploration by the first free choice. In the equal-information case, picking the arm with the lower estimate counts as random exploration. In the unequal case, picking the less-observed arm counts as directed exploration. A logistic regression on reward difference, horizon and their interaction tests both 2206.14576 §Results / Information search.

Reported results for GPT-3 "Davinci", author-reported [arxiv:2206.14576 §Results / Information search]:

• Short horizon: regret not different from the human data (t(5566) = -0.043, p = .97). Long horizon: lower than humans in the initial trials (t(5550) = -4.07, p < .001).
• Pooled over all trials, mean regret was 2.72 for the model and 3.24 for the human reference.
• Random exploration: present (beta = 0.18, p < .001).
• Strategic random exploration (reward difference times horizon): absent (p = .14).
• Directed exploration: absent (p = .58).

The paper's headline reading is that the model beat humans on this bandit task. The probe is a description of one model under one prompt setup, not a statement about exploration in language models in general.

Card: Using cognitive psychology to understand GPT-3.

Caveats for anyone who runs this probe:

• The paper does not state the reward means or noise level of the arms 2206.14576 §Results / Information search. Reproduction needs them from elsewhere; the paper card records where they come from.
• The paper's text says the regression uses the estimated reward difference. The card's Paper vs code section records that the released analysis uses the environment's true difference. Pick one and state it.
• The number of tasks is not stated in the paper, and each item is one answer at temperature 0. The paper reports no run-to-run variance for this task. Pooled trial-level tests may overstate significance if trials within a run are correlated 2206.14576 §Results / Information search.

When to use which

Implementation sketch

The loop below is our own shape of the method, with the paper's sections cited per step. The paper does not fix the solver, the tie-breaking rule or the share convention in the tracking step 2605.00488 §3. The probe in the variant above needs no sketch: it is a prompt loop around a language model, and its environment is described in the paper's Results section.

# Combined score for a candidate allocation  [arxiv:2605.00488 §2, eq. 4]
def score(lam, means, stds, w):
    # Reward term: weighted mean payoff of the allocation  [§2]
    reward = w * dot(lam, means)
    # Error term: needs every lam_i > 0 when stds_i > 0  [§2, fn. 1]
    error = (1 - w) / K * sum(stds / sqrt(lam))
    return reward - error

# One step of the forced-sampling loop  [arxiv:2605.00488 §3]
def choose_arm(counts, t, eta, samples):
    # Forcing: pull the least-pulled arm while it is under the floor  [§3]
    least = argmin(counts)
    if counts[least] < eta * sqrt(t):
        return least
    # Tracking: best allocation under current estimates  [§3]
    lam_hat = argmax_over_simplex(score, means(samples), stds(samples))
    # Pull the arm furthest below its target share  [§3]
    return argmax(lam_hat - counts / t)

Contradictions

None known across the two cards. They measure different things: one reports a regret bound for an algorithm, the other reports how a language model behaves on a bandit task. Within each paper:

• The main text of 2605.00488 gives the second phase bound with lambda_min^2 in the denominator; the appendix restatement gives lambda_min^4 2605.00488 §4, thm. 1 2605.00488 app. B. Until the proof is checked, cite the bound with this difference flagged.
• The theorem of 2605.00488 requires lambda_min > 0, while every experiment uses lambda_min = 0 2605.00488 §4, rem. 2 2605.00488 §5.1.
• 2206.14576 names the regression variable as the estimated reward difference in the text, and the released analysis uses the true difference 2206.14576 §Results / Information search. See the caveats above.

Papers

• Trading off rewards and errors in multi-armed bandits: proposes a weighted reward-error objective and the ForcingBalance method, with author-reported regret bounds and educational experiments.
• Using cognitive psychology to understand GPT-3: tests GPT-3 on a two-armed horizon bandit among other psychology tasks; reports random but not directed exploration (author-reported, one model).