# Combinatorial Semi-Bandits with Knapsacks

arXiv: https://arxiv.org/abs/1705.08110 · HTML: https://mlsanity.com/paper/1705.08110/

## Key facts

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

## Built on by (most cited first, 23 of 23)

- [Cost-Effective Online Multi-LLM Selection with Versatile Reward Models](https://mlsanity.com/paper/2405.16587/) (2024)
- [Stochastic Bandits for Multi-platform Budget Optimization in Online Advertising](https://mlsanity.com/paper/2103.10246/) (2021)
- [Combinatorial Bandits under Strategic Manipulations](https://mlsanity.com/paper/2102.12722/) (2021)
- [Approximately Stationary Bandits with Knapsacks](https://mlsanity.com/paper/2302.14686/) (2023)
- [Bandits with Replenishable Knapsacks: the Best of both Worlds](https://mlsanity.com/paper/2306.08470/) (2023)
- [No-Regret Learning Under Adversarial Resource Constraints: A Spending Plan Is All You Need!](https://mlsanity.com/paper/2506.13244/) (2025)
- [Best of Many Worlds Guarantees for Online Learning with Knapsacks](https://mlsanity.com/paper/2202.13710/) (2022)
- [Safe Online Bid Optimization with Return on Investment and Budget Constraints](https://mlsanity.com/paper/2201.07139/) (2022)
- [Best Arm Identification with Resource Constraints](https://mlsanity.com/paper/2402.19090/) (2024)
- [Cost-Aware Multi-Objective Bandits: Theory and Application to Budgeted LLM Configuration Evaluation](https://mlsanity.com/paper/2608.04333/) (2026)
- [Recurrent Submodular Welfare and Matroid Blocking Bandits](https://mlsanity.com/paper/2102.00321/) (2021)
- [MNL-Bandit with Knapsacks: a near-optimal algorithm](https://mlsanity.com/paper/2106.01135/) (2021)
- [Multi-Task Combinatorial Bandits for Budget Allocation](https://mlsanity.com/paper/2409.00561/) (2024)
- [Online Resource Allocation: Bandits feedback and Advice on Time-varying Demands](https://mlsanity.com/paper/2302.04182/) (2023)
- [Adversarial Combinatorial Semi-bandits with Graph Feedback](https://mlsanity.com/paper/2502.18826/) (2025)
- [Continuous Time Bandits With Sampling Costs](https://mlsanity.com/paper/2107.05289/) (2021)
- [Learning to Explore with Lagrangians for Bandits under Unknown Linear Constraints](https://mlsanity.com/paper/2410.18844/) (2024)
- [Stochastically Constrained Best Arm Identification with Thompson Sampling](https://mlsanity.com/paper/2501.03877/) (2025)
- [Finite-Time Guarantees for Multi-Agent Combinatorial Bandits with Nonstationary Rewards](https://mlsanity.com/paper/2508.20923/) (2025)
- [Learning with a Budget: Identifying the Best Arm with Resource Constraints](https://mlsanity.com/paper/2602.24146/) (2026)
- [Adaptive Combinatorial Experimental Design: Pareto Optimality for Decision-Making and Inference](https://mlsanity.com/paper/2602.24231/) (2026)
- [Combinatorial Allocation Bandits with Nonlinear Arm Utility](https://mlsanity.com/paper/2603.07005/) (2026)
- [Multinomial Subset Routing with Sum-Max Rewards and Operational Constraints](https://mlsanity.com/paper/2608.16375/) (2026)

## 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.