Bandits with Knapsacks

By Ashwinkumar Badanidiyuru, Robert D. Kleinberg, Aleksandrs Slivkins. IEEE Annual Symposium on Foundations of Computer Science, 2013

495 citations recorded by the source corpus.

Multi-armed bandit problems are the predominant theoretical model of exploration-exploitation tradeoffs in learning, and they have countless applications ranging from medical trials, to communication networks, to Web search and advertising. In many of these application domains the learner may be constrained by one or more supply (or budget) limits, in addition to the customary limitation on the time horizon. The literature lacks a general model encompassing these sorts of problems. We introduce such a model, called "bandits with knapsacks", that combines aspects of stochastic integer programming with online learning. A distinctive feature of our problem, in comparison to the existing regret-minimization literature, is that the optimal policy for a given latent distribution may significantly outperform the policy that plays the optimal fixed arm. Consequently, achieving sub linear regret in the bandits-with-knapsacks problem is significantly more challenging than in conventional bandit problems. We present two algorithms whose reward is close to the information-theoretic optimum: one is based on a novel "balanced exploration" paradigm, while the other is a primal-dual algorithm that uses multiplicative updates. Further, we prove that the regret achieved by both algorithms is optimal up to polylogarithmic factors. We illustrate the generality of the problem by presenting applications in a number of different domains including electronic commerce, routing, and scheduling. As one example of a concrete application, we consider the problem of dynamic posted pricing with limited supply and obtain the first algorithm whose regret, with respect to the optimal dynamic policy, is sub linear in the supply.

Subfields: Computer Networks and Communications, Management Science and Operations Research

View Paper: https://www.semanticscholar.org/paper/5df142536d1b1e80930b5ad1f22db62d41d37e3a

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Networks and Communications

In Management Science and Operations Research

Citations in the corpus

Bandit Algorithms (2020, background): “exception of degenerate games, the classification of adversarial partial monitoring games is by Bartók et al. [2014]. The case of degenerate games was resolved by the present authors [Lattimore and Szepesvári, 2019a]. The policies mentioned in Note 9 are due to Bartók [2013] and Lattimore and Szepes”
Stochastic matrix games with bandit feedback (2020, background): “Each resource has a total amount available and the total amount consumed before T time-periods must be less than this total [6].”
Incentivizing exploration (2014, background): “Several recent papers (e.g., [Abraham et al. 2013; Badanidiyuru et al. 2012, 2013; Ho et al. 2013; Singla and Krause 2013]) have drawn a connection between MAB models and crowd-sourcing of tasks.”
Introduction to Multi-Armed Bandits (2019, methodology): “2 is from (Badanidiyuru et al., 2018), and Algorithm 10.”