Bandits with Knapsacks beyond the Worst-Case Analysis

"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 the algorithm's performance in a given round, and prove that it is small in all but a few rounds. Third, we provide a general template for extensions from bandits to BwK which takes advantage of some known helpful structure and apply this template to combinatorial semi-bandits and linear contextual bandits. Our results build on the BwK algorithm from (Agrawal and Devanur, 2014), providing new analyses thereof.