Adaptive Threshold Sampling for Pure Exploration in Submodular Bandits

Wenjing Chen, Shuo Xing, Victoria G. Crawford
Proceedings of the Forty-first Conference on Uncertainty in Artificial Intelligence, PMLR 286:612-646, 2025.

Abstract

We address the problem of submodular maximization under bandit feedback, where the objective function $f:2^U\to\mathbb{R}_{\geq 0}$ can only be accessed through noisy, i.i.d. sub-Gaussian queries. This problem arises in many applications including influence maximization, diverse recommendation systems, and large-scale facility location optimization. In this paper, we focus on the pure-exploration setting, where the goal is to identify a high-quality solution set using as few noisy queries as possible. We propose an efficient adaptive sampling strategy, called Confident Sample (CS) that can serve as a versatile subroutine to propose approximation algorithms for many submodular maximization problems. Our algorithms achieve approximation guarantees arbitrarily close to the standard value oracle setting and are highly sample-efficient. We propose and analyze algorithms for monotone submodular maximization with cardinality and matroid constraints, as well as unconstrained non-monotone submodular maximization. Our theoretical analysis is complemented by empirical evaluation on real instances, demonstrating the superior sample efficiency of our proposed algorithm relative to alternative approaches.

Cite this Paper

BibTeX
@InProceedings{pmlr-v286-chen25c, title = {Adaptive Threshold Sampling for Pure Exploration in Submodular Bandits}, author = {Chen, Wenjing and Xing, Shuo and Crawford, Victoria G.}, booktitle = {Proceedings of the Forty-first Conference on Uncertainty in Artificial Intelligence}, pages = {612--646}, year = {2025}, editor = {Chiappa, Silvia and Magliacane, Sara}, volume = {286}, series = {Proceedings of Machine Learning Research}, month = {21--25 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v286/main/assets/chen25c/chen25c.pdf}, url = {https://proceedings.mlr.press/v286/chen25c.html}, abstract = {We address the problem of submodular maximization under bandit feedback, where the objective function $f:2^U\to\mathbb{R}_{\geq 0}$ can only be accessed through noisy, i.i.d. sub-Gaussian queries. This problem arises in many applications including influence maximization, diverse recommendation systems, and large-scale facility location optimization. In this paper, we focus on the pure-exploration setting, where the goal is to identify a high-quality solution set using as few noisy queries as possible. We propose an efficient adaptive sampling strategy, called Confident Sample (CS) that can serve as a versatile subroutine to propose approximation algorithms for many submodular maximization problems. Our algorithms achieve approximation guarantees arbitrarily close to the standard value oracle setting and are highly sample-efficient. We propose and analyze algorithms for monotone submodular maximization with cardinality and matroid constraints, as well as unconstrained non-monotone submodular maximization. Our theoretical analysis is complemented by empirical evaluation on real instances, demonstrating the superior sample efficiency of our proposed algorithm relative to alternative approaches.} }
Endnote
%0 Conference Paper %T Adaptive Threshold Sampling for Pure Exploration in Submodular Bandits %A Wenjing Chen %A Shuo Xing %A Victoria G. Crawford %B Proceedings of the Forty-first Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2025 %E Silvia Chiappa %E Sara Magliacane %F pmlr-v286-chen25c %I PMLR %P 612--646 %U https://proceedings.mlr.press/v286/chen25c.html %V 286 %X We address the problem of submodular maximization under bandit feedback, where the objective function $f:2^U\to\mathbb{R}_{\geq 0}$ can only be accessed through noisy, i.i.d. sub-Gaussian queries. This problem arises in many applications including influence maximization, diverse recommendation systems, and large-scale facility location optimization. In this paper, we focus on the pure-exploration setting, where the goal is to identify a high-quality solution set using as few noisy queries as possible. We propose an efficient adaptive sampling strategy, called Confident Sample (CS) that can serve as a versatile subroutine to propose approximation algorithms for many submodular maximization problems. Our algorithms achieve approximation guarantees arbitrarily close to the standard value oracle setting and are highly sample-efficient. We propose and analyze algorithms for monotone submodular maximization with cardinality and matroid constraints, as well as unconstrained non-monotone submodular maximization. Our theoretical analysis is complemented by empirical evaluation on real instances, demonstrating the superior sample efficiency of our proposed algorithm relative to alternative approaches.
APA
Chen, W., Xing, S. & Crawford, V.G.. (2025). Adaptive Threshold Sampling for Pure Exploration in Submodular Bandits. Proceedings of the Forty-first Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research 286:612-646 Available from https://proceedings.mlr.press/v286/chen25c.html.

Related Material