We thank the reviewer for the valuable feedback.

We thank the reviewer for pointing out minor issues and typos, we will correct them accordingly.

Questions:

1. Indeed, the SST assumption is unnecessarily strong on Line 122, the total order assumption is sufficient.
2. On using a partial decoupling instead of the full decoupling in WR-TINF: We acknowledge that our sampling method may occasionally result in selecting the same arm twice ($I_t = J_t$), which is not ideal for weak regret minimization. However, WR-TINF's design ensures that the probability of this event is small enough to maintain the presented guarantees, which are optimal in scenarios that we describe. While we could modify the algorithm to prevent entirely that $I_t = J_t$, such a modification would not enhance our theoretical guarantees significantly. The introduction of the internal sampling step $(I'_t, J'_t)$ simplifies the technical analysis by ensuring that the played arms $(I_t, J_t)$ are conditionally independent given $(I'_t, J'_t)$. This conditional independence allows for a reduction to the standard MAB problem in our weak regret setting, stated in Lemma A.1. We propose including this discussion as a remark in the relevant section of our paper.
3. On using data from past stages: Indeed, at each stage, we start learning from scratch. This resulting independence leads to a cleaner technical analysis of the guarantees. While using samples from past stages does not change the theoretical results (except for an impact on multiplicative constants in the upper bound), it does have a practical impact, and we actually advocate for this approach in practice. This was reflected in some experiments conducted with WR-EXP3-IX using past data.
4. On why $S(i)$ mimics a random walk: In WR-EXP3-IX, when we fix the first action $i$ and play the second action $k$ according to the EXP3-IX algorithm, after a few rounds, the choices of $k$ concentrate on the best opponent $j^*(i)$ (corresponding to the best arm in this EXP3-IX instance). Consequently, the algorithm selects the pair $(i, j^*(i))$ in most rounds. This implies that the increments of $S(i)$ (the cumulative loss) are independent and identically distributed as $X(i, j^*(i)) - 1/2$. Therefore, $S(i)$ behaves similarly to a random walk with drift $\mathbb{E}[X(i, j^*(i)) - 1/2] = \Delta_{i, j^*(i)}$, though it is not exactly a random walk.
5. On the zero gaps with the CW: Recall that the case where all the gaps with the CW are $0$, the problem of weak and strong regret minimization is irrelevant, as the losses incurred in each round are a function of those gaps (this will lead to a $0$ loss for any played arms). On the other hand, if one of the gaps between the CW $i^*$ and an arm $i \neq i^*$ is $0$, then the guarantees of WR-EXP3-IX become loose due to the dependence on $\Delta_* = \min_{i \neq i^*} \Delta_{i^*, i}$ in the logarithmic factor in the upper bound. Note that in Assumption 2.1, we suppose that the CW has a probability of winning strictly larger than $1/2$.
6. On numerical simulations:

Variance of WS-W: WS-W is a round-based procedure where the selected arms, "winner and challenger," duel in batches of iterations. The length of each batch increases with the number of duels won by the selected arms so far. When an arm loses, it is replaced by a contender chosen from the remaining arms. Once the set of candidate arms is exhausted, the process is repeated. In numerical experiments, particularly with a large number of arms (Scenario 3 in the simulations section), we observe that in some unfortunate cases, especially in the early stages, the CW may lose its duels. This results in a large number of iterations before it is picked again as a contender, leading to very high weak regret for the procedure. Although such outcomes are infrequent, they significantly impact the empirical variance of the weak regret of WS-W.

Strong performance of WS-W when the number of arms is small: The guarantees on WS-W from [1] show that their upper bound has the advantage of a smaller numerical factor, whereas ours have larger numerical constants. However, this effect is negligible for large-size problems, as Figure 1(d) demonstrates that both WR-TINF and WR-EXP3-IX perform better than WS-W.

[1] Bangrui Chen and Peter I Frazier. Dueling bandits with weak regret. In International Conference on Machine Learning, pages 731–739. PMLR, 2017.

We thank the reviewer for the valuable feedback.

Weaknesses:

Quality: We performed additional experiments using the MBTW algorithm (from [1] below) under the same scenarios outlined in our Numerical Simulations section. The simulation results are presented in Figure 1 of the global rebuttal.

Firstly, it is important to note that there are no theoretical guarantees developed for the MBTW algorithm. Nevertheless, we included MBTW in our experiments to provide a comprehensive comparison.

