An efficient algorithm for contextual bandits with knapsacks, and an extension to concave objectives

Abstract

We consider a contextual version of multi-armed bandit problem with global knapsack constraints. In each round, the outcome of pulling an arm is a scalar reward and a resource consumption vector, both dependent on the context, and the global knapsack constraints require the total consumption for each resource to be below some pre-fixed budget. The learning agent competes with an arbitrary set of context-dependent policies. This problem was introduced by Badanidiyuru et al. (2014), who gave a computationally inefficient algorithm with near-optimal regret bounds for it. We give a computationally efficient algorithm for this problem with slightly better regret bounds, by generalizing the approach of Agarwal et al. (2014) for the non-constrained version of the problem. The computational time of our algorithm scales logarithmically in the size of the policy space. This answers the main open question of Badanidiyuru et al. (2014). We also extend our results to a variant where there are no knapsack constraints but the objective is an arbitrary Lipschitz concave function of the sum of outcome vectors.

Extended abstract appeared in COLT 2016

References in corpus (4)

• Taming the Monster: A Fast and Simple Algorithm for Contextual Bandits
• Efficient Optimal Learning for Contextual Bandits
• Knapsack based Optimal Policies for Budget-Limited Multi-Armed Bandits
• Algorithms with Logarithmic or Sublinear Regret for Constrained Contextual Bandits

Cited by in corpus (14)

• Algorithms with Logarithmic or Sublinear Regret for Constrained Contextual Bandits
• Linear Contextual Bandits with Knapsacks
• Resourceful Contextual Bandits
• An Efficient Pessimistic-Optimistic Algorithm for Stochastic Linear Bandits with General Constraints
• Optimal No-regret Learning in Repeated First-price Auctions
• Exploration-Exploitation Trade-off in Reinforcement Learning on Online Markov Decision Processes with Global Concave Rewards
• Inventory Balancing with Online Learning
• Contextual Blocking Bandits
• Learning Adaptive Display Exposure for Real-Time Advertising
• Matching while Learning
• Efficient Reinforcement Learning in Factored MDPs with Application to Constrained RL
• A Multi-Armed Bandit-based Approach to Mobile Network Provider Selection
• Bandits with Knapsacks beyond the Worst-Case
• The Symmetry between Arms and Knapsacks: A Primal-Dual Approach for Bandits with Knapsacks