2
$\begingroup$

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!

$\endgroup$
5
  • $\begingroup$ Since $n=\Delta=1$ is a counterexample, you'll have to say how the context constrains $n,\,\Delta$. $\endgroup$ – J.G. Oct 21 '20 at 16:53
  • 1
    $\begingroup$ From a typo, I guess. The opposite inequality is true. $\endgroup$ – user436658 Oct 21 '20 at 16:54
  • $\begingroup$ @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. $\endgroup$ – J.G. Oct 21 '20 at 16:56
  • 2
    $\begingroup$ 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. $\endgroup$ – J.G. Oct 21 '20 at 17:05
  • $\begingroup$ Note that @VianneyPerchet is one of the paper's authors. $\endgroup$ – J.G. Oct 22 '20 at 12:25
5
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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

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

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.