mlsanityData to 7 Oct 2026

Combinatorial Semi-Bandits with Knapsacks

arXiv 1705.08110 ↗First posted 23 May 2017cs.LGcited by 23

Not on the map. Why?

Abstract (arXiv)

We unify two prominent lines of work on multi-armed bandits: bandits with knapsacks (BwK) and combinatorial semi-bandits. The former concerns limited "resources" consumed by the algorithm, e.g., limited supply in dynamic pricing. The latter allows a huge number of actions but assumes combinatorial structure and additional feedback to make the problem tractable. We define a common generalization, support it with several motivating examples, and design an algorithm for it. Our regret bounds are comparable with those for BwK and combinatorial semi- bandits.

Key facts. Cited by 23 papers in the map (data through 7 Oct 2026). First posted on arXiv 23 May 2017.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 5; 2022: 2; 2023: 3; 2024: 4; 2025: 4; 2026: 5.

23 papers.

Sort:

By area:

  1. 2024Cost-Effective Online Multi-LLM Selection with Versatile Reward Modelscited by 36
  2. 2021Stochastic Bandits for Multi-platform Budget Optimization in Online Advertisingcited by 25
  3. 2021Combinatorial Bandits under Strategic Manipulationscited by 6
  4. 2023Approximately Stationary Bandits with Knapsackscited by 6
  5. 2023Bandits with Replenishable Knapsacks: the Best of both Worldscited by 6
  6. 2025No-Regret Learning Under Adversarial Resource Constraints: A Spending Plan Is All You Need!cited by 5
  7. 2022Best of Many Worlds Guarantees for Online Learning with Knapsackscited by 4
  8. 2022Safe Online Bid Optimization with Return on Investment and Budget Constraintscited by 3
  9. 2024Best Arm Identification with Resource Constraintscited by 3
  10. 2021Recurrent Submodular Welfare and Matroid Blocking Banditscited by 2
  11. 2021MNL-Bandit with Knapsacks: a near-optimal algorithmcited by 2
  12. 2024Multi-Task Combinatorial Bandits for Budget Allocationcited by 2
11 more
  1. 2023Online Resource Allocation: Bandits feedback and Advice on Time-varying Demandscited by 1
  2. 2025Adversarial Combinatorial Semi-bandits with Graph Feedbackcited by 1
  3. 2026Cost-Aware Multi-Objective Bandits: Theory and Application to Budgeted LLM Configuration Evaluationcited by 1
  4. 2021Continuous Time Bandits With Sampling Costscited by 0
  5. 2024Learning to Explore with Lagrangians for Bandits under Unknown Linear Constraintscited by 0
  6. 2025Stochastically Constrained Best Arm Identification with Thompson Samplingcited by 0
  7. 2025Finite-Time Guarantees for Multi-Agent Combinatorial Bandits with Nonstationary Rewardscited by 0
  8. 2026Learning with a Budget: Identifying the Best Arm with Resource Constraintscited by 0
  9. 2026Adaptive Combinatorial Experimental Design: Pareto Optimality for Decision-Making and Inferencecited by 0
  10. 2026Combinatorial Allocation Bandits with Nonlinear Arm Utilitycited by 0
  11. 2026Multinomial Subset Routing with Sum-Max Rewards and Operational Constraintscited by 0