# "Peeling Technique" in Probability

So I am reading "Bandit Algorithms" by Lattimore wherein for one of the proofs he uses a technique called as "Peeling Device" which he says is a widely used tool in probability. I cannot find any references to it on the net.

For 1-subgaussian and independent random variables $$X_1 \ldots X_n$$ he defines $$\hat{\mu}_t = \frac{1}{t}\sum_{i=1}^t X_t$$ and $$S_t = t\hat{\mu}_t$$.

He then shows the following steps:

$$\mathbb{P}\left(\exists t \geq 1 : \hat{\mu}_t + \sqrt{\frac{4}{t}\log^+\frac{1}{t\delta}} + \Delta \leq 0\right)$$

$$= \mathbb{P}\left(\exists t \geq 1 : S_t + \sqrt{4t\log^+\frac{1}{t\delta}} + t\Delta \leq 0\right)$$

$$\leq \sum_{j=1}^\infty\mathbb{P}\left(\exists t \in [2^j,2^{j+1}] : S_t + \sqrt{4t\log^+\frac{1}{t\delta}} + t\Delta \leq 0\right)$$

$$\leq \sum_{j=1}^\infty\mathbb{P}\left(\exists t \leq 2^{j+1} : S_t + \sqrt{4\cdot2^j\log^+\frac{1}{2^{j+1}\delta}} + 2^j\Delta \leq 0\right)$$

where $$log^+(x) = \max \{0,log x\}$$

I believe the first inequality is the Peeling Argument. Am I right in guessing so? Also, how do we go from the first to the second inequality?

• Never heard of the "Peeling Argument", but the first inequality just seems to be the standard inequality $\mathbb P(A\cup B)\leq \mathbb P(A)+\mathbb P(B)$ for (probability) measures. And the second inequality should come from a comparison of the summands and their respective events (monotonicity of (probability) measure). Commented Jul 18 at 7:57
• Could you justify the explanation for the second inequality? Commented Jul 18 at 10:26
• I write up an answer real quick. Commented Jul 18 at 11:34

For the first inequality, note that, using standard prob. theory notation, we have \begin{align} \left\{ \exists t\geq 1:\: S_t + \sqrt{4t\cdot\log^+\left(\frac{1}{t\delta}\right)} + t\Delta\leq 0\right\} &= \bigcup_{t\geq 1}\left\{ S_t + \sqrt{4t\cdot\log^+\left(\frac{1}{t\delta}\right)} + t\Delta\leq 0\right\}\\ &= \bigcup_{j\in\mathbb N_0}\bigcup_{t\in [2^j,2^{j+1}]} \left\{ S_t + \sqrt{4t\cdot\log^+\left(\frac{1}{t\delta}\right)} + t\Delta\leq 0\right\}\\ &=\bigcup_{j\in\mathbb N_0}\left\{\exists t\in [2^j,2^{j+1}]:\: S_t + \sqrt{4t\cdot\log^+\left(\frac{1}{t\delta}\right)} + t\Delta\leq 0\right\} \end{align} thus, you get the first inequality, by the first comment I made. For the second one, we can prove that we have the following implication of events $$$$\left(\exists t\in [2^j,2^{j+1}]:\:S_t + \sqrt{4t\cdot\log^+\left(\frac{1}{t\delta}\right)} + t\Delta\leq 0\right) \Rightarrow \left(\exists t\leq 2^{j+1}:\:S_t + \sqrt{4\cdot 2^j\cdot\log^+\left(\frac{1}{2^{j+1}\delta}\right)} + 2^j\Delta\leq 0\right)$$$$ and the rest will follow from the monotonicity of $$\mathbb P$$. Since $$\sqrt{\cdot}$$ and $$\log^+$$ are both increasing functions, by $$2^j\leq t\leq 2^{j+1}$$ we have the following chain of inequalities $$$$S_t + \sqrt{4\cdot 2^j\cdot\log^+\left(\frac{1}{2^{j+1}\delta}\right)} + 2^j\Delta \leq S_t + \sqrt{4t\cdot\log^+\left(\frac{1}{t\delta}\right)} + t\Delta \leq 0,$$$$ and thus the above implication.
Edit to keep things complete: The first equality we get by multiplying both sides with $$t$$ and then performing basic calculations.
• Thanks a lot.. I have one doubt, since both $\sqrt.$ and $\log^+$ are increasing that's why substituting $2^j < t$ works for the term inside the square root and the third term, and similarly $t < 2^{j+1}$ works for the logarithm term.. However, after substituting, you removed the condition $2^j < t$ since it has now been put explicitly into the equation. Can we similarly not remove the condition that $t <= 2^{j+1}$. In other words, how do we choose which of the conditions remain? Commented Jul 18 at 14:53
• In the summands of the last term of the inequality, you could simply replace $t\leq 2^{j+1}$ with $t\in [2^j,2^{j+1}]$, as the argument in my answer doesn't force $t< 2^j$. More precisely $\exists t\in [2^j,2^{j+1}]: \dots$ implies $\exists t\leq 2^{j+1}:\dots$ (and then you could use monotonicity of $\mathbb P$ again). To be honest, I don't know why the author would do this exchange in the first place. For that one probably has to read the rest of the proof in the book you mention. Commented Jul 19 at 5:42