Pure Exploration and Regret Minimization in Matching Bandits

Flore Sentenac, Jialin Yi, Clément Calauzènes, Vianney Perchet, Milan Vojnovic

Introduction

Finding an optimal matching in a graph—such as pairing players in a multiplayer game (monopartite) or matching users to ads (bipartite)—is a classic combinatorial problem. In real-world sequential settings, the "weights" or success probabilities of these matches are unknown and must be learned over time through trial and error (bandit feedback).

Standard combinatorial bandit algorithms treat this as a generic problem, leading to sample complexity and regret that scale quadratically with the number of vertices ($O(N^2)$). However, in many real-world scenarios, the probability of a successful match is simply the product of the individual "qualities" of the two matched items. This means the underlying adjacency matrix has a rank-1 structure.

This paper investigates whether this specific structural property can be leveraged to learn the optimal matching much faster. The authors explore both "pair selection" (finding a single optimal pair) and "matching selection" (finding a full maximal matching) under two distinct objectives: pure exploration and regret minimization. By exploiting the rank-1 assumption, they design algorithms that reduce regret and sample complexity from quadratic to linear in the number of vertices.

Proposed Methods

The authors introduce several novel algorithms tailored to different settings and objectives:

  • PAIR-ELIM (Bipartite Pair Selection): To find the single best pair, this algorithm uses an Explore-Then-Commit (ETC) strategy with a clever twist: it eliminates sub-optimal rows and columns on different timescales. Rows are evaluated over a long horizon, while columns are evaluated in shorter, resetting "blocks." This aggressive temporary elimination prevents the algorithm from wasting samples on "doubly-suboptimal" pairs.
  • PAIR-ELIM-MONO (Monopartite Pair Selection): Adapts the above logic for monopartite graphs (where items are matched with each other) by duplicating items to create a pseudo-bipartite graph and tracking active pairs.
  • MATCHING-ID (Pure Exploration for Full Matching): To quickly sort all items and find the maximal matching, this algorithm compares unranked items directly against the top-ranked items.
  • ADAPTIVE-MATCHING (Regret Minimization for Full Matching): Uses a divide-and-conquer approach. It groups items into ranked clusters based on their estimated quality and matches items within the same cluster using a round-robin tournament.

Key Insights

  • Collaborative vs. Competitive Information: Unlike dueling bandits where playing item A against B tells you who is better, matching is collaborative. A high reward just means both items are good. To compare the relative order of A and B, you must pair them both with a third reference item C.
  • The "Best Point of Comparison" Principle: The fastest way to determine the relative order of two items is to pair them both with the highest quality item available.
  • The Tension Between Regret and Exploration: In full matching selection, the fastest way to learn the true rank of an unknown item (pure exploration) is to pair it with the best item. However, this is terrible for regret because you are "wasting" your best item on a potentially terrible match. Hence, regret minimization requires a completely different strategy (clustering similar items together) than pure exploration.

Empirical and Theoretical Results

The authors evaluate their algorithms using synthetic datasets, simulating bipartite and monopartite graphs using Bernoulli and Gaussian random variables to model the stochastic rewards of matched pairs.

Theoretical Speedup: By exploiting the rank-1 assumption, the authors successfully reduced the regret and sample complexity from $O(N^2 \log(T) / \Delta)$ to $O(N \log(T) / \Delta)$. This linear dependency on the number of vertices $N$ is a massive theoretical improvement. They also proved matching lower bounds for sample complexity, demonstrating that their algorithms are optimal up to multiplicative constants.

Empirical Regret (Pair Selection): In simulations, PAIR-ELIM significantly outperforms the baseline RANK1ELIM algorithm in cumulative regret, especially as the gap between optimal and sub-optimal items grows.

Cumulative regret of PAIR-ELIM vs. RANK1ELIM for pair selection

Empirical Regret (Matching Selection): SIMPLE-ADAPTIVE-MATCHING (SAM) outperforms the state-of-the-art ESCB algorithm for large time horizons. Furthermore, it avoids ESCB's NP-hard computational bottleneck, which normally requires solving a complex optimization problem at every single step.

Cumulative regret of SAM vs. ESCB for full matching selection

Limitations and Future Work

  • Theoretical Gaps: For the matching selection problem (pure exploration), the authors note a gap between their upper and lower theoretical bounds in specific regimes where the reward gaps between items are highly uneven.
  • Strict Rank-1 Assumption: The algorithms heavily rely on the strict rank-1 assumption ($W = uv^\top$). In real-world noisy datasets, matrices are rarely perfectly rank-1. Extending these algorithms to handle approximate rank-1 matrices or higher-rank matrices (e.g., $d$-dimensional latent features) would be a highly practical direction for future work.

Summary updated

Abstract

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 tha...
BibTeX
@inproceedings{sentenac2021pure,
  author = {Flore Sentenac and Jialin Yi and Clément Calauzènes and Vianney Perchet and Milan Vojnovic},
  title = {{Pure Exploration and Regret Minimization in Matching Bandits}},
  booktitle = {International Conference on Machine Learning},
  year = {2021},
  url = {https://openreview.net/forum?id=cWRwTU_Ada4},
}
Figure