SOURCE-LINKED INTELLIGENCE

Bandit Submodular Maximization under Matroid Constraints: Learning Compressed Exchange Policy

arXiv · AI, language, vision and robotics · article · Aug 25, 2026 · UTC

We study adversarial bandit maximization of monotone submodular functions under a matroid constraint. For a rank-$k$ matroid on $n$ elements, we give a randomized oracle-polynomial algorithm that makes one feasible value query per round and has expected $(1-1/e)$-regret $\widetilde O(n^{1/3}k^{2/3}T^{2/3})$. This is the first sublinear-regret algorithm for adversarial bandit submodular maximization under general matroid constraints. Technically, we view the problem as learning an exchange policy for the Poisson base walk. This connects the problem to contextual bandits and gives an information

Read original source ↗ Open in workspace

recordType

paper

region

Global