Skip to content
Bandit Lab, home

Methods, as submitted

The algorithms

Plain-language summaries and the key formulas for every bandit in the lab. Each coursework algorithm is ported line for line from the 2023 notebook, so the “Port notes” record what the submitted code actually does wherever it differs from the paper.

Task 1.1 · Li, Chu, Langford & Wang (2011)

Offline replay with delayed feedback

The log was collected by a policy that chose uniformly at random, so the events where a bandit's choice coincides with the logged arm are an unbiased sample of what it would have seen online. Replay walks through the log, asks the bandit for an arm at every event, and only counts (and reveals) the matches.

For delays, the coursework version schedules every logged event to be revealed d=delay(ai,ri)d = \text{delay}(a_i, r_i) steps after it is read, and at each step hands the bandit the first revealed event that matches its choice. Lost feedback (a negative delay) is never revealed. Unlike the instant replay, it wraps around the log until the requested number of rounds has matched.

read (ai,ri),di=delay(ai,ri),Q[ i+di ]←(ai,ri)a=π(⋅);if (a,r)∈Q[i]: update(a,r), t←t+1\begin{aligned} &\text{read } (a_i, r_i),\quad d_i = \text{delay}(a_i, r_i),\quad \mathcal{Q}[\,i + d_i\,] \leftarrow (a_i, r_i) \\ &a = \pi(\cdot);\quad \text{if } (a, r) \in \mathcal{Q}[i]:\ \text{update}(a, r),\ t \leftarrow t + 1 \end{aligned}

Port notes: what the 2023 code does

  • Revealed events whose arm differs from the bandit's choice in that step are discarded, not kept for later.
  • The lab adds a safety valve the notebook lacked: a delayed run that can never finish (for example 100% packet loss on an arm the bandit insists on) is stopped and reported as stalled.

Task 1.2 · Lancewicki, Segal, Koren & Mansour (ICML 2021)

Successive Elimination

ICML 2021 paper (opens in a new tab)

Keep a set of active arms and pull them round-robin. Every arm carries a confidence interval around its observed mean; as soon as one arm's upper bound drops below another arm's lower bound, it can't be the best and is removed for good. With delays, the intervals simply use the feedback observed so far.

μ^i=Sini,UCBi, LCBi=μ^i±2ln⁡TniS←S∖{ i:UCBi<max⁡j∈SLCBj }\begin{gathered} \hat\mu_i = \frac{S_i}{n_i},\qquad \mathrm{UCB}_i,\ \mathrm{LCB}_i = \hat\mu_i \pm \sqrt{\frac{2\ln T}{n_i}} \\ S \leftarrow S \setminus \{\, i : \mathrm{UCB}_i < \max_{j\in S} \mathrm{LCB}_j \,\} \end{gathered}

Port notes: what the 2023 code does

  • n_i counts observed (matched) feedback; the mean divides by n_i + 10⁻¹⁰.
  • The internal round counter t advances by |S| whenever all active arms have the same count; updates stop once t ≥ T.
  • The elimination log uses np.any on the arm indices, so a round that eliminates only arm 0 is not recorded (the elimination itself still happens).

Run SE in the lab and look inside →

Task 1.3 · Lancewicki et al. (ICML 2021)

Phased Successive Elimination

ICML 2021 paper (opens in a new tab)

Exploration happens in phases of growing length. At the start of phase ℓ the phase set SℓS_\ell copies the active set; each arm in it is pulled until it has enough observations for that phase, so an arm whose feedback is mostly lost cannot hold everyone else back. Elimination uses the same confidence intervals as SE.

arm i leaves Sℓ once ni  ≥  16log⁡10T2−2ℓ=16 4ℓlog⁡10T\text{arm } i \text{ leaves } S_\ell \text{ once } n_i \;\ge\; \frac{16 \log_{10} T}{2^{-2\ell}} = 16\,4^{\ell} \log_{10} T

