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

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!

• Since $n=\Delta=1$ is a counterexample, you'll have to say how the context constrains $n,\,\Delta$. – J.G. Oct 21 '20 at 16:53
• From a typo, I guess. The opposite inequality is true. – user436658 Oct 21 '20 at 16:54
• @ProfessorVector Oh, dear! It comes at the end of a chain of $\ge$s at the bottom of page 8, so a $\le$ is unhelpful. – J.G. Oct 21 '20 at 16:56
• I've alerted the paper's authors of this discrepancy, though someone else probably told them 7 years ago. It's been cited 77 times, but I don't know how many such citations already brought it up. – J.G. Oct 21 '20 at 17:05
• Note that @VianneyPerchet is one of the paper's authors. – J.G. Oct 22 '20 at 12:25

## 3 Answers

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*}

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

• Thanks a lot! I still don't understand how to obtain $(1-e^{-1}) / (4 \Delta)$, could you maybe spell that out for me? – Tchaikovski Oct 22 '20 at 9:39

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