Non-Stationary Dueling Bandits
This work addresses the challenge of adapting to changing preferences in online learning for applications like recommendation systems, though it appears incremental as it builds on existing dueling bandits frameworks.
The paper tackles the non-stationary dueling bandits problem by proposing algorithms like Beat the Winner Reset and meta-algorithms DETECT and Monitored Dueling Bandits to minimize regret without prior knowledge of segment changes, achieving tightened bounds in stationary cases and providing regret bounds and a lower bound for non-stationary scenarios.
We study the non-stationary dueling bandits problem with $K$ arms, where the time horizon $T$ consists of $M$ stationary segments, each of which is associated with its own preference matrix. The learner repeatedly selects a pair of arms and observes a binary preference between them as feedback. To minimize the accumulated regret, the learner needs to pick the Condorcet winner of each stationary segment as often as possible, despite preference matrices and segment lengths being unknown. We propose the $\mathrm{Beat\, the\, Winner\, Reset}$ algorithm and prove a bound on its expected binary weak regret in the stationary case, which tightens the bound of current state-of-art algorithms. We also show a regret bound for the non-stationary case, without requiring knowledge of $M$ or $T$. We further propose and analyze two meta-algorithms, $\mathrm{DETECT}$ for weak regret and $\mathrm{Monitored\, Dueling\, Bandits}$ for strong regret, both based on a detection-window approach that can incorporate any dueling bandit algorithm as a black-box algorithm. Finally, we prove a worst-case lower bound for expected weak regret in the non-stationary case.