Port notes: what the 2023 code does

  • The threshold uses log₁₀ T (the paper's analysis uses the natural log) and compares the arm's total observations, not its observations within the phase.
  • Arms are chosen from S_ℓ, so an arm eliminated from S mid-phase keeps being pulled until it reaches the phase threshold.

Run PSE in the lab and look inside →

Task 1.4 · Lancewicki et al. (ICML 2021)

Optimistic-Pessimistic Successive Elimination

ICML 2021 paper (opens in a new tab)

When feedback depends on the reward itself (say, non-clicks report late), the observed mean is biased. OPSE brackets the truth: missing feedback counts as 0 for a pessimistic lower bound and as 1 for an optimistic upper bound. Arms are eliminated only when even the optimistic view loses to another arm's pessimistic one.

μ^i−=Simi,μ^i+=Si+(mi−ni)miLCBi=μ^i−−2ln⁡Tmi,UCBi=μ^i++2ln⁡Tmi\begin{gathered} \hat\mu^-_i = \frac{S_i}{m_i},\qquad \hat\mu^+_i = \frac{S_i + (m_i - n_i)}{m_i} \\ \mathrm{LCB}_i = \hat\mu^-_i - \sqrt{\tfrac{2\ln T}{m_i}},\qquad \mathrm{UCB}_i = \hat\mu^+_i + \sqrt{\tfrac{2\ln T}{m_i}} \end{gathered}

Port notes: what the 2023 code does

  • m_i (pulls) is incremented inside play(), which replay calls for every logged event, matched or not. Pulls therefore outrun observations ten to one, the optimistic bounds stay near 1, and on the course log no arm was ever eliminated.
  • With every arm kept, OPSE pulls them evenly and its reward converges to the log's average click rate (0.2184 vs 0.2229).

Run OPSE in the lab and look inside →

Task 2 · after Agrawal & Goyal (COLT 2012)

Thompson Sampling (Gaussian)

COLT 2012 paper (opens in a new tab)

Each arm's mean reward gets a Gaussian prior and rewards a Gaussian likelihood, so the posterior stays Gaussian and updates in closed form. Every round, draw one plausible mean per arm from its posterior and play the largest draw: uncertain arms win often enough to be explored, good arms win most of the time.

θi∼N(μ0,τ2),r∣θi∼N(θi,σ2)θi∣data∼N ⁣(σ2μ0+τ2Siτ2ni+σ2,  σ2τ2τ2ni+σ2)\begin{gathered} \theta_i \sim \mathcal N(\mu_0, \tau^2),\qquad r \mid \theta_i \sim \mathcal N(\theta_i, \sigma^2) \\ \theta_i \mid \text{data} \sim \mathcal N\!\left(\frac{\sigma^2\mu_0 + \tau^2 S_i}{\tau^2 n_i + \sigma^2},\; \frac{\sigma^2\tau^2}{\tau^2 n_i + \sigma^2}\right) \end{gathered}

Port notes: what the 2023 code does

  • The notebook's defaults μ₀ = 2.22, τ = 0.416, σ = 4 were tuned on the course log. With σ = 4 the prior dominates for hundreds of pulls, which is why posterior means sit well above the true click rates in the lab.
  • Sampling uses the posterior variance as the normal's scale (rng.normal(mean, var)); the port keeps that.
  • The 10-repeat helper constructed every bandit as mab_class(n_arms, n_rounds, rng=rng), which handed TS μ₀ = 20,000 (and an integer array that truncates every update). That is why the notebook's 10-repeat TS curve sits near 0.22 while its single run scored 0.4218.

Run TS in the lab and look inside →

Task 3 · Dimakopoulou, Ren & Zhou (NeurIPS 2021)

Doubly-Adaptive Thompson Sampling

NeurIPS 2021 paper (opens in a new tab)

DATS replaces the plain posterior with doubly-robust (augmented inverse-propensity) estimates whose adaptive weights stabilise the variance, so the arm means it samples from support valid confidence intervals even though the data were collected adaptively. It samples with an inflation factor κ, keeps a uniform exploration floor γ, and eliminates arms that are very unlikely to be best.

Γ^s,a=μ^s,a+r−μ^s,aπs,a,μ^a=∑sπs,a Γ^s,a∑sπs,aσ^a2=∑sπs,a((Γ^s,a−μ^a)2+1)(∑sπs,a)2,πt+1,a=(1−γ) pa+γ∣A∣\begin{gathered} \hat\Gamma_{s,a} = \hat\mu_{s,a} + \frac{r - \hat\mu_{s,a}}{\pi_{s,a}},\qquad \hat\mu_a = \frac{\sum_s \sqrt{\pi_{s,a}}\,\hat\Gamma_{s,a}}{\sum_s \sqrt{\pi_{s,a}}} \\ \hat\sigma^2_a = \frac{\sum_s \pi_{s,a}\big((\hat\Gamma_{s,a}-\hat\mu_a)^2+1\big)}{\big(\sum_s \pi_{s,a}\big)^2},\qquad \pi_{t+1,a} = (1-\gamma)\,p_a + \frac{\gamma}{|\mathcal A|} \end{gathered}

Port notes: what the 2023 code does

  • The next arm is the one with the fewest multinomial draws, and its position in the active list is returned as if it were an arm id. Once arms are eliminated, DATS keeps playing arms 0 … |A|−1.
  • The Monte-Carlo propensity p_a is proportional to the index of each arm's largest normal sample (np.argmax(r, axis=1)) rather than to how often the arm's sample is the largest.
  • Every arm's pseudo-rewards use the reward just observed for the played arm, and n_pulls is incremented twice per update after the first round.
  • On the course log it deactivated arm 2, the best arm, at its 28th round. After its fifth elimination, at round 854, the position bug confined it to arms 0–4. That explains its 0.245, below plain TS. The revival keeps the behaviour and documents it, and DR-003 measures what each quirk costs over 20 seeds.

Run DATS in the lab and look inside →

Revival baseline · see Auer, Cesa-Bianchi & Fischer (2002)

ε-greedy (baseline, new in 2026)

Machine Learning 2002 paper (opens in a new tab)

With probability ε pull a uniformly random arm; otherwise pull the arm with the best running mean (unpulled arms count as infinitely good, so each is tried once). Not part of the coursework; included as a familiar yardstick.

at={uniform(A)w.p. εarg⁡max⁡iμ^iotherwisea_t = \begin{cases} \text{uniform}(\mathcal A) & \text{w.p. } \varepsilon \\ \arg\max_i \hat\mu_i & \text{otherwise} \end{cases}

Run ε-greedy in the lab and look inside →

Revival baseline · Auer, Cesa-Bianchi & Fischer (2002)

UCB1 (baseline, new in 2026)

Machine Learning 2002 paper (opens in a new tab)

Optimism in the face of uncertainty: add an exploration bonus that shrinks as an arm is pulled and play the arm with the highest mean plus bonus. Not part of the coursework; the classic reference point for SE.

at=arg⁡max⁡i  μ^i+cln⁡tni,c=2a_t = \arg\max_i \; \hat\mu_i + \sqrt{\frac{c \ln t}{n_i}},\qquad c = 2

Run UCB1 in the lab and look inside →