Top K Ranking for Multi-Armed Bandit with Noisy Evaluations
Top K Ranking for Multi-Armed Bandit with Noisy Evaluations
复制标题
评价嘈杂的多臂强盗 Top K 排名
DOI：
--
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
and Matteo Pirotta
中科院分区：
文献类型：
--
作者：
Evrard Garcelon;Vashist Avadhanula;A. Lazaric;and Matteo Pirotta
我们考虑一个多臂的强盗设置，在每轮开始时，学习者收到嘈杂的独立的，可能有偏见的，每个手臂的真实奖励的评估，它选择$K$武器的目标是积累尽可能多的奖励超过$T$轮。假设在每一轮，每个手臂的真正奖励是从一个固定的分布，我们得出不同的算法方法和理论保证，这取决于如何产生的评价。首先，我们证明了在一般情况下，当观察函数是真实回报的广义线性函数时，会有一个宽波浪{O}（T^{2/3}）$后悔。另一方面，我们表明，一个改进的$widetilde{O}（sqrt{T}）$遗憾时，观察功能是真正的回报噪声线性函数可以推导出来。最后，我们报告了一个实证验证，证实了我们的理论研究结果，提供了一个彻底的比较替代方法，并进一步支持这种设置在实践中的利益。
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.