---
abstract: 'We formulate and study a novel multi-armed bandit problem called the *qualitative dueling bandit (QDB)* problem, where an agent observes not numeric but qualitative feedback by pulling each arm. We employ the same regret as the *dueling bandit* (DB) problem where the duel is carried out by comparing the qualitative feedback. Although we can naively use classic DB algorithms for solving the QDB problem, this reduction significantly worsens the performance—actually, in the QDB problem, the probability that one arm wins the duel over another arm can be *directly* estimated without carrying out actual duels. In this paper, we propose such direct algorithms for the QDB problem. Our theoretical analysis shows that the proposed algorithms significantly outperform DB algorithms by incorporating the qualitative feedback, and experimental results also demonstrate vast improvement over the existing DB algorithms.'
author:
- 'Liyuan Xu${}^{\dagger\ddagger}$'
- 'Junya Honda${}^{\dagger\ddagger}$'
- |
    Masashi Sugiyama${}^{\ddagger\dagger}$\
    \
    $\dagger$:The University of Tokyo $\ddagger$:RIKEN
bibliography:
- 'reference.bib'
title: Dueling Bandits with Qualitative Feedback
---

Introduction
============

Related Work
============

Problem Formulation {#sec:problem-formulation}
===================

Qualitative Dueling Bandit with the Condorcet Winner
====================================================

Qualitative Dueling Banidt with the Borda Winner {#sec:Borda_winner}
================================================

Experiments {#sec:Experiments}
===========

Conclusions
===========

Acknowledgements
================

LX utilized the facility provided by Masason Foundation. JH acknowledges support by KAKENHI 18K17998, and MS acknowledges support by KAKENHI 17H00757.

Preliminaries {#sec:Preliminaries}
=============

Proof of Theorem \[thm:thompson-condorcet-regret\] {#sec:Proof-of-thompson-condorcet-regret}
==================================================

Proof of Theorem \[thm:thompson-fails-borda\] {#sec:Proof-of-thompson-fails-borda}
=============================================

Proof of Theorem \[thm:UCB-borda-regret\] {#sec:Proof-of-Borda-regret}
=========================================

Proof of Theorem \[thm:borda-lower-bound\] {#sec:Proof-of-borda-lower-bound}
==========================================
