\begin{algorithmic}
\newcommand{\UB}{UB($S_i$, $h$, $\delta_k$)}
\newcommand{\LB}{LB($S_i$,$h$,$\delta_k$))}
\newcommand{\EF}{$\exists h_1$,$h_2 \in H_i$ : $h_1$($x$) $\neq$ $h_2$($x$)}

\STATE $i = 1$, $D_i = D$, $H_i$, $S_i = \phi$, and $k = 1$
\STATE
\STATE $DISAGREE_D$($H_i$) = $\textbf{Pr}_{x~D}$[$\exists h_1$, $h_2 \in G$ : $h_1$($x$) $\neq h_2$($x$)]
\STATE
\WHILE{ $DISAGREE_{D}$($H_i$)( $min_{h \in H_i}$ UB($S_i$, $h$, $\delta_k$) - $min_{h \in H_i}$ LB($S_i$,$h$,$\delta_k$)) $>$ $\varepsilon$ }
	\STATE Set $S_i = \phi$, $H'_i = H_i$, $k \leftarrow k + 1$
	\WHILE { $DISAGREE_{D}$($H_i$) $\geq$ $\frac{1}{2} DISAGREE_D$($H_i$) }
		\IF{$DISAGREE_{D}$($H'_i$)($min_{h \in H'_i}$ \UB - $min_{h \in H]_i}$ \LB) $\leq \varepsilon$}
			\STATE return h = $argmin_h \ in H'_i$ \UB.
		\ELSE
			\STATE $S'_i$ = Rejection Sample $2|S_i| + 1$ samples $x$ from $D$ satisfying: \EF
			\STATE $S_i \leftarrow S_i \bigcup \lbrace $($x$,O($x$)) : $x \in S'_i \rbrace$; $k \leftarrow k + 1$;
			\STATE $H'_i = \lbrace h \in H_i$ : \LB $ \leq min_{h' \in H_i}$ \UB $\rbrace$, $k \leftarrow k + 1$.
		\ENDIF
	\ENDWHILE
	\STATE $H_{i + 1} \leftarrow H'_i$;
	\STATE $D_{i + 1} \leftarrow D_i$ conditioned on the disagreement \EF ;
	\STATE $i \leftarrow i + 1.$
\ENDWHILE 
\RETURN $h = argmin_{h \in H_i}$ \UB
\STATE
\end{algorithmic}