📊 statistics

Tree-Guided Identify-Then-Exploit: A Unified Framework of Best Arm Identification and Regret Minimization for Dueling Bandits

This paper proposes Tree-Guided Identify-Then-Exploit (TG-ITE), a unified framework for $N$ -armed stochastic dueling bandits that achieves optimal $O(N)$ sample complexity for best-arm identification and weak regret, as well as $O(N \log T)$ strong regret, by utilizing a shared tree-guided identification stage followed by objective-specific exploitation strategies.

Original authors: Pu Wang, Yao-Xiang Ding

Published 2026-06-02

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Pu Wang, Yao-Xiang Ding

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a talent scout trying to find the single best performer in a large group of $N$ artists. However, there's a catch: you can't ask the artists to perform solo and get a score. Instead, you can only put two artists in a room together and watch them compete. You don't know who is better beforehand, and sometimes the results are noisy (maybe the audience is tired, or the lighting is bad). This is the world of Dueling Bandits.

The paper proposes a new, unified strategy called Tree-Guided Identify-Then-Exploit (TG-ITE) to solve three different problems in this scenario:

Finding the Winner (BAI): You just want to identify the best artist as quickly as possible and stop.
Minimizing "Bad Dates" (Weak Regret): You want to keep showing the audience the current best artist, but occasionally test new challengers. You only get "penalty points" if you show two bad artists together.
Minimizing "Bad Dates" (Strong Regret): You get penalty points for any comparison that doesn't involve the true best artist. You want to find the winner and then just show them against themselves (or stop testing) as much as possible.

Here is how the paper's solution works, broken down into simple concepts:

1. The Core Idea: "Identify Then Exploit"

Usually, in these problems, you have to choose between exploring (testing new people) and exploiting (sticking with who you think is best). The paper suggests a two-step approach:

Step 1 (Identify): Run a quick, structured tournament to find a "high-confidence" candidate for the best artist.
Step 2 (Exploit): Once you have a strong candidate, switch gears. Depending on your goal (finding the winner fast, or minimizing bad dates), you use that candidate in a specific way.

2. The Secret Sauce: The "Tree" Tournament

The hardest part is Step 1: How do you find the best artist among $N$ people without testing every single pair (which would take forever)?

The authors use a Tree-Guided approach. Imagine the artists are leaves on a giant family tree.

Instead of testing everyone against everyone, you organize them into a knockout tournament based on the tree structure.
You start with a random artist and walk up the tree. At each level, you take the current "champion" and pit them against a new group of challengers (a "sibling block" on the tree).
You run a mini-tournament to see who wins that group.
The winner of that group becomes the new champion, and you move up to the next level.

Why is this smart?
Because the tree is balanced, the groups get bigger as you go up (1 person, then 2, then 4, then 8...). The algorithm is clever about how much "confidence" it demands at each step. It spends just enough time testing to be sure the winner of the small group is actually good, but not so much that it wastes time.

The Result: They prove this method finds the true best artist with high confidence using only $O(N)$ comparisons. This is the fastest possible speed (linear time), and they do it without needing to assume the artists follow a perfect, logical ranking (which is often unrealistic).

3. The Three Strategies (The "Exploit" Phase)

Once the "Tree" phase finds a strong candidate, the algorithm changes its behavior based on what you want:

Goal A: Just Find the Winner (BAI)
- Strategy: Run the Tree tournament, pick the winner, and stop immediately.
- Result: You found the best artist in the fastest possible time ( $O(N)$ ), beating previous methods that required stronger assumptions about how the artists compare.
Goal B: Minimize "Bad Dates" where one side is free (Weak Regret)
- Strategy: Use the Tree tournament to find a "Warm Start" champion. Then, use a "Winner-Stays" strategy.
- How it works: You keep the current champion on stage (one arm). You bring in challengers one by one to fight them (the other arm). If a challenger beats the champion, the challenger becomes the new champion. If the champion wins, they stay.
- The Innovation: Previous "Winner-Stays" methods were slow ( $O(N \log N)$ ). This paper's version is faster ( $O(N)$ ) because the "Warm Start" from the Tree phase gives them a much better starting point than just guessing. It also fixes a gap where previous methods couldn't find the winner and minimize bad dates simultaneously without a penalty.
Goal C: Minimize "Bad Dates" where any non-winner is bad (Strong Regret)
- Strategy: Use the Tree tournament to find a reliable champion. Once found, stop testing and just have the champion compete against themselves (or stop the game).
- Result: This achieves the best possible theoretical guarantee ( $O(N \log T)$ ), matching the best specialized algorithms but using the same simple "Tree" foundation.

