@inproceedings{sankararaman2021bandits,
author = {Sankararaman, Karthik Abinav and Slivkins, Alex},
title = {Bandits with Knapsacks beyond the Worst Case},
booktitle = {NeurIPS 2021},
year = {2021},
month = {December},
abstract = {Bandits with Knapsacks (BwK) is a general model for multi-armed bandits under supply/budget constraints. While worst-case regret bounds for BwK are well-understood, we present three results that go beyond the worst-case perspective. First, we provide upper and lower bounds which amount to a full characterization for logarithmic, instance-dependent regret rates. Second, we consider "simple regret" in BwK, which tracks algorithm's performance in a given round, and prove that it is small in all but a few rounds. Third, we provide a general "reduction" from BwK to bandits which takes advantage of some known helpful structure, and apply this reduction to combinatorial semi-bandits, linear contextual bandits, and multinomial-logit bandits. Our results build on the BwK algorithm from \citet[AgrawalDevanur-ec14], providing new analyses thereof.},
url = {http://approjects.co.za/?big=en-us/research/publication/bandits-with-knapsacks-beyond-the-worst-case/},
}