Multi-objective Contextual Bandit Problem with Similarity Information
Multi-objective Contextual Bandit Problem with Similarity Information
复制标题
DOI：
10.5072/zenodo.44578
复制
发表时间：
2018-03
期刊：
影响因子：
--
通讯作者：
E. Turğay;Doruk Öner;Cem Tekin
中科院分区：
文献类型：
--
作者：
E. Turğay;Doruk Öner;Cem Tekin
在本文中，我们提出了具有相似性信息的多目标上下文匪徒问题。此问题通过引入多个可能相互矛盾的目标来扩展经典的上下文匪徒问题，并通过相似性信息扩展了相似性信息。由于鉴于环境，每个目标中最好的手臂可能会有所不同，因此基于单个目标学习最好的手臂会危害从其他目标获得的奖励。为了评估该设置中学习者的表现，我们使用一个名为“上下文帕累托遗憾”的性能指标。从本质上讲，上下文帕累托遗憾是学习者选择的武器距离的距离之和。对于这个问题，我们开发了一种新的在线学习算法，称为Pareto上下文Zooming（PCZ），该算法利用了上下文缩放的想法，以通过对关节上下文武器设置进行自适应分区，以了解每个观察到的上下文的帕累托方面的武器根据过去选择的上下文臂对的奖励和位置。然后，我们证明pcz达到了$ \ tilde o（t^{（1+d_p）/（2+d_p）}）$ pareto遗憾，其中$ d_p $是帕托的缩放维度，取决于附近集合的大小 - 最佳上下文臂对。此外，我们证明，通过提供几乎匹配的$ \ omega（t^{（1+d_p）/（2+d_p）}）$下限，这种遗憾几乎是最佳的。
In this paper we propose the multi-objective contextual bandit problem with similarity information. This problem extends the classical contextual bandit problem with similarity information by introducing multiple and possibly conflicting objectives. Since the best arm in each objective can be different given the context, learning the best arm based on a single objective can jeopardize the rewards obtained from the other objectives. In order to evaluate the performance of the learner in this setup, we use a performance metric called the contextual Pareto regret. Essentially, the contextual Pareto regret is the sum of the distances of the arms chosen by the learner to the context dependent Pareto front. For this problem, we develop a new online learning algorithm called Pareto Contextual Zooming (PCZ), which exploits the idea of contextual zooming to learn the arms that are close to the Pareto front for each observed context by adaptively partitioning the joint context-arm set according to the observed rewards and locations of the context-arm pairs selected in the past. Then, we prove that PCZ achieves $\tilde O (T^{(1+d_p)/(2+d_p)})$ Pareto regret where $d_p$ is the Pareto zooming dimension that depends on the size of the set of near-optimal context-arm pairs. Moreover, we show that this regret bound is nearly optimal by providing an almost matching $\Omega (T^{(1+d_p)/(2+d_p)})$ lower bound.