# Top K Ranking for Multi-Armed Bandit with Noisy Evaluations

arXiv: https://arxiv.org/abs/2112.06517 · HTML: https://mlsanity.com/paper/2112.06517/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 5 of its 22 references that are in the map.
- First posted on arXiv 13 Dec 2021.

## Builds on (most cited first, 5 of 5)

- [Taming the Monster: A Fast and Simple Algorithm for Contextual Bandits](https://mlsanity.com/paper/1402.0555/) (2014)
- [Deep Bayesian Bandits Showdown: An Empirical Comparison of Bayesian Deep Networks for Thompson Sampling](https://mlsanity.com/paper/1802.09127/) (2018)
- [Provably Optimal Algorithms for Generalized Linear Contextual Bandits](https://mlsanity.com/paper/1703.00048/) (2017)
- [Competence-Level Prediction and Resume & Job Description Matching Using Context-Aware Transformer Models](https://mlsanity.com/paper/2011.02998/) (2020)
- [Machine Learning approach for Credit Scoring](https://mlsanity.com/paper/2008.01687/) (2020)

## Built on by (most cited first, 3 of 3)

- [Improved Adaptive Algorithm for Scalable Active Learning with Weak Labeler](https://mlsanity.com/paper/2211.02233/) (2022)
- [Cost-efficient Crowdsourcing for Span-based Sequence Labeling: Worker Selection and Data Augmentation](https://mlsanity.com/paper/2305.06683/) (2023)
- [PAC-CF: Calibrating Irreversible Frontier Pruning in LLM-Guided Search](https://mlsanity.com/paper/2604.14345/) (2026)

## Abstract (arXiv)

We consider a multi-armed bandit setting where, at the beginning of each round, the learner receives noisy independent, and possibly biased, 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 widetildeO(T2/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 widetildeO(√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.