5D Library › Bayesian Search in Unknown Landscapes, Optimal Stopping and Gittins Indices · 中文

Preface: When to Stop, Where to Look, and Whether to Go On

Note

Please read this first. This book is a teaching and research text on mathematical models and statistical decision theory. It is not investment, trading, start-up, career, human-resources, tax or legal advice; its simulations and worked examples are computed under stated assumptions and say nothing about the future of any real project, market or person. The book recommends no specific asset, platform, exchange, currency, broker or service. Unless a source is given, the “applicants”, “lanes”, “channels”, “projects”, “search areas” and data in the book are fictional or synthesised by the programs, and the parameters are illustrative.

The word “optimal” appears often in this book. It means only that, under the stated assumptions, a rule maximises a stated objective (such as the probability of choosing the best applicant, or expected discounted reward) as a matter of mathematics; when the assumptions fail, the conclusion may fail with them. The book never says that a rule “guarantees” anything or “always wins”. The material on hiring and the selection of people discusses only the mathematical structure of decisions; real hiring is also governed by employment law, anti-discrimination duties and principles of fairness, and must follow local law and professional advice.

In February 1960 Martin Gardner described a game in his “Mathematical Games” column in Scientific American. Someone writes a number on each of many slips of paper, turns them face down and shuffles them; you turn them over one at a time and may stop whenever you like, declaring that the slip just turned is the largest. You win if you are right, and a slip once passed cannot be taken back (Gardner 1960). The game became famous as the “secretary problem”: if you can see only how applicants rank relative to one another and cannot go back, then by looking at about 37 % of them without hiring and afterwards hiring the first one better than everyone before, you choose the best with probability about 37 %.

This “37 % rule” has travelled widely and is often offered as life advice for finding a flat, a partner or an employee. But the conditions under which it holds are demanding, and relaxing them a little changes the best course of action considerably. The same problem keeps returning in other forms. Searching the sea for a lost aircraft, should one look first where the wreck is most probably lying, or where it would most easily be seen? When several options have uncertain payoffs, should one spend one’s time on the option that now looks best, or give some of it to options one knows little about? When a project has absorbed a great deal and its prospects are unclear, should one persist or quit? In statistical decision theory these questions share a structure: stopping times (when to stop observing and act) and the exploration–exploitation trade-off (how much immediate cost to accept for the sake of information).

This book asks four questions. First, what exactly do the classical models — the secretary problem, Bayesian search and the multi-armed bandit — conclude, and under what assumptions? Second, how much experimental evidence is there for the “sunk-cost fallacy”, and how does a normative decision model separate rational persistence from that fallacy? Third, what must change when these models are used for start-up experiments and for selecting people? Fourth, can people make better sequential choices by learning a stopping rule, and can this be tested in a pre-registered randomised trial?

What this book covers

Chapter 1 derives the optimal threshold and success probability of the secretary problem by exact calculation for finite nn, gives the limit 1/e1/e as n→∞n \to \infty, and reviews Ferguson’s 1989 account of the problem’s history. Chapter 2 discusses variants — full information, minimising the expected rank, offers that may be refused, recall, an unknown number of applicants — and how people stop in experiments. Chapter 3 discusses Koopman’s theory of search and Bayesian search, uses a program on a grid to show posterior updating and the rule “posterior probability × detection probability”, discusses the searches for the submarine Scorpion and for the wreckage of Air France Flight 447, and introduces Charnov’s marginal value theorem and the dispute over the Lévy-flight foraging hypothesis in foraging ecology. Chapter 4 turns to multi-armed bandits: the computation of the Gittins index and the conditions for its optimality, Thompson sampling, UCB1, and the regret lower bound of Lai and Robbins. Chapter 5 discusses the experimental evidence on sunk costs and its disputes, “continue or abandon” as a one-armed bandit, and the use of Wald’s sequential probability ratio test to fix a stop-loss boundary in advance. Chapter 6 applies these models to testing start-up “lanes” and to selecting people, and explains the limits of the secretary problem in practice and how to correct for them. Chapter 7 reads this research beside the “Waging War”, “Nine Variations” and “Manoeuvring” chapters of the Sunzi, the phrase “speed is what the army prizes” from the biography of Guo Jia in the Records of the Three Kingdoms, and the “Eminent Teachings” and “Two Handles” chapters of the Han Feizi, and states where classical experience ends and modern stopping theory begins. Chapter 8 offers a “four-step checklist for searching and stopping” and a pre-registered online randomised controlled trial comparing “learning a stopping-threshold rule beforehand” with “control instructions” on the share of sequential-choice games in which the best option is chosen.

