KLUCB Approach to Copeland Bandits
  Multi-armed bandit(MAB) problem is a reinforcement learning framework where
an agent tries to maximise her profit by proper selection of actions through
absolute feedback for each action. The dueling bandits problem is a variation
of MAB problem in which an agent chooses a pair of actions and receives
relative feedback for the chosen action pair. The dueling bandits problem is
well suited for modelling a setting in which it is not possible to provide
quantitative feedback for each action, but qualitative feedback for each action
is preferred as in the case of human feedback. The dueling bandits have been
successfully applied in applications such as online rank elicitation,
information retrieval, search engine improvement and clinical online
recommendation. We propose a new method called Sup-KLUCB for K-armed dueling
bandit problem specifically Copeland bandit problem by converting it into a
standard MAB problem. Instead of using MAB algorithm independently for each
action in a pair as in Sparring and in Self-Sparring algorithms, we combine a
pair of action and use it as one action. Previous UCB algorithms such as
Relative Upper Confidence Bound(RUCB) can be applied only in case of Condorcet
dueling bandits, whereas this algorithm applies to general Copeland dueling
bandits, including Condorcet dueling bandits as a special case. Our empirical
results outperform state of the art Double Thompson Sampling(DTS) in case of
Copeland dueling bandits.
