Multi-armed bandit problems with dependent arms
Multi-armed bandit problems with dependent arms
复制标题
DOI：
10.1145/1273496.1273587
复制
发表时间：
2007-06
期刊：
影响因子：
--
通讯作者：
Sandeep Pandey;Deepayan Chakrabarti;D. Agarwal
中科院分区：
文献类型：
--
作者：
Sandeep Pandey;Deepayan Chakrabarti;D. Agarwal
我们提供了一个框架来利用多武装匪徒问题中武器之间的依赖关系，当依赖关系是关于武器簇的生成性模型的形式时。对于折扣奖励情况，我们找到了一个基于MDP的最优策略，并给出了它在形式误差保证下的一个近似。我们讨论了非折扣奖励情形下后悔的下界，并提出了一般的两级盗贼策略。我们提出了三种不同的总体政策实例化，并为实例化政策的遗憾如何取决于集群的特征提供了理论依据。最后，我们在大规模真实世界和合成数据上实证证明了我们的政策的有效性，并表明它们显著优于为拥有独立武器的匪徒而设计的经典政策。
We provide a framework to exploit dependencies among arms in multi-armed bandit problems, when the dependencies are in the form of a generative model on clusters of arms. We find an optimal MDP-based policy for the discounted reward case, and also give an approximation of it with formal error guarantee. We discuss lower bounds on regret in the undiscounted reward scenario, and propose a general two-level bandit policy for it. We propose three different instantiations of our general policy and provide theoretical justifications of how the regret of the instantiated policies depend on the characteristics of the clusters. Finally, we empirically demonstrate the efficacy of our policies on large-scale real-world and synthetic data, and show that they significantly outperform classical policies designed for bandits with independent arms.