In clustering with noisy queries model, there are n vertices belonging to k unknown clusters. The algorithm is provided with an oracle that answers queries of whether two vertices belong to the same cluster with correct probability \(\frac{1}{2}+\frac{\delta }{2}\) . The goal is to recover the clusters with minimum number of queries. Most previous works give \(O(\frac{nk\log n}{\delta ^2}+{{\,\textrm{poly}\,}}(k,\frac{1}{\delta },\log n))\) query complexity, so we propose a framework that, given a black-box algorithm with the above query complexity, improves to \(O(\frac{n(k+\log n)}{\delta ^2}+{{\,\textrm{poly}\,}}(k,\frac{1}{\delta },\log n))\) , which matches the lower bound of the problem up to an additive \({{\,\textrm{poly}\,}}(k,\frac{1}{\delta },\log n))\) . With this framework, we propose two new algorithms, one recovers clusters with \(O(\frac{n(k+\log n)}{\delta ^2}+\frac{k^2\log ^3 n}{\delta ^4})\) queries, the other recovers clusters with \(O(\frac{n(k+\log n)}{\delta ^2}+\frac{k^4\log ^3 n}{\delta ^4}+\frac{k^3\log ^8 n}{\delta ^4})\) queries with polynomial time. The main idea is to utilize techniques from multi-armed bandit literature in the true cluster identification and verification procedure.