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.
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.
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