mlsanityData to 14 Oct 2026

Contextual Bandits with Packing and Covering Constraints: A Modular Lagrangian Approach via Regression

arXiv 2211.07484 ↗First posted 14 Nov 2022cs.LG stat.MLcited by 30

Not on the map. Why?

Abstract (arXiv)

We consider contextual bandits with linear constraints (CBwLC), a variant of contextual bandits in which the algorithm consumes multiple resources subject to linear constraints on total consumption. This problem generalizes contextual bandits with knapsacks (CBwK), allowing for packing and covering constraints, as well as positive and negative resource consumption. We provide the first algorithm for CBwLC (or CBwK) that is based on regression oracles. The algorithm is simple, computationally efficient, and statistically optimal under mild assumptions. Further, we provide the first vanishing-regret guarantees for CBwLC (or CBwK) that extend beyond the stochastic environment. We side-step strong impossibility results from prior work by identifying a weaker (and, arguably, fairer) benchmark to compare against. Our algorithm builds on LagrangeBwK (Immorlica et al., FOCS 2019), a Lagrangian-based technique for CBwK, and SquareCB (Foster and Rakhlin, ICML 2020), a regression-based technique for contextual bandits. Our analysis leverages the inherent modularity of both techniques.

Key facts. Cited by 30 papers in the map (data through 14 Oct 2026). Builds on 30 of its 82 references that are in the map. First posted on arXiv 14 Nov 2022.

Builds on

30 of 82 references.

References · 30

  1. 2019Introduction to Online Convex Optimizationcited by 803
  2. 2018A Reductions Approach to Fair Classificationcited by 587
  3. 2019Introduction to Multi-Armed Banditscited by 481
  4. 2021The Statistical Complexity of Interactive Decision Makingcited by 218
  5. 2014Taming the Monster: A Fast and Simple Algorithm for Contextual Banditscited by 201
  6. 2020Beyond UCB: Optimal and Efficient Contextual Bandits with Regression Oraclescited by 197
  7. 2013Bandits with Knapsackscited by 164
  8. 2020Exploration-Exploitation in Constrained MDPscited by 149
  9. 2020Provably Efficient Safe Exploration via Primal-Dual Policy Optimizationcited by 134
  10. 2020Bypassing the Monster: A Faster and Simpler Optimal Algorithm for Contextual Bandits under Realizabilitycited by 115
  11. 2018Practical Contextual Bandits with Regression Oraclescited by 93
  12. 2014Bandits with concave rewards and convex knapsackscited by 83
18 more
  1. 2015Linear Contextual Bandits with Knapsackscited by 82
  2. 2021Adapting to Misspecification in Contextual Banditscited by 81
  3. 2020Instance-Dependent Complexity of Contextual Bandits and Reinforcement Learning: A Disagreement-Based Perspectivecited by 78
  4. 2018Adversarial Bandits with Knapsackscited by 73
  5. 2018A Contextual Bandit Bake-offcited by 64
  6. 2016Kernel-based methods for bandit convex optimizationcited by 63
  7. 2013Relative Loss Bounds for On-line Density Estimation with the Exponential Family of Distributionscited by 60
  8. 2020The Best of Many Worlds: Dual Mirror Descent for Online Allocation Problemscited by 58
  9. 2014Resourceful Contextual Banditscited by 45
  10. 2015An efficient algorithm for contextual bandits with knapsacks, and an extension to concave objectivescited by 43
  11. 2022Contextual Bandits with Large Action Spaces: Made Practicalcited by 33
  12. 2022Non-stationary Bandits with Knapsackscited by 25
  13. 2022On Kernelized Multi-Armed Bandits with Constraintscited by 23
  14. 2020Online Learning with Vector Costs and Bandits with Knapsackscited by 20
  15. 2022Budget Pacing in Repeated Auctions: Regret and Efficiency without Convergencecited by 18
  16. 2022Non-monotonic Resource Utilization in the Bandits with Knapsacks Problemcited by 12
  17. 2022Optimal Contextual Bandits with Knapsacks under Realizability via Regression Oraclescited by 12
  18. 2015Bandit Convex Optimization: sqrt{T} Regret in One Dimensioncited by 10

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2022: 1; 2023: 6; 2024: 6; 2025: 9; 2026: 8.

30 papers.

Sort:

  1. 2023No-Regret Learning in Bilateral Trade via Global Budget Balancecited by 17
  2. 2023The Relative Value of Prediction in Algorithmic Decision Makingcited by 14
  3. 2024Beyond Primal-Dual Methods in Bandits with Stochastic and Adversarial Constraintscited by 10
  4. 2024No-Regret Algorithms in non-Truthful Auctions with Budget and ROI Constraintscited by 9
  5. 2023Approximately Stationary Bandits with Knapsackscited by 6
  6. 2024No-Regret is not enough! Bandits with General Constraints through Adaptive Regret Minimizationcited by 6
  7. 2025No-Regret Learning Under Adversarial Resource Constraints: A Spending Plan Is All You Need!cited by 5
  8. 2024A Parametric Contextual Online Learning Theory of Brokeragecited by 4
  9. 2022Contextual Decision-Making with Knapsacks Beyond the Worst Casecited by 3
  10. 2023Interpolating Item and User Fairness in Multi-Sided Recommendationscited by 3
  11. 2023Think Before You Duel: Understanding Complexities of Preference Learning under Constrained Resourcescited by 3
  12. 2025A New Benchmark for Online Learning with Budget-Balancing Constraintscited by 3
18 more
  1. 2023Small Total-Cost Constraints in Contextual Bandits with Knapsacks, with Application to Fairnesscited by 2
  2. 2025Online Bidding under RoS Constraints without Knowing the Valuecited by 2
  3. 2025The Hidden Cost of Waiting for Accurate Predictionscited by 1
  4. 2025Episodic Contextual Bandits with Knapsacks under Conversion Modelscited by 1
  5. 2024Learning to Explore with Lagrangians for Bandits under Unknown Linear Constraintscited by 0
  6. 2024Safe and Efficient Online Convex Optimization with Linear Budget Constraints and Partial Feedbackcited by 0
  7. 2025Bandits with Anytime Knapsackscited by 0
  8. 2025Contextual Learning for Stochastic Optimizationcited by 0
  9. 2025Multi-Armed Bandits with Minimum Aggregated Revenue Constraintscited by 0
  10. 2025Conformal bandits: bringing statistical validity and reward efficiency under weak arm separabilitycited by 0
  11. 2026A Simple Reduction Scheme for Constrained Contextual Bandits with Adversarial Contexts via Regressioncited by 0
  12. 2026On the Meta-Design of Allocation Problemscited by 0
  13. 2026Constrained Contextual Bandits with Adversarial Contextscited by 0
  14. 2026Regret Minimization in Bilateral Trade With Perturbed Marketscited by 0
  15. 2026Multi-Task Representation Learning for Conservative Linear Banditscited by 0
  16. 2026Efficient Online Conformal Selection with Limited Feedbackcited by 0
  17. 2026Online LLM Selection via Constrained Bandits with Time-Varying Demandcited by 0
  18. 2026Multinomial Subset Routing with Sum-Max Rewards and Operational Constraintscited by 0