ANACONDA: An Improved Dynamic Regret Algorithm for Adaptive Non-Stationary Dueling Bandits. (arXiv:2210.14322v1 [cs.LG])

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 …

algorithm anaconda arxiv