# A Framework for Adapting Offline Algorithms to Solve Combinatorial Multi-Armed Bandit Problems with Bandit Feedback

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

## Key facts

- Cited by 19 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 47 references that are in the map.
- First posted on arXiv 30 Jan 2023.

## Builds on (most cited first, 10 of 10)

- [Introduction to Multi-Armed Bandits](https://mlsanity.com/paper/1904.07272/) (2019)
- [What Doubling Tricks Can and Can't Do for Multi-Armed Bandits](https://mlsanity.com/paper/1803.06971/) (2018)
- [Online Learning via Offline Greedy Algorithms: Applications in Market Design and Optimization](https://mlsanity.com/paper/2102.11050/) (2021)
- [Fast Adaptive Non-Monotone Submodular Maximization Subject to a Knapsack Constraint](https://mlsanity.com/paper/2007.05014/) (2020)
- [Online Submodular Maximization under a Matroid Constraint with Application to Learning Assignments](https://mlsanity.com/paper/1407.1082/) (2014)
- [Submodular Bandit Problem Under Multiple Constraints](https://mlsanity.com/paper/2006.00661/) (2020)
- ["Bring Your Own Greedy"+Max: Near-Optimal 1/2-Approximations for Submodular Knapsack](https://mlsanity.com/paper/1910.05646/) (2019)
- [Submodular Maximization in Clean Linear Time](https://mlsanity.com/paper/2006.09327/) (2020)
- [Online Learning with Cumulative Oversampling: Application to Budgeted Influence Maximization](https://mlsanity.com/paper/2004.11963/) (2020)
- [Budgeted Influence Maximization via Boost Simulated Annealing in Social Networks](https://mlsanity.com/paper/2203.11594/) (2022)

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

- [Combinatorial Stochastic-Greedy Bandit](https://mlsanity.com/paper/2312.08057/) (2023)
- [Bandit Multi-linear DR-Submodular Maximization and Its Applications on Adversarial Submodular Bandits](https://mlsanity.com/paper/2305.12402/) (2023)
- [Federated Combinatorial Multi-Agent Multi-Armed Bandits](https://mlsanity.com/paper/2405.05950/) (2024)
- [Learning with Exposure Constraints in Recommendation Systems](https://mlsanity.com/paper/2302.01377/) (2023)
- [Semi-Bandit Learning for Monotone Stochastic Optimization](https://mlsanity.com/paper/2312.15427/) (2023)
- [Nearly Minimax Optimal Submodular Maximization with Bandit Feedback](https://mlsanity.com/paper/2310.18465/) (2023)
- [Combinatorial Multivariant Multi-Armed Bandits with Applications to Episodic Reinforcement Learning and Beyond](https://mlsanity.com/paper/2406.01386/) (2024)
- [Offline Learning for Combinatorial Multi-armed Bandits](https://mlsanity.com/paper/2501.19300/) (2025)
- [Stochastic k-Submodular Bandits with Full Bandit Feedback](https://mlsanity.com/paper/2412.10682/) (2024)
- [Stochastic Submodular Bandits with Delayed Composite Anonymous Bandit Feedback](https://mlsanity.com/paper/2303.13604/) (2023)
- [No-Regret Mnatural-Concave Function Maximization: Stochastic Bandit Algorithms and Hardness of Adversarial Full-Information Setting](https://mlsanity.com/paper/2405.12439/) (2024)
- [A Resilience Framework for Bi-Criteria Combinatorial Optimization with Bandit Feedback](https://mlsanity.com/paper/2503.12285/) (2025)
- [Bandits with Single-Peaked Preferences and Limited Resources](https://mlsanity.com/paper/2510.09425/) (2025)
- [Multi-Agent Combinatorial-Multi-Armed-Bandit framework for the Submodular Welfare Problem under Bandit Feedback](https://mlsanity.com/paper/2602.16183/) (2026)
- [Meritocratic Fairness via K-Shapley Values in Budgeted Combinatorial Bandits with Full-Bandit Feedback](https://mlsanity.com/paper/2605.00762/) (2026)
- [Learning to Sparsify Stochastic Linear Bandits](https://mlsanity.com/paper/2605.10151/) (2026)
- [Distributed Online Bandit Submodular Maximization with Bounded Sampling Violations](https://mlsanity.com/paper/2607.00680/) (2026)
- [Adversarial Resilience of Poisson-Process Submodular Maximization over Matroids, and Full-Bandit Learning](https://mlsanity.com/paper/2608.12134/) (2026)
- [Bandit Submodular Maximization under Matroid Constraints: Learning Compressed Exchange Policy](https://mlsanity.com/paper/2608.24627/) (2026)

## Abstract (arXiv)

We investigate the problem of stochastic, combinatorial multi-armed bandits where the learner only has access to bandit feedback and the reward function can be non-linear. We provide a general framework for adapting discrete offline approximation algorithms into sublinear α-regret methods that only require bandit feedback, achieving Oleft(T^frac23log(T)^frac13right) expected cumulative α-regret dependence on the horizon T. The framework only requires the offline algorithms to be robust to small errors in function evaluation. The adaptation procedure does not even require explicit knowledge of the offline approximation algorithm -- the offline algorithm can be used as a black box subroutine. To demonstrate the utility of the proposed framework, the proposed framework is applied to diverse applications in submodular maximization. The new CMAB algorithms for submodular maximization with knapsack constraints outperform a full-bandit method developed for the adversarial setting in experiments with real-world data.