Advances in Bandits with Knapsacks

We study multi-armed bandit problems with supply or budget c onstraints. Multi-armed bandits is a simple model for exploration-exploitation tradeoff, i.e., the tension between acquiring new information and making optimal decisions. It is an active re search area, spanning computer science, operations research, and economics. Supply/budget constr aints arise in many realistic applications, e.g., a seller who dynamically adjusts the prices may have a limite d inventory, and an algorithm that optimizes ad placement is constrained by the advertise rs' budgets. Other motivating examples concern repeated actions, crowdsourcing markets, and netw ork routing and scheduling. We consider a general model called Bandits with Knapsacks (BwK), which subsumes the examples mentioned above.