  We study the problem of non-stationary dueling bandits and provide the first
adaptive dynamic regret algorithm for this problem. The only two existing
attempts in this line of work fall short across multiple dimensions, including
pessimistic measures of non-stationary complexity and non-adaptive parameter
tuning that requires knowledge of the number of preference changes. We develop
an elimination-based rescheduling algorithm to overcome these shortcomings and
show a near-optimal $\tilde{O}(\sqrt{S^{\texttt{CW}} T})$ dynamic regret bound,
where $S^{\texttt{CW}}$ is the number of times the Condorcet winner changes in
$T$ rounds. This yields the first near-optimal dynamic regret algorithm for
unknown $S^{\texttt{CW}}$. We further study other related notions of
non-stationarity for which we also prove near-optimal dynamic regret guarantees
under additional assumptions on the underlying preference model.
