Exp4 weighted estimated loss has conditional second moment at most k

For the fixed instance, weights and finite estimates are functions of finitely many action histories; they and their squares are measurable with finite ranges, hence integrable. Fix a positive-probability pre-action history. If $P_{t,i}=0$, then $0={\sum }_m{Q}_{t,m}E(t{)}_{m,i}$ with all terms nonnegative and every $Q_{t,m}>0$, so $E(t{)}_{m,i}=0$ for every expert $m$. Thus these coordinates contribute zero. For each realized action, at most one arm loss estimate ${\widehat{L}}_{t,i}$ is nonzero, and hence ${\tilde{L}}_{t,m}^2={\sum }_{i:P_{t,i}>0}E(t{)}_{m,i}^2{\widehat{L}}_{t,i}^2$.

On this history, for $P_{t,i}>0$, the square ${\widehat{L}}_{t,i}^2$ equals $(1-x_{t,i}{)}^2\mathrm{/}{P}_{t,i}^2$ when $A_t=i$ and zero otherwise. By [F2], its conditional mean is therefore $P_{t,i}(1-x_{t,i}{)}^2\mathrm{/}{P}_{t,i}^2=(1-x_{t,i}{)}^2\mathrm{/}{P}_{t,i}$. These finite conditional sums on the history atoms satisfy [F4]; null histories do not affect the identities. Applying this calculation to step 1.1 gives $\mathbb{E}[{\tilde{L}}_{t,m}^2\mid {\mathcal{F}}_{t-1}]={\sum }_{i:P_{t,i}>0}E(t{)}_{m,i}^2(1-x_{t,i}{)}^2\mathrm{/}{P}_{t,i}\le {\sum }_{i:P_{t,i}>0}E(t{)}_{m,i}(1-x_{t,i})\mathrm{/}{P}_{t,i}$, because $0\le E(t{)}_{m,i}(1-x_{t,i})\le 1$, whose square is at most itself.

Multiply step 2.1 by $Q_{t,m}$ and sum over experts. For every supported $i$, ${\sum }_m{Q}_{t,m}E(t{)}_{m,i}=P_{t,i}$, so the result is at most ${\sum }_{i:P_{t,i}>0}(1-x_{t,i})\le k$. This proves the conditional bound.