What is the intuition behind the fact that the Explore Then Commit algorithm in a multiarmed bandit problem can achieve sublinear regret? The thing that confuses me is as follows: no matter how many times we explore each arm at the beginning, there is some chance that the arm that performed the best on the sample is actually a suboptimal arm. Then it seems to me that this implies the regret must be linear. 
 A: There exists multiple Explore-then-commit algorithms so I cannot be very precise. Yet, I think you are missing the fact that Explore-then-commit knows the horizon $T$. 
For a given horizon, you explore until you reach "sufficient" guarantee on your best arm. 
Sufficient means that you trade-off between the cost and the gain of more exploration. 
If we call $T_e$ the number explorative rounds and $T_c$ the number of commit rounds. During the explore phase, you will suffer linear regret (say $\alpha T_e$). As you said, it is true that you do mistakes during the commit phase. In expectation, it is the precision $\Delta(T_e)$ that you reached in the explore phase times the number of commit rounds $T_c = T - T_e$. To sum up, we have that 
$$R_T(\pi) \leq \alpha T_e + \Delta(T_e)(T-T_e)  $$ 
You can look at more precise maths in Tor Lattimore's Theorem 6.1. Yet, it is not "linear" because the precision you reach may be very small. $\Delta(T_e)$ will decrease exponentially with $T_e$ and will compensate the linear $T$ factor only with $T_e = \mathcal{O}(\log(T))$ rounds (for $T$ large enough compared to $\frac{1}{\Delta_i^2}$, you can look in the above reference). 
If you don't know $T$, you may want to use the "doubling trick" which starts by guessing $T$ small (e.g $T = CK$ with $C$ a small integer) and restart the algorithm with a double horizon $T:=2T$ when you reach $t=T$. By doing so, you will restart explorative phase periodically. Indeed, you cannot handle potentially infinite horizon with only a finite amount of explorative sample, because you will end up doing $T\Delta(T_e)$ mistakes which is sublinear only if $T_e$ depends on $T$.
