Regret Analysis for Continuous Dueling Bandit
The dueling bandit is a learning framework wherein the feedback information in the learning process is restricted to a noisy comparison between a pair of actions. In this research, 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( √ T log T )-regret bound under strong convexity and smoothness assumptions for the cost function. Subsequently, we clarify the equivalence between regret minimization in dueling bandit and convex optimization for the cost function. Moreover, when considering a lower bound in convex optimization, our algorithm is shown to achieve the optimal convergence rate in convex optimization and the optimal regret in dueling bandit except for a logarithmic factor.
The submitted paper presents a stochastic mirror descent algorithm for the dueling bandits problem defined in Yue & Joachims 2009. The paper gives a regret bound based on a regret definition established in the dueling bandits framework (where two nearly optimal arms have to be selected in order to minimize regret), an connects this result to convergence rates with respect to the optimality gap in convex optimization. The latter result is the most interesting contribution of the paper.
While the paper is self-contained and the reviewer could not find an error in the proofs (not being an expert in bandit learning), the paper could be improved considerably by putting it into the greater context of stochastic zero-order convex optimization. The gradient estimation approach given in Section 3.2 is reminiscent of work by Duchi et al. (2015). Optimal Rates for Zero-Order Convex Optimization: The Power of Two Function Evaluations. The convergence analysis given in the cited paper can also be interpreted as an expected regret bound for online bandit learning. How do the convergence rates compare? Earlier work on zero-order optimization by Ghadimi & Lan or Nesterov & Spokoiny is cited in this paper.
Furthermore, it would be nice to get a clearer picture how the presented work is different from related work in online bandit learning. Wouldn't the analysis of Yue & Joachims 2009 be easily extended to the setting of the paper by adding an appropriate proximal operator to their algorithm? Where does the assumption of linearity restrict Zhang et al.'s analysis to apply to the presented convex optimization framework?
Overall recommendation: The paper is certainly theoretically solid - a bit more explanation would not hurt and possible lead to wider reception of the presented work.