Thank you for your positive feedback and strong support. We address your comments and questions as follows:

Q1: Besides for the original version of the EXP3 algorithm (Auer et al. 2002), it is more common to find this algorithm stated with the use of losses rather than rewards, as it is not necessary to include extra exploration. Have you considered converting these rewards into losses and relying on EXP3 with losses (and possibly with time-dependent leaning rate?)
A1: We believe the reward formulation and loss formulation are essentially equivalent to a negation sign. For an unknown time horizon, indeed, we can incorporate a time-varying learning rate. For simplicity, we did not add this variant. We will add comments on this.

Q2: Will the ETC algorithm always have larger regret than the BEXP3 one due to the cost of the exploration phase or are there problem settings in which the ETC algorithm is better? as the BEXP3 algorithm is more robust and performs better in the experiments, I wonder if there is any case where one would prefer the ETC algorithm?
A2: ETC versus EXP3: Two algorithms have essentially the same order of regret in our setting because $K = 2^d$. During our experiment, we did not carefully tune the constant in front of each parameter. As shown in Appendix I of the revised version, tuning the parameters of BETC can lead to an improvement of up to 50%. Our belief is that two algorithms should perform equally well in a stochastic setting, and only differ by a constant order.

When can BETC beat BEXP3? BETC can work for general link functions, while BEXP3 is guaranteed to work only for the linear model. Even though in our experiments BEXP3 worked well with the logistic link function, it is not guaranteed to work well under any link function. For a less favorable link function, it might fail.
Besides, our current implementation of BEXP3 requires $K$ to be not too large $K = O(2^d)$, which is often true in real-world applications. When $K$ is extremely large, then BETC is preferred as the sample complexity does not depend on $K$ but only on the dimension $d$. (see Q2 in our response to Reviewer Kuh2 for more details)

Thank you for your feedback! We address your comments and questions as follows:

