Piecewise-Stationary Dueling Bandits

Kolpaczki, Patrick; Hüllermeier, Eyke und Bengs, Viktor (11. September 2024): Piecewise-Stationary Dueling Bandits. In: Transactions on Machine Learning Research

Abstract

We study the piecewise-stationary dueling bandits problem with arms, where the time horizon consists of 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 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 or . We further propose and analyze two meta-algorithms, DETECT for weak regret and 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.

• Item Type: Journal article
• Form of publication: Publisher's Version
• Faculties: Mathematics, Computer Science and Statistics > Computer Science > Artificial Intelligence and Machine Learning
• Subjects: 000 Computer science, information and general works > 004 Data processing computer science
• ISSN: 2835-8856