The experimental results, detailed in Figure 1 of our global rebuttal, indicate that while the MBTW algorithm performs similarly to WR-EXP3-IX and WR-TINF in scenarios with a moderate and large number of arms (Scenarios 3 and 4), its performance is unstable in Scenario 1. Specifically, we observed high variance in results and instances where the regret diverged significantly, resulting in very large regret values in some cases. This particular experiment was conducted multiple times, yielding consistent outcomes.

Clarity: Thank you for your suggestion and for pointing out the typos. We will correct them. Additionally, we will add intermediate steps to the proof of Lemma D.2 to make it clearer and easier to follow.

Question:

You are correct regarding this point. In the discussion of Algorithm 2 (beginning of page 8), $\Delta_{\text{sub}}$ should be defined as the maximal gap between sub-optimal arms (as mentioned in the paragraph by words): $\Delta_{sub} = \max_{i,j \neq k*} \Delta_{i,j}$ instead of $\Delta_{sub} = \max_{j} \Delta_{i,j}$. We apologize for the typo and will correct it.

[1] Erol Peköz, Sheldon M Ross, and Zhengyu Zhang. Dueling bandit problems. Probability in the Engineering and Informational Sciences, 36(2):264–275, 2022.

We thank the reviewer for the valuable feedback.

Weaknesses:

1. We apologize for the typos and the out-of-range equations. We will correct the typos we have identified as well as those noted in the reviews.

Questions:

1. On the correctness of Equation 8: Both the statement of Lemma B.4 and equation (8) in Algorithm 1 are correct. We employed a version of online mirror descent with Tsallis regularization as analyzed in [1] (specifically, refer to Section 3.2 in [1]).
2. Thank you for spotting this typo, we will correct it.
3. On resampling $(I_t,J_t)$ in the else statement of WR-TINF: In WR-TINF, we initially sample two arms $(I'_t, J'_t)$ without playing them. Based on the outcome (whether $I'_t = J'_t$ or not), we then specify the distribution for the arms to be played $(I_t, J_t)$. The reason for resampling $I_t$ and $J_t$ from the same distribution (the else statement) is to enhance clarity by distinguishing between the internal sampling step of $(I'_t, J'_t)$ and the step where we sample the arms $(I_t,J_t)$ that are actually played. Additionally, this is simpler technically, as the played arms $I_t$ and $J_t$ remain independent given $I'_t$ and $J'_t$ - see Algorithm 1.
4. On the possibility of having $I_t=J_t$: You are correct in noticing that with our sampling scheme, there is still a possibility of playing the same arm twice ($I_t = J_t$), which is not ideal for minimizing the weak regret as discussed. However, the rationale behind WR-TINF is that, contrary to algorithms designed for minimizing the strong regret, our scheme makes the probability of the event $I_t = J_t$ low enough to ensure the presented regret upper bound guarantees - which are optimal in the cases that we describe. We could modify the algorithm to ensure that this event never occurs, for example by repeatedly sampling $(I_t, J_t)$ until they are different. However, this would not improve significantly the theoretical guarantees and would complicate the analysis of the algorithm.
5. On the performance of WR-TINF in the strong regret setting: We agree that if the optimality gaps of the Condorcet winner are large, then the sampling distributions $p_t$ and $r_t$ will quickly concentrate on the optimal arm, leading to small losses for the strong regret in this specific case. Note that $r_t$ will concentrate slower than $p_t$ on the Condorcet winner. It is possible that in this scenario, one can derive sublinear regret for the strong regret. However, we believe that it will not achieve the optimal guarantees for the strong regret, which are logarithmic in $T$.
6. Thank you for spotting this formatting issue, we will correct it.
7. We apologize for the typo, instead of $\bar{T} := \lceil*\rceil\frac{256K}{\Delta_*^2}$, we meant $\bar{T} := \lceil\frac{256K}{\Delta_*^2}\rceil$.

[1] Julian Zimmert and Yevgeny Seldin. Tsallis-inf: An optimal algorithm for stochastic and adversarial bandits. The Journal of Machine Learning Research, 22(1):1310–1358, 2021.

Thank you for your explanation.

Aside from such minor issues (e.g., typos), I believe the paper is excellent in terms of motivation (weak regret) and is mathematically robust. After reviewing the appendix again, I found no issues with the overall flow. The additional experiments further strengthened my confidence in the paper. I will raise my score to 7.