5D Library › Bayesian Search in Unknown Landscapes, Optimal Stopping and Gittins Indices · 中文
Chapter 6 Applications: Testing Lanes and Selecting People
Note
This chapter is not start-up, investment, career or human-resources advice. Its “lanes”, “channels”, “applicants” and numbers are fictional and serve only to show how the models of earlier chapters must be corrected when applied. Real business and hiring decisions involve many factors outside any model, and hiring is also governed by employment law and anti-discrimination duties.
Testing lanes: earn while learning, or learn then earn?
A team has several possible product directions (here called “lanes”), each with an unknown “conversion rate” that can be tested with small trials — a campaign, a sales visit, a free trial. The total budget is limited, and at the end one lane must be chosen for investment. This is a multi-armed bandit, but the objective can be of two kinds: as many conversions as possible during the test (earning while learning), or the highest possible probability of choosing correctly at the end (learning, then earning — called “best-arm identification” in statistics). The two objectives call for different allocations: the first should concentrate trials quickly on the lane that looks best; the second needs enough trials on each of the leading lanes to tell them apart. Top-two Thompson sampling, proposed by Russo in 2020, is a simple Bayesian algorithm designed for the second objective: each time, it first finds a “leader” by Thompson sampling, then tries the leader with probability one half and otherwise tries a “challenger” found by resampling (Russo 2020).
Calculation
Six invented lanes with conversion rates fixed at 0.10, 0.12, 0.13, 0.15, 0.16 and 0.20 (the last is best), a budget of 1,200 trials, and one lane chosen at the end. Four approaches are compared: (1) equal split, 200 trials each, choosing the highest observed rate; (2) successive halving: 80 trials for each of 6, keep 3 for 120 each, keep 2 for 180 each, choose the best; (3) Thompson sampling, choosing the highest posterior mean; (4) top-two Thompson sampling. Each approach is simulated 400 times.
# Six invented lanes with fixed conversion rates (lane 5 best), 1,200 trials, then one
# lane is chosen. (1) equal split; (2) successive halving 6 x 80 -> 3 x 120 -> 2 x 180;
# (3) Thompson sampling, Beta(1, 1); (4) top-two Thompson sampling (Russo 2020).
import random
P = [0.10, 0.12, 0.13, 0.15, 0.16, 0.20]
K, B = len(P), 1200
def pull(i, s, n, rng):
s[i] += rng.random() < P[i]; n[i] += 1
def choose(s, n):
return max(range(K), key=lambda i: ((1 + s[i]) / (2 + n[i]), i))
def run(policy, rng):
s, n = [0] * K, [0] * K
if policy == "equal split":
for i in range(K):
for _ in range(B // K):
pull(i, s, n, rng)
elif policy == "successive halving":
alive = list(range(K))
for keep, each in ((3, 80), (2, 120), (1, 180)):
for i in alive:
for _ in range(each):
pull(i, s, n, rng)
alive = sorted(alive, key=lambda i: -(1 + s[i]) / (2 + n[i]))[:keep]
else:
for _ in range(B):
th = [rng.betavariate(1 + s[i], 1 + n[i] - s[i]) for i in range(K)]
lead = max(range(K), key=th.__getitem__)
i = lead
if policy == "top-two Thompson" and rng.random() < 0.5:
for _ in range(100):
th = [rng.betavariate(1 + s[j], 1 + n[j] - s[j]) for j in range(K)]
i = max(range(K), key=th.__getitem__)
if i != lead:
break
pull(i, s, n, rng)
return choose(s, n), sum(s), n
if __name__ == "__main__":
rng = random.Random(2020); runs = 400
print(f"{runs} simulated tests per policy; best lane rate 0.20, budget {B} trials")
print(" policy P(best chosen) loss in rate conversions"
" trials on best")
for pol in ("equal split", "successive halving", "Thompson", "top-two Thompson"):
ok = loss = conv = onbest = 0
for _ in range(runs):
c, sc, n = run(pol, rng)
ok += c == K - 1; loss += P[-1] - P[c]; conv += sc; onbest += n[-1]
print(f" {pol:20s} {ok / runs:.3f} {loss / runs:.4f}"
f" {conv / runs:6.1f} {onbest / runs:6.1f}")
print(f" (always the best lane: {B * P[-1]:.0f} conversions expected;"
f" equal split: {B / K * sum(P):.0f})")
print(" (simulation SE of each P(best chosen) is about 0.02)")
# 400 simulated tests per policy; best lane rate 0.20, budget 1200 trials
# policy P(best chosen) loss in rate conversions trials on best
# equal split 0.820 0.0084 171.9 200.0
# successive halving 0.825 0.0076 188.1 343.9
# Thompson 0.855 0.0066 200.8 568.1
# top-two Thompson 0.873 0.0059 194.4 436.6
# (always the best lane: 240 conversions expected; equal split: 172)
# (simulation SE of each P(best chosen) is about 0.02)The four approaches choose the best lane with probabilities between 0.82 and 0.87, top-two Thompson sampling highest (0.873) and equal split lowest (0.820); but the simulation standard error of each share is about 0.02, so most of the differences in the probability of choosing correctly lie within simulation error. The differences in conversions during the test are clearer: equal split obtains only 171.9, successive halving 188.1, Thompson sampling 200.8 and top-two Thompson sampling 194.4 (knowing the best lane from the start would give 240 in expectation). Thompson sampling gives 568 trials to the best lane and top-two Thompson sampling only 437, because the latter deliberately gives trials to challengers, trading some conversions for a more accurate ranking. Successive halving is a simple form of “early stopping”: each round stops the lanes that are doing badly, needs no probability calculation, and still gains about 16 conversions over equal split.
These results rest on assumptions that often fail in reality. First, conversion rates do not change over time; real markets do, and early results may not represent later ones. Second, results are seen at once; if the result of a trial is known only weeks later, the advantage of sequential allocation shrinks. Third, “conversion” is the right measure; a lane with high short-term conversion need not have high long-term value. Fourth, the observed conversion rate of the chosen lane usually overstates its true rate, because it was chosen partly for being lucky — the “winner’s curse” discussed in Volume 33. Fifth, the test budget is itself a bet, and how much can be committed without endangering the whole team is a question discussed in Volume 19, Non-Ergodic Wealth Dynamics, the Kelly Criterion and Volatility Drag, which is only cited here.
“Continue or abandon” for a single lane can be handled with the one-armed bandit and the sequential probability ratio test of Chapter 5: before starting, write down the break-even point, the target conversion rate, the error rates and the cap on trials, print the boundaries, and act on them when they are reached.
Selecting people: the limits of the secretary problem and how to correct them
Hiring is often presented as the typical application of the secretary problem, but almost none of the conditions listed in Chapter 1 holds. Here are the two most important corrections.
Calculation
- Scoring by actual quality: applicants’ quality is uniform between 0 and 1 and only relative ranks are visible, but the payoff is the actual quality of the person hired; with cutoff (skip the first ), hire the first relative best afterwards, and hire the last applicant if none appears. The expected quality has the exact formula . (b) Quality visible, distribution known, each interview costing : backward induction gives a “reservation level” for each step (hire on reaching it), compared with the 37 % rule in net value (quality of the person hired minus interview costs) and number of interviews. All numbers are illustrative.
# (a) Cardinal payoff (Bearden 2006): quality ~ U(0, 1), relative ranks only, payoff =
# quality hired; cutoff c, last applicant if nobody qualifies; exact formula.
# (b) Quality seen, distribution known, cost k per interview: reservation levels by
# backward induction, against the 1/e rank rule (20,000 simulated runs).
import math, random
def cardinal(n, c):
if c == 1:
return 0.5
return (c - 1) * sum(1 / ((i - 1) * (i + 1)) for i in range(c, n + 1)) \
+ (c - 1) / (2 * (n + 1))
def reservation(n, k):
w = [0.0] # w[j]: value with j interviews left
for j in range(1, n + 1):
prev = w[-1]
emax = (1 + prev ** 2) / 2 if prev > 0 else 0.5
w.append(max(0.0, emax - k))
return w
def sim(n, k, rule, rng, runs=20000):
w, val, cnt = reservation(n, k), 0.0, 0
r = round(n / math.e) + 1
for _ in range(runs):
xs = [rng.random() for _ in range(n)]
if rule == "reservation":
for i, x in enumerate(xs):
if w[n - i] <= 0:
i, x = i - 1, 0.0
break
if x >= w[n - 1 - i]:
break
else:
bar = max(xs[:r - 1])
i = next((j for j in range(r - 1, n) if xs[j] > bar), n - 1); x = xs[i]
val += x - k * (i + 1); cnt += i + 1
return val / runs, cnt / runs
if __name__ == "__main__":
print("(a) cardinal payoff, relative ranks only: expected quality of the hire")
print(" n best c sqrt(n) E at best c 1/e cutoff c E at 1/e cutoff")
for n in (10, 40, 100, 400):
c = max(range(1, n + 1), key=lambda c: cardinal(n, c))
r = round(n / math.e) + 1
print(f" {n:4d} {c:5d} {math.sqrt(n):5.1f} {cardinal(n, c):.4f}"
f" {r:4d} {cardinal(n, r):.4f}")
print("(b) interview cost k, quality seen, n = 40: net value (interviews used)")
print(" k first reservation reservation rule 1/e rank rule")
rng = random.Random(2006)
for k in (0.0, 0.005, 0.02):
w = reservation(40, k)
a = sim(40, k, "reservation", rng); b = sim(40, k, "1/e", rng)
print(f" {k:6.3f} {w[39]:.3f} {a[0]:.3f} ({a[1]:4.1f})"
f" {b[0]:.3f} ({b[1]:4.1f})")
# (a) cardinal payoff, relative ranks only: expected quality of the hire
# n best c sqrt(n) E at best c 1/e cutoff c E at 1/e cutoff
# 10 3 3.2 0.7333 5 0.7000
# 40 6 6.3 0.8542 16 0.7812
# 100 10 10.0 0.9050 38 0.8018
# 400 20 20.0 0.9513 148 0.8129
# (b) interview cost k, quality seen, n = 40: net value (interviews used)
# k first reservation reservation rule 1/e rank rule
# 0.000 0.955 0.955 (15.0) 0.781 (30.0)
# 0.005 0.898 0.898 ( 9.2) 0.628 (30.0)
# 0.020 0.800 0.800 ( 5.0) 0.179 (30.1)The results of (a) agree with Bearden’s 2006 conclusion that when the payoff is actual quality the best cutoff is about (Bearden 2006). With 40 applicants one should skip only 5, for an expected quality of 0.854; applying the 37 % rule and skipping 15 gives only 0.781. The more applicants, the larger the difference: with 400, skipping 19 gives an expected quality of 0.951, skipping 147 only 0.813. The reason is that the 37 % rule has a 37 % chance of ending with nobody (or with the last applicant by default), which does not matter for “the best or nothing” but costs a great deal when the aim is “hire someone as good as possible”.
The results of (b) go further. If the distribution of quality is known (for instance, the distribution of scores in past hiring rounds) and each person’s quality can be seen, no “learning phase” is needed: with no interview cost, the optimal rule achieves an expected quality of 0.955 with 15 interviews on average, while the 37 % rule achieves only 0.781 and needs about 30 interviews. With a cost of 0.005 per interview, the optimal rule’s net value is 0.898 with 9.2 interviews on average, and the 37 % rule falls to 0.628; with a cost of 0.02, the optimal rule needs only 5 interviews on average and hires the first applicant who reaches 0.800, while the 37 % rule’s net value falls to 0.179. When interviews cost something and the distribution is roughly known, “stopping a little early” is often right — one reason why the “early stopping” seen in the experiments of Chapter 2 may be partly reasonable.
Taking the last two chapters and this one together, the corrections needed for selecting people can be listed:
- Replace relative comparison with scoring defined in advance. Structured scoring makes each person’s quality “visible”, and makes the decision independent of the order in which applicants arrive. Deciding only on “better than those before” means that people of equal quality receive different outcomes because they came earlier or later, which is also a problem of fairness.
- Build a prior from historical data. The distribution of past scores plays the role of the “known distribution” of the full-information version, which can raise the success probability from about 0.37 to about 0.58 (Chapter 2), or give a reservation level directly when payoff is actual quality.
- Count the costs of interviewing and of waiting. With costs, the optimal reservation level falls as remaining opportunities shrink, and one should hire earlier.
- Allow for refusals and recall. When offers may be refused, act earlier; when recall is possible, one can look at more people (Chapter 2).
- Do not apply 37 % when numbers are uncertain. When the number of applicants is uncertain within a range, the best single threshold skips only about 13.5 % (Chapter 2).
- Beyond a single position. Hiring several people at once, or needing a mix of skills in a team, turns the problem into multiple stopping or combinatorial selection, which this book does not cover.
Note
A mathematical model is not a hiring procedure. The discussion above concerns only the mathematical structure of decisions. Real hiring needs job-related evaluation criteria that are defined in advance and applied consistently, must comply with local law on equal employment and personal data, and should take the applicant’s experience into account. The models in this book cannot replace these requirements.
Summary
In lane testing, “earning while learning” and “learning, then earning” are different objectives: Thompson sampling obtains the most conversions during the test, top-two Thompson sampling keeps more trials for challengers to raise the probability of choosing correctly, and successive halving is a form of early stopping that needs no probability calculation; with the illustrative parameters, differences in the probability of choosing correctly lie within simulation error, while differences in conversions are clearer. Real applications must attend to delayed outcomes, the choice of measure and the winner’s curse. In selecting people, when the payoff is actual quality the best cutoff is about , so that with 40 applicants only 5 need be skipped; when quality is visible, its distribution known and interviews costly, the optimal rule often hires among the first few applicants. The next chapter reads these ideas beside several classical Chinese texts.
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).