Basketball shots and stopping rule [closed]

Question

Moved over from StackExchange.

You are taken to play a basketball game where you can shoot basketballs at n slots using a machine that is equally likely to shoot the balls into those n slots. You can stop whenever you see fit and get a reward based on your performance. For every slot with only one ball, you get \$1, for every slot with k balls (k>1), you lose \$k, empty slots don't count. What's your strategy to maximize your reward and what will your maximum reward be?

After some discussion, I think the stopping rule should be that you quit once $n\leq2x_1+4x_2$, where $x_1$ and $x_2$ are numbers of slots with one ball and more than one ball, respectively.

I'm having a hard time getting the maximum expected reward.

Answer 1

f you use the notation suggested in the mathexchange question: o is the number of baskets with one ball, s the number of baskets with more than one ball and n the total number of baskets, then the Bellman equation gives you

$$E(o,s) = \max\left(o-2s, \left(1-\frac{o}{n-s}\right) E(o+1,s) + \frac{o}{n-s}E(o-1,s+1)\right)$$

Now define the optionality function $V$ which represents the value of continuing shooting instead of just stopping

$$V(o,s) = E(o,s) - (o-2s)$$

Thus

$$V(o,s) = \max\left(0, \left(1-\frac{o}{n-s}\right) V(o+1,s) + \frac{o}{n-s}V(o-1,s+1) + \left(1-4\frac{o}{n-s}\right)\right)$$

Lemma $V(o,s) \geq \max(V(o+1,s),V(o,s+1))$ This can be verified by induction or by noting that having more balls in the baskets does not open up more options.

Thus, the optimal strategy is to stop playing when $4o+s\geq n$ The expected value of the game can be computed with dynamic programming.