Author Response to Reviewer PcGb
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.