---
kind: concept
slug: multi-armed-bandit
title: Multi-armed bandit
summary: >-
  Sequential choice among K arms with unknown mean payoffs. Covers the trade-off between cumulative reward and accurate estimates of every arm, a weighted objective that balances the two (ForcingBalance), and a bandit task used to test whether GPT-3 explores like people. Author-reported results only.
tags: [sequential-decision-making, exploration, regret, behavioral-evaluation]
papers: ["2206.14576", "2605.00488"]
related: [thompson-sampling, active-learning, llm-evaluation]
status: draft
updated_at: 2026-10-24
---

## 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 [arxiv: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 [arxiv: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 [arxiv: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
[arxiv: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 [arxiv:2605.00488 §3].
The authors call it an adaptation of the forcing idea in GAFS of Antos et al.
[arxiv: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
[arxiv:2605.00488 §4, thm. 1]. Card: [Trading off rewards and errors in multi-armed bandits](/papers/2605.00488).

### 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 [arxiv:2605.00488 §5.2].
- GAFS, adapted to minimise error, which is accurate but collects less reward
  [arxiv:2605.00488 §5.2].
- Uniform sampling, which the paper reports as close to GAFS on error
  [arxiv: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
[arxiv: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
[arxiv: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](/papers/2206.14576).

Caveats for anyone who runs this probe:

- The paper does not state the reward means or noise level of the arms
  [arxiv: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 [arxiv:2206.14576 §Results / Information search].

## When to use which

| Situation | Use | Why |
|---|---|---|
| You need both reward and reliable estimates of every arm, and can set a weight | Forced sampling with weight `w` [arxiv:2605.00488 §2] | In the paper's educational study at `w = 0.6` it had the lowest regret of the compared methods; at `w = 0.95` it collected more reward than GAFS and kept the ranking error close [arxiv:2605.00488 §5.2]. Author-reported, one real study and one synthetic setting. |
| Only cumulative reward matters | A reward-focused method such as UCB | The paper's table has UCB with the highest reward and the worst estimation error [arxiv:2605.00488 §5.2]. The paper does not argue for its own method when reward is the only goal. |
| Only accurate estimates matter, reward is secondary | Error-focused balanced sampling | At `w = 0` the optimal allocation favours the arm with the largest variance, not the best arm [arxiv:2605.00488 §5.1]. An agent that wants balanced estimates should check this before adopting the paper's `w` range. |
| You need a stated regret guarantee | Forced sampling with `lambda_min > 0` and Assumption 1 satisfied | The theorem needs `lambda_min > 0` and the optimal allocation inside the restricted simplex [arxiv:2605.00488 §4, thm. 1]. The experiments use `lambda_min = 0`, which the theorem does not cover [arxiv:2605.00488 §4, rem. 2] [arxiv:2605.00488 §5.1]. |
| You want to know whether a language model explores like people | The horizon probe [arxiv:2206.14576 §Results / Information search] | The design separates random from directed exploration. For GPT-3 Davinci it found the random kind and not the directed kind. That is one model and one setup, and the paper gives no variance across runs. |
| Rewards are heavy-tailed or unbounded | Not covered by this method | The setting assumes bounded support in `[0, 1]`, extended to sub-Gaussian arms [arxiv:2605.00488 §2]. |
| Tight per-step compute budget | Benchmark before adopting | Each step solves an optimisation over the arms [arxiv:2605.00488 §3]. The paper reports no runtime [arxiv:2605.00488 §3]. |

## 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 [arxiv: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.

```pseudocode
# 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` [arxiv:2605.00488 §4, thm. 1] [arxiv: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` [arxiv:2605.00488 §4, rem. 2]
  [arxiv: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
  [arxiv:2206.14576 §Results / Information search]. See the caveats above.

## Papers

- [Trading off rewards and errors in multi-armed bandits](/papers/2605.00488): 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](/papers/2206.14576): tests GPT-3 on a two-armed horizon bandit among other psychology tasks; reports random but not directed exploration (author-reported, one model).