Corollary 11.8: under independent priors, GREEDY suffers Bayesian regret $\ge T \cdot \frac{\alpha}{2}(\mu^0_1 - \mu^0_2)\Pr[\mu_2 > 1 - \alpha]$

Corollary 11.8. Consider independent priors such that $\Pr[\mu_1 = 1] < (\mu^0_1 - \mu^0_2)/2$. Pick any $\alpha > 0$ such that $\Pr[\mu_1 \ge 1 - 2\alpha] \le (\mu^0_1 - \mu^0_2)/2$. Then GREEDY suffers Bayesian regret

Formally: $P$ a prior supported on the finite $F \subseteq [0,1]^2$ under which the coordinates $\mu_1, \mu_2$ are independent (iIndepFun), $\Pr[\mu_1 = 1] < (\mu^0_1 - \mu^0_2)/2$, $\alpha > 0$ with $\Pr[\mu_1 \ge 1 - 2\alpha] \le (\mu^0_1 - \mu^0_2)/2$, $\pi$ any GREEDY policy and $T$ any horizon; then $T \cdot \frac{\alpha}{2}(\mu^0_1 - \mu^0_2)\Pr[\mu_2 > 1 - \alpha] \le \mathrm{BR}(T)$, with $\mathrm{BR}(T)$ the Bayesian regret (3.1) of Chapter 3 (the pseudo-regret $T\max_a \mu_a - \sum_t \mu_{a_t}$ in expectation over the run and the prior). The first hypothesis only guarantees that such an $\alpha$ exists; it is kept as printed.