The book borders on several other volumes of 5D Library, which it recalls only briefly without repeating their programs: Volume 16 (real options; revisited in Chapter 5), Volume 19 (the Kelly criterion and the risk of ruin; cited in Chapter 6), Volume 26 (calibrated probabilities; drawn on for priors in Chapters 3 and 8), Volume 27 (mechanism design; adjacent to the “Two Handles” section of Chapter 7), Volume 32 (whose Chapter 5 already compared greedy, ε\varepsilon-greedy, UCB1 and Thompson sampling; Chapter 4 does not repeat this and discusses only the Gittins index and the regret bound), and Volume 33 (optional stopping; Chapter 5 explains how it differs from a sequential test designed in advance).

Claims corrected after checking

Several statements in the author’s original framework needed correction, supplementation or qualification after checking.

First, the “37 % rule”. For finite nn the optimal number to skip follows from an exact formula: 3 of 10, with success probability 0.399; 37 of 100, with 0.371. Only as n→∞n \to \infty do the skipped share and the success probability both tend to 1/e≈0.3681/e \approx 0.368. The success probability is flat near the optimum (for n=100n = 100, skipping anything from 30 % to 50 % gives at least 0.349). The rule maximises only the probability of choosing the very best; it fails about 63 % of the time, and for n=40n = 40 it ends with nobody in 37.5 % of cases.

Second, the variants. The full-information limit of about 0.5802 of Gilbert and Mosteller (Gilbert and Mosteller 1966) and the minimal-expected-rank limit of about 3.8695 of Chow and colleagues (Chow et al. 1964) both check out, but the first requires a known distribution of scores and the second is a limit as n→∞n \to \infty (3.60 for n=100n = 100). The “case with recall” needs explanation: with unrestricted recall the problem is trivial; the meaningful case is one in which a recalled applicant may no longer be available (Yang 1974). The book uses a simplified “one recall at the end” model and adds the case of offers that may be refused (Smith 1975).

Third, the history. Ferguson’s 1989 answer is “nobody”: in Gardner’s original game of googol the numbers are written by another person, making it a two-person game, whereas the solutions of the 1960s treat the version with relative ranks only (Ferguson 1989); the first solution in a journal was Lindley’s in 1961 (Lindley 1961). Kepler’s search for a wife violated “no recall”, and Cayley’s lottery problem of 1875 scores actual values; neither is a secretary problem, and “Kepler used the 37 % rule” is inaccurate.

Fourth, conditions in practice. The secretary problem requires a known number of applicants, random order, relative ranks only, no recall, offers always accepted and only the best counting as success; in hiring almost none of these holds. When payoff is actual quality, the optimal cutoff is about n\sqrt{n}, that is, skip about n−1\sqrt{n} – 1 (Bearden 2006) — only 5 of 40; when the number is uniform between 1 and bb, the best single threshold skips only about 13.5 %, with success probability about 0.27 (Presman and Sonin 1972).

Fifth, Bayesian search. “Posterior probability × detection probability” is a greedy rule for where to look next, optimal in the discrete problem with one cell searched at a time and fixed detection probabilities; the general theory comes from Koopman (Koopman 1957; Stone 1975). The AF 447 case is in Stone and colleagues, Statistical Science 29(1): 69–80 (2014); the wreckage was found on 3 April 2011, about a week into the new phase of the search (Stone et al. 2014). The key step was re-examining the assumption that the beacons had worked, and the authors themselves say a joint model would have been better. The Scorpion case comes from Richardson and Stone (1971) (Richardson and Stone 1971). Two successes do not prove that the method always succeeds.