Q1: The authors assert that previous work by Saha (2021) on linear contextual duel bandits can be considered a special case of their model. However, the cited work involves a contextual set of arms that may change over time and a more generalized Multi-nomial logistic model, in contrast to the fixed feature vectors and dueling bandits considered in this study.
A1: As explained in Section A.1, in Saha (2021), the assumption is that each item has a `score’ $v_i = x_i^{\top} \theta^*$. Then, a changing set of arms is possible as long as the comparison follows the logistic model $P(i \succ j) = \mu(v_i - v_j) = \mu((x_i - x_j)^{\top}\theta^*)$. Similarly, the generalized multi-nomial logistic model can be satisfied as $P(i \text{ chosen among all items}) \propto e^{v_i}$.

We claimed that our setting covers theirs because we consider $P(i \succ j) = \mu(\phi_{i,j}^{\top} \theta^*)$, and if $\phi_{i,j} = x_i - x_j$, then our setting becomes theirs, albeit with fixed arms and pairwise comparison only. On the other hand, in our general setting, $x_i$ is not available. Then it will not allow either a set of arms that may change over time or a multi-nomial logistic model that depends on the existence of $x_i$.

Q2: Why the previously proposed algorithm in [Saha 2021] attain a regret bound of $\sqrt{T}$ which appears to be superior to the results presented in this work, specifically $T^{2/3}$ in both lower and upper bounds?
A2: We believe there is some misunderstanding here. As explained in the last question if we do only have $\phi_{i,j}$ instead of $x_i$ and $x_j$, then the algorithms in [Saha 2021] cannot work at all in our setting, because they have no access to the non-existent $x_i$, not to mention a $\sqrt{T}$ regret.

We can only achieve $T^{2/3}$ regret because our studied problem is a more general one, as explained above. And a more general class of problems will incur no less regret than a subset of problems does. So it is normal to have their $\sqrt{T}$ regret for a subset of problems against our $T^{2/3}$ for the whole problem set.

Q3: Regarding Theorem 4.1, what constitutes the primary technical challenge in analyzing the lower bound for the linear bandit model compared to the Multi-Armed Bandit (MAB) scenario discussed in [Saha 2021a]?
A3: In the previous work [Saha et al 21], there are $K-1$ good arms and only the best one of them differs from the others. This design will not work in our setting as it leads to lower bounds sub-optimal in dimension $d$. The new construction of our lower bound is based on the hardness of identifying the best arm in the $d$-dimensional linear bandit setting, which is quite different from the multi-armed setting.

[Saha et al 21]’s proof is directly based on hypothesis testing: either identifying the best arm with gap $\epsilon$ within $T$ rounds (if $T > \frac{K}{1440 \epsilon^3}$) or incurring $\epsilon T$ regret (if $T \le \frac{K}{1440 \epsilon^3}$). In contrast, our proof technique bounds from below the regret by the expected number of sub-optimal arm pulls and does not divide the problem instances into two cases (i.e. whether $T≤\frac{K}{1440 \epsilon^3}$). To prove the lower bound, we first apply a new reduction step to restrict the choice of $i_t$. Then we bound from below the regret by the expected number of sub-optimal arm pulls.

Thank you for your feedback and your suggestions on writing! We address your comments and questions as follows:

Q1: Can the adversarial dueling bandit analysis be improved to $d^{2/3} T^{2/3}$ for very large K?
A1: Yes. The main idea is to use an $\epsilon$-covering argument. In the $d$-dimensional space, it suffices to choose $O((1/\epsilon)^{d})$ representative vectors to cover all $K$ average contextual vectors $\frac{1}{K} \sum_{j=1}^{K}\phi_{i,j}$ with error up to $\epsilon$. Now BEXP3 will be performed as the original case except that at Line 7 in Alg 2, we replace the average contextual vectors $\frac{1}{K} \sum_{j=1}^{K}\phi_{i,j}$ with those nearest representative vectors. Since there are only $O((1/\epsilon)^{d})$ uniquely different rewards, the EXP3 argument (equation D.3) can be performed on $O((1/\epsilon)^{d})$ unique arms and eventually the algorithm suffers a regret of $\tilde{O}(d^{2/3} T^{2/3} \log^{1/3}(1/\epsilon))$. The $\epsilon$-net incurs an additional approximation error of order $O(\epsilon T)$. Setting $\epsilon = T^{-1}$ will improve the regret to $d^{2/3} T^{2/3}$ up to log factors. We add a section explaining this in detail (Appendix H) in the revised version.

Q2: Can the authors comment on the dependence in the regret of $\kappa^{-1}$ in the regret and whether it is optimal or realistic for common link functions?
A2: For general link functions, all previous works on generalized linear models suffer the same order of dependence on $\kappa^{-1}$ in their regret upper bounds. For some specific link functions, such as the logistic link function, [1] showed better dependence on $\kappa^{-1}$. Still, it is so far unknown to the community if $\kappa^{-1}$ for general link functions can be improved. We will add comments on this in the revised version.

Q3: BEXP3 seems to perform the best in your experiments. This seems a little confusing to me because the constructed environments seem to be stochastic and not adversarial. Can the authors comment on this?
A3: In principle, we don’t think it is surprising, because the adversarial setting strictly covers the stationary setting when the link function is linear. So BEXP3 should work at least as well as BETC, which is indicated by the regret upper bound. We believe this gap can be eliminated by carefully tuning the constant of each input parameter. Please see Appendix I for the additional experiment, where we show BETC performs better than BEXP3.

[1] Improved Optimistic Algorithms for Logistic Bandits, Faury et al., ICML 2020

Thank you for your feedback! We address your comments and questions as follows:

Q1: In algorithm 2 (adversarial setting), where does $\mu$ show up? How can it work without inferring $\mu$ at all and without assumptions 3.2/3.3?
A1: We would like to clarify that in the adversarial setting, we consider linear models rather than generalized linear models. In detail, we consider the linear link function is $\mu(x) = \frac{1}{2} + x$ in the adversarial setting, and it satisfies Assumption 3.2 with $\mu’(\cdot) = 1$ and Assumption 3.3 with $L_{\mu}=M_{\mu}=1$.

We will add comments on this in the revised version to avoid any misunderstanding.

Q2: Can you explain the novelty in your lower/upper bounds in the stochastic setting?
A2: One key observation in solving the stochastic setting is that, to estimate the Borda score, the most sample-efficient way is to query each pair uniformly. In the linear setting, this means we need to explore each direction in $\mathbb{R}^d$ uniformly well.

Converting this idea into the regret-minimization setting requires new techniques. For the lower bound, this leads to our design of good/bad arms. In the previous work [Saha et al 21], there are $K-1$ identical arms against one best arm. This design will not work in our setting as it leads to lower bounds sub-optimal in dimension $d$. The new construction of our lower bound is based on the hardness of identifying the best arm in the $d$-dimensional linear bandit model. To prove the lower bound, we first apply a new reduction step to restrict the choice of $i_t$. Then we bound from below the regret by the expected number of sub-optimal arm pulls.

For the upper bound, our hard instance construction already sheds light on the algorithm design (see comments below Theorem 4.1): to differentiate the best item from its close competitors, the algorithm must query the bad items to gain information. This means BETC algorithms should naturally be optimal and do not need further complication. To explore each direction in $\mathbb{R}^d$ uniformly, we adopt the G-optimal design to explore all directions efficiently.