mlsanityData to 7 Oct 2026

Asymptotically Optimal Strategies For Combinatorial Semi-Bandits in Polynomial Time

arXiv 2102.07254 ↗First posted 14 Feb 2021stat.ML cs.LGcited by 3

Not on the map. Why?

Abstract (arXiv)

We consider combinatorial semi-bandits with uncorrelated Gaussian rewards. In this article, we propose the first method, to the best of our knowledge, that enables to compute the solution of the Graves-Lai optimization problem in polynomial time for many combinatorial structures of interest. In turn, this immediately yields the first known approach to implement asymptotically optimal algorithms in polynomial time for combinatorial semi-bandits.

Key facts. Cited by 3 papers in the map (data through 7 Oct 2026). Builds on 5 of its 23 references that are in the map. First posted on arXiv 14 Feb 2021.

Builds on

5 of 23 references.

References · 5

  1. 2018Thompson Sampling for Combinatorial Semi-Banditscited by 78
  2. 2017Minimal Exploration in Structured Stochastic Banditscited by 40
  3. 2014Efficient Learning in Large-Scale Combinatorial Semi-Banditscited by 36
  4. 2016Combinatorial semi-bandit with known covariancecited by 24
  5. 2020Statistically Efficient, Polynomial Time Algorithms for Combinatorial Semi Banditscited by 11

Built on by

Cited by year

Citing papers per year: 2022: 1; 2023: 0; 2024: 1; 2025: 1.

3 papers.

  1. 2022A survey on multi-player banditscited by 18
  2. 2024Matroid Semi-Bandits in Sublinear Timecited by 3
  3. 2025Multimodal Bandits: Regret Lower Bounds and Optimal Algorithmscited by 0