# Matroid Bandits: Fast Combinatorial Optimization with Learning

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

## Key facts

- Cited by 30 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 20 Mar 2014.

## Built on by (most cited first, 30 of 30)

- [No Regrets for Learning the Prior in Bandits](https://mlsanity.com/paper/2107.06196/) (2021)
- [Efficient Pure Exploration for Combinatorial Bandits with Semi-Bandit Feedback](https://mlsanity.com/paper/2101.08534/) (2021)
- [Heterogeneous Multi-player Multi-armed Bandits: Closing the Gap and Generalization](https://mlsanity.com/paper/2110.14622/) (2021)
- [Near-Optimal Regret Bounds for Contextual Combinatorial Semi-Bandits with Linear Payoff Functions](https://mlsanity.com/paper/2101.07957/) (2021)
- [Incentivizing Combinatorial Bandit Exploration](https://mlsanity.com/paper/2206.00494/) (2022)
- [Semi-Bandit Learning for Monotone Stochastic Optimization](https://mlsanity.com/paper/2312.15427/) (2023)
- [Effective Off-Policy Evaluation and Learning in Contextual Combinatorial Bandits](https://mlsanity.com/paper/2408.11202/) (2024)
- [The Hardness Analysis of Thompson Sampling for Combinatorial Semi-bandits with Greedy Oracle](https://mlsanity.com/paper/2111.04295/) (2021)
- [Multiple-Play Stochastic Bandits with Shareable Finite-Capacity Arms](https://mlsanity.com/paper/2206.08776/) (2022)
- [Stochastic Bandits for Egalitarian Assignment](https://mlsanity.com/paper/2410.05856/) (2024)
- [Matroid Semi-Bandits in Sublinear Time](https://mlsanity.com/paper/2405.17968/) (2024)
- [Recurrent Submodular Welfare and Matroid Blocking Bandits](https://mlsanity.com/paper/2102.00321/) (2021)
- [Contextual Combinatorial Bandits with Changing Action Sets via Gaussian Processes](https://mlsanity.com/paper/2110.02248/) (2021)
- [Adversarial Attacks on Combinatorial Multi-Armed Bandits](https://mlsanity.com/paper/2310.05308/) (2023)
- [Incentivized Exploration via Filtered Posterior Sampling](https://mlsanity.com/paper/2402.13338/) (2024)
- [Follow-the-Perturbed-Leader Approaches Best-of-Both-Worlds for the m-Set Semi-Bandit Problems](https://mlsanity.com/paper/2504.07307/) (2025)
- [Online SuBmodular + SuPermodular (BP) Maximization with Bandit Feedback](https://mlsanity.com/paper/2207.03091/) (2022)
- [Probably Anytime-Safe Stochastic Combinatorial Semi-Bandits](https://mlsanity.com/paper/2301.13393/) (2023)
- [Note on Follow-the-Perturbed-Leader in Combinatorial Semi-Bandit Problems](https://mlsanity.com/paper/2506.12490/) (2025)
- [A Distributed Neural Linear Thompson Sampling Framework to Achieve URLLC in Industrial IoT](https://mlsanity.com/paper/2401.06135/) (2023)
- [Recommenadation aided Caching using Combinatorial Multi-armed Bandits](https://mlsanity.com/paper/2405.00080/) (2024)
- [Latency-Aware Contextual Bandit: Application to Cryo-EM Data Collection](https://mlsanity.com/paper/2410.13109/) (2024)
- [Near-Optimal Regret for Efficient Stochastic Combinatorial Semi-Bandits](https://mlsanity.com/paper/2508.06247/) (2025)
- [Online Learning to Rank under Corruption: A Robust Cascading Bandits Approach](https://mlsanity.com/paper/2511.03074/) (2025)
- [Efficient Matroid Bandit Linear Optimization Leveraging Unimodality](https://mlsanity.com/paper/2512.00605/) (2025)
- [Multiple-play Stochastic Bandits with Prioritized Arm Capacity Sharing](https://mlsanity.com/paper/2512.21626/) (2025)
- [Efficient Swap Regret Minimization in Combinatorial Bandits](https://mlsanity.com/paper/2602.02087/) (2026)
- [Adaptive Combinatorial Experimental Design: Pareto Optimality for Decision-Making and Inference](https://mlsanity.com/paper/2602.24231/) (2026)
- [Bandits on graphs and structures](https://mlsanity.com/paper/2605.03493/) (2026)
- [Sequential Hiring of Contingent Workers Through Learning-Based Optimization](https://mlsanity.com/paper/2606.18438/) (2026)

## Abstract (arXiv)

A matroid is a notion of independence in combinatorial optimization which is closely related to computational efficiency. In particular, it is well known that the maximum of a constrained modular function can be found greedily if and only if the constraints are associated with a matroid. In this paper, we bring together the ideas of bandits and matroids, and propose a new class of combinatorial bandits, matroid bandits. The objective in these problems is to learn how to maximize a modular function on a matroid. This function is stochastic and initially unknown. We propose a practical algorithm for solving our problem, Optimistic Matroid Maximization (OMM); and prove two upper bounds, gap-dependent and gap-free, on its regret. Both bounds are sublinear in time and at most linear in all other quantities of interest. The gap-dependent upper bound is tight and we prove a matching lower bound on a partition matroid bandit. Finally, we evaluate our method on three real-world problems and show that it is practical.