Top $K$ Ranking for Multi-Armed Bandit with Noisy Evaluations
This addresses a practical challenge in online decision-making with imperfect feedback, offering theoretical guarantees for improved performance in scenarios like recommendation systems, but it is incremental as it builds on existing bandit frameworks.
The paper tackles the problem of selecting top K arms in a multi-armed bandit setting with noisy evaluations, deriving algorithms with regret bounds of O~(T^{2/3}) for generalized linear functions and O~(√T) for noisy linear functions, and empirically validates these results.
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.