At a high level, I am wondering if in a sequential process it is better to reutilize samples even if these samples have been used to make past decisions.
Let me formalize my doubts in a toy example where, informally, the goal is to select a coin with the lowest bias in a sequence of coins. We do so by sequentially drawing samples from two coins at a time, maintaining a $(1-\delta)$-confidence interval for each of them, and discarding a coin as soon as the two intervals detach. The idea is that, for the coin that we keep, we reutilize the samples we have already drawn to compare it to the next coin.
Let $(\mu_{k})_{k\in\mathbb{N}}$ be a sequence of numbers in $[0,1]$, representing the bias of a sequence of coins (where Heads is 1 and Tails is 0).
At the beginning, denote coin $1$ by "old", coin 2 by "new", $n_{0} = 0$, and $\delta\in(0,1)$. The process unfolds in epochs.
During each epoch $\tau\in\mathbb{N}$
- We draw $n_{\tau-1}$ samples of the "new" coin, independently of the past and each other.
- We repeatedly draw 2 samples at the time, 1 from the "old" coin and $1$ from the "new" coin (independently of the past and each other), interrupting as soon as $n_{\tau}$ samples have been drawn, where $n_{\tau}$ is the smallest number of samples needed to verify $$ \overline{X}^{\tau,\text{old}}+\sqrt{\frac{\log(2/\delta)}{2n_{\tau}}}\le\overline{X}^{\tau,\text{new}}-\sqrt{\frac{\log(2/\delta)}{2n_{\tau}}}\qquad\text{or}\qquad\overline{X}^{\tau,\text{new}}+\sqrt{\frac{\log(2/\delta)}{2n_{\tau}}}\le\overline{X}^{\tau,\text{old}}-\sqrt{\frac{\log(2/\delta)}{2n_{\tau}}}\;,$$ and $\overline{X}^{\tau,\text{old}}$ (resp., $\overline{X}^{\tau,\text{new}}$) is the sum of all the samples of the "old" (resp., "new") coin that have been drawn throughout epochs divided by $n_{\tau}$ (i.e, the empirical means).
- If the first condition in the display above is true, then eliminate the "new" coin, conclude the current epoch, and denote by "new" the next unused coin in the sequence. If the second condition in the display above is true, then eliminate the "old" coin, conclude the current epoch, denote by "old" the "new" coin and by "new" the next unused coin in the sequence.
For any $s\in \mathbb N$, if $s$ samples have been drawn so far throughout all epochs, the process is in some (random) epoch that we denote by $\tau(s)$. Moreover, we denote the (random) indices of the two active "old" and "new" coins at time a $s\in\mathbb{N}$ by $k(s,\text{old})$ and $k(s,\text{new})$.
We want to find a (sharp) upper bound, for any $s\in\mathbb{N}$ and $\varepsilon>0$, for the probabilities $$ \mathbb{P}\left(\left|\mu_{k(s,\text{old})}-\overline{X}^{\tau(s),\text{old}} \right|>\varepsilon\right)\qquad\text{and}\qquad\mathbb{P}\left(\left|\mu_{k(s,\text{new})}-\overline{X}^{\tau(s),\text{new}}\right|>\varepsilon\right)\;. $$
The idea is that, if we started drawing fresh samples at the beginning of each epoch (throwing away the old ones), we would easily bound the tail probability above with Hoeffding's inequality. I am wondering if the same can be done when samples are recycled, maintaining the exponentially small tails.