What does Bayesian Search and Optimal Stopping conclude, in numbers, about “Multi-Armed Bandits: Gittins Indices, Thompson Sampling and the Regret Lower Bound”?
Answer: The Gittins index breaks the multi-armed bandit into one-armed problems: each machine's index is the reward that leaves one indifferent between "continue" and "retire on a fixed reward"; the index exceeds the posterior mean, and the exploration bonus shrinks as knowledge grows and grows as the future carries more weight. The optimality of the index policy requires independent arms, frozen arms when not chosen, fixed discounting, an infinite horizon and no switching costs. In the example with discount factor 0.9, the greedy policy loses only about 0.3 % relative to the Gittins policy, while Thompson sampling and UCB1 explore too much. The Lai–Robbins bound is an asymptotic statement; at finite \(T\) the regret of Thompson sampling can lie below \(c\ln T\), while UCB1 lies far above it. The next chapter connects "whether to keep pulling a machine" with sunk costs.
Scope of the numbers: Marked boxes separate published evidence, runnable Python calculations (17 programs, all checked), classical sources and the author's hypotheses.
Data table
The numbers below are printed verbatim by the chapter's Python program and can be reproduced by running it. standard-library Python only
| a | b | mean | g = 0.90 | bonus | g = 0.95 | bonus |
| 1 | 1 | 0.500 | 0.7029 | +0.2029 | 0.7614 | +0.2614 |
| 2 | 2 | 0.500 | 0.6346 | +0.1346 | 0.6810 | +0.1810 |
| 5 | 5 | 0.500 | 0.5676 | +0.0676 | 0.5957 | +0.0957 |
| 10 | 10 | 0.500 | 0.5373 | +0.0373 | 0.5544 | +0.0544 |
| 20 | 20 | 0.500 | 0.5197 | +0.0197 | 0.5295 | +0.0295 |
| 1 | 2 | 0.333 | 0.5001 | +0.1668 | 0.5601 | +0.2268 |
| 2 | 1 | 0.667 | 0.8001 | +0.1334 | 0.8381 | +0.1715 |
| 3 | 7 | 0.300 | 0.3647 | +0.0647 | 0.3937 | +0.0937 |
| restart-in-state check, Beta(1, 1), g = 0.90: 0.7029 | ||||||
| unknown arm Beta(1, 1) against a known arm paying 0.6, g = 0.90: | ||||||
| always the known arm: 6.000; best policy: 6.388 |
Key formula
Show the full program
# Gittins index of a Bernoulli arm with posterior Beta(a, b), discount g. Calibration:
# the index is the retirement reward lam that makes "continue" and "retire" equally good
# at the start; tree of (successes, failures) to depth H; bisection on lam.
# Check: restart-in-state (Katehakis & Veinott 1987) by value iteration.
import math
def calib_value(a, b, g, lam, H):
nxt = [max(lam, (a + s) / (a + b + H)) / (1 - g) for s in range(H + 1)]
for d in range(H - 1, -1, -1):
nxt = [max(lam / (1 - g), m + g * (m * nxt[s + 1] + (1 - m) * nxt[s]))
for s, m in ((s, (a + s) / (a + b + d)) for s in range(d + 1))]
return nxt[0]
def gittins(a, b, g, tol=1e-6):
H, lo, hi = int(math.log(1e-7) / math.log(g)), a / (a + b), 1.0
while hi - lo > tol:
lam = (lo + hi) / 2
lo, hi = (lam, hi) if calib_value(a, b, g, lam, H) > lam / (1 - g) + 1e-12 \
else (lo, lam)
return (lo + hi) / 2
def restart_index(a, b, g, H=150, sweeps=300):
v = [[0.0] * (d + 1) for d in range(H + 1)]
for _ in range(sweeps):
root = v[0][0]
for d in range(H, -1, -1):
for s in range(d + 1):
m = (a + s) / (a + b + d)
go = m + g * (m * v[d + 1][s + 1] + (1 - m) * v[d + 1][s]) if d < H else 0
v[d][s] = go if d == 0 else max(go, root)
return (1 - g) * v[0][0]
if __name__ == "__main__":
print(" a b mean g = 0.90 bonus g = 0.95 bonus")
for a, b in ((1, 1), (2, 2), (5, 5), (10, 10), (20, 20), (1, 2), (2, 1), (3, 7)):
m = a / (a + b); g1, g2 = gittins(a, b, 0.9), gittins(a, b, 0.95)
print(f" {a:3d} {b:3d} {m:.3f} {g1:.4f} {g1 - m:+.4f}"
f" {g2:.4f} {g2 - m:+.4f}")
print(f"restart-in-state check, Beta(1, 1), g = 0.90: {restart_index(1, 1, 0.9):.4f}")
print("unknown arm Beta(1, 1) against a known arm paying 0.6, g = 0.90:")
print(f" always the known arm: {0.6 / (1 - 0.9):.3f};"
f" best policy: {calib_value(1, 1, 0.9, 0.6, 156):.3f}")Single source and citation
Fan, Y. (2026). Bayesian Search in Unknown Landscapes, Optimal Stopping and Gittins Indices (Version 1.0.0), Chapter 4: Multi-Armed Bandits: Gittins Indices, Thompson Sampling and the Regret Lower Bound. 5D Library. https://doi.org/10.5281/zenodo.23810102
DOI: 10.5281/zenodo.23810102 · Read the monograph · 5DL-B-042 · v1.0.0 · CC-BY-NC-ND-4.0
BibTeX
@book{fan2026042,
author = {Fan, Yafu},
title = {Bayesian Search in Unknown Landscapes, Optimal Stopping and Gittins Indices},
year = {2026},
publisher = {5D Library},
edition = {1.0.0},
doi = {10.5281/zenodo.23810102},
url = {https://doi.org/10.5281/zenodo.23810102}
}Other chapter answers in this book
- Chapter 1 · The Secretary Problem and 1/e: When to Stop If You See Only Ranks and Cannot Go Back
- Chapter 2 · Variants of the Secretary Problem and How People Stop
- Chapter 3 · Bayesian Search: Where to Look, and What Not Finding Means
- Chapter 5 · Sunk Costs: Rational Persistence, Fallacious Persistence and Stop-Loss Boundaries Set in Advance
- Chapter 6 · Applications: Testing Lanes and Selecting People
- Chapter 8 · Practice and a Pre-Registered Trial