# Combinatorial semi-bandit with known covariance

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

## Key facts

- Cited by 24 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 6 Dec 2016.

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

- [A survey on multi-player bandits](https://mlsanity.com/paper/2211.16275/) (2022)
- [Heterogeneous Multi-player Multi-armed Bandits: Closing the Gap and Generalization](https://mlsanity.com/paper/2110.14622/) (2021)
- [Batch-Size Independent Regret Bounds for Combinatorial Semi-Bandits with Probabilistically Triggered Arms or Independent Arms](https://mlsanity.com/paper/2208.14837/) (2022)
- [Incentivizing Combinatorial Bandit Exploration](https://mlsanity.com/paper/2206.00494/) (2022)
- [Be Greedy in Multi-Armed Bandits](https://mlsanity.com/paper/2101.01086/) (2021)
- [Combinatorial Multivariant Multi-Armed Bandits with Applications to Episodic Reinforcement Learning and Beyond](https://mlsanity.com/paper/2406.01386/) (2024)
- [When Combinatorial Thompson Sampling meets Approximation Regret](https://mlsanity.com/paper/2302.11182/) (2023)
- [On the Suboptimality of Thompson Sampling in High Dimensions](https://mlsanity.com/paper/2102.05502/) (2021)
- [Asymptotically Optimal Strategies For Combinatorial Semi-Bandits in Polynomial Time](https://mlsanity.com/paper/2102.07254/) (2021)
- [Pure Exploration and Regret Minimization in Matching Bandits](https://mlsanity.com/paper/2108.00230/) (2021)
- [Conservative Contextual Combinatorial Cascading Bandit](https://mlsanity.com/paper/2104.08615/) (2021)
- [Towards Efficient and Optimal Covariance-Adaptive Algorithms for Combinatorial Semi-Bandits](https://mlsanity.com/paper/2402.15171/) (2024)
- [Matroid Semi-Bandits in Sublinear Time](https://mlsanity.com/paper/2405.17968/) (2024)
- [Continuous Mean-Covariance Bandits](https://mlsanity.com/paper/2102.12090/) (2021)
- [Uplifting Bandits](https://mlsanity.com/paper/2206.04091/) (2022)
- [Thompson Sampling For Combinatorial Bandits: Polynomial Regret and Mismatched Sampling Paradox](https://mlsanity.com/paper/2410.05441/) (2024)
- [Covariance-adapting algorithm for semi-bandits with application to sparse rewards](https://mlsanity.com/paper/2604.13738/) (2026)
- [Unimodal Mono-Partite Matching in a Bandit Setting](https://mlsanity.com/paper/2208.01511/) (2022)
- [Logarithmic Regret for Unconstrained Submodular Maximization Stochastic Bandit](https://mlsanity.com/paper/2410.08578/) (2024)
- [Oracle-Efficient Combinatorial Semi-Bandits](https://mlsanity.com/paper/2510.21431/) (2025)
- [Tractable Instances of Bilinear Maximization: Implementing LinUCB on Ellipsoids](https://mlsanity.com/paper/2511.07504/) (2025)
- [Efficient Matroid Bandit Linear Optimization Leveraging Unimodality](https://mlsanity.com/paper/2512.00605/) (2025)
- [Budgeted Online Influence Maximization](https://mlsanity.com/paper/2604.19672/) (2026)
- [Worst-Case Regret Bounds for Combinatorial Thompson Sampling in Sleeping Semi-Bandits](https://mlsanity.com/paper/2605.09277/) (2026)

## Abstract (arXiv)

The combinatorial stochastic semi-bandit problem is an extension of the classical multi-armed bandit problem in which an algorithm pulls more than one arm at each stage and the rewards of all pulled arms are revealed. One difference with the single arm variant is that the dependency structure of the arms is crucial. Previous works on this setting either used a worst-case approach or imposed independence of the arms. We introduce a way to quantify the dependency structure of the problem and design an algorithm that adapts to it. The algorithm is based on linear regression and the analysis develops techniques from the linear bandit literature. By comparing its performance to a new lower bound, we prove that it is optimal, up to a poly-logarithmic factor in the number of pulled arms.