Alert button

Pure Exploration and Regret Minimization in Matching Bandits

Add code
Bookmark button
Alert button
Jul 31, 2021
Flore Sentenac, Jialin Yi, Clément Calauzènes, Vianney Perchet, Milan Vojnovic

Figure 1 for Pure Exploration and Regret Minimization in Matching Bandits
Figure 2 for Pure Exploration and Regret Minimization in Matching Bandits
Figure 3 for Pure Exploration and Regret Minimization in Matching Bandits
Figure 4 for Pure Exploration and Regret Minimization in Matching Bandits

Share this with someone who'll enjoy it:

Twitter IconFacebook IconLinkedin IconWhatsapp IconMessenger Icon

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).

* Proceedings of the 38th International Conference on Machine Learning, PMLR 139, 2021  
View paper onarxiv icon

Share this with someone who'll enjoy it:

Twitter IconFacebook IconLinkedin IconWhatsapp IconMessenger Icon