Computer science is full of problems that sound oddly familiar: how long should you keep looking, when should you commit, and how much time should you spend trying something new? Brian Christian and Tom Griffiths explore those questions in Algorithms to Live By. This is my practical tour of two ideas from the book: optimal stopping and the explore/exploit trade-off.
What counts as an algorithm?
An algorithm is a finite sequence of clear instructions for solving a problem or completing a computation. That definition sounds mechanical, but the same structure appears in ordinary decisions. We gather information, compare options, update our beliefs, and eventually act.
The original brown bag session opened with a suitably confident promise: "I'm gonna teach you how to live."
Optimal stopping
An optimal stopping problem asks when we should stop observing new options and choose one. Stop too early and the best option may still be ahead. Stop too late and a good option may already be gone.
The best-known version is the secretary problem.
Imagine interviewing a fixed number of applicants in random order. You can rank the people you have met, but you cannot assign a perfect score in advance. After each interview, you must either hire that applicant or reject them forever. Your goal is to maximize the chance of hiring the best person in the entire pool.
The first applicant is automatically the best person seen so far. The second has a 1-in-2 chance of being the best so far. The fifth has a 1-in-5 chance. As the search continues, record-breaking applicants become better signals, but they also become less common.
The look-then-leap rule
The classic strategy has two phases:
- Look: Reject the first 37 percent of applicants while using them to establish a benchmark.
- Leap: Hire the next applicant who is better than everyone in the look phase.
For a large applicant pool, the cutoff approaches 1/e, or about 37 percent. Under the classic assumptions, this strategy also gives roughly a 37 percent chance of selecting the single best applicant. That may sound modest, but it is the best possible success rate when choices are random, immediate, and irreversible.
As the applicant pool grows, the best cutoff settles near 37 percent.
A three-applicant example
Suppose the applicants have true ranks 1, 2, and 3, where 3 is best. They can arrive in six possible orders:
1-2-3, 1-3-2, 2-3-1, 3-1-2, 2-1-3, 3-2-1
If we use the first applicant only as the benchmark and then choose the next person who beats that benchmark, we select the best applicant in three of the six orders. That is a 50 percent success rate.
Change the rules, change the cutoff
The 37 percent rule is not universal. It belongs to a very specific model. Change the model and the sensible exploration period moves too.
- If rejected candidates can be recalled but may decline, it can make sense to explore longer. One variation in the original session moved the look phase to about 61 percent when a recalled candidate had a 50 percent chance of accepting.
- If new candidates may reject an offer, committing earlier can be rational. An illustrative 50 percent rejection model moved the look phase closer to 25 percent.
- If every applicant has an absolute score, a threshold strategy becomes possible. Work backward from the last decision and raise the acceptance bar when more candidates remain.
The practical lesson is more useful than any single percentage: identify which decisions are reversible, decide how much information you need, and set a stopping rule before the pressure of the moment changes it.
Explore or exploit?
Exploration means gathering information. Exploitation means using what we already know to get a reliable result.
Picture a buffet with limited time. Sampling every dish may reveal a new favorite, but it leaves less time to enjoy anything. Choosing only familiar dishes is dependable, but we learn nothing. The right balance depends on how much time remains. Early in the meal, exploration is cheap. Near the end, exploitation becomes more valuable.
The same trade-off appears in restaurants, product experiments, career decisions, recommendations, and investments.
The multi-armed bandit problem
Imagine a casino with several slot machines. Each machine has an unknown payoff rate. Every pull serves two purposes: it might produce a reward now, and it reveals information that can improve later choices.
Suppose one machine has paid out 9 times in 15 pulls, while another has paid out once in 2 pulls. Their observed success rates are 60 percent and 50 percent. The first looks better, but the second has much more uncertainty. A few more trials could reveal that it is excellent or terrible.
This is what makes the problem difficult. A decision rule has to value both current reward and information.
A simple heuristic is win-stay, lose-shift: keep using the current option after a win and switch after a loss. It is easy to remember, but one disappointing result can make it abandon a genuinely strong option.
Gittins index
The Gittins index gives each option a score based on its observed wins, losses, and the value of future rewards. An option with little evidence can receive an exploration bonus because learning about it may improve many future decisions.
These values assume the next payoff is worth 90 percent of a payoff now. More wins raise the index; more losses lower it.
Discounting matters. If there are many decisions ahead, information has time to pay for itself, so exploration is valuable. If only one decision remains, learning has almost no future value, so the best-known option usually wins.
What I kept from the book
The useful part of these algorithms is not pretending life has perfect inputs. It is giving vague decisions a shape.
- Separate the learning phase from the deciding phase.
- Write down a stopping rule before you become attached to an option.
- Explore more when the future is long and the cost of trying is low.
- Exploit more when time is short or mistakes are expensive.
- Revisit the rule when choices become reversible, scores become available, or rejection becomes possible.
Algorithms do not remove judgment. They make the trade-offs visible, which is often enough to make a better decision.