1
$\begingroup$

The problem

In this game, you are given empty balloons one by one, and for each balloon you are to inflate it with air until you are satisfied. If it does not burst, you gain happiness points proportional to the volume of air in the balloon (say 1 point per ml). If it bursts, you gain nothing. If you attempt to inflate a balloon beyond 1000L, it will certainly burst. The balloons are inexhaustible infinite, and your goal is to maximize your cumulative gain. More precisely, you want to maximize the asymptotic behaviour of $g(n)$ as $n \to \infty$, where $g(n)$ is the cumulative gain after $n$ balloons. All you know about the balloons is that they are all made by the same factory process, and so you can assume that the maximum inflatable size is always drawn from the same fixed distribution with nonzero variance.

$\def\pp{\mathbb{P}}$$\def\ee{\mathbb{E}}$$\def\lfrac#1#2{{\large\frac{#1}{#2}}}$Is there an optimal strategy, defined as a strategy that guarantees $\ee(\lfrac1n g(n)) \to c$ as $n \to \infty$ and also has asymptotically maximum $\lfrac{\ee(\lfrac1n g(n))-c}{\sqrt{Var(X)}}$ where $X$ is the distribution of the balloon's maximum inflatable size, and $c$ is such that $c \cdot \pp(X \ge c)$ is maximum ($c$ is the optimal inflate size if we knew $X$)?

Partial solution

If we knew $X$, we could easily get an optimal strategy as follows. Simply always inflate to size $c$, which exists by the extreme value theorem because of the balloon size limit (which is one reason I imposed it). I can construct a strategy that guarantees $\lfrac1n g(n) \overset{a.s.}\to c$ as $n \to \infty$: With probability $\lfrac1{n}$ inflate until it bursts, otherwise use previous tries to estimate $c$ and inflate to that estimate. After $n$ tries we have on average roughly $\ln(n)$ samples, and so by CLT our sample distribution's cdf will eventually converge to that of the correct distribution because it has finite variance (which is the other reason for the balloon size limit), and also we use the estimate with probability approaching $1$. The problem is to find a strategy that gives the fastest convergence (or prove that no optimal strategy exist). I don't even know the asymptotic behaviour of this strategy that I've described.

Notes

I made up this generalized game after playing a simple Javascript variant some months ago, but I can no longer find it. Thanks to joriki, this original variant is known as the Balloon Analogue Risk Task (BART), which can be seen as a variant where the distribution is discrete. The strategy I gave above works but can never be asymptotically as good as the strategy that only takes one sample and then always inflates to that size (as pointed out by Keepthesemind).

For each $k > 0$ there is a balloon distribution such that the optimal strategy cannot expect to gain more than $\lfrac1k$ of the actual possible gain (the sum of the maximum inflatable sizes of the balloons). This also means that there is no optimal strategy for the variant of the game where an adversary chooses the maximum inflatable size just before giving you each balloon.

$\endgroup$
  • 1
    $\begingroup$ @Keepthesemind: Indeed thanks for the suggested tag; I missed that one when searching. Anyway to preserve what we discussed in a nutshell, I'll note that it is insufficient to take only a finite sample because for some distributions there is a nonzero probability that the correct c is beyond the maximum burst size m in the finite sample, and so following the estimated c would not give any new sample points beyond m, and so the estimated c would remain incorrect. As you suggested it may be possible to overcome that by using a prior in the estimation of c, but I suspect it will not be optimal. $\endgroup$ – user21820 Jul 24 '16 at 7:27
  • $\begingroup$ See also math.stackexchange.com/questions/1702010. $\endgroup$ – joriki Jul 24 '16 at 7:35
  • $\begingroup$ @Keepthesemind: After my first edit it still allowed discrete distributions. My strategy still works for the discrete distribution because its samples are exactly accurate. But your point that we can't optimize the speed of learning due to that is absolutely correct, thanks! It also suggests that there is no optimal even for continuous distributions since you can approximate the discrete one arbitrarily well. I'm not sure if my new formulation works. Any other ideas you have are welcome! $\endgroup$ – user21820 Jul 24 '16 at 10:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.