Sixth, the optimality of the Gittins index (Gittins and Jones 1974; Gittins 1979) requires independent arms, frozen arms when not chosen, fixed discounting, an infinite horizon, one arm at a time and no switching costs; otherwise it is only an approximation. In the book’s two-armed problem with discount 0.9, a greedy policy loses only about 0.3 % relative to the Gittins policy.

Seventh, Thompson sampling and the regret bound. Agrawal and Goyal (2012) gave the first logarithmic regret bound for Thompson sampling, not with the optimal constant (Agrawal and Goyal 2012); Kaufmann and colleagues showed in the same year that for Bernoulli arms it attains the Lai–Robbins bound asymptotically (Kaufmann et al. 2012). That bound is an asymptotic statement (Lai and Robbins 1985), and at finite TT regret can lie below cln⁡Tc \ln T (21.9 against 48.5 in the book’s program).

Eighth, the evidence on sunk costs. Arkes and Blumer’s 1985 theatre experiment had only 54 analysable participants, and the effect appeared only in the first half of the season (Arkes and Blumer 1985). The framework’s “review by Roth et al. 2015” is a meta-analysis by Roth, Robbert and Straus in Business Research, with a pooled effect of about 0.50 drawn mostly from hypothetical scenarios, although in decisions about progress surveys and field studies showed larger effects than scenario experiments (Roth et al. 2015); in laboratory experiments with real incentives the effect is small and erratic (Friedman et al. 2007); in the meta-analysis of Sleesman and colleagues the average correlation for sunk costs is about 0.24, with an 80 % credibility interval including zero, and only about 0.10 where sunk costs did not vary together with closeness to completion (Sleesman et al. 2012); and “Many Labs” replicated the effect in a hypothetical scenario (Klein et al. 2014).

Ninth, “a rational decision looks only at forward value” is right in the normative model, but “persisting is the fallacy” is not: money spent does not enter the decision, while accumulated evidence and the value of information do, so continuing below break-even early on can be rational; attending to sunk costs is sometimes rational for other reasons too (McAfee et al. 2010).

Tenth, Wald’s boundaries A≈(1−β)/αA \approx (1-\beta)/\alpha and B≈β/(1−α)B \approx \beta/(1-\alpha) are approximations (Wald 1945); the sequential probability ratio test minimises the expected sample size between two simple hypotheses (Wald and Wolfowitz 1948), but can run long when the truth lies between them, so a cap must be set in advance. A “stop-loss boundary” cannot guarantee that losses are avoided.

Eleventh, the classical texts. “Speed is what the army prizes” (兵贵神速) comes from the biography of Guo Jia in the Records of the Three Kingdoms (juan 14), not from the Sunzi, whose nearest lines in “Waging War” are “one has heard of clumsy speed, but never seen skill that prolongs” and “in war victory is prized, not duration”. In the “Nine Variations” the book follows the received text 途 where the framework has 涂; the characters were interchangeable, and a note is given. In “Two Handles” the received text reads 言异事也, emended in some editions to 言与事也; a note is given. “Try them in office and assess their accomplishments” in “Eminent Teachings” checks out.

Twelfth, phrases such as “truncating sunk costs in time” and “optimal stopping” are written throughout as mathematical conclusions under explicit assumptions; the programs’ numbers come from illustrative parameters.

Thirteenth, foraging theory. Charnov’s marginal value theorem g′(t*)=g(t*)/(τ+t*)g'(t^*) = g(t^*)/(\tau + t^*) holds when all patches are alike, the gain curve is known and the aim is the long-run average rate of gain, and the evidence mostly supports it in direction (Charnov 1976; Stephens and Krebs 1986). “Lévy flight is the optimal search strategy” needs qualifying: the 1999 result for μ=2\mu = 2 requires sparse, revisitable targets and a forager without memory (Viswanathan et al. 1999), nearly straight-line motion is better for one-off targets, and in two or more dimensions it is optimal only in special limits, the optimal exponent depending on modelling details (Levernier et al. 2020). The albatross power law of 1996 arose from counting time on the island as flight, a 2007 re-analysis found no power law (Edwards et al. 2007), and later studies remain divided (Humphries et al. 2012; Pyke 2015).

