Bandits and Experts in Metric Spaces
Bandits and Experts in Metric Spaces
复制标题
DOI：
10.1145/3299873
复制
发表时间：
2019-08-01
影响因子：
2.5
通讯作者：
Upfal, Eli
中科院分区：
文献类型：
--
作者：
Kleinberg, Robert;Slivkins, Aleksandrs;Upfal, Eli
在一个多臂强盗问题中，一种在线算法从一系列试验中选择一组策略，以最大程度地利用所选策略的总收益。虽然众所周知，匪徒算法的性能具有较小的有限策略集，但大型策略集的匪徒问题仍然是积极调查的话题，这是受实际应用的动机，例如在线拍卖和网络广告。此类研究的目的是确定能够设计有效解决方案的广泛而自然的策略集和回报功能。在这项工作中，我们研究了多军匪徒问题的一般环境，其中策略形成了指标空间和回报功能满足了对度量的Lipschitz条件。我们将这个问题称为Lipschitz mab问题。我们为在这种情况下提供了多军匪徒问题的解决方案。也就是说，对于每个度量空间，我们定义了一个均衡器不变性，该等轴测图从Lipschitz mab mab算法的性能下方界定，并为此度量空间进行界定，并且我们提出了一种算法，该算法是任意接近符合此界限的算法。此外，我们的技术为良性回报功能提供了更好的结果。我们还讨论了该问题的全反馈（“最佳专家”）版本，在每一轮比赛之后，所有武器的回报都会被揭示。
In a multi-armed bandit problem, an online algorithm chooses from a set of strategies in a sequence of trials to maximize the total payoff of the chosen strategies. While the performance of bandit algorithms with a small finite strategy set is well understood, bandit problems with large strategy sets are still a topic of active investigation, motivated by practical applications, such as online auctions and web advertisement. The goal of such research is to identify broad and natural classes of strategy sets and payoff functions that enable the design of efficient solutions.In this work, we study a general setting for the multi-armed bandit problem, in which the strategies form a metric space, and the payoff function satisfies a Lipschitz condition with respect to the metric. We refer to this problem as the Lipschitz MAB problem. We present a solution for the multi-armed bandit problem in this setting. That is, for every metric space, we define an isometry invariant that bounds from below the performance of Lipschitz MAB algorithms for this metric space, and we present an algorithm that comes arbitrarily close to meeting this bound. Furthermore, our technique gives even better results for benign payoff functions. We also address the full-feedback ("best expert") version of the problem, where after every round the payoffs from all arms are revealed.