mlsanityData to 7 Oct 2026

Linear Contextual Bandits with Knapsacks

arXiv 1507.06738 ↗First posted 24 Jul 2015cs.LG math.OC stat.MLcited by 82

Not on the map. Why?

Abstract (arXiv)

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.

Key facts. Cited by 82 papers in the map (data through 7 Oct 2026). First posted on arXiv 24 Jul 2015.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 9; 2022: 14; 2023: 15; 2024: 17; 2025: 10; 2026: 17.

82 papers.

Sort:

By area:

  1. 2022Contextual Bandits with Packing and Covering Constraints: A Modular Lagrangian Approach via Regressioncited by 30
  2. 2021An Efficient Pessimistic-Optimistic Algorithm for Stochastic Linear Bandits with General Constraintscited by 29
  3. 2021Stochastic Bandits for Multi-platform Budget Optimization in Online Advertisingcited by 25
  4. 2022On Kernelized Multi-Armed Bandits with Constraintscited by 23
  5. 2024Truly No-Regret Learning in Constrained MDPscited by 23
  6. 2025Online Multi-LLM Selection via Contextual Bandits under Unstructured Context Evolutioncited by 18
  7. 2021The Symmetry between Arms and Knapsacks: A Primal-Dual Approach for Bandits with Knapsackscited by 16
  8. 2023The Relative Value of Prediction in Algorithmic Decision Makingcited by 14
  9. 2022Safe Linear Bandits over Unknown Polytopescited by 13
  10. 2021Bandit Algorithms for Precision Medicinecited by 12
  11. 2022Non-monotonic Resource Utilization in the Bandits with Knapsacks Problemcited by 12
  12. 2022Optimal Contextual Bandits with Knapsacks under Realizability via Regression Oraclescited by 12
38 more
  1. 2022Online Contextual Decision-Making with a Smart Predict-then-Optimize Methodcited by 11
  2. 2025Budgeted Multiple-Expert Deferralcited by 11
  3. 2022No-regret Learning in Repeated First-Price Auctions with Budget Constraintscited by 9
  4. 2024No-Regret Algorithms in non-Truthful Auctions with Budget and ROI Constraintscited by 9
  5. 2023Directional Optimism for Safe Linear Banditscited by 8
  6. 2026Adaptive Test-Time Compute Allocation for Reasoning LLMs via Constrained Policy Optimizationcited by 8
  7. 2021Joint Online Learning and Decision-making via Dual Mirror Descentcited by 7
  8. 2023Competing for Shareable Arms in Multi-Player Multi-Armed Banditscited by 6
  9. 2024No-Regret is not enough! Bandits with General Constraints through Adaptive Regret Minimizationcited by 6
  10. 2022Integrating Reward Maximization and Population Estimation: Sequential Decision-Making for Internal Revenue Service Audit Selectioncited by 5
  11. 2023Learning the Pareto Front Using Bootstrapped Observation Samplescited by 5
  12. 2024Stochastic contextual bandits with graph feedback: from independence number to MAS numbercited by 5
  13. 2024Online Decision Deferral under Budget Constraintscited by 5
  14. 2023Coordinated Dynamic Bidding in Repeated Second-Price Auctions with Budgetscited by 4
  15. 2023Price of Safety in Linear Best Arm Identificationcited by 4
  16. 2024Contractual Reinforcement Learning: Pulling Arms with Invisible Handscited by 4
  17. 2021DMBGN: Deep Multi-Behavior Graph Networks for Voucher Redemption Rate Predictioncited by 3
  18. 2022Contextual Bandits with Knapsacks for a Conversion Modelcited by 3
  19. 2022Network Revenue Management with Demand Learning and Fair Resource-Consumption Balancingcited by 3
  20. 2022Contextual Decision-Making with Knapsacks Beyond the Worst Casecited by 3
  21. 2023Contextual Bandits with Budgeted Information Revealcited by 3
  22. 2023High-dimensional Linear Bandits with Knapsackscited by 3
  23. 2023Think Before You Duel: Understanding Complexities of Preference Learning under Constrained Resourcescited by 3
  24. 2024Best Arm Identification with Resource Constraintscited by 3
  25. 2024Testing the Feasibility of Linear Programs with Bandit Feedbackcited by 3
  26. 2025Learning to Price with Resource Constraints: From Full Information to Machine-Learned Pricescited by 3
  27. 2025Multiplayer Information Asymmetric Contextual Banditscited by 3
  28. 2026ParetoBandit: Budget-Paced Adaptive Routing for Non-Stationary LLM Servingcited by 3
  29. 2021Online Selection of Diverse Committeescited by 2
  30. 2022Dynamic Budget Throttling in Repeated Second-Price Auctionscited by 2
  31. 2022Contextual bandits with concave rewards, and an application to fair rankingcited by 2
  32. 2023Improved Algorithms for Multi-period Multi-class Packing Problems with Bandit Feedbackcited by 2
  33. 2023Small Total-Cost Constraints in Contextual Bandits with Knapsacks, with Application to Fairnesscited by 2
  34. 2023Parameter-free projected gradient descentcited by 2
  35. 2023Trading-off price for data quality to achieve fair online allocationcited by 2
  36. 2024Demand Balancing in Primal-Dual Optimization for Blind Network Revenue Managementcited by 2
  37. 2024Multi-Task Combinatorial Bandits for Budget Allocationcited by 2
  38. 2024A Complete Characterization of Learnability for Stochastic Noisy Banditscited by 2

50 most cited of 82 All 82 (JSON)