Loading Events

« All Events

Matthieu LERASLE (ENSAE) – “Pair Matching as a tricky bandit problem”

September 23, 2:00 pm - 3:15 pm

The Statistical Seminar: Every Monday at 2:00 pm.

Time: 2:00 pm – 3:15 pm
Date: 23th of September 2019
Place: Room 3001.

Matthieu LERASLE (ENSAE) – “Pair Matching as a tricky bandit problem

Abstract:

The pair-matching problem appears in many applications where one wants to discover good matches between pairs of individuals.

The set of individuals is represented by the nodes of a graph where the edges, unobserved at first, represents the good matches.

A pair matching algorithm queries sequentially pairs of nodes and observes the presence/absence of edges.

Its goal is to discover as many edges as possible with a fixed budget of queries.

Pair-matching is a particular instance of multi-armed bandit problem in which the arms are pairs of individuals and the rewards are edges linking these pairs.

This bandit problem is non- standard since each arm can only be played once.

Given this last constraint, sublinear regret can be expected only if the graph presents some underlying structure.

In the talk, I will show that sublinear regret is achievable in the case where the graph is generated according to a stochastic block model with two communities.

Optimal regret bounds are computed for this pair-matching problem.

They exhibit a phase transition related to the Kesten-Stigund threshold for community detection in the stochastic block model.

To limit the concentration of queried pairs, the pair-matching problem is also considered in the case where each node is constrained to be sampled less than a given amount of times.

I will show how this constraint deteriorates optimal regret rates.

This talk is based on the submitted paper arXiv:1905.07342.

Organizers:
Cristina BUTUCEA, Alexandre TSYBAKOV, Julie JOSSE, Eric MOULINES, Mathieu ROSENBAUM

Sponsors:
CREST-CMAP

 

Details

Date:
September 23
Time:
2:00 pm - 3:15 pm
Event Category:

Venue