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 | ||||
| T | greedy | thompson | c ln T | linear |
| 100 | 2.53 | 2.17 | 34.40 | 6.00 |
| 1000 | 23.04 | 12.08 | 51.60 | 60.00 |
| 5000 | 113.04 | 20.85 | 63.62 | 300.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
- Chapter 1 · Lock-In: Why Betting Everything on Last Week's Winner Traps a Business on a Second-Best Line
- Chapter 2 · Calibration: Setting a Business Line against a Permanent Safe Yield and Bisecting for the Gittins Index
- Chapter 4 · From Choosing a Line to Splitting a Budget: Five Weekly Quota Rules under Batched Feedback
- Chapter 5 · Two Frictions: Switching Costs Call for a Hysteresis Band, Changing Markets Call for Fading Records
- Chapter 6 · Writing the Tollbooth, Buying and Publishing Lines as Arms: Margins, Unit Costs, Prior Strength and a Stop-Funding Table
- Chapter 7 · Classical Sources East and West: Jiran's "In Drought, Lay In Boats; In Flood, Lay In Carts" and Thompson's Two-Sample Problem of 1933
- Chapter 8 · Closing the Loop: the Weekly Quota Meeting Table, the Business-Line Quota Indexer and a Pre-Registered Test