2 The lower bound
Let \(\delta \in (0, 1/2]\). For every \(\delta \)-correct strategy and every \(\mu \in \mathcal{S}\), \(\mathbb {E}_\mu [\tau _\delta ] \ge T^*(\mu ) \mathrm{kl}(\delta , 1 - \delta )\).
The paper states it for \(\delta \in (0, 1)\), which is false beyond \(1/2\) (notes/paper-errata.md, E1).
A case of LMLExplore’s lower bound for every identification task, lemma 2.
For every identification task, every \(\delta \)-correct strategy with \(\delta \le 1/2\) and every admissible model with a single correct answer, \(\mathbb {E}[\tau ] \ge T^*(\mu ) \mathrm{kl}(\delta , 1 - \delta )\).
In LMLExplore.
For a family of \(\delta \)-correct strategies and every \(\mu \in \mathcal{S}\), \(\liminf _{\delta \to 0} \mathbb {E}_\mu [\tau _\delta ] / \log (1/\delta ) \ge T^*(\mu )\): for every \(c {\lt} T^*(\mu )\), \(\mathbb {E}_\mu [\tau _\delta ] \ge c \log (1/\delta )\) for all small enough \(\delta \).
A case of lemma 4.
The asymptotic lower bound for every identification task.
In LMLExplore.