Multi-Feedback Bandit Learning with Probabilistic Contexts
Multi-Feedback Bandit Learning with Probabilistic Contexts
复制标题
DOI：
10.24963/ijcai.2020/427
复制
发表时间：
2020-07
期刊：
影响因子：
--
通讯作者：
Da Yu;Huishuai Zhang;Wei Chen;Tie-Yan Liu;Jian Yin
中科院分区：
文献类型：
--
作者：
Da Yu;Huishuai Zhang;Wei Chen;Tie-Yan Liu;Jian Yin
上下文强盗是经典的多臂强盗设置，其中边信息（即，上下文）在手臂选择之前可用。一个标准的假设是，确切的上下文是完全已知的手臂选择之前，只有单一的反馈返回。在这项工作中，我们专注于多反馈强盗学习与概率的背景下，一束的背景下透露给代理沿着在每轮开始时，他们相应的概率。这对这样的场景进行了建模，例如从神经网络的概率输出中提取上下文，并且奖励函数由多个反馈信号联合确定。我们提出了一种基于置信度上界的核学习算法，为每个上下文束选择再生核Hilbert空间中的最佳分支。此外，我们从理论上建立了一个上限的累积遗憾相对于一个预言，知道最佳的手臂概率的情况下，并表明，该界随时间呈次线性增长。我们对机器学习模型推荐的模拟进一步验证了我们的累积遗憾的次线性，并证明我们的算法优于基于最可能的上下文选择武器的方法。
Contextual bandit is a classic multi-armed bandit setting, where side information (i.e., context) is available before arm selection. A standard assumption is that exact contexts are perfectly known prior to arm selection and only single feedback is returned. In this work, we focus on multi-feedback bandit learning with probabilistic contexts, where a bundle of contexts are revealed to the agent along with their corresponding probabilities at the beginning of each round. This models such scenarios as where contexts are drawn from the probability output of a neural network and the reward function is jointly determined by multiple feedback signals. We propose a kernelized learning algorithm based on upper confidence bound to choose the optimal arm in reproducing kernel Hilbert space for each context bundle. Moreover, we theoretically establish an upper bound on the cumulative regret with respect to an oracle that knows the optimal arm given probabilistic contexts, and show that the bound grows sublinearly with time. Our simula- tion on machine learning model recommendation further validates the sub-linearity of our cumulative regret and demonstrates that our algorithm outper- forms the approach that selects arms based on the most probable context.