Each chapter states these points in place, and they are collected in the editorial notes published with the book.

How to read the boxes

As in other volumes of 5D Library, different kinds of statement are marked separately.

Evidence

Evidence boxes report published research findings, with sources.

Calculation

Calculation boxes give formulas and short Python programs. Every program runs unchanged in a standard Python 3 environment using only the standard library, and its actual output is printed beneath it. The “applicants”, “lanes”, “channels”, “search areas” and data in the book are fictional or synthesised by the programs; parameters are illustrative values, not estimates for any real system.

Hypothesis · not established

Hypothesis boxes contain the author’s ideas, are marked “not yet established”, and state what result would show them to be wrong.

Source text

Source boxes quote classical texts, with the author’s explanation.

Note

Note boxes give cautions and explain choices.

About this edition

This is version 1.0.0, the first complete edition: a preface and eight chapters, in Chinese and English. The book contains 17 programs and 4 vector figures. The text, boxes and code were drafted with an AI writing tool from the author’s title, framework and notes; the author is responsible for reviewing and revising them and for checking every source. Corrections and missing references are welcome through the 5D Library website.

Disclosure

The author uses the works of 5D Library, including this book, as the methodological basis of his community courses, the 5D Ascension Cards (Dimensional Shift Card Decks) and the Yafu AI knowledge base, and therefore has a commercial interest in the subject of this book. The author also founded and runs Asia Influencer X and Yafu Global, whose business involves screening influencers and talent and testing new lanes and new projects, and therefore has a direct commercial interest in the subject of this book. The book promotes no course, card deck or service, is not investment, start-up or career advice, and uses no client data from these businesses; the Chapter 8 trial is designed to be run and analysed by researchers independent of the author’s business and does not recruit from the author’s community, students or customers, including the clients and students of these businesses; all the code and the study protocol are published openly for anyone to check. All models in this book are offered solely for discussion of mathematics and statistical decision theory, and the book recommends no specific project, lane or candidate.

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.
Arkes, Hal R., and Catherine Blumer. 1985. “The Psychology of Sunk Cost.” Organizational Behavior and Human Decision Processes 35 (1): 124–40.
Bearden, J. Neil. 2006. “A New Secretary Problem with Rank-Based Selection and Cardinal Payoffs.” Journal of Mathematical Psychology 50: 58–59.
Charnov, Eric L. 1976. “Optimal Foraging, the Marginal Value Theorem.” Theoretical Population Biology 9 (2): 129–36. https://doi.org/10.1016/0040-5809(76)90040-X.
Chow, Y. S., S. Moriguti, H. Robbins, and S. M. Samuels. 1964. “Optimal Selection Based on Relative Rank (the ‘Secretary Problem’).” Israel Journal of Mathematics 2: 81–90. https://doi.org/10.1007/BF02759948.
Edwards, Andrew M., Richard A. Phillips, Nicholas W. Watkins, et al. 2007. “Revisiting Lévy Flight Search Patterns of Wandering Albatrosses, Bumblebees and Deer.” Nature 449 (7165): 1044–48. https://doi.org/10.1038/nature06199.
Ferguson, Thomas S. 1989. “Who Solved the Secretary Problem?” Statistical Science 4 (3): 282–89. https://doi.org/10.1214/ss/1177012493.
Friedman, Daniel, Kai Pommerenke, Rajan Lukose, Garrett Milam, and Bernardo A. Huberman. 2007. “Searching for the Sunk Cost Fallacy.” Experimental Economics 10 (1): 79–104.
Gardner, Martin. 1960. “Mathematical Games.” Scientific American 202 (2).
Gilbert, John P., and Frederick Mosteller. 1966. “Recognizing the Maximum of a Sequence.” Journal of the American Statistical Association 61 (313): 35–73.
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.
Humphries, Nicolas E., Henri Weimerskirch, Nuno Queiroz, Emily J. Southall, and David W. Sims. 2012. “Foraging Success of Biological Lévy Flights Recorded in Situ.” Proceedings of the National Academy of Sciences 109 (19): 7169–74. https://doi.org/10.1073/pnas.1121201109.
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.
Klein, Richard A., Kate A. Ratliff, Michelangelo Vianello, et al. 2014. “Investigating Variation in Replicability: A ‘Many Labs’ Replication Project.” Social Psychology 45 (3): 142–52. https://doi.org/10.1027/1864-9335/a000178.
Koopman, Bernard O. 1957. “The Theory of Search. III. The Optimum Distribution of Searching Effort.” Operations Research 5 (5): 613–26. https://doi.org/10.1287/opre.5.5.613.
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.
Levernier, Nicolas, Johannes Textor, Olivier Bénichou, and Raphaël Voituriez. 2020. “Inverse Square Lévy Walks Are Not Optimal Search Strategies for d≥2d \geq 2.” Physical Review Letters 124 (8): 080601. https://doi.org/10.1103/PhysRevLett.124.080601.
Lindley, Dennis V. 1961. “Dynamic Programming and Decision Theory.” Applied Statistics 10 (1): 39–51.
McAfee, R. Preston, Hugo M. Mialon, and Sue H. Mialon. 2010. “Do Sunk Costs Matter?” Economic Inquiry 48 (2): 323–36. https://doi.org/10.1111/j.1465-7295.2008.00184.x.
Presman, E. L., and I. M. Sonin. 1972. “The Best Choice Problem for a Random Number of Objects.” Theory of Probability and Its Applications 17 (4): 657–68. https://doi.org/10.1137/1117078.
Pyke, Graham H. 2015. “Understanding Movements of Organisms: It’s Time to Abandon the Lévy Foraging Hypothesis.” Methods in Ecology and Evolution 6 (1): 1–16. https://doi.org/10.1111/2041-210X.12298.
Richardson, Henry R., and Lawrence D. Stone. 1971. “Operations Analysis During the Underwater Search for Scorpion.” Naval Research Logistics Quarterly 18 (2): 141–57. https://doi.org/10.1002/nav.3800180202.
Roth, Stefan, Thomas Robbert, and Lennart Straus. 2015. “On the Sunk-Cost Effect in Economic Decision-Making: A Meta-Analytic Review.” Business Research 8 (1): 99–138. https://doi.org/10.1007/s40685-014-0014-8.
Sleesman, Dustin J., Donald E. Conlon, Gerry McNamara, and Jonathan E. Miles. 2012. “Cleaning up the Big Muddy: A Meta-Analytic Review of the Determinants of Escalation of Commitment.” Academy of Management Journal 55 (3): 541–62. https://doi.org/10.5465/amj.2010.0696.
Smith, M. H. 1975. “A Secretary Problem with Uncertain Employment.” Journal of Applied Probability 12 (3): 620–24. https://doi.org/10.2307/3212880.
Stephens, David W., and John R. Krebs. 1986. Foraging Theory. Princeton University Press.
Stone, Lawrence D. 1975. Theory of Optimal Search. Academic Press.
Stone, Lawrence D., Colleen M. Keller, Thomas M. Kratzke, and Johan P. Strumpfer. 2014. “Search for the Wreckage of Air France Flight AF 447.” Statistical Science 29 (1): 69–80. https://doi.org/10.1214/13-STS420.
Viswanathan, G. M., Sergey V. Buldyrev, Shlomo Havlin, M. G. E. da Luz, E. P. Raposo, and H. Eugene Stanley. 1999. “Optimizing the Success of Random Searches.” Nature 401 (6756): 911–14. https://doi.org/10.1038/44831.
Wald, Abraham. 1945. “Sequential Tests of Statistical Hypotheses.” The Annals of Mathematical Statistics 16 (2): 117–86. https://doi.org/10.1214/aoms/1177731118.
Wald, A., and J. Wolfowitz. 1948. “Optimum Character of the Sequential Probability Ratio Test.” The Annals of Mathematical Statistics 19 (3): 326–39. https://doi.org/10.1214/aoms/1177730197.
Yang, Mark C. K. 1974. “Recognizing the Maximum of a Random Sequence Based on Relative Rank with Backward Solicitation.” Journal of Applied Probability 11 (3): 504–12. https://doi.org/10.2307/3212694.

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