This paper defines a new learning problem of learning 1-NN graph on a metric space consisting of n points using a noisy distance oracle. Ignoring the metric structure, the problem can be viewed n separate best arm identification problems (for each node find its nearest neighbor by calling the oracle). The best arm identification problem can solved by UCB-like methods that maintain confidence intervals for each distance and has been studied extensively in the literature. The paper proposes an improved algorithm that exploits the triangle inequality and symmetry of the underlying metric in order to improve the confidence intervals. As the paper shows that the improvement doesn't help much for the worst-case metric space. However, the paper also shows that the improvement helps when the metric space consists of clusters. The paper is nicely written. The theoretical analysis is correct and non-trivial. The paper has some simple experiments. The problem definition is novel and it seems that it has some practical applications. The improvements are simple, yet non-trivial.