Bandits with Knapsacks
Authors:
- Ashwinkumar BadanidiyuruABAshwinkumar Badanidiyuru
- Robert KleinbergRKRobert Kleinberg
- Aleksandrs SlivkinsASAleksandrs Slivkins
- 1 October 2013
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 02725428,p. 207-216
Abstract
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.Keywords
All Related Versions
This publication has 24 references indexed in Scilit:
- Regret Minimization for Reserve Prices in Second-Price Auctions2013
- Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit ProblemsFoundations and Trends in Machine Learning, 2012
- Blind Network Revenue ManagementOperations Research, 2012
- Dynamic Pricing Without Knowing the Demand Function: Risk Bounds and Near-Optimal AlgorithmsOperations Research, 2009
- Bandits for Taxonomies: A Model-based Approach2007
- Faster and Simpler Algorithms for Multicommodity Flow and Other Fractional Packing ProblemsSIAM Journal on Computing, 2007
- The Nonstochastic Multiarmed Bandit ProblemSIAM Journal on Computing, 2002
- A Decision-Theoretic Generalization of On-Line Learning and an Application to BoostingJournal of Computer and System Sciences, 1997
- The Weighted Majority AlgorithmInformation and Computation, 1994
- Asymptotically efficient adaptive allocation rulesAdvances in Applied Mathematics, 1985