Filling Up Buckets with Coins Suppose that you have $n$ buckets, and you can hold each bucket under a coin machine that will drop 10 dollars worth of coins into the bucket each time you press a button. Any time you want, you can add the money in the bucket to your total, but then you loose the bucket.
However, each bucket has a random number of button-presses that will cause it to burst from the weight of the coins, and if the bucket bursts then you get none of the money in it and must move on to the next bucket.
What strategy maximizes your expected total sum of money? All I have figured out so far is that you almost certainly want to waste a few buckets at the beginning in order to get a sense of the average amount of money each bucket could hold; if you were very cautious and filled each bucket with just 10 doars, it's possible that each bucket could have had thousands of dollars of capacity. My intuition says to waste something like the first $\sqrt n$ or possibly $n\over e$ buckets to calculate an expected average amount of money each bucket can hold, then fill it up to some reasonably safe percentage of that amount.
 A: I will sketch how you can find a policy with regret almost $n^{2/3}$ if you know that the number of coins the bucket can carry is bounded. You could possibly relax this with the assumption that the expectation of the number of coins a bucket can carry is finite.
First, let us start with finding the optimal policy if we had known the distribution.
Let $K_i$ be i.i.d. random variables over $\{1, 2, ..., k_{max}\}$ which stand for the number of coins the bucket can carry.
You can convince yourself that a deterministic policy is optimal in this case. Say pushing the button $\alpha$ times. Then, the expected reward is the random variable,
$$
\mathbb{E}[{R}] = \mathbb{E}[\alpha \mathbb{1}_{[K \geq \alpha]}] = \alpha \mathbb{P}(K \geq \alpha).
$$
There is an optimal $\alpha^*$. We will compare our performance against this $\alpha^*$.
We will do "explore then exploit". For the first $m$ buckets fill the bucket to $k_{max}$. Then, using the data, estimate each $ \mathbb{P}(K \geq k)$. For each fixed $k$, averaging $\mathbb{1}_{[K \geq k]}$ we get an estimate.
By using subgaussianity of the indicator random variable,
$$  \mathbb{P}\left( \exists k\leq k_{max} \ |\frac{1}{m}\sum_{i = 1}^m \mathbb{1}_{[K_i \geq k)} - \mathbb{P}(K \geq k)| \geq \epsilon\right) \leq 2k_{max}e^{-2m\epsilon^2}
$$
Using the estimates, find the $k^*$ which maximizes,
$$
k \frac{1}{m}\sum_{i = 1}^m \mathbb{1}_{[K_i \geq k)}
$$
over $k$.
Then if we use this $k^*$ as the number of times we press, we get the average regret for the future buckets,
\begin{align}
\mathbb{E}[regret | \text{estimations are $\epsilon$ good}] &= \alpha \mathbb{P}(K \geq \alpha) - k^* \mathbb{P}(K \geq k^*)\\
&=\left(\alpha \mathbb{P}(K \geq \alpha) - \alpha \frac{1}{m}\sum_{i = 1}^m \mathbb{1}_{K_i \geq \alpha}\right) - \left(k^* \mathbb{P}(K \geq k^*) - k^* \frac{1}{m}\sum_{i = 1}^m \mathbb{1}_{K_i \geq k^*}\right)\\
& \  \  \ \ + \alpha \frac{1}{m}\sum_{i = 1}^m \mathbb{1}_{K_i \geq \alpha} - k^* \frac{1}{m}\sum_{i = 1}^m \mathbb{1}_{K_i \geq k^*}\\
&\leq \left(\alpha \mathbb{P}(K \geq \alpha) - \alpha \frac{1}{m}\sum_{i = 1}^m \mathbb{1}_{K_i \geq \alpha}\right) - \left(k^* \mathbb{P}(K \geq k^*) - k^* \frac{1}{m}\sum_{i = 1}^m \mathbb{1}_{K_i \geq k^*}\right)\\
&\leq 2 k_{max}\epsilon
\end{align}
If the estimations are not $\epsilon$ good, the regret could be at most $k_{max}$.
Averaging these we get,
$$
\mathbb{E}[regret] \leq 2k_{max}^2e^{-2m\epsilon^2}+ 2k_{max}\epsilon
$$
Select $\epsilon$ to be something like
$$
\frac{1}{\sqrt{2m}} \sqrt{\log (m)}
$$.
This will give you the regret upper bounded by,
$$
2k_{max}^2\frac{1}{m} + \frac{2k_{max}}{\sqrt{2m}} \sqrt{\log (m)}
$$
which is like $ 1 / {\sqrt{m}}$ ignoring the log factors.
The regret over the whole game is then the following, first m rounds we possibly lose as large as $k_{max}$ in the other $n - m$ rounds we lose
$$
\frac{k_{max}}{\sqrt{m}}
$$
in average at each round. Therefore the total regret can be as large as,
$$
\mathbb{E}{\text{total regret}} \leq k_{max} \left(m + \frac{n}{\sqrt{m}}\right)
$$
Choose $m = n^{2/3}$. You get the bound (ignoring log factors). The nice thing is you don't need to know $k_{max}$ for this policy since $m$ does not depend on $k_max$.
One caution is that I assume that you first fix the distribution then $n$ goes to infinity not other way around. If you fix $n$ first and choose the distribution later $k_max$ may not be negligible so it will not work!