4. Why This Matters

The paper claims that for a long time, people thought you had to sacrifice one goal to get another (e.g., if you want to find the winner fast, you might accumulate many "bad dates" while doing it).

This paper argues that in the world of "Dueling Bandits" (where you compare two things at once), the trade-off is actually much friendlier. By using the Tree-Guided method to get a "warm start," they can build one single framework that:

Finds the winner as fast as theoretically possible.
Minimizes bad dates as fast as theoretically possible.
Does all three things (BAI, Weak Regret, Strong Regret) with the same underlying logic, just changing the "tail end" of the strategy.

In short: They built a universal "Talent Scout" that uses a smart tree-tournament to quickly find a superstar, and then adapts its behavior to either announce the winner, keep the show running smoothly, or stop testing entirely, all while being mathematically proven to be the most efficient way to do it.

Technical Summary: Tree-Guided Identify-Then-Exploit (TG-ITE)

Problem Formulation

The paper addresses the problem of $N$ -armed stochastic dueling bandits under the Condorcet winner assumption. In this setting, a learner selects pairs of arms $(i, j)$ and observes a binary outcome indicating which arm wins, governed by an unknown preference matrix $P$ . The core assumption is the existence of a unique Condorcet winner $a^\star$ such that $P(a^\star, j) > 1/2$ for all $j \neq a^\star$ , while preferences among non-winning arms may be cyclic.

The study focuses on unifying three distinct objectives within this single framework:

Best Arm Identification (BAI): Returning $a^\star$ with high confidence ( $1-\delta$ ) at a data-dependent stopping time.
Weak Regret Minimization: Minimizing the cumulative regret where a round incurs zero regret if at least one of the two chosen arms is $a^\star$ .
Strong Regret Minimization: Minimizing regret where a round incurs zero regret only if both chosen arms are $a^\star$ (self-play).

The central research question is whether a unified algorithmic framework can achieve optimal performance across all three objectives simultaneously, overcoming the traditional trade-off between exploration (needed for BAI) and exploitation (needed for regret minimization).

Methodology: Tree-Guided Identify-Then-Exploit (TG-ITE)

The proposed solution, TG-ITE, adopts an Identify-Then-Exploit paradigm. It decouples the problem into a shared identification phase followed by objective-specific exploitation strategies.

1. Shared Identification Primitive: TREEASCENT

The core innovation is a Tree-Guided Identification algorithm called TREEASCENT. Unlike standard "Explore-Then-Commit" (ETC) strategies which are often suboptimal in cumulative regret, TREEASCENT utilizes a deterministic, balanced binary tree structure to guide the search for the Condorcet winner.

Mechanism: Starting from an arbitrary arm $b$ , the algorithm walks up the ancestor path of a fixed binary tree. At each level $h$ , it performs a knockout tournament on a "sibling block" of arms (arms newly attached at that level) to find a representative.
Merging: The representative from the sibling block is then compared against the current "champion" (the winner from the previous level) using a sequential pairwise test (DUELTEST).
Efficiency: By allocating confidence budgets proportional to the size of the sibling blocks (geometrically growing sizes), the algorithm identifies a high-confidence incumbent with $O(N)$ sample complexity. This is achieved without requiring stronger assumptions like strong stochastic transitivity or stochastic triangle inequality, relying only on the existence of the Condorcet winner and a global gap $\Delta$ .

2. Objective-Specific Exploitation Strategies

Once a high-confidence incumbent is identified via TREEASCENT, the framework switches to specific exploitation policies:

