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!


2 Answers 2


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).


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)$...


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.