  Recently, it was shown that Repeat-Until-Success (RUS) circuits can achieve a
$2.5$ times reduction in expected $T$-count over ancilla-free techniques for
single-qubit unitary decomposition. However, the previously best known
algorithm to synthesize RUS circuits requires exponential classical runtime. In
this paper we present an algorithm to synthesize an RUS circuit to approximate
any given single-qubit unitary within precision $\varepsilon$ in
probabilistically polynomial classical runtime. Our synthesis approach uses the
Clifford+$T$ basis, plus one ancilla qubit and measurement. We provide
numerical evidence that our RUS circuits have an expected $T$-count on average
$2.5$ times lower than the theoretical lower bound of $3 \log_2
(1/\varepsilon)$ for ancilla-free single-qubit circuit decomposition.
