Top K Ranking for Multi-Armed Bandit with Noisy Evaluations

Evrard Garcelon, Vashist Avadhanula, Alessandro Lazaric, Matteo Pirotta

Abstract

This paper addresses the challenge of selecting the top $K$ arms in a multi-armed bandit (MAB) setting where the learner relies on noisy and potentially biased evaluations from multiple experts. We investigate the theoretical limits of regret in this framework, identifying a "selection bias trap" that arises when greedy choices are made based on noisy observations. We prove that while generalized linear evaluation models require forced exploration, leading to $O(T^{2/3})$ regret, linear models allow for a more efficient greedy approach. We introduce the Evaluation-Structure-Aware Greedy (ESAG) algorithm, which achieves the optimal $O(\sqrt{T})$ regret by leveraging the structural relationship between evaluations and rewards across all arms.

Introduction: The Challenge of Noisy Evaluations

In many real-world applications, such as content moderation at scale, human "ground truth" labels are expensive and scarce. Systems must prioritize a small subset ($K$) of items for human review out of a massive volume of candidates. To do this, they rely on automated evaluators—such as NLP or computer vision models—that provide scores for each item.

However, these evaluators are rarely perfectly calibrated. They are often biased or subject to significant noise. A fundamental difficulty in this setting is the statistical dependence between the selection of an arm and the noise in its evaluation. If an algorithm greedily selects an arm because it has a high noisy score, it is likely picking an arm where the noise happened to be positive. This selection bias makes it difficult to accurately calibrate the evaluators over time using standard techniques, as the observed rewards for selected arms are not representative of the underlying distribution.

Figure 1: Relationship between true reward and noisy evaluations, illustrating the calibration gap and selection bias.

Methodology

The authors analyze two primary settings based on the functional relationship between the evaluator's score $f$ and the true reward $r$:

1. Generalized Linear Case (GLM)

In the GLM setting, evaluators follow a model $f(r) = g(\alpha \cdot r) + \text{noise}$, where $g$ is a known link function (e.g., a sigmoid). To overcome the selection bias trap, the authors propose the GLM-$\epsilon$-greedy algorithm. This approach forces random exploration in a small fraction of rounds to collect unbiased data, which is then used to calibrate the evaluators. This strategy leads to a regret bound of $O(T^{2/3})$.

2. Linear Case

When the relationship is strictly linear, $f(r) = \alpha \cdot r + \text{noise}$, a more sophisticated approach is possible. The authors introduce the Evaluation-Structure-Aware Greedy (ESAG) algorithm. ESAG recognizes that in the linear case, the expected evaluation score is directly proportional to the evaluator's reliability parameter ($\alpha$). By averaging evaluations across all arms—not just the ones pulled—the learner can estimate the evaluators' parameters without needing explicit, regret-heavy exploration. This allows ESAG to achieve the optimal $O(\sqrt{T})$ regret.

Key Insights: Exploration vs. Structure

The significant improvement in regret from $O(T^{2/3})$ to $O(\sqrt{T})$ demonstrates that structural assumptions are highly powerful in bandit settings. In the linear case, the learner can "watch" the evaluators score items that are not pulled, gaining information about their quality without incurring the cost of pulling sub-optimal arms.

Additionally, the paper derives optimal "Oracle weights" for aggregating multiple experts. These weights are proportional to the signal-to-noise ratio ($\alpha_j / \sigma_j^2$) of each evaluator, effectively de-prioritizing noisy or uninformative models in the final ranking decision.

Experimental Results

The proposed methods were validated through extensive experiments:

  • Synthetic Data: Verified that ESAG and GLM-$\epsilon$-greedy meet their respective theoretical regret bounds in controlled environments.
  • Content Review Prioritization: Using a proprietary dataset from Meta, the researchers found that the linear-based ESAG was surprisingly robust. Even though real-world evaluators were not perfectly linear, ESAG outperformed more complex GLM-based models, suggesting it serves as a strong, stable baseline for production systems.
  • Jester Dataset: In a public joke rating task, the bandit algorithms effectively selected the "best" jokes for users by aggregating scores from various simulated ML models.

Conclusion and Future Work

This work provides the first regret bounds for the noisy evaluation ranking problem, but several limitations remain. Future research could extend these models to richer function spaces, such as Gaussian Processes, to handle more complex evaluator behaviors. Additionally, relaxing the assumption of fixed noise parameters per evaluator to account for reward-dependent variance (heteroscedastic noise) would further improve the applicability of these methods to real-world systems.

Summary updated

BibTeX
@inproceedings{garcelon2022top,
  author = {Evrard Garcelon and Vashist Avadhanula and Alessandro Lazaric and Matteo Pirotta},
  title = {{Top K Ranking for Multi-Armed Bandit with Noisy Evaluations}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2022},
}
Figure