Linear Contextual Bandits with Knapsacks

Abstract

We consider the linear contextual bandit problem with resource consumption, in addition to reward generation. In each round, the outcome of pulling an arm is a reward as well as a vector of resource consumptions. The expected values of these outcomes depend linearly on the context of that arm. The budget/capacity constraints require that the total consumption doesn't exceed the budget for each resource. The objective is once again to maximize the total reward. This problem turns out to be a common generalization of classic linear contextual bandits (linContextual), bandits with knapsacks (BwK), and the online stochastic packing problem (OSPP). We present algorithms with near-optimal regret bounds for this problem. Our bounds compare favorably to results on the unstructured version of the problem where the relation between the contexts and the outcomes could be arbitrary, but the algorithm only competes against a fixed set of policies accessible through an optimization oracle. We combine techniques from the work on linContextual, BwK, and OSPP in a nontrivial manner while also tackling new difficulties that are not present in any of these special cases.

References in corpus (2)

• Algorithms with Logarithmic or Sublinear Regret for Constrained Contextual Bandits
• An efficient algorithm for contextual bandits with knapsacks, and an extension to concave objectives

Cited by in corpus (14)

• Linear Stochastic Bandits Under Safety Constraints
• An Efficient Pessimistic-Optimistic Algorithm for Stochastic Linear Bandits with General Constraints
• Online Allocation and Pricing: Constant Regret via Bellman Inequalities
• Group-Fair Online Allocation in Continuous Time
• Assortment Optimization under Unknown MultiNomial Logit Choice Models
• Stochastic Bandits with Linear Constraints
• Bandit Algorithms for Precision Medicine
• Budget-Constrained Bandits over General Cost and Reward Distributions
• Fair Personalization
• Near-Optimal Primal-Dual Algorithms for Quantity-Based Network Revenue Management
• Continuous-Time Multi-Armed Bandits with Controlled Restarts
• Bandits with Knapsacks beyond the Worst-Case
• Joint Online Learning and Decision-making via Dual Mirror Descent
• The Symmetry between Arms and Knapsacks: A Primal-Dual Approach for Bandits with Knapsacks