Greedy algorithms for stochastic monotone k-submodular maximization under full-bandit feedback

Xin Sun (), Tiande Guo (), Congying Han () and Hongyang Zhang ()
Additional contact information
Xin Sun: University of Science and Technology Beijing
Tiande Guo: University of Chinese Academy of Sciences
Congying Han: University of Chinese Academy of Sciences
Hongyang Zhang: Ningbo University

Journal of Combinatorial Optimization, 2025, vol. 49, issue 1, No 7, 25 pages

Abstract: Abstract In this paper, we theoretically study the Combinatorial Multi-Armed Bandit problem with stochastic monotone k-submodular reward function under full-bandit feedback. In this setting, the decision-maker is allowed to select a super arm composed of multiple base arms in each round and then receives its k-submodular reward. The k-submodularity enriches the application scenarios of the problem we consider in contexts characterized by diverse options. We present two simple greedy algorithms for two budget constraints (total size and individual size) and provide the theoretical analysis for upper bound of the regret value. For the total size budget, the proposed algorithm achieves a $$\frac{1}{2}$$ 1 2 -regret upper bound by $$\tilde{\mathcal {O}}\left( T^\frac{2}{3}(kn)^{\frac{1}{3}}B\right) $$ O ~ T 2 3 ( k n ) 1 3 B where T is the time horizon, n is the number of base arms and B denotes the budget. For the individual size budget, the proposed algorithm achieves a $$\frac{1}{3}$$ 1 3 -regret with the same upper bound. Moreover, we conduct numerical experiments on these two algorithms to empirically demonstrate the effectiveness.

Keywords: Combinatorial multi-armed bandit; k-submodular; Stochastic reward; Full-bandit feedback; Budget constraints (search for similar items in EconPapers)
Date: 2025
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-024-01240-9 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:49:y:2025:i:1:d:10.1007_s10878-024-01240-9

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-024-01240-9

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().