mlsanityData to 7 Oct 2026

Pure Exploration and Regret Minimization in Matching Bandits

arXiv 2108.00230 ↗First posted 31 Jul 2021stat.ML cs.LGcited by 4

Not on the map. Why?

Abstract (arXiv)

Finding an optimal matching in a weighted graph is a standard combinatorial problem. We consider its semi-bandit version where either a pair or a full matching is sampled sequentially. We prove that it is possible to leverage a rank-1 assumption on the adjacency matrix to reduce the sample complexity and the regret of off-the-shelf algorithms up to reaching a linear dependency in the number of vertices (up to poly log terms).

Key facts. Cited by 4 papers in the map (data through 7 Oct 2026). Builds on 12 of its 23 references that are in the map. First posted on arXiv 31 Jul 2021.

Builds on

12 of 23 references.

References · 12

  1. 2014On the Complexity of Best Arm Identification in Multi-Armed Bandit Modelscited by 280
  2. 2016Optimal Best Arm Identification with Fixed Confidencecited by 233
  3. 2018Thompson Sampling for Combinatorial Semi-Banditscited by 78
  4. 2020Statistical Efficiency of Thompson Sampling for Combinatorial Semi-Banditscited by 30
  5. 2019Top-k Combinatorial Bandits with Full-Bandit Feedbackcited by 28
  6. 2017Online Learning to Rank in Stochastic Click Modelscited by 26
  7. 2016Combinatorial semi-bandit with known covariancecited by 24
  8. 2016Stochastic Rank-1 Banditscited by 23
  9. 2019Solving Bernoulli Rank-One Bandits with Unimodal Thompson Samplingcited by 23
  10. 2017Bernoulli Rank-1 Bandits for Click Feedbackcited by 11
  11. 2020Statistically Efficient, Polynomial Time Algorithms for Combinatorial Semi Banditscited by 11
  12. 2018Exploration vs. Exploitation in Team Formationcited by 1

Built on by

Cited by year

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

4 papers.

  1. 2022Choosing Answers in varepsilon-Best-Answer Identification for Linear Banditscited by 1
  2. 2022Unimodal Mono-Partite Matching in a Bandit Settingcited by 0
  3. 2022UniRank: Unimodal Bandit Algorithm for Online Rankingcited by 0
  4. 2025Linear Bandits beyond Inner Product Spaces, the case of Bandit Optimal Transportcited by 0