Proposition 2, p. 22 — every algorithm has E(R^{PLB}_{T₀}) ≥ C₀C_pT₀ on some PLB with ξ_t ∈ PB(ξ̃, C_p), C₀ depending only on ξ̃

Let $d\ge2$ and let $\tilde\xi\in\mathbb R^d$ have all entries positive. Then there is a constant $C_0>0$, depending only on $\tilde\xi$, with the following property.

Let $C_p\ge0$ satisfy $C_p/2<\min_{i\in[d]}\tilde\xi_i$, let $(\Omega,P)$ be a probability space carrying a measurable noise process $(\eta_t)_{t\ge1}$, and let $\mathcal A^*$ be any (possibly randomized) algorithm. Then there exist deterministic parameters $(\xi_t)_{t\ge1}$ and nonempty finite action sets $(\mathcal A_t)_{t\ge1}$ such that

1. $\xi_t\in PB(\tilde\xi,C_p)$, i.e. $\|\xi_t-\tilde\xi\|_\infty\le C_p/2$, for every $t$;
2. $\|\xi_s-\xi_t\|_\infty\le C_p$ for all $s,t$, so the rewards $Z_t=\langle\xi_t,A_t\rangle+\eta_t$ form a perturbed linear bandit with perturbation $C_p$;
3. every action $a\in\mathcal A_t$ has exactly one nonzero entry and $|\langle\xi_t,a\rangle|\le1$ (Conditions 1 and 3 of the paper's upper bound);
4. when $\mathcal A^*$ is run on this bandit, for every horizon $T_0\ge1$

The regret of every algorithm therefore grows linearly in $C_pT_0$ in the worst case, so the linear term $2a_{\max}C_pT_0$ in the paper's upper bound for M-LinUCB (Lemma 3) cannot be removed: adversarial perturbations of size $C_p$ force regret of order $C_pT_0$.

Formalization Note The hypothesis $d\ge2$ is added: the paper's proof uses the second smallest entry of $\tilde\xi$, and for $d=1$ the statement is false (all parameters in $PB(\tilde\xi,C_p)$ are positive, so always playing the largest action has zero regret). The hypothesis $C_p\ge0$ makes $PB(\tilde\xi,C_p)$ nonempty. The constant $C_0$ is quantified after $\tilde\xi$ and before $C_p$, the probability space, the noise, the algorithm and $T_0$. The parameters and action sets are deterministic and are chosen after the algorithm and the noise are fixed, as in the paper's construction. The noise is an arbitrary measurable process: the paper's PLB asks for conditionally sub-Gaussian noise, and since $\eta\equiv0$ is admissible, quantifying over all noise processes is stronger than the printed existence statement. The algorithm may use its own randomness and the noise through $\omega$ and sees past actions, past rewards and the current action set. The expectation is the lower Lebesgue integral of the nonnegative regret. Arms are Fin d, 0-based; periods are 1-based. Conclusions 2 and 3 are not in the printed statement and only strengthen it.