Combinatorial Pure Exploration of Dueling Bandit

Wei Chen, Yihan Du, Longbo Huang, Haoyu ZhaoarXiv 2020 · arXiv

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:

  1. Relative Feedback: Observations are limited to the winner of a duel between two candidates for a specific position.
  2. 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).

A bipartite graph and its corresponding preference matrix defining the win probabilities between edges.

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.

Comparison of the Borda winner and Condorcet winner for a given instance, demonstrating that they can be distinct matchings.

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

Abstract

In this paper, we study combinatorial pure exploration for dueling bandits (CPE-DB): we have multiple candidates for multiple positions as modeled by a bipartite graph, and in each round we sample a duel of two candidates on one position and observe who wins in the duel, with the goal of finding the best candidate-position matching with high probability after multiple rounds of samples. CPE-DB is an adaptation of the original combinatorial pure exploration for multi-armed bandit (CPE-MAB) problem to the dueling bandit setting. We consider both the Borda winner and the Condorcet winner cases. For Borda winner, we establish a reduction of the problem to the original CPE-MAB setting and design PAC and exact algorithms that achieve both the sample complexity similar to that in the CPE-MAB setting (which is nearly optimal for a subclass of problems) and polynomial running time per round. For Condorcet winner, we first design a fully polynomial time approximation scheme (FPTAS) for the offline problem of finding the Condorcet winner with known winning probabilities, and then use the FPTAS as an oracle to design a novel pure exploration algorithm ${\sf CAR}$-${\sf Cond}$ with sample complexity analysis. ${\sf CAR}$-${\sf Cond}$ is the first algorithm with polynomial running time per round for identifying the Condorcet winner in CPE-DB.
BibTeX
@misc{chen2020combinatorial,
  author = {Wei Chen and Yihan Du and Longbo Huang and Haoyu Zhao},
  title = {{Combinatorial Pure Exploration of Dueling Bandit}},
  year = {2020},
  eprint = {2006.12772},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2006.12772},
}
Figure