content_image/327609.jpg content_image/327610.jpg
## Appendix 

## A Proof of Main ERM Result 

We begin this section with five lemmas and a corollary, whose proofs only require results from functional analysis. We then prove Lemma A.7 and Theorem 1, using results from empirical process theory. 

In Lemmas A.1 through A.4 to follow, all topological results make use of the strong topology on L $^{2}$( P ). A set S ⊂ L $^{2}$( P ) is called totally bounded if, for every ϵ > 0, there exists a finite collection of radius- ϵ open balls that covers S . When we refer to convergence in these lemmas, we refer to convergence with respect to ‖·‖ . A set S is sequentially compact if every sequence of elements of S has a convergent subsequence. A set S ⊂ L $^{2}$( P ) is compact if every open cover has a finite subcover. Sequential compactness and compactness are equivalent for subsets of metric spaces. Lemma A.5 and the proof of Theorem 1 use several additional definitions, which are given immediately before Lemma A.5. 

Lemma A.1. If Π is totally bounded, then Π is compact. 

Proof. The Hilbert space L $^{2}$( P ) is a complete metric space. Therefore, [29, Corollary 6.65] implies that Π is relatively compact. In other words, Π is compact. 

For brevity, introduce Q ( A, X ) ≡ E ( Y | A, X ). Note that γ ( X ) = Q (1 , X ) − Q ( − 1 , X ). Lemma A.2. Both V and R are continuous on Π . 

Proof. The key to this proof is the following simple remark: for every policy π : X → {− 1 , 1 } , 

<img src='content_image/327609.jpg'>

Choose arbitrarily π$_{1}$, π$_{2}$ ∈ Π. By (A.1) and the Cauchy-Schwarz inequality, it holds that 

<img src='content_image/327610.jpg'>

