# Bandit Submodular Maximization under Matroid Constraints: Learning Compressed Exchange Policy

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 10 of its 29 references that are in the map.
- First posted on arXiv 25 Aug 2026.

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

- [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)
- [Bandit Multi-linear DR-Submodular Maximization and Its Applications on Adversarial Submodular Bandits](https://mlsanity.com/paper/2305.12402/) (2023)
- [Nearly Minimax Optimal Submodular Maximization with Bandit Feedback](https://mlsanity.com/paper/2310.18465/) (2023)
- [Online Submodular Maximization via Online Convex Optimization](https://mlsanity.com/paper/2309.04339/) (2023)
- [Deterministic Algorithm and Faster Algorithm for Submodular Maximization subject to a Matroid Constraint](https://mlsanity.com/paper/2408.03583/) (2024)
- [Stochastic k-Submodular Bandits with Full Bandit Feedback](https://mlsanity.com/paper/2412.10682/) (2024)
- [A Poisson Process for Submodular Maximization](https://mlsanity.com/paper/2605.03071/) (2026)

## Abstract (arXiv)

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(n1/3k2/3T2/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.