Why is $\sum_{t=1}^n \exp \{ -t \Delta^2\} \geq \frac{1}{\Delta^2}$?

Question

I am reading a paper about lower bounds for bandit problems (https://arxiv.org/abs/1302.1611). In Theorem 5, they prove a lower bound with an example problem with two arms. In the proof, I see the following step and I wonder where it comes from.

$\sum_{t=1}^n \exp \{ -t \Delta^2\} \geq \frac{1}{\Delta^2}$

I've tried to derive it from

• a Taylor expansion,
• Jensen's inequality,
• summing to infinity,

but I don't see it.

Thanks!

Answer 1

It is the other way aroud: \begin{align*} \sum\limits_{t = 1}^n {\exp ( - t\Delta ^2 )} & \le \sum\limits_{t = 1}^n {\int_{t - 1}^t {\exp ( - s\Delta ^2 )ds} } \\ & = \int_0^n {\exp ( - s\Delta ^2 )ds} \le \int_0^{ + \infty } {\exp ( - s\Delta ^2 )ds} = \frac{1}{{\Delta ^2 }}. \end{align*}

Answer 2

This inequality is indeed obviously incorrect... there are several typos in the statement (and the proof) of Theorem 5. First thing first, it can only be true for $n \geq 1/\Delta^2$ (for smaller $n$, the regret is upper-bounded by $n\Delta$ which is itself smaller than $1/\Delta$). Also, the sum should be from $0$ up to $t-1$ (instead from $1$ up to $t$ as we wrote).

With standard computations, you then get that regret is bigger than $\frac{1-e^{-1}}{4\Delta}$ and even bigger than $\frac{1}{4\Delta}$ asymptotically with $n$ (as it goes to infinity).

Answer 3

$$\sum\limits_{t = 1}^n {\exp ( - t\Delta ^2 )}<\sum\limits_{t = 1}^\infty {\exp ( - t\Delta ^2 )}=\sum\limits_{t = 1}^\infty {[\exp ( - \Delta ^2 )]^t}=\frac{\exp(-\Delta^2)}{1-\exp(-\Delta^2)}=\frac1{\exp\Delta^2-1}\\ <\frac1{\Delta^2}.$$