Overview
This research introduces Combinatorial Pure Exploration for Dueling Bandits (CPE-DB), a framework designed to identify the optimal matching of candidates to positions based on pairwise, relative feedback. The study provides the first computationally efficient algorithms for identifying both Borda and Condorcet winners in a combinatorial setting, effectively bridging the gap between complex combinatorial optimization and learning from relative preferences.
Problem Formulation
In many practical applications—such as matching job candidates to roles or recommending sets of items—feedback is often relative ("A is preferred over B") rather than absolute. While standard dueling bandits address this for single items, many tasks are inherently combinatorial, requiring the selection of an entire set (e.g., a matching in a bipartite graph) that is considered "best."
The CPE-DB problem presents two primary challenges:
- Relative Feedback: Observations are limited to the winner of a duel between two candidates for a specific position.
- Exponential Search Space: The number of possible matchings grows exponentially with the size of the candidate and position sets, precluding exhaustive search.
The objective is to find the best matching with high probability using minimal duels. The authors consider two optimality criteria: the Borda winner (maximizing average performance) and the Condorcet winner (a matching that beats all others in head-to-head comparisons).
Algorithmic Framework
The paper develops distinct strategies for the Borda and Condorcet cases:
Borda Winner Identification
The Borda score of a matching can be decomposed into a sum of rewards on its constituent edges. The authors adapt the Combinatorial Upper Confidence Bound (CLUCB) algorithm to this setting. To obtain an unbiased estimate of an edge's Borda reward, the algorithm duels it against an edge from a uniformly sampled random matching. Since uniform sampling of matchings is #P-complete, the authors utilize a fully polynomial almost uniform sampler and adjust the algorithm to account for the resulting bias.
Condorcet Winner Identification
Identifying a Condorcet winner involves a more complex minimax optimization: $\max_{x} \min_{y} P(x \text{ beats } y)$. The authors propose CAR-Cond, which employs a continuous relaxation of the problem. They develop a Fully Polynomial Time Approximation Scheme (FPTAS) as an "offline oracle" using projected sub-gradient ascent and the Frank-Wolfe algorithm. This oracle guides the online learner in deciding which edges to include in the final matching.
Theoretical Insights
A key finding is the potential discrepancy between Borda and Condorcet winners. As illustrated in the figures below, a matching that performs best on average (Borda) may still lose to a specific rival in a direct head-to-head duel.
Furthermore, the authors demonstrate that Borda winners can be reduced to a linear reward structure, allowing for the application of standard multi-armed bandit techniques. For the Condorcet case, they show that an efficient offline approximation can be integrated into an online learning process while maintaining polynomial time complexity per round.
Main Results
- Computational Efficiency: Both CLUCB-Borda and CAR-Cond operate in polynomial time per round, ensuring practical feasibility for large-scale graphs.
- Sample Complexity: The Borda algorithm achieves sample complexity comparable to standard multi-armed bandits, which is nearly optimal for certain subclasses. CAR-Cond is the first algorithm to achieve polynomial time per round with a rigorous sample complexity analysis.
- Theoretical Tightness: Lower bounds for the Borda case indicate that the proposed algorithms are tight up to logarithmic factors and a graph-dependent "width" term.
Conclusion and Future Directions
While this work establishes a solid foundation for combinatorial dueling bandits, several avenues for future research remain. The sample complexity for Borda winners includes a width(G) factor; determining if this is strictly necessary is an open question. Additionally, there is potential to improve the sample complexity of CAR-Cond. Finally, extending these techniques beyond bipartite matching to other combinatorial structures, such as spanning trees or paths, or to non-linear preference models, would be of significant interest.
Summary updated