Appendix AProofs A.1 ProofofLemma3.1

A.4 ProofofLemma4.5 The proof of Lemma 4.5 depends on another lemma, which will also be useful in the unknown hypothesis class setting. Then there exists somec for whichhc(x) / {0,1}, which is impossible. If qH(x) = c, we don't need to prove anything. Let h H denote the decision maker's decision rule. From Corollary 4.6, we know that h(x)=1 {qH(x) c}aslongasqH(x)6=c.