Skip to yearly menu bar Skip to main content


Poster

Regret Analysis for Continuous Dueling Bandit

Wataru Kumagai

Pacific Ballroom #5

Keywords: [ Bandit Algorithms ] [ Convex Optimization ] [ Stochastic Methods ]


Abstract: The dueling bandit is a learning framework where the feedback information in the learning process is restricted to noisy comparison between a pair of actions. In this paper, we address a dueling bandit problem based on a cost function over a continuous space. We propose a stochastic mirror descent algorithm and show that the algorithm achieves an $O(¥sqrt{T¥log T})$-regret bound under strong convexity and smoothness assumptions for the cost function. Then, we clarify the equivalence between regret minimization in dueling bandit and convex optimization for the cost function. Moreover, considering a lower bound in convex optimization, it is turned out that our algorithm achieves the optimal convergence rate in convex optimization and the optimal regret in dueling bandit except for a logarithmic factor.

Live content is unavailable. Log in and register to view live content