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“
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.
Cristina BUTUCEA, Alexandre TSYBAKOV, Julie JOSSE, Eric MOULINES, Mathieu ROSENBAUM