NDLI: Bandits with Knapsacks

Content Provider	IEEE Xplore Digital Library
Author	Badanidiyuru, A. Kleinberg, R. Slivkins, A.
Copyright Year	2013
Description	Author affiliation: Microsoft Res. Silicon Valley, Mountain View, CA, USA (Slivkins, A.) \|\| Comput. Sci. Dept., Cornell Univ., Ithaca, NY, USA (Badanidiyuru, A.; Kleinberg, R.)
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.
Starting Page	207
Ending Page	216
File Size	255298
Page Count	10
File Format	PDF
ISBN	9780769551357
ISSN	02725428
DOI	10.1109/FOCS.2013.30
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2013-10-26
Publisher Place	USA
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Heuristic algorithms Optimized production technology Algorithm design and analysis Pricing Vectors Approximation algorithms Benchmark testing dynamic ad allocation Multi-armed bandits exploration-exploitation tradeoff regret stochastic packing dynamic pricing dynamic procurement
Content Type	Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Approximation Algorithms for Correlated Knapsacks and Non-martingale Bandits

Pure exploration in multi-armed bandits problems (2009)

Designing multi-objective multi-armed bandits algorithms: A study

Online learning in decentralized multi-user spectrum access with synchronized explorations

Pure exploration in multi-armed bandits problems (2008).

From Stability to Low-Regret Algorithms in Stochastic Multi-Armed Bandits

Adaptive contract design for crowdsourcing markets: bandit algorithms for repeated principal-agent problems

An Analysis of the Value of Information When Exploring Stochastic, Discrete Multi-Armed Bandits

Dynamic Clustering of Contextual Multi-Armed Bandits

Bandits with Knapsacks

Similar Documents

Approximation Algorithms for Correlated Knapsacks and Non-martingale Bandits

Pure exploration in multi-armed bandits problems (2009)

Designing multi-objective multi-armed bandits algorithms: A study

Online learning in decentralized multi-user spectrum access with synchronized explorations

Pure exploration in multi-armed bandits problems (2008).

From Stability to Low-Regret Algorithms in Stochastic Multi-Armed Bandits

Adaptive contract design for crowdsourcing markets: bandit algorithms for repeated principal-agent problems

An Analysis of the Value of Information When Exploring Stochastic, Discrete Multi-Armed Bandits

Dynamic Clustering of Contextual Multi-Armed Bandits

Bandits with Knapsacks