# Matroid Semi-Bandits in Sublinear Time

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 19 of its 50 references that are in the map.
- First posted on arXiv 28 May 2024.

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

- [Thompson Sampling for Combinatorial Semi-Bandits](https://mlsanity.com/paper/1803.04623/) (2018)
- [Scalable Generalized Linear Bandits: Online Computation and Hashing](https://mlsanity.com/paper/1706.00136/) (2017)
- [Minimal Exploration in Structured Stochastic Bandits](https://mlsanity.com/paper/1711.00400/) (2017)
- [Efficient Learning in Large-Scale Combinatorial Semi-Bandits](https://mlsanity.com/paper/1406.7443/) (2014)
- [Statistical Efficiency of Thompson Sampling for Combinatorial Semi-Bandits](https://mlsanity.com/paper/2006.06613/) (2020)
- [Matroid Bandits: Fast Combinatorial Optimization with Learning](https://mlsanity.com/paper/1403.5045/) (2014)
- [Combinatorial semi-bandit with known covariance](https://mlsanity.com/paper/1612.01859/) (2016)
- [Combinatorial Semi-Bandit in the Non-Stationary Environment](https://mlsanity.com/paper/2002.03580/) (2020)
- [Importance weighting without importance weights: An efficient algorithm for combinatorial semi-bandits](https://mlsanity.com/paper/1503.05087/) (2015)
- [Pure Exploration of Multi-armed Bandit Under Matroid Constraints](https://mlsanity.com/paper/1605.07162/) (2016)
- [Statistically Efficient, Polynomial Time Algorithms for Combinatorial Semi Bandits](https://mlsanity.com/paper/2002.07258/) (2020)
- [Linear Bandit Algorithms with Sublinear Time Complexity](https://mlsanity.com/paper/2103.02729/) (2021)
- [Dynamic Matrix Inverse: Improved Algorithms and Matching Conditional Lower Bounds](https://mlsanity.com/paper/1905.05067/) (2019)
- [The Hardness Analysis of Thompson Sampling for Combinatorial Semi-bandits with Greedy Oracle](https://mlsanity.com/paper/2111.04295/) (2021)
- [When Combinatorial Thompson Sampling meets Approximation Regret](https://mlsanity.com/paper/2302.11182/) (2023)
- [A Near-Optimal Change-Detection Based Algorithm for Piecewise-Stationary Combinatorial Semi-Bandits](https://mlsanity.com/paper/1908.10402/) (2019)
- [Asymptotically Optimal Strategies For Combinatorial Semi-Bandits in Polynomial Time](https://mlsanity.com/paper/2102.07254/) (2021)
- [Learning to Act Greedily: Polymatroid Semi-Bandits](https://mlsanity.com/paper/1405.7752/) (2014)
- [Faster Submodular Maximization for Several Classes of Matroids](https://mlsanity.com/paper/2305.00122/) (2023)

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

- [Oracle-Efficient Combinatorial Semi-Bandits](https://mlsanity.com/paper/2510.21431/) (2025)
- [Efficient Matroid Bandit Linear Optimization Leveraging Unimodality](https://mlsanity.com/paper/2512.00605/) (2025)
- [Matroid Algorithms Under Size-Sensitive Independence Oracles](https://mlsanity.com/paper/2605.00201/) (2026)

## Abstract (arXiv)

We study the matroid semi-bandits problem, where at each round the learner plays a subset of K arms from a feasible set, and the goal is to maximize the expected cumulative linear rewards. Existing algorithms have per-round time complexity at least Omega(K), which becomes expensive when K is large. To address this computational issue, we propose FasterCUCB whose sampling rule takes time sublinear in K for common classes of matroids: O(D polylog(K) polylog(T)) for uniform matroids, partition matroids, and graphical matroids, and O(D√K polylog(T)) for transversal matroids. Here, D is the maximum number of elements in any feasible subset of arms, and T is the horizon. Our technique is based on dynamic maintenance of an approximate maximum-weight basis over inner-product weights. Although the introduction of an approximate maximum-weight basis presents a challenge in regret analysis, we can still guarantee an upper bound on regret as tight as CUCB in the sense that it matches the gap-dependent lower bound by Kveton et al. (2014a) asymptotically.