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

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