For BAI (TG-ITE-BAI): The algorithm simply runs TREEASCENT and stops upon returning the identified arm. This achieves $O(N)$ sample complexity, matching the theoretical lower bound for BAI.
For Weak Regret (TG-ITE-WEAK): The algorithm uses TREEASCENT as a constant-confidence "warm start" to find an initial winner. It then employs a Winner-Stays (WS) style strategy called SCREENANDREPLACE. In each epoch, the current incumbent is screened against all challengers. If a challenger appears to beat the incumbent, a replacement tournament is held. This approach achieves $O(N)$ weak regret, improving upon previous $O(N \log N)$ results.
For Strong Regret (TG-ITE-STRONG): The algorithm identifies a reliable incumbent via TREEASCENT and then engages in self-play (comparing the incumbent against itself).
- Known Horizon: Run TREEASCENT with confidence $1/(H+1)$ , then self-play.
- Anytime Horizon: Interleave increasingly confident identification passes with increasingly long self-play blocks.
- This achieves $O(N \log T)$ strong regret, matching specialized strong-regret algorithms.

Key Contributions and Results

1. Unified Framework

TG-ITE is the first framework to unify BAI, weak regret, and strong regret in dueling bandits using a shared identification primitive. It demonstrates that the trade-off between identification and regret minimization is "benign" in the dueling bandit setting due to the ability to use one arm for exploration and another for exploitation.

2. Improved Sample Complexity and Regret Bounds

BAI: Achieves $O(N)$ sample complexity without requiring strong stochastic transitivity or total order assumptions, matching the best-known results for BAI.
Weak Regret: Achieves $O(N)$ weak regret, closing the $O(\log N)$ gap found in previous joint optimization approaches (e.g., Ma et al., 2025) and matching the best instance-independent bounds.
Strong Regret: Achieves $O(N \log T)$ regret, matching the guarantees of specialized algorithms like WS-S and RUCB.
Joint Optimization: The framework allows for the simultaneous optimization of BAI and weak regret, achieving $O(N)$ guarantees for both, eliminating the sub-optimal $O(\log N)$ factors present in prior work.

3. Theoretical Guarantees

The paper provides rigorous proofs for the correctness and cost of TREEASCENT and the subsequent exploitation phases.

Theorem 1: TREEASCENT identifies the Condorcet winner with probability $1-\epsilon$ using $O(N)$ comparisons.
Theorem 2: The weak regret of TG-ITE-WEAK is bounded by $O(N/\Delta^2)$ , which is linear in $N$ and independent of the time horizon $T$ .
Theorem 3 & 4: Strong regret bounds are $O(N \log T)$ for both known and unknown horizons.

4. Extensions

The paper also presents a Known-Gap Budgeted Extension (Section 5). If a lower bound $g$ on the Condorcet gap is known, the algorithm can replace the anytime DUELTEST with a fixed-budget test. This removes the $\log(1/\Delta)$ factor from the bounds, providing deterministic comparison budgets and tighter guarantees, though at the cost of requiring prior knowledge of the gap.

Experimental Validation

The authors evaluate TG-ITE against representative baselines (including WS-W, WS-S, RUCB, WR-TINF, and WSW-PE) on synthetic instances designed to stress-test non-transitivity and asymmetric gaps.

BAI Scaling: TG-ITE-BAI scales near-linearly with $N$ , outperforming adaptive pairwise elimination methods on cyclic instances.
Weak Regret: TG-ITE-WEAK achieves the lowest cumulative regret and plateaus quickly, demonstrating the efficacy of the warm-start strategy.
Strong Regret: TG-ITE-STRONG significantly outperforms baselines, with the curve flattening once self-play begins, confirming the theoretical $O(N \log T)$ behavior.

Significance and Claims

The paper claims that TG-ITE provides theoretical evidence that the trade-off between Best Arm Identification and Regret Minimization is relatively benign in dueling bandits. By leveraging the unique structure of dueling bandits (selecting two arms), the framework successfully decouples the exploration and exploitation phases without the sub-optimality typically seen in standard multi-armed bandits.

The authors emphasize that their approach:

Unifies three distinct objectives under a single, reusable identification primitive (TREEASCENT).
Improves upon the state-of-the-art for weak regret by removing the $O(\log N)$ factor and relaxing the total order assumption.
Matches the optimal rates for BAI and strong regret without requiring stronger structural assumptions (like strong stochastic transitivity) that previous optimal algorithms relied upon.

The work suggests that the "Identify-Then-Exploit" template, when guided by a tree-based tournament decomposition, is a powerful and generalizable strategy for preference-based learning.