  The $K$-armed dueling bandits problem, where the feedback is in the form of
noisy pairwise preferences, has been widely studied due its applications in
information retrieval, recommendation systems, etc. Motivated by concerns that
user preferences/tastes can evolve over time, we consider the problem of
dueling bandits with distribution shifts. Specifically, we study the recent
notion of significant shifts (Suk and Kpotufe, 2022), and ask whether one can
design an adaptive algorithm for the dueling problem with
$O(\sqrt{K\tilde{L}T})$ dynamic regret, where $\tilde{L}$ is the (unknown)
number of significant shifts in preferences. We show that the answer to this
question depends on the properties of underlying preference distributions.
  Firstly, we give an impossibility result that rules out any algorithm with
$O(\sqrt{K\tilde{L}T})$ dynamic regret under the well-studied Condorcet and SST
classes of preference distributions. Secondly, we show that $\text{SST} \cap
\text{STI}$ is the largest amongst popular classes of preference distributions
where it is possible to design such an algorithm. Overall, our results provides
an almost complete resolution of the above question for the hierarchy of
distribution classes.
