RLWE decision to search: probability that oracle work on all automorphic images
(The full version of the paper is at https://eprint.iacr.org/2012/230, and my answer below refers to it.)

The answer to your question is that a different part of the reduction ensures that the oracle has advantage very close to 1 over the random samples $(a_i, a_i s + e_i + r_i)$, i.e., the oracle outputs the correct answer for almost all choices of $s, a_i, e_i, r_i$. With this guarantee, Lemmas 5.5 and 5.9 give a reduction that solves the search problem using the automorphisms and the "guess and check" technique.

The other part of reduction to which I refer is described in Section 5.2, on "worst-case to average-case decision" (Lemma 5.12). This uses a pretty standard "amplification" technique to improve the oracle's distinguishing advantage, by repeatedly invoking it on independent samples and measuring how often it accepts.