Contextual Bandits with Stochastic Experts
Contextual Bandits with Stochastic Experts
复制标题
随机专家的上下文强盗
DOI：
--
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
S. Shakkottai
中科院分区：
文献类型：
--
作者：
Rajat Sen;Karthikeyan Shanmugam;S. Shakkottai
本文研究了随机专家背景强盗问题，它是传统随机背景强盗问题的一种变形。在我们的问题设置中，我们假设访问一类随机专家，其中每个专家是给定上下文的手臂上的条件分布。我们提出了置信上限（UCB）算法，这个问题，采用两种不同的重要性抽样为基础的估计为每个专家的平均奖励。这两个估计器都利用了专家之间的信息泄漏，从而使用在所有专家下收集的样本来估计任何给定专家的平均奖励。这导致了$mathcal{O}left（lambda（pmb{mu}）mathcal{M}log T/Delta的实例相关遗憾界限
ight）$，其中$lambda（pmb{mu}）$是取决于专家平均奖励的项，$Delta$是最优专家的平均奖励与其他专家的平均奖励之间的最小差距，$mathcal{M}$量化了专家之间的信息泄漏。我们表明，在某些假设下，$lambda（pmb{mu}）$通常是$mathcal{O}（log N）$。我们实现了我们的算法与随机专家产生的成本敏感的分类神谕和现实世界的数据集上显示上级经验性能相比，其他国家的最先进的上下文强盗算法。
We consider the problem of contextual bandits with stochastic experts, which is a variation of the traditional stochastic contextual bandit with experts problem. In our problem setting, we assume access to a class of stochastic experts, where each expert is a conditional distribution over the arms given a context. We propose upper-confidence bound (UCB) algorithms for this problem, which employ two different importance sampling based estimators for the mean reward for each expert. Both these estimators leverage information leakage among the experts, thus using samples collected under all the experts to estimate the mean reward of any given expert. This leads to instance dependent regret bounds of $mathcal{O}left(lambda(pmb{mu})mathcal{M}log T/Delta
ight)$, where $lambda(pmb{mu})$ is a term that depends on the mean rewards of the experts, $Delta$ is the smallest gap between the mean reward of the optimal expert and the rest, and $mathcal{M}$ quantifies the information leakage among the experts. We show that under some assumptions $lambda(pmb{mu})$ is typically $mathcal{O}(log N)$. We implement our algorithm with stochastic experts generated from cost-sensitive classification oracles and show superior empirical performance on real-world datasets, when compared to other state of the art contextual bandit algorithms.