# Stochastic k-Submodular Bandits with Full Bandit Feedback

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 34 references that are in the map.
- First posted on arXiv 14 Dec 2024.

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

- [Online Learning via Offline Greedy Algorithms: Applications in Market Design and Optimization](https://mlsanity.com/paper/2102.11050/) (2021)
- [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)
- [Submodular Bandit Problem Under Multiple Constraints](https://mlsanity.com/paper/2006.00661/) (2020)
- [Federated Combinatorial Multi-Agent Multi-Armed Bandits](https://mlsanity.com/paper/2405.05950/) (2024)
- [On maximizing a monotone k-submodular function subject to a matroid constraint](https://mlsanity.com/paper/1607.07957/) (2016)
- [Maximizing k-Submodular Functions and Beyond](https://mlsanity.com/paper/1409.1399/) (2014)
- [Improved Approximation Algorithms for k-Submodular Function Maximization](https://mlsanity.com/paper/1502.07406/) (2015)
- [On maximizing a monotone k-submodular function under a knapsack constraint](https://mlsanity.com/paper/2105.15159/) (2021)
- [No-regret algorithms for online k-submodular maximization](https://mlsanity.com/paper/1807.04965/) (2018)
- [Improved randomized algorithm for k-submodular function maximization](https://mlsanity.com/paper/1907.12942/) (2019)
- [Approximation algorithms for k-submodular maximization subject to a knapsack constraint](https://mlsanity.com/paper/2306.14520/) (2023)

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

- [A Resilience Framework for Bi-Criteria Combinatorial Optimization with Bandit Feedback](https://mlsanity.com/paper/2503.12285/) (2025)
- [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)

In this paper, we present the first sublinear α-regret bounds for online k-submodular optimization problems with full-bandit feedback, where α is a corresponding offline approximation ratio. Specifically, we propose online algorithms for multiple k-submodular stochastic combinatorial multi-armed bandit problems, including (i) monotone functions and individual size constraints, (ii) monotone functions with matroid constraints, (iii) non-monotone functions with matroid constraints, (iv) non-monotone functions without constraints, and (v) monotone functions without constraints. We transform approximation algorithms for offline k-submodular maximization problems into online algorithms through the offline-to-online framework proposed by Nie et al. (2023a). A key contribution of our work is analyzing the robustness of the offline algorithms.