$L_\mathcal{D}(A(S)) \le 0.1$ with prob at least $0.9$ implies PAC learnability
The end of the proof of Theorem 7.2 explicitly states &quot;Using the fundamental theorem of statistical learning, this implies that the VC dimension of $\mathcal{H}_n$ must be finite, and therefore $\mathcal{H}_n$ is agnostic PAC learnable.&quot;
Now, this is confusing, since looking at this &quot;fundamental theorem of statistical learning&quot; (Theorem 6.7 in this book), it looks like we want to use the implication $(4) \Rightarrow (6)$, namely PAC learnability implies finite VC dimension. But, as you point out, instead of PAC learnability we only have the seemingly weaker guarantee you wrote:

With probability at least $6/7$ over $S\sim \mathcal{D}^m$ we have $L_{\mathcal{D}}(A(S))\leq 1/8$

using the notation of the book. However, if you look at the proof of Theorem 6.7, $(4) \Rightarrow (6)$ follows from the No-Free-Lunch theorem (Theorem 5.1), or rather its implication in terms of VC dimension (Corollary 6.4, and then Theorem 6.6). I'll let you check the details, but essentially it proves the stronger-looking statement you need:

Let $\mathcal{H}$ be a class of infinite VC dimension. Then, for every $m$, and every learning algorithm $A$, there exists a distribution $\mathcal{D}$ and a predictor $h\in\mathcal{H}$ such that (i) $L_{\mathcal{D}}(h) = 0$; but (ii) with probability at least $1/7$ over $S\sim \mathcal{D}^m$ we have $L_{\mathcal{D}}(A(S)) &gt; 1/8$.