5D Library › Bayesian Search in Unknown Landscapes, Optimal Stopping and Gittins Indices · 中文
Chapter 4 Multi-Armed Bandits: Gittins Indices, Thompson Sampling and the Regret Lower Bound
An old problem
There are several slot machines, each paying out with a different probability that is unknown in advance, and only one lever can be pulled at a time. Pulling only the machine that now looks best (exploitation) may mean never discovering that another is better; giving pulls to machines one knows little about (exploration) costs something now. This is the multi-armed bandit problem. Thompson in 1933, discussing the comparison of two treatments, first proposed allocating the next patient according to the posterior probability that one treatment is better than the other (Thompson 1933); Robbins in 1952 formulated it as a general problem of the sequential design of experiments (Robbins 1952).
Chapter 5 of Volume 32, Algorithmic Game Theory, Braess’s Paradox and the Price of Anarchy in Traffic and Attention Networks, has already compared four rules by program in the setting of recommendation traffic — greedy, -greedy, UCB1 and Thompson sampling — finding that exploitation without exploration locks exposure onto content that was lucky early on, and that UCB1 over-explores when click rates are low. This chapter does not repeat that comparison. It discusses two questions instead: under what conditions an exact optimal solution exists (the Gittins index), and how large the cost of exploration must be whatever rule is used (the lower bound of Lai and Robbins).
The Gittins index
Gittins and Jones proposed in 1974, in the proceedings of a European meeting of statisticians, and Gittins proved systematically in 1979 in the Journal of the Royal Statistical Society, Series B, that under a certain set of conditions the optimal policy for the multi-armed bandit can be found as follows: compute a single number for each machine separately, its Gittins index, and always pull the machine with the largest index (Gittins and Jones 1974; Gittins 1979). The result was surprising, because it breaks a problem in which all machines are entangled into separate one-armed problems. Whittle gave a short proof in 1980 (Whittle 1980), and Weber in 1992 an intuitive proof that needs almost no calculation (Weber 1992).
Calculation
Calibration. Compare a machine with a “retirement” option that pays a fixed every period for ever. If, in the present state, continuing to pull the machine is exactly as good as retiring now, that is the Gittins index of the state. For a Bernoulli machine the state is a posterior beta distribution (as if successes and failures had been seen), with posterior mean . With discount factor the value satisfies Truncating deep enough (), bisection finds the at which the two terms are equal. Restart-in-state is another algorithm: in every state one may either continue or go back to the starting state and begin again; the optimal value of that problem multiplied by is the index of the starting state (Katehakis and Veinott 1987). The program computes the index of at both ways as a check, and then the choice between an unknown machine and a machine known to pay out with probability 0.6.
# 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}")
# 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.388The index always exceeds the posterior mean, and the excess can be read as an exploration bonus. It follows two regularities. First, the less one knows, the larger the bonus: with mean 0.5 throughout, the index of at is 0.7029 (a bonus of 0.203), that of 0.5676 (0.068), and that of only 0.5197 (0.020). Second, the more weight the future carries, the larger the bonus: raising from 0.90 to 0.95 raises the index of from 0.7029 to 0.7614. The restart method gives exactly the same 0.7029 as calibration.
The last two lines show what the index means. Take a machine never pulled (mean 0.5) and a machine known to pay with probability 0.6. Looking only at means, one should always pull the known machine, for a discounted total of 6.000; but the unknown machine’s index, 0.7029, exceeds 0.6, so the optimal policy tries the unknown machine first and returns to the known one if results are poor, for a total of 6.388, about 6.5 % more. The extra is the value of information.
When is the index policy optimal?
The optimality of the Gittins index requires a definite set of conditions: the machines are independent; machines not pulled do not change state; rewards are discounted by a fixed factor over an infinite horizon; one machine is pulled at a time; switching between machines costs nothing. If any of these fails, an index policy is in general no longer exactly optimal and serves only as an approximation (Gittins et al. 2011). With a finite undiscounted horizon (“100 pulls left”), for instance, the index must depend on the number of pulls remaining and can be computed only approximately; when switching has a cost (changing product lines means reorganising a team), the optimal policy becomes “stickier”.
Calculation
Two Bernoulli machines whose payout probabilities are each drawn uniformly from 0 to 1, a prior that every policy is told; discount factor 0.9 and 60 pulls (, so later rewards are negligible). The Gittins index (computed for the whole state tree at once on a grid of with step 0.0025), a greedy policy that looks only at posterior means, Thompson sampling and UCB1 are compared. In each of the 10,000 simulated runs, the -th pull of a machine gives the same result under every policy (common random numbers), which reduces the error of the comparison.
# Two Bernoulli arms, success probabilities ~ Uniform(0, 1) (known prior); reward
# discounted with g = 0.9 over 60 pulls. Gittins index (optimal here), greedy on the
# posterior mean, Thompson sampling, UCB1; common random numbers across policies.
# Gittins table: for each lam on a grid of step 0.0025, one backward pass over the
# (successes, failures) tree marks the states where continuing beats retiring.
import math, random
G, T, H, STEP = 0.9, 60, 213, 0.0025
def gittins_table():
idx = {}
for j in range(1, int(1 / STEP)):
lam = j * STEP; ret = lam / (1 - G)
nxt = [max(lam, (1 + s) / (2 + H)) / (1 - G) for s in range(H + 1)]
for d in range(H - 1, -1, -1):
cur = []
for s in range(d + 1):
m = (1 + s) / (2 + d); go = m + G * (m * nxt[s + 1] + (1 - m) * nxt[s])
if d <= T and go > ret:
idx[(s, d - s)] = lam + STEP / 2
cur.append(max(ret, go))
nxt = cur
return idx
def play(policy, p, u, rng, idx):
s, f, n, total = [0, 0], [0, 0], [0, 0], 0.0
for t in range(T):
if policy == "Gittins":
sc = [idx.get((s[i], f[i]), STEP / 2) for i in (0, 1)]
elif policy == "greedy":
sc = [(1 + s[i]) / (2 + n[i]) for i in (0, 1)]
elif policy == "Thompson":
sc = [rng.betavariate(1 + s[i], 1 + f[i]) for i in (0, 1)]
else: # UCB1, each arm once first
sc = [math.inf if n[i] == 0
else s[i] / n[i] + math.sqrt(2 * math.log(t) / n[i]) for i in (0, 1)]
i = 0 if sc[0] > sc[1] else 1 if sc[1] > sc[0] else rng.randrange(2)
win = u[i][n[i]] < p[i]
s[i] += win; f[i] += 1 - win; n[i] += 1; total += G ** t * win
return total
if __name__ == "__main__":
idx = gittins_table(); rng = random.Random(1979); runs = 10000
print(f"grid Gittins index, Beta(1, 1): {idx[(0, 0)]:.4f};"
f" Beta(2, 2): {idx[(1, 1)]:.4f}")
pols = ("Gittins", "greedy", "Thompson", "UCB1")
res = {k: [] for k in pols}; best = 0
for _ in range(runs):
p = [rng.random(), rng.random()]
u = [[rng.random() for _ in range(T)] for _ in (0, 1)]
best += max(p) * (1 - G ** T) / (1 - G)
for k in pols:
res[k].append(play(k, p, u, random.Random(rng.random()), idx))
print(f"discounted reward, {runs:,} runs; knowing the better arm: {best / runs:.3f}")
print(" policy mean difference from Gittins (SE)")
for k in pols:
d = [a - b for a, b in zip(res[k], res["Gittins"])]; md = sum(d) / runs
se = math.sqrt(sum((x - md) ** 2 for x in d) / (runs - 1) / runs)
print(f" {k:9s} {sum(res[k]) / runs:.3f} {md:+.3f} ({se:.3f})")
# grid Gittins index, Beta(1, 1): 0.7037; Beta(2, 2): 0.6338
# discounted reward, 10,000 runs; knowing the better arm: 6.660
# policy mean difference from Gittins (SE)
# Gittins 6.079 +0.000 (0.000)
# greedy 6.058 -0.021 (0.006)
# Thompson 5.814 -0.265 (0.006)
# UCB1 5.661 -0.418 (0.007)The grid index of is 0.7037, within grid precision of the exact 0.7029. Knowing in advance which machine is better would give an average discounted total of 6.660; the Gittins policy obtains 6.079, the highest of the four, as theory says it should. The greedy policy loses only 0.021 (standard error 0.006), about 0.3 %; Thompson sampling loses 0.265 and UCB1 0.418.
This result is easily misread. It does not say that Thompson sampling and UCB1 are poor rules; it says that the objectives differ. A discount factor of 0.9 amounts to looking only about ten steps ahead, where exploration is worth little and a greedy policy that hardly explores is close to optimal; Thompson sampling and UCB1 were designed for “undiscounted cumulative loss over a long horizon”, and under this discounted objective they explore too much. Conversely, in the recommendation example of Volume 32 and in the regret comparison below, a greedy policy that does not explore over a long horizon loses a great deal. Before choosing a rule, one must say which objective is being optimised.
Regret and its lower bound
A different kind of analysis uses neither prior nor discounting, but looks at regret: the expected reward lost over tries by not always pulling the best machine.
Evidence
Lower and upper bounds. Lai and Robbins proved in 1985 that for any “consistent” policy — one whose regret grows more slowly than any positive power of on every problem — the regret grows at least like as , with constant , where is the gap in expected reward between machine and the best, and is the relative entropy between two Bernoulli distributions; they also gave rules that achieve this rate (Lai and Robbins 1985). Auer, Cesa-Bianchi and Fischer in 2002 gave the simple UCB1 rule (pull the machine with the largest “average reward ”) with a logarithmic regret bound that holds for every finite , though with a constant larger than the lower bound (Auer et al. 2002). Agrawal and Goyal in 2012 proved the first logarithmic regret bound for Thompson sampling, for two machines (Agrawal and Goyal 2012); Kaufmann, Korda and Munos showed in the same year that for Bernoulli machines Thompson sampling attains the Lai–Robbins bound asymptotically (Kaufmann et al. 2012).
Calculation
Two Bernoulli machines with payout probabilities (0.60, 0.50) and (0.60, 0.55). Thompson sampling (beta(1, 1) priors) and UCB1 are each simulated 100 times for 20,000 steps; the average regret at and is expressed as a multiple of and compared with the Lai–Robbins constant. The values are illustrative.
# Lai-Robbins: for consistent policies regret(T)/ln T -> at least (mu* - mu)/KL(mu, mu*).
# Thompson sampling (Beta(1, 1) priors) and UCB1, two Bernoulli arms, 100 runs of 20,000
# pulls each (illustrative values); regret = (mu* - mu) x pulls of the worse arm.
import math, random
def kl(p, q):
return p * math.log(p / q) + (1 - p) * math.log((1 - p) / (1 - q))
def run(policy, mus, T, rng, checks):
s, n, out = [0, 0], [0, 0], {}
for t in range(1, T + 1):
if policy == "Thompson":
i = 0 if rng.betavariate(1 + s[0], 1 + n[0] - s[0]) > \
rng.betavariate(1 + s[1], 1 + n[1] - s[1]) else 1
elif t <= 2:
i = t - 1
else:
i = max((0, 1), key=lambda j: s[j] / n[j] + math.sqrt(2 * math.log(t) / n[j]))
s[i] += rng.random() < mus[i]; n[i] += 1
if t in checks:
out[t] = (max(mus) - min(mus)) * n[mus.index(min(mus))]
return out
if __name__ == "__main__":
rng = random.Random(1985); checks = (1000, 5000, 20000)
for mus in ([0.60, 0.50], [0.60, 0.55]):
gap = mus[0] - mus[1]; c = gap / kl(mus[1], mus[0])
print(f"arms {mus}: Lai-Robbins constant (mu* - mu)/KL = {c:.2f};"
f" bound at T = 20,000: {c * math.log(20000):.1f}")
for pol in ("Thompson", "UCB1"):
reg = {t: 0.0 for t in checks}
for _ in range(100):
for t, r in run(pol, mus, 20000, rng, checks).items():
reg[t] += r / 100
print(f" {pol:8s}" + "".join(f" T={t:5d}: regret {reg[t]:6.1f}"
f" ({reg[t] / math.log(t):5.2f} ln T)"
for t in checks[1:]))
# arms [0.6, 0.5]: Lai-Robbins constant (mu* - mu)/KL = 4.90; bound at T = 20,000: 48.5
# Thompson T= 5000: regret 16.9 ( 1.98 ln T) T=20000: regret 21.9 ( 2.21 ln T)
# UCB1 T= 5000: regret 64.2 ( 7.54 ln T) T=20000: regret 111.3 (11.24 ln T)
# arms [0.6, 0.55]: Lai-Robbins constant (mu* - mu)/KL = 9.72; bound at T = 20,000: 96.2
# Thompson T= 5000: regret 25.9 ( 3.04 ln T) T=20000: regret 35.5 ( 3.59 ln T)
# UCB1 T= 5000: regret 62.2 ( 7.31 ln T) T=20000: regret 139.4 (14.07 ln T)For (0.60, 0.50) the Lai–Robbins constant is 4.90, and at , . UCB1’s regret is 111.3, 11.24 times , far above the constant, and the multiple is still growing: UCB1’s exploration bonus is too large for this kind of problem, consistent with the finding in Volume 32. Thompson sampling’s regret is only 21.9, 2.21 times — below the constant 4.90. This does not contradict the theorem: the Lai–Robbins bound is a limit statement as , and at finite the regret can lie below ; Thompson sampling’s multiple rises from 1.98 to 2.21, slowly approaching the constant. When the gap shrinks to 0.05 (0.60 against 0.55) the constant doubles to 9.72, and the multiples are 3.59 for Thompson sampling and 14.07 for UCB1. The smaller the gap, the more exploration is needed; that is what in the denominator of the bound means.
Note
Two kinds of “optimal”. The Gittins index is exactly optimal in a Bayesian problem with a prior and discounting; the Lai–Robbins bound states the minimal cost of exploration that no reasonable rule can escape when there is no prior and the horizon tends to infinity. They answer different questions and cannot stand in for each other. Real problems usually lie in between: finite horizons, not necessarily discounted, machines that may be correlated, and payoffs that may change over time.
Summary
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 the regret of Thompson sampling can lie below , while UCB1 lies far above it. The next chapter connects “whether to keep pulling a machine” with sunk costs.
References
Fan, Y. (2026). Bayesian Search in Unknown Landscapes, Optimal Stopping and Gittins Indices: Exploration–Exploitation Trade-offs and Sunk-Cost Truncation in Statistical Decision Theory [未知地形中的贝叶斯搜索、秘书问题与吉廷斯指数] (Version 1.0.0). 5D Library. https://doi.org/10.5281/zenodo.23810102 · Licensed under Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International (CC BY-NC-ND 4.0).