We present a method for transforming an Equivalence-query algorithm using Q queries into a PAC-algorithm using Q/epsilon + O( (Q^(2/3) / epsilon ) * log(Q / delta) examples in expectation. The method is a variation of that by Schuurmans and Greiner (1995) which provides, for each gamma>0, an algorithm using (1+gamma)Q/epsilon + O( (1/epsilon) * log(Q / delta) examples in expectation. In other words, we show that the constant in front of the dominating term Q/epsilon can be made 1+o(1).
Gavaldà, R. "Note: More efficient conversion of equivalence-query algorithms to PAC algorithms". 2009.