Contextual Bandits with Cross-learning
Contextual Bandits with Cross-learning
复制标题
具有交叉学习的上下文强盗
DOI：
10.1287/moor.2022.1313
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Jon Schneider
中科院分区：
文献类型：
--
作者：
S. Balseiro;Negin Golrezaei;Mohammad Mahdian;V. Mirrokni;Jon Schneider
在经典的上下文强盗问题中，在每一轮t中，学习者观察某个上下文c，选择某个动作i来执行，并获得某个奖励[公式：见正文]。我们考虑这个问题的变体，其中除了获得奖励[公式：见正文]之外，学习者还学习[公式：见正文]在集合[公式：见正文]中的其他上下文[公式：见正文]的值，即在不同上下文[公式：见正文]下执行该动作所获得的奖励。这种变体出现在几种策略设置中，例如学习如何在不真实的重复拍卖中出价，这一点最近受到了很多关注，因为许多平台已经转向运行第一价格拍卖。我们称这个问题为交叉学习的上下文强盗问题。经典上下文强盗问题的最佳算法实现了[公式：见正文]对所有静态策略的后悔，其中C是上下文的数量，K是动作的数量，T是回合的数量。我们设计和分析了新的算法的上下文强盗问题的交叉学习，并表明他们的遗憾有更好的依赖于上下文的数量。在完全的交叉学习下，当选择一个动作时，所有上下文的奖励都是学习的，也就是说，集合[公式：见正文]包含所有上下文，我们证明了我们的算法实现了后悔[公式：见正文]，消除了对C的依赖。对于任何其他情况，也就是说，在部分交叉学习下，对于（i，c）的某些上下文-动作对，遗憾界限取决于集合[公式：见文本]如何影响上下文之间交叉学习的程度。我们模拟我们的算法从广告交易所运行的第一价格拍卖的真实的拍卖数据，并表明它们优于传统的上下文强盗算法。
In the classic contextual bandits problem, in each round t, a learner observes some context c, chooses some action i to perform, and receives some reward [Formula: see text]. We consider the variant of this problem in which in addition to receiving the reward [Formula: see text], the learner also learns the values of [Formula: see text] for some other contexts [Formula: see text] in set [Formula: see text], that is, the rewards that would be achieved by performing that action under different contexts [Formula: see text]. This variant arises in several strategic settings, such as learning how to bid in nontruthful repeated auctions, which has gained a lot of attention lately as many platforms have switched to running first price auctions. We call this problem the contextual bandits problem with cross-learning. The best algorithms for the classic contextual bandits problem achieve [Formula: see text] regret against all stationary policies, in which C is the number of contexts, K the number of actions, and T the number of rounds. We design and analyze new algorithms for the contextual bandits problem with cross-learning and show that their regret has better dependence on the number of contexts. Under complete cross-learning in which the rewards for all contexts are learned when choosing an action, that is, set [Formula: see text] contains all contexts, we show that our algorithms achieve regret [Formula: see text], removing the dependence on C. For any other cases, that is, under partial cross-learning in which [Formula: see text] for some context–action pair of (i, c), the regret bounds depend on how the sets [Formula: see text] impact the degree to which cross-learning between contexts is possible. We simulate our algorithms on real auction data from an ad exchange running first price auctions and show that they outperform traditional contextual bandit algorithms.
DOI：
10.1145/3219166.3219233
发表时间：
2017-11
期刊：
Proceedings of the 2018 ACM Conference on Economics and Computation
影响因子：
--
作者：
M. Braverman;Jieming Mao;Jon Schneider;Matt Weinberg
通讯作者：
M. Braverman;Jieming Mao;Jon Schneider;Matt Weinberg
影响因子：
2.7
作者：
Kanoria, Yash;Nazerzadeh, Hamid
通讯作者：
Nazerzadeh, Hamid
动态激励感知学习：关联拍卖中的稳健定价
影响因子：
2.7
作者：
Negin Golrezaei, Adel Javanmard
通讯作者：
Negin Golrezaei, Adel Javanmard