Timezone: »

 
Spotlight
Pure Exploration and Regret Minimization in Matching Bandits
Flore Sentenac · Jialin Yi · Clément Calauzènes · Vianney Perchet · Milan Vojnovic

Wed Jul 21 06:45 PM -- 06:50 PM (PDT) @
in Bandits 3 »

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 to poly-log terms).

Keywords: Bandits · Reinforcement Learning and Planning

Author Information

Flore Sentenac (CREST)
Jialin Yi (London School of Economics)
Clément Calauzènes (Criteo AI Lab)
Vianney Perchet (ENSAE & Criteo AI Lab)
Milan Vojnovic (London School of Economics)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors