Regret Lower Bound and Optimal Algorithm in Dueling Bandit Problem

By Junpei Komiyama, Junya Honda, Hisashi Kashima, Hiroshi Nakagawa. 2015

112 citations recorded by the source corpus.

We study the $K$-armed dueling bandit problem, a variation of the standard stochastic bandit problem where the feedback is limited to relative comparisons of a pair of arms. We introduce a tight asymptotic regret lower bound that is based on the information divergence. An algorithm that is inspired by the Deterministic Minimum Empirical Divergence algorithm (Honda and Takemura, 2010) is proposed, and its regret is analyzed. The proposed algorithm is found to be the first one with a regret upper bound that matches the lower bound. Experimental comparisons of dueling bandit algorithms show that the proposed algorithm significantly outperforms existing ones.

Subfields: Computer Networks and Communications, Management Science and Operations Research, Reinforcement Learning

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Networks and Communications

In Management Science and Operations Research

In Reinforcement Learning

Citations in the corpus

Dueling RL: Reinforcement Learning with Trajectory Preferences (2021, methodology): “Towards these goals, several algorithms have been proposed (Ailon et al., 2014; Zoghi et al., 2014a; Komiyama et al., 2015; Gajane et al., 2015; Saha and Gopalan, 2018b, 2019).”
Bandit Algorithms (2020, background): “Several authors have worked on Bernoulli bandits and the asymptotics have been well-understood since the article by Lai and Robbins [1985]. The earliest version of the algorithm presented in this chapter is due to Lai [1987] who provided asymptotic analysis.”
Principled Reinforcement Learning with Human Feedback from Pairwise or K-wise Comparisons (2023, background): “…comparisons (Yue et al., 2012; Zoghi et al., 2014b; Yue and Joachims, 2009, 2011; Saha and Krishnamurthy, 2022; Ghoshal and Saha, 2022; Saha and Gopalan, 2018a; Ailon et al., 2014; Zoghi et al., 2014a; Komiyama et al., 2015; Gajane et al., 2015; Saha and Gopalan, 2018b, 2019; Faury et al., 2020).”
Preference-based Online Learning with Dueling Bandits: A Survey (2018, methodology): “3.1.10 Relative minimum empirical divergence Komiyama et al. (2015) assume that the preference matrix has a Condorcet winner, and pro-pose the Relative Minimum Empirical Divergence ( RMED ) algorithm that is inspired by the Deterministic Minimum Empirical Divergence ( DMED ) algorithm (Honda and…”
Efficient and Optimal Algorithms for Contextual Dueling Bandits under Realizability (2021, background): “The most frequently used benchmark is the Condorcet winner , which is an arm a ⋆ that beats all others on average [Yue et al., 2012; Zoghi et al., 2014, 2015b; Komiyama et al., 2015; Yue and Joachims, 2011].”
Active Evaluation: Efficient NLG Evaluation with Few Pairwise Comparisons (2022, methodology): “Since UCB Elimination is 507 complementary to Uncertainty-aware selection, we 508 apply both these algorithms together and observe 509 the lowest annotation complexity with a reduction 510 of 89.54% using Electra and 84.00% using Bleurt 511 over standard RMED.”
MergeDTS (2018, methodology): “[31] in terms of K logT , but it is not optimal in the sense that it has large constant coefficients.”
Optimal Algorithms for Stochastic Contextual Preference Bandits (2021, background): “Above notion of learner’s regret is motivated from the definition of classical K-armed dueling bandit regret introduced by [44] which is later adopted by the dueling bandit literature [46, 23, 3, 43, 45, 38, 31].”
Double Thompson Sampling for Dueling Bandits (2016, methodology): “Inspired by the insights from Condorcet dueling bandits, we also discuss how to refine the regret of D-TS in general Copeland dueling bandits.”