# How does the answer to Feynman's Restaurant Problem change if $M$ is not restricted to a single value?

First, the background: Feynman's restaurant problem asks how we can maximise the total rating of the meals we eat at a restaurant with $N$ items on the menu, given that we know up-front that we are going to eat $M$ meals there.

I have transcribed the problem and answer:

Assume that a restaurant has $N$ dishes on its menu that are rated from worst to best, $1$ to $N$ (according to your personal preferences). You, however, don't know the ratings of the dishes, and when you try a new dish, all you learn is whether it is the best (highest rated) dish you have tried so far, or not. Each time you eat a meal at the restaurant you either order a new dish or you order the best dish you have tried so far. Your goal is to maximize the average total ratings of the dishes you eat in $M$ meals (where $M \leq N$).

The average total ratings in a sequence of meals that includes $n$ "new" dishes and $b$ "best so far" dishes can be no higher than the average total ratings in the sequence having all $n$ "new" dishes followed by all $b$ "best so far" dishes. Thus a successful strategy requires you to order some number of new dishes and thereafter only order the best dish so far. The problem then reduces to the following:

Given $N$ (dishes on the menu) and $M\leq N$ (meals to be eaten at the restaurant), how many new dishes $D$ should you try before switching to ordering the best of them for all the remaining $(M–D)$ meals, in order to maximize the average total ratings of the dishes consumed?

Answer : $D = \sqrt{2(M+1)} - 1$

So if we are visiting a restaurant with $20$ dishes $7$ times, we should pick different dishes for the first $3$ trips, then have the best of those the next $4$ times.

However, as far as practical application goes, this answer is the answer to a question that doesn't match reality - rarely do we know exactly how many times we're going to eat at a restaurant!

Suppose instead of having $M$ equal some fixed value, we instead have $M$ distributed according to some probability distribution $P$. For example, suppose we know we are going to visit a restaurant with $20$ dishes on some number of occasions uniformly distributed over $5..10$. What now should be our value for $D$? What about if $P$ is a less simple distribution?

Is it as simple as $\sum_m{P(m) D(m)}$ (which is I think $E(D)$?) where $D(m) = \sqrt{2(m+1)} - 1$ as above? Assuming that $P$ can't change over the course of the exercise, which as mjqxxxx points out would be quite possible in reality...
I imagine the probability distribution $f$ would depend strongly on the quality of the dishes tried so far... –  mjqxxxx Feb 6 '13 at 15:31