Top K Ranking for Multi-Armed Bandit with Noisy Evaluations

Evrard Garcelon, Vashist Avadhanula, Alessandro Lazaric, Matteo Pirotta

Introduction: The Challenge of Noisy Pre-Evaluations

In many real-world recommendation and moderation systems, a learner must select the "top $K$" items from a large pool. However, before making a selection, the learner only has access to noisy, biased pre-evaluations—such as scores from automated AI classifiers. For instance, a social media platform might use multiple NLP and computer vision models to flag potentially harmful content for human review. These "evaluators" provide "badness scores" that are often imperfect, miscalibrated, or on different scales.

The core challenge in this Multi-Armed Bandit (MAB) setting is estimation bias. If a system always selects items with the highest scores to obtain ground-truth rewards (e.g., human labels), the resulting data becomes heavily biased toward what the models already perceive as "bad." This feedback loop makes it difficult to calibrate the evaluators over time, potentially leaving high-reward items undiscovered.

Modeling the Evaluation-Reward Relationship

The authors formalize this by treating evaluations as noisy functions of a latent true reward. They distinguish between two primary settings:

  1. Generalized Linear Model (GLM) Setting: Here, the evaluation is a noisy, non-linear function of the reward (e.g., a sigmoid/logistic function).
  2. Linear Setting: The evaluation is simply the reward scaled by a constant plus noise.
Visualization of the relationship between latent rewards and observed evaluations, showing both linear and non-linear calibration functions.

As shown in the figure above, a "perfectly calibrated" function would be a simple linear mapping. However, real-world evaluators often follow a non-linear path $f(r)$, where noise $\epsilon_i$ further obscures the true reward. This non-linearity can amplify noise, leading to a permanent suboptimality gap if not handled correctly.

Proposed Algorithms: GLM-$\epsilon$-greedy and ESAG

To address these settings, the paper introduces two novel strategies:

  • GLM-$\epsilon$-greedy: Designed for the non-linear case, this algorithm allocates a small fraction of time to random exploration. This "unbiased" data allows the system to calibrate evaluators using Maximum Likelihood Estimation (MLE), eventually overcoming the selection bias, albeit at a slower regret rate of $O(T^{2/3})$.
  • ESAG (Evaluation-Structure-Aware Greedy): This algorithm exploits the specific structure of the linear setting. The authors demonstrate that in the linear case, the average evaluation of an arm is proportional to its true reward regardless of the selection process. Consequently, ESAG can remain purely greedy and still avoid the "bias trap," achieving a much tighter $O(\sqrt{T})$ regret bound.

Empirical Performance and Key Results

The researchers validated these methods across synthetic data, a public joke-rating dataset (Jester), and a real-world content review dataset from Meta.

Comparison of cumulative 'Badness' identified by various algorithms. Bold values indicate superior performance.

The results (summarized in the table above) highlight several key insights:

  • The Cost of Non-Linearity: Non-linear link functions amplify noise, creating a "suboptimality gap" that is harder to close than in linear models.
  • Robustness of ESAG: Despite its simplicity, ESAG and its UCB-based variants (like EvalBasedUCB) consistently outperformed naive greedy strategies. ESAG proved remarkably robust even when the underlying linear assumptions were only approximations.
  • Breaking the Feedback Loop: While standard contextual bandits treat scores as fixed features, explicitly modeling them as noisy functions of the latent reward allows these algorithms to effectively manage selection bias.

Conclusion and Future Directions

This work provides a theoretical and practical framework for ranking items when pre-selection signals are noisy. By distinguishing between linear and non-linear evaluation structures, the authors offer specialized algorithms that balance exploration and exploitation more effectively than traditional MAB approaches. Future work may address non-stationary reward distributions and heteroscedastic noise, where evaluator certainty varies across the reward spectrum.

Summary updated

Abstract

We consider a multi-armed bandit setting where, at the beginning of each round, the learner receives noisy independent, and possibly biased, \emph{evaluations} of the true reward of each arm and it selects $K$ arms with the objective of accumulating as much reward as possible over $T$ rounds. Under the assumption that at each round the true reward of each arm is drawn from a fixed distribution, we derive different algorithmic approaches and theoretical guarantees depending on how the evaluations are generated. First, we show a $\widetilde{O}(T^{2/3})$ regret in the general case when the observation functions are a genearalized linear function of the true rewards. On the other hand, we show that an improved $\widetilde{O}(\sqrt{T})$ regret can be derived when the observation functions are noisy linear functions of the true rewards. Finally, we report an empirical validation that confirms our theoretical findings, provides a thorough comparison to alternative approaches, and further supports the interest of this setting in practice.
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