Resolving Feynman's restaurant problem reveals optimal solutions and human strategies

In the 1970s, physicist Richard Feynman turned lunch with a friend into a math problem-how to optimize dish selection over multiple meals-but his handwritten notes remained a mystery for decades. Here we present the fully deciphered problem and solution, prove its optimality, generalize it to related problems, and compare the results to human behavior. The optimal policy specifies decreasing thresholds for switching from exploring new dishes to exploiting the best, with thresholds varying based on the distribution of the quality of dishes. We connect these results to the existing psychological literature on optimal stopping problems, which has explored close variants on Feynman's problem, and use our generalization of the solution to explore how the underlying distribution of the quality of the options influences people's choices. A preregistered experiment with 2,520 participants shows that people adopt thresholds that decrease linearly with the proportion of trials remaining, consistent with the observation of linear thresholds in other optimal stopping problems. However, we show that people tend to explore more than predicted by linear thresholds, and that different distributions of quality result in thresholds with the same slope but different intercepts. These results indicate that people adapt linear thresholds used in optimal stopping tasks in a way that is sensitive to the underlying distribution-a simple strategy that we show is nearly as effective as Feynman's solution.