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:
- Generalized Linear Model (GLM) Setting: Here, the evaluation is a noisy, non-linear function of the reward (e.g., a sigmoid/logistic function).
- Linear Setting: The evaluation is simply the reward scaled by a constant plus noise.
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.
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