November 12, 2021
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 Agrawal and Devanur (2014), providing new analyses thereof.
Publisher
NeurIPS
December 15, 2021
Roberto Calandra, Nathan Owen Lambert, Albert Wilcox, Howard Zhang, Kristofer S. J. Pister
December 15, 2021
December 06, 2021
Takanori Maehara, Hoang NT
December 06, 2021
December 05, 2021
Evrard Garcelon, Vianney Perchet, Ciara Pike-Burke, Matteo Pirotta
December 05, 2021
December 05, 2021
Jonas Gehring, Gabriel Synnaeve, andreas krause, Nicolas Usunier
December 05, 2021