# Submodular Bandit Problem Under Multiple Constraints

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

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 1 Jun 2020.

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

- [Cost-Effective Online Multi-LLM Selection with Versatile Reward Models](https://mlsanity.com/paper/2405.16587/) (2024)
- [A Framework for Adapting Offline Algorithms to Solve Combinatorial Multi-Armed Bandit Problems with Bandit Feedback](https://mlsanity.com/paper/2301.13326/) (2023)
- [Randomized Greedy Learning for Non-monotone Stochastic Submodular Maximization Under Full-bandit Feedback](https://mlsanity.com/paper/2302.01324/) (2023)
- [Combinatorial Stochastic-Greedy Bandit](https://mlsanity.com/paper/2312.08057/) (2023)
- [Federated Combinatorial Multi-Agent Multi-Armed Bandits](https://mlsanity.com/paper/2405.05950/) (2024)
- [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)
- [Online SuBmodular + SuPermodular (BP) Maximization with Bandit Feedback](https://mlsanity.com/paper/2207.03091/) (2022)
- [Linear Submodular Maximization with Bandit Feedback](https://mlsanity.com/paper/2407.02601/) (2024)
- [On Learning to Rank Long Sequences with Contextual Bandits](https://mlsanity.com/paper/2106.03546/) (2021)
- [Online Subset Selection using α-Core with no Augmented Regret](https://mlsanity.com/paper/2209.14222/) (2022)
- [A Resilience Framework for Bi-Criteria Combinatorial Optimization with Bandit Feedback](https://mlsanity.com/paper/2503.12285/) (2025)
- [Exploitation Over Exploration: Unmasking the Bias in Linear Bandit Recommender Offline Evaluation](https://mlsanity.com/paper/2507.18756/) (2025)
- [Multi-Agent Reinforcement Learning with Submodular Reward](https://mlsanity.com/paper/2603.06810/) (2026)
- [Multinomial Subset Routing with Sum-Max Rewards and Operational Constraints](https://mlsanity.com/paper/2608.16375/) (2026)

## Abstract (arXiv)

The linear submodular bandit problem was proposed to simultaneously address diversified retrieval and online learning in a recommender system. If there is no uncertainty, this problem is equivalent to a submodular maximization problem under a cardinality constraint. However, in some situations, recommendation lists should satisfy additional constraints such as budget constraints, other than a cardinality constraint. Thus, motivated by diversified retrieval considering budget constraints, we introduce a submodular bandit problem under the intersection of l knapsacks and a k-system constraint. Here k-system constraints form a very general class of constraints including cardinality constraints and the intersection of k matroid constraints. To solve this problem, we propose a non-greedy algorithm that adaptively focuses on a standard or modified upper-confidence bound. We provide a high-probability upper bound of an approximation regret, where the approximation ratio matches that of a fast offline algorithm. Moreover, we perform experiments under various combinations of constraints using a synthetic and two real-world datasets and demonstrate that our proposed methods outperform the existing baselines.