Adaptive Sampling for Coarse Ranking
This work addresses the problem of efficiently ranking items with approximate clusters, useful in social science applications involving human raters, though it appears incremental as it builds on existing active ranking methods.
The paper tackles the problem of active coarse ranking, which aims to sort items into clusters by adaptively sampling from reward distributions to reduce the number of ratings needed compared to exact ranking. It proposes the LUCBRank algorithm, deriving an upper bound on sample complexity and showing it outperforms state-of-the-art baselines in experiments on synthetic and real-world data.
We consider the problem of active coarse ranking, where the goal is to sort items according to their means into clusters of pre-specified sizes, by adaptively sampling from their reward distributions. This setting is useful in many social science applications involving human raters and the approximate rank of every item is desired. Approximate or coarse ranking can significantly reduce the number of ratings required in comparison to the number needed to find an exact ranking. We propose a computationally efficient PAC algorithm LUCBRank for coarse ranking, and derive an upper bound on its sample complexity. We also derive a nearly matching distribution-dependent lower bound. Experiments on synthetic as well as real-world data show that LUCBRank performs better than state-of-the-art baseline methods, even when these methods have the advantage of knowing the underlying parametric model.