Adversarial bandits with knapsacks

Nicole Immorlica, Karthik Abinav Sankararaman, Robert Schapire, Aleksandrs Slivkins

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2 Scopus citations

Abstract

We consider Bandits with Knapsacks (henceforth, BwK), a general model for multi-Armed bandits under supply/budget constraints. In particular, a bandit algorithm needs to solve a well-known knapsack problem: find an optimal packing of items into a limited-size knapsack. The BwK problem is a common generalization of numerous motivating examples, which range from dynamic pricing to repeated auctions to dynamic ad allocation to network routing and scheduling. While the prior work on BwK focused on the stochastic version, we pioneer the other extreme in which the outcomes can be chosen adversarially. This is a considerably harder problem, compared to both the stochastic version and the 'classic' adversarial bandits, in that regret minimization is no longer feasible. Instead, the objective is to minimize the competitive ratio: The ratio of the benchmark reward to algorithm's reward. We design an algorithm with competitive ratio O(log T) relative to the best fixed distribution over actions, where T is the time horizon; we also prove a matching lower bound. The key conceptual contribution is a new perspective on the stochastic version of the problem. We suggest a new algorithm for the stochastic version, which builds on the framework of regret minimization in repeated games and admits a substantially simpler analysis compared to prior work. We then analyze this algorithm for the adversarial version, and use it as a subroutine to solve the latter. Our algorithm is the first 'black-box reduction' from bandits to BwK: it takes an arbitrary bandit algorithm and uses it as a subroutine. We use this reduction to derive several extensions.

Original languageEnglish (US)
Title of host publicationProceedings - 2019 IEEE 60th Annual Symposium on Foundations of Computer Science, FOCS 2019
PublisherIEEE Computer Society
Pages202-219
Number of pages18
ISBN (Electronic)9781728149523
DOIs
StatePublished - Nov 2019
Externally publishedYes
Event60th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2019 - Baltimore, United States
Duration: Nov 9 2019Nov 12 2019

Publication series

NameProceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
Volume2019-November
ISSN (Print)0272-5428

Conference

Conference60th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2019
CountryUnited States
CityBaltimore
Period11/9/1911/12/19

All Science Journal Classification (ASJC) codes

  • Computer Science(all)

Keywords

  • Adversarial Online Learning
  • Multi-Armed bandits
  • Online Packing

Fingerprint Dive into the research topics of 'Adversarial bandits with knapsacks'. Together they form a unique fingerprint.

  • Cite this

    Immorlica, N., Sankararaman, K. A., Schapire, R., & Slivkins, A. (2019). Adversarial bandits with knapsacks. In Proceedings - 2019 IEEE 60th Annual Symposium on Foundations of Computer Science, FOCS 2019 (pp. 202-219). [8948695] (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS; Vol. 2019-November). IEEE Computer Society. https://doi.org/10.1109/FOCS.2019.00022