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, ε\varepsilon-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 λ\lambda every period for ever. If, in the present state, continuing to pull the machine is exactly as good as retiring now, that λ\lambda is the Gittins index of the state. For a Bernoulli machine the state is a posterior beta distribution Beta(a,b)\mathrm{Beta}(a, b) (as if a−1a-1 successes and b−1b-1 failures had been seen), with posterior mean m=a/(a+b)m = a/(a+b). With discount factor gg the value satisfies V(a,b)=max⁡{λ1−g,m+g[mV(a+1,b)+(1−m)V(a,b+1)]}.V(a, b) = \max\!\left\{\frac{\lambda}{1-g},\; m + g\,[\,m\,V(a+1, b) + (1-m)\,V(a, b+1)\,]\right\}. Truncating deep enough (gH<10−7g^H < 10^{-7}), bisection finds the λ\lambda 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 1−g1-g is the index of the starting state (Katehakis and Veinott 1987). The program computes the index of Beta(1,1)\mathrm{Beta}(1, 1) at g=0.9g = 0.9 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.388

The 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 Beta(1,1)\mathrm{Beta}(1, 1) at g=0.9g = 0.9 is 0.7029 (a bonus of 0.203), that of Beta(5,5)\mathrm{Beta}(5, 5) 0.5676 (0.068), and that of Beta(20,20)\mathrm{Beta}(20, 20) only 0.5197 (0.020). Second, the more weight the future carries, the larger the bonus: raising gg from 0.90 to 0.95 raises the index of Beta(1,1)\mathrm{Beta}(1, 1) 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 (0.960≈0.0020.9^{60} \approx 0.002, so later rewards are negligible). The Gittins index (computed for the whole state tree at once on a grid of λ\lambda 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 kk-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 Beta(1,1)\mathrm{Beta}(1, 1) 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.

Left: the Gittins index against the number of pseudo-observations a + b with posterior mean 0.5 (g = 0.90 and 0.95); the more one knows, the smaller the exploration bonus. Right: average regret of Thompson sampling and UCB1 with two Bernoulli machines (0.6 and 0.5; 30 simulated runs each), with the Lai–Robbins asymptotic lower bound c\ln T (dashed).

Regret and its lower bound

A different kind of analysis uses neither prior nor discounting, but looks at regret: the expected reward lost over TT 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 TT on every problem — the regret grows at least like ln⁡T\ln T as T→∞T \to \infty, with constant ∑iΔi/KL(μi,μ*)\sum_i \Delta_i/\mathrm{KL}(\mu_i, \mu^*), where Δi\Delta_i is the gap in expected reward between machine ii and the best, and KL\mathrm{KL} 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 +2ln⁡t/ni+ \sqrt{2\ln t/n_i}”) with a logarithmic regret bound that holds for every finite TT, 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, O(ln⁡T/Δ+1/Δ3)O(\ln T/\Delta + 1/\Delta^3) 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 T=5,000T = 5{,}000 and 20,00020{,}000 is expressed as a multiple of ln⁡T\ln T 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 T=20,000T = 20{,}000, cln⁡T=48.5c\ln T = 48.5. UCB1’s regret is 111.3, 11.24 times ln⁡T\ln T, 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 ln⁡T\ln T — below the constant 4.90. This does not contradict the theorem: the Lai–Robbins bound is a limit statement as T→∞T \to \infty, and at finite TT the regret can lie below cln⁡Tc\ln T; 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 KL\mathrm{KL} 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 TT the regret of Thompson sampling can lie below cln⁡Tc\ln T, while UCB1 lies far above it. The next chapter connects “whether to keep pulling a machine” with sunk costs.

References

Agrawal, Shipra, and Navin Goyal. 2012. “Analysis of Thompson Sampling for the Multi-Armed Bandit Problem.” Proceedings of the 25th Annual Conference on Learning Theory, Proceedings of machine learning research, vol. 23: 39.1–26.
Auer, Peter, Nicolò Cesa-Bianchi, and Paul Fischer. 2002. “Finite-Time Analysis of the Multiarmed Bandit Problem.” Machine Learning 47 (2–3): 235–56. https://doi.org/10.1023/A:1013689704352.
Gittins, J. C. 1979. “Bandit Processes and Dynamic Allocation Indices.” Journal of the Royal Statistical Society, Series B (Methodological) 41 (2): 148–77.
Gittins, J. C., and D. M. Jones. 1974. “A Dynamic Allocation Index for the Sequential Design of Experiments.” In Progress in Statistics, edited by J. Gani, K. Sarkadi, and I. Vincze. North-Holland.
Gittins, John, Kevin Glazebrook, and Richard Weber. 2011. Multi-Armed Bandit Allocation Indices. 2nd ed. Wiley.
Katehakis, Michael N., and Jr. Veinott Arthur F. 1987. “The Multi-Armed Bandit Problem: Decomposition and Computation.” Mathematics of Operations Research 12 (2): 262–68. https://doi.org/10.1287/moor.12.2.262.
Kaufmann, Emilie, Nathaniel Korda, and Rémi Munos. 2012. “Thompson Sampling: An Asymptotically Optimal Finite-Time Analysis.” Algorithmic Learning Theory (ALT 2012), 199–213. https://doi.org/10.1007/978-3-642-34106-9_18.
Lai, Tze Leung, and Herbert Robbins. 1985. “Asymptotically Efficient Adaptive Allocation Rules.” Advances in Applied Mathematics 6 (1): 4–22. https://doi.org/10.1016/0196-8858(85)90002-8.
Robbins, Herbert. 1952. “Some Aspects of the Sequential Design of Experiments.” Bulletin of the American Mathematical Society 58 (5): 527–35.
Thompson, William R. 1933. “On the Likelihood That One Unknown Probability Exceeds Another in View of the Evidence of Two Samples.” Biometrika 25 (3/4): 285–94. https://doi.org/10.1093/biomet/25.3-4.285.
Weber, Richard. 1992. “On the Gittins Index for Multiarmed Bandits.” The Annals of Applied Probability 2 (4): 1024–33.
Whittle, Peter. 1980. “Multi-Armed Bandits and the Gittins Index.” Journal of the Royal Statistical Society, Series B (Methodological) 42 (2): 143–49.

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).