Help needed for understanding proof of No Regret Multi Armed Bandit Algorithm
I don't think you wrote anything incorrect, it's just that you didn't finish your proof yet. How are you going to go from there to an actual bound on the regret? You're going to have to use the regret guarantee of the gradient descent algorithm. But we didn't run Gradient Descent on all of the time steps. We only ran it on the time steps not in $S_T$. So we get a regret bound for the steps not in $S_T$ from gradient descent, which is $O\left(\frac{n}{\delta}\sqrt{T}\right)$. And we have to use a separate bound for the time steps in $S_T$. The proof uses the easiest one: at each such step, at worst, the algorithm has loss $1$ while $i^*$ has loss zero, so the contribution to regret from that step is at most $1$, for a total of $|S_T|$, which in expectation is $\delta T$.

As a sidenote, I am not sure that independence of $i^*$ and $\hat{\ell}_t$ is really being used, maybe it is just linearity of expectation (?).