I want to show that if the horizon $n$ is strictly less than the number of arms $k$ then every algorithm enjoys a regret of at least $$ \frac{n(2k-n-1)}{2k} $$ Now, Lattimore and Szepesvári start from a bandit with Gaussian arms with means $\mu=(\Delta,0,\cdots,0)$ and build an arm with the same means except at the point where the algorithms explores the least when confronted with $\mu$ which would then have mean $2\Delta$. Calling this second vector $\mu'$ and using ideas from information theory they show that $$ R_n(\pi,\nu_\mu)+R_n(\pi,\nu_{\mu'})\geq\frac{n\Delta}{4}\exp(-\frac{2n\Delta^2}{k-1}) $$ The $\Delta$ they choose must be between zero and $1/2$ so I can't use that one to solve my problem. But in my situation, perhaps there is another $\Delta\in[0,1/2]$ which I can utilize. But I don't know how to find such a $\Delta$. (Perhaps I should go a totally different route but I don't know how to do that either.)
