Bandits with concave rewards and convex knapsacks
Bandits with concave rewards and convex knapsacks
复制标题
DOI：
10.1145/2600057.2602844
复制
发表时间：
2014-02
期刊：
影响因子：
--
通讯作者：
Shipra Agrawal;Nikhil R. Devanur
中科院分区：
文献类型：
--
作者：
Shipra Agrawal;Nikhil R. Devanur
在本文中，我们考虑了一个非常一般的模型，勘探开发权衡，允许任意凹奖励和凸约束的决定，随着时间的推移，除了在时间范围上的习惯限制。该模型包含了经典的多臂强盗模型（MAB）和Badanidiyuru等人的背包强盗模型（BwK）。[2013年]第10号。我们还考虑了该模型的扩展，以允许线性上下文，类似于MAB模型的线性上下文扩展。我们证明了一个自然和简单的扩展的UCB家庭的算法MAB提供了一个多项式时间算法，具有接近最佳的遗憾保证，这个更一般的模型，并匹配的边界提供Badanidiyuru等人。[2013]对于BwK的特殊情况，这是相当令人惊讶的。我们还提供了计算上更有效的算法，通过建立有趣的连接，这个问题和其他研究问题/算法，如Blackwell逼近问题，在线凸优化，和凸优化的弗兰克-沃尔夫技术。我们给出了几个具体的应用程序的例子，这种更一般的土匪模型允许更丰富和/或更有效的配方的问题。
In this paper, we consider a very general model for exploration-exploitation tradeoff which allows arbitrary concave rewards and convex constraints on the decisions across time, in addition to the customary limitation on the time horizon. This model subsumes the classic multi-armed bandit (MAB) model, and the Bandits with Knapsacks (BwK) model of Badanidiyuru et al.[2013]. We also consider an extension of this model to allow linear contexts, similar to the linear contextual extension of the MAB model. We demonstrate that a natural and simple extension of the UCB family of algorithms for MAB provides a polynomial time algorithm that has near-optimal regret guarantees for this substantially more general model, and matches the bounds provided by Badanidiyuru et al.[2013] for the special case of BwK, which is quite surprising. We also provide computationally more efficient algorithms by establishing interesting connections between this problem and other well studied problems/algorithms such as the Blackwell approachability problem, online convex optimization, and the Frank-Wolfe technique for convex optimization. We give examples of several concrete applications, where this more general model of bandits allows for richer and/or more efficient formulations of the problem.