Bandit Submodular Maximization under Matroid Constraints: Learning Compressed Exchange Policy

arXiv:2608.24627v1 Announce Type: new Abstract: 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-theoretic sublinear-regret guarantee, but directly learning the exponentially many policies requires exponential time and space. We therefore introduce balanced fractional exchanges, which compress the policy mixture into a single fractional base while retaining the exchange information needed by the Poisson analysis. This leads to an polynomial time algorithm with the same regret guarantee.

Related

• Restless Bandits with Individual Penalty Constraints: A New Near-Optimal Index Policy and How to Learn It
• Spectral bandits for smooth graph functions
• Semi-Bandit Learning for Monotone Stochastic Optimization

Source: arXiv cs.LG | 2026-08-26