Skip to content
conftrace_
2026 AISTATS AISTATS 2026

CONTEXTUAL RANKING AND MATCHING. OPTIMAL REGRET UNDER LST

We address the problem of online matchmaking with contextual information. In each round, a perfect matching between a varying set of players – with different strengths – is selected, and the outcomes of the comparisons of the chosen pairs are observed. We assume that matching players incurs dissatisfaction proportional to the "strength gap", thereby incentivising the pairing of players with closely matched strengths. Additionally, we assume that the strength of each player can be inferred from some available contextual information through the contextualised linear stochastic transitivity model (LST). We propose an algorithm that performs matchmaking by selecting pairs of maximum informativeness among admissible pairs and prove that its regret is optimal up to logarithmic factors.

More from AISTATS 2026

All AISTATS 2026 papers →