Why UCB algorithm (of multi armed bandit) gives i.i.d. reward sequence?

Question

I am reading the proofs of regrets bounds of UCB algorithms, and find the following thing quite confusing.

Suppose $T_i(t)$ is the number of times pulling arm $i$, and $I_i(t)$ is set of stages pulling arm $i$, so we have $|I_i(t)| = T_i(t)$. By UCB algorithm, the set $I_i(t)$ should be random because it is determined by the random realization of $X_{i,s}$ for $s<t$. The average of arm $i$ up to time $t$ is \begin{align} &\bar x_i(t) = \frac{1}{T_i(t)} \sum_{s \in I_i(t)} X_{i,s} \quad\quad &(1) \end{align}

Now, most papers ( including proof of Theorem 1 in Finite-time Analysis of the Multiarmed Bandit Problem https://link.springer.com/article/10.1023%2FA%3A1013689704352 and Proof of Theorem 2.1 in Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems https://arxiv.org/pdf/1204.5721.pdf) assume that (1) is the same as the following \begin{align} &\bar x_i(t) = \frac{1}{T_i(t)} \sum_{s=1}^{T_i(t)} X_{i,s} \quad\quad &(2) \end{align} and $X_{i,s}$ in (2) are i.i.d.

This is weird because

1) (1) and (2) are not summing over the same indexes

2) Although $\{X_{i,s}\}_{s=1}^t$ are independent, $I_i(t)$ and $\{X_{i,s}\}_{s=1}^t$ are not independent! So given $T_i(t)$, $\{X_{i,s}\}_{s=1}^t$ may not be independent any more.

Given this, why does Hoeffding inequality still apply?

Thanks a lot!

Answer 1

While it is true that (1) and (2) sum over different indices, they have the same distribution. This is because $X_{i,s}$ and $X_{i,s'}$ are i.i.d. hence the sum over any $T_i$ indices will have the same distribution, that is $$\sum_{s \in I_i(t)} X_{i,s} \sim \sum_{s=1}^{T_i(t)} X_{i,s}$$

You are correct that $I_i(t)$ and $T_i(t)$ depend on $\{X_{i,s}\}_{s=1}^t$. However in the proofs $T_i(t)$ is replaced by an upper bound which is independent of the observed values and so we can apply Hoeffding's to get a bound (this is done at the beginning of the proof for Theorem 1 on page 242 of your first reference).

Answer 2

I found a one line proof... $$Pr(T_j(t)=k,\ |\bar p_i(t) -p_i| \geq \epsilon) \leq Pr(|\frac{1}{ k}\sum_{s=1}^k X_{s,i} -p_i| \geq \epsilon)$$ because $Pr(A\cap B)\leq Pr(A)$...