Bandits with Knapsacks
arXiv:1305.2545 · doi:10.1109/FOCS.2013.30
Abstract
Multi-armed bandit problems are the predominant theoretical model of exploration-exploitation tradeoffs in learning, and they have countless applications ranging from medical trials, to communication networks, to Web search and advertising. In many of these application domains the learner may be constrained by one or more supply (or budget) limits, in addition to the customary limitation on the time horizon. The literature lacks a general model encompassing these sorts of problems. We introduce such a model, called "bandits with knapsacks", that combines aspects of stochastic integer programming with online learning. A distinctive feature of our problem, in comparison to the existing regret-minimization literature, is that the optimal policy for a given latent distribution may significantly outperform the policy that plays the optimal fixed arm. Consequently, achieving sublinear regret in the bandits-with-knapsacks problem is significantly more challenging than in conventional bandit problems. We present two algorithms whose reward is close to the information-theoretic optimum: one is based on a novel "balanced exploration" paradigm, while the other is a primal-dual algorithm that uses multiplicative updates. Further, we prove that the regret achieved by both algorithms is optimal up to polylogarithmic factors. We illustrate the generality of the problem by presenting applications in a number of different domains including electronic commerce, routing, and scheduling. As one example of a concrete application, we consider the problem of dynamic posted pricing with limited supply and obtain the first algorithm whose regret, with respect to the optimal dynamic policy, is sublinear in the supply.
An extended abstract of this work has appeared in the 54th IEEE Symposium on Foundations of Computer Science (FOCS 2013). 55 pages. Compared to the initial "full version" from May'13, this version has a significantly revised presentation and reflects the current status of the follow-up work. Also, this version contains a stronger regret bound in one of the main results
References in corpus (5)
Cited by in corpus (44)
- Bandits with Knapsacks
- Algorithms with Logarithmic or Sublinear Regret for Constrained Contextual Bandits
- Linear Contextual Bandits with Knapsacks
- An efficient algorithm for contextual bandits with knapsacks, and an extension to concave objectives
- Linear Stochastic Bandits Under Safety Constraints
- Thompson Sampling for Budgeted Multi-armed Bandits
- Bandits with concave rewards and convex knapsacks
- Achieving Fairness in the Stochastic Multi-armed Bandit Problem
- Robust Influence Maximization
- Optimal Resource Allocation with Semi-Bandit Feedback
- Online Stochastic Optimization with Wasserstein Based Non-stationarity
- Optimal Auctions for Correlated Buyers with Sampling
- Hierarchical Adaptive Contextual Bandits for Resource Constraint based Recommendation
- Competing Against Equilibria in Zero-Sum Games with Evolving Payoffs
- Logarithmic regret bounds for Bandits with Knapsacks
- Inventory Balancing with Online Learning
- Upper Counterfactual Confidence Bounds: a New Optimism Principle for Contextual Bandits
- Procrastinating with Confidence: Near-Optimal, Anytime, Adaptive Algorithm Configuration
- Stochastic Bandits with Linear Constraints
- Liquid Welfare Guarantees for No-Regret Learning in Sequential Budgeted Auctions
- On Policies for Single-leg Revenue Management with Limited Demand Information
- Budget-Constrained Bandits over General Cost and Reward Distributions
- Multi-Step Budgeted Bayesian Optimization with Unknown Evaluation Costs
- Constrained Thompson Sampling for Wireless Link Optimization
- Discovering Valuable Items from Massive Data
- Episodic Multi-armed Bandits
- Unifying the stochastic and the adversarial Bandits with Knapsack
- Online Learning in Budget-Constrained Dynamic Colonel Blotto Games
- Dynamic Pricing with Finitely Many Unknown Valuations
- Continuous-Time Multi-Armed Bandits with Controlled Restarts
- Provably Efficient Algorithms for Multi-Objective Competitive RL
- Matching while Learning
- Efficient Reinforcement Learning in Factored MDPs with Application to Constrained RL
- A Farewell to Arms: Sequential Reward Maximization on a Budget with a Giving Up Option
- Combinatorial Bandits for Incentivizing Agents with Dynamic Preferences
- Algorithms for Online Matching, Assortment, and Pricing with Tight Weight-dependent Competitive Ratios
- Optimization-friendly generic mechanisms without money
- Risk-Aware Algorithms for Adversarial Contextual Bandits
- The Symmetry between Arms and Knapsacks: A Primal-Dual Approach for Bandits with Knapsacks
- Price of Safety in Linear Best Arm Identification
- Thompson Sampling for Linearly Constrained Bandits
- A Map of Bandits for E-commerce
- Bandit based centralized matching in two-sided markets for peer to peer lending
- Matrix games with bandit feedback