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

abmeang = 0.90bonusg = 0.95bonus
110.5000.7029+0.20290.7614+0.2614
220.5000.6346+0.13460.6810+0.1810
550.5000.5676+0.06760.5957+0.0957
10100.5000.5373+0.03730.5544+0.0544
20200.5000.5197+0.01970.5295+0.0295
120.3330.5001+0.16680.5601+0.2268
210.6670.8001+0.13340.8381+0.1715
370.3000.3647+0.06470.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

\[V(a, b) = \max\!\left\{\frac{\lambda}{1-g},\; m + g\,[\,m\,V(a+1, b) + (1-m)\,V(a, b+1)\,]\right\}.\]
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