Optimal stopping strategy came up recently in an article in Scientific American. Once, when dinning out, the physicist, Richard Feynman, asked the question if one should order a favorite dish or try something new. The same question can be asked about going to a favorite restaurant or trying a new place to dine. Richard Feynman’s “dining optimization” solution is essentially an optimal stopping rule for the explore‑exploit dilemma: how long to keep trying new dishes (or restaurants) before settling on the best one you’ve found so far.
Feynman derived a declining threshold strategy (one such declining threshold is Tn=n/(n+1), where n is the number of remaining visits; the T starts very high with the first visit and declines to 1/2 on the last visit):
- Each night you compare the best restaurant (or dish) you’ve tried so far to a quality threshold.
- If your current best exceeds the threshold, you stop exploring and keep returning to it.
- If not, you try a new restaurant.
- The threshold starts high and decreases as the number of remaining nights shrinks.
- Early in a trip, you should be picky and explore aggressively.
- Near the end, you should lower your standards and exploit whatever is “good enough.”
This strategy maximizes the expected total quality of all meals over a fixed number of nights.
Why the threshold declines
With many nights left, the value of discovering an exceptional restaurant is high, so the threshold is strict. As time runs out, the benefit of exploration drops, so the threshold relaxes. This is mathematically optimal for maximizing cumulative reward.
In plain English, Feynman’s rule says:
Explore new restaurants until the best one you’ve found so far is “good enough” by a standard that gets easier to satisfy as your remaining time decreases. Then stick with that best one.
