What does Weekly Quotas for Business Lines conclude, in numbers, about “Thompson Sampling against the Gittins Index: Two Ways of Keeping a Chance Open on the Same Decision”?

Answer: The relative entropy between the two lines is 0.00803, and the constant c of the lower bound is 7.47. Over a horizon of 100, the greedy rule's cumulative regret is 2.53 and Thompson sampling's 2.17, hardly different. Over 1000 units the first is 23.04 and the second 12.08; over 5000 units the first is 113.04 and the second only 20.85. The greedy rule's regret is roughly proportional to the horizon: 0.0226 per unit, a little over a third of the regret per unit of a rule that is always wrong, which means that on average more than a third of the units went to the worse line. From 1000 to 5000 units, Thompson sampling's regret grows by less than nine, exactly the pattern of logarithmic growth.

Scope of the numbers: Parameters are illustrative, and margins and costs are accounting points, not prices; all calculations are generated by the book's programs. It is not individual business advice, and changes to budgets or live systems need sign-off by the person in charge.

中文版

Data table

The numbers below are printed verbatim by the chapter's Python program and can be reproduced by running it. standard-library Python onlyprinted values that match the answer: 0.00803, 0.0226, 100, 1000, 113.04, 12.08

gap 0.06, KL 0.00803, Lai-Robbins constant c = 7.47
Tgreedythompsonc ln Tlinear
1002.532.1734.406.00
100023.0412.0851.6060.00
5000113.0420.8563.62300.00
greedy regret per unit at T = 5000: 0.0226
Show the full program
# Chapter 3. p32: regret over a long horizon, greedy against Thompson.
# Model: two lines with fixed rates 0.30 and 0.36 (as in p11), one unit
# per period, no discounting. Regret after T units = gap times the units
# spent on the worse line, averaged over runs (fixed seeds). Lai and
# Robbins (1985): any consistent rule has regret at least c ln T
# asymptotically, with
# c = gap / KL(0.30, 0.36) for Bernoulli lines. A rule that can lock in
# has regret growing in proportion to T instead.
import math
import random

P = (0.30, 0.36)
CHECK = (100, 1000, 5000)
RUNS = 200


def kl(p, q):
    return math.fsum((p * math.log(p / q),
                      (1 - p) * math.log((1 - p) / (1 - q))))


def run(rule, rng):
    s, f = [0, 0], [0, 0]
    worse, out = 0, {}
    for t in range(1, CHECK[-1] + 1):
        if rule == "greedy":
            sc = [(1 + s[i]) / (2 + s[i] + f[i]) for i in (0, 1)]
        else:
            sc = [rng.betavariate(1 + s[i], 1 + f[i]) for i in (0, 1)]
        i = 1 if sc[1] > sc[0] else 0
        if i == 0:
            worse += 1
        if rng.random() < P[i]:
            s[i] += 1
        else:
            f[i] += 1
        if t in CHECK:
            out[t] = (P[1] - P[0]) * worse
    return out


c = (P[1] - P[0]) / kl(P[0], P[1])
print("gap %.2f, KL %.5f, Lai-Robbins constant c = %.2f" % (
    P[1] - P[0], kl(P[0], P[1]), c))
print("%6s %10s %10s %10s %10s" % ("T", "greedy", "thompson", "c ln T",
                                   "linear"))
res = {}
for rule in ("greedy", "thompson"):
    rng = random.Random(20261113)
    runs = [run(rule, rng) for _ in range(RUNS)]
    res[rule] = {t: math.fsum(r[t] for r in runs) / RUNS for t in CHECK}
for t in CHECK:
    print("%6d %10.2f %10.2f %10.2f %10.2f" % (
        t, res["greedy"][t], res["thompson"][t], c * math.log(t),
        t * (P[1] - P[0])))
print("greedy regret per unit at T = 5000: %.4f" % (
    res["greedy"][5000] / 5000))

Single source and citation

Fan, Y. (2026). Dynamic Allocation of Compute and Budget across Business Lines: Gittins-Index Exploration and Weekly Quotas for Tollbooth, Buying and Publishing Lines (Version 1.0.0), Chapter 3: Thompson Sampling against the Gittins Index: Two Ways of Keeping a Chance Open on the Same Decision. 5D Library. DOI pending

DOI pending · monograph page goes live after publication · 5DL-B-264 · v1.0.0 · CC-BY-NC-ND-4.0

BibTeX
@book{fan2026264,
  author    = {Fan, Yafu},
  title     = {Dynamic Allocation of Compute and Budget across Business Lines: Gittins-Index Exploration and Weekly Quotas for Tollbooth, Buying and Publishing Lines},
  year      = {2026},
  publisher = {5D Library},
  edition   = {1.0.0},
  note      = {DOI pending}
}

Other chapter answers in this book