Pure Exploration and Regret Minimization in Matching Bandits

Autor:	Sentenac, Flore, Yi, Jialin, Calauz��nes, Cl��ment, Perchet, Vianney, Vojnovic, Milan
Jazyk:	angličtina
Rok vydání:	2021
Předmět:	FOS: Computer and information sciences Computer Science - Machine Learning Statistics - Machine Learning TheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITY Machine Learning (stat.ML) Machine Learning (cs.LG) MathematicsofComputing_DISCRETEMATHEMATICS
Popis:	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).
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_dedup___::ba81353f1cad2b6cf891489acbda5d6f http://arxiv.org/abs/2108.00230 Zobrazit plný text záznamu