also plays an important role. If Π is Donsker, then Lemma A.3 in Section A guarantees that Π ⋆ is nonempty and coincides with the RHS set in the above display. Finally, we define which roughly corresponds to the best approximation in Π of the closest optimal policy π ⋆ ∈ Π ⋆ to the estimated policy ̂ π . We will show that EP$_{n}$ = o$_{P}$ ( n − 1 / $^{2}$) under mild assumptions. Theorem 1 (Main ERM Result) . If ̂ π satisfies (6) and Π is Donsker, then If also Rem$_{n}$ = o$_{P}$ ( n − 1 / $^{2}$) , then R π ) = o$_{P}$ ( n − 1 / $^{2}$) . The proof of Theorem 1 is given in Section A. The above rate on R $^{(}$̂ π ) is faster than the rate of convergence of the standard error of an efficient estimator of the value V ( π ) of a policy π ∈ Π, which converges at rate n − 1 / 2 in all but degenerate cases. Note that our proof of the first result of the above theorem only uses that Π is totally bounded in L $^{2}$( P ) while that of the second one uses the stronger assumption that Π is Donsker. Three detailed remarks on this result are given in Section 3. Section 3.1 discusses why we do not expect a faster than O$_{P}$ ( n − $^{1}$) rate of regret decay for ̂ π , even within a parametric model. A notable exception to this rule of thumb occurs if Π is of finite cardinality and P ( A | X ) is known, since in this case large deviation bounds suggest very fast rates of convergence for ERMs. The same phenomenon has been noted and extensively studied in the classification literature [see the review in 23]. We now show that faster rates are attainable under some conditions if one uses a dif- ferent estimation procedure. We point this out because, in our experience, this alternative 7 2.3 Plug-In Estimators EP$_{n}$ ≡ lim inf s ↓ 0 inf π $^{⋆}$∈ Π ⋆ sup π ∈ Π: ‖ π − π $^{⋆}$‖≤ s ( P$_{n}$ − P )( f$_{̂}$ π − f$_{π}$ ) , 0 ≤ R $^{(}$̂ π ) ≤ EP$_{n}$ + [1 + o$_{P}$ (1)] Rem$_{n}$ .